How to sort my singly link list
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 10 of 10

Thread: How to sort my singly link list

  1. #1
    Join Date
    Oct 2008
    Posts
    9

    How to sort my singly link list

    Hey guy, I have a text file and stores each line into a link list. how do I sort my link list by my varible call myIntPacket? Everything works except for the sorting part. This is what i have so far:

    Code:
        
        //Start of sorting my link list
        temp = head;
        temp2 = temp->next;
        int exchange = 0;
        do
        {
            if(temp == 0)
            {
                cout << "Error..." << "\n";
            }
            else
            {           
    
                if(temp->myIntPacket > temp2->myIntPacket)
                {
                    swap(temp, temp2);
                    exchange = 1;
                    temp = temp->next;
                }            
            }
        }while(exchange != 0);  
        
    
    }
    Last edited by phamster; November 1st, 2009 at 04:27 PM.

  2. #2
    Join Date
    Apr 1999
    Posts
    27,426

    Re: How to sort my singly link list

    Quote Originally Posted by phamster View Post
    Hey guy, I have a text file and stores each line into a link list. how do I sort my link list by my varible call myIntPacket?
    First, please re-edit your post to use code tags. The code you posted is practically unreadable.

    Second, is there a reason why you just didn't use std::list, instead of trying to reinvent the wheel?

    Regards,

    Paul McKenzie

  3. #3
    Join Date
    Apr 1999
    Posts
    27,426

    Re: How to sort my singly link list

    In other words:
    Code:
    #include <list>
    #include <string>
    struct PacketStruct
    {
       int myIntPacket;
       std::string myStringPacket;
    };
    
    typedef std::list<PacketStruct> PacketList;
    
    int main()
    {
       PacketList packetList;
       PacketStruct ps;
       while(! openFile.eof())
       {
             getline(openFile, myLine);
             sequenceNum = string_to_int(myLine.substr(0,4));
             myData = myLine.substr(4,12);
             ps.myIntPacket = sequenceNum;
             ps.myStringPacket = myData;
             packetList.push_back( ps );
        }  
        //...
    //...
    }
    That is basically the whole code using std::list. To sort, all you need to do is call the std::list::sort() member function, and provide it a function that sorts two PacketStructs by the int member,
    Code:
    bool SortByInt(const PacketStruct& ps1, const PacketStruct& ps2)
    {
       // return true if ps1 comes before ps2, else return false;
    }
    When you want to sort by the string member, you provide a similar function that sorts two PacketStructs by the string member.

    The code you have now is very confused, in that you are attempting to create a linked list inside of main(). What you should be doing is creating a linked list class, and then all main() does is tell the class to add nodes, instead of having main() figure out how to add a node.

    To sort, you have to use a sort routine that works. Sorting isn't just writing a simple loop and exchanging adjacent elements. That will never sort the list. The simple bubble sort, insertion sort, etc. should have been used. Which sort technique were you suppose to use?

    But all of this is not necessary if you use std::list, as all of this work has been done already for you.

    Regards,

    Paul McKenzie

  4. #4
    Join Date
    Oct 2008
    Posts
    9

    Re: How to sort my singly link list

    Hi,

    Thanks for the quick reply. I didn't use anything other than a link list because the requirement is only to use link list. As for the sorting i was going with the bubble sort. Could you help me with this statement to help me sort the data?

    Code:
    temp = head;
        temp2 = temp->next;
        int exchange = 0;
        do
        {
            if(temp == 0)
            {
                cout << "Error..." << "\n";
            }
            else
            {           
    
                if(temp->myIntPacket > temp2->myIntPacket)
                {
                    swap(temp, temp2);
                    exchange = 1;
                    temp = temp->next;
                }            
            }
        }while(exchange != 0);

  5. #5
    Join Date
    May 2009
    Posts
    2,413

    Re: How to sort my singly link list

    Quote Originally Posted by phamster View Post
    Could you help me with this statement to help me sort the data?
    The first step is to be able to scan the list from beginning to end. You obviously know how to do that because you can print the list.

    The next step is to be able scan the whole list and to swap neighbouring elements if they're out of order.

    The final step is to be able to repeatedly scan the whole list until there's a full scan without any swaps, then the list is sorted.

  6. #6
    Join Date
    Oct 2008
    Posts
    9

    Re: How to sort my singly link list

    I was thinking to do a bubble sort I would use this for loop i created

    Code:
    for(int i = 0; i<numLines - 1; i++)
        {
            for(int j = 0; j < numLines -1; j++)
            {
                if(temp->myIntPacket > temp2->myIntPacket)
                {
                    swap(temp, temp2);
                    temp = temp->next;
                } 
            }
        }
    I think my problem here is not having the pointer pointing correct to the right node. Any suggestions?

  7. #7
    Join Date
    Apr 1999
    Posts
    27,426

    Re: How to sort my singly link list

    Quote Originally Posted by phamster View Post
    Hi,

    Thanks for the quick reply. I didn't use anything other than a link list because the requirement is only to use link list.
    A std::list is a linked list. I wouldn't mention it if it wasn't a linked list.

    Regards,

    Paul McKenzie

  8. #8
    Join Date
    Oct 2008
    Posts
    9

    Re: How to sort my singly link list

    Quote Originally Posted by Paul McKenzie View Post
    A std::list is a linked list. I wouldn't mention it if it wasn't a linked list.

    Regards,

    Paul McKenzie
    Thanks for helping me with this so far. Now all I need to do is Sort the list. This is where I'm still confuse at. So I have this:

    Code:
    while(! openFile.eof())
        {  
            numLines++;
            getline(openFile, myLine);
            sequenceNum = string_to_int(myLine.substr(0,4));
            myData = myLine.substr(4,12);
            ps.myIntPacket = sequenceNum;
            ps.myStringPacket = myData;
            packetList.push_back(ps);                
        } 
        cout << "Values before the sort" << "\n";
        typedef list<myPacketStruct>::const_iterator LI;
        for(LI i = packetList.begin(); i!=packetList.end(); i++)
        {
            const myPacketStruct& e = *i;
            cout << e.myIntPacket << "\n";
        }
    
        cout << "Values after the sort" << "\n";
        packetList.sort();
    I was trying to understand your function on swaping the value but i couldn't. Any suggestions?

  9. #9
    Join Date
    Apr 1999
    Posts
    27,426

    Re: How to sort my singly link list

    Quote Originally Posted by phamster View Post
    Thanks for helping me with this so far. Now all I need to do is Sort the list. This is where I'm still confuse at. So I have this:
    There are two versions of the sort() function.

    The first version takes no arguments, which is the one you used. The problem is that this version of sort() works only on lists that have items that can be compared using operator <.

    Your packet struct has no such comparison capabilities -- if I were to give you two packet structs, which one is less than the other? Since your packet structs do not have an operator < coded, the best option is to use the other form of the sort() function, and that is one that takes a single argument.

    The argument is a function pointer (or functor) that tells the sort() function how to order the elements.
    Code:
    packetList.sort( SortByInt );
    The SortByInt would be a function that takes two packetStructs, and returns true if the first packet struct is less than the second one, otherwise you return false.

    Look at my previous post. It shows an already written stub for SortByInt() -- you need to fill it in with the comparison. You also need to write a similar SortByString() that takes two packet structs and returns true if the first is less than the second.
    I was trying to understand your function on swaping the value but i couldn't. Any suggestions?
    There really is nothing to understand, because it doesn't do any swapping. The sort() function is doing the "swapping". The only thing that sort() needs to know is that it has two items, and which item comes before the other. That is when sort() will call the SortByInt() and ask "which one of these is less than the other?", and you respond with a true if the first is less than the second.

    Don't worry about the items given to you in SortByInt(), just answer the question that is being asked by returning the right value.

    Regards,

    Paul McKenzie

  10. #10
    Join Date
    Oct 2008
    Posts
    9

    Re: How to sort my singly link list

    Quote Originally Posted by Paul McKenzie View Post
    There are two versions of the sort() function.

    The first version takes no arguments, which is the one you used. The problem is that this version of sort() works only on lists that have items that can be compared using operator <.

    Your packet struct has no such comparison capabilities -- if I were to give you two packet structs, which one is less than the other? Since your packet structs do not have an operator < coded, the best option is to use the other form of the sort() function, and that is one that takes a single argument.

    The argument is a function pointer (or functor) that tells the sort() function how to order the elements.
    Code:
    packetList.sort( SortByInt );
    The SortByInt would be a function that takes two packetStructs, and returns true if the first packet struct is less than the second one, otherwise you return false.

    Look at my previous post. It shows an already written stub for SortByInt() -- you need to fill it in with the comparison. You also need to write a similar SortByString() that takes two packet structs and returns true if the first is less than the second.
    There really is nothing to understand, because it doesn't do any swapping. The sort() function is doing the "swapping". The only thing that sort() needs to know is that it has two items, and which item comes before the other. That is when sort() will call the SortByInt() and ask "which one of these is less than the other?", and you respond with a true if the first is less than the second.

    Don't worry about the items given to you in SortByInt(), just answer the question that is being asked by returning the right value.

    Regards,

    Paul McKenzie
    Thanks I have it sorted now. I thought when calling the SortByInt function you have to pass paramaters but I guess not!

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center