环环相扣谈链表(上)
软件世界
问：小博士，我在用顺序结构编程的时候，常常碰到要对大量数据进行删除或添加的情况。有时只为增加一个数据，就要挪动顺序结构中的大量数据，有没有什么数据结构能解决这个问题呢？
小博士：数据结构的种类非常多，除了前面介绍的数组外，还有线性表、栈和队列、树和图等，这些结构在解决特定问题时显得关键而有趣。你提出的问题，也有专门的数据结构能进行解决，那就是链表。
链表
大家都见过自行车，链表就好似日常生活中的自行车链条，环环相扣。要建立一个链表，必须首先确定组成链表的项目：节点和指针。节点用于存放数据，就好似自行车的链扣。指针用于指向节点，就好似自行车的链条。由于它的结构有上述特征，所以在删除或增加一个节点数据时，只用改变相应的指针，而不用移动大量的数据，为我们带来了方便。要想用好链表，先要构建好链表。很大的下面，我们来看看利用VB如何构建链表。
(一)链扣──节点的建立
我们可以通过“工程”菜单中的“添加类模块”来建立一个名称为Node的节点，它是一个类模块，它包含两部分内容：
1.节点的内容，就是一个数值信息。
Public X As Integer
2.后续节点信息,通过它可对整个表中的节点进行链接，也即指针。
Public NextNode As Node
(二)链条──指向节点的指针
有了上面的Node节点类，也就有了组成链表的基本单位，可以构造自己的链表了。将链表的信息封装起来，组成一个新的类模块，名称为List。
首先在窗体上加上一个文本框，用来放链表的内容，然后通过“工程”菜单中的“添加类模块”来建立一个名称为List类模块。因为链表数据结构的建立是为了方便我们使用的，为了保证它在操作过程中的完整性，我们需要做如下工作：
1.定义表头和表尾
Public ListHead As Node
Public ListTail As Node
2.链表信息初始化
Private Sub Class_Initialize()
Set ListHead = Nothing
Set ListTail = Nothing
End Sub
3.建立新节点
Sub MakeNewNode(n1 As Integer, n2 As Integer)
Dim n As Node
Set n = New Node
n.X = n1
If ListHead Is Nothing Then
Set ListHead = n
Else
Set ListTail.NextNode = n
End If
Set ListTail = n
Set ListTail.NextNode = Nothing
End Sub
4.显示链表信息，可通过下面的方法实现
通过头指针和节点建立联系，将指针信息不断修改后移，在实现节点遍历的同时显示其中的内容。
Sub DisplayList()
Dim n As Node
Set n = ListHead
While Not n Is Nothing
Form1.Text1.Text = Form1.Text1.Text + “X:” + Str(n.X) + vbCr + vbLf
Set n = n.NextNode
Wend
End Sub
5.清空链表内容，删除节点信息
Sub ClearList() '清空链表
Dim n As Node
While Not ListHead Is Nothing
Set n = ListHead
Set ListHead = ListHead.NextNode
Set n = Nothing
Wend
End Sub
6.获取当前链表第一个节点信息，并将该节点清空
Sub GetNode(column As Integer) '取节点
Dim n As Node
If Not ListHead Is Nothing Then
Set n = ListHead
column = n.X
Set ListHead = ListHead.NextNode
If ListHead Is Nothing Then Set ListTa
il = Nothing
Set n = Nothing
End If
End Sub
7.测试链表是空表还是非空表
Function HasNodes() As Boolean
HasNodes = Not ListHead Is Nothing
End Function
我们先设置上面的几个基本的属性，为后面应用链表做好准备工作。
小结
指针和节点，就像链扣和链条，组成了有趣的链表。但如何在应用中体现出它环环相扣的特点呢？我们将在下期利用链表编程中为大家做进一步的讲解。