Thread: Linked list problem

  1. #1
    Registered User
    Join Date
    Dec 2012
    Posts
    6

    Linked list problem

    Hello everyone i am new to this forum. I am italian but I had to come to english forums becouse you can find more people to share your knowledge (and problems....) with.
    I am working on a command line program that helps you to manage a list of invited people to an event and check their confirmation and their +1 (that's how in itlay we say when you bring someone with you wich is not in the list, I gues it is the same in english). Of course the programm will have to save the data onto a file not to lose them at every run. In order for a better controll on the list i decided to use a dynamic linked list instead of a vector (as it was in the first version i wrote).
    Therefore i am now writing 4 functions that allows you to
    0 (not created yet) check for existing data file and, in that case, import data from file
    1 Receive the data from the imput to create a new list or just add a new invited
    2 save the data on the file
    3 print the data on the screen

    I defined the struct of the "invited" wich is:
    Code:
    struct Invitato{
        char nome[MAX];       // Means name
        char cognome[MAX];       // Means surmane
        int partecipa;              // Confirmed partecipation = 1, not confirmed = 0, Maybe = 2
        int uno;                    // The +1 i was talking about, same rules for partecipation
        struct Invitato *next;            // pointer to next element
    };
    typedef struct Invitato Invitato;
    Ok now i have the function number 1 wich add a new invited to the list or, if the list doesn't exist, create the list and add a new invited. As the function 0 has not been created yet it jalways creates a new list. the code is
    Code:
    Invitato *Inserisci_Invitato(Invitato *list){
        Invitato *ptmp;
        ptmp = list;
        
        while (ptmp != NULL){                    // Scorre la lista alla ricerca dell'ultima "cella", nel caso la lista sia vuota dovrebbe saltare l'operazione
            ptmp = ptmp->next;
        }
        
        ptmp=(Invitato *)malloc(sizeof(Invitato));
        ptmp->next = NULL;
    
        printf("Inserisci Nome: ");
        scanf("%s", ptmp->nome);
        printf("Inserisci Cognome: ");
        scanf("%s", &ptmp->cognome);
        printf("Partecipazione confermata?(1=si, 0=no 2=forse) ");
        scanf("%d", &ptmp->partecipa);
        printf("+1? (1=si, 0=no, 2=forse) ");
        scanf("%d", &ptmp->uno);
        printf("\n");
        
        
        return list;
    }
    I'll just stop here for the moment, becouse that doesn't work and o can't get the reason.... Sorry for code being in italian, i promise i'll start writing in english the next times but i didn't have time to translate everithing. Any help?

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Code:
    ptmp = list;
    Here you set ptmp to the start of the list
    Code:
        
    while (ptmp != NULL){                    // Scorre la lista alla ricerca dell'ultima "cella", nel caso la lista sia vuota dovrebbe saltare l'operazione
        ptmp = ptmp->next;
    }
    If there are no elements in your list, then the list variable is NULL, then ptmp is null and your loop never executes. If there are elements in the list, you walk ptmp down the list until you go off the end.
    Code:
    return list;
    Here you return the value of list, but you never update list, i.e. you never have a line like list = ...;.

    Usually, when dealing with inserting into a linked list, there are two cases. The first is inserting into an empty list, the second is inserting into a list with more than one element. I also use two pointers, one for the new node, one as a temp, to walk down the list. Pseudo code might look like:
    Code:
    new_node = malloc
    set new_node->nome, new_node->cognome, etc
    new_node->next = NULL
    if (list == NULL)
        list = new_node
    else
        walk ptmp to the last node in the list
        ptmp->next = new_node
    return list
    Note, when walking ptmp to the last node in the list, make sure you don't go off the end. That is, you want to stop when the next node after ptmp is null.

    Hope that clears things up a bit.

  3. #3
    Registered User
    Join Date
    Dec 2012
    Posts
    6
    Thank you for the amazingly answer's speed and precision. I changed the code and now it works, though I still don't get why it didn't work before, and I think that understanding is more important than everything. So i have a question: i had set up list = ptmp so they should have pointed the same location (NULL in this case) at the very beginning of the function.
    Then (after the loop that didn't run in this case because the list was empty) I had set the information in ptmp. Since i had already decleared that ptmp was equal to list, changing ptmp info shouldn't have changed list's as well?
    Example
    List -> NULL
    list = ptmp
    ptmp = NULL (the same null)
    Therefore if i change null with new info (name ecc.) i expected to have something like:
    ptmp->node->NULL
    therefore as ptmp was equal to list, also this
    list->node->NULL

    Why didn't it work? was it different from what i expexted it to be?

  4. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    So i have a question: i had set up list = ptmp so they should have pointed the same location (NULL in this case) at the very beginning of the function.
    This is not quite accurate, you never set list to anything, i.e. it is never on the left side of an assignment (= sign) expression. It's value in the function depends on what you pass in to the function. You do, however, set ptmp to point to list.

    Then (after the loop that didn't run in this case because the list was empty) I had set the information in ptmp. Since i had already decleared that ptmp was equal to list, changing ptmp info shouldn't have changed list's as well?
    No. You set ptmp to list. ptmp is just a pointer, so all you did was give it the same address as was stored in list. But you overwrote the address in ptmp when you did ptmp = malloc(...). That puts a new address (the one returned by malloc) into ptmp, so now it points somewhere different from list. You are changing different memory from what list points to.

    Here is your old code with comments as to what each line was actually doing:
    Code:
    Invitato *Inserisci_Invitato(Invitato *list){
        Invitato *ptmp;  // declare ptmp as a pointer to Invitato, it is an uninitialized pointer, pointing to a garbage address
        ptmp = list;  // now, make ptmp point to the same memory location as list.  When list is empty (null), ptmp points to null, otherwise it points to the first element in the list
    
    
        while (ptmp != NULL){  // this loop only stops when ptmp is NULL.  If the list is empty, it never executes.  If the list has items, it moves ptmp through the list and
            ptmp = ptmp->next;  // stops after ptmp has gone past the last node in the list
        }
    
    
        ptmp=(Invitato *)malloc(sizeof(Invitato));  // allocate space for a new node
        ptmp->next = NULL;  // set the new node's next pointer to NULL
    
    
        printf("Inserisci Nome: ");
        scanf("%s", ptmp->nome);  // read in the name
        printf("Inserisci Cognome: ");
        scanf("%s", &ptmp->cognome);  // read in the ?last? name
        printf("Partecipazione confermata?(1=si, 0=no 2=forse) ");
        scanf("%d", &ptmp->partecipa);  // read in the participation
        printf("+1? (1=si, 0=no, 2=forse) ");
        scanf("%d", &ptmp->uno);  // read in the "+1"
        printf("\n");
    
    
        return list;  // return list
    }
    Notice that nowhere in there did you change the value of list. That means that it will never get updated.

    Something I forgot to mention in my previous post: you should not cast the return value of malloc. Read this link: FAQ > Casting malloc - Cprogramming.com. A better way to malloc a struct is like this:
    Code:
    ptmp = malloc(sizeof(*ptmp));
    It is preferable to use *ptmp in the sizeof. *ptmp is the thing pointed to by ptmp, i.e. a Invitato object, so sizeof(*ptmp) is equivalent to sizeof(Invitato) here. This way the malloc call will always allocate the right amount of memory. Even if you change the type of the ptmp variable, you need only change the declaration, the malloc call still works.

    One more note: as a matter of good program design, a function should do one thing and do it well. The function that inserts a node into your list should not have any user IO in it. A better design would be to have a function called getInvitationInfo(), which allocates an Invitation structure, reads the input from the user and puts it in the allocated structure, then you pass the pointer to that structure to your insert function:
    Code:
    Invitato *getInvitationInfo(void)
    {
        Invitato *newNode;
    
        newNode = malloc(sizeof(*newNode));
        if (newNode) {  // only do this if malloc was successful, to avoid program crashing
            print "enter name"
            scanf("%s", p->nome);
            ...
            newNode->next = NULL;
        }
        return newNode;
    }
    
    Invitato *insertNode(Invitato *list, Invitato *newNode)
    {
        Invitato *ptmp;
    
        if (list == NULL) {
            list = newNode;
        }
        else {
            walk ptmp to the last node
            ptmp->next = newNode;
        }
        return list;
    }
    ...
    // perhaps somewhere in main, or in your menu function
    Invitato *newNode;
    newNode = getInvitationInfo();
    insertNode(list, newNode);
    Hope that clears everything up.

  5. #5
    Registered User
    Join Date
    Dec 2012
    Posts
    6
    Your clearness is amazing. Thank you very much. I got the point where i was wrong, i didn't know welll the malloc() function. I thought that
    Code:
    *ptmp = malloc(sizeof(*ptmp))
    was meant to put the new struct at the memory address pointed by ptmp, when now I discover that it is the opposite: ptmp is uptadeted to a new memory address: the one of malloc.
    Now everything you said in your first reply mekes perfectly sense. Thank you also for your style suggestion, i will certainly adoperate them.

  6. #6
    Registered User
    Join Date
    Dec 2012
    Posts
    6
    I am having another problem dealing with the list. Thank to your help the programm is being built almost clear, but there is a function that crushes. The function looks for the file with the data of the list of invited (elenco.txt) and is supposed to re-create a linked list with this data, so that you don't lose your linked list if you close the programm. The code is:
    Code:
    Invitato *Recupera_Lista(void){
        Invitato *list, *ptmp;
        FILE *fp;
        ptmp = list;                  // Save pointer to first node and set temp pointer for scaling various file's line
        
        
        if (!(fp=fopen("elenco.txt", "r"))){
            printf("ERRORE nell'apertura del file elenco.txt");          // Print error status
        }else{
            while (!feof(fp)){
                fscanf(fp,"%15s\t%20s\t%5d\7%5d\n", &ptmp->nome, &ptmp->cognome, &ptmp->partecipa, &ptmp->uno);
                ptmp= ptmp->next;
            } 
            fclose (fp); 
        } 
        
        return list;
        
    }
    i think it crushes on the fscanf function, i couldn't find many proper examples of the use of i,t so i re-adapted an example i found some days ago. Maybe it can be useful to know which function writes on the file so i am posting its code as well:
    Code:
    void Salva_Lista_Su_File(Invitato *list){
        FILE *fp;
    
        if (!(fp=fopen("elenco.txt","w")))  {                                // ELENCO.TXT
            printf("ERRORE nell'apertura del file elenco.txt\n\n");
        }else{
            while(list != NULL){
                fprintf(fp, "%15s\t%20s\t%5d\7%5d\n", list->nome, list->cognome, list->partecipa, list->uno);
                list = list->next;
            }
            printf("Dati scritti con successo\n");
        }
        fclose(fp);
    }

  7. #7
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Unfortunately, you can't store the pointers in the file. That is, you can't store the ->next element of your Invitato struct. Next time you run the program, there is no guarantee that the memory address will be the same. Also, you can't store the memory you allocated, so you must reallocate it when you read back in. That is, you must call malloc for each item you read from the file.

    1. Read this FAQ article: FAQ > Why it's bad to use feof() to control a loop - Cprogramming.com. I have an alternative to this below.
    2. In Salva_Lista_Su_File, you are currently calling fclose(fp) regardless of whether the file was opened successfully. If fopen fails, fp is NULL and fclose won't work. Move it inside the else block.


    I recommend reading a line from the file with fgets, the using sscanf to parse the line. Also, you should check the return value of fscanf/sscanf to make sure it read a line that contains correct data. Something like:
    Code:
    char buf[BUFSIZ];  // BUFSIZ is a constant defined in stdio.h
    while (fgets(buf, sizeof(buf), fp) != NULL) {
        newNode = malloc(sizeof(*newNode));
        if (sscanf(buf, "%15s\t%20s\t%d\t%d", newNode->nome, newNode->cognome, &newNode->partecipa, &newNode->uno) == 4) {
            newNode->next = NULL;  // this makes sure that when we insert the node, the list will still have a clear "end", i.e. a NULL pointer
            insertNode(list, newNode);
        }
        else {
            free(newNode);  // bad data, free the memory you allocated
        }
    }
    A few notes about the scanf functions:

    1. They return the number of items successfully scanned. You ask for 4 items (nome, cognome, partecipa and uno). If scanf returns any other value, then there is a problem, so you should not insert that data, thus free the malloc'ed node.
    2. You don't need the & for strings. You are giving newNode->nome, which is the name of an array, and the name of an array is already a pointer to the first element. Thus, no need for & on nome and cognome. You still need the & on partecipa and uno though.
    3. Why only 15 chars for nome and 20 for cognome? They are both declared to have MAX chars (what is MAX?). You should use one less than MAX, to save room for the null terminator required by C strings. For example, if MAX is defined as 20, then they both should be %19.

    EDIT: Oh, and as a side note, the correct term is "crash", not crush. "Crush" is to press, squeeze or smash. "Crash" is like when cars collide, or an airplane crashes.
    Last edited by anduril462; 12-12-2012 at 03:41 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem in Linked List
    By hqt in forum C Programming
    Replies: 1
    Last Post: 08-15-2011, 05:16 AM
  2. Linked List Problem
    By llinocoe in forum C Programming
    Replies: 1
    Last Post: 09-27-2008, 07:02 PM
  3. Replies: 6
    Last Post: 03-02-2005, 02:45 AM
  4. syntax linked list problem & struct problem
    By beely in forum C Programming
    Replies: 5
    Last Post: 11-11-2002, 09:14 AM
  5. Linked list problem
    By Eber Kain in forum C++ Programming
    Replies: 3
    Last Post: 04-18-2002, 12:12 PM