Need help with sorting a linked list?

This is a discussion on Need help with sorting a linked list? within the C Programming forums, part of the General Programming Boards category; I have this code: Code: typedef struct _node{ double total; struct _node *next; struct _node *prev; } NODE; NODE delete_current(NODE ...

  1. #1
    Registered User
    Join Date
    Sep 2008
    Posts
    58

    Need help with sorting a linked list?

    I have this code:

    Code:
    typedef struct _node{
        double total;
        struct _node *next;
        struct _node *prev;
    } NODE;
    
    NODE delete_current(NODE *current)
    {
        current->prev->next = current->next;
        current->next->prev = current->prev;
        free(current);
    }
    
    NODE sort(NODE *new_list, NODE *old_list)
    {
        NODE *current = (NODE *)malloc(sizeof(NODE));
        NODE *max = (NODE *)malloc(sizeof(NODE));
    
        while(old_list != NULL)
        {
            max = old_list->next;
            for(current = old_list->next; current != old_list; old_list= old_list->next)
            {
    
                if(max->total < old_list->total)
                {
                    max = old_list;
                }
    
            }
            new_list = new_list->next;
            new_list = (NODE *)malloc(sizeof(NODE));
            new_list->total = max->total;
            delete_current(old_list);
    
        }
    }
    
    NODE add(NODE *sent, double i)
    {
        NODE *new_node;
        new_node = (NODE *)malloc(sizeof(NODE));
        sent->prev->next = new_node;
        new_node->prev = sent->prev;
        new_node->next = sent;
        sent->prev = new_node;
        new_node->total = i;
    
    
    
    }
    
    NODE print_list(NODE *list)
    {
        NODE *current;
        for(current = list->next; current != list; current = current->next){
            printf("%lf\n",current->total);
        }
    }
    int main(int argc, char **argv)
    {
        NODE *new_list = (NODE *)malloc(sizeof(NODE));
        NODE *old_list = (NODE *)malloc(sizeof(NODE));
        double i;
    
        old_list->next = old_list;
        old_list->prev = old_list;
    
        for( i =1; i<=10 ; i++)
        {
            add(old_list, i);
    
        }
        print_list(old_list);
    
        sort(new_list, old_list);
    
        print_list(new_list);
    }

    Im having trouble on my sort() function.. I know print_list works and add works..
    The whole for loop setting the total in each node is just me making a test list.. its not my actual list.. The sort function is supposed to be sorting the list from greatest to least.

  2. #2
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,762
    You could:
    • build an array of nodes
    • outsource sorting to qsort
    • relink your list


    This works well especially if the list is under a hundred or so nodes. If you must build your own sort procedure, then I would suggest an attempt at merge sort.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    A sort routine for a list should never need to allocate any nodes. All it needs to do is change what various nodes point to. Definitely don't malloc for max and current, just assign them NULL to begin with. Then instead of using malloc right before you delete a node, simply reuse the same node, i'e' instead of copying total, just change the pointers.

    As an added bonus, I'll post some of my C++ selection sort code for a doubly-linked ring-list (which I believe is exactly the structure you are using):
    Code:
    template <class TItem>
    void SelectionSort(TItem *&head) {
    	TItem *unsortedhead = head, *curr;
    	TItem *lowhead = NULL, *currlow;
    	while (unsortedhead != NULL) {
    		currlow = curr = unsortedhead;
    		//step through list finding lowest item
    		do {
    			if (*curr < *currlow)
    				currlow = curr;
    			curr = curr->next;
    		} while (curr != unsortedhead);
    		//take the item out of the list
    		Remove(unsortedhead, currlow);
    		//append the item to the end of the new list
    		Put(lowhead, currlow);
    	}
    	//put new list back into old list
    	head = lowhead;
    }
    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"

  4. #4
    Registered User
    Join Date
    Sep 2008
    Posts
    58
    Quote Originally Posted by iMalc View Post
    A sort routine for a list should never need to allocate any nodes. All it needs to do is change what various nodes point to. Definitely don't malloc for max and current, just assign them NULL to begin with. Then instead of using malloc right before you delete a node, simply reuse the same node, i'e' instead of copying total, just change the pointers.

    As an added bonus, I'll post some of my C++ selection sort code for a doubly-linked ring-list (which I believe is exactly the structure you are using):
    Code:
    template <class TItem>
    void SelectionSort(TItem *&head) {
    	TItem *unsortedhead = head, *curr;
    	TItem *lowhead = NULL, *currlow;
    	while (unsortedhead != NULL) {
    		currlow = curr = unsortedhead;
    		//step through list finding lowest item
    		do {
    			if (*curr < *currlow)
    				currlow = curr;
    			curr = curr->next;
    		} while (curr != unsortedhead);
    		//take the item out of the list
    		Remove(unsortedhead, currlow);
    		//append the item to the end of the new list
    		Put(lowhead, currlow);
    	}
    	//put new list back into old list
    	head = lowhead;
    }


    I tried to turn your code into something that would work for my program..
    Code:
    NODE delete_current(NODE *current)
    {
        current->prev->next = current->next;
        current->next->prev = current->prev;
        free(current);
    }
    
    NODE new_list_add(NODE *sent, NODE *high)
    {
        NODE *new_node;
        new_node = (NODE *)malloc(sizeof(NODE));
        sent->prev->next = new_node;
        new_node->prev = sent->prev;
        new_node->next = sent;
        sent->prev = new_node;
        new_node->total = high->total;
    }
    
    NODE sort(NODE *head)
    {
        NODE *unsorted = head;
        NODE *current;
        NODE *high_head;
        NODE *current_high;
    
        high_head->prev = high_head;
        high_head->next = high_head;
    
        while(unsorted != NULL)
        {
            current_high = current = unsorted;
            current = current->next;
            while(current != unsorted)
            {
                if(current->total > current_high->total)
                {
                    current_high = current;
                }
                current = current->next;
            }
    
            delete_current(unsorted);
            new_list_add(high_head, current_high);  //<<error
    
    
        }
    
    }
    its saying I have a "previous implicit declaration of &#226;new_list_add&#226; was here"

    I dont know what to do...pleaseeee help me...

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    I just noticed that you're returning NODE from your functions. You shouldn't do that. They either need to return NODE* or they should return NULL.

    No idea why you would get that error/warning?
    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"

  6. #6
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Code:
        NODE *unsorted = head;
        NODE *current;
        NODE *high_head;
        NODE *current_high;
    
        high_head->prev = high_head;
        high_head->next = high_head;
    At this point in your code "high_head" seems to be undefined. So, the next and prev links would also be undefined. It looks as if this could screw things up when you call new_list_add(). Or, at least thats the impression I get. Doubt its why you get that error tho, should get a segfualt instead.
    Last edited by mike_g; 10-19-2008 at 07:24 AM.

  7. #7
    Registered User
    Join Date
    Sep 2008
    Posts
    58
    Quote Originally Posted by mike_g View Post
    Code:
        NODE *unsorted = head;
        NODE *current;
        NODE *high_head;
        NODE *current_high;
    
        high_head->prev = high_head;
        high_head->next = high_head;
    At this point in your code "high_head" seems to be undefined. So, the next and prev links would also be undefined. It looks as if this could screw things up when you call new_list_add(). Or, at least thats the impression I get. Doubt its why you get that error tho, should get a segfualt instead.
    Ok I malloced high_head.. and that fixed the error .. but now im in an infinite loop? help ?
    Code:
    NODE delete_current(NODE *current)
    {
        current->prev->next = current->next;
        current->next->prev = current->prev;
        free(current);
    }
    
    NODE new_list_add(NODE *sent, NODE *high)
    {
        NODE *new_node;
        new_node = (NODE *)malloc(sizeof(NODE));
        sent->prev->next = new_node;
        new_node->prev = sent->prev;
        new_node->next = sent;
        sent->prev = new_node;
        new_node->total = high->total;
    }
    
    NODE sort(NODE *head)
    {
        NODE *unsorted = head;
        NODE *current;
        NODE *high_head;
        NODE *current_high;
    
        high_head = (NODE *)malloc(sizeof(NODE));
    
        high_head->prev = high_head;
        high_head->next = high_head;
    
        while(unsorted != NULL)
        {
            current_high = current = unsorted;
            current = current->next;
            while(current != unsorted)
            {
                if(current->total > current_high->total)
                {
                    current_high = current;
                }
                current = current->next;
            }
    
            new_list_add(high_head, current_high);
            delete_current(current_high);
        }
    
    }

  8. #8
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    But what exactly is the new node you have malloced doing?

    You should not have to create any new nodes in order to sort your list; you just need to change where the links point to.

    In pseudo code what (I think) you want to be doing is:
    [code]Set the head node of the new (sorted) list to NULL

    While there are nodes on the old (unsorted) list
    Loop through each node on the unsorted list

  9. #9
    Registered User
    Join Date
    Sep 2008
    Posts
    58
    Quote Originally Posted by mike_g View Post
    But what exactly is the new node you have malloced doing?

    You should not have to create any new nodes in order to sort your list; you just need to change where the links point to.

    In pseudo code what (I think) you want to be doing is:
    [code]Set the head node of the new (sorted) list to NULL

    While there are nodes on the old (unsorted) list
    Loop through each node on the unsorted list
    Its holding the new list.. I dont know how to do what youre saying "change where they point to"

    here is my whole code.. i changed set new_list to equal my high_head..


    Code:
    NODE delete_current(NODE *current)
    {
        current->prev->next = current->next;
        current->next->prev = current->prev;
        free(current);
    }
    
    NODE new_list_add(NODE *sent, NODE *high)
    {
        NODE *new_node;
        new_node = (NODE *)malloc(sizeof(NODE));
        sent->prev->next = new_node;
        new_node->prev = sent->prev;
        new_node->next = sent;
        sent->prev = new_node;
        new_node->total = high->total;
    }
    
    NODE sort(NODE *new_list, NODE *head)
    {
        NODE *unsorted = head;
        NODE *current;
        NODE *high_head;
        NODE *current_high;
    
        high_head = (NODE *)malloc(sizeof(NODE));
    
        high_head->prev = high_head;
        high_head->next = high_head;
    
        while(unsorted != NULL)
        {
            current_high = current = unsorted;
            current = current->next;
            while(current != unsorted)
            {
                if(current->total > current_high->total)
                {
                    current_high = current;
                }
                current = current->next;
            }
    
            new_list_add(high_head, current_high);
            delete_current(current_high);
        }
    new_list = high_head;
    }
    
    NODE add(NODE *sent, double i)
    {
        NODE *new_node;
        new_node = (NODE *)malloc(sizeof(NODE));
        sent->prev->next = new_node;
        new_node->prev = sent->prev;
        new_node->next = sent;
        sent->prev = new_node;
        new_node->total = i;
    
    }
    NODE print_list(NODE *list)
    {
        NODE *current;
        for(current = list->next; current != list; current = current->next){
            printf("%lf\n",current->total);
        }
    }
    
    
    int main(int argc, char **argv)
    {
        NODE *new_list = (NODE *)malloc(sizeof(NODE));
        NODE *old_list = (NODE *)malloc(sizeof(NODE));
        double i;
    
        old_list->next = old_list;
        old_list->prev = old_list;
    
        for( i =1; i<=10 ; i++)
        {
            add(old_list, i);
    
        }
        print_list(old_list);
    
        sort(new_list, old_list);
    
        print_list(new_list);
        return 0;
    }

  10. #10
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    But what are you trying to achieve by mallocing a new node here?

    The first node on your sorted list (high_head) should be set to NULL, so that it acts as the terminator.

    <edit> oh, and get rid of this part:
    Code:
        high_head->prev = high_head;
        high_head->next = high_head;
    </edit>

    Now, assuming that your add and delete functions are fine I think this should work.

    Another approach would be to simply relink you list. This would avoid all the adding and deleting. Basically you do not have to create any new nodes to sort your list; its simply a matter of changing where the links point to. to give you an idea of how you could go about it in pseudo code:
    Code:
    Set the head of the new (sorted)  list to NULL
      
    While there are nodes on the old (unsorted) list
        Loop through each node on unsorted list
            Store the node before the smallest result
            Store the smallest result
            Store the node after the smallest result
    
        Link node from before smallest result to node after smallest result
        Link node from after smallest result to node before smallest result
       
        Add orphaned smallest result node to the new (sorted) list
    but, considering where you are its probably easiest to try and get what you have to work.

    Edit2: oh, and ignore my last post above; it was an accident.
    Last edited by mike_g; 10-19-2008 at 12:06 PM.

  11. #11
    Registered User
    Join Date
    Sep 2008
    Posts
    58
    Quote Originally Posted by mike_g View Post
    But what are you trying to achieve by mallocing a new node here?

    The first node on your sorted list (high_head) should be set to NULL, so that it acts as the terminator.

    <edit> oh, and get rid of this part:
    Code:
        high_head->prev = high_head;
        high_head->next = high_head;
    </edit>

    Now, assuming that your add and delete functions are fine I think this should work.

    Another approach would be to simply relink you list. This would avoid all the adding and deleting. Basically you do not have to create any new nodes to sort your list; its simply a matter of changing where the links point to. to give you an idea of how you could go about it in pseudo code:
    Code:
    Set the head of the new (sorted)  list to NULL
      
    While there are nodes on the old (unsorted) list
        Loop through each node on unsorted list
            Store the node before the smallest result
            Store the smallest result
            Store the node after the smallest result
    
        Link node from before smallest result to node after smallest result
        Link node from after smallest result to node before smallest result
       
        Add orphaned smallest result node to the new (sorted) list
    but, considering where you are its probably easiest to try and get what you have to work.

    Edit2: oh, and ignore my last post above; it was an accident.

    Ok is this right?

    Code:
    NODE sort(NODE *head)
    {
        NODE *unsorted = head;
        NODE *current;
        NODE *high_head;
        NODE *current_high;
        NODE *before_high;
        NODE *after_high;
    
        high_head = NULL;
    
        unsorted = unsorted->next;
        while(unsorted != NULL)
        {
            current_high = current = unsorted;
            for(current=unsorted->next; current != unsorted; current=current->next)
            {
                if(current->total > current_high->total)
                {
                    before_high = current->prev;
                    current_high = current;
                    after_high = current->next;
                }
                current = current->next;
            }
            before_high->next = after_high;
            after_high->prev = before_high;
    
    
            new_list_add(high_head, current_high);
            delete_current(current_high);
        }
        head = high_head;
    
    }

  12. #12
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Ok is this right?
    No, sorry, it looks as if I got you confused. The second part of my post mentioned a different method of sorting the list. Not something you should add to the code you have.

    Just do something like:
    Code:
    NODE* sort(NODE *new_list, NODE *head) /* funtion returns pointer to the sorted head */
    {
        NODE *unsorted = head;  /* head of unsorted list */
        NODE *current;
        NODE *high_head = NULL; /* head of sorted list */
        NODE *current_high;
    
        while(unsorted != NULL)
        {
            current_high = current = unsorted;
            current = current->next;
            while(current != unsorted)
            {
                if(current->total > current_high->total)
                {
                    current_high = current;
                }
                current = current->next;
            }
    
            new_list_add(high_head, current_high);
            delete_current(current_high);
        }
        return high_head; 
    }
    Does that work for you?

  13. #13
    Registered User
    Join Date
    Sep 2008
    Posts
    58
    Quote Originally Posted by mike_g View Post
    No, sorry, it looks as if I got you confused. The second part of my post mentioned a different method of sorting the list. Not something you should add to the code you have.

    Just do something like:
    Code:
    NODE* sort(NODE *new_list, NODE *head) /* funtion returns pointer to the sorted head */
    {
        NODE *unsorted = head;  /* head of unsorted list */
        NODE *current;
        NODE *high_head = NULL; /* head of sorted list */
        NODE *current_high;
    
        while(unsorted != NULL)
        {
            current_high = current = unsorted;
            current = current->next;
            while(current != unsorted)
            {
                if(current->total > current_high->total)
                {
                    current_high = current;
                }
                current = current->next;
            }
    
            new_list_add(high_head, current_high);
            delete_current(current_high);
        }
        return high_head; 
    }
    Does that work for you?
    im getting a seg fault in the sort function and in the new_list_add function

  14. #14
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Ok, you have problems with you add function as well.

    If this is what you have:
    Code:
    NODE new_list_add(NODE *sent, NODE *high)
    {
        NODE *new_node;
        new_node = (NODE *)malloc(sizeof(NODE));
        sent->prev->next = new_node;
        new_node->prev = sent->prev;
        new_node->next = sent;
        sent->prev = new_node;
        new_node->total = high->total;
    }
    Firstly, you want to be returning a pointer to your new_node, not a NODE struct.

    Next, you need to figure out whats linking to where.
    "sent" would be the head of your sorted list.
    "high" would be the node to add.
    So, "sent->next" should point to new_node and "new_node->prev" should point to "sent"

    since you have a doubly linked list "new_node->next" should be set to NULL to terminate the list.

    Once you have created your new node, you should return the pointer to it as it will be the new head of your list.

    I think you want something like:
    Code:
    NODE* new_list_add(NODE *sent, NODE *high)
    {
        NODE *new_node;
        new_node = (NODE *)malloc(sizeof(NODE));
        sent->next = new_node;
        new_node->prev = sent;
        new_node->next = NULL;
        new_node->total = high->total;
        return new_node;
    }
    On a side note, in relation to delete_current, it should probably be declared void as it does not return anything. IE:
    Code:
    void delete_current(NODE *current)

  15. #15
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Okay, I avoided posting my definition of Remove and Put, so that you could finish it on your own (hopefully). I'll describe what they need to do though.
    Firstly though, You need to remove the node from the unsorted list before you add it to the sorted list. Again I will stress that this should be done entirely without any call to malloc during the whole time the sorting happens.
    So, you remove the node from the unsorted list list, and then you add it to the sorted list.
    Removing the node from the unsorted list generally involves finding its neighbours and setting them to point to each other instead of to the node you are removing. You also need to handle the special case of removing from the head of the list, which is why I passed in the pointer to the head of the unsorted list, so it could be updated when required.
    Putting the node in the sorted list involves Getting the node prior to the head node (which is actually the last node) and modifying one he pointers from each of those nodes to point to the node being inserted, AND you have to change both pointers in the new node to point back at the other two.

    mike_g: You need to understand one thing about what he is coding. In this list, the last node points back to the first node, not to NULL. In other words it is a ring-list. You can confirm this by looking at his print_list function.

    However, I now notice that he is using a sentinel as the first item in the list. You have made the necessary change for this above what I posted, already. Actually perhaps he will want to use malloc once afterall, to create the sentinel for the sorted list. Don't forget to free it!
    Last edited by iMalc; 10-19-2008 at 02:24 PM.
    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"

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 09:04 PM
  2. singly linked to doubly linked
    By jsbeckton in forum C Programming
    Replies: 10
    Last Post: 11-06-2005, 07:47 PM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 11:03 AM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 06:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21