严蔚敏版数据结构(C语言版)-第九章资料简介.ppt

数 据 结 构 第 9 章 查找 9.4 计算式查找法—哈希表 以上两节讨论的表示查找表的各种结构的 共同特点： 哈希表是什么？ 2.查找的过程为给定值依次和关 键字集合中各个关键字进行比较; 3.查找的效率取决于和给定值进 行比较的关键字个数。 1.记录在表中的位置和它的关键 字之间不存在一个确定的关系； 用这类方法表示的查找表，其 平均查找长度都不为零。 不同的表示方法，其差别仅在于： 关键字和给定值进行比较的顺序不同。 数 据 结 构 第 9 章 查找 9.4 计算式查找法—哈希表 只有一个办法： 预先知道所查关键字在表中的位置。 对于频繁使用的查找表，希望 ASL = 0。 即要求： 记录在表中位置和其关键字之间存在一种确定的关系。 数 据 结 构 第 9 章 查找 9.4 计算式查找法—哈希表 若以下标为000 ~ 999 的顺序表表示之。 例如：为每年招收的 1000 名新生建立一张查找表，其关键字为学号，其值的范围为 xx000 ~ xx999 (前 两位为年份)。 则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较便可直接从顺序表中找到待查关键字。 数 据 结 构 第 9 章 查找 9.4 计算式查找法—哈希表 但是，对于动态查找表而言， 因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以 f(key) 作为关键字为 key 的记录在表中的位置，通常称这个函数 f(key) 为哈希函数。 1）表长不确定； 2）在设计查找表时，只知道关键字所 属范围，而不知道确切的关键字。 数 据 结 构 第 9 章 查找 9.4 计算式查找法—哈希表 {Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Dei} 例如：对于如下 9 个关键字 设 哈希函数 f(key) = ?(Ord(第一个字母) -Ord(A)+1)/2? 问题: 若添加关键字 Zhou , 怎么办？ 能否找到另一个哈希函数？ 9 10 11 13 12 8 7 6 5 4 3 2 1 0 Chen Zhao Qian Sun Li Wu Han Ye Dei 数 据 结 构 第 9 章 查找 9.4 计算式查找法—哈希表 1）哈希函数是一个映象，即将关键字的集合映 射到某个地址集合上， 它的设置很灵活，只 要这个地址集合的 大小不超出允许范围即可； 从这个例子可见： 2）由于哈希函数是一个压缩映象，因此，在一 般情况下，很容易产生“冲突”现象， 即： key1? key2，而 f(key1) = (key2)。 数 据 结 构 第 9 章 查找 9.4 计算式查找法—哈希表 3) 很难找到一个不产生冲突的哈希函数。 一般情况下，只能选择恰当的哈希函数， 使冲突尽可能少地产生。 因此，在构造这种特殊的“查找表” 时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外；还需要找到一种“处理冲突” 的方法。 数 据 结 构 第 9 章 查找 9.4 计算式查找法—哈希表 哈希表的定义： 根据设定的哈希函数 H(key) 和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集 (区间) 上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。 数 据 结 构 第 9 章 查找 9.4 计算式查找法—哈希表 ①构造哈希函数的方法 对数字的关键字可有下列构造方法： 若是非数字关键字，则需先对其进行 数字化处理。 1. 直接定址法 3. 平方取中法 5. 除留余数法 4. 折叠法 6. 随机数法 2. 数字分析法 * * 数 据 结 构 9.1 查找的基本概念 第 9 章 查找 9.2 基于线性表的查找法 9.3 基于树的查找法 9.4 计算式查找法—哈希表 数 据 结 构 9.1 查找的基本概念 第 9 章 查找 查找表是由同一类型的数据元素(或记录)构成的集合。 由于“集合”中的数据元素之间存在着松散 的关系，因此查找表是一种应用灵便的结构。 数 据 结 构 9.1 查找的基本概念 第 9 章 查找 对查找表常进行的操作: 1）查询某个“特定的”数据元素是否在查找表中 静态 查找 动态查找 3）在查找表中插入一个数据元素 2）检索某个“特定的”数据元素的各种属性 4）从查找表中删去某个数据元素 数 据 结 构 9.1 查找的基本概念 第 9 章 查找 查找表的分类 仅作查询和检索操作