摘要:本文讨论了在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就构成了一个单向循环链表。通过改变指针的指向可以对链表进行插入和删除运算。
图一、循环链接队列示意图