Ad:

C Discussion Thread
Marked Solved
Views: 8566

Permalink

Jun 8th, 2004

help by sorting a simply linked list

Expand Post »

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, 162 views)

Similar Threads

onickel

Reputation Points: 11

Solved Threads: 0

Newbie Poster

Offline

2 posts
since Jun 2004

Permalink

Jun 8th, 2004

Re: help by sorting a simply linked list

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

kc0arf

Team Colleague

Reputation Points: 121

Solved Threads: 57

Posting Virtuoso

Offline

1,629 posts
since Mar 2004

Permalink

Jun 9th, 2004

Re: help by sorting a simply linked list

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

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

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;
		}
	}

abu_sager

Reputation Points: 12

Solved Threads: 2

Newbie Poster

Offline

10 posts
since Jun 2004

Permalink

Jun 11th, 2004

Re: help by sorting a simply linked list

Quote 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:

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.

onickel

Reputation Points: 11

Solved Threads: 0

Newbie Poster

Offline

2 posts
since Jun 2004

This thread is solved

Either the thread starter or a moderator has marked this thread as solved. You can most likely trust the responses and answers given. There is most likely no reason for any further responses to be posted here. If you have a related question, please start a new thread in this forum instead.

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C Forum Timeline: quadratic equation

Next Thread in C Forum Timeline: c vs h header files...

DaniWeb Message

Cancel Changes

User Name
Password