Programmierkurs: Delphi: Dynamische Datenstrukturen
Aus Wikibooks
Inhaltsverzeichnis |
[Bearbeiten] Dynamische Datenstrukturen
[Bearbeiten] Die klassische Methode: Listen
Bitte beachten: 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:
New(Liste^.next);
und die entsprechende Belegung mit Nichts:
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:
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:
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:
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.
[Bearbeiten] 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.
[Bearbeiten] 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.
type TMyList = class private FFeld: array of Integer; public constructor Create; procedure Free; 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;
[Bearbeiten] Implementation
Im Constructor muss dem Feld Speicher zugewiesen werden, ohne diesen jedoch bereits mit Daten zu füllen:
constructor TMyList.Create; begin inherited; SetLength(FFeld, 0); end;
Die Methode Free sollte auf gleiche Weise den Speicher wieder freigeben:
procedure TMyList.Free; 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.
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.
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.
procedure TMyList.Clear; begin SetLength(FFeld, 0); end;
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;
[Bearbeiten] 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:
public property Items[I: Integer]: Integer read GetValue write SetValue; default;
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 end;
[Bearbeiten] 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  |
