内容提要
? 8.1 查找的基本概念
? 8.2 静态查找表
? 无序表查找
? 有序表查找
? 分块查找
??8.3 动态查找表
? B树
? B+树
? 8.4 哈希表
8.1 查找的基本概念
关键字,表示数据元素的数据项
查找,寻找关键字满足特定条件的数据元素的过
程
查找表,用于查找的数据结构，可能是线性结构
，也可能是非线性结构
静态查找,查找过程中，不会修改查找表的查找
操作
动态查找,查找的目的是为了修改查找表，通常
是查找成功则删除结点，查找失败则插入结
点
平均查找长度,查找过程中的平均比较次数，它
是比较查找算法优劣的依据
2、静态查找表
(1)无序表的查找
int sqsearch(SQLIST L,int aidkey)
{int j;
for(j=0;j<L.len;j++)
if(L.elem[j].key==aidkey) return j;
return -1;
}
(2)有序表的查找
I.线性查找算法,
int sqsearch(SQLIST L,int aidkey)
{int j;
for(j=0;j<L.len&&L.elem[j].key<=aidkey;j++)
if(L.elem[j].key==aidkey) return j;
return -1;
}
静态查找表基本上
不作插入和删除操
作,一般采用顺序
存储结构
2、静态查找表 (cont’d)
(2)有序表的查找
II.折半查找算法,
int binsearch(SQLIST L,int aidkey)
{ int low,high,mid;
low=0; high=L.len-1;
while(low<=high)
{ mid=(low+high)/2;
if(L.elem[mid]==aidkey) return mid;
else if(L.elem[mid]>aidkey) high=mid-1;
else low=mid+1;
}
return -1;
}
12 2
3 3 3 3
4 4 4
1+2*2+4*3+3*4=29
O(29/10)
1 2 3 4 5 6 7 8 9 10
2、静态查找表 (cont’d)
(2)有序表的查找
III.斐波那契查找,
根据斐波那契序列的特点对有序表分割
0.618法
斐波那契序列
1 2 3 5 8 13 21 34 55······f(n)······
f(n+2)=f(n)+f(n+1)
从 20个数的数表中查找一个纪录
先找比较第 13个，如果小，再比较第 8个,····
如果大 比较后几个数的第 5个 ······
每次都比较位于这个数列的黄金分割点 0.618处
比如 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
16
查找 15的位置
2、静态查找表 (cont’d)
(2)有序表的查找
IV.插值查找,
应用条件：查找表中关键字分布均匀
查找失败时，确定下一个比较对象的方法：
lo wlo wh ig hk e ylo we le mLk e yh ig he le mL k e ylo we le mLa id k e yi ????? )(*].[.].[,].[.
2、静态查找表 (cont’d)
(3)分块查找
将查找表分成若干块，块的大小可以不等，块内可
以是无序的，但块间是有序的。比如，前面块内的所有
关键字都比后面的小。
利用索引表记录每个块的起点和终点和块内的最大
关键字。查找时先在索引表中搜索确定，需要在哪个块
内查找，然后，在到查找表特定区间内去搜索。
36 54 43 28 49 25 58 74 63 65 76 94 101138146,..
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
54 94 154 ……..最大关键字
0 6 12 ……..块起始地址
3、动态查找表
(1)B树 (B-树 )
I,B树的定义,一棵 m叉 (或称 m阶 )B树，或者是空树，或者是满足下
面特性的 m叉排序树 (lchild<parent<rchild)：
①每个结点至多有 m棵子树，
②如根结点不是叶，至少有两棵子树，
③除根之外，所有非终端结点至少有 ┌m/2 ┐(m/2向上取整 )棵
子树,以后记为 [m/2]
④ 所有的非终端结点含有信息
最多 [m/2]-1个关键字
Ai是子树指针,Ki是关键字，结点内部关键字有序
⑤所有叶结点都在同一层次,叫做失败结点。
AVL树,B树和 B+树都是常用的动态查找
表
AnKn······K2A1K1A0n
3、动态查找表 (cont’d)
(1)B树 (B-树 )
II,B树的查找,
过程演示
·35·1
·18·1 ·78·43·2
·11·1 ·27·1 ·39·1 ·99·1·53·47·2
F F F F F F F F F F F
53
3、动态查找表 (cont’d)
(1)B树 (B-树 )
III,B树的插入,先查找插入的位置，必然在最低一层结点有序插入
！但结点的插入可能会导致结点被撑破，需要分两种情况处理：
(1)如果插入关键字后,叶子结点中的关键字数量 <=m-1，则插入操
作完毕。
(2)如果插入后，叶子结点中的关键字数量是 m，则需要将叶子结点
一分为 2，成为 2个叶子，中间的关键字携带着新叶子结点的指针上
升到双亲结点中。这就转化为在双亲结点中插入一个关键字的问题
了。
这个问题的处理仍需要按照 (1)(2)两种情况处理，一直到增加关键字
的结点未满或者新生成根结点为止。
·35·1
·18·1 ·78·43·2
·11·1 ·27·1 ·39·1 ·99·1·53·47·2
F F F F F F F F F F F
向一棵 3阶 B树增加一个关键字 60
插入底层
·35·1
·18·1 ·78·43·2
·39·1 ·99·1·60·53·47·3
F F F F F F F
增加一个关键字 60
将 53上移结点分裂
·35·1
·18·1 53 ·
·
78·43·3
·39·1 ·99·1·47·1
F F F F F F
增加一个关键字 60
·60·1
F F
再将 53上移结点分裂
·53·35·2
·18·1 1 · ·78·43·1
·39·1 ·99·1·47·1
F F F F F F
增加一个关键字 60
·60·1
F F
3、动态查找表 (cont’d)
(1)B树 (B-树 )
IV,B树的删除,先找到要删除的关键字，如果查找失败，删除操作
终止。如果查找成功，则区分两种情况处理：
(1)如果关键字位于非叶子结点中，则利用它的直接后继替代它，
然后删除它的直接后继。它的直接后继是它的右子树最左端的叶子
结点的最左边的关键字。问题就转化为第二种情况。
(2)如果关键字位于叶子结点中，删除操作仍需要分两种情况处理
,·53·35·2
·18·1 1 · ·78·43·1
·39·1 ·99·1·47·1
F F F F F F
·65·60·2
F F F
删除 5360
3、动态查找表 (cont’d)
① 删除后，结点关键字数量 >=[m/2]-1，删除完成。
②删除后，结点关键字数量 <[m/2]-1，
?若该结点的左右兄弟结点中有一个关键字数大于 [m/2]-1，则将
其兄弟结点中最小或最大的关键字上移至双亲结点中，而将双
亲结点中小于或大于且紧靠该上移关键字的关键字下移至被删
除关键字所在结点中。所谓的“借”个关键字，但借关键字同
时，也要借该关键字左边或右边的子树指针！
?若该结点的左右兄弟结点的关键字数都等于 [m/2]-1，则将其与
一个兄弟结点合并,双亲结点中，左右兄弟中间的关键字下移
到合并的结点中去。
? 重复上面 2步，直到不再发生合并为止。
·53·35·2
·18·1 1 · ·78·43·1
·39·1 ·99·1·47·1
F F F F F F
·65·60·2
F F F
删除 99
65
781
3、动态查找表 (cont’d)
① 删除后，结点关键字数量 >=[m/2]-1，删除完成。
②删除后，结点关键字数量 <[m/2]-1，
?若该结点的左右兄弟结点中有一个关键字数大于 [m/2]-1，则将
其兄弟结点中最小或最大的关键字上移至双亲结点中，而将双
亲结点中小于或大于且紧靠该上移关键字的关键字下移至被删
除关键字所在结点中。所谓的“借”个关键字，但借关键字同
时，也要借该关键字左边或右边的子树指针！
?若该结点的左右兄弟结点的关键字数都等于 [m/2]-1，则将其与
一个兄弟结点合并,双亲结点中，左右兄弟中间的关键字下移
到合并的结点中去。
? 重复上面 2步，直到不再发生合并为止。
·53·35·2
·18·1 1 · ·78·43·1
·39·1 ·99·1·47·1
F F F F F F
·65·60·2
F F F
删除 47
0
·39·2
F F
删除
43
1
· ·782
删除
53
3、动态查找表 (cont’d)
(2)B+树
? B-树的变形
? 根结点 (非叶时 )至少有两个结点
? 除根外，非叶结点至少有 [m/2]棵子树
? 最多有 m棵子树,非叶结点都是索引，含有子树中的最大或最少关
键字
? 含有 n个关键字的非叶结点有 n棵子树
? 所有的叶子结点都在同一个层次上，叶子结点中包含全部关键字,以及指向这些关键字的指针
9759
44 5915 9772
1510 443721 5951 85 97917263
根
叶
4、哈希表
一种搜索结构
不经过任何比较，一次存取就能得到所查的记录：
每个记录和存储位置之间建立一个一一对应关系 f,对每个
关键码 K,f(K)就是 K的存储位置,称 f为哈希函数。
哈希函数的例
int HF(int key)//直接定址法 a,b是选定的常数
{ return a*key+b;}
1993 1994 1996 1999 2001
20011999199619941993
留余数法
int HF(int key)//模一个 素数 得到的余数
{ return key%11; }
23 35 18 48 107 9 43 60
4391810760483523
数字分析法
1939 1949 1969 1999 2001
以第三位定位
19991969194919392001
int HF(char *key)//首末字母法，首末字母之和模 101
{ int len=strlen(key),hashf=0;
if(len<=1)hashf=key[0];
else hashf=key[0]+key[len-1];
return hashf%101;
}
Beijing Shanghai Tianjin Chongqing
TianjinShanghaiChongQingBeijing
int HF(char *key)//全字母法，所有字母的和模 101
{ int hashf=0;
while(*key)hashf+=*key++;
return hashf%101;
}
int HF(int key)//平方取中法
{ key*=key; //key平方
key>>=11; //右移 11位，去掉末尾 11位
return key%1024;//去掉前面 11位
}
处理冲突的方法
冲突 collision,不同的关键码得到同一个地址
1.开放定址法 —— 线性探查法
23 35 48 17 60 29 38 40
291760483523 38 40
开放定址法
查找成功平均查找次数
(1+1+1+1+1+4+3)/8=12/8=3/2
4038291760483523
开放定址法的缺点
容易引起,二次聚集”
发生冲突的点引起再一次冲突的可能性增加
使冲突点聚集
可以用 再哈希法 改进
即定义一个哈希函数序列
发生冲突的关键码用下一个哈希函数确定位置
避免聚集
链地址法
19 14 23 01 68 20 27 55 11 10 79
∧
∧
∧
∧
∧
∧
∧0
1
2
3
4
5
6
7
8
9
10
11
12
01 14 27 ∧79
55 ∧68
19 ∧84
∧20
10 ∧23
∧11
第八章 查找
作业：
? 8.1 查找的基本概念
? 8.2 静态查找表
? 无序表查找
? 有序表查找
? 分块查找
??8.3 动态查找表
? B树
? B+树
? 8.4 哈希表
8.1 查找的基本概念
关键字,表示数据元素的数据项
查找,寻找关键字满足特定条件的数据元素的过
程
查找表,用于查找的数据结构，可能是线性结构
，也可能是非线性结构
静态查找,查找过程中，不会修改查找表的查找
操作
动态查找,查找的目的是为了修改查找表，通常
是查找成功则删除结点，查找失败则插入结
点
平均查找长度,查找过程中的平均比较次数，它
是比较查找算法优劣的依据
2、静态查找表
(1)无序表的查找
int sqsearch(SQLIST L,int aidkey)
{int j;
for(j=0;j<L.len;j++)
if(L.elem[j].key==aidkey) return j;
return -1;
}
(2)有序表的查找
I.线性查找算法,
int sqsearch(SQLIST L,int aidkey)
{int j;
for(j=0;j<L.len&&L.elem[j].key<=aidkey;j++)
if(L.elem[j].key==aidkey) return j;
return -1;
}
静态查找表基本上
不作插入和删除操
作,一般采用顺序
存储结构
2、静态查找表 (cont’d)
(2)有序表的查找
II.折半查找算法,
int binsearch(SQLIST L,int aidkey)
{ int low,high,mid;
low=0; high=L.len-1;
while(low<=high)
{ mid=(low+high)/2;
if(L.elem[mid]==aidkey) return mid;
else if(L.elem[mid]>aidkey) high=mid-1;
else low=mid+1;
}
return -1;
}
12 2
3 3 3 3
4 4 4
1+2*2+4*3+3*4=29
O(29/10)
1 2 3 4 5 6 7 8 9 10
2、静态查找表 (cont’d)
(2)有序表的查找
III.斐波那契查找,
根据斐波那契序列的特点对有序表分割
0.618法
斐波那契序列
1 2 3 5 8 13 21 34 55······f(n)······
f(n+2)=f(n)+f(n+1)
从 20个数的数表中查找一个纪录
先找比较第 13个，如果小，再比较第 8个,····
如果大 比较后几个数的第 5个 ······
每次都比较位于这个数列的黄金分割点 0.618处
比如 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
16
查找 15的位置
2、静态查找表 (cont’d)
(2)有序表的查找
IV.插值查找,
应用条件：查找表中关键字分布均匀
查找失败时，确定下一个比较对象的方法：
lo wlo wh ig hk e ylo we le mLk e yh ig he le mL k e ylo we le mLa id k e yi ????? )(*].[.].[,].[.
2、静态查找表 (cont’d)
(3)分块查找
将查找表分成若干块，块的大小可以不等，块内可
以是无序的，但块间是有序的。比如，前面块内的所有
关键字都比后面的小。
利用索引表记录每个块的起点和终点和块内的最大
关键字。查找时先在索引表中搜索确定，需要在哪个块
内查找，然后，在到查找表特定区间内去搜索。
36 54 43 28 49 25 58 74 63 65 76 94 101138146,..
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
54 94 154 ……..最大关键字
0 6 12 ……..块起始地址
3、动态查找表
(1)B树 (B-树 )
I,B树的定义,一棵 m叉 (或称 m阶 )B树，或者是空树，或者是满足下
面特性的 m叉排序树 (lchild<parent<rchild)：
①每个结点至多有 m棵子树，
②如根结点不是叶，至少有两棵子树，
③除根之外，所有非终端结点至少有 ┌m/2 ┐(m/2向上取整 )棵
子树,以后记为 [m/2]
④ 所有的非终端结点含有信息
最多 [m/2]-1个关键字
Ai是子树指针,Ki是关键字，结点内部关键字有序
⑤所有叶结点都在同一层次,叫做失败结点。
AVL树,B树和 B+树都是常用的动态查找
表
AnKn······K2A1K1A0n
3、动态查找表 (cont’d)
(1)B树 (B-树 )
II,B树的查找,
过程演示
·35·1
·18·1 ·78·43·2
·11·1 ·27·1 ·39·1 ·99·1·53·47·2
F F F F F F F F F F F
53
3、动态查找表 (cont’d)
(1)B树 (B-树 )
III,B树的插入,先查找插入的位置，必然在最低一层结点有序插入
！但结点的插入可能会导致结点被撑破，需要分两种情况处理：
(1)如果插入关键字后,叶子结点中的关键字数量 <=m-1，则插入操
作完毕。
(2)如果插入后，叶子结点中的关键字数量是 m，则需要将叶子结点
一分为 2，成为 2个叶子，中间的关键字携带着新叶子结点的指针上
升到双亲结点中。这就转化为在双亲结点中插入一个关键字的问题
了。
这个问题的处理仍需要按照 (1)(2)两种情况处理，一直到增加关键字
的结点未满或者新生成根结点为止。
·35·1
·18·1 ·78·43·2
·11·1 ·27·1 ·39·1 ·99·1·53·47·2
F F F F F F F F F F F
向一棵 3阶 B树增加一个关键字 60
插入底层
·35·1
·18·1 ·78·43·2
·39·1 ·99·1·60·53·47·3
F F F F F F F
增加一个关键字 60
将 53上移结点分裂
·35·1
·18·1 53 ·
·
78·43·3
·39·1 ·99·1·47·1
F F F F F F
增加一个关键字 60
·60·1
F F
再将 53上移结点分裂
·53·35·2
·18·1 1 · ·78·43·1
·39·1 ·99·1·47·1
F F F F F F
增加一个关键字 60
·60·1
F F
3、动态查找表 (cont’d)
(1)B树 (B-树 )
IV,B树的删除,先找到要删除的关键字，如果查找失败，删除操作
终止。如果查找成功，则区分两种情况处理：
(1)如果关键字位于非叶子结点中，则利用它的直接后继替代它，
然后删除它的直接后继。它的直接后继是它的右子树最左端的叶子
结点的最左边的关键字。问题就转化为第二种情况。
(2)如果关键字位于叶子结点中，删除操作仍需要分两种情况处理
,·53·35·2
·18·1 1 · ·78·43·1
·39·1 ·99·1·47·1
F F F F F F
·65·60·2
F F F
删除 5360
3、动态查找表 (cont’d)
① 删除后，结点关键字数量 >=[m/2]-1，删除完成。
②删除后，结点关键字数量 <[m/2]-1，
?若该结点的左右兄弟结点中有一个关键字数大于 [m/2]-1，则将
其兄弟结点中最小或最大的关键字上移至双亲结点中，而将双
亲结点中小于或大于且紧靠该上移关键字的关键字下移至被删
除关键字所在结点中。所谓的“借”个关键字，但借关键字同
时，也要借该关键字左边或右边的子树指针！
?若该结点的左右兄弟结点的关键字数都等于 [m/2]-1，则将其与
一个兄弟结点合并,双亲结点中，左右兄弟中间的关键字下移
到合并的结点中去。
? 重复上面 2步，直到不再发生合并为止。
·53·35·2
·18·1 1 · ·78·43·1
·39·1 ·99·1·47·1
F F F F F F
·65·60·2
F F F
删除 99
65
781
3、动态查找表 (cont’d)
① 删除后，结点关键字数量 >=[m/2]-1，删除完成。
②删除后，结点关键字数量 <[m/2]-1，
?若该结点的左右兄弟结点中有一个关键字数大于 [m/2]-1，则将
其兄弟结点中最小或最大的关键字上移至双亲结点中，而将双
亲结点中小于或大于且紧靠该上移关键字的关键字下移至被删
除关键字所在结点中。所谓的“借”个关键字，但借关键字同
时，也要借该关键字左边或右边的子树指针！
?若该结点的左右兄弟结点的关键字数都等于 [m/2]-1，则将其与
一个兄弟结点合并,双亲结点中，左右兄弟中间的关键字下移
到合并的结点中去。
? 重复上面 2步，直到不再发生合并为止。
·53·35·2
·18·1 1 · ·78·43·1
·39·1 ·99·1·47·1
F F F F F F
·65·60·2
F F F
删除 47
0
·39·2
F F
删除
43
1
· ·782
删除
53
3、动态查找表 (cont’d)
(2)B+树
? B-树的变形
? 根结点 (非叶时 )至少有两个结点
? 除根外，非叶结点至少有 [m/2]棵子树
? 最多有 m棵子树,非叶结点都是索引，含有子树中的最大或最少关
键字
? 含有 n个关键字的非叶结点有 n棵子树
? 所有的叶子结点都在同一个层次上，叶子结点中包含全部关键字,以及指向这些关键字的指针
9759
44 5915 9772
1510 443721 5951 85 97917263
根
叶
4、哈希表
一种搜索结构
不经过任何比较，一次存取就能得到所查的记录：
每个记录和存储位置之间建立一个一一对应关系 f,对每个
关键码 K,f(K)就是 K的存储位置,称 f为哈希函数。
哈希函数的例
int HF(int key)//直接定址法 a,b是选定的常数
{ return a*key+b;}
1993 1994 1996 1999 2001
20011999199619941993
留余数法
int HF(int key)//模一个 素数 得到的余数
{ return key%11; }
23 35 18 48 107 9 43 60
4391810760483523
数字分析法
1939 1949 1969 1999 2001
以第三位定位
19991969194919392001
int HF(char *key)//首末字母法，首末字母之和模 101
{ int len=strlen(key),hashf=0;
if(len<=1)hashf=key[0];
else hashf=key[0]+key[len-1];
return hashf%101;
}
Beijing Shanghai Tianjin Chongqing
TianjinShanghaiChongQingBeijing
int HF(char *key)//全字母法，所有字母的和模 101
{ int hashf=0;
while(*key)hashf+=*key++;
return hashf%101;
}
int HF(int key)//平方取中法
{ key*=key; //key平方
key>>=11; //右移 11位，去掉末尾 11位
return key%1024;//去掉前面 11位
}
处理冲突的方法
冲突 collision,不同的关键码得到同一个地址
1.开放定址法 —— 线性探查法
23 35 48 17 60 29 38 40
291760483523 38 40
开放定址法
查找成功平均查找次数
(1+1+1+1+1+4+3)/8=12/8=3/2
4038291760483523
开放定址法的缺点
容易引起,二次聚集”
发生冲突的点引起再一次冲突的可能性增加
使冲突点聚集
可以用 再哈希法 改进
即定义一个哈希函数序列
发生冲突的关键码用下一个哈希函数确定位置
避免聚集
链地址法
19 14 23 01 68 20 27 55 11 10 79
∧
∧
∧
∧
∧
∧
∧0
1
2
3
4
5
6
7
8
9
10
11
12
01 14 27 ∧79
55 ∧68
19 ∧84
∧20
10 ∧23
∧11
第八章 查找
作业：
