1北京邮电大学自动化学院
第 8章 查找
? 1、查找表 —— 也叫检索,是由同一类型的数据元素（或记
录）构成的集合。由于“集合”中的数据元素之间存在完全
松散的关系，因此查找表是一种非常灵便的数据结构。
? 2、查找表的操作
? 查找某个“特定”的数据元素是否在查找表中；
? 检索某个“特定”的数据元素的各种属性；
? 在查找表中插入一个数据元素；
? 从查找表中删除某个数据元素。
2北京邮电大学自动化学院
? 3、静态查找表、动态查找表
? 若对查找表只作前两种统称为“查找”的操作，则此
类查找为 静态查找表 。
? 若在查找过程中同时插入查找表中不存在的数据元素，
或从查找表中删除已存在的某个数据元素，则称此类表
为 动态查找表。
? 4、关键字、次关键字
? 关键字,是数据元素（或记录）中某个数据项的值，用
它可以标识（识别）一个数据元素（或记录）。若此关
键字可以唯一地标识一个记录，则称此关键字 为主关键
字 。反之，则称此关键字为 次关键字 。
第 8章 查找
3北京邮电大学自动化学院
? 5、查找
? 根据给定的某个值，在查找表中确定一个其关键字等于给定
值的记录或数据元素。 若表中存在这样的一个记录，则称查
找是成功的,此时查找的结果为给出整个记录的信息，或指
示该记录在查找表中的位置；
? 6、查找方法评价
? 查找速度、占用存储空间多少、算法本身复杂程度
? 平均查找长度 ASL(Average Search Length),为确定记录
在表中的位置，需和给定值进行比较的关键字的个数的期望
值叫 查找算法的 平均查找长度。
? 若表中不存在关键字等于给定值的记录,则称查找不成功。
此时查找的结果可给出一个“空”记录或“空”指针。
第 8章 查找
4北京邮电大学自动化学院
i
例 0 1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
找 64
64
监视哨
i i i i
比较次数 =5
? 比较次数：
? 查找第 n个元素,1
? 查找第 n-1个元素,2
8.1 静态查找表
? 一、顺序表的查找（顺序查找）
? 1、顺序查找 从表中最后一个记录开始，逐个进行记录的关键
字和给定值的比较，若某个记录的关键字和给定值比较相等，
则查找成功，找到所查找记录；反之，若直至第一个记录，其
关键字和给定值比较都不等，则表明表中没有所查记录，查找
不成功。
? 查找第 1个元素,n
? 查找第 i个元素,n+1-i
? 查找失败, n+1
5北京邮电大学自动化学院
2、查找操作的性能分析
? 对于含有 n个记录的表，查找成功时的平均查找长度为：
? 其中, n 为表长,Pi 为查找表中第 i个记录的概率，
且, Ci为找到该记录时，曾和给定值比较过的关
键字的个数。 11 ???
n
i
iP
?
?
?
n
i
ii cpA S L
1
? 从顺序查找的过程可见,Ci取决于所查找记录在表中的位
置。查找表中最后一个记录是，仅需比较一次，而查找表中
第一个记录时，则需比较 n次。一般情况下 Ci等于 n-i+1。
6北京邮电大学自动化学院
ASL = nP1 +(n-1)P2 + +2Pn-1+Pn
2
1
2
)1(11
1
11
?
?
?
????
?
??
??
nnn
n
i
n
cpA S L
n
p
n
i
n
i
ii
i
则
概率相等设表中每个元素的查找
? 从上式可知，在不等概率查找的情况下,ASLss 在
Pn≥Pn-1≥···≥P2≥P1时取极小值。
? 应对记录的查找概率进行排序，使表中记录按查找概率由
小到大重新排列，以便提高查找效率。
? 查找概率无法事先测定，则查找过程采取的改进办法是，
在每次查找之后，将刚刚查找到的记录直接移至表尾的位
置上。
7北京邮电大学自动化学院
? 顺序查找的缺点是 平均查找长度较大,特别是当 n很大
时，查找效率低。然而，它有很大的优点是,算法简单且
适应面广。
nPi 2
1?
)1(43)1(21)1(2 1
1
' ??????? ?
?
nninnA S L
n
i
SS
? 当查找不成功时的情形不忽视时，查找算法的平均查找长
度应是查找成功时的平均查找长度与查找不成功时的平均
查找长度之和。
? 对于顺序查找，不论给定值 key为何值，查找不成功时和
给定值进行比较的关键字个数均为 n+1。 假设查找成功与
不成功的可能性相同,对每个记录的查找概率也相等，
则,此时顺序查找的平均查找长度为：
一、顺序表的查找（顺序查找）
8北京邮电大学自动化学院
? 1、折半查找 折半查找的查找过程是：先确定待查记录
所在的范围（区间），然后逐步缩小范围直到找到或找不到
该记录为止。每次将待查记录所在区间缩小一半。
二、有序表的查找（折半查找）
? 算法实现：假设表长为 n,low,high和 mid分别指向待查
元素所在区间的上界、下界和中点,k为给定值，初始时，令
low=1,high=n,mid=?(low+high)/2?
? 让 k与 mid指向的记录比较
? 若 k==r[mid].key,查找成功
? 若 k<r[mid].key,则 high=mid-1
? 若 k>r[mid].key,则 low=mid+1
? 重复上述操作，直至 low>high时,查找失败 。
9北京邮电大学自动化学院
low highmid
例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92
找 21
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low highmid
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low highmidCh7_2.c
例如：已知如下 11个数据元素的有序表（ 05,13,19，
21,37,56,64,75,80,88,92），现要查找关键
字为 21和 70 的数据元素。
1、折半查找
10北京邮电大学自动化学院
例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92
low highmid
找 70
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low highmid
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low high
mid
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low highmid
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
lowhigh
11北京邮电大学自动化学院
2、折半查找的性能分析
? 先看上述 11个元素的表的具体例子。每一个的比较次数。
? 这个查找过程可用图 8.1所示的二叉
树来描述。树中每个结点表示表中
一个记录，结点中的值为该记录在
表中的位置，通常称这个描述查找
过程的 二叉树为判定树。
8 112
10741
93
6
5
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
? 从判定树上可见，查 21的过程恰好是走了一条从根到结点
（ 4）的路径,和给定值进行比较的关键字个数为该路径上
的结点数或结点 4在判定树上的层次数。
12北京邮电大学自动化学院
1)1(l o g1211 2
1
1
11
???????? ???
?
?
??
nnnjncncpA S L h
j
jn
i
i
n
i
ii则：
1)1(l o g 2 ??? nA S L bs
? 二分法查找在查找成功时进行比较的关键字个数最多不超过
树的深度，而具有 n个结点的判定树的深度为 ?log2n?+1。所
以折半查找法在查找成功时和给定值进行比较的关键字个数
至多为 ?log2n?+1
nPi 1?
? 对于任意的 n，当 n较大（ n>50时），可有下列近似结果：
? 可见，折半查找的效率比顺序查找高，但折半查找只适用于
有序表，且限于顺序存储结构。
? 树中层数为 1的结点有 1个，层数为 2的结点有 2个，层数为 h
的结点有 2h-1个。假设表中每个记录的查找概率,则查
找成功时折半查找的平均查找长度为：
13北京邮电大学自动化学院
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 53
22 48 86
1 7 13
索引表
查 38
三、索引顺序表的查找（分块查找）
? 若以索引顺序表表示静态查找表，则 search函数可用分块
查找来实现。 分块查找又称索引顺序查找,这是顺序查找的
一种改进方法。在此查找法中，除表本身以外，尚需要建立
一个“索引表”。例如：下图所示为一个表及其索引表，表
中含有 18个记录，可分成三个子表（ R1,R2,…, R6）、
（ R7,R8,…, R12）、（ R13,R14,…, R18）。
14北京邮电大学自动化学院
1)(212 12 111
11
??????????? ??
??
ssnsbisjbLLA S L s
i
b
j
wbbs
? 分块查找方法 所谓“分块有序”指的是第 2个子表中所有
记录的关键字均大于第 1子表中的最大关键字，第 3子表中
的所有关键字均大于第 2字表中的最大关键字，依次类推，
分快查找过程需分两步进行。先确定待查记录所在的块
（子表），然后在块中顺序查找。
? 此时的平均查找长度不仅和表长有关，而且和每一块中
的记录个数 s有关。
? 分块查找的平均长度为,ASLbS=Lb+Lw
? 其中 Lb为查找索引表确定所在块的平均查找长度,Lw为在
块中查找元素的平均查找长度。
三、索引顺序表的查找（分块查找）
15北京邮电大学自动化学院
顺序查找 二分法查找 分块查找
ASL 最大 最小 两者之间
表结构 有序表
无序表
有序表 分块有序表
存储结构 顺序存储结构
线性链表
顺序存储结构 顺序存储结构
线性链表
查找方法的比较
16北京邮电大学自动化学院
8.2 动态查找表
? 动态查找表的特点,表结构本身是在查找过程中动态地生成
的，即对于给定值 key，若表中存在其关键字等于 key的记
录，则查找成功返回，否则插入关键字等于 key的记录。
? 一、二叉树排序树及其查找过程
? 1、什么是二叉排序树？
? 二叉排序树或是一棵空树；或是具有下列性质的二叉树：
? （ 1）若它的左子树不空，则左子树上所有结点的值均
小于它的根结点的值；
? （ 2）若它的右子树不空，则右子树上所有结点的值均
大于或等于它的根结点的值；
? （ 3）它的左、右子树也分别为二叉排序树。
17北京邮电大学自动化学院
一、二叉树排序树及其查找过程
? 2、查找过程
90
78
24
100
61
373
5312
45
? 例如右图所示为二叉排序树。
? 若二叉排序树为空，则查找不成功；否则
? （ 1）若给定值等于根结点的关键字，则查找
成功；
? （ 2）若给定值小于根结点的关键字，则继续在左子
树上进行查找；
? （ 3）若给定值大于根结点的关键字，则继续在右子树上
进行查找。
18北京邮电大学自动化学院
查找过程举例,100,40
90
78
24
100
61
373
5312
45
一、二叉树排序树及其查找过程
19北京邮电大学自动化学院
二、二叉排序树的插入与删除
? 1、二叉排序树的插入
? 二叉排序树是一种动态树表。其特点是：树的结构通常不是
一次生成的，而是在查找过程中,当树中不存在关键字等于
给定值的结点时再进行插入 。新插入的结点一定是一个新添
加的叶子结点，并且是查找不成功时，查找路径上访问的最
后一个结点的左孩子或右孩子结点。
? 举例：若从空树出发，经过一系列的查找插入操作之后，可
生成一棵二叉树。设查找的关键字序列为 {45,24,53，
45,12,24,90}，则生成的二叉排序树如图所示。二叉排
序树生成：从空树出发，经过一系列的查找、插入操作之
后，可生成一棵二叉排序树。
20北京邮电大学自动化学院
? 容易看出，中序遍历二叉树可得到
一个关键字的有序序列。这就是
说，一个无序序列可以通过构造一
棵二叉排序树而变成一个有序序
列，构造树的过程即为对无序序列
进行排序的过程。
? 从上面的插入过程还可以看到，每次插入的新的结点都是二叉
排序树上新的叶子结点，则在进行插入操作时，不必移动其它
记录，仅需要改动某个结点的指针，由空变为非空即可。这就
相当于在一个有序序列上插入一个记录而不需要移动其它记
录。它表明,二叉排序树既拥有类似折半查找的特性，又采用
了链表作存储结构，因此是动态查找表的一种适宜表示。
24
45
53
12 90
1、二叉排序树的插入
21北京邮电大学自动化学院
2、二叉排序树的删除
? 对于一般的二叉树来说，删除树中一个结点是没有意义
的。然而，对于二叉排序树，删去树上一个结点相当于删
去有序序列中的一个记录，只要在删除某个结点之后，依
旧保持二叉排序树的特性即可。
? （ 1） *P为叶子结点
? 那么，如何在二叉排序树上删去一个结点呢？假设在二叉
排序树上被删结点为 *P，其双亲结点为 *F，且不失一般
性，可设 *P是 *F的左孩子。要删除二叉排序树中的 P结
点，分三种情况：
? 即 PL和 PR均为空树。由于删去叶子结点不破坏整棵树的
结构，则 只需修改其 P双亲 F的指针
? F->lchild=NULL或 F->rchild=NULL。
22北京邮电大学自动化学院
S
Q
PL
P
中序遍历,Q S PL P
S
Q PL
中序遍历,Q S PL
(2)
S
P
PL
Q
中序遍历,PL P S Q
S
PL Q
中序遍历,PL S Q
(1)
? （ 2） *P只有左子树 PL或右子树 PR
? 此时只要令 PL或 PR直接成为其双亲结点 *F的左子树即可，显
然，作此修改也不破坏二叉树的特性。
23北京邮电大学自动化学院
中序遍历,P PR S Q
S
PR Q
中序遍历,PR S Q
(3)
S
P
PR
Q
中序遍历,Q S P PR
S
Q PR
中序遍历,Q S PR
(4)
S
Q
PR
P
? （ 2） *P只有左子树 PL或右子树 PR
24北京邮电大学自动化学院
? （ 3） *P左、右子树均非空
F
P
C PR
CL Q
QL S
SL
中序遍历,CL C ……Q L Q SL S P PR F
F
S
C PR
CL Q
QL SL
中序遍历,CL C ……Q L Q SL S PR F(5)
? 在删除 *P之前，中序遍历二叉树得到的序列为
{……CLCQLQS LSPPRF……},删除 *P之后，为保持其
它元素之间的相对位置不变，可以有两种：其 一是令 *P
的直接前驱（或直接后继）替代 *P，然后再从二叉排序
树中删去它的直接前驱（或直接后继），如下图所示。
25北京邮电大学自动化学院
? 其二是令 *P的左子树为 *F的左子树，而 *P的右子树为
*S的右子树，如下图所示。
F
P
C PR
CL Q
QL S
SL
中序遍历,CL C ……Q L Q SL S P PR F
F
C
PR
CL Q
QL
SL
中序遍历,CL C ……Q L Q SL S PR F(5)
S
26北京邮电大学自动化学院
?删除算法
例 80
50 120
60 110 150
55 70
53
删除 50
80
60 120
110 15055 70
53
删除 60
80
55 120
110 15053 70
10
4 25
8 13
5
4
删除 10
8
4 25
5 13
4
删除 5
8
4 25
4 13
Ch5_10.c
27北京邮电大学自动化学院
三、二叉排序树的查找分析
? 二分法查找长度为 n的表的判定树是唯一的，而含有 n个结点
的二叉排序树却不是唯一的。由关键字序列
{45,24,53,12,37,93}构造而得的二叉排序树 (a)，
45
53
93
24
3712 a
24
12
37
45
53
93b
? ASL =（ 1+2+2+3+3+3） / 6 = 14/6
? 由关键字序列 {12,24,37,45,53,93}构造而得的二叉排序树
? ASL =（ 1+2+3+4+5+6） /6 =21/6
28北京邮电大学自动化学院
? 因此,含有 n个结点的二叉排序树的平均查找长度和树的形
态有关 。当先后插的关键字有序时，构成的二叉排序树蠕变
为单支树。树的深度为 n，其平均查找长度为（ n+1） /2，
和顺序查找相同，这是最差的情况，显然，最好的情况是二
叉排序树的形态和二分法查找的判定树相同，其平均查找长
度和 log2n成正比。那么，它的平均性能如何？
? 由此可见，在随机的情况下，二叉排序树的平均查找长度
和 log n是等数量级的。然而，在某些情况下（有人研究
证明，这种情况出现的概率约为 46.5%）。尚需在构成二
叉排序树的过程中进行“平衡化处理”，成为二叉平衡
树。
nnnP ln)11(2)( ??
三、二叉排序树的查找分析
29北京邮电大学自动化学院
四、平衡二叉树
? 1、平衡二叉树
? 平衡二叉树，它或者是一棵空树，或者是具有下列性质的二
叉排序树：它的左子树和右子树都是平衡二叉树，且左子树
和右子树高度之差的绝对值不超过 1。
? 若将二叉树上结点的平衡因子 BF(Balance Factor)定义为该
结点的左子树的深度减去它的右子树的深度，则平衡二叉树
上所有结点的平衡因子只可能是 -1,0,1。只要二叉树上有
一个结点的平衡因子的绝对值大于 1，则这棵树就不是平衡
二叉树。
? 平衡二叉树的优点,它的平均查找长度和 logN同数量级。
30北京邮电大学自动化学院
1、平衡二叉树
1
1
0
0
平衡二叉树
不平衡二叉树
0
100
-11
-1
0
10
0-1
2
0
100
-20
-1
31北京邮电大学自动化学院
? 构造二叉平衡（查找）树的方法是：在插入过程中，采用平
衡旋转技术。
? 例如,依次插入的关键字为 5,4,2,8,6,9
5
4
2
4
2 5
8
6
6
5 8
4
2
向右旋转
一次
先向右旋转
再向左旋转
2、如何使二叉排序树成为平衡二叉树
32北京邮电大学自动化学院
4
2 6
5 8
9
4
2
6
8
95
向左旋转一次
继续插入关键字 9
33北京邮电大学自动化学院
? 二叉树的平衡处理调整的规律可归纳为下列四种情况
1
B
2
A
BLh
AR h-1
BRh-1
插入结点
0
A
0
B
BL BR AR
LL
? （ 1）单向右旋平衡处理 由于在结点 *a的左子树根结点的
左子树上插入结点,*a的平衡因子由 1增加到 2，致使以 *a为
根结点的子树失去平衡，则需要进行一次向右的顺时针旋转
操作，如图所示。
? 中序遍历,BL B BR A AR
34北京邮电大学自动化学院
? （ 2）单向左旋平衡处理
-1
B
-2
A
BR h
AL h-1
插入结点
RR
0
A
0
B
AL BL BRBL h-1
? 由于在 *a的右子树根结点的右子树上插入结点,*a的平衡因
子由 -1变为 -2，致使以 *a为根结点的子树失去平衡，则需要
进行一次向左的逆时针旋转操作，如图所示。
? 中序遍历,AL A BL B BR
35北京邮电大学自动化学院
? （ 3）双向旋转（先左后右）平衡处理
-1
B
2
A
CLh-1
AR h-1
h-1 BL
插入结点
0
B
0
C
BL CL CR
LR
AR
-1
A
1
C
h-2 CR
中序遍历,B CL C CR A AR
? 由于在 *a的左子树根结点的右子树上插入结点,*a的平衡因
子由 1增加到 2，致使以 *a为根结点的子树失去平衡，则需要
进行两次旋转（先左旋后右旋）操作，如图所示。
36北京邮电大学自动化学院
? （ 4）双向旋转（先右后左）平衡处理
-1
B
-2
A
CLh-1
h-1 AL
插入结点
0
A
0
C
AL CL CR
RL
BR
-1
B1
C
BR h-1CR h-2
中序遍历,ALACLCCRBBR
? 由于在 *a的右子树根结点的左子树上插入结点,*a的平衡因
子由 -1增加到 -2，致使以 *a为根结点的子树失去平衡，则需
要进行两次旋转（先右旋后左旋）操作，如图所示。
37北京邮电大学自动化学院
3、在平衡树的二叉排序树 BBS上插入一个新的数据元素
? （ 1）若 BBST为空树，则插入一个数据元素为 e的新结
点作为 BBST的根结点，树的深度加 1；
? （ 2）若 e的关键字和 BBST的根结点的关键字相等
时，则不进行插入；
? （ 3）若 e的关键字小于 BBST的根结点的关键字，而
且在 BBST的左子树中不存在和 e相同关键字的结点，
则插入在 BBST的左子树上，并且当插入之后的左子树
深度增加（ +1）时，分别就不同情况处理之。
38北京邮电大学自动化学院
? *BBST的根节点的平衡因子为 1（左子树的深度大于右子树
的深度）：
? *BBST的根节点的平衡因子为 -1（右子树的深度大于左子
树的深度）：则将根结点的平衡因子更改为 0,BBST的
深度不变；
? *BBST的根节点的平衡因子为 0（左、右子树的深度相等）：
则将根结点的平衡因子更改为 1,BBST的深度加 1；
? 若 BBST的左子树根结点的平衡因子为 -1，则需进行先
向左、后向右的双向旋转平衡处理，并且在旋转处理
之后，修改根结点和其左、右子树根结点的平衡因
子，树的深度不变。
? 若 BBST的左子树根节点的平衡因子为 1，则需要进行
单向右旋平衡处理，并且在右旋处理之后，将根结点
和其右子树根结点的平衡因子更改为 0，树的深度不变
39北京邮电大学自动化学院
? （ 4）若 e的关键字大于 BBST的根结点的关键字，而且在
BBST的右子树中不存在和 e 有相同关键字的结点，则将 e
插入在 BBST的右子树上，并且当插入之后的右子树深度增
加（ +1）时，分别就不同情况处理之。其处理操作和（ 3）
中所述相对称。
40北京邮电大学自动化学院
? 理想的情况是希望不经过任何比较，一次存取便能得到所查
记录，那就是必须在记录的存储位置和它的关键字之间建立
一个确定的对应关系 f，使每个关键字和结构中唯一的存储
位置相对应。因而在查找时，只要根据这个对应关系 f找到
给定值 k的像 f(k) 。我们称 这个对应关系 f(k)为哈希函数，按
照这个思想建立的表为哈希表。
8.3 哈希表（散列表和查找）
编号 地区号 总人口 汉族 回族 ….
1 北京
? 假设要建立一张全国 30个地区的各民族人口统计表。
? 显然，可以用一个一维数组 C（ 1,30）来存放这张表，其中
C[i]是编号为 i地区的人口情况。编号 i便为记录的关键字，由
它唯一确定记录的存储位置 C[i]。
41北京邮电大学自动化学院
Key beijing
北京
tianjin
天津
Hebei
河北
shanxi
山西
Shanghai
上海
Shandong
山东
hena
n河南
sichua
n四川
f1(key) 02 20 08 19 19 19 08 19
f2(key) 09 04 17 28 28 26 22 03
f3(key) 04 26 02 13 23 17 16 16
? 为了查找方便应以地区名作为关键字。假设地区名以汉语拼音
的字符表示，则不能简单地取哈希函数，而是首先要将它们转
化为数字。
? （ 1）取关键字的第一个字母在字母表中的序号作为哈希函数；
? （ 2）先求关键字的第一个和最后一个字母在字母表中的序号
之和，然后判别这个值。若比 30大，则减去 30。
? （ 3）先求每个汉字的第一个拼音字母的 ASCII码之和的八进
制形式，然后将这个八进制数看成是十进制再除以 30取余
数。
42北京邮电大学自动化学院
? 从例子可见：
? （ 1）哈希函数只是一种映象，所以哈希函数的设定很灵
活，只要使任何关键字的哈希函数值都落在表长允许的范
围之内即可。
? （ 2）对于不同的关键字可能得到同一哈希地址，即
key1?key2,但 h(key1)=h(key2)，这种现象 叫 冲突 。
? 在一般情况下,冲突只能尽可能地少，而不能完全避免 。
8.3 哈希表（散列表和查找）
? 具有相同函数值的两个关键字对该哈希函数来说称做同义
词 。
43北京邮电大学自动化学院
? 根据设定的哈希函数和处理冲突的方法将 一组关键
字映象到一个有限的连续的地址集（区间）上,
8.3 哈希表（散列表和查找）
? 这一映象过程称为 哈希表或散列,
? 所得到存储位置称 哈希地址或散列地址 。
? 并以关键字在地址集中的“象”作为记录在表中的
存储位置,这种情况便称为 哈希表,
44北京邮电大学自动化学院
二、哈希函数的构造方法
? 若对于关键字集合中的任一关键字，经哈希函数映象
到地址集合中任何一个地址的概率是相同的，则此类
哈希函数为均匀的哈希函数。
? 直接定址法
? 数字分析法
? 平方取中法
? 折叠法
? 除留余数法
45北京邮电大学自动化学院
1、直接定址法
? 取关键字或关键字的某个线性函数作哈希地址，即
h(key)=key 或 h(key)=a·key+b
地址 01 02 03 25
年龄 1 2 3 25
人数 3000 2000 5000 1050
? 例如：有一个从 1岁到 100岁的人口数字统计表，年龄作为
关键字，哈希函数取关键字自身。
46北京邮电大学自动化学院
? 又如：有一个解放后出生的人口调查表，关键字是年
份，哈希函数取关键字加一常数：
? h(key） =key+(-1948)
地址 01 02 03 …,22
年份 1949 1950 1951 … 1970
人数 … 15000
? 这样，若要查 1970年出生的人数，则只要查（ 1970-
1948） =22项即可。由于直接定址所得地址集合和关键
字集合的大小相同，因此不会发生冲突,但实际中能使
用这种哈希函数的情况很少。
1、直接定址法
47北京邮电大学自动化学院
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
8 1 3 6 8 5 3 7
8 1 4 1 9 3 5 5
…..
…..
???????? ?只取 8
?只取 1
?只取 3,4
?只取 2,7,5
????数字分布近乎随机
取 ????任意两位或两位
与另两位的叠加作哈希地址
48北京邮电大学自动化学院
3、平方取中法
记录 关键字 （关键字） 2 哈希地址（ 217~29）
A 0100 0010000 010
I 1100 1210000 210
J 1200 1440000 440
I0 1160 1370400 370
P1 2061 4310541 310
? 通常在选定哈希函数时不一定能知道关键字的全部情况，取
其中哪几位也不一定合适，而一个数平方后的中间几位数和
数的每一位都相关，由此使随机分布的关键字得到的哈希地
址也是随机的。取的位数由表长决定。 例如：为 BASIC源
程序中的标识符
49北京邮电大学自动化学院
4、折叠法
? 将关键字分割成位数相同的几部分（最后一部分的位数可以不
同），然后取这几部分的叠加和（舍去进位）作为哈希地址。
这方法称为折叠法。关键字位数很多，而且关键字中每一位上
数字分布大致均匀时，可以采用折叠法得到哈希地址。
? 例 关键字为, 0442205864，哈希地址位数为 4
5 8 6 4
4 2 2 0
0 4
1 0 0 8 8
H(key)=0088
移位叠加
5 8 6 4
0 2 2 4
0 4
6 0 9 2
H(key)=6092
间界叠加
? 移位叠加,将分割后的几部分低位对齐相加
? 适于关键字位数很多，且每一位上数字分布大致均匀情况
? 间界叠加,从一端沿分割界来回折送，然后对齐相加
50北京邮电大学自动化学院
? 取关键字被某个不大于哈希表表长 m的数 p除后所得余
数作哈希地址，即
5、除留余数法
关键字 28 35 63 77 105
哈希地址 7 14 0 14 0
P=21
? 特点,简单、常用，可与上述几种方法结合使用,p的
选取很重要； p选的不好，容易产生同义词。
? H(key)=key MOD p,p?m
51北京邮电大学自动化学院
? 随机数法构造,选择一个随机函数，取关键字的随机函数
值为它的哈希地址，即 H(key)=random(key)，其中
random(key)为随机函数。通常，当关键字长度不等时采
用此法构造的哈希函数较恰当。
6、随机数法
? 实际工作中需视不同的情况采用不同的哈希函数。通常
考虑的因素有：
? （ 1）计算哈希函数所需时间
? （ 2）关键字的大小
? （ 3）哈希表的大小
? （ 4）关键字的分布情况
? （ 5）记录的查找频率
52北京邮电大学自动化学院
三、处理冲突的方法
? 通常用的处理冲突的方法有下列几种：
? 开放定址法
? 再哈希法
? 链地址法
? 建立一个公共溢出区
53北京邮电大学自动化学院
? 开放定址法 方法,当冲突发生时，形成一个探查序列；沿
此序列逐个地址探查，直到找到一个空位置（开放的地
址），将发生冲突的记录放到该地址中，即
Hi=(H(key)+di) MOD m,i=1,2,……k (k ?m-1)
1、开放定址法
? 其中,H(key)—— 哈希函数, m—— 哈希表表长, di——
增量序列
? di有下列三种取法
? 线性探测再散列, di=1,2,3,……m -1
? 二次探测再散列, di=12,-12,22,-22,32,…… ± k2(k?m/2)
? 伪随机探测再散列, di=伪随机数序列
54北京邮电大学自动化学院
? 例 表长为 11的哈希表中已填有关键字为 17,60,29的记
录,H(key)=key MOD 11,现有第 4个记录，其关键字为
38，按三种处理冲突的方法，将它填入表中
? (1) H(38)=38 MOD 11=5 冲突
? H1=(5+1) MOD 11=6 冲突
? H2=(5+2) MOD 11=7 冲突
? H3=(5+3) MOD 11=8 不冲突
? (2) H(38)=38 MOD 11=5 冲突
? H1=(5+12) MOD 11=6 冲突
? H2=(5-12) MOD 11=4 不冲突
? (3) H(38)=38 MOD 11=5,冲
突,设伪随机数序列为 9，则：
? H1=(5+9) MOD 11=3 不冲突
0 1 2 3 4 5 6 7 8 9 10
60 17 29 383838
55北京邮电大学自动化学院
? 构造若干个哈希函数，当发生冲突时，计算下一个哈
希地址，即：
2、再哈希法
? 其中 Rhi均是 不同的哈希函数，即在同义词产生地址冲
突时计算另一个哈希函数地址，直到冲突不再发生。
这种方法不容易产生,聚集”，但增加了计算的时
间。
? Hi=Rhi(key) i=1,2,……k
56北京邮电大学自动化学院
3、链地址法
? 将所有关键字为同义词的记录存储在一个单链表中，并用
一维数组存放头指针。例如已知一组关键字 (19,14,
23,1,68,20,84,27,55,11,10,79)
? 哈希函数为,H(key)=key MOD 13,
? 其每个分量的初始状态都是
空指针。凡哈希地址为 I的记
录都插入到头指针为
chainHash[i]的链表中。在
链表中的插入位置可以在表
头或表尾；也可以在中间，
以保持同义词在同一线性链
表中按关键字有序。
01 14 27 79
55 68
19 84
20
10 23
11
^
^
^
^
^
^
?13
12
11
?10
?9
8
7
?6
?5
4
?3
2
?1
57北京邮电大学自动化学院
4、建立一个公共溢出区
? 假设哈希函数的值域为 [0,m-1]，则向量 Hash
Table[0,m-1]为基本表，每个分量存放记录，另设立
向量 Over Table[0,v] 为溢出表。所有关键字和基本表
中关键字为同义词的记录，不管它们由哈希函数得到
的哈希地址是什么，一旦发生冲突，都填入溢出表
58北京邮电大学自动化学院
四、哈希表的查找与分析
? 1、哈希表的查找过程
? 在哈希表上进行查找的过程和哈希造表的过程基本
一致。给定 k值，根据造表时设定的哈希函数求得哈
希地址，若表中此位置上没有记录，则查找不成
功；
? 否则比较关键字
? 否则根据造表时设定的处理冲突的方法找“下一
地址”，直至哈希表中某个位置为“空”或者表
中所填记录的关键字等于给定值时为止。
? 若和给定值相等，则查找成功；
59北京邮电大学自动化学院
? 例 已知一组关键字 (19,14,23,1,68,20,84,27,55,11,10,79),哈希函数
为,H(key)=key MOD 13,哈希表长为 m=16,设每个记录的查找概率相等
? (1) 用线性探测再散列处理冲突，即 Hi=(H(key)+di) MOD m
H(55)=3 冲突,H1=(3+1)MOD16=4
冲突,H2=(3+2)MOD16=5
H(79)=1 冲突,H1=(1+1)MOD16=2
冲突,H2=(1+2)MOD16=3
冲突,H3=(1+3)MOD16=4
冲突,H4=(1+4)MOD16=5
冲突,H5=(1+5)MOD16=6
冲突,H6=(1+6)MOD16=7
冲突,H7=(1+7)MOD16=8
冲突,H8=(1+8)MOD16=9
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
ASL=(1*6+2+3*3+4+9)/12=2.5
14 1 68 27 55 19 20 84 79 23 11 10
H(19)=6
H(14)=1
H(23)=10
H(1)=1 冲突,H1=(1+1) MOD16=2
H(68)=3
H(20)=7
H(84)=6 冲突,H1=(6+1)MOD16=7
冲突,H2=(6+2)MOD16=8
H(27)=1 冲突,H1=(1+1)MOD16=2
冲突,H2=(1+2)MOD16=3
冲突,H3=(1+3)MOD16=4
H(11)=11
H(10)=10 冲突,H1=(10+1)MOD16=11
冲突,H2=(10+2)MOD16=12
60北京邮电大学自动化学院
(2) 用链地址法处理冲突
ASL=(1*6+2*4+3+4)/12=1.75
关键字 (19,14,23,1,68,20,84,27,55,11,10,79)
14 01 27 79
68 55
19 84
20
23 10
11
^
^
^
^
^
^
?13
12
11
?10
?9
8
7
?6
?5
4
?3
2
?1
61北京邮电大学自动化学院
? 从哈希表的查找过程可见：
2、哈希查找分析
? （ 1）虽然哈希表在关键字与记录的存储位置之间建立
了直接的映象，但由于“冲突”的产生，使得哈希表的
查找过程仍然是一个给定值和关键字进行比较的过程。
因此，仍需要以平均查找长度作为衡量哈希表的查找效
率的量度。
? （ 2）查找过程中需要和给定值进行比较的关键字的个
数取决于下列三个因素,哈希函数，处理冲突的方法和
哈希表的填满因子 ?。
62北京邮电大学自动化学院
? 哈希函数：假设函数是“均匀的”
? 在一般情况下，处理冲突方法相同的哈希表，其平均
查找长度依赖于哈希表的装填因子。
? 例如用两种不同的处理冲突方法的平均查找长度：
? 处理冲突的方法：对于同样一组关键字，设定相同的哈
希函数，则不同的处理冲突的方法得到的哈希表不同，
它们的平均查找长度不同：
? （ 1）用线性探测再散列处理冲突
? ASL=(1*6+2+3*3+4+9)/12=2.5
? 用链地址法处理冲突
? ASL=(1*6+2*4+3+4)/12=1.75
63北京邮电大学自动化学院
? 线性探测再散列的哈希表查找成功时的平均长度为：
)1 11(21 ????nlS
哈希表的长度
表中填入的记录数??? 哈希表的装填因子定义为：
? α标志哈希表的装满程度。直观地看,α 越小，发生冲突的
可能性就越小；反之,α越大，表中已填入的记录越多，再
填记录时，发生冲突的可能性就越大，则查找时，给定值
需要于之进行比较的关键字的个数也就越多。
? 随机探测再散列，二次探测再散列和再哈希表查找
成功时的平均查找长度：
)1ln (1 ?? ???nrS
64北京邮电大学自动化学院
? 链地址法处理冲突的哈希查找成功时的平均查找长
度：
? 不同的处理冲突方法构成的哈希表查找不成功时的
平均查找长度分别为：
))1( 11(21 2????nlU
??? 1
1
nrU
21
???
ncS
?? ??? eU nc
? 线性探测再散列
? 随机探测再散列
? 链地址法处理冲突
2、哈希查找分析
65北京邮电大学自动化学院
第 8章 上机实习题
?二叉排序树操作：
?基本要求
?（ 1）用二叉链表作为存储结构，输入键值
序列建立一棵二叉排序树；
?（ 2）按中序遍历这棵二叉树；
?（ 3）删除二叉树中的结点 x。
66北京邮电大学自动化学院
第 8章复习提纲
?1,顺序表、有序表和索引顺序表的查找方法及
其平均查找长度的计算方法。
?2,熟练掌握二叉排序树的构造和查找方法。
?3,熟练掌握哈希表的构造和查找方法，深刻理
解哈希表与其它结构的表的实质性的差别。
?4,掌握按定义计算各种查找方法在等概率情况
下查找成功时的平均查找长度
67北京邮电大学自动化学院
第 8章 作业
? 一、单项选择题
? 1、采用顺序查找法查找长度为 n的线性表时，每个元素的平均查找长度
为 。
? （ A） n （ B） n/2 （ C） (n+1)/2 （ D） (n-1)/2
? 2、在一个长度为 12的有序表，按折半查找法对改表进行查找，在表内各
元素等概率情况下查找成功所需的平均比较次数为 。
? （ A） 35/12 （ B） 37/12 （ C） 39/12 （ D） 43/12
? 3、查找效率最高的二叉排序树是 。
? （ A）所有结点的左子树都为空的二叉排序树
? （ B）所有结点的右子树都为空的二叉排序树
? （ C）平衡二叉树 （ D）没有左子树的二叉排序树
68北京邮电大学自动化学院
? 4、以下说法错误的是 。
? A、散列法存储的基本思想是由关键码值决定数据的存储地址
? B、散列表的结点中只包含数据元素自身的信息，不包含任何指针
? C、装填因子是散列法的一个重要参数，它反映了散列表的装填程度
? D、散列表的查找效率主要取决于散列表造表时选取的散列函数何处理
冲突的方法
5、散列表的平均查找长度 。
A、与处理冲突方法有关与表长无关
B、与处理冲突方法无关与表的长度有关
C、与处理冲突方法有关且与表的长度有关
D、与处理冲突方法无关且与表的长度无关
第七章 作业
69北京邮电大学自动化学院
? 二、填空题
? 1、设线性表（ a1,a2,…, a500）元素的值由小到大排列，
对一个给定的 k值用折半法查找线性表，在查找不成功的情况
下至多需比较 次。
? 2、一个无序序列可以通过构造一棵 树而变成一个
有序序列，构造树的过程即为对无序序列进行排序的过程。
? 3、在散列存储中，装填因子 ?的值越大，则 ； ?的值
越小，则
第七章 作业
70北京邮电大学自动化学院
? 1、输入一个正整数序列 {40,28,6,72,100,3,54，
1,80,91,38}，建立一棵二叉排序树，然后删除结点
72，分别画出该二叉树及删除结点 72后的二叉树。
? 2、设有一组关键字 {19,01,23,14,55,20,84，
27,68,11,10,77}采用散列函数 H(key)=key%13，采
用开放地址法的线性探测再散列方法解决冲突，试在 0～
18的散列地址空间中对该关键字序列构造散列表。
第七章 作业
71北京邮电大学自动化学院
第 8章 上机时间及地点
班 级 时 间 地 点 老 师
0215301～ 302 12.24日 (周五）
14:00~17:00
4－ 328
4－ 328
张志霞
李维成
03501~502 12.25日 (周六）
14:00~17:00
4－ 327
4－ 328
杜 伟
王松月
03503～ 04 12.25日 (周六）
16:00~19:00
4－ 328
4－ 328
王松月
杜 伟
03507~509 12.25(周六）
18:00~22:00
4－ 327
4－ 328
李维成
张志霞
72北京邮电大学自动化学院
考试时间
班 级 时 间 地 点 监考老师
03501~502 01.09日 (周日）
8:30~10:30
杜 伟
王松月
03503～ 04 01.09日 (周日）
8:30~10:30
王松月
杜 伟
注：考试地点另行通知
0215301～ 302,03507~509班的考试时间
及地点由学校安排
第 8章 查找
? 1、查找表 —— 也叫检索,是由同一类型的数据元素（或记
录）构成的集合。由于“集合”中的数据元素之间存在完全
松散的关系，因此查找表是一种非常灵便的数据结构。
? 2、查找表的操作
? 查找某个“特定”的数据元素是否在查找表中；
? 检索某个“特定”的数据元素的各种属性；
? 在查找表中插入一个数据元素；
? 从查找表中删除某个数据元素。
2北京邮电大学自动化学院
? 3、静态查找表、动态查找表
? 若对查找表只作前两种统称为“查找”的操作，则此
类查找为 静态查找表 。
? 若在查找过程中同时插入查找表中不存在的数据元素，
或从查找表中删除已存在的某个数据元素，则称此类表
为 动态查找表。
? 4、关键字、次关键字
? 关键字,是数据元素（或记录）中某个数据项的值，用
它可以标识（识别）一个数据元素（或记录）。若此关
键字可以唯一地标识一个记录，则称此关键字 为主关键
字 。反之，则称此关键字为 次关键字 。
第 8章 查找
3北京邮电大学自动化学院
? 5、查找
? 根据给定的某个值，在查找表中确定一个其关键字等于给定
值的记录或数据元素。 若表中存在这样的一个记录，则称查
找是成功的,此时查找的结果为给出整个记录的信息，或指
示该记录在查找表中的位置；
? 6、查找方法评价
? 查找速度、占用存储空间多少、算法本身复杂程度
? 平均查找长度 ASL(Average Search Length),为确定记录
在表中的位置，需和给定值进行比较的关键字的个数的期望
值叫 查找算法的 平均查找长度。
? 若表中不存在关键字等于给定值的记录,则称查找不成功。
此时查找的结果可给出一个“空”记录或“空”指针。
第 8章 查找
4北京邮电大学自动化学院
i
例 0 1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
找 64
64
监视哨
i i i i
比较次数 =5
? 比较次数：
? 查找第 n个元素,1
? 查找第 n-1个元素,2
8.1 静态查找表
? 一、顺序表的查找（顺序查找）
? 1、顺序查找 从表中最后一个记录开始，逐个进行记录的关键
字和给定值的比较，若某个记录的关键字和给定值比较相等，
则查找成功，找到所查找记录；反之，若直至第一个记录，其
关键字和给定值比较都不等，则表明表中没有所查记录，查找
不成功。
? 查找第 1个元素,n
? 查找第 i个元素,n+1-i
? 查找失败, n+1
5北京邮电大学自动化学院
2、查找操作的性能分析
? 对于含有 n个记录的表，查找成功时的平均查找长度为：
? 其中, n 为表长,Pi 为查找表中第 i个记录的概率，
且, Ci为找到该记录时，曾和给定值比较过的关
键字的个数。 11 ???
n
i
iP
?
?
?
n
i
ii cpA S L
1
? 从顺序查找的过程可见,Ci取决于所查找记录在表中的位
置。查找表中最后一个记录是，仅需比较一次，而查找表中
第一个记录时，则需比较 n次。一般情况下 Ci等于 n-i+1。
6北京邮电大学自动化学院
ASL = nP1 +(n-1)P2 + +2Pn-1+Pn
2
1
2
)1(11
1
11
?
?
?
????
?
??
??
nnn
n
i
n
cpA S L
n
p
n
i
n
i
ii
i
则
概率相等设表中每个元素的查找
? 从上式可知，在不等概率查找的情况下,ASLss 在
Pn≥Pn-1≥···≥P2≥P1时取极小值。
? 应对记录的查找概率进行排序，使表中记录按查找概率由
小到大重新排列，以便提高查找效率。
? 查找概率无法事先测定，则查找过程采取的改进办法是，
在每次查找之后，将刚刚查找到的记录直接移至表尾的位
置上。
7北京邮电大学自动化学院
? 顺序查找的缺点是 平均查找长度较大,特别是当 n很大
时，查找效率低。然而，它有很大的优点是,算法简单且
适应面广。
nPi 2
1?
)1(43)1(21)1(2 1
1
' ??????? ?
?
nninnA S L
n
i
SS
? 当查找不成功时的情形不忽视时，查找算法的平均查找长
度应是查找成功时的平均查找长度与查找不成功时的平均
查找长度之和。
? 对于顺序查找，不论给定值 key为何值，查找不成功时和
给定值进行比较的关键字个数均为 n+1。 假设查找成功与
不成功的可能性相同,对每个记录的查找概率也相等，
则,此时顺序查找的平均查找长度为：
一、顺序表的查找（顺序查找）
8北京邮电大学自动化学院
? 1、折半查找 折半查找的查找过程是：先确定待查记录
所在的范围（区间），然后逐步缩小范围直到找到或找不到
该记录为止。每次将待查记录所在区间缩小一半。
二、有序表的查找（折半查找）
? 算法实现：假设表长为 n,low,high和 mid分别指向待查
元素所在区间的上界、下界和中点,k为给定值，初始时，令
low=1,high=n,mid=?(low+high)/2?
? 让 k与 mid指向的记录比较
? 若 k==r[mid].key,查找成功
? 若 k<r[mid].key,则 high=mid-1
? 若 k>r[mid].key,则 low=mid+1
? 重复上述操作，直至 low>high时,查找失败 。
9北京邮电大学自动化学院
low highmid
例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92
找 21
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low highmid
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low highmidCh7_2.c
例如：已知如下 11个数据元素的有序表（ 05,13,19，
21,37,56,64,75,80,88,92），现要查找关键
字为 21和 70 的数据元素。
1、折半查找
10北京邮电大学自动化学院
例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92
low highmid
找 70
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low highmid
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low high
mid
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low highmid
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
lowhigh
11北京邮电大学自动化学院
2、折半查找的性能分析
? 先看上述 11个元素的表的具体例子。每一个的比较次数。
? 这个查找过程可用图 8.1所示的二叉
树来描述。树中每个结点表示表中
一个记录，结点中的值为该记录在
表中的位置，通常称这个描述查找
过程的 二叉树为判定树。
8 112
10741
93
6
5
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
? 从判定树上可见，查 21的过程恰好是走了一条从根到结点
（ 4）的路径,和给定值进行比较的关键字个数为该路径上
的结点数或结点 4在判定树上的层次数。
12北京邮电大学自动化学院
1)1(l o g1211 2
1
1
11
???????? ???
?
?
??
nnnjncncpA S L h
j
jn
i
i
n
i
ii则：
1)1(l o g 2 ??? nA S L bs
? 二分法查找在查找成功时进行比较的关键字个数最多不超过
树的深度，而具有 n个结点的判定树的深度为 ?log2n?+1。所
以折半查找法在查找成功时和给定值进行比较的关键字个数
至多为 ?log2n?+1
nPi 1?
? 对于任意的 n，当 n较大（ n>50时），可有下列近似结果：
? 可见，折半查找的效率比顺序查找高，但折半查找只适用于
有序表，且限于顺序存储结构。
? 树中层数为 1的结点有 1个，层数为 2的结点有 2个，层数为 h
的结点有 2h-1个。假设表中每个记录的查找概率,则查
找成功时折半查找的平均查找长度为：
13北京邮电大学自动化学院
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 53
22 48 86
1 7 13
索引表
查 38
三、索引顺序表的查找（分块查找）
? 若以索引顺序表表示静态查找表，则 search函数可用分块
查找来实现。 分块查找又称索引顺序查找,这是顺序查找的
一种改进方法。在此查找法中，除表本身以外，尚需要建立
一个“索引表”。例如：下图所示为一个表及其索引表，表
中含有 18个记录，可分成三个子表（ R1,R2,…, R6）、
（ R7,R8,…, R12）、（ R13,R14,…, R18）。
14北京邮电大学自动化学院
1)(212 12 111
11
??????????? ??
??
ssnsbisjbLLA S L s
i
b
j
wbbs
? 分块查找方法 所谓“分块有序”指的是第 2个子表中所有
记录的关键字均大于第 1子表中的最大关键字，第 3子表中
的所有关键字均大于第 2字表中的最大关键字，依次类推，
分快查找过程需分两步进行。先确定待查记录所在的块
（子表），然后在块中顺序查找。
? 此时的平均查找长度不仅和表长有关，而且和每一块中
的记录个数 s有关。
? 分块查找的平均长度为,ASLbS=Lb+Lw
? 其中 Lb为查找索引表确定所在块的平均查找长度,Lw为在
块中查找元素的平均查找长度。
三、索引顺序表的查找（分块查找）
15北京邮电大学自动化学院
顺序查找 二分法查找 分块查找
ASL 最大 最小 两者之间
表结构 有序表
无序表
有序表 分块有序表
存储结构 顺序存储结构
线性链表
顺序存储结构 顺序存储结构
线性链表
查找方法的比较
16北京邮电大学自动化学院
8.2 动态查找表
? 动态查找表的特点,表结构本身是在查找过程中动态地生成
的，即对于给定值 key，若表中存在其关键字等于 key的记
录，则查找成功返回，否则插入关键字等于 key的记录。
? 一、二叉树排序树及其查找过程
? 1、什么是二叉排序树？
? 二叉排序树或是一棵空树；或是具有下列性质的二叉树：
? （ 1）若它的左子树不空，则左子树上所有结点的值均
小于它的根结点的值；
? （ 2）若它的右子树不空，则右子树上所有结点的值均
大于或等于它的根结点的值；
? （ 3）它的左、右子树也分别为二叉排序树。
17北京邮电大学自动化学院
一、二叉树排序树及其查找过程
? 2、查找过程
90
78
24
100
61
373
5312
45
? 例如右图所示为二叉排序树。
? 若二叉排序树为空，则查找不成功；否则
? （ 1）若给定值等于根结点的关键字，则查找
成功；
? （ 2）若给定值小于根结点的关键字，则继续在左子
树上进行查找；
? （ 3）若给定值大于根结点的关键字，则继续在右子树上
进行查找。
18北京邮电大学自动化学院
查找过程举例,100,40
90
78
24
100
61
373
5312
45
一、二叉树排序树及其查找过程
19北京邮电大学自动化学院
二、二叉排序树的插入与删除
? 1、二叉排序树的插入
? 二叉排序树是一种动态树表。其特点是：树的结构通常不是
一次生成的，而是在查找过程中,当树中不存在关键字等于
给定值的结点时再进行插入 。新插入的结点一定是一个新添
加的叶子结点，并且是查找不成功时，查找路径上访问的最
后一个结点的左孩子或右孩子结点。
? 举例：若从空树出发，经过一系列的查找插入操作之后，可
生成一棵二叉树。设查找的关键字序列为 {45,24,53，
45,12,24,90}，则生成的二叉排序树如图所示。二叉排
序树生成：从空树出发，经过一系列的查找、插入操作之
后，可生成一棵二叉排序树。
20北京邮电大学自动化学院
? 容易看出，中序遍历二叉树可得到
一个关键字的有序序列。这就是
说，一个无序序列可以通过构造一
棵二叉排序树而变成一个有序序
列，构造树的过程即为对无序序列
进行排序的过程。
? 从上面的插入过程还可以看到，每次插入的新的结点都是二叉
排序树上新的叶子结点，则在进行插入操作时，不必移动其它
记录，仅需要改动某个结点的指针，由空变为非空即可。这就
相当于在一个有序序列上插入一个记录而不需要移动其它记
录。它表明,二叉排序树既拥有类似折半查找的特性，又采用
了链表作存储结构，因此是动态查找表的一种适宜表示。
24
45
53
12 90
1、二叉排序树的插入
21北京邮电大学自动化学院
2、二叉排序树的删除
? 对于一般的二叉树来说，删除树中一个结点是没有意义
的。然而，对于二叉排序树，删去树上一个结点相当于删
去有序序列中的一个记录，只要在删除某个结点之后，依
旧保持二叉排序树的特性即可。
? （ 1） *P为叶子结点
? 那么，如何在二叉排序树上删去一个结点呢？假设在二叉
排序树上被删结点为 *P，其双亲结点为 *F，且不失一般
性，可设 *P是 *F的左孩子。要删除二叉排序树中的 P结
点，分三种情况：
? 即 PL和 PR均为空树。由于删去叶子结点不破坏整棵树的
结构，则 只需修改其 P双亲 F的指针
? F->lchild=NULL或 F->rchild=NULL。
22北京邮电大学自动化学院
S
Q
PL
P
中序遍历,Q S PL P
S
Q PL
中序遍历,Q S PL
(2)
S
P
PL
Q
中序遍历,PL P S Q
S
PL Q
中序遍历,PL S Q
(1)
? （ 2） *P只有左子树 PL或右子树 PR
? 此时只要令 PL或 PR直接成为其双亲结点 *F的左子树即可，显
然，作此修改也不破坏二叉树的特性。
23北京邮电大学自动化学院
中序遍历,P PR S Q
S
PR Q
中序遍历,PR S Q
(3)
S
P
PR
Q
中序遍历,Q S P PR
S
Q PR
中序遍历,Q S PR
(4)
S
Q
PR
P
? （ 2） *P只有左子树 PL或右子树 PR
24北京邮电大学自动化学院
? （ 3） *P左、右子树均非空
F
P
C PR
CL Q
QL S
SL
中序遍历,CL C ……Q L Q SL S P PR F
F
S
C PR
CL Q
QL SL
中序遍历,CL C ……Q L Q SL S PR F(5)
? 在删除 *P之前，中序遍历二叉树得到的序列为
{……CLCQLQS LSPPRF……},删除 *P之后，为保持其
它元素之间的相对位置不变，可以有两种：其 一是令 *P
的直接前驱（或直接后继）替代 *P，然后再从二叉排序
树中删去它的直接前驱（或直接后继），如下图所示。
25北京邮电大学自动化学院
? 其二是令 *P的左子树为 *F的左子树，而 *P的右子树为
*S的右子树，如下图所示。
F
P
C PR
CL Q
QL S
SL
中序遍历,CL C ……Q L Q SL S P PR F
F
C
PR
CL Q
QL
SL
中序遍历,CL C ……Q L Q SL S PR F(5)
S
26北京邮电大学自动化学院
?删除算法
例 80
50 120
60 110 150
55 70
53
删除 50
80
60 120
110 15055 70
53
删除 60
80
55 120
110 15053 70
10
4 25
8 13
5
4
删除 10
8
4 25
5 13
4
删除 5
8
4 25
4 13
Ch5_10.c
27北京邮电大学自动化学院
三、二叉排序树的查找分析
? 二分法查找长度为 n的表的判定树是唯一的，而含有 n个结点
的二叉排序树却不是唯一的。由关键字序列
{45,24,53,12,37,93}构造而得的二叉排序树 (a)，
45
53
93
24
3712 a
24
12
37
45
53
93b
? ASL =（ 1+2+2+3+3+3） / 6 = 14/6
? 由关键字序列 {12,24,37,45,53,93}构造而得的二叉排序树
? ASL =（ 1+2+3+4+5+6） /6 =21/6
28北京邮电大学自动化学院
? 因此,含有 n个结点的二叉排序树的平均查找长度和树的形
态有关 。当先后插的关键字有序时，构成的二叉排序树蠕变
为单支树。树的深度为 n，其平均查找长度为（ n+1） /2，
和顺序查找相同，这是最差的情况，显然，最好的情况是二
叉排序树的形态和二分法查找的判定树相同，其平均查找长
度和 log2n成正比。那么，它的平均性能如何？
? 由此可见，在随机的情况下，二叉排序树的平均查找长度
和 log n是等数量级的。然而，在某些情况下（有人研究
证明，这种情况出现的概率约为 46.5%）。尚需在构成二
叉排序树的过程中进行“平衡化处理”，成为二叉平衡
树。
nnnP ln)11(2)( ??
三、二叉排序树的查找分析
29北京邮电大学自动化学院
四、平衡二叉树
? 1、平衡二叉树
? 平衡二叉树，它或者是一棵空树，或者是具有下列性质的二
叉排序树：它的左子树和右子树都是平衡二叉树，且左子树
和右子树高度之差的绝对值不超过 1。
? 若将二叉树上结点的平衡因子 BF(Balance Factor)定义为该
结点的左子树的深度减去它的右子树的深度，则平衡二叉树
上所有结点的平衡因子只可能是 -1,0,1。只要二叉树上有
一个结点的平衡因子的绝对值大于 1，则这棵树就不是平衡
二叉树。
? 平衡二叉树的优点,它的平均查找长度和 logN同数量级。
30北京邮电大学自动化学院
1、平衡二叉树
1
1
0
0
平衡二叉树
不平衡二叉树
0
100
-11
-1
0
10
0-1
2
0
100
-20
-1
31北京邮电大学自动化学院
? 构造二叉平衡（查找）树的方法是：在插入过程中，采用平
衡旋转技术。
? 例如,依次插入的关键字为 5,4,2,8,6,9
5
4
2
4
2 5
8
6
6
5 8
4
2
向右旋转
一次
先向右旋转
再向左旋转
2、如何使二叉排序树成为平衡二叉树
32北京邮电大学自动化学院
4
2 6
5 8
9
4
2
6
8
95
向左旋转一次
继续插入关键字 9
33北京邮电大学自动化学院
? 二叉树的平衡处理调整的规律可归纳为下列四种情况
1
B
2
A
BLh
AR h-1
BRh-1
插入结点
0
A
0
B
BL BR AR
LL
? （ 1）单向右旋平衡处理 由于在结点 *a的左子树根结点的
左子树上插入结点,*a的平衡因子由 1增加到 2，致使以 *a为
根结点的子树失去平衡，则需要进行一次向右的顺时针旋转
操作，如图所示。
? 中序遍历,BL B BR A AR
34北京邮电大学自动化学院
? （ 2）单向左旋平衡处理
-1
B
-2
A
BR h
AL h-1
插入结点
RR
0
A
0
B
AL BL BRBL h-1
? 由于在 *a的右子树根结点的右子树上插入结点,*a的平衡因
子由 -1变为 -2，致使以 *a为根结点的子树失去平衡，则需要
进行一次向左的逆时针旋转操作，如图所示。
? 中序遍历,AL A BL B BR
35北京邮电大学自动化学院
? （ 3）双向旋转（先左后右）平衡处理
-1
B
2
A
CLh-1
AR h-1
h-1 BL
插入结点
0
B
0
C
BL CL CR
LR
AR
-1
A
1
C
h-2 CR
中序遍历,B CL C CR A AR
? 由于在 *a的左子树根结点的右子树上插入结点,*a的平衡因
子由 1增加到 2，致使以 *a为根结点的子树失去平衡，则需要
进行两次旋转（先左旋后右旋）操作，如图所示。
36北京邮电大学自动化学院
? （ 4）双向旋转（先右后左）平衡处理
-1
B
-2
A
CLh-1
h-1 AL
插入结点
0
A
0
C
AL CL CR
RL
BR
-1
B1
C
BR h-1CR h-2
中序遍历,ALACLCCRBBR
? 由于在 *a的右子树根结点的左子树上插入结点,*a的平衡因
子由 -1增加到 -2，致使以 *a为根结点的子树失去平衡，则需
要进行两次旋转（先右旋后左旋）操作，如图所示。
37北京邮电大学自动化学院
3、在平衡树的二叉排序树 BBS上插入一个新的数据元素
? （ 1）若 BBST为空树，则插入一个数据元素为 e的新结
点作为 BBST的根结点，树的深度加 1；
? （ 2）若 e的关键字和 BBST的根结点的关键字相等
时，则不进行插入；
? （ 3）若 e的关键字小于 BBST的根结点的关键字，而
且在 BBST的左子树中不存在和 e相同关键字的结点，
则插入在 BBST的左子树上，并且当插入之后的左子树
深度增加（ +1）时，分别就不同情况处理之。
38北京邮电大学自动化学院
? *BBST的根节点的平衡因子为 1（左子树的深度大于右子树
的深度）：
? *BBST的根节点的平衡因子为 -1（右子树的深度大于左子
树的深度）：则将根结点的平衡因子更改为 0,BBST的
深度不变；
? *BBST的根节点的平衡因子为 0（左、右子树的深度相等）：
则将根结点的平衡因子更改为 1,BBST的深度加 1；
? 若 BBST的左子树根结点的平衡因子为 -1，则需进行先
向左、后向右的双向旋转平衡处理，并且在旋转处理
之后，修改根结点和其左、右子树根结点的平衡因
子，树的深度不变。
? 若 BBST的左子树根节点的平衡因子为 1，则需要进行
单向右旋平衡处理，并且在右旋处理之后，将根结点
和其右子树根结点的平衡因子更改为 0，树的深度不变
39北京邮电大学自动化学院
? （ 4）若 e的关键字大于 BBST的根结点的关键字，而且在
BBST的右子树中不存在和 e 有相同关键字的结点，则将 e
插入在 BBST的右子树上，并且当插入之后的右子树深度增
加（ +1）时，分别就不同情况处理之。其处理操作和（ 3）
中所述相对称。
40北京邮电大学自动化学院
? 理想的情况是希望不经过任何比较，一次存取便能得到所查
记录，那就是必须在记录的存储位置和它的关键字之间建立
一个确定的对应关系 f，使每个关键字和结构中唯一的存储
位置相对应。因而在查找时，只要根据这个对应关系 f找到
给定值 k的像 f(k) 。我们称 这个对应关系 f(k)为哈希函数，按
照这个思想建立的表为哈希表。
8.3 哈希表（散列表和查找）
编号 地区号 总人口 汉族 回族 ….
1 北京
? 假设要建立一张全国 30个地区的各民族人口统计表。
? 显然，可以用一个一维数组 C（ 1,30）来存放这张表，其中
C[i]是编号为 i地区的人口情况。编号 i便为记录的关键字，由
它唯一确定记录的存储位置 C[i]。
41北京邮电大学自动化学院
Key beijing
北京
tianjin
天津
Hebei
河北
shanxi
山西
Shanghai
上海
Shandong
山东
hena
n河南
sichua
n四川
f1(key) 02 20 08 19 19 19 08 19
f2(key) 09 04 17 28 28 26 22 03
f3(key) 04 26 02 13 23 17 16 16
? 为了查找方便应以地区名作为关键字。假设地区名以汉语拼音
的字符表示，则不能简单地取哈希函数，而是首先要将它们转
化为数字。
? （ 1）取关键字的第一个字母在字母表中的序号作为哈希函数；
? （ 2）先求关键字的第一个和最后一个字母在字母表中的序号
之和，然后判别这个值。若比 30大，则减去 30。
? （ 3）先求每个汉字的第一个拼音字母的 ASCII码之和的八进
制形式，然后将这个八进制数看成是十进制再除以 30取余
数。
42北京邮电大学自动化学院
? 从例子可见：
? （ 1）哈希函数只是一种映象，所以哈希函数的设定很灵
活，只要使任何关键字的哈希函数值都落在表长允许的范
围之内即可。
? （ 2）对于不同的关键字可能得到同一哈希地址，即
key1?key2,但 h(key1)=h(key2)，这种现象 叫 冲突 。
? 在一般情况下,冲突只能尽可能地少，而不能完全避免 。
8.3 哈希表（散列表和查找）
? 具有相同函数值的两个关键字对该哈希函数来说称做同义
词 。
43北京邮电大学自动化学院
? 根据设定的哈希函数和处理冲突的方法将 一组关键
字映象到一个有限的连续的地址集（区间）上,
8.3 哈希表（散列表和查找）
? 这一映象过程称为 哈希表或散列,
? 所得到存储位置称 哈希地址或散列地址 。
? 并以关键字在地址集中的“象”作为记录在表中的
存储位置,这种情况便称为 哈希表,
44北京邮电大学自动化学院
二、哈希函数的构造方法
? 若对于关键字集合中的任一关键字，经哈希函数映象
到地址集合中任何一个地址的概率是相同的，则此类
哈希函数为均匀的哈希函数。
? 直接定址法
? 数字分析法
? 平方取中法
? 折叠法
? 除留余数法
45北京邮电大学自动化学院
1、直接定址法
? 取关键字或关键字的某个线性函数作哈希地址，即
h(key)=key 或 h(key)=a·key+b
地址 01 02 03 25
年龄 1 2 3 25
人数 3000 2000 5000 1050
? 例如：有一个从 1岁到 100岁的人口数字统计表，年龄作为
关键字，哈希函数取关键字自身。
46北京邮电大学自动化学院
? 又如：有一个解放后出生的人口调查表，关键字是年
份，哈希函数取关键字加一常数：
? h(key） =key+(-1948)
地址 01 02 03 …,22
年份 1949 1950 1951 … 1970
人数 … 15000
? 这样，若要查 1970年出生的人数，则只要查（ 1970-
1948） =22项即可。由于直接定址所得地址集合和关键
字集合的大小相同，因此不会发生冲突,但实际中能使
用这种哈希函数的情况很少。
1、直接定址法
47北京邮电大学自动化学院
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
8 1 3 6 8 5 3 7
8 1 4 1 9 3 5 5
…..
…..
???????? ?只取 8
?只取 1
?只取 3,4
?只取 2,7,5
????数字分布近乎随机
取 ????任意两位或两位
与另两位的叠加作哈希地址
48北京邮电大学自动化学院
3、平方取中法
记录 关键字 （关键字） 2 哈希地址（ 217~29）
A 0100 0010000 010
I 1100 1210000 210
J 1200 1440000 440
I0 1160 1370400 370
P1 2061 4310541 310
? 通常在选定哈希函数时不一定能知道关键字的全部情况，取
其中哪几位也不一定合适，而一个数平方后的中间几位数和
数的每一位都相关，由此使随机分布的关键字得到的哈希地
址也是随机的。取的位数由表长决定。 例如：为 BASIC源
程序中的标识符
49北京邮电大学自动化学院
4、折叠法
? 将关键字分割成位数相同的几部分（最后一部分的位数可以不
同），然后取这几部分的叠加和（舍去进位）作为哈希地址。
这方法称为折叠法。关键字位数很多，而且关键字中每一位上
数字分布大致均匀时，可以采用折叠法得到哈希地址。
? 例 关键字为, 0442205864，哈希地址位数为 4
5 8 6 4
4 2 2 0
0 4
1 0 0 8 8
H(key)=0088
移位叠加
5 8 6 4
0 2 2 4
0 4
6 0 9 2
H(key)=6092
间界叠加
? 移位叠加,将分割后的几部分低位对齐相加
? 适于关键字位数很多，且每一位上数字分布大致均匀情况
? 间界叠加,从一端沿分割界来回折送，然后对齐相加
50北京邮电大学自动化学院
? 取关键字被某个不大于哈希表表长 m的数 p除后所得余
数作哈希地址，即
5、除留余数法
关键字 28 35 63 77 105
哈希地址 7 14 0 14 0
P=21
? 特点,简单、常用，可与上述几种方法结合使用,p的
选取很重要； p选的不好，容易产生同义词。
? H(key)=key MOD p,p?m
51北京邮电大学自动化学院
? 随机数法构造,选择一个随机函数，取关键字的随机函数
值为它的哈希地址，即 H(key)=random(key)，其中
random(key)为随机函数。通常，当关键字长度不等时采
用此法构造的哈希函数较恰当。
6、随机数法
? 实际工作中需视不同的情况采用不同的哈希函数。通常
考虑的因素有：
? （ 1）计算哈希函数所需时间
? （ 2）关键字的大小
? （ 3）哈希表的大小
? （ 4）关键字的分布情况
? （ 5）记录的查找频率
52北京邮电大学自动化学院
三、处理冲突的方法
? 通常用的处理冲突的方法有下列几种：
? 开放定址法
? 再哈希法
? 链地址法
? 建立一个公共溢出区
53北京邮电大学自动化学院
? 开放定址法 方法,当冲突发生时，形成一个探查序列；沿
此序列逐个地址探查，直到找到一个空位置（开放的地
址），将发生冲突的记录放到该地址中，即
Hi=(H(key)+di) MOD m,i=1,2,……k (k ?m-1)
1、开放定址法
? 其中,H(key)—— 哈希函数, m—— 哈希表表长, di——
增量序列
? di有下列三种取法
? 线性探测再散列, di=1,2,3,……m -1
? 二次探测再散列, di=12,-12,22,-22,32,…… ± k2(k?m/2)
? 伪随机探测再散列, di=伪随机数序列
54北京邮电大学自动化学院
? 例 表长为 11的哈希表中已填有关键字为 17,60,29的记
录,H(key)=key MOD 11,现有第 4个记录，其关键字为
38，按三种处理冲突的方法，将它填入表中
? (1) H(38)=38 MOD 11=5 冲突
? H1=(5+1) MOD 11=6 冲突
? H2=(5+2) MOD 11=7 冲突
? H3=(5+3) MOD 11=8 不冲突
? (2) H(38)=38 MOD 11=5 冲突
? H1=(5+12) MOD 11=6 冲突
? H2=(5-12) MOD 11=4 不冲突
? (3) H(38)=38 MOD 11=5,冲
突,设伪随机数序列为 9，则：
? H1=(5+9) MOD 11=3 不冲突
0 1 2 3 4 5 6 7 8 9 10
60 17 29 383838
55北京邮电大学自动化学院
? 构造若干个哈希函数，当发生冲突时，计算下一个哈
希地址，即：
2、再哈希法
? 其中 Rhi均是 不同的哈希函数，即在同义词产生地址冲
突时计算另一个哈希函数地址，直到冲突不再发生。
这种方法不容易产生,聚集”，但增加了计算的时
间。
? Hi=Rhi(key) i=1,2,……k
56北京邮电大学自动化学院
3、链地址法
? 将所有关键字为同义词的记录存储在一个单链表中，并用
一维数组存放头指针。例如已知一组关键字 (19,14,
23,1,68,20,84,27,55,11,10,79)
? 哈希函数为,H(key)=key MOD 13,
? 其每个分量的初始状态都是
空指针。凡哈希地址为 I的记
录都插入到头指针为
chainHash[i]的链表中。在
链表中的插入位置可以在表
头或表尾；也可以在中间，
以保持同义词在同一线性链
表中按关键字有序。
01 14 27 79
55 68
19 84
20
10 23
11
^
^
^
^
^
^
?13
12
11
?10
?9
8
7
?6
?5
4
?3
2
?1
57北京邮电大学自动化学院
4、建立一个公共溢出区
? 假设哈希函数的值域为 [0,m-1]，则向量 Hash
Table[0,m-1]为基本表，每个分量存放记录，另设立
向量 Over Table[0,v] 为溢出表。所有关键字和基本表
中关键字为同义词的记录，不管它们由哈希函数得到
的哈希地址是什么，一旦发生冲突，都填入溢出表
58北京邮电大学自动化学院
四、哈希表的查找与分析
? 1、哈希表的查找过程
? 在哈希表上进行查找的过程和哈希造表的过程基本
一致。给定 k值，根据造表时设定的哈希函数求得哈
希地址，若表中此位置上没有记录，则查找不成
功；
? 否则比较关键字
? 否则根据造表时设定的处理冲突的方法找“下一
地址”，直至哈希表中某个位置为“空”或者表
中所填记录的关键字等于给定值时为止。
? 若和给定值相等，则查找成功；
59北京邮电大学自动化学院
? 例 已知一组关键字 (19,14,23,1,68,20,84,27,55,11,10,79),哈希函数
为,H(key)=key MOD 13,哈希表长为 m=16,设每个记录的查找概率相等
? (1) 用线性探测再散列处理冲突，即 Hi=(H(key)+di) MOD m
H(55)=3 冲突,H1=(3+1)MOD16=4
冲突,H2=(3+2)MOD16=5
H(79)=1 冲突,H1=(1+1)MOD16=2
冲突,H2=(1+2)MOD16=3
冲突,H3=(1+3)MOD16=4
冲突,H4=(1+4)MOD16=5
冲突,H5=(1+5)MOD16=6
冲突,H6=(1+6)MOD16=7
冲突,H7=(1+7)MOD16=8
冲突,H8=(1+8)MOD16=9
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
ASL=(1*6+2+3*3+4+9)/12=2.5
14 1 68 27 55 19 20 84 79 23 11 10
H(19)=6
H(14)=1
H(23)=10
H(1)=1 冲突,H1=(1+1) MOD16=2
H(68)=3
H(20)=7
H(84)=6 冲突,H1=(6+1)MOD16=7
冲突,H2=(6+2)MOD16=8
H(27)=1 冲突,H1=(1+1)MOD16=2
冲突,H2=(1+2)MOD16=3
冲突,H3=(1+3)MOD16=4
H(11)=11
H(10)=10 冲突,H1=(10+1)MOD16=11
冲突,H2=(10+2)MOD16=12
60北京邮电大学自动化学院
(2) 用链地址法处理冲突
ASL=(1*6+2*4+3+4)/12=1.75
关键字 (19,14,23,1,68,20,84,27,55,11,10,79)
14 01 27 79
68 55
19 84
20
23 10
11
^
^
^
^
^
^
?13
12
11
?10
?9
8
7
?6
?5
4
?3
2
?1
61北京邮电大学自动化学院
? 从哈希表的查找过程可见：
2、哈希查找分析
? （ 1）虽然哈希表在关键字与记录的存储位置之间建立
了直接的映象，但由于“冲突”的产生，使得哈希表的
查找过程仍然是一个给定值和关键字进行比较的过程。
因此，仍需要以平均查找长度作为衡量哈希表的查找效
率的量度。
? （ 2）查找过程中需要和给定值进行比较的关键字的个
数取决于下列三个因素,哈希函数，处理冲突的方法和
哈希表的填满因子 ?。
62北京邮电大学自动化学院
? 哈希函数：假设函数是“均匀的”
? 在一般情况下，处理冲突方法相同的哈希表，其平均
查找长度依赖于哈希表的装填因子。
? 例如用两种不同的处理冲突方法的平均查找长度：
? 处理冲突的方法：对于同样一组关键字，设定相同的哈
希函数，则不同的处理冲突的方法得到的哈希表不同，
它们的平均查找长度不同：
? （ 1）用线性探测再散列处理冲突
? ASL=(1*6+2+3*3+4+9)/12=2.5
? 用链地址法处理冲突
? ASL=(1*6+2*4+3+4)/12=1.75
63北京邮电大学自动化学院
? 线性探测再散列的哈希表查找成功时的平均长度为：
)1 11(21 ????nlS
哈希表的长度
表中填入的记录数??? 哈希表的装填因子定义为：
? α标志哈希表的装满程度。直观地看,α 越小，发生冲突的
可能性就越小；反之,α越大，表中已填入的记录越多，再
填记录时，发生冲突的可能性就越大，则查找时，给定值
需要于之进行比较的关键字的个数也就越多。
? 随机探测再散列，二次探测再散列和再哈希表查找
成功时的平均查找长度：
)1ln (1 ?? ???nrS
64北京邮电大学自动化学院
? 链地址法处理冲突的哈希查找成功时的平均查找长
度：
? 不同的处理冲突方法构成的哈希表查找不成功时的
平均查找长度分别为：
))1( 11(21 2????nlU
??? 1
1
nrU
21
???
ncS
?? ??? eU nc
? 线性探测再散列
? 随机探测再散列
? 链地址法处理冲突
2、哈希查找分析
65北京邮电大学自动化学院
第 8章 上机实习题
?二叉排序树操作：
?基本要求
?（ 1）用二叉链表作为存储结构，输入键值
序列建立一棵二叉排序树；
?（ 2）按中序遍历这棵二叉树；
?（ 3）删除二叉树中的结点 x。
66北京邮电大学自动化学院
第 8章复习提纲
?1,顺序表、有序表和索引顺序表的查找方法及
其平均查找长度的计算方法。
?2,熟练掌握二叉排序树的构造和查找方法。
?3,熟练掌握哈希表的构造和查找方法，深刻理
解哈希表与其它结构的表的实质性的差别。
?4,掌握按定义计算各种查找方法在等概率情况
下查找成功时的平均查找长度
67北京邮电大学自动化学院
第 8章 作业
? 一、单项选择题
? 1、采用顺序查找法查找长度为 n的线性表时，每个元素的平均查找长度
为 。
? （ A） n （ B） n/2 （ C） (n+1)/2 （ D） (n-1)/2
? 2、在一个长度为 12的有序表，按折半查找法对改表进行查找，在表内各
元素等概率情况下查找成功所需的平均比较次数为 。
? （ A） 35/12 （ B） 37/12 （ C） 39/12 （ D） 43/12
? 3、查找效率最高的二叉排序树是 。
? （ A）所有结点的左子树都为空的二叉排序树
? （ B）所有结点的右子树都为空的二叉排序树
? （ C）平衡二叉树 （ D）没有左子树的二叉排序树
68北京邮电大学自动化学院
? 4、以下说法错误的是 。
? A、散列法存储的基本思想是由关键码值决定数据的存储地址
? B、散列表的结点中只包含数据元素自身的信息，不包含任何指针
? C、装填因子是散列法的一个重要参数，它反映了散列表的装填程度
? D、散列表的查找效率主要取决于散列表造表时选取的散列函数何处理
冲突的方法
5、散列表的平均查找长度 。
A、与处理冲突方法有关与表长无关
B、与处理冲突方法无关与表的长度有关
C、与处理冲突方法有关且与表的长度有关
D、与处理冲突方法无关且与表的长度无关
第七章 作业
69北京邮电大学自动化学院
? 二、填空题
? 1、设线性表（ a1,a2,…, a500）元素的值由小到大排列，
对一个给定的 k值用折半法查找线性表，在查找不成功的情况
下至多需比较 次。
? 2、一个无序序列可以通过构造一棵 树而变成一个
有序序列，构造树的过程即为对无序序列进行排序的过程。
? 3、在散列存储中，装填因子 ?的值越大，则 ； ?的值
越小，则
第七章 作业
70北京邮电大学自动化学院
? 1、输入一个正整数序列 {40,28,6,72,100,3,54，
1,80,91,38}，建立一棵二叉排序树，然后删除结点
72，分别画出该二叉树及删除结点 72后的二叉树。
? 2、设有一组关键字 {19,01,23,14,55,20,84，
27,68,11,10,77}采用散列函数 H(key)=key%13，采
用开放地址法的线性探测再散列方法解决冲突，试在 0～
18的散列地址空间中对该关键字序列构造散列表。
第七章 作业
71北京邮电大学自动化学院
第 8章 上机时间及地点
班 级 时 间 地 点 老 师
0215301～ 302 12.24日 (周五）
14:00~17:00
4－ 328
4－ 328
张志霞
李维成
03501~502 12.25日 (周六）
14:00~17:00
4－ 327
4－ 328
杜 伟
王松月
03503～ 04 12.25日 (周六）
16:00~19:00
4－ 328
4－ 328
王松月
杜 伟
03507~509 12.25(周六）
18:00~22:00
4－ 327
4－ 328
李维成
张志霞
72北京邮电大学自动化学院
考试时间
班 级 时 间 地 点 监考老师
03501~502 01.09日 (周日）
8:30~10:30
杜 伟
王松月
03503～ 04 01.09日 (周日）
8:30~10:30
王松月
杜 伟
注：考试地点另行通知
0215301～ 302,03507~509班的考试时间
及地点由学校安排
