DaniWeb Forum Index > Software Development > C

C RSS

help by sorting a simply linked list

Thread Solved

•

Join Date: Jun 2004

Posts: 2

Reputation: onickel is an unknown quantity at this point

Solved Threads: 0

onickel

Offline

Newbie Poster

help by sorting a simply linked list

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

bank.cpp (4.2 KB, 34 views)

•

Join Date: Mar 2004

Posts: 1,620

Reputation: kc0arf is a jewel in the rough

Solved Threads: 50

kc0arf

Offline

Posting Virtuoso

Re: help by sorting a simply linked list

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

•

Join Date: Jun 2004

Posts: 10

Reputation: abu_sager is an unknown quantity at this point

Solved Threads: 2

abu_sager

Offline

Newbie Poster

Re: help by sorting a simply linked list

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

 Help with Code Tags 
 C Syntax (Toggle Plain Text) 
void Sortable_List::sort()
{
	Node *ptr1,*ptr2,*temp,*Imithead1,*Imithead2,*before;
	if (head != NULL) {
		ptr2 = head;
		ptr1 = head->next;
		//First Step Set the smallest value to head
		while(ptr1 != NULL ) {
			if (ptr2->data > ptr1->data ) {
				temp = ptr2;
				while(temp->next != ptr1) 
					temp = temp->next;
				temp->next = ptr1->next;
				ptr1->next = ptr2;
				head = ptr1;}
			ptr1 = ptr1->next;
			ptr2 = head;}
 
////////////////////////////////////////////
////////////////////////////////////////////
		before = head;
		Imithead1 = Imithead2 = head->next;
		while (Imithead1 != NULL) {
 
		while (Imithead2 != NULL ) {
			ptr1 = ptr2 =Imithead2;
			while(ptr1 != NULL ) {
				if (ptr2->data > ptr1->data ) {
					temp = ptr2;
					while(temp->next != ptr1) 
						temp = temp->next;
					before->next = ptr1;
					temp->next = ptr1->next;
					ptr1->next = ptr2;
					Imithead2 = ptr1;
 
				}
				ptr1 = ptr1->next;
				ptr2 = Imithead2;
			}
			before = Imithead2;
			Imithead2 = Imithead2->next;
 
		}
 
		Imithead1 = Imithead1->next;
		Imithead2 = Imithead1;
		}
 
 
	}
 
 
}
void Sortable_List::sort()
{
	Node *ptr1,*ptr2,*temp,*Imithead1,*Imithead2,*before;
	if (head != NULL) {
		ptr2 = head;
		ptr1 = head->next;
		//First Step Set the smallest value to head
		while(ptr1 != NULL ) {
			if (ptr2->data > ptr1->data ) {
				temp = ptr2;
				while(temp->next != ptr1) 
					temp = temp->next;
				temp->next = ptr1->next;
				ptr1->next = ptr2;
				head = ptr1;}
			ptr1 = ptr1->next;
			ptr2 = head;}
		
////////////////////////////////////////////
////////////////////////////////////////////
		before = head;
		Imithead1 = Imithead2 = head->next;
		while (Imithead1 != NULL) {
			
		while (Imithead2 != NULL ) {
			ptr1 = ptr2 =Imithead2;
			while(ptr1 != NULL ) {
				if (ptr2->data > ptr1->data ) {
					temp = ptr2;
					while(temp->next != ptr1) 
						temp = temp->next;
					before->next = ptr1;
					temp->next = ptr1->next;
					ptr1->next = ptr2;
					Imithead2 = ptr1;
			
				}
				ptr1 = ptr1->next;
				ptr2 = Imithead2;
			}
			before = Imithead2;
			Imithead2 = Imithead2->next;
			
		}
		
		Imithead1 = Imithead1->next;
		Imithead2 = Imithead1;
		}

		
	}
	
	
}

Swapping Data

 Help with Code Tags 
 C Syntax (Toggle Plain Text) 
	NodeEmp *Ptr1,*Ptr2;
	Ptr1 = Ptr2 = Emp;
	if (Emp != NULL && Emp->next != NULL){
		while (Ptr1 != NULL)
		{		
			Ptr2= Ptr1;
		             while(Ptr2!= NULL){
			swap(Ptr1,Ptr2);				
			Ptr2 = Ptr2->next;				
		}
		Ptr1 = Ptr1->next;
		}
	}
	NodeEmp *Ptr1,*Ptr2;
	Ptr1 = Ptr2 = Emp;
	if (Emp != NULL && Emp->next != NULL){
		while (Ptr1 != NULL)
		{		
			Ptr2= Ptr1;
		             while(Ptr2!= NULL){
			swap(Ptr1,Ptr2);				
			Ptr2 = Ptr2->next;				
		}
		Ptr1 = Ptr1->next;
		}
	}

•

Join Date: Jun 2004

Posts: 2

Reputation: onickel is an unknown quantity at this point

Solved Threads: 0

onickel

Offline

Newbie Poster

Re: help by sorting a simply linked list

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:

 Help with Code Tags 
 C Syntax (Toggle Plain Text) 
void List::listsort(){
  element *p, *n, *flag, *anterior;
  bool sortiert;
  do {
    p = head;
    n = head -> next;
    for (int i = 0; i< anzahl; i++) {
      if (p -> nummer < n -> nummer) {
        p = n;
        n = n-> next;
        sortiert = 1;
      } else {
        //jetzt wird geordnet
        sortiert = 0;
        flag = n;
        p -> next = flag -> next; //p (tail) mußt zu 0 zeigen. Bevor: p -> n -> 0
        n -> next = p; //n -> p statt n -> 0
 
        anterior = head;
        for (int j=1; j<i; j++) { //damit j=1 wird in eine vor p gehalten
          anterior = anterior -> next; //anterior wird bewegt genau vor p (anterior -> p -> n -> 0)
        }
        anterior -> next = n; //damit wird anterior Nachfolgers n
 
        if (p -> next == 0) {  //d.h. tail!!!!
          tail = p;
          n -> next = tail;
          number = (tail -> nummer) + 1; //der nächste nummer von tail
        }       else {
        n = n -> next -> next;
        }
        //        p = head;
        //      n = head -> next;
      }
    }
  } while (!sortiert);
}
void List::listsort(){
  element *p, *n, *flag, *anterior;
  bool sortiert;
  do {
    p = head;
    n = head -> next;
    for (int i = 0; i< anzahl; i++) {
      if (p -> nummer < n -> nummer) {
        p = n;
        n = n-> next;
        sortiert = 1;
      } else {
        //jetzt wird geordnet
        sortiert = 0;
        flag = n;
        p -> next = flag -> next; //p (tail) mußt zu 0 zeigen. Bevor: p -> n -> 0
        n -> next = p; //n -> p statt n -> 0

        anterior = head;
        for (int j=1; j<i; j++) { //damit j=1 wird in eine vor p gehalten
          anterior = anterior -> next; //anterior wird bewegt genau vor p (anterior -> p -> n -> 0)
        }
        anterior -> next = n; //damit wird anterior Nachfolgers n

        if (p -> next == 0) {  //d.h. tail!!!!
          tail = p;
          n -> next = tail;
          number = (tail -> nummer) + 1; //der nächste nummer von tail
        }       else {
        n = n -> next -> next;
        }
        //        p = head;
        //      n = head -> next;
      }
    }
  } while (!sortiert);
}

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.