Buchempfehlung
Mikrocomputertechnik mit Controllern der Atmel AVR-RISC-Familie
Mikrocomputertechnik mit Controllern der Atmel AVR-RISC-Familie
Umfassend, aber leicht verständlich führt dieses Buch in die Programmierung von ATMEL AVR Mikrocontrollern ein. [Mehr Infos...]
FreeBASIC-Chat
Es sind Benutzer im FreeBASIC-Chat online.
(Stand:  )
FreeBASIC bei Twitter
Twitter FreeBASIC-Nachrichten jetzt auch über Twitter erhalten. Follow us!

Tutorial

Baumstrukturen in FreeBASIC

von MitgliedThePuppetMasterSeite 5 von 7

Der nächste Schritt beim Aufbau einer Baum-Struktur-Verwaltung ist das Erstellen einer Funktion, mit der Elemente hinzugefügt werden können.

Um weiterhin flexibel bleiben zu können, designen wir diesen Codeabschnitt als Funktion. Eine Funktion ermöglicht uns die Rückgabe von Werten oder Pointern. In diesem Fall nutzen wir die Rückgabe, um das neu erzeugte Element zurückgeben zu können. Das erleichtert später das Hinzufügen neuer und Verwalten der Elemente.
Damit das Hinzufügen unterschiedlicher Daten ebenfalls erleichert wird, gestalten wir die Parameter ebenfalls flexibel: Da jedes Element vom selben Typ ist, brauchen wir keine überladenen (Overload) Funktionen - zumindest momentan noch nicht. Aber das richtet sich dann an den eigentlichen Nutzer dieses Quellcodes.

Die ersten beiden Parameter sind Pointer auf 2 Element-UDTs. Diese werden hier nicht nur als Pointer (Ptr) übergeben, sondern zusätzlich auch ByRef, damit die Variablen, welche der Funktion später übergeben werden, auch unsere Änderungen beinhalten. Als nächstes müssen wir einen Typ angeben (V_Type), damit dem späteren Nutzer die Möglichkeit gegeben wird, unterschiedliche Dateninhalte (z.B. Strings, UByte, UInteger oder eigene UDTs) abzuspeichern. Der Nutzer hat nun die Möglichkeit, für jeden seiner zu speichernden Datentyp eine Kennungsnummer zu vergeben wie zum Beispiel für Strings die 1, für UInteger die 2, für UDT_1 die 3 oder für UDT_2 die 4. Dadurch kann der Nutzer später beim Abrufen des Elements heraufinden, zu welchem Datentyp er die abgerufenen Daten "casten" (explizites Type-Casting, siehe BefehlsreferenzeintragCAST) muss. Die nächste Variable ist ein Pointer auf den eigentlichen Speicherbereich. Dieser Speicherbereich wird vom Nutzer festgelegt (z.B. @MyUDTVariable). Dieser beinhaltet die zu speichernden Daten. Damit unsere Funktion auch weiß, wie groß diese Daten sind (SizeOf()), definieren wir zusätzlich noch eine V_DataSize Variable. Der Wert kann hier mithilfe von SizeOf(MyUDTVariable) übergeben werden.

Zusätzlich kommen natürlich noch die beiden Pointer hinzu, welche auf das Ursprungselement zeigen (quasi "Adam und Eva") und ein Pointer auf das Elternelement.
Wir übergeben hier beide Pointer auf "Adam und Eva", um zum einen überprüfen zu können, ob eine Liste bereits erzeugt wurde oder nicht, und zum anderen, um ein neues Element schneller an das Ende der Liste anhängen zu können. Man könnte dies auch anders machen, aber aufgrund des besseren Verständnisses habe ich die Pointer aufgeteilt. Aber das ist in diesem Tutorial erstmal nicht relevant.

Function LL_Add(ByRef V_List_F as Element_Type Ptr, ByRef V_List_L as Element_Type Ptr, V_Root as Element_Type Ptr, V_Parent as Element_Type Ptr, V_Type as UInteger, V_DataPtr as UInteger, V_DataSize as UInteger) as Element_Type Ptr
'...
End Function

Wird die Funktion LL_Add aufgerufen, muss sie zuerst prüfen, ob bereits Daten in der Linked List hinterlegt wurden. Das kann man durch die Prüfung des Wertes V_List_L machen. Ist deren Wert ungleich 0, dann hält diese Variable bereits einen Pointer.

'...
If V_List_L <> 0 Then     'Prüfen, ob bereits Elemente vorhanden sind.
    '...
Else
    '...
End If
'...

