VB6数据结构之线性表(二)（数据结构线性表基本操作全代码）

今天我们继续线性表存储结构的链表。链表分为单链表与双链表。

单链表的存储表示：

线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。

我们知道线性表的顺序存储结构由于使用连续存储单位存储数据元素，因此存储结构和逻辑结构是一致的。对线性表的链式存储结构来说，为了反映数据元素之间的逻辑关系，在存储每个数据元素（data）的同时，还必须存储反映数据元素之间逻辑关系的地址信息，这个地址信息称为指针(next)。这两部分信息组成了元素的存储映象，称为结点，它包括两个域：data和next。

其中：data是数据域，用来存放结点的值（数据元素）；next是指针域，用来存放结点的直接后继的地址。

链式存储结构的特点如下：

(1)线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致。

(2)在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。

用VB6实现的单链表的操作方法：

Publie Head As Node'头结点

Publlc length As Integer'记录表中元素个数

1.初始化链表

Private sub Class_Initia1ize()

initList

End Sub

2.销毁链表

Sub clearList()

Dim p Ae Node，q As Node

P = Head.NextNode

while Not p Is Nothing '若不为空链表,进行以下操作

set q = p

Set p = p.NextNode '将表头下一个结点内容置为表头

set q = Nothing

Wend

lenqth = 0

End Sub

3.清空链表

Private Sub Class Terminate()

destroyList

EndSub

sub destroyList()

Dim p As Node

while Not Head Is Nothing '若不为空链表，进行以下操作

Set p = Head

set Head = Head.NextNode '将表头下一个结点内容置为表头

Set p = Nothing

wend

End Sub

4.求链表的长度

Function getLength() As Integer

getLength= 1ength

End Function

5.判断表是否为空

Funetion isEmpty() As Boolean

isEmpty=Head.NextNode Is Nothing

End Function

6.返回链表工中第i个数据元素的内容,1<=i<=len。

Function getElem (i%)

dim j%,ret,p as Node

ret=Null

if i>=1 and i<=getLength() then

set p=Head.NextNode

for j=1 to i-1

set p=p.NextNode

next j

ret=p.data

end if

getElem=ret

End Function

7.在链表中检索值为e 的数据元素

Function locateElem (e)'返回值: 0---表示不存在e。其他---e在表中的位置

Dim i%，j%,p as Node

If Not isEmpty () Then

Set p = Head.NextNode

Do while Not p Is Nothing

If e = p.data Then Exit Do

Set p = p.NextNode

i = i + 1

Loop

'寻找满足条件的结点

If 1 <= length Then j = i

End If

1ocateElem = j

End Function

8.返回链表中结点e的直接前驱结点

Function priorElem (e)'返回值: Null---表示不存在直接前驱结点或为空表。其他---e在表中的直接前驱结点

Dim p As Node, q As Node, ret

ret = Null

If Not isEmpty() Then

Set p = Head.NextNode

set q = Head

'检调第1个结点

Do While Not p Is Nothing

If e = p.data Then Exit Do

Set q = p

Set p = p.NextNode

Loop

IE Not p Is Nothing Then ret = q.data

End If

priorsElem = ret

End Function

9.返回链表L中结点e的直接后继结点

Function nextElem (e) '返回值:Null---表示不存在直接后继结点或为空表。 其它---e在表中的直接后继结点

Dim p Ae Node，ret

ret = Null

If Not isEmpty() Then

Set p = Head.NextNode

'检测第1个结点

Do While Not p Is nothing

If e = p.data Then Exit Do

Set p = p.NextNode

Loop

If Not p Is Nothing Then

Set p = p.NextNode

If Not p Is nothing Then ret e p.data

end Tf

End If

nextElem = ret

End Function

10.在链表中第i个数据元素之前插入数据元素e

Function insertList (i%, e) Ae Integer

dim j%,ret%

dim p as node,s as node

ret=0

if i>=1 and i<=getLength() + 1 then

set s=new node

s.data = e

set p=head

for j=1 to i-1

set p=p.NextNode

next j

'寻找第i-1个节点

set s.NextNode = p.NextNode

set p.nextnode = s

length=length + 1

ret=1

end if

insertList=st

end function

11.将链表中第i个数据元素删除

Function deleteList（i%) Ae Integer

dim j%,ret%

dim p as node,s as node

ret=0

if i>=1 and i<=getLength() then

set p=head

for j=1 to i-1

set p=p.nextnode

next j

'寻找第i-1个节点

set s=p.nextnode

set p.nextnode=s.nextnode

set s=nothing

length=length-1

ret=1

end if

deleteList=ret

end function

循环链表的表示:

表中最后一个结点的指针指向头结点,使链表构成环状。其特点是:从表中任一结点出发都可以找到表中其他结点，能提高查找效率。

循环单链表操作与单链表基本一致，只是循环条件有所不同。

在单链表中通过比较p.NextNode=Nothing来判断指针是否指向最后一个结点，而在循环链表中则通过p.NextNode=Head 来判断指针是否指向最后一个结点。

以下列出几个稍微有点差异的操作，其他操作同单链表。

1.初始化循环单链表

初始化循环单链表，实际上是生成一个带头结点的空表。

Private sub Clase Initialize（）

initList

End Sub

Sub initList()

Dim p As Node

Set p = New Node

p.data = Empty

Set p.NextNode

set Head = P

1ength = 0

End Sub

2判断线性表是否为空

Function isEmpty() As Boolean

Dim ret As Boolean

ret=False

if Head.NextNode=Head then ret=True

isEmpty = ret

End Function

3.在循环单链表中查找值为e的数据元素

Function locateElem(e) '返回值: 0---表示不存在e 其他---e在表中的位置

Dim i%，j%

Dim p As Node

j = 0

i=1

If Not isEmpty() Then

Set p = Head.HextNode

Do While (p <>Head)

If e = p.data Then Exit Do

Set p = p.NextNode

i=i + 1

Loop

'寻找满足条件的结点

If i <- length Then j = 1

End If

1ocateElem = j

End Function

4返回循环链表中结点e的直接前驱结点

Function priorElem(e)

Dim p As Node, q As Node,ret

ret = Null

If Not isEmpty() Then

Set p = Head.HextNode

set q = Head

'检测第1个结点

Do While ( p <>Head)

If e = p.data Then exit Do

Set q = p

Set p= p.Nextnode

Loop

If Not p Is nothing Then ret = q.data

End If

priorElem = ret

End Function

5返回循环链表中结点e的直接后继

Function nextElem(e)

Dim p As Node,ret

ret = null

If Not isEmpty() Then

Set p = Head.HextNode

'检测第1个结点

Do While p<>Head

If e = p.data Then Exit Do

Set p = p.NextNode

Loop

If not p Is nothing Then

Set p = p.NextNode

If not p Is nothing Then ret = p.data

End If

End If

nextElem = ret

End Function

双向循环链表的表示和基本操作的实现

在前面所讲的链表存储结构的结点中只包含一个指向直接后继的指针，在这种情况下，从某结点出发只能顺着指针方向寻找其他结点。若要寻找某结点的直接前驱，则必须从头结点开始遍历链表。因此单链表(包括循环单链表)并不适用于经常访问前驱结点的情况。

当在实际应用中需要频繁地同时访问前驱和后继结点时，应使用双向循环链表。双向循环链表就是每个结点有两个指针域。一个指向后继结点，另一个指向前驱结点。

用VB6实现双向循环链表

定义结点类模块Node2.cls：

public data

Public NextNede As Node2

Public PriorNode As Node2

其次，定义双向链表类模块List2.cls，内容为:

Public Head As Node2'头结点

pub1ic length As Integer'记录表中元素个数

双向循环链表的基本操作的实现和前面循环单链表操作的实现基本类似。以下仅说明双向循环链表的插人操作和删除操作。

假定指针s为指向待插入结点，指针p指向插入位置，即s指向结点插入到p所指向结点后，作为其直接后继。步骤如下：

第一步: set s.NextNode=p.NextNode

第二步: set s.PriorNode=p

第三步: set p.NextNode.PriorNode=s

第国步: set p.NextNode=s

假定指针p指向待删除结点。步骤如下：

第一步:.set q=p.PiorNode

第二步: set q.NextNode=p.NextNode

第三补: set p.NextNode.PriorNode=q

第四步: set p=Nothing

链表的应用

若有两个集合A和B，分别用两个线性表LA和LB表示，即线性表中的数据元素部为集合中的成员。现要求一个新的集合A=AUB。假定A={a，b，c}，B=A={b，d}，则A=AUB={a，b，c，d}。现使用单链表来存储集合。

基本思路:依次从线性表LB取结点，判断所取结点对应元素在线性表LA中是否存在，若不存在则插人到线性表 LA中。程序如下:

Sub union (LA as List, LB as List)

Dim lenA%，1enB%,i%

求线性表的长度

1enA = LA.getLength()

1enB = LB.getLength()

for i = 1 to lenB

e=LB.GetElem (i)

if LA.LocateElem (e) <>0 then

lenA=lenA+1

LA.InsertList lenA, e

End if

'LA中不存在和e相同的数据元素。则插入

Next i

End Sub