资源描述:
《DS chap2 线性表》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、线性表是最典型的线性结构第二章线性表11.集合中必存在唯一的“第一元素”;2.集合中必存在唯一的“最后元素”;3.除最后元素之外,均有唯一的(直接)后继;4.除第一元素之外,均有唯一的(直接)前驱。线性结构是数据元素的序列线性结构的基本特征:22.1线性表的类型定义2.3线性表类型的实现链式映象2.4一元多项式的表示2.2线性表类型的实现顺序映象目录32.1线性表的类型定义4ADTList{数据对象:D={ai
2、ai∈ElemSet,i=1,2,...,n,n≥0}{称n为线性表的表长;称n=0时的线
3、性表为空表。}数据关系:R1={
4、ai-1,ai∈D,i=2,...,n}{设线性表为(a1,a2,...,ai,...,an),称i为ai在线性表中的位序。}抽象数据类型线性表的定义如下:5结构初始化操作结构销毁操作引用型操作加工型操作}ADTList基本操作:6InitList(&L)操作结果:构造一个空的线性表L。初始化操作7DestroyList(&L)初始条件:操作结果:线性表L已存在。销毁线性表L。结构销毁操作8ListEmpty(L)判表空ListLength(L)求表长P
5、riorElem(L,cur_e,&pre_e)求前驱NextElem(L,cur_e,&next_e)求后继GetElem(L,i,&e)取第i个元素LocateElem(L,e,compare())元素定位ListTraverse(L,visit())遍历引用型操作(7种)9ListEmpty(L)初始条件:操作结果:线性表L已存在。若L为空表,则返回TRUE,否则FALSE。(线性表判空)10ListLength(L)初始条件:操作结果:线性表L已存在。返回L中元素个数。(求线性表的长度)11Pr
6、iorElem(L,cur_e,&pre_e)初始条件:操作结果:线性表L已存在。若cur_e是L的元素,但不是第一个,则用pre_e返回它的前驱,否则操作失败,pre_e无定义。(求数据元素的前驱)12NextElem(L,cur_e,&next_e)初始条件:操作结果:线性表L已存在。若cur_e是L的元素,但不是最后一个,则用next_e返回它的后继,否则操作失败,next_e无定义。(求数据元素的后继)13GetElem(L,i,&e)初始条件:操作结果:线性表L已存在,且1≤i≤LengthLi
7、st(L)用e返回L中第i个元素的值。(求线性表中某个数据元素)14LocateElem(L,e,compare())初始条件:操作结果:线性表L已存在,e为给定值,compare()是元素判定函数。返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在,则返回值为0。(定位函数)15ListTraverse(L,visit())初始条件:操作结果:线性表L已存在。Visit()为某个访问函数。依次对L的每个元素调用函数visit(ai)。一旦visit(ai)失败,则操作失败。(遍
8、历线性表)16ClearList(&L)清空PutElem(L,i,&e)置第i元素ListInsert(&L,i,e)插入第i元素ListDelete(&L,i,&e)删除第i元素加工型操作(4种)17ClearList(&L)初始条件:操作结果:线性表L已存在。将L重置为空表。(线性表置空)18PutElem(L,i,&e)初始条件:操作结果:线性表L已存在,且1≤i≤LengthList(L)L中第i个元素赋值同e的值。(改变数据元素的值)19ListInsert(&L,i,e)初始条件:操作结果
9、:线性表L已存在,且1≤i≤LengthList(L)+1在L的第i个元素之前插入新的元素e,L的长度增1。(插入数据元素)20ListDelete(&L,i,&e)初始条件:操作结果:线性表L已存在且非空,1≤i≤LengthList(L)删除L的第i个元素,并用e返回其值,L的长度减1。(删除数据元素)21利用上述定义的线性表可以实现其它更复杂的操作22B假设:有两个集合A和B分别用线性表LA和LB表示(线性表中的数据元素即为集合中的成员)。求新集合A=A∪B。例2-1ABAAABB23要求对线性表作
10、如下操作:扩大线性表LA——将存在于线性表LB中而不存在于LA中的数据元素插入到LA中。上述问题可演绎为:241.从线性表LB中依次察看每个数据元素;2.依值在线性表LA中进行查访;3.若不存在,则插入之。GetElem(LB,i)→eLocateElem(LA,e,equal())ListInsert(LA,n+1,e)操作步骤:25GetElem(Lb,i,e);//取Lb中第i个元素赋给eif(!LocateElem(L