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 ?? :roll:

[Binärbaum]

Zitat:

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 ?? :roll:

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:

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:

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:

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:

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? :zwinker:

@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 :-D

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:

Zitat von Der_Unwissende

Zitat:

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? :zwinker:

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... :mrgreen:

[tigerman33]

Das ist IMHO keine so gute Idee. Zumindest funktioniert sie nur, wenn einige (zusätzliche) Bedingungen, die du als gegeben vorausgesetzt hast erfüllt sind.

So muss zum Beispiel ein Element des Datentyps existieren, dass garantiert niemals angenommen wird (denn das benutzt du ja als Datum der Wurzel). Wenn du aber beispielsweise eine Liste von ganzen Zahlen verwalten willst, wird dieses Kriterium Probleme bereiten.

Zum anderen wird es schwieriger, gesicherte Aussagen über die einzelnen Listenelemente zu treffen, da als zusätzlicher Fall immer die Wurzel hinzukommt, die man beachten muss.

Außerdem ist es doch nicht so das Problem, die leere Liste auch als solche zu implementieren (sprich Wurzelknoten = nil <=> Liste leer). Erst recht, wenn man das ganze in einer anständige Klasse kapselt. :)

[alzaimar]

Zitat:

Zitat von tigerman33

Das ist IMHO keine so gute Idee.

Wie willst Du dann in eine leere Liste das erste Element einfügen?

Zitat:

Zitat von tigerman33

So muss zum Beispiel ein Element des Datentyps existieren, dass garantiert niemals angenommen wird (denn das benutzt du ja als Datum der Wurzel). Wenn du aber beispielsweise eine Liste von ganzen Zahlen verwalten willst, wird dieses Kriterium Probleme bereiten.

Die Prämisse, ein 'Alpha', also ein kleinstes Element zu verwenden, erhöht die Performance "beträchtlich", da eine Abfrage in der zentralen Routine (Suchen) entfällt. Der Code wird einfacher, weil es eben immer einen Anfang gibt. Zur Not kann man aber auch auf

Delphi-Quellcode:

Result^.Element := EinWertDerGarantiertKleinerAlsAlleJemalsEinzufuegendenElementeIst;

verzichten. Dann kommt eben wieder eine kleine Abfrage hinzu (If Walker<>Root Then ...)

Zitat:

Zitat von tigerman33

Zum anderen wird es schwieriger, gesicherte Aussagen über die einzelnen Listenelemente zu treffen, da als zusätzlicher Fall immer die Wurzel hinzukommt, die man beachten muss.

Nee, genau anders herum. Ich muss doch nie(!) die Wurzel beachten. Wie funktioniert denn der Code, wenn die leere Liste als 'Nil' deklariert ist?

Zitat:

Zitat von tigerman33

Außerdem ist es doch nicht so das Problem, die leere Liste auch als solche zu implementieren (sprich Wurzelknoten = nil <=> Liste leer).

Zeig mal am Beispiel vom Verketten. Und zähle anschließend die Anzahl der Zeilen und die Performance. :mrgreen:

Zitat:

Zitat von tigerman33

Erst recht, wenn man das ganze in einer anständige Klasse kapselt. :)

Wie gesagt: Zeig mal. :coder:

[stoxx]

es macht sich sogar gut, wenn man nicht nur einen wurzelknoten, sondern sogar einen ungenutzen "Fußknoten" verwendet ( mit leerem nicht genutzten Inhalt)
man prüft also das Ende, ob Zeiger = Ende und nicht den Zeiger auf nil.
Das vereinfacht das ganze erheblich, da man im Code nicht die Fälle unterscheiden muss, ob man nun ein Element in der Mitte am Anfang oder am Ende einfügt.
Sondern man fügt es IMMER in der Mitte ein.

[tigerman33]

Zitat:

Zeig mal.

Gerne, aber nicht jetzt. Ich schreib nämlich diese und nächste Woche Klausuren und hab eigentlich keine Zeit. :wink: :pale:

Zitat:

Die Prämisse, ein 'Alpha', also ein kleinstes Element zu verwenden, erhöht die Performance "beträchtlich", da eine Abfrage in der zentralen Routine (Suchen) entfällt. Der Code wird einfacher, weil es eben immer einen Anfang gibt.

Hmm, da verstehe ich jetzt nicht so ganz was du mir sagen willst. Meinst du die einmalige Abfrage, ob Wurzel = nil? Und es bleibt immer noch das Problem, dass ein solches 'Alpha' nicht unbedingt existieren muss.

Zitat:

Zitat:

Zitat von tigerman33

Zum anderen wird es schwieriger, gesicherte Aussagen über die einzelnen Listenelemente zu treffen, da als zusätzlicher Fall immer die Wurzel hinzukommt, die man beachten muss.

Nee, genau anders herum. Ich muss doch nie(!) die Wurzel beachten. Wie funktioniert denn der Code, wenn die leere Liste als 'Nil' deklariert ist?

Das bezog sich jetzt eigentlich nicht direkt auf Code, sondern auf "normalsprachliche" oder mathematische Aussagen über die Listenelemente etwa nach der Art "Alle Listendatümmer" (:mrgreen:) sind Zweierpotenzen" o.ä.

[simonko]

also das einfügen ist eigentlich ganz leicht.
du hast einen listenkopf der am anfang der liste zeigt.

du übergibst ihn einer prozedur und den wert den du einfügen willst

Delphi-Quellcode:

new(neu);
neu.inhalt:=wert;
..
if zeiger = nil then
...zeiger:=neu
else
  if neu.inhalt<zeiger.inhalt then begin
    neu^.naechster:=zeiger;
    zeiger:=neu;
  end
    else
      einfuegen(zeiger^.naechster,wert);

so in etwa. löschen ist mit doppeltverketten listen auch leicht. und ausgeben sowieso

aja und der parameter zeiger muss VAR sein

[alzaimar]

Zitat:

Zitat von tigerman33

Zitat:

Zeig mal.

Gerne, aber nicht jetzt. Ich schreib nämlich diese und nächste Woche Klausuren und hab eigentlich keine Zeit. :wink: :pale:

Buuuuh! :zwinker: Das ist aber eine Ausrede, denn die paar Zeilen solltest Du in 2 Minuten heruntergetippt haben: Es ist ja einfacher, als meine 5 Zeilen, oder?

Die leere Liste besteht aus genau einem Element, der Wurzel. Eine leere Liste ist doch nicht Nichts, oder? Sondern eine 'leere Liste'.
Die Wurzel kann ein 'Alpha' (also ein kleinstes vorstellbares Element beinhalten) oder auch nicht. Ich arbeite meistens mit 'Alpha', weil es, wie gesagt, einen Vergleich spart. Das mit dem Alpha war übrigens dezenter Quark :oops: . Kein Wunder, das Du das nicht kapiert hast. Um Performance zu sparen, sollte man ein 'Omega' haben, also ein Element, das größer als alles Andere ist (siehe stoxx's Vorschlag)

Ich korrigiere also meinen Code:

Delphi-Quellcode:

Function LeereListe : PListenElement;
Begin
  New(Result);
  Result^.Element := EinWertDerGarantiertGrößerAlsAlleJemalsEinzufuegendenElementeIst;
  Result^.Next := Result;
  Result^.Prev := Result;
End;

Ich implementiere Linked Lists nicht mehr. Verwenden tu ich sie auch nicht, dafür gibts schliesslich SkipLists oder Dictionaries.

Schau mal in der einschlägigen Literatur (Wirth, Algorithms & Datastructures von Leiserson & Rivest, Sedgewick oder die Bibel:Knuth, etc.). Ist ja nicht auf meinem Mist gewachsen.

Die Idee, noch ein Tail zu verwenden ist äquivalent mit einer zirkulären Liste. Beide Versionen sind charmant, aber nicht ganz so trivial wie die 'reine Liste'. Dafür zu Ende gedacht.

@simonko: Das Einfügen hatte ich bereits kodiert..

[simonko]

ja aber meines ist besser :p ausserdem hab ich keine lust alle threads zu lesn :)

[daswurm]

huhu
danke schon mal für eure nette hilfe ... ich werde es mir morgen mal alles ganz genau ansehen und denn versuchen es selbst zu programmieren ... das kann ja ganz schön schwer werden, denn ich bin echt der meinung, dass ich in meiner noch recht jungen programmier laufbahn(2jahre) *g* noch nix schwierigeres gemacht habe. aba egal da muss ich wohl durch, wenn ich noch weitere fragen habe melde ich mal wieder *g* ... bei der netten hilfe komm ich echt gerne wieder
also rechnet damit dass ich bald wieder komme :lol:

[tigerman33]

Zitat:

Buuuuh! Zwinkern Das ist aber eine Ausrede, denn die paar Zeilen solltest Du in 2 Minuten heruntergetippt haben: Es ist ja einfacher, als meine 5 Zeilen, oder?

Na gut, aber wenn ich Freitag durchfalle mach ich dich verantwortlich (juhu...endlich einen Schuldigen gefunden!) :lol:

Delphi-Quellcode:

type PListElement = ^TListElement;
     TListElement = record
       Next: PListElement;
       Data: pointer; // Beispielsweise 
     end;
type TVList = class
     private
       FCount: integer;
       FWurzel: PListElement;
       function IsEmpty: boolean; inline;
       property RawItems[Index: integer]: PListElement read... // Den Code zum durchiterieren lass ich jetzt mal weg, ja?
     public
       property Count: integer read FCount;
       procedure Add(Element: pointer);
     end;

...
function EmptyList: TVList;
begin
  Result := TVList.Create;
end;

constructor TVList.Create;
begin
  FWurzel := nil;
  FCount := 0;
end;

function TVList.Empty: boolean;
begin 
  Result := FWurzel = nil;
end;

procedure TVList.Add(Element: pointer);
var InsIndex: integer;
    NewEl: PListElement;
begin
  if Empty then 
    InsIndex := 0 else
    InsIndex := GetInsIndex(Element);

  New(NewEl);
  if InsIndex <= Count - 1 then
    NewEl^.Next := RawItems[InsIndex];
  if InsIndex = 0 then
    Wurzel := NewEl else
    RawItems[InsIndex - 1].Next := NewEl;
end;

Das ist zwar natürlich nicht besonders sauber und beileibe nicht vollständig (außerdem ungetested), aber zumindest das Einfügen müsste so funktionieren. Dass die Funktion zum Einfüge-Index finden gegeben ist habe ich einfach mal angenommen. Das ließe sich zwar auch mit einem Methodenzeiger-Feld erledigen, aber so viel Arbeit wollte ich jetzt eigentlich nicht investieren.

//edit:
Okay, das

Zitat:

Eine leere Liste ist doch nicht Nichts, oder? Sondern eine 'leere Liste'.

ist natürlich ein Argument. Fragt sich nur, ob das programmiertechnisch irgendeinen Unterschied machen wird. Denn Konkatenation, Schnitt etc. musst du ja sowieso selbst implementieren.
Letztendlich handelt es sich also um verschiedene "Darstellungen" ein und desselben: Deine leere Liste wird charakterisiert durch "nur der Grundknoten vorhanden", meine durch "Wurzel = nil"

Ich sehe zwar mittlerweile, dass du namhafte Verstärkung auf deiner Seite hast, aber so ganz überzeug bin ich immer noch nicht. :zwinker:

PS: Wenn du mir jetzt sagst, dass mein Code länger ist, dann halte ich dem entgegen, dass da ja auch der ganze Klassenoverhead mit drinhängt (bis auf das was ich mir mal geschenkt habe...). Meine Add-Methode ist auch nicht viel länger als deine, und EmptyList sogar noch kürzer :mrgreen:

//edit2:
Ooh, so ein Quark. EmptyList geändert.