第9章 查找48695

第九章查找 何谓查找表 查找表是由同一类型的数据元素 或记录 构成的集合 由于 集合 中的数据元素之间存在着松散的关系 因此查找表是一种应用灵便的结构 对查找表经常进行的操作 1 查询某个 特定的 数据元素是否在查找表中 2 检索某个 特定的 数据元素的各种属性 3 在查找表中插入一个数据元素 4 从查找表中删去某个数据元素 仅作查询和检索操作的查找表 静态查找表 有时在查询之后 还需要将 查询 结果为 不在查找表中 的数据元素插入到查找表中 或者 从查找表中删除其 查询 结果为 在查找表中 的数据元素 动态查找表 查找表可分为两类 根据给定的某个值 在查找表中确定一个其关键字等于给定值的数据元素或 记录 查找 若查找表中存在这样一个记录 则称 查找成功 查找结果给出整个记录的信息 或指示该记录在查找表中的位置 否则称 查找不成功 查找结果给出 空记录 或 空指针 是数据元素 或记录 中某个数据项的值 用以标识 识别 一个数据元素 或记录 关键字 若此关键字可以识别唯一的一个记录 则称之谓 主关键字 若此关键字能识别若干记录 则称之谓 次关键字 用集合表示查找表 数据元素之间的关系不作限定查询时无规律可循 只能对集合中的元素一一加以辨认 用其它结构表示查找表 对查找表的元素人为地附加上某种关系 问题 如何进行查找 查找方法取决于查找表的结构 有序表 字典 索引表 电话号码表 散列表 树表 效率低 效率高 9 1静态查找表 9 2动态查找树表 9 3哈希表 9 1静态查找表 静态查找表的存储结构 顺序表 线性链表 存储结构不同 实现查找操作的方法则不同 顺序查找 typedefstruct 数据元素存储空间基址 建表时 按实际长度分配 0号单元留空intlength 表的长度 SSTable 假设静态查找表的顺序存储结构为 ElemType elem 数据元素类型的定义为 typedefstruct keyTypekey 关键字域 其它属性域 ElemType TElemType 一 顺序查找表 二 有序查找表 三 索引顺序表 以顺序表或线性链表表示静态查找表 一 顺序查找表 ST elem 回顾顺序表的查找过程 假设给定值e 64 要求ST elem k e 问 k k k intlocation SqListL ElemType location ST elem i ST elem i 60 i key 64 key 60 i 64 elsereturn0 intSearch Seq SSTableL KeyTypekey ST elem 0 key key for i ST length ST elem i key key i if i 0 break if i 0 returni 查找方法评价 时间复杂度 空间复杂度 算法本身复杂程度 因为查找算法的基本操作为 将记录的关键字同给定值比较 所以以关键字同给定值进行过比较的记录的个数的期望值作为衡量查找算法好坏的依据 平均查找长度ASL AverageSearchLength 找到第i个记录需比较的次数 对含有n个记录的表 查找成功时 第i个记录被查找的概率 1110987654321 顺序查找的平均查找长度 ASL nP1 n 1 P2 2Pn 1 Pn 假设每个记录的查找概率相等 Pi 1 n则 查找不成功时 关键字的比较次数总是n 1次 121110987654321 假设 1 查找成功与不成功的概率相同 2 每个记录被查找的概率相同 则 平均查找长度 成功与不成功的平均查找长度之和 为 1 记录的查找概率不相等时如何提高查找效率 查找表存储记录原则 1 查找概率越高比较次数越少 2 查找概率越低 比较次数较多 讨论 2 记录的查找概率无法测定时如何提高查找效率 方法 1 在每个记录中设一个访问频度域 2 始终保持记录按非递增有序的次序排列 3 每次查找后均将刚查到的记录直接移至表头 上述顺序查找表的查找算法简单 但平均查找长度较大 特别不适用于表长较大的查找表 二 有序查找表 若以有序表表示静态查找表 则查找过程可以基于 折半 进行 ST elem ST length 例如 key 64的查找过程如下 low high mid low mid high mid low指示查找区间的下界high指示查找区间的上界mid low high 2 intSearch Bin SSTableST KeyTypekey low 1 high ST length 置区间初值while low high mid low high 2 if EQ key ST elem mid key returnmid 找到待查元素elseif LT key ST elem mid key high mid 1 继续在前半区间进行查找elselow mid 1 继续在后半区间进行查找 return0 顺序表中不存在待查元素 Search Bin 性能分析 1 2 2 3 3 3 3 4 4 4 4 Ci i 判定树 表中一个记录 比较次数 路径上的结点数 比较次数 结点4的层数 比较次数 树的深度 log2n 1 查找成功 查找不成功 比较次数 路径上的内部结点数 比较次数 log2n 1 1 3 4 6 7 9 10 1 2 2 3 4 5 5 6 7 8 8 9 10 11 11 平均查找长度ASL 成功时 设表长n 2h 1 则h log2 n 1 此时 判定树为深度 h的满二叉树 且表中每个记录的查找概率相等 Pi 1 n 第j层的每个结点要比较的次数 第j层结点数 第j层要比较的总次数 折半查找优点 效率比顺序查找高 折半查找缺点 只适用于有序表 且限于顺序存储结构 三 索引查找 当数据对象个数n很大时 如果用无序表形式的静态查找结构存储 采用顺序查找 则查找效率极低 如果采用有序表存储形式的静态查找结构 则插入新记录进行排序 时间开销也很可观 这时可采用索引方法来实现存储和查找 查38 索引顺序表的查找 分块查找 条件 1 将表分成几块 且表或者有序 或者分块有序 索引表 查找过程 先确定待查记录所在块 顺序或折半查找 再在块内查找 顺序查找 若i j 则第j块中所有记录的关键字均大于第i块中的最大关键字 2 建立 索引表 每个结点含有最大关键字域和指向本块第一个结点的指针 且按关键字有序 索引顺序表的查找过程 1 由索引确定记录所在区间 2 在顺序表的某个区间内进行查找 注意 索引可以根据查找表的特点来构造 可见 索引顺序查找的过程也是一个 缩小区间 的查找过程 性能分析 平均查找长度 ASLbs Lb Lw 在块中查找元素的平均查找长度 在索引表中查找所在块的平均查找长度 若将长度为n的表均分成b块 每块含s个记录 b n s 并设表中每个记录的查找概率相等 则每块查找的概率为1 b 块中每个记录的查找概率为1 s 1 用顺序查找确定所在块 2 用折半查找确定所在块 查找方法比较 9 2动态查找树表 n 1 n nlogn 综合上一节讨论的几种查找表的特性 查找插入删除 无序顺序表无序线性链表有序顺序表静态查找树表 n n logn logn 1 1 n nlogn 1 从查找性能看 最好情况能达 logn 此时要求表有序 2 从插入和删除的性能看 最好情况能达 1 此时要求存储结构是链表 可得如下结论 动态查找表 特点 表结构本身是在查找过程中动态生成的 即对于给定值key 若表中存在关键字等于key的记录 则查找成功返回 否则 插入关键字等于key的记录 一 二叉排序树 二叉查找树 1 定义 2 查找算法 3 插入算法 4 删除算法 5 查找性能的分析 1 若它的左子树不空 则左子树上所有结点的值均小于根结点的值 1 定义 二叉排序树或者是一棵空树 或者是具有如下特性的二叉树 3 它的左 右子树也都分别是二叉排序树 2 若它的右子树不空 则右子树上所有结点的值均大于根结点的值 50 30 80 20 90 10 85 40 35 25 23 88 例如 是二叉排序树 66 不 通常 取二叉链表作为二叉排序树的存储结构 typedefstructBiTNode 结点结构structBiTNode lchild rchild 左右孩子指针 BiTNode BiTree TElemTypedata 2 二叉排序树的查找算法 1 若给定值等于根结点的关键字 则查找成功 2 若给定值小于根结点的关键字 则继续在左子树上进行查找 3 若给定值大于根结点的关键字 则继续在右子树上进行查找 否则 若二叉排序树为空 则查找不成功 50 30 80 20 90 85 40 35 88 32 例如 二叉排序树 查找关键字 50 50 50 35 50 30 40 35 50 90 50 80 90 95 从上述查找过程可见 在查找过程中 生成了一条查找路径 从根结点出发 沿着左分支或右分支逐层向下直至关键字等于给定值的结点 或者 从根结点出发 沿着左分支或右分支逐层向下直至指针指向空树为止 查找成功 查找不成功 算法描述如下 StatusSearchBST BiTreeT KeyTypekey BiTreef BiTree SearchBST 否则表明查找不成功 返回 指针p指向查找路径上访问的最后一个结点 并返回函数值为FALSE 指针f指向当前访问 的结点的双亲 其初始调用值为NULL if T elseif EQ key T data key elseif LT key T data key else p f returnFALSE 查找不成功 p T returnTRUE 查找成功 SearchBST T lchild key T p 在左子树中继续查找 SearchBST T rchild key T p 在右子树中继续查找 30 20 10 40 35 25 23 f T 设key 48 f T f T 22 p f T f T T T T f f f p 根据动态查找表的定义 插入 操作在查找不成功时才进行 3 二叉排序树的插入算法 若二叉排序树为空树 则新插入的结点为新的根结点 否则 新插入的结点必为一个新的叶子结点 其插入位置由查找过程得到 StatusInsertBST BiTree InsertBST s BiTree malloc sizeof BiTNode 为新结点分配空间s data e s lchild s rchild NULL if p T s 插入s为新的根结点 elseif LT e key p data key p lchild s 插入 s为 p的左孩子elsep rchild s 插入 s为 p的右孩子 returnTRUE 插入成功 输入数据 建立二叉搜索树的过程 输入数据 53 78 65 17 87 09 81 15 53 53 78 53 78 65 1 被删除的结点是叶子 2 被删除的结点只有左子树或者只有右子树 3 被删除的结点既有左子树 也有右子树 4 二叉排序树的删除算法 可分三种情况讨论 和插入相反 删除在查找成功之后进行 并且要求在删除二叉排序树上某个结点之后 仍然保持二叉排序树的特性 50 30 80 20 90 85 40 35 88 32 1 被删除的结点是叶子结点 例如 被删关键字 20 88 其双亲结点中相应指针域的值改为 空 50 30 80 20 90 85 40 35 88 32 2 被删除的结点只有左子树或者只有右子树 其双亲结点的相应指针域的值改为 指向被删除结点的左子树或右子树 被删关键字 40 80 50 30 80 20 90 85 40 35 88 32 3 被删除的结点既有左子树 也有右子树 40 40 以其前驱替代之 然后再删除该前驱结点 被删结点 前驱结点 被删关键字 50 StatusDeleteBST BiTree 不存在关键字等于key的数据元素else DeleteBST 算法描述如下 if EQ key T data key 找到关键字等于key的数据元素elseif LT key T data key else Delete T returnTRUE DeleteBST T lchild key 继续在左子树中进行查找 DeleteBST T rchild key 继续在右子树中进行查找 voidDelete BiTree p 从二叉排序树中删除结点p 并重接它的左子树或右子树if p rchild elseif p lchild else Delete 其中删除操作过程如下所描述 右子树为空树则只需重接它的左子树 q p p p lchild free q p p 左子树为空树只需重接它的右子树 q p p p rchild free q p p q p s p lchild while s rchild q s s s rchild s指向被删结点的前驱 左右子树均不空 p data s data if q p q rchild s lchild elseq lchild s lchild 重接 q的左子树free s p q s 5 查找性能的分析 对于每一棵特定的二叉排序树 均可按照平均查找长度的定义来求它的ASL值 显然 由值相同的n个关键字 构造所得的不同形态的各棵二叉排序树的平均查找长度的值不同 甚至可能差别很大 由关键字序列3 1 2 5 4构造而得的二叉排序树 由关键字序列1 2 3 4 5构造而得的二叉排序树 例如 2 1 3 4 5 3 5 4 1 2 ASL 1 2 3 4 5 5 3 ASL 1 2 3 2 3 5 2 2 下面讨论平均情况 不失一般性 假设长度为n的序列中有k个关键字小于第一个关键字 则必有n k 1个关键字大于第一个关键字 由它构造的二叉排序树 n k 1 k 的平均查找长度是n和k的函数 P n k 0 k n 1 假设n个关键字可能出现的n 种排列的可能性相同 则含n个关键字的二叉排序树的平均查找长度 在等概率查找的情况下 由此 可类似于解差分方程 此递归方程有解 一 哈希表是什么 二 哈希函数的构造方法 三 处理冲突的方法 四 哈希表的查找 9 3哈希表 以上两节讨论的表示查找表的各种结构的共同特点 记录在表中的位置和它的关键字之间不存在一个确定的关系 一 哈希表是什么 查找的过程为给定值依次和关键字集合中各个关键字进行比较 查找的效率取决于和给定值进行比较的关键字个数 用这类方法表示的查找表 其平均查找长度都不为零 不同的表示方法 其差别仅在于 关键字和给定值进行比较的顺序不同 只有一个办法 预先知道所查关键字在表中的位置 对于频繁使用的查找表 希望ASL 0 即 要求 记录在表中位置和其关键字之间存在一种确定的关系 若以下标为000 999的顺序表表示之 例如 为每年招收的1000名新生建立一张查找表 其关键字为学号 其值的范围为xx000 xx999 前两位为年份 则查找过程可以简单进行 取给定值 学号 的后三位 不需要经过比较便可直接从顺序表中找到待查关键字 但是 对于动态查找表而言 因此在一般情况下 需在关键字与记录在表中的存储位置之间建立一个函数关系 以f key 作为关键字为key的记录在表中的位置 通常称这个函数f key 为哈希函数 1 表长不确定 2 在设计查找表时 只知道关键字所属范围 而不知道确切的关键字 Zhao Qian Sun Li Wu Chen Han Ye Dei 例如 对于如下9个关键字 设哈希函数f key Ord 第一个字母 Ord A 1 2 Chen Zhao Qian Sun Li Wu Han Ye Dei 问题 若添加关键字Zhou 怎么办 能否找到另一个哈希函数 1 哈希函数是一个映象 即 将关键字的集合映射到某个地址集合上 它的设置很灵活 只要这个地址集合的大小不超出允许范围即可 从这个例子可见 2 由于哈希函数是一个压缩映象 因此 在一般情况下 很容易产生 冲突 现象 即 key1 key2 而f key1 f key2 3 很难找到一个不产生冲突的哈希函数 一般情况下 只能选择恰当的哈希函数 使冲突尽可能少地产生 因此 在构造这种特殊的 查找表 时 除了需要选择一个 好 尽可能少产生冲突 的哈希函数之外 还需要找到一种 处理冲突 的方法 哈希表的定义 根据设定的哈希函数H key 和所选中的处理冲突的方法 将一组关键字映象到一个有限的 地址连续的地址集 区间 上 并以关键字在地址集中的 象 作为相应记录在表中的存储位置 如此构造所得的查找表称之为 哈希表 二 构造哈希函数的方法 对数字的关键字可有下列构造方法 若是非数字关键字 则需先对其进行数字化处理 1 直接定址法 3 平方取中法 5 除留余数法 4 折叠法 6 随机数法 2 数字分析法 哈希函数为关键字的线性函数H key key或者H key a key b 1 直接定址法 此法仅适合于 地址集合的大小 关键字集合的大小 例 有一组关键码如下 942148 941269 940527 941630 941805 941558 942047 940001 散列函数为h K K 940000h 942148 2148h 941269 1269h 940527 527h 941630 1630h 941805 1805h 941558 1558h 942047 2047h 940001 1可以按计算出的地址存放记录 此方法仅适合于 能预先估计出全体关键字的每一位上各种数字出现的频度 2 数字分析法 假设关键字集合中的每个关键字都是由s位数字组成 u1 u2 us 分析关键字集中的全体 并从中提取分布均匀的若干位或它们的组合作为地址 34705243491487348269634852703486305349805834796713473919 例 有一组 例如80个 关键码 其样式如下 讨论 第1 2位均是 3和4 第3位也只有 7 8 9 因此 这几位不能用 余下四位分布较均匀 可作为哈希地址选用 若哈希地址取两位 因元素仅80个 则可取这四位中的任意两位组合成哈希地址 也可以取其中两位与其它两位叠加求和后 取低两位作哈希地址 以关键字的平方值的中间几位作为存储地址 求 关键字的平方值 的目的是 扩大差别 同时平方值的中间各位又能受到整个关键字中各位的影响 3 平方取中法 此方法适合于 关键字中的每一位都有某些数字重复出现频度很高的现象 例 2589的平方值为6702921 可以取中间的029为地址 将关键字分割成若干部分 然后取它们的叠加和为哈希地址 有两种叠加处理的方法 移位叠加和间界叠加 4 折叠法 此方法适合于 关键字的数字位数特别多 法1 移位法 将各部分的最后一位对齐相加 法2 间界叠加法 从一端向另一端沿分割界来回折叠后 最后一位对齐相加 例 元素42751896 用法1 427 518 96 1041用法2 42751896 724 518 69 1311 5 除留余数法 设定哈希函数为 H key keyMODp其中 p m 表长 并且p应为不大于m的素数或是不含20以下的质因子 给定一组关键字为 12 39 18 24 33 21 若取p 9 则他们对应的哈希函数值将为 3 3 0 6 6 3 例如 为什么要对p加限制 可见 若p中含质因子3 则所有含质因子3的关键字均映射到 3的倍数 的地址上 从而增加了 冲突 的可能 H 例 有一线性表A 18 75 60 43 54 90 46 哈希函数为 h K K p 取m 13 p 13 h 18 18 13 5h 75 75 13 10h 60 60 13 8h 43 43 13 4h 54 54 13 2h 90 90 13 12h 46 46 13 7 6 随机数法 设定哈希函数为 H key Random key 其中 Random 不能是一般的随机函数 固定的参数必须返回确定的值 通常 此方法用于对长度不等的关键字构造哈希函数 以上介绍了几种常用的散列函数 在实际工作中应根据关键码的特点 选用适当的方法 有人曾用 轮盘赌 的统计分析方法对它们进行了模拟分析 结论是平方取中法最接近于 随机化 在应用平方取中法时 若关键码不是整数而是字符串时 可以把每个字符串转换成整数 实际造表时 采用何种构造哈希函数的方法取决于建表的关键字集合的情况 包括关键字的范围和形态 总的原则是使产生冲突的可能性降到尽可能地小 三 处理冲突的方法 有6个元素的关键码分别为 14 23 39 9 25 11 选取关键码与元素位置间的函数为H k kmod7 通过哈希函数对6个元素建立哈希表 25 39 23 9 14 冲突现象举例 6个元素用7个地址应该足够 H 14 14 7 0 11 H 25 25 7 4H 11 11 7 4 有冲突 处理冲突 的实际含义是 为产生冲突的地址寻找下一个哈希地址 1 开放定址法 2 链地址法 为产生冲突的地址H key 求得一个地址序列 H0 H1 H2 Hs1 s m 1其中 H0 H key Hi H key di MODmi 1 2 s 1 开放定址法 对增量di有三种取法 1 线性探测再散列di c i最简单的情况c 12 平方探测再散列di 12 12 22 22 3 随机探测再散列di是一组伪随机数列或者di i H2 key 又称双散列函数探测 关键码集为 47 7 29 11 16 92 22 8 3 设 哈希表表长为m 11 哈希函数为Hash key keymod11 拟用线性探测法处理冲突 建哈希表如下 解释 47 7是由哈希函数得到的没有冲突的哈希地址 012345678910 29 22 8 3 Hash 29 7 哈希地址有冲突 需寻找下一个空的哈希地址 由H1 Hash 29 1 mod11 8 哈希地址8为空 因此将29存入 另外 22 8 3同样在哈希地址上有冲突 也是由H1找到空的哈希地址的 其中3还连续移动了两次 二次聚集 线性探测法的优点 只要哈希表未被填满 保证能找到一个空地址单元存放有冲突的元素 线性探测法的缺点 可能使第i个哈希地址的同义词存入第i 1个哈希地址 这样本应存入第i 1个哈希地址的元素变成了第i 2个哈希地址的同义词 因此 可能出现很多元素在相邻的哈希地址上 堆积 起来 大大降低了查找效率 解决方案 可采用二次探测法或伪随机探测法 以改善 堆积 问题 讨论 仍举上例 改用二次探测法处理冲突 建表如下 012345678910 注 只有3这个关键码的冲突处理与上例不同 Hash 3 3 哈希地址上冲突 由H1 Hash 3 12 mod11 4 仍然冲突 H2 Hash 3 12 mod11 2 找到空的哈希地址 存入 2 二次探测法 Hi Hash k di mod11其中 Hash k 为哈希函数di为增量序列12 12 22 22 q2 关键码集为 47 7 29 11 16 92 22 8 3 H2 key 是另设定的一个哈希函数 它的函数值应和m互为素数 若m为素数 则H2 key 可以是1至m 1之间的任意数 若m为2的幂次 则H2 key 应是1至m 1之间的任意奇数 例如 关键字集合 19 01 23 14 55 68 11 82 36 H key keyMOD11 当m 11时 可设H2 key 3key MOD10 1 19 01 23 14 55 68 11 82 36 211121213 将所有哈希地址相同的记录都链接在同一链表中 2 链地址法 0123456 14 01 36 19 82 23 11 68 55 ASL 6 1 2 2 3 9 13 9 例如 同前例的关键字 哈希函数为H key keyMOD7 查找过程和造表过程一致 假设采用开放定址处理冲突 则查找过程为 四 哈希表的查找 对于给定值K 计算哈希地址i H K 若r i NULL则查找不成功 若r i key K则查找成功 否则 求下一地址Hi 直至r Hi NULL 查找不成功 或r Hi key K 查找成功 为止 inthashsize 997 typedefstruct ElemType elem intcount 当前数据元素个数intsizeindex hashsize sizeindex 为当前容量 HashTable defineSUCCESS1 defineUNSUCCESS0 defineDUPLICATE 1 开放定址哈希表的存储结构 StatusSearchHash HashTableH KeyTypeK int p int c 在开放定址哈希表H中查找关键码为K的记录 SearchHash p Hash K 求得哈希地址 while H elem p key NULLKEY 求得下一探查地址p if EQ K H elem p key returnSUCCESS 查找成功 返回待查数据元素位置p elsereturnUNSUCCESS 查找不成功 StatusInsertHash HashTable H Elemtypee InsertHash c 0 if HashSearch H e key p c SUCCESS returnDUPLICATE 表中已有与e有相同关键字的元素 elseH elem p e H count returnOK 查找不成功时 返回p为插入位置 elseRecreateHashTable H 重建哈希表 if c hashsize H sizeindex 2 冲突次数c未达到上限 阀值c可调 1 选用的哈希函数 2 选用的处理冲突的方法 3 哈希表饱和的程度 装载因子 n m值的大小 n 记录数 m 表的长度 决定哈希表查找的ASL的因素 哈希表查找的分析 从查找过程得知 哈希表查找的平均查找长度实际上并不等于零 一般情况下 可以认为选用的哈希函数是 均匀