数据结构第9章查找

1、查找表查找表（Search Table）是由一些具有相同可辨认特性的数据元素（或记录）构成的集合。关键字关键字（key）是数据元素中某个数据项的值，用它可以标识（识别）一个数据元素。主关键字唯一地标识一个元素， 次关键字识别若干元素 查找查找（searching）根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。 定义：定义：查找过程中先后和给定值进行比较的关键字个数的期望值称作查找算法的平均查找长度平均查找长度(Average Search Length)。 查找表通常可分两类： 1.静态查找表静态查找表 2.动态查找表动态查找表如何评价查找算法的时间效率？对查找表经常进行的

2、操作有：（1）查询某个特定的数据元素是否在表中；（2）检索某个特定的数据元素的各种属性；（3）在查找表中插入一个数据元素；（4）从查找表中删除某个数据元素。9.1 静态查找表9.1.1 顺序表的查找实现静态查找表的最简单的方法是以“顺序存储结构的线性表-顺序表”表示之 。查找过程为：从第一个或最后一个数据元素起，逐个进行“比较”直至其中某个数据元素的关键字等于给定值为止。 缺点：其平均查找长度较大，特别是当表中记录数 n 很大时，查找效率较低。优点：算法简单且适应面广，无论表中记录是否按关键字有序排列均可应用，而且，上述讨论对链式存储的线性表也同样适用。 9.1.2 有序表的查找 折半查找(B

3、inary Search)又称二分查找折半查找的过程为：给定值首先和处于待查区间“中间位置”的关键字进行比较，若相等，则查找成功，否则将查找区间缩小到“前半个区间” 或 “后半个区间” 之后继续进行查找。例如，在有序表(05,13,19,21,37,56,64,75,80,88,92)中查找关键字为21和85的数据元素。算法算法 int Search_Bin ( SSTable ST, KeyType kval ) / 在有序表在有序表ST中折半查找其关键字等于中折半查找其关键字等于kval的数据元素，的数据元素，/ 若找到，则函数值为该元素在表中的位置，否则为若找到，则函数值为该元素在表中的

4、位置，否则为0。low = 1; high = ST.length; / 置区间初值while (low = high) mid = (low + high) / 2;if ( kval = ST.elemmid.key )return mid; / 找到待查元素else if ( kval ST.elemmid.key )high = mid - 1; / 继续在前半区间内进行查找else low = mid + 1;/ 继续在后半区间内进行查找 / whilereturn 0; / 有序表中不存在待查元素 / Search_Bin9.1.3 索引顺序表的查找 线性表中的记录按关键字“分段有

5、序” 称它为分块有序表)，同时，另建一个索引，由分块有序表和相应的索引构成一个索引顺序表， 索引表最大关键字起始地址9.2动态查找表9.2.1 动态查找表的类型定义 动态查找表的特点：在查找过程中尚需进行插入或删除的操作。因此，表示动态查找表的结构应不仅便于查找，还应便于插入和删除。抽象数据类型动态查找表的定义参见教材P226-2279.2.2 二叉查找树 一、二叉查找树的定义一、二叉查找树的定义 二叉查找树或者是一棵空树；或者是具有如下特性的二叉树：（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值；（3）它的左、右

6、子树也都分别是二叉查找树。例如，下图所示是一棵二叉查找树 二叉链表作为二叉查找树的存储结构typedef struct BiTNode / 结点结构 ElemType data;/ 数据元素struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BSTree; 例如，下图所示是不是一棵二叉查找树？ 二、二叉查找树的二、二叉查找树的查找算法查找算法 若二叉查找树为空，则查找不成功；否则1）若给定值等于根结点的关键字，则查找成功；2）若给定值小于根结点的关键字，则继续在左子树上进行查找；3）若给定值大于根结点的关键字，则继续在右子树上进行查找。 三、

