Ch线性表顺序存储作业答案实用.pptx

《Ch线性表顺序存储作业答案实用.pptx》由会员分享，可在线阅读，更多相关《Ch线性表顺序存储作业答案实用.pptx（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1例例3、学生健康情况登记表如下：学生健康情况登记表如下：姓 名学 号性 别年龄 健康情况王小林790631 男 18 健康陈 红790632 女 20 一般刘建平790633 男 21 健康张立立790634 男 17 神经衰弱.第1页/共26页2 从以上例子可看出线性表的逻辑特征是：在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋a n-1；其余的内部结点ai(2in-1)都有且仅有一个直接前趋a i-1和一个直接后继a i+1。线性表的逻辑特征第2页/共26页3ADT 线性表的定义线性表是一种典

2、型的线性结构。抽象数据类型线性表的定义如下ADT List data object:D=ai|ai ElemSet,i=1,2,n,n0 data relation:R=|ai-1,ai D,i=2,n basic operation:InitList(L)构造一个空的线性表DestroyList(L)销毁已存在的线性表第3页/共26页4第4页/共26页5 例1 利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=AB。void union(List&La，List Lb)La-len=listlength(La);Lb-len=listlength(Lb);for(I=1;

3、I=lb-len;I+)getelem(Lb，I，e);if(!locateelem(La，e，equal)listinsert(la，+la-en，e)ADT线性表的应用第5页/共26页6 例2 巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。此问题的算法如下：第6页/共26页7void mergelist(list la，list lb，list&lc)initlist(lc);I=j=1;k=0;la-len=listlength(la);lb-len=listlength(lb);while(I=

4、la-len)&(j=lb-len)getelem(la，I，ai);getelem(lb，j，bj);if(ai=bj)listinsert(lc，+k，ai);+I;elselistinsert(lc，+k，bj);+j;第7页/共26页8 while(I=la-len)getelem(la，I+，ai);listinsert(lc，+k，ai);while(j=lb-len)getelem(lb，j+，bj);listinsert(lc，+k，bi);第8页/共26页9 2.2.1 线性表的顺序表示 线性表的顺序表示：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法

5、存储的线性表简称顺序表。如何计算数据元素的存储位置？假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(a i+1)和第i个数据元素的存储位置LOC(a i )之间满足下列关系：LOC(a i+1)=LOC(a i)+l 线性表的第i个数据元素ai的存储位置为：LOC(ai)=LOC(a1)+(i-1)*l 2.2 线性表的顺序存储结构第9页/共26页10 由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长

6、度属性，所以我们用结构类型来定义顺序表类型。#define ListSize 100 typedef ElemType DataType;typedef struc DataType dataListSize;int length;Sqlist;第10页/共26页11在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第i个元素的访问。注意：C语言中的数组下标从“0”开始，因此，若L是Sqlist类型的顺序表，则表中第i个元素是L.dataI-1。以下主要讨论线性表的插入和删除两种运算。1、插入 线性表的插入运算是指在表的第I(1in+1个位置上，插入一个新结点x，2.2.2 顺序

7、表上实现的基本操作第11页/共26页12使长度为n的线性表 (a1，a i-1，ai，an)变成长度为n+1的线性表 (a1，a i-1，x，ai，an)第12页/共26页13算法 线性表插入操作Void InsertList(Sqlist&L，DataType x，int I)int j;if(IL.length+1)printf(“Position error”);return ERROR第13页/共26页14 if(L.length=ListSize)printf(“overflow”);exit(overflow);for(j=L.length-1;j=I-1;j-)L.dataj+1

8、=L.dataj;L.dataI-1=x;L.length+;第14页/共26页15 这里的问题规模是表的长度，设它的值为n。该算法的时间主要化费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）是n-i+1。由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。当”插入”操作在表尾进行时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度O（1）；当”插入”操作在表头进行时，结点后移语句将循环执行n次，需移动表中所有结点，这是最坏情况，其时间复杂度为O（n）。算法的复杂度分析第15页/共26页16由于插入可能在表中任何位置上进行，因此需分

9、析算法的平均复杂度。在长度为n的线性表中第i个位置上插入一个结点，令Eis(n)表示移动结点的期望值（即移动的平均次数），则在第i个位置上插入一个结点的移动次数为n-i+1。故 Eis(n)=pi(n-i+1)不失一般性，假设在表中任何位置(1in+1)上插入结点的机会是均等的，则 p1=p2=p3=p n+1=1/(n+1)因此，在等概率插入的情况下，Eis(n)=(n-i+1)/(n+1)=n/2 第16页/共26页17 也就是说，在顺序表上做插入运算，平均要移动表上一半结点。当表长 n较大时，算法的效率相当低。虽然Eis(n)中n的的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的

10、平均时间复杂度为O(n)。第17页/共26页182、删除 线性表的删除运算是指将表的第i(1in)结点删除，使长度为n的线性表：(a1，a i-1，ai，a i+1，an)变成长度为n-1的线性表 (a1，a i-1，a i+1，an)第18页/共26页19算法 线性表删除操作Void deleteList(Sqlist&L，int I)int j;if(IL.length)printf(“Position error”);return ERROR；for(j=i;j=L.length-1;j+)l.dataj-1=l.dataj;l.length-;第19页/共26页20 该算法的时间分析与

11、插入算法相似，结点的移动次数也是由表长n和位置i决定。若i=n，则由于循环变量的初值大于终值，前移语句将不执行，无需移动结点；若i=1，则前移语句将循环执行n-1次，需移动表中除开始结点外的所有结点。这两种情况下算法的时间复杂度分别为O(1)和O(n)。删除算法的平均性能分析与插入算法相似。在长度为n的线性表中删除一个结点，令Ede(n)表示所需移动结点的平均次数，删除表中第i个结点的移动次数为n-i，故 Ede(n)=Pi(n-I)式中，Pi表示删除表中第i个结点的概率。算法的复杂度分析第20页/共26页21 在等概率的假设下，p1=p2=p3=pn=1/n 由此可得：Ede(n)=(n-I

12、)/n=(n-1)/2 即在顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是O(n)。第21页/共26页22小结：顺序存储方式的优缺点优点：.在节点等长时可以随机存取。存储密度高，节省存储空间。用结点的物理次序反映结点之间的逻辑关系。缺点：插入和删除结点时需要移动大量的结点。必须静态分配连续的空间。第22页/共26页23顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（）。【解答】108 在一个长度为n的顺序表的第i（1in+1）个元素之前插入一个元素，需向后移动（）个元素，删除第i（1in）个元素时，需向前移动（）个元素。【解答】n-i+1，n-i 作业 第23页/共26页24当线性表采用顺序存储结构时，其主要特点是（）。【解答】逻辑结构中相邻的结点在存储结构中仍相邻 第24页/共26页25 4.试写一个删除算法 Void elete_seq(Sqlist，ElemType x),在顺序表list中，删除一个值为的元素，返回删除成功与否的标志。第25页/共26页26感谢您的欣赏！第26页/共26页