Programmierkurs: Delphi: Dynamische Datenstrukturen

Dynamische Datenstrukturen

Die klassische Methode: Listen

Die hier gezeigte Vorgehensweise ist stark veraltet, fehleranfällig und umständlich. Seit Delphi 4 gibt es bessere und sicherere Methoden, dynamische Datenstrukturen zu handhaben. Siehe hierzu Die moderne Methode: Klassen. Die klassische Vorgehensweise ist nur für erfahrene Programmierer geeignet, die aus dieser Laufzeit-Geschwindigkeitsvorteile ziehen wollen.

Eine Liste ist wie alle dynamischen Datenstrukturen eine rekursive Datenstruktur, d.h.: sie referenziert sich selbst. Schauen wir uns mal folgendes Beispiel für eine Typendefinition für Listen an:

Code:

type
  PListItem = ^TListItem;
  TListItem = record
    data: Integer;
    next: PListItem;  // Verweis auf das nächste Item
  end;

Man sieht, dass der Zeiger in PListItem auf ein Objekt gelegt wird, das noch nicht definiert ist. Eine solche Definition ist nur bei rekursiven Strukturen möglich.

Möchte man nun eine neue, leere Liste erzeugen, so reicht folgender Code:

Code:

var
  Liste: PListItem;
begin
  New(Liste);
  Liste^.data := 0;
  Liste^.next := nil; // WICHTIG!!!
end;

Vergessen Sie bitte niemals, einen nicht benötigten Zeiger (wie in diesem Fall) auf nil zu setzen, da das gerade bei dynamischen Datenstrukturen zu nicht vorhersehbaren Fehlern führen kann.

Wollen sie nun ein Item der Liste hinzufügen, ist folgender Code zu benutzen:

Code:

New(Liste^.next);

und die entsprechende Belegung mit Nichts:

Code:

 Liste^.next^.data := 0;
 Liste^.next^.next := nil;

Es ist natürlich lästig und aufwändig, die Liste auf diese Weise zu vergrößern. Deshalb benutzt man eine Prozedur, um die Liste bis zu ihrem Ende zu durchlaufen und an ihrem Ende etwas anzuhängen:

Code:

procedure AddItem(List: PListItem; data: Integer);
var
  tmp: PListItem;
begin
  tmp := List;
  while tmp^.next <> nil do
    tmp := tmp^.next;
  New(tmp^.next);
  tmp^.next^.data := data;
  tmp^.next^.next := nil;
end;

Da dies aber sehr zeitaufwändig ist, sollte immer das letzte Element der Liste gespeichert werden, um nicht zuerst die gesamte Liste durchlaufen zu müssen, bevor das neue Element angehängt werden kann.

Um eine Liste wieder aus dem Speicher zu entfernen, genügt es nicht, die Variable Liste auf nil zu setzen. Dabei würde der verbrauchte Speicherplatz belegt bleiben und auf die Dauer würde das Programm den Speicher „zumüllen“. Um die Objekte wieder freizugeben, muss Dispose verwendet werden:

Code:

 Dispose(Item);

Da hierbei jedoch das Element in next (falls vorhanden) nicht ordnungsgemäß freigegeben würde, muss man mit einer Schleife alle Elemente einzeln freigeben:

Code:

procedure DisposeList(var List: PListItem);
var
  current, temp: PListItem;
begin
  current := List;
  while current <> nil do
  begin
    temp := current^.next;
    Dispose(current);
    current := temp;
  end;
  List := nil;
end;

Hier wird in jedem Schleifendurchlauf das aktuelle Element freigegeben und das nächste Element zum aktuellen gemacht. Hier wäre zwar prinzipiell auch eine rekursive Funktion möglich (und eventuell auch die zunächst offensichtliche Lösung), diese würde aber bei sehr großen Listen einen Stack Overflow auslösen.

Die moderne Methode: Klassen

Nachteile der Listenmethode sind vor allem die Fehleranfälligkeit und die umständliche Referenzierung. Sinnvoller - und natürlich auch komplexer - ist hier der Einsatz einer sich selbst verwaltenden Klasse. Hierbei hat man als Anwender lediglich Zugriff auf Methoden, nicht jedoch auf die Datenstruktur selbst. Dies bewirkt einen höchstmöglichen Schutz vor Fehlern.

Grundgerüst

Als Basis für die dynamische Liste wird ein dynamisches Array verwendet. Der Speicherbedarf hierfür lässt sich dem Bedarf entsprechend anpassen. Weiterhin werden Methoden benötigt, um neue Daten hinzuzufügen, nicht mehr benötigte zu löschen, vorhandene auszulesen oder zu ändern. Dies alles wird in einer Klasse gekapselt.

Code:

type
  TMyList = class
  private
    FFeld: array of Integer;
  public
    constructor Create;
    destructor Destroy; override;
    function Count: Integer;
    procedure Add(NewValue: Integer);
    procedure Delete(Index: Integer);
    procedure Clear;
    function GetValue(Index: Integer): Integer;
    procedure SetValue(Index: Integer; NewValue: Integer);
  end;

