数据结构第9章课件.ppt

《数据结构第9章课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第九章查找基本概念顺序查找二分查找分块索引查找二叉排序树的查找B树与B+树的查找Hash(散列)9.1基本概念查找表:由具有同一类型的数据元素（或记录）组成的集合称为查找表。关键字:关键字是记录中某个项或组合项的值，用它可以标识一个记录。能唯一确定一个记录的关键字，称为主关键字；而不能唯一确定一个记录的关键字，称为次关键字.查找是指按给定的某个值k，在查找表中查找关键字为给定值k的记录。查找是计算机中经常遇到的操作。特别是当问题所涉及到的数据量相当大时，查找的效率就显得格外重要。查找运算的主要操作是关键字的比较，所以，通常把查找过程中对关键字需要执行的平均比较次数（也称

2、为平均查找长度）作为衡量一个查找算法效率优劣的标准。*查找结果：成功、失败*查找算法的性能指标时间复杂性平均查找长度:平均比较次数平均查找长度定义为：其中，n是元素的个数；pi是查找第i个元素的概率，p1=p2=...=pn=1/n；ci是找到第i个元素所需要的比较次数*常用的查找算法顺序查找二分查找(折半查找)分块索引查找二叉排序树的查找B树与B+树的查找Hash(散列)查找9.2顺序查找structRecord{intkey;……};Recordr[n];无监视哨的顺序查找:intSeqSearch(Recordr[],intn,intk){inti=0;w

3、hile(i

4、行比较，若相等，则查找完成；否则，若R[mid].key>K，则说明待查找的结点只可能在左子表R[0]到R[mid-1]中，只需在左子表中继续查找；否则在右子表R[mid+1]到R[n-1]中继续查找。这样，经过一次关键字的比较就缩小了一半的查找区间。如此进行下去，直到找到为止（当然也存在最后找不到的可能）。例:[0513192137566475808892][0513192137]566475808892051319[2137]566475808892查找K=21的过程（查找成功）[0513192137566475808892]051319213756[6475808

5、892]051319213756647580[8892]查找K=85的过程（查找失败）051319213756647580[8892]二分查找算法(非递归)intBiSearch(Recordr[],intn,intk){low=0,high=n-1;while(low<=high){mid=(low+high)/2;if(r[mid].key==k)returnmid;elseif(r[mid].key

6、gh,intk){if(low>high)return-1;else{mid=(low+high)/2;if(r[mid].key==k)returnmid;elseif(r[mid].key

7、：O(logn)即在最坏情况下，二分查找方法查找成功的比较次数不超过判定树的高度。虽然二分查找的效率较高，但它要求被查找序列事先按关键字排好序，而排序本身是一种很费时的运算；另外，二分查找只适用于顺序存储结构，因此，二分查找特别适用于那种一经建立就很少改动、而又需要经常查找的线性表。平均长度的计算例如:长度为13的有序表进行折半查找的平均查找长度ASL=(1×1+2×2+3×4+4×6)/13=41/13。9.4分块查找分块查找又称为索引查找，它是一种性能介于顺序查找和二分查找之间的查找算法。分块查找要求将被查找表分成块，建立块索引。每