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.

>>tok = strtok(buf, "\n");
instead try
>>tok = strtok(NULL, "\n");

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.

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.

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 :)

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!

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!

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.

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