help by sorting a simply linked list

Question

onickel 0 Newbie Poster

20 Years Ago

Hi!
Pls, somebody help me!! I'm stuck here since days. I don't know, what i'm doing wrong.

c

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

struct node {
  int nummer; //nummer der element
  struct node *next; //zeigt der Nachfolger
};
typedef struct node element; //neue Typ element

class List { // klasse fr die Erzeugung, Verwaltung, usw. der Liste
  int number, anzahl; //in anzahl wird der Anzahl der Elemente gespeichert 
  bool leerliste; //Zu wissen, ob die Liste leer ist
  element *head, *tail; //kopf, ende der Liste
public:
  List (void); //konstructor
  ~List(void); //destruktor
  void addelement (); //element hinfgen
  void removeelement(); //element lschen
  void printlist(); //Liste auf stdout zurckgeben
  int menu (); //auswahl menu
  void listsort(); //Liste sortieren -> bubble sort
};

List::List(void) {
  head = new element; //platz im memory fr neues element
  tail = head; //Am Anfang, die Liste ist Leer
  number = 1; //fngt mit dem 1ten Element
  anzahl = 0; //Es gibt noch keine Elemente
}

List :: ~List (void) {
  element *n;
  element *p;
  for (p = head; p != 0; p=n) {
    n = p->next;
    delete p;
  }
}

void List::listsort(){
  element *p, *n, *flag;
  bool sortiert;
  p = head;
  n = head -> next;
  do {
    sortiert = 1;
    while (n != 0) {
      if (p -> nummer < n -> nummer) {
	p = n;
	n = n-> next;
	sortiert = 0;
      } else {
	//jetzt wird geordnet
	sortiert = 0;
	flag = n;
	p -> next = flag -> next;
	n -> next = p;
	
	/*
	n = p;
	p= flag;
	tail -> next = 0;
	
	n -> next = p -> next;
	p = flag -> next; //p zeigt zu n
	//	n -> next = flag -> next; //flag hat die Adresse von n!!!! so flag -> next ist der nachfolger von n!!!
	*/
	p = n;
	n = n -> next;
	
	if (n -> next == 0) {  //d.h. tail!!!!
	  tail = n;  
	}
	//        p = head;
	//	n = head -> next;
      }
    }
  } while (!sortiert);
}

void List::removeelement () {
  element *aktuell, *naechste;
  int element;
  aktuell = head;
  naechste = head -> next;

  cout << endl << "Welches Element: ";
  cin >> element;

  if (anzahl != 0) { //Liste mut nicht leer sein!!
    for (int i=0; i < anzahl; i++) {  //sucht durch die Liste
      if (naechste -> nummer != element) { //wenn gewnschte element nicht gefunden...
	aktuell = naechste;  //aktuell ist nchste
	naechste = naechste -> next; //nchste von aktuell
      } else {
	number = (aktuell -> nummer) + 1; //nummer mut sein von aktuell + 1
	aktuell -> next = naechste -> next;  //aktuell zeigt jetz was nchste zeigt
	delete naechste;
	anzahl--;
	if (aktuell -> next == 0) {  //d.h. tail!!!!
	  tail = aktuell;  
	  number = (tail -> nummer) + 1; //nummer von tail + 1
	}
      }
    }
  }
}

void List::addelement() {
  tail -> next= new element; //Nachfolger von tail -> memory address fr neues element
  tail = tail -> next; // tail ist das neues element
  tail -> nummer = number; //schreibt nummer
  tail -> next = 0; //tail mut zu nichts zeigen!!!
  number ++; //nchste nummer fr das zukunftige Element
  anzahl++; //ein Element mehr in der Liste
}

void List::printlist() {
  if (anzahl != 0) { //Liste nicht leer!
    element *aktuell;
    aktuell = head -> next; //der Aktuelladress wird denselbe von Nachfolger heads
    while (aktuell != 0) { //hrt falls aktuell ist NULL
      cout << aktuell -> nummer << endl; //nummer von aktuelles Element
      aktuell = aktuell -> next; //nchste...
	}
  } else
    cout << endl << "Liste ist leer" << endl << endl;
}

int List::menu () {
 int wahl;

 cout << "Eroeffnen neu Filial..............1"<< endl;
 cout << "Loeschen Filial...................2" << endl;
 cout << "Siehe vorhandene Filiale..........3" << endl;
 cout << "Verlassen.........................4" << endl;
 cout << "Ihr Wahl: ";
 cin >> wahl;
 return wahl;

}

int main (int argc, char argv[]) {
  int wahl;
  bool taste;
  //  FILE *zentral;
  List a;  

  do {
  wahl= a.menu();
    switch (wahl) {
    case 1:  //neues Element
      a.addelement();
      //      a.listsort();
	taste = 1;
	break;   
    case 2: //Lsche Element       
	a.removeelement ();
	taste = 1;
	break;
    case 3: //Drcke Liste aus       
        a.listsort();
	a.printlist();
	taste = 1;
	break;
    case 4:  //Verlassen
	exit (0);
	break;
    default: 
      cout << "Ungueltiges Wahl" << endl << endl;
      taste = 1;
    }
  } while (taste);  
  //  fclose (zentral);


  return 0;
}

3 Contributors
3 Replies
110 Views
2 Days Discussion Span
Latest Post 20 Years Ago Latest Post by onickel

kc0arf 68 Posting Virtuoso

20 Years Ago

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.

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

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

Edited 11 Years Ago by Dani because: Formatting fixed

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

abu_sager 0 Newbie Poster · Answer 1 · 2004-06-09T18:15:39+00:00

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

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

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

onickel 0 Newbie Poster · Answer 2 · 2004-06-11T17:03:41+00:00

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:

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.