Verständnissfrage Verkettete Listen.

Zackorz

Hallo,

ich habe in meinem Lehrbuch eine Übung zu mit Verketteten Listen, leider ist aber das Prinzip dieser Listen nicht gut erklärt.

Auch aus Anleitungen im Internet ist mir einfach nicht klar geworden wie diese Funnktionieren.

Hier mal ein Beispiel:

Struct Knoten {
int daten;
Knoten *zeiger;
}

Nun steht hier, Knoten *zeiger ist das Knotenelement, es zeigt auf das nächste Element.

Ich kann das leider nicht im geringsten Nachvollziehen, welches nächste Element? Da ist kein weiteres, wie ist das gemeint?

Wäre wirklich Nett, wenn mir einer die Struktur in einfachen Worten erklären könnte und wie ich neue Elmente dynamisch hinzufüge.

drakon

Das nächste Element wird erzeugt und an den letzten Knoten angehängt.

struct Knoten {
int daten;
Knoten *zeiger;
};

int main()
{
 Knoten* node = new Knoten;
 node->daten = 2;

 node->zeiger = new Knoten; // nächster Knoten
 node->zeiger->daten = 5;

 node->zeiger->zeiger = new Knoten; // und der nächste
 node->zeiger->zeiger->daten = 8;
 //...

 //am Ende die Elemente wieder mit delete freigeben
}

So in etwa sieht das Prinzip aus. Oftmals hast du auch noch Zeiger auf das vorherige Element in der Struktur. Dazu kommt noch, dass das ganze schön gewrappt wird, damit weniger Fehler gemacht werden können.

Aber ich denke, dass du das Prinzip so verstehen kannst.

SeppJ

Es geht darum, mehrmal Daten vom gleichen Typ zu speichern, so ähnlich wie bei einem Array, jedoch mit einer anderen Struktur. Die Membervariable daten steht in deinem Beispiel für ein Element aus diesem ganzen Satz von Daten. Und der Zeiger zeigt dann auf den nächsten Knoten, der das nächste Element beinhaltet.

Soweit verstanden? Weitere Fragen?

Zackorz

So ganz versthe ich es zwar noch nicht, aber es ist eigentlich fast das gleiche wie rekursion oder?

Ad aCTa

Na anders rum. Sich durch Listen zu bewegen wird durch Rekursion bewerkstelligt. Es geht aber u.U. auch ohne.

Ist dein Buch zufällig "C++ von A bis Z"?

drakon

Also rekursion heisst ja lediglich, dass z.B eine Funktion sich selbst aufruft.. Das hat direkt eigentlich nichts damit zu tun. Auf eine Art weiss ich, was du meinst, aber ich würde mir das weniger als verschachtelung vorstellen, sondern lediglich Objekte, die einen Link zu einem anderen Objekt haben

Zuerst hast du ja eine Leere Liste:

Dann erzeugst du ein erstes Element

0xFF45AF21  
|-----------|
| daten  = 2|
| zeiger* =0|
|-----------|

Der zeiger zeigt noch auf nichts.
Dann kommt das nächste Element:

0xFF45AF21                     ----->0xFF3590F5
|---------------------|        |     |-----------| 
| daten  = 2          |        |     | daten  = 5|
| zeiger* =0xFF3590F5 |--------|     | zeiger* =0| 
|---------------------|              |-----------|

Und so geht das immer weiter.
Ist imo eigentlich recht anschaulich.
Oder probier mal genau zu sagen, was du nicht verstehst.

Zackorz

Ad aCTa schrieb:

Na anders rum. Sich durch Listen zu bewegen wird durch Rekursion bewerkstelligt. Es geht aber u.U. auch ohne.

Ist dein Buch zufällig "C++ von A bis Z"?

Ja ist es ^^

Also ich erkläre mal wie ich das Ganze verstehe, dann wird vielleicht klarer wo meine Verständnissfehler liegen:

Das Element Knoten *zeiger, deutet quasi auf ein Objekt, was es bis zu diesem Zeitpunkt noch nicht gibt. Dieses Objekt hat den Namen zeiger.

Zeiger ist kein Wert sondern die Verschachtelung der Datenstruktur "Knoten".

Ich muss Quasi ein neues Objekt aus "Knoten erstellen":

Knoten *Irgendwas = new Knoten;

aus diesem Objekt kann ich nun unterobjekte erstellen, die andere Datenwerte haben:

Irgendwas -> zeiger = new Knoten.
Irgendwas -> zeiger -> Daten = 60.

Stimmt das soweit?

Es muss allerdings ja auch eine einfachere Methode geben, Elemente anzuhängen, z.b. mit einer Schleife oder? Wie würde das funktionieren?

