2009-7-30 软件基础教案（第十章 查找）
第十章 查找
1.查找概念
2.顺序表的查找 （ 顺序查找,二分查找和分块查找 ）
3.树表的动态查找 （ 二叉排序树查找 ）
4.哈希表查找的概念和哈希冲突的解决方法
Chapter 10 Search
2009-7-30 软件基础教案（第十章 查找）
10.1 查找的基本概念
1） 查找 Search,又称 检索,是指在大量的数据中 寻找关键字等于给定值 的记录。 若存在这样一个记录，
则称查找成功，否则称查找不成功。 若存在，确定其位置的过程。
2） 关键字 (Keyword),就是数据元素中可以唯一标识一个数据元素的数据项。
例如：学生管理登记卡中的学号。
3） 平均查找长度 (Average Search Length) (ASL)
算法评价,评价时考虑：（ 1） 速度；
（ 2） 占用存储空间；
（ 3） 复杂程度。
2009-7-30 软件基础教案（第十章 查找）
引入平均查找长度，作为评价依据。
平均查找长度：为确定记录在表中的位置所进行的和关键字比较的次数的期望值，简写为
ASL.
含有 n个元素的表中找一个元素成功的 ASL为：
Pi为查找第 i个元素的概率；
Ci为 查到第 i个元素所需的比较次数。
ASL=∑ Pi × Cii=1
n
2009-7-30 软件基础教案（第十章 查找）
结构体数组
typedef struct
{char name[10];
int key;
} eletype;
eletype r[Maxnum];
name[0]
…
name[9]
key
r[0]
r[1]
………
r[Maxnum]
name[0]
…
name[9]
key
设表中记录以顺序存储结构组织。
每个记录包括：关键字，其他数据项等。
其类型说明用 C语言描述如下：
4) 类型说明：
2009-7-30 软件基础教案（第十章 查找）
5）查找方法,
顺序表静态查找树表动态查找（ 二叉排序树查找 ）
哈希查找顺序查找二分查找分块查找
2009-7-30 软件基础教案（第十章 查找）
i=0
18 26 32 21 37 56 64 75
i=1 i=5i=4i=3i=2
基本思想：从第一个元素开始，将给定值与表中逐个元素的关键字比较，直至检索成功或直至最后一个元素检索失败为止。
10.2,顺序表的静态查找
10.2.1,顺序查找：
2009-7-30 软件基础教案（第十章 查找）
int Seqsearch (eletype r[ ],int key,int n)
{ int i=0;
while ( r[ i ].key != key && i< n)
i ++;
if (r[ i ].key ==key)
return i ;
else return -1 ;
}
顺序查找算法：
i=0
18 26 32 21 37 56 64 75
i=1 i=5i=4i=3i=2
演示：查找
key=56
2009-7-30 软件基础教案（第十章 查找）
算法分析：
ASL=∑ Pi × Ci
=1/n (1+2+……..+n)
=（ n+1） /2
i=1
n
表从 r[1]~r[Max],r[0]存放 key。
也可以这样做,
32
int seqsearch(eletype r[],int key,int n)
{int i;
r[0].key=key;
i=n;
while(r[i].key!=key)
i--;
return i;
}
算法描述
i=8
18 26 32 21 37 56 64 75
i=7i=6i=5i=4i=3
0 1 2 3 4 5 6 7 8
演示：查找
key=32
2009-7-30 软件基础教案（第十章 查找）
算法分析算法简单，效率较低算法特点
ASL=∑ Pi × Ci
=(1/n) × (1+2+……..+n)
=(n+1)/2
i=1
n
2009-7-30 软件基础教案（第十章 查找）
10.2.2 二分查找法（对半或折半查找）
针对有序表使用的查找方法，是简单有效的方法。
有序表,纪录的关键字以 递增（或递减） 顺序排列的表。
基本思想,给定值 key与中间位置的记录的关键字比较，若相等则查找成功；若给定值大于中间位置记录的关键字值，则在表的后半部分继续二分查找；否则在表的前半部分进行二分查找，直至查找成功或不成功。
2009-7-30 软件基础教案（第十章 查找）
（ 1）计算中间位置 mid=(low+high)/2取整。
（ 2） key与 R[mid].key比较若 key=R [mid].key则查找成功；
若 key<R[mid].key,则 high=mid-1,转（ 3）。
若 key>R[mid].key,则 low=mid+1,转（ 3）。
（ 3）若 low≤high,则重复（ 1）
否则：查找不成功，结束。
1.二分查找的步骤：
2009-7-30 软件基础教案（第十章 查找）
Search
18 26 32 45 52 66 80 91
high
mid
52 66 80 91
low
80 91
mid
用二分查找法在顺序表中查找关键字为 80的纪录！
low
low high
high
mid
2.二分查找的示例：
2009-7-30 软件基础教案（第十章 查找）
low
18 26 32 45 52 66 80 91
highmid
low highmid
high
Low
mid
18 26 32 45 52 66 80 91
18 26 32 45 52 66 80 91
low
18 26 32 45 52 66 80 91
high
查找关键字为 10的纪录！
注意：使用二分查找算法时，
线性表中的元素必须按照关键字 排列有序；
并且必须以 顺序存储方式 存储。
int binsearch(elemtype r[],int
n,int key)
{int low,high,mid;
low=0;
high=n-1;
while(low<=high)
{mid=(low+high)/2;
if(key==r[mid].key)return mid;
else if(key > r[mid].key)
low=mid+1;
else high=mid-1;
}
returu –1;
}
算法描述初始化循环条件计算中间下标查找成功前半部分后半部分查找失败
int binsearch(elemtype
r[],int n,int key)
{int low,high,mid;
low=0;high=n-1;
while(low<=high)
{mid=(low+high)/2;
if(key==r[mid].key)
return mid;
else if(key > r[mid].key)
low=mid+1;
else high=mid-1;
}
returu –1;
}
low
18 26 32 45 52 66 80 91
highmid
52 66 80 91
low highmid
80 91
highLowmid
用二分查找法在顺序表中查找关键字为 80的纪录！
low=mid+1;
2009-7-30 软件基础教案（第十章 查找）
假设：查找关键字为 0~6的数据
3.二分法算法分析 3
5
64
1
0 2
二叉判定树
假设：有序表长度为 n,且 n≤2h-1
若 n=2h-1
则：查找过程为一棵深度为 h的满二叉树。
查找的过程形成二叉判定树
ASL=1/7(1+2× 2+4× 3)
=2.43
2009-7-30 软件基础教案（第十章 查找）
1.比顺序查找效率高
2.只适用于有序的顺序存储的表。
1l o g1 )1(2n
n
nA S L
算法特点,
ASL≈log2(n+1)-1 ≈ log2n
ASL=∑[(1/n)× 2i-1 × i]
i=1
h
则满二叉树的第 i 层有 2i-1个结点。 (i从 1开始 )
2009-7-30 软件基础教案（第十章 查找）
10.2.3,分块查找（索引顺序查找）
将顺序查找法与二分查找法结合
1.基本思想,
使用分块查找算法时，要求将线性表均匀地分成若干 块,每块的元素不要求有序，但一定要保证 块间有序 。另外，对表要进行索引存储。即新建一个索引表，存放相应块中最大关键字。
分块查找实际上是 先 在索引表中进行 顺序查找 或 二分查找,再 在块内进行 顺序查找。
例如,{17,8,21,19,31,33,25,22，
43,37,35,40,61,78,73,55}
分块 [17,8,21,19],[31,33,25,22]，
[43,37,35,40],[61,73,78,55]
索引表,21 33 43 78
21
33
43
78
关键字 地址数据表
8 …
21 …
31 …
33 …
25 …
43 …
61 …
37 …
35 …
73 …
78 …
19 …
22 …
40 …
55 …
17 …
typedef struct
{char name[10];
int key;
} elemtype;
eletype r[Max];
typedef struct
{ int key;
int link;
} indextype;
indextype lr[m];
索引表结构：
顺序表结构：
表结构说明：
int indexsearch(indextype lr[],eletype r[],
int key,int L,int m)
{int i,j;
i=0; //*在索引表中顺序查找 *//
while(i<m && lr[i].key<key)
i++;
if(i>=m) return -1;
else //*在顺序表中顺序查找 *//
{j=lr[i].link;
while(key!=r[j].key && j-lr[i].link<L)
j++;
if(key==r[j].key) return j;
else return -1;
}
}
索引表：
lr[0~m-1]
顺序表：
r[]
块长,L
算法描述限制查找的范围
int indexsearch(indextype lr[],eletype r[],
int key,int L,int m)
{int i,j;
i=0; //*在索引表中顺序查找 *//
while(i<m && lr[i].key<key)
i++;
if(i>=m) return -1;
else //*在顺序表中顺序查找 *//
{j=lr[i].link;
while(key!=r[j].key && j-lr[i].link<L)
j++;
if(key==r[j].key) return j;
else return -1;
}
}
演示,key=25
L=3; M=2
21 0
33 4
43 8
8 …
21 …
31 …
33 …
25 …
43 …
37 …
35 …
19 …
22 …
40 …
17 …
Lr[]
Key link
r[]
i=0
i=1 j=4
j=5
j=6
2009-7-30 软件基础教案（第十章 查找）
练习 2：
索引表：采用二分查找法顺序表：采用顺序查找法算法练习练习 1：索引表和顺序表采用改进顺序查找法
2009-7-30 软件基础教案（第十章 查找）
索引表采用顺序查找
2.算法分析假设：长度为 n的顺序表分成 b块，每块长度为 L,
ASLb=∑[(1/b)× i]
=(b+1)/2
i=1
b
ASLw=∑[(1/L)× i]
=(L+1)/2
i=1
L
块内采用顺序查找
ASLblocks=
(b+1)/2+(L+1)/2
2009-7-30 软件基础教案（第十章 查找）
效率介于顺序查找和二分查找之间线性表存储结构为索引存储结构算法特点索引表中采用二分查找ASLb=log2(b+1)-1
ASLblocks= log2(b+1)-1 +(L+1)/2
ASLw=(L+1)/2
总之：顺序表结构适用于查找操作，
不适于做插入和删除的操作。
2009-7-30 软件基础教案（第十章 查找）
10.3,树表的动态查找用树结构存储纪录既可查找又可插入和删除
1.树表查找方法：
1.二叉排序树查找
2.B-树查找
3.B+树查找与二分查找类似，逐步缩小查找范围。
2,二叉排序树查找
2009-7-30 软件基础教案（第十章 查找）
typedef struct bsnode
{int key;
struct bsnode *L;
struct bsnode *R;
} bstree;
二叉排序树结点结构 C语言描述
2009-7-30 软件基础教案（第十章 查找）
bstree *btsearch(bstree *p,int key)
//p指向二叉排序树的根结点 *//
{while(p!=NULL)
{if(key==p->key)
return p;
else if(key<p->key)
p=p->L;
else p=p->R;
}
return NULL;
}
算法描述：
结束条件查找成功在左子树中查找在右子树中查找查找失败
2009-7-30 软件基础教案（第十章 查找）
bstree *btsearch(bstree
*p,int key)
//p指向二叉排序树的根结点 *//
{while(p!=NULL)
{if(key==p->key)
return p;
else if(key<p->key)
p=p->L;
else p=p->R;
}
return NULL;
}
15
10 18
2 11
8
16 25
11
p
p
p
p
演示：
Key=8
2009-7-30 软件基础教案（第十章 查找）
算法分析
1l o g1 )1(2nnnA S L
ASL≈log2(n+1)-1
二叉排序树查找与二分法查找类似，与关键字比较的次数不会超过树的深度。
最好情况,二叉排序树为一棵平衡二叉树最坏情况,二叉排序树为一棵单支树，
与顺序查找情况相同。
2009-7-30 软件基础教案（第十章 查找）
10.4 哈希查找（散列查找）
前述的查找方法建立在,比较,的基础上，查找的次数依赖于查找过程中进行比较的次数。
问题,能否不用比较就能 直接计算 出记录的存储地址，从而找到所要的结点？
----采用散列（ hash）方法。
2009-7-30 软件基础教案（第十章 查找）
10.4.1.哈希 (散列 )表的基本概念
1.哈希（又称杂凑、散列）的基本思想：
以结点的键值 k为自变量，通过一定的函数关系 h计算出对应的函数值 h(k),把这个值解释为结点的存储地址（哈希地址），将结点存入该地址中去。
2.函数 h---哈希函数 h(k)---哈希 地址
3.基本区 ---分配给哈希表的连续存储空间。
4.冲突的概念：
若对于不同的键值 k1和 k2,且 k1<>k2,但
h(k1)=h(k2)，即具有相同的散列地址，称为冲突。
2009-7-30 软件基础教案（第十章 查找）
例,key={3,15,20,24},m=5（表长），
h(k)=k%5,h(15)=h(20),产生冲突。
4.同义词 ---发生冲突的两个或多个键值。
5.哈希 (散列 )表 ---
是根据设定的哈希 (散列 )函数和相应解决冲突的方法为一组结点建立的一张表，表中的结点的存储位置依赖于设定的哈希 (散列 )函数和处理冲突的方法。
2009-7-30 软件基础教案（第十章 查找）
散列表和查找问题,如何选择一个好的散列函数？即主要考虑：
（ 1）能将键值均匀地分布在整个地址空间，使冲突机会尽量少。
（ 2）同时选定一个解决冲突的办法（即如何存储冲突的同义词）。
2009-7-30 软件基础教案（第十章 查找）
哈希冲突主要与三个因素有关：
1.与装填因子 α有关。装填因子是指哈希表中已存入数据元素个数 n与哈希地址空间大小 m的比值，即,α=n/m,
当 α越小，冲突可能性越小。 α控制在 0.6-0.9范围内。
2.与所采用的哈希函数有关。
3.与解决哈希冲突的哈希冲突函数有关。
2009-7-30 软件基础教案（第十章 查找）
10.4.2.哈希函数构造方法
（ 1）直接定址法,
当关键字是整型数时，取关键字作为哈希地址。
H(k)=k 或 H(k)=ak+b （ a,b为常数）
特点：简单；浪费空间；
例：一组关键码,{ 942148,941269,940527,941630,
941805,941558,942047,940001 }。 散列函数为
H (k) = k - 940000
则有 H (942148) = 2148 H (941269) = 1269
H (940527) = 527 H (941630) = 1630
H (941805) = 1805 H (941558) = 1558
H (942047) = 2047 H (940001) = 1
2009-7-30 软件基础教案（第十章 查找）
（ 2）除留余数法,选择一个适当的正整数 p（通常 p取小于或等于表长的最大素数），用 p去除键值，取其余数作为散列地址，即,h(k)=k mod p
P的取法：实践证明，取小于表长的最大质数。
例,设表长 m=8,16,32,64,128
则,p=7,13,31,61,127
例：有一个关键码 key = 962148，散列表大小
m = 25，即 取质数 p= 23。散列函数 h ( k ) =
k % p。则散列地址为
h ( 962148 ) = 962148 % 23 = 12。
（ 3）数字分析法设有 n 个 d 位数，每一位可能有 r 种不同的符号。这 r
种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布均匀些；在某些位上分布不均匀，只有某几种符号经常出现。可根据散列表的大小，选取其中各种符号分布均匀的若干位作为散列地址。
计算各位数字中符号分布的均匀度?k 的公式：
其中,表示第 i 个符号在第 k 位上出现的次数,n/r
表示各种符号在 n 个数中均匀出现的期望值。计算出的?k
值越小，表明在该位 (第 k 位 )各种符号分布得越均匀。
若散列表地址范围有 3 位数字,取各关键码的④⑤⑥位做为记录的散列地址。也可以把第①，②，③和第⑤位相加，
舍去进位位，变成一位数，与第④，⑥位合起来作为散列地址。还有其它方法。
r
i
k
ik rn
1
2)/(αλ
2009-7-30 软件基础教案（第十章 查找）
9 4 2 1 4 8 ① 位,? 1 = 510.60
9 4 1 2 6 9 ② 位,? 2 = 510.60
9 4 0 5 2 7 ③ 位,? 3 = 110.60
9 4 1 6 3 0 ④ 位,? 4 = 110.60
9 4 1 8 0 5 ⑤ 位,? 5 = 110.60
9 4 1 5 5 8 ⑥ 位,? 6 = 110.60
9 4 2 0 4 7
9 4 0 0 0 1
① ② ③ ④ ⑤ ⑥
数字分析法仅适用于事先明确知道表中所有关键码每一位数值的分布情况，它完全依赖于关键码集合。如果换一个关键码集合，
选择哪几位要重新决定。
2009-7-30 软件基础教案（第十章 查找）
（ 4）折叠法
此方法把关键码自左到右分成位数相等的几部分，
每一部分的位数应与散列表地址位数相同，只有最后一部分的位数可以短一些。
把这些部分的数据叠加起来，就可以得到具有该关键码的记录的散列地址。
有两种叠加方法：
移位法 — 把各部分的最后一位对齐相加；
分界法 — 各部分不折断，沿各部分的分界来回折叠，然后对齐相加，将相加的结果当做散列地址。
2009-7-30 软件基础教案（第十章 查找）
把超出地址位数的最高位删去,仅保留最低的 3位，做为可用的散列地址。
例：设给定的关键码为 key = 23938587841，若存储空间限定 3 位,则划分结果为每段 3 位,上述关键码可划分为 4
段,239 385 878 41
2009-7-30 软件基础教案（第十章 查找）
10.4.3.哈希冲突解决方法两种处理冲突的基本方法：
拉链法、开放地址法
（ 1）拉链法 （外链法、内链法）：
外链法 ---把具有相同哈希地址的键值都存放在一个同义词链表中（称为桶），若有
m个同义词，就建 m个链表（桶）。
内链法 ---把发生冲突的所有同义词建立一个单链表。
2009-7-30 软件基础教案（第十章 查找）
例：对于 m=5,h(x)=x%5,关键值序列
={1,2,5,7,9,10}
基本区
∧
5 ∧10
1 ∧
2 7 ∧
9 ∧
key next
外链法示例
2009-7-30 软件基础教案（第十章 查找）
基本区 ---数组 t[m]存放各个链表的头指针，
其下标表示关键字为 k的记录所在的桶号。
同义词链表 ---在基本区外开辟。
结点类型描述：
type struct node
{int key;
struct node *next;
}JD;
基本运算描述：
（ 1）查找结点、
（ 2）插入结点、删除结点。
2009-7-30 软件基础教案（第十章 查找）
（ 2）开放地址法
当冲突发生时，使用某种方法在基本表中形成一个探查序列，沿着此序列逐个地址去探查，直到找到一个 开放的地址（空位置）,将发生冲突的键值放到该 地址中。
Hi(k)=(H(k)+di)mod m
(i=1,2,…,k(k?m-1))
m:表长
di,每次探测时的地址增量
di不同取值：
(1) di =1,2,3,…
(2) di =12,-12,22,-22,…
(3) di =伪随机序列
(4) di =2i-1
分类：
线性探测法再 (二次 )散列探测法伪随机再散列平方探查法
2009-7-30 软件基础教案（第十章 查找）
例：
记录集合,{R1,R2,R3,…,R8},m=10,
它们的哈希地址为：
H(k1)=2,H(k2)=2,H(k3)=3,H(k4)=3,
H(k5)=8,H(k6)=0,H(k7)=7,H(k8)=9,
用线性探测法和再散列探测法构造哈希表
2009-7-30 软件基础教案（第十章 查找）
H(k1)=2,H(k2)=2,H(k3)=3,H(k4)=3,
H(k5)=8,H(k6)=0,H(k7)=7,H(k8)=9,
线性探测法
0
1
2
3
4
5
6
7
8
9
R1
R2
R3
R4
R5
R6
R7
R8
二次探测再散列法
0
1
2
3
4
5
6
7
8
9
R1
R2
R3
R4
R5
R6
R7
R8
2009-7-30 软件基础教案（第十章 查找）
设：哈希表 A[m]
公共溢出表 O[v]
冲突时，把记录放到公共溢出表的尾部
（ 3）建立公共溢出表
2009-7-30 软件基础教案（第十章 查找）
10.4.4 哈希表的查找方法,
1) 计算哈希函数，得出哈希地址 H(ki)
2) 若 R(H(ki))=NULL 则：查找失败，退出；否则，进入
3）
3) R(H(ki)).key=key?,相等，则查找成功，退出；否则，
进入 4）
4) 不相等，用解决冲突的方法，继续查找
2009-7-30 软件基础教案（第十章 查找）
例：哈希表如下：解决冲突方法：线性探测法
0
1
2
3
4
5
6
7
8
9
R1
R2
R3
R4
R5
R6
R7
R8
查找 R4,key
H(k4)=3
R4.key? R2.key
R4.key? R3.key
查找成功
2009-7-30 软件基础教案（第十章 查找）
总结：
概念,
关键字，平均查找长度算法及算法评价,顺序查找（原理及算法）
二分查找（原理及算法）
分块查找（原理）
二叉排序树查找（原理及算法）
哈希查找（原理）
作业,10-1,10-2,10-6,10-7,10-9
第十章 查找
1.查找概念
2.顺序表的查找 （ 顺序查找,二分查找和分块查找 ）
3.树表的动态查找 （ 二叉排序树查找 ）
4.哈希表查找的概念和哈希冲突的解决方法
Chapter 10 Search
2009-7-30 软件基础教案（第十章 查找）
10.1 查找的基本概念
1） 查找 Search,又称 检索,是指在大量的数据中 寻找关键字等于给定值 的记录。 若存在这样一个记录，
则称查找成功，否则称查找不成功。 若存在，确定其位置的过程。
2） 关键字 (Keyword),就是数据元素中可以唯一标识一个数据元素的数据项。
例如：学生管理登记卡中的学号。
3） 平均查找长度 (Average Search Length) (ASL)
算法评价,评价时考虑：（ 1） 速度；
（ 2） 占用存储空间；
（ 3） 复杂程度。
2009-7-30 软件基础教案（第十章 查找）
引入平均查找长度，作为评价依据。
平均查找长度：为确定记录在表中的位置所进行的和关键字比较的次数的期望值，简写为
ASL.
含有 n个元素的表中找一个元素成功的 ASL为：
Pi为查找第 i个元素的概率；
Ci为 查到第 i个元素所需的比较次数。
ASL=∑ Pi × Cii=1
n
2009-7-30 软件基础教案（第十章 查找）
结构体数组
typedef struct
{char name[10];
int key;
} eletype;
eletype r[Maxnum];
name[0]
…
name[9]
key
r[0]
r[1]
………
r[Maxnum]
name[0]
…
name[9]
key
设表中记录以顺序存储结构组织。
每个记录包括：关键字，其他数据项等。
其类型说明用 C语言描述如下：
4) 类型说明：
2009-7-30 软件基础教案（第十章 查找）
5）查找方法,
顺序表静态查找树表动态查找（ 二叉排序树查找 ）
哈希查找顺序查找二分查找分块查找
2009-7-30 软件基础教案（第十章 查找）
i=0
18 26 32 21 37 56 64 75
i=1 i=5i=4i=3i=2
基本思想：从第一个元素开始，将给定值与表中逐个元素的关键字比较，直至检索成功或直至最后一个元素检索失败为止。
10.2,顺序表的静态查找
10.2.1,顺序查找：
2009-7-30 软件基础教案（第十章 查找）
int Seqsearch (eletype r[ ],int key,int n)
{ int i=0;
while ( r[ i ].key != key && i< n)
i ++;
if (r[ i ].key ==key)
return i ;
else return -1 ;
}
顺序查找算法：
i=0
18 26 32 21 37 56 64 75
i=1 i=5i=4i=3i=2
演示：查找
key=56
2009-7-30 软件基础教案（第十章 查找）
算法分析：
ASL=∑ Pi × Ci
=1/n (1+2+……..+n)
=（ n+1） /2
i=1
n
表从 r[1]~r[Max],r[0]存放 key。
也可以这样做,
32
int seqsearch(eletype r[],int key,int n)
{int i;
r[0].key=key;
i=n;
while(r[i].key!=key)
i--;
return i;
}
算法描述
i=8
18 26 32 21 37 56 64 75
i=7i=6i=5i=4i=3
0 1 2 3 4 5 6 7 8
演示：查找
key=32
2009-7-30 软件基础教案（第十章 查找）
算法分析算法简单，效率较低算法特点
ASL=∑ Pi × Ci
=(1/n) × (1+2+……..+n)
=(n+1)/2
i=1
n
2009-7-30 软件基础教案（第十章 查找）
10.2.2 二分查找法（对半或折半查找）
针对有序表使用的查找方法，是简单有效的方法。
有序表,纪录的关键字以 递增（或递减） 顺序排列的表。
基本思想,给定值 key与中间位置的记录的关键字比较，若相等则查找成功；若给定值大于中间位置记录的关键字值，则在表的后半部分继续二分查找；否则在表的前半部分进行二分查找，直至查找成功或不成功。
2009-7-30 软件基础教案（第十章 查找）
（ 1）计算中间位置 mid=(low+high)/2取整。
（ 2） key与 R[mid].key比较若 key=R [mid].key则查找成功；
若 key<R[mid].key,则 high=mid-1,转（ 3）。
若 key>R[mid].key,则 low=mid+1,转（ 3）。
（ 3）若 low≤high,则重复（ 1）
否则：查找不成功，结束。
1.二分查找的步骤：
2009-7-30 软件基础教案（第十章 查找）
Search
18 26 32 45 52 66 80 91
high
mid
52 66 80 91
low
80 91
mid
用二分查找法在顺序表中查找关键字为 80的纪录！
low
low high
high
mid
2.二分查找的示例：
2009-7-30 软件基础教案（第十章 查找）
low
18 26 32 45 52 66 80 91
highmid
low highmid
high
Low
mid
18 26 32 45 52 66 80 91
18 26 32 45 52 66 80 91
low
18 26 32 45 52 66 80 91
high
查找关键字为 10的纪录！
注意：使用二分查找算法时，
线性表中的元素必须按照关键字 排列有序；
并且必须以 顺序存储方式 存储。
int binsearch(elemtype r[],int
n,int key)
{int low,high,mid;
low=0;
high=n-1;
while(low<=high)
{mid=(low+high)/2;
if(key==r[mid].key)return mid;
else if(key > r[mid].key)
low=mid+1;
else high=mid-1;
}
returu –1;
}
算法描述初始化循环条件计算中间下标查找成功前半部分后半部分查找失败
int binsearch(elemtype
r[],int n,int key)
{int low,high,mid;
low=0;high=n-1;
while(low<=high)
{mid=(low+high)/2;
if(key==r[mid].key)
return mid;
else if(key > r[mid].key)
low=mid+1;
else high=mid-1;
}
returu –1;
}
low
18 26 32 45 52 66 80 91
highmid
52 66 80 91
low highmid
80 91
highLowmid
用二分查找法在顺序表中查找关键字为 80的纪录！
low=mid+1;
2009-7-30 软件基础教案（第十章 查找）
假设：查找关键字为 0~6的数据
3.二分法算法分析 3
5
64
1
0 2
二叉判定树
假设：有序表长度为 n,且 n≤2h-1
若 n=2h-1
则：查找过程为一棵深度为 h的满二叉树。
查找的过程形成二叉判定树
ASL=1/7(1+2× 2+4× 3)
=2.43
2009-7-30 软件基础教案（第十章 查找）
1.比顺序查找效率高
2.只适用于有序的顺序存储的表。
1l o g1 )1(2n
n
nA S L
算法特点,
ASL≈log2(n+1)-1 ≈ log2n
ASL=∑[(1/n)× 2i-1 × i]
i=1
h
则满二叉树的第 i 层有 2i-1个结点。 (i从 1开始 )
2009-7-30 软件基础教案（第十章 查找）
10.2.3,分块查找（索引顺序查找）
将顺序查找法与二分查找法结合
1.基本思想,
使用分块查找算法时，要求将线性表均匀地分成若干 块,每块的元素不要求有序，但一定要保证 块间有序 。另外，对表要进行索引存储。即新建一个索引表，存放相应块中最大关键字。
分块查找实际上是 先 在索引表中进行 顺序查找 或 二分查找,再 在块内进行 顺序查找。
例如,{17,8,21,19,31,33,25,22，
43,37,35,40,61,78,73,55}
分块 [17,8,21,19],[31,33,25,22]，
[43,37,35,40],[61,73,78,55]
索引表,21 33 43 78
21
33
43
78
关键字 地址数据表
8 …
21 …
31 …
33 …
25 …
43 …
61 …
37 …
35 …
73 …
78 …
19 …
22 …
40 …
55 …
17 …
typedef struct
{char name[10];
int key;
} elemtype;
eletype r[Max];
typedef struct
{ int key;
int link;
} indextype;
indextype lr[m];
索引表结构：
顺序表结构：
表结构说明：
int indexsearch(indextype lr[],eletype r[],
int key,int L,int m)
{int i,j;
i=0; //*在索引表中顺序查找 *//
while(i<m && lr[i].key<key)
i++;
if(i>=m) return -1;
else //*在顺序表中顺序查找 *//
{j=lr[i].link;
while(key!=r[j].key && j-lr[i].link<L)
j++;
if(key==r[j].key) return j;
else return -1;
}
}
索引表：
lr[0~m-1]
顺序表：
r[]
块长,L
算法描述限制查找的范围
int indexsearch(indextype lr[],eletype r[],
int key,int L,int m)
{int i,j;
i=0; //*在索引表中顺序查找 *//
while(i<m && lr[i].key<key)
i++;
if(i>=m) return -1;
else //*在顺序表中顺序查找 *//
{j=lr[i].link;
while(key!=r[j].key && j-lr[i].link<L)
j++;
if(key==r[j].key) return j;
else return -1;
}
}
演示,key=25
L=3; M=2
21 0
33 4
43 8
8 …
21 …
31 …
33 …
25 …
43 …
37 …
35 …
19 …
22 …
40 …
17 …
Lr[]
Key link
r[]
i=0
i=1 j=4
j=5
j=6
2009-7-30 软件基础教案（第十章 查找）
练习 2：
索引表：采用二分查找法顺序表：采用顺序查找法算法练习练习 1：索引表和顺序表采用改进顺序查找法
2009-7-30 软件基础教案（第十章 查找）
索引表采用顺序查找
2.算法分析假设：长度为 n的顺序表分成 b块，每块长度为 L,
ASLb=∑[(1/b)× i]
=(b+1)/2
i=1
b
ASLw=∑[(1/L)× i]
=(L+1)/2
i=1
L
块内采用顺序查找
ASLblocks=
(b+1)/2+(L+1)/2
2009-7-30 软件基础教案（第十章 查找）
效率介于顺序查找和二分查找之间线性表存储结构为索引存储结构算法特点索引表中采用二分查找ASLb=log2(b+1)-1
ASLblocks= log2(b+1)-1 +(L+1)/2
ASLw=(L+1)/2
总之：顺序表结构适用于查找操作，
不适于做插入和删除的操作。
2009-7-30 软件基础教案（第十章 查找）
10.3,树表的动态查找用树结构存储纪录既可查找又可插入和删除
1.树表查找方法：
1.二叉排序树查找
2.B-树查找
3.B+树查找与二分查找类似，逐步缩小查找范围。
2,二叉排序树查找
2009-7-30 软件基础教案（第十章 查找）
typedef struct bsnode
{int key;
struct bsnode *L;
struct bsnode *R;
} bstree;
二叉排序树结点结构 C语言描述
2009-7-30 软件基础教案（第十章 查找）
bstree *btsearch(bstree *p,int key)
//p指向二叉排序树的根结点 *//
{while(p!=NULL)
{if(key==p->key)
return p;
else if(key<p->key)
p=p->L;
else p=p->R;
}
return NULL;
}
算法描述：
结束条件查找成功在左子树中查找在右子树中查找查找失败
2009-7-30 软件基础教案（第十章 查找）
bstree *btsearch(bstree
*p,int key)
//p指向二叉排序树的根结点 *//
{while(p!=NULL)
{if(key==p->key)
return p;
else if(key<p->key)
p=p->L;
else p=p->R;
}
return NULL;
}
15
10 18
2 11
8
16 25
11
p
p
p
p
演示：
Key=8
2009-7-30 软件基础教案（第十章 查找）
算法分析
1l o g1 )1(2nnnA S L
ASL≈log2(n+1)-1
二叉排序树查找与二分法查找类似，与关键字比较的次数不会超过树的深度。
最好情况,二叉排序树为一棵平衡二叉树最坏情况,二叉排序树为一棵单支树，
与顺序查找情况相同。
2009-7-30 软件基础教案（第十章 查找）
10.4 哈希查找（散列查找）
前述的查找方法建立在,比较,的基础上，查找的次数依赖于查找过程中进行比较的次数。
问题,能否不用比较就能 直接计算 出记录的存储地址，从而找到所要的结点？
----采用散列（ hash）方法。
2009-7-30 软件基础教案（第十章 查找）
10.4.1.哈希 (散列 )表的基本概念
1.哈希（又称杂凑、散列）的基本思想：
以结点的键值 k为自变量，通过一定的函数关系 h计算出对应的函数值 h(k),把这个值解释为结点的存储地址（哈希地址），将结点存入该地址中去。
2.函数 h---哈希函数 h(k)---哈希 地址
3.基本区 ---分配给哈希表的连续存储空间。
4.冲突的概念：
若对于不同的键值 k1和 k2,且 k1<>k2,但
h(k1)=h(k2)，即具有相同的散列地址，称为冲突。
2009-7-30 软件基础教案（第十章 查找）
例,key={3,15,20,24},m=5（表长），
h(k)=k%5,h(15)=h(20),产生冲突。
4.同义词 ---发生冲突的两个或多个键值。
5.哈希 (散列 )表 ---
是根据设定的哈希 (散列 )函数和相应解决冲突的方法为一组结点建立的一张表，表中的结点的存储位置依赖于设定的哈希 (散列 )函数和处理冲突的方法。
2009-7-30 软件基础教案（第十章 查找）
散列表和查找问题,如何选择一个好的散列函数？即主要考虑：
（ 1）能将键值均匀地分布在整个地址空间，使冲突机会尽量少。
（ 2）同时选定一个解决冲突的办法（即如何存储冲突的同义词）。
2009-7-30 软件基础教案（第十章 查找）
哈希冲突主要与三个因素有关：
1.与装填因子 α有关。装填因子是指哈希表中已存入数据元素个数 n与哈希地址空间大小 m的比值，即,α=n/m,
当 α越小，冲突可能性越小。 α控制在 0.6-0.9范围内。
2.与所采用的哈希函数有关。
3.与解决哈希冲突的哈希冲突函数有关。
2009-7-30 软件基础教案（第十章 查找）
10.4.2.哈希函数构造方法
（ 1）直接定址法,
当关键字是整型数时，取关键字作为哈希地址。
H(k)=k 或 H(k)=ak+b （ a,b为常数）
特点：简单；浪费空间；
例：一组关键码,{ 942148,941269,940527,941630,
941805,941558,942047,940001 }。 散列函数为
H (k) = k - 940000
则有 H (942148) = 2148 H (941269) = 1269
H (940527) = 527 H (941630) = 1630
H (941805) = 1805 H (941558) = 1558
H (942047) = 2047 H (940001) = 1
2009-7-30 软件基础教案（第十章 查找）
（ 2）除留余数法,选择一个适当的正整数 p（通常 p取小于或等于表长的最大素数），用 p去除键值，取其余数作为散列地址，即,h(k)=k mod p
P的取法：实践证明，取小于表长的最大质数。
例,设表长 m=8,16,32,64,128
则,p=7,13,31,61,127
例：有一个关键码 key = 962148，散列表大小
m = 25，即 取质数 p= 23。散列函数 h ( k ) =
k % p。则散列地址为
h ( 962148 ) = 962148 % 23 = 12。
（ 3）数字分析法设有 n 个 d 位数，每一位可能有 r 种不同的符号。这 r
种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布均匀些；在某些位上分布不均匀，只有某几种符号经常出现。可根据散列表的大小，选取其中各种符号分布均匀的若干位作为散列地址。
计算各位数字中符号分布的均匀度?k 的公式：
其中,表示第 i 个符号在第 k 位上出现的次数,n/r
表示各种符号在 n 个数中均匀出现的期望值。计算出的?k
值越小，表明在该位 (第 k 位 )各种符号分布得越均匀。
若散列表地址范围有 3 位数字,取各关键码的④⑤⑥位做为记录的散列地址。也可以把第①，②，③和第⑤位相加，
舍去进位位，变成一位数，与第④，⑥位合起来作为散列地址。还有其它方法。
r
i
k
ik rn
1
2)/(αλ
2009-7-30 软件基础教案（第十章 查找）
9 4 2 1 4 8 ① 位,? 1 = 510.60
9 4 1 2 6 9 ② 位,? 2 = 510.60
9 4 0 5 2 7 ③ 位,? 3 = 110.60
9 4 1 6 3 0 ④ 位,? 4 = 110.60
9 4 1 8 0 5 ⑤ 位,? 5 = 110.60
9 4 1 5 5 8 ⑥ 位,? 6 = 110.60
9 4 2 0 4 7
9 4 0 0 0 1
① ② ③ ④ ⑤ ⑥
数字分析法仅适用于事先明确知道表中所有关键码每一位数值的分布情况，它完全依赖于关键码集合。如果换一个关键码集合，
选择哪几位要重新决定。
2009-7-30 软件基础教案（第十章 查找）
（ 4）折叠法
此方法把关键码自左到右分成位数相等的几部分，
每一部分的位数应与散列表地址位数相同，只有最后一部分的位数可以短一些。
把这些部分的数据叠加起来，就可以得到具有该关键码的记录的散列地址。
有两种叠加方法：
移位法 — 把各部分的最后一位对齐相加；
分界法 — 各部分不折断，沿各部分的分界来回折叠，然后对齐相加，将相加的结果当做散列地址。
2009-7-30 软件基础教案（第十章 查找）
把超出地址位数的最高位删去,仅保留最低的 3位，做为可用的散列地址。
例：设给定的关键码为 key = 23938587841，若存储空间限定 3 位,则划分结果为每段 3 位,上述关键码可划分为 4
段,239 385 878 41
2009-7-30 软件基础教案（第十章 查找）
10.4.3.哈希冲突解决方法两种处理冲突的基本方法：
拉链法、开放地址法
（ 1）拉链法 （外链法、内链法）：
外链法 ---把具有相同哈希地址的键值都存放在一个同义词链表中（称为桶），若有
m个同义词，就建 m个链表（桶）。
内链法 ---把发生冲突的所有同义词建立一个单链表。
2009-7-30 软件基础教案（第十章 查找）
例：对于 m=5,h(x)=x%5,关键值序列
={1,2,5,7,9,10}
基本区
∧
5 ∧10
1 ∧
2 7 ∧
9 ∧
key next
外链法示例
2009-7-30 软件基础教案（第十章 查找）
基本区 ---数组 t[m]存放各个链表的头指针，
其下标表示关键字为 k的记录所在的桶号。
同义词链表 ---在基本区外开辟。
结点类型描述：
type struct node
{int key;
struct node *next;
}JD;
基本运算描述：
（ 1）查找结点、
（ 2）插入结点、删除结点。
2009-7-30 软件基础教案（第十章 查找）
（ 2）开放地址法
当冲突发生时，使用某种方法在基本表中形成一个探查序列，沿着此序列逐个地址去探查，直到找到一个 开放的地址（空位置）,将发生冲突的键值放到该 地址中。
Hi(k)=(H(k)+di)mod m
(i=1,2,…,k(k?m-1))
m:表长
di,每次探测时的地址增量
di不同取值：
(1) di =1,2,3,…
(2) di =12,-12,22,-22,…
(3) di =伪随机序列
(4) di =2i-1
分类：
线性探测法再 (二次 )散列探测法伪随机再散列平方探查法
2009-7-30 软件基础教案（第十章 查找）
例：
记录集合,{R1,R2,R3,…,R8},m=10,
它们的哈希地址为：
H(k1)=2,H(k2)=2,H(k3)=3,H(k4)=3,
H(k5)=8,H(k6)=0,H(k7)=7,H(k8)=9,
用线性探测法和再散列探测法构造哈希表
2009-7-30 软件基础教案（第十章 查找）
H(k1)=2,H(k2)=2,H(k3)=3,H(k4)=3,
H(k5)=8,H(k6)=0,H(k7)=7,H(k8)=9,
线性探测法
0
1
2
3
4
5
6
7
8
9
R1
R2
R3
R4
R5
R6
R7
R8
二次探测再散列法
0
1
2
3
4
5
6
7
8
9
R1
R2
R3
R4
R5
R6
R7
R8
2009-7-30 软件基础教案（第十章 查找）
设：哈希表 A[m]
公共溢出表 O[v]
冲突时，把记录放到公共溢出表的尾部
（ 3）建立公共溢出表
2009-7-30 软件基础教案（第十章 查找）
10.4.4 哈希表的查找方法,
1) 计算哈希函数，得出哈希地址 H(ki)
2) 若 R(H(ki))=NULL 则：查找失败，退出；否则，进入
3）
3) R(H(ki)).key=key?,相等，则查找成功，退出；否则，
进入 4）
4) 不相等，用解决冲突的方法，继续查找
2009-7-30 软件基础教案（第十章 查找）
例：哈希表如下：解决冲突方法：线性探测法
0
1
2
3
4
5
6
7
8
9
R1
R2
R3
R4
R5
R6
R7
R8
查找 R4,key
H(k4)=3
R4.key? R2.key
R4.key? R3.key
查找成功
2009-7-30 软件基础教案（第十章 查找）
总结：
概念,
关键字，平均查找长度算法及算法评价,顺序查找（原理及算法）
二分查找（原理及算法）
分块查找（原理）
二叉排序树查找（原理及算法）
哈希查找（原理）
作业,10-1,10-2,10-6,10-7,10-9
