第八章 查找一、静态查找表
基本概念
顺序查找
折半查找
所谓 查找,就是在数据集合中寻找满足某种条件的数据对象 。
查找的结果通常有两种可能：
查找成功,即找到满足条件的数据对象这时,作为结果,可报告该对象在结构中的位置,还可给出该对象中的具体信息。
查找不成功,或查找失败。作为结果,
应报告一些信息,如失败标志、位置等。
通常称用于查找的数据集合为 查找结构,
它是由 同一数据类型的对象 (或记录 )组成。
在每个对象中有若干属性，其中有一个属性，其值可唯一地标识这个对象。称为关键码。 使用基于关键码的查找，查找结果应是唯一的。 但在实际应用时，查找条件是多方面的，可以 使用基于属性的查找方法，但查找结果可能不唯一。
实施查找时有两种不同的环境。
静态环境,查找结构在插入和删除等操作的前后不发生改变。
静态查找表
动态环境,为保持较高的查找效率,查找结构在执行插入和删除等操作的前后将自动进行调整，结构可能发生变化。
动态查找表
#define MaxSize 100 //查找表最大尺寸
typedef int DataType; //查找数据的类型
typedef struct { //查找表结点定义
DataType key; //关键码域
other; //其他数据域
} ListNode;
typedef struct dataList { //查找表结点定义
ListNode data[MaxSize]; //数据存储数组
int n; //数组当前长度
}
静态查找表结构的定义
衡量一个查找算法的时间效率的标准是：
在查找过程中关键码的平均比较次数,也称 为 平 均 查 找 长 度 ASL(Average
Search Length),通常它是查找结构中对象总数 n的函数 。
在静态查找表中,利用数组元素的下标作为数据对象的存放地址 。 查找算法根据给定值 x,在数组中进行查找 。 直到找到
x在数组中的位置或可确定在数组中找不到 x为止 。
另外衡量一个查找算法还要考虑算法所需要的存储量和算法的复杂性等问题。
顺序查找 (Sequential Search)
所谓顺序查找,又称线性查找,主要用于在线性结构中进行查找 。
设若表中有 n 个对象,则顺序查找从表的先端 (或后端 ) 开始,顺序用各对象的关键码与 给定值 x 进行比较,直到找到与其值相等的对象,则查找成功 ; 给出该对象在表中的位置 。
若整个表都已检测完仍未找到关键码与 x
相等的对象,则查找失败 。 给出失败信息 。
int LinearSearch ( dataList A,DataType x ) {
//在数据表 A.data[1..n]中顺序查找关键码为 x
//的数据对象,A.data[0].key 作为控制查找自动
//结束的,监视哨,使用
A.data[0].key = x; int i = A.n;
//将 x送 0号位置设置监视哨
while ( A.data[i].key != x ) i-- ;
//从后向前顺序查找
return i;
}
设置“监视哨”的顺序查找算法顺序查找的平均查找长度
1
0
1
0
n
i
i
n
i
iis u c c pcpA S L ) 1 (,
)( 1
1
inpA SL
n
i
is u c c
设查找第 i 个元素的概率为 pi,查找到第 i 个元素所需比较次数为 ci,则查找成功的平均查找长度,
在顺序查找并设置“监视哨”情形：
ci = n- i +1,i = n,n-1,?,1，因此
.)()(?
n
i
s u c c
nnn
n
in
n
A S L
1 2
1
2
1111
在等概率情形,pi = 1/n,i = 1,2,?,n。
在查找不成功情形,ASLunsucc = n+1.
有序顺序表的顺序查找
( 10,20,
30,40,50,60 )
10
50
60
=
=
=
=
=
=
20
30
40
<
<
<
<
<
<
>
>
>
>
>
>
2
71
6
1 5
0
i
s u c c iA S L
7
27
61
7
1 5
0
i
u n s u c c
i
A S L
基于有序顺序表的折半查找
设 n个对象存放在一个按其关键码从小到大排好了序的有序顺序表中 。
折半查找时,先求位于查找区间正中的对象的下标 mid,用其关键码与 给定值 x比较,
A.data[mid].key == x,查找成功 ；
A.data[mid].key > x,把查找区间缩小到 表的 前半部分,继续折半查找 ；
A.data[mid].key < x,把查找区间缩小到表的 后半部分,继续折半查找 。
如果查找区间已缩小到一个对象,仍未找到想要查找的对象,则查找失败 。
查找成功的例子
-1 0 1 3 4 6 8 10 126
0 1 2 3 4 5 6 7 8
查找 low mid high6
6 8 10 12
5 6 7 8
low mid high
6 6
5
low mid high
6
查找失败的例子
-1 0 1 3 4 6 8 10 125
0 1 2 3 4 5 6 7 8
查找 low mid high5
6 8 10 12
5 6 7 8
low mid high
65
5
low mid high
5
int BinarySearch ( dataList A,DataType x,
int low,int high ) {
int mid = -1;
if ( low <= high ) {
mid = ( low + high ) / 2;
if ( A.data[mid].key < x )
mid = BinarySearch ( A,x,mid +1,high );
else if ( A.data[mid].key > x )
mid = BinarySearch ( A,x,low,mid -1 );
}
return mid;
}
基于有序顺序表的折半查找递归算法
int BinarySearch ( dataList A,DataType x ) {
int high = A.n-1,low = 0,mid;
while ( low <= high ) {
mid = ( low + high ) / 2;
if ( A.data[mid].key < x )
low = mid + 1; //右缩查找区间
else if ( A.data[mid].key > x )
high = mid - 1; //左缩查找区间
else return mid; //查找成功
}
return -1; //查找失败
}
基于有序顺序表的折半查找迭代算法
有序顺序表的折半查找的判定树
( 10,20,30,40,50,60 )
10 50
=
=
==
=
=
30
<
<
<
<
<
<
>
>
> >
> >
20 40 60
ASLunsucc = (2*1+3*6)/7
= 20/7
ASLsucc = (1+2*2+
3*3)/6 = 14/6
折半查找性能分析
若设 n = 2h-1，则描述折半查找的判定树是高度为 h-1 的满二叉树。
2h = n+1,h =
log2(n+1)。
第 0层结点有 1个,查找第 0层结点要比较 1
次 ; 第 1层结点有 2个,查找第 1层结点要比较 2次 ; …,第 i (0? i? h) 层结点有 2i 个,查找第 i 层结点要比较
i+1次,…。
假定每个结点的查找概率相等，即 pi =
1/n，则查找成功的平均查找长度为
121)(
221)( 232211 1221
h
hh
h
hh?
11)(l o g11)(l o g
1
)1)(1 ) l o g((
1
1)21)((
1
22
2
nn
n
n
nnn
n
h
n
A S L
h
s u c c
可以用归纳法证明这样三、散列表 (Hash表 )
基本思想
gas
summer
yock
blood
zoom
John
0
1
2
3
……
Hash表
summer
picture
plate
moment pleasure
beach
company
gas
zoom
blood
french John
newland yock
H(key)
集合三、散列表 (Hash表 )
散列函数
–散列函数的理想目标
设散列表 L[0…N-1]，则对散列函数 H(key)：
1,0≤H(key)≤N-1
2,k1≠k2 → H(k1)≠H(k2)
三、散列表 (Hash表 )
散列函数
– 散列函数的常用构造方法
选择法
叠加法
折叠法
模除法
数乘法
平方取中法
基数转换法
伪随机法身份证号,10210119750921011X
图书书号,ISBN 7-302-05932-2/TP·3530
书名,Thinking in C++
设备号,PV0103,LI0211,TI0004
记录 ID,1031,1231,232,772,12003,14223
zig
xerox
sachem
quad
pucker
mobile
kulla
hedge
cube
apace
设散列表的表长为 100，定义 H(key)为各字符 ASCII码之和模除 100。
30
66
25
27
50
32
37
9
15
6
三、散列表 (Hash表 )
冲突解决策略
–空状态和删除状态
–线性探测法
–二次散列法
–链表法设一组记录的关键字为：
PV1031,TI1104,PV0301,TI0103,PV0012,TI1205
存储表为 L[0..9]
定义 H(key)为 key的后四位之和模除 10。
探测序列为,+1,-1,+2,-2,+3,-3,...
H(PV1031)=5
H(TI1104)=6
H(PV0301)=4
H(TI0103)=4
H(PV0012)=3
H(TI1205)=8
0
1
2
3
4
5
6
7
8
9
PV1031
TI1104
PV0301
TI0103
PV0012
TI1205
设一组记录的关键字为：
PV1031,TI1104,PV0301,TI0103,PV0012,TI1205
存储表为 L[0..9]
定义 H1(key)为 key的后四位之和模除 10，
定义 H2(key)为 key的后四位的位或再模除 10。
H1(PV1031)=5
H1(TI1104)=6
H1(PV0301)=4
H2(TI0103)=3
H2(PV0012)=2
H1(TI1205)=8
0
1
2
3
4
5
6
7
8
9
PV1031
TI1104
PV0301
TI0103
PV0012
TI1205
设一组记录的关键字为：
PV1031,TI1104,PV0301,TI0103,PV0012,TI1205
存储表为 L[0..9]
定义 H(key)为 key的后四位之和模除 10。
探测序列为,+1,-1,+2,-2,+3,-3,...
H(PV1031)=5
H(TI1104)=6
H(PV0301)=4
H(TI0103)=4
H(PV0012)=3
H(TI1205)=8
0
1
2
3
4
5
6
7
8
9
PV0012
PV0301
PV1031
TI1104
TI1205
TI0103 PV0301
三、散列表 (Hash表 )
散列表上的查找
– E1：计算 H(key)，获得存储地址；
– E2：循环直到元素为空或等于 key
E21：按照冲突解决策略，计算下一个地址；
– E3：若元素为空，则查找失败，否则查找成功。
散列表上的插入
– E1：计算 H(key)，获得存储地址；
– E2：循环直到元素为空
E21：按照冲突解决策略，计算下一个地址；
– E3：写入新元素二、树表查找
二叉排序树
–基本概念
87
45
27
3921
4225
9066
11
二叉排序树
–在二叉排序树上查找
87
45
27
3921
4225
9066
11
二叉排序树
–在二叉排序树上插入新记录
87
45
27
3921
4225
9066
11
设输入序列为,43,25,29,67,17,88,54,47,35,62
43
43
25
43
25
29
43
25
29
67
43
25
29
67
17
43
25
29
67
17 8854
43
25
29
67
17 8854
4735 62
BiNode *T;
BiNode **pRoot = &T->lchild;;
BiNode *p = T->lchild;
pRoot
p
T
p->data,(*pRoot)->data
p->lchild,(*pRoot)->lchild
p->rchild,(*pRoot)->rchild
*pRoot = XXX; 是 p做不到的事情 ! CODING
二叉排序树
–从二叉排序树上删除一条记录
87
45
27
3921
4225
9066
11
x
y
y
若被删除结点没有右子（或左子）。
若被删除结点既有左子又有右子：
x
y z
..
a
ar
……
y z
..
a
ar
……
87
45
27
3921
4225
9066
11 71
87
66
27
3921
4225
9071
11
平衡二叉树
–基本概念
平衡因子
平衡二叉树
43
25
29
67
17 8854
4735 62
平衡二叉树
–插入结点的调整策略
LL型,R旋
RR型,L旋
LR型,L旋 R旋
RL型,R旋 L旋
LL型：在结点的左子的左子树上插入新结点导致失衡。
a
b
B
C
A h
a
b
B C
A
h
RR型：在结点的右子的右子树中插入新结点导致失衡。
a
b
B
C
Ah
a
b
BC
A
h
LR型：在结点的左子的右子树上插入新结点导致失衡。
a
b
C
D
A
B h
c
ab
C
DA
B h
c
RL型：在结点的右子的左子树上插入新结点导致失衡。
a
b
C
D
A
Bh
c
a b
C
D A
Bh
c
设输入序列：
45,32,16,77,94,38,44,21,39,68,33,87
45
32
16
45
32
16 45
32
16
77
94
45
77
94
38
38
4421
39
38 4421
39
32
16 94
4421
39 68
33
45
7738 44
39
6833
87
45
77
94
68 87
基本概念
顺序查找
折半查找
所谓 查找,就是在数据集合中寻找满足某种条件的数据对象 。
查找的结果通常有两种可能：
查找成功,即找到满足条件的数据对象这时,作为结果,可报告该对象在结构中的位置,还可给出该对象中的具体信息。
查找不成功,或查找失败。作为结果,
应报告一些信息,如失败标志、位置等。
通常称用于查找的数据集合为 查找结构,
它是由 同一数据类型的对象 (或记录 )组成。
在每个对象中有若干属性，其中有一个属性，其值可唯一地标识这个对象。称为关键码。 使用基于关键码的查找，查找结果应是唯一的。 但在实际应用时，查找条件是多方面的，可以 使用基于属性的查找方法，但查找结果可能不唯一。
实施查找时有两种不同的环境。
静态环境,查找结构在插入和删除等操作的前后不发生改变。
静态查找表
动态环境,为保持较高的查找效率,查找结构在执行插入和删除等操作的前后将自动进行调整，结构可能发生变化。
动态查找表
#define MaxSize 100 //查找表最大尺寸
typedef int DataType; //查找数据的类型
typedef struct { //查找表结点定义
DataType key; //关键码域
other; //其他数据域
} ListNode;
typedef struct dataList { //查找表结点定义
ListNode data[MaxSize]; //数据存储数组
int n; //数组当前长度
}
静态查找表结构的定义
衡量一个查找算法的时间效率的标准是：
在查找过程中关键码的平均比较次数,也称 为 平 均 查 找 长 度 ASL(Average
Search Length),通常它是查找结构中对象总数 n的函数 。
在静态查找表中,利用数组元素的下标作为数据对象的存放地址 。 查找算法根据给定值 x,在数组中进行查找 。 直到找到
x在数组中的位置或可确定在数组中找不到 x为止 。
另外衡量一个查找算法还要考虑算法所需要的存储量和算法的复杂性等问题。
顺序查找 (Sequential Search)
所谓顺序查找,又称线性查找,主要用于在线性结构中进行查找 。
设若表中有 n 个对象,则顺序查找从表的先端 (或后端 ) 开始,顺序用各对象的关键码与 给定值 x 进行比较,直到找到与其值相等的对象,则查找成功 ; 给出该对象在表中的位置 。
若整个表都已检测完仍未找到关键码与 x
相等的对象,则查找失败 。 给出失败信息 。
int LinearSearch ( dataList A,DataType x ) {
//在数据表 A.data[1..n]中顺序查找关键码为 x
//的数据对象,A.data[0].key 作为控制查找自动
//结束的,监视哨,使用
A.data[0].key = x; int i = A.n;
//将 x送 0号位置设置监视哨
while ( A.data[i].key != x ) i-- ;
//从后向前顺序查找
return i;
}
设置“监视哨”的顺序查找算法顺序查找的平均查找长度
1
0
1
0
n
i
i
n
i
iis u c c pcpA S L ) 1 (,
)( 1
1
inpA SL
n
i
is u c c
设查找第 i 个元素的概率为 pi,查找到第 i 个元素所需比较次数为 ci,则查找成功的平均查找长度,
在顺序查找并设置“监视哨”情形：
ci = n- i +1,i = n,n-1,?,1，因此
.)()(?
n
i
s u c c
nnn
n
in
n
A S L
1 2
1
2
1111
在等概率情形,pi = 1/n,i = 1,2,?,n。
在查找不成功情形,ASLunsucc = n+1.
有序顺序表的顺序查找
( 10,20,
30,40,50,60 )
10
50
60
=
=
=
=
=
=
20
30
40
<
<
<
<
<
<
>
>
>
>
>
>
2
71
6
1 5
0
i
s u c c iA S L
7
27
61
7
1 5
0
i
u n s u c c
i
A S L
基于有序顺序表的折半查找
设 n个对象存放在一个按其关键码从小到大排好了序的有序顺序表中 。
折半查找时,先求位于查找区间正中的对象的下标 mid,用其关键码与 给定值 x比较,
A.data[mid].key == x,查找成功 ；
A.data[mid].key > x,把查找区间缩小到 表的 前半部分,继续折半查找 ；
A.data[mid].key < x,把查找区间缩小到表的 后半部分,继续折半查找 。
如果查找区间已缩小到一个对象,仍未找到想要查找的对象,则查找失败 。
查找成功的例子
-1 0 1 3 4 6 8 10 126
0 1 2 3 4 5 6 7 8
查找 low mid high6
6 8 10 12
5 6 7 8
low mid high
6 6
5
low mid high
6
查找失败的例子
-1 0 1 3 4 6 8 10 125
0 1 2 3 4 5 6 7 8
查找 low mid high5
6 8 10 12
5 6 7 8
low mid high
65
5
low mid high
5
int BinarySearch ( dataList A,DataType x,
int low,int high ) {
int mid = -1;
if ( low <= high ) {
mid = ( low + high ) / 2;
if ( A.data[mid].key < x )
mid = BinarySearch ( A,x,mid +1,high );
else if ( A.data[mid].key > x )
mid = BinarySearch ( A,x,low,mid -1 );
}
return mid;
}
基于有序顺序表的折半查找递归算法
int BinarySearch ( dataList A,DataType x ) {
int high = A.n-1,low = 0,mid;
while ( low <= high ) {
mid = ( low + high ) / 2;
if ( A.data[mid].key < x )
low = mid + 1; //右缩查找区间
else if ( A.data[mid].key > x )
high = mid - 1; //左缩查找区间
else return mid; //查找成功
}
return -1; //查找失败
}
基于有序顺序表的折半查找迭代算法
有序顺序表的折半查找的判定树
( 10,20,30,40,50,60 )
10 50
=
=
==
=
=
30
<
<
<
<
<
<
>
>
> >
> >
20 40 60
ASLunsucc = (2*1+3*6)/7
= 20/7
ASLsucc = (1+2*2+
3*3)/6 = 14/6
折半查找性能分析
若设 n = 2h-1，则描述折半查找的判定树是高度为 h-1 的满二叉树。
2h = n+1,h =
log2(n+1)。
第 0层结点有 1个,查找第 0层结点要比较 1
次 ; 第 1层结点有 2个,查找第 1层结点要比较 2次 ; …,第 i (0? i? h) 层结点有 2i 个,查找第 i 层结点要比较
i+1次,…。
假定每个结点的查找概率相等，即 pi =
1/n，则查找成功的平均查找长度为
121)(
221)( 232211 1221
h
hh
h
hh?
11)(l o g11)(l o g
1
)1)(1 ) l o g((
1
1)21)((
1
22
2
nn
n
n
nnn
n
h
n
A S L
h
s u c c
可以用归纳法证明这样三、散列表 (Hash表 )
基本思想
gas
summer
yock
blood
zoom
John
0
1
2
3
……
Hash表
summer
picture
plate
moment pleasure
beach
company
gas
zoom
blood
french John
newland yock
H(key)
集合三、散列表 (Hash表 )
散列函数
–散列函数的理想目标
设散列表 L[0…N-1]，则对散列函数 H(key)：
1,0≤H(key)≤N-1
2,k1≠k2 → H(k1)≠H(k2)
三、散列表 (Hash表 )
散列函数
– 散列函数的常用构造方法
选择法
叠加法
折叠法
模除法
数乘法
平方取中法
基数转换法
伪随机法身份证号,10210119750921011X
图书书号,ISBN 7-302-05932-2/TP·3530
书名,Thinking in C++
设备号,PV0103,LI0211,TI0004
记录 ID,1031,1231,232,772,12003,14223
zig
xerox
sachem
quad
pucker
mobile
kulla
hedge
cube
apace
设散列表的表长为 100，定义 H(key)为各字符 ASCII码之和模除 100。
30
66
25
27
50
32
37
9
15
6
三、散列表 (Hash表 )
冲突解决策略
–空状态和删除状态
–线性探测法
–二次散列法
–链表法设一组记录的关键字为：
PV1031,TI1104,PV0301,TI0103,PV0012,TI1205
存储表为 L[0..9]
定义 H(key)为 key的后四位之和模除 10。
探测序列为,+1,-1,+2,-2,+3,-3,...
H(PV1031)=5
H(TI1104)=6
H(PV0301)=4
H(TI0103)=4
H(PV0012)=3
H(TI1205)=8
0
1
2
3
4
5
6
7
8
9
PV1031
TI1104
PV0301
TI0103
PV0012
TI1205
设一组记录的关键字为：
PV1031,TI1104,PV0301,TI0103,PV0012,TI1205
存储表为 L[0..9]
定义 H1(key)为 key的后四位之和模除 10，
定义 H2(key)为 key的后四位的位或再模除 10。
H1(PV1031)=5
H1(TI1104)=6
H1(PV0301)=4
H2(TI0103)=3
H2(PV0012)=2
H1(TI1205)=8
0
1
2
3
4
5
6
7
8
9
PV1031
TI1104
PV0301
TI0103
PV0012
TI1205
设一组记录的关键字为：
PV1031,TI1104,PV0301,TI0103,PV0012,TI1205
存储表为 L[0..9]
定义 H(key)为 key的后四位之和模除 10。
探测序列为,+1,-1,+2,-2,+3,-3,...
H(PV1031)=5
H(TI1104)=6
H(PV0301)=4
H(TI0103)=4
H(PV0012)=3
H(TI1205)=8
0
1
2
3
4
5
6
7
8
9
PV0012
PV0301
PV1031
TI1104
TI1205
TI0103 PV0301
三、散列表 (Hash表 )
散列表上的查找
– E1：计算 H(key)，获得存储地址；
– E2：循环直到元素为空或等于 key
E21：按照冲突解决策略，计算下一个地址；
– E3：若元素为空，则查找失败，否则查找成功。
散列表上的插入
– E1：计算 H(key)，获得存储地址；
– E2：循环直到元素为空
E21：按照冲突解决策略，计算下一个地址；
– E3：写入新元素二、树表查找
二叉排序树
–基本概念
87
45
27
3921
4225
9066
11
二叉排序树
–在二叉排序树上查找
87
45
27
3921
4225
9066
11
二叉排序树
–在二叉排序树上插入新记录
87
45
27
3921
4225
9066
11
设输入序列为,43,25,29,67,17,88,54,47,35,62
43
43
25
43
25
29
43
25
29
67
43
25
29
67
17
43
25
29
67
17 8854
43
25
29
67
17 8854
4735 62
BiNode *T;
BiNode **pRoot = &T->lchild;;
BiNode *p = T->lchild;
pRoot
p
T
p->data,(*pRoot)->data
p->lchild,(*pRoot)->lchild
p->rchild,(*pRoot)->rchild
*pRoot = XXX; 是 p做不到的事情 ! CODING
二叉排序树
–从二叉排序树上删除一条记录
87
45
27
3921
4225
9066
11
x
y
y
若被删除结点没有右子（或左子）。
若被删除结点既有左子又有右子：
x
y z
..
a
ar
……
y z
..
a
ar
……
87
45
27
3921
4225
9066
11 71
87
66
27
3921
4225
9071
11
平衡二叉树
–基本概念
平衡因子
平衡二叉树
43
25
29
67
17 8854
4735 62
平衡二叉树
–插入结点的调整策略
LL型,R旋
RR型,L旋
LR型,L旋 R旋
RL型,R旋 L旋
LL型：在结点的左子的左子树上插入新结点导致失衡。
a
b
B
C
A h
a
b
B C
A
h
RR型：在结点的右子的右子树中插入新结点导致失衡。
a
b
B
C
Ah
a
b
BC
A
h
LR型：在结点的左子的右子树上插入新结点导致失衡。
a
b
C
D
A
B h
c
ab
C
DA
B h
c
RL型：在结点的右子的左子树上插入新结点导致失衡。
a
b
C
D
A
Bh
c
a b
C
D A
Bh
c
设输入序列：
45,32,16,77,94,38,44,21,39,68,33,87
45
32
16
45
32
16 45
32
16
77
94
45
77
94
38
38
4421
39
38 4421
39
32
16 94
4421
39 68
33
45
7738 44
39
6833
87
45
77
94
68 87
