资源描述：
《chap2 linear list》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章线性表12．1线性表的类型定义2．2线性表的顺序表示与实现2．3线性表的链式表示与实现2．3．1线性链表2．3．2循环链表2．3．3双向链表主要内容（Contents）2从第2章至第4章将讨论线性结构。特点：(1)存在唯一的“第一个”的数据元素；(2)存在唯一的“最后一个”的数据元素；(3)除第一个之外，每个元素只有一个前驱；(4)除最后一个之外，每个元素只有一个后继。3线性表(Linear_List)：n个数据元素的有限序列。每个数据元素的具体含义，在不同的情况下各不相同。可以是一个数、或一个符号，也可以
2、是一页书，甚至其它更复杂的信息。2.1线性表的类型定义4例如，26个英文字母的字母表：(A，B，C，……，Z)数据元素是单个字母字符。又如，某机构从2003年到2011年计算机数量的变化情况可以用线性表的形式给出：(6，17，28，50，92，188,257,349,468)数据元素是整数。5例如学生健康情况登记表，每个学生的情况为一个记录(数据元素)，由姓名、学号、性别、年龄、班级和健康状况等六个数据项组成。姓名学号性别年龄班级健康状况王小林790631男18计05健康陈红790631女18计05一般刘键平79
3、0633男19计05健康张立立790634男17计05神经衰弱………………6线性表中元素的个数n(n≥0)定义为线性表的长度，n=0时称为空表。ai是第i个数据元素，称i为数据元素ai在线性表中的位序。n个元素的线性表:（a1,a2,…,ai,ai+1,…,an）第一个元素(没有前驱)第i个元素(有唯一的前驱和唯一的后继)最后一个元素(没有后继)7线性表的抽象数据类型(ADT)ADTList{数据对象：D={ai
4、ai属于Elemset,(i=1,2,…,n,n≥0)}数据关系：R1={＜ai-1,ai＞
5、ai-
6、1,ai属于D,(i=2,3,…,n)}基本操作：InitList(&L);DestroyList(&L);ListInsert(&L,i,e);ListDelete(&L,i,&e);……}ADTList8InitList(&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,
7、&next_e);ListInsert(&L,i,e);ListDelete(&L,i,&e);ListTraverse(&L,visited())线性表ADT的基本操作：9InitList(&L)操作结果:构造一个空的线性表L。DestroyList(&L)初始条件:线性表L已经存在。操作结果:销毁线性表L。ClearList(&L)初始条件:线性表L已经存在。操作结果:将线性表L重置为空表。基本操作(一)：10ListEmpty(L)初始条件:线性表L已经存在。操作结果:若线性表L为空表，则返回TURE;否则
8、返回FALSE。ListLength(L)初始条件:线性表L已经存在。操作结果:返回线性表L中的数据元素个数。基本操作(二)：11GetElem(L,i,&e)；初始条件:线性表L已经存在，1<=i<=ListLength(L)。操作结果:用e返回线性表L中第i个数据元素的值。LocateElem(L,e,compare())初始条件:线性表L已经存在，compare()是数据元素判定函数。操作结果:返回L中第1个与e满足compare()的数据元素的位序。若这样的数据元素不存在则返回值为0。基本操作(三)：12
9、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无意义。基本操作(四)：13ListInsert(&L,i,e)初始条件:线性表L已经存在，1<=i<=ListLength(L)+1。操作
10、结果:在L的第i个位置之前插入新的数据元素e,L的长度加一。插入前（长度为n）：（a1,a2,…,ai-1,ai,…,an）插入后（长度为n+1）：（a1,a2,…,ai-1,e,ai,…,an）基本操作(五)：14ListDelete(&L,i,&e)初始条件:线性表L已经存在，1<=i<=ListLength(L)。操作结果:删除L的第i个数据元素,并用e返回其值,L
