第2章 线性表

《第2章 线性表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章线性表学习要点:了解线性表的逻辑结构特性熟练掌握线性表的顺序存储结构和链式存储结构的描述方法熟练掌握线性表在这两种存储结构上实现的基本操作——查找、插入和删除能够从时间和空间复杂度的角度综合比较线性表的两种存储结构的不同特点及其适用场合线性表是一种最简单的线性结构。线性结构是一个数据元素的有序(次序)关系存在唯一的一个“第一个”的数据元素；存在唯一的一个“最后一个”的数据元素；除第一个数据元素外，均有唯一的前驱；除最后一个数据元素外，均有唯一的后继。2.1线性表的类型定义线性表是最常用而且最简单的一种数据结构。定义：

2、线性表是n个数据元素的有限序列。记为：(a1,...,ai-1,ai,ai+1,...,an)26个字母表：(A，B，C，…，Z)是一个线性表例如：某校近4年计算机拥有量：(120，340，510，720)记录文件特征：元素个数n——表长度；n=0——空表1

3、ai∈ElemSet,i=1,2,...,n,n≥0}{称n为线性表的表长;称n=0时的

4、线性表为空表。}数据关系：R1＝{

5、ai-1,ai∈D,i=2,...,n}{设线性表为(a1，a2,...，ai，...，an),称i为ai在线性表中的位序。}基本操作：结构初始化操作结构销毁操作引用型操作加工型操作}ADTList初始化操作：InitList(&L)操作结果：构造一个空的线性表L。结构撤销操作：引用型操作：ListEmpty(L)ListLength(L)PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e)GetElem(L,i,&e)L

6、ocateElem(L,e,compare())ListTraverse(L,visit())DestroyList(&L)初始条件：操作结果：线性表L已存在。销毁线性表L。加工型操作：ClearList(&L)PutElem(&L,i,e)——改变数据元素的值初始条件：线性表L已存在，且1≤i≤LengthList(L)操作结果：L中第i个元素赋值为e。ListInsert(&L,i,e)ListDelete(&L,i,&e)例2-1:假设:有两个集合A和B分别用两个线性表LA和LB表示，即：线性表中的数据元素即为集合中

7、的成员。现要求一个新的集合A=A∪B。GetElem(Lb,i,e);//取Lb中第i个数据元素赋给eif(!LocateElem(La,e,equal()))ListInsert(La,++La_len,e);//La中不存在和e相同的数据元素，则插入之La_len=ListLength(La);//求线性表的长度Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){}//for}//unionvoidunion(List&La,ListLb){分析：操作步骤：从线性表LB中依次取出每

8、个数据元素;依值在线性表LA中进行查访;若不存在，则插入之。GetElem(LB,i)→eLocateElem(LA,e,equal())ListInsert(LA,n+1,e)(n表示线性表LA当前长度)例2-2:已知一个非纯集合B，试构造一个纯集合A，使A中只包含B中所有值各不相同的数据元素。分析：算法的策略应该和例2-1基本相同,差别仅在于集合A的初始状态是“空集”。集合B集合Avoidunion(List&La,ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);

9、}//unionGetElem(Lb,i,e);//取Lb中第i个数据元素赋给eif(!LocateElem(La,e,equal()))ListInsert(La,++La_len,e);//La中不存在和e相同的数据元素，则插入之for(i=1;i<=Lb_len;i++){}InitList(La);//构造(空的)线性表LA思考：改变结构，以有序表表示集合。则算法有什么不同？例如：集合B:(2，3，3，5，6，6，6，8，12)对构造集合A而言，数据元素两两不同，且依值从小至大的顺序插入。voidpurge(Lis

10、t&La,ListLb){InitList(LA);La_len=ListLength(La);Lb_len=ListLength(Lb);//求线性表的长度for(i=1;i<=Lb_len;i++){}}//purgeGetElem(Lb,i,e);//取Lb中第i个数据元素赋给eif(){List