sorting a doubly linked list/node

[Susan.Adkins]

Alright, I must say that the problem my teacher has given us to do has
royally annoyed me.
We are to take a letter *txt file* and then read in the words.

Make 2 seperate lists *even and odd* for the number of occurances...

so the first time a word is entered its going to have an occurance of
one and be in the odd list then it is going to go to the next word see
if its in the odd list. If its not its going to check the even list. if
its in the even list it will add one to the occurance move it to the
odd list and then take it out of the evenlist. same goes for if its
found in the odd list... move then delete.

now i've got it working almost exactly. I just cannot figure out how to
make it in alphabetical order.

my code can be found on

http://mandalicious.com/itzaprincess/program5.htm

beacuse i dont want to post all that code here.. its a lot.
so yes if anyone has any ideas on which way to point me on how to get
my oddlist and even lists sorted... i will love you forever and a day!
thank you

Susan

 

[Alf P. Steinbach]

* (e-mail address removed):

Alright, I must say that the problem my teacher has given us to do has
royally annoyed me.
We are to take a letter *txt file* and then read in the words.

Make 2 seperate lists *even and odd* for the number of occurances...

so the first time a word is entered its going to have an occurance of
one and be in the odd list then it is going to go to the next word see
if its in the odd list. If its not its going to check the even list. if
its in the even list it will add one to the occurance move it to the
odd list and then take it out of the evenlist. same goes for if its
found in the odd list... move then delete.

now i've got it working almost exactly. I just cannot figure out how to
make it in alphabetical order.

my code can be found on

http://mandalicious.com/itzaprincess/program5.htm

beacuse i dont want to post all that code here.. its a lot.
so yes if anyone has any ideas on which way to point me on how to get
my oddlist and even lists sorted... i will love you forever and a day!
thank you

Are you sure that you have to have to implement the lists yourself?

The standard library provides std::list.

Also, are you sure it must be linked lists?

Because the execution time is then at best O(n^2) for n words.

Anyway, a few suggestions:

* Don't store data in the header node, let the header node be a
dummy node. That will simplify all of your code that currently
treats the header node as a special case.

* Try to remove all dead code, e.g. MAX_length and (it seems)
SortedList::data.

* Instead of member functions that modify their arguments, try to have
all arguments 'const' and return whatever the returned information is,
via the function result.

I know, this isn't going to help you sort, unless you can use std::list.

But it's going to significantly reduce the amount of work needed to
implementent sorting (which you can do by inserting each new word in its
sorted position).

 

[Ivan Vecerina]

: Alright, I must say that the problem my teacher has given us to do has
: royally annoyed me.
: We are to take a letter *txt file* and then read in the words.
:
: Make 2 seperate lists *even and odd* for the number of occurances...
....
: now i've got it working almost exactly. I just cannot figure out how to
: make it in alphabetical order.

Sorting linked lists is best achieved with the MergeSort algorithm:
http://en.wikipedia.org/wiki/Merge_sort
Of course, this is implemented by std::list::sort if you can use
standard library containers...

hth -Ivan