《数据结构与算法分析课件第9章剖析》由会员分享，可在线阅读，更多相关《数据结构与算法分析课件第9章剖析（20页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法分析数据结构与算法分析 A Practical Introduction to Data Structures and Algorithm Analysis 陈陈 星星 第第9 9章章 检索检索 u使用最频繁的计算任务。 u在一组记录中找到具有某个关键码值的记录，或找到关键 码值符合某条件的一些记录。 精确匹配查询：检索关键码值与某个特定值匹配的记录 。 范围查询：检索关键码值在某个指定值范围内的所有记 录。 u检索算法分类： 顺序表和线性表方法 根据关键码值直接访问方法（散列法） 树索引方法 9.1 检索已排序的数组 u顺序检索算法：简单，但时间代价大（(n)）。 u二分法检索
2、（对分查找、折半查找）：(logn)。 u字典检索（插值检索）：一种改进的二分法检索，原理 是：利用记录的关键码值估算记录在线性表中的位置。 9.2 自组织线性表 u如果知道对各记录的访问频率，可根据访问频率排列线 性表中记录。对线性表中记录采用顺序检索。 u一次检索需要的预计比较数是： u80/20规则：80%的访问都是对20%的记录进行的。 u如果不知道记录的访问频率，则根据启发式规则决定如何重新排列线性 表。 计数方法：对每条记录保存一个访问计数，按计数顺序排列记录 。 移至前端法：将最新进行检索操作的记录移到线性表的最前端。 转置法：将最新进行检索操作的记录与它在线性表中的前一条记 录
3、交换位置。 u自组织线性表的优点： 不需要对线性表进行排序。 实现容易。 不需要额外的空间。 可以通过少量修改极大地加快顺序检索速度。 9.3 9.3 集合的检索集合的检索 确定一个值是否是某集合的元素。 在关键码值范围有限的情况下，可采用的一种简单技术：存 储一个位数组，为每个可能的元素分配一个比特位位置。 通过简单的逻辑上的位操作，可完成集合中元素的检索。 9.4 9.4 散列方法散列方法 u 一种完全不同的检索表方法：根据关键码值访问表。 u 通过散列函数，在关键码值和散列表存储位置之间建立对应 关系。 u 散列又称为哈希（Hash）。 u概念：散列、散列函数h、散列表HT、槽。 有M个
4、槽的散列表中槽从0M-1编号。 u 散列设计的目标：对任何关键码K和某个散列函数h， 0h(K) M，有HTi=K。 u散列方法对按关键码进行检索，效率非常高。效率非常高。 u但不适用于： 允许多条记录有相同关键码的应用程序。 不适用于范围检索。 检索最大或最小的关键码。 按关键码的顺序访问记录。 u 散列允许关键码范围中的值比散列表中的槽多。 u 冲突：两个或多个不同关键码通过散列函数映射到散列表的 同一个槽。 对于一个散列函数h和两个关键码值k1, k2, 如果 h(k1)=h(k2)，其中是表中的一个槽。 采用散列方法检索关键码值采用散列方法检索关键码值K K的步骤：的步骤： 根据散列函
5、数h计算在散列表中的位置h(K)。 使用冲突解决策略找到包含关键码值K的记录。 9.4.19.4.1 散列函数散列函数 uu散列函数选取的标准：尽量减少冲突，这要求散列函数能把记散列函数选取的标准：尽量减少冲突，这要求散列函数能把记 录以相同的概念分布到散列表的所有槽中（均匀分布）。录以相同的概念分布到散列表的所有槽中（均匀分布）。 uu设计散列函数时，要面临的两种情况：设计散列函数时，要面临的两种情况： 对关键码值的分布不了解。 散列函数产生一个大致平均的关键码值随机分布。 了解关键码值的分布。 使用一个依赖于分布的散列函数，尽可能地避免冲突。 散列函数散列函数 例9.6: int h(in
6、t x) return(x % 16); 分析：该散列函数只依赖于关键码的最低四位（二进制），分布 可能很差。 例9.7：平方取中法： 计算关键码值的平方，再取中间若干位。 分析：散列函数值与关键码值的每一位都有关，并且随机性强。 例9.8 用于字符串的散列函数 int h(char* x) int i, sum; for (sum=0, i=0; xi != 0; i+) sum += (int) xi; return(sum % M); 原理：折叠法。累加字符串中所有字母的ASCII值 ，再对M（槽 的数量）取余数。 分析：散列函数值与关键码值的每一位都有关系。如果M较小， 随机性较大，如
7、果M较大，则随机性不足，可能会产生一个差的 分布。 9.4.2 9.4.2 开散列方法开散列方法 冲突解决技术分类： 开散列方法，也称单链方法。将冲突记录存储在表外。 闭散列方法，也称开地址方法。将冲突记录存储在表中的 另一个槽中。 将散列表的每个槽定义为一个 链表的表头，散列到一个槽中的 所有记录都放到该槽的链表中。 槽链接的链表中记录排列顺序 可按：1. 插入次序。2. 关键码值 次序。3. 访问频率次序。 适用于内存散列，不适用于磁盘。 9.4.3 9.4.3 闭散列方法闭散列方法 原理：所有记录直接存储在散列表中。由散 列函数计算出来的槽称为基位置，如果有冲 突（基位置已被占据），则由
8、冲突解决策略 安排冲突记录存储到散列表的其它槽内。 桶式散列 将散列表分为多个桶，每个桶包含多个槽。 有相同散列函数值记录（即冲突）分配到同 一个桶中，如果桶中槽已被占用完，则存储 在表后面具有无限容量的溢出桶中。 桶式散列的一个简单变体 桶中的每个槽都可以是基位置。 线性探查 “经典”形式的散列方法： 原理：如果某记录的基位置已被占用（发 生冲突），由冲突解决策略在散列表中产 生下一个存放记录的槽。如果下一个槽仍 被占用，则由冲突解决策略产生再下一个 槽，直到有空槽为止。 由冲突解决策略产生的一组槽称为探查序 列，由探查函数P(K,i)产生。 例如：关键码K对应的基位置为home，如 果ho
9、me已被占用，则该记录移动到 home+P(K,1), 如果仍被占用，则移动到 home+P(K,2)，直到找到一个空槽为止。 线性探查 简单线性探查：P(K, i) = mod(i, M) 如果基位置已被占用，则从基位置出 发向后依次寻找空槽。 线性探查可能出现基本聚集现象，即关键 码探查序列的某些段重叠在一起。 改进的冲突解决方法（为避免基本聚集） 仍线性探查，但跳过多个槽。即 P(K, i) = mod(iC, M) C与M互素，以便可以走遍所有的槽。 随机地选择下一个槽。即 P(K, i) = mod( Random（i）C, M) Random(i)为一个伪随机序列。 二次探测 不同
10、基位置的两个关键码具有叉开的探查序列 例：P(K, i) = mod(i2, M) 伪随机探查和二次探查能消除基本聚集，但存在二次聚集。 概念：两个关键码散列在同一个基位置，则它们会有相同的探 查序列。 解决方法：探查序列是关键码值的函数，而不是基位置的函 数。 如仍采用线性探查， P(K, i) = i * h(K) 又称为双散列方法 闭散列方法分析 成功检索和删除的时间代价一样，而不成功检索和插入的时间 代价一样。前者时间代价低于后者。 如果不存在冲突（所有记录都存储在它的基位置），则检索 、插入和删除操作都只需一次记录访问。 冲突越多，操作所需的访问次数越多。 冲突发生的概率同表填充程序
11、成正例，由负载因子a=N/M表示 ，其中N为记录数，M为表中槽数。 在散列表中槽随机排列（不存在聚集）条件下，线性探查的 插入和不成功检索的平均代价： 删除和成功检索的平均代价： 填充因子a0.5后，散列方法的时间代价随a增大而急剧恶化。 为减小访问代价，可以对记录沿着探查序列按访问频率排序，即 访问频率最高的记录放在基位置。 删除 从散列表中删除记录应考虑： 不能影响后面的检索。 删除的位置可再利用。 解决方法：在被删除记录的位置上置一个特殊标记（墓 碑）。 为减少墓碑： 删除时进行一次局部重组。 定期重新散列整个表。 设散列表容量为7(散列地址空间0.6)，给定表(30，36，47，52 ，34)，散列函数H(k)=k mod 6，采用线性探测法（发生冲突时移 动步长为1）解决冲突，要求： (1)构造散列表； (2)求查找数34需要的比较次数。 练练 习习 答答 案案 0123456 3036524734 查找34需要比较3次。 1.
