Sotiert einfügen (Liste)

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Sotiert einfügen (Liste)

    Hallo Leute..

    Habe eine verkettete Liste selbst geschrieben die die funktionen einfügenAnfang und einfügenEnde bezitzt ..
    alles schön und gut bis hier her :confused:
    aber...
    versuche seit tagen eine funktion zu schreiben die ein obj in die Liste sotiert einfuegt. Das objekt hat einen namen von typ string

    die funktion soll ein obj nach seinem namen sotiert in die liste einfügen

    versuche alles zu machen aber funktioniert nicht ich verliere irgendwo meine zeiger :D :confused:

    Bitte hilft mir


    gazoz
  • ah, oki, dann musst du die liste durchlaufen, bis du die stelle gefunden hast, an der das obj eingefügt werden soll, den zeiger des vorherigen auf das einzufügende objekt ändern und den zeiger des einzufügenden obj auf das nachfolgende.

    so weit - so einfach ;)

    wenn das dann immer noch nicht klappt, paste mal deinen code im [code=php]

    // noch ne frage nebenher: brauchst du das für schule, uni oder job ?
  • hats denn nun soweit geklappt ?

    bei einer liste kannst du leider nur sortieren indem du die liste durchläufst und dabei die elemente "aushängst" und an passender stelle wieder "einhängst" (was im vergleich zu einem array relativ viel laufzeit beansprucht). wie das aus- und einhängen geht hatten wir ja oben schon.

    wenn du das sortieren nicht in sito (am platz, in derselben liste) machen musst, so bietet sich an, eine zweite leere liste zu erstellen und jeweils das erste element der ersten liste zu entnehmen (also anschliessend aus der liste löschen). Nun kannst du die zweite liste bis zur richtigen position durchlaufen und das element einzufügen. dazu vergleichst du immer dein oben entnommenes element (obj.String) mit dem an der aktuellen position in der zweiten liste.

    zum schluss ist die erste liste leer.

    dann änderst du noch den zeiger der ersten liste auf die zweite liste und gibst den zeiger auf die zweite liste frei.
  • hi feuerstein

    also das sortierte einfügen funktioniert jetzt wunderbar

    die frage ist jetzt wie man ein unsortierte liste sortiert ausgeben kann

    die idee mit den zwei listen ist interessant , aber ich muss es ohne eine zweite liste machen...
    versuche es mal mit dem bubblesort oder anderen sortier algorithmen

    würde mich über weitere antworten und ideen freuen

    thanx feuerstein
  • Sortieren geht bei solchen Listen ja relativ leicht, da nur Zeiger kopiert werden müssen und die Operationen somit unabhängig von der Größe der in den Listen gespeicherten Objekten ist.

    Jeder gängige Algorithmus funktioniert, auch wenn der Quicksort oder Heapsort hier zu bevorzugen wäre.
    Den Quicksort gibt es übrigens fertig in der Standardbibliothek. Er heisst qsort. Aber ich vermute, du sollst das ohne schaffen.

    Das größte Problem bei solchen verketteten Gebilden ist immer, sich nicht mit den Zeigern zu verheddern. Ich male mir immer alle Situationen auf und überlege mir damit den Algorithmus. Dann musst du drei Fälle bedenken:
    - vertauschen mitten in der Liste (wohl der Normalfall)
    - Vertauschen am Anfang der Liste (der Anfangszeiger ist dann mit zu ändern)
    - Vertauschen am Ende der Liste (es gibt keinen Nachfolgezeiger, bzw. der ist NULL).

    Grüße
    Michael
  • genau. quicksort würde ich auch nehmen.

    da du ja nicht die stl benutzen darfst, leih dir einfach aus der uni-bib ein standard-algorithmen buch aus und sieh dir den algorithmus an. er ist relativ einfach nachzubauen.

    heapsort finde ich etwas überdimensioniert für die einfache aufgabe, bzw die anzahl der zugriffe.

    genau wie kelzoo denke ich das dein problem in der hauptsache im "verheddern" mit den pointern liegt.

    das ist aber völlig normal und kein grund zur besorgnis ;)

    wenn man es einmal raus hat, spart man sich eine menge datenschaufelei damit, weil man eben nur den pointer (zb an eine funktion) weiterreichen muss und nicht die komplette datenstruktur, die ja auch schon mal was umfangreicher sein kann, als ein einfacher string :D

    das wirkt sich dann sofort auf laufzeit und speicherplatzbedarf deiner anwendung aus