第九章 查找 ￡9.1 概述 ￡9.2 静态查找表 ￡9.3 动态查找表 ￡9.4 哈希表 ￡9.1.1 查找表 ￡9.2.1 概述 第九章 查找 ￡9.1 概述 ￡9.2 静态查找表 ￡9.1.1 查找表 ￡9.2.1 概述 ￡9.1.2 相关术语 ￡9.2.2 顺序表的查找 ￡9.1.3 类型说明 ￡9.2.3 有序表的查找 ￡9.2.4 索引顺序表的查找 ￡9.3 动态查找表 ￡9.4 哈希表 ￡9.3.1 概述 ￡9.4.1 定义 ￡9.3.2 二叉排序树和平衡二叉树 ￡9.4.2 哈希函数的构造 ￡9.3.3 B-树和B+树 ￡9.4.3 处理冲突的方法 ￡9.4.4 哈希表的查找及其分析

￡9.1 概述 ￡9.1.1 查找表 查找表（Search Table）：是由同一类型的数据元素（或记录）构 成的集合。 静态查找表（Static Search Table）：只对查找表作“查找”操作的 一类查找表。 动态查找表（Dynamic Search Table）：对查找表不仅作“查找”操 作，在查找过程中还同时插入查找表中不存在的数据元素，或者从查找 表中删除已存在的某个数据元素的一类查找表。 对查找表经常进行的操作通常有： （1）查询某个“特定的”数据元素是否在查找表中； （2）检索某个“特定的”数据元素的各种属性； （3）在查找表中插入一个数据元素； （4）从查找表中删去某个数据元素。

￡9.1.2 相关术语 关键字（Key）：是数据元素（或记录）中某个数据项的值，用 它可以标识（识别）一个数据元素（或记录）。 主关键字（Primary Key）：可以唯一的标识一个建立的关键字。 次关键字（Secondary Key）：用以识别若干记录的关键字。 查找（Searching）：根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。 查找成功：查找表中存在关键字等于给定值的记录。此时查找的结果为给出整个记录的信息，或指示该记录在查找表中的位置。 查找失败：查找表中不存在关键字等于给定值的记录。此时查找 的结果可给出一个“空”记录或“空”指针。

￡9.1.3 类型说明 以下是在本章以后各节的讨论中涉及的关键字类型和数据元素类型 的统一说明： 典型的关键字类型说明： typedef float KeyType; //实型 typedef int KeyType; //整型 typedef char* KeyType; //字符串型 数据元素类型说明： typedef struct { KeyType key; //关键字域 … //其他域 } ElemType; 对两个关键字比较的宏定义： //-----对数值型关键字 #define EQ(a, b) ((a) = = (b)) #define LT(a, b) ((a) < (b)) #define LQ(a, b) ((a) < = (b)) … //-----对字符串型关键字 #define EQ(a, b) (!strcmp ((a) , (b))) #define LT(a, b) (strcmp ((a) , (b)) < 0) #define LQ(a, b) (strcmp ((a) , (b)) < = 0) …

￡9.2 静态查找表 ￡9.2.1 概述 （1）静态查找表的抽象数据类型定义： ADT StaticSearchTable { 数据对象D：D是具有相同特性的数据元素的集合。各个数据元 素均含有类型相同，可唯一标识数据元素的关键字。 数据关系R：数据元素同属一个集合。 基本操作P： Create (&ST, n); 操作结果：构造一个含n个数据元素的静态查找表ST。 Destroy (&ST); 初始条件：静态查找表ST存在。 操作结果：销毁表ST。 Search (ST, key); 初始条件：静态查找表ST存在，key为和关键字类型相同的给定值。 操作结果：若ST中存在其关键字等于key的数据元素，则函数值为 该元素的值或在表中的位置，否则为“空”。 Traverse (ST, Visit ( )); 初始条件：静态查找表ST存在，Visit是对元素操作的应用函数。 操作结果：按某种次序对ST的每个元素调用函数visit ( )一次且仅 一次。一旦visit ( )失败，则操作失败。 } ADT StaticSearchTable

（2）查找操作的性能分析 衡量查找算法好坏的依据：其关键字和给定值进行过比较的记录个 数的平均值。 平均查找长度（Average Search Length）：为确定记录在查找表中 的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在 查找成功时的平均查找长度。 对于含有n个记录的表，查找成功时的平均查找长度为： （9－1） 其中：Pi为查找表中查找第i个记录的概率，且 ；Ci为找到表中其关 键字与给定值相等的第i个记录时，和给定值已进行过比较的关键字个数。 查找算法的平均查找长度＝ 查找成功时的平均查找长度 ＋ 查找不成功时的平均查找长度

