-
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
-
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
-
Whoops put a using namespace std; in there, sorry.
-
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 ?
-
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();