第9章查找 静态查找表 二叉排序树 平衡二叉树(AVL树) 小结 B树 哈希表
静态查找表 查找 Search)的概念 查找:就是在数据集合中寻找满足某种条 件的数据对象。 查找表:是由同一类型的数据元素(或记录) 组成的数据集合。 查找的结果通常有两种可能: ◆查找成功,即找到满足条件的数据对象 ◆查找不成功,或查找失败。作为结果, 报告一些信息,如失败标志、失败位置等
n关键字:数据元素中某个数据项的值,用以 标识一个数据元素。 主关键字:可唯一地标识一个数据元素的关 键字。 n次关键字:用以识别若干记录的关键字。 n使用基于主关键字的查找,杳找结果应是 唯一的 静态查找表(p214) n动态查找表
91静态查找表 基本操作: Create(&STn);∥构造含有n个元素的静态查找表ST Destroy(&ST);∥销毁表 Search( ST, key),∥查找关键字为key的数据元素 Traverse(ST; visitO),遍历查找表
基本操作： Create(&ST,n); //构造含有n个元素的静态查找表ST Destroy(&ST); //销毁表 Search(ST,key); //查找关键字为key的数据元素 Traverse(ST,visit()); //遍历查找表
衡量一个查找算法的时间效率的标准是:在查 找过程中关键字的平均比较次数或平均读写磁 盘次数(只适合于外部查找),这个标准也称为 平均查找长度ASL( verage search length),通 常它是查找结构中对象总数n或文件结构中物 理块总数n的函数。 另外衡量一个查找算法还要考虑算法所需要的 存储量和算法的复杂性等问题。 在静态查找表中,数据对象存放于数组中,利 用数组元素的下标作为数据对象的存放地址。 查找算法根据给定值x,在数组中进行查找。 直到找到x在数组中的存放位置或可确定在数 组中找不到x为止
91顺序表的查找( Sequential Search) 所谓顺序查找,又称线性查找,主要用于在线性结构中进 行查找。 存储结构: typedef structi Elem Type *elem; int length; 3 SSTable 查找过程:从表中最后一个元素开始,顺序用各元素的关键 字与给定值x进行比较,若找到与其值相等的元素,则查找成 功,给出该元素在表中的位置;否则,若直到第一个记录仍 未找到关键字与x相等的对象,则查找失败
算法9.1(p217) Search Seq(ssTable st, KeyType key i ∥顺序查找的算法,0号元素为监视哨 int i: STelem o key=key for (i=STlength; !EQ(ST. i key, key);--1); return 19
算法9.1 （p217） Search_Seq(SSTable ST, KeyType key){ // ST.elem[0].key=key; for (i=ST.length; !EQ(ST.elem[i].key,key);--i); return i; }
顺序查找的平均查找长度 设查找第i个元素的概率为P,查找到第i个元素 所需比较次数为c,则查找成功的平均查找长度: ASL ∑P;c,(∑p1=1) i=1 在顺序查找情形,c1=ni+1,i=1,…,n,因此 ASL ∑P1:(n-i+1) 在等概率情形,P;=1/n,i=0,1,…,n-1 ASL (n-i+1) ln(n+1)n+1 2
n i i n i ASL succ pi ci p 1 . ( 1 ) 1 ( ) 1 1 ASL p i n i succ i n . ( ) ( ) n i succ n n n n i n ASL 1 2 1 2 1 1 1 1 n
92有序表的查找 折半查找:先求位于查找区间正中的对象的 下标mid,用其关键字与给定值x比较: ◆ Element(mid getKey()=x,查找成功 ◆ Element mid getKey()>x,把查找区间缩小 到表的前半部分,再继续进行对分查找; ◆ Element(mid getKey()<x,把查找区间缩小 到表的后半部分,再继续进行对分查找 每比较一次,查找区间缩小一半。如果查找 区间已缩小到一个对象,仍未找到想要查找 的对象,则查找失败
912有序表的查找 折半查找: (1)mid=(ow+high)2」 (2)比较 STelem mid. key==key? 如果 STele mid key==key,则查找成功, 返回mid值 如果 ST. mid. key>key,则置high=mid-1 如果 STele mid]keyhigh时,表明查找不成功,查找结東
（1）mid= (low+high)/2」
