Using a linked list globally and File I/O

I've spent the whole day reading the book given to us by the University as well as tutorials all over the internet regarding linked lists. I'm not looking for a solution to my assignment, I'm looking for a better understanding in linked lists and a methodology.

The program we're making allows a person to edit a soldier database, by creating entries, finding and deleting one, printing them, and of course, loading that database on start-up from a file, and saving it back to it on demand. In order to be memory efficient, we need to use dynamic memory allocation, which means we need to keep the memory use down to the most essential as far as the database goes. So when we delete an entry, we must also free up the memory it used.

It's getting late and I'm getting pretty dizzy and anxious. I still have 2 weeks to find it out, but there's lots of studying to do and I wanted to get the assignment out of the way first, since I enjoy programming.

So here are the things I want cleared up, anyone who has some time available and could help, I'd respect it.

1. In order to start pointing .next pointers towards the next entry in the linked list, we need to have a first entry (the "head" as many tutorials call it.) Does that mean that I have to check if it's the first entry during the load from the file or during manual creation of an entry?
2. How will I be able to safely use the same linked list, the same data, in all the separate functions I write? I'm quite confused on this part.
3. What's the quickest way to File I/O regarding linked lists? Fixed size arrays/structures are easy, simple fread and fwrite with size of, but how can I go on reading the data off each node? Is it simpler than I'm thinking it is? Just a simple loop?

For a quick idea, here are the structure declarations. The rest of the code I'm reluctant to post, it's messy, it's incomplete, it's most probably wrong and does nothing right and could crash, only thing is it compiles right.

Code:

---

/* Initialize record structure for each soldier */
struct record {
        long int aa;
        char firstname[20];
        char lastname[30];
        char datein[11];
        char dateout[11];
        int freedays;
        int servicedays;
} soldiers[1];

/* Initialize nodes for linked list */
struct node {
        struct record        soldier;
        struct node*        next;
};

---

I'm following tutorials letter by letter, but my head has started spinning and I'm guessing most of the code I've written will go straight to the trash, especially since I began writing some functions based on just the record structure and not a linked list, and now I'm not sure how to get the data from soldiers to soldier without much fuss.

You never specified what type of linked list, single or double?

You're right, single linked list.

Quote:

---

1. In order to start pointing .next pointers towards the next entry in the linked list, we need to have a first entry (the "head" as many tutorials call it.) Does that mean that I have to check if it's the first entry during the load from the file or during manual creation of an entry?

---

When you create the HEAD, its .next entry is set to NULL.
When you add an object to the list you do set the .next of the head to the new object, and the .next of the new object to the old .next

Quote:

---

2. How will I be able to safely use the same linked list, the same data, in all the separate functions I write? I'm quite confused on this part.

---

Generally you write methods/functions that step through the list until they get to the last object, which will have its .next value set to NULL.

Quote:

---

3. What's the quickest way to File I/O regarding linked lists? Fixed size arrays/structures are easy, simple fread and fwrite with size of, but how can I go on reading the data off each node? Is it simpler than I'm thinking it is? Just a simple loop?

---

The QUICKEST way is to just write out the list one object at a time until you get to the end of the list, then close the file. This wastes a lot of space on the disk though, as you are also writing out all the data in the .next pointers, which will certainly be invalid when the data is loaded, and so must be handled correctly. There are MUCH BETTER ways of doing it, but they are more involved, both in development time, and in processing time.

To read the data on each node, just start at the head node, and itereate through each node until you get to the last one. Each iteration you can process the 'current' node.

Thanks for the general guidelines. Regarding 2, I meant to ask how can I correctly pass the linked list from main() to each function and back, making sure all changes are reflected and that every function has proper access to the list.

just pass a pointer to the head object. Since its a single linked list, the function shoudl stop processing when it gets to the last entry, denoted by ->next == NULL

Code:

---

void foo(LINKED_LIST* pList){
 
    do {
        // something
        pList->Stuff = NewStuff;

        pList = pList->next;
        } while (pList != NULL);
 
    return;
    }

---

if on the other hand you only want to process a single node, just pass the function a pointer to that node.

Code:

---

void foo(LINKED_LIST* pNode){
    // do somethign to pNode
    pNode->Stuff = OtherStuff && MoreStuff;

    return;
    }

---

Quote:

---

Originally Posted by Leftos

Thanks for the general guidelines. Regarding 2, I meant to ask how can I correctly pass the linked list from main() to each function and back, making sure all changes are reflected and that every function has proper access to the list.

---

