数据结构第二章线性表ppt课件.ppt

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

1、第二章线性表线性结构是一个数据元素的有序（次序）集线性表的基本特征存在惟一的一个被称做“第一个”的数据元素；存在惟一的一个被称做“最后一个”的数据元素；除第一个之外，集合中的每个数据元素均只有一个前驱；除最后一个之外，集合中的每个数据元素均只有一个后继。2.1线性表的类型定义2.2线性表类型的实现——顺序映像2.3线性表类型的实现——链式映像2.4一元多项式的表示抽象数据类型线性表的定义ADTList{数据对象：D={ai

2、aiElemSeti=1,2,..,nn≥0}{称n为线性表的表长，称n=0时的线性表为空表}数据关系：R1={

3、ai,ai

4、+1ElemSet,i=1,2,..,n-1≥0}{称i为ai在线性表中的位序}(a1,a2,...,ai-1,ai,ai+1,…,an)基本操作：{结构初始化}InitList(&L)操作结果：构造一个空的线性表L{销毁结构}DetroyList(&L)初始条件：线性表L已经存在操作结果：销毁线性表L{引用型操作}ListEmpty(L)ListLength(L)PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e)GetElem(L,i,&e)LocateElem(L,e,compare())ListTravers

5、e(L,visit())ListEmpty(L)操作结果：若线性表L为空表，则返回True，否则返回FalseListLength(L)操作结果：返回线性表L中元素的个数PriorElem(L,cur_e,&pre_e)操作结果：若cur_e是L的元素，但不是第一个，则用pre_e返回它的前驱，否则操作失败NextElem(L,cur_e,&next_e)操作结果：若cur_e是L中的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败GetElem(L,i,&e)操作结果：用e返回L中第i个元素的值，其中1<=i<=ListLength(L)Locat

6、eElem(L,e,compare())操作结果：返回第一个与e满足compare()关系的数据元素的位序。若不存在这样的元素，则返回0ListTraverse(L,visit())操作结果：遍历线性表L，对每个元素执行函数visit(){加工型操作}ClearList(&L)PutElem(L,i,&e)ListInsert(&L,i,e)ListDelete(&l,i,&e)ClearList(&L)初始条件：线性表L已经存在操作结果：将L重至为空表PutElem(L,i,&e)初始条件：线性表L已存在，其中1<=i<=LengthList(L)操作结果：L中的

7、第i个元素赋值为e的值ListInsert(&L,i,e)初始条件：线性表L已存在，其中1<=i<=LengthList(L)+1操作结果：在L的第i个元素之前插入一个新的元素e，L的长度增加1ListDelete(&l,i,&e)初始条件：线性表L已存在并且非空，其中1<=i<=LengthList(L)操作结果：将L的第i个元素删除，并将之，L的长度增加1利用上述定义的线性表可以完成更复杂的操作例2-1假设有两个集合A和B，分别用两个线性表LA和LB来表示（即：线性表中的数据元素为集合中的成员）现求一个新的集合A=A∪B上述问题可以演绎为，要求对线性表作如下操作

8、：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中EBFHVDALAASFGLBVSGijjjjjjiiii从线性表LB中依次取得每个数据元素：GetElem(LB,i)→e依值在线性表LA中进行查访：LocateElem(LA,e,Equal())若不存在，则插入之，ListInsert(LA,n+1,e)VoidUnion(List&La,ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);//求线性表的长度for(i=0;i

9、i,e);//取Lb中的第i个元素赋给eif(!LocateElem(La,e,equal()))ListInsert(La,La_len++,e)//若La中不存在和e相同的值，则插入之}}例2-2已知一个非纯集合B，试构造一个纯集合A，使A中只包含B中所有值各不相同的数据元素EBEHDALBBDBELAEBHDAVoidPurge(List&La,ListLb){InitList(La);//设置空的线性表LaLa_len=ListLength(La);Lb_len=ListLength(Lb);//求线性表的长度for(i=0;i