sorting the nodes

J

jw

hi all,i have such 2 classes for a linked list,
class Node{
private:
int value;
Node *next;
public:
Node()
{
next=NULL;
}
friend class List;
};
class List{
private:
Node *head,*tail,*TOP;
void append(Node *add);
public:
List()
{
TOP=new Node;
head=tail=TOP;
}
void sortAll();...
 
H

Howard

jw said:
hi all,i have such 2 classes for a linked list,
class Node{
private:
int value;
Node *next;
public:
Node()
{
next=NULL;
}
friend class List;
};
class List{
private:
Node *head,*tail,*TOP;
void append(Node *add);
public:
List()
{
TOP=new Node;
head=tail=TOP;
}
void sortAll();...

You already said how you would do it: use an insertion sort. Read your
textbook on how to do an insertion sort. (But note: you generally don't
call an insertion sort after the list is already built. It's something
that's usually done as you read in or otherwise enter the data, and insert
it into the list. Thus the term "insertion".)

BTW: what is the tail pointer for? If you've got a singly-linked list like
this (where each node only has a next pointer), then there's no need for a
tail pointer, since the last (tail) node is identifiable by the fact that
its next pointer is NULL. And it's pretty useless to have, since you have
to maintain it, and can't use it for much due to the fact that you don't
have a previous pointer, so you can't manuipulate the tail without
traversing the list anyway.

And what's "TOP"?

-Howard
 
J

jw

Howard said:
You already said how you would do it: use an insertion sort. Read your
textbook on how to do an insertion sort. (But note: you generally don't
call an insertion sort after the list is already built. It's something
that's usually done as you read in or otherwise enter the data, and insert
it into the list. Thus the term "insertion".)
i have to first create the list and then sort it by swaping the nodes
BTW: what is the tail pointer for? If you've got a singly-linked list like
this (where each node only has a next pointer), then there's no need for a
tail pointer, since the last (tail) node is identifiable by the fact that
its next pointer is NULL. And it's pretty useless to have, since you have
to maintain it, and can't use it for much due to the fact that you don't
have a previous pointer, so you can't manuipulate the tail without
traversing the list anyway.

And what's "TOP"?
TOP is a pointer that is not necessary but i use it as an empty node
before the head
 
H

Howard

i have to first create the list and then sort it by swaping the nodes

Then that's not an insertion sort. An insertion sort inserts the data in
the correct location in the first place.

Decide which sort you want to use (e.g., bubble sort), then implement that.
Your textbook (or class notes) should show how to implement each of the most
common sorts.

If you have a C++ language problem while implementing your sort, post the
code here, and explain the problem you're having with it. (But don't expect
us to simply write the code for you.)

-Howard
 
J

jw

Howard said:
Then that's not an insertion sort. An insertion sort inserts the data in
the correct location in the first place.

Decide which sort you want to use (e.g., bubble sort), then implement that.
Your textbook (or class notes) should show how to implement each of the most
common sorts.
ok the sort tecnique is not important now,the thing i have to is to
sort the nodes,and i dont expect a code only a way
 
H

Howard

ok the sort tecnique is not important now,the thing i have to is to
sort the nodes,and i dont expect a code only a way

That's what your textbook and class notes are for. But it involves two
things: traversing the list somehow, and swapping nodes that are out of
order.

For something like a bubble sort, you effectively traverse the list multiple
times, using nested loops. Something like this:

for each node I in the last _except_ the last one:
for each node J _after_ I in the list:
if the data value in I is greater than the data value in J, then:
swap nodes I and J

(For descending sort, change "greater than" to "less than".)

So you need to know how to swap in a singly linked list. Do you? It
requires four pointers: one for each node to be swapped, and one for each of
the nodes _preceding_ the nodes to be swapped (because you need to modify
their "next" pointers, right?). NOTE that if your node I in the algorithm
above is the head node, then when you go to swap it, there IS NO preceding
node! In that case, you'll need to identify that special case and modify
the "head" pointer instead.

Work it out on paper, if your textbook or class notes don't contain the
details. Then turn the design into some real code.

-Howard
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top