第 七 章 查 找
查找也叫检索,是一种在实际中大量应用的基本运算,
查找表是由同一类型的数据元素 (或记录 )构成的集合,
对查找表经常进行的操作有以下几种,
(1)查询某个“特定的”数据元素是否在查找表中 ;
(2)检索某个“特定的”数据元素的各种属性 ;
(3)在查找表中插如一个数据元素 ;
(4)从查找表中删去某个数据元素,
只对查找表进行 (1)﹑ (2)二种操作时,称查找表为静态查找
表, 若对查找表需同时进行上述四种操作时,称查找表为动态查
找表, 在上述四种操作中,(1)﹑ (2)二种是基本的操作,统称为查找
下面给出“特定的”这个词的含义,
关键字 (key),是数据元素 (或记录 )中某个数据项的值,用以
标识 (识别 )一个数据元素 (或记录 ).
主关键字 (primary key),能唯一地标识一个记录的
关键字,对不同的记录,其主关键词的值均不同,
次关键字 (secondary key),用以识别若干个记录的
关键字,
查找, 设查找表 F有 n个记录,
iK
为 记录
iR
的 关键字
现给定 关键字 K,将寻找相应的记录 R的过程称为查找,
以后为讨论问题方便起见,常用记录的关键字值 K表
示该记录,
7.1线性表的查找
7.1.1 顺序查找
顺序查找是最简单的一种查找方法,其查找过程为,
从表的一端开始,逐个进行记录的关键字值和给定关键字
值的比较,若找到一个记录的关键字值和给定关键字值相
等,则查找成功 ; 若整个表中记录均已比较,仍未有记录
的关键字值等于给定值,则查找失败,
由于顺序查找方法是顺序地逐个进行记录关键字的
比较,因此这种查找方法既适合于线性表的顺序存储,
也适合于线性表的链式存储, 且对于查找表中的记录是
否按关键字值有序也无关,
下面先给出对顺序存储的线性表进行顺序查找的 C函
数,
struct node
{ ink key; char ch; }
typedef struct node NODE;
void seqsrch(r,n,k)
NODE r[ ]; int n,k;
{ int i;
r[n+1].key=k; /* 标识边界,在此称为上监视哨,如 r[0].key=k,称为下监视哨,*/
/* 下面程序有些语句需作相应改动, */
i=1;
while(r[i].key!=k) i++;
if(i<=n) printf(“成功,%d%c”,r[i].key,r[i].ch);
else printf(“表中无此记录 \n”);
}
下面给出的 C函数其作用是对带头结点的单向循环链
表 中的记录进行顺序查找,
struct node
{ ink key; char ch; struct node *next }
typedef struct node NODE;
void seqsrch(h,k)
NODE *h; int k;
{ NODE *p;
p=h->next;
while(p!=h)
{ if(p->key==k)
{ printf(“成功,%d%c”,p ->key,p->ch); return; }
else p=p->next;
}
printf(“表中无此记录 \n”);
}
查找操作的性能分析
在此主要分析查找操作的时间复杂度, 查找算法中的
基本运算是,将记录的关键字和给定值进行比较”, 因
此
通常以,其关键字和给定值进行过比较的记录个数的平均
值” 作为量度查找算法的好坏依据,
定义, 为确定记录在查找表中的位置,需和给定值进
行比较的关键字个数的期望值称为查找算法在查找成功时
的平均查找长度,也即时间复杂度,
对含有 n个记录的查找表,查找成功时的平均查找长度
?
?
? n
i
iicpA C N
1
上式中,ip 为查找表中第 i个记录的概率,且有 1
1
??
?
n
i
ip
当查找表中任一个记录的概率相等即等概时,有
npi
1?
为找到表中其关键字与给定值相等的第 i个记录时,和 给
定值已进行过比较的关键字个数,
对于顺序查找算法,等概时查找成功的平均查找长度
ic
为,
2
1
2
)1(11
11
?????? ??
??
nnn
nincpACN
n
i
n
i
ii
则 顺序查找算法查找成功时的时间复杂度为 O(n).
在实际应用的大多数情况下,查找成功的可能性比不
成功的可能性大的多,特别是当 n很大时,查找不成功的概
率可忽略不计, 但当查找不成功的概率不能忽略时,查找
算法的平均查找长度应当是查找成功时的平均查找长度和
查找不成功时的平均查找长度之和,
对于顺序查找,不论给定关键字值为何值,查找不成功
时和给定值进 行比较的关键字个数均为 n+1,设 查找成功和
不成功的概率相等,即均为二分之一,对每个记录的查找
概率也相等,
则,此时顺序查找的 平均查找长度为,np
i 2/1?
4
)1(3
2
1
4
1
2
1
2
1
2
1
11
???????????? ??
??
nnnni
n
ncpACN n
i
n
i
ii
顺序查找的优点, 算法简单,适应面广,查找表中的记
录按关键字值的排列即可无序,也可有序,查找表的存储结
构即可为顺序,也可为链表,
顺序查找的缺点, 平均查找 长度较大,尤其当 n较大时
查找效率较低,
7.1.2 折半查找
折半查找也叫二分查找,其前提条件是, 查找表必须以
顺序表的结构存储,且查找表中的记录必须按关键字值有序
排列,
以后所举例子中假设查找表中的记录按关键字值递增有
序排列,
下面用具体的例子说明 折半查找的基本思想和手工操作
的过程,
例, 设在顺序存储的有序表中各记录的关键字为,
现要求查找关键字值为 21的记录,
查找过程如下, 设三个变量分别为
1 2 3 4 5 6 7 8 9 10 11
05 13 19 21 37 56 64 75 80 88 92
m idhiglow,,,它们的初值
? ? 62/)(,11,1 ????? h iglo wm idh iglo w,则它们的初始指向如
下左图,1 2 3 4 5 6 7 8 9 10 11
05 13 19 21 37 56 64 75 80 88 92
low higmid
第一次比较,
? ? 32/)(
5161
2156].6[].[
???
??????
????
h iglowm id
m idh ig
kk e yrk e ym idr?
low higmid 第二次比较, 2119].3[].[ ???? kk e yrk e ym idr?
? ? 42/)(,4131 ????????? h iglo wm idm idlo w
low
higmid 第三次比较, 2121].4[].[ ???? kk e yrk e ym idr?
所以查找成功,
若现需查找关键字值为 85的记录,则过程如下, 第一次比较,
1 2 3 4 5 6 7 8 9 10 11
05 13 19 21 37 56 64 75 80 88 92
low higmid
? ? 92/)(
7161
8556].6[].[
???
??????
????
h iglowm id
m idlow
kk e yrk e ym idr?
low higmid
第二次比较,
? ? ? ? 105.102/)(
10191
8580].9[].[
????
??????
????
hi glowm id
m idlow
kk e yrk e ym idr?
第三次比较,
low
higmid
91101
8588].10[].[
??????
????
m idh ig
kk e yrk e ym idr?
low
hig 109 ??? lowhi g?
查找不成功, 其它例子可见教材 P.173~P.174,算法的 C函数
可见教材 P.175
下面分析 折半查找的 平均查找 长度,
折半查找中查到每一个记录的比较次数可通过二叉
判定树来描述, 画二叉判定树的步骤为,
(1) 用当前查找区间的中间位置上的记录作为根,
(2) 左子表和右子表中的记录分别作为根的左子树和右
子树,
(3) 分别对左子表和右子表执行步骤 (1),
下面用前面举的例子介绍画二叉判定树的过程,
1 2 3 4 5 6 7 8 9 10 11
05 13 19 21 37 56 64 75 80 88 92
1low 1hig1mid
56
2low 2hig2mid
19
3low
3hig
3mid
05
以上画出了以关键字值为 56的记录为根的
二叉判定树的左子树, 按同样的步骤可
继续画出右子树,
1 2 3 4 5 6 7 8 9 10 11
05 13 19 21 37 56 64 75 80 88 92
1low 1hig1mid
2low 2mid 2hig
3low
3hig
3mid
56
19
05
444,,m idh iglo w
133low
3hig
3mid
21
444,,m idh iglo w
37
80
64
75
88
92
由画 二叉判定树的过程,可得其具有如下特点,
(1)二叉判定树本质上也是一棵二叉排序树,
(2)二叉判定树必须由一组有序的记录画出,
(3)当确定了 mid是下取整还是上取整后,二叉判定树的形态是
唯一的,
下面由已画出的二叉判定树分析折半查找的平均查找长
度,
1 2 3 4 5 6 7 8 9 10 11
05 13 19 21 37 56 64 75 80 88 92
56
19
05
13
21
37
80
64
75
88
92
由于此记录在初始区间的中
如查找关键字值为 56的记录
间位置上,是整棵 二叉判定树的根,处于
第一层,如查找成功,只需比较一次, 以
次类推,在第 k层上的结点需比较 k次,
因此,折半查找的过程恰好是走了一
条从树根到被查结点的路经,关键字
进行比较的次数即为被查结点在树中
层数,从而 折半查找 成功时 进行比较的次数最多不超过树的
深度,而具有 n个结点的 二叉判定树的 深度为 ? ? 1log 2 ?n
为方便起见,不妨设 二叉判定树的 结点总数为 12 ?? kn
则 判定树为 深度 )1(lo g
2 ?? nk 的满 二叉树,在等概条件下,
折半查找的平均查找长度为,
1)1(lo g1211 2
1
1
11
???????? ???
?
?
??
nnnjncncpAC N k
j
jn
i i
n
i ii
当 n很大时,
以上讨论的内容,是以递增有序的一组记录为例的,
如被查找的表是递减有序的,则折半查找也适用,只需
将某些方法作相应的改变即可,
7.1.2 分块查找
分块查找又称索引顺序查找,其查找的方法以 折半
查找和 顺序查找为基础,故其性能介于 折半查找和 顺序
查找之间, 其基本思想是, 将表分成若干块,每一块中
关键字不一定有序,但块之间是有序的,即指第二个块
中所有记录的关键字值均大于第一个块中最大的关键字
值 ; 此外,还需建立一个“索引表”,索引表按关键字
有
序,它存放的是各块中最大的关键字值及各块的起始位
置,显然,索引表是按关键字 递增 有 序的,
1)1(lo g 2 ??? nA C N,折半查找在查找不成功时
进行和关键字比较的次数最多也不超过 ? ? 1log
2 ?n
下面举例说明, 设有一查找表如下图所示,
分块查找过程分两步, 第一步在索引表确定待查记
录所在的块 ; 第二步在块内顺序查找,
若查找关键字值 k=20的记录,查找过程为,
第一步, 因 18<20<38,故应到第二块中查找,
第二步, 在第二块中顺序查找到第 7个单元中记录的关键
字值 k=20,查找成功,
若查找关键字值 k=89的记录,按上述步骤进行,显然
查找不成功,
18 06 10 11 21 31 20 38 19 60 71 75 88 73 79 90
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
第一块 第二块 第三块 第四块
关键字 18 38 71 90
地 址 1 5 10 12
由于分块查找实际上是两次查找过程,因此整个分
块查找的平均查找长度应是两次查找的平均查找长度 (块
内查找与索引查找 )之和,所以分块查找的平均查找长度
sb LLA C N ??
上式中,
bL
为查找索引表时的平均查找长度,
sL
为在块内
查找时的平均查找长度,
为进行分块查找,假设将长度为 n的表均匀地分成 b
块,每块中含有 s个记录,即有 b= n/ s,在等概情况下,
块内查找的概率为 1 / s,每块查找的概率为 1 / b,则
(1)若顺序查找所在的块,有,
1)(212 12 111
11
??????????? ??
??
ssnsbisjbLLAC N s
i
b
j
sb
可证明当 s取 n 时,1?? nA C N 取最小值,
(2)若用折半查找确定所在的块,有,
2)1(lo g 2
s
s
nAC N ???
7.3哈希表及其查找
7.3.1哈希法
哈希查找是一种新的查找方法,其基本思想是将记录
的关键字 K作为自变量,通过一个确定的函数关系 H,计
算出相应的函数值 H(K),通常把这个函数值解释为记录的
存储地址,即记录在存储空间中的存储地址, 查找时再根
据要查找的关键字 K,利用相同的函数 H计算出地址,直接到
该地址所在的单元中去读取要找的记录, 因此哈希法又称
为关键字 --地址转换法,
现举一个按上述思想建立一张表的简单的例子,
设建立一张全国各省 ﹑ 区和直辖市的各民族人口统计
表,如用一维数组 r存储这张表,显然表中各元素应为记录
类型,即一个地区为一条记录,
记录的各项数据为,
其中 r[i]是编号为 i的地区人口情况,编号 i便为记录的关键
字,由它唯一确定记录的存储位置 r[i].
上面这张表就叫哈希表,表中记录的关键字 K即地区
编号与存储位置的对应关系 H叫哈希函数或叫散列函数,
对于此例,H(K)= K,由此可得所为哈希函数是,
通过对关键字进行某种运算后,直接确定被查记录
在表中的地址,这种函数叫哈希函数或叫散列函数,其
地区编号 地区名 总人口 汉族 回族 …
一般形式为, )()(
ii aadrKH ?,式中 ia 为表中第 i个元素 (或
记录 ),
iK
为 ia 的关键字,)(
iaadr 为 ia 元素在表中的地址,
也叫哈希地址,)( iKH 叫哈希函数,也叫散列函数,
也可用地区名作为关键字来构造哈希函数, 假设地区
名采用汉语拼音,则不能简单以 H(K)= K做为哈希函数,
而是先将它们转换为数字,再作些简单的处理,
处理的方法有多种,比如取关键字中第一个字母在
字母表中的序号作为哈希函数,'',19)( SSH A N G H A IH ?在
字母表中的序号为 19,但用这一方法又产生新的问题,即
当地区名为山西时,其,19)( ?S H A N X IH 不同的 地区名得
到相同的 哈希地址,即 )()(,
jiji KHKHKK ??
,这种现象叫
做冲突, 具有相同 函数值的关键字对该哈希函数来说叫
同义词,
由上面例子可得如下一些基本结论,
(1)哈希函数是一个映像,把关键字集合中的元素映像到
地址集合中的元素,因此哈希函数的构造很灵活,只
要使任何关键字由此所得的哈希函数值都落在表长允
许范围内即可,
(2)运用哈希函数可根据关键字确定相应元素在表中的位
置,并将其存入表中, 在查找 (或称检索 )时,则以同样
的哈希函数求得被查元素在表中地址,从而查到所需元
素,若该地址的空间未被占用,则查找失败,
(3)发生冲突的现象一般来说是不可避免的,只是程度不
同,只能尽可能地少, 因此,在构造哈希表时,不仅
要构造一个“好”的哈希函数,而要设定一种处理冲
突
的方法,
7.3.2哈希 函数的构造方法
一个“好”的 哈希 函数,应对于关键字集合中的任
一
个关键字,经 哈希 函数映像到地址集合中任何一个地址
的概率是相等的,则称此类 哈希 函数为均匀的 哈希 函数,
也即使关键字经过 哈希 函数得到一个“随机的地址”,
以
便使一组关键字的 哈希 地址均匀分布整个地址区间中,
以减少冲突,
构造 哈希 函数的方法很多,在此只讨论一种方法,叫
除留余数法,
选择一个适当的正整数 P,用 P去除关键字,取其余数作
为哈希地址,即, H(K)=K % P,P<=m,m为存储容量
也即哈希表的表长,
7.3.3解决哈希法冲突 的基本方法
设 哈希表的地址集为 0~ m-1,即表长为 m,所谓冲突
是指由关键字得到的哈希地址为 j(0<=j<=m-1)的位置上
已存有记录,则处理冲突就是为该关键字的记录找到另
一个空的哈希地址, 在处理冲突的过程中可能得到一个
地址序列 ? ?? ?1,0,,,2,1 ??? mHkiH
ii ?
,即在处理
哈希地址的冲突时,若得到的另一个哈希地址
1H
,仍然
发生冲突,则求下一个地址
2H
,若
2H,仍冲突,再找
3H,依此类推,直到 kH 不发生冲突为止,则 kH 为记录
在表中的地址, 若到某一个
iH,哈希表已满,则表明产生
溢出,解决冲突 的方法有多种,在此只介绍两种,
一 ﹑ 开放地址法
开放地址法解决冲突的做法是, 当发生冲突时,使用
某种方法在哈希表中形成一个探测序列,沿着此序列逐个
单元进行查找,直到找到一个空的单元时将新记录放入,
因此在造表开始时先将表置空, 形成探测序列最简单的一
种叫线性探测再散列,
设表长为 m,哈希地址为 0~ m-1,关键字个数为 n,且
n <= m,线性探测再散列的基本思想是,将哈希表看成一
个环形表,若发生冲突的单元地址为 d,则依次探测 d+1,
d+2,…,m -1,0,1,…,d -1,直到找到一个空单元为止, 开放
地址公式为, )11(%)( ????? mimidH
i,式中 d =H(K)
i为增量序列,当 i依次取 1,2,…,m-1时,叫线性探测,
下面将举例说明,如何用除留余数法及线性探测再散列
来构造一个哈希表,
例, 有一组记录,其关键字值如下所示,
71 ~ RR
181230691423:
7654321
K
RRRRRRR
设哈希表长 m=7,记录类型的数组下标 0~6,哈希函数,
7%)( KKH ?,采用线性探测再散列解决冲突,哈
希表初始置空,造表过程如下,
0 1 2 3 4 5 6
27%23)23( ??H
1R
07%14)14(,??H
2R
27%9)9( ??H 37%37%)1(,1 ???? dH
3R
67%6)6( ??H
4R
27%30)30(,??H 37%37%)1(,1 ???? dH
47%47%)2(2 ???? dH
5R
57%12)12(,??H
6R
47%18)18(,?H
57%57%)1(1 ???? dH 67%67%)2(,1 ???? dH
07%77%)3(3 ???? dH 17%87%)4(,4 ???? dH
7R
二 ﹑ 链地址法
将哈希地址相同的记录链接到同一个单链表中的方
法叫链地址法,在此只介绍链地址法中的外链地址法,
外链地址法是把哈希表分成两个存储区,一个区叫
基本存储区,存放哈希地址不冲突的记录,另一个区叫
溢出区或叫附加区,存放哈希地址发生冲突的记录,
例, 有一组记录
71 ~ RR
,其关键字值如下所示,
181230691423:
7654321
K
RRRRRRR
设哈希表长 m=7,基本存储区的数组下标 0~6,哈希函数,
7%)( KKH ?,用外链地址法解决冲突,哈希表的基
本存储区初始置空,造表过程如下,
7.3.4哈希表的查找及其分析 (补充 )
哈希表的查找过程与建表过程相似,即根据给定的
关键字值 K,按建表时的哈希函数 H(K)计算哈希地址,若
表中该地址对应的单元未使用,则查找失败,否则将该地
址对应的单元的关键字值与 K比较,若相等则查找成功,
否则根据建表时解决冲突的方法寻找下一个地址,反复
数据 域 指针域
0
1
2
3
4
5
6
?
?
?
?
?
?
?
27%23)23( ??H
1R
07%14)14( ??H2R
27%9)9( ??H3
R ?
67%6)6( ??H4R
27%30)30( ??H
5R ?
57%12)12( ??H6R
47%18)18( ??H7R
进行,直到查找成功或失败为止,
下面举例说明查找过程和对具体的例子分析其平均
查找长度,
例, 已建的哈希表如下所示,
0 1 2 3 4 5 6
2314 9 630 1218
7%)( KKH ?,用线性
探测再散列解决冲突,计算其平均
查找长度,
解, 2)1132151(
7
1 ????????ACN
例, 已建的哈希表如下所示,7%)( KKH ?,用链地
址法中的外链地址法解决冲突,计算其平
均查找长度,
数据 域 指针域
0
1
2
3
4
5
6
?
?
?
?
?
?
?
23
14
9 ?
6
30 ?
12
18 解, 710)1113211(71 ????????ACN
由上面的例子可见,同一哈希函数,用不同的解决
冲突 方法构造的哈希表,其平均查找长度 不同,
对 哈希表的查找效率取决于三个因素,
(1)哈希函数,(2)处理冲突的 方法,(3)哈希表的装填因子,
哈希函数的好坏主要影响出现冲突的频繁程度,假
设哈希函数是均匀的,意即不同的哈希函数对同一组随
机的关键字,产生冲突的可能性相同,则可不考虑不同
的哈希函数对 平均查找长度的 影响,
一般情况下,处理冲突 方法 相同的 哈希表,其平均
查找长度依赖于哈希表的装填因子, 哈希表的装填因子
定义为 ?? 哈希表中的记录数 哈希表的长度,α 标志哈希表的装
满程度,α越小,发生 冲突的可能性 越小 ; 反之,表中已
填入的记录越多,在填记录时,发生 冲突的可能性 越大,
下面给出在等概情况下,采用不同的方法处理冲突
时得 到的平均查找长度,
平均查找长度
解决冲突方法
成功 不成功
线性探测法
外链地址法
2/))1/(11( ??? 2/))1/(11( 2???
2/1 ?? )exp( ?? ??
课外习题, 教材 P.194第 1题
补充习题, 将整数序列 13,15,22,8,34,19,21插到一个初始
为空的哈希表中,哈希函数为 H(K)=K % 7
(1)使用线性探测再散列解决冲突,并给出
平均查找长度,
(2)使用外链地址法解决冲突,并给出平均查
找长度,
查找也叫检索,是一种在实际中大量应用的基本运算,
查找表是由同一类型的数据元素 (或记录 )构成的集合,
对查找表经常进行的操作有以下几种,
(1)查询某个“特定的”数据元素是否在查找表中 ;
(2)检索某个“特定的”数据元素的各种属性 ;
(3)在查找表中插如一个数据元素 ;
(4)从查找表中删去某个数据元素,
只对查找表进行 (1)﹑ (2)二种操作时,称查找表为静态查找
表, 若对查找表需同时进行上述四种操作时,称查找表为动态查
找表, 在上述四种操作中,(1)﹑ (2)二种是基本的操作,统称为查找
下面给出“特定的”这个词的含义,
关键字 (key),是数据元素 (或记录 )中某个数据项的值,用以
标识 (识别 )一个数据元素 (或记录 ).
主关键字 (primary key),能唯一地标识一个记录的
关键字,对不同的记录,其主关键词的值均不同,
次关键字 (secondary key),用以识别若干个记录的
关键字,
查找, 设查找表 F有 n个记录,
iK
为 记录
iR
的 关键字
现给定 关键字 K,将寻找相应的记录 R的过程称为查找,
以后为讨论问题方便起见,常用记录的关键字值 K表
示该记录,
7.1线性表的查找
7.1.1 顺序查找
顺序查找是最简单的一种查找方法,其查找过程为,
从表的一端开始,逐个进行记录的关键字值和给定关键字
值的比较,若找到一个记录的关键字值和给定关键字值相
等,则查找成功 ; 若整个表中记录均已比较,仍未有记录
的关键字值等于给定值,则查找失败,
由于顺序查找方法是顺序地逐个进行记录关键字的
比较,因此这种查找方法既适合于线性表的顺序存储,
也适合于线性表的链式存储, 且对于查找表中的记录是
否按关键字值有序也无关,
下面先给出对顺序存储的线性表进行顺序查找的 C函
数,
struct node
{ ink key; char ch; }
typedef struct node NODE;
void seqsrch(r,n,k)
NODE r[ ]; int n,k;
{ int i;
r[n+1].key=k; /* 标识边界,在此称为上监视哨,如 r[0].key=k,称为下监视哨,*/
/* 下面程序有些语句需作相应改动, */
i=1;
while(r[i].key!=k) i++;
if(i<=n) printf(“成功,%d%c”,r[i].key,r[i].ch);
else printf(“表中无此记录 \n”);
}
下面给出的 C函数其作用是对带头结点的单向循环链
表 中的记录进行顺序查找,
struct node
{ ink key; char ch; struct node *next }
typedef struct node NODE;
void seqsrch(h,k)
NODE *h; int k;
{ NODE *p;
p=h->next;
while(p!=h)
{ if(p->key==k)
{ printf(“成功,%d%c”,p ->key,p->ch); return; }
else p=p->next;
}
printf(“表中无此记录 \n”);
}
查找操作的性能分析
在此主要分析查找操作的时间复杂度, 查找算法中的
基本运算是,将记录的关键字和给定值进行比较”, 因
此
通常以,其关键字和给定值进行过比较的记录个数的平均
值” 作为量度查找算法的好坏依据,
定义, 为确定记录在查找表中的位置,需和给定值进
行比较的关键字个数的期望值称为查找算法在查找成功时
的平均查找长度,也即时间复杂度,
对含有 n个记录的查找表,查找成功时的平均查找长度
?
?
? n
i
iicpA C N
1
上式中,ip 为查找表中第 i个记录的概率,且有 1
1
??
?
n
i
ip
当查找表中任一个记录的概率相等即等概时,有
npi
1?
为找到表中其关键字与给定值相等的第 i个记录时,和 给
定值已进行过比较的关键字个数,
对于顺序查找算法,等概时查找成功的平均查找长度
ic
为,
2
1
2
)1(11
11
?????? ??
??
nnn
nincpACN
n
i
n
i
ii
则 顺序查找算法查找成功时的时间复杂度为 O(n).
在实际应用的大多数情况下,查找成功的可能性比不
成功的可能性大的多,特别是当 n很大时,查找不成功的概
率可忽略不计, 但当查找不成功的概率不能忽略时,查找
算法的平均查找长度应当是查找成功时的平均查找长度和
查找不成功时的平均查找长度之和,
对于顺序查找,不论给定关键字值为何值,查找不成功
时和给定值进 行比较的关键字个数均为 n+1,设 查找成功和
不成功的概率相等,即均为二分之一,对每个记录的查找
概率也相等,
则,此时顺序查找的 平均查找长度为,np
i 2/1?
4
)1(3
2
1
4
1
2
1
2
1
2
1
11
???????????? ??
??
nnnni
n
ncpACN n
i
n
i
ii
顺序查找的优点, 算法简单,适应面广,查找表中的记
录按关键字值的排列即可无序,也可有序,查找表的存储结
构即可为顺序,也可为链表,
顺序查找的缺点, 平均查找 长度较大,尤其当 n较大时
查找效率较低,
7.1.2 折半查找
折半查找也叫二分查找,其前提条件是, 查找表必须以
顺序表的结构存储,且查找表中的记录必须按关键字值有序
排列,
以后所举例子中假设查找表中的记录按关键字值递增有
序排列,
下面用具体的例子说明 折半查找的基本思想和手工操作
的过程,
例, 设在顺序存储的有序表中各记录的关键字为,
现要求查找关键字值为 21的记录,
查找过程如下, 设三个变量分别为
1 2 3 4 5 6 7 8 9 10 11
05 13 19 21 37 56 64 75 80 88 92
m idhiglow,,,它们的初值
? ? 62/)(,11,1 ????? h iglo wm idh iglo w,则它们的初始指向如
下左图,1 2 3 4 5 6 7 8 9 10 11
05 13 19 21 37 56 64 75 80 88 92
low higmid
第一次比较,
? ? 32/)(
5161
2156].6[].[
???
??????
????
h iglowm id
m idh ig
kk e yrk e ym idr?
low higmid 第二次比较, 2119].3[].[ ???? kk e yrk e ym idr?
? ? 42/)(,4131 ????????? h iglo wm idm idlo w
low
higmid 第三次比较, 2121].4[].[ ???? kk e yrk e ym idr?
所以查找成功,
若现需查找关键字值为 85的记录,则过程如下, 第一次比较,
1 2 3 4 5 6 7 8 9 10 11
05 13 19 21 37 56 64 75 80 88 92
low higmid
? ? 92/)(
7161
8556].6[].[
???
??????
????
h iglowm id
m idlow
kk e yrk e ym idr?
low higmid
第二次比较,
? ? ? ? 105.102/)(
10191
8580].9[].[
????
??????
????
hi glowm id
m idlow
kk e yrk e ym idr?
第三次比较,
low
higmid
91101
8588].10[].[
??????
????
m idh ig
kk e yrk e ym idr?
low
hig 109 ??? lowhi g?
查找不成功, 其它例子可见教材 P.173~P.174,算法的 C函数
可见教材 P.175
下面分析 折半查找的 平均查找 长度,
折半查找中查到每一个记录的比较次数可通过二叉
判定树来描述, 画二叉判定树的步骤为,
(1) 用当前查找区间的中间位置上的记录作为根,
(2) 左子表和右子表中的记录分别作为根的左子树和右
子树,
(3) 分别对左子表和右子表执行步骤 (1),
下面用前面举的例子介绍画二叉判定树的过程,
1 2 3 4 5 6 7 8 9 10 11
05 13 19 21 37 56 64 75 80 88 92
1low 1hig1mid
56
2low 2hig2mid
19
3low
3hig
3mid
05
以上画出了以关键字值为 56的记录为根的
二叉判定树的左子树, 按同样的步骤可
继续画出右子树,
1 2 3 4 5 6 7 8 9 10 11
05 13 19 21 37 56 64 75 80 88 92
1low 1hig1mid
2low 2mid 2hig
3low
3hig
3mid
56
19
05
444,,m idh iglo w
133low
3hig
3mid
21
444,,m idh iglo w
37
80
64
75
88
92
由画 二叉判定树的过程,可得其具有如下特点,
(1)二叉判定树本质上也是一棵二叉排序树,
(2)二叉判定树必须由一组有序的记录画出,
(3)当确定了 mid是下取整还是上取整后,二叉判定树的形态是
唯一的,
下面由已画出的二叉判定树分析折半查找的平均查找长
度,
1 2 3 4 5 6 7 8 9 10 11
05 13 19 21 37 56 64 75 80 88 92
56
19
05
13
21
37
80
64
75
88
92
由于此记录在初始区间的中
如查找关键字值为 56的记录
间位置上,是整棵 二叉判定树的根,处于
第一层,如查找成功,只需比较一次, 以
次类推,在第 k层上的结点需比较 k次,
因此,折半查找的过程恰好是走了一
条从树根到被查结点的路经,关键字
进行比较的次数即为被查结点在树中
层数,从而 折半查找 成功时 进行比较的次数最多不超过树的
深度,而具有 n个结点的 二叉判定树的 深度为 ? ? 1log 2 ?n
为方便起见,不妨设 二叉判定树的 结点总数为 12 ?? kn
则 判定树为 深度 )1(lo g
2 ?? nk 的满 二叉树,在等概条件下,
折半查找的平均查找长度为,
1)1(lo g1211 2
1
1
11
???????? ???
?
?
??
nnnjncncpAC N k
j
jn
i i
n
i ii
当 n很大时,
以上讨论的内容,是以递增有序的一组记录为例的,
如被查找的表是递减有序的,则折半查找也适用,只需
将某些方法作相应的改变即可,
7.1.2 分块查找
分块查找又称索引顺序查找,其查找的方法以 折半
查找和 顺序查找为基础,故其性能介于 折半查找和 顺序
查找之间, 其基本思想是, 将表分成若干块,每一块中
关键字不一定有序,但块之间是有序的,即指第二个块
中所有记录的关键字值均大于第一个块中最大的关键字
值 ; 此外,还需建立一个“索引表”,索引表按关键字
有
序,它存放的是各块中最大的关键字值及各块的起始位
置,显然,索引表是按关键字 递增 有 序的,
1)1(lo g 2 ??? nA C N,折半查找在查找不成功时
进行和关键字比较的次数最多也不超过 ? ? 1log
2 ?n
下面举例说明, 设有一查找表如下图所示,
分块查找过程分两步, 第一步在索引表确定待查记
录所在的块 ; 第二步在块内顺序查找,
若查找关键字值 k=20的记录,查找过程为,
第一步, 因 18<20<38,故应到第二块中查找,
第二步, 在第二块中顺序查找到第 7个单元中记录的关键
字值 k=20,查找成功,
若查找关键字值 k=89的记录,按上述步骤进行,显然
查找不成功,
18 06 10 11 21 31 20 38 19 60 71 75 88 73 79 90
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
第一块 第二块 第三块 第四块
关键字 18 38 71 90
地 址 1 5 10 12
由于分块查找实际上是两次查找过程,因此整个分
块查找的平均查找长度应是两次查找的平均查找长度 (块
内查找与索引查找 )之和,所以分块查找的平均查找长度
sb LLA C N ??
上式中,
bL
为查找索引表时的平均查找长度,
sL
为在块内
查找时的平均查找长度,
为进行分块查找,假设将长度为 n的表均匀地分成 b
块,每块中含有 s个记录,即有 b= n/ s,在等概情况下,
块内查找的概率为 1 / s,每块查找的概率为 1 / b,则
(1)若顺序查找所在的块,有,
1)(212 12 111
11
??????????? ??
??
ssnsbisjbLLAC N s
i
b
j
sb
可证明当 s取 n 时,1?? nA C N 取最小值,
(2)若用折半查找确定所在的块,有,
2)1(lo g 2
s
s
nAC N ???
7.3哈希表及其查找
7.3.1哈希法
哈希查找是一种新的查找方法,其基本思想是将记录
的关键字 K作为自变量,通过一个确定的函数关系 H,计
算出相应的函数值 H(K),通常把这个函数值解释为记录的
存储地址,即记录在存储空间中的存储地址, 查找时再根
据要查找的关键字 K,利用相同的函数 H计算出地址,直接到
该地址所在的单元中去读取要找的记录, 因此哈希法又称
为关键字 --地址转换法,
现举一个按上述思想建立一张表的简单的例子,
设建立一张全国各省 ﹑ 区和直辖市的各民族人口统计
表,如用一维数组 r存储这张表,显然表中各元素应为记录
类型,即一个地区为一条记录,
记录的各项数据为,
其中 r[i]是编号为 i的地区人口情况,编号 i便为记录的关键
字,由它唯一确定记录的存储位置 r[i].
上面这张表就叫哈希表,表中记录的关键字 K即地区
编号与存储位置的对应关系 H叫哈希函数或叫散列函数,
对于此例,H(K)= K,由此可得所为哈希函数是,
通过对关键字进行某种运算后,直接确定被查记录
在表中的地址,这种函数叫哈希函数或叫散列函数,其
地区编号 地区名 总人口 汉族 回族 …
一般形式为, )()(
ii aadrKH ?,式中 ia 为表中第 i个元素 (或
记录 ),
iK
为 ia 的关键字,)(
iaadr 为 ia 元素在表中的地址,
也叫哈希地址,)( iKH 叫哈希函数,也叫散列函数,
也可用地区名作为关键字来构造哈希函数, 假设地区
名采用汉语拼音,则不能简单以 H(K)= K做为哈希函数,
而是先将它们转换为数字,再作些简单的处理,
处理的方法有多种,比如取关键字中第一个字母在
字母表中的序号作为哈希函数,'',19)( SSH A N G H A IH ?在
字母表中的序号为 19,但用这一方法又产生新的问题,即
当地区名为山西时,其,19)( ?S H A N X IH 不同的 地区名得
到相同的 哈希地址,即 )()(,
jiji KHKHKK ??
,这种现象叫
做冲突, 具有相同 函数值的关键字对该哈希函数来说叫
同义词,
由上面例子可得如下一些基本结论,
(1)哈希函数是一个映像,把关键字集合中的元素映像到
地址集合中的元素,因此哈希函数的构造很灵活,只
要使任何关键字由此所得的哈希函数值都落在表长允
许范围内即可,
(2)运用哈希函数可根据关键字确定相应元素在表中的位
置,并将其存入表中, 在查找 (或称检索 )时,则以同样
的哈希函数求得被查元素在表中地址,从而查到所需元
素,若该地址的空间未被占用,则查找失败,
(3)发生冲突的现象一般来说是不可避免的,只是程度不
同,只能尽可能地少, 因此,在构造哈希表时,不仅
要构造一个“好”的哈希函数,而要设定一种处理冲
突
的方法,
7.3.2哈希 函数的构造方法
一个“好”的 哈希 函数,应对于关键字集合中的任
一
个关键字,经 哈希 函数映像到地址集合中任何一个地址
的概率是相等的,则称此类 哈希 函数为均匀的 哈希 函数,
也即使关键字经过 哈希 函数得到一个“随机的地址”,
以
便使一组关键字的 哈希 地址均匀分布整个地址区间中,
以减少冲突,
构造 哈希 函数的方法很多,在此只讨论一种方法,叫
除留余数法,
选择一个适当的正整数 P,用 P去除关键字,取其余数作
为哈希地址,即, H(K)=K % P,P<=m,m为存储容量
也即哈希表的表长,
7.3.3解决哈希法冲突 的基本方法
设 哈希表的地址集为 0~ m-1,即表长为 m,所谓冲突
是指由关键字得到的哈希地址为 j(0<=j<=m-1)的位置上
已存有记录,则处理冲突就是为该关键字的记录找到另
一个空的哈希地址, 在处理冲突的过程中可能得到一个
地址序列 ? ?? ?1,0,,,2,1 ??? mHkiH
ii ?
,即在处理
哈希地址的冲突时,若得到的另一个哈希地址
1H
,仍然
发生冲突,则求下一个地址
2H
,若
2H,仍冲突,再找
3H,依此类推,直到 kH 不发生冲突为止,则 kH 为记录
在表中的地址, 若到某一个
iH,哈希表已满,则表明产生
溢出,解决冲突 的方法有多种,在此只介绍两种,
一 ﹑ 开放地址法
开放地址法解决冲突的做法是, 当发生冲突时,使用
某种方法在哈希表中形成一个探测序列,沿着此序列逐个
单元进行查找,直到找到一个空的单元时将新记录放入,
因此在造表开始时先将表置空, 形成探测序列最简单的一
种叫线性探测再散列,
设表长为 m,哈希地址为 0~ m-1,关键字个数为 n,且
n <= m,线性探测再散列的基本思想是,将哈希表看成一
个环形表,若发生冲突的单元地址为 d,则依次探测 d+1,
d+2,…,m -1,0,1,…,d -1,直到找到一个空单元为止, 开放
地址公式为, )11(%)( ????? mimidH
i,式中 d =H(K)
i为增量序列,当 i依次取 1,2,…,m-1时,叫线性探测,
下面将举例说明,如何用除留余数法及线性探测再散列
来构造一个哈希表,
例, 有一组记录,其关键字值如下所示,
71 ~ RR
181230691423:
7654321
K
RRRRRRR
设哈希表长 m=7,记录类型的数组下标 0~6,哈希函数,
7%)( KKH ?,采用线性探测再散列解决冲突,哈
希表初始置空,造表过程如下,
0 1 2 3 4 5 6
27%23)23( ??H
1R
07%14)14(,??H
2R
27%9)9( ??H 37%37%)1(,1 ???? dH
3R
67%6)6( ??H
4R
27%30)30(,??H 37%37%)1(,1 ???? dH
47%47%)2(2 ???? dH
5R
57%12)12(,??H
6R
47%18)18(,?H
57%57%)1(1 ???? dH 67%67%)2(,1 ???? dH
07%77%)3(3 ???? dH 17%87%)4(,4 ???? dH
7R
二 ﹑ 链地址法
将哈希地址相同的记录链接到同一个单链表中的方
法叫链地址法,在此只介绍链地址法中的外链地址法,
外链地址法是把哈希表分成两个存储区,一个区叫
基本存储区,存放哈希地址不冲突的记录,另一个区叫
溢出区或叫附加区,存放哈希地址发生冲突的记录,
例, 有一组记录
71 ~ RR
,其关键字值如下所示,
181230691423:
7654321
K
RRRRRRR
设哈希表长 m=7,基本存储区的数组下标 0~6,哈希函数,
7%)( KKH ?,用外链地址法解决冲突,哈希表的基
本存储区初始置空,造表过程如下,
7.3.4哈希表的查找及其分析 (补充 )
哈希表的查找过程与建表过程相似,即根据给定的
关键字值 K,按建表时的哈希函数 H(K)计算哈希地址,若
表中该地址对应的单元未使用,则查找失败,否则将该地
址对应的单元的关键字值与 K比较,若相等则查找成功,
否则根据建表时解决冲突的方法寻找下一个地址,反复
数据 域 指针域
0
1
2
3
4
5
6
?
?
?
?
?
?
?
27%23)23( ??H
1R
07%14)14( ??H2R
27%9)9( ??H3
R ?
67%6)6( ??H4R
27%30)30( ??H
5R ?
57%12)12( ??H6R
47%18)18( ??H7R
进行,直到查找成功或失败为止,
下面举例说明查找过程和对具体的例子分析其平均
查找长度,
例, 已建的哈希表如下所示,
0 1 2 3 4 5 6
2314 9 630 1218
7%)( KKH ?,用线性
探测再散列解决冲突,计算其平均
查找长度,
解, 2)1132151(
7
1 ????????ACN
例, 已建的哈希表如下所示,7%)( KKH ?,用链地
址法中的外链地址法解决冲突,计算其平
均查找长度,
数据 域 指针域
0
1
2
3
4
5
6
?
?
?
?
?
?
?
23
14
9 ?
6
30 ?
12
18 解, 710)1113211(71 ????????ACN
由上面的例子可见,同一哈希函数,用不同的解决
冲突 方法构造的哈希表,其平均查找长度 不同,
对 哈希表的查找效率取决于三个因素,
(1)哈希函数,(2)处理冲突的 方法,(3)哈希表的装填因子,
哈希函数的好坏主要影响出现冲突的频繁程度,假
设哈希函数是均匀的,意即不同的哈希函数对同一组随
机的关键字,产生冲突的可能性相同,则可不考虑不同
的哈希函数对 平均查找长度的 影响,
一般情况下,处理冲突 方法 相同的 哈希表,其平均
查找长度依赖于哈希表的装填因子, 哈希表的装填因子
定义为 ?? 哈希表中的记录数 哈希表的长度,α 标志哈希表的装
满程度,α越小,发生 冲突的可能性 越小 ; 反之,表中已
填入的记录越多,在填记录时,发生 冲突的可能性 越大,
下面给出在等概情况下,采用不同的方法处理冲突
时得 到的平均查找长度,
平均查找长度
解决冲突方法
成功 不成功
线性探测法
外链地址法
2/))1/(11( ??? 2/))1/(11( 2???
2/1 ?? )exp( ?? ??
课外习题, 教材 P.194第 1题
补充习题, 将整数序列 13,15,22,8,34,19,21插到一个初始
为空的哈希表中,哈希函数为 H(K)=K % 7
(1)使用线性探测再散列解决冲突,并给出
平均查找长度,
(2)使用外链地址法解决冲突,并给出平均查
找长度,
