[Gelöst] Sortierung von einfach verketteter Liste



  • Hallo liebe C++-Gemeinde 🙂 ,
    Ich habe mich prüfungsvorbereitend (Informatik für Physiker)
    mit einfachen Progammieraufgaben beschäftigt.

    Ich weiß das ich für diese Aufgabe besser eine doppelt verkettete Liste nehme,
    aber das Programm ist einfach immer weiter "gewachsen" und ich denke lösbar
    sollte es eigentlich auch so sein.

    Zum Problem:

    Ich wollte nur eine verkettete Liste mit Namen und Alter als Daten,
    die sortiert wird und in einer Extra-Datei und mit cout ausgegeben wird.
    Eingabe/Ausgabe funktioniert schon mal, nur meine sortier-funktion macht ärger.

    //...
    struct Listenelement
    {
    	string name;
    	int data;
    	
    	Listenelement *next;
    } 
    
    //...andere Funktionen
    
    void sortiere(Listenelement *anfang)
    {
    	string tmp_name;
    	int tmp_alter;
    	Listenelement *aktuell;
    	Listenelement *vorheriges;
    	
    	aktuell = anfang;
    	vorheriges = aktuell;
    	aktuell = aktuell->next;
    	
    	while(aktuell->next != NULL)
    	{
    		if(vorheriges->data > aktuell->data)
    		{   
    			aktuell=anfang;                                               //EDIT: Hier lag das Problem =(
    			tmp_name = vorheriges->name;
    			tmp_alter = vorheriges->data;
    			vorheriges->name = aktuell->name;
    			vorheriges->data = aktuell->data;
    			aktuell->name = tmp_name;
    			aktuell->data = tmp_alter;
    		}
    		else
    		{
    		vorheriges = aktuell;
    		aktuell = aktuell->next;
    		}
    	}
    }
    
    //... int main ...
    

    Ich hab mir das ziemlich umständlich gemacht, aber der Gedanke war, dass
    falls es unsortierte Daten gibt die if-Bedingung greift,
    wodurch die Liste nochmal von Anfang an durchlaufen wird,
    und sonst die while-Schleife nur die else-Anweisung durchläuft.

    Wenn ich jetzt aber ein paar Daten eingebe, bleibt das Programm
    bei der sortier-funktion hängen und lädt sich tot.

    Ohne die erste Zeile von if

    			aktuell=anfang;
    

    schiebt es mir, bei abnehmender Alterseingabe,
    das erste Element schon mal nach hinten, bis
    zur vorletzten Stelle und der return-Wert ist 0.
    Die letzte Stelle ist eh noch nicht abgedeckt damit, ist klar..
    Aber mit aktuell=anfang; bleibt der ganz stecken. 😞

    Jemand ne Idee?



  • Hier nochmal der komplette Quellcode, mit allem:

    #include <iostream>
    #include <fstream>
    
    using namespace std;
    
    struct Listenelement
    {
    	string name;
    	int data;
    	
    	Listenelement *next;
    };
    
    void neuele (string name_1, int daten, Listenelement *anfang)  //Funktion zum Anlegen neuer Listenelemente
    {
    	Listenelement *aktuell;
    	aktuell = anfang;
    	
    	while (aktuell->next != NULL)       /*zum Letzten Element gehen (wollte das Programm noch um datei-einlesen erweitern, deswegen fstream statt ofstream)*/
    	{
    		aktuell = aktuell->next;
    	}
    	
    	aktuell->next = new Listenelement;            //neues Element anlegen
    	
    	aktuell = aktuell->next;                           //in neues Element gehen
    	aktuell->name = name_1;                       //mit Daten füllen
    	aktuell->data = daten;
    	aktuell->next = NULL;                             //Folgeelement 0 setzen
    }
    
    void sortiere(Listenelement *anfang)      //Sortierfunktion (Problem?!)
    {
    	string tmp_name;
    	int tmp_alter;
    	Listenelement *aktuell;
    	Listenelement *vorheriges;
    	
    	aktuell = anfang;
    	vorheriges=aktuell;
    	aktuell = aktuell->next;
    	
    	while(aktuell->next != NULL)
    	{
    		if(vorheriges->data > aktuell->data)               //wenn Alter des Folgeelementes größer
    		{   
    			aktuell=anfang;
    			tmp_name=vorheriges->name;                         //Daten über "temporäre Ablage" tauschen
    			tmp_alter=vorheriges->data;
    			vorheriges->name=aktuell->name;
    			vorheriges->data=aktuell->data;
    			aktuell->name=tmp_name;
    			aktuell->data=tmp_alter;
    		}
    		else
    		{
    		vorheriges=aktuell;                              //sonst einfach weitergehen
    		aktuell=aktuell->next;
    		}
    	}
    }
    
    void ausgabe(Listenelement *anfang)          //Ausgabe- und Speicherlöschfunktion
    {
    	Listenelement *aktuell;
    	Listenelement *vorheriges;
    	aktuell = anfang;
    	
    	cout << aktuell->name << "\t" << aktuell->data << endl;              //Ausgabe
    	vorheriges=anfang;
    	
    	fstream f;                                                                                      //Ausgabe in Datei
    	f.open("namensliste.txt", ios::out);
    	f << aktuell->name << "\t" << aktuell->data << endl;
    	
    	while (aktuell->next != NULL)
    	{
    		aktuell = aktuell->next;
    		delete vorheriges;                                                         //reservierten Speicher nach Ausgabe leeren
    		cout << aktuell->name << "\t" << aktuell->data << endl;	
    		
    		f << aktuell->name << "\t" << aktuell->data << endl;
    	
    		vorheriges=aktuell;
    	}
    	f.close();
    	delete anfang;                                                          //reservierten Speicher für Listenkopf leeren
    }
    
    
    
    int main()
    {
    	Listenelement *lanfang;
    	lanfang=new Listenelement;
    	lanfang->next=NULL;
    	
    	string eingabe_name;
    	int eingabe_alter;
    	
    	cout << "Geben Sie den Namen der ersten Person ein: ";
    	cin >> eingabe_name;
    	lanfang->name=eingabe_name;
    	
    	cout << endl << "Geben Sie das Alter der ersten Person ein ein: ";
    	cin >> eingabe_alter;
    	lanfang->data=eingabe_alter;
    	cout << endl;
    	
    	while(eingabe_name != "quit")
    	{
    		cout << "Geben Sie weitere Namen ein, zum Beenden 'quit': ";
    		cin >> eingabe_name;
    		
    		if(eingabe_name != "quit")
    		{
    			cout << endl << "Geben Sie das Alter ein: ";
    			cin >> eingabe_alter;                       
    		 	cout << endl;                               
    		 	neuele(eingabe_name, eingabe_alter, lanfang);
    		}
    		
    	}
    	sortiere(lanfang);
    	ausgabe(lanfang);
    	return 0;	
    }
    


  • Mein Gedanke war, dass durch die Eingabe von "quit", was der Abbruchbefehl für die Eingabe-Schleife ist,
    noch ein Element ohne Daten angelegt wird, was zum Fehler führt und kein Schleifen-Abbruch erfolgt.

    Aber auch wenn ich in der "sortiere"-Funktion die while-Bedingung auf

    while(aktuell->name != "quit")
    

    ändere geht es nicht..



  • Benutze einen Debugger und schau dir an, was dein Programm tut.

    lanfang kann von sortiere nicht geändert werden, da hast du auf jeden Fall ein Problem.

    Falls es dir nicht darauf ankommt, selber eine Liste zu implementieren: verwende std::vector und std::sort.



  • Oh mann... was für ein Denkfehler..
    Ich hab ja in der while-Schleife den "aktuell"-Zeiger
    auf den Anfang gesetzt, bevor ich die Daten zwischengespeichert und getauscht habe.. 😡
    OK, gelöst...
    Werde noch ein Update reinstellen und den Thread dann schließen..



  • So, ok... da das letzte Listenelement noch nicht einsortiert wurde, hab ich einfach die
    "russische Brecheisenmethode" rausgeholt,
    einfach die if-Bedingung aus der while schleife wiederholt,
    und die while-schleife nochmal durchlaufen lassen.
    Macht was es soll:

    #include <iostream>
    #include <fstream>
    
    using namespace std;
    
    struct Listenelement
    {
    	string name;
    	int data;
    	
    	Listenelement *next;
    };
    
    void neuele (string name_1, int daten, Listenelement *anfang)
    {
    	Listenelement *aktuell;
    	aktuell = anfang;
    	
    	while (aktuell->next != NULL)
    	{
    		aktuell = aktuell->next;
    	}
    	
    	aktuell->next = new Listenelement;
    	
    	aktuell = aktuell->next;
    	aktuell->name = name_1;
    	aktuell->data = daten;
    	aktuell->next = NULL;
    }
    
    void sortiere(Listenelement *anfang)
    {
    	string tmp_name;
    	int tmp_alter;
    	Listenelement *aktuell;
    	Listenelement *vorheriges;
    	
    	aktuell = anfang;
    	vorheriges=aktuell;
    	aktuell = aktuell->next;
    	
    	while(aktuell->next != NULL)
    	{
    		if(vorheriges->data > aktuell->data)
    		{   
    			tmp_name=vorheriges->name;
    			tmp_alter=vorheriges->data;
    			vorheriges->name=aktuell->name;
    			vorheriges->data=aktuell->data;
    			aktuell->name=tmp_name;
    			aktuell->data=tmp_alter;
    			aktuell=anfang;
    		}
    		else
    		{
    		vorheriges=aktuell;
    		aktuell=aktuell->next;
    		}		
    	}
    	if(vorheriges->data > aktuell->data)
    		{   
    			tmp_name=vorheriges->name;
    			tmp_alter=vorheriges->data;
    			vorheriges->name=aktuell->name;
    			vorheriges->data=aktuell->data;
    			aktuell->name=tmp_name;
    			aktuell->data=tmp_alter;
    			aktuell=anfang;
    		}
    		
    	while(aktuell->next != NULL)
    	{
    		if(vorheriges->data > aktuell->data)
    		{   
    			tmp_name=vorheriges->name;
    			tmp_alter=vorheriges->data;
    			vorheriges->name=aktuell->name;
    			vorheriges->data=aktuell->data;
    			aktuell->name=tmp_name;
    			aktuell->data=tmp_alter;
    			aktuell=anfang;
    		}
    		else
    		{
    		vorheriges=aktuell;
    		aktuell=aktuell->next;
    		}		
    	}
    	
    }
    
    void ausgabe(Listenelement *anfang)
    {
    	Listenelement *aktuell;
    	Listenelement *vorheriges;
    	aktuell = anfang;
    	
    	cout << aktuell->name << "\t" << aktuell->data << endl;
    	vorheriges=anfang;
    	
    	fstream f;
    	f.open("namensliste.txt", ios::out);
    	f << aktuell->name << "\t" << aktuell->data << endl;
    	
    	while (aktuell->next != NULL)
    	{
    		aktuell = aktuell->next;
    		delete vorheriges;
    		cout << aktuell->name << "\t" << aktuell->data << endl;	
    		
    		f << aktuell->name << "\t" << aktuell->data << endl;
    	
    		vorheriges=aktuell;
    	}
    	f.close();
    	delete anfang;
    }
    
    
    
    int main()
    {
    	Listenelement *lanfang;
    	lanfang=new Listenelement;
    	lanfang->next=NULL;
    	
    	string eingabe_name;
    	int eingabe_alter;
    	
    	cout << "Geben Sie den Namen der ersten Person ein: ";
    	cin >> eingabe_name;
    	lanfang->name=eingabe_name;
    	
    	cout << endl << "Geben Sie das Alter der ersten Person ein ein: ";
    	cin >> eingabe_alter;
    	lanfang->data=eingabe_alter;
    	cout << endl;
    	
    	while(eingabe_name != "quit")
    	{
    		cout << "Geben Sie weitere Namen ein, zum Beenden 'quit': ";
    		cin >> eingabe_name;
    		
    		if(eingabe_name != "quit")
    		{
    			cout << endl << "Geben Sie das Alter ein: ";
    			cin >> eingabe_alter;                       
    		 	cout << endl;                               
    		 	neuele(eingabe_name, eingabe_alter, lanfang);
    		}
    		
    	}
    	sortiere(lanfang);
    	ausgabe(lanfang);
    	return 0;	
    }
    


  • Du gibst den Speicher, den du mit new anforderst nicht wieder frei. Zu jedem new gehört ein delete!



  • @schlangenmensch

    Ok, ich dachte das hätte ich in der Ausgabe-Funktion erfolgreich mit eingebaut.
    Werde ich mir nochmal genauer anschauen. Danke schonmal 🙂



  • @marco_der_noob sagte in [Gelöst] Sortierung von einfach verketteter Liste:

    Ok, ich dachte das hätte ich in der Ausgabe-Funktion erfolgreich mit eingebaut.

    Speicherverwaltung ist wohl kaum eine Aufgabe, die eine Funktion erfüllen soll, die der Ausgabe einer Datenstruktur dient. Eine Funktion sollte eine Aufgabe erfüllen.

    @marco_der_noob sagte in [Gelöst] Sortierung von einfach verketteter Liste:

    delete anfang;

    Mhm. Und wer gibt anfang->next frei? Wer anfang->next->next? ...



  • Sorry, scheint tatsächlich in der Ausgabe Funktion gemacht zu werden. Hatte ich müde und dank mangelndem Syntaxhighlighting für delete übersehen.

    Aber was nützt dir eine Ausgabe Funktion, die immer die Kette löscht. Dann kannst du jede Kette immer nur einmal ausgeben.



  • @Swordfish: Das in die Ausgabe mit reinzupacken ist zwar nicht so toll, aber ich dachte ich spar mir damit die Funktion und es ist kürzer. Schlechter Programmierstil..

    @Schlangenmensch: Ich hab ja die Ausgabe in einer extra-Datei "namensliste.txt".. Ich wollte das Programm eigentlich noch um das Einlesen aus dieser Datei erweitern. Deswegen soll das Programm auch bei der "neuele"-Funktion, die neue Listenelemente anlegt, erstmal bis zum letzten Listenelement gehen, bevor das erste angelegt wird.
    Und natürlich könnte ich sonst auch einfach nur ofstream verwenden..

    Etwas verwirrend von mir programmiert... Ich gelobe mir Besserung bis zur Prüfung. 🙂