7、二叉查找树的插入算法 二叉查找树结构本身正是从空树开始逐个插入生成的。 插入的原则：若二叉查找树为空树空树，则插入的结点为新的根结点新的根结点；否则，插入的结点必为一个新的叶子结点新的叶子结点，其插入位置插入位置由查找过程确定。 例如，若给定值序列为 50,30,40,80,20,36,90,40,38 四、二叉查找树的四、二叉查找树的删除算法删除算法 分三种情况讨论：(1) 被删结点为“叶子”，仅需修改其双亲结点的相应指针；(2) 被删结点只有左子树或右子树，则只需保持该结点的子树和其双亲之间原有的关系 (3) 被删结点的左右子树均不空。 四、二叉查找树的四、二叉查找树的删除算法删除算法 F

8、PPLPRfp（a）（b）fFPCPRCLQQLSLScpqs四、二叉查找树的四、二叉查找树的删除算法删除算法 FCCLfc（c）SLPRSs方法方法1*p的左子树为的左子树为*f的左子树的左子树*p的右子树为的右子树为*s的右子树的右子树（b）fFPCPRCLQQLSLScpqs四、二叉查找树的四、二叉查找树的删除算法删除算法 （d）fFSCPRCLQQLSLcpq方法方法2*p的直接前的直接前驱或直接后驱或直接后继代替继代替*p，然后再从二然后再从二叉排序树中叉排序树中删除它的直删除它的直接前驱或直接前驱或直接后继。接后继。（b）fFPCPRCLQQLSLScpqs参见教材参见教材p230

9、算法算法9.7算法算法9.89.2.3 平衡二叉(查找)树 平衡二叉树：它或是空树，或具有下列特性：其左子树和右子树都是平衡二叉树，且左右子树深度之差的绝对值不大于1。 平衡二叉树非平衡二叉树树中结点内的数值称作结点的平衡因子，定义为左子树的深度减去右子树的深度。 平衡处理的原则是保证二叉查找树始终处于平衡状态。从空树起（空树是平衡树），每插入一个关键字都需要检查二叉查找树是否失去平衡，如因插入新的结点引起不平衡，则需对它进行平衡旋转处理。 9.3 哈希表 9.3.1 何谓哈希表 记录在表中的位置为关键字的某个函数，通常称这种函数为“哈希函数哈希函数”。 若关键字不同而函数值相同，则称这两个关

10、键字（对于该哈希函数而言）为同义词，并称这种现象为冲突。 根据设定的哈希函数哈希函数 H(key)和所选中的处理冲突处理冲突的方法，将一组关键字映象到一个映象到一个有限的、地址连续的地址集地址集(区间区间)上上，并以关键字在地址集中的象象作为相应记录在表中的存储位置，这种表被称为哈希表哈希表，这一映象的过程亦被称为散列散列。 9.3.2 构造哈希函数的方法 若对于关键字集合中的任意一个关键字，经哈希函数映象到地址集合中任何一个地址的概率相等，则称此类哈希函数为均匀的哈希函数 构造均匀的哈希函数的方法有如下几种：一、直接定址法 Hash(key)=key 或 Hash(key)=a key+b

11、（a 和 b 均为常数） 直接定址所得地址集的大小和关键字集的大小相同，关键字和地址一一对应，决不会产生冲突。但实际应用中能采用直接定址的情况极少。二、数字分析法 如果可能出现的关键字的数位相同，且取值事先知道，则可对关键字进行分析，取其中“分布均匀”的若干位或它们的组合作为哈希表的地址。 02146532021722420228742702201367022288170223298202354152023685350231932702395715 例如 已知80个记录的关键字为8位十进制数（右图列出其中部分），假设哈希表的表长为100，即地址为0099。三、平方取中法 如果关键字的所有各位分

12、布都不均匀，则可取关键字的平方值的中间若干位作为哈希表的地址。 例如：右表八进制数的关键字及其哈希地址关键字(关键字)2哈希地址010000100000101100121000021012001440000440116013704003702061431054131020624314704314216147347417342162474130474121634745651745四、折叠法四、折叠法 若关键字的位数很多，且每一位上数字分布大致均匀，则可采用移位叠加移位叠加或间界叠加间界叠加，即将关键字分成若干部分，然后以它们的叠加和(舍去进位)作为哈希地址。 例如，key = 110108780

