为便于理解数组的作用,我们引入数据项和指针项的概念,在数据项中存放数组中各元素的值,指针项中存放该值在数组中的位置,两者一一对应。指针的上限指向数组第一个元素的位置,下限指向最末一个元素的位置。数组中的元素在内存中是连续的线性的节点序列,这种线性的数据结构是应用最广泛,最简单的一种数据结构。 自定义数据类型(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定义的数组均可作为链表使用。 例 用queue将a(10)初始化为一个单向链接表: For i = 0 To 9 a( i ).next = i + 1 ’ i + 1为下一个元素的指针 a( i ).data=10*rnd Next i
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实现了当队满时在链表中插入一个节点的操作。在链表中删除一个节点的操作与此类似。 例:队列的进队及出队操作,利用上例定义的循环链表并假设已按例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