Doppelt verkettete Liste

Also der vorgegeben Code ist folgender:

#include <iostream>
using namespace std;
struct TListenKnoten
{
int data;
TListenKnoten *prev;
TListenKnoten next;
};
void hinten_anfuegen(TListenKnoten &anker, int wert)
{
TListenKnoten *neuer_eintrag = new TListenKnoten;
neuer_eintrag->data = wert;
neuer_eintrag->next->prev = neuer_eintrag;
neuer_eintrag->next = nullptr;
if (anker == nullptr)
anker = neuer_eintrag;
else
{
TListenKnoten *ptr = anker;
while (ptr->next != nullptr)
ptr = ptr->next;
ptr->next = neuer_eintrag;
}
}
void liste_ausgeben(TListenKnoten * anker)
{
if (anker == nullptr)
cout << "Leere Liste." << endl;
else
{
cout << "[ ";
TListenKnoten *ptr = anker;
do
{
cout << ptr->data;
if (ptr->next != nullptr) cout << " , ";
else cout << " ";
ptr = ptr->next;
} while (ptr != nullptr);
cout << "]" << endl;
}
}
int main()
{
int laenge = 10;
TListenKnoten anker = nullptr;
liste_ausgeben(anker);
for (int i = 0; i < laenge; i++)
hinten_anfuegen(anker, ii);
liste_ausgeben(anker);
system("PAUSE");
return 0;
}

Und die Aufgabe ist schließlich:
Nehmen Sie das Programm für die dynamische Datenstruktur „einfach
verkettete“ Liste (siehe unten) und erweitern Sie das Programm (sowohl
die Datenstruktur als auch die Funktionen) so, dass die resultierende
Datenstruktur eine doppelt verkettete Liste bildet.
Bei der doppelt verketteten Liste zeigt jedes Listenelement sowohl auf
seinen Nachfolger (Pointer next) als auch auf seinen Vorgänger (Pointer
prev, von „previous“). Der erste Listenknoten hat den Nullpointer als Wert
von prev.
Als Verankerung der Datenstruktur soll weiterhin der Pointer anker
verwendet werden, auch wenn dadurch die doppelte Verkettung nicht viel
Nutzen bringt.

Ich will aber jetzt keine komplette Lösung, sondern finde eben einfach keinen Ansatz. Ohne Ansatz bringt es mir nichts selbst stundenlang darüber nachzudenken (was ich schon getan habe). Wie fängt man da also am besten an?

du schreibst da einfach noch einen zweiten zeiger rein, der auf das vorherige Element zeigt und den musst du dann natürlich noch mit adressen oder NULL füttern

Danke, aber wäre noch ein Beispiel möglich bitte?

Belli

HansKlaus schrieb:

du schreibst da einfach noch einen zweiten zeiger rein

Wo bitte soll er den reinschreiben?

Ah ja, TListenknoten prev* im struct und neuer_eintrag->next->prev = neuer_eintrag; hab ich erst nachträglich reingemacht, der Originalcode ist also ohne die beiden.

DirkB

Mit Zettel und Bleistift.
Knoten als Kasten zeichen und mit Pfeilen die Zeiger darstellen.
Ungefähr so: https://tdimov.files.wordpress.com/2013/03/doublylinkedlist.jpg

Und dann überlegst du dir Schrittweise, wie du welchen Zeiger umbiegen musst.

Du kannst dir erstmal für jeden beteiligten Knoten (Vorgänger, Nachfolger, Neuer) eigene Zeiger nehmem.
Dann kommst du mit den -> nicht durcheinander wie bei neuer_eintrag->next->prev

SvenJungwird

Fh aachen gip

Guck mal ins andere thema habe da den ansatz drin.

Gota schrieb:

Danke, aber wäre noch ein Beispiel möglich bitte?

Wenn Du C++ programmierst solltest Du Dich auf jeden Fall auch mit Konstruktoren und Destruktoren beschäftigen. Das spart Zeilen und hebt die Performance und hilft Fehler zu vermeiden. Weiter ist for i.A. angebrachter als do-while mit vorhergehenden if .
Bei doppelt verketteten Listen kommt man schnell zum letzten Element, wenn man den Vorgänger(!) des Ankers wählt. Die Konsequenz ist, dass aus dem Anker-Pointer ein Anker-Knoten wird.

#include <iostream>
using namespace std;

struct TListenKnoten
{
    TListenKnoten()
        : data(), prev(this), next(this)
    {}
    TListenKnoten(int d, TListenKnoten* p, TListenKnoten* n)
        : data(d), prev(p), next(n)
    {}
    // ~TListenKnoten(); // fehlt!?

    int data;
    TListenKnoten *prev;
    TListenKnoten *next;

    TListenKnoten(const TListenKnoten&) = delete;
    TListenKnoten& operator=(const TListenKnoten&) = delete;
};
void hinten_anfuegen(TListenKnoten& anker, int wert)
{
    TListenKnoten *neuer_eintrag = new TListenKnoten(wert, anker.prev, &anker);
    anker.prev->next = neuer_eintrag;
    anker.prev = neuer_eintrag;
}
void liste_ausgeben(TListenKnoten& anker)
{
    cout << "[ ";
    bool print_done = false;
    for(TListenKnoten* p = anker.next; p != &anker; p = p->next)
    {
        if(print_done)
            cout << ", ";
        else
            print_done = true;
        cout << p->data;
    }
    cout << "]";
}
int main()
{
    int laenge = 10;
    TListenKnoten anker;
    liste_ausgeben(anker);
    cout << endl;
    for (int i = 0; i < laenge; i++)
        hinten_anfuegen(anker, i*i);
    liste_ausgeben(anker);
    cout << endl;
    system("PAUSE");
    return 0;
}

Im nächsten Schritt kannst Du mal versuchen, nicht nur den Listenknoten als Typ zu modellieren, sondern die gesamte Liste.

Solche zusätzlichen/neuen Typen sollen wir nicht verwenden, sondern eben nur die, die auch das Grundgerüst hat.