Wenn dem nicht so ist, müssen wir davon ausgehen, dass noch keine Liste vorhanden ist, und sie grundlegend erzeugen. Hierfür erstellen wir einen Speicherbereich mit CAllocate(). Wir nutzen hier absichtlich BefehlsreferenzeintragCAllocate und nicht BefehlsreferenzeintragAllocate, da die Funktion den erzeugten Speicherbereich mit 0 füllt. Das verhindert spätere Missverständnisse auf Pointer-Variablen in unserem Element_Type. Würden wir BefehlsreferenzeintragAllocate verwenden, ist es möglich, dass noch Daten im Speicher stehen, die zuvor von einem anderem Programm verwendet wurden. Das würde natürlich zu den genannten Missverständnissen führen.

Function LL_Add(ByRef V_List_F as Element_Type Ptr, ByRef V_List_L as Element_Type Ptr, V_Root as Element_Type Ptr, V_Parent as Element_Type Ptr, V_Type as UInteger, V_DataPtr as UInteger, V_DataSize as UInteger) as Element_Type Ptr
If V_List_L <> 0 Then
    '...
Else
    V_List_L = CAllocate(SizeOf(Element_Type))      'Ein Stückchen Speicher erzeugen mit der Länge von unserem Element_Type UDT
    V_List_F = V_List_L                             'Der Pointer auf diesen Speicherbereich wird zusätzlich auch als erstes Element definiert.
End If
'...
End Function

Da beim grundlegenden Erstellen der Linked List noch keine Elemente vorhanden sind, müssen wir nicht nur ein neues Element erzeugen, sondern diesen auch als erstes Element festlegen. Das wird dadurch bewerkstelligt, dass wir den Pointer einfach in die xxx_F Variable schreiben. F steht ja bekanntlich für "First" also "erstes" und L für "Last" bzw. "letztes".

Sollten jedoch bereits ein oder mehrere Elemente vorhanden sein, ist die Variable V_List_L ungleich 0, da sie ja bekanntlich den Pointer des zuletzt erzeugten Elements speichert. Aus diesem Grunde wird bei jedem neuem Element, das zu einer bereits bestehenden Liste hinzugefügt werden soll, einfach das V_Next im letzten Element verwendet. Nachdem das neue Element erzeugt wurde, muss in diesem der Pointer des vorherigen Elements untergebracht werden. Das ist nötig, damit man über jedes Element nach vorne und auch nach hinten wandern kann.

Function LL_Add(ByRef V_List_F as Element_Type Ptr, ByRef V_List_L as Element_Type Ptr, V_Root as Element_Type Ptr, V_Parent as Element_Type Ptr, V_Type as UInteger, V_DataPtr as UInteger, V_DataSize as UInteger) as Element_Type Ptr
If V_List_L <> 0 Then
    V_List_L->V_Next = CAllocate(SizeOf(Element_Type))    'Neues Element erzeugen.
    V_List_L->V_Next->V_Prev = V_List_L                   'Dem neuem Element den Pointer auf sein vorheriges Element mitteilen
    V_List_L = V_List_L->V_Next                          'Das neue Element als das letzte Element abspeichern.
Else
    '...
End If
'...
End Function

Jetzt fehlen nur noch die Pointer auf das Parent- (das Eltern Element) sowie auf das Ursprungselement (Root). Beide werden über die mitgelieferten Parameter der Funktion bereitgestellt. Auch diese beiden dienen der Navigation. V_Root dient vorallem der leichteren und schnelleren Navigation. Natürlich könnte man sich das V_Root auch sparen und sich stattdessen wieder mit dem V_Parent von Element zu Element hangeln, bis man am Ende angekommen ist.

Function LL_Add(ByRef V_List_F as Element_Type Ptr, ByRef V_List_L as Element_Type Ptr, V_Root as Element_Type Ptr, V_Parent as Element_Type Ptr, V_Type as UInteger, V_DataPtr as UInteger, V_DataSize as UInteger) as Element_Type Ptr
If V_List_L <> 0 Then
    '...
Else
    '...
End If
With *V_List_L
    .V_Parent   = V_Parent      'Pointer auf das Elternelement setzen
    .V_Root     = V_Root        'Pointer auf das Ursprungselement setzen.
    '...
End With
End Function

