Help with linked list

This is a discussion on Help with linked list within the C Programming forums, part of the General Programming Boards category; Okay, I tested it and it works. I'll post the whole code in a short while. Now I have to ...

  1. #31
    Banned Troll_King's Avatar
    Join Date
    Oct 2001
    Posts
    1,784
    Okay, I tested it and it works. I'll post the whole code in a short while. Now I have to go back through the whole damn thing and readjust it. See the whole problem centered around feof reading the end of file. This solves the problem because it tells you how many records are in the file. That way you can design your loop to read the correct number of records and avoid reading end of file. So in about 45 minutes I'll post my linked list solution, but look at this, look up ftell and let me know if you get it.

    Code:
    	
      //seek to the end of the file
      fseek(fin,sizeof(List),SEEK_END);
      //size represents number of records in file
      long size = ( ftell(fin) / sizeof(List) ) - 1;

  2. #32
    Code Warrior
    Join Date
    Nov 2001
    Posts
    669
    I know that ftell returns a current position of file pointer, but I don't know why do you divide it with the size of the list. And why is that -1 there?
    Current projects:
    1) User Interface Development Kit (C++)
    2) HTML SDK (C++)
    3) Classes (C++)
    4) INI Editor (Delphi)

  3. #33
    Banned Troll_King's Avatar
    Join Date
    Oct 2001
    Posts
    1,784
    Divide by size of the list because the ftell returns how many records there are of the specified size, so if it return 5 records than it will be 5 * size of records. And in a structure that could mean 5 * n, where n would be the size of the structure, therefore to get the true number of records you have to divide by the size of the structure. Also the minus one is due to the fact that SEEK_END goes right to the end of file, so the minus 1 takes away the end of file records from the count.

    I almost have the example finished, infact I did have it completed but the ADT was a stack, where I think you will want a queue instead, than I ran into another snag but I'm almost out of it. The code will look fine.

    binary files are a real ***** because of the end of file. I had forgotten how much of a ***** it would be, a few more minutes. Do you understand how to get the record count after reading this?

  4. #34
    Banned Troll_King's Avatar
    Join Date
    Oct 2001
    Posts
    1,784
    Here is a linked list. For some reason I had to make it a stack implimentation. I was having trouble creating a queue using the bianry file and random access. Notice that I changed the name of the datafile. Change it if your file has a different extension. I wonder about that binary file. Where did you get if from? I think that if you need a queue than Salem will have to help or else someone else. Anway this works as a Linked List Stack.

    Code:
    # include <stdio.h>
    # include <stdlib.h>
    # include <ctype.h>
    # include <conio.h>
    
    
    typedef struct node_s
    {  
    	int Value;
    	struct node_s *link;
    }List;
    
    List * AddNode(FILE *,List *,int count);
    void OpenFile(FILE **fptr, char path[], char mode[]);
    void DisplayList(List*,int);
    
    int main()
    {
    	List *first = NULL;
    	FILE *fin = NULL;
    
    	//start at the first record
    	long rec_num = 0;
    
    	OpenFile(&fin,"c:\\data.txt","rb");
    
    	//seek to the end of the file
    	fseek(fin,sizeof(List),SEEK_END);
    	//size represents number of records in file
    	long size = ( ftell(fin) / sizeof(List) ) - 1;
    
    	for(rec_num = 0; rec_num < size; rec_num++)
    	{
    		first = AddNode(fin,first,rec_num);
    
    	}
    
    	DisplayList(first,rec_num);
    
    	return 0;
    }
    
    void OpenFile(FILE **fptr, char path[], char mode[])
    {
    	*fptr = fopen(path,mode);
    	if (*fptr == NULL) 
    	{
    		fprintf(stderr,"Error: File a:\\name?? is missing!\n");
    		exit(1);
    	}
    }
    
    List* AddNode (FILE *fin,List *first, int count)
    {
    	List *next = NULL;
    
    	next = (List *) malloc (sizeof(List));
    	next->link = NULL;
    
    	fseek(fin,sizeof(List) * count,SEEK_SET);
    	fread(next, sizeof(List), 1, fin);
    		
    	next->link = first;
    	first = next;
    	return first;
    
    }
    
    void DisplayList(List *start,int rec_num)
    {
    	int i;
    	for(i=0; i < rec_num; i++)
    	{
    		printf("%d\n",start->Value);
    		start = start->link;
    	}
    }

  5. #35
    Code Warrior
    Join Date
    Nov 2001
    Posts
    669
    Yes I understand that now. But another thing is bugging me. What is the difference between queue and stack implementation?
    Current projects:
    1) User Interface Development Kit (C++)
    2) HTML SDK (C++)
    3) Classes (C++)
    4) INI Editor (Delphi)

  6. #36
    Banned Troll_King's Avatar
    Join Date
    Oct 2001
    Posts
    1,784
    Diiference between a queue and a stack is the order that the records are stored in the list.

    BTW I have to write a Cobol test in 4 hrs so I don't want to spend any more time on this right now, but I though of something more that I wanted to add. Since with ftell you can discover how many records there are it would be easy enough to dynamically allocate an array of structures and use one call to fread to load that array.

    //Get size of datafile
    //dynamically allocate array of structures
    fread(array_of_structures, sizeof(List), size, fin);

  7. #37
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    The linked list implementations of a stack and queue are as follows...

    For a stack, you can only add elemenets to the beginning of the list, and can only remove elements from the beginning of the list.

    For a queue, you can only add elements to the end of the list, and can only remove elements from the beginning of the list. This is generally done by keeping two pointers, one for each end.
    Callou collei we'll code the way
    Of prime numbers and pings!

  8. #38
    Code Warrior
    Join Date
    Nov 2001
    Posts
    669

    Talking

    Ok, now I know the difference.

    Current projects:
    1) User Interface Development Kit (C++)
    2) HTML SDK (C++)
    3) Classes (C++)
    4) INI Editor (Delphi)

  9. #39
    Code Warrior
    Join Date
    Nov 2001
    Posts
    669
    Troll_King, I was trying with:

    "//Get size of datafile
    //dynamically allocate array of structures
    fread(array_of_structures, sizeof(List), size, fin);"

    but I got stucked. Please help.
    Current projects:
    1) User Interface Development Kit (C++)
    2) HTML SDK (C++)
    3) Classes (C++)
    4) INI Editor (Delphi)

  10. #40
    Banned Troll_King's Avatar
    Join Date
    Oct 2001
    Posts
    1,784
    a. We know how to get the file size already

    b. allocate an array of structures of 'size'

    List *array = (List*) malloc (sizeof (List) * size);

    c. Read stuctures into array of structures in one statement

    fread(array, sizeof(List), size, fin);


    Basically you are looking at something like that, than you can index the array for example:

    for(int i = 0; i < size; i++)
    printf("%d", array[i].Value);

    Something to that affect. I passed my Cobol test this afternoon but now I have to strive for a couple hours sleep before I go to work. I'm tired as hell. Totally overextended. Tommorow though I'll test this code if I have time.

  11. #41
    Registered User zahid's Avatar
    Join Date
    Aug 2001
    Posts
    532
    [ Never code before desk work ]
    -------------------------------------:-->
    A man who fears Nothing is the man who Loves Nothing
    If you Love Nothing, what joy is there in your life.
    =------------------------------------------------------= - I may be wrong.

  12. #42
    Banned Troll_King's Avatar
    Join Date
    Oct 2001
    Posts
    1,784
    A queue is not a problem to implement, but the code you gave here look okay from peeking at it. The actual difficulty is for some reason using 'random access' and fread would produce a situation where the fread call would read the end-of-file, and feof or ferror would not prevent it from reading end-of-file, therefore the fseek ... SEEK_END and ftell was used to know ahead of time how many records there were. Now I know in my sleep how to write a queue, but couldn't do it because EITHER the datafile was corrupt or else there was some difficulty with the end-of-file causeing disaster. I'm too burdened to look into it now, have too much work but I would indeed like to know the solution. Use the datafile provided and any code, make the list a queue. This would help. Maybe it is not difficult but for some reason this morning I was having trouble. I have written far to many ADT's using text files that the binary file was presenting problems that I'm not accustomed too. For sure there are several solutions.

  13. #43
    Code Warrior
    Join Date
    Nov 2001
    Posts
    669
    The actual difficulty is for some reason using 'random access' ...
    I don't know what random access are you talking about. If I use "!feof" and "fread" it will begin reading from the beggining of the file, right?

    Anyway, here is my solution for that 0. This function is called in the main function like this "start = ReadList(start, "data.txt");". But I must say that this is not a good solution.

    Code:
    List *ReadList (List *start, char File01[])
    {
    	List *New = NULL;
    	FILE *fin = NULL;
    	long size = 0, i = 0;
    
    	fin = fopen(File01, "rb");
    	fseek(fin, sizeof(List), SEEK_END);
    	size = ( ftell(fin) / sizeof(List) ) - 1;
    	rewind(fin);
    	while ( !feof(fin) )
    	{
    		New = (List *) malloc (sizeof(List));
    		fread(New, sizeof(List), 1, fin);
    		if (i < size)
    		{
    			(List *)New->link = start;
    			start = New;
    		}
    		i++;
    	}
    	fclose(fin);
    	return start;
    }
    Last edited by GaPe; 02-09-2002 at 10:46 AM.
    Current projects:
    1) User Interface Development Kit (C++)
    2) HTML SDK (C++)
    3) Classes (C++)
    4) INI Editor (Delphi)

  14. #44
    Banned Troll_King's Avatar
    Join Date
    Oct 2001
    Posts
    1,784
    (List *)New->link = start;

    Can be written as (without the cast):

    New->link = start;

    And is traditional to have this line right after you 'malloc' even if not manditory:

    New->link = NULL;

    Pass the size into the function so that you can use the size when you display the list. That size is needed in main unless you want to display the list from a call in ReadList, but that makes ReadList too unspecialized for my taste, again a matter of choice.

    No actually nothing has been solved but when I have time I'll investigate the problem I was having. I'll create my own binary file too. Alright no problem. Do what works for you and thanks for reminding me that I have not worked with binaries for a long time. BTW I meant random access because retrieving the size is done through random access and any time one works with fread/fwrite they are using functions that can perform random access, where as fscanf/fprintf are exclusively for sequential access.


    BTW This works too:
    Code:
    # include <stdio.h>
    # include <stdlib.h>
    # include <ctype.h>
    # include <conio.h>
    
    typedef struct node_s
    {  
    	int Value;
    	struct node_s *link;
    }List;
    
    void OpenFile(FILE **fptr, char path[], char mode[]);
    
    
    int main()
    {
    	FILE *fin = NULL;
    
    	OpenFile(&fin,"c:\\data.txt","rb");
    
    	//seek to the end of the file
    	fseek(fin,sizeof(List),SEEK_END);
    
    	long size = ( ftell(fin) / sizeof(List) ) - 1;
    	rewind(fin);
    	List *array = (List*) malloc (sizeof (List) * size); 
    
    	fread(array, sizeof(List), size, fin); 
    
    	for(long i = 0; i < size; i++) 
    		printf("%d ", array[i].Value); 
    
    	return 0;
    }
    
    void OpenFile(FILE **fptr, char path[], char mode[])
    {
    	*fptr = fopen(path,mode);
    	if (*fptr == NULL) 
    	{
    		fprintf(stderr,"Error: File a:\\name?? is missing!\n");
    		exit(1);
    	}
    }
    Last edited by Troll_King; 02-09-2002 at 03:30 PM.

Page 3 of 3 FirstFirst 123
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, 11:03 AM
  2. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 11:10 AM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 11: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, 11:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21