C problem - can't figure out how to assign a pointer to the beginning of a list

Question

I have a simple assignment that the professor wants us to do. Basically, to pull some numbers from a text file and load into a linked list. I do not want to understand the details in detail, but I have a basic question.

He provided us with this function:

INTLIST* init_intlist( int n ) { INTLIST *lst; lst = (INTLIST *)malloc(sizeof(INTLIST)); lst->datum = n; lst->next = NULL; return lst; } 

This function is used to initialize the linked list with the first element. Then he asked us to define a function with this signature:

 int insert_intlist( INTLIST *lst, int n ) 

So I assume that he just wants us to add to the linked list, so I tried this:

 int insert_intlist( INTLIST *lst, int n ) { INTLIST* lstTemp; lstTemp = (INTLIST *)malloc(sizeof(INTLIST)); lstTemp->datum = n; lstTemp->next = lst; lst = lstTemp; free(lstTemp); } 

So, what I thought was that it creates a temporary node, assigns a data value (Datum), and assigns the next pointer to indicate what the current pointer points to. Then I reassign the main pointer to this newly created temp node.

Thus, we have, for example, 2 nodes:

[New Temp Node] → [Prev Initialized Node]

When I look at the code, it looks great ...

Then basically I only have a function to print the list:

  while (lst!=NULL) { printf("The value is:%d", lst->datum); lst=lst->next; } 

The problem is that this only prints one digit (namely, the first digit that I read from the file, which, in my opinion, is the last on the list, or at least I thought it was the last on the list).

But it has to go on since I have 10 digits in the file. I know that the code is very dirty and I will clean it ... here is my main function if someone needs more information:

 #include <stdio.h> #include <stdlib.h> #include "intlist.h" int main(int argc, char *argv[]) { char c; /* Character read from the file. */ FILE* ptr; /* Pointer to the file. FILE is a structure defined in <stdio.h> */ int index=0; //INTLIST* aList[10]; //will use later /* Open the file - no error checking done */ ptr = fopen("1.txt","r"); /* Read one character at a time, checking for the End of File. EOF is defined in <stdio.h> as -1 */ if(ptr==NULL) { printf("Error: can't open file.\n"); /* fclose(file); DON'T PASS A NULL POINTER TO fclose !! */ return 1; } //aList[index] = malloc(sizeof(INTLIST)); WE NEED THIS LATER ON.... INTLIST *lst=NULL; while ((c = fgetc(ptr)) != EOF) { if (c != ' ') { //make sure it isnt a space int i = c - '0'; //get the value from the text file if(c=='\n') { // aList[index]=lst; // index++; // aList[index] = malloc(sizeof(INTLIST)); while (lst!=NULL) { printf("The value is:%d", lst->datum); lst=lst->next; } free(lst); free(aList[index]); return 0; //new line in the file //create another linked list } if (lst==NULL) lst = init_intlist(i); else insert_intlist( lst, i); } } fclose(ptr); system("PAUSE"); return 0; } 

Here is intlist.h for those you might need:

 #ifndef __intlist_h__ #define __intlist_h__ /* each entry in the list contains an int */ typedef struct intlist { int datum; struct intlist *next; } INTLIST; INTLIST *init_intlist( int n ); /* initializes the intlist with initial datum n */ int insert_intlist( INTLIST *lst, int n ); /* Inserts an int (n) into an intlist from the beginning*/ void list_append(INTLIST *list, void *datum); /* Inserts entry to the end of the list */ INTLIST* list_front(INTLIST *list); /*return the element at the front of the list, and remove it from the list*/ void list_map( INTLIST *list, void (*f)(void *) ); /*Applies a function to each element of the list */ void list_delete( INTLIST *list ); /* Deletes (and frees) all entries in the list */ #endif 

Answer 1

A few problems here.

