第8章 查找解析.ppt

3．二叉排序树的插入算法 根据动态查找表的定义，“插入”操作在查找不成功时才进行； 冲突现象举例： 讨论： 2. 二次探测法 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个），则可取这四位中的任意两位组合成哈希地址，也可以取其中两位与其它两位叠加求和后，取低两位作哈希地址。 以关键字的平方值的中间几位作为存储地址。求“关键字的平方值” 的目的是“扩大差别” ，同时平方值的中间各位又能受到整个关键字中各位的影响。 3. 平方取中法 此方法适合于: 关键字中的每一位都有某些数字重复出现频度很高的现象。 例：2589的平方值为6702921，可以取中间的029为地址。 将关键字分割成若干部分，然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加和间界叠加。 4. 折叠法 此方法适合于: 关键字的数字位数特别多。 法1：移位法 ── 将各部分的最后一位对齐相加。 法2：间界叠加法──从一端向另一端沿分割界来回折叠后，最后一位对齐相加。 例：元 用法1： 427＋518＋96=1041 用法2： 427 518 96— 724+518+69 =1311 5. 除留余数法 设定哈希函数为: H(key) = key MOD p 其中， p≤m (表长) 并且 p 应为不大于 m 的素数 或是 不含 20 以下的质因子 给定一组关键字为：12, 39, 18, 24, 33, 21， 若取 p=9, 则他们对应的哈希函数值将为： 3, 3, 0, 6, 6, 3 例如： 为什么要对 p 加限制？ 可见，若 p 中含质因子 3， 则所有含质因子 3 的关键字均映射到“3 的倍数”的地址上，从而增加了“冲突”的可能。 90 75 60 46 18 43 54 12 11 10 9 8 7 6 5 4 3 2 1 0 H 例：有一线性表 A=(18,75,60,43,54,90,46) 哈希函数为：h(K)=K%p ( 取m=13,p=13) h(18)=18%13=5 h(75)=75%13=10 h(60)=60%13=8 h(43)=43%13=4 h(54)=54%13=2 h(90)=90%13=12 h(46)=46%13=7 6.随机数法 设定哈希函数为: H(key) = Random(key) 其中，Random()不能是一般的随机函数， 固定的参数必须返回确定的值。 通常，此方法用于对长度不等的关键字构造哈希函数。 以上介绍了几种常用的散列函数。在实际工作中应根据关键码的特点，选用适当的方法。有人曾用“轮盘赌”的统计分析方法对它们进行了模拟分析，结论是平方取中法最接近于“随机化”。 在应用平方取中法时，若关键码不是整数而是字符串时，可以把每个字符串转换成整数。 实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小。 三、处理冲突的方法 有6个元素的关键码分别为：（14，23，39，9，25，11）选取关键码与元素位置间的函数为H(k)=k mod 7 通过哈希函数对6个元素建立哈希表： 25 39 23 9 14 6个元素用7个地址应该足够! H(14)=14%7=0 11 H(25)=25%7=4 H(11)=11%7=4 有冲突！ 0 1 2 3 4 5 6 50 30 80 20 90 85 40 35 88 32 例如: 二叉排序树 查找关键字 == 50 , 50 50 35 , 50 30 40 35 50 90 , 50 80 90 95 , 从上述查找过程可见， 在查找过程中，生成了一条查找路径： 从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点; 或者 从根结点出发，沿着左分支或