Just pass the point to the node you want to modify. Since it's dynamically allocated, the changes will reflect in all the functions you use it in.
If you want to create a new node and assign it to a pointer from a function, you can use a pointer-to-pointer (type**).

Code:

---

typedef my_struct
{
        /* Data here */
        struct my_struct* pNext;
} mystruct;

int main()
{
        mystruct* pHead = /* Let's just say it's valid */;
        AddNewNode(pHead);
        return 0;
}

void AddNewNode(mystruct* pNextTo)
{
        mystruct* pNew = malloc( sizeof(mystruct) );
        mystruct* pNext = pNextTo->pNext ? pNextTo->pNext : NULL;
        pNextTo->pNext = pNew;
        pNew->pNext = pNext;
}

---

The new node will be inserted into the list and will be visible from main (pHead->pNext).

1. If I interpret your question correctly, then yes; the first node you set up will need to also be the head of the list.

2. All you need to do is pass around the head pointer. We can get to anywhere in the list just by chasing links from there.

3. As far as file I/O goes, I would guess that freading and fwriting should work.

Quote:

---

Originally Posted by Elysia

Just pass the point to the node you want to modify. Since it's dynamically allocated, the changes will reflect in all the functions you use it in.

---

More correctly, it's because the variable passed is a pointer, not an actual variable value. It's called pass by reference when you pass an address of a variable (like what you want to do), and it's called pass by value when you just pass a value of whatever you want to pass.

pass 'a' by value:
void func1(node a);

pass 'a' by reference:
void func2(node *a);

since malloc returns data with pointers, it is usually dealt with through pointers, but it's still not quite the same thing. You can pass a variable allocated on the stack to a pass-by-reference function by using the address-of operator:

node a;
func2(&a);

As far as printing the linked list out, I would encourage against using fread and fwrite if you are going to be outputting the node en mass.

You could simply count up all the nodes, output that number, and then output arrays of the data one after the other.

It may be a little slower, but it's more portable.

I'd stay away from calling it by reference since that may be confusing. Rather it's more by pointer or address or whatever you want to call it.
References are used in C++, not C (technically speaking).

I've had a long night's sleep, printed out the chapter on linked lists from cslibrary.stanford.edu, and gave it a long read. My understanding on linked lists an passing them from a function to the other is now better. As long as you give head by reference from main to any other function, you can push nodes onto it and do whatever else you wish.

On the same assignment, different question. Why doesn't the following work?

Code:

---

struct record {
        long int aa;
        char firstname[20];
        char lastname[30];
        char datein[11];
        char dateout[11];
        int freedays;
        int servicedays;
} soldiers;

...

        if(fread(soldiers, sizeof soldiers, 1, fp) != 1) {
                        printf("Den htan dynath h eisagwgh twn dedomenwn apo to arxeio.\n");
                        exit(1);
        };

---

It's giving me incompatible type for argument 1 of fread. Do I have to make soldiers into an array by using [1]?

You are passing the struct record to fread, you need to pass a pointer to it.

--
Mats

Code:

---

