第 8章 查找
数据结构（ C++描述）
目录
8,4 散列查找
8,3 树表查找
8.1 查找的基本概念
8,2 线性表的查找
退出
8.1 查找的基本概念
查找, 也称为检索 。 在我们日常生活中, 随处可见查找
的实例 。 如查找某人的地址, 电话号码；查某单位 45岁
以上职工等, 都属于查找范畴 。 本书中, 我们规定查找
是按关键字进行的, 所谓关键字 (key)是数据元素 (或记
录 )中某个数据项的值, 用它可以标识 (或识别 )一个数据
元素 。 例如, 描述一个考生的信息, 可以包含：考号,
姓名, 性别, 年龄, 家庭住址, 电话号码, 成绩等关键
字 。 但有些关键字不能唯一标识一个数据元素, 而有的
关键字可以唯一标识一个数据元素 。 如刚才的考生信息
中, 姓名不能唯一标识一个数据元素 (因有同名同姓的
人 ),而考号可以唯一标识一个数据元素 (每个考生考号
是唯一的, 不能相同 )。 我们将能唯一标识一个数据元素
的关键字称为主关键字, 而其它关键字称为辅助关键字
或从关键字 。
有了主关键字及关键字后, 我们可以给查找下一个完整
的定义 。 所谓查找, 就是根据给定的值, 在一个表中查
找出其关键字等于给定值的数据元素, 若表中有这样的
元素, 则称查找是成功的, 此时查找的信息为给定整个
数据元素的输出或指出该元素在表中的位置；若表中不
存在这样的记录, 则称查找是不成功的, 或称查找失败,
并可给出相应的提示 。
因为查找是对已存入计算机中的数据所进行的操作, 所
以采用何种查找方法, 首先取决于使用哪种数据结构来
表示, 表,, 即表中结点是按何种方式组织的 。 为了提
高查找速度, 我们经常使用某些特殊的数据结构来组织
表 。 因此在研究各种查找算法时, 我们首先必须弄清这
些算法所要求的数据结构, 特别是存储结构 。
查找有内查找和外查找之分。若整个查找过程全部在内
存进行，则称这样的查找为内查找；反之，若在查找过
程中还需要访问外存，则称之为外查找。我们仅介绍内
查找。
要衡量一种查找算法的优劣, 主要是看要找的值与关键字
的比较次数, 但我们将找到给定值与关键字的比较次数的
平均值来作为衡量一个查找算法好坏的标准, 对于一个含
有 n个元素的表, 查找成功时的平均查找长度可表示为
ASL=, 其中Ｐ i为查找第 i个元素的概率, 且 =1。
一般情形下我们认为查找每个元素的概率相等, Ｃ i为查找
第 i个元素所用到的比较次数 。
要衡量一种查找算法的优劣, 主要是看要找的值与关键字
的比较次数, 但我们将找到给定值与关键字的比较次数的
平均值来作为衡量一个查找算法好坏的标准, 对于一个含
有 n个元素的表, 查找成功时的平均查找长度可表示为
ASL=, 其中Ｐ i为查找第 i个元素的概率, 且 =1。 一般情
形下我们认为查找每个元素的概率相等, Ｃ i为查找第 i个
元素所用到的比较次数 。
??ni iicp1 ?
?
n
i
ip
1
8,2 线性表的查找
8.2.1 顺序查找
1,顺序查找的基本思想
顺序查找是一种最简单的查找方法, 它的基本思想是：
从表的一端开始, 顺序扫描线性表, 依次将扫描到的
结点关键字和待找的值Ｋ相比较, 若相等, 则查找成
功, 若整个表扫描完毕, 仍末找到关键字等于Ｋ的元
素, 则查找失败 。
顺序查找既适用于顺序表, 也适用于链表 。 若用顺序
表, 查找可从前往后扫描, 也可从后往前扫描, 但若
采用单链表, 则只能从前往后扫描 。 另外, 顺序查找
的表中元素可以是无序的 。
下面以顺序表的形式来描述算法。
2,顺序查找算法实现
const int n=maxn //n为表的最大长度
struct node
{…
elemtype key; //key为关键字, 类型设定为 elemtype
};
int seqsearch (node R[n+1],elemtype k) //在表Ｒ
中查找关键字值为Ｋ的元素
{R[0].key=k; int i=n; //从表尾开始向前扫描
while(R[i].key!=k) i--;
return i;}
在函数 seqsearch中, 若返回的值为０表示查找不成功,
否则查找成功 。 函数中查找的范围从Ｒ [n]到Ｒ [１ ]，
Ｒ [０ ]为监视哨, 起两个作用, 其一, 是为了省去判
定 while循环中下标越界的条件 i≥1,从而节省比较时
间, 其二, 保存要找值的副本, 若查找时, 遇到它,
表示查找不成功 。 若算法中不设立监视哨 R[0],程序
花费的时间将会增加, 这时的算法可写为下面形式 。
int seqsearch(node R[n+1],elemtype k)
{int i=n;
while(R[i].key!=k)&&(i>=1) i--;
return i;
}
当然上面算法也可以改成从表头向后扫描, 将监视哨设在右
边, 这种方法请读者自己完成 。
3.顺序查找性能分析
假设在每个位置查找的概率相等, 即有 pi=1/n,由于查
找是从后往前扫描, 则有每个位置的查找比较次数 Cn=1，
Cn-1=2,…, C1=n,于是, 查找成功的平均查找 ASL=
= = =,即它 的时间复杂度为 O(n)。
这就是说, 查找成功的平均比较次数约为表长的一半 。
若 k值不在表中, 则必须进行 n+1次比较之后才能确定查
找失败 。 另处, 从 ASL可知, 当 n较大时, ASL值较大,
查找的效率较低 。
?
?
n
i
iicp
1
?? ??ni n in1 1 )]1([ 21?n
顺序查找的优点是算法简单，对表结构无任何要求，无
论是用向量还是用链表来存放结点，也无论结点之间是
否按关键字有序或无序，它都同样适用。顺序查找的缺
点是查找效率低，当 n较大时，不宜采用顺序查找，而
必须寻求更好的查找方法。
8.2.2二分查找
1.二分查找的基本思想
二分查找，也称折半查找，它是一种高效率的查找方法。
但二分查找有条件限制：要求表必须用向量作存贮结构，
且表中元素必须按关键字有序 (升序或降序均可 )。我们不
妨假设表中元素为升序排列。二分查找的基本思想是：
首先将待查值 K与有序表 R[1]到 R[n]的中点 mid上的关键
字 R[mid].key进行比较，若相等，则查找成功；否则，若
R[mid].key>k, 则在 R[1]到 R[mid-1]中继续查找，若有
R[mid].key<k, 则在 R[mid+1]到 R[n]中继续查找。每通
过一次关键字的比较，区间的长度就缩小一半，区间的
个数就增加一倍，如此不断进行下去，直到找到关键字
为 K的元素；若当前的查找区间为空 (表示查找失败 )。
从上述查找思想可知, 每进行一次关键字比较, 区间数
目增加一倍, 故称为二分 （ 区间一分为二 ）, 而区间长
度缩小一半, 故也称为折半 （ 查找的范围缩小一半 ） 。
2,二分查找算法实现
int binsearch (node R[n+1],elemtype k)
{ int low=1,high=n;
while (low<=high)
{ int mid=(low +high)/2; //取区间中点
if (R[mid].key= =k) return mid; //查找成功
else if (R[mid].key>k)
high=mid-1; //在左子区间中查找
else low=mid+1; } //在右子区间中查找
return 0; } //查找失败
例如, 假 设 给 定 有 序 表 中 关 键 字 为
8,17,25,44,68,77,98,100,115,125,将查找 K=17和 K=120
的情况描述为图 8-1及图 8-2形式 。
[ 8 1 7 2 5 4 4 6 8 7 7 9 8 1 0 1 1 5 1 2 5 ]
low high
(a ) 初始情形
[ 8 17 25 44 ] 68 44 98 10 0 1 15 12 5
lo w hi gh m id
( b ) 经过一次比较后的情形
[8 17 25 44 ] 68 77 98 100 1 15 125
(c ) 经过二次比较后的情形 ( R[m id ], ke y =1 7)
low m id high
图 8 - 1 查找 K=17 的示意图 ( 查找成功 )
[ 8 1 7 2 5 4 4 6 8 7 7 9 8 1 0 0 1 1 5 1 2 5 ]
( a ) 初始情形
lo w h ig h
8 1 7 2 5 4 4 6 8 [ 7 7 9 8 1 0 0 1 1 5 1 2 5 ]
( b ) 经过一次比较后的情形
m id lo w h ig h
8 17 25 44 68 77 98 100 [ 1 15 125 ]
(c) 经过二次比较后的情形
m id low high
8 1 7 2 5 4 4 6 8 7 7 9 8 1 0 0 1 1 5 [ 125 ]
( d ) 经过三次比较后的情形
m id lo w h ig h
17 25 44 77 98 100 1 15 125
high low m id
(e) 经过四次比较后的情形 ( high<low )
图 8 - 2 查找 K =120 的示意图 ( 查找不成功 )
3.二分查找的性能分析
为了分析二分查找的性能, 可以用二叉树来描述二分查找
过程 。 把当前查找区间的中点作为根结点, 左子区间和右
子区间分别作为根的左子树和右子树, 左子区间和右子区
间再按类似的方法, 由此得到的二叉树称为二分查找的判
定树 。 例如, 图 8-1 给定的关键字序列
8,17,25,44,68,77,98,100,115,125,的判定树见图 8-3。
44
8 25
17
98
77
68
100
1 15
125
图 8 - 3 具有 10 个关键字序列的二分查找判定树
从图 8-3 可知, 查找根结点 68,需一次查找, 查找 17和
100,各需二次查找, 查找 8,25,77,115各需三次查
找, 查找 44,98,125各需四次查找 。 于是, 可以得到
结论：二叉树第 K层结点的查找次数各为 k次 (根结点为
第 1层 ),而第 k层结点数最多为 2k-1个 。 假设该二叉树的
深度为 h,则二分查找的成功的平均查找长度为 （ 假设
每个结点的查找概率相等 ）,
?
?
n
i
iicp
1 ?
?
n
i
ic
1
ASL= =1/n ≤1/n（ 1+2?2+3?22+… +h?2h-1）,
因此, 在最坏情形下, 上面的不等号将会成立, 并根据
二叉树的性质, 最大的结点数 n=2h-1,h=log2(n+1), 于是
可以得到平均查找长度 ASL=(n+1)/n log2(n+1)-1。 该公式
可以按如下方法推出：
?
?
?
h
k
kk
1
12设 s= =2
0+2.21+3.22+… +(h-1).2h-2+h.2h-1
则 2s=21+2.22+… +(h-2).2h-2+h-1).2h-1+h.2h
s=2s-s
=h,2h-(20+21+22+… +2h-2+2h-1)
=h,2h-(2h-1)
= log2(n+1).(n+1)-n
所以, ASL=s/n=(n+1)/n log2(n+1)-1。
当 n很大时,ASL? log2(n+1)-1 可以作为二分查找成功
时的平均查找长度，它的时间复杂度为 O(log2n)。
8.2.3 索引查找
1.索引查找的思想
索引查找, 又称分级查找, 它既是一种查找方法, 又是
一种存贮方法, 称为索引存贮 。 它在我们的日常生活中
有着广泛的应用 。 例如, 在汉语字典中查找某个汉字时,
若知道某个汉字读者, 则可以先在音节表中查找到对应
正文中的页码, 然后再在正文中所对应的页中查出待查
的汉字；若知道该汉字的字形, 但不知道读者, 则可以
先在部首表中根据字的部首查找到对应检字表中的页码,
再在检字表中根据字的笔画找到该汉字所在的页码 。 在
这里, 整个字典就是索引查找的对象, 字典的正文是字
典的主要部分, 被称之为主表, 而检字表, 部首表和音
节表都有是为了方便查找主表而建立的索引, 所以被称
之为索引表 。
在索引查找中, 主表只有一个, 其中包含的是待查找的
内容, 而索引表可以有多个, 包含一级索引, 二级索
引 ……, 所需的级数可根据具体问题而定 。 如刚才的利
用读音查找汉字为一级索引, 而 利用字形查找汉字为二
级索引 （ 部首表 → 检字表 → 汉字 ） 。 在此, 我们仅讨论
一级索引 。
索引查找是在线性表 （ 主表 ） 的索引存贮结构上进行的,
而索引存贮的基本思想是：首先将一个线性表 （ 主表 ） 按
照一定的规则分成若干个逻辑上的子表, 并为每个子表分
别建立一个索引项, 由所有这些索引项得到主表的一个索
引表, 然后, 可采用顺序或链接的方法来存储索引表和各
个子表 。 索引表中的每个索引项通常包含三个域：一是索
引值域, 用来存储标识对应子表的索引值, 它相当于记录
的关键字, 在索引表中由此索引值来唯一标识一个索引项
（ 子表 ） ；二是子表的开始位置, 用来存储对应子表的第
一个元素的存储位置；三是子表的长度, 用来存储对应子
表的元素个数 。
例如, 设有一个学校部分教师档案表如表 8-1所示, 设
编号为主关键字, 则该表可以用一个线性表 L=（ a1,a2,
a3,a4,a5,a6,a7,a8,a9,a10） 来表示, 其中 ai (1≤i≤n)表示第 i位
教师的信息 （ 包含有编号, 姓名, 部门, 职称 ）, 而
它的索引表可以按部门进行, 也可以按职称进行, 按
部门的索引表中有 4个子表, 分别为：
计算机系 J=（ a1,a2,a3,a4）
电工系 D=(a5,a6,a7)
管理系 G=(a8,a9)
成教部 C=(a10)
该 4个子表示成一个索引表如表 8-2所示。
表 8-1 教师档案表
编号 姓名 部门 职称
J001 赵一 计算机系 教授
J002 钱二 计算机系 讲师
J003 张三 计算机系 副教授
J004 李四 计算机系 助教
D001 王五 电工系 讲师
D002 孙六 电工系 助教
D003 刘七 电工系 副教授
G001 朱八 管理系 教授
G002 杨九 管理系 讲师
C001 罗十 成教部 副教授
表 8-2 按部门的索引表
J 0 4
D 4 3
G 7 2
C 9 1
index start length
若按职称进行索引, 则得到的索引表中也有 4个子表,
分别为：
Jiaosou=(a1,a8)
FuJiaosou=(a3,a7,a10)
Jiangshi=(a2,a5,a9)
Zhujiao=(a4,a6)
这时的主表用顺序存贮不太方便，因相同职称的教师没
有连在一起，故用链式存储得到主表较方便。具体的存
贮如图 8-4所示。在图 8-4中，箭头上面的数字表示该元
素在主表中的下标位置（指针），每个子表中最后个元
素的指针为 -1，表示为空指针。
a 1
0
a 8
- 1
7
a 4
3
a 6
- 1
5
a 2
1
a 5
4
a 9
- 1
8
a 3
2
a 7
6
a 10
- 1
9
教授
副教授
讲师
助教
图 8 - 4 按职称的链式存贮结构
于是，可以得到如表 8-3所示的职称索引表。
表 8-3 按职称的索引表
index start length
教授 0 2
副教授 2 3
讲师 1 3
助教 3 2
从刚才的两种索引表中, 可以给出索引查找的基本思
想如下：
第一步, 在索引表中按 index域查找所给值 K1,这时可
得到子表起始位置 start 和长度 length,若找不到 K1,结
束查找, 表示查找不成功 。 第二步, 在主表的 start位置
开始, 长度为 length的范围内查找所给值 K2,若找到,
查找不成功, 否则, 查找不成功 。
例如, 对于按部门的索引查找, 主表可以用顺序存贮, 假设
K1=“D”,,D”代电工系, K2=“孙六,, 则先在表 8-2的索引
表中找到的 index域为, D”的项, 得到 start=4,length=3，
然后从主表的第 4个位置开始 （ 即 a5） 找姓名为, 孙六, 的
人, 则在主表的第 5个位置可以找到, 故查找成功 。 若假设
K1=“D”,K2=“杨九,, 则索引表的查找与上面相同, 然后
在主表的第 4个位置开始查找, 没找到, 进入第 5个位置查找,
还没找到进入第 6位置查找, 仍然没找到, 但查找的 length=3，
既只允许 3次查找, 故查找不成功 。 若假设 K1=“F”,K2=“张
三,, 则首先在索引表中就找不到, F”,故无需进入主表进
行查找, 查找不成功 。
3.索引查找的性能分析
由于索引查找中涉及到两方面查找, 第一个是索引表的
查找, 第二个是主表的查找, 假设两种查找都按顺序查
找方式进行, 则索引表的平均查找长度为 (m+1)/2,主表
中的平均查找长度为 （ s+1） /2,(m为索引表的长度, S为
主表中相应子表的长度 ),则索引查找的平均查找长度为：
ASL=(m+1)/2+ (s+1） /2。 若假定每个子表具有相同的长
度, 而主表的长度为 n,则有 n=m.s,这时当 s= 时,
索引查找具有最小的平均查找长度, 即 ASL=1+ 。
从该公式可以看出, 索引查找的 性能优先顺序查找, 但
比二分查找要差, 时间复杂度介于 O(log2 n)~O(n)之间 。
n
n
8.2.4分块查找
1.分块查找 的思想
分块查找实际上就是一种索引查找, 但查找的性能更优
先于索引查找 。 原因是分块查找的索引表是一个有序表,
故可以用二分查找 来代替 顺序查找 实现索引 表的快速
查找 。
具体实现如下：将一个含有 n个元素的主表分成 m个子表,
但要求子表之间元素是按关键字有序排列的, 而子表中
元素可以无序的, 然后建立索引表, 索引表中索引域的
值用每个子表最大关键字代替, 则可以按索引查找思想
找到表中元素 。
例如, 给 定 关 键 字 序 列 如 下,
18,7,26,34,15,42,36,70,60,55,83,90,78,72,74, 假设 m=3,
s=5,即将该序序分成 3个子表, 每个子表有 5 个元素, 则
得到的主表和索引表如图 8-5所 示 。
18 7 26 34 15 42 36 70 60 55 83 90 78 72 74
4 2 7 5 3 1 0 6 8 10 9 11 12 13 14
（ a ） 15 个关键字序列得到的主表
34 0 5
70 5 5
90 10 5
i ndex star t
length
(b) 按关键字序列递增得到的索引表
图 8 - 5 分块查找的主表和索引表
3.分块查找的性能分析
分块查找实际上就是索引查找,但分块查找中索引的域
的类型与主表的关键字域的类型相同, 且索引表按索
引域递增 （ 或递减 ） 有序, 故它的平均查找长度与索
引查找接近, 且优于索引查找 。
8,3 树表查找
8.3.1二叉排序树查找
1,什么是二叉排序树
二叉排序树 （ Binary Sorting Tree）, 它或者是一棵空树,
或者是一棵具有如下特征的非空二叉树：
(1)若它的左子树非空, 则左子树上所有结点的关键字均
小于根结点的关键字；
(2)若它的右子树非空, 则右子树上所有结点的关键字均
大于等于根结点的关键字；
(3)左, 右子树本身又都是一棵二叉排序树 。
2,二叉排序树的数据类型描述
和第六章类似, 可以用一个二叉链表来描述一棵二叉
排序树, 具体为：
struct Btreenode
{ elemtype data; //代表关键字
Btreenode *left,*right; //代表左, 右孩子
};
3．二叉排序树的基本运算
（ 1） 二叉排序树的插入
若二叉排序树为空，则作为根结点插入，否则，若待
插入的值小于根结点值，则作为左子树插入，否则作为
右子树插入，算法描述为：
void Insert (Btreenode *BST,elemtype X )
{ if(BST= =NULL)
{ Btreenode *p= new Btreenode;
p -> data = X;
p->left=p->right=NULL;
BST=p; }
else if (BST->data >= X )
Insert ( BST -> left,X); //在左子树中扦
入
else Insert (BST->right,X); } //在右子树中扦入
（ 2） 二叉排序树的建立
只要反复调用二叉排序树的扦入算法即可，算法描述
为：
Btreenode *Creat (int n) //建立含有 n个结点的二叉
排序树
{ Btreenode *BST= NULL;
for ( int i=1; i<=n; i++)
{ cin>>x; //输入关键字序列
Insert ( BST,x);
}
return BST ;}
例如, 结定关键字序列 79,62,68,90,88,89,17，
5,100,120,生成二叉排序树过程如图 8-6所示 。 （ 注：
二叉排序树与关键字排列顺序有关, 排列顺序不一样,
得到的二叉排序树也不一样 ）
79 62
79
68
62
79
68
62
79
90
88 68
62
79
90
( a) ( b) ( c) ( d) ( e)
88 68
62
79
90
89 89
17 88 68
62
79
90
17
5
88 68
62
79
90
89
(f) (g) (h)
89
17
5
88 68
62
79
90
100
89
17
5
88 68
62
79
90
100
120
图 8 - 6 二叉排序树的生成过程
( i)
( j)
4．二叉排序 树上的查找
（ 1） 二叉排序 树的查找思想
若二叉排树为空, 则查找 失败, 否则, 先拿根结点值与
待查值进行比较, 若相等, 则查找成功, 若根结点值大
于待查值, 则进入左子树重复此步骤, 否则, 进入右子
树重复此步骤, 若在查找过程中遇到二叉排序树的叶子
结点时, 还没有找到待找结点, 则查找不成功 。
（ 2） 二叉排序树查找的算法实现
Btreenode * find( Btreenode *BST,elentype x)
//在以 BST为根指针的二叉排队 树中查找值为 x的结点
{ if ( BST= =NULL)
return NULL; //查找失败
else {
if (BST->data= =x) //查找成功
return BST;
else if (BST->data>x) //进入左子树查找
return find ( BST->left,x);
else //进入右子树查找
return find (BST->right,x);} }
5,二叉排序树查找的性能分析
在二叉排序树查找中, 成功的查找次数不会超过二叉树
的深度, 而具有 n个结点的二叉排序树的深度, 最好为
log2n,最坏为 n。 因此, 二叉排序树查找的最好时间复
杂度为 O(log2n),最坏的时间复杂度为 O(n),一般情形
下, 其时间复杂度大致可看成 O(log2n),比顺序查找效
率要好, 但比二分查找要差 。
8.3.2平衡二叉树查找
1,平衡二叉树的概念
平衡二叉树 (balanced binary tree)是由阿德尔森一维尔斯和
兰迪斯 (Adelson-Velskii and Landis)于 1962年首先提出的,
所以又称为 AVL树 。
若一棵二叉树中每个结点的左、右子树的深度之差的绝
对值不超过 1，则称这样的二叉树为平衡二叉树。将该
结点的左子树深度减去右子树深度的值，称为该结点的
平衡因子 (balance factor)。也就是说，一棵二叉排序树
中，所有结点的平衡因子只能为 0,1,-1时，则该二叉
排序树就是一棵平衡二叉树，否则就不是一棵平衡二叉
树。如图 8-8所示二叉排序树，是一棵平衡二叉树，而
如图 8-9所示二叉 排序树，就不是一棵平衡二叉树。
5
2
3
4
1
2
6
7
图 8 - 8 一棵平衡二叉树
6
1
2
3
4
8
5
7
图 8 - 9 一棵非平衡二叉树
2.非平衡二叉树的平衡处理
若一棵二叉排序树是平衡二叉树，扦入某个结点后，
可能会变成非平衡二叉树，这时，就可以对该二叉
树进行平衡处理，使其变成一棵平衡二叉树。处理
的原则应该是处理与扦入点最近的、而平衡因子又
比 1大或比 -1小的结点。下面将分四种情况讨论平衡
处理。（ 1） LL型 的处理 (左左型 )
如图 8-10所示, 在 C的左孩子 B上扦入一个左孩子结点 A，
使 C的平衡因子由 1变成了 2,成为不平衡的二叉树序树 。
这时的平衡处理为：将 C顺时针旋转, 成为 B的右子树,
而原来 B的右子树则变成 C的左子树, 待扦入结点 A作为 B
的左子树 。 (注：图中结点旁边的数字表示该 结点的平衡
因子 )
平衡外理 1
A
B
C
0
2
C
B
A
0
0 0
图 8 - 10 LL 型平衡外理
（ 2） LR型的处理 (左右型 )
如图 8-11所示, 在 C的左孩子 A上扦入一个右孩子 B，
使的 C的平衡因子由 1变成了 2,成为不平衡的二叉
排序树 。 这是的平衡处理为：将 B变到 A与 C 之间,
使之成为 LL型, 然后按第 (1)种情形 LL型处理 。
0
- 1
C
A
B
2
0
1
C
A
B
2 B
0 0 C A
0
平衡处理 旋转
图 8 - 1 1 L R 型平衡处理
（ 3） RR型的处理 (右右型 )
如图 8-12所示, 在 A的右孩子 B上扦入一个右孩子 C,使
A的平衡因子由 -1变成 -2,成为不平衡的二叉排序树 。
这时的平衡处理为：将 A逆时针旋转, 成为 B的左子树,
而原来 B的左子树则变成 A的右子树, 待扦入结点 C成为
B的右子树 。
平衡处理 - 1
C
B
A
0
- 2
C
B
A
0
0 0
图 8 - 12 RR 型平衡处理
（ 4） RL型的处理 (右左型 )
如 图 8-13所示, 在 A的右孩子 C上扦入一个左孩子 B，
使 A的平衡因子由 -1变成 -2,成为不平衡的二叉排序
树 。 这时的平衡处理为：将 B变到 A与 C之间, 使之
成为 RR型, 然后按第 (3) 种情形 RR型处理 。
平衡处理
C
B
A
0
0 0
图 8 - 13 RL 型平衡处理
- 1
- 2
C
B
A
B 0
1
- 2 A
旋转 C
例 8-2,给定一个关键字序列 4,5,7,2,1,3,6,试生成一棵
平衡二叉树 。
分析：平衡二叉树实际上也是一棵二叉排序树, 故可
以按建立二叉排序树的思想建立, 在建立的过程中,
若遇到不平衡, 则进行相应平衡处理, 最后就可以建
成一棵平衡二叉树 。 具体生成过程见图 8-14。
(a) 插入 4 (b ) 插入 5 (c) 插入 7
RR 型
4 0
4
5 0
- 1
7
4
5
- 2
- 1
0 0
0
4
5
7 0
LL 型
( d ) 插入 2
( e ) 插入 1
4
2
5
7
1
0
0 0
0 0
4
2
5
7
1
0
0
1
2
2
4
2
5
7
0
0 1
1
- 1
5
2
1
4
3
7
2
0
1
0
0
5 2
1
4
3 7
- 1
0
0
0 0 0
LR 型
( f ) 插入 3
5 2
1
4
3 7
- 2
- 1
0
1 0 0
6 0
RL 型 0 6 2
1
4
3
7
0
0
0 0 0 5 0
( g ) 插入 6
图 8 - 14 平衡二叉树的生成过程
3．平衡二叉树的查找及性能分析
平衡二叉树本身就是一棵二叉排序树，故它的查找与二
叉排序树完全相同。但它的查找 性能优于二叉排序树，
不像二叉排序树一样，会出现最坏的时间复杂度 O(n)，
它的时间复杂度与二叉排序树的最好时间复杂相同，都
为 O(log2n)。
例 8-3,对例 8-2给定的关键字序列 4,5,7,2,1,3,6,试用二
叉排序树和平衡二叉树两种方法查找, 给出查找 6的次
数及成功的平均查找长度 。
分析：由于关键字序列的顺序己经确定，故得到的二叉
排序树和平衡二叉树都是唯一的。得到的平衡二叉树见
图 8-14，得到的二叉排序树见图 8-15。
4
2
3 1
5
7
6
图 8 - 15 由关键字序列 4,5,7,2,1,3,6 生成的
二叉排序树
从图 8-15的二叉排序树可知, 查找 6需 4次, 平均查
找长度 ASL=(1+2+2+3+3+3+4)/7=18/7≈2.57。
从图 8-14的平衡二叉树可知, 查找 6需 2次, 平均查
找长度
ASL=(1+2+2+3+3+3+3)=17/7≈2.43。
从结果可知，平衡二叉树的查找性能优于二叉排
序树。
8,4 散列查找
8.4.1 基本概念
散列查找, 也称为哈希查找 。 它既是一种查找方法, 又
是一种存贮方法, 称为散列存贮 。 散列存贮的内存存放
形式也称为散列表 。
散列查找, 与前面介绍的查找方法完全不同, 前面介绍
的所有查找都是基于待查关键字与表中元素进行比较而
实现的查找方法, 而散列查找是通过构造散列函数来得
到待查关键字的地址, 按理论分析真正不需要用到比较
的一种查找方法 。 例如, 要找关键字为 k的元素, 则只需
求出函数值 H（ k）, H（ k） 为给定的散列函数, 代表关
键字 k在存贮区中的地址, 而存贮区为一块连续的内存单
元, 可用一个一维数组 (或链表 )来表示 。
例 8-4,假设有一批关键字序列 18,75,60,43,54,90,46，
给定散列函数 H（ k） =k%13,存贮区的内存地址从 0到
15,则可以得到每个关键字的散列地址为：
H（ 18） =18%13=5
H（ 75） =75%13=10
H（ 60） =60%13=8
H（ 43） =43%13=4
H（ 54） =54%13=2
H（ 90） =90%13=12
H（ 46） =46%13=7
于是, 根据散列地址, 可以将上述 7个关键字序列存贮
到一个一维数组 HT（ 散列表 ） 中, 具体表示为：
5 4 4 3 1 8 4 6 6 0 7 5 9 0
0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4 1 5
HT
其中 HT就是散列存贮的表, 称为散列表 。 从散列表中
查找一个元素相当方便, 例如, 查找 75,只需计算出
H（ 75） =75%13=10,则可以在 HT[10]中找到 75。
上面讨论的散列表是一种理想的情形, 即每一个关键
字对应一个唯一的地址 。 但是有可能出现这样的情形,
两个不同的关键字有可能对应同一个内存地址, 这样,
将导致后放的关键字无法存贮, 我们把这种现象叫做
冲突 （ collision） 。 在散列存贮中, 冲突是很难避免的,
除非构造出的散列函数为线性函数 。 散列函数选得比
较差, 则发生冲突的可能性越大 。 我们把相互发生冲
突的关键字互称为, 同义词, 。
在散列存贮中，若发生冲突，则必须采取特殊的方法
来解决冲突问题，才能使散列查找能顺利进行。虽然
冲突不可避免，但发生冲突的可能性却与三个方面因
素有关。第一是与装填因子 α有关，所谓装填因子是
指散列表中己存入的元素个数 n与散列表的大小 m的比
值，即 α=n/m。当 α越小时，发生冲突的可能性越小，
α越大（最大为 1）时，发生冲突的可能性就越大。但
是，为了减少冲突的发生，不能将 α变得太小，这样
将会造成大量存贮空间的浪费，因此必须兼顾存储空
间和冲突两个方面。第二是与所构造的散列函数有关
(前面己介绍 )。第三是与解决冲突的方法有关，这些
内容后面将再作进一步介绍。
8.4.2 散列函数的构造
散列函数的构造目标是使散列地址尽可能均匀地分布在
散列空间上，同时使计算尽可能简单。具体常用的构造
方法有如下几种：
1,直接定址法
可表示为 H（ k） =a.k+b,其中 a,b均为常数 。
这种方法计算特别简单, 并且不会发生冲突, 但当关
键字分布不连续时, 会出现很多空闲单元, 将造成大
量存贮单元的浪费 。
2,数字分析法
对关键字序列进行分析，取那些位上数字变化多的、频率
大的作为散列函数地址。
例如, 对如下的关键字序列：
430104681015355
430101701128352
430103720818350
430102690605351
430105801226356
．．．．．．通过对上述关键字序列分析, 发现前 5位相同, 第 6、8,10位上的数字变化多些, 若规定地址取 3位, 则散
列函数可取它的第 6,8,10位 。 于是有：
H（ 430104681015355） ＝ 480
H（ 430101701128352） ＝ 101
H（ 430103620805351） ＝ 328
H（ 430102690605351） ＝ 296
H（ 430105801226356） ＝ 502
3,平方取中法
取关键字平方后的中间几位为散列函数地址 。 这是一
种比较常用的散列函数构造方法, 但在选定散列函数
时不一定知道关键字的全部信息, 取其中哪几位也不
一定合适, 而一个数平方后的中间几位数和数的每一
位都相关, 因此, 可以使用随机分布的关键字得到函
数地址 。
如图 8-16中，随机给出一些关键字，并取平方后的第 2到
4位为函数地址。
关键字 （关键字）
2
函数地址
01 00 0 010 000 0 1 0
1 10 0 1 210 000 2 1 0
12 00 1 440 000 4 4 0
1 16 0 1 370 400 3 7 0
20 61 4 310 541 3 1 0
图 8 - 16 利用平方取中法得到散列函数地址
4,折叠法
将关键字分割成位数相同的几部分（最后一部分的位
数可以不同），然后取这几部分的叠加和（舍去进位）
作为散列函数地址，称为折叠法。
例如, 假设关键字为某人身份证号码 430104681015355，
则可以用 4位为一组进行叠加, 即有 5355＋ 8101＋ 1046
＋ 430＝ 14932,舍去高位, 则有 H（ 430104681015355）
＝ 4932为该身份证关键字的散列函数地址 。
5,除留余数法
该方法是用关键字序列中的关键字 k除以散列表长度 m所
得余数作为散列函数的地址，即有 H（ k）＝ k％ m 。
除留余数法计算简单, 适用范围广, 是一种最常使用的
方法 。 这种方法的关键是选取较理想的 m值, 使得每一
个关键字通过该函数转换后映射到散列空间上任一地址
的概率都相等, 从而尽可能减少发生冲突的可能性 。 一
般情形下, m取为一个素数较理想, 并且要求装填因子
α最好是在 0.6∽ 0.9之间, 所以 m最好取 1.1n∽ 1.7n之间
的一个素数较好, 其中 n为散列表中待装元素个数 。
8.4.3 解决冲突的方法
由于散列存贮中选取的散列函数不是线性函数, 故不可避
免地会产生冲突, 下面给出常见的解决冲突方法 。
1,开放定址法
开放定址法就是从发生冲突的那个单元开始, 按照一定
的次序, 从散列表中找出一个空闲的存储单元, 把发生
冲突的待扦入关键字存储到该单元中, 从而解决冲突的
发生 。
在开放定址法中, 散列表中的空闲单元 （ 假设地址为 K）
不仅向散列地址为 K的同义词关键字开放, 即允许它们
使用, 而且还向发生冲突的其它关键字开放 （ 它们的
散列地址不为 K）, 这些关键字称为非同义词关键字 。
例如, 设有关键字序列 14,27,40,15,16,散列函
数为 H（ k） =k%13,则 14,27,40的散列地址都为 1，
因此发生冲突, 即 14,27,40互为同义词, 这时, 假
设处理冲突的方法是从冲突处顺序往后找空闲位置,
找到后放入冲突数据即可 。 则 14放入第 1个位置, 27只
能放入第 2个位置, 40就只能放入第 3个位置, 接着往
后有关键字 15,16要放入散列表中, 而 15,16的散列
地址分别为 2和 3,即 15应放入第 2个位置, 16应放入第
3个位置, 而第 2个位置己放入了 27,第 3个位置己放入
了 40,故也发生冲突, 但这时是非同义词冲突, 即 15
和 27,16和 40相互之间是非同义词 。 这时, 解决冲突
后, 15应放入第 4个位置, 16应放入第 5个位置 。 因此,
在使用开放定址法处理冲突的散列表中, 地址为 K的单
元到底存储的是同义词中的一个关键字, 还是非同义
词关键字, 这就要看谁先占用它 。
在开放定址法中, 解决冲突时具体使用下面一些方法 。
（ 1） 线性探查法
假设散列表的地址为 0∽ m-1,则散列表的长度为 m。 若
一个关键字在地址 d处发生冲突, 则依次探查 d+1，
d+2,…, m-1(当达到表尾 m-1时, 又从 0,1,2,…,开
始探查 )等地址, 直到找到一个空闲位置来装冲突处的
关键字, 将这一种方法称为线性探查法 。 假设发生冲突
时的地址为 d0=H(k),则探查下一位置的公式为 di=(di-
1+1)%m (1≤i≤m-1),最后将冲突位置的关键字存入 di地
址中 。
例 8-5 给定关键字序列为 19,14,23,1,68,20,84,27，
55,11,10,79,散到函数 H（ k） =k%13, 散列表空间地
址为 0∽ 12,试用线性探查法建立散列存贮 (散列表 )结构 。
得到的散列表如图 8-17所示
14 1 68 27 55 19 20 84 79 23 1 1 10
0 1 2 3 4 9 10 7 8 5 6 11 12
图 8 - 17 用线性探查建立的散列表
(2) 平方探查法
该方法规定, 若在 d地址发生冲突, 下一次探查位置为
d+12,d+22,…, 直到找到一个空闲位置为止 。
(3) 双散列函数探查法
该方法使用两个散列函数 H和 T，用 H作散列函数建立散
列存储（散列表），用 T来解决冲突。具体实施时，若
H(k)在 d0位置发生冲突时，即 d0 =H(k)，则下一个探查位
置序列应该是 di=(di-1+T(k))%m (1≤i≤m-1)。
2.拉链法
拉链法也称链地址法，是把相互发生冲突的同义词用
一个单链表链接起来，若干组同义词可以组成若干个
单链表
例 8-6 对例 8-5 给 定 的 关 键 字 序 列
19,14,23,1,68,20,84,27,55,11,10,79, 给 定 散 列 函 数 为
H(k)=k%13,试用拉链法解决冲突建立散列表 。
图 8-18为用尾插法建立的关于例 8-6的拉链法解决冲
突的散列表 。
0
1
2
3
4
5
6
7
8
9
10
11
12
^
^
^
^
^
^
^
14
1
27
79
^
68
55
^
19
84
^
20
^
23
10
^
11
^
图 8 - 18 拉链法解决冲突的散列表
8.4.5 散列查找的性能分析
散列查找按理论分析, 它的时间复杂度应为 O(1),它的
平均查找长度应为 ASL=1,但实际上由于冲突的存在,
它的平均查找长度将会比 1大 。 下面将分析几种方法的
平均查找长度 。
1.线性探查法的性能分析
由于线性探查法解决冲突是线性地查找空闲位置的,
平均查找长度与表的大小 m无关, 只与所选取的散列
函数 H及装填因子 α的值和该处理方法有关, 这时的
成功的平均查找长度为 ASL=1/2 (1+1/(1- α))。,
2.拉链法查找的性能分析
由于拉链法查找就是在单链表上查找，查找单链表
中第一个结点的次数为 1，第二个结点次数为 2，其
余依次类推。它的平均查找长度 ASL=1+α/2。
例 8-7 给定关键字序列 11,78,10,1,3,2,4,21，
试分别用顺序查找, 二分查找, 二叉排序树查找,
平衡二叉树查找, 散列查找 (用线性探查法和拉链法 )
来实现查找, 试画出它们的对应存储形式 (顺序查找
的顺序表, 二分查找的判定树, 二叉排序树查找的
二叉排序树及平衡二叉树查找的平衡二叉树, 两种
散列查找的散列表 ),并求出每一种查找的成功平均
查找长度 。 散列函数 H(k)=k%11。
顺序查找的顺序表（一维数组）如图 8-19所示,
1 1 7 8 1 0 1 3 2 4 2 1
0 1 2 3 4 5 6 7 8 9 10
图 8 - 19 顺序存储的顺序表
从图 8-19可以得到顺序查找的成功平均查找长度为：
ASL=(1+2+3+4+5+6+7+8)/8=4.5；
二分查找的判定树（中序序列为从小到大排列的有序序
列）如图 8-20所示，
4
2
1 3
1 1
10 21
78
图 8 - 20 二分查找的判定树
从图 8-20可以得到二分查找的成功平均查找长度为：
ASL=(1+2*2+3*4+4)/8=2.625；
二叉排序树（关键字顺序已确定，该二叉排序树应唯一）
如图 8-21(a)所示，平衡二叉树（关键字顺序已确定，该
平衡二叉树也应该是唯一的），如图 8-21(b)所示，
1 1
10 78
1
21
3
2 4
3
1 1 1
2 10
4
78
21
( a) 二叉排序树 (b) 平衡二叉树
图 8 - 21 二叉排序树及平衡二叉树
从图 8-21(a)可以得到二叉排序树查找的成功平均查找长度
为：
ASL=(1+2*2+3*2+4+5*2)=3.125；
从图 8-21(b)可以得到平衡二叉树的成功平均查找长度为：
ASL=(1+2*2+3*3+4*2)/8=2.75；
线性探查法解决冲突的散列表如图 8-22所示，
1 1 7 8 1 3 2 4 2 1 1 0
0 1 2 3 4 5 6 7 8 9 1 0
图 8 - 22 线性探查的散列表
从图 8-22可以得到线性探查法的成功平均查找长度为：
ASL=（ 1+1+2+1+3+2+1+8） /8=2.375；
拉链法解决冲突的散列表如图 8-23所示 。
0
1
2
3
4
5
6
7
8
9
10
^
^
^
^
^
1
^ 78
11
^
1
^ 78
2
^
3
^
4
^
图 8 - 23 拉链法的散列表
从图 8-23可以得到拉链法的成功平均查找长度为：
ASL=(1*6+2*2)/8=1.25。
数据结构（ C++描述）
目录
8,4 散列查找
8,3 树表查找
8.1 查找的基本概念
8,2 线性表的查找
退出
8.1 查找的基本概念
查找, 也称为检索 。 在我们日常生活中, 随处可见查找
的实例 。 如查找某人的地址, 电话号码；查某单位 45岁
以上职工等, 都属于查找范畴 。 本书中, 我们规定查找
是按关键字进行的, 所谓关键字 (key)是数据元素 (或记
录 )中某个数据项的值, 用它可以标识 (或识别 )一个数据
元素 。 例如, 描述一个考生的信息, 可以包含：考号,
姓名, 性别, 年龄, 家庭住址, 电话号码, 成绩等关键
字 。 但有些关键字不能唯一标识一个数据元素, 而有的
关键字可以唯一标识一个数据元素 。 如刚才的考生信息
中, 姓名不能唯一标识一个数据元素 (因有同名同姓的
人 ),而考号可以唯一标识一个数据元素 (每个考生考号
是唯一的, 不能相同 )。 我们将能唯一标识一个数据元素
的关键字称为主关键字, 而其它关键字称为辅助关键字
或从关键字 。
有了主关键字及关键字后, 我们可以给查找下一个完整
的定义 。 所谓查找, 就是根据给定的值, 在一个表中查
找出其关键字等于给定值的数据元素, 若表中有这样的
元素, 则称查找是成功的, 此时查找的信息为给定整个
数据元素的输出或指出该元素在表中的位置；若表中不
存在这样的记录, 则称查找是不成功的, 或称查找失败,
并可给出相应的提示 。
因为查找是对已存入计算机中的数据所进行的操作, 所
以采用何种查找方法, 首先取决于使用哪种数据结构来
表示, 表,, 即表中结点是按何种方式组织的 。 为了提
高查找速度, 我们经常使用某些特殊的数据结构来组织
表 。 因此在研究各种查找算法时, 我们首先必须弄清这
些算法所要求的数据结构, 特别是存储结构 。
查找有内查找和外查找之分。若整个查找过程全部在内
存进行，则称这样的查找为内查找；反之，若在查找过
程中还需要访问外存，则称之为外查找。我们仅介绍内
查找。
要衡量一种查找算法的优劣, 主要是看要找的值与关键字
的比较次数, 但我们将找到给定值与关键字的比较次数的
平均值来作为衡量一个查找算法好坏的标准, 对于一个含
有 n个元素的表, 查找成功时的平均查找长度可表示为
ASL=, 其中Ｐ i为查找第 i个元素的概率, 且 =1。
一般情形下我们认为查找每个元素的概率相等, Ｃ i为查找
第 i个元素所用到的比较次数 。
要衡量一种查找算法的优劣, 主要是看要找的值与关键字
的比较次数, 但我们将找到给定值与关键字的比较次数的
平均值来作为衡量一个查找算法好坏的标准, 对于一个含
有 n个元素的表, 查找成功时的平均查找长度可表示为
ASL=, 其中Ｐ i为查找第 i个元素的概率, 且 =1。 一般情
形下我们认为查找每个元素的概率相等, Ｃ i为查找第 i个
元素所用到的比较次数 。
??ni iicp1 ?
?
n
i
ip
1
8,2 线性表的查找
8.2.1 顺序查找
1,顺序查找的基本思想
顺序查找是一种最简单的查找方法, 它的基本思想是：
从表的一端开始, 顺序扫描线性表, 依次将扫描到的
结点关键字和待找的值Ｋ相比较, 若相等, 则查找成
功, 若整个表扫描完毕, 仍末找到关键字等于Ｋ的元
素, 则查找失败 。
顺序查找既适用于顺序表, 也适用于链表 。 若用顺序
表, 查找可从前往后扫描, 也可从后往前扫描, 但若
采用单链表, 则只能从前往后扫描 。 另外, 顺序查找
的表中元素可以是无序的 。
下面以顺序表的形式来描述算法。
2,顺序查找算法实现
const int n=maxn //n为表的最大长度
struct node
{…
elemtype key; //key为关键字, 类型设定为 elemtype
};
int seqsearch (node R[n+1],elemtype k) //在表Ｒ
中查找关键字值为Ｋ的元素
{R[0].key=k; int i=n; //从表尾开始向前扫描
while(R[i].key!=k) i--;
return i;}
在函数 seqsearch中, 若返回的值为０表示查找不成功,
否则查找成功 。 函数中查找的范围从Ｒ [n]到Ｒ [１ ]，
Ｒ [０ ]为监视哨, 起两个作用, 其一, 是为了省去判
定 while循环中下标越界的条件 i≥1,从而节省比较时
间, 其二, 保存要找值的副本, 若查找时, 遇到它,
表示查找不成功 。 若算法中不设立监视哨 R[0],程序
花费的时间将会增加, 这时的算法可写为下面形式 。
int seqsearch(node R[n+1],elemtype k)
{int i=n;
while(R[i].key!=k)&&(i>=1) i--;
return i;
}
当然上面算法也可以改成从表头向后扫描, 将监视哨设在右
边, 这种方法请读者自己完成 。
3.顺序查找性能分析
假设在每个位置查找的概率相等, 即有 pi=1/n,由于查
找是从后往前扫描, 则有每个位置的查找比较次数 Cn=1，
Cn-1=2,…, C1=n,于是, 查找成功的平均查找 ASL=
= = =,即它 的时间复杂度为 O(n)。
这就是说, 查找成功的平均比较次数约为表长的一半 。
若 k值不在表中, 则必须进行 n+1次比较之后才能确定查
找失败 。 另处, 从 ASL可知, 当 n较大时, ASL值较大,
查找的效率较低 。
?
?
n
i
iicp
1
?? ??ni n in1 1 )]1([ 21?n
顺序查找的优点是算法简单，对表结构无任何要求，无
论是用向量还是用链表来存放结点，也无论结点之间是
否按关键字有序或无序，它都同样适用。顺序查找的缺
点是查找效率低，当 n较大时，不宜采用顺序查找，而
必须寻求更好的查找方法。
8.2.2二分查找
1.二分查找的基本思想
二分查找，也称折半查找，它是一种高效率的查找方法。
但二分查找有条件限制：要求表必须用向量作存贮结构，
且表中元素必须按关键字有序 (升序或降序均可 )。我们不
妨假设表中元素为升序排列。二分查找的基本思想是：
首先将待查值 K与有序表 R[1]到 R[n]的中点 mid上的关键
字 R[mid].key进行比较，若相等，则查找成功；否则，若
R[mid].key>k, 则在 R[1]到 R[mid-1]中继续查找，若有
R[mid].key<k, 则在 R[mid+1]到 R[n]中继续查找。每通
过一次关键字的比较，区间的长度就缩小一半，区间的
个数就增加一倍，如此不断进行下去，直到找到关键字
为 K的元素；若当前的查找区间为空 (表示查找失败 )。
从上述查找思想可知, 每进行一次关键字比较, 区间数
目增加一倍, 故称为二分 （ 区间一分为二 ）, 而区间长
度缩小一半, 故也称为折半 （ 查找的范围缩小一半 ） 。
2,二分查找算法实现
int binsearch (node R[n+1],elemtype k)
{ int low=1,high=n;
while (low<=high)
{ int mid=(low +high)/2; //取区间中点
if (R[mid].key= =k) return mid; //查找成功
else if (R[mid].key>k)
high=mid-1; //在左子区间中查找
else low=mid+1; } //在右子区间中查找
return 0; } //查找失败
例如, 假 设 给 定 有 序 表 中 关 键 字 为
8,17,25,44,68,77,98,100,115,125,将查找 K=17和 K=120
的情况描述为图 8-1及图 8-2形式 。
[ 8 1 7 2 5 4 4 6 8 7 7 9 8 1 0 1 1 5 1 2 5 ]
low high
(a ) 初始情形
[ 8 17 25 44 ] 68 44 98 10 0 1 15 12 5
lo w hi gh m id
( b ) 经过一次比较后的情形
[8 17 25 44 ] 68 77 98 100 1 15 125
(c ) 经过二次比较后的情形 ( R[m id ], ke y =1 7)
low m id high
图 8 - 1 查找 K=17 的示意图 ( 查找成功 )
[ 8 1 7 2 5 4 4 6 8 7 7 9 8 1 0 0 1 1 5 1 2 5 ]
( a ) 初始情形
lo w h ig h
8 1 7 2 5 4 4 6 8 [ 7 7 9 8 1 0 0 1 1 5 1 2 5 ]
( b ) 经过一次比较后的情形
m id lo w h ig h
8 17 25 44 68 77 98 100 [ 1 15 125 ]
(c) 经过二次比较后的情形
m id low high
8 1 7 2 5 4 4 6 8 7 7 9 8 1 0 0 1 1 5 [ 125 ]
( d ) 经过三次比较后的情形
m id lo w h ig h
17 25 44 77 98 100 1 15 125
high low m id
(e) 经过四次比较后的情形 ( high<low )
图 8 - 2 查找 K =120 的示意图 ( 查找不成功 )
3.二分查找的性能分析
为了分析二分查找的性能, 可以用二叉树来描述二分查找
过程 。 把当前查找区间的中点作为根结点, 左子区间和右
子区间分别作为根的左子树和右子树, 左子区间和右子区
间再按类似的方法, 由此得到的二叉树称为二分查找的判
定树 。 例如, 图 8-1 给定的关键字序列
8,17,25,44,68,77,98,100,115,125,的判定树见图 8-3。
44
8 25
17
98
77
68
100
1 15
125
图 8 - 3 具有 10 个关键字序列的二分查找判定树
从图 8-3 可知, 查找根结点 68,需一次查找, 查找 17和
100,各需二次查找, 查找 8,25,77,115各需三次查
找, 查找 44,98,125各需四次查找 。 于是, 可以得到
结论：二叉树第 K层结点的查找次数各为 k次 (根结点为
第 1层 ),而第 k层结点数最多为 2k-1个 。 假设该二叉树的
深度为 h,则二分查找的成功的平均查找长度为 （ 假设
每个结点的查找概率相等 ）,
?
?
n
i
iicp
1 ?
?
n
i
ic
1
ASL= =1/n ≤1/n（ 1+2?2+3?22+… +h?2h-1）,
因此, 在最坏情形下, 上面的不等号将会成立, 并根据
二叉树的性质, 最大的结点数 n=2h-1,h=log2(n+1), 于是
可以得到平均查找长度 ASL=(n+1)/n log2(n+1)-1。 该公式
可以按如下方法推出：
?
?
?
h
k
kk
1
12设 s= =2
0+2.21+3.22+… +(h-1).2h-2+h.2h-1
则 2s=21+2.22+… +(h-2).2h-2+h-1).2h-1+h.2h
s=2s-s
=h,2h-(20+21+22+… +2h-2+2h-1)
=h,2h-(2h-1)
= log2(n+1).(n+1)-n
所以, ASL=s/n=(n+1)/n log2(n+1)-1。
当 n很大时,ASL? log2(n+1)-1 可以作为二分查找成功
时的平均查找长度，它的时间复杂度为 O(log2n)。
8.2.3 索引查找
1.索引查找的思想
索引查找, 又称分级查找, 它既是一种查找方法, 又是
一种存贮方法, 称为索引存贮 。 它在我们的日常生活中
有着广泛的应用 。 例如, 在汉语字典中查找某个汉字时,
若知道某个汉字读者, 则可以先在音节表中查找到对应
正文中的页码, 然后再在正文中所对应的页中查出待查
的汉字；若知道该汉字的字形, 但不知道读者, 则可以
先在部首表中根据字的部首查找到对应检字表中的页码,
再在检字表中根据字的笔画找到该汉字所在的页码 。 在
这里, 整个字典就是索引查找的对象, 字典的正文是字
典的主要部分, 被称之为主表, 而检字表, 部首表和音
节表都有是为了方便查找主表而建立的索引, 所以被称
之为索引表 。
在索引查找中, 主表只有一个, 其中包含的是待查找的
内容, 而索引表可以有多个, 包含一级索引, 二级索
引 ……, 所需的级数可根据具体问题而定 。 如刚才的利
用读音查找汉字为一级索引, 而 利用字形查找汉字为二
级索引 （ 部首表 → 检字表 → 汉字 ） 。 在此, 我们仅讨论
一级索引 。
索引查找是在线性表 （ 主表 ） 的索引存贮结构上进行的,
而索引存贮的基本思想是：首先将一个线性表 （ 主表 ） 按
照一定的规则分成若干个逻辑上的子表, 并为每个子表分
别建立一个索引项, 由所有这些索引项得到主表的一个索
引表, 然后, 可采用顺序或链接的方法来存储索引表和各
个子表 。 索引表中的每个索引项通常包含三个域：一是索
引值域, 用来存储标识对应子表的索引值, 它相当于记录
的关键字, 在索引表中由此索引值来唯一标识一个索引项
（ 子表 ） ；二是子表的开始位置, 用来存储对应子表的第
一个元素的存储位置；三是子表的长度, 用来存储对应子
表的元素个数 。
例如, 设有一个学校部分教师档案表如表 8-1所示, 设
编号为主关键字, 则该表可以用一个线性表 L=（ a1,a2,
a3,a4,a5,a6,a7,a8,a9,a10） 来表示, 其中 ai (1≤i≤n)表示第 i位
教师的信息 （ 包含有编号, 姓名, 部门, 职称 ）, 而
它的索引表可以按部门进行, 也可以按职称进行, 按
部门的索引表中有 4个子表, 分别为：
计算机系 J=（ a1,a2,a3,a4）
电工系 D=(a5,a6,a7)
管理系 G=(a8,a9)
成教部 C=(a10)
该 4个子表示成一个索引表如表 8-2所示。
表 8-1 教师档案表
编号 姓名 部门 职称
J001 赵一 计算机系 教授
J002 钱二 计算机系 讲师
J003 张三 计算机系 副教授
J004 李四 计算机系 助教
D001 王五 电工系 讲师
D002 孙六 电工系 助教
D003 刘七 电工系 副教授
G001 朱八 管理系 教授
G002 杨九 管理系 讲师
C001 罗十 成教部 副教授
表 8-2 按部门的索引表
J 0 4
D 4 3
G 7 2
C 9 1
index start length
若按职称进行索引, 则得到的索引表中也有 4个子表,
分别为：
Jiaosou=(a1,a8)
FuJiaosou=(a3,a7,a10)
Jiangshi=(a2,a5,a9)
Zhujiao=(a4,a6)
这时的主表用顺序存贮不太方便，因相同职称的教师没
有连在一起，故用链式存储得到主表较方便。具体的存
贮如图 8-4所示。在图 8-4中，箭头上面的数字表示该元
素在主表中的下标位置（指针），每个子表中最后个元
素的指针为 -1，表示为空指针。
a 1
0
a 8
- 1
7
a 4
3
a 6
- 1
5
a 2
1
a 5
4
a 9
- 1
8
a 3
2
a 7
6
a 10
- 1
9
教授
副教授
讲师
助教
图 8 - 4 按职称的链式存贮结构
于是，可以得到如表 8-3所示的职称索引表。
表 8-3 按职称的索引表
index start length
教授 0 2
副教授 2 3
讲师 1 3
助教 3 2
从刚才的两种索引表中, 可以给出索引查找的基本思
想如下：
第一步, 在索引表中按 index域查找所给值 K1,这时可
得到子表起始位置 start 和长度 length,若找不到 K1,结
束查找, 表示查找不成功 。 第二步, 在主表的 start位置
开始, 长度为 length的范围内查找所给值 K2,若找到,
查找不成功, 否则, 查找不成功 。
例如, 对于按部门的索引查找, 主表可以用顺序存贮, 假设
K1=“D”,,D”代电工系, K2=“孙六,, 则先在表 8-2的索引
表中找到的 index域为, D”的项, 得到 start=4,length=3，
然后从主表的第 4个位置开始 （ 即 a5） 找姓名为, 孙六, 的
人, 则在主表的第 5个位置可以找到, 故查找成功 。 若假设
K1=“D”,K2=“杨九,, 则索引表的查找与上面相同, 然后
在主表的第 4个位置开始查找, 没找到, 进入第 5个位置查找,
还没找到进入第 6位置查找, 仍然没找到, 但查找的 length=3，
既只允许 3次查找, 故查找不成功 。 若假设 K1=“F”,K2=“张
三,, 则首先在索引表中就找不到, F”,故无需进入主表进
行查找, 查找不成功 。
3.索引查找的性能分析
由于索引查找中涉及到两方面查找, 第一个是索引表的
查找, 第二个是主表的查找, 假设两种查找都按顺序查
找方式进行, 则索引表的平均查找长度为 (m+1)/2,主表
中的平均查找长度为 （ s+1） /2,(m为索引表的长度, S为
主表中相应子表的长度 ),则索引查找的平均查找长度为：
ASL=(m+1)/2+ (s+1） /2。 若假定每个子表具有相同的长
度, 而主表的长度为 n,则有 n=m.s,这时当 s= 时,
索引查找具有最小的平均查找长度, 即 ASL=1+ 。
从该公式可以看出, 索引查找的 性能优先顺序查找, 但
比二分查找要差, 时间复杂度介于 O(log2 n)~O(n)之间 。
n
n
8.2.4分块查找
1.分块查找 的思想
分块查找实际上就是一种索引查找, 但查找的性能更优
先于索引查找 。 原因是分块查找的索引表是一个有序表,
故可以用二分查找 来代替 顺序查找 实现索引 表的快速
查找 。
具体实现如下：将一个含有 n个元素的主表分成 m个子表,
但要求子表之间元素是按关键字有序排列的, 而子表中
元素可以无序的, 然后建立索引表, 索引表中索引域的
值用每个子表最大关键字代替, 则可以按索引查找思想
找到表中元素 。
例如, 给 定 关 键 字 序 列 如 下,
18,7,26,34,15,42,36,70,60,55,83,90,78,72,74, 假设 m=3,
s=5,即将该序序分成 3个子表, 每个子表有 5 个元素, 则
得到的主表和索引表如图 8-5所 示 。
18 7 26 34 15 42 36 70 60 55 83 90 78 72 74
4 2 7 5 3 1 0 6 8 10 9 11 12 13 14
（ a ） 15 个关键字序列得到的主表
34 0 5
70 5 5
90 10 5
i ndex star t
length
(b) 按关键字序列递增得到的索引表
图 8 - 5 分块查找的主表和索引表
3.分块查找的性能分析
分块查找实际上就是索引查找,但分块查找中索引的域
的类型与主表的关键字域的类型相同, 且索引表按索
引域递增 （ 或递减 ） 有序, 故它的平均查找长度与索
引查找接近, 且优于索引查找 。
8,3 树表查找
8.3.1二叉排序树查找
1,什么是二叉排序树
二叉排序树 （ Binary Sorting Tree）, 它或者是一棵空树,
或者是一棵具有如下特征的非空二叉树：
(1)若它的左子树非空, 则左子树上所有结点的关键字均
小于根结点的关键字；
(2)若它的右子树非空, 则右子树上所有结点的关键字均
大于等于根结点的关键字；
(3)左, 右子树本身又都是一棵二叉排序树 。
2,二叉排序树的数据类型描述
和第六章类似, 可以用一个二叉链表来描述一棵二叉
排序树, 具体为：
struct Btreenode
{ elemtype data; //代表关键字
Btreenode *left,*right; //代表左, 右孩子
};
3．二叉排序树的基本运算
（ 1） 二叉排序树的插入
若二叉排序树为空，则作为根结点插入，否则，若待
插入的值小于根结点值，则作为左子树插入，否则作为
右子树插入，算法描述为：
void Insert (Btreenode *BST,elemtype X )
{ if(BST= =NULL)
{ Btreenode *p= new Btreenode;
p -> data = X;
p->left=p->right=NULL;
BST=p; }
else if (BST->data >= X )
Insert ( BST -> left,X); //在左子树中扦
入
else Insert (BST->right,X); } //在右子树中扦入
（ 2） 二叉排序树的建立
只要反复调用二叉排序树的扦入算法即可，算法描述
为：
Btreenode *Creat (int n) //建立含有 n个结点的二叉
排序树
{ Btreenode *BST= NULL;
for ( int i=1; i<=n; i++)
{ cin>>x; //输入关键字序列
Insert ( BST,x);
}
return BST ;}
例如, 结定关键字序列 79,62,68,90,88,89,17，
5,100,120,生成二叉排序树过程如图 8-6所示 。 （ 注：
二叉排序树与关键字排列顺序有关, 排列顺序不一样,
得到的二叉排序树也不一样 ）
79 62
79
68
62
79
68
62
79
90
88 68
62
79
90
( a) ( b) ( c) ( d) ( e)
88 68
62
79
90
89 89
17 88 68
62
79
90
17
5
88 68
62
79
90
89
(f) (g) (h)
89
17
5
88 68
62
79
90
100
89
17
5
88 68
62
79
90
100
120
图 8 - 6 二叉排序树的生成过程
( i)
( j)
4．二叉排序 树上的查找
（ 1） 二叉排序 树的查找思想
若二叉排树为空, 则查找 失败, 否则, 先拿根结点值与
待查值进行比较, 若相等, 则查找成功, 若根结点值大
于待查值, 则进入左子树重复此步骤, 否则, 进入右子
树重复此步骤, 若在查找过程中遇到二叉排序树的叶子
结点时, 还没有找到待找结点, 则查找不成功 。
（ 2） 二叉排序树查找的算法实现
Btreenode * find( Btreenode *BST,elentype x)
//在以 BST为根指针的二叉排队 树中查找值为 x的结点
{ if ( BST= =NULL)
return NULL; //查找失败
else {
if (BST->data= =x) //查找成功
return BST;
else if (BST->data>x) //进入左子树查找
return find ( BST->left,x);
else //进入右子树查找
return find (BST->right,x);} }
5,二叉排序树查找的性能分析
在二叉排序树查找中, 成功的查找次数不会超过二叉树
的深度, 而具有 n个结点的二叉排序树的深度, 最好为
log2n,最坏为 n。 因此, 二叉排序树查找的最好时间复
杂度为 O(log2n),最坏的时间复杂度为 O(n),一般情形
下, 其时间复杂度大致可看成 O(log2n),比顺序查找效
率要好, 但比二分查找要差 。
8.3.2平衡二叉树查找
1,平衡二叉树的概念
平衡二叉树 (balanced binary tree)是由阿德尔森一维尔斯和
兰迪斯 (Adelson-Velskii and Landis)于 1962年首先提出的,
所以又称为 AVL树 。
若一棵二叉树中每个结点的左、右子树的深度之差的绝
对值不超过 1，则称这样的二叉树为平衡二叉树。将该
结点的左子树深度减去右子树深度的值，称为该结点的
平衡因子 (balance factor)。也就是说，一棵二叉排序树
中，所有结点的平衡因子只能为 0,1,-1时，则该二叉
排序树就是一棵平衡二叉树，否则就不是一棵平衡二叉
树。如图 8-8所示二叉排序树，是一棵平衡二叉树，而
如图 8-9所示二叉 排序树，就不是一棵平衡二叉树。
5
2
3
4
1
2
6
7
图 8 - 8 一棵平衡二叉树
6
1
2
3
4
8
5
7
图 8 - 9 一棵非平衡二叉树
2.非平衡二叉树的平衡处理
若一棵二叉排序树是平衡二叉树，扦入某个结点后，
可能会变成非平衡二叉树，这时，就可以对该二叉
树进行平衡处理，使其变成一棵平衡二叉树。处理
的原则应该是处理与扦入点最近的、而平衡因子又
比 1大或比 -1小的结点。下面将分四种情况讨论平衡
处理。（ 1） LL型 的处理 (左左型 )
如图 8-10所示, 在 C的左孩子 B上扦入一个左孩子结点 A，
使 C的平衡因子由 1变成了 2,成为不平衡的二叉树序树 。
这时的平衡处理为：将 C顺时针旋转, 成为 B的右子树,
而原来 B的右子树则变成 C的左子树, 待扦入结点 A作为 B
的左子树 。 (注：图中结点旁边的数字表示该 结点的平衡
因子 )
平衡外理 1
A
B
C
0
2
C
B
A
0
0 0
图 8 - 10 LL 型平衡外理
（ 2） LR型的处理 (左右型 )
如图 8-11所示, 在 C的左孩子 A上扦入一个右孩子 B，
使的 C的平衡因子由 1变成了 2,成为不平衡的二叉
排序树 。 这是的平衡处理为：将 B变到 A与 C 之间,
使之成为 LL型, 然后按第 (1)种情形 LL型处理 。
0
- 1
C
A
B
2
0
1
C
A
B
2 B
0 0 C A
0
平衡处理 旋转
图 8 - 1 1 L R 型平衡处理
（ 3） RR型的处理 (右右型 )
如图 8-12所示, 在 A的右孩子 B上扦入一个右孩子 C,使
A的平衡因子由 -1变成 -2,成为不平衡的二叉排序树 。
这时的平衡处理为：将 A逆时针旋转, 成为 B的左子树,
而原来 B的左子树则变成 A的右子树, 待扦入结点 C成为
B的右子树 。
平衡处理 - 1
C
B
A
0
- 2
C
B
A
0
0 0
图 8 - 12 RR 型平衡处理
（ 4） RL型的处理 (右左型 )
如 图 8-13所示, 在 A的右孩子 C上扦入一个左孩子 B，
使 A的平衡因子由 -1变成 -2,成为不平衡的二叉排序
树 。 这时的平衡处理为：将 B变到 A与 C之间, 使之
成为 RR型, 然后按第 (3) 种情形 RR型处理 。
平衡处理
C
B
A
0
0 0
图 8 - 13 RL 型平衡处理
- 1
- 2
C
B
A
B 0
1
- 2 A
旋转 C
例 8-2,给定一个关键字序列 4,5,7,2,1,3,6,试生成一棵
平衡二叉树 。
分析：平衡二叉树实际上也是一棵二叉排序树, 故可
以按建立二叉排序树的思想建立, 在建立的过程中,
若遇到不平衡, 则进行相应平衡处理, 最后就可以建
成一棵平衡二叉树 。 具体生成过程见图 8-14。
(a) 插入 4 (b ) 插入 5 (c) 插入 7
RR 型
4 0
4
5 0
- 1
7
4
5
- 2
- 1
0 0
0
4
5
7 0
LL 型
( d ) 插入 2
( e ) 插入 1
4
2
5
7
1
0
0 0
0 0
4
2
5
7
1
0
0
1
2
2
4
2
5
7
0
0 1
1
- 1
5
2
1
4
3
7
2
0
1
0
0
5 2
1
4
3 7
- 1
0
0
0 0 0
LR 型
( f ) 插入 3
5 2
1
4
3 7
- 2
- 1
0
1 0 0
6 0
RL 型 0 6 2
1
4
3
7
0
0
0 0 0 5 0
( g ) 插入 6
图 8 - 14 平衡二叉树的生成过程
3．平衡二叉树的查找及性能分析
平衡二叉树本身就是一棵二叉排序树，故它的查找与二
叉排序树完全相同。但它的查找 性能优于二叉排序树，
不像二叉排序树一样，会出现最坏的时间复杂度 O(n)，
它的时间复杂度与二叉排序树的最好时间复杂相同，都
为 O(log2n)。
例 8-3,对例 8-2给定的关键字序列 4,5,7,2,1,3,6,试用二
叉排序树和平衡二叉树两种方法查找, 给出查找 6的次
数及成功的平均查找长度 。
分析：由于关键字序列的顺序己经确定，故得到的二叉
排序树和平衡二叉树都是唯一的。得到的平衡二叉树见
图 8-14，得到的二叉排序树见图 8-15。
4
2
3 1
5
7
6
图 8 - 15 由关键字序列 4,5,7,2,1,3,6 生成的
二叉排序树
从图 8-15的二叉排序树可知, 查找 6需 4次, 平均查
找长度 ASL=(1+2+2+3+3+3+4)/7=18/7≈2.57。
从图 8-14的平衡二叉树可知, 查找 6需 2次, 平均查
找长度
ASL=(1+2+2+3+3+3+3)=17/7≈2.43。
从结果可知，平衡二叉树的查找性能优于二叉排
序树。
8,4 散列查找
8.4.1 基本概念
散列查找, 也称为哈希查找 。 它既是一种查找方法, 又
是一种存贮方法, 称为散列存贮 。 散列存贮的内存存放
形式也称为散列表 。
散列查找, 与前面介绍的查找方法完全不同, 前面介绍
的所有查找都是基于待查关键字与表中元素进行比较而
实现的查找方法, 而散列查找是通过构造散列函数来得
到待查关键字的地址, 按理论分析真正不需要用到比较
的一种查找方法 。 例如, 要找关键字为 k的元素, 则只需
求出函数值 H（ k）, H（ k） 为给定的散列函数, 代表关
键字 k在存贮区中的地址, 而存贮区为一块连续的内存单
元, 可用一个一维数组 (或链表 )来表示 。
例 8-4,假设有一批关键字序列 18,75,60,43,54,90,46，
给定散列函数 H（ k） =k%13,存贮区的内存地址从 0到
15,则可以得到每个关键字的散列地址为：
H（ 18） =18%13=5
H（ 75） =75%13=10
H（ 60） =60%13=8
H（ 43） =43%13=4
H（ 54） =54%13=2
H（ 90） =90%13=12
H（ 46） =46%13=7
于是, 根据散列地址, 可以将上述 7个关键字序列存贮
到一个一维数组 HT（ 散列表 ） 中, 具体表示为：
5 4 4 3 1 8 4 6 6 0 7 5 9 0
0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4 1 5
HT
其中 HT就是散列存贮的表, 称为散列表 。 从散列表中
查找一个元素相当方便, 例如, 查找 75,只需计算出
H（ 75） =75%13=10,则可以在 HT[10]中找到 75。
上面讨论的散列表是一种理想的情形, 即每一个关键
字对应一个唯一的地址 。 但是有可能出现这样的情形,
两个不同的关键字有可能对应同一个内存地址, 这样,
将导致后放的关键字无法存贮, 我们把这种现象叫做
冲突 （ collision） 。 在散列存贮中, 冲突是很难避免的,
除非构造出的散列函数为线性函数 。 散列函数选得比
较差, 则发生冲突的可能性越大 。 我们把相互发生冲
突的关键字互称为, 同义词, 。
在散列存贮中，若发生冲突，则必须采取特殊的方法
来解决冲突问题，才能使散列查找能顺利进行。虽然
冲突不可避免，但发生冲突的可能性却与三个方面因
素有关。第一是与装填因子 α有关，所谓装填因子是
指散列表中己存入的元素个数 n与散列表的大小 m的比
值，即 α=n/m。当 α越小时，发生冲突的可能性越小，
α越大（最大为 1）时，发生冲突的可能性就越大。但
是，为了减少冲突的发生，不能将 α变得太小，这样
将会造成大量存贮空间的浪费，因此必须兼顾存储空
间和冲突两个方面。第二是与所构造的散列函数有关
(前面己介绍 )。第三是与解决冲突的方法有关，这些
内容后面将再作进一步介绍。
8.4.2 散列函数的构造
散列函数的构造目标是使散列地址尽可能均匀地分布在
散列空间上，同时使计算尽可能简单。具体常用的构造
方法有如下几种：
1,直接定址法
可表示为 H（ k） =a.k+b,其中 a,b均为常数 。
这种方法计算特别简单, 并且不会发生冲突, 但当关
键字分布不连续时, 会出现很多空闲单元, 将造成大
量存贮单元的浪费 。
2,数字分析法
对关键字序列进行分析，取那些位上数字变化多的、频率
大的作为散列函数地址。
例如, 对如下的关键字序列：
430104681015355
430101701128352
430103720818350
430102690605351
430105801226356
．．．．．．通过对上述关键字序列分析, 发现前 5位相同, 第 6、8,10位上的数字变化多些, 若规定地址取 3位, 则散
列函数可取它的第 6,8,10位 。 于是有：
H（ 430104681015355） ＝ 480
H（ 430101701128352） ＝ 101
H（ 430103620805351） ＝ 328
H（ 430102690605351） ＝ 296
H（ 430105801226356） ＝ 502
3,平方取中法
取关键字平方后的中间几位为散列函数地址 。 这是一
种比较常用的散列函数构造方法, 但在选定散列函数
时不一定知道关键字的全部信息, 取其中哪几位也不
一定合适, 而一个数平方后的中间几位数和数的每一
位都相关, 因此, 可以使用随机分布的关键字得到函
数地址 。
如图 8-16中，随机给出一些关键字，并取平方后的第 2到
4位为函数地址。
关键字 （关键字）
2
函数地址
01 00 0 010 000 0 1 0
1 10 0 1 210 000 2 1 0
12 00 1 440 000 4 4 0
1 16 0 1 370 400 3 7 0
20 61 4 310 541 3 1 0
图 8 - 16 利用平方取中法得到散列函数地址
4,折叠法
将关键字分割成位数相同的几部分（最后一部分的位
数可以不同），然后取这几部分的叠加和（舍去进位）
作为散列函数地址，称为折叠法。
例如, 假设关键字为某人身份证号码 430104681015355，
则可以用 4位为一组进行叠加, 即有 5355＋ 8101＋ 1046
＋ 430＝ 14932,舍去高位, 则有 H（ 430104681015355）
＝ 4932为该身份证关键字的散列函数地址 。
5,除留余数法
该方法是用关键字序列中的关键字 k除以散列表长度 m所
得余数作为散列函数的地址，即有 H（ k）＝ k％ m 。
除留余数法计算简单, 适用范围广, 是一种最常使用的
方法 。 这种方法的关键是选取较理想的 m值, 使得每一
个关键字通过该函数转换后映射到散列空间上任一地址
的概率都相等, 从而尽可能减少发生冲突的可能性 。 一
般情形下, m取为一个素数较理想, 并且要求装填因子
α最好是在 0.6∽ 0.9之间, 所以 m最好取 1.1n∽ 1.7n之间
的一个素数较好, 其中 n为散列表中待装元素个数 。
8.4.3 解决冲突的方法
由于散列存贮中选取的散列函数不是线性函数, 故不可避
免地会产生冲突, 下面给出常见的解决冲突方法 。
1,开放定址法
开放定址法就是从发生冲突的那个单元开始, 按照一定
的次序, 从散列表中找出一个空闲的存储单元, 把发生
冲突的待扦入关键字存储到该单元中, 从而解决冲突的
发生 。
在开放定址法中, 散列表中的空闲单元 （ 假设地址为 K）
不仅向散列地址为 K的同义词关键字开放, 即允许它们
使用, 而且还向发生冲突的其它关键字开放 （ 它们的
散列地址不为 K）, 这些关键字称为非同义词关键字 。
例如, 设有关键字序列 14,27,40,15,16,散列函
数为 H（ k） =k%13,则 14,27,40的散列地址都为 1，
因此发生冲突, 即 14,27,40互为同义词, 这时, 假
设处理冲突的方法是从冲突处顺序往后找空闲位置,
找到后放入冲突数据即可 。 则 14放入第 1个位置, 27只
能放入第 2个位置, 40就只能放入第 3个位置, 接着往
后有关键字 15,16要放入散列表中, 而 15,16的散列
地址分别为 2和 3,即 15应放入第 2个位置, 16应放入第
3个位置, 而第 2个位置己放入了 27,第 3个位置己放入
了 40,故也发生冲突, 但这时是非同义词冲突, 即 15
和 27,16和 40相互之间是非同义词 。 这时, 解决冲突
后, 15应放入第 4个位置, 16应放入第 5个位置 。 因此,
在使用开放定址法处理冲突的散列表中, 地址为 K的单
元到底存储的是同义词中的一个关键字, 还是非同义
词关键字, 这就要看谁先占用它 。
在开放定址法中, 解决冲突时具体使用下面一些方法 。
（ 1） 线性探查法
假设散列表的地址为 0∽ m-1,则散列表的长度为 m。 若
一个关键字在地址 d处发生冲突, 则依次探查 d+1，
d+2,…, m-1(当达到表尾 m-1时, 又从 0,1,2,…,开
始探查 )等地址, 直到找到一个空闲位置来装冲突处的
关键字, 将这一种方法称为线性探查法 。 假设发生冲突
时的地址为 d0=H(k),则探查下一位置的公式为 di=(di-
1+1)%m (1≤i≤m-1),最后将冲突位置的关键字存入 di地
址中 。
例 8-5 给定关键字序列为 19,14,23,1,68,20,84,27，
55,11,10,79,散到函数 H（ k） =k%13, 散列表空间地
址为 0∽ 12,试用线性探查法建立散列存贮 (散列表 )结构 。
得到的散列表如图 8-17所示
14 1 68 27 55 19 20 84 79 23 1 1 10
0 1 2 3 4 9 10 7 8 5 6 11 12
图 8 - 17 用线性探查建立的散列表
(2) 平方探查法
该方法规定, 若在 d地址发生冲突, 下一次探查位置为
d+12,d+22,…, 直到找到一个空闲位置为止 。
(3) 双散列函数探查法
该方法使用两个散列函数 H和 T，用 H作散列函数建立散
列存储（散列表），用 T来解决冲突。具体实施时，若
H(k)在 d0位置发生冲突时，即 d0 =H(k)，则下一个探查位
置序列应该是 di=(di-1+T(k))%m (1≤i≤m-1)。
2.拉链法
拉链法也称链地址法，是把相互发生冲突的同义词用
一个单链表链接起来，若干组同义词可以组成若干个
单链表
例 8-6 对例 8-5 给 定 的 关 键 字 序 列
19,14,23,1,68,20,84,27,55,11,10,79, 给 定 散 列 函 数 为
H(k)=k%13,试用拉链法解决冲突建立散列表 。
图 8-18为用尾插法建立的关于例 8-6的拉链法解决冲
突的散列表 。
0
1
2
3
4
5
6
7
8
9
10
11
12
^
^
^
^
^
^
^
14
1
27
79
^
68
55
^
19
84
^
20
^
23
10
^
11
^
图 8 - 18 拉链法解决冲突的散列表
8.4.5 散列查找的性能分析
散列查找按理论分析, 它的时间复杂度应为 O(1),它的
平均查找长度应为 ASL=1,但实际上由于冲突的存在,
它的平均查找长度将会比 1大 。 下面将分析几种方法的
平均查找长度 。
1.线性探查法的性能分析
由于线性探查法解决冲突是线性地查找空闲位置的,
平均查找长度与表的大小 m无关, 只与所选取的散列
函数 H及装填因子 α的值和该处理方法有关, 这时的
成功的平均查找长度为 ASL=1/2 (1+1/(1- α))。,
2.拉链法查找的性能分析
由于拉链法查找就是在单链表上查找，查找单链表
中第一个结点的次数为 1，第二个结点次数为 2，其
余依次类推。它的平均查找长度 ASL=1+α/2。
例 8-7 给定关键字序列 11,78,10,1,3,2,4,21，
试分别用顺序查找, 二分查找, 二叉排序树查找,
平衡二叉树查找, 散列查找 (用线性探查法和拉链法 )
来实现查找, 试画出它们的对应存储形式 (顺序查找
的顺序表, 二分查找的判定树, 二叉排序树查找的
二叉排序树及平衡二叉树查找的平衡二叉树, 两种
散列查找的散列表 ),并求出每一种查找的成功平均
查找长度 。 散列函数 H(k)=k%11。
顺序查找的顺序表（一维数组）如图 8-19所示,
1 1 7 8 1 0 1 3 2 4 2 1
0 1 2 3 4 5 6 7 8 9 10
图 8 - 19 顺序存储的顺序表
从图 8-19可以得到顺序查找的成功平均查找长度为：
ASL=(1+2+3+4+5+6+7+8)/8=4.5；
二分查找的判定树（中序序列为从小到大排列的有序序
列）如图 8-20所示，
4
2
1 3
1 1
10 21
78
图 8 - 20 二分查找的判定树
从图 8-20可以得到二分查找的成功平均查找长度为：
ASL=(1+2*2+3*4+4)/8=2.625；
二叉排序树（关键字顺序已确定，该二叉排序树应唯一）
如图 8-21(a)所示，平衡二叉树（关键字顺序已确定，该
平衡二叉树也应该是唯一的），如图 8-21(b)所示，
1 1
10 78
1
21
3
2 4
3
1 1 1
2 10
4
78
21
( a) 二叉排序树 (b) 平衡二叉树
图 8 - 21 二叉排序树及平衡二叉树
从图 8-21(a)可以得到二叉排序树查找的成功平均查找长度
为：
ASL=(1+2*2+3*2+4+5*2)=3.125；
从图 8-21(b)可以得到平衡二叉树的成功平均查找长度为：
ASL=(1+2*2+3*3+4*2)/8=2.75；
线性探查法解决冲突的散列表如图 8-22所示，
1 1 7 8 1 3 2 4 2 1 1 0
0 1 2 3 4 5 6 7 8 9 1 0
图 8 - 22 线性探查的散列表
从图 8-22可以得到线性探查法的成功平均查找长度为：
ASL=（ 1+1+2+1+3+2+1+8） /8=2.375；
拉链法解决冲突的散列表如图 8-23所示 。
0
1
2
3
4
5
6
7
8
9
10
^
^
^
^
^
1
^ 78
11
^
1
^ 78
2
^
3
^
4
^
图 8 - 23 拉链法的散列表
从图 8-23可以得到拉链法的成功平均查找长度为：
ASL=(1*6+2*2)/8=1.25。
