在VisualBasic編程中運用數據結構
|
摘要：本文討論了在VB編程中利用數組和自定義數據類型構造鏈表、棧和隊列等數據結構的方法。
關鍵詞：Visual Basic，數據結構
1．引言
Basic語言擁有較高的普及率，同時在Windows操作系統中Visual Basic以功能強、代碼量小，容易上手和所見即所得的可視化界面贏得了廣大Basic程序編制者的交口稱贊。然而，在諸如數值計算、結構計算及項目管理系統的編程中如何構建數據結構，并設計出相應的算法，卻經常困擾著他們。實際上在VB中利用數組（尤其動態數組）和自定義數據類型（Type Statement）完全可以描述諸如鏈表、棧、隊列和二叉樹這樣的結構，并實現排序、查找等運算，且機制上也非常靈活。
2．鏈表、棧及隊列數據結構在VB編程中的實現
2．1數組和自定義數據類型所起的作用
為便于理解數組的作用，我們引入數據場和指針場的概念，在數據場中存放數組中各元素的值，指針場中存放該值在數組中的位置，兩者一一對應。指針的上限指向數組第一個元素的位置，下限指向最末一個元素的位置。數組中的元素在內存中是連續的線性的節點序列，這種線性的數據結構是應用最廣泛，最簡單的一種數據結構。
自定義數據類型（Type Statement）可以包含多個互相關聯的不同數據類型的元素，VB限定聲明一個自定義數據類型必須在模塊層（Module Level）進行。聲明了一個自定義數據類型后便可以定義一個那種類型的變量。
例1 用名為queue的自定義數據類型聲明一個固定大小的數組：
| Type queue data As Integer '用作數據場 next As Integer '用作指針場 End Type Const max=10 Dim a(10) As queue |
設a( i )為數組中的一個元素，該元素的指針指向數組a(10)第i+1個元素，其下標為i ，指針的值為i 。需要指出的是數據結構不同于數據類型，也不同于數據類型聲明的對象（變量）。數據結構不僅描述數據類型的數據對象，而且要描述數據對象各元素之間的各種運算。為了弄清自定義數據類型的作用，我們規定變量data存放元素的值（作數據場用），變量next存放緊接本元素后的元素的指針。通過用自定義數據類型queue聲明數組a(10)和對變量next作專門規定，可以發現，我們能將一片連續的線性分布的數據存放在內存中非線性的不連續的地址空間里，卻不影響我們對其進行線性的運算操作。
像這種利用指針把各個元素鏈接起來的結構被稱為鏈表，類似例1定義的數組均可作為鏈表使用。
例2 用queue將a(10)初始化為一個單向鏈接表：
| For i = 0 To 9 a( i ).next = i + 1 ' i + 1為下一個元素的指針 a( i ).data=10*rnd Next i |
如果再加上語句a(10).next = 0就構成了一個單向循環鏈表。通過改變指針的指向可以對鏈表進行插入和刪除運算。
圖一、循環鏈接隊列示意圖
2．2棧和隊列
棧是一種數據只能由一端出入如彈匣的數據結構。在Visual Basic程序設計中，棧可以用來實現遞歸作用；或者是將數組和鏈表中因刪除而空閑的資源回收利用，避免出現一邊是資源空閑，一邊數組或鏈表長度不斷增長的尷尬局面。棧可以用一維數組或鏈表作存儲結構。用數組來實現既容易又方便，此時用指針變量Top1指向數組結點，每次有元素進棧棧頂指針top1=top1+1，a(top1).data= 10*rnd，每次有元素出棧top1=top1-1，b= a(top1).data 。當top1=0棧空，top1等于數組上限時棧滿。
與棧的在一頭進出方式不同，隊列是先進先出的數據結構，隊列也可以用一維數組或鏈表作存儲結構。隊運算中要使用兩個指向隊頭和隊尾的指針變量top1、bottom，最后進隊元素的指針等于隊頭指針top1，隊中最先進隊元素的指針等于隊尾指針bottom，當top1=bottom時隊空，初始條件為top1=bottom=0，當top1+1=bottom（數組）或a(top1).next=bottom（鏈表）時隊滿。有元素進隊時top1=top1+1（數組）或top1=a(top1).next（鏈表）；有元素出隊時bottom=bottom+1（數組）或bottom = a(bottom).next（鏈表）。
使用固定大小的數組總會遇到棧滿或隊滿的情形，我們可以使用動態數組來避免，動態數組是Visual Basic靈活性、便捷性的重要特征，它可以有效地管理內存。在例3中還通過引入變量linshi實現了當隊滿時在鏈表中插入一個節點的操作。在鏈表中刪除一個節點的操作與此類似。
例3隊列的進隊及出隊操作，利用例1定義的循環鏈表并假設已按例2進行了初始化。
| Dim top1 As integer'定義指向隊頭的指針變量 Dim bottom As integer'定義指向隊尾的指針變量 Dim linshi '變量 Public Function removequeue(a1 As Integer) '出隊函數 If bottom = top1 Then 'bottom = top1隊空 Debug.Print "隊空" top1 = 0: bottom = 0 Else bottom = a(bottom).next 'bottom指針后移，為元素出隊作準備 j = a(bottom).data '元素a1出隊 Debug.Print "出隊,b, j", bottom, j End If End Function Public Function insertqueue(ByVal a1 As Integer) '進隊函數 If a(top1).next = bottom Then 'a(top1).next = bottom隊滿 max=max+1 Redim Preserve a(max) as queue linshi = a(top1).next '隊滿，準備插入新節點 a(top1).next = max '插入新節點的指針 top1 = max 'top1指針指向新位置，為新元素a1進隊作準備 a(top1).next = linshi '新節點插入結束 a(top1).data = a1 '新元素a1進隊 Else top1 = a(top1).next '隊不滿，top1指針后移，新元素a1準備進隊 a(top1).data = a1 '新元素a1進隊 Debug.Print "進隊,t,i", top1, a(top1).data End If End Function |