1
第九章 查找
? 静态查找表静态查找表
? 动态查找表动态查找表
? 哈希查找表哈希查找表
数
据
结
构
之
查
找
2
9.1 基本概念 (Page 214)
?查找表：是由同一类型数据元素构成的集合。
?静态查找表：只做“查询”或“检索”操作。
?动态查找表：查询、检索、插入、删除。
?关键字：是数据元素中某个数据相的值，用
它可以标识一个数据元素。
主关键字、次关键字
?查找：根据给定值，在查找表中确定一个其
关键字等于给定值的数据元素。
查找成功返回位置序号、查找不成功返回0
2
数
据
结
构
之
查
找
3
注意
比较各种查找算法时间
复杂度和空间复杂度，
查找算法的主要时间用
于“关键字的比较”。
数
据
结
构
之
查
找
4
9.2 静态查找表
?顺序表的查找
typedef int KT ;
typedef struct{KT key ; ... }ET;
typedef struct{ET *elem; //数据元素存储空间基址，
0为空单元
int length;}SST;
int Search_Sq(SST ST, KT key){
St.elem[0].key=key;//设置哨兵
for(i=ST.length ; key!=ST.elem[i].key; i--) ;
return i;
}
3
数
据
结
构
之
查
找
5
?顺序表的查找算法性能分析
在等概率的情况下：Pi=1/n
?查找成功时的平均查找长度：(n+1)/2
?查找不成功时的比较次数：n+1
?假设查找成功与不成功的可能性相同，
在等概率的情况下：Pi=1/2n , 则顺序
查找的平均查找长度为：
ASLss=((n+1)+(n+1)/2)/2=3(n+1)/4
数
据
结
构
之
查
找
6
?有序表的查找——折半查找
?折半查找（二分查找）：经过一次比较将
表分割成两部分，然后只在表的一部分中
继续进行查找的方法。
mid=(low+high)/2
key =13
4
数
据
结
构
之
查
找
7
?二分算法描述
int Search_Bin(SST ST, KT key){
low=1 ; high=ST. length;
while(low<=high){
mid=(low+high)/2;
if(key==ST.elem[mid].key) return mid;
else if(key<ST.elem[mid].key)
high=mid-1;
else low=mid+1; }
return 0;
}//时间复杂度：O(log2 n)
数
据
结
构
之
查
找
8
?二叉树的性质
1、在二叉树的第i 层上至多有2 个结点(i>=1);
2、深度为k的二叉树至多有2 -1个结点(k>=1);
3、对任何一棵二叉树T，如果其终端结点数为
n0，度为2的结点数为n2，则n0=n2+1。
4、具有n个结点的完全二叉树的深度为:
?log2 n? +1
k
i-1
5
数
据
结
构
之
查
找
9
?二叉判定树
?查找过程可用二
叉树来描述。树
中每个结点表示
一个记录，结点
中的值为该记录
在表中的位置，
通常这个描述查
找过程的二叉树
为判定树。
?在该树中，和给
定值进行比较的
次数恰为该结点
在判定树中的层
次。
数
据
结
构
之
查
找
10
?性能分析
比较次数最多：
?log2 n?+1
不超过判定树的深度
时间复杂度：
O(log2 n)
?此方法只能适用
于有序表，且限
于顺序存储结构。
6
数
据
结
构
之
查
找
11
?索引顺序表的查找（分块查找）要求：
?索引表
?按表中记录的关键字分块, R
1
,R
2
,…,R
L
第R
k
块中所有关键字< R
k+1
块中的所有关键字
k=1,2,…,L-1, 称为“分块有序”
?对每块建立一个索引项, 包含有两项内
容:
?关键字项: 为该块中最大关键字值;
?指针项: 为该块第一个记录在表中位置.
?所有索引项组成索引表
数
据
结
构
之
查
找
12
?查找过程
?确定待查记录所在块; (可以用顺序或折半查
找)
?在块内顺序查找. (块内查找只能用顺序查找)
22 1 48 7 86 13
22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53
12345678910112 13 14 15 16 17 18
索引表
查找数据24
7
数
据
结
构
之
查
找
13
?性能分析
ASL
bs
=L
b
+L
w，
L
b
为确定块的平均查找长度；L
w
为块内查找次数。
若顺序查找：ASL
bs
=L
b
+L
w
=(n/s+s)/2+1
若折半查找：ASL
bs
=L
b
+L
w
= log
2
(n/s+1)+s/2
三种查找方法比较三种查找方法比较
顺序查找顺序查找折半查找折半查找
分块查找分块查找
ASL大大小小中中
表结构要求表结构要求
无无有序表有序表
块之间有序块之间有序
数
据
结
构
之
查
找
14
9.3 动态查找表
?二叉排序树(BST)
?二叉排序树的定义：page 227
?查找过程
?二叉排序树的插入和删除
?二叉排序树的查找分析
含有n个结点的二叉排序树的平均查找长度
和树的形态有关：最差的形态是：单支树
( (n+1)/2 )；最好的形态是：判定树( log
2
n )。
在随机情况下，二叉排序树的平均查找长度
和log n是等数量级的。
8
数
据
结
构
之
查
找
15
数
据
结
构
之
查
找
16
?查找算法
?当前BST非空时，将给定值k与当前根结
点的关键字比较:
?若相等，查找成功，结束; 若k小于当前根
结点的关键字，则将左子树作为当前BST;
若k大于当前根结点的关键字，则将右子
树作为当前BST;
?重复(1)。
9
数
据
结
构
之
查
找
17
BT SearchBST ( BT T,int key )
{
if ( ( !T ) || key = =T->data) )
return ( T );
else if (key<T->data)
return ( SearchBST ( T->lchild, key ) );
else
return ( SearchBST ( T->rchild, key ) );
}
数
据
结
构
之
查
找
18
Status Search_Bit(BT T,BTN &f ,BTN &p, int
key){
// f 是p 的双亲结点指针
p=T; f=T ;
while(p){
if(p->data==key) return TRUE;
else if(key<(p->data)){ f = p ; p=p->lchild; }
else {f = p ; p=p->rchild ; }
}
return FALSE; }
10
数
据
结
构
之
查
找
19
?在二叉排序树中插入关键字为key 的结点
Status Insert_Bit(BT T ,int key ){
if( !Search_Bit(T , f , p , key )){
p=(BTN *)malloc(sizeof(BTN));
p->lchild=p->rchild= NULL;
p->data = key ;
if(!f ) T= p;
else if (key<(f->data) ) f->lchild=p;
else f->rchild=p;
return OK; }
return ERROR ;
}
数
据
结
构
之
查
找
20
例： 将序列（45，24，53，12，24，90）
构造成为二叉排序树。
11
数
据
结
构
之
查
找
21
? BST的特点：
?中序遍历BST可得到一个关键字的有序
序列。
?在BST上插入新结点时，不必移动其他
结点，仅需改动某结点的指针（因新结点
总是BST上的一个新叶结点）。
? BST既具有类似折半查找的特性（与BST
的平衡度有关）又采用了链表存储结构
（折半查找不能为链表存储结构），因此，
对于经常要进行查找、插入和删除记录的
有序表，采用BST尤其合适。
数
据
结
构
之
查
找
22
?平衡二叉树(AVL树)：
?定义：它或是一棵空树，或者是左子树
和右子树的深度之差的绝对值不超过1；
且左子树和右子树都是平衡二叉树。
?平衡因子BF：是该结点的左子树的深度
减去它的右子树的深度。
?平衡二叉树上的所有结点的平衡因子只
可能是-1，0，1。
?在构成二叉排序树的过程中进行“平衡
化”处理，成为二叉平衡树
12
数
据
结
构
之
查
找
23
例：平衡二叉树与非平衡二叉树的比较。
平衡二叉树
非平衡二叉树
数
据
结
构
之
查
找
24
二叉平衡树的平衡调整的四种基本类型
L
L
型
R
R
型
插入
元素
1
插入
元素
9
13
数
据
结
构
之
查
找
25
L
R
型
R
L
型
数
据
结
构
之
查
找
26
LL型平衡旋转（顺时针）型平衡旋转（顺时针）
失去平衡点的平衡因子为失去平衡点的平衡因子为2, 其左孩子的平衡因子为其左孩子的平衡因子为1
LL
0
A
A
R
B
R
h-1h-1
0
B
B
L
h h
2
A
a
A
R
h-1
1
B
B
R
B
L
h-1h
h+1
L
+1
14
数
据
结
构
之
查
找
27
RR型平衡旋转（逆时针，与型平衡旋转（逆时针，与LL对称对称)
失去平衡点的平衡因子为失去平衡点的平衡因子为-2, 其右孩子的平衡因子为其右孩子的平衡因子为-1
-2
A
A
L
B
L
h-1
h-1
-1
B
h
B
R
RR
0
B
B
L
A
L h-1
0
A
B
R
数
据
结
构
之
查
找
28
LR型平衡旋转型平衡旋转
失去平衡点的平衡因子为失去平衡点的平衡因子为2, 其左孩子的平衡因子为其左孩子的平衡因子为-1
2
A
A
R
h-1
-1
B
B
L
C
L
h-1
h-1
h+1
1
C
h
h-2
C
R
LR
0
C
A
R
h-1
0
B
B
L
C
L
h-1
h-1
-1
A
h-2
C
R
中序遍历：中序遍历：B
L
B C
L
C C
R
A A
R
B
L
B C
L
C C
R
A A
R
15
数
据
结
构
之
查
找
29
RL型平衡旋转型平衡旋转
失去平衡点的平衡因子为失去平衡点的平衡因子为-2, 其右孩子的平衡因子为其右孩子的平衡因子为1
RL
0
C
B
R
0
A
A
L
C
L
-1
B
h-2
C
R
1
B
B
R
h-1
-2
A
A
L h-1
C
L
h-1
1
C
h-2
C
R
中序遍历：中序遍历：A
L
A C
L
C C
R
B B
R
A
L
A C
L
C C
R
B B
R
数
据
结
构
之
查
找
30
?平衡化算法
?平衡二叉排序树的类型定义：
typedef struct BSTN{
Elemtype data;
int bf; /* 结点的平衡因子*/
struct BSTN *Lc , *Rc; } BSTN ,*BST;
1. 右旋处理：p指向旋转处理之前的左子树的根结点
void R_rotate( BST &p){ lc=p->Lc ;
p->Lc=lc->Rc ; lc->Rc=p ; p=lc;}
2. 左旋处理：p指向旋转处理之前的右子树的根结点
void L_rotate(BST &p) { rc=p->Rc ;
p->Rc= rc->Lc ; rc->Lc=p ; p=rc ; }
A
B
p
lc A
B
p
rc
16
数
据
结
构
之
查
找
31
?对二叉树T作左平衡旋转
void LeftBalance( BST &T){ lc =T->Lc;
switch(lc->bf){
case 1: T->bf = lc->bf =0;
R_rotate(T); break;
case -1: rd = lc->Rc;
switch(rd->bf){
case 1:T->bf = -1 ; lc->bf =0;break;
case 0:T->bf = lc->bf =0;break;
case -1:T->bf =0;lc->bf =1; }
rd->bf =0;
L_rotate(T->Lc); R_rotate(T); } }
数
据
结
构
之
查
找
32
?在平衡二叉排序树上插入元素
Status InsertAVL(BST &T, ElemType e ,Boolean &taller)
{ if(!T) { T=(BST)malloc(sizeof(BSTN)); T->data=e;
T->Lc=T->Rc=NULL;T->bf =0;taller =TRUE; }
else { if( e.key==T->data.key){taller=FALSE;return 0;}
if((e.key<T->data.key){k =InsertAVL(T->Lc,e,taller);
if(!k) return 0;
if(taller) switch(T->bf){
case 1: LeftBalance(T);taller =FALSE;break;
case 0: T->bf =1;taller =TRUE; break;
case -1: T->bf =0;taller =FALSE; } }
else {k = InsertAVL(T->Rc , e , taller );
17
数
据
结
构
之
查
找
33
if(!k) return 0;
if(taller)
switch(T->bf){
case 1: T->bf =0 ;
taller=FALSE;break;
case 0:T->bf = -1 ;
taller=TRUE ; break;
case -1: RightBalace(T) ;
taller = FALSE ; } }
}
return 1;
}
数
据
结
构
之
查
找
34
7.4 B-树
? B-树的定义：一棵m阶B-树，或为空树，或
为满足下列特性的m叉树：
?树中每个结点至多有m棵子树；
?若根结点不是叶子结点，则至少有两棵子树；
?除根之外的所有非终端结点至少有?m/2?棵子树；
?所有的结点中包含下列信息数据(P 239)
( n , A0 , K1 , A1 , K2 , A2 ,......, Kn , An ) (Ki<Ki+1)
?所有的叶子结点都出现在同一层次上。
例如：3阶B-树的非终端结点：
N A0 Key1 A1 Key2 A2
18
数
据
结
构
之
查
找
35
一棵四阶的B
-
树
1 11
351
1 18
1 27 1 9964533 47
78432
1 39
F FF F F FFFF FFF
数
据
结
构
之
查
找
36
B-树的查找
3 阶B-树
30
25 48 32 , 38
50
45
57
Key = 38
t
19
数
据
结
构
之
查
找
37
? B 树的插入
在B 树中插入时，形成的结点‘分裂’是
由下层结点逐步向上层传递的，在极端
情况下，会一直传递到根结点（实际上，
这是B 树长高的唯一途径）。
38 , 45 , 57
45
38 57
45 , 57
结点分裂
插
入
38
依次插入48，25，30
数
据
结
构
之
查
找
38
45
25 , 30 , 38 48 , 57
30 , 45
25
48 , 50 , 57
38
30
25 48 32 , 38
50
45
57
试依次插入32，15，55，35，20，41，90
插入50，
产生两次
结点分裂
20
数
据
结
构
之
查
找
39
B
-
树
的
删
除
操
作
?可能形成结
点的合并
? B-树的高度
降低。30
25 48 32 , 38
50
45
57
32
25 48 38
50
45
57
32 , 45
25
48 , 57
38
1.删除关键字30
2.删除关键字50
数
据
结
构
之
查
找
40
7.5 哈希表
?概念
?哈希函数：在记录的存储位置和它的关键字之
间建立一个确定关系f ，是每个关键字和结构
中一个唯一的存储位置对应。这个对应关系f
为哈希函数。根据这个思想建立的表为哈希表。
?同义词：若key1 != key2 ,而f(key1)=f(key2)，
则这种现象成为冲突，且key1和key2对哈希
函数f 来说称为同义词。
关键字集A
m
地址空间D
n
哈希函数哈希函数
H（（k））
21
数
据
结
构
之
查
找
41
?哈希造表或散列：根据设定的哈希函数f
=H(key)和处理冲突的方法，将一组关键
字映象到一个有限的连续地址集（区间）
上，以关键字的哈希函数值作为记录在表
中的位置，这一映象过程称为哈希造表或
散列。记录的存储位置叫哈希地址或散列
地址
?关键问题
?构造好哈希函数的方法;
?研究解决冲突的方法。
数
据
结
构
之
查
找
42
?装填因子：
表中填入的记录数
α =
哈希表的长度
α标志哈希表的装满程度：
α越小，发生冲突的可能性就越小；反之，
α越大，表中已填入的记录越多，再填记
录时，发生冲突的可能性就越大。
22
数
据
结
构
之
查
找
43
?哈希函数的构造方法
?判定标准
?计算简单容易
?冲突极少
?直接地址法：取关键字或关键字的某个线性
函数值为哈希地址。
H(key)=key 或H(key)=a*key+b
例：开辟60个记录的存储区，key =年号
H(key)=key -1949哈希地址
H(1949)= 0 H(1962)= 13
H(1950)= 1 H(1963)= 14
H(1951)= 2 H(1964)= 15
.............. H(1998)= 49
数
据
结
构
之
查
找
44
?除留余数法：取关键字被某个不大于哈希表表
长m的数p除后所得余数为哈希地址。
H(key)=key mod p ( p ≤ m)
例：开辟38 个记录的存储区，
key = 学号% 1000
H(key)=key % 38
H(031)= 31 H(044)= 6
H(032)=32 H(045)= 7
H(033)= 33 H(046)= 8
.............. H(069)= 31
H(071)=33 //031和069是同义词，散列时产生冲突
通常，选择p≤m的某个质数。
23
数
据
结
构
之
查
找
45
?数字分析法
假设关键字是以r 为基的数，并且哈希表中可能出现的关键
字都是事先知道的，则可取关键字的若干数位组成哈希地址。
?平方取中法
取关键字平方后的中间几位为哈希地址。
?折叠法
将关键字分割成位数相同的几部分，然后取这几部分的叠加
和。
?随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址。
即：H(key)=random(key)。
数
据
结
构
之
查
找
46
?处理冲突的方法
?开放地址法：（探测法）
Hi=(H(key)+di) mod m
（1）线性探测再散列：di=1,2,3,4,.....,m-1
（2）二次探测再散列：di=±k*k ( 1 ≤ k ≤ m/2)
（3）伪随机探测再散列：di=伪随机数列
?再哈希法：用另一个哈希函数计算地址，直到
冲突不再发生。
?链地址法：将所有的关键字为同义词的记录存
储在同一线性链表中。（Page 258）
?建立一个公共溢出区：Hash表分为基本表和
溢出表，所有发生冲突的关键字都填入溢出表。
2
24
数
据
结
构
之
查
找
47
例： 长度为16的哈希表中已有关键字节19，70，33，
H(key)= key mod 13，现有18，用开放地址法
处理冲突。
解：其处理方法如下图所示。
181918 3370
0123456789101 12
…
15
二次探测线性探测
数
据
结
构
之
查
找
48
例：H（key）= key mod 13 , 采用线性探测再散列法处理冲突, m=16
对关键字19，14，23，01，68，20，84，27，55，11，10，79
19，14，23，01，68，20，84，27，55，11，10，79
61101 376 1 3 11 10 1
↓ ↓↓↓ ↓↓
2 7 2 4 11 2
↓↓ ↓ ↓↓
8 3 5123
4 4
↓
.
.
.
↓
9
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
19
14 2301 68 20 8427 55 11 1079
25
数
据
结
构
之
查
找
49
H（key）= key mod 13
对关键字19，14，23，01，68，20，84，27，55，11，10，79
链地址法链地址法处理的结果为：
0
1
2
3
4
5
6
7
8
9
10
11
12
79
01 14
6855
1984
20
2310
11
∧
∧
∧
∧
∧
∧
27
∧
∧
∧
∧
∧
∧
∧
数
据
结
构
之
查
找
50
0
1
2
3
4
5
6
7
8
9
10
11
12
∧
∧
68
∧
∧
19
20
∧
∧
23
11
∧
14
Hash表
01
27
55
10
79
84
溢出表
顺序查找
H（key）= key mod 13
对关键字19，14，23，
01，68，20，84，27，
55，11，10，79
公共溢出区法公共溢出区法处理的结
果为：
26
数
据
结
构
之
查
找
51
两种方法平均查找长度的比较：
链地址法：
ASL(12)=(1*6+2*4+3+4)/12=1.75
线性探测再散列：
ASL(12)=(1*6+2+3*3+4+9)/12=2.5
因此，线性探测在散列在处理冲突的过程中
易产生记录的二次聚集，而链地址法处理冲
突时不会发生类似情况，故其平均查找长度
较优。
数
据
结
构
之
查
找
52
?哈希表算法描述
1.计算哈希地址#define ListLen 13
int Hash(int key){return(key %Listlen);}
2.哈希表查找
int Search_H(int A[ ] , int key){
k=Hash(key);
for(i=0;i<ListLen ;i++){
j=(k+i)%ListLen;
if(A[ j]==0 || key==A[j] ) return j; }
return k;
}
27
数
据
结
构
之
查
找
53
3. 在哈希表中插入关键字key
Insert_Hash( int H[ ] ; int key ){
k=Search_H( H , key);
if( H[k]==0 ) H[k]=key ;
else if(key==H[k]) printf(“表中已存在该关键字”);
else printf(“哈希表已满!! ”);
}
main( ){ int H[ListLen] , i, key;
for( i=0; i<ListLen; i++) H[ i ]=0; //置空
for(i=0;i<ListLen-2 ; i++){
scanf(“%d”, &key);
Insert_Hash(H, key); }
}
数
据
结
构
之
查
找
54
要求掌握的内容
1. 熟练掌握除留余数法，会构造Hash函数。
2. 根据哈希函数和处理冲突的方法，
（1）手工构造已知序列的哈希表。
（2）编写构造哈希表的算法。
（3）编写在哈希表上的查找算法；
（4）在记录的查找概率相等的前提下，
计算哈希表平均查找长度。
28
数
据
结
构
之
查
找
55
?本章重点
?与查找有关的基本概念及存储结构。
?静态查找表：顺序表的查找，有序表的查
找，索引顺序表的查找。
?动态查找表：二叉排序树的构造过程，插
入及删除操作；平衡二叉树几种类型的调
整；B-树的定义，插入及删除操作。
?各种查找方法的性能比较。
?哈希函数及哈希表；哈希函数的构造方法；
处理冲突的方法。
第九章查找
作业
29
数
据
结
构
之
查
找
57
查找 ——作业
1. 已知一组关键字为（38，65，20，18，50，90，35，
80，100，95，61，19），依次插入关键字生成一
棵二叉排序树，问：
（1）查找关键字等于61的结点记录需比较次；
（2）与61比较的关键字序列是；
（3）如果将关键字为85的记录插入到树中，它将作
为结点的孩子结点；
（4）若要删除关键字为65的记录，可以取或
替换65作为38结点的右子树的根。
2. 什么叫二叉平衡树？试按下列次序将各关键字插入
到二叉平衡树中，画出重新平衡的情况。
（8，9，10，2，1，5，3，6，4，7，11，12）
数
据
结
构
之
查
找
58
编写算法
1. 在二叉排序树T（二叉链存储）中插入一个结点p；
2. 在二叉排序树T中删除任一结点q；
3. 根据给定关键字序列，生成一棵二叉排序树。
4. 分别对LL型、RR型、LR型、RL型的二叉排序
树T( T所指结点的平衡因子为2 或-2 )进行平衡
化处理。
5. 设计实现分块查找的算法。
30
数
据
结
构
之
查
找
59
哈希表作业
设哈希表长为13，散列函数为H(k)=k mod 13，
关键字序列为7，4，1，14，100，30，5，9，
20，134；试求：
（1）散列后的表中关键字分布（假定解决
冲突的方法为线性探测再散列法）；求平均
查找长度ASL；
（2）求出散列后的表的装填因子；
（3）用链地址法解决冲突，给出相应的哈
希表，求ASL；
（4）分别计算该序列用顺序查找法和排序
之后用折半查找的ASL。