Implementation

Im Konstruktor muss dem Feld Speicher zugewiesen werden, ohne diesen jedoch bereits mit Daten zu füllen:

Code:

constructor TMyList.Create;
begin
  inherited;
  SetLength(FFeld, 0);
end;

Der Destruktor sollte auf gleiche Weise den Speicher wieder freigeben:

Code:

destructor TMyList.Destroy;
begin
  SetLength(FFeld, 0);
  inherited;
end;

Für die Verwendung der Liste ist es oftmals notwendig, deren Größe zu kennen, um nicht eventuell über deren Ende hinaus Daten auszulesen. Das wird mit der simplen Methode Count verwirklicht.

Code:

function TMyList.Count: Integer;
begin
  Result := Length(FFeld);
end;

Um nun Daten hinzuzufügen, wird eine weitere Methode benötigt: Add. Hierbei ist zu beachten, dass der erste Index der Liste immer 0 (Null) ist. Wenn nur ein Eintrag enthalten ist (Count = 1), dann ist dieser in FFeld[0] zu finden. Durch den Aufruf von SetLength wird das Feld um einen Eintrag erweitert, womit sich auch das Ergebnis von Count um 1 erhöht. Demnach muss beim Speichern des Wertes wieder 1 subtrahiert werden.

Code:

procedure TMyList.Add(NewValue: Integer);
begin
  SetLength(FFeld, Count + 1);    // Größe des Feldes erhöhen
  FFeld[Count - 1] := NewValue;   // Neuen Eintrag ans Ende der Liste setzen
end;

Das Löschen eines Eintrages gestaltet sich etwas schwieriger, da dieser sich am Anfang, in der Mitte oder am Ende der Liste befinden kann. Je nachdem müssen die Daten gegebenenfalls umkopiert werden.

Code:

procedure TMyList.Delete(Index: Integer);
var
  i: Integer;
begin
  if (Index < 0) or (Index >= Count) then
    Exit;

  if Index = Count - 1 then        // letzter Eintrag
    SetLength(FFeld, Count - 1)    // Es reicht, den Speicher vom letzten Eintrag freizugeben
  else                             // erster Eintrag oder irgendwo in der Mitte
  begin
    for i := Index to Count - 2 do
      FFeld[i] := FFeld[i + 1];
    SetLength(FFeld, Count - 1);
  end;
end;

Man sollte auch die Liste leeren können, ohne jeden einzelnen Eintrag zu löschen. Hierfür muss nur wieder die Größe des Feldes auf 0 gesetzt werden.

Code:

procedure TMyList.Clear;
begin
  SetLength(FFeld, 0);
end;

Das Auslesen und Ändern vorhandener Daten gestaltet sich ebenfalls sehr einfach.

Code:

function TMyList.GetValue(Index: Integer): Integer;
begin
  if (Index < 0) or (Index >= Count) then
    Result := -1                      // Oder ein anderer Wert, der einen Fehler darstellt
  else
    Result := FFeld[Index];
end;

procedure TMyList.SetValue(Index: Integer; NewValue: Integer);
begin
  if (Index < 0) or (Index >= Count) then
    Exit
  else
    FFeld[Index] := NewValue;
end;

Erweiterungsmöglichkeit

Um einen noch komfortableren Zugriff auf die Daten zu erhalten, können diese über eine Eigenschaft aufgerufen werden. Hierzu werden die Methoden GetValue und SetValue „versteckt“, das heißt, im Bereich private der Klasse untergebracht. Im Bereich public kommt folgendes hinzu:

Code:

public
  property Items[I: Integer]: Integer read GetValue write SetValue; default;

Auf diese Weise ist ein wirklich einfacher Zugriff auf die Daten möglich:

Code:

var
  MyList: TMyList;
  i: Integer;
begin
  MyList := TMyList.Create;
  MyList.Add(2);       // MyList[0] = 2
  MyList.Add(3);       // MyList[1] = 3
  MyList.Add(5);       // MyList[2] = 5

  i := MyList[2];      // i = 5
  MyList[0] := 13;     // MyList[0] = 13
  MyList.Free;
end;

Anmerkung

Die hier gezeigte Lösung stellt nur den einfachsten Ansatz einer dynamischen Datenverwaltung dar. Sie kann jedoch Daten jeden Typs speichern, es muss lediglich der Typ von FFeld und aller betroffenen Methoden angepasst werden. Auch andere Klassen können so gespeichert werden.

Dieses Grundgerüst ist auf einfachste Weise erweiterbar. Zum Beispiel können Methoden zum Suchen und Sortieren von Daten eingebaut werden. Auch das Verschieben von Einträgen wäre denkbar.

Pointer

Inhaltsverzeichnis

DLL-Programmierung