第8章查找 山西建筑职业技术学院.pptVIP

第8章 查 找 折半查找举例： (2)算法的实现 int BinarySearch(SeqList S, DataType x) {int low = 0, high = S.size-1;/确定初始查找区间上下界 int mid; while(low = high) { mid=(low + high)/2;//确定初始查找区间中心位置 if(S.list[mid].key == x.key) return mid;//查找成功 else if(S.list[mid].key x.key) low = mid + 1; else if(S.list[mid].key x.key) high = mid - 1; } return -1; //查找失败 } 分块查找过程举例： 冲突现象举例： 在哈希查找方法中，冲突是不可能避免的，只能尽可能减少。 1、直接定址法 2、数字分析法 3、除留余数法 8.4.3 哈希冲突解决方法 1、开散列表处理冲突（开链地址法） 2.闭散列表处理冲突(开放定址法) 例： 2. 二次探测法 8.5 应用举例及分析 例1 画出对长度为10 的有序表进行二分查找的判定树，并求其等概率时查找成功的平均查找长度。10个有序整数的序列为(10,20,30,40,50,60,70,80,90,100)。对应的二分查找的判定树如下图8所示。 判定树共四层，第一层表示比较一次可查到的结点有一个，第二层表示比较两次可查到的结点有两个，第三层表示比较三次可查到的结点有四个，第四层表示比较四次可查到的结点有三个。计算等概率时查找成功的平均查找长度为（1+2+2+3+3+3+3+4+4+4）/10=29/10。 对上面的二叉排序树中进行中序遍历，获得的有序表为（Apr,Aug,Dec,Feb,Jan,Jun,Jul,Mar,Nov,Oct,Sep）,对此有序表进行二分查找时，求在等概率情况下查找成功的平均查找长度，其方法与上题中描述的方法一样，为（1+2+2+3+3+3+3+4+4+4+4+4）/12=37/12。 习题 P151 8.2, 8.4, 8.5 Hash(key) = a·key + b (a、b为常数) 优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突. 缺点：要占用连续地址空间，空间效率低。 例：关键码集合为{100，300，500，700，800，900}， 选取哈希函数为Hash(key)=key/100， 则存储结构（哈希表）如下： 0 1 2 3 4 5 6 7 8 9 900 800 700 500 300 100 特点：选用关键字的某几位组合成哈希地址。选用原则应当是：各种符号在该位上出现的频率大致相同。 3 4 7 0 5 2 4 3 4 9 1 4 8 7 3 4 8 2 6 9 6 3 4 8 5 2 7 0 3 4 8 6 3 0 5 3 4 9 8 0 5 8 3 4 7 9 6 7 1 3 4 7 3 9 1 9 例：有一组（例如80个）关键码，其样式如下： 讨论： ① 第1、2位均是“3和4”，第3位也只有“ 7、8、9”，因此，这几位不能用，余下四位分布较均匀，可作为哈希地址选用。 位号：① ② ③ ④ ⑤ ⑥ ⑦ ② 若哈希地址取两位（因元素仅80个），则可取这四位中的任意两位组合成哈希地址，也可以取其中两位与其它两位叠加求和后，取低两位作哈希地址。 Hash(key)=key mod m (m是一个整数) 特点：以关键码除以p的余数作为哈希地址。 关键：如何选取合适的m 技巧：若设计的哈希表长为m，则一般取p≤m且为质数 （也可以是合数，但不能包含小于20的质因子）。 ① 执行速度（即计算哈希函数所需时间）； ② 关键字的长度； ③ 哈希表的大小； ④ 关键字的分布情况； ⑤ 查找频率。 小结：构造哈希函数的原则： 常见的冲突处理方法有： 开放定址法（开地址法） 链地址法（拉链法） 基本思想：将具有相同哈希地址的记录链成一个单链表，m个哈希地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。 设{ 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89 }的哈希函数为： Hash(key)=key mod 11， 用开链地址法处理冲突，则建表如右图所示。 例： 0