￡9.2.2 顺序表的查找 （1）顺序存储结构的类型定义 typedef struct { ElemType *elem; //数据元素存储空间基址，建表时按 //实际长度分配，0号单元留空 int length; //表长度 } SSTable （2）顺序查找的实现 顺序查找（Sequential Search）的查找过程为：从表中最后一个记录开 始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值 比较相等，则查找成功，找到所查记录；反之，若直至第一个记录，其关键 字和给定值比较都不等，则表明表中没有所查记录，查找不成功。 算法9.1如下： int Search_Seq (SSTable ST, KeyType key) { //在顺序表ST中顺序查找其关键字等于key的数据元素。 //若找到，则函数值为该元素在表中的位置，否则为0。 ST.elem[0].key = key; //“哨兵” for (i = ST.length; !EQ(ST.elem[i].key, key); ――i); //从后往前找 return i; //找不到时i为0 } // Search_Seq

（3）性能分析 ①只考虑查找成功时的情况 在顺序查找的过程中，式（9－1）中Ci取决于所查记录在表中的位置。 假设n＝ST.length，则顺序查找的平均长度为： ASL = nP1 + (n－1)P2 + … + 2Pn-1 + Pn 假设查找每个记录的概率相等，即 Pi＝1/n。则在等概率情况下顺序查 找的平均查找长度为： ②考虑查找成功和查找不成功时的情况 顺序查找中，不论给定值key为何值，查找不成功时和给定值进行比较的关 键字个数均为n＋1。 假设查找成功与不成功的可能性相同，对每个记录的查找概率也相等，则 Pi＝1/(2n)，此时顺序查找的平均查找长度为：

缺点：平均查找长度较大，特别是当n很大时，查找效率较低。 （4）顺序查找算法的特点 优点：算法简单且适应面广。它对表的结构无任何要求，无论 记录是否按关键字有序均可应用。 缺点：平均查找长度较大，特别是当n很大时，查找效率较低。

￡9.2.3 有序表的查找 （1）有序表查找的实现 折半查找（Binary Search）的查找过程：先选定待查记录所在范 围（区间），然后逐步缩小范围直到找到或找不到该记录为止。 算法9.2如下： int Search_Bin (SSTable ST, KeyType key) { //在有序表ST中折半查找其关键字等于key的数据元素。 //若找到，则函数值为该元素在表中的位置，否则为0。 low = 1; //置区间初值 high = ST.length; //low和high分别指示待查元素所在范围的下界和上界 while (low <= high) { mid = (low + high) / 2; //mid指示区间的中间位置 if (EQ(key, ST.elem[mid].key)) //找到待查元素 return mid; else if (LT(key, ST.elem[mid].key)) //继续在前半区间进行查找 high = mid－1; else low = mid + 1; //继续在后半区间进行查找 } // while return 0; } // Search_Bin

（2）例子 例如：已知如下11个数据元素的有序表（关键字即为数据元素的值）： （05，13，19，21，37，56，64，75，80，88，92） 现要查找关键字为21和85的数据元素。 ①给定值key＝21的查找过程： 05 13 19 21 37 56 64 75 80 88 92 high low mid ST.elem[mid].key > key, 令high = mid－1, mid = 3； 05 13 19 21 37 56 64 75 80 88 92 low mid high ST.elem[mid].key < key, 令low = mid + 1, mid = 4； 05 13 19 21 37 56 64 75 80 88 92 low mid high ST.elem[mid].key = key。查找成功。

②给定值key＝85的查找过程： 05 13 19 21 37 56 64 75 80 88 92 high low mid ST.elem[mid].key < key, 令low = mid + 1, mid = 9； 05 13 19 21 37 56 64 75 80 88 92 low mid high ST.elem[mid].key < key, 令low = mid + 1, mid = 10； 05 13 19 21 37 56 64 75 80 88 92 low mid high ST.elem[mid].key > key, 令high = mid－1, mid = 9； 05 13 19 21 37 56 64 75 80 88 92 low high 因为下界low >上界high，说明表中没有关键字等于key的元素，查找不成功。

（3）性能分析 ①查找算法的判定树 判定树：描述查找过程的二叉树。 判定树中圆形结点为内部结点；方形结点为外部结点（由内部结点的 空指针域链接）。树中每个圆形结点标识表中一个记录，结点中的值为该 记录在表中的位置。方形结点中的值v为：第i结点的值< v <第i＋1结点的 值；若i结点为第1个结点则v <第1个结点的值；若i结点为最后一个结点则 v >最后一个结点的值。 多不超过树的深度，而具有n个结点的判定树的深度为 ，所以， 显然，折半查找法在查找成功（或不成功）时进行比较的关键字个数最 折半查找法在查找成功时和给定值进行比较的关键字个数至多为 。

例如，上述11个元素的表的例子。查找21的过程如红线所示，查找 85的过程如蓝线所示。 6 3 9 1 4 7 10 2 5 8 11 -1 3-4 6-7 9-10 1-2 2-3 4-5 5-6 7-8 8-9 10-11 11- 图9.1 判定树和查找21(红线)，85(蓝线)的过程

②折半查找的平均查找长度 假定有序表的长度n＝2h－1（反之，h＝log2(n+1)），则描述折半 查找的判定树是深度为h的曼二叉树。假设表中每个记录的查找概率相 等(Pi = 1/n)，则查找成功时折半查找的平均查找长度： 对任意的n，当n较大(n>50)时，可有下列近似结果： （4）折半查找算法的特点 特点：只适用于有序表，且限于顺序存储结构（对线性链表无法进行 折半查找）。 （5）斐波那契查找 斐波那契序列：F0 = 0, F1= 1, Fi = Fi-1+ Fi-2, i≥2。 算法思想：假设开始时表中记录个数比某个斐波那契数小，即n＝Fu－1， 然后将给定值key和ST.elem[Fu-1].key进行比较，若相等，则查找成功；若 key < ST.elem[Fu-1].key，则继续在自ST.elem[1]至ST.elem[Fu-1]的子表中进行 查找，否则继续在自ST.elem[Fu-1＋1]至ST.elem[Fu－1]的子表中进行查找， 后一子表的长度为Fu-2－1。

特点：①斐波那契查找的平均性能比折半查找好，但最坏情况下的性能 却比折半查找差。 ②分割时只需进行加、减运算。 （6）插值查找 插值查找时根据给定值key来确定进行比较的关键字ST.elem[i].key 的查找方法。 ST.elem[h]分别为有序表中具有最小关键字和最大关键字的记录。显然， 这种插值查找只适于关键字均匀分布的表，在这种情况下，对表长较大的顺序 表，其平均性能比折半查找好。 令 ，其中ST.elem[l]和

￡9.2.4 索引顺序表的查找 （1）分块查找 分块查找又称索引顺序查找，这是顺序查找的一种改进方法。在此 查找法中，除表本身以外，尚需建立一个“索引表”。如下例所示。 例如，图9.2所示为一个表及其索引表，表中含有18个记录，可分成 3个子表(R1, R2, …, R6)、(R7, R8, …, R12)和(R13, R14, …, R18)。对每一个子 表（或称块）建立索引项。索引表按关键字有序，则表或者有序或者分块 有序。 22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53 索引表 最大关键字 起始地址 22 48 86 1 7 13 图9.2 表及其索引表 索引项包括： 关键字项：其值为该子表内的最大关键字。 指针项：指示该子表的第一个记录在表中的位置。

分块有序：即后一个子表中的所有记录的关键字均大于前一个子表中 的最大关键字。 分块查找的算法思想： ①确定待查记录所在的块（子表）； ②在块中顺序查找 （2）性能分析 分块查找的平均查找长度为： ASLbs＝Lb＋Lw 其中：Lb为查找索引表确定所在块的平均查找长度，Lw为在块中查找元素的 平均查找长度。 ；又假定表中每个记录的查找概率相等，则每 一般情况下，为进行分块查找，可以将长度为n的表均匀地分成b块，每 块含有s个记录，即 块查找的概率为1/b，块中每个记录的查找概率为1/s。则分块查找的平均长 度为： ①用顺序查找确定所在块 ②用折半查找确定所在块

￡9.3 动态查找表 ￡9.3.1 概述 （1）动态查找表的抽象数据类型定义： ADT DynamicSearchTable { 数据对象D：D是具有相同特性的数据元素的集合。各个数据元素均含有 类型相同，可唯一标识数据元素的关键字。 数据关系R：数据元素同属一个集合。 基本操作P： InitDSTable (&DT); 操作结果：构造一个空的动态查找表DT。 DestroyDSTable (&DT); 初始条件：动态查找表DT存在。 操作结果：销毁动态查找表DT。 SearchDSTable (DT, key); 初始条件：动态查找表DT存在，key为和关键字类型相同的给定值。 操作结果：若DT中存在其关键字等于key的数据元素，则函数值为 该元素的值或在表中的位置，否则为“空”。 InsertDSTable (&DT, e); 初始条件：动态查找表DT存在，e为待插入的数据元素。 操作结果：若DT中不存在其关键字等于e.key的数据元素，则插入 e到DT。

DeleteDSTable (&DT, key); TraverseDSTable (DT, Visit ( )); 初始条件：动态查找表DT存在，Visit是对元素操作的应用函数。 操作结果：按某种次序对DT的每个元素调用函数visit ( )一次且仅一 次。一旦visit ( )失败，则操作失败。 } ADT DynamicSearchTable （2）动态查找表的特点 特点：表结构本身是在查找过程中动态生成的，即对于给定值key， 若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字 等于key的记录。

￡9.3.2 二叉排序树和平衡二叉树 （1）二叉排序树 ① 定义 二叉排序树（Binary Sort Tree）：它或者是一棵空树；或者是具有 下列性质的二叉树： 1．若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 2．若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 3．它的左、右子树也分别为二叉排序树。 ② 图形表示 45 12 53 3 37 100 24 78 61 90 CAO ZHAO DING CHEN LI DU WANG XIA MA (b) (a) 图9.3 二叉排序树示例

③二叉排序树的查找 算法思想：二叉排序树又称二叉查找树，当二叉排序树不空时，首 先将给定值和根结点的关键字比较，若相等，则查找成功，否则将依据 给定值和根结点的关键字之间的大小关系，分别在左子树或右子树上继 续进行查找。 算法实现：取二叉链表作为二叉排序树的存储结构。 算法9.3(a)如下： BiTree SearchBST (BiTree T, KeyType key) { //在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素， //若查找成功，则返回指向该数据元素结点的指针，否则返回空指针。 if ((!T) | | EQ(key, T－>data.key)) //查找结束 return (T); else if LT(key, T－>data.key) //在左子树中继续查找 return (SearchBST (T－>lchild, key)); else return (SearchBST (T－>rchild, key)); //在右子树中继续查找 } // SearchBST

④二叉排序树的插入和删除 1．插入算法 i．算法思想：根据二叉排序树的特点，易知，新插入的结点一定是 一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个 结点的左孩子或右孩子。 ii．算法实现：为了在查找不成功时返回新结点的插入位置，将上述 算法算法9.3(a)修改为9.3(b)。插入算法如算法9.4所示。 算法9.3(b)如下： Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree &p) { //在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素，若 //查找成功，则指针p指向该数据元素结点，并返回TRUE，否则指针p指向 //查找路径上访问的最后一个结点并返回FALSE，指针f指向T的双亲，其初 //始调用值为NULL。 if (!T) { p = f; return FALSE;} //查找不成功 else if EQ(key, T－>data.key) { p = T; return TRUE;} //查找成功 else if LT(key, T－>data.key) //在左子树中继续查找 return (SearchBST (T－>lchild, key, T, p)); else return (SearchBST (T－>rchild, key, T, p)); //在右子树中继续查找 } // SearchBST

算法9.4如下： Status InsertBST (BiTree T, ElemType e) { //当二叉排序树T中不存在关键字等于e.key的数据元素时，插入e并 //返回TRUE，否则返回FALSE。 if (!SearchBST (T, e.key, NULL, p)) { //查找不成功 s = (BiTree) malloc (sizeof (BiTree)); s－>data = e; s－>lchild = s－>rchild = NULL; if (!p) T = s; //被插结点*s为新的根结点 else if LT(e.key, p－>data.key) //被插结点*s为左孩子 p－>lchild = s; else p－>rchild = s; //被插结点*s为右孩子 return TRUE; } else return FALSE; //树中已有关键字相同的结点 } // InsertBST

iii．例子 例如，从空树出发，经过一系列的查找插入操作之后，可生成一棵二叉树。设查找的关键字序列为{45, 24, 53, 45, 12, 24, 90}，则删除的二叉排序树如图9.4所示。 45 24 45 24 53 45 24 53 12 45 24 53 12 90 45 (a) (b) (c) (d) (e) (f) 图9.4 二叉排序树的构造过程

2．删除算法 i．算法思想 假设在二叉排序树上被删结点为*p（指向结点的指针为p），其双亲 结点为*f（结点指针为f），且不失一般性，可设*p是*f的左孩子（如图 9.5(a)所示）。 a.若*p结点为叶子结点，即PL和PR均为空树。由于删去叶子结点不破坏 整棵树的结构，则只需修改其双亲结点的指针即可。 b.若*p结点只有左子树PL后者只有右子树PR，此时只要令PL或PR直接成 为其双亲结点*f的左子树即可。 c.若*p结点的左子树和右子树均不空。从图9.5(b)可知，在删去*p结点之 前，中序遍历该二叉树得到的序列为{…CLC…QLQSLSPPRF…}，在删去*p 之后，为保持其他元素直接的相对位置不变，可以有两种做法：其一是令*p 的左子树为*f的左子树，而*p的右子树为*s的右子树，如图9.5(c)所示；其二 是令*p的直接前驱（或直接后继）替代*p，然后再从二叉排序树中删去它的 直接前驱（或直接后继）。如图9.5(d)所示，当以直接前驱*s替代*p时，由于 *s只有左子树SL，则在删去*s之后，只要令SL为*s的双亲*q的右子树即可。

c f p F P C Q S PR s q CL QL SL f p F P PL PR (a) 以*f为根的子树 (b) 删除*p之前 返回 算法

c f p F S C Q PR q CL QL SL f c F C PR S CL SL (c) 删除*p之后,以PR作为*s的右子树的情形 (d) 删除*p之后,以*s 代替*p的情形 返回 算法 图9.5 在二叉排序树中删除*p

ii．算法实现 在二叉排序树上删除一个结点的算法如算法9.5所示，其中由前述3 中情况综合所得的删除操作如算法9.6所示。 算法9.5如下： Status DeleteBST (BiTree &T, KeyType key) { //若二叉排序树T中存在关键字等于key的数据元素时， //则删除该数据元素结点，并返回TRUE，否则返回FALSE。 if (!T) return FALSE; //不存在关键字等于key的数据元素 else { if (EQ(key, T－>data.key)) { //找到关键字等于key的数据元素 return Delete(T); } else if LT(key, T－>data.key) return (Delete BST (T－>lchild, key)); else return (Delete BST (T－>rchild, key)); } // DeleteBST

算法9.6如下： Status Delete (BiTree &p) { //从二叉排序树中删除结点p，并重接它的左或右子树 if (!p－>rchild) { //右子树空则只需要接它的左子树 q = p; p = p－>lchild; free (q); } else if (!p－>lchild) { //只要重接它的右子树 p = p－>rchild;

else { //左右子树均不空 q = p; s = p－>lchild; while (s－>rchild) { //转左然后向右到尽头 q = s; s = s－>rchild; } p－>data = s－>data; //s指向被删除结点的前驱 if (q != p) q－>rchild = s－>lchild; //重接*q的右子树 else q－>lchild = s－>lchild; //重接*q的左子树 delete s; } // else return TRUE; } // Delete

⑤二叉排序树的查找分析 假设在含有n(n≥1)个关键字的序列中，i个关键字小于第一个关键字，n－i－1个关键字大于第一个关键字，则由此构造而得的二叉排序树在n个记录的查找概率相等的情况下，其平均查找长度为： （9－2） 其中，P(i)为含有i个结点的二叉排序树的平均查找长度，则P(i)＋1为查找 左子树中每个关键字时所用比较次数的平均值，P(n－i－1)＋1为查找右子 树中每个关键字时所用比较次数的平均值。 又，假设表中n个关键字的排列是“随机”的，即任一个关键字在序列中将是第1个，或第2个，……，或第n个的概率相同，则可对（9－2）式从i等于0至n－1取平均值： 容易看出上式括弧中的第一项和第二项对称。又，i＝0时iP(i)=0，则上式 可改写为： n≥2 （9－3） 显然，P(0)=0, P(1)=1。

由式（9－3）可推得： 又 由此可得 （9－4） 即 由递推公式（9－4）和初始条件P(1)=1可推得： 则当n≥2时： （9－5）

平衡二叉树（Balanced Binary Tree 或Height-Balanced Tree）又称 （2）平衡二叉树 ①定义 平衡二叉树（Balanced Binary Tree 或Height-Balanced Tree）又称 AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子 树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不 超过1。 平衡因子BF（Balance Factor）：二叉树上结点的左子树的深度减去它的右子树的深度的值。 由平衡二叉树的定义易知，平衡二叉树上所有结点的平衡因子只可能 是－1、0和1。 ②图形表示 例如，图9.6(a)所示为两棵平衡二叉树，而图 9.6(b)为两棵不平衡二叉树，结点中的值为该结点 的平衡因子 1 -1 1 (a) 平衡二叉树

-1 -2 1 2 -1 1 (b) 不平衡二叉树 图9.6 平衡与不平衡二叉树及结点的平衡因子 ③C语言描述 typedef struct BSTNode { ElemType data; int bf; //结点的平衡因子 struct BSTNode *lchild, *rchild; //左、右孩子指针 } BSTNode, * BSTree;

④平衡调整 假设由于在二叉排序树上插入结点而失去平衡的最小子树根结点的 指针为a（即a是离插入结点最近，且平衡因子绝对值超过1的祖先结点)， 则失去平衡后进行调整的规律可归纳为下列4种情况： 1．单向右旋平衡处理： 由于在*a的左子树根结点的左子树上插入结点，*a的平衡因子由1增 至2，致使以*a为根的子树失去平衡，则需进行一次向右的顺时针旋转操 作。如图9.6(a)所示。 2．单向左旋平衡处理： 由于在*a的右子树根结点的右子树上插入结点，*a的平衡因子由－1 变为－2，致使以*a为根的子树失去平衡，则需进行一次向左的顺逆针旋 转操作。如图9.6(c)所示。 3．双向旋转（先左后右）平衡处理： 由于在*a的左子树根结点的右子树上插入结点，*a的平衡因子由1增 至2，致使以*a为根的子树失去平衡,则需进行两次旋转（先左旋后右旋） 操作。如图9.6(b)所示。 4．双向旋转（先右后左）平衡处理： 由于在*a的右子树根结点的左子树上插入结点，*a的平衡因子由－1变 为－2，致使以*a为根的子树失去平衡,则需进行两次旋转（先右旋后左旋） 操作。如图9.6(d)所示。

(a) LL型 (b) LR型 返回 算法 LL 插入结点 LR 插入结点 2 A 1 B AR h-1 BL BR AR LL AR h-1 h BL h-1 BR (a) LL型 BL CL CR AR LR 2 A -1 B 1 C AR h-1 h BL h-1 CL h-2 CR 插入结点 (b) LR型 返回 算法

(c) RR型 返回 算法 (d) RL型 图9.6 二叉排序树的平衡旋转图例 RR 插入结点 RL 插入结点 AL BL BR -2 A -1 B RR AL h-1 BL h-1 BR h (c) RR型 RL -2 A 1 B C -1 BR h-1 h AL h-1 CL h-2 CR 插入结点 AL CL CR BR 返回 算法 (d) RL型 图9.6 二叉排序树的平衡旋转图例

⑤插入算法 算法思想： 在平衡二叉排序树BBST上插入一个新的数据元素e的递归算法可描述如下： 1．若BBST为空树，则插入一个数据元素为e的新结点作为BBST的根结 点，树的深度增1； 2．若e的关键字和BBST的根结点的关键字相等，则不进行插入； 3．若e的关键字小于BBST的根结点的关键字，而且在BBST的左子树中 不存在和e有相同关键字的结点，则将e插入在BBST的左子树上，并 且当插入之后的左子树深度增加（＋1）时，分别就下列不同情况处 理之： i．BBST的根结点的平衡因子为－1（右子树的深度大于左子树的深度）： 则将根结点的平衡因子更改为0，BBST的深度不变； ii．BBST的根结点的平衡因子为0（左、右子树的深度相等）：则将根结 点的平衡因子更改为1，BBST的深度增1； iii．BBST的根结点的平衡因子为1（左子树的深度大于右子树的深度）： a.若BBST的左子树根结点的平衡因子为1，则需进行单向右旋平衡处理， 并且在右旋处理之后，将根结点和其右子树根结点的平衡因子更改为0， 树的深度不变；b. 若BBST的左子树根结点的平衡因子为－1，则需进行 先向左、后向右的双向旋转平衡处理，并且在旋转处理之后，修改根结 点和其左、右子树根结点的平衡因子，树的深度不变。

4．若e的关键字大于BBST的根结点的关键字，而且在BBST的右子树中不 存在和e有相同关键字的结点，则将e插入在BBST的右子树上，并且当 插入之后的右子树深度增加（＋1）时，分别就不同情况处理之。其处 理操作和上述3．中描述相对称。 算法实现： 算法9.7如下： void R_Rotate (BSTree &p) { //对以*p为根的二叉排序树作右旋处理，处理之后p指向新的树根结点， //即旋转处理之前的左子树的根结点 lc = p－>lchild; //lc指向的*p的左子树根结点 p－>lchild = lc－>rchild; //lc的右子树挂接为*p的左子树 lc－>rchild = p; p = lc; //p指向新的根结点 } // R_Rotate 算法9.8如下： void L_Rotate (BSTree &p) { //对以*p为根的二叉排序树作左旋处理，处理之后p指向新的树根结点， //即旋转处理之前的右子树的根结点 rc = p－>rchild; //rc指向的*p的右子树根结点 p－>rchild = rc－>lchild; //rc的左子树挂接为*p的右子树 rc－>lchild = p; p = rc; //p指向新的根结点 } // L_Rotate

算法9.9如下： void LeftBalance (BSTree &T) { //对以指针T所指结点为根的二叉树作左平衡旋转处理，本算法 //结束时，指针T指向新的根结点 lc = T－>lchild; //lc指向*T的左子树根结点 switch (lc－>bf) { //检查*T的左子树的平衡度，并作相应平衡处理 case LH: //新结点插入在*T的左孩子的左子树上，要作单右旋处理 T－>bf = lc－>bf = EH; R_Rotate (T); break; case RH: //新结点插入在*T的左孩子的右子树上，要作双旋处理 rd = lc－>rchild; //rd指向*T的左孩子的右子树根 switch (rd－>bf) { //修改*T及其左孩子的平衡因子 case LH: T－>bf = RH; lc－>bf = EH; case EH:

case RH: T－>bf = EH; lc－>bf = LH; break; } // switch (rd－>bf) rd－>bf = EH; L_Rotate (T－>lchild); //对*T的左子树作左旋平衡处理 R_Rotate (T); //对*T作右旋平衡处理 } // switch (lc－>bf) } // LeftBalance 算法9.10如下： #define LH +1 //左高 #define EH 0 //等高 #define RH -1 //右高 Status InsertAVL (BSTree &T, ElemType e, Boolean &taller) { //若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入 //一个数据元素为e的新结点，并返回1，否则返回0。若因插入而使二 //叉排序树失去平衡，则作平衡旋转处理，布尔变量taller反映T长高 //与否。 if (!T) { //插入新结点，树“长高”，置taller为TRUE T = (BSTree) malloc (sizeof (BSTNode)); T－>data = e; T－>lchild = T－>rchild = NULL; T－>bf = EH;

taller = TRUE; } else { if (EQ(e.key, T－>data.key)) //树中已存在和e有相同关键字的 {taller = FALSE; return 0;} //结点则不再插入 if (LT(e.key, T－>data.key)) { //应继续在*T的左子树中进行搜索 if (!InsertAVL(T－>lchild, e, taller)) //未插入 return 0; if (taller) //已插入到*T的左子树中且左子树“长高” switch (T－>bf) { //检查*T的平衡度 case LH: //原本左子树比右子树高，需要作左平衡处理 LeftBalance (T); taller = FALSE; break; case EH: //原本左右子树等高，现因左子树增高而使树增高 T－>bf = LH; case RH: //原本右子树比左子树高，现左、右子树等高 T－>bf = EH; } // switch (T－>bf) } // if

else { //应继续在*T的右子树中进行搜索 if (!InsertAVL(T－>rchild, e, taller)) //未插入 return 0; if (taller) //已插入到*T的右子树中且右子树“长高” switch (T－>bf) { //检查*T的平衡度 case LH: //原本右子树比左子树高，现左、右子树等高 T－>bf = EH; taller = FALSE; break; case EH: //原本左右子树等高，现因右子树增高而使树增高 T－>bf = RH; taller = TRUE; case RH: //原本右子树比左子树高，需要作右平衡处理 RightBalance (T); } // switch (T－>bf) } // else return 1; } // InsertAVL

⑥平衡树查找的分析 在平衡树上进行查找的过程和排序树相同，由此，在查找过程中 和给定值进行比较的关键字个数不超过树的深度。 含有n个结点的平衡树的最大深度为 。 由此，在平衡树上进行查找的时间复杂度为O(logn)。

￡9.3.3 B-树和B+树 （1）B-树 ① B-树的定义 B-树是一种平衡的多路查找树。一棵m阶的B-树，或为空树，或 2．若根结点不是叶子结点，则至少有两棵子树； 3．除根之外的所有非终端结点至少有 棵子树； 4．所有的非终端结点中包含下列信息数据： (n, A0, K1, A1, K2, A2, … , Kn, An) 其中：Ki(i = 1, … , n)为关键字，且Ki < Ki+1(i = 1, … , n－1)； Ai(i = 1, … , n)为指向子树根结点的指针，且指针Ai-1所指子树中 所有结点的关键字均小于Ki(i = 1, … , n)，An所指子树中所有结 点的关键字均大于Kn， 为关键字的个数（或 n＋1为子树个数）。 5．所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是 外部结点或查找失败的结点，实际上这些结点不存在，指向这些结 点的指针为空）。

t a b c f e g d h 1 35 1 11 2 43 78 1 18 1 27 1 39 1 99 3 47 53 64 F F ②图形表示 图9.7 一棵4阶的B-树 ③C语言说明 #define m 3 // B-树的阶，暂设为3 typedef struct BTNode { int keynum; //结点中关键字个数，即结点的大小 struct BTNode *parent; //指向双亲结点 KeyType key[m + 1]; //关键字向量，0号单元未用 struct BTNode *ptr[m + 1]; //子树指针向量 Record *recptr[ m + 1]; //记录指针向量，0号单元未用 } BTNode, *BTree;;

typedef struct { BTNode *pt; //指向找到的结点 int i; //1..m，在结点中的关键字序号 int tag; //1:查找成功，0:查找失败 } Result; //B-树的查找结果类型 ④ B-树的查找 1．算法思想：在B-树上进行查找的过程是一个顺时针查找结点和在结点 的关键字中进行查找交叉进行的过程。 2．算法实现： 算法9.11如下： Result SearchBTree (BTree T, KeyType K) { //在m阶B-树T上查找关键字K，返回结果(pt, i , tag)。若查找成功， //则特征值tag＝1，指针pt所指结点中第i个关键字等于K；否则 //特征值tag＝0，等于K的关键字应插入在指针pt所指结点中第i和 //第i＋1个关键字之间 p = T; //初始化，p指向待查结点，q指向p的双亲 q = NULL; found = FALSE; i = 0;

while (p && !found) { i = Search (p, K); //在p－>key[1..keynum]中查找， //i使得: p－>key[i] <= K < p－>key[i + 1] if (i > 0 && p－>key[i] = = K) found = TRUE; //找到待查关键字 else { q = p; p = p－>ptr[i]; } if (found) return (p, i, 1); //查找成功 else return (q, i, 0); //查找不成功，返回K的插入位置信息 } // SearchBTree

3．查找分析： 从算法9.10可见，在B-树上进行查找包含两种基本操作： a.在B-树中找结点（操作在磁盘上进行）； b.在结点中找关键字（操作在内存中进行）。 显然，在磁盘上进行一次查找比在内存中进行一次查找耗费时间多 得多，因此，在磁盘上进行查找的次数、即待查关键字所在结点在B-树 上的层次数，是决定B-树查找效率的首要因素。 根据B-树的定义，第一层至少有1个结点；第二层至少有2个结点；由 棵子树，则第三层至少有 2( )个结点；……；依次类推，第l＋1层至少有2( )l-1个结点。 于除根之外的每个非终端结点至少有 而l＋1层的结点为叶子结点。若m阶B-树中具有N个关键字，则叶子结点即查找不成功的结点为N＋1，由此有： 推得： 这就是说，在含有N个关键字的B-树上进行查找时，从根结点到关键字所 在结点的路径上涉及的结点数不超过

⑤B-树的插入 1．算法思想：由于B-树结点中的关键字个数必须 ，因此， 每次插入一个关键字不是在树中添加一个叶子结点，而是首先在最低层的某个非终端结点中添加一个关键字，若该结点的关键字个数不超过 m-1，则插入完成，否则要产生结点的“分裂”。 一般情况下，结点可如下实现“分裂”： 假设*p结点中已有m－1个关键字，当插入一个关键字之后，结点中含有信息为： m, A0, (K1, A1), … , (Km, Am) 且其中 Ki < Ki+1 1≤i < m 此时可将*p结点分裂为*p和*p’两个结点，其中*p结点中含有信息为： *p’结点中含有信息： 而关键字 和指针*p’一起插入到*p的双亲结点中。

Status InsertBTree (BTree &T, KeyType K, BTree q, int i) { 2．算法实现 算法9.12如下： Status InsertBTree (BTree &T, KeyType K, BTree q, int i) { //在m阶B-树T上结点*q的key[i]与key[i+1]之间插入关键字K。 //若引起结点过大，则沿双亲链进行必要的结点分裂调整， //使T仍是m阶B-树。 x = K; ap = NULL; finished = FALSE; while (q && !finished) { Insert (q, i, x, ap); //将x和ap分别插入到q－>key[i+1]和q－>ptr[i+1] if (q－>keynum < m) finished = TRUE; //插入完成 else { //分裂结点*q s = ; split (q, s, ap); x = q－>key[s]; //将q－>key[s+1..m], q－>ptr[s..m] //和q－>recptr[s+1..m]移入新结点*ap q = q－>parent; if (q) i = Search(q, x); //在双亲结点*q中查找x 的插入位置 } // else } // while q和i是由查找函数SearchBTree 返回的信息而得。

if (!finished) NewRoot (T, q, x, ap); //T是空树（参数q初值为NULL）或者根结点 //已分裂为结点*q和*ap生成含信息(T, x, ap) //的新的根结点*T，原T和ap为子树指针。 return OK; } // InsertBTree 3．例子 例如，图9.8(a)所示为3阶B-树（图中略去F结点，即叶子结点），假设需一 次插入关键字30，26，85和7。 bt a 45 b 24 c 3 12 d 37 f 50 h 100 g 61 70 e 53 90 (a) 一棵2-3树 返回 图9.9例

bt a 45 b 24 c 3 12 d f 50 h 100 g 61 70 e 53 90 30 37 (b) bt a 45 b 24 c 3 12 d f 50 h 100 g 61 70 e 53 90 26 30 37 (c)

bt a 45 b 24 30 c 3 12 d f 50 h 100 g 61 70 e 53 90 37 26 d’ (d) bt a 45 b 24 30 c 3 12 d f 50 h 100 g 6170 85 e 53 90 37 26 d’ (e)

bt a 45 b 24 30 c 3 12 d f 50 h 100 g 61 e 53 70 90 37 26 d’ 85 g’ (f) bt a 45 70 b 24 30 c 3 12 d f 50 h 100 g 61 e 53 37 26 d’ 85 g’ e’ 90 (g)

bt a 45 70 b 7 24 30 c 3 d f 50 h 100 g 61 e 53 37 26 d’ 85 g’ e’ 90 12 c’ (h) bt a 24 45 70 b 7 c 3 d f 50 h 100 g 61 e 53 26 d’ 85 g’ e’ 90 12 c’ 30 b’ 37 (i)

bt a 70 b 7 c 3 d f 50 h 100 g 61 e 53 26 d’ 85 g’ e’ 90 12 c’ 30 b’ m a’ 45 24 37 (j) 图9.8 在B-树中进行插入（省略叶子结点） (a) 一棵2-3树； (b) 插入30之后； (c)、(d) 插入26之后； (e)~(g) 插入85之后； (h)~(j) 插入7之后；

⑥B-树的删除 1．算法思想： 在B-树中删除一个关键字，则首先应找到该关键字所在结点，并 从中删除之。 i．若所删关键字为非终端结点中的Ki，则可以指针Ai所指子树中的最 小关键字Y替代Ki，然后在相应的结点中删去Y。 ii．若所删关键字在最下层非终端结点中。有下列3种情况： a．被删关键字所在结点中的关键字数目不小于 ，则只需从该结点 中删去该关键字Ki和相应指针Ai，树的其他部分不变。 b．被删关键字所在结点中的关键字数目等于 －1，而与该结点相邻 的右兄弟（或左兄弟）结点中的关键字数目大于 －1，则需将其 兄弟结点中的最小（或最大）的关键字上移至双亲结点中，而将双亲 结点中小于（或大于）且紧靠该上移关键字的关键字下移至被删关键 字所在结点中。 c．被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于 －1。假设该结点有右兄弟，且其右兄弟结点地址由双亲结 点中的指针Ai所指，则在删去关键字之后，它所在结点中剩余的关 键字和指针，加上双亲结点中的关键字Ki一起，合并到Ai所指兄弟 结点中（若没有右兄弟，则合并至左兄弟结点中）。如果因此使双 亲结点中的关键字数目小于 －1，则一次类推作相应处理。

2．例子 bt a 45 b 24 c 3 d 37 f 50 h 100 g 61 70 e 53 90 (a) bt 45 a b 24 c 3 d 37 f 53 h 100 g 70 e 61 90 (b) 说 明

bt 45 a b 24 c 3 d 37 h 100 g 61 70 e 90 (c) e c 3 24 h 100 g 61 70 45 90 bt (d) 说 明 图9.9 在B-树中删除关键字的情形

i．从图9.8(a)所示B-树中删去关键字12，删除后的B-树如图9.9(a) 所示。 说明： i．从图9.8(a)所示B-树中删去关键字12，删除后的B-树如图9.9(a) 所示。 ii．从图9.9(a)中删去50，需将其右兄弟结点中的61上移至*e结点 中，而将*e结点中的53移至*f，从而使*f和*g中关键字数目均 不小于 －1，而双亲结点中的关键字数目不变，如图9.9(b) iii．从图9.9(b)所示B-树中删去53，则应删去*f结点，并将*f中的 剩余信息（指针“空”）和双亲*e结点中的61一起合并到右兄弟 结点*g中，删除后的树如图9.9(c)所示。 iv．在图9.9(c)的B-树中删去关键字37之后，双亲b结点中剩余信息 （“指针c”）应和其双亲*a结点中关键字45一起合并至右兄弟结点 *e中，删除后的B-树如图9.9(d)所示。 （2）B＋树 ① 定义 B＋树是应文件系统所需而出的一种B-树的变型树。一棵m阶的B＋树和 m阶的B-树的差异在于： 有n棵子树的结点中含有n个关键字。

2.所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录 的指针，且叶子结点本身依关键字的大小自小而大顺序链接。 3.所有的非终端结点可以看成是索引部分，结点中仅含其子树（根结点） 中的最大（或最小）关键字。 通常在B＋树上有两个头指针，一个指向根 结点，一个指向关键字最小的叶子结点。 root sqt 59 97 15 44 59 72 97 10 15 21 37 44 51 59 63 72 85 91 97 ②图形表示 图9.10 一棵3阶的B＋树

③B＋树的查找 对B＋树可以进行两种查找运算： 1.从最小关键字起顺序查找； 2.从根结点开始，进行随机查找。 在查找时，若非终端结点上的剧组机等于给定值，并不终止，而是 继续向下直到叶子结点。因此，在B＋树中，不管查找成功与否，每次 查找都是走了一条从根到叶子结点的路径。其余同B-树的查找类似。 ④B＋树的插入 B＋树的插入仅在叶子结点上进行，当结点中的关键字个数大于m时要分 和 。并且，它们的 裂成两个结点，它们所含关键字的个数分别为 双亲结点中应同时包含这两个结点中的最大关键字。其余同B-树的插入类似。 ⑤ B＋树的删除 B＋树的删除也仅在叶子结点进行，当叶子结点中的最大关键字被删除时， 其在非终端结点中的值可以作为一个“分界关键字”存在。若因删除而使结点中 时，其和兄弟结点的合并过程亦和B-树类似。 关键字的个数少于

￡9.4 哈希表 ￡9.4.1 定义 哈希（Hash）函数：在记录的存储位置和它的关键字之间建立的一个 确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。 称这个对应关系f为哈希函数。 均匀的（Uniform）哈希函数：对于关键字集合中的任一个关键字， 经哈希函数映像到地址集合中任何一个地址的概率是相等的，则称此类哈 希函数为均匀的哈希函数。 哈希表：根据设定的哈希函数H(key)和处理冲突的方法将一组关键字映像 到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记 录在表中的存储位置，这种表便称为哈希表，这一映像过程称为哈希造表或散 列，所得存储位置称哈希地址或散列地址。 冲突（collision）：不同的关键字可能得到同一哈希地址的现象。 同义词（synonym）：在一个哈希函数中，具有相同函数值的关键字，互 称为同义词。

例如，假设建立一张全国30个地区的各民族人口统计表，每个地区 为一个记录，记录的各数据项为： 编号 地区名 总人口 汉族 回族 显然，可以用一个一维数组C(1:30)来存放这张表，其中C[i]是编号为i的 地区的人口情况。编号i便为记录的关键字，由它唯一确定记录的存储位 置C[i]。假设北京市的编号为1，则若要查看北京市的各民族人口，只要 取出C[1]的记录即可。若把这个数组看成是哈希表，则哈希函数f(key)=key。 又，若取关键字中第一个字母在字母表中的序号作为哈希函数。如， BEIJING的哈希函数值为字母“B”在字母表中的序号等于02。关键字 HEBEI和HENAN不等，但f(HEBEI)=f(HENAN)，这种现象即为冲突。 HEBEI和HENAN相对于该哈希函数称为同义词。

￡9.4.2 哈希函数的构造 构造哈希函数要考虑的元素，通常有： 1．计算哈希函数所需时间（包括硬件指令的因素）； 2．关键字的长度； 3．哈希表的大小； 4．关键字的分布情况； 5．记录的查找频率。 直接定址所得地址集合和关键字集合的大小相同。对于不同的关键字不会发生冲突。 （1）直接定址法 1．定义 取关键字或关键字的某个线性函数值为哈希地址。即： H(key) = key 或H(key) = a * key + b 其中a和b为常数（这种哈希函数叫做自身函数）。 2．例子 例一，有一个从1岁到100岁的人口数字统计表。 地址 01 02 03 … 25 26 27 … 100 年龄 1 2 3 … 25 26 27 … … 人数 300 2000 5000 … 1050 … … … … 表9.1 直接定址哈希函数例子一 其中，年龄作为关键字，哈希函数取关键字自身。若要询问25岁的人有 多少，则只要查表的第25项即可。

其中，关键字是年份，哈希函数取关键字加一常数：H(key) = key + (－1948)。 例二：有一个解放后出生的人口调查表。 地址 01 02 03 … 22 … 年份 1949 1950 1951 … 1970 … 人数 … … … … 15000 … 表9.2 直接定址哈希函数例子二 其中，关键字是年份，哈希函数取关键字加一常数：H(key) = key + (－1948)。 若要查1970年出生的人，则只要查第(1970－1948)＝22项即可。 （2）数字分析法 主要思想：假设关键字是以r为基的数（如：以10为基的十进制数），并且哈 希表中可能出现的关键字都是事先知道的，则可取关键字的若干位组成哈希地址。 例如，有80个记录，其关键字为8位十进制数。假设哈希表的表长为10010，则 可取两位十进制数组成哈希地址。这两位的取法，原则是使得到的哈希地址尽量避 免产生冲突。假设这80个关键字中的一部分如下所列：

8 1 3 4 6 5 3 2 8 1 3 7 2 2 4 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 对关键字全体的分析：第①②位都是“8 1”，第③位只可能取1、2、3或4， 第⑧位只可能取2、5或7，因此这4位都不可取。由于中间4位可看成是近乎随 机的，因此可取其中任意两位，或取其中两位与另两位的叠加求和后舍去进位 作为哈希地址。 （3）平方取中法 1．定义 取关键字平方后的中间几位为哈希地址。取的位数由表长决定。

例如，为BASIC源程序中的标识符建立一个哈希表。假设BASIC语言 中允许的标识符为一个字母，或一个字母和一个数字。在计算机内可用两 2．例子 例如，为BASIC源程序中的标识符建立一个哈希表。假设BASIC语言 中允许的标识符为一个字母，或一个字母和一个数字。在计算机内可用两 位八进制数表示字母和数字，如图9.11(a)所示。取表示符在计算机中的八 进制数为它的关键字。假设表长为512＝29，则可取关键字平方后的中间9 位二进制数为哈希地址。例如，图9.11(b)列出了一些标识符及它们的哈希 地址。 A B C … Z 0 1 2 … 9 01 02 03 … 32 60 61 62 … 71 (a) 字符的八进制表示对照表 A 0100 0 010000 000 I 1100 1 210000 210 J 1200 1 440000 440 I0 1160 1 370400 370 P1 2061 4 310541 310 P2 2062 4 314704 314 Q1 2161 4 734741 734 Q2 2162 4 741304 741 Q3 2163 4 745651 745 记录 关键字 (关键字)2 哈希地址(217~29) (b) 标识符及其哈希地址 图9.11

（4）折叠法 1．定义 折叠法（folding）：将关键字分割成位数相同的几部分（最后一 部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为 哈希地址。 移位叠加：将分割后的每一部分的最低位对齐，然后相加。 间界叠加：从一端向另一端沿分割界来回折叠，然后对齐相加。 2．使用前提 关键字位数很多，而且关键字中每一位上数字分布大致均匀时。 3．例子 例如，每一种西文图书馆都有一个国际标准图书编号（ISBN），它是一 个10位的十进制数字，若要以它作关键字建立一个哈希表，当馆藏书种类不 到10000时，可采用折叠法构造一个四位数的哈希函数。如国际标准图书馆 图书编号0-442-20586-4的哈希地址分别如图9.12(a)和(b)所示。 5864 5864 4220 0224 ＋) 04 ＋) 04 10088 6092 H(key) = 0088 H(key) = 6092 (b) 间界叠加 (a) 移位叠加 图9.12 由折叠法求得哈希地址

（5）除留余数法 1．定义 取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。 即： H(key) = key MOD p , p ≤ m 由经验得知：一般情况下，可以选p为质数或不包含小于20的质因数的合数。 2．例子 若p含有质因子pf，则所有含有pf因子的关键字的哈希地址均为pf的倍数。 例一：当p＝21（＝3×7）时，下列含因子7的关键字21取模的哈希地址均 为7的被数。 关键字 28 35 63 77 105 哈希地址 7 14 0 14 0 例二：假设有两个标识符xy和yx，其中x、y均为字符，又假设它们的机器 代码（6位二进制数）分别为c(x)和c(y)，则上述两个标识符的关键字分别为： key1 = 26 c (x) + c (y) 或 key2 = 26 c (y)+ c (x) 用除留余数法求哈希地址，且p＝tq，t是某个常数，q是某个质数。则当q＝3时， 这两个关键字将被散列在差为3的地址上。因为：

= {[26 c (x) + c (y)] MOD p－[26 c (y)+ c (x)] MOD p} MOD q [H(key1)－H(key2)] MOD q = {[26 c (x) + c (y)] MOD p－[26 c (y)+ c (x)] MOD p} MOD q = {26 c (x) MOD p + c (y) MOD p－26 c (y) MOD p－c (x) MOD p} MOD q ={26 c (x) MOD q + c (y) MOD q－26 c (y) MOD q－c (x) MOD q} MOD q （因对任一x有(x MOD (t * q)) MOD q = (x MOD q) MOD q） 当q＝3时，上式为： = {(26 MOD 3)c(x) MOD 3 + c(y) MOD 3－(26 MOD 3)c(y) MOD 3 － c(x) MOD 3} MOD 3 = 0 MOD 3 （6）随机数法 1．定义 选择一个随机函数，取关键字的随机函数值为它的哈希地址，即 H(key)＝random(key)，其中random为随机函数。 2．使用前提 关键字长度不等时，采用此法构造哈希函数较恰当。

￡9.4.3 处理冲突的方法 假设哈希表的地址集为0~(n－1)。 冲突：指由关键字得到的哈希地址为j(0≤j≤n－1)的位置上已存 在记录。 处理冲突：为产生冲突的关键字的记录找到另一个“空”的哈希地址。 （1）开放定址法 1．定义 Hi = (H(key) + di) MOD m i = 1, 2, … , k (k≤m－1) 其中，H(key)为哈希函数；m为哈希表长；di为增量序列。 增量序列，可有下述3种取法： i．di = 1, 2, 3, … , m－1，称线性探测再散列； ii．di = 12, －12, 22, －22, 32, … , ±k2 (k≤m/2)，称二次探测再散列； iii．di = 伪随机数序列，称伪随机探测再散列。 二次聚集：处理冲突过程中发生的两个第一个哈希地址不同的记录争夺 同一个后继哈希地址的现象。即，在处理同义词的冲突过程中又添加了非同 义词的冲突。

2．例子 例如，在长度为11的哈希表中已填有关键字分别为17，60和29的记 录（哈希函数H(key)＝ key MOD 11），现有第四个记录，其关键字为 38，由哈希函数得到的哈希地址为5，产生冲突。 线性探测再散列：得到下一个地址6，仍冲突；再求下一个地址7， 仍冲突；直到哈希地址为8的位置（“空”）时止。 二次探测再散列：应填入序号为4的位置。 伪随机探测再散列：伪随机数列9, … 应填入序号为2的位置。 0 1 2 3 4 5 6 7 8 9 60 17 29 (a) 插入前 60 17 29 38 (b) 线性探测再散列 38 60 17 29 (c) 二次探测再散列 60 17 29 38 (d) 伪随机探测再散列 图9.12 用开放定址处理冲突时，关键字为38的记录插入前后的哈希表

（2）再哈希法 Hi = RHi (key) i = 1, 2, … , k 其中，R、Hi均是不同的哈希函数，即在同义词产生地址冲突时计算另一 个哈希函数地址，直到冲突不再发生。 （3）链地址法 1．定义 将所有关键字为同义词的记录存储在同一线性链表中。 假设某哈希函数产生的哈希地址区间[0, m－1]上，则设立一个指针 型向量： Chain Chain Hash[m]; 其每个分裂的初始状态都是空指针。凡哈希地址为i的记录都插入到头指 针为Chain Hash[m]的链表中。在链表中的插入位置可以在表头或表尾， 也可以在中间，以保持同义词在同一线性链表中按关键字有序。 2．例子 例9－1，已知一组关键字(19，14，23，01，68，20，84，27，55，11， 10，79)。则按哈希函数H(key)＝key MOD 13和链地址法处理冲突构造所得 的哈希表如图9.13所示。

设哈希函数的值域为[0, m－1]，则设向量HashTable[0..m－1]为基本表，每 01 14 27 29 55 68 19 84 10 23 20 11 1 2 3 4 5 6 7 8 9 10 12 图9.13 链地址法处理冲突时的哈希表 （同一链表中关键字自小至大有序） （4）建立一个公共溢出区 设哈希函数的值域为[0, m－1]，则设向量HashTable[0..m－1]为基本表，每 个分量存放一个记录，另设立向量OverTable[0..v]为溢出表。所有关键字和基本 表中关键字为同义词的记录，不管它们由哈希函数得到的哈希地址是什么，一旦 发生冲突，都填入溢出表。

￡9.4.4 哈希表的查找及其分析 （1）相关术语 查找过程：给定K值，根据造表时设定的哈希函数求得哈希地址， 若表中此位置上没有记录，则查找不成功；否则比较关键字，若和给 定值相等，则查找成功；否则根据造表时设定的处理冲突的方法找“下 一地址”，直至哈希表中某个位置为“空”或者表中所填记录的关键字等 于给定值为止。 影响查找过程中需和给定值进行比较的关键字的个数的因素： 1．哈希函数 2．冲突处理方法 3．哈希表的装填因子 装填因子： 其中，α标志哈希表的装满程度。 直观的看，α越小，发生冲突的可能性就越小；反之，α越大，表中 已填入的记录越多，再填记录时，发生冲突的可能性就越大，则查找时， 给定值需与之进行比较的关键字的个数也就越多。

（2）查找算法实现（开放定址法处理冲突） //----------------------开放定址哈希表的存储结构---------------------- int hashsize[ ] = {997, …}; //哈希表容量递增表，一个合适的素数序列 typedef struct { ElemType *elem; //数据元素存储基址，动态分配数组 int count; //当前数据元素个数 int sizeindex; // hashsize[sizeindex]为当前容量 } HashTable; #define SUCCESS 1 #define UNSUCCESS 0 #define DUPLICATE -1 算法9.13如下： Status SearchHash (HashTable H, KeyType K, int &p, int &C) { //在开放定址哈希表H中查找关键字为K的元素，若查找成功，以p指示待查 //数据元素在表中位置，并返回SUCCESS；否则，以p指示插入位置，并返回 //UNSUCCESS，c用以计冲突次数，其初值置零，供建表插入时参考 p = Hash (K)； //求得哈希地址 while (H.elem[p].key != NULLKEY && !EQ(K, H.elem[p].key)) //该位置中填有记录并且关键字不相等 collision (p, ++ c); //求得下一探查地址p

return SUCCESS; //查找成功，p返回待查数据元素位置 else return UNSUCCESS; if EQ(K, H.elem[p].key return SUCCESS; //查找成功，p返回待查数据元素位置 else return UNSUCCESS; //查找不成功(H.elem[p].key = = NULLKEY)， p返回的是插入位置 } // SearchHash 算法9.14如下： Status InsertHash (HashTable &H, ElemType e) { //查找不成功时插入数据元素e到开放定址哈希表H中，并返回OK; //若冲突次数过大，则重建哈希表 c = 0; if (SearchHash (H, e.key, p, c)) return DUPLICATE; //表中已有与e相同关键字的元素 else if (c < hashsize[H.sizeindes]/2) { //冲突次数c未达到上限(c的阈值可调) H.elem[p] = e; //插入e ++H.count; return OK; } else { RecreateHashTable (H); //重建哈希表 return UNSUCCESS; } // InsertHash 算法9.14通过调用查找算法（算法9.13） 实现了开放定址哈希表的插入操作。

（3）查找的例子 例如，已知例9－1中所示的一组关键字按哈希函数H(key) = key MOD 13 和线性探测处理冲突构造所得哈希表a.elem[0..15]如图9.14所示 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 14 01 68 27 55 19 20 84 79 23 11 10 图9.14 哈希表a.elem[0:15] 给定值K＝84： 首先求得哈希地址H(84)＝6,因a.elem[6]不空且a.elem[6].key≠84, 则 找第一次冲突处理后的地址H1＝(6＋1) MOD 16＝7，而a.elem[7]不空且 a.elem[7].key≠84,则找第二次冲突处理后的地址H2＝(6＋2) MOD 16＝8， a.elem[8]不空且a.elem[8].key＝84，则查找成功，返回记录在表中序号8。 给定值K＝38： 先求哈希地址H(38)＝12，a.elem[12]不空且a.elem[12].key≠38，则 找下一地址H1＝(12＋1) MOD 16＝13，由于a.elem[13]是空记录，则表 明表中不存在关键字等于38的记录。

（4）平均查找长度 ①查找成功时的平均查找长度 1．线性探测再散列 2．伪随机探测再散列、二次探测再散列和再哈希表 3．链地址法 ②查找不成功时的平均查找长度 1．线性探测再散列 2．伪随机探测再散列、二次探测再散列和再哈希表 3．链地址法

③公式推导 仅以伪随机探测的一组公式为例进行分析推导。 假定：1．哈希函数是均匀的。即产生表中各个地址的概率相等； 2．处理冲突后产生的地址也是随机的。 若设pi表示前i个哈希地址均发生冲突的概率；qi表示需进行i次比较才 找到一个“空位”的哈希地址（即前i－1次发生冲突，第i次不冲突）的概率。 则有： 可见，在pi和qi之间，存在关系式： qi＝pi-1－pi

由此，当长度为m的哈希表中已填有n个记录时，查找不成功的平均 查找长度为： （用归纳法证明） 由于哈希表中n个记录是先后填入的，查找每一个记录所需比较次数的期望 值，恰为填入此记录时找到此哈希地址所进行的比较次数的期望值。因此，对 表长为m、记录数为n的哈希表，查找成功时的平均查找长度为：

设对n个记录的查找概率相等。即pi＝1/n则： 度限定在一个范围内。