doppeltverkettete liste C++ Rückwärts



  • Hi Leute ich brauche eure Hilfe , ich muss diese Liste rückwärts ausgeben komme aber nicht weiter, bitte um hilfe!

    class listenelement
    {
    string daten;
    listenelement* next;
    listenelement* last;
    public:
    void datenSetzen(string datenneu);
    void anhaengen(string datenneu);
    void ausgeben();
    void rueckwaertsausgeben();
    void freigeben();
    };

    void listenelement::datenSetzen(string datenneu)
    {
    daten =datenneu;

    last= nullptr;
    }

    void listenelement::anhaengen(string datenneu)

    {
    if (next != nullptr)
    {
    next = new listenelement();

        next->daten=datenneu;
    
        next = nullptr;
    
     }
     else
        if(last != nullptr)
        {
            next->last = new listenelement();
            
            last->daten = datenneu;
    
    
         }
         else
        {
         next->anhaengen(datenneu);
         }
    

    }

    void listenelement::rueckwaertsausgeben()
    {

        cout<<last->daten <<'\n';
    do{
        last->rueckwaertsausgeben();
    
       }while (last == nullptr);
    

    }

    void listenelement::ausgeben()
    {

    cout << daten << '\n';
    
    if (next != nullptr)
        next->ausgeben();
    

    }

    void listenelement::freigeben()
    {

    if (next != nullptr)
    {
        next->freigeben();
        delete(next);
    }
    

    }

    int main ()
    {

    listenelement* listenanfang;
    
    listenelement* listenende;
    
    
    listenanfang = new listenelement();
    listenende = new listenelement();
    
    listenanfang = listenende;
    
    listenanfang->datenSetzen("Element 1");
    
    listenende->anhaengen("Element 2");
    listenende->anhaengen("Element 3");
    listenende->anhaengen("Element 4");
    
    listenanfang->ausgeben();
    
    listenende->rueckwaertsausgeben();
    
    listenanfang->freigeben();
    
    delete(listenanfang);
    
    return 0;
    

    }



  • @Coocky79 sagte in doppeltverkettete liste C++ Rückwärts:

    Bitte schliesse seinen Code in Code-Tags ein (Editor hat auch einen Knopf dafür), dann wird er lesbarer. Mit lesbarem Code sind die Chancen höher, dass einem geholfen wird 😉

    So z.B.

    ```cpp
    Mein C++-Code
    ```

    Nun zu deinem Problem:

    void listenelement::rueckwaertsausgeben()
    {
        cout << last->daten <<'\n';
        do {
            last->rueckwaertsausgeben();
        } while (last == nullptr);
    }
    

    Du scheinst hier zwei unterschiedliche Iterations-Ansätze zu vermischen: Schleife und Endrekursion. Entscheide dich für eins von beiden.

    Für eine Endrekursion z.B. benötigst du die Schleife nicht. Da reicht es, einfach rueckwaertsausgeben() für das Vorgänger-Element aufzurufen und die (rekursiven) Funktionsaufrufe "rutschen" automatisch durch die gesamte Liste.

    Gehe dabei wie folgt vor:

    1. Gib die Daten des aktuellen Elements aus, nicht ungeprüft die eines potentiell nicht existierenden (erstes Element in der Liste) Vorgängers, wie du es jetzt tust.

    2. Prüfe, ob es einen Vorgänger gibt (Rekursions-Abbruchbedingung). Wenn ja, dann rufe rueckwaertsausgeben() für diesen Vorgänger auf, sonst mache nichts, bzw. kehre aus der Funktion zurück.

    Fertig.

    P.S.: Ich gehe mal davon aus dass es sich bei last nicht um das letzte Element der Liste, sondern um das Vorgänger-Element handelt, korrekt? prev (ious) / pred (ecessor) wären da vielleicht geeignetere Namen.



  • Hi, Vielen Dank für den Denkanstoß, hab mich total verrannt , den last/prev zeiger hätte es garnicht gebraucht. Nur den abruf der rückwärtsausgabe richtig sortieren und ja ohne Schleife einfach richtige if abfrage setzten!

    Danke , bin Quereinsteiger und hoffe auf weitere Hilfe von Hier!



  • @Coocky79 sagte in doppeltverkettete liste C++ Rückwärts:

    den last/prev zeiger hätte es garnicht gebraucht

    Eine doppelt verkettete Liste ohne doppelte Verkettung?



  • @manni66 sagte in doppeltverkettete liste C++ Rückwärts:

    Eine doppelt verkettete Liste ohne doppelte Verkettung?

    @Coocky79 sagte in doppeltverkettete liste C++ Rückwärts:

    Hi Leute ich brauche eure Hilfe , ich muss diese Liste rückwärts ausgeben komme aber nicht weiter, bitte um hilfe!

    Vielleicht geht es gar nicht um eine doppelt verkettete Liste, würde mich zwar auch wundern, aber man weiß ja nie?



  • @Belli naja, der Titel der Frage ist da eindeutig.



  • @Belli sagte in doppeltverkettete liste C++ Rückwärts:

    Vielleicht geht es gar nicht um eine doppelt verkettete Liste, würde mich zwar auch wundern, aber man weiß ja nie?

    Um etwas abzuschweifen: Das elegante an der Listeniteration via Rekursion ist, dass man damit nur durch verschieben des cout um ein, zwei Zeilen auch eine nur einfach vorwärtsverkettete Liste rückwärts ausgeben kann - etwas das mit Schleifencode schnell fummelig wird.



  • @Finnegan solange die Liste nicht zu lang wird.



  • @manni66 sagte in doppeltverkettete liste C++ Rückwärts:

    @Finnegan solange die Liste nicht zu lang wird.

    Ja, das ist schade, dass einen Plattform hier ab einer gewissen Länge eine iterative Lösung zwingt. Die Alternative, die next-Pointer manuell zwischenzuspeichern ist ja nichtmal effizienter. Ich würde es schon begrüßen, wenn Compiler solche Limits irgendwann mal wegabstrahieren. Das ist ja schliesslich keine Einschränkung von C++ und dessen abstrakter Maschine - ich finde lediglich diese sollte letztendlich gewisse Algorithmen vorschreiben können.

    Das schweift aber noch weiter ab. Ich wüsste keine Sprache die das wie gefordert "wegabstrahiert". Nichtmal hochlevelige VM- oder interpretierte Sprachen.

    Ist sowas eigentlich irgendwann mal angedacht worden oder ist das einfach praktisch zu wenig relevant, da man es in den meisten Fällen mit eleganter rekursiver Lösung doch eher mit einer O(logn)\mathcal{O}(\log n)-Aufruftiefe zu tun hat? Die meisten Diskussionen dazu scheinen das a als "gottgegeben" anzusehen 😉

    Edit: Um die Frage selbst zu beantworten - ja: https://gcc.gnu.org/wiki/SplitStacks - wenn auch nicht für speziell diese Problematik.



  • @Finnegan sagte in doppeltverkettete liste C++ Rückwärts:

    Ja, das ist schade, dass einen Plattform hier ab einer gewissen Länge eine iterative Lösung zwingt. D

    Das Grundproblem bei zu großen rekursiven Iterationen ist doch, dass der Stack voll läuft. Wie willst du das denn verhindern?



  • @inflames2k sagte in doppeltverkettete liste C++ Rückwärts:

    @Finnegan sagte in doppeltverkettete liste C++ Rückwärts:

    Ja, das ist schade, dass einen Plattform hier ab einer gewissen Länge eine iterative Lösung zwingt. D

    Das Grundproblem bei zu großen rekursiven Iterationen ist doch, dass der Stack voll läuft. Wie willst du das denn verhindern?

    Ja, das ist schon bekannt. Geschenkt. Das Gedankenspiel hier war aber, dass der Compiler durchaus die Freiheit hat, sowas wegzuabstrahieren. So könnte er z.B. Code erzeugen, der bei solchen kritischen Rekursionen lokale Variablen und Rücksprungadressen in einer Heap-Datenstruktur speichert und diese z.B. mit JMP direkt anspringt. Der C++-Standard schreibt nicht vor, dass sowas auf einem begrenzten Stack gespeichert werden muss.

    Auch diese GNU Split Stacks könnten das ermöglichen. Wenn ich das richtig verstanden habe, dann stellen die einen dynamischen Stack zur Verfügung, der je nach Bedarf wachsen und schrumpfen kann.


Log in to reply