Programmierkurs: Delphi: Dynamische Datenstrukturen
Dynamische Datenstrukturen
[Bearbeiten]Die klassische Methode: Listen
[Bearbeiten]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:
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:
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:
und die entsprechende Belegung mit Nichts:
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:
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:
Da hierbei jedoch das Element in next
(falls vorhanden) nicht ordnungsgemäß freigegeben würde, muss man mit einer Schleife alle Elemente einzeln freigeben:
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
[Bearbeiten]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
[Bearbeiten]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.
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
[Bearbeiten]Im Konstruktor muss dem Feld Speicher zugewiesen werden, ohne diesen jedoch bereits mit Daten zu füllen:
Der Destruktor sollte auf gleiche Weise den Speicher wieder freigeben:
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.
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.
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.
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.
Das Auslesen und Ändern vorhandener Daten gestaltet sich ebenfalls sehr einfach.
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
[Bearbeiten]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:
Auf diese Weise ist ein wirklich einfacher Zugriff auf die Daten möglich:
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
[Bearbeiten]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.
Inhaltsverzeichnis | DLL-Programmierung |