数据结构 第8章 查找(作业).ppt

图8.12 不平衡二叉树的调整(4) 1） LL型 图8.13 二叉排序树的LL型平衡旋转 2） LR型 图8.14 二叉排序树的LR型平衡旋转 图8.15 二叉排序树的RR型平衡旋转 3） RR型 4） RL型 图8.16 二叉排序树的RL型平衡旋转 8.4 哈希表 哈希法又称散列法、杂凑法或关键字地址计算法等，相应的表称为哈希表。这种方法的基本思想：首先在元素的关键字k和元素的存储位置p之间建立一个对应关系H，使得p=H(k)，H称为哈希函数。创建哈希表时，把关键字为k的元素直接存入地址为H(k)的单元；以后当查找关键字为k的元素时，再利用哈希函数计算出该元素的存储位置p=H(k)，从而达到按关键字直接存取元素的目的。 当关键字集合很大时，关键字值不同的元素可能会映象到哈希表的同一地址上，即 k1≠k2，但 H（k1）=H（k2），这种现象称为冲突，此时称k1和k2为同义词。实际中，冲突是不可避免的， 只能通过改进哈希函数的性能来减少冲突。  综上所述， 哈希法主要包括以下两方面的内容：  (1） 如何构造哈希函数； (2） 如何处理冲突。 8.4.1 哈希函数的构造方法 1. 直接定址法 哈希函数为关键字的线性函数，即H(key)=key或者H(key)=a·key+b (a和b为常数)。 此方法适合于地址集合的大小=关键字集合的大小。 例：P253 解放后出生的人口调查表 2. 数字分析法 如果事先知道关键字集合，并且每个关键字的位数比哈希表的地址码位数多时，可以从关键字中选出分布较均匀的若干位，构成哈希地址。 例如有80个记录，关键字为8位十进制整数d1d2d3…d7d8，如哈希表长取100，则哈希表的地址空间为： 00~99。假设经过分析，各关键字中d4和d7的取值分布较均匀， 则哈希函数为：H(key)=H(d1d2d3…d7d8)=d4d7。例如， H=43，H=06。 8 1 3 4 6 5 3 2 8 1 3 7 2 2 4 2 8 1 3 8 7 4 2 2 8 1 3 0 1 3 6 7 8 1 3 2 2 8 1 7 8 1 3 3 8 9 6 7 8 1 3 5 4 1 5 7 8 1 3 6 8 5 3 7 8 1 4 1 9 3 5 5 ①② ③ ④ ⑤ ⑥ ⑦⑧ ④⑤⑥⑦数字分布近乎随机, 可取其中任意两位或取其中 两位与另两位的叠加求和后 舍去进位作哈希地址 3. 平方取中法 当无法确定关键字中哪几位分布较均匀时， 可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。  * 第8章 查找 第8章 查找 8.1 查找的基本概念 8.2 静态查找表 8.3 动态查找表 8.4 哈希表 8.1 查找的基本概念 关键字：数据元素的某个数据项的值，用它可以标识列表中的一个或一组数据元素。如果一个关键字可以唯一标识列表中的一个数据元素， 则称其为主关键字，否则为次关键字。当数据元素仅有一个数据项时， 数据元素的值就是关键字。 查找：根据给定的关键字值，在查找表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在查找表中的位置。若找到相应的数据元素，则称查找是成功的，否则称查找是失败的，此时应返回空地址及失败信息，并可根据要求插入这个不存在的数据元素。 8.2 静态查找表 8.2.1 顺序查找法 顺序查找法的过程是：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，否则查找失败。存储结构通常为顺序结构，也可为链式结构。 //静态查找表的顺序存储结构 typedef struct { ElemType *elem; //数据元素存储空间基址，建 //表时按实际长度分配，0号单元留空