第 9 章 查找

第一节： 查找的概念及常用操作 静态查找表 顺序表查找 有序表：折半查找 索引顺序表 考研真题1 动态查找表： 二叉排序树 2、平衡二叉树

9.1 查找的基本概念 查找的术语（P171） 查找表。由具有同一类型的数据元素（或记录）组成的集合。 9.1 查找的基本概念 查找的术语（P171） 查找表。由具有同一类型的数据元素（或记录）组成的集合。 关键字。是记录中某个项或组合项的值，用它可以标识一个记录。能唯一确定一个记录的关键字，称为主关键字；而不能唯一确定一个记录的关键字，称为次关键字。 查找。是指按给定的某个值k，在查找表中查找关键字为给定值k的记录。

9.1 查找的基本概念 查找算法的性能 查找算法时间性能通过关键码的比较次数来度量。 关键码的比较次数与哪些因素有关呢？ ⑴算法； 9.1 查找的基本概念 查找算法的性能 查找算法时间性能通过关键码的比较次数来度量。 关键码的比较次数与哪些因素有关呢？ ⑴算法； ⑵问题规模； ⑶待查关键码在查找集合中的位置； ⑷查找频率。查找频率与算法无关，取决于具体应用。通常假设pi是已知的。

9.1 查找的基本概念 查找算法的性能 ASL å 平均查找长度：查找算法进行的关键码的比较次数的数学期望值。计算公式为： = n c p 9.1 查找的基本概念 查找算法的性能 平均查找长度：查找算法进行的关键码的比较次数的数学期望值。计算公式为： ASL å = n i c p 1 其中：n：问题规模，查找集合中的记录个数； pi：查找第i个记录的概率； ci：查找第i个记录所需的关键码的比较次数。 结论：ci取决于算法；pi与算法无关，取决于具体应用。如果pi是已知的，则平均查找长度只是问题规模的函数。

9.1 查找的基本概念 查找技术 静态查找 ：不涉及插入和删除操作的查找 。 9.1 查找的基本概念 查找技术 静态查找 ：不涉及插入和删除操作的查找 。 静态查找适用于：查找集合一经生成，便只对其进行查找，而不进行插入和删除操作，或经过一段时间的查找之后，集中地进行插入和删除等修改操作； 动态查找 ：涉及插入和删除操作的查找。 动态查找适用于：查找与插入和删除操作在同一个阶段进行，例如当查找成功时，要删除查找到的记录，当查找不成功时，要插入被查找的记录。

静态查找 ： 静态查找表 顺序表查找：适用于顺序表及链表 有序表：折半查找 索引顺序表

9.2 顺序表查找 1）顺序查找 基本思想：从线性表的一端向另一端逐个将关键码与给定值进行比较，若相等，则查找成功，给出该记录在表中的位置；若整个表检测完仍未找到与给定值相等的关键码，则查找失败，给出失败信息。

顺序查找算法 int SeqSearch(Record r[], int n, int k) { int i=0; while (i<n&&r[i].key!=k) i++; if (i<n) return i; else return -1; } 由于查找中二个重要信息是记录和关键字，简化之，记录即为关键字，所以直接定义 int key 即可，不需要结构体类型定义

改进的顺序查找 基本思想：设置“哨兵”。哨兵就是待查值，将它放在查找方向的尽头处，免去了在查找过程中每一次比较后都要判断查找位置是否越界，从而提高查找速度。 例：查找k＝35 0 1 2 3 4 5 6 7 8 9 10 15 24 6 12 35 40 98 55 35 i i i i 哨兵 查找方向

