课件7查找讲述.ppt

2.链地址法(拉链法） 基本思想：相同哈希地址的记录链成一单链表，m个哈希地址就设m个单链表，然后用用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构 0 1 2 3 4 5 6 7 8 9 10 11 12 14 ^ 1 27 79 68 55 19 84 20 23 10 11 ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ 链地址法的优点： 非同义词不会冲突，无“聚集”现象 链表上结点空间动态申请，更适合于表长不确定的情况 哈希表的查找 给定k值 计算H(k) 此地址为空 关键字==k 查找失败 查找成功 按处理冲突 方法计算Hi Y N Y N 给定值与关键字比较 已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为：H(key)=key MOD 13, 哈希表长为m=16， 设每个记录的查找概率相等 (1) 用线性探测再散列处理冲突，即Hi=(H(key)+di) MOD m 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 14 1 68 27 55 19 20 84 79 23 11 10 1 2 1 4 3 1 1 3 9 1 1 3 H(19)=6 H(14)=1 H(23)=10 H(1)=1 冲突，H1=(1+1) MOD16=2 H(68)=3 H(20)=7 H(27)=1 冲突，H1=(1+1)MOD16=2 冲突，H2=(1+2)MOD16=3 冲突，H3=(1+3)MOD16=4 ASL=(1*6+2+3*3+4+9)/12=2.5 哈希表的查找 (2) 用链地址法处理冲突 0 1 2 3 4 5 6 7 8 9 10 11 12 14 ^ 1 27 79 68 55 19 84 20 23 10 11 ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ASL=(1*6+2*4+3+4)/12=1.75 关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希表的查找 使用平均查找长度ASL来衡量查找算法，ASL取决于 　　哈希函数 　　处理冲突的方法 　　哈希表的装填因子 哈希表的查找效率分析 ? 越大，表中记录数越多，说明表装得越满，发生冲突的可能性就越大，查找时比较次数就越多。 O(1)? ASL与装填因子?有关！既不是严格的O(1)，也不是O(n) 哈希表的查找效率分析 对哈希表技术具有很好的平均性能，优于一些传统的技术 链地址法优于开地址法 除留余数法作哈希函数优于其它类型函数 几点结论 1.熟练掌握顺序表和有序表（折半查找）的查找算法及其性能分析方法； 2.熟练掌握二叉排序树的构造和查找算法及其性能分析方法； 3.掌握二叉排序树的插入算法，了解二叉排序树的删除算法； 4.熟练掌握平衡二叉树的旋转方法 5.熟练掌握哈希函数（除留余数法）的构造 6.熟练掌握哈希函数解决冲突的方法及其特点 开放地址法（线性探测法、二次探测法） 链地址法 给定实例计算平均查找长度ASL，ASL依赖于装填因子? 小结 * * * * * （1）若二叉排序树为空，则查找失败，返回空指针。 （2）若二叉排序树非空，将给定值key与根结点的关键字T-data.key进行比较： ① 若key等于T-data.key，则查找成功，返回根结点地址； ② 若key小于T-data.key，则进一步查找左子树； ③ 若key大于T-data.key，则进一步查找右子树。 【算法思想】 二叉排序树的操作－插入 插入的元素一定在叶结点上 若二叉排序树为空，则插入结点应为根结点 否则，继续在其左、右子树上查找 树中已有，不再插入 树中没有，查找直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子 45 12 53 3 37 24 100 61 90 78 20 插入结点20 二叉排序树的操作－插入 {10， 18， 3， 8， 12， 2， 7} 10 10 18 10 18 3 10 18 3 8 10 18 3 8 12 10 18 3 8 12 2 10 18 3 8 12 2 7 从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树 二叉排序树的操作－生成 不同插入次序的序列生成不同形态的二叉排序树 40 24 55 12 37 12 24 37 40 55 40，24，12，37，55 12，24，