Thread: Linked lists - deleting a list

  1. #1
    Registered User
    Join Date
    Mar 2010
    Location
    Australia
    Posts
    174

    Linked lists - deleting a list

    I have a program that takes two arguments and makes a random word., The first argument argv[1] is the number of letters in the word, and the second argument is the random number seed.
    I need to put each random character into a node in a linked list and after I've done that, I need to print out the linked list (the random word). FInally, I need to be able to delete any characters that are duplicated in a row and then print out the new word.

    This is what I have:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    #define ALPHABET 26
    
    typedef struct _Node {
        char letter;
        struct _Node *next;
    } NodeT;
    
    int isNum(char *);
    NodeT *addNode(NodeT *);
    NodeT *addLetter(NodeT *);
    void printList(NodeT *);
    NodeT *removeDupes(NodeT *);
    
    int main(int argc, char **argv) {
        int length = 0;
        int seed = 0;
        NodeT *head1 = NULL;
        NodeT *head2 = NULL;
        int i = 0;
        
        if (argc != 3 || !isNum(argv[1]) || !isNum(argv[2])) {
            fprintf(stderr, "Usage: ./llrandword "
                    "wordlength randomseed\n"); 
            return EXIT_FAILURE;  
        }
        
        length = atoi(argv[1]);
        seed = atoi(argv[2]);
        srandom(seed);
        for(i=0; i<length; i++) {
           head1 = addNode(head1);
        }
        head1 = addLetter(head1);
        printList(head1);
        putchar('\n');
        head2 = head1;
        head2 = removeDupes(head1);
        printList(head2);
        putchar('\n');
    
        return EXIT_SUCCESS;
    }
    
    int isNum(char *string) {
        int isNum = 1;
        
        while(*string != '\0') {
            if (*string < '0' || *string > '9') {
                isNum = 0;
            }
            string++;
        }
        
        return isNum;
    }
    
    NodeT *addNode(NodeT *list) {
        NodeT *new = NULL;
        NodeT *cur = NULL;
        
        new = malloc(sizeof(NodeT));
        if (new == NULL) {
            fprintf(stderr, "Out of memory\n");
            exit(1);
        }
        
        if (list == NULL) {
            list = new;
        } else {
            cur = list; 
            while (cur->next != NULL) {
                cur=cur->next;
            }
            cur->next = new;
        }
        
        new->next = NULL;
        
        return list;
    }
    
    NodeT *addLetter(NodeT *head) {
        NodeT *cur = NULL;
        int r = 0;
        int rand = 0;
        
        for(cur = head; cur != NULL; cur = cur->next) {
            r = random();
            rand = r % ALPHABET;
            cur->letter = 'a'+rand;
        }
        
        return head;
    }
    
    void printList(NodeT *head) {
        NodeT *cur = NULL;
        
        for (cur=head; cur != NULL; cur=cur->next) {
            printf("%c", cur->letter);
            if(cur->next != NULL) {
                printf("->");
            }
        }
    }
    
    NodeT *removeDupes(NodeT *head) {
        NodeT *cur = NULL;
        NodeT *tmp = NULL;
        
        for(cur=head; cur->next != NULL; cur = cur->next) {
            if (cur->letter == cur->next->letter) {
                tmp->next = cur->next->next;
                cur->next->next = NULL;
                free(cur->next);
                cur->next = tmp->next;
                tmp->next = NULL;
            }
        }
        
        return head;
    }
    When I execute the program, this is what I get:

    $ ./llrandword 10 1
    n->w->l->r->b->b->m->q->b->h
    Segmentation fault (core dumped)
    What the output should be is
    $ ./llrandword 10 1
    n->w->l->r->b->b->m->q->b->h
    n->w->l->r->b->m->q->b->h
    I have a feeling something is wrong with the removeDupes function.

  2. #2
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    Quote Originally Posted by Mentallic
    I have a feeling something is wrong with the removeDupes function.
    Yep...
    Code:
    NodeT *removeDupes(NodeT *head) {
        NodeT *cur = NULL;
        NodeT *tmp = NULL;
        
        for(cur=head; cur->next != NULL; cur = cur->next) {
            if (cur->letter == cur->next->letter) {
                tmp->next = cur->next->next;
                cur->next->next = NULL;
                free(cur->next);
                cur->next = tmp->next;
                tmp->next = NULL;
            }
        }
        
        return head;
    }
    Ask yourself what does tmp point to and then ask yourself why you are dereferencing a null pointer.

    Code:
    typedef struct _Node {
        char letter;
        struct _Node *next;
    } NodeT;
    Identifiers beginning with an underscore character followed by an uppercase letter are reserved for use only by the implementation.

    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  3. #3
    Registered User
    Join Date
    Mar 2010
    Location
    Australia
    Posts
    174
    Quote Originally Posted by hk_mp5kpdw View Post
    Ask yourself what does tmp point to
    Nothing (unless I'm misunderstanding NULL).

    Quote Originally Posted by hk_mp5kpdw View Post
    and then ask yourself why you are dereferencing a null pointer.
    Sorry, I don't know what this means.

    Quote Originally Posted by hk_mp5kpdw View Post
    Identifiers beginning with an underscore character followed by an uppercase letter are reserved for use only by the implementation.
    I don't really understand this either, but if I were to guess, I shoiuldn't be using _Node as a name for the typedef struct? I merely copied what my lecturer had used.

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    This is the same problem you had with the string rotation, using a pointer. You have a pointer, which you assign to NULL.

    Then, without changing the pointers address, you have temp->next (in red, in the above post), which you can not do. As long as the pointer has the address of NULL, you can't do anything with it, except assign it a new address. NOTHING ELSE!!

    Dexter won't like this! <grin>

  5. #5
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    I don't really understand this either, but if I were to guess, I shoiuldn't be using _Node as a name for the typedef struct? I merely copied what my lecturer had used.
    Identifiers/names starting with underscore are reserved for usage in the standard library. Your lecturer should read section 7.1.3 in the standard.

    Bye, Andreas

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Mentallic View Post
    Nothing (unless I'm misunderstanding NULL).

    Sorry, I don't know what this means.
    Look at what hk_mp5kpdw hilighted in the previous post. You're trying to set nothing's next pointer to something, but clearly "nothing" doesn't have a next pointer.
    Perhaps you mean to set tmp to something first, or instead.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Registered User
    Join Date
    Mar 2010
    Location
    Australia
    Posts
    174
    Quote Originally Posted by Adak View Post
    This is the same problem you had with the string rotation, using a pointer. You have a pointer, which you assign to NULL.

    Then, without changing the pointers address, you have temp->next (in red, in the above post), which you can not do. As long as the pointer has the address of NULL, you can't do anything with it, except assign it a new address. NOTHING ELSE!!

    Dexter won't like this! <grin>
    Haha it seems so obvious now, but it wasn't registering in my head last night.

    Quote Originally Posted by AndiPersti View Post
    Identifiers/names starting with underscore are reserved for usage in the standard library. Your lecturer should read section 7.1.3 in the standard.

    Bye, Andreas
    But it doesn't seem to have had any negative effects on the functionality of the program. Unlike declaring the name of a variable as int, loop, main etc. which wouldn't even compile, the _Node name is an exception. I'll mention it to him and keep it in mind myself, but I'd like a little more information as to why that article is saying it's reserved yet I can freely use it.

    Quote Originally Posted by iMalc View Post
    Look at what hk_mp5kpdw hilighted in the previous post. You're trying to set nothing's next pointer to something, but clearly "nothing" doesn't have a next pointer.
    Perhaps you mean to set tmp to something first, or instead.
    Of course, I need to malloc room for the tmp pointer.


    EDIT: I've simply added a line to give the tmp Node some room on the heap, so now my removeDupes function is

    Code:
    NodeT *removeDupes(NodeT *head) {
        NodeT *cur = NULL;
        NodeT *tmp = NULL;
    
        tmp = addNode(tmp);
         
        for(cur=head; cur->next != NULL; cur = cur->next) {
            if (cur->letter == cur->next->letter) {
                tmp->next = cur->next->next;
                cur->next->next = NULL;
                free(cur->next);
                cur->next = tmp->next;
                tmp->next = NULL;
            }
        }
         
        return head;
    }
    And it's still seg faulting. I can't think of any other reasons why it would be, so I have no clue with how to proceed.
    Last edited by Mentallic; 09-05-2012 at 12:05 AM.

  8. #8
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Code:
    NodeT *removeDupes(NodeT *head) {
        NodeT *cur = NULL;
        NodeT *tmp = NULL;
         
        for(cur=head; cur->next != NULL; cur = cur->next) {
            if (cur->letter == cur->next->letter) {
                tmp = cur;
                tmp->next = cur->next->next;
                cur->next->next = NULL;
                free(cur->next);
                cur->next = tmp->next;
                tmp->next = NULL;
            }
        }
         
        return head;
    }
    This is basically untested, but I think it will work. Be careful with NULL pointers. I'm not sure what the last line is for either.

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    Quote Originally Posted by Mentallic
    But it doesn't seem to have had any negative effects on the functionality of the program. Unlike declaring the name of a variable as int, loop, main etc. which wouldn't even compile, the _Node name is an exception. I'll mention it to him and keep it in mind myself, but I'd like a little more information as to why that article is saying it's reserved yet I can freely use it.
    Okay, instead of writing:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
     
    #define ALPHABET 26
     
    typedef struct _Node {
        char letter;
        struct _Node *next;
    } NodeT;
    write:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    struct _Node {
        int n;
    };
     
    #define ALPHABET 26
     
    typedef struct _Node {
        char letter;
        struct _Node *next;
    } NodeT;
    Attempt to compile your program and observe the error message. Now, imagine that this:
    Code:
    struct _Node {
        int n;
    };
    was in <stdlib.h>. Obviously, you would get the same error message. Yet, it is possible that that is in <stdlib.h> because the name is reserved to the compiler and standard library implementation. In other words, by using reserved names, you risk such errors. It might not happen now, but it could happen with a different compiler, standard library implementation, or a different version thereof, and the fault for the error would be entirely yours.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Registered User
    Join Date
    Mar 2010
    Location
    Australia
    Posts
    174
    Umm that was stupid of me... the most recent function update I had posted did work, I was just editing a duplicate copy of my c file in another folder by accident, so I was then compiling the unedited version.

    And yes you have a point, that last line is unnecessary.

    Ok so I got it working by doing a malloc for the tmp node, but if there is a way to do it without mallocing tmp as whiteflags has suggested, I'd like to see it. At the moment with the modified function whiteflags has posted, I'm getting the output

    $ ./llrandword 10 1
    n->w->l->r->b->b->m->q->b->h
    n->w->l->r->b->

  11. #11
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Actually I take it back, as written that can't work because assigning to tmp->next will screw up the part where you free.

    Let's think about it a bit.

    Code:
    /* 1. Find duplicate */
    for (cur = head; cur->next != NULL; cur = cur->next) {
        if (cur->letter == cur->next->letter) {
           /* 2. Save pointer to node after dupe */
           tmp = cur->next->next;
           /* 3. free dupe */
           free(cur->next);
           /* 4. Repair list */
           cur->next = tmp;
        }
    }
    Much better.

  12. #12
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    My objection to that sort of loop is that cur->next != NULL kind of makes the "next" sound like the "current". I guess that cannot be helped if you want to avoid otherwise unnecessary checks, but then head should be checked before the entire loop is run, just in case.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #13
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Actually I agree. Freeing the first occurrence does help solve an annoying problem. This way you can correctly handle if a certain node appears an odd number of times as well.

    Like
    a -> b -> b -> b -> c -> b
    a -> b -> b ...
    a -> b -> b -> c ...
    a -> b -> c -> b

    So if we're going for something like that it would be the right way to go.

  14. #14
    Registered User
    Join Date
    Mar 2010
    Location
    Australia
    Posts
    174
    Oh ok thanks silverlight, I'll pass on your message to my professor.

    Whiteflags, I drew up the situation we had with the previous code so I can try and understand why it doesn't work a little better. If tmp was created as its own node (such as if we malloc'ed room for it) everything seems like it would work, so I'm guessing the problem lies with the first line tmp = cur.

    When we make cur->next->next = NULL, doesn't that mean we've lost the 3rd node (if cur is the 1st node, cur->next is the 2nd) even though we set tmp to be pointing to it? Because tmp points to it through cur, and the link between the 2nd and 3rd node have been broken, so the program stops working even before we free the 2nd node. Am I understanding this correctly?

  15. #15
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    It was pretty much my mistake at this time of night. The problem is exactly as I described. The loop wants to free cur->next. We made an alias for cur called "tmp" through the assignment, so tmp->next is cur->next. Since we assign to tmp->next a different pointer, we end up freeing the wrong node and breaking the list. The next code I posted is different because of where tmp points to and how I use tmp in the code.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 05-01-2010, 10:19 PM
  2. Linked List deleting Help
    By StealthRT in forum C++ Programming
    Replies: 6
    Last Post: 10-21-2009, 02:19 AM
  3. Deleting linked lists...
    By shiver in forum C++ Programming
    Replies: 2
    Last Post: 07-09-2006, 10:25 PM
  4. deleting a linked list
    By gordy in forum C++ Programming
    Replies: 3
    Last Post: 07-01-2002, 05:01 PM
  5. Deleting - Linked List
    By TeeTee in forum C Programming
    Replies: 2
    Last Post: 09-16-2001, 07:39 PM