Thread: Question On Linked Lists

  1. #1
    Registered User
    Join Date
    Sep 2003
    Posts
    69

    Question On Linked Lists

    Hello,

    I'm working on a problem now that involves using Linked Lists. Input is as follows:

    CS1101 CS1100
    Ma1010 Ma1000
    CS2132 CS1100
    CS3132 CS2132
    CS3132 CS2140
    What I'm trying to do right now is put every single course into a linked list. Here is my code:

    Code:
     #include <stdio.h>
     #include <string.h>
     
     #define NODES_AT_ONCE 1000
     #define NAME_LENGTH 100
    
     struct node { char name[NAME_LENGTH];    struct node* next; };
     typedef  struct node    Node;
    
     static Node* freeList = NULL;
    
     void freeNode( Node* p ) { p->next = freeList;  freeList = p; }
    
     /* This is the memory allocation function.  */
     Node* newNode( char* s, Node* next) {
      Node * r = freeList;  int i;
      if ( freeList == NULL ) { /* then get space for some Nodes */
        freeList = (Node*)calloc(NODES_AT_ONCE, sizeof(Node));
        for(i = NODES_AT_ONCE - 1; i >= 0; i--) {
         freeList[i].next = r;
         r = &freeList[i];
        } 	/* the Nodes are linked together as the freeList. */
      }
      freeList = r->next;  strncpy(r->name, s, NAME_LENGTH);   r->next = next;
      return r; /* r points to the new Node which was removed from freeList */
     } 
       
     void output( Node* head ) { Node* p;
       for( p = head; p != NULL; p = p->next )
         printf( "%s ", p->name );
       printf("\n");
     }
     
     main() {
        // Lists of courses
        Node *crsHead = NULL, *crsTail = NULL, *noPreqHead, *noPreqTail, *crsPrintHead, 
             *crsPrintTail, *crsToPrintHead, *crsToPrintTail;
        char buf[BUFSIZ];
        char *tok;
        
        // Loop to put all courses into a linked list
        while ( fgets(buf, BUFSIZ, stdin) ) {
           tok = strtok(buf, " ");
           if (crsTail == NULL) crsHead = crsTail = newNode(strdup(tok),NULL);
           else crsTail = crsTail->next = newNode(strdup(tok),NULL);
           tok = strtok(buf, "\n");
           if (crsTail == NULL) crsHead = crsTail = newNode(strdup(tok),NULL);
           else crsTail = crsTail->next = newNode(strdup(tok),NULL);
        }
        
        output(crsHead);
     }
    Everything above main() was given to me, so it should be correct. When I run the program, the output shows:

    CS1101 CS1101 Ma1010 Ma1010 CS2132 CS2132 CS3132 CS3132 CS3132 CS3132
    What it appears to be doing is adding all the courses in the left column twice instead of adding one from the first column, then the one in the second column. Can someone see my error? Thanks.

  2. #2
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    >>tok = strtok(buf, "\n");
    instead try
    >>tok = strtok(NULL, "\n");
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  3. #3
    Registered User
    Join Date
    Sep 2003
    Posts
    69
    Thanks. Gotta love those little stupid mistakes! Now I'm trying to add the courses with no pre-requisites to a linked list. What I want to do is take every second element in the linked list, look for them in the odd positions (as the odd positions have pre-requisites) and, if it finds it there, then don't add it to the pre-req list. If it's not there, then I want to add it to the pre-req list, but only if it's not already there. Here is my code:

    Code:
    // Put all courses without pre-requisites into a linked list
        for (p = crsHead->next; p != NULL; p = p->next->next) {
           for (q = crsHead; q != NULL; q = q->next->next)
              if (strcmp(q->name,p->name) == 0) break;
           if (strcmp(q->name,p->name) != 0) {
              for (r = noPreqHead; r != NULL; r = r->next) {
                 if (strcmp(r->name,p->name) == 0) break;
                 else {
                    if (noPreqTail == NULL) noPreqHead = noPreqTail = newNode(p->name,NULL);
                    else noPreqTail = noPreqTail->next = newNode(p->name,NULL);
                 }
              }
           }
        }
    I get a segmentation fault when I do this and try to output the noPreq linked list. I think the problem might be in the second for loop when checking if the element in p is in the odd positions. What I think happens there is, if it goes all the way through the linked list without finding it, q should stay set at the last element? I don't know if that's how it works. Also, it might be a problem with ->next->next operation. Could this cause the loop to go over the end of the linked list? I wouldn't think so because it checks to see if p or q are null. Thanks for the help.

  4. #4
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    Code:
    for (p = crsHead->next; p != NULL; p = p->next->next) {
      for (q = crsHead; q != NULL; q = q->next->next)
        if (strcmp(q->name,p->name) == 0)
          break;
      if (strcmp(q->name,p->name) != 0) {
    Yeah, the next->next bit looks like it'll be a problem. if the first "next" is NULL, attempting to dereference it to get to the next next will land you in trouble (seq fault).

    Also, when the second loop terminates, it could end with q being NULL (as you test for q != NULL in the if statement). In that case, using q->next in the strcmp() will also give you grief.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  5. #5
    Registered User
    Join Date
    Sep 2003
    Posts
    69
    Alright, I'm going about this differently now and I've got the first part of it working right. I'm sure I'll be back with more questions though
    Last edited by Zildjian; 10-16-2003 at 07:15 AM.

  6. #6
    Registered User
    Join Date
    Sep 2003
    Posts
    22
    Ok, i'm having a problem like you zild, how do u populate the link list with the courses without prerequiste and the one with prerequsite.
    I tried it but i got a segmentation fault just like the one you got above..

    I mean getting read of the p->next->next, and the q->next->next

    Help!
    M

  7. #7
    Registered User
    Join Date
    Sep 2003
    Posts
    22
    Ok, i'm having a problem like you zild, how do u populate the link list with the courses without prerequiste and the one with prerequsite.
    I tried it but i got a segmentation fault just like the one you got above..

    I mean getting read of the p->next->next, and the q->next->next

    Help!
    M

  8. #8
    Registered User
    Join Date
    Sep 2003
    Posts
    69
    I decided to go about differently, so I wouldn't have to use the next->next thing. Sorry I can't really elaborate more. You might want to just put in an if statement to check that next->next is NULL or not, and then do something accordingly.

  9. #9
    Registered User
    Join Date
    Sep 2003
    Posts
    22

    LinkedList

    Thanks man,
    I figureed the problem out. I appreciate the info.
    M

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Question regarding comparing two linked lists
    By cyberfish in forum C++ Programming
    Replies: 2
    Last Post: 08-23-2007, 04:28 AM
  2. Linked Lists Question
    By panfilero in forum C Programming
    Replies: 4
    Last Post: 11-22-2005, 01:33 AM
  3. Linked Lists Question
    By SlyMaelstrom in forum C++ Programming
    Replies: 12
    Last Post: 11-12-2005, 12:03 PM
  4. eof in fstream & singly linked lists
    By mazo in forum C++ Programming
    Replies: 3
    Last Post: 06-03-2002, 09:50 AM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM