资源描述：
《线性表的类型定义线性表的顺序表示与实现线性.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、2．1线性表的类型定义2．2线性表的顺序表示与实现2．3线性表的链式表示与实现2．3．1线性链表2．3．2循环链表2．3．3双向链表第2章线性表DataStructure一、教学目的与要求了解线性表的定义；学会线性表的顺序表示和实现、链式表示和实现二、主要教学内容线性表的类型定义；线性表的顺序表示和实现；线性表的链式表示和实现；一元多项式的表示及相加三、教学重点、难点线性表的顺序表示和实现、链式表示和实现四、授课方法及手段采用多媒体大屏幕投影授课五、讲课具体内容（讲稿）DataStructure线性结构的特点是：存在唯一的“第一个”数据元素；存
2、在唯一的“最后一个”数据元素；除第一个外，每个数据元素均有且只有一个前驱元素；除最后一个外，每个数据元素均有且只有一个后继元素。DataStructure2.1线性表的类型定义线性表举例:字母表(A,B,C,…,X,Y,Z)数据序列(6,17,28,50,92,188)n个元素的线性表:（a1,a2,…,ai,ai+1,…,an）第一个元素(没有前驱)第i个元素(有唯一的前驱和唯一的后继)最后一个元素(没有后继)DataStructure线性表的抽象数据类型(ADT)ADTList{数据对象：D={ai
3、ai属于Elemset,(i=1,2,…
4、,n,n≥0)}数据关系：R1={＜ai-1,ai＞
5、ai-1,ai属于D,(i=2,3,…,n)}基本操作：InitList(&L);DestroyList(&L);ListInsert(&L,i,e);ListDelete(&L,i,&e);…}ADTListDataStructureInitList(&L)操作结果:构造一个空的线性表L。DestroyList(&L)初始条件:线性表L已经存在。操作结果:销毁线性表L。ClearList(&L)初始条件:线性表L已经存在。操作结果:将线性表L重置为空表。基本操作(一)DataStructu
6、reListEmpty(L)初始条件:线性表L已经存在。操作结果:若线性表L为空表，则返回TURE;否则返回FALSE。ListLength(L)初始条件:线性表L已经存在。操作结果:返回线性表L中的数据元素个数。基本操作(二)DataStructureGetElem(L,i,&e)；初始条件:线性表L已经存在，1<=I<=ListLength(L)。操作结果:用e返回线性表L中第i个数据元素的值。LocateElem(L,e,compare())初始条件:线性表L已经存在，compare()是数据元素判定函数。操作结果:返回L中第1个与e满足
7、compare()的数据元素的位序。若这样的数据元素不存在则返回值为0。基本操作(三)DataStructurePriorElem(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无意义。基本操作(四)DataStructureListIn
8、sert(&L,i,e)初始条件:线性表L已经存在，1<=i<=ListLength(L)+1。操作结果:在L的第i个位置之前插入新的数据元素e,L的长度加一。ListDelete(&L,i,&e)初始条件:线性表L已经存在，1<=i<=ListLength(L)。操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减一。基本操作(五)DataStructure例2-1线性表La,Lb的合并合并前：La=(2,5,7,9)Lb=(4,5,6,7)合并后:La=(2,5,7,9,4,6)DataStructurevoidunion(List
9、&La,ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);If(!LocateElem(La,e,equal))ListInsert(La,++La_len,e);}}//union时间复杂度：O(ListLength(La)×ListLength(Lb))DataStructure例：非递减线性表La,Lb的合并合并前：La=(3,5,8,11)Lb=(2,6,8,9,11,15,20)合并后:Lc=(2,3,5
10、,6,8,8,9,11,11,15,20)voidMergeList(ListLa,ListLb,List&Lc){//已知非递减线性表La,Lb//
