资源描述：
《第二章+线性表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第二章线性表☞2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4线性表的应用2.1线性表的类型定义线性结构的基本特征:集合中必存在唯一的一个“第一元素”；集合中必存在唯一的一个“最后元素”；除最后元素之外，均有唯一的后继；除第一元素之外，均有唯一的前驱。从逻辑上：数据之间的关系可以分4类：线性结构,树型结构,图状结构,集合线性表最简单的一种线性结构一个线性表是n个数据元素的有限序列比如AB……Z英文字母表比如001高等数学华罗庚S01……002线性代数銮汝书L01……003高等数学郑杭生S01…
2、…004离散数学耿素云S02………………………………线性表中每个数据元素的具体含义，各不相同，数据元素是基本单位，一个数据元素由若干个数据项组成2.1线性表的类型定义线性表记为（a1,……,ai-1,ai,ai+1,……,an）ai-1在ai之前称ai-1是ai的前驱ai在ai-1之后称ai是ai-1的后继序列中数据元素的个数n定义为线性表的表长称i为ai在线性表中的位序i=2，……,n线性表的元素个数称为的表长，n＝0时称为空表2.1线性表的类型定义线性表的抽象数据类型(ADT)定义如下：ADTList{数据
3、对象：D={ai
4、ai∈ElemSet,i=1,2,...,n,n>0}数据关系：R1={
5、ai-1,ai∈D,i=2,...,n}//表示为相邻元素的有序对基本操作：InitList(&L)操作结果：构造一个空的线性表L。DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表L，将原表中各结点所占的内存空间释放。引用型操作ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则FALSE。ListLength(L)初始条件：线性表L已存在。操作结果：返
6、回L中元素个数。PriorElem(L,cur_e,&pre_e)初始条件：线性表L已存在。操作结果：若cur_e是L的元素，但不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。NextElem(L,cur_e,&next_e)初始条件：线性表L已存在。操作结果：若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。LocateElem(L,e,compare())初始条件：线性表L已存在，compare()是元素判定函数。操作结果：返回L中第1个与e满足关
7、系compare()的元素的位序。若这样的元素不存在，则返回值为0。ListTraverse(L,visit())初始条件：线性表L已存在。操作结果：依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。GetElem(L,i,&e)初始条件：线性表L已存在，1≤i≤LengthList(L)操作结果：用e返回L中第i个元素的值。PutElem(&L,i,e)初始条件：线性表L已存在，1≤i≤LengthList(L)操作结果：L中第i个元素赋e的值。ListDelete(&L,i,&e)初始条件：线性表
8、L已存在且非空，1≤i≤LengthList(L)操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。ListInsert(&L,i,e)初始条件：线性表L已存在，1≤i≤LengthList(L)+1操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。}ADTListClearList(&L)初始条件：线性表L已存在。操作结果：将L重置为空表。加工型操作算法2.1利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B。voidunion(List&La，ListLb){La_len=Lis
9、tLength(La);Lb_len=ListLength(Lb);for(i=1;i<=lb_len;i++){GetElem(lb，i，e);if(!LocateElem(la，e，equal))ListInsert(la，++la_en，e)}}时间复杂度O(ListLength(La)×ListLength(Lb))算法2.2巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。此问题的算法如下：voidmergelist(Listla，
10、Listlb，List&lc){InitList(lc);i=j=1;k=0;la-len=ListLength(la);lb-len=ListLength(lb);while((i<=la-len)&&(j<=lb-len)){GetElem(la，i，ai)
