数据结构第次课第二章线性表顺序表精品文稿.ppt

《数据结构第次课第二章线性表顺序表精品文稿.ppt》由会员分享，可在线阅读，更多相关《数据结构第次课第二章线性表顺序表精品文稿.ppt（42页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据结构第次课第二章线性表顺序表第1页，本讲稿共42页2.1 线性表的逻辑结构线性表的逻辑结构 线性表：由线性表：由n(n0)个数据元素个数据元素(结点结点)a1，a2，an组成的组成的有限有限序列序列。其中数据元素的个数。其中数据元素的个数n定义为表的长度。当定义为表的长度。当n=0时称为空表，常常将非空的线性表时称为空表，常常将非空的线性表(n0)记作：记作：(a1，a2，an)这里的数据元素这里的数据元素ai(1in)只是一个抽象的符号，其具体只是一个抽象的符号，其具体含义在不同的情况下可以不同。含义在不同的情况下可以不同。例例1、26个英文字母组成的字母表个英文字母组成的字母表 （A，

2、B，C、Z）例例2、某校从某校从1978年到年到1983年各种型号的计算机拥有量的变化年各种型号的计算机拥有量的变化情况。情况。（6，17，28，50，92，188）线性结构是一个数据元素的有序（次序）集。这里的序不是指一定要是数值上的次序关系。第2页，本讲稿共42页 .神经衰弱 17 男790634张立立 健康 21 男790633刘建平 一般 20 女790632陈 红 健康 18 男790631王小林 健康情况年龄性 别学 号姓 名例3、学生健康情况登记表如下：第3页，本讲稿共42页 从以上例子可看出线性表的逻辑特征是：从以上例子可看出线性表的逻辑特征是：(1)对非空的线性表，有且仅有一

3、个开始结点对非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有它没有直接前趋，而仅有一个直接后继一个直接后继a2；(2)有且仅有一个终端结点有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋它没有直接后继，而仅有一个直接前趋a n-1；(3)其余的内部结点其余的内部结点ai(2in-1)都有且仅有一个直接前趋都有且仅有一个直接前趋a i-1和一个和一个直接后继直接后继ai+1。线性表是一种典型的线性结构。线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。储结构上进行的

4、。第4页，本讲稿共42页抽象数据类型抽象数据类型线性表线性表的定义如下：的定义如下：ADT List 数据对象：数据对象：D ai|ai ElemSet,i=1,2,.,n,n0 称称 n 为线性表的为线性表的表长表长;称称 n=0 时的线性表为时的线性表为空表空表。数据关系：数据关系：R1|ai-1,aiD,i=2,.,n 设线性表为设线性表为(a1 1，a2 2,.,.，ai，.，a an),),称称 i 为为 ai 在线性表中的在线性表中的位序位序。基本操作：基本操作：ADT List关系：相邻元素的有序对第5页，本讲稿共42页 InitList(&L)操作结果：操作结果：构造一个空的线

5、性表构造一个空的线性表 L。DestroyList(&L)初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在。已存在。销毁线性表销毁线性表 L。构造n=0的线性表初始条件：操作前状态第6页，本讲稿共42页 ListEmpty(L)初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在。已存在。若若 L 为空表，则返回为空表，则返回TRUE，否则，否则FALSE。（线性表判空）第7页，本讲稿共42页ListLength(L)初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在。已存在。返回返回 L 中元素个数。中元素个数。（求线性表的长度）第8页，本讲稿共42

6、页 PriorElem(L,cur_e,&pre_e)初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在。已存在。若若 cur_e 是是 L 的元素，则用的元素，则用pre_e 返回它的前驱，否则操返回它的前驱，否则操作失败，作失败，pre_e无定义。无定义。（求数据元素的前驱）当不是第一个元素时，则存在，否则不存在该元素或是表的第一个元素，无定义。第9页，本讲稿共42页NextElem(L,cur_e,&next_e)初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在。已存在。若若 cur_e 是是 L 的元素，则用的元素，则用next_e 返回它的后继，否则操作

7、返回它的后继，否则操作失败，失败，next_e无定义。无定义。（求数据元素的后继）第10页，本讲稿共42页GetElem(L,i,&e)初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在，已存在，用用 e 返回返回L中第中第 i 个元素的值。个元素的值。（求线性表中某个数据元素）且且 1iLengthList(L)第11页，本讲稿共42页LocateElem(L,e,compare()初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在，已存在，e e 为给定值，为给定值，compare()是元素判定函数。是元素判定函数。返回返回 L 中第中第 1 个与个与 e 满足

8、关系满足关系 compare()的元素的的元素的位序位序。若这样的元素不存在，则返回值为若这样的元素不存在，则返回值为 0。（定位函数）第12页，本讲稿共42页 ListTraverse(L,visit()初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在。已存在。visit()为某个访问函数。为某个访问函数。依次依次对对 L 中中每个元素调用每个元素调用函数函数visit()。一旦。一旦 visit()失败，失败，则操作失败。则操作失败。（遍历线性表）引用性操作不改变原表的结构第13页，本讲稿共42页ClearList(&L)初始条件：初始条件：操作结果：操作结果：线性表线性表

9、 L 已存在。已存在。将将 L 重置为空表。重置为空表。（线性表置空）第14页，本讲稿共42页PutElem(&L,i,&e)初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在，已存在，L 中第中第 i 个元素赋值个元素赋值 e e。（改变数据元素的值）且且 1iLengthList(L)第15页，本讲稿共42页 ListInsert(&L,i,e)初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在已存在，在在 L 的第的第 i 个元素之前个元素之前插入插入新的元素新的元素 e，L 的长度增的长度增1。（插入数据元素）且且 1iLengthList(L)+1改变了元

10、素之间的关系第16页，本讲稿共42页ListDelete(&L,i,&e)初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在且非空，已存在且非空，删除删除 L 的第的第 i 个元素，并用个元素，并用 e 返回其值，返回其值，L 的长度减的长度减1。（删除数据元素）1iLengthList(L)第17页，本讲稿共42页利用上述定义的利用上述定义的线性表类型线性表类型 可以实现其它更复杂的操作可以实现其它更复杂的操作例例 2-1第18页，本讲稿共42页 假设假设:有两个集合有两个集合 A 和和 B 分别用两分别用两个线性表个线性表 LA 和和 LB 表示，即：线性表示，即：线性表中的

11、数据元素即为集合中的成员。表中的数据元素即为集合中的成员。现要求一个新的集合现要求一个新的集合AAB。例例 2-1 第19页，本讲稿共42页 要求对线性表作如下操作：要求对线性表作如下操作：扩大线性表扩大线性表 LA，将，将存在于线性表存在于线性表LB 中中而而不存在于线性表不存在于线性表 LA 中中的数据元的数据元素素插入到线性表插入到线性表 LA 中中去。去。上述问题可演绎为：AUB，相同的元素只有一个A和B本身也是集合，所以各自不含有重复元素第20页，本讲稿共42页1从线性表从线性表 LB 中依次察看每个数据元素中依次察看每个数据元素;2依值在线性表依值在线性表 LA 中进行查访中进行查

12、访;3若不存在，则插入之。若不存在，则插入之。GetElem(LB,i)e LocateElem(LA,e,equal()ListInsert(LA,n+1,e)(n 表示线性表表示线性表 LA 当前长度当前长度)操作步骤：第21页，本讲稿共42页 GetElem(Lb,i,e);/取Lb中第i个数据元素赋给e if(!LocateElem(La,e,equal()ListInsert(La,+La_len,e);/La中不存在和 e 相同的数据元素，则插入之 La_len=ListLength(La);/求线性表的长度求线性表的长度 Lb_len=ListLength(Lb);for(i=1

13、;i n;Float*p;P=new floatn;Delete p;第28页，本讲稿共42页例如：顺序表23 75 41 38 54 62 17L.elemL.length=7L.listsize第29页，本讲稿共42页线性表操作 ListInsert(&L,i,e)的实现：首先分析首先分析:插入元素时，线性表的逻辑结构逻辑结构发生什么变化发生什么变化？第30页，本讲稿共42页(a1,ai-1,ai,an)改变为a1 a2 ai-1 ai ana1 a2 ai-1 ai ean,表的长度增加(a1,ai-1,e,ai,an)第31页，本讲稿共42页21 18 30 75 42 56 8721

14、 18 30 75例如：ListInsert(L,5,66)L.length-1087564266第32页，本讲稿共42页void ListInsert(&L,i,e)/在线性表在线性表L中第中第i个位置插入元素个位置插入元素e if(iL.length+1)cout“插入序号错误插入序号错误”=ListSize)溢出处理；溢出处理；else for(j=L.length-1;j=i-1;j-)/第第i个元素（下标为个元素（下标为i-1)开始开始 L.dataj+1=L.dataj;/顺序后移顺序后移 L.datai-1=e;L.length+;第33页，本讲稿共42页算法分析 设表的长度为n

15、。该算法的时间主要花费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）是n-i+1。由此，所需移动结点的次数依赖于 (1)表的长度 (2)插入位置。当=n+1时，不移动-最好情况；当=1时，需移动表中所有结点-最坏情况，a1，a i-1，ai，anx移动数据：n-i+1第34页，本讲稿共42页算法的平均移动算法的平均移动 由于插入可能在表中任何位置上进行，在长度为由于插入可能在表中任何位置上进行，在长度为n的线性表中第的线性表中第i个位置上插入一个结点，令个位置上插入一个结点，令Eis(n)表示移动表示移动结点的期望值（即移动的平均次数），则在第结点的期望值（即移动的平均次数），则

16、在第i个位置上插个位置上插入一个结点的移动次数为入一个结点的移动次数为n-i+1。Pi代表在第代表在第i个位置插入概个位置插入概率，则率，则 Eis(n)=p1*n+p2*(n-1)+.+pn*1+pn+1*0 若表中任何位置若表中任何位置(1in+1)上插入结点的概率是均上插入结点的概率是均等的，则等的，则 p1=p2=p3=p n+1=1/(n+1)因此，在等概率插入的情况下：因此，在等概率插入的情况下：Eis(n)=1/(n+1)n+(n-1)+1+0=n/2 结论结论a1，a i-1，ai，an可能的插入点有n+1处第35页，本讲稿共42页结论：在顺序表上做插入运算，平均要移动表上一半

17、结点。当表长 n较大时，算法的效率相当低。虽然Eis(n)中n的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为O(n)。第36页，本讲稿共42页线性表操作 ListDelete(&L,i,&e)的实现：首先分析：删除元素时，线性表的逻辑结构发生什么变化？第37页，本讲稿共42页(a1,ai-1,ai,ai+1,an)改变为ai+1an,表的长度减少a1 a2 ai-1 ai ai+1 ana1 a2 ai-1(a1,ai-1,ai+1,an)第38页，本讲稿共42页21 18 30 75 42 56 8721 18 30 75L.length-108756例如：List

18、Delete(L,5,e)第39页，本讲稿共42页void deleteList(&L,i,e)/表L中删除第i个元素 if(iL.length)cout“删除序号错”endl;return ERROR;e=L.datai-1;for(j=i;j=L.length-1;j+)L.dataj-1=L.dataj;L.length-;第40页，本讲稿共42页 算法分析与插入算法相似，结点的移动次数也是由表算法分析与插入算法相似，结点的移动次数也是由表长长n和位置和位置i决定。决定。若若i=n，无需移动结点；无需移动结点；若若i=1，则前移元素则前移元素n-1个个 令令Edl表示所需移动结点的平均次

19、数，删除表中第表示所需移动结点的平均次数，删除表中第i个结点个结点的移动次数为的移动次数为n-i，pi是删除是删除i个元素的概率，则个元素的概率，则 Edl=p1*(n-1)+p2(n-2)+.+pn-1*1+pn*0等概率的假设下：等概率的假设下：p1=p2=p3=pn=1/n Edl=1/n(n-1)+(n-2)+1+0=(n-1)/2 即在顺序表上做删除运算，即在顺序表上做删除运算，平均要移动表中约一半的结平均要移动表中约一半的结点，点，平均时间复杂度也是平均时间复杂度也是O(n)。第41页，本讲稿共42页顺序表总结顺序表总结1.是线性表的一种表示方法；是线性表的一种表示方法；2.是一组地址连续的存储空间；是一组地址连续的存储空间；3.可用一维数组类型描述，长度可变，数组可用一维数组类型描述，长度可变，数组需动态分配；需动态分配；优点：可对每个数据元素随机存取，表长是优点：可对每个数据元素随机存取，表长是显值；显值；缺点：在进行插入和删除元素时要进行元素缺点：在进行插入和删除元素时要进行元素移动，大致移动表长一半的元素。移动，大致移动表长一半的元素。第42页，本讲稿共42页