Damit wäre ein neues Element erzeugt und an die Liste angehängt. Zu guter Letzt muss noch Speicher reserviert werden, damit die eigentlichen Nutzdaten abgespeichert werden können. Zu erwähnen wäre hier im Vorfeld schon einmal, dass bei String-Daten darauf geachtet werden muss, dass es sich dabei selbst um einen UDT handelt und man nicht ohne Weiteres einen String abspeichern kann. Hierfür wird später eine "Überlade-Funktion" geschrieben, welche diese Nutzdaten abspeichern kann.

Aber zuerst einmal speichern wir die übergebenen Daten in das neu erzeugte Element ab. Das neue Element ist am Ende der Linked List, folglich auch über V_List_L, ansprechbar.

Function LL_Add(ByRef V_List_F as Element_Type Ptr, ByRef V_List_L as Element_Type Ptr, V_Root as Element_Type Ptr, V_Parent as Element_Type Ptr, V_Type as UInteger, V_DataPtr as UInteger, V_DataSize as UInteger) as Element_Type Ptr
'...
With *V_List_L
    '...
    .V_Type = V_Type                            'Datentyp abspeichern
    .V_Size = V_DataSize                        'Datengröße abspeichern
    .V_Data = CAllocate(SizeOf(V_DataSize))     'Datenspeicher erzeugen
    '...
End With
End Function

Jetzt müssen wir nur noch die Daten kopieren. Hierfür eignet sich eine "movememory"-Funktion wie sie von Windows (noch) und von Linux bereitgestellt wird. Diese Funktion hat viele Vorteile, jedoch einen kleinen Nachteil. Erstens ist diese Funktion nicht auf jedem "Target" (Windows, Linux, XBox, DOS) verfügbar und muss dementsprechend für jedes System gewählt werden. Auf jedem System hat sie möglicherweise einen anderen Namen und benötigt daher womöglich unterschiedliche Parameter. Ein weiterer Nachteil ist, dass diese Funktion wohl in Windows bald durch eine andere ersetzt wird, da sie sicherheitstechnisch viele Probleme verursachen kann.

Daher werden wird uns hier auf eine einfache und wohl auch nicht wirklich schnelle Art der Datenkopierung beschränken (zumal es sowieso nur ein Beispiel ist).

Function LL_Add(ByRef V_List_F as Element_Type Ptr, ByRef V_List_L as Element_Type Ptr, V_Root as Element_Type Ptr, V_Parent as Element_Type Ptr, V_Type as UInteger, V_DataPtr as UInteger, V_DataSize as UInteger) as Element_Type Ptr
'...
With *V_List_L
    '...
    For X as UInteger = 1 To V_DataSize         'Byte für Byte durchgehen
        *(.V_Data[X - 1]) = *(V_Data[X - 1])    'und kopieren
    Next
End With
Return V_List_L                                 'Am Ende das neue Element zurückgeben
End Function

Die fertige Funktion sieht anschließend wie folgt aus:

Function LL_Add(ByRef V_List_F as Element_Type Ptr, ByRef V_List_L as Element_Type Ptr, V_Root as Element_Type Ptr, V_Parent as Element_Type Ptr, V_Type as UInteger, V_DataPtr as UInteger, V_DataSize as UInteger) as Element_Type Ptr
If V_List_L <> 0 Then
    V_List_L->V_Next = CAllocate(SizeOf(Element_Type))
    V_List_L->V_Next->V_Prev = V_List_L
    V_List_L = V_List_L->V_Next
Else
    V_List_L = CAllocate(SizeOf(Element_Type))
    V_List_F = V_List_L
End If
With *V_List_L
    .V_Parent   = V_Parent
    .V_Root     = V_Root
    .V_Type = V_Type
    .V_Size = V_DataSize
    .V_Data = CAllocate(SizeOf(V_DataSize))
    For X as UInteger = 1 To V_DataSize
        *(.V_Data[X - 1]) = *(V_Data[X - 1])
    Next
End With
Return V_List_L
End Function

Diese Funktion ist geeignet, um neue Elemente an eine Liste anzuhängen. Sie kann jedoch keine Elemente an beliebiger Position einfügen! Hierfür kann man die Funktion passend umschreiben oder aber eine separate Funktion entwickeln, welche ein Element verschiebt. Dies kostet zwar etwas Zeit, aber es handelt sich dabei nur um Bruchteile einer Sekunde. Kommt es wirklich auf jeden Wimpernschlag bei der Programmausführung an, ist es sinnvoller, eine separate Funktion zu schreiben und die Verschiebefunktion zu vernachlässigen.





 

Gehe zu Seite Gehe zu Seite  1  2  3  4  5  6  7  
Zusätzliche Informationen und Funktionen
  Bearbeiten Bearbeiten  

  Versionen Versionen