Tutorial

Baumstrukturen in FreeBASIC

von

Seite 2 von 7

Bevor wir beginnen, möchte ich kurz auf die Linked List selbst eingehen. Dies erleichtert (so hoffe ich) das Verständnis der der hier vorgestellten Strukturierung des Programms bzw. primär des UDTs (User Defined Type).
Fangen wir mit einem einfachen Prinzip an.
Wir möchten zuerst einmal 1 Byte Daten abspeichern. Hierfür erzeugen wir eine Variable vom Typ UByte:

Dim Var1 as UByte

Möchten wir noch ein Byte abspeichern, müssen wir eine weitere Variable deklarieren.

Dim Var1 as UByte

Dim Var2 as UByte

Dim Var3 as UByte

'...

... usw. usw.

Das Problem an dieser Vorgehensweise ist schnell erkannt. Für jeden neuen Wert muss eine neue Variable erzeugt werden, indem sie im Quelltext ausdrücklich deklariert, also benannt wird. Diese Art Daten abzuspeichern ist dadurch nicht geeignet, um eine unbekannte Anzahl von Daten zu verwalten. Eine Alternative wäre die Verwendung eines Arrays:

Dim Var() as UByte

Der Vorteil eines Array ist seine dynamische Anpassungsfähigkeit. Es ist möglich, die Größe des Array zur Laufzeit zu ändern und somit die Anzahl der Variablen, wohingegen dies mit einer statischen Variable nicht möglich ist. Der folgende Quelltext zeigt, wie sich ein Array im Nachhinein vergrößern lässt:

Dim Var() as UByte

Redim Var(10) as UByte

'...

Redim Var(100) as UByte

'...

Redim Var(1000) as UByte

'...

An sich ist dieses Vorgehen, also die Nutzung eines Arrays, sehr hilfreich und durchaus schnell. Der Zugriff auf die einzelnen Variablen erfolgt über einen numerischen Index. Aus speichertechnischer Sicht ist diese Zugriffsmethode sehr günstig.

Sehen wir uns die Zugriffstechnik einmal genauer an. Wir also haben einen Speicher. Dieser Speicher sei 20 Bytes gross.
[ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ]

Erzeugen wir ein Array mit 10 Einträgen, ist dessen erstes Element beispielsweise an 2. Stelle im Speicher platziert. Ein Speicher beginnt immer mit der Adresse 0!
[ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ]

Diese Position im Speicher wird auch Basisadresse genannt. Um nun auf das 2. Element im Array zugreifen zu können, wird zur Basisadresse ein Offset addiert, das sich als das Produkt der Faktoren Index*GrößeEinesEinzelnenElements berechnet.
Beispielrechnung: Die Basisadresse sei 2 und die Indexnummer 1, multipliziert mir der Dateitypgröße (UByte = 1 Byte) ist dies 3. (Wichtig! Ein Array beginnt regulär mit der Indexnummer 0!)
3 wäre dann die reale Speicheradresse für das 2. Element.
[ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ]

Würden wir anstatt eines UBytes einen UInteger nutzen, wäre die neue Adresse:
2 (Basisadresse) + 1 (Indexnummer) * 4 (Dateitypgröße) = 6

Arrayindex 8 wäre folglich 2 + 8 * 1 = 10 bzw. mit einem UInteger: 2 + 8 * 4 = 34

[ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ]

Folglich belegt ein Array mit einer Grösse von 10 Elementen des Typs UByte nicht nur die Speicherstelle an der Basisadresse, sondern auch die darauf folgenden 9 Bytes:
[ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ]

Das erste Problem, das sich hier offenbart, ist die Position der Basisadresse bei Größenänderungen des Arrays. Angenommen wir erzeugen eine UShort-Variable (Sie verbraucht 2 Bytes.) und ein UByte-Array mit 10 Einträgen. Dadurch sind insgesamt 12 Bytes belegt. Der Speicher steht in unserem Beispiel komplett für uns zur Verfügung. Dadurch beginnt die UShort-Variable ab Adresse 0 und endet bei Adresse 1:
[ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ]

