Thread: linked list problem

  1. #1
    Registered User
    Join Date
    Oct 2008
    Posts
    92

    linked list problem

    Hi everyone. I am having a trouble with linked list program. This program will read a file with names and store them in a two lists. Then I need to make a linked list and then write them back to the file, seems that the problem is inside of a while loop, I don't understand why it's not working

    Here is the code, thank you.
    Code:
    #include <stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #define CHARS 30
    #define NAMES 20
    
    
    int main(void)
    {
    	int count=-1;
    	int index1=0,index2=0, i=0;
    	char list1[NAMES][CHARS],list2[NAMES][CHARS];
    	//char *l1, *l2;
    	
    	struct NODE {
    	   char name[CHARS];
    	   struct NODE *next;
    	};
    	typedef struct NODE Node;
    	FILE *fp, *out;
    	Node* head;
    	Node *curr, *n;
    	head=(Node*)malloc(sizeof(Node));
    	curr=head;
    	//l1=list1;
    	//l2=list2;
    
    
    /* open the file and load the strings into 2 arrays  */
    	 if((fp=fopen("merge.dat","r"))==NULL)
    		 printf("Cannot open file fot reading");
    		//exit(1);
    	
    	 while (!feof(fp))
    	 {
    	   count++;
    	   fscanf(fp,"%s %s ",list1[count],list2[count]);
    	 }
    	 fclose(fp);
    
    /*copys names from both lists until one of the lists is finished*/
    	 while(index1<=count||index2<=count)
    	 { 
    		curr->next=(Node*)malloc(sizeof(Node));    /*allocate space for next node*/
    		curr=curr->next;						   /* point curr to new allocated space*/
    		 
    		if(strcmp(list1[index1], list2[index2])>0) /*compare list1 and list2*/
    		{
    			strcpy(curr->name, list1[index1]);
    			++index1;
    			//++l1;
    		}
    		if(strcmp(list1[index1], list2[index2])<0)
    		{
    			strcpy(curr->name, list2[index2]);
    			++index2;
    			//++l2;
    		}
    	 }
    
    
    /*finish off the list that isn't finished*/
    
    	 for(i=index1; i<=count; ++i)
    	 {
    		curr->next=(Node*)malloc(sizeof(Node));
    		curr=curr->next;
    			strcpy(curr->name, list1[index1]);	
    	 }
    
    	 for(i=index2; i<=count; ++i)
    	 {
    		curr->next=(Node*)malloc(sizeof(Node));
    		curr=curr->next;
    			strcpy(curr->name, list2[index2]);
    	 }
    
    	 curr->next=NULL; 
    	 curr=head;
    
    	 while(curr!=NULL)
    	{
    		 printf( "%s\n", curr->name);
    		 curr=curr->next;
    	}
    	
    /*writing list back to the file*/
    
    	if((out=fopen("merge.dat","w"))==NULL)
    		printf("Cannot open file for writing\n");
    	
    	while(curr!=NULL)
    	{
    		 fprintf(out, "%s\n", curr->name);
    		 curr=curr->next;
    	}
    
    	
    	fclose(out);
    
    	for (curr = head; curr != NULL; curr=n) 
    	{
                      n = curr->next;
                      free(curr);
                   }
    
    	return 0;
    
    }

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    seems that the problem is inside of a while loop
    You didn't actually say what the problem is, or which while loop you are suspicious of.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    Registered User
    Join Date
    Oct 2008
    Posts
    92
    Sorry, I think the problem is in this loop

    Code:
    while(index1<=count||index2<=count)
    	 { 
    		curr->next=(Node*)malloc(sizeof(Node));    /*allocate space for next node*/
    		curr=curr->next;						   /* point curr to new allocated space*/
    		 
    		if(strcmp(list1[index1], list2[index2])>0) /*compare list1 and list2*/
    		{
    			strcpy(curr->name, list1[index1]);
    			++index1;
    			//++l1;
    		}
    		if(strcmp(list1[index1], list2[index2])<0)
    		{
    			strcpy(curr->name, list2[index2]);
    			++index2;
    			//++l2;
    		}
    	 }

  4. #4
    Webhead Spidey's Avatar
    Join Date
    Jul 2009
    Posts
    285
    /*copys names from both lists until one of the lists is finished*/
    while(index1<=count||index2<=count)
    I have'n't read your entire code but heres a bug -

    The || operator evaluates to true even if one of two operands is false.
    hence (false || true) will evaluate to true.

    Since you want the loop to stop when either one is finished, you will have to use the && operator.

    Code:
    while(index1<=count && index2<=count)

  5. #5
    Registered User
    Join Date
    Oct 2008
    Posts
    92
    Quote Originally Posted by Spidey View Post
    I have'n't read your entire code but heres a bug -

    The || operator evaluates to true even if one of two operands is false.
    hence (false || true) will evaluate to true.

    Since you want the loop to stop when either one is finished, you will have to use the && operator.

    Code:
    while(index1<=count && index2<=count)
    Thank you.
    The problem did not go away yet

    .

  6. #6
    Webhead Spidey's Avatar
    Join Date
    Jul 2009
    Posts
    285
    Thank you.
    The problem did not go away yet
    Could you describe what exactly the problem is ?

  7. #7
    Registered User Cooloorful's Avatar
    Join Date
    Feb 2009
    Posts
    59
    At a glance...

    Quote Originally Posted by nynicue View Post
    Code:
    #include <stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #define CHARS 30
    #define NAMES 20
    
    
    int main(void)
    {
    	int count=-1;
    	int index1=0,index2=0, i=0;
    	char list1[NAMES][CHARS],list2[NAMES][CHARS];
    	//char *l1, *l2;
    	
    	struct NODE {
    	   char name[CHARS];
    	   struct NODE *next;
    	};
    	typedef struct NODE Node;
    	FILE *fp, *out;
    	Node *head = malloc(sizeof(Node));
    	Node *curr, *n;
    	curr=head;
    	//l1=list1;
    	//l2=list2;
    
    
    /* open the file and load the strings into 2 arrays  */
    	 if((fp=fopen("merge.dat","r"))==NULL)
    		 printf("Cannot open file fot reading");
    		//exit(1);
    	
    	 while (!feof(fp))
    	 {
    	   count++;
    	   fscanf(fp,"%s %s ",list1[count],list2[count]);
    	 }
    	 fclose(fp);
    
    /*copys names from both lists until one of the lists is finished*/
    	 while(index1<=count && index2<=count)
    	 { 
    		curr->next=malloc(sizeof(Node));    /*allocate space for next node*/
    
                    // You SHOULD check to make sure malloc didn't return a null pointer
    
    		curr=curr->next;						   /* point curr to new allocated space*/
    		 
    		if(strcmp(list1[index1], list2[index2])>0) /*compare list1 and list2*/
    		{
    			strcpy(curr->name, list1[index1]);
    			++index1;
    			//++l1;
    		}
    		if(strcmp(list1[index1], list2[index2])<0)
    		{
    			strcpy(curr->name, list2[index2]);
    			++index2;
    			//++l2;
    		}
    	 }
    
    
    /*finish off the list that isn't finished*/
    
    	 for(i=index1; i<=count; ++i)
    	 {
    		curr->next=(Node*)malloc(sizeof(Node));
    		curr=curr->next;
    			strcpy(curr->name, list1[index1]);	
    	 }
    
    	 for(i=index2; i<=count; ++i)
    	 {
    		curr->next=(Node*)malloc(sizeof(Node));
    		curr=curr->next;
    			strcpy(curr->name, list2[index2]);
    	 }
    
    	 curr->next=NULL; 
    	 curr=head->next;
    
    	 while(curr!=NULL)
    	{
    		 printf( "%s\n", curr->name);
    		 curr=curr->next;
    	}
    	
    /*writing list back to the file*/
    
    	if((out=fopen("merge.dat","w"))==NULL)
    		printf("Cannot open file for writing\n");
    	
    	while(curr!=NULL)
    	{
    		 fprintf(out, "%s\n", curr->name);
    		 curr=curr->next;
    	}
    
    	
    	fclose(out);
    
    	for (curr = head; curr != NULL;) 
    	{
                      cur = curr->next;
                      free(curr);
                   }
    
    	return 0;
    
    }
    Last edited by Cooloorful; 07-22-2009 at 06:33 PM.

  8. #8
    Registered User
    Join Date
    Oct 2008
    Posts
    92
    OK the problem is in a while loop (post #3) first if statements always skips and then it goes to the second if , and I don't understand why. Given to us file already sorted , but we still need to do comparation, so the first if suppose to be evaluated first and the linked list should be started with a name from list1[index1]. but because it skips only names from list2[index2] go to the linked list.

    BTW
    Code:
    while(index1<=count || index2<=count)
    it what I need the while loop needs to be evaluated untill names from any of these files copied to the linked list. And then I have a for loop where I finish off linked list and copy the name from a list1 or list2 that wasn't finished in a while loop

  9. #9
    Registered User
    Join Date
    Oct 2008
    Posts
    92
    Quote Originally Posted by Cooloorful View Post
    // You SHOULD check to make sure malloc didn't return a null pointer...
    I checked it doesn't return a null pointer.

  10. #10
    Registered User Cooloorful's Avatar
    Join Date
    Feb 2009
    Posts
    59
    Ok the || should be && and I see some ways to fix the "extra" node problem I saw at a quick glance. I need to know a few things first, since there are other sources for bugs in your program.

    What does your input data look like (i.e. is it single words delimited by a whitespace character)? Is this an assignment? I fail to see why this should be done with linked lists considering you have read the entire file into memory anyway.

    Quote Originally Posted by nynicue View Post
    I checked it doesn't return a null pointer.
    The end user does not have the luxury of a debugger to know why your program just crashed. You should still check.

  11. #11
    Registered User
    Join Date
    Oct 2008
    Posts
    92
    This is an assignment and we have to read file into char arrays and then put then into linked list and then write them back into the same file, the file looks like
    Code:
    Ariel, Brooks      Bob,Mccarthy
    Colin, Black       Deborah, McGail
    Eve, .....         Fred,.......
    and so on
    given names already sorted so we don't need to sort them but have to compare first to names in case to put them into the linked list (even if we know it sorted already)

    One more questions, why I can't use || if I need to run while untill names from one file are finished off.
    Thank you

  12. #12
    Registered User Cooloorful's Avatar
    Join Date
    Feb 2009
    Posts
    59
    Think about it this way.

    I have two lists. One with 5 names, the other with 7.

    I need to read entry #1,

    is 1 < 5 (yes) OR 1 < 7 (yes)
    --Proceed.
    is 2 < 5 (yes) OR 2 < 7 (yes)
    --Proceed.
    is 3 < 5 (yes) OR 3 < 7 (yes)
    --Proceed.
    is 4 < 5 (yes) OR 4 < 7 (yes)
    --Proceed.
    is 5 < 5 (no) OR 5 < 7 (yes)
    --Proceed.
    is 6 < 5 (no) OR 6 < 7 (yes)
    --Proceed.
    is 7 < 5 (no) OR 7 < 7 (no)
    --Stop looping.

    With AND
    s 1 < 5 (yes) AND 1 < 7 (yes)
    --Proceed.
    is 2 < 5 (yes) AND 2 < 7 (yes)
    --Proceed.
    is 3 < 5 (yes) AND 3 < 7 (yes)
    --Proceed.
    is 4 < 5 (yes) OR 4 < 7 (yes)
    --Proceed.
    is 5 < 5 (no) AND 5 < 7 (yes)
    --Stop looping.

    You don't want to buffer overflow. Given the way the data is organized how can you ever have index1 be greater than index2?

  13. #13
    Registered User
    Join Date
    Oct 2008
    Posts
    92
    I don't really understand. I am using strcmp to compare names in list1[index1] and list2[index2] at index 0 for alphabetical order , assume that list1[] goes first so, index1 now at index 1 and index2 still at index 0, then it compares list1[index] at index 1 and list2[index2] at index 0 , name from list2 goes to the linked list next and then index2 increaments on 1 and so on, is this not right?

  14. #14
    Registered User Cooloorful's Avatar
    Join Date
    Feb 2009
    Posts
    59
    I do not follow the logic of your comparisons at all, but I made a few minor changes to your code

    Code:
    #include <stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #define CHARS 30
    #define NAMES 20
    
    /* traditionally these declarations go out here... 
     * Your code wasn't *wrong* but it was bad form.
     */
    struct NODE {
       char name[CHARS];
       struct NODE *next;
    };
    typedef struct NODE Node;
    
    int main(void)
    {
      int count=-1;
      int index1=0,index2=0, i=0;
      char list1[NAMES][CHARS],list2[NAMES][CHARS] = {0};
      FILE *fp, *out;
      Node* head;
      Node *curr, *n;
      head=malloc(sizeof(Node));
      curr=head;
    
      /* open the file and load the strings into 2 arrays  */
      if((fp=fopen("merge.dat","r"))==NULL)
      {
        printf("Cannot open file fot reading");
        exit(1);
      }
      
       while (!feof(fp))
       {
         count++;
         fscanf(fp,"%s %s ",list1[count],list2[count]);
       }
       fclose(fp);
    
    /*copys names from both lists until one of the lists is finished*/
      while(index1 <count && index2 < count)
      { 
        int cmp = strcmp(list1[index1], list2[index2]);
    
        if(curr == NULL)
          exit(1);
    
        if(cmp>0) /*compare list1 and list2*/
        {
          strcpy(curr->name, list1[index1]);
          ++index1;
        } else if(cmp<0)
        {
          strcpy(curr->name, list2[index2]);
          ++index2;
        }
    
        curr->next=malloc(sizeof(Node));    /*allocate space for next node*/
        curr=curr->next;               /* point curr to new allocated space*/
      }
    
    
      /*finish off the list that isn't finished*/
      for(i=index1; i<count; ++i)
      {
        curr->next=(Node*)malloc(sizeof(Node));
        curr=curr->next;
        if(cur == NULL)
          exit(1);
        strcpy(curr->name, list1[i]);
      }
    
      for(i=index2; i<count; ++i)
      {
        curr->next=(Node*)malloc(sizeof(Node));
        curr=curr->next;
        if(cur == NULL)
          exit(1);
        strcpy(curr->name, list2[i]);
      }
    
      curr->next=NULL; 
      curr=head;
    
      for(cur=head; curr!=NULL; cur = cur->next)
        printf( "%s\n", curr->name);
      
      /*writing list back to the file*/
    
      if((out=fopen("merge.dat","w"))==NULL)
      {
        printf("Cannot open file for writing\n");
        exit(1);
      }
      
      for(cur=head; curr!=NULL; cur = cur->next)z
        fprintf(out, "%s\n", curr->name);
      
      fclose(out);
    
      for (curr = head; curr != NULL) 
      {
        cur = curr->next;
        free(curr);
      }
    
      return 0;
    
    }
    Last edited by Cooloorful; 07-22-2009 at 07:50 PM.
    wipe on -
    A slap on the hand is better than a slap on the face. A tragic lesson learned far too late in life.
    - wipe off

  15. #15
    Registered User
    Join Date
    Oct 2008
    Posts
    92
    Ooo I got this now, thank you. Can I ask what 'z' means in there
    Code:
    for(cur=head; curr!=NULL; cur = cur->next)z
    Thank you Cooloorful , now I see where problems were .
    It was very helpfull.

    One more question, why in a while loop space for the node must be allocated at the end of the loop after names were copied into curr->next? I thought that it needs to be allocated before....
    Last edited by nynicue; 07-22-2009 at 08:15 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help sorting a linked list. Beginner
    By scarlet00014 in forum C Programming
    Replies: 1
    Last Post: 09-27-2008, 06:16 PM
  2. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  3. Replies: 6
    Last Post: 03-02-2005, 02:45 AM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 06:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM