doppelt verkettete listen

[daswurm]

huhu
ich habe eine dummes problem und kann es leider absolut nicht alleine lösen. wir müssen im informatik unterricht ein programm machen welches folgende kriterien erfüllen soll ( alles delphi 4 ) :

- doppelt verkettete liste
- einfügen neuer einträge alphabetisch
- ausgabe der daten in einer listbox
- suchen
- löschen des gefundenen eintrags
- speichern und laden auf der festplatte

so das wars auch schon was wir machen müssen, nur leider habe ich keine ahnung was wir machen sollen, da unser lehrer sehr kompliziert erklärt und leider auch nicht so ganz auf fragen eingeht, naja egal ich tue mir auf jeden fall sehr schwer zu begreifen wie ich sowas programmieren soll....

kann mir vielleicht jemand nettes dabei helfen ... ich würde mich sehr freuen ... danke schon mal im vorraus fürs erklären

[Binärbaum]

Also gut.
Der grundgedanke bei doppelt verketteten Listen ist, dass man bei jedem Element auch einen Zeiger auf das vorherige und nachfolgende Listenelement hat. Damit kann man (im Gegensatz zu einfach verketteten Listen) von jedem Element aus in beide Richtungen einer Liste gehen.
Eine Typdeklaration könnte etwa so aussehen:

Delphi-Quellcode:

type
  PListelement = ^TListelement;//Zeiger auf Listenelement
  TListelement = record
                     data: char; //oder Integer oder String
                                 //oder was auch immer man gerade benötigt
                     vorheriges, //Zeiger auf vorheriges Element
                     naechstes:  PListenElement; //Zeiger auf nachfolgendes Element
  end;

MfG
Binärbaum

[daswurm]

ok das hab ich begriffen, hab ich auch schon eingebaut in meine procdure ... aba wie gehts jetzt weiter mit dem alphabetischen einfügen ??

[Binärbaum]

Zitat von daswurm:

ok das hab ich begriffen, hab ich auch schon eingebaut in meine procdure ... aba wie gehts jetzt weiter mit dem alphabetischen einfügen ??

Nun ja, wenn du das bloße Einfügen beherrschst, ist das kein zu großes Problem: man läuft einfach die Liste vom Anfang an durch und prüft, ob das Element, bei dem man sich gerade befindet, im Alphabet vor oder nach dem einzufügenden Element kommt, und fügt dann an der entsprechenden Stelle das neue Element ein. Dabei sind allerdings einige Sonderfälle wie z.B. das Einfügen in eine noch leere Liste zu beachten.

MfG
Binärbaum

[daswurm]

ähm das klingt jetzt bestimmt völlig behemmert für dich aba so ganz hab ich das jetzt nicht verstanden ! sry ...
mir war schon bewusst das ich die liste von vorne durch laufen muss, aba wie mach ich das denn genau ??

ich bin leider vollkommen verwirrt ... ich habe bis jetzt nur mit einfacher verkettungung gearbeitet, nun wäre es ja eigentlich auch sehr sinnvoll könnte man einfach die einfache verkettung umschreiben, aba dies stellt sich als recht schwer für mich heruas .. naja ich weiß echt nicht weiter

scheiße, auch wenns jetzt bestimmt nervt kannst du mir das vll anhand eines beispieles erläutern mit dem einfügen ... ich möchte auch wirklich nicht, wenn das den schein erwecken sollte, dass mir das komplette programm geschrieben wir, denn dies erachte ich als nicht sehr sinnvoll.

[Binärbaum]

Zitat von daswurm:

so ganz hab ich das jetzt nicht verstanden ! sry ...
mir war schon bewusst das ich die liste von vorne durch laufen muss, aba wie mach ich das denn genau ??

ich bin leider vollkommen verwirrt ... ich habe bis jetzt nur mit einfacher verkettungung gearbeitet, nun wäre es ja eigentlich auch sehr sinnvoll könnte man einfach die einfache verkettung umschreiben, aba dies stellt sich als recht schwer für mich heruas .. naja ich weiß echt nicht weiter

Wenn du schon mit einfach verketteten Listen gearbeitet hast, hast du doch schon die (sprichwörtliche) halbe Miete. Du kannst ja erstmal "so tun", als ob die Liste nur einfach verkettet wäre und (wie bei einfach verketteten Listen) immer nur den Zeiger auf das nächste Element nutzen, um die Liste zu durchlaufen.

Zitat von daswurm:

kannst du mir das vll anhand eines beispieles erläutern mit dem einfügen ...

Ach du Schreck, da muss ich ja selbst Code schreiben, oder? :p
Nee, Scherz, ich kanns machen, aber das dauert eine Weile, da ich aus der Listenmaterie etwas raus bin.

Aber mal etwas zum allgemeinen Prinzip: nehmen wir an, du hast eine Liste, die nicht leer ist und schon einige alphabetisch sortiete Elemente enthält. Nehmen wir weiterhin an, dass sich folgende Elemente in der Liste befinden:

Code:

'a' <-> 'c' <-> 'f' <-> 'r' <-> 'a'

(Das letze Element ist wieder das Anfangselement.)
Als Beispiel sei mal gesagt, dass wir das Zeichen 'd' einfügen wollen. Also fangen wir am Anfang der Liste an und vergleichen:
a kommt vor d, also ermitteln wir über die Komponente .nachstes das nächste Element in der Liste. Diese wird dann wieder verglichen, und c kommt ja vor d, also gehen wir wieder ein Element weiter. Nun sind wir bei f und merken, dass f nach d kommt, also sind wir eigentlich schon zu weit. Also (und jetzt kommt der komplizierte Teil) müssen wir ein neues Listenelement anlegen und dieses vor f einfügen, indem wir die Zeiger von f und von c entsprechend abändern, sodass der Zeiger .naechstes von c auf das neue Listenelement zeigt und der Zeiger .vorheriges von f ebenfalls auf das neue Listenelement. Jetzt müssen noch die Zeiger .vorheriges bzw. .naechstes von d so geändert werden, dass sie auf die Elemente c bzw. f zeigen.
Fertig.

Zitat von daswurm:

ich möchte auch wirklich nicht, wenn das den schein erwecken sollte, dass mir das komplette programm geschrieben wir, denn dies erachte ich als nicht sehr sinnvoll.

Sehr gut, dass du das von selbst einsiehst. Wenn man etwas selber schreibt, lernt man mehr, als wenn man nur den fertigen Code vorgestzt bekommt.

MfG
Binärbaum

[Der_Unwissende]

Zitat von Binärbaum:

Code:

'a' <-> 'c' &lt;-&gt; 'f' &lt;-&gt; 'r' &lt;-&gt; 'a'

hm, dein letztes a ist aber alphabetisch etwas falsch eingefügt, oder?

@daswurm Wie gut hast du denn die Listen (egal wie die verkettet sind) überhaupt verstanden? Ist nämlich wichtig die gut zu kennen, auf der Idee basiert unter anderem auch ein Binärbaum

Ist echt wichtig, die zu verstehen. Mit dem Sinn hast du schon deswegen recht, weil es (bestimmt immer noch) eine der beliebten Klausur- und Testaufgaben ist. Aber natürlich ist es auch wichtig es einfach verstanden zu haben (und an sich gar nicht so schwer).
Solltest nur nie Angst haben nachzufragen, wenn du etwas nicht verstehst (hast du zum Glück nicht).

Gruß Der Unwissende

[Binärbaum]

Zitat von Der_Unwissende:

Zitat von Binärbaum:

Code:

'a' <-> 'c' &lt;-&gt; 'f' &lt;-&gt; 'r' &lt;-&gt; 'a'

hm, dein letztes a ist aber alphabetisch etwas falsch eingefügt, oder?

Nein, das stimmt schon und ist so beabsichtigt. Das letzte 'a' soll nur verdeutlichen, dass die Liste dann wieder von vorn beginnt, weil der Zeiger .naechstes von r wieder auf das a am Anfag der Liste zeigt.
Alternativ könnte man es auch so machen, dass der entsprechende Zeiger im letzten Element nil ist (das würde wahrscheinlich auch die Programmierung der Funktionen/Prozeduren fürs Einfügen u.a. erleichtern).

[Der_Unwissende]

Ok, sorry hab es dann nur falsch verstanden, wusste nicht dass du gleich eine zirkuläre verwenden wolltest. Denke aber auch dass es für einen Anfänger leichter wird, wenn du mit nil anfängst (wobei es ja nur ein anderer Vergleich ist).

[alzaimar]

Ich würde Listen/Bäume etc., also verkettete Strukturen immer mit einem 'Wurzelknoten' beginnen. Dann sollte der Rest ohne Probleme gehen. Ob man die zirkulär oder nicht implementiert ist dann eigentlich Wurscht, soweit ich mich erinnere (o.k. eine Abfrage fällt weg).

Delphi-Quellcode:

Procedure EinfuegenInListe (EinWert : string; EineListe : PListenElement);
Var
  Q : PListenElement;

Begin
  P := FindeEinfuegePosition (EineListe, EinWert); // P ist das größte Element, das kleiner als EinWert ist.
  New (Q);
  Q^.Next := P^.Next;    // Der Nachfolger vom neuen Knoten Q ist der alte Nachfolger von P
  P^.Next := Q;          // Der neue Nachfolger von P ist Q.
  Q^.Prev := P;          // Der Vorgänger vom neuen Knoten ist P (den haben wir ja deswegen gesucht)
  If Q^.Next<>Nil Then   // Wenn der neue Knoten überhaupt einen Nachfolger hat, dann 
     Q^.Next^.Prev := Q; // ist Q der Vorgänger des Nachfolgers von Q (irgendwie logisch)
End;

Die 'leere Liste' wird einfach so initialisiert:

Delphi-Quellcode:

Function LeereListe : PListenElement;
Begin
  New(Result);
  Result^.Element := EinWertDerGarantiertKleinerAlsAlleJemalsEinzufuegendenElementeIst;
  Result^.Next := Nil;
  Result^.Prev := Nil;
End;

Wenn man die Liste zirkulär machen will (also dann zeigt das letzte Element nicht ins Leere, sondern wieder auf das vorderste Element, bzw. die Wurzel, dann sieht das so aus:

Delphi-Quellcode:

Procedure EinfuegenInListe (EinWert : string; EineListe : PListenElement);
Var
  Q : PListenElement;

Begin
  P := FindeEinfuegePosition (EineListe, EinWert); // P ist das größte Element, das kleiner als EinWert ist.
  New (Q);
  Q^.Next := P^.Next;    // Der Nachfolger vom neuen Knoten Q ist der alte Nachfolger von P
  P^.Next := Q;          // Der neue Nachfolger von P ist Q.
  Q^.Prev := P;          // Der Vorgänger vom neuen Knoten ist P (den haben wir ja deswegen gesucht)
  Q^.Next^.Prev := Q; // Q ist der Vorgänger des Nachfolgers von Q (irgendwie logisch)
End;

Die 'leere Liste' wird einfach so initialisiert:

Delphi-Quellcode:

Function LeereListe : PListenElement;
Begin
  New(Result);
  Result^.Element := EinWertDerGarantiertKleinerAlsAlleJemalsEinzufuegendenElementeIst;
  Result^.Next := Result;
  Result^.Prev := Result;
End;

Hier noch die Funktion zum Finden der Position:

Delphi-Quellcode:

Function FindeEinfuegePosition (EineListe : PListenElement; EinWert : TListenDatenTyp) : PListeElement;
       External 'IrgendwasMussJaAufDeinemMistGewachsenSein.DLL';

Ach ja: Alles aus dem Gedächtnis, ungetestet und eventuell fehlerhaft...