文档介绍：第9章查找
本章主题:表的查找
教学目的:掌握各种不同的查找表的查找算法和性能分析
教学重点:线性表的查找、树表的查找和哈希表的查找以及
各种查找的性能分析
教学难点:树表的查找
2017/12/5
1
本章学习导读
查找就是在数据集中找出一个“特定元素”。在软件设计中,通常是将待查找的数据元素集按照一定的存储结构存入计算机中,变为计算机可处理的数据结构,从而构成一种新的数据结构—查找表。
基本概念
本章主要系统地讨论了各种查找方法。主要包括线性表的查找、树表的查找和哈希表的查找以及各种查找的性能分析等。通过本章学习,读者应该熟练掌握以下内容:
了解查找及查找表的相关概念
掌握各种不同的查找表的查找算法和性能分析
掌握哈希表的各种构造方法、冲突处理和性能分析
2017/12/5
2
查找表是记录的集合,每个记录至少包含一个关键字。所谓查找就是根据给定的关键字值,在查找表中找出一个记录,该记录的关键字值等于给定的值。
若在查找的同时对表做修改运算(如插入和删除),则相应的表称之为动态查找表,否则称之为静态查找表。
由于查找表的范围和给定的关键字值的不同,查找有两种可能的结果:一种是找到了相应的记录,称为查找成功。通常要求返回该记录的存储位置,以便对该记录作进一步处理;一种是找不到相应的记录,称为查找失败。此时应返回一个能表示查找失败的值。
采用何种查找方法,取决于使用哪种数据结构来表示“表”。即表中记录是按何种方式组织的,根据不同的数据结构采用不同的查找方法。
2017/12/5
3
查找算法中的基本运算是记录的关键字与给定值所进行的比较。其执行时间通常取决于关键字的比较次数,也称为平均查找长度。比较次数的多少就是相应算法的时间复杂度,它是衡量一个查找算法优劣的重要指标。平均查找长度ASL定义为:
n 是查找表中记录的个数
Pi 是查找第i个记录的概率
Ci 是找到第i个记录所需进行的比较次数。
2017/12/5
4
顺序表的静态查找
定义被查找的顺序表类型定义如下:
#define MAXLEN <表中最多记录个数>
typedef struct{
KeyType key; //KeyType为关键字的数据类型
infoType data; //其他数据
}SeqList;
在顺序表中的查找,根据元素之间是否具有递增(减)特性又可分为三种情况:简单顺序查找、二分查找和分块有序查找。各种情况的查找方法及其性能存在较大差异。
2017/12/5
5
简单顺序查找
基本思想是:从表的一端开始,逐个把每条记录的关键字值与给定值k进行比较。若某个记录关键字值与给定值k相等,则查找成功,返回找到的记录位置。反之,若已查找到表的另一端,仍未找到关键字值与给定值相等的记录,则查找不成功,返回-1。
Typedef int KeyType;
int SeqSearch(SeqList A[],int n,KeyType k)
{ int i; int find=0;
for(i=0;i<n;i++)
if(A[i].key==k) { find=1;break;}
return (find?i:-1);}
2017/12/5
6
算法分析
从顺序查找过程可见(不考虑越界比较),顺序查找不论给定值k为何,若第1个记录符合给定值,只要比较1次。若第n个记录符合给定值,要比较n次,即ci=i。若每个记录的查找概率相等,且每次查找都是成功的。则在等概率的情况下,顺序查找的平均查找长度为:
查找成功时的平均比较次数约为表长的一半。若k值不在表中,则须进行n+1次比较之后才能确定查找失败。顺序查找算法的时间复杂性为O(n)。
2017/12/5
7
二分查找
二分查找的基本思想是:首先确定待查记录所在的范围(区域)。假设用变量low和high分别表示当前查找区域的首尾下标。将待查关键字k和该区域的中间元素,其下标为mid=(low+high)/2的关键字进行比较。比较的结果有如下三种情况:
(1)k==A[mid].key:查找成功,返回mid的值。
(2)k<A[mid].key:则由表的有序性可知,若表中存在关键字等于k的记录,则该记录必定是在位置mid左边的区域(下标从low到mid-1)中。因此应在此区域继续取中间位置记录的关键字进行比较。
(3)k>A[mid].key:说明元素只可能在右边区域(下标从mid+1到high)。因此应在此区域继续取中间位置记录的关键字进行比较。
2017/12/5
8
int BinSearch(SeqList A[],int n,KeyType k)
{ int low=