446,234 Members | 1,889 Online
Need help? Post your question and get tips & solutions from a community of 446,234 IT Pros & Developers. It's quick & easy.

# Sort list

 P: n/a 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 #include 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).number = 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).number << "\n"; q = (*q).next; } return 0; } //------------------------------ void getdata (int& grade_value) { cout << "\n\t\tEnter grade => "; cin >> num; } Jul 19 '05 #1
4 Replies

 P: n/a JC wrote in message news:P7********************@comcast.com... 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 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(); }; Jul 19 '05 #2

 P: n/a JC wrote: Hello, I'm running into a huge wall with linked lists. 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. 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 #include void numberIn (int& num); const int nil = 0; class node_type //declaration of class { public: int number; //info node_type *next; node_type( int in_number ) : number( in_number ), next( 0 ) { } }; 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; p = first = new node_type( num ); for (i = 2; i <= 5; ++i) { numberIn(num); newnode = new node_type; //create node (*newnode).number = num; (*newnode).next = nil; try doing these things in the constuctor newnode = new node_type( num ); Also - (*newnode).number can be more easily written as newnode->number (*p).next = newnode; if (p > p->next) { first = p->next; } The last five lines make no sense p = newnode; if ( p->number > first->number) // while ( p->number > first->number) { q = first; p = q->next; } 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; } } } q = first; cout << "\nThe list contains \n"; while (q != nil) //tests for end of list { cout << "number is :"<<(*q).number << "\n"; q = (*q).next; } return 0; } //------------------------------ void getdata (int& grade_value) { cout << "\n\t\tEnter grade => "; cin >> num; I suspect you mean "cin >> grade_value" } Jul 19 '05 #3

 P: n/a "JC" wrote in message news:P7********************@comcast.com... 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 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 Here is my code... ------------------------------------------------------- #include #include 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).number = 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).number << "\n"; q = (*q).next; } return 0; } //------------------------------ void getdata (int& grade_value) { cout << "\n\t\tEnter grade => "; cin >> num; } Jul 19 '05 #4

 P: n/a 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" wrote in message news:bp********@dispatch.concentric.net... JC wrote: Hello, I'm running into a huge wall with linked lists. 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. 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 #include void numberIn (int& num); const int nil = 0; class node_type //declaration of class { public: int number; //info node_type *next; node_type( int in_number ) : number( in_number ), next( 0 ) { } }; 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; p = first = new node_type( num ); for (i = 2; i <= 5; ++i) { numberIn(num); newnode = new node_type; //create node (*newnode).number = num; (*newnode).next = nil; try doing these things in the constuctor newnode = new node_type( num ); Also - (*newnode).number can be more easily written as newnode->number (*p).next = newnode; if (p > p->next) { first = p->next; } The last five lines make no sense p = newnode; if ( p->number > first->number) // while ( p->number > first->number) { q = first; p = q->next; } 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; } } } q = first; cout << "\nThe list contains \n"; while (q != nil) //tests for end of list { cout << "number is :"<<(*q).number << "\n"; q = (*q).next; } return 0; } //------------------------------ void getdata (int& grade_value) { cout << "\n\t\tEnter grade => "; cin >> num; I suspect you mean "cin >> grade_value" } Jul 19 '05 #5

### This discussion thread is closed

Replies have been disabled for this discussion.