Zeiger in VB - Seite 4
von Konrad Rudolph
Eine Warteschlange
Datenstruktur
Damit eine Warteschlange funktioniert, müssen wir einen neuen Datentyp konzipieren, das ListItem. Es ist folgendermaßen definiert:
Type ListItem Data As String Prev_ As Long Next_ As Long End Type
Data enthält die Daten des Listeneintrags. Der Typ dieses Mitglieds kann variieren. Prev_ und Next_ sind Zeiger auf das vorhergehende und nachfolgende Element in der Liste. Hier müssen Zeiger verwendet werden, denn wenn wir diese Mitglieder als Listeinträge definieren würden, dann würde für sie neuer Speicher im RAM reserviert werden, anstatt auf den selben Speicher zu zeigen wie das tatsächliche Element. Wenn wir nun den Datentyp unseres Heaps anpassen, können wir unsere Listenklasse schreiben, die lediglich als Hülle agiert, damit wir unsere Liste bequem verwenden können.
Der Code
' Queue.cls Option Explicit Private m_First As Long Private m_Last As Long Private m_Count As Long '---------------------------------------------------- Private Sub Class_Terminate() Call Clear End Sub '---------------------------------------------------- Public Sub Clear() Dim pIter As Long Do While m_First pIter = m_First m_First = Heap(m_First).Seg.Next_ Call Free(pIter) Loop m_Last = 0 m_Count = 0 End Sub Public Sub Push(Item As String) If m_Count = 0 Then m_First = Alloc() Heap(m_First).Seg.Data = Item m_Last = m_First Else Dim pTmp As Long pTmp = Alloc() Heap(pTmp).Seg.Data = Item Heap(m_Last).Seg.Next_ = pTmp Heap(pTmp).Seg.Prev_ = m_Last m_Last = pTmp End If m_Count = m_Count + 1 End Sub Public Function Pop() As String If m_Count > 0 Then Pop = Heap(m_First).Seg.Data Dim pTmp As Long pTmp = m_First m_First = Heap(m_First).Seg.Next_ Call Free(pTmp) m_Count = m_Count - 1 End If End Function Public Property Get Peek() As String If m_Count > 0 Then _ Peek = Heap(m_First).Seg.Data End Property Public Property Get Size() As Long Size = m_Count End Property Public Function Clone() As Queue Set Clone = New Queue Dim pIter As Long pIter = m_First Do While pIter Call Clone.Push(Heap(pIter).Seg.Data) pIter = Heap(pIter).Seg.Next_ Loop End Function
Zur Funktionsweise: Mit der Funktion Push() wird ein Wert ans Ende der Kette angehängt. Wir beziehen uns daher auf den Wert m_Last. Wenn noch kein Wert im Container enthalten ist, wird zuerst ein neuer Zeiger für m_Last erstellt. Um dem Speichersegment hinter m_Last einen Wert zuzuweisen, schreiben wir Heap(m_Last).Seg.Data = Item. Nun wird der Zeiger m_First auf m_Last gesetzt.
Falls bereits ein Wert im Container vorhanden war, reservieren wir zunächst einen neuen Speicherplatz über den Zeiger pTmp und weisen ihm den neuen Wert zu. Dann hängen wir den Zeiger in unsere Kette ein wie ein neues Kettenglied, indem wir die Zeiger Next_ und Prev_ entsprechend auf pTmp und m_Last setzen. Zu guter letzt rücken wir m_Last auf pTmp vor.
Das Entfernen von Werten erfolgt im Prinzip genau umgekehrt, diesmal beziehen wir uns auf m_First statt m_Last. Dann wird m_First um ein Element vorgerückt und per m_First der Speicher freigegeben.
Die Prozeduren Clear() und Clone() verwenden eine Hilfsvariable pIter, um alle Elemente der Liste aufzuzählen (= iterieren, daher heißt die Variable auch "Iterator"). Dank Zeigern kein Problem. Ohne Zeiger ist diese besondere Programmiertechnik nicht möglich.
Diese Klasse implementiert übrigens mehr oder weniger eine Quasi-Standard-Schnittstelle für Containerklassen: Es gibt eine Funktion Push() um Elemente hinzuzufügen, eine Funktion Pop() um sie wieder zu entfernen, außerdem eine Eigenschaft Peek, die den ersten Wert ausgibt, ohne ihn jedoch aus dem Container zu entfernen. Dann ist da noch die Eigenschaft Size, um die Größe des Behälters zu bestimmen und zu guter Letzt eine Funktion Clone(), um einen neuen Behälter gleichen Inhalts zu erstellen. Clear() leert den Behälter.
In C++ sind solche Standard-Schnittstellen weit mehr verbreitet als in VB, da in C++ sehr viel mehr mit Containern gearbeitet wird. Aber eine gewisse Standardisierung kann auch in VB nicht schaden.
Funktionsbeispiel
Ein Beispiel sagt mehr als tausend Worte. Folgendes Beispiel zeigt, wie man die Listenklasse verwendet:
Sub Main() Call SetHeapSize(10) Dim MyList As List Set MyList = New List Call MyList.Push("Hello, ") Call MyList.Push("brave ") Call MyList.Push("new ") Call MyList.Push("World!") Do While MyList.Size > 0 Debug.Print MyList.Pop(); Loop End Sub
Zum Download des Beispielcodes.