严蔚敏数据结构课件09查找.ppt

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

1、静态查找表二叉排序树平衡二叉树（AVL树）小结B树哈希表第9章查找查找(Search)的概念静态查找表查找：就是在数据集合中寻找满足某种条件的数据对象。查找表：是由同一类型的数据元素(或记录)组成的数据集合。查找的结果通常有两种可能：查找成功，即找到满足条件的数据对象。查找不成功，或查找失败。作为结果，报告一些信息，如失败标志、失败位置等。关键字：数据元素中某个数据项的值，用以标识一个数据元素。主关键字：可唯一地标识一个数据元素的关键字。次关键字：用以识别若干记录的关键字。使用基于主关键字的查找，查找结果应是唯一的。静态查找表（p214）动态查找表9.1静态查找表基

2、本操作：Create(&ST,n);//构造含有n个元素的静态查找表STDestroy(&ST);//销毁表Search(ST,key);//查找关键字为key的数据元素Traverse(ST,visit());//遍历查找表关键字比较约定为如下宏定义#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)<=(b))衡量一个查找算法的时间效率的标准是：在查找过程中关键字的平均比较次数或平均读写磁盘次数(只适合于外部查找)，这个标准也称为平均查找长度ASL(AverageSearchLengt

3、h)，通常它是查找结构中对象总数n或文件结构中物理块总数n的函数。另外衡量一个查找算法还要考虑算法所需要的存储量和算法的复杂性等问题。在静态查找表中，数据对象存放于数组中，利用数组元素的下标作为数据对象的存放地址。查找算法根据给定值x，在数组中进行查找。直到找到x在数组中的存放位置或可确定在数组中找不到x为止。9.1.1顺序表的查找(SequentialSearch)所谓顺序查找，又称线性查找，主要用于在线性结构中进行查找。存储结构：typedefstruct{ElemType*elem;intlength;}SSTable;查找过程：从表中最后一个元素开始，顺序用

4、各元素的关键字与给定值x进行比较，若找到与其值相等的元素，则查找成功，给出该元素在表中的位置；否则，若直到第一个记录仍未找到关键字与x相等的对象，则查找失败。有序顺序表的顺序查找(10,20,30,40,50,60)105060======203040<<<<<<>>>>>>最后一次查找失败需比较6次算法9.1（p217）Search_Seq(SSTableST,KeyTypekey){//顺序查找的算法，0号元素为监视哨inti；ST.elem[0].key=key;for(i=ST.length;!EQ(ST.elem[i].key,key);--i);retu

5、rni;}顺序查找的平均查找长度设查找第i个元素的概率为pi，查找到第i个元素所需比较次数为ci，则查找成功的平均查找长度:在顺序查找情形，ci=n-i+1,i=1,,n，因此在等概率情形，pi=1/n,i=0,1,,n-1。9.1.2有序表的查找折半查找：先求位于查找区间正中的对象的下标mid，用其关键字与给定值x比较:Element[mid].getKey()=x，查找成功；Element[mid].getKey()>x，把查找区间缩小到表的前半部分，再继续进行对分查找；Element[mid].getKey()

6、对分查找。每比较一次，查找区间缩小一半。如果查找区间已缩小到一个对象，仍未找到想要查找的对象，则查找失败。9.1.2有序表的查找折半查找：（1）mid=(low+high)/2」（2）比较ST.elem[mid].key==key?如果ST.elem[mid].key==key，则查找成功，返回mid值如果ST.elem[mid].key>key，则置high=mid-1如果ST.elem[mid].keyhigh时，表明查找不成功，查找结束。查找成功的例

7、子查找失败的例子算法9.2(p220)intSearch_Bin(SSTableST,KeyTypekey)//折半查找{intlow,high,mid;low=1;high=ST.length;while(low