数据结构与算法课件第9章.ppt

数据结构与算法分析A Practical Introduction toData Structures and Algorithm Analysis陈 星  第9章 检索 使用最频繁的计算任务。 在一组记录中找到具有某个关键码值的记录，或找到关键码值符合某条件的一些记录。 精确匹配查询：检索关键码值与某个特定值匹配的记录。 范围查询：检索关键码值在某个指定值范围内的所有记录。 检索算法分类： 顺序表和线性表方法 根据关键码值直接访问方法（散列法） 树索引方法 9.1 检索已排序的数组 顺序检索算法：简单，但时间代价大（Θ(n)）。 二分法检索（对分查找、折半查找）：Θ(logn)。 字典检索（插值检索）：一种改进的二分法检索，原理是：利用记录的关键码值估算记录在线性表中的位置。 9.2 自组织线性表 如果知道对各记录的访问频率，可根据访问频率排列线性表中记录。对线性表中记录采用顺序检索。 一次检索需要的预计比较数是： 80/20规则：80%的访问都是对20%的记录进行的。 如果不知道记录的访问频率，则根据启发式规则决定如何重新排列线性表。 计数方法：对每条记录保存一个访问计数，按计数顺序排列记录。 移至前端法：将必威体育精装版进行检索操作的记录移到线性表的最前端。 转置法：将必威体育精装版进行检索操作的记录与它在线性表中的前一条记录交换位置。 自组织线性表的优点： 不需要对线性表进行排序。 实现容易。 不需要额外的空间。 可以通过少量修改极大地加快顺序检索速度。 9.3 集合的检索 确定一个值是否是某集合的元素。 在关键码值范围有限的情况下，可采用的一种简单技术：存储一个位数组，为每个可能的元素分配一个比特位位置。 通过简单的逻辑上的位操作，可完成集合中元素的检索。 9.4 散列方法 一种完全不同的检索表方法：根据关键码值访问表。 通过散列函数，在关键码值和散列表存储位置之间建立对应 关系。 散列又称为哈希（Hash）。 概念：散列、散列函数h、散列表HT、槽。 有M个槽的散列表中槽从0～M-1编号。 散列设计的目标：对任何关键码K和某个散列函数h， 0≤h(K) ≤M，有HT[i]=K。 散列方法对按关键码进行检索，效率非常高。 但不适用于： 允许多条记录有相同关键码的应用程序。 不适用于范围检索。 检索最大或最小的关键码。 按关键码的顺序访问记录。 散列允许关键码范围中的值比散列表中的槽多。 冲突：两个或多个不同关键码通过散列函数映射到散列表的 同一个槽。 对于一个散列函数h和两个关键码值k1, k2, 如果 h(k1)=β=h(k2)，其中β是表中的一个槽。 采用散列方法检索关键码值K的步骤： 根据散列函数h计算在散列表中的位置h(K)。 使用冲突解决策略找到包含关键码值K的记录。 9.4.1 散列函数 散列函数选取的标准：尽量减少冲突，这要求散列函数能把记录以相同的概念分布到散列表的所有槽中（均匀分布）。 设计散列函数时，要面临的两种情况： 对关键码值的分布不了解。 散列函数产生一个大致平均的关键码值随机分布。 了解关键码值的分布。 使用一个依赖于分布的散列函数，尽可能地避免冲突。 散列函数 例9.6: int h(int x) { return(x % 16); } 分析：该散列函数只依赖于关键码的最低四位（二进制），分布可能很差。 例9.7：平方取中法： 计算关键码值的平方，再取中间若干位。 分析：散列函数值与关键码值的每一位都有关，并且随机性强。 例9.8 用于字符串的散列函数 int h(char* x) { int i, sum; for (sum=0, i=0; x[i] != \0; i++) sum += (int) x[i]; return(sum % M); } 原理：折叠法。累加字符串中所有字母的ASCII值 ，再对M（槽的数量）取余数。 分析：散列函数值与关键码值的每一位都有关系。如果M较小，随机性较大，如果M较大，则随机性不足，可能会产生一个差的分布。 9.4.2 开散列方法 冲突解决技术分类： 开散列方法，也称单链方法。将冲突记录存储在表外。 闭散列方法，也称开地址方法。将冲突记录存储在表中的另一个槽中。 将散列表的每个槽定义为一个 链表的表头，散列到一个槽中的 所有记录都放到该槽的链表中。 槽链接的链表中记录排列顺序 可按：1. 插入次序。2. 关键码值 次序。3. 访问频率次序。 适用于