Sort list

[JC]

Hello,

I'm running into a huge wall with linked lists.

If anyone outhere can help me, I'll appreciate it very much.

Here is my delima!
I need to create a simple list of numbers.
which I can do, by assigning the pointer to *next.

but I also have to do it in sortorder.
so if I enter the number 5, 4, 10, 2

when I display the list is should look like

2, 4, 5, 10.

Again, thank you for all of your help... sorry to be a pain with such a
simple problem... (hmm, i think I need some rest..._

JC


Here is my code...
-------------------------------------------------------

#include <iostream>
#include <fstream>

void numberIn (int& num);
const int nil = 0;

class node_type //declaration of class
{
public:
int number; //info
node_type *next;
};

int main()
{
node_type *first, *p, *q, *newnode;
int i, num;
first = new node_type;
p = first;
numberIn(num);
(*first).number = num;
(*first).next = nil;

for (i = 2; i <= 5; ++i)
{
numberIn(num);
newnode = new node_type; //create node
(*newnode).numb er = num;
(*newnode).next = nil;
(*p).next = newnode;

if (p > p->next)
{
first = p->next;
}
p = newnode;


if ( p->number > first->number)
// while ( p->number > first->number)
{
q = first;
p = q->next;
}

}

q = first;
cout << "\nThe list contains \n";

while (q != nil) //tests for end of list
{
cout << "number is :"<<(*q).num ber << "\n";
q = (*q).next;
}

return 0;
}
//------------------------------

void getdata (int& grade_value)
{
cout << "\n\t\tEnte r grade => ";
cin >> num;
}

[Deming He]

Re: Sort list

JC <keepit@secret. com> wrote in message
news:P7WdnYx7t8 jllCqiRVn-vA@comcast.com. ..[color=blue]
> Hello,
>
> I'm running into a huge wall with linked lists.
>
> If anyone outhere can help me, I'll appreciate it very much.
>
> Here is my delima!
> I need to create a simple list of numbers.
> which I can do, by assigning the pointer to *next.
>
> but I also have to do it in sortorder.
> so if I enter the number 5, 4, 10, 2
>
> when I display the list is should look like
>
> 2, 4, 5, 10.
>
> Again, thank you for all of your help... sorry to be a pain with such a
> simple problem... (hmm, i think I need some rest..._
>
> JC
>
>[/color]
This should get you started...

struct Node
{
void* Element;
struct Node *Next;
};


class List
{
public:
struct Node *Head;
void insert(void* data);//Find the right location in the list based on your
numbers
//& insert a new created node there
void* pop();//Read the head element
List() { Head = NULL; }
~List();
};

[Gianni Mariani]

Re: Sort list

JC wrote:[color=blue]
> Hello,
>
> I'm running into a huge wall with linked lists.[/color]

You can use one of the standard containers ...

an std::multimap will allow you to insert random objects and will
provide a sorted iterator when you're finished inserting.
[color=blue]
>
> If anyone outhere can help me, I'll appreciate it very much.
>
> Here is my delima!
> I need to create a simple list of numbers.
> which I can do, by assigning the pointer to *next.
>
> but I also have to do it in sortorder.
> so if I enter the number 5, 4, 10, 2
>
> when I display the list is should look like
>
> 2, 4, 5, 10.
>
> Again, thank you for all of your help... sorry to be a pain with such a
> simple problem... (hmm, i think I need some rest..._
>
> JC
>
>
> Here is my code...
> -------------------------------------------------------
>
> #include <iostream>
> #include <fstream>
>
> void numberIn (int& num);
> const int nil = 0;
>
> class node_type //declaration of class
> {
> public:
> int number; //info
> node_type *next;[/color]

node_type( int in_number )
: number( in_number ), next( 0 )
{
}
[color=blue]
> };
>
> int main()
> {
> node_type *first, *p, *q, *newnode;
> int i, num;
> first = new node_type;
> p = first;
> numberIn(num);
> (*first).number = num;
> (*first).next = nil;[/color]

p = first = new node_type( num );

[color=blue]
>
> for (i = 2; i <= 5; ++i)
> {
> numberIn(num);
> newnode = new node_type; //create node
> (*newnode).numb er = num;
> (*newnode).next = nil;[/color]

try doing these things in the constuctor
newnode = new node_type( num );

Also - (*newnode).numb er can be more easily written as
newnode->number

[color=blue]
> (*p).next = newnode;
>
> if (p > p->next)
> {
> first = p->next;
> }[/color]

The last five lines make no sense
[color=blue]
> p = newnode;
>
>
> if ( p->number > first->number)
> // while ( p->number > first->number)
> {
> q = first;
> p = q->next;
> }[/color]

I think you need some logic like the one below.

p = first;
q = 0;

while ( p )
{
if ( p->number < newnode->number )
{
q = p;
p = p->next;
}
else
{
if ( q )
{
q->next = newnode;
newnode->next = p;
}
else
{
first = newnode;
newnode->next = p;
}
p = 0;
newnode = 0;
}
}

if ( newnode )
{
if ( q )
{
q->next = newnode;
}
else
{
first = newnode;
}
}
[color=blue]
>
> }
>
> q = first;
> cout << "\nThe list contains \n";
>
> while (q != nil) //tests for end of list
> {
> cout << "number is :"<<(*q).num ber << "\n";
> q = (*q).next;
> }
>
> return 0;
> }
> //------------------------------[/color]

[color=blue]
>
> void getdata (int& grade_value)
> {
> cout << "\n\t\tEnte r grade => ";
> cin >> num;[/color]

I suspect you mean "cin >> grade_value"
[color=blue]
> }[/color]

[paul]

Re: Sort list

"JC" <keepit@secret. com> wrote in message
news:P7WdnYx7t8 jllCqiRVn-vA@comcast.com. ..[color=blue]
> Hello,
>
> I'm running into a huge wall with linked lists.
>
> If anyone outhere can help me, I'll appreciate it very much.
>
> Here is my delima!
> I need to create a simple list of numbers.
> which I can do, by assigning the pointer to *next.
>
> but I also have to do it in sortorder.
> so if I enter the number 5, 4, 10, 2
>
> when I display the list is should look like
>
> 2, 4, 5, 10.
>
> Again, thank you for all of your help... sorry to be a pain with such a
> simple problem... (hmm, i think I need some rest..._
>
> JC
>[/color]

One thing I've found handy for linked lists is to traverse the code and find
out
where you want to insert the new node before you begin the actual insertion
process. Like so...

1. format new node to go in list
2. traverse the list until you find the node that comes just before your new
node
3. save the "next" pointer from the current node
4. change the "next" pointer in the current node to point to the new node
(created in step 1)
5. set the "next" pointer in the new node to hold the saved pointer (from
step 3)

The list is now maintained in order, rather than having to insert at the end
and then re-sort. Of course this only matters if you care about the order
of retrieval.

Paul

[color=blue]
>
> Here is my code...
> -------------------------------------------------------
>
> #include <iostream>
> #include <fstream>
>
> void numberIn (int& num);
> const int nil = 0;
>
> class node_type //declaration of class
> {
> public:
> int number; //info
> node_type *next;
> };
>
> int main()
> {
> node_type *first, *p, *q, *newnode;
> int i, num;
> first = new node_type;
> p = first;
> numberIn(num);
> (*first).number = num;
> (*first).next = nil;
>
> for (i = 2; i <= 5; ++i)
> {
> numberIn(num);
> newnode = new node_type; //create node
> (*newnode).numb er = num;
> (*newnode).next = nil;
> (*p).next = newnode;
>
> if (p > p->next)
> {
> first = p->next;
> }
> p = newnode;
>
>
> if ( p->number > first->number)
> // while ( p->number > first->number)
> {
> q = first;
> p = q->next;
> }
>
> }
>
> q = first;
> cout << "\nThe list contains \n";
>
> while (q != nil) //tests for end of list
> {
> cout << "number is :"<<(*q).num ber << "\n";
> q = (*q).next;
> }
>
> return 0;
> }
> //------------------------------
>
> void getdata (int& grade_value)
> {
> cout << "\n\t\tEnte r grade => ";
> cin >> num;
> }
>
>
>
>[/color]

[JC]

Re: Sort list

Hi Gianni,

thank you for clearing things up... I think that my problem was that I was
trying to do too much with *first,
thanks for the detail information.

also, I want to thank Deming He and Paul for helping me understand Lists.
Now I have to get back to work... second part of the project...

Thank you again!
JC


"Gianni Mariani" <gi2nospam@mari ani.ws> wrote in message
news:bp7e0v$6mp @dispatch.conce ntric.net...[color=blue]
> JC wrote:[color=green]
> > Hello,
> >
> > I'm running into a huge wall with linked lists.[/color]
>
> You can use one of the standard containers ...
>
> an std::multimap will allow you to insert random objects and will
> provide a sorted iterator when you're finished inserting.
>[color=green]
> >
> > If anyone outhere can help me, I'll appreciate it very much.
> >
> > Here is my delima!
> > I need to create a simple list of numbers.
> > which I can do, by assigning the pointer to *next.
> >
> > but I also have to do it in sortorder.
> > so if I enter the number 5, 4, 10, 2
> >
> > when I display the list is should look like
> >
> > 2, 4, 5, 10.
> >
> > Again, thank you for all of your help... sorry to be a pain with such a
> > simple problem... (hmm, i think I need some rest..._
> >
> > JC
> >
> >
> > Here is my code...
> > -------------------------------------------------------
> >
> > #include <iostream>
> > #include <fstream>
> >
> > void numberIn (int& num);
> > const int nil = 0;
> >
> > class node_type //declaration of class
> > {
> > public:
> > int number; //info
> > node_type *next;[/color]
>
> node_type( int in_number )
> : number( in_number ), next( 0 )
> {
> }
>[color=green]
> > };
> >
> > int main()
> > {
> > node_type *first, *p, *q, *newnode;
> > int i, num;
> > first = new node_type;
> > p = first;
> > numberIn(num);
> > (*first).number = num;
> > (*first).next = nil;[/color]
>
> p = first = new node_type( num );
>
>[color=green]
> >
> > for (i = 2; i <= 5; ++i)
> > {
> > numberIn(num);
> > newnode = new node_type; //create node
> > (*newnode).numb er = num;
> > (*newnode).next = nil;[/color]
>
> try doing these things in the constuctor
> newnode = new node_type( num );
>
> Also - (*newnode).numb er can be more easily written as
> newnode->number
>
>[color=green]
> > (*p).next = newnode;
> >
> > if (p > p->next)
> > {
> > first = p->next;
> > }[/color]
>
> The last five lines make no sense
>[color=green]
> > p = newnode;
> >
> >
> > if ( p->number > first->number)
> > // while ( p->number > first->number)
> > {
> > q = first;
> > p = q->next;
> > }[/color]
>
> I think you need some logic like the one below.
>
> p = first;
> q = 0;
>
> while ( p )
> {
> if ( p->number < newnode->number )
> {
> q = p;
> p = p->next;
> }
> else
> {
> if ( q )
> {
> q->next = newnode;
> newnode->next = p;
> }
> else
> {
> first = newnode;
> newnode->next = p;
> }
> p = 0;
> newnode = 0;
> }
> }
>
> if ( newnode )
> {
> if ( q )
> {
> q->next = newnode;
> }
> else
> {
> first = newnode;
> }
> }
>[color=green]
> >
> > }
> >
> > q = first;
> > cout << "\nThe list contains \n";
> >
> > while (q != nil) //tests for end of list
> > {
> > cout << "number is :"<<(*q).num ber << "\n";
> > q = (*q).next;
> > }
> >
> > return 0;
> > }
> > //------------------------------[/color]
>
>[color=green]
> >
> > void getdata (int& grade_value)
> > {
> > cout << "\n\t\tEnte r grade => ";
> > cin >> num;[/color]
>
> I suspect you mean "cin >> grade_value"
>[color=green]
> > }[/color]
>[/color]