VB6数据结构之线性表(一)（数据结构线性表程序）

线性表的含义及基本操作

一、线性表的含义

线性表是由n（n≥0）个类型相同的数据元素组成的有限序列集合。线性表中数据元素的个数被称为线性表的长度，当n=0时，线性表为空，又称为空线性表。一个非空线性表具有以下特征：

（1）有限序列集合中必存在唯一的一个“第一元素”；

（2）有限序列集合中必存在唯一的一个“最后元素”

（3）有限序列集合中除最后元素之外，均有唯一的后继；

（4）有限序列集合中除第一元素之外，均有唯一的前驱。

线性表通常可表示成以下形式：

L=(a1,a2,a3,...,ai-1,ai,...an)

其中：L为线性表名称，一般用大写字母表示；ai为组成该线性表的数据元素，一般用小字母写表示(ai,i是下标，由于下标在网站上表示麻烦，所以直接打上数字表示）。

a1为线性表L的第一元素，an为线性表L的最后元素。对元素ai而言，ai-1为其直接前驱，ai+1为其直接后继。

线性表有顺序存储结构与链式存储结构之分。本篇先介绍顺序存储结构及应用。

举例说明：

1.L1=(1,2,3,4,5) ‘L1为数据元素类型为int（整型）的线性表。

2.L2=（“张三”，“李四”，“王五”) ‘L2为数据元素类型为string（字符串型）的线性表。

Public Type STUDENT

name as String*20

age as Integer

score as Float

End Type

stu1,stu2,stu3 as STUDENT

3.L3=（stu1, stu2,stu3) ‘L3为数据元素类型为结构类型的线性表。

二、线性表的基本操作描述

（1）初始化线性表L：InitList(L)

（2）销毁一个已存在的线性表L：DestroyList(L)

（3）清空一个已存在的线性表L：ClearList(L)

（4）求线性表L的长度(即元素个数)：getLength(L)

（5）判断一个已存在的线性表L是否为空：IsEmpty（L）

（6）获取一个已存在的线性表L中的某个数据元素内容（第i个元素的值，该值保存在e中，需要符合条件为：1≤i≤LengthList（L））：GetElem(L,i，e）

（7）检索值为e的数据元素（返回L中元素为e的结点所在位置）：LocateElem（L,e）

（8）返回线性表L中e的直接前驱元素：PriorElem(L,e）

（9）返回线性表L中e的直接后继元素：NextElem（L,e）

（10）在线性表L中插入一个数据元素（条件：1≤i≤LengthList（L））：ListInsert(L,i,e)

（11）删除线性表L中第i个数据元素（条件：1≤i≤LengthList（L））：ListDelete(L,i,e）

顺序存储结构

（1）顺序表的存储表示

线性表的顺序存储结构是指用一组连续的存储单元依次存储线性表中的每个数据元素，如图1所示。

其中，len为每个数据元素所占据的存储单元数目。

由于线性表中数据元素是同一类型，所占空间大小一样，所以相邻两个数据元素的存储位置关系如下：

L（ai+1）=L（ai）+len。其中i，i+1是元素下标。

由此可知L中任意一个元素的存储位置为：

L（ai）=L（a1）+（i-1）len。其中1，i是元素下标。

用VB6描述一个顺序存储结构的类型如下：

Public Const MaxSize as Integer=5 '此处L大小为5

Public Type SeqList

Data(1 To MaxSize) As Variant

Last As Integer

End Type

用VB6描述一个顺序表的基本操作的实现

1.初始化线性表

Public Function InitSeqList(list As SeqList) As Integer

list.Last

End Function

2.销毁线性表

Public Function destroySeqList (list As SeqList) As Integer

list.Last =0

ReDim Data(1)

End Function

3.清空线性表

Public Function clearSeqList(list As SeqList) As Integer

list.Last =0

End Function

4.求线性表的长度

Public Function getLength(list As SeqList) As Integer

getLength = list.Last

End Function

5.判断线性表是否为空

Public Function isEmpty(list As SeqList) As Boolean '1 空，0 非空

If (list.Last = 0) Then

isEmpty = True

Else

isEmpty= False

End If

End Function

6.获取线性表L中的某个数据元素内容

Public Function getElem(list As SeqList,i as Integer) 'NULL不存在的值，0 非空值。

Dim ret

ret = Null

if (i >=1 And i <= LIST.last) Lhen ret = list.Data(i)

getElem = ret

End Function

7.检索值为e的数据元素

Public Function locateElem(list As SeqList, e) '0 不存在e值，其它 e在线性表中的位置

Dim i As Integer，ret As Integer

ret=0

For i=1 To list.Last

If (list.Data(i) = e Then Exit For

Next i

，寻找e所在位置

If (i <= list.Last) Then ret = i

locateElem = ret

End Function

8.返回线性表L中e的直接前驱元素

Public Function priorElem(list As SeqList, e) '0 不存在e值或无前驱, 其他 e的前驱在线性表的位置

Dim i As Integer, ret

ret = Null

For i=1 To list.Last

If list.Data(i) = e) Then Exit For

Next i

'寻找e所在位置

If i<list.Last And i<>1 Then ret = list.Data(i-1)

priorElem = ret

End Function

9.返回线性表L中e的直接后继元素

Public Function nextElem(list As SeqList, e) '0 不存在e值或无后继, 其他 e的后继在线性表的位置

Dim i As Integer, ret

ret = Null

For i=1 To list.Last

If list.Data(i) = e) Then Exit For

Next i

'寻找e所在位置

If i<list.Last Then ret = list.Data(i+1)

nextElem = ret

End Function

10.在线性表L中插入一个元素

Public Function insertSeqList(list As SeqList, i As Integer,e) As Integer '-1 表满，0 插入位置错，1 插入成功

Dim j As Integer

If list.Last = MaxSize Then

insertSeqList = -1

Exit Function

End If

If i < 1 Or i > list.Last + 1 Then

insertSeqList = 0

Exit Function

End If

For j = list.Last To i Step -1

list.Data(j+1) =list.Data(j)

Next j

list.Data(i) = e

list.Last = list.Last + 1

insertSeqList = 1

End Function

11.删除线性表L中第i个元素

Public Function deleteSeqList(list As SeqList, i As Integer) As Integer '0 删除失败，1 成功

Dim j As Integer,ret As Integer

ret = 0

If i >= 1 And i <= list.Last Then

For j = i+1 To list.Last

list.Data(j-1) =list.Data(j)

Next j

list.Last = list.Last - 1

ret = 1

End If

deleteSeqList = ret

End Function

顺序表的应用

用VB6实现将两个线性有序表合成为一个有序表，合并后的结果保存在原来的一个表中。

例如，两个有序表LA和LB分别为：LA=(1，4，5) ，LB=（2，6，9，20）

则合并后的有序表LA为：LA=（1，2，4，5，6，9，20）

具体实现

Public Const MaxSize As Integer = 7 '线性表大小为常量

Public Type SeqList

Data(1 To MaxSize) As Variant

Last As Integer

Ena Type

Dim LA As SeqList

Dim LB As SeqList

Function LocateEleml(list As SeqList, e)

Dim i As Integer,ret As Integer

ret =0

for i=l to list.Last

if list .data(i)<=e then

ret=i+1'找到内容大于e的第1节点的位置

Exit For

End if

Next i

LocateEleml=ret

End Function

Sub MergeAB1 (LA As SeqList, LB As SeqList)

Dimi As Integer,j As Integer,k As Integer

for i=1 to LB.Last

j = LocateEleml( LB.data(i))

k=insertSeqList (LA,j, LB.data(i))

Next i

End Sub