分块检索的优缺点 92集合的检索 优点: 用位向量来表示集合 插入、删除相对较易 对于密集型集合(数据范围小,而 没有大量记录移动 集合中有效元素个数比较多) ■缺点: 增加一个辅助数组的存储空间 初始线性表分块排序 00110100001 当大量插入/删除时,或结点分布不均 匀时,速度下降 叔新有,盘 张 例:计算0到15之间所有的奇素数 实际实现用无符合长整数数组 奇数:012345678910112131415 全集元素个数N=40的集合,集 010f0d10101o1o 合{359753,1}表示为 000000000000000000000000 00 000 o00000000000000000000010 奇素数: 不够一个 signed long,左补0 订恤 张铝 权新有,种 张帖 93散列检索 9.3.0散列中的基本问题 9.3.0散列中的基本问题 基于关键码比较的检索 9.31散列函数 二分法、树型 令碰撞的处理 检索是直接面向用户的操作 上述检索的时间效率可 △9.32开散列方法 能使得用户无法 .33闭散列方法 最理想的情况 Q9.34闭散列表的算法实现 根据关健码值,直接找到记录的存储地址 待查关键码与候选记录集合的某些记录进 △935散列方法的效率分析 学恤息 权新有,种6 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 31 分块检索的优缺点 „ 优点： „ 插入、删除相对较易 „ 没有大量记录移动 „ 缺点： „ 增加一个辅助数组的存储空间 „ 初始线性表分块排序 „ 当大量插入/删除时，或结点分布不均 匀时，速度下降 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 32 9.2 集合的检索 „ 用位向量来表示集合 „ 对于密集型集合（数据范围小，而 集合中有效元素个数比较多） 0 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 33 例：计算0到15之间所有的奇素数 奇数： 素数： 奇素数： 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 2 4 6 8 10 12 14 1 3 5 7 9 11 13 15 0 4 6 8 10 12 14 1 9 15 2 3 5 7 11 13 0 2 4 6 8 10 12 14 1 9 15 3 5 7 11 13 1 3 5 7 9 11 13 15 2 3 5 7 11 13 3 5 7 11 13 & = 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 34 实际实现用无符合长整数数组 „ 全集元素个数N=40的集合，集 合{35, 9, 7, 5, 3, 1}表示为 0000 0000 0000 0000 0000 0000 0000 1000 0000 0000 0000 0000 0000 0010 1010 1010 不够一个usigned long, 左补0 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 35 9.3 散列检索 „ 9.3.0 散列中的基本问题 „ 9.3.1 散列函数 „ 碰撞的处理 „ 9.3.2 开散列方法 „ 9.3.3 闭散列方法 „ 9.3.4 闭散列表的算法实现 „ 9.3.5 散列方法的效率分析 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 36 9.3.0 散列中的基本问题 „ 基于关键码比较的检索 „ 顺序检索，==, != „ 二分法、树型 >, == , < „ 检索是直接面向用户的操作 „ 当问题规模n很大时，上述检索的时间效率可 能使得用户无法忍受 „ 最理想的情况 „ 根据关键码值，直接找到记录的存储地址 „ 不需要把待查关键码与候选记录集合的某些记录进 行逐个比较