Thread: Linked list help

  1. #1
    Registered User
    Join Date
    May 2010
    Posts
    13

    Linked list help

    I am having trouble with a programming assignment in which I have to read a file, create a singly linked list, delete the nodes from the list, and print the modified list.

    My biggest problem so far is writing code that builds the list so far I have.

    Code:
    void bldList (FILE* spListData, struct node* ptLnkList)
    {
        struct node* ptNew;
        struct node* ptCur;
    
        while (!feof(spListData))
            {
                ptNew = (struct node*) malloc (sizeof(struct node));
                if (ptNew == NULL)
                   {
                       printf("Error allocating node.");
                       exit(201);
                   }
                
                fscanf(spListData, "%d%*c ", ptNew -> listEl);
    
                if (ptLnkList == NULL)
                    {
                        ptLnkList = ptNew;
                        ptNew -> link = NULL;
                    }            
                else
                    {
                        ptCur = ptLnkList;
                        while (ptCur != NULL)
                            {
                                ptCur = ptCur -> link;
                            }
                        ptCur -> link = ptNew;
                        ptNew -> link = NULL;
                    }
            }
    
        return;
    }
    The first problem is that, when I go to read the file, the program spontaneously quits. However, when I remove fscanf(spListData, "%d%*c ", ptNew -> listEl); from the code the program still spontaneously quit. As far as I can figure out the first part of the if-else statement, which insert a node into an empty list, but the program either segfault or loops infinitely, depending on condition in the while loop.

    If the condition is ptCur != NULL, it segfaults; if the condition is ptCur -> link != NULL, it loops infinitely. The former makes sense since there are references in the code to ptCur -> link after ptCur -> link has been assigned NULL. The latter, however, make little sense to me because the behavior of the program is governed by the outer while loop, which is dependent on feof() returning 0, which it apparently must do at some point if the file contains an EOF character.

    Any ideas?

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    You need to learn to use a debugger, at least enough to locate the offending code. If you have access to gdb, that will take you about 2 minutes:

    getting a segfault using pointers

    Anyway, most likely this is your problem:
    Code:
                        while (ptCur != NULL)
                            {
                                ptCur = ptCur -> link;
                            }
                        ptCur -> link = ptNew;
    Going by the while condition, you just assigned to a NULL pointer.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    Registered User GL.Sam's Avatar
    Join Date
    Aug 2009
    Posts
    88
    No error checking for fscanf(). That's the reason why it loops indefinitely, I assume.
    Last edited by GL.Sam; 05-16-2010 at 09:08 PM.
    The only good is knowledge and the only evil is ignorance.
    ~Socrates

  4. #4
    Registered User
    Join Date
    May 2010
    Posts
    13
    Quote Originally Posted by MK27 View Post
    You need to learn to use a debugger, at least enough to locate the offending code. If you have access to gdb, that will take you about 2 minutes:

    getting a segfault using pointers

    Anyway, most likely this is your problem:
    Code:
                        while (ptCur != NULL)
                            {
                                ptCur = ptCur -> link;
                            }
                        ptCur -> link = ptNew;
    Going by the while condition, you just assigned to a NULL pointer.
    Thank you for your answer, but that wasn't the only problem. When I assigned ptNew to ptCur instead of ptCur -> link, the program went into an infinite loop.

    The other solution was to change the while condition to while (ptCur -> link != NULL) so that the next reference to ptCur -> link does not create a "pointer from NULL". The program goes into a infinite loop, which leads me to think that it has something to do with how I am control the outer while loop.

  5. #5
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    That and the fact he is looping around feof(). The FAQ is pretty clear on why this should be avoided.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    To further the point, why don't you control your loop based on what fscanf returns?


    Quzah.
    Hope is the first step on the road to disappointment.

  7. #7
    Registered User
    Join Date
    May 2010
    Posts
    13
    Quote Originally Posted by claudiu View Post
    That and the fact he is looping around feof(). The FAQ is pretty clear on why this should be avoided.
    I understand why using feof() is not a a good choice for a control conditions. I've tried other conditions and they didn't work. For instance, fscanf(spListData, "%d%*c ", ptNew -> listEl) != EOF and fscanf(spListData, "%d%*c ", ptNew -> listEl) == 3 segfault.

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    while( fscanf() == WHATIEXPECTITTORETURN )
    {
        ...make new node...
        ...put what i scanned into it...
        ...link it to the list...
    }
    See, that wasn't hard, was it?


    Quzah.
    Hope is the first step on the road to disappointment.

  9. #9
    Registered User
    Join Date
    May 2010
    Posts
    13
    Quote Originally Posted by quzah View Post
    Code:
    while( fscanf() == WHATIEXPECTITTORETURN )
    {
        ...make new node...
        ...put what i scanned into it...
        ...link it to the list...
    }
    See, that wasn't hard, was it?


    Quzah.
    Maybe I'm implementing it wrong.

    Code:
    void bldList (FILE* spListData, FILE* spModList, struct node* ptLnkList)
    {
        int i;
        struct node* ptNew; //pointer to new node
        struct node* ptCur; //pointer to current node
    
        i = fscanf(spListData, "%d%*c ", &ptNew -> listEl);
        
        while (i == 2)
            {
                ptNew = (struct node*) malloc (sizeof(struct node));
                if (ptNew == NULL)
                   {
                       fprintf(spModList,"Node not allocated.");
                       exit(201);
                   }
    
    
                if (ptLnkList == NULL)
                    {
                        ptLnkList = ptNew;
                        ptNew -> link = NULL;
                    }
                else
                    {
                        i = fscanf(spListData, "%d%*c ", &ptNew -> listEl);
                        ptCur = ptLnkList;
                        while (ptCur != NULL)
                            {
                                ptCur = ptCur -> link;
                            }
                        ptCur = ptNew;
                        ptNew -> link = NULL;
                    }
            }
    
        return;
    }

    Code:
    void bldList (FILE* spListData, FILE* spModList, struct node* ptLnkList)
    {
        struct node* ptNew; //pointer to new node
        struct node* ptCur; //pointer to current node
    
        while (fscanf(spListData, "%d%*c ", &ptNew -> listEl) != EOF)
            {
                ptNew = (struct node*) malloc (sizeof(struct node));
                if (ptNew == NULL)
                   {
                       fprintf(spModList,"Node not allocated.");
                       exit(201);
                   }
    
    
                if (ptLnkList == NULL)
                    {
                        ptLnkList = ptNew;
                        ptNew -> link = NULL;
                    }
                else
                    {
                        ptCur = ptLnkList;
                        while (ptCur != NULL)
                            {
                                ptCur = ptCur -> link;
                            }
                        ptCur = ptNew;
                        ptNew -> link = NULL;
                    }
            }
    
        return;
    }
    Both of these codes segfault at the first fscanf() call.

  10. #10
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    That's because you're not paying attention to what you're doing.
    Code:
    int scanhere = 0;
    
    while( fscanf( "%d%*c ", &scanhere ) == 1 )
    {
        newnode = malloc( sizeof *newnode );
        if( newnode )
        {
            nednode->data = scanhere;
            ...link it up...
        }
    }
    Of course your version would sefgault. You're scanning to randomly pointing pointers, and pretending you're actually allowed to go there.


    Quzah.
    Hope is the first step on the road to disappointment.

  11. #11
    Registered User
    Join Date
    May 2010
    Posts
    13
    Quote Originally Posted by quzah View Post
    That's because you're not paying attention to what you're doing.
    Code:
    int scanhere = 0;
    
    while( fscanf( "%d%*c ", &scanhere ) == 1 )
    {
        newnode = malloc( sizeof *newnode );
        if( newnode )
        {
            nednode->data = scanhere;
            ...link it up...
        }
    }
    Of course your version would sefgault. You're scanning to randomly pointing pointers, and pretending you're actually allowed to go there.


    Quzah.
    Thank you for your help.

    I'm sorry for my carelessness. I understand that it is very difficult to try to help people who don't seem to be considering the consequences of their actions.

    I did originally point out that I thought the problem of the infinite loop was in the outer while loop and that the segfault was due to trying to get NULL to point somewhere, which was of course a stupid mistake.

    Now, however, I don't understand why the suggested code creates an empty list, especially since I fixed the problem with the segfault and the control condition.

  12. #12
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    It's not difficult, it is just better in the long run if I can get you to figure out the answer, rather than just hand the answer to you.

    The reason you're getting an empty list is probably because you need to be passing a pointer to a pointer, not just a pointer. Anything you change inside a function, that you want to keep outside the function, needs a pointer to that type. So if you want to change what a pointer points at, you have to pass the address of that pointer to the function.


    Quzah.
    Hope is the first step on the road to disappointment.

  13. #13
    Registered User
    Join Date
    May 2010
    Posts
    13
    Quote Originally Posted by quzah View Post
    It's not difficult, it is just better in the long run if I can get you to figure out the answer, rather than just hand the answer to you.
    Oh, I didn't mean to imply that it was difficult. It's just that I've been at it for a very long time today, and sometimes makes me miss very basic things.

    And I do appreciate that you want me to figure it out on my own.

    Quote Originally Posted by quzah View Post
    The reason you're getting an empty list is probably because you need to be passing a pointer to a pointer, not just a pointer. Anything you change inside a function, that you want to keep outside the function, needs a pointer to that type. So if you want to change what a pointer points at, you have to pass the address of that pointer to the function.
    Thanks for the advice. I'll try it.

  14. #14
    Registered User
    Join Date
    May 2010
    Posts
    13
    I'm beginning to think that I just don't understand how pointers work as well as I thought I did.

    The way I implemented the suggestion that I pass a pointer to a pointer to the linked list segfault, and I'm not sure exactly why:

    Code:
    struct node** bldList (FILE* spListData, FILE* spModList, struct node** ptPtLnkList);
    
    int main (void)
    {
        struct node* ptLnkList;
        struct node** ptPtLnkList;
        FILE* spModList;
    
        *ptPtLnkList = NULL;
    
        return 0;
    }
    
    struct node** bldList (FILE* spListData, FILE* spModList, struct node** ptPtLnkList)
    {
        int scanned;
        struct node* ptNew;
        struct node* ptCur;
        
        while (fscanf(spListData, "%d%*c ", &scanned) == 1)
            {
                ptNew = (struct node*) malloc (sizeof(struct node));\
                
                if (ptNew == NULL)
                   {
                       printf("Node not allocated.");
                       exit(201);
                   }
    
                if (*ptPtLnkList == NULL)
                    {
                        *ptPtLnkList = ptNew;
                        ptNew -> link = NULL;
                    }
                else
                    {
                        ptCur = *ptPtLnkList;
                        while (ptCur -> link != NULL)
                            {
                                ptCur = ptCur -> link;
                            }
                        ptCur = ptNew;
                        ptNew -> listEl = scanned;
                        ptNew -> link = NULL;
                    }
            }
    
        return ptPtLnkList;
    }
    I have also included the relevant parts of main this time, because I am aware that there might be a problem with how I am declaring or assigning ptLinkList or ptPtLnkList. As far as I can see (which is apparently not very far at all), if everything else is correct in the code, I haven't derefernced NULL or tried to get NULL to point to something (i.e., to of the most common ways of creating a segfault).

    I am however unsure if I need to declare a variable such as sturct node lnkList so that ptLnkList has something to point to. This is mainly because I'm note sure how well I understand how malloc() works. I know that it returns a pointer to an integer variable (if not explicitly cast) or any type of variable (if explicitly cast), but does is reserve a block of memory for the entire type?

    Anyway, the issue I'm having with the above code seem partly to arise from the fact that I assign *ptPtLnkList to NULL in main and then pass it to bldList. However, if I assign *ptPtLnkList to NULL in bldList, a segfault occurs wherever I put it. This is why I think that I don't understand pointers very well, because, as I understand pointers, a pointer to a data type is the address of the first byte of the data type in the memory and a pointer to a pointer to a data type is address of the address of the first byte of the data type in the memory. Thus dereferencing a pointer to a pointer should yield the address of the first byte of the data type.

    In other words, dereferencing ptPtLnkList (i.e., *ptPtLnkLst) should yield the address of the first byte of the node structure. (As I understand it, that would be the first byte of int data, because fields in a structure are stored contiguously in the memory and int data is the first field in struct node.) I am confused, because *ptPtLnkLst = NULL; seems to cause the same problems as dereferencing NULL when all I think I'm doing is assigning an address to the first byte of the linked list, which should be NULL if the list is empty.

    As far as I can see, the rest of the dereferences of ptPtLnkList do not dereference NULL and should not cause a segfault in that respect. (I realize that there are other ways of causing a segfault than the ones explicitly mentioned in this post.)

    I'm sorry if the above is rambling and disconnected, but I am really unsure that I understand the concept.

  15. #15
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You didn't include how you call it, which is kinda relevant.
    Code:
    In main:
    
    type *mylist = NULL;
    ...
    yourfun( file1, file2, &mylist );

    Quzah.
    Hope is the first step on the road to disappointment.

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