Das Array belegt 10 Bytes nach der UShort-Variable:
[ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ]

Deklarieren wir noch eine UInteger (4 Byte) Variable.
[ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ]

Verändern wir anschließend die Größe des Arrays - z. B. auf 11 Einträge, so haben wir das Problem, dass das 11. Element in den Speicherbereich der UInteger-Variable hinein laufen würde. Das Betriebssystem verhindert dies dadurch, dass es einen freien Speicherbereich sucht, der 11 Bytes am Stück aufnehmen kann. Das Problem bei dieser Speicherverlagerung ist, dass der dabei verschobene Speicher umkopiert (PRESERVE) werden muss, da sich die Basisadresse des Arrays ändert. Dies kostet immens Zeit und kann das Programm massiv ausbremsen, insbesondere wenn die Arraygröße immer wieder angehoben werden muss.

Ein ähnliches Problem entsteht beim Entfernen eines Eintrags aus dem Array. FreeBASIC besitzt keine Funktion, die das Entfernen eines Eintrags erleichtert. Dadurch müssen wir zuerst alle Daten, die nach dem zu löschenden Element noch kommen, um jeweils 1 Element nach vorne kopieren. Das kostet ebenfalls beträchtlich Zeit.

Angenommen wir erzeugen kein Array aus UByte-Variablen, sondern aus UInteger- oder ULongInt-Variablen (8 Byte) oder sogar aus eigenen UDTs mit komplexen Inhalten, die z.B. 50 Byte groß sein könnten. Die zuvor beschriebenen Kopiervorgänge dauern - auf 1000 Einträge oder mehr angewendet - sehr lange und gestalten die Manipulation der Datenmenge als sehr zeitraubend.

Eine Möglichkeit dieses Problem zu umgehen, ist eine Linked List, eine verkettete Liste. Hierfür wird ein UDT erzeugt, das die zu speichernde Information enthält.

Achtung! Die nun folgenden weiteren Quellcodes dienen ausschließlich dem einfacheren Verständnis und sind wegen syntaktischer Vereinfachungen unter Umständen nicht compilierbar!

Type Element_Type

    V_Data  as UInteger

End Type

Ein Array mit Variablen dieses UDTs sieht im Speicher genauso wie eine Array aus UInteger-Variablen aus.

Jetzt erzeugen wir ein Pointer auf ein solches UDT ...

Dim Var as Element_Type

...und holen uns die Basisadresse zu einem freien Speicherstück, das die Größe des benötigten Speichers aufnehmen kann.

Var = Allocate(SizeOf(Element_Type))

In unserem Fall ist Element_Type 4 Byte groß, da sich nur ein UInteger in diesem UDT befindet.

Nehmen wir im Folgenden an, der Speicher stünde voll zu unserer Verfügung. Dadurch würde die Basisadrese 0 sein. Der Speicher wird mit 4 Byte belegt.
[ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ]

Würde jetzt eine neue Variable benötigt, würde diese die nächsten Bytes belegen. Beispielsweise ein UShort-Wert mit 2 Bytes Länge:
[ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ]

Würden wir nun das Index-Prinzip mit einem Array anwenden, hätten wir erneut das Problem, dass Daten kopiert werden müssten.

Umgehen lässt sich dies, indem wir einfach in unser UDT eine weitere Variable einfügen. Diese Variable nutzen wir nun dafür, die Basisadresse eines weiteren Elements zu speichern.

Type Element_Type

    V_Next  as UInteger

    V_Data  as UInteger

End Type

Dadurch vergrößert sich zwar der belegte Speicher um weitere 4 Bytes, jedoch ist dies in der heutigen Zeit kaum ein Problem, wenn man andere Variablen nicht überdimensioniert und den Verbrauch mit Verstand berücksichtigt.
[ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ]

Die UShort liege nun mal im Bereich 8 bis 9:
[ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ]

Jetzt erzeugen wir ein 2tes UDT-Element. Die Adresse dieses neuen Elements wird jetzt jedoch nicht mehr in einer seperaten Variable gespeichert, sondern in die Variable V_Next des ersten Elements.

'Das UDT

