武汉理工大学华夏学院 -信息工程系第七章 查找由于查找运算的使用频率很高，几乎在任何一个计算机系统软件和应用软件中都会涉及到，所以当问题所涉及的数据量相当大时，查找方法的效率就显得格外重要。在一些实时查询系统中尤其如此。因此，本章将系统地讨论各种查找方法，并通过对它们的效率分析来比较各种查找方法的优劣。
武汉理工大学华夏学院 -信息工程系
7.1 查找的基本概念
1,查找表和查找结果一般，假定被查找的对象是由一组结点组成的表 ( Table)或文件，而每个结点则由若干个数据项组成。并假设每个结点都有一个能惟一标识该结点的关键字。
查找 (Searching)的定义是：给定一个值 K,在含有 n个结点的表中找出关键字等于给定值,K
的结点。若找到，则查找成功,返回该结点的信息或该结点在表中的位置 ;否则查找失败，
返回相关的指示信息。
搜索关键字武汉理工大学华夏学院 -信息工程系
（ 1）动态查找和静态查找若在查找的同时对相应的数据结构做修改操作 (如插入和删除 ),则称之为动态查找。否则称之为静态查找 。
2,查找方法分类
（ 2）内查找和外查找查找还有内查找和外查找之分的分类方法。
若整个查找过程都在内存中进行，则称之为内查找；反之，若查找过程中需要访问外存，则称之为外查找。
武汉理工大学华夏学院 -信息工程系
3,平均查找长度 ASL
查找运算的主要操作是关键字的比较，所以通常把查找过程中对关键字需要执行的 平均比较次数 (也称为平均查找长度 )作为衡量一个查找算法效率优劣的标准。
平均查找长度 ASL(Average Search Length)定义为：
ASL=∑P i*Ci (1<=i<=n)其中：
① n是结点的个数；
② Pi是查找第 i个结点的概率。若不特别声明，认 为每个结点的查找概率相等，即 pl=p2…=p n=1/n;
③ ci是找到第 i个结点所需进行的比较次数。
武汉理工大学华夏学院 -信息工程系
7.2 静态查找在表的组织方式中，线性表是最简单的一种。
顺序查找是一种最简单的查找方法。
基本思想是：从表的一端开始,顺序扫描线性表，依次将扫描到的结点关键宇和给定值 K相比较。若当前扫描到的结点关键字与 K相等，则查找成功 ;若扫描结束后,仍未找到关键字等于 K
的结点，则查找失败。
（一）顺序查找 (Sequential Search)
1,顺序查找的基本思想武汉理工大学华夏学院 -信息工程系
2,顺序查找的存储结构要求顺序查找方法既适用于线性表的顺序存储结构也适用于线性表的链式存储结构（使用单链表作存储结构时，扫描必须从第一个结点开始）。
（ 1）类型说明
typedef struct{
KeyType key；
InfoType otherinfo； //此类型依赖于应用
}NodeType；
typedef NodeType SeqList[n+1]； //0号单元用作哨兵
3,基于顺序结构的顺序查找算法武汉理工大学华夏学院 -信息工程系
（ 2）具体算法
int SeqSearch(Seqlist R,KeyType K)
{ //在顺序表 R[1..n]中顺序查找关键字为 K的结点,
//成功时返回找到的结点位置，失败时返回 0
int i；
R[0].key=K； //设置哨兵
for(i=n； R[i].key!=K;i--)； //从表后往前找
return i； //若 i为 0，表示查找失败,否则 R[i]是要找的结点
} //SeqSearch
武汉理工大学华夏学院 -信息工程系
（ 3）算法分析为了在 for循环中省去判定防止下标越界的条件 i≥1,从而节省比较的时间。
②成功时的顺序查找的平均查找长度：
在等概率情况下,pi=1/n(1≤i≤n),故成功的平均查找长度为,(n+…+2+1)/n=(n+1)/2 即查找成功时的平均比较次数约为表长的一半。若 k 值不在表中,则须进行 n+1
次比较之后才能确定查找失败。
① 算法中监视哨 R[0]的作用武汉理工大学华夏学院 -信息工程系
③ 链表结构的顺序查找算法设被查数据是一个单链表，其数据类型描述为：
Struct LNode
｛ elemtype data;
struct LNode * next；
｝
struct lnode *P,*head；
elemtype data V；
/* 要查找的数据用 V表示 */
则查找的第一个元素从头开始，最后一个元素应为指针场为空的结点（结束条件）,
算法描述如下：
武汉理工大学华夏学院 -信息工程系
P=*head
否否
p＝ P->next
显示查找不成功显示查找结果结束输入待查值 V
P=空
P－ >data＝ V
武汉理工大学华夏学院 -信息工程系
（ 4) 若事先知道表中各结点的查找概率不相等和它们的分布情况，则应将表中结点按查找概率由小到大地存放，以便提高顺序查找的效率。为了提高查找效率，对算法 SeqSearch做如下修改：每当查找成功，就将找到的结点和其后继 (若存在 )结点交换。这样,使得查找概率大的结点在查找过程中不断往后移，便于在以后的查找中减少比较次数。
武汉理工大学华夏学院 -信息工程系
④顺序查找的优点
⑤顺序查找的缺点查找效率低,因此,当 n较大时不宜采用顺序查找。
算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。
武汉理工大学华夏学院 -信息工程系
（二） 折半（二分）查找
1、二分查找 (Binary Search)
二分查找又称折半查找，它是一种效率较高的查找方法。
二分查找要求：线性表是有序的，即表中结点按关键字从小到大（或从大到小），并且要用向量作为表的存储结构（即用顺序存储方法进行存储）。不妨设有序表是递增有序的。
2、二分查找的基本思想二分查找的基本思想是,（设 R[low..high]
是当前的查找区间）
武汉理工大学华夏学院 -信息工程系
(1)首先确定该区间的中点位置：
mid＝（ low＋ high） /2
其中：
low为左界结点下标,high为右 界结点下标。
(2)然后将待查的 K值与 R[mid].key比较：
若相等,则查找成功并返回此位置,否则须确定新的查找区间,继续二分查找,具体方法如下：
① 若 R[mid].key>K,则由表的有序性可知
R[mid..n].keys均大于 K,因此若表中存在关键字等于 K的结点，则该结点必定是在位置 mid
左边的子表 R[low..mid-1]中，故新的查找区间是左子表 R[low..mid-1]。
武汉理工大学华夏学院 -信息工程系
② 类似地，若 R[mid].key <K,则要查找的 K必在
mid的右子表 R[mid+1..high]中,即新的查找区间是右子表 R[mid+1..high],下一次查找是针对新的查找区间进行的。
因此，从初始的查找区间 R[1..n]开始,,此时 low＝ 1,high＝ n。每经过一次与当前查找区间的中点位置上的结点关键字的比较,就可确定查找是否成功,不成功则当前的查找区间就缩小一半,这一过程重复直至找到关键字为 K的结点,或者直至当前的查找区间为空 (即查找失败 )时为止。
武汉理工大学华夏学院 -信息工程系例如：在关键字有序序列
〔 2,4,7,9,10,14,18,26,32,40〕 中采用二分查找法查找 V=7的元素。查找过程如下开始：
2 4 7 9 10 14 18 26 32 40
Low＝ 1 high＝ 10?
武汉理工大学华夏学院 -信息工程系第一次比较,mid＝（ 1+10)/2取整）＝ 5
2 4 7 9 10 14 18 26 32 40
Low＝ 1 mid＝ 5high＝ 4 注：右端点左移第二次比较,mid＝（ 1+4)/2取整）＝ 2
2 4 7 9 10 14 18 26 32 40
mid＝ 3
Low＝ 3
Low＝ 1
Mid＝ 2
第三次比较,mid＝（ 2+4)/2取整）＝ 3
2 4 7 9 10 14 18 26 32 40
注：左端点右移查找完成high＝ 4
high＝ 4
武汉理工大学华夏学院 -信息工程系
int BinSearch(SeqList R,KeyType K)
{//在有序表 R[1..n]中进行二分查找，成功时返回结点的位置，失败时返回零
int low=1,high=n,mid； //置当前查找区间上、下界 的 初值
while(low<=high){ //当前查找区间 R[low..high]非空
mid=(low+high)/2；
if(R[mid].key==K) return mid； //查找成功返回
if(R[mid].kdy>K)
high=mid-1; //继续在 R[low..mid-1]中查找
else
low=mid+1； /继续在 R[mid+1..high]中查找 /
}
return 0； //当 low>high时表示查找区间为空，查找失败
} //BinSeareh
3,二分查找算法二分查找算法亦很容易给出其递归程序【参见练习】
武汉理工大学华夏学院 -信息工程系
4,二分查找的优点和缺点虽然二分查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。既使采用高效率的排序方法也要花费 O(nlgn)的时间。
二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。
对那些查找少而又经常需要改动的线性表，
可采用链表作存储结构，进行顺序查找。链表上无法实现二分查找。
武汉理工大学华夏学院 -信息工程系
5,二分查找的平均查找长度设内部结点的总数为 n=2h-1,则判定树是深度为 h=lg(n+1)的满二叉树 (深度 h不计外部结点 )。
树中第 k层上的结点个数为 2k-1,查找它们所需的比较次数是 k。 因此在等概率假设下，二分查找成功时的平均查找长度为：
ASLbn≈lg(n+1)-1
二分查找在查找失败时所需比较的关键字个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度。即为,[lg(n+1)]
二分查找的最坏性能和平均性能相当接近。
武汉理工大学华夏学院 -信息工程系
（三） 分块查找分块查找 (Blocking Search)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。
1,分块查找表存储结构分块查找表由,分块有序,的线性表和索引表组成。
（ 1）,分块有序,的线性表表 R[1..n]均分为 b块，前 b-1块中结点个数为 s=[n/b],
第 b块的结点数小于等于 s； 每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是 "分块有序 "的。
武汉理工大学华夏学院 -信息工程系抽取各块中的最大关键字及其起始位置构成一个索引表 ID[l..b],即,ID[i] (1≤i≤b) 中存放第 i块的最大关键字及该块在表 R中的起始位置。由于表 R是分块有序的，所以索引表是一个递增有序表。
【例】 对于关键字序列为：
｛ 9,22,12,14,35,42,44,38,48,60,58,4778,80,77,82｝
的线性表建分块索引表上例中共有 16个元素,可以将其分为四块，其块表与索引表为：
（ 2）索引表武汉理工大学华夏学院 -信息工程系块表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
9 22 12 14 35 42 44 38 48 60 58 47 78 80 77 82
索引表
data low high
22 1 4
44 5 8
60 9 12
82 13 16
武汉理工大学华夏学院 -信息工程系分块查找的基本思想是：
（ 1）首先查找索引表索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。
（ 2）然后在已确定的块中进行顺序查找由于块内元素无序，只能采用顺序查找的方法实现块内查找。
2、分块查找的基本思想武汉理工大学华夏学院 -信息工程系
3、分块查找示例
【例】对于上例的存储结构：
（ 1）查找关键字等于给定值 K=35的结点因为索引表比较小，不妨用顺序查找方法查找索引表。即首先将 K依次和索引表中各关键字比较，直到找到第 1个关键宇大小等于 K的结点，由于 K<44,所以关键字为 35的结点若存在的话，则必定在第二块中；然后，由
ID[2].addr找到第二块的起始地址 5，从该地址开始在 R[5..8]中进行顺序查找，
直到 R[5].key=K为止。此时查找成功。
武汉理工大学华夏学院 -信息工程系
（ 2）若查找关键字等于给定值 K=79的结点先确定第四块，然后在该块中查找。因该块中查找不成功，故说明表中不存在关键字为
79的结点。
具体过程为：
先查索引表，将 K与 s[i]（ 1<=i<=4）
看 k是否小于等于 s[i],若是则块号为 i，
不是将 i加 1继续查找块号；当块号为 i
确定后，再定该块的起止下标，即起始下标为 s[i].low 终止 下标为 s[i].gigh 最后按顺序查找的方法在该范围内查找。
武汉理工大学华夏学院 -信息工程系
4、算法分析
（ 1）平均查找长度 ASL
分块查找是两次查找过程。整个查找过程的平均查找长度是两次查找的平均查找长度之和。
①以二分查找来确定块,分块查找成功时的平均查找长度
ASLblk=ASLbn+ASLsq≈lg(b+1)1+(s+1)/2≈lg(n/s+1)+s/2
② 以顺序查找确定块，分块查找成功时的平均查找长度
ASL'blk=(b+1)/2+(s+1)/2=(s2+2s+n)/(2s)
注意,分块查找算法的效率介于顺序查找和二分查找之间。
武汉理工大学华夏学院 -信息工程系
（ 2）块的大小在实际应用中，分块查找不一定要将线性表分成大小相等的若干块，可根据表的特征进行分块。
【例】一个学校的学生登记表，可按系号或班号分块。
（ 3） 结点的存储结构各块可放在不同的向量中，也可将每一块存放在一个单链表中。
分块查找的优点是：
① 在表中插入或删除一个记录时，只要找到该记录所属的块，
就在该块内进行插入和删除运算。
② 因块内记录的存放是任意的,所以插入或删除比较容易，
无须移动大量记录。
分块查找的主要代价是增加一个辅助数组的存储空间和将初始表分块排序的运算。
（ 4）分块查找的优点武汉理工大学华夏学院 -信息工程系
7.3 动态查找当用线性表作为表的组织形式时，可以有三种查找法。其中以二分查找效率最高。但由于二分查找要求表中结点按关键字有序，且不能用链表作存储结构，因此，
当表的插入或删除操作频繁时，为维护表的有序性，势必要移动表中很多结点。这种由移动结点引起的额外时间开销，就会抵消二分查找的优点。也就是说，二分查找只适用于静态查找表。若要对动态查找表进行高效率的查找，可采用下面介绍的几种特殊的二叉树或树作为表的组织形式。不妨将它们统称为树表。下面将分别讨论在这些树表上进行查找和修改操作的方法。
武汉理工大学华夏学院 -信息工程系
（一） 二叉排序树
1、二叉排序树的定义二叉排序树 (Binary Sort Tree)又称二叉查找
(搜索 )树 (Binary Search Tree)。 其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：
① 若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
② 若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
③ 左、右子树本身又各是一棵二叉排序树。
上述性质简称二叉排序树性质 (BST性质 )，
故二叉排序树实际上是满足 BST性质的二叉树。
武汉理工大学华夏学院 -信息工程系
2、二叉排序树的特点由 BST性质可得：
(1)二叉排序树中任一结点 x,其左 (右 )子树中任一结点 y(若存在 )的关键字必小 (大 )于 x的关键字。
(2)二叉排序树中，各结点关键字是惟一的。
注意：
实际应用中,不能保证被查找的数据集中各元素的关键字互不相同,所以可将二叉排序树定义中 BST性质 (1)里的,小于,改为,大于等于,,或将 BST性质 (2)里的 "大于 "改为 "小于等于 "，甚至可同时修改这两个性质。
武汉理工大学华夏学院 -信息工程系
(3)按中序遍历该树所得到的中序序列是一个递增有序序列。
【例】下图所示的两棵树均是二叉排序树，它们的中序序列均为有序序列,2,3,4,5,7,8。
4
2
3
7
5 8
42
3 7
5
8
武汉理工大学华夏学院 -信息工程系
3、二叉排序树的存储结构
typedef int KeyType； //假定关键字类型为整数
typedef struct node
{ //结点类型
KeyType key； //关键字项
InfoType otherinfo； //其它数据域,InfoType视应用情况而定，下面不处理它
struct node *lchild,*rchild； //左右孩子指针
} BSTNode；
typedef BSTNode *BSTree； //BSTree是二叉排序树的类型武汉理工大学华夏学院 -信息工程系
4、二叉排序树上的运算
（ 1） 二叉排序树的插入和生成
① 二叉排序树插入新结点的过程在二叉排序树中插入新结点，要保证插入后仍满足 BST性质。其插入过程是：
(a)若二叉排序树 T为空，则为待插入的关键字 key申请一个新结点，并令其为根；
(b)若二叉排序树 T不为空，则将 key和根的关键字比较：
(i)若二者相等，则说明树中已有此关键字 key，
无须插入。
(ii)若 key<T→key,则将 key插入根的左子树中。
(iii)若 key>T→key,则将它插入根的右子树中。
武汉理工大学华夏学院 -信息工程系子树中的插入过程与上述的树中插入过程相同。如此进行下去，直到将 key 作为一个新的叶结点的关键字插入到二叉排序树中，或者直到发现树中已有此关键字为止。
例如,设有结点序列 为 34,17,45,23,40
要求构造一棵二叉排序树。
步骤如下：
武汉理工大学华夏学院 -信息工程系将 34作为新树的树根
34
17 45
23
输入 17，与树根比较，
因 17 比 34小，则将 17挂在 34 的左子树下 。
输入 45，与树根比较，
因 45比 34大，则将 45挂在 34 的右子树下。
输入 23，与树根比较，因 23比 34小，
则将 23挂在 34 的左子树下。又因左子树不空则将 23与 17比较，而 23比 17大，故挂在其右子树下输入 40，与树根比较，因 40比 34大，
则将 40挂在 34 的右子树下。又因右子树不空则将 40与 45比较，而 40比 45小，故挂在其左子树下
40
武汉理工大学华夏学院 -信息工程系
③ 二叉排序树插入新结点的非递归算法
void InsertBST(BSTree *Tptr,KeyType key)
{//若二叉排序树 *Tptr中没有关键字为 key,则插入，否则直接返回
BSTNode *f,*p=*TPtr； //p的初值指向根结点
while(p){ //查找插入位置
if(p->key==key) return； //树中已有 key,无须插入
f=p； //f保存当前查找的结点
p=(key<p->key)?p->lchild,p->rchild；
//若 key<p->key,则在左子树中查找，否则在右子树中查找
} //endwhile
武汉理工大学华夏学院 -信息工程系
p=(BSTNode *)malloc(sizeof(BSTNode))；
p->key=key；
p->lchild=p->rchild=NULL； //生成新结点
if(*TPtr==NULL) //原树为空
*Tptr=p； //新插入的结点为新的根
else //原树非空时将新结点关 p作为关 f的左孩子或右孩子插入
if(key<f->key)
f->lchild=p；
else f->rchild=p；
} //InsertBST
武汉理工大学华夏学院 -信息工程系
④ 二叉排序树的生成二叉排序树的生成，是从空的二叉排序树开始，每输入一个结点数据，就调用一次插入算法将它插入到当前已生成的二叉排序树中。生成二叉排序树的算法如下：
BSTree CreateBST(void)
{ //输入一个结点序列，建立一棵二叉排序树，将根结点指针返回
BSTree T=NULL； //初始时 T为空树
KeyType key；
scanf(“％ d”,&key)； //读人一个关键字
while(key){ //假设 key=0是输人结束标志
InsertBST(&T,key)； //将 key插入二叉排序树 T
scanf(“％ d”,&key)； //读人下一关键字
}
return T； //返回建立的二叉排序树的根指针
} //BSTree
武汉理工大学华夏学院 -信息工程系
（ 2）二叉排序树的删除从二叉排序树中删除一个结点，不能把以该结点为根的子树都删去，并且还要保证删除后所得的二叉树仍然满足 BST性质。
① 删除操作的一般步骤
(1) 进行查找查找时，令 p指向当前访问到的结点,parent指向其双亲 (其初值为 NULL)。 若树中找不到被删结点则返回，否则被删结点是 *p。
(2) 删去 *p。
删 *p时，应将 *p的子树 (若有 ) 仍连接在树上且保持 BST性质不变。按 *p的孩子数目分三种情况进行处理。
武汉理工大学华夏学院 -信息工程系
② 删除 *p结点的三种情况
(1)*p是叶子 (即它的孩子数为 0)
无须连接 *p的子树，只需将 *p的双亲 *parent中指向 *p的指针域置空即可。
(2)*p只有一个孩子 *child
只需将 *child和 *p的双亲直接连接后,即可删去 *p。
*p 既可能是 *parent的左孩子也可能是其右孩子，
而 *child可能是 *p的左孩子或右孩子，故共有 4种状态。
注意武汉理工大学华夏学院 -信息工程系
③ 二叉排序树删除算法上述三种情况都能统一到情况 (2)，算法中只需针对情况
(2)处理即可。
注意边界条件：若 parent为空，被删结点 *p 是根，
故删去 *p后，应将 child置为根。
(3)*p有两个孩子先令 q=p,将被删结点的地址保存在 q中；然后找 *q
的中序后继 *p,并在查找过程中仍用 parent记住 *p 的双亲位置。 *q的中序后继 *p一定是 *q 的右子树中最左下的结点，它无左子树。因此，可以将删去 *q 的操作转换为删去的 *p的操作，即在释放结点 *p 之前将其数据复制到
*q中，就相当于删去了 *q。
分析武汉理工大学华夏学院 -信息工程系
void DelBSTNode(BSTree *Tptr,KeyType key)
{//在二叉排序树 *Tptr中删去关键字为 key的结点
BSTNode *parent=NUll,*p=*Tptr,*q，
*child；
while(p){ //从根开始查找关键字为 key的待删结点
if(p->key==key) break； //已找到，跳出查找循环
parent=p； //parent指向 *p的双亲
p=(key<p->key)?p->lchild,p->rchild；
//在关 p的左或右子树中继续找
}
if(!p) return； //找不到被删结点则返回
q=p； //q记住被删结点 *p
算法：
武汉理工大学华夏学院 -信息工程系
if(q->lchild&&q->rchild)
//*q的两个孩子均非空，故找 *q的中序后继 *p
for(parent=q,p=q->rchild； p->lchild；
parent=p,p=p=->lchild)；
//现在情况 (3)已被转换为情况 (2)，而情况 (1)相当于是情况 (2)中 child=NULL的状况
child=(p->lchild)?p->lchild,p->rchild；
//若是情况 (2)，则 child非空；否则 child为空
if(!parent)
//*p的双亲为空，说明 *p为根，删 *p后应修改根指针
*Tptr=child；
//若是情况 (1)，则删去 *p后，树为空；否则 child变为根武汉理工大学华夏学院 -信息工程系
else{//*p不是根,将 *p的孩子和 *p的双亲进行连接,*p从树上被摘下
if(p==parent->lchild)
//*p是双亲的左孩子
parent->lchild=child；
//*child作为 *parent的左孩子
else parent->rchild=child；
//*child作为 parent的右孩子
if(p!=q)
//是情况 (3)，需将 *p的数据复制到 *q
q->key=p->key； //若还有二叉排序树的删除运算实例具体操作如下武汉理工大学华夏学院 -信息工程系
42
3 7
5
8
删除叶结点 2
4
3 7
5
8
删除根结点 5后
3 7
4
8
删除内结点 7后
3 8
4
注意：删除某一个结点后的二叉树，必须保持其仍然是一棵二叉排序树。（不能改变该性质）
武汉理工大学华夏学院 -信息工程系
(3) 二叉排序树上的查找
①查找递归算法在二叉排序树上进行查找，和二分查找类似，也是一个逐步缩小查找范围的过程。
递归的查找算法：
BSTNode *SearchBST(BSTree T,KeyType key)
{ //在二叉排序树 T上查找关键字为 key的结点，成功时返回该结点位置，否则返回 NUll
if(T==NULL||key==T->key) //递归的终结条件
return T; //T为空,查找失败 ;否则成功,返回找到的结点位置
if(key<T->key)
return SearchBST(T->lchild,key)；
else
return SearchBST(T->rchild,key)； //继续在右子树中查找
} //SearchBST
武汉理工大学华夏学院 -信息工程系
②算法分析在二叉排序树上进行查找时，若查找成功，
则是从根结点出发走了一条从根到待查结点的路径。若查找不成功，则是从根结点出发走了一条从根到某个叶子的路径。
(1) 二叉排序树查找成功的平均查找长度在等概率假设下，二叉排序树查找成功的平均查找长度为
nASLa= ∑
picj=(1+2?2+3?4+4?3)/10=3i=1
武汉理工大学华夏学院 -信息工程系
(2)在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关二分查找法查找长度为 n的有序表，其判定树是惟一的。含有 n个结点的二叉排序树却不惟一。对于含有同样一组结点的表，由于结点插入的先后次序不同，所构成的二叉排序树的形态和深度也可能不同在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关：
武汉理工大学华夏学院 -信息工程系
① 在最坏情况下，二叉排序树是通过把一个有序表的 n 个结点依次插入而生成的，此时所得的二叉排序树蜕化为棵深度为 n的单支树,它的平均查找长度和单链表上的顺序查找相同,亦
(n+1)/2。
② 在最好情况下，二叉排序树在生成的过程中，
树的形态比较匀称，最终得到的是一棵形态与二分查找的判定树相似的二叉排序树，此时它的平均查找长度大约是 lgn。
③ 插入、删除和查找算法的时间复杂度 O(lgn)。
武汉理工大学华夏学院 -信息工程系
(3)二叉排序树和二分查找的比较就平均时间性能而言，二叉排序树上的查找和二分查找差不多。
就维护表的有序性而言，二叉排序树无须移动结点，只需修改指针即可完成插入和删除操作,且其平均的执行时间均为 O(lgn),因此更有效。二分查找所涉及的有序表是一个向量，
若有插入和删除结点的操作，则维护表的有序性所花的代价是 O(n)。 当有序表是静态查找表时，宜用向量作为其存储结构，而采用二分查找实现其查找操作；若有序表里动态查找表，
则应选择二叉排序树作为其存储结构。
武汉理工大学华夏学院 -信息工程系
(二）平衡二叉树（ AVL树）
1.定义：平衡二叉树或为空树，或为具有如下性质的二叉排序树：
a,左右子树为平衡二叉树；
b,左右子树的深度之差的绝对值小于 1；
2,结点的平衡因子：用结点的左子树的深度减右子树的深度。
显然：平衡二叉树的各结点的平衡因子只能为－ 1,0,1。例如：
a
fe
c b
g
d
－ 1
0
0 － 2
－ 1
00
非平衡二叉树 平衡二叉树
a
fe
c b
g
d
－ 1
0
0 － 1
－ 1
0
0
h
0
武汉理工大学华夏学院 -信息工程系
3.平衡二叉树的用途：提高查找速度
4.二叉排序树的平衡旋转对于构造的二叉排序树转化为平衡二叉树一般有四种情况：
A,单向右旋平衡处理（ LL型平衡旋转）
当某一个结点 A的平衡因子为 1时，其左子树插入结点后平衡因子为 2，失去平衡。此时需进行一次向右旋转（顺时针）操作。例如：
a
ab
b
ar
brbl
2
1
插入结点
0
0
arbr
bl
LL
武汉理工大学华夏学院 -信息工程系
B,单向左旋平衡处理（ RR型平衡旋转）
当某一个结点 A的平衡因子为 -1时，其右子树插入结点后平衡因子为 -2，失去平衡。
此时需进行一次向左旋转（逆时针）操作。
例如：
A
ABAL
BRBL
2
插入结点
0
0
BrAL
BR
RR-1
B
武汉理工大学华夏学院 -信息工程系
C,双向平衡处理（先左后右）
（ LR型平衡旋转）
当某一个结点 A的平衡因子为 1时，其左子树的右子树插入结点后平衡因子为 2，
失去平衡。此时需进行两次旋转（先逆时针，后顺时针）操作。例如：
a
ab
C
ar
CL
bl
2
-1
插入结点
0
0
arCrbl
LR
Cr
C
1 B
CL
武汉理工大学华夏学院 -信息工程系
D,双向平衡处理（先右后左）
（ RL型平衡旋转）
当某一个结点 A的平衡因子为 1时，其左子树的右子树插入结点后平衡因子为 2，
失去平衡。此时需进行两次旋转（先逆时针，后顺时针）操作。例如：
A
BB
C
AL
CL
BR
-2
1
插入结点
-1
-1
BRCrAL
RL
CR
C
1 A
CL
0
武汉理工大学华夏学院 -信息工程系例：设有一个序列 {13,24,37,90,53}
构造二叉平衡树。
按二叉排序树的构造方法进行空树，平衡
13
一个结点，平衡
13
两个结点，平衡
24
0 -1
0
13
三个结点，不平衡
24
-2
-1
370
24
逆时针右旋，平衡
37
0
0
13 0
24
插入 90后，平衡
37
-1
-1
13 0
90
0
武汉理工大学华夏学院 -信息工程系
24
插入 53后，不平衡
37
-2
-2
13 0
90
1
53 0
24
以 37为根，第一次顺时针旋转
3713
53
90
24
第二次逆时针旋转，平衡
37
-1
0
13 0
90
0530
武汉理工大学华夏学院 -信息工程系
7.4 散列查找技术 （ 又称哈希查找技术 ）
散列查找方法不同于顺序查找、二分查找、二叉排序树及 B-树上的查找。它不以关键字的比较为基本操作，采用直接寻址技术。在理想情况下，无须任何比较就可以找到待查关键字，查找的期望时间为 O(1)。
（一）散列表的概念
1、散列表设所有可能出现的关键字集合记为 U(简称全集 )。实际发生 (即实际存储 )的关键字集合记为 K(|K|比 |U|小得多 )。
散列方法是使用函数 h将 U映射到表 T [0..m-1] 的下标上
（ m=O(|U|)）。 这样以 U中关键字为自变量，以 h为函数的运算结果就是相应结点的存储地址。从而达到在 O (1)
时间内就可完成查找。
武汉理工大学华夏学院 -信息工程系
① h,U→{0,1,2,…,m-1},通常称 h
为散列函数 (Hash Function)。 散列函数 h的作用是压缩待处理的下标范围,使待处理的 |U|
个值减少到 m个值，从而降低空间开销。
② T为散列表 (Hash Table)。
③ h(Ki)(Ki∈ U)是关键字为 Ki结点存储地址 (亦称散列值或散列地址 )。
④ 将结点按其关键字的散列地址存储到散列表中的过程称为散列 (Hashing)
其中：
武汉理工大学华夏学院 -信息工程系
2 建散列表的方法举例设 B是一个有 15个元素的线性表，其中各值为
B=(12,33,65,9,38,71,82,63,75,15,24,57,54,88,98)
要把这 15个元素存放到有 20个存储单元的存储区内，步骤为：
（ 1) 选取 h(k)=int(k/5) （ k除 5取整）
（ 2) 根据结点的值，计算出该结点的存储地址即 loc(k)=h(k)
（ 3) 将 k存入 s[loc(k)]中。即有地址 1 2 3 4 5 6 7 8 9 1011 1213141516171819
结点值 9 121524 3338 5457636571758288 98
0
武汉理工大学华夏学院 -信息工程系
3、散列表的冲突现象
（ 1）冲突两个不同的关键字，由于散列函数值相同,因而被映射到同一表位置上。该现象称为冲突 (Collision)或碰撞。发生冲突的两个关键字称为该散列函数的同义词 (Synonym)。
【 例】上图中,增加一个结点值 37,则 h(37)=h(38 ),故上述两个 结点的存储地址相同。即产生了冲突。
（ 2）安全避免冲突的条件最理想的解决冲突的方法是安全避免冲突。要做到这一点必须满足两个条件：
① 其一是 |U|≤m
② 其二是选择合适的散列函数。
这只适用于 |U|较小,且关键字均事先已知的情况,此时经过精心设计散列函数 h有可能完全避免冲突。
武汉理工大学华夏学院 -信息工程系
（ 3）冲突不可能完全避免通常情况下,h是一个压缩映像,虽然 |K|≤m,但
|U| >m,故无论怎样设计 h,也不可能完全避免冲突。因此只能在设计 h时尽可能使冲突最少。
同时还需要确定解决冲突的方法，使发生冲突的同义词能够存储到表中。
（ 4）影响冲突的因素冲突的频繁程度除了与 h相关外，还与表的填满程度相关。
设 m 和 n 分别表示表长和表中填人的结点数,则将 a=n/m定义为散列表的装填因子 (Load Factor )。
α越大,表越满,冲突的机会也越大,通常取 α≤1。
武汉理工大学华夏学院 -信息工程系
（二） 散列函数的构造方法
1、散列函数的选择有两条标准,简单和均匀。
简单指散列函数的计算简单快速；
均匀指对于关键字集合中的任一关键字，散列函数能以等概率将其映射到表空间的任何一个位置上。也就是说，散列函数能将子集 K随机均匀地分布在表的地址集 {0,1,…,m-1}上，以使冲突最小化。
2、常用散列函数为简单起见，假定关键字是定义在自然数集合上。
（ 1）平方取中法具体方法：先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值。
又因为一个乘积的中间几位数和乘数的每一位都相关，
所以由此产生的散列地址较为均匀。
武汉理工大学华夏学院 -信息工程系
【例】 将一组关键 (0100,0110,1010,1001,0111)
平方后得 (0010000,0012100,1020100,1002001,0012321)
若取表长为 1000，则可取中间的三位数作为散列地址集,(100,121,201,020,123)。
相应的散列函数用 C实现很简单：
int Hash(int key)
{ //假设 key是 4位整数
key*=key；
key/=100； //先求平方值，后去掉末尾的两位数
return key％ 1000; //取中间三位数作为散列地址返回
}
武汉理工大学华夏学院 -信息工程系
（ 2）除余法该方法是最为简单常用的一种方法。它是以表长 m来除关键字，取其余数作为散列地址，即
h(key)=key％ m
该方法的关键是选取 m。 选取的 m 应使得散列函数值尽可能与关键字的各位相关。 m最好为素数。
【例 若选 m是关键字的基数的幂次,则就等于是选择关键字的最后若干位数字作为地址，而与高位无关。于是高位不同而低位相同的关键字均互为同义词。
【例】 若关键字是十进制整数，其基为 10 则当
m=100时,159,259,359,…,等均互为同义词。
武汉理工大学华夏学院 -信息工程系
（ 3）相乘取整法该方法包括两个步骤：首先用关键字 key乘上某个常数 A(0<A<1),并抽取出 key.A的小数部分；然后用 m乘以该小数后取整。即：
h(key)=[m(key.A-key.A)]
该方法最大的优点是选取 m不再像除余法那样关键。比如，完全可选择它是 2的整数次幂。虽然该方法对任何 A
的值都适用，但对某些值效果会更好。 Knuth建议选取
int Hash(int key){
double d=key *A； //不妨设 A和 m已有定义
return (int)(m*(d-(int)d))；
//(int)表示强制转换后面的表达式为整数 }
A ≈ (5-1)/2=0.61803398 87…
该函数的 C代码为：
武汉理工大学华夏学院 -信息工程系
（ 4）随机数法选择一个随机函数，取关键字的随机函数值为它的散列地址，即,h(key)=random(key)
其中 random为伪随机函数，但要保证函数值是在 0到 m-1之间。
（三）处理冲突的方法通常有两类方法处理冲突：开放定址 (Open
Addressing)法和拉链 (Chaining)法。前者是将所有结点均存放在散列表 T[0..m-1]中；后者通常是将互为同义词的结点链成一个单链表，而将此链表的头指针放在散列表 T[0..m-1]中。
武汉理工大学华夏学院 -信息工程系
1、开放定址法
（ 1）开放地址法解决冲突的方法用开放定址法解决冲突的做法是：当冲突发生时，
使用某种探查 (亦称探测 )技术在散列表中形成一个探查
(测 )序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址 (即该地址单元为空 )
为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探查到开放的地址则表明表中无待查的关键字，即查找失败。
注意：
① 用开放定址法建立散列表时，建表前须将表中所有单元 (更严格地说，是指单元中存储的关键字 )置空。
② 空单元的表示与具体的应用相关。
武汉理工大学华夏学院 -信息工程系
【例】 关键字均为非负数时，可用,-1” 来表示空单元，
而关键字为字符串时，空单元应是空串。
（ 2）开放地址法的一般形式开放定址法的一般形式为,hi=(h(key)+di)％ m
1≤i≤m-1
其中：
① h(key)为散列函数,di为增量序列,m为表长。
② h(key)是初始的探查位置，后续的探查位置依次是 hl，
h2,…,hm-1,即 h(key),hl,h2,…,hm-1形成了一个探查序列。
③ 若令开放地址一般形式的 i从 0开始，并令 d0=0,则
h0=h(key),则有：
hi=(h(key)+di)％ m 0≤i≤m-1
探查序列可简记为 hi(0≤i≤m-1)。
总之：应该用一个不会出现的关键字来表示空单元。
武汉理工大学华夏学院 -信息工程系
（ 3）开放地址法堆装填因子的要求开放定址法要求散列表的装填因子 α≤l,实用中取 α为 0.5到 0.9之间的某个值为宜。
（ 4）形成探测序列的方法按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、二次探查法、双重散列法等。
武汉理工大学华夏学院 -信息工程系
① 线性探查法 (Linear Probing)
该方法的基本思想是：
将散列表 T[0..m-1]看成是一个循环向量，若初始探查的地址为 d(即 h(key)=d),则最长的探查序列为：
d,d+l,d+2,…,m-1,0,1,…,d-1
即,探查时从地址 d开始，首先探查 T[d],然后依次探查 T[d+1],…,直到 T[m-1],此后又循环到 T[0]，
T[1],…,直到探查到 T[d-1]为止。
探查过程终止于三种情况：
(1)若当前探查的单元为空，则表示查找失败（若是插入则将 key写入其中）；
(2)若当前探查的单元中含有 key,则查找成功，但对于插入意味着失败；
(3)若探查到 T[d-1]时仍未发现空单元也未找到 key,则无论是查找还是插入均意味着失败 (此时表满 )。
武汉理工大学华夏学院 -信息工程系利用开放地址法的一般形式，线性探查法的探查序列为：
hi=(h(key)+i)％ m 0≤i≤m -1 //即 di=i利用线性探测法构造散
【例 7.1】 已知一组关键字为 ( 26,36,41,38,44,15,
68,12,06,51),用除余法构造散列函数，用线性探查法解决冲突构造这组关键字的散列表。
解答,为了减少冲突，通常令装填因子 α<l。 这里关键字个数 n=10,不妨取 m=13,此时 α≈0.77,散列表为 T[0..12],散列函数为,h(key)=key％ 13。
由除余法的散列函数计算出的上述关键字序列的散列地址为 (0,10,2,12,5,2,3,12,6,12)。
武汉理工大学华夏学院 -信息工程系前 5个关键字插入时，其相应的地址均为开放地址，
故将它们直接插入 T[0],T[10),T[2],T[12]和 T[5]中。
当插入第 6个关键字 15时，其散列地址 2( 即 h(15)=15
％ 13=2)已被关键字 41( 15和 41互为同义词 )占用。故探查
h1=(2+1)％ 13=3,此地址开放，所以将 15放入 T[3]中。
当插入第 7个关键字 68时,其散列地址 3已被非同义词
15先占用，故将其插入到 T[4]中。
当插入第 8个关键字 12 时,散列地址 12已被同义词 38
占用，故探查 hl=(12+1)％ 13=0,而 T[0]亦被 26占用，再探查 h2=(12+2)％ 13=1,此地址开放，可将 12插入其中。
类似地，第 9个关键字 06直接插入 T[6]中；而最后一个关键字 51插人时,因探查的地址 12,0,1,…,6均非空，
故 51插入 T[7]中。
武汉理工大学华夏学院 -信息工程系聚集或堆积现象用线性探查法解决冲突时，当表中 i,i+1,…,
i+k 的位置上已有结点时，一个散列地址为 I,
i +1,…,i+k+1的结点都将插入在位置 i+k+1
上。把这种散列地址不同的结点争夺同一个后继散列地址的现象称为聚集或堆积 (Clustering)。
这将造成不是同义词的结点也处在同一个探查序列之中，从而增加了探查序列的长度，即增加了查找时间。若散列函数不好或装填因子过大，都会使堆积现象加剧。
武汉理工大学华夏学院 -信息工程系
【例】 上例中,h (15)=2,h (68)=3,即 15和 68
不是同义词。但由于处理 15和同义词 41的冲突时,15抢先占用了 T[ 3 ],这就使得插入 68时，
这两个本来不应该发生冲突的非同义词之间也会发生冲突。
为了减少堆积的发生，不能像线性探查法那样探查一个顺序的地址序列 ( 相当于顺序查找 )，而应使探查序列跳跃式地散列在整个散列表中。
武汉理工大学华夏学院 -信息工程系
（ 2)二次探查法 (Quadratic Probing)
二次探查法的探查序列是：
hi=(h(key)+i*i)％ m 0≤i≤m-1 //即 di=i2
即探查序列为 d=h(key),d+12,d+22,…,等。
该方法的缺陷是不易探查到整个散列空间。
（ 3)双重散列法 (Double Hashing)
该方法是开放定址法中最好的方法之一，它的探查序列是：
hi=(h(key)+i*h1(key))％ m 0≤i≤m-1 //即 di=i*h1(key)
即探查序列为：
d=h(key),(d+h1(key))％ m,(d+2h1(key))％ m,…,
等。该方法使用了两个散列函数 h(key)和 h1(key)，
故也称为双散列函数探查法。
武汉理工大学华夏学院 -信息工程系注意：
定义 h1(key)的方法较多，但无论采用什么方法定义，都必须使 h1(key)的值和 m互素，才能使发生冲突的同义词地址均匀地分布在整个表中，
否则可能造成同义词地址的循环计算。
【例】 若 m为素数，则 h1 (key)取 1到 m-1之间的任何数均与 m互素，因此，我们可以简单地将它定义为,h1(key)=key％ (m-2)+1
【 例】 对例 7.1，我们可取 h(key)=key％ 13,而
h1(key)=key％ 11+1。
【 例】 若 m是 2的方幂，则 h1( key)可取 1到 m-1之间的任何奇数。
武汉理工大学华夏学院 -信息工程系
（ 4)伪随机探查法将 二次探查法的探查函数 d(i) 设计为一个随机函数，如 d(i)＝（ d+p) MOD m
其中 m为表长,d为产生冲突的地址,p为质数
（是一个不大于 m的最大质数）。
例如,在一个表长为 11的散列表中，存放值为
｛ 29,17,60,38}的记录，其哈希函数为
h(key)=key MOD 11
则有 h(29)=7;h(17)=6;h(60)=5；
h(38)=5 此时与 60产生了冲突哈希表为：
60 17 29
0 1 2 3 4 5 6 7 8 9 10
武汉理工大学华夏学院 -信息工程系
（ 1)用 线性探查法 处理冲突，散列地址 =8
60 17 29 38
0 1 2 3 4 5 6 7 8 9 10
（ 2)用 二次探查法 处理冲突，散列地址 =4
此时取 d(i)=-12
地址＝ h(key)+（ -12 ） MOD m＝ 4
6038 17 29
0 1 2 3 4 5 6 7 8 9 10
（ 3)用 伪随机探查法 处理冲突，散列地址 =3
此时取 d(i)=（ h(38)+p） MOD m
h(38)=5 ; p=9 ; m=11；
6038 17 29
0 1 2 3 4 5 6 7 8 9 10
武汉理工大学华夏学院 -信息工程系
2、拉链法
（ 1）拉链法解决冲突的方法拉链法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为 m,则可将散列表定义为一个由 m
个头指针组成的指针数组 T[0..m-1]。 凡是散列地址为 i的结点，均插入到以 T[i]为头指针的单链表中。 T中各分量的初值均应为空指针。在拉链法中，装填因子 α可以大于 1，但一般均取 α≤1。
武汉理工大学华夏学院 -信息工程系
【 例 7.2】已知一组关键字和选定的散列函数和例 7.1相同，用拉链法解决冲突构造这组关键字的散列表。
解答：不妨和例 7.1类似，取表长为 13，故散列函数为 h(key)=key％ 13,散列表为 T[0..12]。
武汉理工大学华夏学院 -信息工程系
(2)拉链法的优点与开放定址法相比，拉链法有如下几个优点：
(1)拉链法处理冲突简单，且无堆积现象,即非同义词决不会发生冲突，因此平均查找长度较短；
(2)由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
(3)开放定址法为减少冲突,要求装填因子 α 较小，故当结点规模较大时会浪费很多空间。而拉链法中可取 α ≥ 1,且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
武汉理工大学华夏学院 -信息工程系
(4)在用拉链法构造的散列表中,删除结点的操作易于实现 。 只要简单地删去链表上相应的结点即可 。 而对开放地址法构造的散列表,删除结点不能简单地将被删结点的空间置为空,否则将截断在它之后填人散列表的同义词结点的查找路径 。 这是因为各种开放地址法中,空地址单元 (即开放地址 )都是查找失败的条件 。 因此在用开放地址法处理冲突的散列表上执行删除操作,只能在被删结点上做删除标记,而不能真正删除结点 。
（ 3） 拉链法的缺点拉链法的缺点是：指针需要额外的空间,故当结点规模较小时,开放定址法较为节省空间,而若将节省的指针空间用来扩大散列表的规模,可使装填因子变小,这又减少了开放定址法中的冲突,从而提高平均查找速度 。
武汉理工大学华夏学院 -信息工程系
（四）散列表上的运算散列表上的运算有查找、插入和删除。其中主要是查找，这是因为散列表的目的主要是用于快速查找，且插入和删除均要用到查找操作。
1、散列表类型说明：
#define NIL -1 //空结点标记依赖于关键字类型,
本节假定关键字均为非负整数
#define M 997 //表长度依赖于应用，但一般应根据。确定 m为一素数
typedef struct{ //散列表结点类型
KeyType key；
InfoType otherinfo； //此类依赖于应用
}NodeType；
typedef NodeType HashTable[m]； //散列表类型
武汉理工大学华夏学院 -信息工程系
2、基于开放地址法的查找算法散列表的查找过程和建表过程相似。假设给定的值为 K,根据建表时设定的散列函数 h，
计算出散列地址 h(K),若表中该地址单元为空，
则查找失败；否则将该地址中的结点与给定值
K比较。若相等则查找成功,否则按建表时设定的处理冲突的方法找下一个地址。如此反复下去，直到某个地址单元为空 ( 查找失败 )或者关键字比较相等 (查找成功 )为止。
武汉理工大学华夏学院 -信息工程系
(1)开放地址法一般形式的函数表示
int Hash(KeyType k,int i)
{ //求在散列表 T[0..m-1]中第 i次探查的散列地址 hi,0≤i≤m -1
//下面的 h是散列函数。 Increment是求增量序列的函数，它依赖于解决冲突的方法
return(h(K)+Increment(i))％ m； //Increment(i)相当于是 di
}
若散列函数用除余法构造，并假设使用线性探查的开放定址法处理冲突，则上述函数中的 h(K)和
Increment(i)可定义为：
int h(KeyType K){ //用除余法求 K的散列地址
return K％ m；
}
int Increment(int i)
{//用线性探查法求第 i个增量 di
return i; //若用二次探查法，则返回 i*i
}
武汉理工大学华夏学院 -信息工程系
（ 2）通用的开放定址法的散列表查找算法：
int HashSearch(HashTable T,KeyType K,int *pos)
{ //在散列表 T[0..m-1]中查找 K,成功时返回 1。失败有两种情况：找到一个开放地址
//时返回 0，表满未找到时返回 -1。 *pos记录找到 K或找到空结点时表中的位置
int i=0； //记录探查次数
do{
*pos=Hash(K,i)； //求探查地址 hi
if(T[*pos].key==K) return l； //查找成功返回
if(T[*pos].key==NIL) return 0； //查找到空结点返回
}while(++i<m) //最多做 m次探查
return -1； //表满且未找到时，查找失败
} //HashSearch?
武汉理工大学华夏学院 -信息工程系注意,上述算法适用于任何开放定址法，只要给出函数 Hash 中的散列函数 h ( K ) 和增量函数
Increment( I )即可。但要提高查找效率时，可将确定的散列函数和求增量的方法直接写入算法 HashSearch中，相应的算法 【参见习题】 。
3、基于开放地址法的插入及建表建表时首先要将表中各结点的关键字清空，
使其地址为开放的；然后调用插入算法将给定的关键字序列依次插入表中。
插入算法首先调用查找算法，若在表中找到待插入的关键字或表已满，则插入失败；若在表中找到一个开放地址，则将待插入的结点插入其中，即插入成功。
武汉理工大学华夏学院 -信息工程系
void Hashlnsert(HashTable T,NodeTypene w)
{ //将新结点 new插入散列表 T[0..m-1]中
int pos,sign；
sign=HashSearch(T,new.key,&pos)；
//在表 T中查找 new的插入位置
if(!sign) //找到一个开放的地址 pos
T[pos]=new； //插入新结点 new,插入成功
else //插人失败
if(sign>0)
printf(“duplicate key!”)； //重复的关键字
else //sign<0
Error(“hashtableoverflow!”)； //表满错误,终止程序执行
} //Hashlnsert
武汉理工大学华夏学院 -信息工程系
void CreateHashTable(HashTable T,NodeType A[]，
int n)
{ //根据 A[0..n-1]中结点建立散列表 T[0..m-1]
int i
if(n>m) //用开放定址法处理冲突时，装填因子 α须不大于 1
Error("Load factor>1")；
for(i=0;i<m； i++)
T[i].key=NIL； //将各关键字清空，使地址 i为开放地址
for(i=0;i<n； i++) //依次将 A[0..n-1]插入到散列表 T[0..m-1]中
Hashlnsert(T,A[i])；
} //CreateHashTable
武汉理工大学华夏学院 -信息工程系
4、删除基于开放定址法的散列表不宜执行散列表的删除操作。若必须在散列表中删除结点，则不能将被删结点的关键字置为 N I L,而应该将其置为特定的标记
DELETED。
因此须对查找操作做相应的修改，使之探查到此标记时继续探查下去。同时也要修改插人操作，使其探查到 DELETED 标记时，将相应的表单元视为一个空单元，将新结点插入其中。这样做无疑增加了时间开销，并且查找时间不再依赖于装填因子。
因此，当必须对散列表做删除结点的操作时，一般是用拉链法来解决冲突。
注意：
用拉链法处理冲突时的有关散列表上的算法 【参见练习】 。
武汉理工大学华夏学院 -信息工程系
5、性能分析插入和删除的时间均取决于查找，故下面只分析查找操作的时间性能。
虽然散列表在关键字和存储位置之间建立了对应关系，理想情况是无须关键字的比较就可找到待查关键字。但是由于冲突的存在，散列表的查找过程仍是一个和关键字比较的过程，
不过散列表的平均查找长度比顺序查找、二分查找等完全依赖于关键字比较的查找要小得多。
武汉理工大学华夏学院 -信息工程系
（ 1）查找成功的 ASL
散列表上的查找优于顺序查找和二分查找。
【例】在例 9.1 和例 9.2 的散列表中，在结点的查找概率相等的假设下，线性探查法和拉链法查找成功的平均查找长度分别为：
ASL=(1× 6+2× 2+3× l+9× 1)/10=2.2 //线性探查法
ASL=(1× 7+2× 2+3× 1)/10=1.4 //拉链法而当 n = 10 时，顺序查找和二分查找的平均查找长度 (成功时 )分别为：
ASL=(10+1)/2=5.5 //顺序查找
ASL=(1× l+2× 2+3× 4+4× 3)/10=2.9
//二分查找，可由判定树求出该值武汉理工大学华夏学院 -信息工程系
(2)查找不成功的 ASL
对于不成功的查找，顺序查找和二分查找所需进行的关键字比较次数仅取决于表长，而散列查找所需进行的关键字比较次数和待查结点有关。因此，在等概率情况下，也可将散列表在查找不成功时的平均查找长度，
定义为查找不成功时对关键字需要执行的平均比较次数
【例】 例 7.1和例 7.2的散列表中，在等概率情况下，查找不成功时的线性探查法和拉链法的平均查找长度分别为：
ASLunsucc=(1+0+2+1+0+1+1+0+0+0+1+0+3)/13≈10/13≈0.77
ASLunsucc=(9+8+7+6+5+4+3+2+1+1+2+1+10)/13=59/13≈4.54
武汉理工大学华夏学院 -信息工程系注意：
①由同一个散列函数、不同的解决冲突方法构造的散列表，其平均查找长度是不相同的。
②散列表的平均查找长度不是结点个数 n的函数，
而是装填因子 α 的函数。因此在设计散列表时可选择 α 以控制散列表的平均查找长度。
③ α 的取值
α 越小，产生冲突的机会就小，但 α 过小,
空间的浪费就过多。只要 α 选择合适，散列表上的平均查找长度就是一个常数，即散列表上查找的平均时间为 O(1)。
直接求出地址的查找方法,其查找的期望时间为 O(1)。
武汉理工大学华夏学院 -信息工程系
④ 散列法与其他查找方法的区别,
除散列法外，其他查找方法有共同特征为：均是建立在比较关键字的基础上。其中顺序查找是对无序集合的查找，每次关键字的比较结果为,=” 或,!=” 两种可能，其平均时间为
O(n)； 其余的查找均是对有序集合的查找，每次关键字的比较有,=”,,<” 和,>” 三种可能，且每次比较后均能缩小下次的查找范围，
故查找速度更快，其平均时间为 O(lgn)。 而散列法是根据关键字直接求地址的查找方法，其期望的时间为 O(1)。
武汉理工大学华夏学院 -信息工程系例：使用的哈希函数为：
H(Ki)=3Ki mod 11并采用开放地址法（伪随机探测）处理冲突,其求下一个地址的函数为：
di=H(ki)
Di=(di-1+(7ki mod 10)+1)mod11 (i=2,3…)
试在 0~10的散列地址空间中对关键字序列（ 22,41,53，
46,30,13,01,67）构造哈希表，求等概率情况下查找成功的平均查找长度，并设计构造哈希表的完整函数。
本题的哈希表构造过程如下：
（ 1） H(22)=3*33 mod 11=0
（ 2） H(41)=3*41 mod 11=2
武汉理工大学华夏学院 -信息工程系
（ 3） H(53)=3*53 mod 11=5
（ 4） H(46)=3*46 mod 11=6
（ 5） H(30)=3*30 mod 11=2 (冲突 )
d1=H(30)=2
H(30)=(2+(7*30 mod 10) +1 ） mod 11=3
（ 6） H(13)=3*13 mod 11=6 (冲突 )
d1=H(13)=6
H(13)=(6+(7*13 mod 10) +1） mod 11=8
（ 7） H(1)=3*1 mod 11=3 (冲突 )
d1=H(1)=3
H(1)=(3+(1*7 mod 10) +1） mod 11=0 (冲突 )
武汉理工大学华夏学院 -信息工程系
d2=H(1)=0
H(1)=(0+(1*7 mod 10) +1） mod 11=8 (冲突 )
d3=H(1)=8
H(1)=(8+(1*7 mod 10) +1 )mod 11=5 (冲突 )
d4=H(1)=5
H(1)=(5+(1*7 mod 10) +1 )mod 11=2 (冲突 )
d5=H(1)=2
H(1)=(2+(1*7 mod 10) +1) mod 11=10 (冲突 )
（ 8） H(67)=3*67 mod 11=3 (冲突 )
d1=H(67)=3
H(67)=(3+(7*67 mod 10) +1 )mod 11=2 (冲突 )
d2=H(67)=2
H(67)=(2+(7*67 mod 10) +1) mod 11=1 (冲突 )
武汉理工大学华夏学院 -信息工程系查找的成功的平均查找长度为：
ASL=（ 1?4+2?2+3?1+6?1）?（ 1/8） =2.125
构造哈希表的程序如下：
#include<stdio.h>
#define M 11
#define N 8
{
int key; /*关键字值 */
int si;
};
struct hterm hashlist[M+1];
int I,address,sum,d,x[N+1];
float average;
武汉理工大学华夏学院 -信息工程系
main()
{
for (i=1;i<=M;i++) /*置初值 */
{
hashlist[I].key=0;
hashlist[I].si=0;
}
x[1]=22; x[2]=41; x[3]=53;
x[4]=46; x[5]=30; x[6]=13;
x[7]=1; x[8]=6;
for (i=1;i<=N;i++)
{
sum=0;
address=(3*x[I])%M;
武汉理工大学华夏学院 -信息工程系
d=address;
if (hashlist[address].key==0)
{
hashlist[address].key=x[i];
hashlist[address].si=1;
}
else
{
do /*处理冲突 */
{
d=(d+(x[i]*7) %10+1) %11;
sum=sum+1;
} while (hashlist[d].key!=0);
武汉理工大学华夏学院 -信息工程系
hashlist[d].key=x[i];
hashlist[d].si=1;
} }
printf(“哈希表地址：,)
for (i-0; i<M; i++) printf(“% -4d”,i);
printf(“\”);
printf(“哈希表关键字：” );
for (i=0;i<M;i++) printf(“% -4d”,hashlist[i].key);
printf(“\”);
printf(“搜索长度：,);
for (i=0; i<M; i++) average=average+hashlist[i].si;
average=average/N;
printf(“平均搜索长途,ASL（ %d)=%g”,N,average);
}
武汉理工大学华夏学院 -信息工程系
7.5 查找操作应用举例例 1 （ p249） 例 7.1 画出对长度为 10的有序表进行折半查找的判定树，并求等概率时的平均查找长度。
方法：利用折半查找，将表中的每个结点放在放在二叉排序树的相应位置。
第一次找中点是 m＝ 5 则 d[5]为树根；（第一层）
第二次找中点是左部 m＝ 2 则 d[2]为左子树树根、
右部 m＝ 8 则 d[8]为右子树树根（第二层）
第三次找中点可能有 d[1],d[3],d[6],d[9]
最后为第四层的结点。
构成的判定树为：
武汉理工大学华夏学院 -信息工程系
50
10 30
40 70
60
80
90
100
20
其平均查找长度为：
ASL＝（ 1+2+2+3*4+4*3)/10=29/10=2.9
其余例题见 p250页武汉理工大学华夏学院 -信息工程系小结：
1.查找方法有四种：顺序、索引、树型、散列
2,顺序查找方法简单，对待查序列无要求，但速度慢，
时间复杂度为 o(n)；
3.折半查找是一种常用的方法，速度快
时间复杂度为 o(log2n),但对待查序列要求高；
4,二叉排序树的查找取决于树的高度；
5.哈希查找方法的速度取决于冲突解决的策略，
作业：
P253
7.2,7.3,7.5,7.8,7.11,7.14
武汉理工大学华夏学院 -信息工程系
7.1 查找的基本概念
1,查找表和查找结果一般，假定被查找的对象是由一组结点组成的表 ( Table)或文件，而每个结点则由若干个数据项组成。并假设每个结点都有一个能惟一标识该结点的关键字。
查找 (Searching)的定义是：给定一个值 K,在含有 n个结点的表中找出关键字等于给定值,K
的结点。若找到，则查找成功,返回该结点的信息或该结点在表中的位置 ;否则查找失败，
返回相关的指示信息。
搜索关键字武汉理工大学华夏学院 -信息工程系
（ 1）动态查找和静态查找若在查找的同时对相应的数据结构做修改操作 (如插入和删除 ),则称之为动态查找。否则称之为静态查找 。
2,查找方法分类
（ 2）内查找和外查找查找还有内查找和外查找之分的分类方法。
若整个查找过程都在内存中进行，则称之为内查找；反之，若查找过程中需要访问外存，则称之为外查找。
武汉理工大学华夏学院 -信息工程系
3,平均查找长度 ASL
查找运算的主要操作是关键字的比较，所以通常把查找过程中对关键字需要执行的 平均比较次数 (也称为平均查找长度 )作为衡量一个查找算法效率优劣的标准。
平均查找长度 ASL(Average Search Length)定义为：
ASL=∑P i*Ci (1<=i<=n)其中：
① n是结点的个数；
② Pi是查找第 i个结点的概率。若不特别声明，认 为每个结点的查找概率相等，即 pl=p2…=p n=1/n;
③ ci是找到第 i个结点所需进行的比较次数。
武汉理工大学华夏学院 -信息工程系
7.2 静态查找在表的组织方式中，线性表是最简单的一种。
顺序查找是一种最简单的查找方法。
基本思想是：从表的一端开始,顺序扫描线性表，依次将扫描到的结点关键宇和给定值 K相比较。若当前扫描到的结点关键字与 K相等，则查找成功 ;若扫描结束后,仍未找到关键字等于 K
的结点，则查找失败。
（一）顺序查找 (Sequential Search)
1,顺序查找的基本思想武汉理工大学华夏学院 -信息工程系
2,顺序查找的存储结构要求顺序查找方法既适用于线性表的顺序存储结构也适用于线性表的链式存储结构（使用单链表作存储结构时，扫描必须从第一个结点开始）。
（ 1）类型说明
typedef struct{
KeyType key；
InfoType otherinfo； //此类型依赖于应用
}NodeType；
typedef NodeType SeqList[n+1]； //0号单元用作哨兵
3,基于顺序结构的顺序查找算法武汉理工大学华夏学院 -信息工程系
（ 2）具体算法
int SeqSearch(Seqlist R,KeyType K)
{ //在顺序表 R[1..n]中顺序查找关键字为 K的结点,
//成功时返回找到的结点位置，失败时返回 0
int i；
R[0].key=K； //设置哨兵
for(i=n； R[i].key!=K;i--)； //从表后往前找
return i； //若 i为 0，表示查找失败,否则 R[i]是要找的结点
} //SeqSearch
武汉理工大学华夏学院 -信息工程系
（ 3）算法分析为了在 for循环中省去判定防止下标越界的条件 i≥1,从而节省比较的时间。
②成功时的顺序查找的平均查找长度：
在等概率情况下,pi=1/n(1≤i≤n),故成功的平均查找长度为,(n+…+2+1)/n=(n+1)/2 即查找成功时的平均比较次数约为表长的一半。若 k 值不在表中,则须进行 n+1
次比较之后才能确定查找失败。
① 算法中监视哨 R[0]的作用武汉理工大学华夏学院 -信息工程系
③ 链表结构的顺序查找算法设被查数据是一个单链表，其数据类型描述为：
Struct LNode
｛ elemtype data;
struct LNode * next；
｝
struct lnode *P,*head；
elemtype data V；
/* 要查找的数据用 V表示 */
则查找的第一个元素从头开始，最后一个元素应为指针场为空的结点（结束条件）,
算法描述如下：
武汉理工大学华夏学院 -信息工程系
P=*head
否否
p＝ P->next
显示查找不成功显示查找结果结束输入待查值 V
P=空
P－ >data＝ V
武汉理工大学华夏学院 -信息工程系
（ 4) 若事先知道表中各结点的查找概率不相等和它们的分布情况，则应将表中结点按查找概率由小到大地存放，以便提高顺序查找的效率。为了提高查找效率，对算法 SeqSearch做如下修改：每当查找成功，就将找到的结点和其后继 (若存在 )结点交换。这样,使得查找概率大的结点在查找过程中不断往后移，便于在以后的查找中减少比较次数。
武汉理工大学华夏学院 -信息工程系
④顺序查找的优点
⑤顺序查找的缺点查找效率低,因此,当 n较大时不宜采用顺序查找。
算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。
武汉理工大学华夏学院 -信息工程系
（二） 折半（二分）查找
1、二分查找 (Binary Search)
二分查找又称折半查找，它是一种效率较高的查找方法。
二分查找要求：线性表是有序的，即表中结点按关键字从小到大（或从大到小），并且要用向量作为表的存储结构（即用顺序存储方法进行存储）。不妨设有序表是递增有序的。
2、二分查找的基本思想二分查找的基本思想是,（设 R[low..high]
是当前的查找区间）
武汉理工大学华夏学院 -信息工程系
(1)首先确定该区间的中点位置：
mid＝（ low＋ high） /2
其中：
low为左界结点下标,high为右 界结点下标。
(2)然后将待查的 K值与 R[mid].key比较：
若相等,则查找成功并返回此位置,否则须确定新的查找区间,继续二分查找,具体方法如下：
① 若 R[mid].key>K,则由表的有序性可知
R[mid..n].keys均大于 K,因此若表中存在关键字等于 K的结点，则该结点必定是在位置 mid
左边的子表 R[low..mid-1]中，故新的查找区间是左子表 R[low..mid-1]。
武汉理工大学华夏学院 -信息工程系
② 类似地，若 R[mid].key <K,则要查找的 K必在
mid的右子表 R[mid+1..high]中,即新的查找区间是右子表 R[mid+1..high],下一次查找是针对新的查找区间进行的。
因此，从初始的查找区间 R[1..n]开始,,此时 low＝ 1,high＝ n。每经过一次与当前查找区间的中点位置上的结点关键字的比较,就可确定查找是否成功,不成功则当前的查找区间就缩小一半,这一过程重复直至找到关键字为 K的结点,或者直至当前的查找区间为空 (即查找失败 )时为止。
武汉理工大学华夏学院 -信息工程系例如：在关键字有序序列
〔 2,4,7,9,10,14,18,26,32,40〕 中采用二分查找法查找 V=7的元素。查找过程如下开始：
2 4 7 9 10 14 18 26 32 40
Low＝ 1 high＝ 10?
武汉理工大学华夏学院 -信息工程系第一次比较,mid＝（ 1+10)/2取整）＝ 5
2 4 7 9 10 14 18 26 32 40
Low＝ 1 mid＝ 5high＝ 4 注：右端点左移第二次比较,mid＝（ 1+4)/2取整）＝ 2
2 4 7 9 10 14 18 26 32 40
mid＝ 3
Low＝ 3
Low＝ 1
Mid＝ 2
第三次比较,mid＝（ 2+4)/2取整）＝ 3
2 4 7 9 10 14 18 26 32 40
注：左端点右移查找完成high＝ 4
high＝ 4
武汉理工大学华夏学院 -信息工程系
int BinSearch(SeqList R,KeyType K)
{//在有序表 R[1..n]中进行二分查找，成功时返回结点的位置，失败时返回零
int low=1,high=n,mid； //置当前查找区间上、下界 的 初值
while(low<=high){ //当前查找区间 R[low..high]非空
mid=(low+high)/2；
if(R[mid].key==K) return mid； //查找成功返回
if(R[mid].kdy>K)
high=mid-1; //继续在 R[low..mid-1]中查找
else
low=mid+1； /继续在 R[mid+1..high]中查找 /
}
return 0； //当 low>high时表示查找区间为空，查找失败
} //BinSeareh
3,二分查找算法二分查找算法亦很容易给出其递归程序【参见练习】
武汉理工大学华夏学院 -信息工程系
4,二分查找的优点和缺点虽然二分查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。既使采用高效率的排序方法也要花费 O(nlgn)的时间。
二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。
对那些查找少而又经常需要改动的线性表，
可采用链表作存储结构，进行顺序查找。链表上无法实现二分查找。
武汉理工大学华夏学院 -信息工程系
5,二分查找的平均查找长度设内部结点的总数为 n=2h-1,则判定树是深度为 h=lg(n+1)的满二叉树 (深度 h不计外部结点 )。
树中第 k层上的结点个数为 2k-1,查找它们所需的比较次数是 k。 因此在等概率假设下，二分查找成功时的平均查找长度为：
ASLbn≈lg(n+1)-1
二分查找在查找失败时所需比较的关键字个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度。即为,[lg(n+1)]
二分查找的最坏性能和平均性能相当接近。
武汉理工大学华夏学院 -信息工程系
（三） 分块查找分块查找 (Blocking Search)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。
1,分块查找表存储结构分块查找表由,分块有序,的线性表和索引表组成。
（ 1）,分块有序,的线性表表 R[1..n]均分为 b块，前 b-1块中结点个数为 s=[n/b],
第 b块的结点数小于等于 s； 每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是 "分块有序 "的。
武汉理工大学华夏学院 -信息工程系抽取各块中的最大关键字及其起始位置构成一个索引表 ID[l..b],即,ID[i] (1≤i≤b) 中存放第 i块的最大关键字及该块在表 R中的起始位置。由于表 R是分块有序的，所以索引表是一个递增有序表。
【例】 对于关键字序列为：
｛ 9,22,12,14,35,42,44,38,48,60,58,4778,80,77,82｝
的线性表建分块索引表上例中共有 16个元素,可以将其分为四块，其块表与索引表为：
（ 2）索引表武汉理工大学华夏学院 -信息工程系块表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
9 22 12 14 35 42 44 38 48 60 58 47 78 80 77 82
索引表
data low high
22 1 4
44 5 8
60 9 12
82 13 16
武汉理工大学华夏学院 -信息工程系分块查找的基本思想是：
（ 1）首先查找索引表索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。
（ 2）然后在已确定的块中进行顺序查找由于块内元素无序，只能采用顺序查找的方法实现块内查找。
2、分块查找的基本思想武汉理工大学华夏学院 -信息工程系
3、分块查找示例
【例】对于上例的存储结构：
（ 1）查找关键字等于给定值 K=35的结点因为索引表比较小，不妨用顺序查找方法查找索引表。即首先将 K依次和索引表中各关键字比较，直到找到第 1个关键宇大小等于 K的结点，由于 K<44,所以关键字为 35的结点若存在的话，则必定在第二块中；然后，由
ID[2].addr找到第二块的起始地址 5，从该地址开始在 R[5..8]中进行顺序查找，
直到 R[5].key=K为止。此时查找成功。
武汉理工大学华夏学院 -信息工程系
（ 2）若查找关键字等于给定值 K=79的结点先确定第四块，然后在该块中查找。因该块中查找不成功，故说明表中不存在关键字为
79的结点。
具体过程为：
先查索引表，将 K与 s[i]（ 1<=i<=4）
看 k是否小于等于 s[i],若是则块号为 i，
不是将 i加 1继续查找块号；当块号为 i
确定后，再定该块的起止下标，即起始下标为 s[i].low 终止 下标为 s[i].gigh 最后按顺序查找的方法在该范围内查找。
武汉理工大学华夏学院 -信息工程系
4、算法分析
（ 1）平均查找长度 ASL
分块查找是两次查找过程。整个查找过程的平均查找长度是两次查找的平均查找长度之和。
①以二分查找来确定块,分块查找成功时的平均查找长度
ASLblk=ASLbn+ASLsq≈lg(b+1)1+(s+1)/2≈lg(n/s+1)+s/2
② 以顺序查找确定块，分块查找成功时的平均查找长度
ASL'blk=(b+1)/2+(s+1)/2=(s2+2s+n)/(2s)
注意,分块查找算法的效率介于顺序查找和二分查找之间。
武汉理工大学华夏学院 -信息工程系
（ 2）块的大小在实际应用中，分块查找不一定要将线性表分成大小相等的若干块，可根据表的特征进行分块。
【例】一个学校的学生登记表，可按系号或班号分块。
（ 3） 结点的存储结构各块可放在不同的向量中，也可将每一块存放在一个单链表中。
分块查找的优点是：
① 在表中插入或删除一个记录时，只要找到该记录所属的块，
就在该块内进行插入和删除运算。
② 因块内记录的存放是任意的,所以插入或删除比较容易，
无须移动大量记录。
分块查找的主要代价是增加一个辅助数组的存储空间和将初始表分块排序的运算。
（ 4）分块查找的优点武汉理工大学华夏学院 -信息工程系
7.3 动态查找当用线性表作为表的组织形式时，可以有三种查找法。其中以二分查找效率最高。但由于二分查找要求表中结点按关键字有序，且不能用链表作存储结构，因此，
当表的插入或删除操作频繁时，为维护表的有序性，势必要移动表中很多结点。这种由移动结点引起的额外时间开销，就会抵消二分查找的优点。也就是说，二分查找只适用于静态查找表。若要对动态查找表进行高效率的查找，可采用下面介绍的几种特殊的二叉树或树作为表的组织形式。不妨将它们统称为树表。下面将分别讨论在这些树表上进行查找和修改操作的方法。
武汉理工大学华夏学院 -信息工程系
（一） 二叉排序树
1、二叉排序树的定义二叉排序树 (Binary Sort Tree)又称二叉查找
(搜索 )树 (Binary Search Tree)。 其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：
① 若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
② 若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
③ 左、右子树本身又各是一棵二叉排序树。
上述性质简称二叉排序树性质 (BST性质 )，
故二叉排序树实际上是满足 BST性质的二叉树。
武汉理工大学华夏学院 -信息工程系
2、二叉排序树的特点由 BST性质可得：
(1)二叉排序树中任一结点 x,其左 (右 )子树中任一结点 y(若存在 )的关键字必小 (大 )于 x的关键字。
(2)二叉排序树中，各结点关键字是惟一的。
注意：
实际应用中,不能保证被查找的数据集中各元素的关键字互不相同,所以可将二叉排序树定义中 BST性质 (1)里的,小于,改为,大于等于,,或将 BST性质 (2)里的 "大于 "改为 "小于等于 "，甚至可同时修改这两个性质。
武汉理工大学华夏学院 -信息工程系
(3)按中序遍历该树所得到的中序序列是一个递增有序序列。
【例】下图所示的两棵树均是二叉排序树，它们的中序序列均为有序序列,2,3,4,5,7,8。
4
2
3
7
5 8
42
3 7
5
8
武汉理工大学华夏学院 -信息工程系
3、二叉排序树的存储结构
typedef int KeyType； //假定关键字类型为整数
typedef struct node
{ //结点类型
KeyType key； //关键字项
InfoType otherinfo； //其它数据域,InfoType视应用情况而定，下面不处理它
struct node *lchild,*rchild； //左右孩子指针
} BSTNode；
typedef BSTNode *BSTree； //BSTree是二叉排序树的类型武汉理工大学华夏学院 -信息工程系
4、二叉排序树上的运算
（ 1） 二叉排序树的插入和生成
① 二叉排序树插入新结点的过程在二叉排序树中插入新结点，要保证插入后仍满足 BST性质。其插入过程是：
(a)若二叉排序树 T为空，则为待插入的关键字 key申请一个新结点，并令其为根；
(b)若二叉排序树 T不为空，则将 key和根的关键字比较：
(i)若二者相等，则说明树中已有此关键字 key，
无须插入。
(ii)若 key<T→key,则将 key插入根的左子树中。
(iii)若 key>T→key,则将它插入根的右子树中。
武汉理工大学华夏学院 -信息工程系子树中的插入过程与上述的树中插入过程相同。如此进行下去，直到将 key 作为一个新的叶结点的关键字插入到二叉排序树中，或者直到发现树中已有此关键字为止。
例如,设有结点序列 为 34,17,45,23,40
要求构造一棵二叉排序树。
步骤如下：
武汉理工大学华夏学院 -信息工程系将 34作为新树的树根
34
17 45
23
输入 17，与树根比较，
因 17 比 34小，则将 17挂在 34 的左子树下 。
输入 45，与树根比较，
因 45比 34大，则将 45挂在 34 的右子树下。
输入 23，与树根比较，因 23比 34小，
则将 23挂在 34 的左子树下。又因左子树不空则将 23与 17比较，而 23比 17大，故挂在其右子树下输入 40，与树根比较，因 40比 34大，
则将 40挂在 34 的右子树下。又因右子树不空则将 40与 45比较，而 40比 45小，故挂在其左子树下
40
武汉理工大学华夏学院 -信息工程系
③ 二叉排序树插入新结点的非递归算法
void InsertBST(BSTree *Tptr,KeyType key)
{//若二叉排序树 *Tptr中没有关键字为 key,则插入，否则直接返回
BSTNode *f,*p=*TPtr； //p的初值指向根结点
while(p){ //查找插入位置
if(p->key==key) return； //树中已有 key,无须插入
f=p； //f保存当前查找的结点
p=(key<p->key)?p->lchild,p->rchild；
//若 key<p->key,则在左子树中查找，否则在右子树中查找
} //endwhile
武汉理工大学华夏学院 -信息工程系
p=(BSTNode *)malloc(sizeof(BSTNode))；
p->key=key；
p->lchild=p->rchild=NULL； //生成新结点
if(*TPtr==NULL) //原树为空
*Tptr=p； //新插入的结点为新的根
else //原树非空时将新结点关 p作为关 f的左孩子或右孩子插入
if(key<f->key)
f->lchild=p；
else f->rchild=p；
} //InsertBST
武汉理工大学华夏学院 -信息工程系
④ 二叉排序树的生成二叉排序树的生成，是从空的二叉排序树开始，每输入一个结点数据，就调用一次插入算法将它插入到当前已生成的二叉排序树中。生成二叉排序树的算法如下：
BSTree CreateBST(void)
{ //输入一个结点序列，建立一棵二叉排序树，将根结点指针返回
BSTree T=NULL； //初始时 T为空树
KeyType key；
scanf(“％ d”,&key)； //读人一个关键字
while(key){ //假设 key=0是输人结束标志
InsertBST(&T,key)； //将 key插入二叉排序树 T
scanf(“％ d”,&key)； //读人下一关键字
}
return T； //返回建立的二叉排序树的根指针
} //BSTree
武汉理工大学华夏学院 -信息工程系
（ 2）二叉排序树的删除从二叉排序树中删除一个结点，不能把以该结点为根的子树都删去，并且还要保证删除后所得的二叉树仍然满足 BST性质。
① 删除操作的一般步骤
(1) 进行查找查找时，令 p指向当前访问到的结点,parent指向其双亲 (其初值为 NULL)。 若树中找不到被删结点则返回，否则被删结点是 *p。
(2) 删去 *p。
删 *p时，应将 *p的子树 (若有 ) 仍连接在树上且保持 BST性质不变。按 *p的孩子数目分三种情况进行处理。
武汉理工大学华夏学院 -信息工程系
② 删除 *p结点的三种情况
(1)*p是叶子 (即它的孩子数为 0)
无须连接 *p的子树，只需将 *p的双亲 *parent中指向 *p的指针域置空即可。
(2)*p只有一个孩子 *child
只需将 *child和 *p的双亲直接连接后,即可删去 *p。
*p 既可能是 *parent的左孩子也可能是其右孩子，
而 *child可能是 *p的左孩子或右孩子，故共有 4种状态。
注意武汉理工大学华夏学院 -信息工程系
③ 二叉排序树删除算法上述三种情况都能统一到情况 (2)，算法中只需针对情况
(2)处理即可。
注意边界条件：若 parent为空，被删结点 *p 是根，
故删去 *p后，应将 child置为根。
(3)*p有两个孩子先令 q=p,将被删结点的地址保存在 q中；然后找 *q
的中序后继 *p,并在查找过程中仍用 parent记住 *p 的双亲位置。 *q的中序后继 *p一定是 *q 的右子树中最左下的结点，它无左子树。因此，可以将删去 *q 的操作转换为删去的 *p的操作，即在释放结点 *p 之前将其数据复制到
*q中，就相当于删去了 *q。
分析武汉理工大学华夏学院 -信息工程系
void DelBSTNode(BSTree *Tptr,KeyType key)
{//在二叉排序树 *Tptr中删去关键字为 key的结点
BSTNode *parent=NUll,*p=*Tptr,*q，
*child；
while(p){ //从根开始查找关键字为 key的待删结点
if(p->key==key) break； //已找到，跳出查找循环
parent=p； //parent指向 *p的双亲
p=(key<p->key)?p->lchild,p->rchild；
//在关 p的左或右子树中继续找
}
if(!p) return； //找不到被删结点则返回
q=p； //q记住被删结点 *p
算法：
武汉理工大学华夏学院 -信息工程系
if(q->lchild&&q->rchild)
//*q的两个孩子均非空，故找 *q的中序后继 *p
for(parent=q,p=q->rchild； p->lchild；
parent=p,p=p=->lchild)；
//现在情况 (3)已被转换为情况 (2)，而情况 (1)相当于是情况 (2)中 child=NULL的状况
child=(p->lchild)?p->lchild,p->rchild；
//若是情况 (2)，则 child非空；否则 child为空
if(!parent)
//*p的双亲为空，说明 *p为根，删 *p后应修改根指针
*Tptr=child；
//若是情况 (1)，则删去 *p后，树为空；否则 child变为根武汉理工大学华夏学院 -信息工程系
else{//*p不是根,将 *p的孩子和 *p的双亲进行连接,*p从树上被摘下
if(p==parent->lchild)
//*p是双亲的左孩子
parent->lchild=child；
//*child作为 *parent的左孩子
else parent->rchild=child；
//*child作为 parent的右孩子
if(p!=q)
//是情况 (3)，需将 *p的数据复制到 *q
q->key=p->key； //若还有二叉排序树的删除运算实例具体操作如下武汉理工大学华夏学院 -信息工程系
42
3 7
5
8
删除叶结点 2
4
3 7
5
8
删除根结点 5后
3 7
4
8
删除内结点 7后
3 8
4
注意：删除某一个结点后的二叉树，必须保持其仍然是一棵二叉排序树。（不能改变该性质）
武汉理工大学华夏学院 -信息工程系
(3) 二叉排序树上的查找
①查找递归算法在二叉排序树上进行查找，和二分查找类似，也是一个逐步缩小查找范围的过程。
递归的查找算法：
BSTNode *SearchBST(BSTree T,KeyType key)
{ //在二叉排序树 T上查找关键字为 key的结点，成功时返回该结点位置，否则返回 NUll
if(T==NULL||key==T->key) //递归的终结条件
return T; //T为空,查找失败 ;否则成功,返回找到的结点位置
if(key<T->key)
return SearchBST(T->lchild,key)；
else
return SearchBST(T->rchild,key)； //继续在右子树中查找
} //SearchBST
武汉理工大学华夏学院 -信息工程系
②算法分析在二叉排序树上进行查找时，若查找成功，
则是从根结点出发走了一条从根到待查结点的路径。若查找不成功，则是从根结点出发走了一条从根到某个叶子的路径。
(1) 二叉排序树查找成功的平均查找长度在等概率假设下，二叉排序树查找成功的平均查找长度为
nASLa= ∑
picj=(1+2?2+3?4+4?3)/10=3i=1
武汉理工大学华夏学院 -信息工程系
(2)在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关二分查找法查找长度为 n的有序表，其判定树是惟一的。含有 n个结点的二叉排序树却不惟一。对于含有同样一组结点的表，由于结点插入的先后次序不同，所构成的二叉排序树的形态和深度也可能不同在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关：
武汉理工大学华夏学院 -信息工程系
① 在最坏情况下，二叉排序树是通过把一个有序表的 n 个结点依次插入而生成的，此时所得的二叉排序树蜕化为棵深度为 n的单支树,它的平均查找长度和单链表上的顺序查找相同,亦
(n+1)/2。
② 在最好情况下，二叉排序树在生成的过程中，
树的形态比较匀称，最终得到的是一棵形态与二分查找的判定树相似的二叉排序树，此时它的平均查找长度大约是 lgn。
③ 插入、删除和查找算法的时间复杂度 O(lgn)。
武汉理工大学华夏学院 -信息工程系
(3)二叉排序树和二分查找的比较就平均时间性能而言，二叉排序树上的查找和二分查找差不多。
就维护表的有序性而言，二叉排序树无须移动结点，只需修改指针即可完成插入和删除操作,且其平均的执行时间均为 O(lgn),因此更有效。二分查找所涉及的有序表是一个向量，
若有插入和删除结点的操作，则维护表的有序性所花的代价是 O(n)。 当有序表是静态查找表时，宜用向量作为其存储结构，而采用二分查找实现其查找操作；若有序表里动态查找表，
则应选择二叉排序树作为其存储结构。
武汉理工大学华夏学院 -信息工程系
(二）平衡二叉树（ AVL树）
1.定义：平衡二叉树或为空树，或为具有如下性质的二叉排序树：
a,左右子树为平衡二叉树；
b,左右子树的深度之差的绝对值小于 1；
2,结点的平衡因子：用结点的左子树的深度减右子树的深度。
显然：平衡二叉树的各结点的平衡因子只能为－ 1,0,1。例如：
a
fe
c b
g
d
－ 1
0
0 － 2
－ 1
00
非平衡二叉树 平衡二叉树
a
fe
c b
g
d
－ 1
0
0 － 1
－ 1
0
0
h
0
武汉理工大学华夏学院 -信息工程系
3.平衡二叉树的用途：提高查找速度
4.二叉排序树的平衡旋转对于构造的二叉排序树转化为平衡二叉树一般有四种情况：
A,单向右旋平衡处理（ LL型平衡旋转）
当某一个结点 A的平衡因子为 1时，其左子树插入结点后平衡因子为 2，失去平衡。此时需进行一次向右旋转（顺时针）操作。例如：
a
ab
b
ar
brbl
2
1
插入结点
0
0
arbr
bl
LL
武汉理工大学华夏学院 -信息工程系
B,单向左旋平衡处理（ RR型平衡旋转）
当某一个结点 A的平衡因子为 -1时，其右子树插入结点后平衡因子为 -2，失去平衡。
此时需进行一次向左旋转（逆时针）操作。
例如：
A
ABAL
BRBL
2
插入结点
0
0
BrAL
BR
RR-1
B
武汉理工大学华夏学院 -信息工程系
C,双向平衡处理（先左后右）
（ LR型平衡旋转）
当某一个结点 A的平衡因子为 1时，其左子树的右子树插入结点后平衡因子为 2，
失去平衡。此时需进行两次旋转（先逆时针，后顺时针）操作。例如：
a
ab
C
ar
CL
bl
2
-1
插入结点
0
0
arCrbl
LR
Cr
C
1 B
CL
武汉理工大学华夏学院 -信息工程系
D,双向平衡处理（先右后左）
（ RL型平衡旋转）
当某一个结点 A的平衡因子为 1时，其左子树的右子树插入结点后平衡因子为 2，
失去平衡。此时需进行两次旋转（先逆时针，后顺时针）操作。例如：
A
BB
C
AL
CL
BR
-2
1
插入结点
-1
-1
BRCrAL
RL
CR
C
1 A
CL
0
武汉理工大学华夏学院 -信息工程系例：设有一个序列 {13,24,37,90,53}
构造二叉平衡树。
按二叉排序树的构造方法进行空树，平衡
13
一个结点，平衡
13
两个结点，平衡
24
0 -1
0
13
三个结点，不平衡
24
-2
-1
370
24
逆时针右旋，平衡
37
0
0
13 0
24
插入 90后，平衡
37
-1
-1
13 0
90
0
武汉理工大学华夏学院 -信息工程系
24
插入 53后，不平衡
37
-2
-2
13 0
90
1
53 0
24
以 37为根，第一次顺时针旋转
3713
53
90
24
第二次逆时针旋转，平衡
37
-1
0
13 0
90
0530
武汉理工大学华夏学院 -信息工程系
7.4 散列查找技术 （ 又称哈希查找技术 ）
散列查找方法不同于顺序查找、二分查找、二叉排序树及 B-树上的查找。它不以关键字的比较为基本操作，采用直接寻址技术。在理想情况下，无须任何比较就可以找到待查关键字，查找的期望时间为 O(1)。
（一）散列表的概念
1、散列表设所有可能出现的关键字集合记为 U(简称全集 )。实际发生 (即实际存储 )的关键字集合记为 K(|K|比 |U|小得多 )。
散列方法是使用函数 h将 U映射到表 T [0..m-1] 的下标上
（ m=O(|U|)）。 这样以 U中关键字为自变量，以 h为函数的运算结果就是相应结点的存储地址。从而达到在 O (1)
时间内就可完成查找。
武汉理工大学华夏学院 -信息工程系
① h,U→{0,1,2,…,m-1},通常称 h
为散列函数 (Hash Function)。 散列函数 h的作用是压缩待处理的下标范围,使待处理的 |U|
个值减少到 m个值，从而降低空间开销。
② T为散列表 (Hash Table)。
③ h(Ki)(Ki∈ U)是关键字为 Ki结点存储地址 (亦称散列值或散列地址 )。
④ 将结点按其关键字的散列地址存储到散列表中的过程称为散列 (Hashing)
其中：
武汉理工大学华夏学院 -信息工程系
2 建散列表的方法举例设 B是一个有 15个元素的线性表，其中各值为
B=(12,33,65,9,38,71,82,63,75,15,24,57,54,88,98)
要把这 15个元素存放到有 20个存储单元的存储区内，步骤为：
（ 1) 选取 h(k)=int(k/5) （ k除 5取整）
（ 2) 根据结点的值，计算出该结点的存储地址即 loc(k)=h(k)
（ 3) 将 k存入 s[loc(k)]中。即有地址 1 2 3 4 5 6 7 8 9 1011 1213141516171819
结点值 9 121524 3338 5457636571758288 98
0
武汉理工大学华夏学院 -信息工程系
3、散列表的冲突现象
（ 1）冲突两个不同的关键字，由于散列函数值相同,因而被映射到同一表位置上。该现象称为冲突 (Collision)或碰撞。发生冲突的两个关键字称为该散列函数的同义词 (Synonym)。
【 例】上图中,增加一个结点值 37,则 h(37)=h(38 ),故上述两个 结点的存储地址相同。即产生了冲突。
（ 2）安全避免冲突的条件最理想的解决冲突的方法是安全避免冲突。要做到这一点必须满足两个条件：
① 其一是 |U|≤m
② 其二是选择合适的散列函数。
这只适用于 |U|较小,且关键字均事先已知的情况,此时经过精心设计散列函数 h有可能完全避免冲突。
武汉理工大学华夏学院 -信息工程系
（ 3）冲突不可能完全避免通常情况下,h是一个压缩映像,虽然 |K|≤m,但
|U| >m,故无论怎样设计 h,也不可能完全避免冲突。因此只能在设计 h时尽可能使冲突最少。
同时还需要确定解决冲突的方法，使发生冲突的同义词能够存储到表中。
（ 4）影响冲突的因素冲突的频繁程度除了与 h相关外，还与表的填满程度相关。
设 m 和 n 分别表示表长和表中填人的结点数,则将 a=n/m定义为散列表的装填因子 (Load Factor )。
α越大,表越满,冲突的机会也越大,通常取 α≤1。
武汉理工大学华夏学院 -信息工程系
（二） 散列函数的构造方法
1、散列函数的选择有两条标准,简单和均匀。
简单指散列函数的计算简单快速；
均匀指对于关键字集合中的任一关键字，散列函数能以等概率将其映射到表空间的任何一个位置上。也就是说，散列函数能将子集 K随机均匀地分布在表的地址集 {0,1,…,m-1}上，以使冲突最小化。
2、常用散列函数为简单起见，假定关键字是定义在自然数集合上。
（ 1）平方取中法具体方法：先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值。
又因为一个乘积的中间几位数和乘数的每一位都相关，
所以由此产生的散列地址较为均匀。
武汉理工大学华夏学院 -信息工程系
【例】 将一组关键 (0100,0110,1010,1001,0111)
平方后得 (0010000,0012100,1020100,1002001,0012321)
若取表长为 1000，则可取中间的三位数作为散列地址集,(100,121,201,020,123)。
相应的散列函数用 C实现很简单：
int Hash(int key)
{ //假设 key是 4位整数
key*=key；
key/=100； //先求平方值，后去掉末尾的两位数
return key％ 1000; //取中间三位数作为散列地址返回
}
武汉理工大学华夏学院 -信息工程系
（ 2）除余法该方法是最为简单常用的一种方法。它是以表长 m来除关键字，取其余数作为散列地址，即
h(key)=key％ m
该方法的关键是选取 m。 选取的 m 应使得散列函数值尽可能与关键字的各位相关。 m最好为素数。
【例 若选 m是关键字的基数的幂次,则就等于是选择关键字的最后若干位数字作为地址，而与高位无关。于是高位不同而低位相同的关键字均互为同义词。
【例】 若关键字是十进制整数，其基为 10 则当
m=100时,159,259,359,…,等均互为同义词。
武汉理工大学华夏学院 -信息工程系
（ 3）相乘取整法该方法包括两个步骤：首先用关键字 key乘上某个常数 A(0<A<1),并抽取出 key.A的小数部分；然后用 m乘以该小数后取整。即：
h(key)=[m(key.A-key.A)]
该方法最大的优点是选取 m不再像除余法那样关键。比如，完全可选择它是 2的整数次幂。虽然该方法对任何 A
的值都适用，但对某些值效果会更好。 Knuth建议选取
int Hash(int key){
double d=key *A； //不妨设 A和 m已有定义
return (int)(m*(d-(int)d))；
//(int)表示强制转换后面的表达式为整数 }
A ≈ (5-1)/2=0.61803398 87…
该函数的 C代码为：
武汉理工大学华夏学院 -信息工程系
（ 4）随机数法选择一个随机函数，取关键字的随机函数值为它的散列地址，即,h(key)=random(key)
其中 random为伪随机函数，但要保证函数值是在 0到 m-1之间。
（三）处理冲突的方法通常有两类方法处理冲突：开放定址 (Open
Addressing)法和拉链 (Chaining)法。前者是将所有结点均存放在散列表 T[0..m-1]中；后者通常是将互为同义词的结点链成一个单链表，而将此链表的头指针放在散列表 T[0..m-1]中。
武汉理工大学华夏学院 -信息工程系
1、开放定址法
（ 1）开放地址法解决冲突的方法用开放定址法解决冲突的做法是：当冲突发生时，
使用某种探查 (亦称探测 )技术在散列表中形成一个探查
(测 )序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址 (即该地址单元为空 )
为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探查到开放的地址则表明表中无待查的关键字，即查找失败。
注意：
① 用开放定址法建立散列表时，建表前须将表中所有单元 (更严格地说，是指单元中存储的关键字 )置空。
② 空单元的表示与具体的应用相关。
武汉理工大学华夏学院 -信息工程系
【例】 关键字均为非负数时，可用,-1” 来表示空单元，
而关键字为字符串时，空单元应是空串。
（ 2）开放地址法的一般形式开放定址法的一般形式为,hi=(h(key)+di)％ m
1≤i≤m-1
其中：
① h(key)为散列函数,di为增量序列,m为表长。
② h(key)是初始的探查位置，后续的探查位置依次是 hl，
h2,…,hm-1,即 h(key),hl,h2,…,hm-1形成了一个探查序列。
③ 若令开放地址一般形式的 i从 0开始，并令 d0=0,则
h0=h(key),则有：
hi=(h(key)+di)％ m 0≤i≤m-1
探查序列可简记为 hi(0≤i≤m-1)。
总之：应该用一个不会出现的关键字来表示空单元。
武汉理工大学华夏学院 -信息工程系
（ 3）开放地址法堆装填因子的要求开放定址法要求散列表的装填因子 α≤l,实用中取 α为 0.5到 0.9之间的某个值为宜。
（ 4）形成探测序列的方法按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、二次探查法、双重散列法等。
武汉理工大学华夏学院 -信息工程系
① 线性探查法 (Linear Probing)
该方法的基本思想是：
将散列表 T[0..m-1]看成是一个循环向量，若初始探查的地址为 d(即 h(key)=d),则最长的探查序列为：
d,d+l,d+2,…,m-1,0,1,…,d-1
即,探查时从地址 d开始，首先探查 T[d],然后依次探查 T[d+1],…,直到 T[m-1],此后又循环到 T[0]，
T[1],…,直到探查到 T[d-1]为止。
探查过程终止于三种情况：
(1)若当前探查的单元为空，则表示查找失败（若是插入则将 key写入其中）；
(2)若当前探查的单元中含有 key,则查找成功，但对于插入意味着失败；
(3)若探查到 T[d-1]时仍未发现空单元也未找到 key,则无论是查找还是插入均意味着失败 (此时表满 )。
武汉理工大学华夏学院 -信息工程系利用开放地址法的一般形式，线性探查法的探查序列为：
hi=(h(key)+i)％ m 0≤i≤m -1 //即 di=i利用线性探测法构造散
【例 7.1】 已知一组关键字为 ( 26,36,41,38,44,15,
68,12,06,51),用除余法构造散列函数，用线性探查法解决冲突构造这组关键字的散列表。
解答,为了减少冲突，通常令装填因子 α<l。 这里关键字个数 n=10,不妨取 m=13,此时 α≈0.77,散列表为 T[0..12],散列函数为,h(key)=key％ 13。
由除余法的散列函数计算出的上述关键字序列的散列地址为 (0,10,2,12,5,2,3,12,6,12)。
武汉理工大学华夏学院 -信息工程系前 5个关键字插入时，其相应的地址均为开放地址，
故将它们直接插入 T[0],T[10),T[2],T[12]和 T[5]中。
当插入第 6个关键字 15时，其散列地址 2( 即 h(15)=15
％ 13=2)已被关键字 41( 15和 41互为同义词 )占用。故探查
h1=(2+1)％ 13=3,此地址开放，所以将 15放入 T[3]中。
当插入第 7个关键字 68时,其散列地址 3已被非同义词
15先占用，故将其插入到 T[4]中。
当插入第 8个关键字 12 时,散列地址 12已被同义词 38
占用，故探查 hl=(12+1)％ 13=0,而 T[0]亦被 26占用，再探查 h2=(12+2)％ 13=1,此地址开放，可将 12插入其中。
类似地，第 9个关键字 06直接插入 T[6]中；而最后一个关键字 51插人时,因探查的地址 12,0,1,…,6均非空，
故 51插入 T[7]中。
武汉理工大学华夏学院 -信息工程系聚集或堆积现象用线性探查法解决冲突时，当表中 i,i+1,…,
i+k 的位置上已有结点时，一个散列地址为 I,
i +1,…,i+k+1的结点都将插入在位置 i+k+1
上。把这种散列地址不同的结点争夺同一个后继散列地址的现象称为聚集或堆积 (Clustering)。
这将造成不是同义词的结点也处在同一个探查序列之中，从而增加了探查序列的长度，即增加了查找时间。若散列函数不好或装填因子过大，都会使堆积现象加剧。
武汉理工大学华夏学院 -信息工程系
【例】 上例中,h (15)=2,h (68)=3,即 15和 68
不是同义词。但由于处理 15和同义词 41的冲突时,15抢先占用了 T[ 3 ],这就使得插入 68时，
这两个本来不应该发生冲突的非同义词之间也会发生冲突。
为了减少堆积的发生，不能像线性探查法那样探查一个顺序的地址序列 ( 相当于顺序查找 )，而应使探查序列跳跃式地散列在整个散列表中。
武汉理工大学华夏学院 -信息工程系
（ 2)二次探查法 (Quadratic Probing)
二次探查法的探查序列是：
hi=(h(key)+i*i)％ m 0≤i≤m-1 //即 di=i2
即探查序列为 d=h(key),d+12,d+22,…,等。
该方法的缺陷是不易探查到整个散列空间。
（ 3)双重散列法 (Double Hashing)
该方法是开放定址法中最好的方法之一，它的探查序列是：
hi=(h(key)+i*h1(key))％ m 0≤i≤m-1 //即 di=i*h1(key)
即探查序列为：
d=h(key),(d+h1(key))％ m,(d+2h1(key))％ m,…,
等。该方法使用了两个散列函数 h(key)和 h1(key)，
故也称为双散列函数探查法。
武汉理工大学华夏学院 -信息工程系注意：
定义 h1(key)的方法较多，但无论采用什么方法定义，都必须使 h1(key)的值和 m互素，才能使发生冲突的同义词地址均匀地分布在整个表中，
否则可能造成同义词地址的循环计算。
【例】 若 m为素数，则 h1 (key)取 1到 m-1之间的任何数均与 m互素，因此，我们可以简单地将它定义为,h1(key)=key％ (m-2)+1
【 例】 对例 7.1，我们可取 h(key)=key％ 13,而
h1(key)=key％ 11+1。
【 例】 若 m是 2的方幂，则 h1( key)可取 1到 m-1之间的任何奇数。
武汉理工大学华夏学院 -信息工程系
（ 4)伪随机探查法将 二次探查法的探查函数 d(i) 设计为一个随机函数，如 d(i)＝（ d+p) MOD m
其中 m为表长,d为产生冲突的地址,p为质数
（是一个不大于 m的最大质数）。
例如,在一个表长为 11的散列表中，存放值为
｛ 29,17,60,38}的记录，其哈希函数为
h(key)=key MOD 11
则有 h(29)=7;h(17)=6;h(60)=5；
h(38)=5 此时与 60产生了冲突哈希表为：
60 17 29
0 1 2 3 4 5 6 7 8 9 10
武汉理工大学华夏学院 -信息工程系
（ 1)用 线性探查法 处理冲突，散列地址 =8
60 17 29 38
0 1 2 3 4 5 6 7 8 9 10
（ 2)用 二次探查法 处理冲突，散列地址 =4
此时取 d(i)=-12
地址＝ h(key)+（ -12 ） MOD m＝ 4
6038 17 29
0 1 2 3 4 5 6 7 8 9 10
（ 3)用 伪随机探查法 处理冲突，散列地址 =3
此时取 d(i)=（ h(38)+p） MOD m
h(38)=5 ; p=9 ; m=11；
6038 17 29
0 1 2 3 4 5 6 7 8 9 10
武汉理工大学华夏学院 -信息工程系
2、拉链法
（ 1）拉链法解决冲突的方法拉链法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为 m,则可将散列表定义为一个由 m
个头指针组成的指针数组 T[0..m-1]。 凡是散列地址为 i的结点，均插入到以 T[i]为头指针的单链表中。 T中各分量的初值均应为空指针。在拉链法中，装填因子 α可以大于 1，但一般均取 α≤1。
武汉理工大学华夏学院 -信息工程系
【 例 7.2】已知一组关键字和选定的散列函数和例 7.1相同，用拉链法解决冲突构造这组关键字的散列表。
解答：不妨和例 7.1类似，取表长为 13，故散列函数为 h(key)=key％ 13,散列表为 T[0..12]。
武汉理工大学华夏学院 -信息工程系
(2)拉链法的优点与开放定址法相比，拉链法有如下几个优点：
(1)拉链法处理冲突简单，且无堆积现象,即非同义词决不会发生冲突，因此平均查找长度较短；
(2)由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
(3)开放定址法为减少冲突,要求装填因子 α 较小，故当结点规模较大时会浪费很多空间。而拉链法中可取 α ≥ 1,且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
武汉理工大学华夏学院 -信息工程系
(4)在用拉链法构造的散列表中,删除结点的操作易于实现 。 只要简单地删去链表上相应的结点即可 。 而对开放地址法构造的散列表,删除结点不能简单地将被删结点的空间置为空,否则将截断在它之后填人散列表的同义词结点的查找路径 。 这是因为各种开放地址法中,空地址单元 (即开放地址 )都是查找失败的条件 。 因此在用开放地址法处理冲突的散列表上执行删除操作,只能在被删结点上做删除标记,而不能真正删除结点 。
（ 3） 拉链法的缺点拉链法的缺点是：指针需要额外的空间,故当结点规模较小时,开放定址法较为节省空间,而若将节省的指针空间用来扩大散列表的规模,可使装填因子变小,这又减少了开放定址法中的冲突,从而提高平均查找速度 。
武汉理工大学华夏学院 -信息工程系
（四）散列表上的运算散列表上的运算有查找、插入和删除。其中主要是查找，这是因为散列表的目的主要是用于快速查找，且插入和删除均要用到查找操作。
1、散列表类型说明：
#define NIL -1 //空结点标记依赖于关键字类型,
本节假定关键字均为非负整数
#define M 997 //表长度依赖于应用，但一般应根据。确定 m为一素数
typedef struct{ //散列表结点类型
KeyType key；
InfoType otherinfo； //此类依赖于应用
}NodeType；
typedef NodeType HashTable[m]； //散列表类型
武汉理工大学华夏学院 -信息工程系
2、基于开放地址法的查找算法散列表的查找过程和建表过程相似。假设给定的值为 K,根据建表时设定的散列函数 h，
计算出散列地址 h(K),若表中该地址单元为空，
则查找失败；否则将该地址中的结点与给定值
K比较。若相等则查找成功,否则按建表时设定的处理冲突的方法找下一个地址。如此反复下去，直到某个地址单元为空 ( 查找失败 )或者关键字比较相等 (查找成功 )为止。
武汉理工大学华夏学院 -信息工程系
(1)开放地址法一般形式的函数表示
int Hash(KeyType k,int i)
{ //求在散列表 T[0..m-1]中第 i次探查的散列地址 hi,0≤i≤m -1
//下面的 h是散列函数。 Increment是求增量序列的函数，它依赖于解决冲突的方法
return(h(K)+Increment(i))％ m； //Increment(i)相当于是 di
}
若散列函数用除余法构造，并假设使用线性探查的开放定址法处理冲突，则上述函数中的 h(K)和
Increment(i)可定义为：
int h(KeyType K){ //用除余法求 K的散列地址
return K％ m；
}
int Increment(int i)
{//用线性探查法求第 i个增量 di
return i; //若用二次探查法，则返回 i*i
}
武汉理工大学华夏学院 -信息工程系
（ 2）通用的开放定址法的散列表查找算法：
int HashSearch(HashTable T,KeyType K,int *pos)
{ //在散列表 T[0..m-1]中查找 K,成功时返回 1。失败有两种情况：找到一个开放地址
//时返回 0，表满未找到时返回 -1。 *pos记录找到 K或找到空结点时表中的位置
int i=0； //记录探查次数
do{
*pos=Hash(K,i)； //求探查地址 hi
if(T[*pos].key==K) return l； //查找成功返回
if(T[*pos].key==NIL) return 0； //查找到空结点返回
}while(++i<m) //最多做 m次探查
return -1； //表满且未找到时，查找失败
} //HashSearch?
武汉理工大学华夏学院 -信息工程系注意,上述算法适用于任何开放定址法，只要给出函数 Hash 中的散列函数 h ( K ) 和增量函数
Increment( I )即可。但要提高查找效率时，可将确定的散列函数和求增量的方法直接写入算法 HashSearch中，相应的算法 【参见习题】 。
3、基于开放地址法的插入及建表建表时首先要将表中各结点的关键字清空，
使其地址为开放的；然后调用插入算法将给定的关键字序列依次插入表中。
插入算法首先调用查找算法，若在表中找到待插入的关键字或表已满，则插入失败；若在表中找到一个开放地址，则将待插入的结点插入其中，即插入成功。
武汉理工大学华夏学院 -信息工程系
void Hashlnsert(HashTable T,NodeTypene w)
{ //将新结点 new插入散列表 T[0..m-1]中
int pos,sign；
sign=HashSearch(T,new.key,&pos)；
//在表 T中查找 new的插入位置
if(!sign) //找到一个开放的地址 pos
T[pos]=new； //插入新结点 new,插入成功
else //插人失败
if(sign>0)
printf(“duplicate key!”)； //重复的关键字
else //sign<0
Error(“hashtableoverflow!”)； //表满错误,终止程序执行
} //Hashlnsert
武汉理工大学华夏学院 -信息工程系
void CreateHashTable(HashTable T,NodeType A[]，
int n)
{ //根据 A[0..n-1]中结点建立散列表 T[0..m-1]
int i
if(n>m) //用开放定址法处理冲突时，装填因子 α须不大于 1
Error("Load factor>1")；
for(i=0;i<m； i++)
T[i].key=NIL； //将各关键字清空，使地址 i为开放地址
for(i=0;i<n； i++) //依次将 A[0..n-1]插入到散列表 T[0..m-1]中
Hashlnsert(T,A[i])；
} //CreateHashTable
武汉理工大学华夏学院 -信息工程系
4、删除基于开放定址法的散列表不宜执行散列表的删除操作。若必须在散列表中删除结点，则不能将被删结点的关键字置为 N I L,而应该将其置为特定的标记
DELETED。
因此须对查找操作做相应的修改，使之探查到此标记时继续探查下去。同时也要修改插人操作，使其探查到 DELETED 标记时，将相应的表单元视为一个空单元，将新结点插入其中。这样做无疑增加了时间开销，并且查找时间不再依赖于装填因子。
因此，当必须对散列表做删除结点的操作时，一般是用拉链法来解决冲突。
注意：
用拉链法处理冲突时的有关散列表上的算法 【参见练习】 。
武汉理工大学华夏学院 -信息工程系
5、性能分析插入和删除的时间均取决于查找，故下面只分析查找操作的时间性能。
虽然散列表在关键字和存储位置之间建立了对应关系，理想情况是无须关键字的比较就可找到待查关键字。但是由于冲突的存在，散列表的查找过程仍是一个和关键字比较的过程，
不过散列表的平均查找长度比顺序查找、二分查找等完全依赖于关键字比较的查找要小得多。
武汉理工大学华夏学院 -信息工程系
（ 1）查找成功的 ASL
散列表上的查找优于顺序查找和二分查找。
【例】在例 9.1 和例 9.2 的散列表中，在结点的查找概率相等的假设下，线性探查法和拉链法查找成功的平均查找长度分别为：
ASL=(1× 6+2× 2+3× l+9× 1)/10=2.2 //线性探查法
ASL=(1× 7+2× 2+3× 1)/10=1.4 //拉链法而当 n = 10 时，顺序查找和二分查找的平均查找长度 (成功时 )分别为：
ASL=(10+1)/2=5.5 //顺序查找
ASL=(1× l+2× 2+3× 4+4× 3)/10=2.9
//二分查找，可由判定树求出该值武汉理工大学华夏学院 -信息工程系
(2)查找不成功的 ASL
对于不成功的查找，顺序查找和二分查找所需进行的关键字比较次数仅取决于表长，而散列查找所需进行的关键字比较次数和待查结点有关。因此，在等概率情况下，也可将散列表在查找不成功时的平均查找长度，
定义为查找不成功时对关键字需要执行的平均比较次数
【例】 例 7.1和例 7.2的散列表中，在等概率情况下，查找不成功时的线性探查法和拉链法的平均查找长度分别为：
ASLunsucc=(1+0+2+1+0+1+1+0+0+0+1+0+3)/13≈10/13≈0.77
ASLunsucc=(9+8+7+6+5+4+3+2+1+1+2+1+10)/13=59/13≈4.54
武汉理工大学华夏学院 -信息工程系注意：
①由同一个散列函数、不同的解决冲突方法构造的散列表，其平均查找长度是不相同的。
②散列表的平均查找长度不是结点个数 n的函数，
而是装填因子 α 的函数。因此在设计散列表时可选择 α 以控制散列表的平均查找长度。
③ α 的取值
α 越小，产生冲突的机会就小，但 α 过小,
空间的浪费就过多。只要 α 选择合适，散列表上的平均查找长度就是一个常数，即散列表上查找的平均时间为 O(1)。
直接求出地址的查找方法,其查找的期望时间为 O(1)。
武汉理工大学华夏学院 -信息工程系
④ 散列法与其他查找方法的区别,
除散列法外，其他查找方法有共同特征为：均是建立在比较关键字的基础上。其中顺序查找是对无序集合的查找，每次关键字的比较结果为,=” 或,!=” 两种可能，其平均时间为
O(n)； 其余的查找均是对有序集合的查找，每次关键字的比较有,=”,,<” 和,>” 三种可能，且每次比较后均能缩小下次的查找范围，
故查找速度更快，其平均时间为 O(lgn)。 而散列法是根据关键字直接求地址的查找方法，其期望的时间为 O(1)。
武汉理工大学华夏学院 -信息工程系例：使用的哈希函数为：
H(Ki)=3Ki mod 11并采用开放地址法（伪随机探测）处理冲突,其求下一个地址的函数为：
di=H(ki)
Di=(di-1+(7ki mod 10)+1)mod11 (i=2,3…)
试在 0~10的散列地址空间中对关键字序列（ 22,41,53，
46,30,13,01,67）构造哈希表，求等概率情况下查找成功的平均查找长度，并设计构造哈希表的完整函数。
本题的哈希表构造过程如下：
（ 1） H(22)=3*33 mod 11=0
（ 2） H(41)=3*41 mod 11=2
武汉理工大学华夏学院 -信息工程系
（ 3） H(53)=3*53 mod 11=5
（ 4） H(46)=3*46 mod 11=6
（ 5） H(30)=3*30 mod 11=2 (冲突 )
d1=H(30)=2
H(30)=(2+(7*30 mod 10) +1 ） mod 11=3
（ 6） H(13)=3*13 mod 11=6 (冲突 )
d1=H(13)=6
H(13)=(6+(7*13 mod 10) +1） mod 11=8
（ 7） H(1)=3*1 mod 11=3 (冲突 )
d1=H(1)=3
H(1)=(3+(1*7 mod 10) +1） mod 11=0 (冲突 )
武汉理工大学华夏学院 -信息工程系
d2=H(1)=0
H(1)=(0+(1*7 mod 10) +1） mod 11=8 (冲突 )
d3=H(1)=8
H(1)=(8+(1*7 mod 10) +1 )mod 11=5 (冲突 )
d4=H(1)=5
H(1)=(5+(1*7 mod 10) +1 )mod 11=2 (冲突 )
d5=H(1)=2
H(1)=(2+(1*7 mod 10) +1) mod 11=10 (冲突 )
（ 8） H(67)=3*67 mod 11=3 (冲突 )
d1=H(67)=3
H(67)=(3+(7*67 mod 10) +1 )mod 11=2 (冲突 )
d2=H(67)=2
H(67)=(2+(7*67 mod 10) +1) mod 11=1 (冲突 )
武汉理工大学华夏学院 -信息工程系查找的成功的平均查找长度为：
ASL=（ 1?4+2?2+3?1+6?1）?（ 1/8） =2.125
构造哈希表的程序如下：
#include<stdio.h>
#define M 11
#define N 8
{
int key; /*关键字值 */
int si;
};
struct hterm hashlist[M+1];
int I,address,sum,d,x[N+1];
float average;
武汉理工大学华夏学院 -信息工程系
main()
{
for (i=1;i<=M;i++) /*置初值 */
{
hashlist[I].key=0;
hashlist[I].si=0;
}
x[1]=22; x[2]=41; x[3]=53;
x[4]=46; x[5]=30; x[6]=13;
x[7]=1; x[8]=6;
for (i=1;i<=N;i++)
{
sum=0;
address=(3*x[I])%M;
武汉理工大学华夏学院 -信息工程系
d=address;
if (hashlist[address].key==0)
{
hashlist[address].key=x[i];
hashlist[address].si=1;
}
else
{
do /*处理冲突 */
{
d=(d+(x[i]*7) %10+1) %11;
sum=sum+1;
} while (hashlist[d].key!=0);
武汉理工大学华夏学院 -信息工程系
hashlist[d].key=x[i];
hashlist[d].si=1;
} }
printf(“哈希表地址：,)
for (i-0; i<M; i++) printf(“% -4d”,i);
printf(“\”);
printf(“哈希表关键字：” );
for (i=0;i<M;i++) printf(“% -4d”,hashlist[i].key);
printf(“\”);
printf(“搜索长度：,);
for (i=0; i<M; i++) average=average+hashlist[i].si;
average=average/N;
printf(“平均搜索长途,ASL（ %d)=%g”,N,average);
}
武汉理工大学华夏学院 -信息工程系
7.5 查找操作应用举例例 1 （ p249） 例 7.1 画出对长度为 10的有序表进行折半查找的判定树，并求等概率时的平均查找长度。
方法：利用折半查找，将表中的每个结点放在放在二叉排序树的相应位置。
第一次找中点是 m＝ 5 则 d[5]为树根；（第一层）
第二次找中点是左部 m＝ 2 则 d[2]为左子树树根、
右部 m＝ 8 则 d[8]为右子树树根（第二层）
第三次找中点可能有 d[1],d[3],d[6],d[9]
最后为第四层的结点。
构成的判定树为：
武汉理工大学华夏学院 -信息工程系
50
10 30
40 70
60
80
90
100
20
其平均查找长度为：
ASL＝（ 1+2+2+3*4+4*3)/10=29/10=2.9
其余例题见 p250页武汉理工大学华夏学院 -信息工程系小结：
1.查找方法有四种：顺序、索引、树型、散列
2,顺序查找方法简单，对待查序列无要求，但速度慢，
时间复杂度为 o(n)；
3.折半查找是一种常用的方法，速度快
时间复杂度为 o(log2n),但对待查序列要求高；
4,二叉排序树的查找取决于树的高度；
5.哈希查找方法的速度取决于冲突解决的策略，
作业：
P253
7.2,7.3,7.5,7.8,7.11,7.14
