第8章查找 静态查找表 二叉排序 平衡二叉树(AD树) 验希表
◼ 静态查找表 ◼ 二叉排序树 ◼ 平衡二叉树（AVL树） ◼ 哈希表
81静态查找表 查找( Search)的概念 查找:就是在数据集合中寻找满足某种条 件的数据对象。 查找表:是由同一类型的数据元素(或记录) 组成的数据集合。 查找的结果通常有两种可能 ◆查找成功,即找到满足条件的数据对象。 ◆查找不成功,或查找失败。作为结果, 报告一些信息,如失败标志、失败位置等
查找(Search)的概念 8.1 静态查找表 ◼ 查找：就是在数据集合中寻找满足某种条 件的数据对象。 ◼ 查找表：是由同一类型的数据元素(或记录) 组成的数据集合。 ◼ 查找的结果通常有两种可能： ◆ 查找成功，即找到满足条件的数据对象。 ◆查找不成功，或查找失败。作为结果， 报告一些信息，如失败标志、失败位置等
衡量一个查找算法的时间效率的标准是:在查 找过程中关键字的平均比较次数或平均读写磁 盘次数(只适合于外部查找),这个标准也称为 平均查找长度AL(4 average search length),通 常它是查找结构中对象总数n或文件结构中物 理块总数n的函数。 另外衡量一个查找算法还要考虑算法所需要的 存储量和算法的复杂性等问题。 在静态查找表中,数据对象存放于数组中,利 用数组元素的下标作为数据对象的存放地址。 查找算法根据给定值x,在数组中进行查找。 直到找到x在数组中的存放位置或可确定在数 组中找不到为止
衡量一个查找算法的时间效率的标准是：在查 找过程中关键字的平均比较次数或平均读写磁 盘次数(只适合于外部查找)，这个标准也称为 平均查找长度ASL(Average Search Length)，通 常它是查找结构中对象总数 n 或文件结构中物 理块总数 n 的函数。 另外衡量一个查找算法还要考虑算法所需要的 存储量和算法的复杂性等问题。 在静态查找表中，数据对象存放于数组中，利 用数组元素的下标作为数据对象的存放地址。 查找算法根据给定值x，在数组中进行查找。 直到找到x在数组中的存放位置或可确定在数 组中找不到x为止
811顺序表的查找( Sequential Search) 所谓顺序查找,又称线性查找,主要用于在线性结构中进 行查找 存储结构: ty pedef struct ElemType *elem; int length 3 SSTable 查找过程:从表中最后一个元素开始,顺序用各元素的关键 字与给定值进行比较,若找到与其值相等的元素,则查找成 功,给出该元素在表中的位置;否则,若直到第一个记录仍 未找到关键字与x相等的对象,则查找失败
8.1.1顺序表的查找 (Sequential Search) 所谓顺序查找，又称线性查找，主要用于在线性结构中进 行查找。 存储结构： typedef struct{ ElemType *elem; int length; } SSTable; 查找过程：从表中最后一个元素开始，顺序用各元素的关键 字与给定值x进行比较，若找到与其值相等的元素，则查找成 功，给出该元素在表中的位置；否则，若直到第一个记录仍 未找到关键字与x相等的对象，则查找失败
算法8.1 Search_ Seq(ssTable ST, KeyType key) /顺序查找的算法,0号元素为监视哨 int i STelem oj. key=key; for(=STlength; !EQ(STelemi. key, key); -1); return i
算法8.1 Search_Seq(SSTable ST, KeyType key){ //顺序查找的算法，0号元素为监视哨 int i； ST.elem[0].key=key; for (i=ST.length; !EQ(ST.elem[i].key,key);--i); return i; }
顺序查找的平均查找长度 设查找第i个元素的概率为p,查找到第i个元素 所需比较次数为c,则查找成功的平均查找长度: ASL SucC ∑pc;:(∑P=1) i=1 在顺序查找情形,c1=ni+1,i=1,…,n,因此 ASD、w=∑p1(n-i+1) 在等概率情形,P;=1/m,i=0,1,,n-1 AsLI n(n+ + 2 2
顺序查找的平均查找长度 = = = = n i i n i ASLsucc 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 设查找第 i 个元素的概率为 pi，查找到第 i 个元素 所需比较次数为 ci，则查找成功的平均查找长度: 在顺序查找情形，ci = n-i +1, i = 1, , n，因此 在等概率情形，pi = 1/n, i = 0, 1, , n-1
812有序表的查找 折半查找:先求位于查找区间正中的对象的 下标mid,用其关键字与给定值比较: n Element(mid. getKey()=x,查找成功 o Element mid getKey()>x,把查找区间缩小 到表的前半部分,再继续进行对分查找; n Element mid- getKey()<x,把查找区间缩小 到表的后半部分,再继续进行对分查找。 每比较一次,查找区间缩小一半。如果查找 区间已缩小到一个对象,仍未找到想要查找 的对象,则查找失败
8.1.2 有序表的查找 折半查找：先求位于查找区间正中的对象的 下标mid，用其关键字与给定值x比较: Element[mid].getKey( ) = x，查找成功； Element[mid].getKey( ) > x，把查找区间缩小 到表的前半部分，再继续进行对分查找； Element[mid].getKey( ) < x，把查找区间缩小 到表的后半部分，再继续进行对分查找。 每比较一次，查找区间缩小一半。如果查找 区间已缩小到一个对象，仍未找到想要查找 的对象，则查找失败
折半查找 (1) mid=L(low+high)/2 (2)比较 STelem mid). key==key 如果 STelem mid . key==key,则查找成功, 返回md值 如果 STelem mid]. key>key,则置high=mid-1 如果 STelem mid]. keyhigh时,表明查找不成功,查找结束
折半查找： （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].key high时，表明查找不成功，查找结束
面叫013146812国 查找 查找 OZO mia high mid high 681012 low mid high low mid high 查找成功 查找失败国 low mid high low mid high 查找成功的例子 查找失败的例子
查找成功的例子 查找失败的例子
算法8.2 int search bin( SSTable ST, Key Type key)/折半查找 f int low, high, mid low=l; high-STlength while (low high) f mid=(low+high)/2 if(eQ(key, ST elem [ mid]. key)) return mid else if (lt(key, STelem mid. key)) high=mid-1 else low-mid+1 eturn o
算法8.2 int Search_Bin(SSTable ST,KeyType key) //折半查找 { int low,high,mid; low = 1; high=ST.length; while (low < high) { mid = (low+high)/2; if (EQ(key,ST.elem[mid].key)) return mid; else if (LT(key,ST.elem[mid].key)) high=mid-1; else low=mid+1; } return 0; }