改进的顺序查找 int SeqSearch2(Record r[], int n, int k) { int i=0; r[n].key=k; while (r[i].key!=k) i++; if (i<n) return i; else return -1; } ASL= = å n i c p 1 + - ) ( = (n+1)/2=O(n)

9.2 顺序表查找 顺序查找的缺点： 顺序查找的优点： 平均查找长度较大，特别是当待查找集合中元素较多时，查找效率较低。 9.2 顺序表查找 顺序查找的缺点： 平均查找长度较大，特别是当待查找集合中元素较多时，查找效率较低。 顺序查找的优点： 算法简单而且使用面广。 对表中记录的存储没有任何要求，顺序存储和链接存储均可； 对表中记录的有序性也没有要求，无论记录是否按关键码有序均可。

9.2 顺序表查找 2）折半查找（ 有序表的查找） 使用条件： 基本思想： 线性表中的记录必须按关键码有序； 必须采用顺序存储。 9.2 顺序表查找 2）折半查找（ 有序表的查找） 使用条件： 线性表中的记录必须按关键码有序； 必须采用顺序存储。 基本思想： 在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。

例：查找值为14的记录的过程： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 7 14 18 21 23 29 31 35 38 42 46 49 52 low=1 mid=7 high=13 31>14 18>14 mid=3 high=6 high=2 mid=1 7<14 low=2 mid=2 14=14

例：查找值为22的记录的过程： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 7 14 18 21 23 29 31 35 38 42 46 49 52 low=1 mid=7 high=13 31>22 18<22 mid=3 high=6 low=4 mid=5 23>22 high=4 mid=4 21<22 low=5 low>high

折半查找——非递归 int BiSearch(Record r[ ], int n, int k) //查找成功时返回该对象的下标序号，失败时返回-1 { low=0,high=n-1; while (low<=high) { mid=(low+high)/2; if (r[mid].key==k) return mid; else if (r[mid].key<k) low=mid+1; else high=mid-1; } return -1;

折半查找——递归 int BiSearch2(Record r[],int low,int high,int k) { if (low>high) return -1; else { mid=(low+high)/2; if (r[mid].key==k) return mid; if (r[mid].key<k) return BiSearch2(r,mid+1,high,k); return BiSearch2(r,low,mid-1,k); }

折半查找的判定树 判定树：折半查找的过程可以用二叉树来描述，树中的每个结点对应有序表中的一个记录，结点的值为该记录在表中的位置。通常称这个描述折半查找过程的二叉树为折半查找判定树，简称二叉判定树。

练习： 画出二叉判定树 设有序顺序表各元素编号： 0，1，2，3，4，5，6，7

折半查找的性能分析 ë û 具有n个结点的折半查找判定树的深度为 。 ë û 1 log 2 + n 查找成功：在表中查找任一记录的过程，即是折半查找判定树中从根结点到该记录结点的路径，和给定值的比较次数等于该记录结点在树中的层数。 查找不成功：查找失败的过程就是走了一条从根结点到外部结点的路径，和给定值进行的关键码的比较次数等于该路径上内部结点的个数。

9.2 顺序表查找 3）分块查找 基本思想：分块查找又称分块索引查找 分块查找过程分两步进行： 9.2 顺序表查找 3）分块查找 基本思想：分块查找又称分块索引查找 分块查找过程分两步进行： ① 确定要查找的记录所在的子表。用给定值k在索引表中查找索引项，以确定要查找的记录位于哪个子表中。 ② 确定要查找的记录的情况。对第①步确定的子表进行顺序查找，以确定要查找的记录的情况。 是顺序查找的改进

9.2 顺序表查找 3）分块查找 先确定待查记录所在的块（子表）， 接着在块中顺序查找。 9.2 顺序表查找 先确定待查记录所在的块（子表）， 接着在块中顺序查找。 3）分块查找 索引表关键字有序 第二个子表中所有记录的关键字均大于第一个子表中的关键字

考研真题1： 1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。【北京航空航天大学 2000 一、8 （2分）】 A． (n-1)/2 B. n/2 C. (n+1)/2 D. n 4. 下面关于二分查找的叙述正确的是 ( ) 【南京理工大学 1996 一、3 （2分）】 A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序且表中数据必须是整型，实型或字符型 C. 表必须有序，而且只能从小到大排列 D. 表必须有序，且表只能以顺序方式存储

考研真题1： 7. 用二分（对半）查找表的元素的速度比用顺序法( ) 【南京理工大学 1998 一、11 （2分）】 7. 用二分（对半）查找表的元素的速度比用顺序法( ) 【南京理工大学 1998 一、11 （2分）】 必然快 B. 必然慢 C. 相等 D. 不能确定 9. 具有12个关键字的有序表，折半查找的平均查找长度（ ）【中山大学 1998 二、10 （2分）】 A. 3.1 B. 4 C. 2.5 D. 5 10. 折半查找的时间复杂性为（ ）【中山大学 1999 一、15】 A. O（n2） B. O（n） C. O（nlogn） D. O（logn） 11．当采用分快查找时，数据的组织方式为 ( ) 【南京理工大学 1996 一、7 （2分）】 A．数据分成若干块，每块内数据有序 B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同

9.3 树表的查找 1）二叉排序树 二叉排序树（也称二叉查找树）：或者是一棵空的二叉树，或者是具有下列性质的二叉树： 9.3 树表的查找 1）二叉排序树 二叉排序树（也称二叉查找树）：或者是一棵空的二叉树，或者是具有下列性质的二叉树： ⑴ 若它的左子树不空，则左子树上所有结点的值均小于根结点的值； ⑵ 若它的右子树不空，则右子树上所有结点的值均大于根结点的值； ⑶ 它的左右子树也都是二叉排序树。 二叉排序树的定义采用的是递归方法。

二叉排序树 63 90 55 42 58 10 45 67 83 70 63 60 55 82 58 10 45 67 83 70 二叉排序树 非二叉排序树 中序遍历二叉排序树可以得到一个按关键码有序的序列

二叉排序树的插入 在一棵二叉排序树中插入值为k的结点，步骤如下： ① 若二叉排序树为空，则生成值为k的新结点s，同时将新结点s作为根结点插入。 ② 若k小于根结点的值，则在根的左子树中插入值为k的结点。 ③ 若k大于根结点的值，则在根的右子树中插入值为k的结点。 ④ 若k等于根结点的值，表明二叉排序树中已有此关键字，则无须插入。 从以上描述可知，插入过程是递归的。

例：插入值为98的结点 63 55 90 58 70 98 root 63 root ∧ 55 90 ∧ ∧ 58 ∧ ∧ 70 ∧ ∧ s

二叉排序树中插入关键字的算法 Int BSTinsert (BTNode *&bt, int key) { if (bt==NULL) { Bt=(BTNode*) malloc( sizeof(BTNode)); Bt->lchild=bt->rchild=NULL; Bt->key=key; Return 1; } Else { If(key==bt->key) Return 0; Else if( key < bt->key ) Return BSTInsert(bt->lchild,key); Return BSTInsert(bt->rchild,key); }

二叉排序树的构造 从空的二叉排序树开始，依次插入一个个结点 。 例：关键码集合为 {63，90，70，55，58}， 二叉排序树的构造过程为： 63 55 90 58 70

二叉排序树的构造算法 Void CreatBST( BTNode *&bt, int key [] ,int n) { int i; Bt=NULL; For(i=1; i<=n; ++i) BSTInsert (bt, key[i]); }

二叉排序树的查找 在二叉排序树中查找给定值k的过程是： 这是一个递归查找过程。

二叉排序树的查找的算法 BTNode * BSTSearch (BTNode * bt, int key) { if(bt==NULL) return NULL; Else { if ( bt->key==key) Return bt; Else if(key<bt->key) Return BSTSearch(bt->lchild, key); Return BSTSearch(bt->rchild, key); }

递归删除算法的步骤如下： ① 若二叉排序树为空，则表明不存在删除的结点，不进行删除操作。 ② 若给定值k小于根结点的值，则继续在根的左子树中删除。 ③ 若给定值k大于根结点的值，则继续在根的右子树中删除。 ④ 若给定值k等于根结点的值，则根结点即为要删除的结点，此时需要根据上述分析的三种结点情况：叶子结点、单支结点或双支结点，执行相应的删除操作。

方法一：用右子树中最小的结点替补定位*p的右子树的最左下结点*s，及其父结点*parent_s 若*s是叶子: parent_s->lchild=NULL; 若*s是有右孩子: parent_s->lchild=s->rchild;s->lchild=p->lchild; s->rchild=p->rchild; parent_p->lchild=s; 或 parent_p->rchild=s; 方法二：用左子树中最大的结点替补定位*p的左子树的最右下结点*s，及其父结点*parent_s 若*s是叶子: parent_s->rchild=NULL; 若*s是有左孩子: parent_s->rchild=s->lchild;s->lchild=p->lchild; s->rchild=p->rchild; parent_p->lchild=s; 或 parent_p->rchild=s;

4．二叉排序树的删除操作 分三种情况 : （1）删除叶子结点

（2）删除单支结点

（3）删除双支结点

二叉排序树的查找 例：在二叉排序树中查找关键字值为35，95的过程： 50 50 30 80 30 80 20 90 20 40 40 90 85 35 85 88 32 88 32

二叉排序树的查找性能分析 ASL =（1+2+3+4+5）/ 5= 3 ASL =（1+2+3+2+3）/ 5 = 2.2 由序列{1, 2, 3, 4, 5}得到二叉排序树： ASL =（1+2+3+4+5）/ 5= 3 3 1 2 5 4 由序列{3, 1, 2, 5, 4}得到二叉排序树： ASL =（1+2+3+2+3）/ 5 = 2.2 二叉排序树的查找性能取决于二叉排序树的形状，在O(log2n)和O(n)之间。

考研真题例一 51. 输入一个正整数序列（53,17,12,66,58,70,87,25,56,60），试完成下列各题。 按次序构造一棵二叉排序树BS。 依此二叉排序树，如何得到一个从大到小的有序序列？ 画出在此二叉排序树中删除“66”后的树结构。 【同济大学 2001 一 (10分)】

9.3.2 平衡二叉树 平衡二叉树：或者是一棵空的二叉排序树，或者是具有下列性质的二叉排序树： ⑴ 根结点的左子树和右子树的深度最多相差1; ⑵ 根结点的左子树和右子树也都是平衡二叉树。 平衡因子：结点的平衡因子是该结点的左子树的深度与右子树的深度之差。

9.3.2 平衡二叉树 结点的平衡因子＝HL-HR 5 4 8 2 1 是平衡树 非平衡树 在平衡树中，结点的平衡因子可以是1，0，-1。

平衡二叉树的构造 基本思想：在构造二叉排序树的过程中，每插入一个结点时，首先检查是否因插入而破坏了树的平衡性，若是，在保持二叉排序树特性的前提下，调整各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。

平衡二叉树的构造 设结点A为最小不平衡子树的根结点，对该子树进行平衡调整归纳起来有以下四种情况： 1. LL型 2. RR型 3. LR型

调整有4种情况 （1）LL型

（2）RR型

（3）LR型

（4）RL型

例题讲解二：P264：例9－3 已知关键码：16，3，7，11，9，26，18，14，15依次插入到一棵初始为空的AVL树中，画出插入每一个关键码后的AVL树。并标出平衡旋转的类型。构造完成后依次删除结点16，15，11.给出详细的操作过程。

考研真题2 12. 二叉查找树的查找效率与二叉树的( （1）)有关, 在 (（2）)时其查找效率最低【武汉交通科技大学1996 一、2(4分)】 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 13. 要进行顺序查找，则线性表（1）；要进行折半查询，则线性表（2）；若表中元素个数为n,则顺序查找的平均比较次数为（3）；折半查找的平均比较次数为（4）。【北方交通大学 1999 一、2 （4分）】 （1）（2）：A. 必须以顺序方式存储； B. 必须以链式方式存储； C. 既可以以顺序方式存储，也可以链式方式存储； D. 必须以顺序方式存储，且数据已按递增或递减顺序排好； E. 必须以链式方式存储，且数据已按递增或递减的次序排好。 （3）（4）：A.n B.n/2 C.n*n D.n*n/2 E.log2n F.nlog2n G.(n+1)/2 H.log2(n+1) 14．在等概率情况下,线性表的顺序查找的平均查找长度ASL为( （1） ),有序表的折半查找的ASL为( （2） ),对静态树表,在最坏情况下,ASL为( （3） ),而当它是一棵平衡树时,ASL为 ( （4） ),在平衡树上删除一个结点后可以通过旋转使其平衡,在最坏情况下需( （5） )次旋转。供选择的答案：【上海海运学院 1999 二、3 （5分）】 A. O(1) B. O( log2n ) C. O((log2n)2) D.O(nlog2n) E. O(n)

考研真题2 16．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找法。 16．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找法。 A. 分快查找 B. 顺序查找 C. 折半查找 D. 基于属性 【西安电子科技大学 2001应用一、8 （2分）】 18．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) 【合肥工业大学2000一、4（2分）】 A．（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90） C.（100，60， 80， 90， 120，110，130） D. (100，80， 60， 90， 120，130，110) 19. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。【合肥工大 2001 一、4 （2分）】 A. LL B. LR C. RL D. RR

练习： 已知关键码：DEC，FEB，NOV，OCT，JUL，SEP，AUG，APR，MAR，MAY，JUN，JAN依次插入到一棵初始为空的AVL树中，画出插入每一个关键码后的AVL树。并标出平衡旋转的类型。

小结 查找的概念及常用操作 静态查找表 动态查找表： 顺序表查找 有序表：折半查找 索引顺序表 考研真题1 二叉排序树 2、平衡二叉树 二叉排序树 2、平衡二叉树 对比各种查找算法的性能和适用情况。

复习： 查找的概念及常用操作 静态查找表 动态查找表： 顺序表查找 有序表：折半查找，二叉判定树 索引顺序表 考研真题1 二叉排序树（查找） 2、平衡二叉树 对比各种查找算法的性能和适用情况。 查找成功的平均查找长度，查找不成功的平均查找长度

第二节 B树 哈希表 B树的特性及查找性能过程 查找分析、B树插入和删除 B+树现B树的区别 查找思想 哈希函数构造方法及处理冲突的方法 性能分析（计算查找成功和失败的平均查找时间）

9.7 B树与B+树 什么是B树? B树的特征 B树中结点的插入和删除 什么是B+树?

B树的特征 或是空树，或是满足以下条件m叉树： 每个结点最多有m个分支，除根外，所有分支结点的子树数>=m/2; 根结点至少有二棵分支(除非它是叶子); 所有叶子结点都在同一级上。 结点内的关键字互不相同且按从小到大排列 N个分支的结点有n-1个关键字。 所有的非终端结点中包含下列信息数据：（n,A0,K1,A1,K2,A2……，Kn,An)

B树结点的插入 找到叶结点上的插入位置，直接插入 插入后检查被插入结点内关键字的个数，若大于m-1,则进行拆分。取第m/2个关键字升到父结点中，重复至满足B树的定义 不改变叶子结点的结构，只会使树变高。

B树插入实例 P268例9－4 用以下关键字序列{1，2，6，7，11，4，8，13，10，5，17，9，16，20，3，12，14，18，19，15}创建一棵5阶B-树。

B树中关键字的删除 如果要删除的关键字不在叶子上，则换孩子（以相邻关键字交换），使其转化为在叶子结点上。 删除的关键字在叶子上： 结点内关键字个数大于m/2-1，直接删除 结点内关键字个数等于m/2-1，若有兄弟结点中关键字个数大于m/2-1 ，则借兄弟，否则，对父结点或兄结点进行合并（并父兄）。

B树删除结点实例 P268例9－4 用以下关键字序列{1，2，6，7，11，4，8，13，10，5，17，9，16，20，3，12，14，18，19，15}创建一棵5阶B-树。给出删除关键字8，16，15，4的过程

练习： P282（6） 设有一颗空的3阶B－树，依次插入关键字{30，20，10，40，80，58，47，50，29，22，56，98，99}，请画出该树。 P283，4选择题

B树的特点： 平衡、高效、易变。 与其他知识点的联系： ①是二叉平衡树的扩展； ②是索引查找树的扩展； ③是树的孩子表示法的扩展。

B+树的定义 ①有n个子树的结点含有n个关键字； ②所有叶子结点按关键值组成有序链表： 包含了全部关键字的信息，及指向对应记录的指针； ③所有非终端结点是叶子结点的索引，其中关键值是对应子树中的最大/小关键值

B+树

考研真题一 21. 下面关于m阶B树说法正确的是( ) 【南京理工大学 1999 一、5 （2分）】 A． ①②③ B. ②③ C. ②③④ D. ③ 22. 下面关于B和B+树的叙述中，不正确的是( ) 【北方交通大学 2001 一、17 （2分）】 A. B树和B+树都是平衡的多叉树。 B. B树和B+树都可用于文件的索引结构。 C. B树和B+树都能有效地支持顺序检索。 D. B树和B+树都能有效地支持随机检索。 23. m阶B-树是一棵( ) 【北京邮电大学 2000 二、2 （20/8分）】 A. m叉排序树 B. m叉平衡排序树 C. m-1叉平衡排序树 D. m+1叉平衡排序树

考研真题一判断 21．完全二叉树肯定是平衡二叉树。 【南京航空航天大学 1996 六、5 （1分）】 24．有n个数存放在一维数组A[1..n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。 【北京邮电大学 1998 一、6 （2分）】 29. B-树中所有结点的平衡因子都为零。 【大连海事大学2001 一、（1，17） (1分)】 30. 在m阶B-树中每个结点上至少有m/2个关键字，最多有m个关键字。 【东北大学 1997 二、 4 (2分)】 36、B+树既能索引查找也能顺序查找。【青岛大学 2002 一、10 （1分）】

9.4 Hash查找 查找操作要完成什么任务？ 我们学过哪些查找技术？这些查找技术的共性？ 待查值k 顺序查找、折半查找、二叉排序树查找等。 以上讨论的查找方法，由于记录的存储位置与关键字之间不存在确定的关系，因此查找时需要进行一系列对关键字的查找比较，即“查找算法”是建立在比较的基础上的，查找效率由比较一次缩小的查找范围决定。 待查值k 确定k在存储结构中的位置

能否不用比较，通过关键码直接确定存储位置？ 理想的情况是，依据关键字直接得到其对应的记录位置，即要求关键字与记录位置间存在一一对应关系，通过这个关系，能很快地由关键字得到对应的记录位置。

散列技术仅仅是一种查找技术吗？ 散列是一种完整的存储结构吗？ 散列既是一种查找技术，也是一种存储技术。 散列只是通过记录的关键码定位该记录，没有完整地表达记录之间的逻辑关系，所以，散列主要是面向查找的存储结构。

散列技术适合于哪种类型的查找？ 散列技术一般不适用于允许多个记录有同样关键码的情况。散列方法也不适用于范围查找，换言之，在散列表中，我们不可能找到最大或最小关键码的记录，也不可能找到在某一范围内的记录。

散列技术的关键问题： 函数设计、冲突解决，ASL，装填因子 ⑴ 散列函数的设计。如何设计一个简单、均匀、存储利用率高的散列函数。 ① 所选函数尽可能简单，以便提高转换速度。 ② 所选函数对关键字计算出的地址，应在Hash地址集中大致均匀分布，以尽量减少冲突。

散列技术的关键问题： ⑵ 冲突的处理。如何采取合适的处理冲突方法来解决冲突。 ① Hash函数。若Hash函数选择得当，就可使Hash地址尽可能均匀地分布在Hash地址空间上，从而减少冲突的发生；否则，若Hash函数选择不当，就可能使Hash地址集中于某些区域，从而加大冲突的发生。 ② 处理冲突的方法。选择适当的Hash函数可以减少冲突，但不能避免冲突，因此当冲突发生时，必须有较好的处理冲突的方法。 ③ Hash表的装填因子。关键字个数/表长度

构造散列函数——直接定址法 H(key) = a  key + b （a，b为常数） 散列函数是关键码的线性函数，即： 例：关键码集合为{10, 30, 50, 70, 80, 90}，选取的散列函数为H(key)=key/10，则散列表为： 0 1 2 3 4 5 6 7 8 9 10 30 50 70 80 90 适用情况？ 事先知道关键码，关键码集合不是很大且连续性较好。

构造散列函数——除留余数法 散列函数为： H(key)=key mod p 如何选取合适的 p，产生较少同义词？ 14 7 散列地址 56 49 42 35 28 21 关键码 P常是小于或等于表长的最大素数

散列函数——数字分析法 根据关键码在各个位上的分布情况，选取分布比较均匀的若干位组成散列地址。 例：关键码为8位十进制数，散列地址为2位十进制数 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 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

散列函数——平方取中法 对关键码平方后，按散列表大小，取中间的若干位作为散列地址（平方后截取）。 例：散列地址为2位，则关键码123的散列地址为： (1234)2＝1522756 适用情况: 事先不知道关键码的分布且关键码的位数不是很大。

散列函数——折叠法 将关键码从左到右分割成位数相等的几部分，将这几部分叠加求和，取后几位作为散列地址。 例：设关键码为2 5 3 4 6 3 5 8 7 0 5，散列地址为三位。 2 5 3 4 6 3 5 8 7 + 0 5 ─── 1 3 0 8 移位叠加 2 5 3 3 6 4 5 8 7 + 5 0 ─── 1 2 5 4 间界叠加 适用情况: 关键码位数很多，事先不知道关键码的分布。

冲突的解决：散列函数——开放定址法 由关键码得到的散列地址一旦产生了冲突，就去寻找下一个空的散列地址，并将记录存入。 如何寻找下一个空的散列地址? （1）线性探测法 （2）二次探测法 （3）随机探测法

冲突的解决：线性探测法 当发生冲突时，从冲突位置的下一个位置起，依次寻找空的散列地址。 对于键值key，设H(key)=d，闭散列表的长度为m，则发生冲突时，寻找下一个散列地址的公式为： Hi=(H(key)＋di) % m （di=1，2，…，m-1） 用开放定址法处理冲突得到的散列表叫闭散列表。

线性探测法实例 例9-13 有关键字序列为{7，4，1，14，100，30，5，9，20，134}， Hash(key)=key % 13，用线性探测法处理冲突，建立Hash表 ，计算查找成功和失败的平均查找时间

真题练习 P282 4 已知一组关键字：{26，36，41，38，44，15，68，12，6，51，25}，用链地址法解决冲突，假设装填因子为0.75， Hash函数的形式为H(key)=key Mod P 确定表长，构造Hash 函数 计算等概率下查找成功的平均查找长度 计算等概率下查找失败的平均查找长度（只将与关键字比较次数计算在内）

9.4.3 Hash查找算法及分析 在线性探测法构造的散列表中查找算法——C++描述 int HashSearch_1(int hash[ ], int m, int k) { pos=k%m; //计算Hash地址 t=pos; while (hash[pos]!=EMPTY) //当Hash地址中的记录不为空时循环 if (hash[pos]==k) return pos; //查找成功，返回下标 else pos=(pos+1)%m; if (pos==t) return -1; //查找失败，返回-1 } return -1; //查找失败，返回-1

散列查找的性能分析 由于冲突的存在，产生冲突后的查找仍然是给定值与关键码进行比较的过程。 在查找过程中，关键码的比较次数取决于产生冲突的概率。而影响冲突产生的因素有： （1）散列函数是否均匀 （2）处理冲突的方法 （3）散列表的装载因子 α=表中填入的记录数/表的长度

考研真题二 32. 假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？( ) A．k-1次 B. k次 C. k+1次 D. k（k+1）/2次 【中国科技大学 1998 二、3 （2分）】【中科院计算所1998 二、3 （2分）】 34. 散列函数有一个共同的性质，即函数值应当以( )取其值域的每个值。 A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率 【西安电子科技大学01应用一、7 （2分）】 【北京邮电大学 1999 一、4 （2分）】 35. 散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。 （1）元素59存放在散列表中的【北方交通大学 2001 一、（19，20）（4分）】地址是（ ）。 A． 8 B. 9 C. 10 D. 11 （2）存放元素59需要搜索的次数是（ ）。 A． 2 B. 3 C. 4 D. 5 36. 将10个元素散列到100000个单元的哈希表中，则（ ）产生冲突。【北京邮电大学 2001 一、4 （2分）】 A. 一定会 B. 一定不会 C. 仍可能会

真题练习 已知关键字集合为{53，17，19，61，98，75，79，63，46，49}，用除留余数法将关键字散列到地址区间{100，101，102，103，104，105，106，107，108，109}内，若产生冲突，用开放定址法的线性探查法解决。 写出选用的hash函数及形成的hash表。并计算查找成功时的平均查找长度。

作业：P283，（二）

小结 B树 哈希表 B树的特性及查找性能过程 查找分析、B树插入和删除 B+树现B树的区别 查找思想 哈希函数构造方法及处理冲突的方法 性能分析

考研真题一

考研真题二 28. 下面关于哈希(Hash，杂凑)查找的说法正确的是( ) 【南京理工大学 1998 一、10 （2分）】 B．除留余数法是所有哈希函数中最好的 C．不存在特别好与坏的哈希函数，要视情况而定 D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可 29. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 (（1）) 个链表。这些链的链首指针构成一个指针数组，数组的下标范围为 (（2）) 【南京理工大学 1999 一、12(13) （4分）】 （1） A．17 B. 13 C. 16 D. 任意 （2） A．0至17 B. 1至17 C. 0至16 D. 1至16 30. 关于杂凑查找说法不正确的有几个( ) 【南京理工大学 2000 一、16 （1.5分）】 （1）采用链地址法解决冲突时，查找一个元素的时间是相同的 （2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的 （3）用链地址法解决冲突易引起聚集现象 （4）再哈希法不易产生聚集 A. 1 B. 2 C. 3 D. 4

考研真题二 7. 对下面的关键字集{30,15,21,40,25,26,36,37}若查找表的装填因子为0.8，采用线性探测再散列方法解决冲突，做： （1）设计哈希函数； （2）画出哈希表； （3）计算查找成功和查找失败的平均查找长度； （4）写出将哈希表中某个数据元素删除的算法； 【东北大学 2001 六 (18分)】

考研真题二判断 11．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。 【中科院软件所 1997 一、6 （1分）】 15. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。【西安交通大学 1996 二、 3 (3分)】 16．对无序表用二分法查找比顺序查找快。【青岛大学 2002 一、8 （1分）】 17．对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。【上海海运学院 1995 一、11 （1分） 1998 一、12 （1分）】 19． 最佳二叉树是AVL树（平衡二叉树）。【北京大学 1994 】

查找成功时 查找不成功时 线性探测法 二次探测法 拉链法 几种不同处理冲突方法的平均查找长度 查找成功时 查找不成功时 ASL 处理冲突方法 线性探测法 二次探测法 拉链法