I will start with a BAD error:

 int insert_intlist( INTLIST *lst, int n ) { INTLIST* lstTemp; lstTemp = (INTLIST *)malloc(sizeof(INTLIST)); lstTemp->datum = n; lstTemp->next = lst; lst = lstTemp; free(lstTemp); // <<<<< NO! } 

You are still using this memory, so you cannot free it.

---

Secondly, the prototype provided to you for insertion is not able to return a new front of the list, so you cannot change the front of the list. This means that you must add new nodes to the back, and not to the front, as you did.

Also, the return type of the int return value probably means that it expects the number of nodes in the list will not be a problem, since you have to go through the list to find back anyway.

Try again, you are not doing anything wrong.

Answer 2

Work with type code:

 int insert_intlist( INTLIST *lst, int n ) { INTLIST* lstTemp; lstTemp = (INTLIST *)malloc(sizeof(INTLIST)); lstTemp->datum = n; lstTemp->next = lst; lst = lstTemp; free(lstTemp); } 

This has a couple of problems. First of all, free(lstTemp) seems to free the node you just pasted into the list, which you probably don't want to do.

Secondly, you pass a pointer to a list in a function - this means that the function cannot change this pointer, so when you assign a pointer, you only change your local copy.

You have two options: you can either pass a pointer to that pointer (so that you can change the original pointer), or you can become smarter and figure out a way to avoid the need (but I won’t give away the secret right away ...)

Answer 3

This line:

 lst = lstTemp; 

Changes the value of lst inside a function. It will not extend back to the copy of the pointer that the caller has.

You can use pointer-to-pointer, or if you cannot change the signature of the function, insert somewhere except the head of the list.

Although the typical way to handle this is to not point to the first element in the list - rather, you have some kind of list structure that contains a pointer to the first element and some other information about the list (let's say how many elements it has). Then you pass a pointer to this structure around.

Answer 4

In C, the parameters are passed to the function "by value", that is, they are copied when you enter the function, and any changes you make are not returned back to the caller. This means that when you change lst to point to your newly allocated memory, it does not actually change the caller’s pointer to the list.

EDIT: As dmckee pointed out, you should not free memory in your insert function since you are still using it. This is definitely a mistake, but it is not the one that causes your problem.

Answer 5

In C, everything is passed by value. If you want the function to change something, you need to pass your address to the function. Since in int insert_intlist( INTLIST *lst, int n ) you want to change the list title, you need to pass a pointer to it, i.e. The first parameter should be INTLIST **lst (see below, too). But the prototype of the function is given and cannot be changed.

This means that you cannot add a number to the top of the list - the caller cannot know that you did it. So, you have to cross the list pointed to by lst and then add a new node anywhere along the chain. The professor probably wants you to add a node at the end, but he may have asked for a different condition.

With this information, let's look at the comments on the prototypes:

 /* Inserts an int (n) into an intlist from the beginning*/ int insert_intlist( INTLIST *lst, int n ); 

The comment or prototype is incorrect. If your professor gave you this file, insert_intlist() cannot be written to satisfy the comments, since it cannot return a new head to the caller. The prototype should be:

 /* Inserts an int (n) into an intlist from the beginning and returns the new head */ INTLIST *insert_intlist( INTLIST *lst, int n ); 

Or:

 /* Inserts an int (n) into an intlist from the beginning */ int insert_intlist( INTLIST **lst, int n ); 

(Note ** .)

The header also has:

 /*return the element at the front of the list, and remove it from the list*/ INTLIST* list_front(INTLIST *list); 

It is right. Note that you need to change the list title in list_front() so that you return a new head.

Finally, you do not want free() anything in insert_intlist() . You want to keep the new node in the list, right? Once the caller is with the list, he will need to call list_delete() , which will traverse the linked list and free each node.

Answer 6

I agree with Alok. I have the same problem / professor. I am new to C programming, and I have searched all over the Internet for C forms and C web pages for help. I came across a source that supports Aloka.

I used

INTLIST * list_add (INTLIST ** p, int i) {

 INTLIST *n; 

  n = (INTLIST *) malloc(sizeof(INTLIST)); if (n == NULL) return NULL; n->next = *p; /* the previous element (*p) now becomes the "next" element */ *p = n; /* add new empty element to the front (head) of the list */ n->datum = i; return p; } 

From my point of view, I can go over

INTLIST List *

list_add (& list, 1); list_add (& list, 2);

so when i print the list it prints 2 1

The professor suggested the following:

INTLIST * mylist [N];

Where N is the number of lines of your input file. Then mylist [i] is a pointer to the i-th linked list.

Good Good: create for testing purposes INTLIST * mylist [2];

I call the same functions:

list_add (& list [0], 1); list_add (& list [0], 2);

Will print 2 1 ... Great,

But when I do this:

list_add (& list [1], 3); list_add (& list [1], 4);

I get a segmentation error.