文档介绍：第10章查找
查找的基本概念
本章小结
线性表的查找
树表的查找
哈希表查找
查找的基本概念
被查找的对象是由一组记录组成的表或文件,而每个记录则由若干个数据项组成,并假设每个记录都有一个能惟一标识该记录的关键字。
在这种条件下,查找的定义是:给定一个值k,在含有n个记录的表中找出关键字等于k的记录。若找到,则查找成功,返回该记录的信息或该记录在表中的位置;否则查找失败,返回相关的指示信息。
采用何种查找方法?
(1) 使用哪种数据结构来表示“表”,即表中记录是按何种方式组织的。
(2) 表中关键字的次序。是对无序集合查找还是对有序集合查找?
若在查找的同时对表做修改运算(如插入和删除),则相应的表称之为动态查找表,否则称之为静态查找表。
由于查找运算的主要运算是关键字的比较,所以通常把查找过程中对关键字需要执行的平均比较次数(也称为平均查找长度)作为衡量一个查找算法效率优劣的标准。平均查找长度ASL(Average Search Length)定义为:
其中,n是查找表中记录的个数。pi是查找第i个记录的概率,一般地,均认为每个记录的查找概率相等,即pi=1/n(1≤i≤n),ci是找到第i个记录所需进行的比较次数。
线性表的查找
在表的组织方式中,线性表是最简单的一种。三种在线性表上进行查找的方法:
(1) 顺序查找
(2) 二分查找
(3) 分块查找。
因为不考虑在查找的同时对表做修改,故上述三种查找操作都是在静态查找表上实现的。
查找与数据的存储结构有关,线性表有顺序和链式两种存储结构。本节只介绍以顺序表作为存储结构时实现的顺序查找算法。定义被查找的顺序表类型定义如下:
#define MAXL <表中最多记录个数>
typedef struct
{ KeyType key; /*KeyType为关键字的数据类型*/
InfoType data; /*其他数据*/
} NodeType;
typedef NodeType SeqList[MAXL]; /*顺序表类型*/
顺序查找
顺序查找是一种最简单的查找方法。
它的基本思路是:从表的一端开始,顺序扫描线性表,依次将扫描到的关键字和给定值k相比较,若当前扫描到的关键字与k相等,则查找成功;若扫描结束后,仍未找到关键字等于k的记录,则查找失败。
例如,在关键字序列为{3,9,1,5,8,10,6,7,2,4}的线性表查找关键字为6的元素。
顺序查找过程如下:
开始: 3 9 1 5 8 10 6 7 2 4
第1次比较: 3 9 1 5 8 10 6 7 2 4
i=0
第2次比较: 3 9 1 5 8 10 6 7 2 4
i=1
第3次比较: 3 9 1 5 8 10 6 7 2 4
i=2
第4次比较: 3 9 1 5 8 10 6 7 2 4
i=3
第5次比较: 3 9 1 5 8 10 6 7 2 4
i=4
第6次比较: 3 9 1 5 8 10 6 7 2 4
i=5
第7次比较: 3 9 1 5 8 10 6 7 2 4
i=6
查找成功,返回序号6
顺序查找的算法如下(在顺序表R[0..n-1]中查找关键字为k的记录,成功时返回找到的记录位置,失败时返回-1):
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;
}