数据结构与算法设计幻灯片.ppt
《数据结构与算法设计幻灯片.ppt》由会员分享,可在线阅读,更多相关《数据结构与算法设计幻灯片.ppt(99页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、数据结构与算法设计课件第1页,共99页,编辑于2022年,星期六线性表是一种最简单的线性结构。什么是线性结构?简单地说,线性结构线性结构是一个数是一个数据元素的有序(次序)集合。它有四个基本特征:据元素的有序(次序)集合。它有四个基本特征:1集合中必存在唯一的一个集合中必存在唯一的一个第一元素第一元素;2集合中必存在唯一的一个集合中必存在唯一的一个最后元素最后元素;3除最后元素之外,其它数据元素均有唯一的除最后元素之外,其它数据元素均有唯一的后继后继;4除第一元素之外,其它数据元素均有唯一的除第一元素之外,其它数据元素均有唯一的前驱前驱。第2页,共99页,编辑于2022年,星期六2.1.1 抽
2、象数据类型线性表的定义抽象数据类型线性表的定义通常可以下列“n个数据元素的序列”表示线性表线性表(Linear_List)(a1,a2,.,ai,.,an)序列中数据元素的个数n定义为线性表的表长;n=0时的线性表被称为空表。称i为ai在线性表中的位序。其抽象数据类型的定义如下:ADT List 数据对象:数据对象:Dai|aiElemSet,i=1,2,.,n,n0数据关系:数据关系:R1|,D,i=2,.,n第3页,共99页,编辑于2022年,星期六基本操作:基本操作:结构初始化结构初始化InitList(&L)操作结果:构造一个空的线性表L。销毁结构销毁结构DestroyList(&L)
3、初始条件:线性表L已存在。操作结果:销毁线性表L。第4页,共99页,编辑于2022年,星期六引用型操作引用型操作ListEmpty(L)初始条件:线性表L已存在。操作结果:若L为空表,则返回TRUE,否则返回FALSE。ListLength(L)初始条件:线性表L已存在。操作结果:返回L中元素个数。PriorElem(L,cur_e,&pre_e)初始条件:线性表L已存在。操作结果:若cur_e是L中的数据元素,则用pre_e返回它的前驱,否则操作失败,pre_e无定义。第5页,共99页,编辑于2022年,星期六NextElem(L,cur_e,&next_e)初始条件:线性表L已存在。操作结
4、果:若cur_e是L中的数据元素,则用next_e返回它的后继,否则操作失败,next_e无定义。GetElem(L,i,&e)初始条件:线性表L已存在,1iLengthList(L)。操作结果:用e返回L中第i个元素的值。第6页,共99页,编辑于2022年,星期六LocateElem(L,e,compare()初始条件:线性表L已存在,compare()是元素判定函数。操作结果:返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在,则返回值为0。ListTraverse(L,visit()初始条件:线性表L已存在,visit()为元素的访问函数。操作结果:依次对L的每
5、个元素调用函数visit()。一旦visit()失败,则操作失败。第7页,共99页,编辑于2022年,星期六加工型操作加工型操作ClearList(&L)初始条件:线性表初始条件:线性表 L 已存在。已存在。操作结果:将操作结果:将 L 重置为空表。重置为空表。PutElem(&L,i,&e)初始条件:线性表初始条件:线性表L已存在,已存在,1iLengthList(L)。操作结果:操作结果:L 中第中第 i 个元素赋值同个元素赋值同 e 的值。的值。第8页,共99页,编辑于2022年,星期六ListInsert(&L,i,e)初始条件:线性表L已存在,1iLengthList(L)+1。操作
6、结果:在L的第i个元素之前插入新的元素e,L的长度增1。ListDelete(&L,i,&e)初始条件:线性表L已存在且非空,1iLengthList(L)。操作结果:删除删除 L的第i个元素,并用e返回其值,L的长度减长度减1。ADT List第9页,共99页,编辑于2022年,星期六2.1.2 2.1.2 线性表类型的应用线性表类型的应用 如果已经实现了上述定义的线性表类型,那么在应用问题的求解中就可以利用类型中定义的各种操作。下面将举三个例子说明之。第10页,共99页,编辑于2022年,星期六例例2-12-1 已知集合 A 和 B,求两个集合的并集,使 AAB,且 B 不再单独存在。从集
7、合的观点看,此问题求解的方法很简单,只要对集合 B 中的所有元素一个一个地检查,看看在集合 A 中是否存在相同元素,若不存在,则将该元素插入到集合 A,否则舍弃之。要在计算机中求解,首先要确定如何表示集合。集合可以有多种表示方法,对上述集合求并的问题可以用线性表表示集合。现假设以线性表 LA 和 LB 分别表示集合 A 和 B,即构造两个线性表 LA 和 LB,它们的数据元素分别为集合 A 和 B 中的成员。由此,上述集合求并的问题便可演绎为:要求对线性表作如下操作:扩大线性表 LA,将存在于存在于线性表线性表 LB LB 中中而不存在于线性表不存在于线性表 LA LA 中中的数据元素插入到线
8、性表插入到线性表 LA LA 中中去。第11页,共99页,编辑于2022年,星期六具体操作步骤为:1从线性表 LB 中取出一个数据元素;2依值在线性表 LA 中进行查询;3若不存在,则将它插入到 LA 中。重复上述三步直至 LB 为空表止。那么,其中的每一步能否利用上述线性表类型中定义的基本操作来完成呢?第12页,共99页,编辑于2022年,星期六容易看出,上述的每一步恰好对应线性表的一个基本操作:1.ListDelete(LB,1,e);2.LocateElem(LA,e,equal();3.ListInsert(LA,n+1,e)第13页,共99页,编辑于2022年,星期六由此得到求并集的
9、算法如下所示:算法算法2.12.1voidvoid union(List&LA,List&LB)/将所有在线性表将所有在线性表LBLB中但不在中但不在LALA中的数据元素插入到中的数据元素插入到 LA LA 中中,算法执行之后,线性表算法执行之后,线性表 LB LB 不再存在。不再存在。La_len=ListLength(LA);/求得线性表 LA 的长度whilewhile(!ListEmpty(LB)/依次处理 LB 中元素直至 LB 为空表止 ListDelete(LB,1,e);/从 LB 中删除第1个数据元素并赋给 e ifif(!LocateElem(LA,e,equal()Lis
10、tInsert(LA,+La_len,e);/当LA中不存在和 e 值相同的数据元素时进行插入 /whileDestroyList(LB);/销毁线性表 LB)/union第14页,共99页,编辑于2022年,星期六例例2-22-2 已知一个非纯集合 B,试构造一个集合 A,使 A 中只包含 B 中所有值各不相同的数据元素。换句话说,此问题即为从 B 中挑选出所有彼此相异的元素构成一个新的集合。如何区分元素的相异或相同,一个简单方法即为将每个从 B 中取出的元素和已经加入到集合 A 中的元素相比较。如果还是以线性表 LB 和 LA 分别表示集合 B 和 A,那么和例2-1的问题相比,此问题求解
11、的算法应该如何写呢?第15页,共99页,编辑于2022年,星期六容易看出,应对线性表作和上例相同的操作,具体的三步也都相同,所不同之处仅仅在于所不同之处仅仅在于两点:两点:一是例2-1的算法中 LA 是已知的,而在此例算法中的 LA 是待新建的;二是例2-1在求得并集之后,原来的两个集合不再保留,而在此例中构建新的集合 A 的同时,原来的集合 B 不变。第16页,共99页,编辑于2022年,星期六算法算法2.22.2voidvoid purge(List&LA,List LB)/构造线性表构造线性表LALA,使其只包含使其只包含LBLB中所有值不相同的数据中所有值不相同的数据/元素元素,算法不
12、改变线性表算法不改变线性表LBLB InitList(LA);/创建一个空的线性表 LA La_len=0;Lb_len=ListLength(LB);/求线性表 LB 的长度 forfor(i=1;i=Lb_len;i+)/依次处理 LB 中每个元素 GetElem(LB,i,e);/取 LB 中第 i 个数据元素赋给 eifif(!LocateElem(LA,e,equal()ListInsert(LA,+La_len,e);/当 LA 中不存在和 e 值相同的数据元素时进行插入 /for)/purge第17页,共99页,编辑于2022年,星期六例例2-32-3 判别两个集合是否相等。两个
13、集合相等的充分必要条件是它们具有相同的元素。当以线性表表示集合时,两个线性表的长度应该相等,且表中所有数据元素都能一一对应,但相同的数据元素在各自的线性表中的位序不一定相同。由此,判别两个线性表中的数据元素是否完全相同的算法的基本思想为:首先判别两者的表长是否相等;在表长相等的前提下,如果对于一个表中的所有元素,都能在另一个表中找到和它相等的元素的话,便可得到两个线性表表示的集合相等的结论;反之,只要有一个元素在另一个表中不能找到相等元素时,便可得出不等的结论。第18页,共99页,编辑于2022年,星期六算法算法2.32.3boolbool isEqual(List LA,List LB)/若
14、线性表若线性表 LA LA 和和 LB LB 不仅长度相等,且所含数据元素也相同,不仅长度相等,且所含数据元素也相同,/则返回则返回 TRUETRUE,否则返回否则返回 FALSEFALSE。La_len=Listlength(LA);Lb_len=Listlength(LB);ifif(La_len!=Lb_len)returnreturn FALSEFALSE;/两表的长度不等 elseelse i=1;found=TRUETRUE;whilewhile(i=La_len&found)GetElem(LA,i,e);/取得 LA 中一个元素 ifif(LocateElem(LB,e,equ
15、al()i+;/依次处理下一个 elseelse found=FALSEFALSE;/LB中没有和该元素相同的元素 /whilereturnreturn found;/else)/isEqual第19页,共99页,编辑于2022年,星期六2.2.1 2.2.1 顺序表顺序表顺序表顺序表是线性表的顺序存储表示的简称,它指的是,“用一组地址连续地址连续的存储单元依次存放依次存放线性表中的数据元素”,即以“存储位置相邻存储位置相邻”表示“位序相继的两个数据元素之间的前驱和后继的关系(有序对)”,并以表中第一个元素的存储位置作为线性表的起始地址,称作线线性表的基地址性表的基地址。如下图所示。第20页,
16、共99页,编辑于2022年,星期六 不失一般性,假设每个数据元素占据的存储量是一个常量 C,则后继元素的存储地址和其前驱元素相隔一个常量,即:LOC(ai)=LOC(ai-1)+C C 一个数据元素所占存储量由此,所有数据元素的存储位置均可由第一个数据元素的存储位置得到 LOC(ai)=LOC(a1)+(i-1)C 基地址基地址第21页,共99页,编辑于2022年,星期六用C语言描述的顺序表类型顺序表类型如下所示:/存储结构存储结构constconst intint MAXLISTSIZE=80;/预设的存储空间最大容量typedef struct typedef struct ElemTyp
17、e*elem;/存储空间基址 intint length;/当前长度 intint listsize;/允许的最大存储容量(以sizeofsizeof(ElemType)为单位)SqList;/俗称 顺序表顺序表第22页,共99页,编辑于2022年,星期六/基本操作接口基本操作接口(函数声明函数声明)voidvoid InitList(SqList&L,intint maxsize);/构造一个最大存储容量为 maxsize 的空的顺序表 L。void void DestroyList(SqList&L)/销毁顺序表 L。boolbool ListEmpty(SqList L)/若顺序表 L
18、为空表,则返回TRUETRUE,否则返回 FALSEFALSE。intint ListLength(SqList L)/返回顺序表 L 中元素个数。intint PriorElem(SqList L,ElemType cur_e)/若 cur_e 是顺序表 L 的元素,则返回其前驱的位序/(设第一个元素的前驱的位序为0),否则返回-1。第23页,共99页,编辑于2022年,星期六intint NextElem(SqList L,ElemType cur_e)/若 cur_e 是顺序表 L 的元素,则返回其后继的位序/(设最后一个元素的后继的位序为L的表长+1),否则返回-1。boolbool
19、GetElem(SqList L,intint pos,ElemType&e)/若11posLengthList(L)posLengthList(L),则用 e 带回顺序表 L 中第 /pos个元素的值且返回函数值为TRUETRUE,否则返回函数值为FALSEFALSE。intint LocateElem(SqList L,ElemType e,boolbool(*compare)(ElemType,ElemType)/返回顺序表L中第第1 1个个与 e 满足满足关系 compare()的数据元素的位序。/若这样的元素不存在,则返回值为0。compare()为数据元素的判定函数。voidvoi
20、d ListTraverse(SqList L,voidvoid(*visit)(ElemType)/依次依次对顺序表 L 的每个元素调用函数 visit()。/一旦 visit()失败,则操作失败。voidvoid ClearList(SqList&L)/将顺序表 L 重置为空表。第24页,共99页,编辑于2022年,星期六boolbool PutElem(SqList L,intint pos,ElemType&e)/若1 1posposLengthList(L)LengthList(L),则对顺序表 L 中第 pos 个元素/赋值同 e 的值且返回函数值为 TRUE,否则返回函数值为 F
21、ALSE。boolbool ListInsert(SqList&L,intint pos,ElemType e)/若存储空间未满且1 1posposLengthList(L)+1LengthList(L)+1,则在顺序表 L 的/第 pos 个元素之前插入新的元素 e,L的长度增1,且返回函数值为TRUE,/否则不改变顺序表且返回函数值为 FALSE。boolbool ListDelete(SqList&L,intint pos,ElemType&e)/若1 1posposLengthList(L)LengthList(L),则删除顺序表 L 的第 pos 个元素 e,/L的长度增1,且返回函
22、数值为TRUE,否则不改变顺序表且返回函数值为FALSE。第25页,共99页,编辑于2022年,星期六以上定义的函数可在程序设计中引用,例如,上述算法算法2.22.2可改写为下列可在主函数中调用的函数。voidvoid purge(SqList&La,SqList Lb)/构造顺序表构造顺序表 LaLa,使其只包含使其只包含 Lb Lb 中所有值不相同的数据元素中所有值不相同的数据元素,/算法不改变顺序表算法不改变顺序表 Lb Lb boolbool b;intint Lb_len=Listlength(Lb);/求线性表 Lb 的长度 InitList(La,Lb_len);/创建一个空的线
23、性表 Laintint La_len=0;forfor(i=1;i=Lb_len;i+)/依次处理 Lb 中每个元素 b=GetElem(Lb,i,e);/取Lb中第 i 个数据元素赋给 eifif(!LocateElem(La,e,equal()+La_len;b=ListInsert(La,La_len,e);/当 La 中不存在和 e 值相同的 /数据元素时,进行插入 /for第26页,共99页,编辑于2022年,星期六2.2.2 2.2.2 顺序表中基本操作的实现顺序表中基本操作的实现从顺序表的存储结构定义容易看出,由于顺序表的长度是个显值,且由于第i个元素恰好存储在数组的第 i 个分
24、量(数组下标为 i-1)中,因此其求长、判空以及存取第 i 个数据元素等操作都很容易实现。下面重点讨论顺序表类型定义中五个操作的实现。一、初始化操作一、初始化操作二、元素定位操作二、元素定位操作三、插入元素操作三、插入元素操作四、删除元素操作四、删除元素操作五、销毁结构操作五、销毁结构操作第27页,共99页,编辑于2022年,星期六一、初始化操作一、初始化操作对顺序表而言,初始化的实质是为它分配一个足够应用的元素存储空间,由用户根据它对线性表的使用要求定义一个最大存储容量 maxsize,并约定当用户没有提出特殊需求(maxsize=0)时,按予设的最大存储量 MAXLISTSIZE 进行分配
25、。第28页,共99页,编辑于2022年,星期六算法算法2.42.4voidvoid InitList(SqList&L,intint maxsize)/构造一个空的线性表构造一个空的线性表 L Lifif(maxsize=0)maxsize=MAXLISTSIZE;L.elem=newnew ElemTypemaxsize;if if(!L.elem)exitexit(1);/存储分配失败L.length=0;/顺序表的初始长度为0L.listsize=maxsize;/该顺序表可以存储元素的最大容量 /InitList此算法的时间复杂度为O O(1)(1)。第29页,共99页,编辑于2022
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 算法 设计 幻灯片
限制150内