第四章 查找与排序技术
4.1 基本的查找技术查找,查找是在一个给定的数据结构中,根据给定的条件查找满足条件的结点 。
不同的数据结构采用不同的查找方法。
查找的效率直接影响数据处理的效率。
查找的结果：
查找成功,找到满足条件的结点查找失败,找不到满足条件的结点。
·可以采用从前向后查,也可采用从后向前查的方法 。
·在平均情况下,大约要与表中一半以上元素进行比较,效率较低 。 平均查找长度较大 。
·在下面两种情况下只能采取顺序查找：
a,线性表为无序表 （ 元素排列是无序的 ） ；
b,即使是有序线性表,但采用的是链式存储结构 。
4.1.1顺序查找 （ 线性查找 ）
查找过程：
对给定的一关键字 K,从线性表的一端开始,逐个进行记录的 关键字和 K的比较,直到找到关键字等于 K的记录或到达表的另一端 。
1,顺序查找 (线性表在顺序存储结构下的顺序查找 ）
数据结构：
typedef struct{
int key;
float info;
}SSTable;
每个结点包含两部分内容,Key 和 info
其他信息
0 1 2 3 4 5 6 7
（ a） 初态
40 80 30 6010 20 25
(b) K=80 (return i=4)
80 40 80 30 6010 20 25
0 1 2 3 4 5 6 7
(c) K=90 (return i=0 )
0 1 2 3 4 5 6 7
90 40 80 30 6010 20 25
顺序查找的算法：
int Search_seq(SSTable ST[ ],int n,int key)
{ int i=n;
ST[0].key=key;
while(ST[i].key!=key) i- -; /*从表尾往前查 */
return i;
}
监视哨使用了监视哨,
在查找过程中,
不用每一步都去判断是否查找结束 。
找到：返回元素在线性表中的存储位置；
未找到：返回 0。
根据上述算法可知：
查找成功时的平均查找次数为：
ASL=(1+2+3+4+……+n)/n=(n+1)/2
查找不成功时的比较次数为,n+1
则顺序查找的平均查找长度为：
ASL==((n+1)/2+n+1)/2=(n+1)3/4
顺序查找的优点,算法简单，无需排序，采用顺序和链式存储均可。
缺点,平均查找长度较大。
4.1.2 折半查找 （ 二分法查找 ）
思想,先确定待查找记录所在的范围,然后逐步缩小范围,直到找到或确认找不到该记录为止 。
前提,必须在 具有顺序存储结构的 有序表中进行 。
分三种情况：
1） 若中间项的值等于 x,则说明已查到 。
2） 若 x小于中间项的值,则在线性表的前半部分查找；
3） 若 x大于中间项的值,则在线性表的后半部分查找 。
特点：比顺序查找方法效率高 。 最坏的情况下,需要比较 log2n次 。
查找 23和 79的过程如下图,mid=(low+high)/2不进位取整
( 08,14,23,37,46,55,68,79,91 )
( 08,14,23,37,46,55,68,79,91 )
low highmid
( 08,14,23,37,46,55,68,79,91 )
low high=mid-1mid( 08,14,23,37,46,55,68,79,91 )
low=mid+1 high
mid
( 08,14,23,37,46,55,68,79,91 )
low highmid
( 08,14,23,37,46,55,68,79,91 )
low highmid
( 08,14,23,37,46,55,68,79,91 )
low high
mid
折半查找的 c语言算法程序：
int Search_Bin( SSTable ST[ ],int n,int key)
{int low,high,mid;
low=1; high=n;
while(low<=high)
{ mid=(low+high)/2;
if(ST[mid].key= = key) return (mid); /*查找成功 */
else if( key< ST[mid].key) high=mid-1; /*在前半区间继续查找 */
else low=mid+1; /*在后半区间继续查找 */
}
return (0); /*查找不成功 */
}
是顺序查找的一种改进方法,就是把被查找的表分成若干块,每块中记录的存放顺序是无序的,但 块与块之间必须按关键字有序 。 即第一块中任一记录的关键字都小于第二块中任一记录的关键字,而第二块中任一记录的关键字都小于第三块中任一记录的关键字,依此类推 。
该法要为被查找的表建立一个 索引表,索引表中的一项对应于表中的一块,索引表中含有这一块中的最大关键字 和 指向块内第一个记录位置的指针,索引表中各项 关键字有序 。
4.1.3分块查找 （ 索引顺序查找 ）
索引表
20 53 89
1 6 11
18 12 8 5 20 51 36 22 29 53 89 60 72 66 76
块中的最大关键字块内第一个记录位置的指针分块查找步骤：
1,查索引表,确定要找的记录在哪一块 。
2,在相应的块中查找 。
例：要找关键字为 22的记录 。
由索引的第一项可知,要找的记录要么在第二块中,要么不存在 。 并获取第二块中第一个记录的位置 。
18 12 8 5 20 51 36 22 29 53 89 60 72 66 76
4.3.1,基本概念 —— 哈希函数,冲突
4.3 哈希表技术主要目标：
提高查找效率 — 缩短查表和填表的时间。
基本思想：
对被查找元素的关键字做某种运算后直接确定所要查找元素在表中的位置。
哈希函数：
根据关键字直接计算出元素所在位置的函数。
3127262119161309
11
0501
02
H(K)=int(K/3)+1
121110987654321表项序号根据关键字直接计算出元素所在位置的函数。
例,设哈希函数为：
int(K/3)+1
则构造 01,02,05,09,11,13,16,19,21,26、
27,31,的散列表 (哈希表）为：
哈希函数：
冲突,两个不同的关键字具有相同的存储位置。
哈希表技术的关键 ——
处理好表中元素的冲突问题主要需要解决两方面的问题：
构造好的哈希函数,使冲突的现象尽可能少
Hash码均匀性好
Hash码的计算要尽量简单
设计有效的解决冲突的方法
4.3.2 构造哈希函数的方法
（ 1） 直接定址法 ——
取关键字或关键字的某个线性函数值为散列地址,
即 H（ K） =K 或 H（ K） =A*K+B； （ 其中 A,B为常数 ）
例,某公司一险种投保费交纳表 （ 20年 ）,
将年份作关键字,哈希函数取关键字本身,若查找第 3年应交纳的保费,只要查找表的第 3项即可 。
地址 01 02 03 …… 20
年份 1 2 3 ……,20
保费 ……,……,……,…… ……
4.3.2 构造哈希函数的方法
（ 2） 平方取中法 —— 取关键字平方后的中间几位为哈希函数 。
如,K=308,K2=94864,H（ K） =486
（ 3） 除后余数法 —— 取关键字被不大于散列表表长 m的数 p除后所得的余数为哈希函数。 即 H（ K） =K MOD p （ p?m）
4.3.3 处理冲突的方法
（ 1） 线性 Hash表 （ 开放定址法 ）
设哈希函数 H（ k） =k MOD m
（ m为表长,设 m=11)
若发生冲突,设发生冲突的地址为 p,则沿着一个探查序列逐个探查,那么,探查的地址序列为,P+1,P+2,P+3,…,m-1,0,1,…,P-1.
那么,第 i次计算冲突的散列地址为：
Hi=(H(K)+di)MOD m
(di=1,2,…,m-1,i=1,2,…,F(F<=m-1))
29
17
60
0
1
2
3
4
5
6
7
8
9
10
60
17
29
38
0
1
2
3
4
5
6
7
8
9
10
例,设 Hash函数 H(k)=k MOD 11
求,60,17,29,38在散列表中的位置。
H(60)= 60 mod 11 = 5
H(17)= 17 mod 11 = 6
H(29)= 29 mod 11 = 7
H(38)= 38 mod 11 = 5,H(38+1) mod 11 = 6
H(38+2) mod 11 = 7
H(38+3) mod 11 = 8
4.3.3 处理冲突的方法
（ 1） 线性 Hash表 （ 开放定址法 ）
按开放地址法所建的 Hash表的哈希查找算法：
# difine M 100
int h(int k) {
return (k%97);}
int SearchHase(int t[ ],int k)
{ int i,j=0;
i=h(K); /*求得哈希地址 */
while(j<M &&( t[i+j}%M!=k)&&(t[i+j)%M!=0)
j++; /*该地址有数据且与待查关键字不等时,求下一地址 */
i=(i+j)%M;
if(t(i)= =k) return (i); /*查找成功 */
else return (-1)} /*查找不成功 */
(2)链地址法解决冲突的方法,把具有相同散列地址的键值存放在同一个链表中,称为同义词链表 。
优点,插入,删除方便,缺点,占用存储空间多 。
例 一组关键字为 （ 21,14,19,58,65,32,72）
H(K)=K MOD 11
21 65 32 ∧
19 ∧
72 ∧
14 58 ∧
∧
∧
∧
∧
∧
∧
∧0
1
2
3
4
5
6
7
8
9
10
作业 1
在地址空间 0— 16的散列区中，对以下关键字序列构造两个哈希表：
（ Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)
(1) 用线性开放定址法处理冲突；
(2) 用链地址法处理。
并分别求这两个哈希表在等概率情况下查找成功的平均查找长度。
设哈希函数为 H（ x） =int（ i/2）,其中 i为关键字中第一个字母在字母表中的序号。
– 用线性开放定址法
– 字母序号从 0开始
J=9 H(J)=4
F=5 H(F)=2
M=12 H(M)=6
A=0 H(A)=0
S=18 H(S)=9
O=14 H(O)=7
N=13 H(N)=6
D=3 H(D)=1
Apr
Aug
Feb
Dec
Jan
Jun
Mar
May
Jul
Sep
Oct
Nov
0
1
2
3
4
5
6
7
8
9
10
11
12
查找次数
1
2
1
3
1
2
1
2
5
1
4
6
–平均查找长度 =(1+2+1+3+1+2+1+2+5+1+4+6)/12=29/12
算出哈希值哈希函数为 H（ x） =int（ i/2）
– 链地址法 Apr Aug
Feb
Dec
Jan Jun
Mar May
Jul
Sep
Oct
Nov
0
1
2
3
4
5
6
7
8
9
10
11
12
查找次数
1
1
1
2
1
3
1
2 3
1
2
1
(1× 7＋ 2× 3＋ 3× 2） /12=19/12
–平均查找长度字母序号从 0开始
J=9 H(J)=4
F=5 H(F)=2
M=12 H(M)=6
A=0 H(A)=0
S=18 H(S)=9
O=14 H(O)=7
N=13 H(N)=6
D=3 H(D)=1
– 字母序号从 1开始
J=10 H(J)=5
F=6 H(F)=3
M=13 H(M)=6
A=1 H(A)=0
S=19 H(S)=9
O=15 H(O)=7
N=14 H(N)=7
D=4 H(D)=2
Apr
Aug
Feb
Dec
Jan
Jun
Mar
May
Jul
Sep
Oct
Nov
0
1
2
3
4
5
6
7
8
9
10
11
12
查找次数
1
2
1
1
1
1
2
4
5
2
5
6
13–平均查找长度–=(1+2+1+1+1+1+2+4+5+2+5+6)/12=31/12
算出哈希值
– 链地址法
– 字母序号从 1开始
Apr Aug
Feb
Dec
Jan Jun
Mar May
Jul
Sep
Oct Nov
0
1
2
3
4
5
6
7
8
9
10
11
12
查找次数
1
1
1
2
1
3
1
1
2
1
(1× 7＋ 2× 4＋ 3） /12=18/12
平均查找长度
J=10 H(J)=5
F=6 H(F)=3
M=13 H(M)=6
A=1 H(A)=0
S=19 H(S)=9
O=15 H(O)=7
N=14 H(N)=7
D=4 H(D)=2
4.1 基本的查找技术查找,查找是在一个给定的数据结构中,根据给定的条件查找满足条件的结点 。
不同的数据结构采用不同的查找方法。
查找的效率直接影响数据处理的效率。
查找的结果：
查找成功,找到满足条件的结点查找失败,找不到满足条件的结点。
·可以采用从前向后查,也可采用从后向前查的方法 。
·在平均情况下,大约要与表中一半以上元素进行比较,效率较低 。 平均查找长度较大 。
·在下面两种情况下只能采取顺序查找：
a,线性表为无序表 （ 元素排列是无序的 ） ；
b,即使是有序线性表,但采用的是链式存储结构 。
4.1.1顺序查找 （ 线性查找 ）
查找过程：
对给定的一关键字 K,从线性表的一端开始,逐个进行记录的 关键字和 K的比较,直到找到关键字等于 K的记录或到达表的另一端 。
1,顺序查找 (线性表在顺序存储结构下的顺序查找 ）
数据结构：
typedef struct{
int key;
float info;
}SSTable;
每个结点包含两部分内容,Key 和 info
其他信息
0 1 2 3 4 5 6 7
（ a） 初态
40 80 30 6010 20 25
(b) K=80 (return i=4)
80 40 80 30 6010 20 25
0 1 2 3 4 5 6 7
(c) K=90 (return i=0 )
0 1 2 3 4 5 6 7
90 40 80 30 6010 20 25
顺序查找的算法：
int Search_seq(SSTable ST[ ],int n,int key)
{ int i=n;
ST[0].key=key;
while(ST[i].key!=key) i- -; /*从表尾往前查 */
return i;
}
监视哨使用了监视哨,
在查找过程中,
不用每一步都去判断是否查找结束 。
找到：返回元素在线性表中的存储位置；
未找到：返回 0。
根据上述算法可知：
查找成功时的平均查找次数为：
ASL=(1+2+3+4+……+n)/n=(n+1)/2
查找不成功时的比较次数为,n+1
则顺序查找的平均查找长度为：
ASL==((n+1)/2+n+1)/2=(n+1)3/4
顺序查找的优点,算法简单，无需排序，采用顺序和链式存储均可。
缺点,平均查找长度较大。
4.1.2 折半查找 （ 二分法查找 ）
思想,先确定待查找记录所在的范围,然后逐步缩小范围,直到找到或确认找不到该记录为止 。
前提,必须在 具有顺序存储结构的 有序表中进行 。
分三种情况：
1） 若中间项的值等于 x,则说明已查到 。
2） 若 x小于中间项的值,则在线性表的前半部分查找；
3） 若 x大于中间项的值,则在线性表的后半部分查找 。
特点：比顺序查找方法效率高 。 最坏的情况下,需要比较 log2n次 。
查找 23和 79的过程如下图,mid=(low+high)/2不进位取整
( 08,14,23,37,46,55,68,79,91 )
( 08,14,23,37,46,55,68,79,91 )
low highmid
( 08,14,23,37,46,55,68,79,91 )
low high=mid-1mid( 08,14,23,37,46,55,68,79,91 )
low=mid+1 high
mid
( 08,14,23,37,46,55,68,79,91 )
low highmid
( 08,14,23,37,46,55,68,79,91 )
low highmid
( 08,14,23,37,46,55,68,79,91 )
low high
mid
折半查找的 c语言算法程序：
int Search_Bin( SSTable ST[ ],int n,int key)
{int low,high,mid;
low=1; high=n;
while(low<=high)
{ mid=(low+high)/2;
if(ST[mid].key= = key) return (mid); /*查找成功 */
else if( key< ST[mid].key) high=mid-1; /*在前半区间继续查找 */
else low=mid+1; /*在后半区间继续查找 */
}
return (0); /*查找不成功 */
}
是顺序查找的一种改进方法,就是把被查找的表分成若干块,每块中记录的存放顺序是无序的,但 块与块之间必须按关键字有序 。 即第一块中任一记录的关键字都小于第二块中任一记录的关键字,而第二块中任一记录的关键字都小于第三块中任一记录的关键字,依此类推 。
该法要为被查找的表建立一个 索引表,索引表中的一项对应于表中的一块,索引表中含有这一块中的最大关键字 和 指向块内第一个记录位置的指针,索引表中各项 关键字有序 。
4.1.3分块查找 （ 索引顺序查找 ）
索引表
20 53 89
1 6 11
18 12 8 5 20 51 36 22 29 53 89 60 72 66 76
块中的最大关键字块内第一个记录位置的指针分块查找步骤：
1,查索引表,确定要找的记录在哪一块 。
2,在相应的块中查找 。
例：要找关键字为 22的记录 。
由索引的第一项可知,要找的记录要么在第二块中,要么不存在 。 并获取第二块中第一个记录的位置 。
18 12 8 5 20 51 36 22 29 53 89 60 72 66 76
4.3.1,基本概念 —— 哈希函数,冲突
4.3 哈希表技术主要目标：
提高查找效率 — 缩短查表和填表的时间。
基本思想：
对被查找元素的关键字做某种运算后直接确定所要查找元素在表中的位置。
哈希函数：
根据关键字直接计算出元素所在位置的函数。
3127262119161309
11
0501
02
H(K)=int(K/3)+1
121110987654321表项序号根据关键字直接计算出元素所在位置的函数。
例,设哈希函数为：
int(K/3)+1
则构造 01,02,05,09,11,13,16,19,21,26、
27,31,的散列表 (哈希表）为：
哈希函数：
冲突,两个不同的关键字具有相同的存储位置。
哈希表技术的关键 ——
处理好表中元素的冲突问题主要需要解决两方面的问题：
构造好的哈希函数,使冲突的现象尽可能少
Hash码均匀性好
Hash码的计算要尽量简单
设计有效的解决冲突的方法
4.3.2 构造哈希函数的方法
（ 1） 直接定址法 ——
取关键字或关键字的某个线性函数值为散列地址,
即 H（ K） =K 或 H（ K） =A*K+B； （ 其中 A,B为常数 ）
例,某公司一险种投保费交纳表 （ 20年 ）,
将年份作关键字,哈希函数取关键字本身,若查找第 3年应交纳的保费,只要查找表的第 3项即可 。
地址 01 02 03 …… 20
年份 1 2 3 ……,20
保费 ……,……,……,…… ……
4.3.2 构造哈希函数的方法
（ 2） 平方取中法 —— 取关键字平方后的中间几位为哈希函数 。
如,K=308,K2=94864,H（ K） =486
（ 3） 除后余数法 —— 取关键字被不大于散列表表长 m的数 p除后所得的余数为哈希函数。 即 H（ K） =K MOD p （ p?m）
4.3.3 处理冲突的方法
（ 1） 线性 Hash表 （ 开放定址法 ）
设哈希函数 H（ k） =k MOD m
（ m为表长,设 m=11)
若发生冲突,设发生冲突的地址为 p,则沿着一个探查序列逐个探查,那么,探查的地址序列为,P+1,P+2,P+3,…,m-1,0,1,…,P-1.
那么,第 i次计算冲突的散列地址为：
Hi=(H(K)+di)MOD m
(di=1,2,…,m-1,i=1,2,…,F(F<=m-1))
29
17
60
0
1
2
3
4
5
6
7
8
9
10
60
17
29
38
0
1
2
3
4
5
6
7
8
9
10
例,设 Hash函数 H(k)=k MOD 11
求,60,17,29,38在散列表中的位置。
H(60)= 60 mod 11 = 5
H(17)= 17 mod 11 = 6
H(29)= 29 mod 11 = 7
H(38)= 38 mod 11 = 5,H(38+1) mod 11 = 6
H(38+2) mod 11 = 7
H(38+3) mod 11 = 8
4.3.3 处理冲突的方法
（ 1） 线性 Hash表 （ 开放定址法 ）
按开放地址法所建的 Hash表的哈希查找算法：
# difine M 100
int h(int k) {
return (k%97);}
int SearchHase(int t[ ],int k)
{ int i,j=0;
i=h(K); /*求得哈希地址 */
while(j<M &&( t[i+j}%M!=k)&&(t[i+j)%M!=0)
j++; /*该地址有数据且与待查关键字不等时,求下一地址 */
i=(i+j)%M;
if(t(i)= =k) return (i); /*查找成功 */
else return (-1)} /*查找不成功 */
(2)链地址法解决冲突的方法,把具有相同散列地址的键值存放在同一个链表中,称为同义词链表 。
优点,插入,删除方便,缺点,占用存储空间多 。
例 一组关键字为 （ 21,14,19,58,65,32,72）
H(K)=K MOD 11
21 65 32 ∧
19 ∧
72 ∧
14 58 ∧
∧
∧
∧
∧
∧
∧
∧0
1
2
3
4
5
6
7
8
9
10
作业 1
在地址空间 0— 16的散列区中，对以下关键字序列构造两个哈希表：
（ Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)
(1) 用线性开放定址法处理冲突；
(2) 用链地址法处理。
并分别求这两个哈希表在等概率情况下查找成功的平均查找长度。
设哈希函数为 H（ x） =int（ i/2）,其中 i为关键字中第一个字母在字母表中的序号。
– 用线性开放定址法
– 字母序号从 0开始
J=9 H(J)=4
F=5 H(F)=2
M=12 H(M)=6
A=0 H(A)=0
S=18 H(S)=9
O=14 H(O)=7
N=13 H(N)=6
D=3 H(D)=1
Apr
Aug
Feb
Dec
Jan
Jun
Mar
May
Jul
Sep
Oct
Nov
0
1
2
3
4
5
6
7
8
9
10
11
12
查找次数
1
2
1
3
1
2
1
2
5
1
4
6
–平均查找长度 =(1+2+1+3+1+2+1+2+5+1+4+6)/12=29/12
算出哈希值哈希函数为 H（ x） =int（ i/2）
– 链地址法 Apr Aug
Feb
Dec
Jan Jun
Mar May
Jul
Sep
Oct
Nov
0
1
2
3
4
5
6
7
8
9
10
11
12
查找次数
1
1
1
2
1
3
1
2 3
1
2
1
(1× 7＋ 2× 3＋ 3× 2） /12=19/12
–平均查找长度字母序号从 0开始
J=9 H(J)=4
F=5 H(F)=2
M=12 H(M)=6
A=0 H(A)=0
S=18 H(S)=9
O=14 H(O)=7
N=13 H(N)=6
D=3 H(D)=1
– 字母序号从 1开始
J=10 H(J)=5
F=6 H(F)=3
M=13 H(M)=6
A=1 H(A)=0
S=19 H(S)=9
O=15 H(O)=7
N=14 H(N)=7
D=4 H(D)=2
Apr
Aug
Feb
Dec
Jan
Jun
Mar
May
Jul
Sep
Oct
Nov
0
1
2
3
4
5
6
7
8
9
10
11
12
查找次数
1
2
1
1
1
1
2
4
5
2
5
6
13–平均查找长度–=(1+2+1+1+1+1+2+4+5+2+5+6)/12=31/12
算出哈希值
– 链地址法
– 字母序号从 1开始
Apr Aug
Feb
Dec
Jan Jun
Mar May
Jul
Sep
Oct Nov
0
1
2
3
4
5
6
7
8
9
10
11
12
查找次数
1
1
1
2
1
3
1
1
2
1
(1× 7＋ 2× 4＋ 3） /12=18/12
平均查找长度
J=10 H(J)=5
F=6 H(F)=3
M=13 H(M)=6
A=1 H(A)=0
S=19 H(S)=9
O=15 H(O)=7
N=14 H(N)=7
D=4 H(D)=2