if(fread(&soldiers, sizeof soldiers, 1, fp) != 1) {

---

fread and fwrite takes a pointer to the data.

So now I know that I need to do this...

Code:

---

void printall (struct node** head)

---

...in order for the printall function to have access to the list. However, if I call printone from within printall and I want printone to have access to the same list as well, how do I declare printone, and how do I pass on head?

Code:

---

printone(struct node *n)

---

perhaps?

--
Mats

I've got it to compile past the incompatible pointer warnings (I use -Wall) by the following:

Code:

---

void printone (struct node** head, int i)

...

void printall (struct node** head)
{
      ...
      printone(&*head, i)
      ...
}

---

Is that form correct?

I would have thought that you do the loop through the linked list in printall, and printone is responsible for printing a particular node. Your model appears to imply that it's printing the "nth" element in the linked list, and presumably traverses the list every time.

"Pointer to incomplete type" would indicate that you don't have a "struct node" declared - perhaps it's called something else?

--
Mats

I saw that too, and I've changed the code. printall has the loop to go to the next node before handing "current" over to printone so that printtone can actually print the data in "current", the Nth node.

Another quick question though.

Code:

---

current->soldier = soldiers

---

works, while...

Code:

---

soldiers = current->soldier

---

doesn't. Why?

EDIT: Full code.

Code:

---

void printall(struct node** head)
{
        struct node* current = *head;
       
        printf("\n");
       
        while (current->next != NULL)
        {
                printone(&current);
                current = current->next;
        }
}

void printone(struct node** current)
{
        soldiers = current->soldier;
        printf("\n\n");
        printf("ASM: %ld", soldiers.aa);
        printf("Onomatepwnymo: %s", soldiers.firstname);
}

---

Quote:

---

Originally Posted by Leftos

I saw that too, and I've changed the code. printall has the loop to go to the next node before handing "current" over to printone so that printtone can actually print the data in "current", the Nth node.

Another quick question though.

Code:

---

current->soldier = soldiers

---

works, while...

Code:

---

soldiers = current->soldier

---

doesn't. Why?

EDIT: Full code.

Code:

---

void printall(struct node** head)
{
        struct node* current = *head;
       
        printf("\n");
       
        while (current->next != NULL)
        {
                printone(&current);
                current = current->next;
        }
}
Are you sure this is correct - I expect this to not print the final node.

void printone(struct node** current)
{
        soldiers = current->soldier;
        printf("\n\n");
        printf("ASM: %ld", soldiers.aa);
        printf("Onomatepwnymo: %s", soldiers.firstname);
}

---

---

What is soldiers - is it a global variable?

See also red comment above.

--
Mats

Let's go again.

Code:

---

/* Initialize record structure for each soldier */
struct record {
        long int aa;
        char firstname[20];
        char lastname[30];
        char datein[11];
        char dateout[11];
        int freedays;
        int servicedays;
} soldiers;

/* Initialize nodes for linked list */
struct node {
        struct record        soldier;
        struct node*        next;
};

void printall(struct node** head)
{
        struct node* current = *head;
       
        printf("\n");
       
        while (current != NULL)
        {
                printone(&current);
                current = current->next;
        }
}

void printone(struct node** current)
{
        soldiers = current->soldier;
        printf("\n\n");
        printf("ASM: %ld", soldiers.aa);
        printf("Onomatepwnymo: %s", soldiers.firstname);
}

---

Both node and record are globals. The "record" type "soldiers" structure is also global, and contains the data we want to insert into a new element or the data we want to print each time, while the linked list holding all the "soldiers" element travels by reference from function to function.

In printone, current isn't a pointer to node, it's a pointer to a pointer to node, so you'll have to dereference once: try (*current)->soldier.

Thanks, that worked. I hope everything goes well from here on now. And thanks to everyone who bothered to show up and reply.

Why do you use ** in those functions? Why not just one *?

Quote:

---

Originally Posted by Leftos

So now I know that I need to do this...

Code:

---

void printall (struct node** head)

---

...in order for the printall function to have access to the list. However, if I call printone from within printall and I want printone to have access to the same list as well, how do I declare printone, and how do I pass on head?

---

No you don't.
You only need ** if a function is going to modify a *. So in essence, taking a struct node** head means it's going to reassign the head * pointer, which it shouldn't.

Okay, well, the double asterisk is only needed when the called function is going to modify the linked list.

Any ways to delete an element from a single linked list? I'm confused as to how I'll set the previous element's pointer to point to the next element from the one deleted.

I tried the following but I get segmentation fault.

Code:

---

void delrec(struct node** head, int acount)
{
        int i;
        struct node* current = *head;
        struct node* todel;
       
        for (i=0;i<=acount-1;i++)
        {
                current = current->next;
        }
       
        todel = current->next;
        current->next = current->next->next;
        free(todel);
}

---

No it's not. It's already referencing the node, not a copy of it.

To delete, you would be able to delete the next, or pass a pointer to the node and the head, and delete it.

This is one of the places that a doubly linked list is useful.

robwhit, I based my code on the tutorials I found in this e-book. Pages 12 to 14 are what I based the double asterisk on. If they're wrong or I'm still wrong, please do tell.

Could this work?

Code:

---

void delrec(struct node** head, int acount)
{
        int i;
        struct node* current = *head;
       
        for (i=0;i<=acount-1;i++)
        {
                current = current->next;
        }
       
        current->soldier = current->next->soldier;
        current->next = current->next->next;
        free(current->next);
}

---

Nope. Segmentation fault. I obviously can't access current->next->soldier.

EDIT: SOLVED! Took a look here, and changed it only slightly for it to work with my code.

Code:

---

void delrec(struct node** head, int acount)
{
        int i;
        struct node* current = *head;
        struct node* previous = NULL;
       
        for (i=1;i<=acount-1;i++)
        {
                previous = current;
                current = current->next;
        }
       
        if (previous == NULL) *head = current->next;
        else previous->next = current->next;
        free(current);
}

---

The double asterisk is only needed if you want to be able to modify the head variable that you have in the calling code. It will still point to the same linked list.

You could do it that way, but gaining the extra level of indirection just to dereference it again is extraneous.

Singly linked lists don't have a previous member. edit: haha never mind that.

Suppose that you delete more than one node at a time. How many times would you have called malloc? How many times would you have called free? edit2: nevermind to that too...

I sense from what you're saying that there's something obviously wrong with my code, but could you elaborate?

nevermind, brain fart.

there are still a few things though:

for (i=0;i<=acount-1;i++)

this can be written as:

for (i=0;i<acount;i++)

and what is acount used for?

I assume the number in the list to delete. X numbers from head. That's what I gather from the code.

Oh ok, I get it. I'm used to seeing previous used in doubly linked lists and numbers being zero based, so that messed me up a little.

But when you enter in 0 for acount, it still deletes one. Is that what you want?

Deleting the first person on the list works fine, because we never enter the loop anyway, so it doesn't matter.

Here's the full code along with the process that calls it so that you can fully understand how it works.

Code:

---

void search(struct node** head, int afunc)
/* afunc: 0 = delete, 1 = print */
{
        int choice;
        long int aa;
        char lastname[20];
        int count = 0;
        struct node* current = *head;
       
        printf("\nAnazhthsh vash se:\n\n");
        printf("1. ASM\n");
        printf("2. Epitheto\n\n");
        printf("Epilogh: ");
        fflush(stdin);
        scanf("%1d", &choice);
       
        switch(choice)
        {
                case 1:
                printf("\nDwse ASM: ");
                scanf("%6ld", &aa);
                while (current != NULL && current->soldier.aa != 0) {
                        count++;
                        if (aa == current->soldier.aa) {
                                if (afunc == 1) {
                                        printone(&current, 0);
                                        printf("\n");
                                        fflush(stdin);
                                        getchar();
                                        return;
                                }
                                else goto delrecbreak;
                        }
                        current = current->next;
                }
                printf("Den vrethike o ASM pou dwsate.\n");
                case 2:
                printf("\nDwse epitheto: ");
                fflush(stdin);
                fgets(lastname, 20, stdin);
                lastname[strlen(lastname)-1] = '\0';
                while (current != NULL && current->soldier.aa != 0) {
                        count++;
                        if (strcmp(lastname, current->soldier.lastname) == 0) {
                                if (afunc == 1) {
                                        printone(&current, 0);
                                        printf("\n");
                                        fflush(stdin);
                                        getchar();
                                        return;
                                }
                                else goto delrecbreak;
                        }
                        current = current->next;
                }
                printf("Den vrethike stratiwths me to epitheto pou dwsate.\n");
        }
        delrecbreak:
        if (afunc == 0) delrec(&*head, count);
}

void delrec(struct node** head, int acount)
{
        int i;
        struct node* current = *head;
        struct node* previous = NULL;
       
        for (i=1;i<=acount-1;i++)
        {
                previous = current;
                current = current->next;
        }
       
        if (previous == NULL) *head = current->next;
        else previous->next = current->next;
        free(current);
}

---

And because I bet you don't really understand greeklish, what search() does is ask the user if he wants to search for a certain soldier via index or their surname, and depending on afunc (whether the user selected "search and delete" or "search and print" in the main menu), search prints the current soldier or passes their linked list "index" to delrec(), which goes to delete that record.

http://faq.cprogramming.com/cgi-bin/...&id=1043284351

yeah I'm not getting this. Could you post the whole program?

and is this for a homework assignment? do you have to use those function prototypes?

Yeah, this is a college assignment, our final assignment for "Procedural Programming: C". As I mentioned in the first post, we have to make a program that opens a database of soldiers and has their index, first name, last name, date that they entered the army, date they're getting out, number of days they're allowed out of the army, and number of days they've offered their services. I'm not good with army terminology in English, so that part may not be all that clear.

I'm using those function prototypes only because I want to. We could do it all in main() if we wanted, but we've learned how to use separate functions so they're expecting us to use them, a bit up to a lot.

I could post the whole assignment (it's unfinished anyway, only load, save, create entry, search and print, search and delete, print all work, the other two army specific functions I haven't even started yet) if you still want to, or I could explain the above procedure more.

As for fflush(stdin), I had it in my mind as a recommendation from another user around here, who obviously hadn't read the FAQ. So should I increase all array sizes by 1 to avoid them filling up? Or is there some other way that works both in Windows and UNIX in order to clear the standard input buffer?

For arrays - just don't go over bounds. No matter how many idexes you create in there, there's always a chance you'll do out of bounds, so do proper checking first.
And for second, you can use fgets and you don't have to worry about the input buffer at all, which is the preferred solution.

Well, I have flushes all over the create entry function, because either the scanf's or fgets' kept the \n character in their buffers and the next "get string" command got overriden with \n as input. What could I do to avoid such a thing happening?

fgets reads everything into the buffer and does not leave dangling newlines in the input buffer.
You don't like the newline? You can get rid of it by erasing the last element in a string array.

I'm already doing that, by insterting \0 in strlen-1. Let me check which function keeps the \n and I'll get back and edit.

EDIT: Found it. fgets following scanf is overriden.

Code:

---

        printf("\n");
        printf("Dwse ASM stratiwth (6 pshfia): ");
        scanf("%6ld", &soldiers.aa);
       
        printf("Dwse onoma stratiwth: ");
        fgets(soldiers.firstname, 20, stdin);
        soldiers.firstname[strlen(soldiers.firstname)-1] = '\0';

---

The fgets doesn't give me a chance to input at all.

Quote:

---

Using a linked list globally and File I/O

---

Hmm.. I finally read the title and it makes sense now. So many mistakes by me in one thread....

/me goes and sits in the corner now... :D

What kind of mistakes? I found your explanations pretty well-based.

Still, can anyone recommend me what course of action should I take in the above part of code so that the fgets command doesn't get overriden by what's remaining in the stdin buffer?

use fgets for ALL input
and than parse it with something like sscanf

Example, please?

http://faq.cprogramming.com/cgi-bin/...&id=1043284385

see OPTION 3 Read As A String and Convert

I'm getting annoyed with the newline problem. If anyone could provide a solution, please do so. Here's the code.

Code:

---

int main(int argc, char *argv[])
{
        int choice;
        char choice2[3];
       
        /* if (argc!=2) {
        printf("Usage: SOLDIERSDB <database>\n");
        exit(1);
        }
       
        struct node* head = loadfile(*argv[1]); */
        struct node* head = loadfile("soldiers");

        for(;;)
        {
                choice = menu();
                switch(choice)
                {
                        case 1:        create(&head); continue;
                        case 2:        search(&head, 0); continue;
                        case 3:        search(&head, 1); continue;
                        case 4:        printall(&head); continue;
                        case 5:        printf("5 not completed.");        continue;
                        case 6:        printf("6 not completed.");        continue;
                        case 7:        savedb(head, "soldiers"); continue;
                        /* Exit */
                        case 8:
                        printf("\nAll unsaved changes will be lost. Are you sure you want");
                        printf("\nto exit?\n");
                        fgets(choice2, 3, stdin);
                        choice2[strlen(choice2)-1] = '\0';
                        if (choice2=="y") break;
                        else continue;
                        /* Not a valid menu selection */
                        default:
                        continue;
                }
                break;
        }
        return 0;
}

int menu()
{
        int choice;
       
        printf("\nDialekste epilogh:\n\n");
        printf("1. Eisagwgh stratiwth\n");
        printf("2. Diagrafh stratiwth\n");
        printf("3. Ektypwsh stratiwth\n");
        printf("4. Ektypwsh olwn\n");
        printf("5. Epilogh twn N prwtwn stratiwtwn pou exoun dikaiwma na\n");
        printf("  paroun M meres adeia.\n");
        printf("6. Epilogh twn N prwtwn stratiwtwn gia yphresia\n");
        printf("7. Apo8hkeysh vashs dedomenwn.\n");
        printf("8. Exodos.\n");
        printf("\nEpilogh: ");
       
        fgets(tempbuf, 3, stdin);
        choice = atoi(tempbuf);       
        return choice;
}

---

Never mind the greeklish. I choose option 8 at the menu, but then even if I type y at the prompt to exit, the program just displays the menu again.

EDIT: This works:

Code:

---

fgets(choice2, 3, stdin);
choice2[strlen(choice2)-1] = '\0';
if (choice2[0]=='y' && choice2[1]=='\0') break;

---

You are using break/continue in a non-traditional way, and I don't think you actually mean to do it that way, as there is so little benefit and huge increase in confusion from it [in fact, I think most of your confusion stems from this].

Change ALL of your continue to break.

Then use do - while instead of for(;;), and set a flag based on your choice2 input.

However, you also compare choice2 with the string "y" - this will not work - choice2's location in memory will never ever match the string "y" [at least not and also function correctly with the fgets() that you are using]. You need to use strcmp or just use a compare of the first character of your string.

--
Mats

Code:

---

if (choice2=="y") break;

---

OK, so choice is char* and "y" is char*, so you're basically comparing pointer vs. pointer, and that's why it doesn't work.
If you need to compare a char against a char, you would do choice[n] = 'n' as you did. If you need to compare a string against another string, you need to use strcmp.