einfach verkettete Liste < Datenstrukturen < Schule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:11 Do 04.03.2010 | | Autor: | Ferma |
Hallo Forum,
aus eine einfach verketteten Liste soll eine doppelt verkettete Liste gebastelt werden.
#include "stdafx.h"
using namespace System;
ref struct liste {
String ^daten
liste ^next;
};
Es folgen zwei Funktionen: "anhaengen" und "ausgeben"
Dann folgt die main (Hauptfunktion)
int main(array<System::String ^> ^args) {....}
Kann jemand mir die "Idee" dieser Listen erklären und wie man aus der einfachen eine doppelt verkettete Liste erstellt? Bin dankbar für jede Hilfe.
Das in C++/CLI
Viele Grüße, Ferma
|
|
| |
|
Hallo,
> Hallo Forum,
> aus eine einfach verketteten Liste soll eine doppelt
> verkettete Liste gebastelt werden.
> #include "stdafx.h"
> using namespace System;
> ref struct liste {
> String ^daten
> liste ^next;
> };
> Es folgen zwei Funktionen: "anhaengen" und "ausgeben"
> Dann folgt die main (Hauptfunktion)
> int main(array<System::String ^> ^args) {....}
> Kann jemand mir die "Idee" dieser Listen erklären und wie
> man aus der einfachen eine doppelt verkettete Liste
> erstellt?
Zum Prinzip:
Du kennst Arrays in C++. Bei diesen musst du bei der Initialisierung immer die Größe angeben (also wieviele Felder du haben möchtest). Wenn du dann ein größeres Array brauchst, musst du eigentlich immer ein komplett neues Array initialisieren, die Daten kopieren usw., das ist im Allgemeinen nicht sehr elegant und auch langsam.
Listen sind ein Möglichkeit, Daten dynamisch zu speichern, und zwar so viele Daten eines Typs, wie man möchte. Das Prinzip ist Folgendes:
Ein "Listenelement" besteht aus den Daten (bei dir: "String daten") und einem Zeiger auf das nächste Listenelement (bei dir: "liste next"). Ein Listenelement enthält also immer Daten und weiß, wo das nächste Listenelement ist (aber nicht das vorherige; das Listenelement X weiß nicht, welches Listenelement gerade auf X zeigt).
Es entsteht folgende Struktur ![[]](/images/popup.gif) Hier ist ein Bild.
Überhaupt empfehle ich dir, den Wikipedia-Artikel zum Thema "Liste (Datenstruktur)" zu lesen.
Durch die Datenstruktur kann man immer wieder neue Listenelement dynamisch erschaffen und diese an die Liste anhängen. Eine Liste kann deswegen auch während der Laufzeit seine Länge beliebig ändern.
-------
Wie ich oben schon erwähnt hatte, haben die Listenelemente dern"einfach verkettete Listen" aber nur einen Zeiger auf das NÄCHSTE Element, wissen aber nicht, wer auf sie selbst zeigt.
Eine doppelt verkettete Liste behebt diesen Nachteil (oft ist es wichtig, auch das Element zu kennen, das auf das gerade behandelte Listenelement zeigt). Dazu fügt man einfach in das struct einen neuen Zeiger ein:
#include "stdafx.h"
using namespace System;
ref struct liste {
String ^daten
liste ^next;
liste ^vorher;
};
Der Zeiger vorher bleibt beim "obersten" Listenelement immer NULL (es gibt kein Listenelement, das auf das "oberste" zeigt).
Grüße,
Stefan
|
|
|
|
![[]](http://de.wikipedia.org/w/index.php?title=Datei:Einfach_verkettete_Liste.png&filetimestamp=20041221154949){kind=small}
Hier ist ein Bild