87 基于树的查找法 - 浙江工商大学.ppt

8.10 计算式查找法——散列表运算 8.10.3 散列表的建表算法 散列函数为：h(key)=key％13。从而得到关键字(26，36，41，38，44，15，68，12，06，51)的地址为(0，10，2，12，5，2，3，12，6，12)。 前5个关键字插入时没有冲突，结果为 26 41 44 36 38 0 1 2 3 4 5 6 7 8 9 10 11 12 1 1 1 1 1 探查次数 序号 15 2 68 2 12 3 06 1 51 9 8.10 计算式查找法——散列表运算 8.10.3 散列表的建表算法 采用链地址法解决冲突，结果如下（可头插或尾插）。 8.10 计算式查找法——散列表运算 8.10.4 散列表的查找算法 算法思想： 当查找关键字为K的元素时，首先计算p0= h（K）。如果单元p0为空，则所查元素不存在； 如果单元p0中元素的关键字为K，则找到所查元素； 否则重复下述解决冲突的过程：按解决冲突的方法，找出下一个散列地址pi，如果单元pi为空，则所查元素不存在；如果单元pi中元素的关键字为K，则找到所查元素。 8.10 计算式查找法——散列表运算 8.10.4 散列表的查找算法 查找实例——查找成功的ASL： 线性探查法ASL=(1×6+2×2+3×1+9×1)/10=2.2 26 41 44 36 38 0 1 2 3 4 5 6 7 8 9 10 11 12 1 1 1 1 1 探查次数 序号 15 2 68 2 12 3 06 1 51 9 8.10 计算式查找法——散列表运算 8.10.4 散列表的查找算法 查找实例——查找成功的ASL： 链地址法ASL=(1×7+2×2+3×1)/10=1.4 8.10 计算式查找法——散列表运算 8.10.4 散列表的查找算法 查找实例——查找成功的ASL： 顺序查找ASL=(10+1)/2=5.5 26 41 44 36 38 0 1 2 3 4 5 6 7 8 9 序号 15 68 12 06 51 8.10 计算式查找法——散列表运算 8.10.4 散列表的查找算法 查找实例——查找成功的ASL： 二分查找ASL=(1×1+2×2+3×4+4×3)/10=2.9 8.10 计算式查找法——散列表运算 8.10.4 散列表的查找算法 查找实例——查找不成功的ASL： 线性探查法ASLunsucc=(9+8+7+6+5+4+3+2+1+1+2+1+10)/13 =59/13≈4.54 26 41 44 36 38 0 1 2 3 4 5 6 7 8 9 10 11 12 1 1 1 1 1 探查次数 序号 15 2 68 2 12 3 06 1 51 9 8.10 计算式查找法——散列表运算 8.10.4 散列表的查找算法 查找实例—— 查找不成功的ASL： 链地址法ASLunsucc=(1×6+2×5+3×1+4×1)/13=23/13≈1.77 8.10 计算式查找法——散列表运算 8.10.4 散列表的查找算法 查找实例——查找不成功的ASL： 顺序查找ASLunsucc=11 26 41 44 36 38 0 1 2 3 4 5 6 7 8 9 序号 15 68 12 06 51 8.10 计算式查找法——散列表运算 8.10.4 散列表的查找算法 查找实例—— 查找不成