1
10.1 查找的基本概念
10.2 线性表的查找
10.3 树表的查找
10.4 哈希表查找第十章 查找
2
查找,也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素的过程。
查找结果,
查找成功 (table中存在给定值的记录，返回该记录的信息或该记录在表中的位臵）
查找不成功 (table中不存在给定值的记录，
返回相关的指示信息 。
10.1 查找的基本概念
3
查找表 (search table):是由同一类型的数据元素
（或记录）构成的集合，集合中的数据元素之间的关系是完全松散的。
查找表的主要操作：
查询某个“特定的”数据元素是否在表中；
检索某个“特定的”数据元素的各种属性；
在查找表中插入一个数据元素；
从查找表中删去某个数据元素。
查找表分为：
静态查找表 (对表中的 DE不 进行插入和删除 )；
动态查找表 (对表中的 DE可 进行插入和删除 )；
10.1 查找的基本概念
4
平均查找长度 (average search length):查找过程中,
对关键字进行比较的平均次数即比较次数的期望值。
n
i
ii cpA S L
1
其中,n是结点个数,pi是查找第 i个结点的概率
Ci是查找第 i个结点所需的比较次数
10.1 查找的基本概念
5
10.2 线性表的查找线性表是表的组织方式中最简单的一种，在其上我们主要介绍 顺序查找、二分查找和分块查找 。
一、顺序查找（ Sequential Search),从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值进行比较，若当前扫描到的结点值与给定值相等，则查找成功；反之，若扫描到最后，仍未找到关键字等于 k的结点，则查找失败。适用于顺序存储结构和链表存储结构。
顺序查找算法：
int SeqSearch(SeqList R,int n,KeyType k)
{ int i=0;
while (i<n && R[i].key!=k) i++; /*从表头往后找 */
if (i>=n)
return -1;
else
return i;
}
i
例 0 1 2 3 4 5 6 7 8 9 10 11
找 64
iiii
比较次数 =7*2
返回结果,i=6
5 13 19 21 37 56 64 75 80 88 92
i i
改进的顺序查找算法：
int SeqSearch(SeqList R,int n,KeyType k)
{ int i=0;
R[n].key=k; //哨兵,免去监测查找完毕的操作
while( R[i].key!=k) i++; //从前往后找
if(i= =n) return -1;
else return i;
}
i
例 0 1 2 3 4 5 6 7 8 9 10 11
找 64
64
监视哨
iiii
比较次数 =7
返回结果,i=6
5 13 19 21 37 56 64 75 80 88 92
i i
i+1
对于含有 n个纪录的表,查找成功 时的平均查找长度为：
1
0
n
i
ii CPA S L
其中,为查找表中第 i个纪录的概率,等概率时iP np i /1?
iC 为找到第 i个记录时，已比较的次数。
keyi
2/)1()1(1 1
0
ninA S L n
i
平均查找长度 (ASL)
9
顺序查找的优缺点：
优点,算法简单且适应面广，对表的结构无任何要求，对线性链表同样适用。
缺点,平均查找长度较大，特别是当 n很大时，
查找效率较低。
10.2 线性表的查找
10
10.2 线性表的查找二、二分查找（ Binary Search)：
有序表,查找表中记录按关键字有序排列的表。
即,r[i].key<=r[i+1].key i=1,2,…,n -1
二分查找：
要求：查找表为有序表
查找过程：先确定待查找记录范围；
然后逐步缩小范围；
直到：查找成功或不成功。
二分查找（ Binary Search):将待查的 k值和有序表的中间位臵 mid=n/2上的结点的关键字进行比较，若相等则查找成功；若 k<R[mid].key,则以同样的方法在区间 [0,mid-1]内进行查找 ;若 k>R[mid].key,则按同样的方法在区间 [mid+1,n-1]内进行查找。又称为折半 查找。
low highmid
05 13 19 21 37 (21)
21 37 (21)
0 1 2 3 4 5 6 7 8 9 10
05 13 19 21 37 56 64 75 80 88 92 （ 21）
05 13 19 21 37 56 64 75 80 88 92 （ 90）
mid
0 1 2 3 4 5 6 7 8 9 10
int BinSearch(SeqList R,int n,KeyType k)
{int low=0,high=n-1,mid;
while (low<=high)
{ mid=(low+high)/2;
if (R[mid].key==k)
return mid;
if (R[mid].key>k)
high=mid-1;
else
low=mid+1;
}
return -1;
}
highlow low mid lowmid lowmidhigh
R 11 90
13
二分查找的判定树或比较树,二分查找过程可用二叉树来描述,我们把当前查找区间的中间位臵上的记录作为根,左子表和右子表中的记录分别作为根的左子树和右子树 。
0 1 2 3 4 5 6 7 8 9 10
05 13 19 21 37 56 64 75 80 88 92 （ 90）
5
2 8
0 3 6 9
1 4 7 102-3-1 5-6 8-9
0-1 1-2 3-4 4-5 6-7 7-8 9-10 10-外部结点
R[0..10]的二分查线的判定树 (n=11)
14
假设有序表的长度 n=2h-1，则描述折半查找的判定树是深度为 h的满二叉树，在等概率情况下查找成功时的平均查找长度为,
1)1(l o g)1(21 2
1
1
1
n
n
nj
n
CPAS L
h
j
j
n
i
iibs
当 n很大时,ASLbs≈log2(n+1)-1
层次,1 结点数,1
2 2
3 4
4 8
15
例 10.1 对 于 给 定 11 个 数 据 元 素 的 有 序 表
{2,3,10,15,20,25,28,29,30,35,40},采用二分查找,试问：
(1)若查找给定值为 20的元素,将依次与表中哪些元素比较？
(2)若查找给定值为 26的元素,将依次与哪些元素比较？
(3)假设查找表中每个元素的概率相同,求查找成功时的平均查找长度和查找不成功时的平均查找长度。
16
25
10 30
2 15 28 35
3 20 29 40
二分查找判定树
(2)若查找给定值为 26的元素,依次与 25,30,28元素比较,共比较 3次 。
(3)在查找成功时,会找到图中某个 圆形 结点,则成功时的平均查找长度：
311 44342211A S L s u c c ＝＝
(1)若查找给定值为 20的元素,依次与表中 25,10,15,20元素比较,共比较 4次 。
在查找不成功时,会找到图中某个 方形 结点,
则不成功时的平均查找长度：
67.312 4834A S L u n s u c c ＝＝
17
对比顺序查找和二分查找的性能之差别：
顺序查找 二分查找表的特性存储结构插删操作
ASL值无序表 有序表顺序或链式结构 顺序结构易于进行 需移动元素大 小
18
10.2 线性表的查找三、分块查找（索引顺序查找 )：
索引表：
按表中的记录关键字分块,R1,R2,…R L.
要求：第 Rk块中的所有关键字小于 Rk+1块中的所有关键字,k=1,2,…L -1,称为“分块有序”
对每块建立一个索引项,包含以下两项内容：
关键字项,为该块中最大关键字值；
指针项,为该块第一个记录在表中的位臵。
所有索引项组成索引表
索引查找过程序分两步进行：
1）确定待查纪录所在的块 (子表 );(有序表的查找方法 )
2）然后在块内查找。 (块内有序或无序，用顺序查找）
如查找 key=74和 key=2
14 34 66
0 5 10
索引表 IDX
8 14 6 9 10 22 34 18 19 31 40 38 54 66
0 1 2 3 4 5 6 7 8 9 10 11 12 13
46
14
第 1块 第 2块 第 3块
key
link
索引表的结点类型：
#define MAXI <索引表的最大长度 >
typedef struct
{ keytype key;
int link;
}Idxtype;
typedef Idxtype IDX[MAXI];
分块查找的平均查找长度：
其中,ASLbn为查找索引表的平均查找长度；
ASLsq为在块中查找元素的平均查找长度。
用二分查找确定块时：
用顺序查找确定块时：
ASL何时最小？
分块查找的优点：查找速度快缺点：需辅助空间及建表较费时
2)1/(l o g2
11)1(l o g
22
ssnsbA S LA S LA S L
sqbnb l k
s2
ns2s
2
1s
2
1bA S LA S LLAS 2
sqbnb l k
sqbnb l k A S LA S LA S L
22
动态查找表的的特点是,表结构本身是在查找过程中动态生成的。即查找不成功时，将该记录插入在动态 查找表中。
10.3 树表的查找一、二叉排序树 (Binary Sort Tree)(又称为二叉查找树）
1,BST定义：
BST或者是一棵空树 ;或者是具有如下性质的 BT:
若左子树非空，则左子树上所有结点的值均小于根结点的值；
若右子树非空，则右子树上所有结点的值均大于根结点的值；
左、右子树也为 BST
45
12 53
3 37
24
100
61
90
78
45
12 53
3 50 49 100
61
90
40
2,查找过程为：
(1)当前 BST非空时,将给定值 k与当前根结点的关键字比较
(2)若相等，查找成功，结束；
若 k小于当前根结点关键字,则将左子树作为当前 BST;
若 k大于当前根结点关键字,则将右子树作为当前 BST；
(3),重复 (1)(2)。
24
5
4 8
972
3
int A[]={5,8,7,4,2,3,9};
二叉排序树
3,二叉排序树的插入和生成：
设 BST为空,查找关键字序列为 {5,8,7,4,2,3,
9}，则经过一系列的查找插入之后，可生成一棵二叉树。生成的二叉排序树的过程为：
BSTNode *CreatBST(KeyType A[ ],int n) //返回树根指针
{ BSTNode *bt=NULL; //初始时 bt为空树
int i=0;
while (i<n)
{ InsertBST(bt,A[i]); //将 A[i]插入二叉排序树 T中
i++;
}
return bt; //返回建立的二叉排序树的根指针
}
4,二叉排序树的存储结构及相关算法：
typedef struct node
{ KeyType key; InfoType data;
struct node *lchild,*rchild;
} BSTNode;
26
int InsertBST(BSTNode *&p,KeyType k)
/*在以 *p为根结点的 BST中插入一个关键字为 k的结点。插入成功返回 1,否则返回 0*/
{ if (p==NULL) /*原树为空,新插入的记录为根结点 */
{ p=(BSTNode *)malloc(sizeof(BSTNode));
p->key=k;p->lchild=p->rchild=NULL;
return 1;
}
else if (k==p->key) /*存在相同关键字的结点,返回 0*/
return 0;
else if (k<p->key)
return InsertBST(p->lchild,k);/*插入到左子树中 */
else
return InsertBST(p->rchild,k); /*插入到右子树中 */
}
27
BSTNode *SearchBST(BSTNode *bt,KeyType k)
{ if (bt==NULL || bt->key==k) /*递归终结条件 */
return bt;
if (k<bt->key)
return SearchBST(bt->lchild,k);
else
return SearchBST(bt->rchild,k);
}
28
5,BST的特点
(1) 中序遍历 BST可得到一个关键字的有序序列。
如 关键字序列为 {47,35,80,22,56,65,11}生成的 BST
，其中序遍历序列为 {11,22,35,47,56,65,80}。
47
35 80
22 56
6511
中序序列 {11,22,35,47,56,65,80}
(2) 在 BST上插入新结点时，不必移动其他结点，
仅需改动某结点的指针 (因新结点总是插在 BST上的一个新的叶子结点）。
(3) BST既具有类似折半查找的特性（与 BST的平衡度有关）又采用了链表存储结构（折半查找不能为链表存储结构），因此，对于经常要进行查找、插入和删除记录的有序表，采用 BST尤其合适
。
BST上查找过程与二分查找类似，是从根结点到所找结点的一条路径。与给定值比较次数等于该路径长度 +1(即结点所在的层次数），最大次数不超过树的深度。
ASL左 =（ 1+2+2+3+3+3） /6=14/6
关键字 {45,24,53,12,37,93}（不考虑次序）
45
24 53
12 37 93
（ 45,24,53,12,37,93）
12
24
37
45
53
93
（ 12,24,37,45,53,93）
ASL右 =（ 1+2+3+4+5+6） /6=21/6
6,BST的查找分析但长度为 n的二分查找表对应的判定树是唯一的。而含有 n个结点的 BST却不唯一。
30
最差情况是 BST时蜕化为单支树 (当先后插入的关键字有序 ),树的深度为 n,ASL=(n+1)/2(同顺序查找 )。
最好的情况是 BST形态和折半查找的判定树相同,ASL≈log2n。
随机情况下，其平均查找长度为 1+4log2n,即
T(n)=O(log2n)
因此，含有 n个结点的二叉排序树的平均查找长度和树的形态有关。
为了避免出现单分支树，在构成 BST的过程中可进行“平衡化”处理。
31
10.4 哈希表的查找
10.4.1哈希表在查找表中 (顺序存贮结构的静态查找表或二叉链表表示的动态查找表 ),数据元素的关键字和数据元素在存贮器中的物理位臵并没有（建立）必然的联系，
查找算法是建立在“比较”的基础上：
在顺序查找中：,==”或,!=”
在折半查找,二叉排序树查找时 ;“==”,“<”,“>”。
查找的效率取决于查找过程中所进行的比较次数。
期望,不经比较，一次存取便能得到所查纪录。
32
关键字集合 A
存储地址集合 D
H
这一节将介绍另一种通过 计算 来查找的新型方法 -
------哈希法 (Hash)或称杂凑法、散列法。
设关键字集合 A，地址空间 D,哈希法 就是在 A和
D之间建立一种函数关系 H，通过计算函数 H(k),就能得到关键字 K的地址。
设 D是长度为 n的表,A是含有 m个记录的关键字集合如果存在一个 函数 H,使得对 A中任一关键字 ki,均有：
0≤H(ki) ≤n-1 i=1,2,…,m
同时,ki所标识的记录 Ri在表 D中的地址是 H(ki),则称 函数 H为关键字集合 A到地址空间 D之间的哈希函数
,地址空间 D为哈希表。
33
哈希函数并不一定是一对一的，例如，当 m>n
时，对任何哈希函数 H，至少存在两个关键字
ki≠kj,使得 H(ki)=H(kj),这种对不同关键字而得到同一地址的现象，称为 冲突 。把这种具有不同关键字而具有相同哈希地址的对象称作,同义词,。
因此，在应用哈希查找方法时，主要要解决两个技术问题：
一是构造好哈希函数的方法；
二是研究解决冲突的方法；
一、哈希函数构造方法一个好的哈希函数应满足下列两个条件：
计算简单容易? 冲突极少
直接定址法构造,取关键字或关键字的某个线性函数作散列地址，
即 H(key)=key 或 H(key)=a·key+b
地址 01 02 03 …… 22 ……
年份 1949 1950 1951 …… 1970 ……
人数 …… …… …… ….,….,…..
……
例,有一个解放后出生的人口调查表,每个记录包括年份、
人数等数据项,其中年份为关键字,则哈希函数可取为：
H(key)=key+(-1948),
那么就可方便的存储和查找 1948年后任一年的纪录特点,计算简单且没有冲突发生,适合关键字的分布基本连续，否则，会造成内存单元的大量浪费。
数字分析法
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
数字分布近乎随机所以：取任意两位作为散列地址即可。如取位。
addr
46
72
87
01
22
38
68
19
例 有 80个记录，关键字为 8位十进制数，散列地址为 2位十进制数。
设 n个 d位数的关键字，由 r个不同的符合组成，此 r个符号在关键字的各位出现的频率不一定相同，有些位上分布均匀，有些则不均匀。选择其中均匀分布的 s位作为哈希地址，即 H(key)=“key中数字均匀分布的 s位”,
36
构造,对关键字进行分析,取关键字的若干位或其组合作散列地址适于关键字位数比散列地址位数大，且可能出现的关键字事先知道的情况
除余法构造,取关键字被某个不大于散列表表长 m的数 p除后所得余数作散列地址,即 H(key)=key MOD p,p?m
特点,简单、常用；一般选 p为小于或等于散列表长 m
的某个最大素数比较好。
推荐参数,m=8,16,62,64,128,256,512,1024
p=7,13,31,61,127,251,503,1019
平方取中法例,对下列一组关键字 (0100,0110,1010,1 001,0111)构造其散列函数。
构造,取关键字平方后中间几位作散列地址，取的位数由表长决定适于不知道全部关键字情况首先求关键字的平方值以扩大它们之间的差别，关键字平方的结果为,（ 0010000,0012100,1020100，
1002001,0012321）
然后取中间的几位或其组合作为散列地址，若表长为 1000，则可取中间三位为地址集，即,(100,121，
201,020,123）
折叠法构造,将关键字分割成位数相同的几部分（最后一段的位数可以不同），然后取这几部分的叠加和（舍去高位进位）做散列地址
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
间界叠加适于关键字位数很多，且每一位上数字分布大致均匀情况例：关键字为,04 4220 5864，散列地址位数为 4
种类
1.移位叠加：将分割后的几部分低位对齐相加
2.间界叠加：从一端沿分割界来回折送，然后对齐相加
随机数法构造,取关键字的随机函数值作散列地址,即
H(key)=random(key)
适于关键字长度不等的情况选取散列函数，考虑以下因素：
计算散列函数所需时间
关键字长度
散列表长度（散列地址范围）
关键字分布情况
记录的查找频率
40
二、处理冲突的方法冲突 是指由关键字得到的 Hash地址上已有其他记录处理冲突 就是为该关键字找到另一个 空 的 Hash地址。
开放地址法
Hi＝ (H(key)+di)mod m i=1,2…m -1;
其中,Hi为第 i次冲突的地址,H(key)为 Hash函数值,m为 Hash表表长,di为增量序列。
di为增量序列，有三种取法：
di=1,2,3,…,m -1 称为线性探测法
di=12,-12,22,-22,…,(m -1)2 称为平方探测法
di=伪随机序列 称为伪随机探测法
1.线性探测法,ki=1,2,3,……m -1
di=(H(key)+ki) MOD m
0 1 2,,,H(key),,,m-1
当冲突发生时：
其中,H（ key)为哈希函数,m为表长
d0=h(k)
di=(di-1+1) mod m (1≤i≤m-1)
例,已知一组关键字为 (26,36,41,38,44,15,68,12,06,51,25),用线性探测法解决冲突构造散列表。
取 α =0.75，则表长为 m=? n/ α? =15,散列函数为,H=key%13
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14H26=26%13=0
26H36=36%13=10 36
H41=41%13=2
41
H38=38%13=12
38
H44=44%13=5
44
H15=15%13=2,冲突
H15=(2+1)%15=3，成功
15
H68=68%13=3,冲突
H68=(3+1)%15=4，成功
68
H12=12%13=12,冲突
H68=(12+1)%15=13，成功
12
H6=6%13=6
06 51
H51=51%13=12,冲突
H51=(12+1)%15=13,冲突
H51=(13+1)%15=14,成功
H25=25%13=12,冲突
H25=(12+1)%15=13,冲突
H25=(13+1)%15=14,冲突
H25=(14+1)%15=0,冲突
H25=(15+1)%15=1,成功
25
43
2.二次探测法：
ki=12,-12,22,-22,32,…,± i2(1≤i≤m-1 )
di=(H(key)+ki) MOD m
当冲突发生时：
0 1 2,,,H(key),,,m-1
二次探测法减少了堆积的可能，但不容易探查到整个散列表空间
d0=h(k)
di=(d0+i2) mod m (1≤i≤m-1)
例,已知关键字 (19,14,23,1,68,20,84,27,55,11,10,79),散列函数为,H(key)=key MOD 13,用链地址法处理冲突
0
1
2
3
4
5
6
7
8
9
10
11
12
14 1
68
19 84
20
23
27 79
55
10
11
^
^
^
^
^
^
^
^
^
^
^
^
^
拉链法：
key addr
19 6
14 1
23 10
1 1
68 3
20 7
84 6
27 1
55 3
11 11
10 10
79 1
地址将所有关键字为同义词的记录存储在一个单链表中,
并用一维数组存放头指针,
45
三、散列查找过程及分析
散列查找过程给定 k值计算 H(k)
此地址为空关键字 ==k
查找失败查找成功按处理冲突方法计算 Hi
Y
N
Y
N
例,已知一组关键字 (19,14,23,1,68,20,84,27,55,11,10,79)，其散列函数为,H(key)=key MOD 13,散列 表长为 m=16，用线性探测再散列处理冲突 构造所得散列表如下图：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
14 1 68 27 55 19 20 84 79 23 11 10
查找 K= 84的过程：
首先求其散列地址 H(84)=6，因 a.elem[6]不空且不等于 84.
a.elem
找第一次冲突地址 H1=(6+1) MOD 16=7,而 a.elem[7]不空且不等于 84
找第二次冲突处理后的地址 H2=(6+2) MOD 16=8,
a.elem[8]不空且等于 84，故查找成功，返回记录在表中的序号 8
查找 K=36的过程：
首先求散列地址 H(36)=36 mod 13=10,a.elem[10]不空且不等于 36，
找第一次冲突地址 H1=(10+1)mod 16=11,而 a.elem[11]不空且 ≠36
找第二次冲突地址 H1=(10+2)mod 16=12,而 a.elem[12]不空且 ≠36
找第三次冲突地址 H1=(10+3)mod 16=13,而 a.elem[13] 空，此时可肯定表中不存在值为 36的纪录，查找失败。
例,已知一组关键字 (19,14,23,1,68,20,84,27,55,11,10,79)，其散列函数为,H(key)=key MOD 13,散列 表长为 m=16，用线性探测再散列处理冲突 构造所得散列表如下图：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
14 1 68 27 55 19 20 84 79 23 11 10a.elem
48
散列查找分析
虽然散列表在关键字与纪录的存储位臵之间建立了直接映象，但由于冲突的产生，使得散列表的查找过程仍然是一个给定值和关键字进行比较的过程。
评价散列查找效率仍要用 ASL。
49
=(1*6+2*4+3+4)/12=1.75
0
1
2
3
4
5
6
7
8
9
10
11
12
14
^
1 27 79
68 55
19 84
20
23 10
11
^
^
^
^
^
^
^
^
^
^
^
^
散列地址关键字序列 (19,14,23,1,68,20,84,27,55,11,10,79),其散列函数为 H(key)=key MOD 13的拉链法存贮为
n
i
i
n
i
ii CCPA S L
11 12
1
50
=(1*6+2+3*3+4+9)/12=2.5
关键字序列 (19,14,23,1,68,20,84,27,55,11,10,79),其散列函数为 H(key)=key MOD 13，按线性探测处理冲突构造的散列表为
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
14 1 68 27 55 19 20 84 79 23 11 10
101110167631311H(key)
0 1 0 3 2 0 0 2 8 0 0 2探测次数求查找成功时的平均查找长度。
n
i
i
n
i
ii CCPA S L
11 12
1
小 结：
分类
1.适用的表类型
2.编程方法顺序查找折半查找索引查找二叉排序树的定义基于二叉排序树的查找二叉排序树的插入和删除散列表的构造方法处理冲突的方法基于散列表的查找静态查找表动态查找表散列表
1.对上述三种类型的查找表，各存在何优缺点
2,分析各种查找表的时间复杂度或求 ASL
10.1 查找的基本概念
10.2 线性表的查找
10.3 树表的查找
10.4 哈希表查找第十章 查找
2
查找,也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素的过程。
查找结果,
查找成功 (table中存在给定值的记录，返回该记录的信息或该记录在表中的位臵）
查找不成功 (table中不存在给定值的记录，
返回相关的指示信息 。
10.1 查找的基本概念
3
查找表 (search table):是由同一类型的数据元素
（或记录）构成的集合，集合中的数据元素之间的关系是完全松散的。
查找表的主要操作：
查询某个“特定的”数据元素是否在表中；
检索某个“特定的”数据元素的各种属性；
在查找表中插入一个数据元素；
从查找表中删去某个数据元素。
查找表分为：
静态查找表 (对表中的 DE不 进行插入和删除 )；
动态查找表 (对表中的 DE可 进行插入和删除 )；
10.1 查找的基本概念
4
平均查找长度 (average search length):查找过程中,
对关键字进行比较的平均次数即比较次数的期望值。
n
i
ii cpA S L
1
其中,n是结点个数,pi是查找第 i个结点的概率
Ci是查找第 i个结点所需的比较次数
10.1 查找的基本概念
5
10.2 线性表的查找线性表是表的组织方式中最简单的一种，在其上我们主要介绍 顺序查找、二分查找和分块查找 。
一、顺序查找（ Sequential Search),从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值进行比较，若当前扫描到的结点值与给定值相等，则查找成功；反之，若扫描到最后，仍未找到关键字等于 k的结点，则查找失败。适用于顺序存储结构和链表存储结构。
顺序查找算法：
int SeqSearch(SeqList R,int n,KeyType k)
{ int i=0;
while (i<n && R[i].key!=k) i++; /*从表头往后找 */
if (i>=n)
return -1;
else
return i;
}
i
例 0 1 2 3 4 5 6 7 8 9 10 11
找 64
iiii
比较次数 =7*2
返回结果,i=6
5 13 19 21 37 56 64 75 80 88 92
i i
改进的顺序查找算法：
int SeqSearch(SeqList R,int n,KeyType k)
{ int i=0;
R[n].key=k; //哨兵,免去监测查找完毕的操作
while( R[i].key!=k) i++; //从前往后找
if(i= =n) return -1;
else return i;
}
i
例 0 1 2 3 4 5 6 7 8 9 10 11
找 64
64
监视哨
iiii
比较次数 =7
返回结果,i=6
5 13 19 21 37 56 64 75 80 88 92
i i
i+1
对于含有 n个纪录的表,查找成功 时的平均查找长度为：
1
0
n
i
ii CPA S L
其中,为查找表中第 i个纪录的概率,等概率时iP np i /1?
iC 为找到第 i个记录时，已比较的次数。
keyi
2/)1()1(1 1
0
ninA S L n
i
平均查找长度 (ASL)
9
顺序查找的优缺点：
优点,算法简单且适应面广，对表的结构无任何要求，对线性链表同样适用。
缺点,平均查找长度较大，特别是当 n很大时，
查找效率较低。
10.2 线性表的查找
10
10.2 线性表的查找二、二分查找（ Binary Search)：
有序表,查找表中记录按关键字有序排列的表。
即,r[i].key<=r[i+1].key i=1,2,…,n -1
二分查找：
要求：查找表为有序表
查找过程：先确定待查找记录范围；
然后逐步缩小范围；
直到：查找成功或不成功。
二分查找（ Binary Search):将待查的 k值和有序表的中间位臵 mid=n/2上的结点的关键字进行比较，若相等则查找成功；若 k<R[mid].key,则以同样的方法在区间 [0,mid-1]内进行查找 ;若 k>R[mid].key,则按同样的方法在区间 [mid+1,n-1]内进行查找。又称为折半 查找。
low highmid
05 13 19 21 37 (21)
21 37 (21)
0 1 2 3 4 5 6 7 8 9 10
05 13 19 21 37 56 64 75 80 88 92 （ 21）
05 13 19 21 37 56 64 75 80 88 92 （ 90）
mid
0 1 2 3 4 5 6 7 8 9 10
int BinSearch(SeqList R,int n,KeyType k)
{int low=0,high=n-1,mid;
while (low<=high)
{ mid=(low+high)/2;
if (R[mid].key==k)
return mid;
if (R[mid].key>k)
high=mid-1;
else
low=mid+1;
}
return -1;
}
highlow low mid lowmid lowmidhigh
R 11 90
13
二分查找的判定树或比较树,二分查找过程可用二叉树来描述,我们把当前查找区间的中间位臵上的记录作为根,左子表和右子表中的记录分别作为根的左子树和右子树 。
0 1 2 3 4 5 6 7 8 9 10
05 13 19 21 37 56 64 75 80 88 92 （ 90）
5
2 8
0 3 6 9
1 4 7 102-3-1 5-6 8-9
0-1 1-2 3-4 4-5 6-7 7-8 9-10 10-外部结点
R[0..10]的二分查线的判定树 (n=11)
14
假设有序表的长度 n=2h-1，则描述折半查找的判定树是深度为 h的满二叉树，在等概率情况下查找成功时的平均查找长度为,
1)1(l o g)1(21 2
1
1
1
n
n
nj
n
CPAS L
h
j
j
n
i
iibs
当 n很大时,ASLbs≈log2(n+1)-1
层次,1 结点数,1
2 2
3 4
4 8
15
例 10.1 对 于 给 定 11 个 数 据 元 素 的 有 序 表
{2,3,10,15,20,25,28,29,30,35,40},采用二分查找,试问：
(1)若查找给定值为 20的元素,将依次与表中哪些元素比较？
(2)若查找给定值为 26的元素,将依次与哪些元素比较？
(3)假设查找表中每个元素的概率相同,求查找成功时的平均查找长度和查找不成功时的平均查找长度。
16
25
10 30
2 15 28 35
3 20 29 40
二分查找判定树
(2)若查找给定值为 26的元素,依次与 25,30,28元素比较,共比较 3次 。
(3)在查找成功时,会找到图中某个 圆形 结点,则成功时的平均查找长度：
311 44342211A S L s u c c ＝＝
(1)若查找给定值为 20的元素,依次与表中 25,10,15,20元素比较,共比较 4次 。
在查找不成功时,会找到图中某个 方形 结点,
则不成功时的平均查找长度：
67.312 4834A S L u n s u c c ＝＝
17
对比顺序查找和二分查找的性能之差别：
顺序查找 二分查找表的特性存储结构插删操作
ASL值无序表 有序表顺序或链式结构 顺序结构易于进行 需移动元素大 小
18
10.2 线性表的查找三、分块查找（索引顺序查找 )：
索引表：
按表中的记录关键字分块,R1,R2,…R L.
要求：第 Rk块中的所有关键字小于 Rk+1块中的所有关键字,k=1,2,…L -1,称为“分块有序”
对每块建立一个索引项,包含以下两项内容：
关键字项,为该块中最大关键字值；
指针项,为该块第一个记录在表中的位臵。
所有索引项组成索引表
索引查找过程序分两步进行：
1）确定待查纪录所在的块 (子表 );(有序表的查找方法 )
2）然后在块内查找。 (块内有序或无序，用顺序查找）
如查找 key=74和 key=2
14 34 66
0 5 10
索引表 IDX
8 14 6 9 10 22 34 18 19 31 40 38 54 66
0 1 2 3 4 5 6 7 8 9 10 11 12 13
46
14
第 1块 第 2块 第 3块
key
link
索引表的结点类型：
#define MAXI <索引表的最大长度 >
typedef struct
{ keytype key;
int link;
}Idxtype;
typedef Idxtype IDX[MAXI];
分块查找的平均查找长度：
其中,ASLbn为查找索引表的平均查找长度；
ASLsq为在块中查找元素的平均查找长度。
用二分查找确定块时：
用顺序查找确定块时：
ASL何时最小？
分块查找的优点：查找速度快缺点：需辅助空间及建表较费时
2)1/(l o g2
11)1(l o g
22
ssnsbA S LA S LA S L
sqbnb l k
s2
ns2s
2
1s
2
1bA S LA S LLAS 2
sqbnb l k
sqbnb l k A S LA S LA S L
22
动态查找表的的特点是,表结构本身是在查找过程中动态生成的。即查找不成功时，将该记录插入在动态 查找表中。
10.3 树表的查找一、二叉排序树 (Binary Sort Tree)(又称为二叉查找树）
1,BST定义：
BST或者是一棵空树 ;或者是具有如下性质的 BT:
若左子树非空，则左子树上所有结点的值均小于根结点的值；
若右子树非空，则右子树上所有结点的值均大于根结点的值；
左、右子树也为 BST
45
12 53
3 37
24
100
61
90
78
45
12 53
3 50 49 100
61
90
40
2,查找过程为：
(1)当前 BST非空时,将给定值 k与当前根结点的关键字比较
(2)若相等，查找成功，结束；
若 k小于当前根结点关键字,则将左子树作为当前 BST;
若 k大于当前根结点关键字,则将右子树作为当前 BST；
(3),重复 (1)(2)。
24
5
4 8
972
3
int A[]={5,8,7,4,2,3,9};
二叉排序树
3,二叉排序树的插入和生成：
设 BST为空,查找关键字序列为 {5,8,7,4,2,3,
9}，则经过一系列的查找插入之后，可生成一棵二叉树。生成的二叉排序树的过程为：
BSTNode *CreatBST(KeyType A[ ],int n) //返回树根指针
{ BSTNode *bt=NULL; //初始时 bt为空树
int i=0;
while (i<n)
{ InsertBST(bt,A[i]); //将 A[i]插入二叉排序树 T中
i++;
}
return bt; //返回建立的二叉排序树的根指针
}
4,二叉排序树的存储结构及相关算法：
typedef struct node
{ KeyType key; InfoType data;
struct node *lchild,*rchild;
} BSTNode;
26
int InsertBST(BSTNode *&p,KeyType k)
/*在以 *p为根结点的 BST中插入一个关键字为 k的结点。插入成功返回 1,否则返回 0*/
{ if (p==NULL) /*原树为空,新插入的记录为根结点 */
{ p=(BSTNode *)malloc(sizeof(BSTNode));
p->key=k;p->lchild=p->rchild=NULL;
return 1;
}
else if (k==p->key) /*存在相同关键字的结点,返回 0*/
return 0;
else if (k<p->key)
return InsertBST(p->lchild,k);/*插入到左子树中 */
else
return InsertBST(p->rchild,k); /*插入到右子树中 */
}
27
BSTNode *SearchBST(BSTNode *bt,KeyType k)
{ if (bt==NULL || bt->key==k) /*递归终结条件 */
return bt;
if (k<bt->key)
return SearchBST(bt->lchild,k);
else
return SearchBST(bt->rchild,k);
}
28
5,BST的特点
(1) 中序遍历 BST可得到一个关键字的有序序列。
如 关键字序列为 {47,35,80,22,56,65,11}生成的 BST
，其中序遍历序列为 {11,22,35,47,56,65,80}。
47
35 80
22 56
6511
中序序列 {11,22,35,47,56,65,80}
(2) 在 BST上插入新结点时，不必移动其他结点，
仅需改动某结点的指针 (因新结点总是插在 BST上的一个新的叶子结点）。
(3) BST既具有类似折半查找的特性（与 BST的平衡度有关）又采用了链表存储结构（折半查找不能为链表存储结构），因此，对于经常要进行查找、插入和删除记录的有序表，采用 BST尤其合适
。
BST上查找过程与二分查找类似，是从根结点到所找结点的一条路径。与给定值比较次数等于该路径长度 +1(即结点所在的层次数），最大次数不超过树的深度。
ASL左 =（ 1+2+2+3+3+3） /6=14/6
关键字 {45,24,53,12,37,93}（不考虑次序）
45
24 53
12 37 93
（ 45,24,53,12,37,93）
12
24
37
45
53
93
（ 12,24,37,45,53,93）
ASL右 =（ 1+2+3+4+5+6） /6=21/6
6,BST的查找分析但长度为 n的二分查找表对应的判定树是唯一的。而含有 n个结点的 BST却不唯一。
30
最差情况是 BST时蜕化为单支树 (当先后插入的关键字有序 ),树的深度为 n,ASL=(n+1)/2(同顺序查找 )。
最好的情况是 BST形态和折半查找的判定树相同,ASL≈log2n。
随机情况下，其平均查找长度为 1+4log2n,即
T(n)=O(log2n)
因此，含有 n个结点的二叉排序树的平均查找长度和树的形态有关。
为了避免出现单分支树，在构成 BST的过程中可进行“平衡化”处理。
31
10.4 哈希表的查找
10.4.1哈希表在查找表中 (顺序存贮结构的静态查找表或二叉链表表示的动态查找表 ),数据元素的关键字和数据元素在存贮器中的物理位臵并没有（建立）必然的联系，
查找算法是建立在“比较”的基础上：
在顺序查找中：,==”或,!=”
在折半查找,二叉排序树查找时 ;“==”,“<”,“>”。
查找的效率取决于查找过程中所进行的比较次数。
期望,不经比较，一次存取便能得到所查纪录。
32
关键字集合 A
存储地址集合 D
H
这一节将介绍另一种通过 计算 来查找的新型方法 -
------哈希法 (Hash)或称杂凑法、散列法。
设关键字集合 A，地址空间 D,哈希法 就是在 A和
D之间建立一种函数关系 H，通过计算函数 H(k),就能得到关键字 K的地址。
设 D是长度为 n的表,A是含有 m个记录的关键字集合如果存在一个 函数 H,使得对 A中任一关键字 ki,均有：
0≤H(ki) ≤n-1 i=1,2,…,m
同时,ki所标识的记录 Ri在表 D中的地址是 H(ki),则称 函数 H为关键字集合 A到地址空间 D之间的哈希函数
,地址空间 D为哈希表。
33
哈希函数并不一定是一对一的，例如，当 m>n
时，对任何哈希函数 H，至少存在两个关键字
ki≠kj,使得 H(ki)=H(kj),这种对不同关键字而得到同一地址的现象，称为 冲突 。把这种具有不同关键字而具有相同哈希地址的对象称作,同义词,。
因此，在应用哈希查找方法时，主要要解决两个技术问题：
一是构造好哈希函数的方法；
二是研究解决冲突的方法；
一、哈希函数构造方法一个好的哈希函数应满足下列两个条件：
计算简单容易? 冲突极少
直接定址法构造,取关键字或关键字的某个线性函数作散列地址，
即 H(key)=key 或 H(key)=a·key+b
地址 01 02 03 …… 22 ……
年份 1949 1950 1951 …… 1970 ……
人数 …… …… …… ….,….,…..
……
例,有一个解放后出生的人口调查表,每个记录包括年份、
人数等数据项,其中年份为关键字,则哈希函数可取为：
H(key)=key+(-1948),
那么就可方便的存储和查找 1948年后任一年的纪录特点,计算简单且没有冲突发生,适合关键字的分布基本连续，否则，会造成内存单元的大量浪费。
数字分析法
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
数字分布近乎随机所以：取任意两位作为散列地址即可。如取位。
addr
46
72
87
01
22
38
68
19
例 有 80个记录，关键字为 8位十进制数，散列地址为 2位十进制数。
设 n个 d位数的关键字，由 r个不同的符合组成，此 r个符号在关键字的各位出现的频率不一定相同，有些位上分布均匀，有些则不均匀。选择其中均匀分布的 s位作为哈希地址，即 H(key)=“key中数字均匀分布的 s位”,
36
构造,对关键字进行分析,取关键字的若干位或其组合作散列地址适于关键字位数比散列地址位数大，且可能出现的关键字事先知道的情况
除余法构造,取关键字被某个不大于散列表表长 m的数 p除后所得余数作散列地址,即 H(key)=key MOD p,p?m
特点,简单、常用；一般选 p为小于或等于散列表长 m
的某个最大素数比较好。
推荐参数,m=8,16,62,64,128,256,512,1024
p=7,13,31,61,127,251,503,1019
平方取中法例,对下列一组关键字 (0100,0110,1010,1 001,0111)构造其散列函数。
构造,取关键字平方后中间几位作散列地址，取的位数由表长决定适于不知道全部关键字情况首先求关键字的平方值以扩大它们之间的差别，关键字平方的结果为,（ 0010000,0012100,1020100，
1002001,0012321）
然后取中间的几位或其组合作为散列地址，若表长为 1000，则可取中间三位为地址集，即,(100,121，
201,020,123）
折叠法构造,将关键字分割成位数相同的几部分（最后一段的位数可以不同），然后取这几部分的叠加和（舍去高位进位）做散列地址
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
间界叠加适于关键字位数很多，且每一位上数字分布大致均匀情况例：关键字为,04 4220 5864，散列地址位数为 4
种类
1.移位叠加：将分割后的几部分低位对齐相加
2.间界叠加：从一端沿分割界来回折送，然后对齐相加
随机数法构造,取关键字的随机函数值作散列地址,即
H(key)=random(key)
适于关键字长度不等的情况选取散列函数，考虑以下因素：
计算散列函数所需时间
关键字长度
散列表长度（散列地址范围）
关键字分布情况
记录的查找频率
40
二、处理冲突的方法冲突 是指由关键字得到的 Hash地址上已有其他记录处理冲突 就是为该关键字找到另一个 空 的 Hash地址。
开放地址法
Hi＝ (H(key)+di)mod m i=1,2…m -1;
其中,Hi为第 i次冲突的地址,H(key)为 Hash函数值,m为 Hash表表长,di为增量序列。
di为增量序列，有三种取法：
di=1,2,3,…,m -1 称为线性探测法
di=12,-12,22,-22,…,(m -1)2 称为平方探测法
di=伪随机序列 称为伪随机探测法
1.线性探测法,ki=1,2,3,……m -1
di=(H(key)+ki) MOD m
0 1 2,,,H(key),,,m-1
当冲突发生时：
其中,H（ key)为哈希函数,m为表长
d0=h(k)
di=(di-1+1) mod m (1≤i≤m-1)
例,已知一组关键字为 (26,36,41,38,44,15,68,12,06,51,25),用线性探测法解决冲突构造散列表。
取 α =0.75，则表长为 m=? n/ α? =15,散列函数为,H=key%13
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14H26=26%13=0
26H36=36%13=10 36
H41=41%13=2
41
H38=38%13=12
38
H44=44%13=5
44
H15=15%13=2,冲突
H15=(2+1)%15=3，成功
15
H68=68%13=3,冲突
H68=(3+1)%15=4，成功
68
H12=12%13=12,冲突
H68=(12+1)%15=13，成功
12
H6=6%13=6
06 51
H51=51%13=12,冲突
H51=(12+1)%15=13,冲突
H51=(13+1)%15=14,成功
H25=25%13=12,冲突
H25=(12+1)%15=13,冲突
H25=(13+1)%15=14,冲突
H25=(14+1)%15=0,冲突
H25=(15+1)%15=1,成功
25
43
2.二次探测法：
ki=12,-12,22,-22,32,…,± i2(1≤i≤m-1 )
di=(H(key)+ki) MOD m
当冲突发生时：
0 1 2,,,H(key),,,m-1
二次探测法减少了堆积的可能，但不容易探查到整个散列表空间
d0=h(k)
di=(d0+i2) mod m (1≤i≤m-1)
例,已知关键字 (19,14,23,1,68,20,84,27,55,11,10,79),散列函数为,H(key)=key MOD 13,用链地址法处理冲突
0
1
2
3
4
5
6
7
8
9
10
11
12
14 1
68
19 84
20
23
27 79
55
10
11
^
^
^
^
^
^
^
^
^
^
^
^
^
拉链法：
key addr
19 6
14 1
23 10
1 1
68 3
20 7
84 6
27 1
55 3
11 11
10 10
79 1
地址将所有关键字为同义词的记录存储在一个单链表中,
并用一维数组存放头指针,
45
三、散列查找过程及分析
散列查找过程给定 k值计算 H(k)
此地址为空关键字 ==k
查找失败查找成功按处理冲突方法计算 Hi
Y
N
Y
N
例,已知一组关键字 (19,14,23,1,68,20,84,27,55,11,10,79)，其散列函数为,H(key)=key MOD 13,散列 表长为 m=16，用线性探测再散列处理冲突 构造所得散列表如下图：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
14 1 68 27 55 19 20 84 79 23 11 10
查找 K= 84的过程：
首先求其散列地址 H(84)=6，因 a.elem[6]不空且不等于 84.
a.elem
找第一次冲突地址 H1=(6+1) MOD 16=7,而 a.elem[7]不空且不等于 84
找第二次冲突处理后的地址 H2=(6+2) MOD 16=8,
a.elem[8]不空且等于 84，故查找成功，返回记录在表中的序号 8
查找 K=36的过程：
首先求散列地址 H(36)=36 mod 13=10,a.elem[10]不空且不等于 36，
找第一次冲突地址 H1=(10+1)mod 16=11,而 a.elem[11]不空且 ≠36
找第二次冲突地址 H1=(10+2)mod 16=12,而 a.elem[12]不空且 ≠36
找第三次冲突地址 H1=(10+3)mod 16=13,而 a.elem[13] 空，此时可肯定表中不存在值为 36的纪录，查找失败。
例,已知一组关键字 (19,14,23,1,68,20,84,27,55,11,10,79)，其散列函数为,H(key)=key MOD 13,散列 表长为 m=16，用线性探测再散列处理冲突 构造所得散列表如下图：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
14 1 68 27 55 19 20 84 79 23 11 10a.elem
48
散列查找分析
虽然散列表在关键字与纪录的存储位臵之间建立了直接映象，但由于冲突的产生，使得散列表的查找过程仍然是一个给定值和关键字进行比较的过程。
评价散列查找效率仍要用 ASL。
49
=(1*6+2*4+3+4)/12=1.75
0
1
2
3
4
5
6
7
8
9
10
11
12
14
^
1 27 79
68 55
19 84
20
23 10
11
^
^
^
^
^
^
^
^
^
^
^
^
散列地址关键字序列 (19,14,23,1,68,20,84,27,55,11,10,79),其散列函数为 H(key)=key MOD 13的拉链法存贮为
n
i
i
n
i
ii CCPA S L
11 12
1
50
=(1*6+2+3*3+4+9)/12=2.5
关键字序列 (19,14,23,1,68,20,84,27,55,11,10,79),其散列函数为 H(key)=key MOD 13，按线性探测处理冲突构造的散列表为
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
14 1 68 27 55 19 20 84 79 23 11 10
101110167631311H(key)
0 1 0 3 2 0 0 2 8 0 0 2探测次数求查找成功时的平均查找长度。
n
i
i
n
i
ii CCPA S L
11 12
1
小 结：
分类
1.适用的表类型
2.编程方法顺序查找折半查找索引查找二叉排序树的定义基于二叉排序树的查找二叉排序树的插入和删除散列表的构造方法处理冲突的方法基于散列表的查找静态查找表动态查找表散列表
1.对上述三种类型的查找表，各存在何优缺点
2,分析各种查找表的时间复杂度或求 ASL
