Einfach verkettete Listen

[p80286]

Ich bin da nicht ganz zufrieden:

Delphi-Quellcode:

procedure ClearList;
var
  TempNode: PNode;
begin
  CurrentNode := FirstNode;
  while (CurrentNode <> nil) do
  begin
    TempNode := CurrentNode.Next;
    Dispose (CurrentNode);
    CurrentNode := TempNode;
  end;
  FirstNode := nil;
  LastNode := nil;
end;

Wenn es den FirstNode und den LastNode gibt sollte mann sie auch nutzen, wobei bei den einfach verketteten Listen der LastNode eigentlich überflüssig ist.

Delphi-Quellcode:

procedure ClearList;
// ---- TempNode ist überflüssig
//var
//  TempNode: PNode;
begin
  CurrentNode := FirstNode;
  repeat
    FirstNode:=FirstNode^.Next;   // FirstNode zeigt immer auf den ersten gültigen... 
    dispose(CurrentNode);         // Freigeben
    CurrentNode:=FirstNode;       // CurrentNode nachziehen   
  until CurrentNode=Nil;  
  //FirstNode := nil;         ----das ist er schon!!
  LastNode := FirstNode;
end;

Mir gefällt hier "Return until" besser, weil es mir logischer erscheint.

Edit:
einfügen von Daten an beliebiger Stelle in eine doppelt verkettete Liste:

Delphi-Quellcode:

{ FirstNode ist wirklich der erste! }
{ CurrentNode enthält Daten und .next und .last sind mit Nil vorbelegt!        }
begin
  LastNode:=FirstNode;
  While (LastNode.next<>Nil) and (LastNode^.data<>MeineBedingung) do LastNode:=LastNode^.next;
  {-- vor LastNode einfügen --}
  CurrentNode^.last:=LastNode^.last;
  CurrentNode^.last^.next:=CurrentNode;
  CurrentNode^.next:=LastNode;
  LastNode^.last:=CurrentNode;
  {-- nach LastNode einfügen --}
  CurrentNode^.last:=LastNode;
  CurentNode^.next:=LastNode^.next;
  LastNode^.next:=CurrentNode;
  if CurrentNode^.next<>Nil then
    currentNode^.next^.last:=CurrentNode;
end;

Gruß
K-H

[TBx]

Zitat von p80286:

Mir gefällt hier "Return until" besser, weil es mir logischer erscheint.

Repeat Until ist hier definitiv falsch, Wendet man ClearList nun an, wenn noch kein Node existiert, knallt es!

Klar ist es möglich, den TempNode zu umgehen. Fragt sich nur, was besser zu verstehen ist.

[p80286]

Jo das kommt davon wenn man altes Zeug einfach kopiert!
Die Abfrage
If FirstNode<>nil then hatte ich geschlabbert.

Nach Meinem Verständnis ist der FirstNode der Anker der Liste, und der CurrentNode ist der "Gleiter".
Darum will ich nicht noch eine weitere Variable einführen, mit der ich an der Liste arbeite.

Gruß
K-H

[Bjoerk]

Ich habe mir das Tutorium von Michael Puff dieser Tage auch mal näher angesehen und daraus nachfolgende unit erstellt. Könnte mal jemand kurz drüber schauen, ob das Ganze soweit okay ist, ob ich nicht irgendwelche Speicherlecks produziere und ob man sich das inherited sparen kann, sofern es sich nur auf TObject bezieht? Danke!

Delphi-Quellcode:

unit EinfachVerketteteListen;

interface

uses
  Classes;

type
  TData = record
    Name: string;
  end;
  PNode = ^TNode;
  TNode = record
    Data: TData;
    Next: PNode;
  end;
  Tliste = class(TObject)
    function Count: integer;
    procedure clearItem(Index: integer);
    procedure AddItem(Data: TData);
    function GetItem(Index: integer): TData;
    procedure SetItem(Index: integer; Data: TData);
    procedure DelItem(Index: integer);
    procedure InsItem(Index: integer; Data: TData);
    procedure Exchange(Index1,Index2: integer);
    procedure SortByName;
    function IndexOfName (Name: string) : integer;
  private
    FirstNode, LastNode, CurrentNode: PNode;
    procedure InitList;
    procedure ClearList;
    procedure AddNode(Data: TData);
    procedure InsertNodeAfter(AfterNode: PNode; Data: TData);
    procedure DeleteNextNode(Node: PNode);
    function GetNode(Index: integer): PNode;
    Procedure Null(var Data: TData);
  public
    constructor Create;
    destructor Destroy; override;
  end;

implementation

procedure TListe.InitList;
begin
  FirstNode := nil;
  LastNode := nil;
end;

constructor TListe.Create;
begin
  inherited Create;
  InitList;
end;

procedure TListe.ClearList;
var
  Node: PNode;
begin
  CurrentNode := FirstNode;
  while (CurrentNode <> nil) do
  begin
    Node := CurrentNode.Next;
    Dispose (CurrentNode);
    CurrentNode := Node;
  end;
  InitList;
end;

destructor TListe.Destroy;
begin
  ClearList;
  inherited;
end;

procedure TListe.AddNode(Data: TData);
begin
  New(CurrentNode);
  CurrentNode.Data := Data;
  CurrentNode.Next := nil;
  if LastNode = nil then
  begin
    FirstNode := CurrentNode;
    LastNode := CurrentNode;
  end
  else
  begin
    LastNode.Next := CurrentNode;
    LastNode := CurrentNode;
  end;
end;

procedure TListe.InsertNodeAfter(AfterNode: PNode; Data: TData);
var
  Node: PNode;
begin
  New(Node);
  Node.Data := Data;
  Node.Next := AfterNode.Next;
  AfterNode.Next := Node;
