Verkette Liste sortieren



  • naja gut den "leerlauf" könnte man weglassen.



  • Eine Lösung wäre, das Problem in zwei halb so große Probleme zu zerlegen: Du teilst einfach die Liste in 2 gleich große Listen und sortierst dann die halb so großen Listen. Wenn eine Liste nur noch die Länge 0 oder 1 hat, ist sie fertig sortiert. Danach musst du die sortierten Teillisten einfach in der richtigen Reihenfolge aneinanderhängen. Fertig.
    Das wäre mein naiver Ansatz. Allerdings erscheint mir das Teilen der Liste jeweils recht teuer, weil man jeweils size/2 Schritte braucht, um zur Mitte zu kommen. Vielleicht gibt es also einen besseren Ansatz.



  • @wob
    Das macht doch keinen Sinn, wenn du alles zerlegst bis es n Listen mit nur 1 Element hat und als nächstes wieder in der richtigen Reihenfolge aneinanderhängen willst, bist du doch wieder am Anfang des Problems, wo du n Elemente ordnen wolltest?



  • @TGGC Ah, ich habe mich offenbar unklar/falsch ausgrdrückt. Mit "in der richtigen Reihenfolge aneinanderhängen" meinte ich natürlich, dass ich jeweils die Kopf-Elemente der beiden Listen vergleiche und das kleinere (oder größere) dann für meine Zielliste wähle. Danach gehe ich dann in der Quellliste, aus der das Element gewählt wurde, einen Schritt weiter und vergleiche erneut beide Quelllistenköpfe. Bis beide Quellisten leer sind. Das geht, weil beide Quelllisten jeweils sortiert sind. Also "richtig aneinanderhängen" meint hier, "sortiert zusammenführen".



  • wie wäre es damit, das neue element einfach an den anfang der liste zu setzen und dies so lange mit den jeweiligen next-elementen zu vergleichen, bis das nächste next-element größer ist?



  • @wob: Diese "Ineinanderhängen" heisst Mergesort.



  • This post is deleted!


  • This post is deleted!


  • Hallo,
    bin heute auch bei dem Thema verkettete Listen angekommen und hätte das bei meiner "Eintageserfahrung" so umgesetzt.

    #include <iostream>
    #include <list>
    
    using namespace std;
    
    void ZeigeListe(list<int> lListe);	// Inhalt der Liste anzeigen
    
    int main()
    {
       list<int> lDaten;	   // Verkettete Liste
       list<int>::iterator i;  // Iterator
       int eingabe;
    
       do
       {
          cout << "Zahl eingeben: ";
          cin >> eingabe;
    
          lDaten.push_back(eingabe);   // Eingegebene Zahl in die Liste schieben (hinten anhängen)
          lDaten.sort();		   // Liste sortieren
          ZeigeListe(lDaten);	   // Liste anzeigen
    
       } while (eingabe != 123);
    
       lDaten.clear();   // Liste löschen
    }
    
    // ZeigeListe
    //
    // Aufgabe: Inhalt der verketteten Liste anzeigen
    //
    void ZeigeListe(list<int> lListe)
    {
       list<int>::iterator i;	// Iterator
    
       /* Kleiner Bonus. War ja nicht gefordert. */
       // Anzahl der Elemente in der Liste ausgeben
       cout << "Anzahl der Elemente in der Liste: ";
       cout << static_cast<int> (lListe.size()) << endl;
    
       cout << "Inhalt der Liste: " << endl;
    
       // Ist die Liste leer?
       if (lListe.empty() == false)
       {
       	// Nein, dann Inhalt ausgeben
       	for (i = lListe.begin(); i != lListe.end(); i++)
       	{
       		cout << *i << ", ";
       	}
       }
       else
       {
       	// Ja, dann Meldung ausgeben
       	cout << "Leer." << endl;
       }
       cout << "\n\n";
    
    } // ZeigeListe
    

    Ausgabe:
    Zahl eingeben: 5
    Anzahl der Elemente in der Liste: 1
    Inhalt der Liste:
    5,

    Zahl eingeben: 21
    Anzahl der Elemente in der Liste: 2
    Inhalt der Liste:
    5, 21,

    Zahl eingeben: 13
    Anzahl der Elemente in der Liste: 3
    Inhalt der Liste:
    5, 13, 21,

    Zahl eingeben: 0
    Anzahl der Elemente in der Liste: 4
    Inhalt der Liste:
    0, 5, 13, 21,

    Zahl eingeben: 123
    Anzahl der Elemente in der Liste: 5
    Inhalt der Liste:
    0, 5, 13, 21, 123,

    Zugegeben, für das Beenden gibt es sicherlich bessere Möglichkeiten, als dies mit der Eingabe "123" zu tun, aber da hat sicher jeder hier mehr Erfahrung und mir ist da auf die schnelle nichts eingefallen.

    Auch wenn es für den Post-Verfasser zu spät kommen könnte, würde ich mich auf Fragen/Vorschläge/Kritik freuen. Bin wie gesagt auch erst heute mit dem Thema angefangen.


  • Mod

    Nun, du machst ja nichts selber, außer die fertigen Funktionen aufzurufen (was gut ist!) daher kann man kaum etwas zum Speichern und Sortieren sagen. Wobei man, wenn es nur um Speichern von sortierten Daten ginge, wohl eher ein (multi-)set nehmen würde. Das ist von Natur aus sortiert, wodurch das aufwändige Neusortieren bei jedem Einfügen entfällt.

    Eine typische C++-Leseschleife würde so aussehen:

    while(cin >> eingabe)
    {
          lDaten.push_back(eingabe);
          lDaten.sort();
          ZeigeListe(lDaten);
    }
    

    Da hast du automatisch alles drin: Fehlerprüfung (fehlt bei dir bisher) und Abbruchbedingung (mit CTRL+D (bzw CTRL+Z in Windows) oder bei Fehler).


Log in to reply