Die Community zu .NET und Classic VB.
Menü

Zeiger in VB - Seite 4

 von 

Ein Stapel
Nächste Seite >>
Das Heap-Modul
<< Vorherige Seite

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

Listing 6

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

Listing 7

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

Listing 8

Zum Download des Beispielcodes.

Nächste Seite >>
Ein Stapel
<< Vorherige Seite
Das Heap-Modul