下一页
计算机软件基础
The software basic
of computer
主讲：刘志强
西安交通大学
计算机教学实验中心
第 6单元
查找
下一页
上一页
停止放映
第 2 页
教学目标
?了解有关查找的
– 基本概念
– 查找的主要算法
下一页
上一页
停止放映
第 3 页
教学要求
通过本单元的学习，了解、掌握有关
查找的：
? 基本概念
– 查找、平均查找长度
? 主要查找算法
– 顺序查找、折半查找、分块查找
– 树表查找、哈希查找
下一页
上一页
停止放映
第 4 页
本单元涉及的内容
? 第 3章
?3.1 什么是查找
?3.2 顺序表查找
?3.3 树表查找
?3.4 哈希查找
?P90~P102
下一页
上一页
停止放映
第 5 页
一、基本概念
? 查找
? 查找表
? 静态查找
? 动态查找
? 平均查找长度
下一页
上一页
停止放映
第 6 页
查找
? 查找 就是在给定的 DS中找出满足某种条件
的结点；若存在这样的结点, 查找成功；
否则, 查找失败 。
? 查找表 是一组待查数据元素的集合 。
? 静态查找 是仅仅进行查询和检索操作, 不
改变查找表中数据元素间的逻辑关系的查
找 。
? 动态查找 是除了进行查询和检索操作外, 还对查
找表进行插入, 删除操作的查找, 动态地改变查找
表中数据元素之间的逻辑关系 。
下一页
上一页
停止放映
第 7 页
平均查找长度
? 平均查找长度 （ ASL-Average Search Length）
在查找过程中, 对每个结点记录中的关键字要进行反复
比较, 以确定其位置 。 因此, 与关键字进行比较的平
均次数, 就成为平均查找长度 。 它是用来评价一个算
法好坏的一个依据 。
? 对含有 n个数据元素的查找表, 查找成功时的平均查找
长度为：
ASL = ? Pi * Ci
其中：
Pi 为查找表中第 i个数据元素的概率, 且 ? Pi = 1
Ci为查找第 i个数据元素时需比较的次数 。
显然, Ci随查找过程及 DS的不同而各异 。
i=1
n
i=1
n
下一页
上一页
停止放映
第 8 页
二、主要查找算法
?顺序查找
?折半查找
?分块查找
?树表查找
?哈希查找
下一页
上一页
停止放映
第 9 页
1、顺序查找
? 顺序查找是最简单, 最普通的查找方法 。
? 查找步骤：
– step1 从第 1个元素开始查找；
– step2 用待查关键字值与各结点 （ 记录 ） 的
关键字值逐个进行比较；若找到相等的结点,
则查找成功；否则, 查找失败 。
? 查找表的存储结构：
– 既适用于顺序存储结构
– 也适用于链式存储结构
下一页
上一页
停止放映
第 10页
顺序查找算法 3-1
seq_search(item,n,key )
int *item,n,key ;
{ int i=0 ;
while ( i < n && item[i] != key )
i++;
if (item[i]= = key )
{ printf(“查找成功 !\n”); return (i); }
else
{ printf(“查找失败 !\n”); return (-1);}
}
下一页
上一页
停止放映
第 11 页
顺序查找算法 3-2（改进算法）
? seq_search_adv(item,n,key )
int *item,n,key ;
{ int i=0 ; item[n]=key ;
while ( item[i] != key )
i++;
if ( i< n )
{ printf(“查找成功 !\n”); return (i); }
else
{ printf(“查找失败 !\n”); return (-1); }
}
注, 顺序查找算法中,执行频率最高的是 while语
句,改进后,可以节省近一半的时间 。
下一页
上一页
停止放映
第 12页
顺序查找算法主程序
#include,stdio.h”
main()
｛ int key,n,loc=0;
int a[10]={43,15,21,37,2,5,82};
printf(“Input key,n:”,&key,&n);
loc=seq_search_adv(a,n,key);
if (loc >0)
printf(“loc=%d,key=%d\n”,loc,key);
}
下一页
上一页
停止放映
第 13页
算法讨论
? 平均查找长度 ASL
在等概率的情况下,
ASL = ? Pi*Ci = ? (n-i+1) =
一般情况下,ASL ?
? 优点,
– 对结点的逻辑次序 (不必有序 )和存储结构 (顺序、链
表均可）无要求；
– 当序列中的记录, 基本有序, 或 N值较小时，是较好
的算法；
? 缺点：
– ASL较长
? 讨论：能否减少比较次数，以提高效率。例如，二分法
等。
i=1n
n
1
2
n+1
2
n
i=1
n
下一页
上一页
停止放映
第 14页
2、折半查找
? 二分查找是一种高效的查找方法 。 它可以明显减少比较次
数, 提高查找效率 。 但是, 二分查找的先决条件是查找表
中的数据元素必须有序 。
? 算法步骤：
– step1 首先确定整个查找区间的中间位置,
mid = （ left + right ） / 2
– step2 用待查关键字值与中间位置的关键字值进行比较；
? 若相等, 则查找成功；
? 若大于, 则在后半区域继续进行二分查找；
? 若小于, 则在前半区域继续进行二分查找 。
– 对确定的缩小区域再按二分公式, 重复上述步骤；
– 最后, 得到结果：
? 要么, 查找成功, 要么, 查找失败 。
? 存储结构
– 用一维数组存放 。
下一页
上一页
停止放映
第 15页
折半查找算法举例
? 对给定数列（有序） { 3,5,11,17,21,23，
28,30,32,50}，按折半查找算法，查找关键字
值为 30的数据元素。
第 1次,{ 3,5,11,17,21,23,28,30,32,50 }
mid1= （ 1+10） /2 = 5
第 2次,{ 23,28,30,32,50 }
mid2 = （ 6+10） /2 = 8
left rightmid
left rightmid
下一页
上一页
停止放映
第 16页
折半查找算法 3-3
bin_search ( item,n,key )
int *item,n,key;
{ int left,right,mid; left=0; right = n-1;
while ( left ? right )
{ num++;
mid = ( left + right )/2 ;
if ( key < item[mid]) right = mid - 1;
else if (key > item[mid]) left = mid + 1;
else{ printf (, Successful search\n”);
return mid ;
}
}
printf(, Search failure \n”);
return -1;
}
下一页
上一页
停止放映
第 17页
折半查找算法 3-3主程序
#define,stdio.h”
int num;
main( )
{ int res,key ;
int s[10]={1,2,3,4,5,6,7,8,9,10,11,12};
res=b_search(s,12,11);
printf("res=%d,num=%d\n",res,num);
}
下一页
上一页
停止放映
第 18页
算法讨论
? 优点, ASL ? log2n;即每经过一次比较,查找范围
就缩小一半。经 log2n 次计较就可以完成查找过
程。
? 缺点,因要求有序，所以对所有数据元素按大小
排序是非常费时的操作。另外，顺序存储结构的
插入、删除操作不大便利。
? 考虑：
– 能否一次比较抛弃更多的部分（即一次比较，
使查找范围缩得更小），以达到提高效率的目
的；
– 把两种方法（顺序查找和二分查找）结合起来，
来达到提高效率的目的。
下一页
上一页
停止放映
第 19页
3、分块查找
? 分块查找又称索引顺序查找, 这
是顺序查找的一种改进方法 。
? 方法描述：将 n个数据元素, 按块
有序, 划分为 m块 （ m ? n） 。 每
一块中的结点不必有序, 但块与
块之间必须, 按块有序, ；即第 1
快中任一元素的关键字都必须小
于第 2块中任一元素的关键字；而
第 2块中任一元素又都必须小于第
3块中的任一元素, …… 。 每个块
中元素不一定是有序的 。
下一页
上一页
停止放映
第 20页
分块查找算法描述
? step1 先选取各块中的最大关键字构成
一个索引表；
? step2 查找分两个部分：
– 先对索引表进行二分查找或顺序查找，
以确定待查记录在哪一块中；
– 在已确定的块中用顺序法进行查找。
下一页
上一页
停止放映
第 21页
索引表结构定义
#include "stdio.h"
typedef struct
{
int key;
int link;
} index;
下一页
上一页
停止放映
第 22页
index_seq_search.c子函数
index_seq_search(index ls[],int s[],
int m,int key,int l)
{ int i,j;
i=0;
while(i<m && key>ls[i].key)
i++;
if(i>=m)
{ printf("Searching failure\n");
return(-1);
}
else /* 否则, 查找成功处理 */
下一页
上一页
停止放映
第 23页
分块查找子函数（续）
{ j=ls[i].link;
while (key !=s[j] && (j-ls[i].link)<l) j++;
if(key==s[j])
{ printf("Successful search\n
LOC(s[%2d])=%d\n",j,s[j]);
return(j);
}
else
{ printf("Searching failure\n");
return(-1);
}
}
} /* mian() 结束 */
下一页
上一页
停止放映
第 24页
分块查找主函数
main()
{ index ls[5]={ 14,0,34,5,66,10,85,15,100,20} ;
int a[]={8,4,3,2,14,34,20,17,28,29,58,61,59,66,48,
81,80,79,83,69,89,100,96,86,87}; int i,j=0,key;
for(i=0;i<25;i++)
{ if (j==0) printf("{ ");
if (j==5) { printf(" }"); j=0; printf(" {"); }
printf("%4d",a[i]); j++;
}
printf(" } \n");
printf("Enter key,");
scanf("%d",&key);
index_seq_search(ls,a,25,key,5);
}
下一页
上一页
停止放映
第 25页
分块查找举例
? 有数列如下：
{ 22,12,13,9,8,33,42,44,38,24,48,60,58,75,47}
按, 块有序, 分三块,(22,12,13,9,8),(33,42,44,38,24),
(48,6,58,74,47)。选取每块中最大的关键字组成索引表
[22,44,74],查找关键字值为 60的元素。
? 用二分法，确定在索引表中的位置为 mid=2,key值 60与 a[2]比
较,60>a[2],取第 3个块 ;在第 3块中用顺序法查找,比较两次,就可
以找出 60的元素来。
44
22
74
22
12
13
9
8
33
42
44
38
24
48
60
58
74
47
List[1]
List[2]
List[3]
下一页
上一页
停止放映
第 26页
算法讨论
? 设索引表使用二分法，则有,ASL ? log·2（ n/S
+1） + S/2
其中,n为表长,S为块长（假设各块长度相等）。
? 优点：
插入、删除操作方便；只要找到对应的块，在块中
任意位置操作均可。
? 缺点：
索引表增加了辅助存储空间。
注,索引表在数据库系统中广泛使用。
下一页
上一页
停止放映
第 27页
4、树表（二叉排序树）查找
? 前三种查找方法各有千秋 。 二分法查
找效率高, 顺序法可以采用链表存储
结构, 操作灵活 。
但最好是既有二分法的高效率, 又有
链表灵活性的查找方法 。
? 二叉排序树实际上就是将数据元素组
织成二叉树形式, 以达到与二分法相
同的查找效率, 而又具有链表的插入,
删除操作的灵活性 。
下一页
上一页
停止放映
第 28页
二叉排序树查找（算法 3-4）
? step1 首先建立起二叉排序树 。
? step2 将待查关键字值与树根结点进行比
较, 若相等, 查找成功；
? step3 否则根据比较结果确定查找路径：
– 若小于根结点的关键字值, 则与左子树
的根结点的关键字值进行比较；
– 若大于等于根结点的关键字值, 则与右
子树的根结点的关键字值进行比较 。
? step4 重复上述步骤, 直到要么找到, 查
找成功；要么找不到, 查找失败 。
下一页
上一页
停止放映
第 29页
存储结构描述
二叉排序树结点结构：
struct tree {
char info；
struct tree *left, * right ；
}
下一页
上一页
停止放映
第 30页
struct tree *search_btree(root,key)
struct tree *root; char key;
{ if (!root)
{ printf(“Emptu btree\n”);return root; }
while(root->info!=key)
{ if(key<root->info) root=root->left;
else root=root->right;
if(root==0)
{ printf(“Search Failure\n”); break ; }
}
if (root !=0)
printf(“Successful search\n key=%c\n”,root->info);
return root ;
}
查询二叉排序树程序
下一页
上一页
停止放映
第 31页
举例
? 对数列 {10,18,3,4,9,13，
25}，生成二叉排序树如右；
查找关键字值 25。
? 25比较根结点值 10，走右路，
再与 18进行比较，走右路，最
后与 25进行比较，相等，查找
成功。比较了 3次。
? 若查找 35，则与 10,18,25
分别进行比较后仍没找到相等
元素，查找失败，也比较了三
次。
10
3
9
4
18
13 25
下一页
上一页
停止放映
第 32页
算法讨论
? 二叉排序树查找的 ASL ? log2n。 若
其平衡特性较好的话, ASL与折半查
找相同 。
? 二叉排序树是动态生成的, 其特性随
插入结点的先后次序的不同而改变,
为防止其蜕化为单枝树, 要进行平衡
化处理 。
? 二叉排序树因采用链表结构, 需要辅
助存储空间 。
下一页
上一页
停止放映
第 33页
5、哈希（ hash）查找
? 哈希查找也称为散列查找 。 它不同于前面介
绍的几种查找方法 。 上述方法都是把查找建
立在比较的基础上, 而哈希查找则是通过计
算存储地址的方法进行查找的 。
? 计算是计算机的特点之一, 因此, 建立在计
算基础上的哈希查找是一种快速查找方法 。
下一页
上一页
停止放映
第 34页
哈希查找的基本概念
? 哈希表 由哈希函数的值组成的表 。 哈希查找
是建立在哈希表的基础上, 它是线性表的一种
重要存储方式和检索方法 。 在哈希表中可以实
现对数据元素的快速检索 。
? 哈希函数 哈希表中元素是由哈希函数确定的 。
将数据元素的关键字 K作为自变量, 通过一定的
函数关系 （ 称为哈希函数 ）, 计算出的值, 即
为该元素的存储地址 。 表示为：
Addr = H（ key）
? 建立哈希函数的原则
– 均匀性 H（ key） 的值均匀分布在哈希表中；
– 简单 以提高地址计算的速度 。
下一页
上一页
停止放映
第 35页
哈希函数常用的构造方法
? 数字分析法
? 平方取中法
? 折叠法
? 除留余数法 （ 求模取余法 ）
? 直接定址法
下一页
上一页
停止放映
第 36页
数字分析法
? 当关键字的位数比存储区地址码位数多时, 可
合理选择关键字的某几位组成的哈希地址 。
? 选取的原则,尽量避免计算出的地址有冲突 。
? 举例,学校的电话号码是 7位十进制数, 学校
的程控交换机是 3000门 。 但经分析不难得出：
0XXX
226 8XXX
9XXX
前 3位是相同的, 第 4位分别为, 0,8,9”，
这样一来, 正好可以表示 3000个不同的电话号
码 。
H（ KEY） = Right（ telenum,4）
下一页
上一页
停止放映
第 37页
平方取中法
? 取关键字平方后的中间几位为哈
希地址 。 这是一种较常用的构造
哈希函数的方法 。 通常在选定哈
希函数时不知道关键字的全部情
况, 取其中的哪几位也不一定合
适, 在这种情况下, 取一个数平
方后的中间几位数作哈希地址 。
取的位数由表长决定 。
下一页
上一页
停止放映
第 38页
折叠法
? 将关键字分割成位数相同的几部分 （ 最后一部分的位数可
以不同 ）, 然后取这几部分的叠加和 （ 舍去进位 ） 作为哈
希地址 。
? 关键字位数很多, 且每一位上数字分布大致均匀时, 可采
用折叠法 。
? 举例：某资料室藏书近万册 。 采用国际标准图书编号
（ ISBN）, 每个编号 10位十进制数字 。 可用折叠法构造一
个 4位数的哈希函数 。
例如,书号为,0 - 4 4 2 - 2 0 5 8 6 - 4
5 8 6 4
4 2 2 0 H（ key） = 0088
0 4+）
1 0 0 8 8
下一页
上一页
停止放映
第 39页
除留余数法（求模取余法）
? 取关键字被某个不大于哈希表表长 m的数 p除后
所得余数为哈希地址 。
H（ key） = key MOD p
这是一种最简单, 也是最常用的构造哈希函数
的方法 。
? 举例, 32834872, 哈希表长为 4位十进制数 。
P值可取小于 9999的数, 例如, 取 5000；
H（ KEY） = 32834872 MOD 5000 = 4872
? 由经验得知,通常选 p为小于哈希表长的最大
素数 。
下一页
上一页
停止放映
第 40页
直接定址法
? 取关键字或关键字的某个线性函数值为哈希地址,
即：
H（ key） = key
H（ key） = a * key + b （ a,b为常数 ）
? 例如, 从 1~100岁的人口统计表中, 年龄作为关
键字, 哈希函数取关键字本身 。
? 再如, 解放后出生人口统计表中, 年份作为关键
字, 哈希函数取为：
H（ key） = key +（ -1948）
地址
年份
人数
01 02 42
1949 1950 1990
…..
…..
43
1991
3000 3500 2500 2300…..
下一页
上一页
停止放映
第 41页
选择哈希函数的标准
? 哈希函数计算所需要的时间
? 关键字的长度
? 哈希表的长度
? 关键字的分布情况
? 记录的查找频率
下一页
上一页
停止放映
第 42页
冲突及冲突处理
? 在哈希元素 （ 地址 ） 求解过程中, 不同关
键字值对应到同一个存储地址的现象称为
冲突 。 即关键字 K1 ? K2,但哈希函数值
H（ K1） = H（ K2） 。
? 均匀的哈希函数可以减少冲突, 但不能避
免冲突 。 发生冲突后, 必须解决；也即必
须寻找下一个可用地址 。
? 处理冲突是建立哈希表过程中不可缺少的
一部分 。
? 处理冲突有两种方法：
– 开放地址法
– 链地址法
下一页
上一页
停止放映
第 43页
处理冲突 —— 开放地址法
? 当发生地址冲突后, 求解下一个地址用
Hi =( H（ key） +di） MOD m
i=1,2,…,k(k ? m-1)
其中, H(key)为哈希函数,m为哈希表长度,di为
增量序列 。 增量序列的不同取法, 又构成不同的
开放地址法 。
? 线性探测再散列
di=1,2,…,m-1
? 二次探测再散列
di=12,-12,22,-22,…,+k2,-k2(k ? m/2)
下一页
上一页
停止放映
第 44页
处理冲突 —— 链地址法
? 当发生地址冲突后,将所有函数
值相同的记录连成一个单链表 。
下一页
上一页
停止放映
第 45页
哈希查找操作步骤
? 用给定的哈希函数构造哈希表
? 根据选择的冲突处理方法解决地
址冲突
? 在哈希表的基础上执行哈希查找
下一页
上一页
停止放映
第 46页
建立哈希表
? 建立哈希表操作步骤：
– step1 取数据元素的关键字 key,计算其
哈希函数值 （ 地址 ） 。 若该地址对应的存
储空间还没有被占用, 则将该元素存入；
否则执行 step2解决冲突 。
– step2 根据选择的冲突处理方法, 计算关
键字 key的下一个存储地址 。 若下一个存储
地址仍被占用, 则继续执行 step2,直到找
到能用的存储地址为止 。
下一页
上一页
停止放映
第 47页
举例
? 对给定数列 { 22,41,53,46,30,13,1,67 },建立哈
希表 。 表长取 9,即 [0~8]。 哈希函数设定为, H(key)
= key MOD 8,用线性探测解决冲突
Hi=(H(key)+di) MOD m,di=1,2,…,m-1。
? 取 22,计算 H（ 22） =6,该地址空, 可用；
? 取 41,计算 H（ 41） =1,该地址空, 可用；
0 1 2 3 4 5 6 7 8
22
22
0 1 2 3 4 5 6 7 8
41
比较次数,1 1
下一页
上一页
停止放映
第 48页
举例（续一）
? 取 53，计算 H（ 53） = 5，该地址空，可用；
? 取 46，计算 H（ 46） = 6，该地址冲突，用线性探测
法计算下一个可用地址 Hi=（ 6+1） MOD 8 = 7，
该地址空，可用；
2241
0 1 2 3 4 5 6 7 8
53
2241 53 46
0 1 2 3 4 5 6 7 8
比较次数,1 1 1
比较次数,1 1 1 2
下一页
上一页
停止放映
第 49页
举例（续二）
? 取 30，计算 H（ 30） = 6，该地址冲突，用线性探测
法计算下一个可用地址 Hi=（ 6+1） MOD 8 = 7，
该地址冲突，再用线性探测法计算下一个可用地址；
Hi=0，地址空，可用；
? 取 13，计算 H（ 13） = 5，依法解决冲突，得出：
2241
0 1 2 3 4 5 6 7 8
53
2241 53 46
0 1 2 3 4 5 6 7 8
比较次数,3 1 1 1 2
比较次数,3 1 6 1 1 2
4630
30 13
下一页
上一页
停止放映
第 50页
举例（续三）
? 取 1，计算 H（ 1） = 1，该地址冲突，解决冲突可得；
? 取 67，计算 H（ 67） = 3，冲突，解决冲突，得出：
2241
0 1 2 3 4 5 6 7 8
53
2241 53 46
4630
30
13
比较次数,3 1 6 3 1 1 2
1
13 1 67
比较次数,3 1 6 3 2 1 1 2
0 1 2 3 4 5 6 7 8
下一页
上一页
停止放映
第 51页
哈希查找
哈希查找的过程和建立哈希表的过程是一致的 。
设哈希表为 HST[0~M-1],哈希函数取 H（ key）,
解决冲突的方法为 R（ x）, 则哈希查找步骤为：
– Step1 对给定 k值, 计算哈希地址 Di=H（ k） ；
若 HST[i]为空, 则查找失败；若 HST[i]=k，
则查找成功；否则, 执行 step2（ 处理冲突 ） 。
– Step2 重复计算处理冲突的下一个存储地址
Dk=R （ Dk-1 ）, 直到 HST[Dk] 为空, 或
HST[Dk}=k为止 。
若 HST[Dk]=K,则查找成功, 否则查找失败 。
下一页
上一页
停止放映
第 52页
查找举例
以上述哈希表为例 。 哈希函数为 H(key)=key MOD 8,
设有数列 {22,41,53,46,30,13,1,67},用线性探测法解决
冲突,建立的哈希的表为,
平均查找长度 ASL= (3+1+6+3+2+1+1+2)=
? 查找 key = 67 比较两次找到,查找成功 ;
? 查找 key = 21 比较 8次找不到,查找失败 。
0 1 2 3 4 5 6 7 8
比较次数,3 1 6 3 2 1 1 2
2241 53 4630 13 1 67
8
1
8
19
下一页
上一页
停止放映
第 53页
链地址法处理冲突
? 以上述数列为例, 产生的哈希表为：
H(41)=H(1)=1
H(67)=3
H(530=H(13)=5
H(22)=H(46)=H(30)=6
1
2
3
4
5
6
7
41 1 ^
46
13 ^
30 ^22
^
53
^
^
^
67
下一页
上一页
停止放映
第 54页
作业、思考题
1、第 3章
思考, 第 2,3,5~7,11题
作业,第 13题
下一页
上一页
停止放映
第 55页
结束语
? 欢迎参加到中心网站, 软件基础, 课程
的学习讨论中来。
? 中心网址：
http,//ctec.xjtu.edu.cn
? 课件下载地址,
ftp,//ctec.xjtu.edu.cn
? 我的 E-mail地址,
LZQ_2668634@263.net
谢谢，再见！
计算机软件基础
The software basic
of computer
主讲：刘志强
西安交通大学
计算机教学实验中心
第 6单元
查找
下一页
上一页
停止放映
第 2 页
教学目标
?了解有关查找的
– 基本概念
– 查找的主要算法
下一页
上一页
停止放映
第 3 页
教学要求
通过本单元的学习，了解、掌握有关
查找的：
? 基本概念
– 查找、平均查找长度
? 主要查找算法
– 顺序查找、折半查找、分块查找
– 树表查找、哈希查找
下一页
上一页
停止放映
第 4 页
本单元涉及的内容
? 第 3章
?3.1 什么是查找
?3.2 顺序表查找
?3.3 树表查找
?3.4 哈希查找
?P90~P102
下一页
上一页
停止放映
第 5 页
一、基本概念
? 查找
? 查找表
? 静态查找
? 动态查找
? 平均查找长度
下一页
上一页
停止放映
第 6 页
查找
? 查找 就是在给定的 DS中找出满足某种条件
的结点；若存在这样的结点, 查找成功；
否则, 查找失败 。
? 查找表 是一组待查数据元素的集合 。
? 静态查找 是仅仅进行查询和检索操作, 不
改变查找表中数据元素间的逻辑关系的查
找 。
? 动态查找 是除了进行查询和检索操作外, 还对查
找表进行插入, 删除操作的查找, 动态地改变查找
表中数据元素之间的逻辑关系 。
下一页
上一页
停止放映
第 7 页
平均查找长度
? 平均查找长度 （ ASL-Average Search Length）
在查找过程中, 对每个结点记录中的关键字要进行反复
比较, 以确定其位置 。 因此, 与关键字进行比较的平
均次数, 就成为平均查找长度 。 它是用来评价一个算
法好坏的一个依据 。
? 对含有 n个数据元素的查找表, 查找成功时的平均查找
长度为：
ASL = ? Pi * Ci
其中：
Pi 为查找表中第 i个数据元素的概率, 且 ? Pi = 1
Ci为查找第 i个数据元素时需比较的次数 。
显然, Ci随查找过程及 DS的不同而各异 。
i=1
n
i=1
n
下一页
上一页
停止放映
第 8 页
二、主要查找算法
?顺序查找
?折半查找
?分块查找
?树表查找
?哈希查找
下一页
上一页
停止放映
第 9 页
1、顺序查找
? 顺序查找是最简单, 最普通的查找方法 。
? 查找步骤：
– step1 从第 1个元素开始查找；
– step2 用待查关键字值与各结点 （ 记录 ） 的
关键字值逐个进行比较；若找到相等的结点,
则查找成功；否则, 查找失败 。
? 查找表的存储结构：
– 既适用于顺序存储结构
– 也适用于链式存储结构
下一页
上一页
停止放映
第 10页
顺序查找算法 3-1
seq_search(item,n,key )
int *item,n,key ;
{ int i=0 ;
while ( i < n && item[i] != key )
i++;
if (item[i]= = key )
{ printf(“查找成功 !\n”); return (i); }
else
{ printf(“查找失败 !\n”); return (-1);}
}
下一页
上一页
停止放映
第 11 页
顺序查找算法 3-2（改进算法）
? seq_search_adv(item,n,key )
int *item,n,key ;
{ int i=0 ; item[n]=key ;
while ( item[i] != key )
i++;
if ( i< n )
{ printf(“查找成功 !\n”); return (i); }
else
{ printf(“查找失败 !\n”); return (-1); }
}
注, 顺序查找算法中,执行频率最高的是 while语
句,改进后,可以节省近一半的时间 。
下一页
上一页
停止放映
第 12页
顺序查找算法主程序
#include,stdio.h”
main()
｛ int key,n,loc=0;
int a[10]={43,15,21,37,2,5,82};
printf(“Input key,n:”,&key,&n);
loc=seq_search_adv(a,n,key);
if (loc >0)
printf(“loc=%d,key=%d\n”,loc,key);
}
下一页
上一页
停止放映
第 13页
算法讨论
? 平均查找长度 ASL
在等概率的情况下,
ASL = ? Pi*Ci = ? (n-i+1) =
一般情况下,ASL ?
? 优点,
– 对结点的逻辑次序 (不必有序 )和存储结构 (顺序、链
表均可）无要求；
– 当序列中的记录, 基本有序, 或 N值较小时，是较好
的算法；
? 缺点：
– ASL较长
? 讨论：能否减少比较次数，以提高效率。例如，二分法
等。
i=1n
n
1
2
n+1
2
n
i=1
n
下一页
上一页
停止放映
第 14页
2、折半查找
? 二分查找是一种高效的查找方法 。 它可以明显减少比较次
数, 提高查找效率 。 但是, 二分查找的先决条件是查找表
中的数据元素必须有序 。
? 算法步骤：
– step1 首先确定整个查找区间的中间位置,
mid = （ left + right ） / 2
– step2 用待查关键字值与中间位置的关键字值进行比较；
? 若相等, 则查找成功；
? 若大于, 则在后半区域继续进行二分查找；
? 若小于, 则在前半区域继续进行二分查找 。
– 对确定的缩小区域再按二分公式, 重复上述步骤；
– 最后, 得到结果：
? 要么, 查找成功, 要么, 查找失败 。
? 存储结构
– 用一维数组存放 。
下一页
上一页
停止放映
第 15页
折半查找算法举例
? 对给定数列（有序） { 3,5,11,17,21,23，
28,30,32,50}，按折半查找算法，查找关键字
值为 30的数据元素。
第 1次,{ 3,5,11,17,21,23,28,30,32,50 }
mid1= （ 1+10） /2 = 5
第 2次,{ 23,28,30,32,50 }
mid2 = （ 6+10） /2 = 8
left rightmid
left rightmid
下一页
上一页
停止放映
第 16页
折半查找算法 3-3
bin_search ( item,n,key )
int *item,n,key;
{ int left,right,mid; left=0; right = n-1;
while ( left ? right )
{ num++;
mid = ( left + right )/2 ;
if ( key < item[mid]) right = mid - 1;
else if (key > item[mid]) left = mid + 1;
else{ printf (, Successful search\n”);
return mid ;
}
}
printf(, Search failure \n”);
return -1;
}
下一页
上一页
停止放映
第 17页
折半查找算法 3-3主程序
#define,stdio.h”
int num;
main( )
{ int res,key ;
int s[10]={1,2,3,4,5,6,7,8,9,10,11,12};
res=b_search(s,12,11);
printf("res=%d,num=%d\n",res,num);
}
下一页
上一页
停止放映
第 18页
算法讨论
? 优点, ASL ? log2n;即每经过一次比较,查找范围
就缩小一半。经 log2n 次计较就可以完成查找过
程。
? 缺点,因要求有序，所以对所有数据元素按大小
排序是非常费时的操作。另外，顺序存储结构的
插入、删除操作不大便利。
? 考虑：
– 能否一次比较抛弃更多的部分（即一次比较，
使查找范围缩得更小），以达到提高效率的目
的；
– 把两种方法（顺序查找和二分查找）结合起来，
来达到提高效率的目的。
下一页
上一页
停止放映
第 19页
3、分块查找
? 分块查找又称索引顺序查找, 这
是顺序查找的一种改进方法 。
? 方法描述：将 n个数据元素, 按块
有序, 划分为 m块 （ m ? n） 。 每
一块中的结点不必有序, 但块与
块之间必须, 按块有序, ；即第 1
快中任一元素的关键字都必须小
于第 2块中任一元素的关键字；而
第 2块中任一元素又都必须小于第
3块中的任一元素, …… 。 每个块
中元素不一定是有序的 。
下一页
上一页
停止放映
第 20页
分块查找算法描述
? step1 先选取各块中的最大关键字构成
一个索引表；
? step2 查找分两个部分：
– 先对索引表进行二分查找或顺序查找，
以确定待查记录在哪一块中；
– 在已确定的块中用顺序法进行查找。
下一页
上一页
停止放映
第 21页
索引表结构定义
#include "stdio.h"
typedef struct
{
int key;
int link;
} index;
下一页
上一页
停止放映
第 22页
index_seq_search.c子函数
index_seq_search(index ls[],int s[],
int m,int key,int l)
{ int i,j;
i=0;
while(i<m && key>ls[i].key)
i++;
if(i>=m)
{ printf("Searching failure\n");
return(-1);
}
else /* 否则, 查找成功处理 */
下一页
上一页
停止放映
第 23页
分块查找子函数（续）
{ j=ls[i].link;
while (key !=s[j] && (j-ls[i].link)<l) j++;
if(key==s[j])
{ printf("Successful search\n
LOC(s[%2d])=%d\n",j,s[j]);
return(j);
}
else
{ printf("Searching failure\n");
return(-1);
}
}
} /* mian() 结束 */
下一页
上一页
停止放映
第 24页
分块查找主函数
main()
{ index ls[5]={ 14,0,34,5,66,10,85,15,100,20} ;
int a[]={8,4,3,2,14,34,20,17,28,29,58,61,59,66,48,
81,80,79,83,69,89,100,96,86,87}; int i,j=0,key;
for(i=0;i<25;i++)
{ if (j==0) printf("{ ");
if (j==5) { printf(" }"); j=0; printf(" {"); }
printf("%4d",a[i]); j++;
}
printf(" } \n");
printf("Enter key,");
scanf("%d",&key);
index_seq_search(ls,a,25,key,5);
}
下一页
上一页
停止放映
第 25页
分块查找举例
? 有数列如下：
{ 22,12,13,9,8,33,42,44,38,24,48,60,58,75,47}
按, 块有序, 分三块,(22,12,13,9,8),(33,42,44,38,24),
(48,6,58,74,47)。选取每块中最大的关键字组成索引表
[22,44,74],查找关键字值为 60的元素。
? 用二分法，确定在索引表中的位置为 mid=2,key值 60与 a[2]比
较,60>a[2],取第 3个块 ;在第 3块中用顺序法查找,比较两次,就可
以找出 60的元素来。
44
22
74
22
12
13
9
8
33
42
44
38
24
48
60
58
74
47
List[1]
List[2]
List[3]
下一页
上一页
停止放映
第 26页
算法讨论
? 设索引表使用二分法，则有,ASL ? log·2（ n/S
+1） + S/2
其中,n为表长,S为块长（假设各块长度相等）。
? 优点：
插入、删除操作方便；只要找到对应的块，在块中
任意位置操作均可。
? 缺点：
索引表增加了辅助存储空间。
注,索引表在数据库系统中广泛使用。
下一页
上一页
停止放映
第 27页
4、树表（二叉排序树）查找
? 前三种查找方法各有千秋 。 二分法查
找效率高, 顺序法可以采用链表存储
结构, 操作灵活 。
但最好是既有二分法的高效率, 又有
链表灵活性的查找方法 。
? 二叉排序树实际上就是将数据元素组
织成二叉树形式, 以达到与二分法相
同的查找效率, 而又具有链表的插入,
删除操作的灵活性 。
下一页
上一页
停止放映
第 28页
二叉排序树查找（算法 3-4）
? step1 首先建立起二叉排序树 。
? step2 将待查关键字值与树根结点进行比
较, 若相等, 查找成功；
? step3 否则根据比较结果确定查找路径：
– 若小于根结点的关键字值, 则与左子树
的根结点的关键字值进行比较；
– 若大于等于根结点的关键字值, 则与右
子树的根结点的关键字值进行比较 。
? step4 重复上述步骤, 直到要么找到, 查
找成功；要么找不到, 查找失败 。
下一页
上一页
停止放映
第 29页
存储结构描述
二叉排序树结点结构：
struct tree {
char info；
struct tree *left, * right ；
}
下一页
上一页
停止放映
第 30页
struct tree *search_btree(root,key)
struct tree *root; char key;
{ if (!root)
{ printf(“Emptu btree\n”);return root; }
while(root->info!=key)
{ if(key<root->info) root=root->left;
else root=root->right;
if(root==0)
{ printf(“Search Failure\n”); break ; }
}
if (root !=0)
printf(“Successful search\n key=%c\n”,root->info);
return root ;
}
查询二叉排序树程序
下一页
上一页
停止放映
第 31页
举例
? 对数列 {10,18,3,4,9,13，
25}，生成二叉排序树如右；
查找关键字值 25。
? 25比较根结点值 10，走右路，
再与 18进行比较，走右路，最
后与 25进行比较，相等，查找
成功。比较了 3次。
? 若查找 35，则与 10,18,25
分别进行比较后仍没找到相等
元素，查找失败，也比较了三
次。
10
3
9
4
18
13 25
下一页
上一页
停止放映
第 32页
算法讨论
? 二叉排序树查找的 ASL ? log2n。 若
其平衡特性较好的话, ASL与折半查
找相同 。
? 二叉排序树是动态生成的, 其特性随
插入结点的先后次序的不同而改变,
为防止其蜕化为单枝树, 要进行平衡
化处理 。
? 二叉排序树因采用链表结构, 需要辅
助存储空间 。
下一页
上一页
停止放映
第 33页
5、哈希（ hash）查找
? 哈希查找也称为散列查找 。 它不同于前面介
绍的几种查找方法 。 上述方法都是把查找建
立在比较的基础上, 而哈希查找则是通过计
算存储地址的方法进行查找的 。
? 计算是计算机的特点之一, 因此, 建立在计
算基础上的哈希查找是一种快速查找方法 。
下一页
上一页
停止放映
第 34页
哈希查找的基本概念
? 哈希表 由哈希函数的值组成的表 。 哈希查找
是建立在哈希表的基础上, 它是线性表的一种
重要存储方式和检索方法 。 在哈希表中可以实
现对数据元素的快速检索 。
? 哈希函数 哈希表中元素是由哈希函数确定的 。
将数据元素的关键字 K作为自变量, 通过一定的
函数关系 （ 称为哈希函数 ）, 计算出的值, 即
为该元素的存储地址 。 表示为：
Addr = H（ key）
? 建立哈希函数的原则
– 均匀性 H（ key） 的值均匀分布在哈希表中；
– 简单 以提高地址计算的速度 。
下一页
上一页
停止放映
第 35页
哈希函数常用的构造方法
? 数字分析法
? 平方取中法
? 折叠法
? 除留余数法 （ 求模取余法 ）
? 直接定址法
下一页
上一页
停止放映
第 36页
数字分析法
? 当关键字的位数比存储区地址码位数多时, 可
合理选择关键字的某几位组成的哈希地址 。
? 选取的原则,尽量避免计算出的地址有冲突 。
? 举例,学校的电话号码是 7位十进制数, 学校
的程控交换机是 3000门 。 但经分析不难得出：
0XXX
226 8XXX
9XXX
前 3位是相同的, 第 4位分别为, 0,8,9”，
这样一来, 正好可以表示 3000个不同的电话号
码 。
H（ KEY） = Right（ telenum,4）
下一页
上一页
停止放映
第 37页
平方取中法
? 取关键字平方后的中间几位为哈
希地址 。 这是一种较常用的构造
哈希函数的方法 。 通常在选定哈
希函数时不知道关键字的全部情
况, 取其中的哪几位也不一定合
适, 在这种情况下, 取一个数平
方后的中间几位数作哈希地址 。
取的位数由表长决定 。
下一页
上一页
停止放映
第 38页
折叠法
? 将关键字分割成位数相同的几部分 （ 最后一部分的位数可
以不同 ）, 然后取这几部分的叠加和 （ 舍去进位 ） 作为哈
希地址 。
? 关键字位数很多, 且每一位上数字分布大致均匀时, 可采
用折叠法 。
? 举例：某资料室藏书近万册 。 采用国际标准图书编号
（ ISBN）, 每个编号 10位十进制数字 。 可用折叠法构造一
个 4位数的哈希函数 。
例如,书号为,0 - 4 4 2 - 2 0 5 8 6 - 4
5 8 6 4
4 2 2 0 H（ key） = 0088
0 4+）
1 0 0 8 8
下一页
上一页
停止放映
第 39页
除留余数法（求模取余法）
? 取关键字被某个不大于哈希表表长 m的数 p除后
所得余数为哈希地址 。
H（ key） = key MOD p
这是一种最简单, 也是最常用的构造哈希函数
的方法 。
? 举例, 32834872, 哈希表长为 4位十进制数 。
P值可取小于 9999的数, 例如, 取 5000；
H（ KEY） = 32834872 MOD 5000 = 4872
? 由经验得知,通常选 p为小于哈希表长的最大
素数 。
下一页
上一页
停止放映
第 40页
直接定址法
? 取关键字或关键字的某个线性函数值为哈希地址,
即：
H（ key） = key
H（ key） = a * key + b （ a,b为常数 ）
? 例如, 从 1~100岁的人口统计表中, 年龄作为关
键字, 哈希函数取关键字本身 。
? 再如, 解放后出生人口统计表中, 年份作为关键
字, 哈希函数取为：
H（ key） = key +（ -1948）
地址
年份
人数
01 02 42
1949 1950 1990
…..
…..
43
1991
3000 3500 2500 2300…..
下一页
上一页
停止放映
第 41页
选择哈希函数的标准
? 哈希函数计算所需要的时间
? 关键字的长度
? 哈希表的长度
? 关键字的分布情况
? 记录的查找频率
下一页
上一页
停止放映
第 42页
冲突及冲突处理
? 在哈希元素 （ 地址 ） 求解过程中, 不同关
键字值对应到同一个存储地址的现象称为
冲突 。 即关键字 K1 ? K2,但哈希函数值
H（ K1） = H（ K2） 。
? 均匀的哈希函数可以减少冲突, 但不能避
免冲突 。 发生冲突后, 必须解决；也即必
须寻找下一个可用地址 。
? 处理冲突是建立哈希表过程中不可缺少的
一部分 。
? 处理冲突有两种方法：
– 开放地址法
– 链地址法
下一页
上一页
停止放映
第 43页
处理冲突 —— 开放地址法
? 当发生地址冲突后, 求解下一个地址用
Hi =( H（ key） +di） MOD m
i=1,2,…,k(k ? m-1)
其中, H(key)为哈希函数,m为哈希表长度,di为
增量序列 。 增量序列的不同取法, 又构成不同的
开放地址法 。
? 线性探测再散列
di=1,2,…,m-1
? 二次探测再散列
di=12,-12,22,-22,…,+k2,-k2(k ? m/2)
下一页
上一页
停止放映
第 44页
处理冲突 —— 链地址法
? 当发生地址冲突后,将所有函数
值相同的记录连成一个单链表 。
下一页
上一页
停止放映
第 45页
哈希查找操作步骤
? 用给定的哈希函数构造哈希表
? 根据选择的冲突处理方法解决地
址冲突
? 在哈希表的基础上执行哈希查找
下一页
上一页
停止放映
第 46页
建立哈希表
? 建立哈希表操作步骤：
– step1 取数据元素的关键字 key,计算其
哈希函数值 （ 地址 ） 。 若该地址对应的存
储空间还没有被占用, 则将该元素存入；
否则执行 step2解决冲突 。
– step2 根据选择的冲突处理方法, 计算关
键字 key的下一个存储地址 。 若下一个存储
地址仍被占用, 则继续执行 step2,直到找
到能用的存储地址为止 。
下一页
上一页
停止放映
第 47页
举例
? 对给定数列 { 22,41,53,46,30,13,1,67 },建立哈
希表 。 表长取 9,即 [0~8]。 哈希函数设定为, H(key)
= key MOD 8,用线性探测解决冲突
Hi=(H(key)+di) MOD m,di=1,2,…,m-1。
? 取 22,计算 H（ 22） =6,该地址空, 可用；
? 取 41,计算 H（ 41） =1,该地址空, 可用；
0 1 2 3 4 5 6 7 8
22
22
0 1 2 3 4 5 6 7 8
41
比较次数,1 1
下一页
上一页
停止放映
第 48页
举例（续一）
? 取 53，计算 H（ 53） = 5，该地址空，可用；
? 取 46，计算 H（ 46） = 6，该地址冲突，用线性探测
法计算下一个可用地址 Hi=（ 6+1） MOD 8 = 7，
该地址空，可用；
2241
0 1 2 3 4 5 6 7 8
53
2241 53 46
0 1 2 3 4 5 6 7 8
比较次数,1 1 1
比较次数,1 1 1 2
下一页
上一页
停止放映
第 49页
举例（续二）
? 取 30，计算 H（ 30） = 6，该地址冲突，用线性探测
法计算下一个可用地址 Hi=（ 6+1） MOD 8 = 7，
该地址冲突，再用线性探测法计算下一个可用地址；
Hi=0，地址空，可用；
? 取 13，计算 H（ 13） = 5，依法解决冲突，得出：
2241
0 1 2 3 4 5 6 7 8
53
2241 53 46
0 1 2 3 4 5 6 7 8
比较次数,3 1 1 1 2
比较次数,3 1 6 1 1 2
4630
30 13
下一页
上一页
停止放映
第 50页
举例（续三）
? 取 1，计算 H（ 1） = 1，该地址冲突，解决冲突可得；
? 取 67，计算 H（ 67） = 3，冲突，解决冲突，得出：
2241
0 1 2 3 4 5 6 7 8
53
2241 53 46
4630
30
13
比较次数,3 1 6 3 1 1 2
1
13 1 67
比较次数,3 1 6 3 2 1 1 2
0 1 2 3 4 5 6 7 8
下一页
上一页
停止放映
第 51页
哈希查找
哈希查找的过程和建立哈希表的过程是一致的 。
设哈希表为 HST[0~M-1],哈希函数取 H（ key）,
解决冲突的方法为 R（ x）, 则哈希查找步骤为：
– Step1 对给定 k值, 计算哈希地址 Di=H（ k） ；
若 HST[i]为空, 则查找失败；若 HST[i]=k，
则查找成功；否则, 执行 step2（ 处理冲突 ） 。
– Step2 重复计算处理冲突的下一个存储地址
Dk=R （ Dk-1 ）, 直到 HST[Dk] 为空, 或
HST[Dk}=k为止 。
若 HST[Dk]=K,则查找成功, 否则查找失败 。
下一页
上一页
停止放映
第 52页
查找举例
以上述哈希表为例 。 哈希函数为 H(key)=key MOD 8,
设有数列 {22,41,53,46,30,13,1,67},用线性探测法解决
冲突,建立的哈希的表为,
平均查找长度 ASL= (3+1+6+3+2+1+1+2)=
? 查找 key = 67 比较两次找到,查找成功 ;
? 查找 key = 21 比较 8次找不到,查找失败 。
0 1 2 3 4 5 6 7 8
比较次数,3 1 6 3 2 1 1 2
2241 53 4630 13 1 67
8
1
8
19
下一页
上一页
停止放映
第 53页
链地址法处理冲突
? 以上述数列为例, 产生的哈希表为：
H(41)=H(1)=1
H(67)=3
H(530=H(13)=5
H(22)=H(46)=H(30)=6
1
2
3
4
5
6
7
41 1 ^
46
13 ^
30 ^22
^
53
^
^
^
67
下一页
上一页
停止放映
第 54页
作业、思考题
1、第 3章
思考, 第 2,3,5~7,11题
作业,第 13题
下一页
上一页
停止放映
第 55页
结束语
? 欢迎参加到中心网站, 软件基础, 课程
的学习讨论中来。
? 中心网址：
http,//ctec.xjtu.edu.cn
? 课件下载地址,
ftp,//ctec.xjtu.edu.cn
? 我的 E-mail地址,
LZQ_2668634@263.net
谢谢，再见！
