Thread: Sorting a linked list upon node insertion

  1. #1
    Registered User
    Join Date
    Aug 2013
    Posts
    5

    Sorting a linked list upon node insertion

    While I know that linked lists seem to be a fairly common problem area among beginner C programmers, most examples that I have come across abstract the sorting of a linked list to a separate function which is sadly not what I am trying to do.

    The code below is my attempt to have the nodes inserted into their correct place so that once all nodes have been inserted they are already in a sorted order.

    Code:
    int main(int argc, char *argv[])
    {
        struct node_t* dict_head;
        struct node_t* traversor;
        struct node_t* newnode;
    
    
        int list_size = 0, insert_key, search_key, delete_key, x;
        char insert_word[WORDLEN];
        
        
        /*Opening the dictionary file provided by the command line argument */
        FILE *fp;
        fp = fopen(argv[1], "r");
    
    
        dict_head = malloc(sizeof(struct node_t));
        assert(dict_head != NULL);
        traversor = malloc(sizeof(struct node_t));
        assert(dict_head != NULL); 
        
        while(fscanf(fp,"%d %s\n", &traversor->key, traversor->word) == 2){
            newnode =  malloc(sizeof(struct node_t));
            newnode->key = traversor->key;
            strcpy(newnode->word, traversor->word);
            traversor = dict_head;
            
            while(traversor->next!= NULL){
                
                if(traversor->next->key > newnode->key){break;}
                
                traversor = traversor->next;
            }
            printf("Traversor is sitting on %s\n", traversor->word);
            newnode->next = traversor->next;
            traversor->next = newnode;
            traversor = dict_head;
            for(x = 0; x < list_size; x++)
            {
                printf("%d %s %d ->", traversor, traversor->word, traversor->key);
                traversor = traversor->next;
            }
            printf("%d %s %d",traversor->next, traversor->next->word, traversor->next->key);
            
            printf("\n");
            list_size++;
        }
        
        return 0;
    }
    with node_t being
    Code:
    struct node_t{
        int key;
        char word[WORDLEN];
        struct node_t *next;
    };

    The problem is as follows. When you provide it with input in which the first word scanned is any other word than that which would be placed at the front of the list, it works as intended. For example.

    7 world
    0 ant
    3 kodak
    1 best
    6 the
    2 is

    Produces ant -> best->is->kodak->best->world

    However, swapping ant and world in the above input gives:
    world->best->is->kodak->best->world


    In regards to why I have my head node set as a node without a word or a key, it was suggested that I make it so that the first node inserted is set to be the head of the list and then changed as sorting required, yet this caused only additional problems.

    Any help that can be given would be greatly appreciated

  2. #2
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964
    This seems wrong to me:

    Code:
    traversor = malloc(sizeof(struct node_t));
    Generally, the conductor will be assigned such that it points to the head of the list, and then use the next members to traverse the list. Why are you allocating a node for the conductor to point to?

    The algorithm for what you are trying to do would be (roughly) something like this:

    1. Get input
    2. Compare input to current node. (root node initially)
    3. If comp(input, current_node->val) insert a new node before the current node. Else move to the next node.
    4. If current_node == tail, insert the new node at the end of the list.

    You also need to make sure that the list properties are maintained along the way.
    How I need a drink, alcoholic in nature, after the heavy lectures involving quantum mechanics.

  3. #3
    Registered User
    Join Date
    Aug 2013
    Posts
    5
    Agreed, I removed the malloc for the traversor. Yet the same problem still manifests, and in my mind my program is following the above algorithm, so I honestly have no idea why it only works when the first line of input isn't the first item in the sorted list

  4. #4
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Hi James,

    When you cross-post a question (i.e., post it to multiple forums), say so and include links to the other posts. Otherwise (and I promise there are multiple users here that also subscribe to C on S.O.) people will get irritated with you, because it means someone can end up wasting time giving you help that you already got elsewhere.

    Let's look at some potential pitfalls with your code:

    Code:
        dict_head = malloc(sizeof(struct node_t));
    On most modern operating systems, the various fields in 'traversor' will be zero'd out, hence 'traversor->next' will be NULL. However, you should not rely on this,

    • because it is coincidental -- the reason it is zero'd out is NOT to initialize your struct, and
    • because it's not guaranteed to happen.


    Instead, you should initialize the fields after you allocate memory, or use calloc() or memset(). This is important because the first place dict_head gets used is:

    Code:
    traversor = dict_head;
             
    while(traversor->next!= NULL){
    If your OS had not coincidentally zero'd dict_head, traversor->next would be a random junk address and you would seg fault here. Note also that on the first run, you have leaked the memory you assigned to traversor.

    Something eventually becomes of the traversor pointer in this loop:

    Code:
    while(fscanf(fp,"%d %s\n", &traversor->key, traversor->word) == 2){
    
    [...]
            for(x = 0; x < list_size; x++)
            {
                printf("%d %s %d ->", traversor, traversor->word, traversor->key);
                traversor = traversor->next;
            }
           printf("%d %s %d",traversor->next, traversor->next->word, traversor->next->key);
    [...]
    }
    At the end, 'traversor' is the last node in the list. Then the loop re-iterates and *gasp* you overwrite it with fscanf().:/ Remember this point.

    Next let's consider your insertion:

    Code:
            while(traversor->next!= NULL){
                 
                if(traversor->next->key > newnode->key){break;}
                 
                traversor = traversor->next;
            }
    If traversor == dict_head, and dict_head->key == 0 (since dict_head was not initialized, and so coincidentally zero'd), then the "if" condition will always be true, unless newnode->key is also zero.

    That won't sort at all, since everything will just get inserted at the beginning.

    Except remember that point about overwriting traversor? This means the second insertion will now overwrite dict_head (since after the first one, traversor == dict_head). Now the sorting will work, just not quite via the mechanism you intended; although traversor will be overwritten, it won't matter because you actually have two copies of that first node on the first insertion (traversor, which you wrote into, and newnode, which you copied into). This is how you potentially end up with two "worlds".

    But if the first thing you put in has a key of 0, the next insertion will get put in front of that and the "ant" node will be leaked here:

    Code:
            newnode->next = traversor->next;
            traversor->next = newnode;
            traversor = dict_head
    Because it was in the traversor node and when you reassign the pointer, that node is not attached to anything anymore (hence, leaked).

    -- Goldilocks
    Last edited by MK27; 08-30-2013 at 09:12 AM.
    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

  5. #5
    Registered User
    Join Date
    Aug 2013
    Posts
    5
    I can't begin to express how grateful I am for your help tonight, were I able to give you more than one like I definitely would. Thanks for the in-depth analysis of what is going wrong, incredibly helpful after a night of staring at the code trying to fix it. Thanks again

  6. #6
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    If you move the next pointer to the beginning of the struct, then a pointer to pointer to node is the same as pointer to node->next. (The rule in C / C++ is the address to the first member of a struct is the same as the address of the struct). In this example, dict_head is initialized to NULL, and traversor is initialized as a pointer to dict_head, so that traversor->next == dict_head. I also added code to free the nodes after displaying them, using newnode as a temp pointer.

    Code:
    #include <malloc.h>
    #include <stdio.h>
    #include <string.h>
    
    #define WORDLEN 24
    
    struct node_t{
        struct node_t *next;
        int key;
        char word[WORDLEN];
    };
    
    int main(int argc, char *argv[])
    {
        struct node_t* dict_head = NULL;
        /* since next is first member, this will work */
        struct node_t* traversor = (struct node_t *)&dict_head;
        struct node_t* newnode;
        int key;
        char word[WORDLEN];
        FILE *fp;
        fp = fopen(argv[1], "r");
        while(fscanf(fp,"%d %s\n", &key, word) == 2){
            newnode =  malloc(sizeof(struct node_t));
            newnode->key = key;
            strcpy(newnode->word, word);
            while(traversor->next!= NULL){
                if(traversor->next->key > newnode->key){break;}
                traversor = traversor->next;
            }
            newnode->next = traversor->next;
            traversor->next = newnode;
        }
        traversor = dict_head;
        while(traversor != NULL){
            printf("%s %d", traversor->word, traversor->key);
            newnode   = traversor;
            traversor = traversor->next;
            if(traversor)
                printf(" ->");
            free(newnode);
        }
        printf("\n");
        return(0);
    }
    Last edited by rcgldr; 08-30-2013 at 11:54 AM.

  7. #7
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    Correction to previous code example. traversor needs to be initialized each time a node is inserted / appended to the list. Same principle, since next is first member of node_t, then setting traversor = &dict_head results in traversor->next == dict_head.

    Code:
    #include <malloc.h>
    #include <stdio.h>
    #include <string.h>
    
    #define WORDLEN 24
    
    struct node_t{
        struct node_t *next;
        int key;
        char word[WORDLEN];
    };
    
    int main(int argc, char *argv[])
    {
        struct node_t* dict_head = NULL;
        struct node_t* traversor;
        struct node_t* newnode;
        int key;
        char word[WORDLEN];
        FILE *fp;
        fp = fopen(argv[1], "r");
        while(fscanf(fp,"%d %s\n", &key, word) == 2){
            newnode =  malloc(sizeof(struct node_t));
            newnode->key = key;
            strcpy(newnode->word, word);
            /* since next is first member, this will work */
            traversor = (struct node_t *)&dict_head;
            while(traversor->next!= NULL){
                if(traversor->next->key > newnode->key){break;}
                traversor = traversor->next;
            }
            newnode->next = traversor->next;
            traversor->next = newnode;
        }
        traversor = dict_head;
        while(traversor != NULL){
            printf("%s %d", traversor->word, traversor->key);
            newnode   = traversor;
            traversor = traversor->next;
            if(traversor)
                printf(" -> ");
            free(newnode);
        }
        printf("\n");
        return(0);
    }
    Last edited by rcgldr; 08-30-2013 at 05:56 PM.

  8. #8
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    When using %s in scanf I prefer always limit the number of chars to read to prevent buffer overrun, so line 22 I would write
    Code:
    while(fscanf(fp,"%d %23s", &key, word) == 2){
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. HELP! Linked List Insertion
    By divisionbyzero in forum C Programming
    Replies: 1
    Last Post: 04-08-2010, 03:43 PM
  2. Replies: 0
    Last Post: 09-16-2008, 05:04 AM
  3. Insertion Linked List Help
    By 0rion in forum C Programming
    Replies: 4
    Last Post: 05-12-2004, 07:38 AM
  4. traversing a linked list with a node and list class
    By brianptodd in forum C++ Programming
    Replies: 2
    Last Post: 04-24-2003, 11:57 AM
  5. Replies: 5
    Last Post: 10-04-2001, 03:42 PM