资源描述：
《第2章 线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章线性表2.1线性表的类型定义2.2线性表的顺序表示与实现2.3线性表的链式表示与实现2.3.1线性链表2.3.2循环链表2.3.3双向链表1线性结构的特点是:存在唯一的“第一个”数据元素;存在唯一的“最后一个”数据元素;除第一个外,每个数据元素均有且只有一个前驱元素;除最后一个外,每个数据元素均有且只有一个后继元素。线性表是一种常用的简单的数据结构，它属于线性结构的范畴。22.1线性表的类型定义线性表举例:字母表(A,B,C,…,X,Y,Z)数据序列(6,17,28,50,92,188)学生健康情况登记表n个元素的线性表:（a1,a2,…,ai,ai+1,…,an）第一个元
2、素(没有前驱)第i个元素(有唯一的前驱和唯一的后继)最后一个元素(没有后继)数据元素的个数n称为线性表的长度，当n＝0时称为空表。3学生健康情况登记表姓名学号性别年龄健康情况王小林790631男18健康陈红790632女20一般刘建平790633男21健康张立立790634男17一般……..……..…….…….…….4线性表的抽象数据类型(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(&
5、L);ListInsert(&L,i,e);ListDelete(&L,i,&e);……}ADTList5InitList(&L);DestroyList(&L);ClearList(&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,visit())线性表ADT的基本操作6In
6、itList(&L)操作结果:构造一个空的线性表L。DestroyList(&L)初始条件:线性表L已经存在。操作结果:销毁线性表L。ClearList(&L)初始条件:线性表L已经存在。操作结果:将线性表L重置为空表。基本操作(一)：7ListEmpty(L)初始条件:线性表L已经存在。操作结果:若线性表L为空表，则返回TURE;否则返回FALSE。ListLength(L)初始条件:线性表L已经存在。操作结果:返回线性表L中的数据元素个数。基本操作(二)：8GetElem(L,i,&e)；初始条件:线性表L已经存在，1<=i<=ListLength(L)。操作结果:用e返回线
7、性表L中第i个数据元素的值。LocateElem(L,e,compare())初始条件:线性表L已经存在，compare()是数据元素判定函数。操作结果:返回L中第1个与e满足compare()的数据元素的位序。若这样的数据元素不存在则返回值为0。基本操作(三)：9PriorElem(L,cur_e,&pre_e)初始条件:线性表L已经存在。操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,否则操作失败，pre_e无意义。NextElem(L,cur_e,&next_e)初始条件:线性表L已经存在。操作结果:若cur_e是L的数据元素,且不是最后一个
8、,则用next_e返回它的后继,否则操作失败,next_e无意义。基本操作(四)：10ListInsert(&L,i,e)初始条件:线性表L已经存在，1<=i<=ListLength(L)+1。操作结果:在L的第i个位置之前插入新的数据元素e,L的长度加1。插入前（长度为n）:（a1,a2,…,ai-1,ai,…,an）插入后（长度为n+1）:（a1,a2,…,ai-1,e,ai,…,an）基本操作(五)：11ListDelete(&L,i,&e)初始条件:线性表L已经存在，1<=i<=ListLength(L)。操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1。删
9、除前（长度为n）:（a1,a2,…,ai-1,ai,ai+1,…,an）删除后（长度为n-1）:（a1,a2,…,ai-1,ai+1,…,an）ListTraverse(L,visit())初始条件:线性表L已经存在。操作结果:依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。基本操作(六)：12线性表（a1,a2,…,ai,ai+1,…,an）的顺序表示:用一组地址连续的存储单元依次存储线性表的数据元素。Loc(ai+1)=Loc(ai)+ιLoc(
