第8章 查找 预备知识 8.1 静态查找表 8.2 动态查找表 8.3 哈希表

本章重点难点 重点：顺序查找、二分查找、二叉排序树查找以 难点：二叉排序树的删除算法和平衡二叉树的 及散列表查找的基本思想和算法实现。 构造算法。

第8章 查找 预备知识 8.1 静态查找表 8.2 动态查找表 8.3 哈希表

预备知识 有关概念 (1) 查找表： 是由同一类型的数据元素(或记录)构成的集合。 (2) 静态查找表： 仅作查询和检索操作的查找表。 (3) 动态查找表： 在查找时包含插入、删除或修改。

预备知识 有关概念 (4) 主关键字 可以识别唯一的一个记录的数据项（字段）。 (5) 次关键字 关联若干项记录的数据项（字段）。 (6) 查找 根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。

预备知识 有关概念 (7) 查找成功 查找表中存在满足条件的记录。 (8) 查找不成功 查找表中不存在满足条件的记录。

预备知识 类型定义 typedef float Keytype; //Keytype定义为浮点数据类型 typedef int Keytype; //Keytype定义为整型数据类型 typedef char *Keytype; //Keytype定义为字符指针数据类型

预备知识 类型定义 数据元素类型定义为： typedef struct{ Keytype key;//关键字 … }SElemType; // SElemType结构体数据类型

预备知识 宏定义 //数值型关键字的比较 #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)

第8章 查找 预备知识 8.1 静态查找表 8.2 动态查找表 8.3 哈希表

8.1 静态查找表 8.1.1 顺序表的查找 8.1.2 有序表的查找 *8.1.3 静态树表的查找 8.1.4 索引顺序表的查找

见下页 8.1 静态查找表 静态查找表的抽象数据类型 ADT StaticSearchTable { 数据元素同属一个集合。 基本操作 P： 见下页 } ADT StaticSearchTable

8.1 静态查找表 基本操作 Create(&ST, n); //建立静态查找表 Destroy(&ST); //销毁静态查找表 Search(ST, key); //按关键字字key查找 Traverse(ST, Visit()); //遍历查找表

8.1 静态查找表 8.1.1 顺序表的查找 8.1.2 有序表的查找 *8.1.3 静态树表的查找 //自学 8.1.4 索引顺序表的查找

8.1.1 顺序查找表 顺序查找表存储结构 typedef struct { // 数据元素存储空间基址，建表时 // 按实际长度分配，0号单元留空 int length; // 表的长度 } SSTable; ElemType *elem;

8.1.1 顺序查找表 顺序查找表的思想 (1) 从查找表的第一个元素向后（或从最后一 个元素向前），比较当前位置数据元素的关键字 与查找关键字； (2) 若相等，输出当前位置，查找成功，若不 相等，走向下一个位置； (3) 循环执行(1)、(2)步，直到查找成功或超出 范围，表示查找失败。

查找55，从后向前 监视哨 表示没找到，返回值为0 8.1.1 顺序查找表 顺序查找表示例演示 查找55，从后向前 67 78 76 45 33 99 88 监视哨 55 67 78 76 45 33 99 88 表示没找到，返回值为0

查找33，从后向前 监视哨 查找成功，返回当前位置5 8.1.1 顺序查找表 顺序查找表示例演示 查找33，从后向前 67 78 76 45 33 99 88 监视哨 33 67 78 76 45 33 99 88 查找成功，返回当前位置5

8.1.1 顺序查找表 顺序查找表的算法与实现 int Search_Seq(SSTable ST, KeyType key) { // 在顺序表ST中顺序查找其关键字等于 // key的数据元素。若找到，则函数值 // 为该元素在表中的位置，否则为0。 ST.elem[0].key = key; // “哨兵” for (i=ST.length; ST.elem[i].key!=key; --i) ; // 从后往前找 return i; // 找不到时，i为0 } // Search_Seq

8.1.1 顺序查找表 顺序查找表算法分析 给定值进行比较的关键字个数的期望值: n 为表长 Pi 为查找表中第i个记录的概率 Ci为找到记录时，关键字的比较次数

什么情况下取最小值？ 8.1.1 顺序查找表 顺序查找表算法分析 在等概率查找的情况下， 顺序表查找的平均查找长度为： 思考题：在概率不等的情况下，ASL在 什么情况下取最小值？

8.1.1 顺序查找表 顺序查找表算法分析 答案：在不等概率查找的情况下，ASL 在 Pn≥Pn-1≥···≥P2≥P1 时取最小值。

 8.1.2 有序表的查找 折半查找的前提要求 想一想：英文字典的特点及英语单词的查找过程。 英文字典是有序的，英语单词的查找用的是折半查找。 折半查找的前提要求是顺序存储并且有序。

 8.1.2 有序表的查找 折半查找表的思想 (1) 将要查找关键字与查找表的中间的元素进行比较，若相等，返回当前位值； (2) 若查找关键字比当前位置关键字大，向前递归，否则向后递归。

查找21 mid 8.1.2 有序表的查找 折半查找表示例演示 位置 0 1 2 3 4 5 6 7 8 9 10  8.1.2 有序表的查找 折半查找表示例演示 查找21 位置 0 1 2 3 4 5 6 7 8 9 10 关键字05 13 19 21 37 56 64 75 80 88 90 low mid= (low+high)/2 high mid high=mid-1 low=mid+1 mid

 8.1.2 有序表的查找 折半查找表算法与实现 int Search_Bin ( SSTable ST, KeyType key ) { low = 1; high = ST.length; // 置区间初值 while (low <= high) { ……………… } return 0; // 顺序表中不存在待查元素 } // Search_Bin

 8.1.2 有序表的查找 折半查找表算法与实现 while (low <= high) { mid = (low + high) / 2; if （EQ (key , ST.elem[mid].key) ) return mid; // 找到待查元素 else if ( LT (key , ST.elem[mid].key) ) high = mid - 1; // 继续在前半区间进行查找 else low = mid + 1; // 继续在后半区间进行查找 }

 8.1.2 有序表的查找 折半查找表算法分析 0 1 2 3 4 5 6 7 8 9 10 5 13 19 21 37 56 64 75 80 88 90 用判定树描述折半查找的过程。 设n=2h-1 ( h=log2(n+1) ) 5 平均查找长度 2 8 3 6 9 1 4 7 10

8.1.4 索引顺序表的查找 索引顺序表的前提要求 (1) 查找表要求顺序存储 (2) 查找表分成n块，当i>j时，第i块中的最小元素大于第j块中的最大元素。

8.1.4 索引顺序表的查找 索引顺序表的查找思想 (1) 首先确定所要查找关键字在哪一块中。 (2) 在所确定的块中用顺序查找查找关键字。

8.1.4 索引顺序表的查找 索引顺序表的示例演示 索引表 该块最大关键字 该块起始地址 0 1 2 3 4 5 6 7 8 9 10 22 48 86 4 7 22 12 9 20 33 42 48 49 60 86 53 0 1 2 3 4 5 6 7 8 9 10 线性表

8.1.4 索引顺序表的查找 索引表的存储结构 typedef struct { keytype key; int addr; }indextype; indextype index[maxblock]; int block; }INtable; INtable IX;

8.1.4 索引顺序表的查找 索引顺序表的算法与实现 int SEARCH(SSTable ST,INtable IX, KeyType key ) { int i=0,s,e; //s记录在查找表中的开始位置 //e记录在查找表中的结束位置 { 在索引表中查找，确定s和e的值 } { 根据s和e的值在线性表中查找 } return -1 }

8.1.4 索引顺序表的查找 索引顺序表的算法与实现 while ((key>IX.index[i].key)&&(i<=IX.block)) i++; if (i<=IX.block) { s=IX.index[i].addr; if (i==IX.block) e=ST.length; else e=IX.index[i+1].addr-1; while (key!=ST.elem[s].key&&(s<=e) s=s+1; if (s<=e) return s; } return -1;

8.1.4 索引顺序表的查找 索引顺序表的算法分析 思考题：如果索引表长度为b，每块平均长度为L 平均查找长度是多少？ 答案：(b+1)/2+(L+1)/2。 思考题：长度为n的线性表, 分成多少块平均查找次 数最少? 答案：

第8章 查找 预备知识 8.1 静态查找表 8.2 动态查找表 8.3 哈希表

8.2 动态查找表 8.2.1 二叉排序树和平衡二叉树 8.2.2 B树和B+树

ADT DynamicSearchTable { 8.2 动态查找表 动态查找表的抽象数据类型 ADT DynamicSearchTable { D是具有相同特性的数据元素的集合，每个数据元素含有类型相同的关键字，可唯一标识数据元素。 数据对象D： 数据关系R： 数据元素同属一个集合。 见下页 基本操作P： }ADT DynamicSearchTable

8.2 动态查找表 基本操作 InitDSTable(&DT) // 初始化表 DestroyDSTable(&DT) // 销毁表 SearchDSTable(DT, key); // 按关键字查找 InsertDSTable(&DT, e); // 插入数据元素 DeleteDSTable(&T, key); // 删除数据元素 TraverseDSTable(DT, Visit()); // 遍历表

8.2 动态查找表 8.2.1 二叉排序树和平衡二叉树 8.2.2 B树和B+树

8.2.1 二叉排序树和平衡二叉树 二叉排序树的定义 二叉排序树(Binary Sort Tree)或者是一棵空树； 或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有的结点的关 键字的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有的结点的关 键字的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

8.2.1 二叉排序树和平衡二叉树 二叉排序树的存储结构 typedef struct BiTNode { // 结点结构 struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree; TElemType data;

8.2.1 二叉排序树和平衡二叉树 二叉排序树的查找思想 (1) 当二叉排序树不空时，先将给定值和根 结点的关键字比较，若相等，则查找成功；否则： (2) 若给定值小于根结点的关键字，则在左 子树上继续进行查找； (3) 若给定值大于根结点的关键字，则在右 子树上继续进行查找; (4) 直到找到或查到空结点时为止。

24 45 12 37 8.2.1 二叉排序树和平衡二叉树 二叉排序树的查找示例演示 例 在下图中查24 45 12 53 3 37 24 100 24 24 61 90 78

45 53 100 61 90 NULL 8.2.1 二叉排序树和平衡二叉树 二叉排序树的查找示例演示 例 在下图中查99 45 12 53 37 100 100 24 61 61 90 90 NULL 78

8.2.1 二叉排序树和平衡二叉树 二叉排序树的查找算法 BiTree SearchBST(BiTree T,keytype k) { BiTree p=T; while(p!=NULL) { if (p->data.key==k) return p; if (k<p->data.key) p=p->lchild else p=p->rchild } return NULL;

8.2.1 二叉排序树和平衡二叉树 二叉排序树的查找算法分析 12 45 24 24 53 37 12 37 94 45 53 树1平均查找长度 O(log2n) 树2平均查找长度O(n) 94

8.2.1 二叉排序树和平衡二叉树 二叉排序树的查找算法分析 (1) 二叉排序树的平均查找长度最差情况与顺序表相同(关键字有序时), 为O(n); (2) 最好情况与折半查找相同，是O(log2n)数量级的; (3) 二叉排序树的平均查找长度仍然是O(log2n)。 思考题：若按中序对二叉查找树进行遍历，遍历序列 有什么特点? 答案：按关键字升序排列。

8.2.1 二叉排序树和平衡二叉树 二叉排序树的插入算法思想 (1) 若二叉树为空： 则待插入结点*s作为根结点； (2) 当二叉排序树非空时： 将待插结点关键字与根结点进行比较，若相 等，则说明树中已有此结点，无须插入； 若小于根结点，插入左子树； 若大于根结点，插入右子树。

8.2.1 二叉排序树和平衡二叉树 二叉排序树的插入过程演示 在如下二叉排序树中插入25过程演示 45 45 12 12 53 37 3 37 100 24 24 61 25

8.2.1 二叉排序树和平衡二叉树 二叉排序树的插入算法 Status InsertBST(BiTree &T, ElemType e) { BiTree p,s; if (!SearchBST(T, e.key, NULL, p)) // 查找不成功 { s = (BiTree)malloc(sizeof(BiTNode)); s->data = e; s->lchild = s->rchild = NULL; if (!p) T = s; // 插入 s 为新的根结点 else if (LT(e.key, p->data.key)) p->lchild=s; // 插入s为左孩子 else p->rchild = s; // 插入 s 为右孩子 return TRUE; } else return FALSE; // 树中已有关键字相同的结点，不再插入 } // Insert BST

8.2.1 二叉排序树和平衡二叉树 二叉排序树的插入算法分析 (1) 二叉排序树的插入算法的时间复杂性与查找算法的时间复杂性相同; (2) 最好情况是O（log2n）;最坏情况是O(n); 平均情况是O(log2n)。 思考题：如何生成二叉排序树? 答案：从空树开始循环调用插入算法。

8.2.1 二叉排序树和平衡二叉树 二叉排序树的结点删除定义 在二元查找树上的删除一个结点，要求删除结点后，仍保持二叉排序树的结构特点不变。

8.2.1 二叉排序树和平衡二叉树 二叉排序树的结点删除方法 设被删结点为p, 其双亲结点为f，则p可能有以下4种情况： (1) p为叶结点 (2) p只有左子树 (3) p只有右子树 (4) p左右子树都有

f p 8.2.1 二叉排序树和平衡二叉树 二叉排序树的结点删除方法 45 (1) p为叶结点, 如右图所示. 12 53 3 37 51 100 删除方法： 释放结点p，修改其父结点f的相应指针。 24 61 p 25

p 8.2.1 二叉排序树和平衡二叉树 二叉排序树的结点删除方法 45 45 12 53 12 53 51 3 37 51 3 24 100 25 24 61 61 25 (2) p只有左子树,如上图所示. 删除方法：释放结点p，p的左子树顶替p点的位置。

p 8.2.1 二叉排序树和平衡二叉树 二叉排序树的结点删除方法 45 45 12 53 12 100 3 37 100 3 37 61 24 61 24 25 25 (3) p只有右子树, 如上图 所示. 删除方法：释放结点p，p的右子树顶替p点的位置。

8.2.1 二叉排序树和平衡二叉树 二叉排序树的结点删除方法 45 删除方法： 12 53 把左子树作为右子树中最小结点的左子树。 3 37 51 100 或者把右子树作为左子树中最大结点的右子树。 24 61 缺点： 增加了树的高度。 25 (4) p既有左子树，也有右子树, 如上图 所示。

8.2.1 二叉排序树和平衡二叉树 二叉排序树的结点删除方法 改进删除方法： 45 找一个结点顶替它的位置。 12 53 能够顶替它的结点是左子树中最大的，右子树中最小的。 我们用左子树最大的结点来顶替。 3 37 51 100 24 61 25 (4) p既有左子树，也有右子树, 如上图 所示。

8.2.1 二叉排序树和平衡二叉树 二叉排序树的结点删除算法 Status DeleteBST(BiTree &T, KeyType key) { if (!T) return FALSE; else { if (EQ(key, T->data.key)) return Delete(T); else if (LT(key, T->data.key)) return DeleteBST(T->lchild, key); else return DeleteBST(T->rchild, key); } } // DeleteBST

8.2.1 二叉排序树和平衡二叉树 二叉排序树的结点删除算法 Status Delete(BiTree &p) { BiTree q, s; if (!p->rchild) {q = p; p = p->lchild; free(q);} else if (!p->lchild) {q = p; p = p->rchild; free(q);} else {q = p; s = p->lchild;

8.2.1 二叉排序树和平衡二叉树 二叉排序树的结点删除算法 while (s->rchild) {q = s; s = s->rchild; } p->data = s->data; if (q != p) q->rchild = s->lchild; else q->lchild = s->lchild; free(s); } return TRUE; } // Delete

8.2.1 二叉排序树和平衡二叉树 二叉排序树的删除算法分析 (1) 二叉排序树的删除算法的时间复杂性与查找算法的时间复杂性相同; (2)最好情况是O（log2n）; 最坏情况是O(n); 平均情况是O(log2n)。

8.2.1 二叉排序树和平衡二叉树 平衡二叉树的定义 平衡二叉树又称AVL树 一棵AVL树或者是空树，或者是具有下 列性质的二叉排序树：它的左子树和右子 树都是AVL树，且左子树和右子树的高度 之差的绝对值不超过1。

8.2.1 二叉排序树和平衡二叉树 平衡二叉树示例 45 45 24 53 24 53 12 37 94 12 37 94 96 平衡二叉树 非平衡二叉树

8.2.1 二叉排序树和平衡二叉树 平衡因子的定义 平衡因子(BF--Balance Factor): 任一结点的左子树的高度减去右子树的高度所得的高度差称为该结点的平衡因子BF。 根据AVL树的定义，任一结点的平衡因子只能取 -1，0 和 1。 一棵平衡二叉排序树如果有n个结点，其高度可保持在O(log2n)，平均查找长度也可保持在O(log2n)。

8.2.1 二叉排序树和平衡二叉树 平衡二叉树的构造 给定序列25、27、30、12、11、18、14、20、15、22，求其AVL树 -1 -2 25 25 -1 25 RR旋转 27 27 1 30 27 27 1 25 30 25 30 12

8.2.1 二叉排序树和平衡二叉树 平衡二叉树的构造 给定序列25、27、30、12、11、18、14、20、15、22，求其AVL树 LL旋转 1 2 1 27 27 27 1 2 25 30 25 30 30 12 1 12 12 11 25 11

8.2.1 二叉排序树和平衡二叉树 平衡二叉树的构造 给定序列25、27、30、12、11、18、14、20、15、22，求其AVL树 2 LR旋转 2 先左旋后右旋 27 27 2 -1 30 30 25 12 25 -1 1 12 27 11 25 12 30 11 18 18 11 18

8.2.1 二叉排序树和平衡二叉树 平衡二叉树的构造 给定序列25、27、30、12、11、18、14、20、15、22，求其AVL树 1 25 25 -1 -1 -1 27 27 12 12 30 30 11 18 11 18 14 20

8.2.1 二叉排序树和平衡二叉树 平衡二叉树的构造 给定序列25、27、30、12、11、18、14、20、15、22，求其AVL树 2 RL旋转 2 先右旋后左旋 25 25 -1 -1 -2 -2 27 12 27 12 1 1 30 11 30 18 11 14 -1 14 20 18 15 15 20

8.2.1 二叉排序树和平衡二叉树 平衡二叉树的构造 给定序列25、27、30、12、11、18、14、20、15、22，求其AVL树 1 RL旋转 先右旋后左旋 25 -1 27 14 1 12 30 18 11 15 20

8.2.1 二叉排序树和平衡二叉树 平衡二叉树的构造思想 在构造过程中，每当插入一个新结点时，首先检查是否因插入而破坏了树的平衡性。 若是, 则找出其中最小不平衡子树，在保持二叉排序树特性的前提下, 调整最小不平衡子树中各结点之间的连接关系，以达到新的平衡。 最小不平衡子树：以离插入结点最近，且平衡因子绝对值大于 1 的结点作为根的子树。 假设二叉排序树的最小不平衡子树的根结点为 A ，则有四种形态需要调整。

A A B C C B B D A D E h D E h E C h + 1 h h h + 1 h h h (a) (b) (c) 8.2.1 二叉排序树和平衡二叉树 平衡二叉树的构造算法 ① LL型—右旋 1 A 2 A B C 1 C B B D A D E h D E h E C h + 1 h h h + 1 h h h (a) (b) (c)

A C B D E h h + 1 h B D A E C h + 1 h h 8.2.1 二叉排序树和平衡二叉树 平衡二叉树的构造算法 2 ① LL型—右旋 1 C B D E h void R_Rotate(BSTree &p) { BSTree lc; lc = p->lchild; p->lchild=lc->rchild; lc->rchild=p; p = lc; } h + 1 h B D A E C h + 1 h h

A A C B C B C A h D h D D E E h + 1 B h h h h + 1 h h (a) (b) (c) 8.2.1 二叉排序树和平衡二叉树 平衡二叉树的构造算法 ② RR型— 左旋 -1 A -2 A C -1 B C B C A h D h D D E E h + 1 B h h h h + 1 h h (a) (b) (c)

A B C D E C A D h + 1 B h h 8.2.1 二叉排序树和平衡二叉树 平衡二叉树的构造算法 ② RR型— 左旋 -2 -1 B C void L_Rotate(BSTree &p) {BSTree rc; rc = p->rchild; p->rchild=rc->lchild; rc->lchild = p; p = rc; } h D E h h + 1 C A D h + 1 B h h

8.2.1 二叉排序树和平衡二叉树 平衡二叉树的构造算法 #define EH 0 #define LH 1 #define RH -1 Status InsertAVL(BSTree &T,ElemType e, Boolean &taller) { if(!T) { T =(BSTree)malloc(sizeof(BSTNode)); T->data = e; T->lchild = T->rchild = NULL; T->bf = EH; taller = TRUE; }

8.2.1 二叉排序树和平衡二叉树 平衡二叉树的构造算法 else { if(EQ(e.key,T->data.key)) {taller=FALSE;return 0;} // 则不再插入 if (LT(e.key,T->data.key)){ if (InsertAVL(T->lchild,e,taller)==0) return 0;

8.2.1 二叉排序树和平衡二叉树 平衡二叉树的构造算法 Status InsertAVL(BSTree &T,ElemType e, Boolean &taller) { …………… if (taller) switch (T->bf) { case LH:LeftBalance(T);taller = FALSE;break; case EH:T->bf=LH;taller=TRUE;break; case RH: T->bf=EH;taller=FALSE;break; } // switch (T->bf) } // if

8.2.1 二叉排序树和平衡二叉树 平衡二叉树的构造算法 else {if(InsertAVL(T->rchild,e,taller)==0) return 0; if (taller) switch (T->bf) {case LH: T->bf = EH;taller=FALSE;break; case EH: T->bf=RH;taller=TRUE;break; case RH: RightBalance(T); taller=FALSE;break; } // switch (T->bf) } // else } // else return 1;}//InsertAVL

8.2.2 B-树和B+树 B-树的引入 当数据量太大时，不可能一次调入内存,要多次访问外存。硬盘的访问速度慢。主要矛盾变为减少访问外存次数。 用二叉树组织文件，若在查找时一次调入一个结点进内存，当文件的记录个数为100000时，要找到给定关键字的记录，平均需访问外存17次(log2100000)

8.2.2 B-树和B+树 B-树的定义 一棵m阶B-树，它或者为空，或者满足以下性质的m叉树： (1 )树中每个结点最多有m个子树； (2) 若根结点不是叶子结点，则至少有2棵子树。 (3) 除根结点以外的所有非终端结点至少有 m/2棵子树。 (4) 所有的非终端结点中包含下列信息数据 （n，A0，K1，A1，K2，…，Kn，An） Ki为关键字, 且Ki<Ki+1, 子树Ai中所有结点的关键字均小于Ki+1,大于Ki；An所指子树中所有结点的关键码均大于Kn, 每棵子树Ai都是m-路B-树，0≦i≦n。

8.2.2 B-树和B+树 B-树的特点分析 设一棵m路B树的高度为h，则各层阶点情况如下; 第一层最多1个; 第二层最多m个; 第三层最多m2个; ……… 第h层最多mh-1; 总结点最多为(mh-1)/(m-1) mh-1 关键字最多为?

8.2.2 B-树和B+树 B-树的查找算法 B-树的查找类似二叉排序树的查找，所不同的是B-树每个结点上是多关键码的有序表: (1)在到达某个结点时，先在(多关键码的)有序表中查找，若找到，则查找成功； (2)否则，到按照对应的指针信息指向的子树中去查找，当到达叶子结点时，则说明树中没有对应的关键码，查找失败。 即在B-树上的查找过程是一个顺指针查找结点和在结点中查找关键码交叉进行的过程。

8.2.2 B-树和B+树 B+树的定义 B+树可以看作是B-树的一种变形，在实现文件索引结构方面比B-树使用得普遍。 一棵m阶的B+树和m阶的B-树的差异在于： (1) 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键码记录的指针; (2 )所有的非终端结点可以看成是索引,结点中仅含有其子树根结点中最大(或最小)关键字; (3) 通常在B+树上有两个头指针，一个指向根结点，另一个指向关键码最小的叶子结点。

8.2.2 B-树和B+树 B+树的查找过程 在B+树上进行随机搜索、插入和删除的过程基本上与B-树类似。 只是在搜索过程中，若非终端结点上的关键码等于给定值，搜索并不停止，而是继续沿右指针向下，一直查到叶结点上的这个关键码。 在B+树，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。

第8章 查找 预备知识 8.1 静态查找表 8.2 动态查找表 8.3 哈希表

8.3 哈希表 8.3.1 什么是哈希表 8.3.2 哈希函数的构造方法 8.3.3 处理冲突的方法 8.3.4 哈希表的查找及其分析

8.3.1 什么是哈希表 哈希表的引入 例 学生名单的顺序存储与查找方式： 030530101 张三 男 030530103 李四 男 030530101 张三 男 030530103 李四 男 …………………………… 030530133 王五 男 … 030530101 张三 男 030530103 李四 男 030530133 王五 男 0 1 … …

8.3.1 什么是哈希表 哈希表的引入 030530101 张三 男 030530103 李四 男 …………………………… 030530101 张三 男 030530103 李四 男 …………………………… 030530133 王五 男 num=“030530101” name=“张三” sex=“男” substr(num,8,2)=“01” H(num)=atoi(substr(num,8,2))-1 F[H(num)].num=num; F[H(num)].name=name; F[H(num)].sex=sex; … 030530101 张三 男 030530103 李四 男 030530133 王五 男 0 1 2 … 32 …

8.3.1 什么是哈希表 哈希表的思想 以结点的关键字K为自变量，通过一个确定的函数关系H，计算出对应的函数值H(K)，把这个函数值作为结点的存储地址。 存储时： 把关键字为K的数据元素存储在地址H(K)中; 查找时： 给定关键字K，直接到地址H(k)中取数据元素。

8.3.1 什么是哈希表 哈希表的定义 用散列法存储的线性表叫散列表（Hash table）,又称杂凑表，哈希表，对应的函数称为散列函数、杂凑函数或哈希函数。

8.3.1 什么是哈希表 哈希表的有关概念 (1) 装填因子： 设散列表空间大小为n，填入表中的结点数为m,则称=m/n为散列表的装填因子。 (2) 散列函数的选取原则： ① 运算简单； ② 函数值域不能超过表长； ③ 尽可能使关键字不同时，散列函数值也不同。 (3) 冲突与同义词 若H(k1) = H(k2),则称为冲突， 发生冲突的两个关键字k1和k2称为同义词。

8.3.2 哈希函数的构造方法 直接定址法 取关键字或关键字的某个线性函数值为哈希地址。 即：H(key)=key或H(key)=a*key+b 其中a、b为常数。又称H(key)为自身函数。 优点：没有冲突； 缺点：若关键字集合很大，浪费存储空间严重。

8.3.2 哈希函数的构造方法 质数除余法 如果表长为n，取小于或等于n的最大质数m作模，关键字通过m取模运算，所得值作为散列地址。

在不知道关键字的全部情况时，可通过求关键字的平方值扩大差别，然后取中间几位作为哈希地址： 8.3.2 哈希函数的构造方法 平方取中法 在不知道关键字的全部情况时，可通过求关键字的平方值扩大差别，然后取中间几位作为哈希地址： int Hash(int key) { // 假设key是4位整数 key*=key； //求平方 key=key/100； // 去掉末尾的两位数 Key=key%1000;   return key； } 关键字 (关键字)2 地址 0100 0010000 100 0110 0012100 121 1010 1020100 201 1001 1002001 020 0111 0012321 123

8.3.2 哈希函数的构造方法 折叠法 数字分析法 基数转换法

8.3.3 处理冲突的方法 开放定址法的定义 又叫开放地址，用于顺序存储； 开放地址指地址单元为空，对于数组来说，是指还没存入数据的数组单元，在顺序存储结构中用一定方法进行散列存取的方法称为开放定址法。

8.3.3 处理冲突的方法 开放定址法示例演示 例 设散列表的长度为13，散列函数为: H(K) = K%13, 给定的关键字序列为: 19,14,23, 1,68,20,84,27,54,11,10, H(K)=6, 1,10, 1, 3, 7, 6, 1, 2, 11,10, 14 1 68 27 54 19 20 84 23 11 10 0 1 2 3 4 5 6 7 8 9 10 11 12 (1) 线性探测再散列法：若H(key)=d的单元发生冲突，则按下述方法进行探查： hi(k)=(h(k)+i)%n, n是散列表的长度，1≤i≤n-1

8.3.3 处理冲突的方法 二次聚集的概念 两个本来不发生冲突的非同义词，也就是散列地址不同的结点，发生争夺同一个散列地址的现象称为二次聚集或堆积。

8.3.3 处理冲突的方法 开放定址法查找示例演示 19, 14, 23, 1, 68, 20, 84, 27, 54, 11, 10, H(K)=6, 1,10, 1, 3, 7, 6, 1, 2, 11,10, 14 1 68 27 54 19 20 84 23 11 10 0 1 2 3 4 5 6 7 8 9 10 11 12 查找分析：查11，查40。 1、利用散列函数计算出关键字为K的数据元素的地址：d=H(K)，如果F[d].key==K,查找成功，返回d; 2、如果F[d].key!=K,依次查找F[(d+i)%n].key, 直到找到某个F[(d+j)%n].key==K,返回(d+j)%n, 或者找到一个开放地址为止，此时显示没找到。

8.3.3 处理冲突的方法 开放定址法删除示例演示 19,14,23, 1,68,20,84,27,54,11,10, H(K)=6, 1,10, 1, 3, 7, 6, 1, 2, 11,10, 14 1 68 27 54 19 20 84 23 11 10 0 1 2 3 4 5 6 7 8 9 10 11 12 删除分析：如果删除68，查找27。 删除结点时不能简单地将被删结点的地址置 空，否则将截断它之后填入散列表的同义词的查 找路径。

8.3.3 处理冲突的方法 开放定址法处理冲突的方法 (1) 线性探测再散列法：若H(key)=d的单元发生冲突，则按下述方法进行探查： hi(k)=(h(k)+i)%n, n是散列表的长度，1≤i≤n-1 (2) 二次探测再散列法：若H(key)=d的单元发生冲突，则按下述方法进行探查： hi(k)=(h(k)+di)%n,n是散列表的长度， di=12,-12,22,-22,…,+k2,-k2,(k≤n/2) (3) di=伪随机序列，称伪随机探测再散列。

8.3.3 处理冲突的方法 开放定址法处理冲突的方法 (4)再哈希法（再散列法） 设置RHi() i=1,2,…,k,多个哈希函数，当一个哈希函数产生冲突时，顺序用下一个。

8.3.3 处理冲突的方法 链地址法（又称拉链法）的示例演示 19,14,23, 1,68,20,84,27,54,11,10,79, 8.3.3 处理冲突的方法 链地址法（又称拉链法）的示例演示 19,14,23, 1,68,20,84,27,54,11,10,79, H(K)=6, 1,10, 1, 3, 7, 6, 1, 2, 11,10, 1, 1 2 3 4 … ^ 14 1 27 79 ^ 54 ^ 68 ^ ^ …… ………

8.3.3 处理冲突的方法 开放定址法与链地址法平均查找长度比较 外散列表平均查找长度短。 查79 14 1 68 27 54 19 20 84 79 23 11 10 0 1 2 3 4 5 6 7 8 9 10 11 12 14 1 27 79 ^

8.3.3 处理冲突的方法 拉链法的查找算法  　   (1) 根据关键字K找到关键字为K的结点所在单链表的首地址； (2)在所找到的单链表上进行顺序查找，若找到返回地址值，否则返回空值。 　 1 2 3 4 ^ 14 1 27 79 ^ 54 ^ 68 ^ ^

8.3.3 处理冲突的方法 拉链法的插入算法： (1) 根据关键字K找到关键字为K的结点所应该存在的单链表的首地址； (2)在单链表中查找结点为K的关键字，若找到，则无须插入； (3)若没找到，利用头插法或尾插法插入单链表中。 　

8.3.4 哈希表的查找和分析 哈希表存储结构 int hashsize[] = { 997, ... }; typedef struct { ElemType *elem; int count; // 当前数据元素个数 int sizeindex; // hashsize[sizeindex]为当前容量 } HashTable; #define SUCCESS 1 #define UNSUCCESS 0 #define DUPLICATE -1

8.3.4 哈希表的查找和分析 哈希表的查找算法 Status SearchHash (HashTable H, KeyType K, int &p, int &c) { } // SearchHash p = Hash(K); // 求得哈希地址 while ( H.elem[p].key != NULLKEY && !EQ(K, H.elem[p].key)） collision(p, ++c); // 求得下一探查地址 p if (EQ(K, H.elem[p].key)) return SUCCESS; // 查找成功，返回待查数据元素位置 p else return UNSUCCESS; // 查找不成功

8.3.4 哈希表的查找和分析 哈希表的插入算法分析 决定哈希表查找的ASL的因素： (1) 选用的哈希函数； (2) 选用的处理冲突的方法； (3) 哈希表饱和的程度，装载因子 α=n/m 值的大小（n—记录数，m—表的长度）

8.3.4 哈希表的查找和分析 哈希表的插入算法分析 一般情况下，可以认为选用的哈希函数是“均匀”的，也就是在讨论ASL时，认为各个位置被存数据的概率是相等的。 在这种情况下，可认为哈希表的ASL是处理冲突方法和装载因子的函数。

8.3.4 哈希表的查找和分析 查找成功时有下列结果： (1) 线性探测再散列

8.3.4 哈希表的查找和分析 查找成功时有下列结果： (2) 随机探测再散列 (3) 链地址法

8.3.4 哈希表的查找和分析 哈希表的平均查找长度是  的函数，而不是 n 的函数。 这说明，用哈希表构造查找表时，可以选择一个适当的装填因子  ，使得平均查找长度限定在某个范围内。

8.3.4 哈希表的查找和分析 散列法与其它方法的比较 (1) 不同的散列函数构成的散列表平均查找长度是不同的。 (2) 由同一个散列函数、不同的解决冲突方法构造的散列表，其平均查找长度是不相同的。 (3) 散列法与其他查找方法的区别: 除散列法外，其他查找方法有共同特征为：均是建立在比较关键字的基础上。 散列法是根据关键字直接求出地址的查找方法，其查找的期望时间为O(1)。

本章小结 (1) 熟练掌握顺序查找、二分查找、二叉排序树查找以及散列表查找的基本思想和算法实现。 (2) 熟练掌握顺序查找、二分查找、二叉排序树查找以及散列表查找的应用条件以及算法优劣。 (3) 掌握二叉排序树的删除算法。