专题三 数据结构与算法.ppt

《专题三 数据结构与算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、查找与排序专题三数据结构与控制算法分析学习内容与要求学习和掌握顺序查找和折半查找算法的原理和实现；学习和掌握二叉排序树的概念及其构造方法、二叉排序树的查找算法原理。学习和掌握选择排序、交换排序、插入排序、归并排序和快速排序方法的原理。第2页1Search(查找/搜索)第3页第4页所谓查找（或搜索），就是在数据集合中寻找满足某种条件的数据对象:1.查找成功即找到满足条件的数据对象时,作为结果,可报告该对象在结构中的位置,还可给出该对象中的具体信息。2.查找不成功或搜索失败。作为结果,应报告一些信息,如失败标志、位置

2、等。通常称用于查找的数据集合为查找结构，它是由同一数据类型的数据(或记录)组成。每个对象有若干属性，其中有一个属性，其值可唯一地标识这个对象，称为关键字。使用基于关键字的搜索，查找结果应是唯一的。但在实际应用时，查找条件是多方面的，可以使用基于属性的查找方法，但查找结果可能不唯一。第5页实施查找时有两种不同的环境静态环境查找结构不需进行插入和删除操作。静态查找表第6页动态环境查找过程中可能要对查找结构执行数据插入、删除或修改等操作，并对查找结构进行调整，结构可能发生变化。动态查找表动态查找表的表结构是在查找过

3、程中动态生成的。第7页以线性结构表示静态查找表。基本原理：将待查找记录依次逐个与表中记录进行比较。1.1顺序查找（SequentialSearch)第8页SL.elem顺序查找过程（从前向后查找）假设给定查找值e=64,要求SL.elem[k]=e,问:k=?kk第9页SL.elemiSL.elemi60ikey=64key=60i64顺序查找过程（从后向前查找）0单元用于存放待查找关键字，作为“哨兵”(guard)返回0返回7第10页intSearch_Seq(TBSL,TYPEkey){SL.elem[0].

4、key=key;//“哨兵”for(i=SL.length;SL.elem[i].key!=key;--i);//从后往前找returni;//查找成功时i为有效下标,否则i为0}顺序查找算法实现（从后向前查找）第11页查找成功:最少比较次数最多比较次数平均比较次数查找失败:最少比较次数最多比较次数平均比较次数查找算法的评价指标第12页查找算法的平均查找长度ASL(AverageSearchLength)指为了确定记录在查找表中的位置，需要和给定值进行关键字比较的次数的期望值:其中，n为表长，Pi为查找表中第i个

5、记录的概率，且；Ci为查找到该记录时，曾和给定值进行关键字比较的次数。第13页在等概率情形，查找任一记录的概率相等：pi=1/n,i=1,2,,n查找不成功时，查找成功时，以从前向后顺序查找算法为例，查找算法时间复杂度？O(n)顺序查找算法总结查找长度：查找成功:最少比较次数1最多比较次数n平均比较次数(n+1)/2查找失败:最少比较次数n最多比较次数n平均比较次数n优点：查找结构无特殊要求（线性结构均适用）；算法简单；缺点：查找效率较低，不适于大表查找。第14页第15页上述按顺序查找表的查找算法简单，但平均查

6、找长度较大，不适用于表长较大的查找结构。1.2折半查找（二分查找）（BinarySearch)若静态查找表为有序表，则查找过程可以基于“折半”进行。基于有序顺序表的折半查找设n个数据对象存放在一个有序顺序表中，并按其关键字值从小到大（或从大到小）排好序。原理：折半查找时,每次都先求出位于查找区间正中的对象的下标mid，用其关键字与给定值x比较，然后根据比较结果将查找区间缩小一半，直至找到被查找对象。第16页折半查找算法（设数据按关键字从小到大有序排列）1.Element[mid].key==x查找成功；2.Ele

7、ment[mid].key>x把查找区间缩小为表的前半部分，继续折半查找；3.Element[mid].key

8、lowmidhigh66810125678lowmidhigh665lowmidhigh6(1)low=0,high=8,mid=4;由于Elem[mid]Key,因此,high=mid-1=5;(3)mid=5,Elem[mid]=Key,因此查找成功.第20页查找失败的例子-101346