end;

procedure TListe.DeleteNextNode(Node: PNode);
var
  TempNode: PNode;
begin
  if Count>1 then
  begin
    if Node.Next <> nil then
    begin
      TempNode := Node.Next;
      Node.Next := Node.Next.Next;
      Dispose(TempNode);
    end
  end
  else
    ClearList;
end;

function TListe.Count: integer;
begin
  Result := 0;
  CurrentNode := FirstNode;
  while CurrentNode <> nil do
  begin
    CurrentNode := CurrentNode.Next;
    Result := Result + 1;
  end;
end;

function TListe.GetNode(Index: integer): PNode;
var
  i: integer;
begin
  i:=0;
  CurrentNode := FirstNode;
  while ((CurrentNode <> nil) and (i < Index)) do
  begin
    i:= i+1;
    CurrentNode := CurrentNode.Next;
  end;
  Result:=CurrentNode;
end;

procedure TListe.Null(var Data: TData);
begin
  with Data do
  begin
    Name := '';
  end;
end;

procedure TListe.ClearItem(Index: integer);
var
  Node: PNode;
begin
  Node := GetNode(Index);
  Null(Node.Data);
end;

procedure TListe.AddItem(Data: TData);
begin
  AddNode(Data);
end;

function TListe.GetItem(Index: integer): TData;
var
  Node: PNode;
begin
  Null(Result);
  Node := GetNode(Index);
  Result := Node.Data;
end;

procedure TListe.SetItem(Index: integer; Data: TData);
var
  Node: PNode;
begin
  Node := GetNode(Index);
  Node.Data := Data;
end;

procedure TListe.DelItem(Index: integer);
var
  Node: PNode;
begin
  Node := GetNode(Index-1);
  DeleteNextNode(Node);
  FirstNode := GetNode(0);
  LastNode := GetNode(Count-1);
end;

procedure TListe.InsItem(Index: integer; Data: TData);
var
  Node: PNode;
begin
  Node := GetNode(Index);
  InsertNodeAfter(Node,Data);
  FirstNode := GetNode(0);
  LastNode := GetNode(Count-1);
end;

procedure TListe.Exchange(Index1,Index2: integer);
var
  Data1,Data2: TData;
begin
  Data1 := GetItem(Index1);
  Data2 := GetItem(Index2);
  SetItem(Index1,Data2);
  SetItem(Index2,Data1);
end;

procedure TListe.SortByName;
var
  i,j: integer;
begin
  for i := 0 to Count - 2 do
    for j := i+1 to Count - 1 do
      if GetItem(i).Name > GetItem(j).Name then Exchange(i,j);
end;

function TListe.IndexOfName (Name: string): integer;
var
  i: integer;
begin
  result := -1;
  for i := 0 to Count - 1 do
    if GetItem(i).Name = Name then
    begin
      result := i;
      break;
    end;
end;

end.

[p80286]

Hallo Bjoerk,

mir ist da nichts aufgefallen. Allerdings hätte ich an Deiner Stelle eine doppelt verkettete Liste genommen, das erspart den immer wiederkehrenden Einstieg über Firstnode.

Das hier solltest Du einmal überdenken, da meiner Meinung nach FirstNode FirstNode bleibt, bist FirstNode=NIL!

Delphi-Quellcode:

procedure TListe.DelItem(Index: integer);
var
  Node: PNode;
begin
  Node := GetNode(Index-1);
  DeleteNextNode(Node);
  FirstNode := GetNode(0);
  LastNode := GetNode(Count-1);
end;

Und die Definition von TData ist irgendwie doppelt gemoppelt.

Gruß
K-H

[Bjoerk]

thanx!

Wie ist das mit dem inherited (Siehe letzten Teil der Frage)? Ist das erforderlich?

[p80286]

Mit Gewissheit kann ich es Dir nicht beantworten, Zu dem Thema gab es hier schon einmal eine Diskussion, aber es ist eigentlich nicht falsch.

Gruß
K-H

Edith:
War da nicht etwas mit Free und Destroy?

Zitat:

Beschreibung

Mit Free wird ein Objekt freigegeben. Wenn die Objektreferenz nicht nil ist, wird Destroy aufgerufen. Alle zur Laufzeit instantiierten Objekte, die keinen Eigentümer besitzen, sollten mit Free aufgelöst werden, damit sowohl das Objekt als auch der zugehörige Speicher korrekt freigegeben wird. Im Gegensatz zu Destroy funktioniert Free auch dann, wenn das Objekt nil ist. Es ist also kein Fehler, die Methode für ein Objekt aufzurufen, das niemals initialisiert wurde.

Wenn Sie Free für eine Komponente aufrufen, werden alle untergeordneten Objekte (die Einträge in ihrer Komponentenliste) automatisch freigegeben. Da ein Formular der Eigentümer aller Steuerelemente und anderer Komponenten ist, die Sie im Entwurfsmodus hinzugefügt haben, werden diese Komponenten automatisch mit dem Formular freigegeben. Alle Formulare gehören standardmäßig zum Anwendungsobjekt (TApplication) und werden daher zusammen mit diesem aus dem Speicher entfernt. Bei Objekten, die keine Komponenten sind, oder bei mit dem Eigentümer nil erstellten Komponenten muss Free explizit aufgerufen werden, wenn das betreffende Objekt nicht mehr benötigt wird. Der zugewiesene Speicher kann sonst erst nach dem Beenden der Anwendung wieder verwendet werden.

[mleyen]

Indexe sind aber nicht der Sinn von verketteten Listen. Dabei besser zu TList greifen.

[Bjoerk]

wird bezüglich inherited dort fortgesetzt:

http://forum.delphi-treff.de/showthr...170#post218170