数据结构2线性表1

《数据结构2线性表1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性表2．1线性表的类型定义2．2线性表的顺序表示与实现2．3线性表的链式表示与实现2．3．1线性链表2．3．2循环链表2．3．3双向链表第二章线性表线性结构的特点是:存在唯一的”第一个”数据元素;存在唯一的”最后一个”数据元素;除第一个外,每个数据元素均有且只有一个前驱元素;除最后一个外,每个数据元素均有且只有一个后继元素。2．1线性表的类型定义线性表举例:字母表(A,B,C,…,X,Y,Z)数据序列(6,17,28,50,92,188)n个元素的线性表:（a1,a2,…,ai,ai+1,…,an）第一

2、个元素(没有前驱)第i个元素(有唯一的前驱和唯一的后继)最后一个元素(没有后继)线性表的抽象数据类型(ADT)ADTList{数据对象：D={ai

3、ai属于Elemset,(i=1,2,…,n,n≥0)}数据关系：R1={＜ai-1,ai＞

4、ai-1,ai属于D,(i=2,3,…,n)}基本操作：InitList(&L);DestroyList(&L);ListInsert(&L,i,e);ListDelete(&L,i,&e);等等}ADTListInitList(&L);DestroyList(&L);Cl

5、earList(&L);ListEmpty(L);ListLength(L);GetElem(L,i,&e);LocateElem(L,e,compare());PriorElem(L,cur_e,&pre_e);NextElem(L,cur_e,&next_e);ListInsert(&L,i,e);ListDelete(&L,i,&e);ListTraverse(&L,visited())线性表ADT的基本操作：InitList(&L)操作结果:构造一个空的线性表L。DestroyList(&L)初始条件:

6、线性表L已经存在。操作结果:销毁线性表L。ClearList(&L)初始条件:线性表L已经存在。操作结果:将线性表L重置为空表。基本操作(一)：ListEmpty(L)初始条件:线性表L已经存在。操作结果:若线性表L为空表，则返回TURE;否则返回FALSE。ListLength(L)初始条件:线性表L已经存在。操作结果:返回线性表L中的数据元素个数。基本操作(二)：GetElem(L,i,&e)；初始条件:线性表L已经存在，1<=i<=ListLength(L)。操作结果:用e返回线性表L中第i个数据元素的值

7、。LocateElem(L,e,compare())初始条件:线性表L已经存在，compare()是数据元素判定函数。操作结果:返回L中第1个与e满足compare()的数据元素的位序。若这样的数据元素不存在则返回值为0。基本操作(三)：PriorElem(L,cur_e,&pre_e)初始条件:线性表L已经存在。操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,否则操作失败;pre_e无意义。NextElem(L,cur_e,&next_e)初始条件:线性表L已经存在。操作结果:

8、若cur_e是L的数据元素,且不是第最后个,则用next_e返回它的后继,否则操作失败,next_e无意义。基本操作(四)：ListInsert(&L,i,e)初始条件:线性表L已经存在，1<=i<=ListLength(L)+1。操作结果:在L的第i个位置之前插入新的数据元素e,L的长度加一。插入前（长度为n）:（a1,a2,…,ai-1,ai,…,an）插入后（长度为n+1）:（a1,a2,…,ai-1,e,ai,…,an）基本操作(五)：ListDelete(&L,i,&e)初始条件:线性表L已经存在，1

9、<=i<=ListLength(L)。操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减一。删除前（长度为n）:（a1,a2,…,ai-1,ai,ai+1,…,an）删除后（长度为n-1）:（a1,a2,…,ai-1,ai+1,…,an）ListTraverse(&L,visited())基本操作(六)：例2-1线性表La,Lb的合并.La=La∪Lb.(算法2.1)voidunion(List&La,ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb

10、);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);If(!LocateElem(La,e,equal))ListInsert(La,++La_len,e);}}//union例2-1线性表La,Lb的合并.La=(2,5,7,9)Lb=(4,5,6,7)合并结果:La=(2,5,7,9,4,6)由本节最后知，算法2.1的时间复杂度为O(ListLengt