数据结构中链表之VisualBasic实现

1 引言

《数据结构》在计算机科学中是一门综合性的专业基础课。数据结构的研究不仅涉及到计算机硬件 (特别是编码理论、存储装置和存取方法等) 的研究范围, 而且和计算机软件的研究有着更密切的关系, 无论是编译程序还是操作系统, 都涉及到数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据, 以便查找和存取数据元素更为方便。因此, 可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程, 在计算机科学中, 数据结构不仅是一般程序设计 (特别是非数值计算的程序设计) 的基础, 而且是设计和实现编译程序、操作系统、数据系统及其它系统程序和大型应用程序的重要基础。只有学好了《数据结构》这门课, 才能在今后的计算机专业课程的学习中游刃有余。但是由于学习《数据结构》这门课程先修课程为C语言程序设计, 而基于有些好学者只学习了Visual Basic程序设计的, 缺少了描述数据结构中的必不可缺少的指针类型。故本文讨论在Visual Basic中实现链表这样的数据结构的两种方法。

2 数组和自定义数据类型实现链表

2.2 定义链表

所谓链表就是用一组任意的存储单元存储线性表的若干个数据元素。首先, 链表是由若干个 (假定为10个) 数据元素组成, 故可以通过Visual Basic中数组来表示整个链表。其次, 为了能表示每个数据元素本身的信息以及其与后继元素之间的逻辑关系, 通常用结点来表示数据元素, 其中结点主要包括两个域:存放数据元素信息的数据域 (Data) 和存放其直接后继元素存储位置的指针域 (next) 。Visual Basic中的自定义数据类型可以包括多个互相关联的不同数据类型的元素。所以链表中的结点可以通过字定义数据类型来完成。

首先是在标准模块中定义一个名为LNode的自定义数据类型:

Public Type LNode'链表的结点类型

data As Integer'存放元素的值 (作数据域使用)

next As Integer'存放紧接本元素后的元素的地址 (作指针域使用)

End Type

其次在窗体模块中定义一个固定大小的数组, 类型就是我们刚刚定义的LNode类型:

Dim a (10) as LNode'定义含有10个数据元素的链表

因为Visual Basic没有指针, 故Next域中所存放的是该数据元素后继元素在数组中的下标值。通过用自定义数据类型queue声明数组a (10) 和对变量next作专门规定, 可以发现, 我们能将一片连续的线性分布的数据存放在内存中非线性的不连续的地址空间里。

2.2 链表的初始化

代码如下:

数据元素的信息

a (i) .next=i+1'数据元素后继元素的下标值

如果再加上语句a (10) .next=0就构成了一个单向循环链表。通过改变N e x t域的下标值可以对链表进行插入和删除运算。

3 定义对象变量实现链表

Visual Basic中的对象变量有类似指针的功能, 故实现链表这样的数据结构也可以使用对象变量来完成。

3.1 定义链表的结点

实现链表的关键是如何表达一个元素, 在VB中可用类模块实现:

添加一个类模块, 类名称为Node

在其中添加代码如:

Public pNext As node'指针域

Public data As Single'数据域

结点内存的分配和回收都是由类的构造器Class_Initialize () 过程, 类的析构Class_Termainate () 过程来完成。代码如下:

3.2 创建链表

首先在窗体的通用-声明段定义如下:

Option Explicit

Private pHead As Object'定义头结点

其次在某一控件的事件过程中代码如下:

如果再加上语句Set p.pNext=pHead就构成了一个单向循环链表。通过改变Next域的下标值可以对链表进行插入和删除运算。

4 结语

本文讨论在Visual Basic环境中用数组和自定义数据类型以及定义对象变量这两种来实现数据结构之链表中结点的定义和创建链表。对于链表中的插入元素和删除元素等基本操作都可以在此基础上通过修改结点中的next域的下标值来实现。

摘要：本文讨论了在VisualBasic编程中利用数组和自定义数据类型以及定义对象变量两种方法构造数据结构中链表的方法。

关键词：数据结构,Visual Basic,链表

参考文献

[1] 　严蔚敏, 吴伟民.数据结构, 清华大学出版社, 2005, 10:27￣33.

[2] 　龚沛曾, 陆蔚民, 杨志强.Visual　Basic程序设计简明教程 (第二版) , 高等教育出版社, 2004, 5:114￣117.

[3] 　沃得工作室.Visual　Basic中文版开发与应用技巧, 人民邮电出版社.

[4] 　谭浩强.C程序设计 (第三版) .清华大学出版社, 2005, 7.