Thread: linked list question

  1. #1
    Registered User
    Join Date
    Dec 2008
    Posts
    4

    linked list question

    Hello,

    I have this code here that I would like to use to construct two linked lists. one for students and one for courses..

    I had it working for just students, that is, before I tried to pass the head and end of the different lists to the init function. Now that I have two different lists, notice the head and end pointers for courses and students, I cannot get this to work. hints?

    Code:
     
    #include <stdio.h>
    #include <alloc.h>
    #include <stdlib.h>
    #include <conio.h>
    #include <ctype.h>
    #include <string.h>
     
    struct node * initnode( char *, int );
    void printnode( struct node * );
    void printlist( struct node * );
     
    struct node {
       char name[20];
       int  id;
       struct node *next;
       // struct course *myCourse;
    };
    
    //struct course {
    //   char courseID[7];
    //   struct course *next;
    //};
    
    
    struct node *studentHead = (struct node *) NULL;
    struct node *studentEnd = (struct node *) NULL;
    
    struct node *courseHead = (struct node *) NULL;
    struct node *courseEnd = (struct node *) NULL;
    
     
    struct node * initnode( char *name, int id )
    {
       printf("START INIT NODE......");
       struct node *ptr;
       ptr = (struct node *) calloc( 1, sizeof(struct node ) );
       if( ptr == NULL )    {                   /* error allocating node?      */
       printf("INIT NODE ERROR\n");
           return (struct node *) NULL;        /* then return NULL, else      */
           }
       else {                                  /* allocated node successfully */
           strcpy( ptr->name, name );          /* fill in name details        */
           ptr->id = id;                       /* copy id details             */
           printf("INIT NODE COMPLETE\n");
           return ptr;                         /* return pointer to new node  */
       }
    
    }
    
     
    
    void printlist( struct node *ptr )
    {
       printf("printing list...");
       while( ptr != NULL )           /* continue whilst there are nodes left */
       {
          printnode( ptr );           /* print out the current node           */
          ptr = ptr->next;            /* goto the next node in the list       */
       }
    }
    
    
    void printnode( struct node *ptr )
    {
    
       printf("\nName ->%s\n", ptr->name );
       printf("ID   ->%d\n", ptr->id );
    }
    
    
    void insertnode( struct node *newNode, struct node *phead, struct node *pend )
    {
       struct node *temp, *prev;                /* similar to deletenode      */
    
       if( phead == NULL ) {                     /* if an empty list,          */
           printf("set head and end... ");
           phead = newNode;                          /* set 'head' to it           */
           pend = newNode;
           phead->next = NULL;                   /* set end of list to NULL    */
           printf("done.\n");
           return;                              /* and finish                 */
       }
    
       temp = phead;                             /* start at beginning of list */
                          /* whilst currentname < newname to be inserted then */
       while( strcmp( temp->name, newNode->name) < 0 ) {
              temp = temp->next;                /* goto the next node in list */
              if( temp == NULL )                /* dont go past end of list   */
                  break;
       }
       
       if( temp == phead ) {
          newNode->next = phead;             /* link next field to original list   */
          phead = newNode;                   /* head adjusted to new node          */
       }
       else {     /* okay, so its not the first node, a different approach    */
          prev = phead;   /* start of the list, will cycle to node before temp */
          while( prev->next != temp ) {
              prev = prev->next;
          }
          prev->next = newNode;             /* insert node between prev and next  */
          newNode->next = temp;
          if( pend == prev )             /* if the new node is inserted at the */
             pend = newNode;                 /* end of the list the adjust 'end'   */
       }
    }
    
    
    
    main()
    {
       char name[20];
       char cname[10];
       int id;
       struct node *sPtr;
       struct node *crsPtr;
    
       
       printf("Enter student name ");
       scanf("%s", name );
       printf("Enter in id -- ");
       scanf("%d", &id );
       sPtr = initnode( name, id );
       insertnode( sPtr, studentHead, studentEnd);
    
       printf("Enter course name ");
       scanf("%s", cname );
       sPtr = initnode( cname, -1 );
       insertnode( sPtr, courseHead, courseEnd);   
       
       // now print
       printlist(studentHead);
       printlist(courseHead);
       
       system("pause");
       
    }

  2. #2
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    You have to pass the heads by reference not by value!

  3. #3
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Entire logic of the insertion sort can be put inside the while loop so I see no reason to break from within it and process the head, middle, end of the list separately (just my 2c). When adding to the end of the list you forgot to set the next pointer of newNode to NULL as:
    Code:
    if( pend == prev ) {          /* if the new node is inserted at the */
        pend = newNode;           /* end of the list the adjust 'end'   */
        pend->next = NULL;
    }

  4. #4
    Registered User
    Join Date
    Dec 2008
    Posts
    4
    Thank you for your time, I have tried that but continue to get errors.

    I tried to pass call insertnode like this:
    Code:
    insertnode( sPtr, &studentHead, &studentEnd);
    but still no dice.

    please illustrate.

    thank you again.

  5. #5
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    studentHead and studentEnd are pointers so your function call insertnode( sPtr, studentHead, studentEnd) is correct. Being global you don't even need to pass 'em as arguments to insertnode() as they are always there.

  6. #6
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    Yeah, my bad :S

    EDIT: Actually, not my bad. You still have to pass them by reference. Or not pass them at all. What you do is pass the value of the global variables...

  7. #7
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Quote Originally Posted by C_ntua View Post
    Yeah, my bad :S

    EDIT: Actually, not my bad. You still have to pass them by reference. Or not pass them at all. What you do is pass the value of the global variables...
    You're right, they need to be called by reference and the OP has 'em coded that way so no need to change the insertnode() call.

  8. #8
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    The correct insernode call is indeed this:
    Code:
    insertnode( sPtr, &studentHead, &studentEnd);
    and insertNode has to be changed like this:

    Code:
    void insertnode( struct node *newNode, struct node **phead, struct node **pend )
    {
       struct node *temp, *prev;                /* similar to deletenode      */
    
       if( *phead == NULL ) {                     /* if an empty list,          */
           printf("set head and end... ");
           *phead = newNode;                          /* set 'head' to it           */
           *pend = newNode;
           (*phead)->next = NULL;                   /* set end of list to NULL    */
           printf("done.\n");
           return;                              /* and finish                 */
       }
    .........
    }
    Btw, it would be better not to declare the variables global, since there in no sense doing so...

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by itCbitC View Post
    You're right, they need to be called by reference and the OP has 'em coded that way so no need to change the insertnode() call.
    Are we looking at the same function? I'm looking at
    Code:
    void insertnode( struct node *newNode, struct node *phead, struct node *pend )
    where the head and the end are most definitely not "passed by pointer", but by value.

  10. #10
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Quote Originally Posted by tabstop View Post
    Are we looking at the same function? I'm looking at
    I hope so
    Quote Originally Posted by tabstop View Post
    Code:
    void insertnode( struct node *newNode, struct node *phead, struct node *pend )
    where the head and the end are most definitely not "passed by pointer", but by value.
    In that function arent' phead and pend being passed as pointers to struct node type unless I don't understand what you're trying to say.

  11. #11
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by itCbitC View Post
    I hope so

    In that function arent' phead and pend being passed as pointers to struct node type unless I don't understand what you're trying to say.
    Yes. Since they are pointers to struct node type in the first place, that means they are being passed by value. If you wanted to pass them "by pointer", you would need to have a pointer to a pointer to a struct node.

  12. #12
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Ah! yes I see what you're talking about now.

  13. #13
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Quote Originally Posted by C_ntua View Post
    The correct insernode call is indeed this:
    Code:
    insertnode( sPtr, &studentHead, &studentEnd);
    What the OP currently has is correct too, besides you're adding an extra level of indirection which is unwarranted.

  14. #14
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by itCbitC View Post
    What the OP currently has is correct too, besides you're adding an extra level of indirection which is unwarranted.
    What the OP currently has will not insert a node into the beginning or end of a list, meaning that (among other things) it cannot create a list (an empty list passed in must needs be an empty list coming out, since the beginning or end cannot change).

  15. #15
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    That's correct for the parameters passed to insertnode() and it should return a value instead of nothing.

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. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  3. 1st Class LIST ADT
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 11-09-2001, 07:29 PM
  4. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM