Thread: sorting a double linked list

  1. #1
    Registered User
    Join Date
    Sep 2001
    Posts
    44

    Question sorting a double linked list

    Hello,

    I've attempted to sort a double linked list, alphabetically by its member 'name' which is a character string, and it doesn't seem to work. It either goes into an endless loop, or it sorts them around, and puts em back in their original order. I used a typical bubble sort, and it worked fine in an array of character strings, but I suppose it doesn't work well for a linked list.

    Heres the code I used:

    Code:
    	COMMAND_DATA *cmd, *cmd2, *temp;
    
    	for(cmd=first_command;cmd!=NULL;cmd=cmd->next){
    		for(cmd2=first_command;cmd2!=NULL;cmd=cmd2->next){
    			if(cmd->name<cmd2->name){
    				temp=cmd;
    				cmd=cmd2;
    				cmd2=temp;
    			}
    		}
    	}
    Could someone please enlighten me on a way that will actually work? Or tell me if I made a stupid mistake? Thanks.
    [Strut]

    I lay on my bed watching the stars, and I thought to myself... Where the hell is my roof?

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Well for one:
    >>>
    cmd2 = first_command;
    cmd2 != NULL;
    cmd = cmd2->next
    <<<
    I'm sure you see it by now...(and here's a good argument for using unique names )

    Also, you can't compare character arrays as you would numbers. All you're doing is comparing their addresses. Use strcmp or stricmp. They return negative if the first string is 'less' than the second, positive if otherwise, and zero if they are identical.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  3. #3
    Registered User
    Join Date
    Sep 2001
    Posts
    44

    Thanks. :)

    Thank you, I'll see what I can do with that. Although I must say I've rewritten that loops several several times, and it might just be a typo for when I posted it(i had to type it up real quick, becuase I deleted the code in the program I was writing).

    However, the comparing addresses I most definitley didn't know about. I figured itd work the same as comapring character arrays, or something of the sort.

    Thanks again.

    Oh, and on the unique names I used cmd2 sort of as a form to know that it was the second one running through the list. I suppose you could use it as an argument, and maybe changing it would prevent any typos... but the rest of my code is a little more unique in the names.
    Last edited by Strut; 10-18-2002 at 09:06 PM.
    [Strut]

    I lay on my bed watching the stars, and I thought to myself... Where the hell is my roof?

  4. #4
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Ok, now that I have some more time I will explain to you what's wrong with your program. Look at how a doubly linked list is structured:

    Code:
    NULL <- h -> n <- n -> n
            h <- n -> n <- n -> NULL
    ...where each double-stacked letter is a single node.

    Now look at your code. You are basically sorting pointers! Making iterator 'cmd' point to the object pointed to by 'cmd2', and so forth. An iterator merely 'stands in the shoes' of the current list object. It is *not* the object itself. Thus, the only useful thing to do is 'comandeer' the object's 'next' and 'previous' pointers. This is how you sort a linked list.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  5. #5
    Registered User
    Join Date
    Sep 2001
    Posts
    44

    hmm..

    Well, after staring at the code for a few hours, and thinking hard about how pointers worked I came up with a similiar conclusion. I figured I was just making cmd, and cmd2 point at each other. Simple enough?

    Not sure exactley how I'm supposed to 'commondeer', but I suppose I came up with a work around.

    Being as the commands are saved in a file, and loaded later... I figure I grab all the command names, put em in an array, sort the array, and then save the commands in the order of the array. Good enough, eh?

    One problem... how do I allocate memory as needed for a multideminsional array? command_names[][]; ?

    If no one replies soon, I'll make a new post.
    [Strut]

    I lay on my bed watching the stars, and I thought to myself... Where the hell is my roof?

  6. #6
    Registered User
    Join Date
    Sep 2001
    Posts
    44

    oops

    Ignore this. :P
    Last edited by Strut; 10-19-2002 at 04:32 AM.
    [Strut]

    I lay on my bed watching the stars, and I thought to myself... Where the hell is my roof?

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, 08:04 PM
  2. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  3. Problem with linked list ADT and incomplete structure
    By prawntoast in forum C Programming
    Replies: 1
    Last Post: 04-30-2005, 01:29 AM
  4. How to use Linked List?
    By MKashlev in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 07:11 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM