AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Thema durchsuchen
Ansicht
Themen-Optionen

doppelt verkettete listen

Ein Thema von daswurm · begonnen am 14. Dez 2005 · letzter Beitrag vom 14. Dez 2005
 
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#10

Re: doppelt verkettete listen

  Alt 14. Dez 2005, 19:33
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...
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
 


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 06:23 Uhr.
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz