# Question On Linked Lists

Printable View

• 10-15-2003
Zildjian
Question On Linked Lists
Hello,

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

Quote:

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:

Quote:

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.
• 10-15-2003
Hammer
>>tok = strtok(buf, "\n");
instead try
>>tok = strtok(NULL, "\n");
• 10-15-2003
Zildjian
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.
• 10-15-2003
Hammer
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.
• 10-15-2003
Zildjian
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 :)
• 10-22-2003
dalguy2004
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!
• 10-22-2003
dalguy2004
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!
• 10-22-2003
Zildjian
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.
• 10-23-2003
dalguy2004
LinkedList
Thanks man,
I figureed the problem out. I appreciate the info.