Linked list Segmentation

This is a discussion on Linked list Segmentation within the C Programming forums, part of the General Programming Boards category; Hi, I made a couple of functions using linked lists and I keep getting Segmentation fault error. can someone tell ...

  1. #1
    Registered User
    Join Date
    Feb 2006
    Posts
    21

    Linked list Segmentation

    Hi,

    I made a couple of functions using linked lists and I keep getting Segmentation fault error. can someone tell me why I am getting this error.

    My code is:

    Code:
      
    #include <stdio.h>
    #include<stdlib.h>
    
    typedef struct nodeTag{
     int value;
     struct nodeTag*link;
    }Node;
    
    //Inserting Last
    Node *insertNode(Node*head,int value){
      Node*newNode=(Node*)malloc(sizeof(Node));
      newNode->value=value;
      newNode->link=NULL;
      if(!head){ head=newNode;}
    
      else{
                 Node*temp=head;
                 while(temp->link){
    	temp=temp->link;
    	temp->link=newNode;
                  }
    
    
              }
       return newNode;
    }
    
    //Printing the list Contents
    void printList(Node *head){
       Node*temp=head;
       while(temp){
    	printf("%d",temp->value);
        temp=temp->link;
       }
    
    }
    
    //Inserting in the First
    Node* insertFirst(Node*head,int value){
      Node*newNode=(Node*)malloc(sizeof(Node));
      newNode->value=value;
      newNode->link=head;
      head=newNode;
      return head;
    
    }
    
    Node*insertSorted(Node*head,int value){
      Node* newNode=(Node*)malloc(sizeof(Node));
      if(head&&(head->value>value)){
    	   head=insertFirst(head,value);
       }
       else{
                  newNode->value=value;
                  newNode->link=NULL;
              }
        if(!head){
                     head=newNode;
         }
    
      else{
                Node*temp=head;
                while((temp->link)&&(temp->link->value<value))
    		temp=temp->link;
    		newNode->link=temp->link;
    		temp->link=newNode;
    
              }
    
       }
    
    
    int main()
    {
    Node*list;
     //Inserting Last
     list=insertNode(list,10);
     list=insertNode(list,15);
     list=insertNode(list,5);
     //Inserting First
     list=insertFirst(list,10);
     list=insertFirst(list,5);
     list=insertFirst(list,15);
     //Inserting sorted
     list=insertSorted(list,77);
     list=insertSorted(list,200);
     list=insertSorted(list,55);
    
    printList(list);
    
    }
    Last edited by daisy_polly; 03-17-2006 at 09:37 PM.

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,648
    you need to pass the address of 'head', otherwise whatever you do to it in the functions are performed on a copy.
    Code:
    #include <ip.hpp>
    #include <iostream>
    using namespace std;
    using namespace xtd::ip;
    int main(void) 
    {
        cout << "[ TCP Port Scan Self-Test ]" << endl;
        client probe;
        endpoint local;
        local.address = "127.0.0.1";
        local.protocol = IPPROTO_TCP;
        for(local.port = 0; local.port < (1 << 16); ++local.port)
        {
            if(probe.open(local))
                cout << "Listening: ";
            else
                cout << "No Response: ";
            cout << local.port << endl;
        }    
    }

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,434
    Code:
    #include <stdio.h>
    #include<stdlib.h>
    
    typedef struct nodeTag{
     int value;
     struct nodeTag*link;
    }Node;
    
    /* Inserting Last */
    Node *insertNode(Node*head,int value){
      Node*newNode=(Node*)malloc(sizeof(Node));
      newNode->value=value;
      newNode->link=NULL;
      if(!head){ head=newNode;}
    
      else{
        Node*temp=head;
        while(temp->link){
          temp=temp->link;
          temp->link=newNode;
        }
    
    
      }
      return newNode;
    }
    
    /* Printing the list Contents */
    void printList(Node *head){
      Node*temp=head;
      while(temp){
        printf("%d",temp->value);
        temp=temp->link;
      }
    
    }
    
    /* Inserting in the First */
    Node* insertFirst(Node*head,int value){
      Node*newNode=(Node*)malloc(sizeof(Node));
      newNode->value=value;
      newNode->link=head;
      head=newNode;
      return head;
    
    }
    
    Node*insertSorted(Node*head,int value){
      Node* newNode=(Node*)malloc(sizeof(Node));
      if(head&&(head->value>value)){
        head=insertFirst(head,value);
      }
      else{
        newNode->value=value;
        newNode->link=NULL;
      }
      if(!head){
        head=newNode;
      }
    
      else{
        Node*temp=head;
        while((temp->link)&&(temp->link->value<value))
          temp=temp->link;
        newNode->link=temp->link;
        temp->link=newNode;
    
      }
      /*!! what should be returned here? */
    }
    
    
    int main()
    {
      Node*list;  /*!! initialise to an empty list */
      /*Inserting Last*/
      list=insertNode(list,10);
      list=insertNode(list,15);
      list=insertNode(list,5);
      /*Inserting First */
      list=insertFirst(list,10);
      list=insertFirst(list,5);
      list=insertFirst(list,15);
      /*Inserting sorted*/
      list=insertSorted(list,77);
      list=insertSorted(list,200);
      list=insertSorted(list,55);
    
      printList(list);
      /*!! main returns 0 if all is well */
    }
    I get these warnings, you should also increase the warning level of your compiler
    Code:
    $ gcc -W -Wall -ansi -pedantic -O2 foo.c
    foo.c: In function ‘insertSorted’:
    foo.c:70: warning: control reaches end of non-void function
    foo.c: In function ‘main’:
    foo.c:77: warning: ‘list’ is used uninitialized in this function
    foo.c:91: warning: control reaches end of non-void function
    Oh, and read the FAQ on casting malloc in C - it's not necessary.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  4. #4
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    Oh, and read the FAQ on casting malloc in C - it's not necessary.
    Here it is: http://faq.cprogramming.com/cgi-bin/...&id=1043284351

    You should also free() your memory when you're done with it.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  5. #5
    Registered User
    Join Date
    Jan 2006
    Location
    Berkeley, Ca
    Posts
    195
    In addition to what others have said, there are a few other things that should be corrected.

    Code:
    /* Inserting Last */
    Node *insertNode(Node*head,int value){
      Node*newNode=(Node*)malloc(sizeof(Node));
    You should check malloc() for NULL.

    Code:
    /* Inserting in the First */
    Node* insertFirst(Node*head,int value){
      Node*newNode=(Node*)malloc(sizeof(Node));
    Again, check malloc() for NULL.

    In the function
    Code:
    Node*insertSorted(Node*head,int value)
    I would venture to say that you want to return head.

    On a side note, I would have just made a seperate function to make the nodes.

    Maybe something like

    Code:
    n_type *l_make(size_t count) 
    { 
        n_type *node, *list; 
    
        list = count ? malloc(sizeof *list) : NULL; 
        if (list != NULL) { 
            node = list; 
            while (--count != 0) { 
                node -> NEXT = malloc(sizeof *node -> NEXT); 
                if (node -> NEXT == NULL) { 
                    l_free(list); 
                    return NULL; 
                } else { 
                    node = node -> NEXT; 
                } 
            } 
            node -> NEXT = NULL; 
        } 
        return list; 
    
    
    
    }
    Then when I sort

    Code:
    n_type *n_sort(n_type *list, size_t count) 
    { 
        size_t half, other_half; 
        n_type *head, *tail, *sorted, **node; 
    
        if (count > 1) { 
            head = list; 
            other_half = half = count / 2; 
            while (--other_half != 0) { 
                head = head -> NEXT; 
            } 
            tail = head -> NEXT; 
            head -> NEXT = NULL; 
            tail = n_sort(tail, count - half); 
            head = n_sort(list, half);   
            node = GT(head, tail) ? &tail : &head; 
            sorted = list = *node; 
            *node = sorted -> NEXT; 
            while (*node != NULL) { 
                node = GT(head, tail) ? &tail : &head; 
                sorted = sorted -> NEXT = *node; 
                *node = sorted -> NEXT; 
            } 
            sorted -> NEXT = head != NULL ? head : tail; 
        } 
        return list; 
    
    
    
    }
    Of course this is just my biased opinion on the whole thing.

  6. #6
    Registered User
    Join Date
    Feb 2006
    Posts
    21
    thanks guys for the help. I made the changes you recommended to my code. I don't get the segmentation fault anymore but my "insertSorted" and "insertnode" functions do not give the correct output. Could someone please take a look and tell me what I am doing wrong.
    My Code:

    Code:
    #include <stdio.h>
    #include<stdlib.h>
    
    typedef struct nodeTag{
     int value;
     struct nodeTag*link;
    }Node;
    
    /* Inserting Last */
    Node *insertNode(Node*head,int value){
      Node*newNode=(Node*)malloc(sizeof(Node));
      newNode->value=value;
      newNode->link=NULL;
      if(!head){ head=newNode;}
    
      else{
        Node*temp=head;
        while(temp->link){
          temp=temp->link;
          temp->link=newNode;
        } }
    
    
    
      return newNode;
    }
    
    /* Printing the list Contents */
    void printList(Node*head){
      Node*temp=head;
      while(temp){
        printf("%d  " ,  temp->value);
    temp=temp->link;
      }
    
    }
    
    /* Inserting in the First */
    Node* insertFirst(Node*head,int value){
      Node*newNode=(Node*)malloc(sizeof(Node));
      newNode->value=value;
      newNode->link=head;
      head=newNode;
      return head;
    
    }
    
    Node*insertSorted(Node*head,int value){
      Node* newNode=(Node*)malloc(sizeof(Node));
      if(head&&(head->value>value)){
        head=insertFirst(head,value);
      }
      else{
        newNode->value=value;
        newNode->link=NULL;
      }
      if(!head){
        head=newNode;
      }
    
      else{
        Node*temp=head;
        while((temp->link)&&(temp->link->value<value))
          temp=temp->link;
        newNode->link=temp->link;
        temp->link=newNode;
    
      }
    return newNode;
    }
    
    
    int main()
    {
      Node*list=NULL;
    
     //Inserting Last
       list=insertNode(list,10);
       list=insertNode(list,15);
       list=insertNode(list,5);
       printList(list);
    
    
     /*Inserting First */
      list=insertFirst(list,12);
      list=insertFirst(list,13);
      list=insertFirst(list,14);
      printList(list);
    
      list=insertSorted(list,77);
      list=insertSorted(list,200);
      list=insertSorted(list,55);
      printList(list);
    
    }

  7. #7
    Registered User
    Join Date
    Jan 2006
    Location
    Berkeley, Ca
    Posts
    195
    Hmm.... really?

    Code:
    Node *insertNode(Node*head,int value){
      Node*newNode=(Node*)malloc(sizeof(Node));
    You are still casting malloc() and you still aren't checking malloc() for NULL;

    Code:
    void printList(Node*head){
      Node*temp=head;
      while(temp){
        printf("%d  " ,  temp->value);
    temp=temp->link;
      }
    
    }
    You forgot to insert a newline. This leads to undefined behavior. Including but not limited to printf() not printing. I'm pretty sure
    while(temp) should be while(temp !=NULL). Zero and NULL are not the same thing.

    Skipping down to main()

    Code:
    int main()
    It should be
    int main(void)

    Code:
    {
      Node*list=NULL;
    This doesn't seem right. Okay. I need to cut this short. My mom need her computer again.

    Yeah, you also forgot to return zero in main.

  8. #8
    Registered User
    Join Date
    Jan 2006
    Location
    Berkeley, Ca
    Posts
    195
    I think the problem with having list set to NULL is that when it encounters the following lines in your code:

    Code:
    Node *insertNode(Node*head,int value){
      Node*newNode=(Node*)malloc(sizeof(Node));
      newNode->value=value;
      newNode->link=NULL;
      if(!head){ head=newNode;}

    It will always fail. In this case both head and list point to the same thing. NULL. It would suggest the loop will always fail since you have

    if(!head)

    However, I don't have immediate access c compiler to verify this. With that, Now I'm off.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,292
    The two functions that are incorrect are returning newNode. But newNode is not the head of the list in every case, so obviously it wont work.

    Hint: You're allowed to have more than one return statement within a function.

  10. #10
    Registered User
    Join Date
    Feb 2006
    Posts
    21
    thanks a bunch I got it to work.

    Here is the working one:
    Code:
    #include <stdio.h>
    #include<stdlib.h>
    
    typedef struct nodeTag{
     int value;
     struct nodeTag*link;
    }Node;
    
    /* Inserting Last */
    Node *insertNode(Node*head,int value){
      Node*newNode=(Node*)malloc(sizeof(Node));
      newNode->value=value;
      newNode->link=NULL;
      if(head==NULL){
        head=newNode;
    }
      else{
    
      Node*temp=head;
    
    
        while(temp->link!=NULL){
            temp=temp->link;}
            temp->link=newNode;
    
    
       }
     return head;
    }
    
    
    
    
    /* Printing the list Contents */
    void printList(Node*head){
      Node*temp=head;
      while(temp){
        printf("%d  " ,  temp->value);
    temp=temp->link;
      }
    
    }
    
    /* Inserting in the First */
    Node* insertFirst(Node*head,int value){
      Node*newNode=(Node*)malloc(sizeof(Node));
      newNode->value=value;
      newNode->link=head;
      head=newNode;
      return head;
    
    }
    
    Node*insertSorted(Node*head,int value){
      Node* newNode=(Node*)malloc(sizeof(Node));
      if(head&&(head->value>value)){
        head=insertFirst(head,value);
      }
      else{
        newNode->value=value;
        newNode->link=NULL;
      }
      if(!head){
        head=newNode;
      }
    
      else{
        Node*temp=head;
        while((temp->link)&&(temp->link->value<value))
          temp=temp->link;
        newNode->link=temp->link;
        temp->link=newNode;
    
      }
    return head;
    }
    
    
    int main()
    {
      Node*list=NULL;
    
     //Inserting Last
       list=insertNode(list,10);
       list=insertNode(list,15);
       list=insertNode(list,5);
    
    /*Inserting First */
      list=insertFirst(list,12);
      list=insertFirst(list,13);
      list=insertFirst(list,14);
    
      list=insertSorted(list,77);
      list=insertSorted(list,200);
      list=insertSorted(list,55);
      printList(list);
    
    
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked List Not Saving Value as Int
    By bar338 in forum C Programming
    Replies: 4
    Last Post: 05-04-2009, 07:53 PM
  2. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  3. Anyone good with linked list.....I am not....
    By chadsxe in forum C++ Programming
    Replies: 11
    Last Post: 11-10-2005, 01:48 PM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 08:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21