13、428895 ，(哈希表的表长为1000) 895 824 780 801+）110 3410 895 428 780 108+）110 2321间界叠加移位叠加五、除留余数法五、除留余数法 以关键字被某个数p除后所得余数作为哈希地址。 即 Hash(key) = key MOD p 其中，MOD表示取模运算，p 为不大于表长的素数或不包含小于20的质因素的合数。 六、随机数法六、随机数法当关键字不等长时，可取关键字的某个伪随机函数值作为哈希地址。Hash(key) = random(key) 对于非数值型关键字，则需先将它们转化为数字。实际造表时，采用何种采用何种构造哈希函数的方法方法取决于

14、建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小使产生冲突的可能性降到尽可能地小。 9.3.3 处理冲突的方法处理冲突的方法有两类处理冲突的方法:一、开放定址法一、开放定址法 二、链地址法二、链地址法 一、开放定址 处理冲突的办法是，设法为发生冲突的关键字找到哈希表中另一个尚未被记录占用的位置。哈希表的表长为m（即哈希表中可用地址为：0m-1），若关键字key，Hash(key)的位置已被占用，则下一个地址H1=(Hash(key)+d1)MODm，若也已被占用，则再H2=(Hash(key)+d2)MODm，依次类推直至找到一个地址Hs=(Hash

15、(key)+ds)MODm未被占用为止。即Hi是为解决冲突生成的一个地址序列，其值取决于设定增量序列di。对于di通常可有三种设定方法： “线性探测再散列”，di=1,2,3,m-1，2.“平方探测再散列”， di = 12,-12, 22 , -22 , k2(km/2)，3.伪随机探测再散列“或”双散列函数探测再散列 为伪随机数列或者di=i H2(key)，（H2 (key)为关键字的另一个哈希函数） 按线性探测再散列处理冲突构造的哈希表为：按平方探测再散列处理冲突构造的哈希表为：按双散列函数探测处理冲突构造的哈希表为：二、链地址法 将所有关键字为同义词的记录链接在一个线性链表中 例如，

16、假设关键字序列为 19,56,23,14,68,82,70,36,91 ，哈希表的表长为 7，哈希函数为 Hash(key)=key % 7，则构建的以链地址处理冲突的哈希表如flash9-4-2所示。 9.4.4 开放定址的哈希表的查找和插入 在利用开放定址处理冲突的哈希表中进行查找时，首先应计算给定值的哈希函数值，若表中该位置上没有记录， 则表明关键字等于给定值的记录不存在；若该位置上的记录的关键字和给定值不等， 则依据建表时设定的增量值寻找“下一个”地址，直至查找成功(即某个位置上的记录的关键字等于给定值)或查找不成功（哈希表中不存在关键字等于给定值的记录），且在查找不成功的情况下，该地

17、址为新的记录的插入位置。 本章小结 在本章中介绍了查找表的三类存储表示方法：顺序表、树表和哈希表。这里的顺序表指的是顺序存储结构，包括有序表和索引顺序表，因此主要用于表示静态查找表，树表包括静态查找树、二叉查找树，树表和哈希表主要用于表示动态查找表。 查找树的特点是，每经过一次比较便可将继续查找的范围缩小到某一棵子树上，但查找树并不仅限于二叉树，以后还将介绍其它形式的查找树。 所有顺序结构的表和查找树的平均查找长度都是随之查找表中记录数的增加而增大，而哈希表的平均查找长度是装填因子的函数，因此有可能设计出使平均查找长度不超过某个期望值的哈希表。 课后习题 1.试分别画出在线性表(a,b,c,d,e,e,f)中进行折半查找，以查关键字等于 e、f 和 g 的过程。 2.选取哈希函数 H(k)=(3k) MO