Bei 50 verschiedenen Datensätzen kann ich ja nicht 50 mal zeiger schreiben um das letzte Element zu benennen ^^

drakon

Zackorz schrieb:

Also ich erkläre mal wie ich das Ganze verstehe, dann wird vielleicht klarer wo meine Verständnissfehler liegen:

Das Element Knoten *zeiger, deutet quasi auf ein Objekt, was es bis zu diesem Zeitpunkt noch nicht gibt. Dieses Objekt hat den Namen zeiger.

Genau. Üblicherweise hat der Zeiger den Wert 0, um anzuzeigen, dass er auf kein gültiges Objekt verweist.

Zeiger ist kein Wert sondern die Verschachtelung der Datenstruktur "Knoten".

Zeiger zeigt, (wenn es auf etwas zeigt) auf ein Objekt vom Typen "Knoten". Verschachtelt finde ich insofern ungünstig, dass es eine Enthalten impliziert, was ja nicht der Fall ist, da die Objekte nicht ineinander sind, sondern neben einander sind. Der Vorgänger zeigt einfach auf das nächste Element.

Ich muss Quasi ein neues Objekt aus "Knoten erstellen":

Knoten *Irgendwas = new Knoten;

aus diesem Objekt kann ich nun unterobjekte erstellen, die andere Datenwerte haben:

Irgendwas -> zeiger = new Knoten.
Irgendwas -> zeiger -> Daten = 60.

Stimmt das soweit?

Es muss allerdings ja auch eine einfachere Methode geben, Elemente anzuhängen, z.b. mit einer Schleife oder? Wie würde das funktionieren?

Bei 50 verschiedenen Datensätzen kann ich ja nicht 50 mal zeiger schreiben um das letzte Element zu benennen ^^

Ja. Das stimmt so eigentlich. Du kannst dir natürlich eine Funktion schreiben.

struct Knoten {
int daten;
Knoten *zeiger;
};

Knoten* append_node (Knoten* sibling, int data )
{
 sibling->zeiger = new Knoten; // Knoten erstellten
 sibling->zeiger->daten = data; // Daten einfüllen
 return sibling->zeiger; // Neuen Knoten zurückgeben
}

int main()
{
 Knoten* node = new Knoten;
 Knoten* last_node = 0; 
 last_node = append_node ( node2, 2 );

 last_node = append_node ( last_node, 5 );
 last_node = append_node ( last_node, 8 );
 // ...

 //am Ende die Elemente wieder mit delete freigeben
}

So kann man das Problem vermeiden. Und das befüllen mit mehreren Werten ist in einer Schleife nun auch trivial.

Es sei hier aber gesagt, dass das ganze üblicherweise in einer Klasse implementiert wird und dann auch für jegliche Typen. Das Beispiel da oben enthält ein paar Inkonsistenzen, ist also wirkilch nur gedacht, um das Prinzip zu erklären. Dazu fehlen noch Funktionen für das entfernen, suchen usw.

SeppJ

Zackorz schrieb:

Das Element Knoten *zeiger, deutet quasi auf ein Objekt, was es bis zu diesem Zeitpunkt noch nicht gibt. Dieses Objekt hat den Namen zeiger.

Nicht ganz. zeiger zeigt auf ein anderes Objekt vom Typ Knoten und das Objekt existiert auch tatsächlich. Die Bemerkung mit dem Namen verstehe ich nicht. Weißt du überhaupt wie zeiger genau funktonieren?

Zeiger ist kein Wert sondern die Verschachtelung der Datenstruktur "Knoten".

Zeiger ist ein Wert und zwar ein Zeiger auf das nächste Element.

Ich muss Quasi ein neues Objekt aus "Knoten erstellen":

Knoten *Irgendwas = new Knoten;

aus diesem Objekt kann ich nun unterobjekte erstellen, die andere Datenwerte haben:

Irgendwas -> zeiger = new Knoten.
Irgendwas -> zeiger -> Daten = 60.

Stimmt das soweit?

Ganz richtig. Aber denke nicht in Unterobjekten, sondern denk an eine Kette von Objekten.

Es muss allerdings ja auch eine einfachere Methode geben, Elemente anzuhängen, z.b. mit einer Schleife oder? Wie würde das funktionieren?

Klar, das automatisiert man normalerweise. Guck dir mal die Referenz von std::list an, damit du siehst, welche Operationen Sinn machen. Wenn dein Compiler eine lesbare Implementierung von std::list hat, kannst du dir die auch angucken, damit du siehst, wie diese Funktionen umgesetzt werden. Da Compilerimplementierungen jedoch meistens eher unleserlich sind, empfehle ich eher mal im Netz nach einer Beispielimplementierung zu suchen.

Zackorz

Danke für eure Hilfe

Ich glaube ich hab das Grundprinzip jetzt verstanden.