Thread: one way linked list

  1. #1
    Registered User Max's Avatar
    Join Date
    Jul 2002
    Posts
    110

    one way linked list

    I am trying to read text from a file
    The file has text written in that manner

    hello is
    my Sam
    name

    I want to store each of these words in a node in a one way linked list

    and insert each new node at the head of the list.

    I want to then print the linked list

    here is my code so far. I think I am pretty close...but something is missing and not working right such as the printing of the list.

    Any suggestions?


    Code:
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #define MAXLINES  10
    #define MAXRECORDS  10
    
    FILE *ifp;
    
    int main(void)
    {
    	int k;
    	const char ifn[]={"word.txt"};
    	char *t[MAXLINES];
    	char line[1+MAXLINES/2];
    
    	ifp=fopen(ifn,"r");
    	if (ifp==NULL)
    	{
    		perror(ifn);
    		exit(1);
    	}
    
    	for (k=0;k<MAXLINES;k++)
    	{
    		fgets(line, sizeof(line), ifp);
    		if (feof(stdin)) break;
    		strtok(line," ");
    	
    		t[k]=(char*)malloc(1+strlen(line));
    		
    		strcpy(t[k],line);
    		printf("%s",line);
    	}
    	
    	for (k=0;k<MAXLINES;k++)
    	{
            free(t);
    	}
    	
    	fclose(ifp);
    	
        return 0;
    }

  2. #2
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145

    Re: one way linked list

    First of all, that is not a linked list, but an array of strings .
    Originally posted by Max
    I am trying to read text from a file
    The file has text written in that manner

    hello is
    my Sam
    name

    I want to store each of these words in a node in a one way linked list

    and insert each new node at the head of the list.

    I want to then print the linked list

    here is my code so far. I think I am pretty close...but something is missing and not working right such as the printing of the list.

    Any suggestions?


    Code:
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #define MAXLINES  10
    #define MAXRECORDS  10
    
    FILE *ifp;
    
    int main(void)
    {
    	int k;
    	const char ifn[]={"word.txt"};
    	char *t[MAXLINES]; //You should nullify (set to NULL) all elements in this array, since it is not certain all elements gets allocated
    	char line[1+MAXLINES/2]; //Why do you divide by 2?
    
    	ifp=fopen(ifn,"r");
    	if (ifp==NULL)
    	{
    		perror(ifn);
    		exit(1);
    	}
    
    	for (k=0;k<MAXLINES;k++)
    	{
    		fgets(line, sizeof(line), ifp); //Should be sizeof - 1, since the NULL terminator needs one spot also. This only happens for words larger than or equal to the size.
    		if (feof(stdin)) break;
    		strtok(line," ");
    	
    		t[k]=(char*)malloc(1+strlen(line));
    		
    		strcpy(t[k],line); //Check if the allocation succeeds before attempting to write to it
    		printf("%s",line);
    	}
    	
    	for (k=0;k<MAXLINES;k++)
    	{
            free(t); //Always check if the pointer differs from NULL before attempting to deallocate it. Otherwise you will get runtime errors (most likely).
    	}
    	
    	fclose(ifp);
    	
        return 0;
    }
    Last edited by Magos; 11-20-2002 at 10:50 AM.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  3. #3
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    free(t); //Always check if the pointer differs from NULL before attempting to deallocate it. Otherwise you will get runtime errors (most likely).
    Not so, have a look here
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  4. #4
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    >fgets(line, sizeof(line), ifp); //Should be sizeof - 1, since the NULL terminator needs one spot also. This only happens for words larger than or equal to the size.

    Maybe I misunderstand the correction, but doesn't fgets already reserve room for the terminating null character?

  5. #5
    Registered User Max's Avatar
    Join Date
    Jul 2002
    Posts
    110
    Thanks Magos

    So basically by initiallizing the arrays to NULL I have now a linked list!!

    If i put a -1 in sizeof(line-1) I don't get all the words printed on the screen!!

    Also how do I check if the pointer differs from NULL before attempting to deallocate it.

    and how do I print all the nodes of the string in one column ie:

    hello
    my
    name
    is
    sam

    my programs now prints:
    hello is
    my sam
    name

    Here is my updated code:

    Code:
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #define MAXLINES  20
    
    FILE *ifp;
    
    int main(void)
    {
    	int k;
    	const char ifn[]={"word.txt"};
    	char *t[MAXLINES]={NULL};
    	char line[1+MAXLINES];
    
    	ifp=fopen(ifn,"r");
    	if (ifp==NULL)
    	{
    		perror(ifn);
    		exit(1);
    	}
    
    	for (k=0;k<MAXLINES;k++)
    	{
    		fgets(line, sizeof(line-1), ifp);
    		if (feof(stdin)) break;
    		
    		t[k]=(char*)malloc(1+strlen(line));
    		if (t[k]==NULL)
    		{
    			fprintf(stderr,"link1: no storage available\n");
    			break;
    		}
    		
    		strcpy(t[k],line);
    		printf("%s",line);
    	}
    	
    	for (k=0;k<MAXLINES;k++)
    	{
            free(t);
    	}
    	
    	fclose(ifp);
    	
        return 0;
    }

  6. #6
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Originally posted by Dave_Sinkula
    >fgets(line, sizeof(line), ifp); //Should be sizeof - 1, since the NULL terminator needs one spot also. This only happens for words larger than or equal to the size.

    Maybe I misunderstand the correction, but doesn't fgets already reserve room for the terminating null character?
    *Looking in the help files*

    True, it reads a max of n - 1 characters, not n as I thought.
    I stand corrected...
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  7. #7
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Originally posted by Max
    So basically by initiallizing the arrays to NULL I have now a linked list!!
    No, an array != linked list (see the picture below). An array is a chunk of continous memory with a static size. A linked list is data randomly spread in memory, but linked together with pointers (thus a linked list.
    Sure there are versions of linked lists stored in arrays too, but they can never have 'infinite' size as linked lists can (in theory that is).

    If i put a -1 in sizeof(line-1) I don't get all the words printed on the screen!!
    I meant sizeof(line) - 1, but it seems like fgets reserves one character for the NULL terminator, so it should be sizeof(line) as you used in the first place.

    Also how do I check if the pointer differs from NULL before attempting to deallocate it.
    Don't bother, as Hammer pointed out.

    and how do I print all the nodes of the string in one column ie:

    hello
    my
    name
    is
    sam

    my programs now prints:
    hello is
    my sam
    name
    fgets reads characters until newline is found, meaning that the whole first row is stored as your first element, the second row as the second element. I'm not an expert on 'formatting' input, so I'll leave this to the experts. I can only suggest read one character at a time until space or newline is found.
    Last edited by Magos; 11-20-2002 at 02:19 PM.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  8. #8
    Registered User Max's Avatar
    Join Date
    Jul 2002
    Posts
    110
    So how do I turn my program into a linked list?

  9. #9
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    Do a search for a few examples. Here's one for you to start with.

    You need a struct to be a node, and some functions to handle the insert, delete and traverse routines (and whatever else you want to do).
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  10. #10
    Registered User Max's Avatar
    Join Date
    Jul 2002
    Posts
    110
    OK here is my updated link list code. It compiles with no errors but it does not run....it freezes.

    I get the feeling it has to do with file IO...I am not reading words from the file correctly!!

    Any suggestions?

    Code:
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #define MAXLINES 10
    #define MAXWORDLENGTH 10
    
    FILE *ifp;
    
    struct word_link
    {
    	char word[MAXWORDLENGTH];
    	struct word_link *pnext;
    };
    
    int main(void)
    {
    	const char ifn[]={"word.txt"};
    	char line[1+MAXLINES];
    	struct word_link *phead,*pthis, *pnew;
    
    	
    	ifp=fopen(ifn,"r");
    	if (ifp==NULL)
    	{
    		perror(ifn);
    		exit(1);
    	}
    
    	phead=NULL;
    
    	for(;;)
    	{
    		fscanf(ifp,"%s", line);
    		if (feof(stdin)) break;
    		
    		if ((pnew=(struct word_link *)malloc(sizeof(struct word_link)) )==NULL)		
    		{
    			fprintf(stderr,"link1: no storage available\n");
    			exit(1);
    		}
    		
    		strcpy(pnew->word,line);
    			
    		pnew->pnext=phead;
    		phead=pnew;	
    	}
    
    	for(pthis=phead;pthis!=NULL;pthis=pthis->pnext)
    		printf("%p %s\n",pthis,pthis->word);
    
    	while(pnew !=NULL)
    	{
            free(pnew);
    	}	
    	
    	fclose(ifp);
    	
        return 0;
    }

  11. #11
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    This piece of code reads one character at a time from a file, filters out spaces and newline, then building words of the rest. You can modify it to fit your program.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MAX_LENGTH 64
    
    void ReadWords(char** Buffer, int MaxNrOfWords, char* FileName)
    {
       char TempBuffer[MAX_LENGTH];
       char C = ' ';
       int CurrentWord = 0;
       int CurrentLetter = 0;
       FILE* File;
    
       //Open the file
       if((File = fopen(FileName, "r")) == NULL)
       {
          return;
       }
    
       while((C != EOF) && (CurrentWord < MaxNrOfWords))
       {
          //Remove all spaces and newlines
          while((C == ' ') || (C == '\n'))
          {
             C = fgetc(File);
          }
    
          //Read the word
          CurrentLetter = 0;
          while((C != EOF) && (C != ' ') && (C != '\n') && (CurrentLetter < (MAX_LENGTH - 1)))
          {
             TempBuffer[CurrentLetter] = C;
             CurrentLetter++;
             C = fgetc(File);
          }
    
          //Add a terminator
          TempBuffer[CurrentLetter] = '\0';
    
          //Copy the data from the temporary buffer to the array of strings
          Buffer[CurrentWord] = (char*)malloc((strlen(TempBuffer) + 1) * sizeof(char));
          if(Buffer[CurrentWord] != NULL)
          {
             strcpy(Buffer[CurrentWord], TempBuffer);
             CurrentWord++;
          }
       }
    
       fclose(File);
    }
    
    int main()
    {
       const int MaxNrOfWords = 25;
       char** StringList = NULL;
    
       //Create a list of strings
       if((StringList = (char**)malloc(MaxNrOfWords * sizeof(char*))) == NULL)
       {
          return 0;
       }
    
       //Nullify all strings
       for(int i=0; i<MaxNrOfWords; i++) StringList[i] = NULL;
    
       //Read the words
       ReadWords(StringList, MaxNrOfWords, "Test.txt");
    
       //Print all words
       for(int i=0; i<MaxNrOfWords; i++)
       {
          if(StringList[i] != NULL)
          {
             printf("%s\n", StringList[i]);
          }
       }
    
       //Free memory
       for(int i=0; i<MaxNrOfWords; i++) free(StringList[i]);
       free(StringList);
    
       return 0;
    }
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  12. #12
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    Originally posted by Max
    OK here is my updated link list code. It compiles with no errors but it does not run....it freezes.
    Well, this bit is definately wrong:
    Code:
    while(pnew !=NULL)
    {
           free(pnew);
    }
    This is an example of a better approach:
    Code:
    struct Node *Current = Head;
    struct Node *tmp;
    
    while (Current)
    {
    	tmp = Current->Next;
    	free(Current);
    	Current = tmp;
    }
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  13. #13
    Registered User Max's Avatar
    Join Date
    Jul 2002
    Posts
    110
    My program works fine...I just had to fix the freeing of memory and the feof line...

    However, it is not the printing the words in order.

    Is this normal for a linked list...if not how can I print in the same order it reads from a file

    file has:

    hello is
    my sam
    name

    the program is printing:

    name

    my
    sam
    hello
    is

  14. #14
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    >>it is not the printing the words in order.
    Think carefully about how your code creates its link list, and how it traverses it. Draw it out on paper showing the links between each node, to get a better understanding.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  15. #15
    Registered User Max's Avatar
    Join Date
    Jul 2002
    Posts
    110
    Thanks all for your help!!!!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  2. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 09:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM