数据结构线性表顺序表精选PPT.ppt

《数据结构线性表顺序表精选PPT.ppt》由会员分享，可在线阅读，更多相关《数据结构线性表顺序表精选PPT.ppt（48页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于数据结构线性表顺序表第1页，讲稿共48张，创作于星期二线性结构四大特点第一个元素无直接前驱第一个元素无直接前驱最后一个元素无直接后继最后一个元素无直接后继除第一个元素外，其他每个数据元素除第一个元素外，其他每个数据元素都有唯一一个直接前驱都有唯一一个直接前驱除最后一个元素外，其他每个数据元素除最后一个元素外，其他每个数据元素都有唯一一个直接后面都有唯一一个直接后面第2页，讲稿共48张，创作于星期二线性表定义定义记法记法特点特点结构结构基本术语基本术语空表、表长直接前驱、直接后继位序最基本、最常用的线性结构。若最基本、最常用的线性结构。若n(nn(n0)个数据个数据特性相同的数据元素组成的有

2、限序列。特性相同的数据元素组成的有限序列。（a1,a2,ai-1,ai,ai+1,an)1.同一线性表中的数据元素必须具有相同特性2.具有线性结构的四大特性3.数据元素之间存在序偶关系逻辑结构（1对1）、物理结构（顺序存储和链式存储）第3页，讲稿共48张，创作于星期二线性表的抽象数据类型数据对象数据对象数据关系数据关系操作集操作集初始化、销毁、查找、插入、删除、求前驱（后继）、遍历线性表中的数据元素具有相同特性线性表中的数据元素具有相同特性相邻数据元素之间存在序偶关系相邻数据元素之间存在序偶关系线性表的基本操作声明线性表的基本操作声明仅是模型定义，不涉及模型实现，参数不必考虑具体仅是模型定义，

3、不涉及模型实现，参数不必考虑具体数据类型，实际应用中，具体问题具体分析。数据类型，实际应用中，具体问题具体分析。第4页，讲稿共48张，创作于星期二顺序表定义定义特点特点C C描述描述基本形态基本形态基本操作实现基本操作实现用一组地址连续地址连续的存储单元依次存放依次存放线性表中的数据元素。采用这种存储结构的线性表叫做顺序表顺序表。a1 a2 ai-1 ai an基地址基地址1.数据元素在“逻辑逻辑关系上的相邻相邻”用“物理地址相邻物理地址相邻”来表示。2.顺序表中任一元素都可“随机存取随机存取”。第5页，讲稿共48张，创作于星期二typedef struct SqList;/俗称 顺序表顺序表

4、#define MAXSIZE 100 /线性表存储空间的分配量，即数组长度ElemType elemMAXSIZE;int length;/当前长度顺序表的C描述第6页，讲稿共48张，创作于星期二顺序表空：条件顺序表空：条件 L.length=0 不允许删除操作顺序表满：顺序表满：条件 L.length=MAXSIZE 不允许插入操作不空也不满：不空也不满：可以插入，删除操作顺序表的基本形态第7页，讲稿共48张，创作于星期二顺序表-基本算法根据顺序表的实现形式，表长根据顺序表的实现形式，表长length是类型定义的属性，是类型定义的属性，可以实现求表长、初始化、取值、判空等操作，时间可以实现

5、求表长、初始化、取值、判空等操作，时间复杂度均为复杂度均为O(1)。而遍历算法、查找表中元素的存在、插入、删除等操而遍历算法、查找表中元素的存在、插入、删除等操作，时间复杂度均为作，时间复杂度均为O(n)。第8页，讲稿共48张，创作于星期二（1）初始化空表时间复杂为：O(1)顺序表-基本算法L.length=0；第9页，讲稿共48张，创作于星期二（2）判空时间复杂为：O(1)顺序表-基本算法if(L.length=0)return OK;else return ERROR;第10页，讲稿共48张，创作于星期二（3）求表长时间复杂为：O(1)顺序表-基本算法return L.length；第11

6、页，讲稿共48张，创作于星期二（4）取元素（取第i个元素e）时间复杂为：O(1)顺序表-基本算法e=L.elemi-1;i合法if(i=1&i=L.length)e=L.elemi-1;return OK;else return ERROR;第12页，讲稿共48张，创作于星期二顺序表-基本算法（5）遍历for(i=1;i=L.length;i+)visit(L.elemi-1);时间复杂为：O(L.length)第13页，讲稿共48张，创作于星期二顺序表-基本算法（6）查找搜索顺序表中是否存在指定的数据元素。存在，查找成功；否则，查找失败。第14页，讲稿共48张，创作于星期二例如：顺序表23

7、75 41 38 54 62 17L.elem0L.length-1e=38i12341 850可见，基本操作是：将顺序表中的元素逐个和给定值 e 相比较。第15页，讲稿共48张，创作于星期二算法的算法的时间复杂度时间复杂度为：为：O(L.length)int LocateElem(SqList L,Elemtype e)for(i=1;i=L.length;i+)if(e=L.elemi-1)return i;return 0;第16页，讲稿共48张，创作于星期二顺序表-基本算法（7）插入在顺序表中插入指定的数据元素，插入成功，表长增1。第17页，讲稿共48张，创作于星期二线性表操作 Lis

8、tInsert(&L,i,e)的实现：首先分析首先分析:插入元素时，线性表的逻辑结构逻辑结构发生什么变化发生什么变化？第18页，讲稿共48张，创作于星期二(a1,ai-1,ai,an)改变为 (a1,ai-1,e,ai,an)a1 a2 ai-1 ai ana1 a2 ai-1 ai ean,表的长度增加第19页，讲稿共48张，创作于星期二必备条件：表存在且不满i值的合法性检查：1L.length+1将第i个到最后1个元素依次后移一个位置；在i个位置插入元素；表长增加1。分析分析：第20页，讲稿共48张，创作于星期二21 18 30 75 42 56 8721 18 30 75例如：ListI

9、nsert_Sq(L,5,66)L.length-1087564266第21页，讲稿共48张，创作于星期二O(L.length)算法的算法的时间复杂度时间复杂度为：为：Status ListInsert(SqList&L,int i,ElemType e)if(i=1&i=i;j-)/元素后移L.elemj=L.elemj-1;L.elemi-1=e;/插入e L.length+;/表长增1 return OK;/插入成功 elsereturn ERROR;第22页，讲稿共48张，创作于星期二插入算法时间复杂度分析：插入算法时间复杂度分析：考虑移动元素的平均情况考虑移动元素的平均情况插入位置插

10、入位置需要移动的结点次数需要移动的结点次数1n2n-1n1n+10平均次数平均次数:(1+2+n-1+n)/(n+1)=n/2T(n)=O(n)第23页，讲稿共48张，创作于星期二顺序表-基本算法（8）删除在顺序表中删除指定位置的数据元素，删除成功，表长减1。第24页，讲稿共48张，创作于星期二线性表操作 ListDelete(&L,i,&e)的实现：首先分析：删除元素时，线性表的逻辑结构发生什么变化？第25页，讲稿共48张，创作于星期二(a1,ai-1,ai,ai+1,an)改变为 (a1,ai-1,ai+1,an)ai+1 an,表的长度减少a1 a2 ai-1 ai ai+1 ana1

11、a2 ai-1 第26页，讲稿共48张，创作于星期二必备条件：表非空i值的合法性检查：1L.length取出第i个元素；第i个元素以后的元素向前移动一个位置；表长减小1。分析分析：第27页，讲稿共48张，创作于星期二21 18 30 75 42 56 8721 18 30 75L.length-10pppq8756例如：ListDelete_Sq(L,5,e)p第28页，讲稿共48张，创作于星期二算法时间复杂度为算法时间复杂度为:O(L.length)Status ListDelete(SqList&L,int i,ElemType&e)if(i=1&i=L.length)e=L.elemi-

12、1;for(j=i+1;j=L.length;j+)/元素前移L.elemj-2=L.elemj-1;L.length-;/表长减1 return OK;/删除成功 elsereturn ERROR;第29页，讲稿共48张，创作于星期二 删除算法时间复杂度分析：删除算法时间复杂度分析：考虑移动元素的平均情况考虑移动元素的平均情况删除位置删除位置需要移动的结点次数需要移动的结点次数1n-12n-2n0平均次数平均次数:(0+1+n-11)/n=(n-1)/2T(n)=O(n)第30页，讲稿共48张，创作于星期二时间复杂度为O(1)顺序表-基本算法（9）求前驱pre=L.elemi-2;在顺序表中

13、查找元素cur_e，位序为ii=LocateElem(L,cur_e);cur_e是顺序表中元素，但不是第一个元素便有直接前驱pre第31页，讲稿共48张，创作于星期二 顺序表-基本算法（10）求后继next=L.elemi;在顺序表中查找元素cur_e，位序为ii=LocateElem(L,cur_e);cur_e是顺序表中元素，但不是最后一个元素便有直接后继next时间复杂度为O(1)第32页，讲稿共48张，创作于星期二顺序表-经典算法分析算法插入删除基本操作移动元素移动元素平均移动次数时间复杂度O(n)O(n)O(n)O(n)最好情况在n+1处插入，不需移动删除第n个，不需移动第33页，

14、讲稿共48张，创作于星期二线性表应用举例例例1 1：合并线性表：合并线性表例例2 2：归并线性表：归并线性表第34页，讲稿共48张，创作于星期二例1：合并线性表假设有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合AAB。去掉重复元素去掉重复元素第35页，讲稿共48张，创作于星期二扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。问题分析问题分析：第36页，讲稿共48张，创作于星期二1从线性表LB中依次取得每个数据元素;2依值在线性表LA中进行查访;3若不存在，则插入之。GetEle

15、m(LB,i)e LocateElem(LA,e,equal()ListInsert(LA,n+1,e)操作步骤：操作步骤：第37页，讲稿共48张，创作于星期二 GetElem(Lb,i,e);/取取Lb中第中第i个数据元素赋给个数据元素赋给e if(!LocateElem(La,e,equal()ListInsert(La,+La_len,e);/La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之void union(List&La,List Lb)La_len=ListLength(La);/求线性表的长度求线性表的长度 Lb_len=ListLength(Lb

16、);for(i=1;i=Lb_len;i+)/union第38页，讲稿共48张，创作于星期二算法分析时间复杂度：时间复杂度：O(O(ListLength(LA)ListLength(LA)*ListLength(LB)ListLength(LB)空间复杂度：空间复杂度：O(O(1 1)第39页，讲稿共48张，创作于星期二例2：归并线性表已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列。不去掉重复元素不去掉重复元素第40页，讲稿共48张，创作于星期二 LC中的数据元素或是LA中的数据元素，或是LB中的数据元素。

17、则先设LC为空表，然后将LA或LB中的元素逐个插入到LC中。为使LC表按值非递减有序排列，可设两个整型变量i、j，分别指向LA和LB，比较i、j所指元素的大小，决定哪个元素插入LC。插入后，在LA 或LB 中顺序后移。问题分析问题分析：第41页，讲稿共48张，创作于星期二void MergeList(List La,List Lb,List&Lc)/本算法将非递减的有序表 La 和 Lb 归并为 Lc/merge_listwhile(i=La_len)&(j=Lb_len)/La 和 Lb 均不空 while(i=La_len)/若 La 不空while(j=Lb_len)/若 Lb 不空In

18、itList(Lc);/构造空的线性表 Lci=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);第42页，讲稿共48张，创作于星期二 GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai=bj)ListInsert(Lc,+k,ai);+i;else ListInsert(Lc,+k,bj);+j;第43页，讲稿共48张，创作于星期二 while(i=La_len)/当La不空时 GetElem(La,i+,ai);ListInsert(Lc,+k,ai);/插入插入 La 表中剩余元素表中剩余元素 while(

19、j=Lb_len)/当Lb不空时 GetElem(Lb,j+,bj);ListInsert(Lc,+k,bj);/插入插入 Lb 表中剩余元素表中剩余元素第44页，讲稿共48张，创作于星期二算法分析时间复杂度：时间复杂度：O(O(ListLength(LA)ListLength(LA)+ListLength(LB)ListLength(LB)空间复杂度：空间复杂度：O(O(ListLength(LA)ListLength(LA)+ListLength(LB)ListLength(LB)第45页，讲稿共48张，创作于星期二void MergeList(SqList La,SqList Lb,Sq

20、List&Lc)pa=La.elem;pb=Lb.elem;Lc.length=La.length+Lb.length;pc=Lc.elem;pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;while(pa=pa_last&pb=pb_last)if(*pa=*pb)*pc+=*pa+;else*pc+=*pb+;while(pa=pa_last)*pc+=*pa+;while(pb=pb_last)*pc+=*pb+;if(*pa*pb)*pc+=*pa+;else if(*pa=*pb)*pc+=*pa+;pb+;else*pc+=*pb+;第46页，讲稿共48张，创作于星期二一元多项式Pn(x)=p0+p1x+p2x2+p3x3+pnxnQn(x)=q0+q1x+q2x2+q3x3+qmxm其中系数组成的线性表其中系数组成的线性表P=(p0,p1,p2,p3,pn)系数pi的序号为每一项的指数i其中系数组成的线性表其中系数组成的线性表Q=(q0,q1,q2,q3,qm)第47页，讲稿共48张，创作于星期二感谢大家观看第48页，讲稿共48张，创作于星期二