help by sorting a simply linked list

Thread Solved
Reply

Join Date: Jun 2004
Posts: 2
Reputation: onickel is an unknown quantity at this point 
Solved Threads: 0
onickel onickel is offline Offline
Newbie Poster

help by sorting a simply linked list

 
1
  #1
Jun 8th, 2004
Hi!
Pls, somebody help me!! I'm stuck here since days. I don't know, what i'm doing wrong.
Attached Files
File Type: cpp bank.cpp (4.2 KB, 34 views)
Reply With Quote Quick reply to this message  
Join Date: Mar 2004
Posts: 1,620
Reputation: kc0arf is a jewel in the rough kc0arf is a jewel in the rough kc0arf is a jewel in the rough 
Solved Threads: 50
Team Colleague
kc0arf kc0arf is offline Offline
Posting Virtuoso

Re: help by sorting a simply linked list

 
0
  #2
Jun 8th, 2004
Hello,

I looked at your code, and it appears to be a bubble-sort. Here is what I would do.

1) Get yourself a nice sheet of paper, and a pencil.

2) Draw out your data structure.

[CODE]

+-------+ +------------------+ +------------------+
| head | | data | point | | data | point |
+-------+ +------------------+ +------------------+

[\CODE]

Remember to draw little boxes for the temp pointers and stuff too.

3) Go through your code by hand, and fill in the paper as the computer would during the iterations. Do not assume when doing this by hand. Go through the motions, and stick with it. You will find your error.

4) In my coding days, I was always sure to make a duplicate head pointer, just in case I messed up the transition somewhere. Guess it was mild parinoia.

Christian
Reply With Quote Quick reply to this message  
Join Date: Jun 2004
Posts: 10
Reputation: abu_sager is an unknown quantity at this point 
Solved Threads: 2
abu_sager abu_sager is offline Offline
Newbie Poster

Re: help by sorting a simply linked list

 
0
  #3
Jun 9th, 2004
Hello my brother
there is two way to sort a single linked list
First , swapping data but it is unsufficient (( suppose the data is very bug))
Second, swapping pointer is better but it's harder
here you are the two ways
Swapping the pointers
  1. void Sortable_List::sort()
  2. {
  3. Node *ptr1,*ptr2,*temp,*Imithead1,*Imithead2,*before;
  4. if (head != NULL) {
  5. ptr2 = head;
  6. ptr1 = head->next;
  7. //First Step Set the smallest value to head
  8. while(ptr1 != NULL ) {
  9. if (ptr2->data > ptr1->data ) {
  10. temp = ptr2;
  11. while(temp->next != ptr1)
  12. temp = temp->next;
  13. temp->next = ptr1->next;
  14. ptr1->next = ptr2;
  15. head = ptr1;}
  16. ptr1 = ptr1->next;
  17. ptr2 = head;}
  18.  
  19. ////////////////////////////////////////////
  20. ////////////////////////////////////////////
  21. before = head;
  22. Imithead1 = Imithead2 = head->next;
  23. while (Imithead1 != NULL) {
  24.  
  25. while (Imithead2 != NULL ) {
  26. ptr1 = ptr2 =Imithead2;
  27. while(ptr1 != NULL ) {
  28. if (ptr2->data > ptr1->data ) {
  29. temp = ptr2;
  30. while(temp->next != ptr1)
  31. temp = temp->next;
  32. before->next = ptr1;
  33. temp->next = ptr1->next;
  34. ptr1->next = ptr2;
  35. Imithead2 = ptr1;
  36.  
  37. }
  38. ptr1 = ptr1->next;
  39. ptr2 = Imithead2;
  40. }
  41. before = Imithead2;
  42. Imithead2 = Imithead2->next;
  43.  
  44. }
  45.  
  46. Imithead1 = Imithead1->next;
  47. Imithead2 = Imithead1;
  48. }
  49.  
  50.  
  51. }
  52.  
  53.  
  54. }

Swapping Data
  1. NodeEmp *Ptr1,*Ptr2;
  2. Ptr1 = Ptr2 = Emp;
  3. if (Emp != NULL && Emp->next != NULL){
  4. while (Ptr1 != NULL)
  5. {
  6. Ptr2= Ptr1;
  7. while(Ptr2!= NULL){
  8. swap(Ptr1,Ptr2);
  9. Ptr2 = Ptr2->next;
  10. }
  11. Ptr1 = Ptr1->next;
  12. }
  13. }
Reply With Quote Quick reply to this message  
Join Date: Jun 2004
Posts: 2
Reputation: onickel is an unknown quantity at this point 
Solved Threads: 0
onickel onickel is offline Offline
Newbie Poster

Re: help by sorting a simply linked list

 
0
  #4
Jun 11th, 2004
Originally Posted by onickel
Hi!
Pls, somebody help me!! I'm stuck here since days. I don't know, what i'm doing wrong.
Thanks to all people that replied.
I finally found the solution. I'm posting the method for sorting below:
  1. void List::listsort(){
  2. element *p, *n, *flag, *anterior;
  3. bool sortiert;
  4. do {
  5. p = head;
  6. n = head -> next;
  7. for (int i = 0; i< anzahl; i++) {
  8. if (p -> nummer < n -> nummer) {
  9. p = n;
  10. n = n-> next;
  11. sortiert = 1;
  12. } else {
  13. //jetzt wird geordnet
  14. sortiert = 0;
  15. flag = n;
  16. p -> next = flag -> next; //p (tail) mußt zu 0 zeigen. Bevor: p -> n -> 0
  17. n -> next = p; //n -> p statt n -> 0
  18.  
  19. anterior = head;
  20. for (int j=1; j<i; j++) { //damit j=1 wird in eine vor p gehalten
  21. anterior = anterior -> next; //anterior wird bewegt genau vor p (anterior -> p -> n -> 0)
  22. }
  23. anterior -> next = n; //damit wird anterior Nachfolgers n
  24.  
  25. if (p -> next == 0) { //d.h. tail!!!!
  26. tail = p;
  27. n -> next = tail;
  28. number = (tail -> nummer) + 1; //der nächste nummer von tail
  29. } else {
  30. n = n -> next -> next;
  31. }
  32. // p = head;
  33. // n = head -> next;
  34. }
  35. }
  36. } while (!sortiert);
  37. }
P..S. i live in germany and this programm is for the university of münchen. Therefore, the comments are in german. And also, i come from ecuador, so my mother language is spanish. So, anterior means previous.
Reply With Quote Quick reply to this message  
Reply

This thread has been marked solved.
Perhaps start a new thread instead?
Message:


Thread Tools Search this Thread



About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC