Sortieren einer verketteten Liste



  • Hallo,

    ich sitze schon recht lang an einer verketteten Liste, bzw. daran diese zu sortieren. Die Struktur besitzt lediglich ein Element für ein Zahlenwert und einen Zeiger (next) der auf die nächste Struktur (Kettenglied) zeigen soll. Folglich sollen die Kettenglieder nach der Zahl sortiert werden.

    Zunächst sollten per random-Befehl Kettenglieder erzeugt werden, anschließend ausgegeben und letzendlich gelöscht werden, was soweit auch funktioniert (der random-Befehl ist noch nicht optimiert, da immer wieder die selben Zufallszahlen erscheinen, doch das lässt sich ja realtiv leicht beheben und ist eigentlich nicht Gegenstand meiner Frage).

    Ich vermute mal, es wäre schlau einen Zeiger in die Struktur aufzunehmen, der auf das vorherige Kettenglied zeigt, allerdings komme ich irgendwo immer durcheinander in dem ganzen Zeigerwirrwarr.

    Hier mal mein Code und ich hoffe jemand kann mir helfen, denn nun habe ich eine schlaflose Nacht ... 😞

    #include <stdlib.h>						
    #include <stdio.h>		
    #include <stdlib.h>
    
    // Struktur und Typ für die Glieder der verketteten Liste 						
    struct sKette {						
    	int Zahl;					
    	struct sKette *next;	
    };						
    typedef struct sKette tKette;						
    
    // Funktion zum Anähgen
    int NeuesGlied(tKette **Doppelpointer, int NeueZahl);
    
    // Funktion zum Ausgeben
    void KetteAusgeben(tKette *StartPointerKopie);
    
    // Funktion zum Löschen
    void KetteLoeschen(tKette **pStart);
    
    // Funktion zum Sortieren 
    int KetteSortieren(tKette **Sortierpointer);
    
    int main()						
    {			
    	// Beginn der Struktur
    	tKette *Start = NULL;
    
    	// Neue Glieder einfügen mit zufälligen Zahlen
    	NeuesGlied(&Start, rand());
    	NeuesGlied(&Start, rand());
    	NeuesGlied(&Start, rand());
    	NeuesGlied(&Start, rand());
    
    	// Kette ausgeben
    	KetteAusgeben(Start);
    
    	// Kette löschen
    	KetteLoeschen(&Start);
    	return 0;					
    }	
    
    // Funktion zum Anfügen eines Kettenelements
    int NeuesGlied(tKette **Doppelpointer, int NeueZahl){
    	int Fehler=0;	// Fehlerindikator
    	tKette *pNeu;
    
    	// pNeu holt sich Speicher für eine Struktur
    	pNeu = (tKette*)malloc(sizeof(tKette));
    	if(pNeu==NULL) Fehler = -1;
    
    	// Wenn kein Fehler aufgetreten ist ...
    	if(!Fehler) {
    
    		// Nextzeiger der Struktur wird auf Null gesetzt, weils damit das Ende markiert wird
    		pNeu->next = NULL;
    		pNeu ->Zahl = NeueZahl;
    
    		// Letztes Kettenglied finden
    		while(*Doppelpointer!=NULL) Doppelpointer = &(*Doppelpointer)->next;
    		*Doppelpointer = pNeu;
    	}
    
    	// Rückgabe des Fehlerindikators
    	return Fehler;
    }
    
    // Funktion zur Ausgabe der gesamten Kette
    void KetteAusgeben(
    	tKette *StartPointerKopie){
    	while(StartPointerKopie!=NULL){
    		printf("Zahl: %d\n",StartPointerKopie->Zahl);
    		StartPointerKopie = StartPointerKopie->next;
    	}
    }
    
    // Zeiger löschen aus dem Speicher
    void KetteLoeschen(tKette **pStart){
    	tKette *pNext;	// Zeiger auf das nächste Kettenglied
    
    	// Solange der Start-Zeiger in main nicht auf null zeigt
    	while(*pStart!=NULL) {
    		// Nächstes Kettenglied merken
    		pNext = (*pStart)->next;
    		// Atuelles Kettenglied löschen
    		free(*pStart);
    		// Start-Zeiger in main auf nächstes Kettenglied (oder null) zeigen lassen
    		*pStart = pNext;
    	}
    }
    


  • Ergänzung:
    Also nach Aufgabenstellung sollen die ersten zwei Kettenglieder verglichen werden und gegebenenfalls getauscht werden. Danach sollen das zweite und dritte, danach das dritt und vierte usw. verglichen werden, solange bis bei einem Durchgang kein Kettenglied getauscht werden muss.

    Es sollen nicht einfach die Zahlenwerte sondern die Kettenglieder als ganzes getauscht werden ...


  • Mod

    Was ist deine Frage?



  • Die Frage ist, wie ich es schaffe, eine Funktion zu schreiben, die die Kettenglieder entsprechend der Aufgabenstellung sortiert.
    Ich habe einiges probiert jedoch ohne großen Erfolg ...



  • Eilein schrieb:

    Ich vermute mal, es wäre schlau einen Zeiger in die Struktur aufzunehmen, der auf das vorherige Kettenglied zeigt, ...

    Das wäre dann eine doppelt verkettete List.

    Eilein schrieb:

    ... allerdings komme ich irgendwo immer durcheinander in dem ganzen Zeigerwirrwarr.

    Nimm die ein Blatt Papier und male dir die Liste auf.
    Ein Kasten für die Struktur und einen Pfeil für den Zeiger.
    Dann kannst du schauen, welchen Zeiger du wann umbiegen musst.

    Du kannst allerdings auch nur den Inhalt vertauschen.



  • Eilein schrieb:

    Also nach Aufgabenstellung sollen die ersten zwei Kettenglieder verglichen werden und gegebenenfalls getauscht werden. Danach sollen das zweite und dritte, danach das dritt und vierte usw. verglichen werden, solange bis bei einem Durchgang kein Kettenglied getauscht werden muss.

    Das entspricht einem klassischem Bubble-Sort und ist NICHT an verk. Listen gebunden.

    Eilein schrieb:

    allerdings komme ich irgendwo immer durcheinander in dem ganzen Zeigerwirrwarr.

    Deswegen benutzen auch nur Deppen verk. Listen, und nur noch viel größere Deppen versuchen dann auch noch, verk. Listen zu sortieren oder gar zu persistieren.
    Gehe davon aus, dass dein Lehrer keine Ahnung von C-Programmierung hat, wenn er solche Aufgaben stellt.
    Gehe davon aus, dass du NICHT C programmieren kannst, wenn du den Kurs absolviert hast.



  • Ich probiere es auch schon die ganze Zeit auf dem Papier zebreche mir aber schon seit Stunden den Kopf an dieser dummen Aufgabe. Ich vermute mal das hier eine doppelt verkettete Liste Sinn und Zweck der Aufgabe ist oder nicht?

    Ich verstehe es nämlich so, dass ich quasi eine Schleife programmieren soll, die alle Elemente durchgeht bis die Adresse NULL, also das Ende der Kette erreicht wird.
    Dabei werden das 1 und 2 Glied, dann das 2 und 3 Glied usw. kontrolliert und gegebenenfalls getauscht. Nun kann es ja sein das man mehrere Durchläufe hat bis die Kette sortiert ist (es soll ja solange erneut Sortiert werden, bis kein Umtausch stattgefunden hat). Mein Problem ist einfach der, dass ich nicht weiß wie ich mich geschickt durch die Kette hangel und wenn ich das 3 und 4 Glied tausche, muss ich auch irgendwie dem 2ten Glied bescheidgeben, dass er nicht mehr auf das 3 sondern das 4 Glied zeigen soll usw ...

    Mein Kopf explodiert schon beinahe 😡

    Ohne fremde Hilfe komme ich wirklich nicht weiter vlt. denke ich auch einfach zu kompliziert - wenn mir jemand weiterhelfen kann am besten mit einem Code ich wäre ihm/ihr unendlich dankbar da es in Richtung Prüfung geht und die Zeit knapp wird.



  • Da du von vorne durch die Liste gehst, warst du ja schon beim 2. Element, wenn du das 3. mit dem 4. vergleichst. Dann kannst du dir das 2. merken.

    DirkB schrieb:

    Du kannst allerdings auch nur den Inhalt vertauschen.

    Damit ist gemeint, dass du den Inhalt von Zahl austauscht und nicht den Inhalt von next.



  • also du merkst dir den anfang der liste, vergleichst dann liste->daten mit liste->next->daten, vertauscht diese evtl (temp=liste, liste=next, next=liste) und gehst dann um eins weiter, also liste=liste->next. wenn liste->next irgendwann 0 ist, fängst du wieder von vorne an.

    ich glaube, damit ist dir mehr als genug geholfen.


Log in to reply