Type Element_Type

    V_Next  as UInteger     'Basisadresse des nächsten Elements

    V_Data  as UInteger     'Die eigentlichen Daten

End Type



'Eine Variable, welche das erste Element speichert.

Dim Var as Element_Type



'Einen Speicherbereich mit der Größe von Element_Type vom Betriebssystem anfordern und dessen Basisadresse abspeichern

Var = Allocate(SizeOf(Element_Type))



'Noch ein neues Element erzeugen. Diesmal wird die Basisadresse in V_Next des ersten Elements gespeichert.

Var.V_Next = Allocate(SizeOf(Element_Type))

Im Speicher sieht es nun folgendermaßen aus:
Das erste Element:
[ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ]

Die UShort-Variable:
[ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ]

Das zweite Element:
[ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ]

Im ersten Element befinden sich 2 Variablen. Die erste enthält die Basisadresse auf das nächste (zweite) Element, die zweite Variable die eigentlichen Daten des Elements selbst.

Datenbereich für den Pointer (Zeiger) auf das nächste Element:
[ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ]

Datenbereich für die eigentlich zu speichernden Nutzdaten:
[ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ]

Natürlich ist der oben beschriebene Quellcode nicht ganz funktionsfähig. Das liegt im eigentlichen daran, dass der FreeBASIC-Compiler sehr genau überprüft, was wir zusammenprogrammieren, um uns vor unbeabsichtigten Fehlern zu schützen.
Ich habe jedoch absichtlich den Quellcode so formuliert, also ohne Berücksichtigung der Unterscheidung von Variablen, die Daten, und solchen, die Pointer speichern, formuliert, damit erkennbar ist, dass für einen Pointer ein UInteger Verwendung findet. Eine "Ptr" bzw. "Pointer" Angabe nach einem Datentyp (z.B. UInteger Ptr) weist darauf hin, dass es sich um einen Zeiger auf einen anderen Speicherbereich handelt. Darum passen wir den Quellcode nun an die Richtlinien von FreeBASIC an.

Achtung! Ab hier sind die Quellcodes wieder funktionsfähig.

'Das UDT

Type Element_Type

    V_Next  as Element_Type Ptr     'Basisadresse des nächsten Elements

    V_Data  as UInteger             'Die eigentlichen Daten

End Type



'Eine Variable, welche das erste Element speichert.

Dim Var as Element_Type Ptr



'Einen Speicherbereich mit der Größe von Element_Type vom Betriebssystem anfordern und dessen Basisadresse abspeichern

Var = Allocate(SizeOf(Element_Type))



'Noch ein neues Element erzeugen. Diesmal wird die Basisadresse in V_Next des ersten Elements gespeichert.

Var->V_Next = Allocate(SizeOf(Element_Type))

FreeBASIC kann mit Pointern ohne Weiteres umgehen (siehe Befehlsreferenzeintrag). Das ist nicht nur für uns eine große Erleichterung, sondern auch für den Compiler selbst sowie für eine IDE (Programmierumgebung).

Zurück zur Linked List, die wir gerade fertiggestellt haben. Denn viel mehr gibt es eigentlich nicht, das eine Linked List ausmacht.
Kapitelabschließend kann man sagen, das eine Linked List nichts anderes als eine Verkettete Liste (was auch der eigentlichen Übersetzung ins Deutsche entspricht) ist, die nichts anderes macht, als in jedem Element auf das nächste zu zeigen.

Im nächsten Kapitel geht es dann schon ans Eingemachte. Hier werden mehrere Pointer verwendet, die jeweils auf bestimmte andere Elemente in solch einer Liste zeigen. Als vorgezogenes Beispiel sei hier einmal V_Prev erwähnt, das nicht auf das nächste, sondern auf das vorherige Element zeigt.

Gehe zu Seite 1 2 3 4 5 6 7

Zusätzliche Informationen und Funktionen

Das Tutorial wurde am 01.07.2009 von ThePuppetMaster angelegt.
Die aktuellste Version wurde am 09.07.2009 von ThePuppetMaster gespeichert.

Bearbeiten

Versionen