数据结构第次课第二章线性表顺序表幻灯片.ppt

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

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

2、组成的字母表 （A，B，C、Z）例例2、某校从某校从1978年到年到1983年各种型号的计算机拥有量的变化年各种型号的计算机拥有量的变化情况。情况。（6，17，28，50，92，188）线性结构是一个数据元素的有序（次序）集。这里的序不是指一定要是数值上的次序关系。第2页，共42页，编辑于2022年，星期六 .神经衰弱神经衰弱 17 男男790634张立立张立立 健康健康 21 男男790633刘建平刘建平 一般一般 20 女女790632陈陈 红红 健康健康 18 男男790631王小林王小林 健康情况健康情况年龄年龄性性 别别学学 号号姓姓 名名例例3 3、学生健康情况登记表如下：、学生健

3、康情况登记表如下：第3页，共42页，编辑于2022年，星期六 从以上例子可看出线性表的逻辑特征是：从以上例子可看出线性表的逻辑特征是：(1)对非空的线性表，有且仅有一个开始结点对非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，它没有直接前趋，而仅有一个直接后继而仅有一个直接后继a2；(2)有且仅有一个终端结点有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋它没有直接后继，而仅有一个直接前趋a n-1；(3)其余的内部结点其余的内部结点ai(2in-1)都有且仅有一个直接前趋都有且仅有一个直接前趋a i-1和一个直和一个直接后继接后继ai+1。线性表是一种典型的线性结构。线性

4、表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。上进行的。第4页，共42页，编辑于2022年，星期六抽象数据类型抽象数据类型线性表线性表的定义如下：的定义如下：ADT List 数据对象：数据对象：D ai|ai ElemSet,i=1,2,.,n,n0 称称 n 为线性表的为线性表的表长表长;称称 n=0 时的线性表为时的线性表为空表空表。数据关系：数据关系：R1|ai-1,aiD,i=2,.,n 设线性表为设线性表为(a1，a2,.，ai，.，an),称称 i 为为 ai 在线性表

5、中的在线性表中的位序位序。基本操作：基本操作：ADT List关系：相邻元素的有序对第5页，共42页，编辑于2022年，星期六 InitList(&L)操作结果：操作结果：构造一个空的线性表构造一个空的线性表 L。DestroyList(&L)初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在。已存在。销毁线性表销毁线性表 L。构造n=0的线性表初始条件：操作前状态第6页，共42页，编辑于2022年，星期六 ListEmpty(L)初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在。已存在。若若 L 为空表，则返回为空表，则返回TRUE，否则，否则FALSE。（线性

6、表判空）（线性表判空）第7页，共42页，编辑于2022年，星期六ListLength(L)初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在。已存在。返回返回 L 中元素个数。中元素个数。（求线性表的长度）（求线性表的长度）第8页，共42页，编辑于2022年，星期六 PriorElem(L,cur_e,&pre_e)初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在。已存在。若若 cur_e 是是 L 的元素，则用的元素，则用pre_e 返回它的前驱，否则操返回它的前驱，否则操作失败，作失败，pre_e无定义。无定义。（求数据元素的前驱）（求数据元素的前驱）当不是第

7、一个元素时，则存在，否则不存在该元素或是表的第一个元素，无定义。第9页，共42页，编辑于2022年，星期六NextElem(L,cur_e,&next_e)初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在。已存在。若若 cur_e 是是 L 的元素，则用的元素，则用next_e 返回它的后继，否则操返回它的后继，否则操作失败，作失败，next_e无定义。无定义。（求数据元素的后继）（求数据元素的后继）第10页，共42页，编辑于2022年，星期六GetElem(L,i,&e)初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在，已存在，用用 e 返回返回L中第中第 i

8、 个元素的值。个元素的值。（求线性表中某个数据元素）（求线性表中某个数据元素）且且 1iLengthList(L)第11页，共42页，编辑于2022年，星期六LocateElem(L,e,compare()初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在，已存在，e e 为给定值，为给定值，compare()是元素判定函数。是元素判定函数。返回返回 L 中第中第 1 个与个与 e 满足关系满足关系 compare()的元素的的元素的位序位序。若这样的元素不存在，则返回值为若这样的元素不存在，则返回值为 0。（定位函数）（定位函数）第12页，共42页，编辑于2022年，星期六 L

9、istTraverse(L,visit()初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在。已存在。visit()为某个访问函数。为某个访问函数。依次依次对对 L 中中每个元素调用每个元素调用函数函数visit()。一旦。一旦 visit()失败，失败，则操作失败。则操作失败。（遍历线性表）（遍历线性表）引用性操作不改变原表的结构第13页，共42页，编辑于2022年，星期六ClearList(&L)初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在。已存在。将将 L 重置为空表。重置为空表。（线性表置空）（线性表置空）第14页，共42页，编辑于2022年，星期六P

10、utElem(&L,i,&e)初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在，已存在，L 中第中第 i 个元素赋值个元素赋值 e e。（改变数据元素的值）（改变数据元素的值）且且 1iLengthList(L)第15页，共42页，编辑于2022年，星期六 ListInsert(&L,i,e)初始条件：初始条件：操作结果：操作结果：线性表线性表 L 已存在已存在，在在 L 的第的第 i 个元素之前个元素之前插入插入新的元素新的元素 e，L 的长度增的长度增1。（插入数据元素）（插入数据元素）且且 1iLengthList(L)+1改变了元素之间的关系第16页，共42页，编辑于2

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

12、 表示，即：线性表示，即：线性表中的数据元素即为集合中的成员。表中的数据元素即为集合中的成员。现要求一个新的集合现要求一个新的集合AAB。例例 2-1 第19页，共42页，编辑于2022年，星期六 要求对线性表作如下操作：要求对线性表作如下操作：扩大线性表扩大线性表 LA，将，将存在于线性表存在于线性表LB 中中而而不存在于线性表不存在于线性表 LA 中中的数据元的数据元素素插入到线性表插入到线性表 LA 中中去。去。上述问题可演绎为：上述问题可演绎为：AUB，相同的元素只有一个A和B本身也是集合，所以各自不含有重复元素第20页，共42页，编辑于2022年，星期六1从线性表从线性表 LB 中依

13、次察看每个数据元素中依次察看每个数据元素;2依值在线性表依值在线性表 LA 中进行查访中进行查访;3若不存在，则插入之。若不存在，则插入之。GetElem(LB,i)e LocateElem(LA,e,equal()ListInsert(LA,n+1,e)(n 表示线性表表示线性表 LA 当前长度当前长度)操作步骤：操作步骤：第21页，共42页，编辑于2022年，星期六 GetElem(Lb,i,e);/取取Lb中第中第i个数据元素赋给个数据元素赋给e if(!LocateElem(La,e,equal()ListInsert(La,+La_len,e);/La中不存在和中不存在和 e 相同的

14、数据元素，则插入之相同的数据元素，则插入之 La_len=ListLength(La);/求线性表的长度求线性表的长度 Lb_len=ListLength(Lb);for(i=1;i n;Float*p;P=new floatn;Delete p;第28页，共42页，编辑于2022年，星期六例如：顺序表23 75 41 38 54 62 17L.elemL.length=7L.listsize第29页，共42页，编辑于2022年，星期六线性表操作 ListInsert(&L,i,e)的实现：首先分析首先分析:插入元素时，线性表的逻辑结构逻辑结构发生什么变化发生什么变化？第30页，共42页，编辑

15、于2022年，星期六(a1,ai-1,ai,an)改变为a1 a2 ai-1 ai ana1 a2 ai-1 ai ean,表的长度增加(a1,ai-1,e,ai,an)第31页，共42页，编辑于2022年，星期六21 18 30 75 42 56 8721 18 30 75例如：ListInsert(L,5,66)L.length-1087564266第32页，共42页，编辑于2022年，星期六void ListInsert(&L,i,e)/在线性表在线性表L中第中第i个位置插入元素个位置插入元素e if(iL.length+1)cout“插入序号错误插入序号错误”=ListSize)溢出处

16、理；溢出处理；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页，编辑于2022年，星期六算法分析算法分析 设表的长度为设表的长度为n。该算法的时间主要花费在循环的结点后移语句上，该算法的时间主要花费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）是该语句的执行次数（即移动结点的次数）是n-i+1。由此，所需移动结由此，所需移动结点的次数依赖于点的次数依赖于 (1)表的长度表的长度 (2)插入位置。插

17、入位置。当当=n+1时，不移动时，不移动-最好情况；最好情况；当当=1时，需移动表中所有结点时，需移动表中所有结点-最坏情况最坏情况，a1，a i-1，ai，anx x移动数据：移动数据：n-i+1n-i+1第34页，共42页，编辑于2022年，星期六算法的平均移动算法的平均移动 由于插入可能在表中任何位置上进行，在长度为由于插入可能在表中任何位置上进行，在长度为n的线的线性表中第性表中第i个位置上插入一个结点，令个位置上插入一个结点，令Eis(n)表示移动结点的表示移动结点的期望值（即移动的平均次数），则在第期望值（即移动的平均次数），则在第i个位置上插入一个个位置上插入一个结点的移动次数为

18、结点的移动次数为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+1n+1处处第35页，共42页，编辑于2022年，星期六结论：在顺序表上做插入运算，平均要结论：在顺序表上做插入运

19、算，平均要移动表上一移动表上一半结点半结点。当表长。当表长 n较大时，算法的效率相当低。较大时，算法的效率相当低。虽然虽然Eis(n)中中n的系数较小，但就数量级而言，它的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为仍然是线性阶的。因此算法的平均时间复杂度为O(n)。第36页，共42页，编辑于2022年，星期六线性表操作 ListDelete(&L,i,&e)的实现：首先分析：删除元素时，线性表的逻辑结构发生什么变化？第37页，共42页，编辑于2022年，星期六(a1,ai-1,ai,ai+1,an)改变为ai+1an,表的长度减少a1 a2 ai-1 ai ai+1

20、 ana1 a2 ai-1(a1,ai-1,ai+1,an)第38页，共42页，编辑于2022年，星期六21 18 30 75 42 56 8721 18 30 75L.length-108756例如：ListDelete(L,5,e)第39页，共42页，编辑于2022年，星期六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页，编辑于2022年，

21、星期六 算法分析与插入算法相似，结点的移动次数也是由表算法分析与插入算法相似，结点的移动次数也是由表长长n和位置和位置i决定。决定。若若i=n，无需移动结点；无需移动结点；若若i=1，则前移元素则前移元素n-1个个 令令Edl表示所需移动结点的平均次数，删除表中第表示所需移动结点的平均次数，删除表中第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 即在顺

22、序表上做删除运算，即在顺序表上做删除运算，平均要移动表中约一半的结平均要移动表中约一半的结点，点，平均时间复杂度也是平均时间复杂度也是O(n)。第41页，共42页，编辑于2022年，星期六顺序表总结顺序表总结1.是线性表的一种表示方法；是线性表的一种表示方法；2.是一组地址连续的存储空间；是一组地址连续的存储空间；3.可用一维数组类型描述，长度可变，数组需可用一维数组类型描述，长度可变，数组需动态分配；动态分配；优点：可对每个数据元素随机存取，表长是显值；优点：可对每个数据元素随机存取，表长是显值；缺点：在进行插入和删除元素时要进行元素移动，缺点：在进行插入和删除元素时要进行元素移动，大致移动表长一半的元素。大致移动表长一半的元素。第42页，共42页，编辑于2022年，星期六