linkedlist sort

This is a discussion on linkedlist sort within the C++ Programming forums, part of the General Programming Boards category; I am new to the world of c++ and am trying to learn on my own i was wondering if ...

  1. #1
    Unregistered
    Guest

    linkedlist sort

    I am new to the world of c++ and am trying to learn on my own i was wondering if i have a linked list

    struct node
    {
    int item;
    node* next;
    };

    what would be the best wat to sort this list (in assending order)
    and could you please show me what that sort would look like
    thanks

  2. #2
    Evil Member
    Join Date
    Jan 2002
    Posts
    638
    Well unregged, you might have better luck using an STL list rather than a plain single link list.

    .sort() will automatically and quickly sort your list, provided operator< is defined for whatever data type the list is of.
    .reverse() will turn it around

    .copy() will dump the list into another iterator.

    .copy()'ing to ostream_iterator<WHATEVER_YOUR_TYPE_IS>(cout, "\n") will output it. You can change the \n to any delimiter you want.

    Load this, c/l/r it, then see if you can adapt it to your problem:



    Code:
    #include <iostream>
    #include <list>
    #include <string>         
    
       int main () {           
          list<string>f;
          f.push_back("Tarp");
          f.push_back("Yellow");
          f.push_back("Alpha");
          f.push_back("Doggie");
          f.push_back("Markers");
          f.push_back("Bush");
          copy(f.begin(), f.end(), ostream_iterator<string>(cout, "\n"));
          f.sort();
          cout << '\n';
          copy(f.begin(), f.end(), ostream_iterator<string>(cout, "\n"));
          f.reverse();
          cout << '\n';
          copy(f.begin(), f.end(), ostream_iterator<string>(cout, "\n"));
          return 0;
       }

    Enjoy

  3. #3
    Evil Member
    Join Date
    Jan 2002
    Posts
    638

    Exclamation

    Whoops put a using namespace std; in there, sorry.

  4. #4
    Something Clever ginoitalo's Avatar
    Join Date
    Dec 2001
    Posts
    187
    How can you overload the operator< for you own datatype that is stored in the list ?

    do you have an example using a class say Myclass sorting on the attribute char * (points to a new char array) maybe sorting alphabetically ?

  5. #5
    Unregistered
    Guest
    you could try this. not compiled. not tested:

    Code:
    //use keyword class if you prefer, but make members public then
    struct myStruct
    {
      char name[20];
      bool operator <(const & rhs);
    };
    
    //overload the < operator for myStruct
    //this will be case sensitive comparison!
    bool myStruct::operator <(const & rhs)
    {
      if(strcmp(name, rhs.name) < 0)
        return true;
      return false;
    }
    
    //create list using type myStruct as type in list
    list <myStruct> myList;
    
    //variables for loop counter and to hold user input 
    int i;
    myStruct dummy;
    
    //add 5 instances of myStruct to end of myList using user input
    for(i = 0; i < 5; i++)
    {
      cout << "enter a name without spaces" << endl;
      cin >> myStruct.name;
      myList.push_back(myStruct);
    }
    
    //sort myList alphabetically using list::sort()
    //uses overloaded < operator for type myStruct
    myList.sort();

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Straight Insertion Sort function problem
    By StaticKyle in forum C++ Programming
    Replies: 6
    Last Post: 05-12-2008, 04:03 AM
  2. Calculator + LinkedList
    By maro009 in forum C++ Programming
    Replies: 20
    Last Post: 05-17-2005, 12:56 PM
  3. threaded merge sort
    By AusTex in forum Linux Programming
    Replies: 4
    Last Post: 05-04-2005, 04:03 AM
  4. Sorting
    By vasanth in forum A Brief History of Cprogramming.com
    Replies: 12
    Last Post: 11-10-2003, 04:21 PM
  5. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 07:05 PM

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