第七章 查找.ppt
《第七章 查找.ppt》由会员分享,可在线阅读,更多相关《第七章 查找.ppt(73页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第7章 查找7.1 7.1 基本概念基本概念7.2 7.2 静态查找表静态查找表7.7.3 3 动态查找表动态查找表7.4 7.4 哈希表哈希表17.1 基本概念与术语基本概念与术语查找表查找表查找表查找表 :由同一类型的数据元素(或记录)构成的集合。由同一类型的数据元素(或记录)构成的集合。由同一类型的数据元素(或记录)构成的集合。由同一类型的数据元素(或记录)构成的集合。关键码关键码关键码关键码 :记录中某个数据项的值,可用来标识一个记录。记录中某个数据项的值,可用来标识一个记录。记录中某个数据项的值,可用来标识一个记录。记录中某个数据项的值,可用来标识一个记录。主关键码:主关键码:主关键
2、码:主关键码:可以可以可以可以唯一唯一唯一唯一标识一个记录的关键字。标识一个记录的关键字。标识一个记录的关键字。标识一个记录的关键字。次关键码:次关键码:次关键码:次关键码:识别若干记录的关键字,识别若干记录的关键字,识别若干记录的关键字,识别若干记录的关键字,不能唯一不能唯一不能唯一不能唯一确定一个记录。确定一个记录。确定一个记录。确定一个记录。27.1 基本概念与术语基本概念与术语查查查查 找:找:找:找:在查找表中查找在查找表中查找在查找表中查找在查找表中查找关键码为给定值关键码为给定值关键码为给定值关键码为给定值kxkx(特定元素特定元素特定元素特定元素)的的的的记录记录记录记录。静态
3、查找表:静态查找表:静态查找表:静态查找表:只查找,只查找,只查找,只查找,不改变表内数据元素不改变表内数据元素不改变表内数据元素不改变表内数据元素的查找表。的查找表。的查找表。的查找表。动态查找表:动态查找表:动态查找表:动态查找表:既查找,又既查找,又既查找,又既查找,又可改变表内数据元素可改变表内数据元素可改变表内数据元素可改变表内数据元素(插入或删除)。插入或删除)。插入或删除)。插入或删除)。查找成功查找成功查找成功查找成功 :若表中存在特定元素,称查找成功,应输出该记录;若表中存在特定元素,称查找成功,应输出该记录;若表中存在特定元素,称查找成功,应输出该记录;若表中存在特定元素,
4、称查找成功,应输出该记录;查找不成功查找不成功查找不成功查找不成功:否则称查找不成功(否则称查找不成功(否则称查找不成功(否则称查找不成功(应输出失败标志应输出失败标志应输出失败标志应输出失败标志)。)。)。)。3讨讨 论:论:讨论讨论1:查找的过程是怎样的?查找的过程是怎样的?给定一个值给定一个值K K,在含有在含有n n个记录的文件中进行搜索,寻找个记录的文件中进行搜索,寻找一个关键字值等于一个关键字值等于K K的记录,如找到则输出该记录,或给出其的记录,如找到则输出该记录,或给出其位置,否则输出查找不成功的信息。位置,否则输出查找不成功的信息。显然,查找涉及到三类参量:显然,查找涉及到三
5、类参量:查找对象查找对象K K(找什么);(找什么);查找范围查找范围L L(在哪找);(在哪找);K K在在L L中的位置(查找的结果)。中的位置(查找的结果)。其中其中、为输入参量,为输入参量,为输出参量,在函数中,输为输出参量,在函数中,输入参量必不可少,输出参量也可用函数返回值表示。入参量必不可少,输出参量也可用函数返回值表示。4讨论讨论2:对查找表常用的操作有对查找表常用的操作有哪些?哪些?v查询某个查询某个“特定的特定的”数据元素是否在表中;数据元素是否在表中;v查询某个查询某个“特定的特定的”数据元素的各种属性;数据元素的各种属性;v在查找表中插入一元素;在查找表中插入一元素;v
6、从查找表中删除一元素。从查找表中删除一元素。讨论讨论3:有哪些查找方法?有哪些查找方法?查找方法取决于表中数据的排列方式查找方法取决于表中数据的排列方式;针对静态查找表和动态查找表的查找方法也有所不同。针对静态查找表和动态查找表的查找方法也有所不同。查找的基本方法可以分为两大类:查找的基本方法可以分为两大类:1 1、比较式查找法、比较式查找法、比较式查找法、比较式查找法基于线性表的查找法(静态查基于线性表的查找法(静态查找表)找表)基于树的查找法(动态查找表)基于树的查找法(动态查找表)2 2、计算式查找法、计算式查找法、计算式查找法、计算式查找法 HASHHASHHASHHASH(哈希)查找
7、法(哈希)查找法(哈希)查找法(哈希)查找法5讨论讨论4:如何评估查找方法的优劣?如何评估查找方法的优劣?明确:明确:查找的过程就是将给定的查找的过程就是将给定的K K值与文件中各记录的关值与文件中各记录的关键字项进行比较的过程。所以用键字项进行比较的过程。所以用比较次数的平均值比较次数的平均值来评估来评估算法的优劣。称为算法的优劣。称为平均查找长度平均查找长度ASLASL。n n:文件记录个数;文件记录个数;P Pi i:查找第查找第i i个记录的查找概率(通常取等概率个记录的查找概率(通常取等概率,即即P Pi i=1/n=1/n);C Ci i:找到第找到第i i个记录时所经历的比较次数
8、。个记录时所经历的比较次数。物理意义:物理意义:假设每一元素被查找的概率相同,则查找每一元素假设每一元素被查找的概率相同,则查找每一元素所需的比较次数之总和再取平均,即为所需的比较次数之总和再取平均,即为ASLASL。显然,显然,ASLASL值越小,时间效率越高。值越小,时间效率越高。6针对静态查找表的查找算法主要有:针对静态查找表的查找算法主要有:7.2 静态查找表静态查找表一、一、顺序查找(线性查找)顺序查找(线性查找)二、二、折半查找(二分或对分查找)折半查找(二分或对分查找)三、三、分块查找(索引顺序查找)分块查找(索引顺序查找)7一些约定:一些约定:典型的关键字类型说明:典型的关键字
9、类型说明:typedef float KeyType;/实型实型typedef int KeyType;/整型整型typedef char *KeyType;/字符串型字符串型数据元素类型定义为:数据元素类型定义为:typedef struct KeyType key;/关键码域关键码域 ./其它域其它域ElemType;8一、顺序查找(一、顺序查找(Linear search,又称线性查找又称线性查找)顺序查找:用逐一比较的办法顺序查找关键字,是最直接的办法。顺序查找:用逐一比较的办法顺序查找关键字,是最直接的办法。顺序查找过程:顺序查找过程:从表的一端开始,用给定值与线性表中各元素的关键字
10、逐个比较,从表的一端开始,用给定值与线性表中各元素的关键字逐个比较,从表的一端开始,用给定值与线性表中各元素的关键字逐个比较,从表的一端开始,用给定值与线性表中各元素的关键字逐个比较,直到成功或失败。存储结构通常为顺序结构,也可为链式结构。直到成功或失败。存储结构通常为顺序结构,也可为链式结构。直到成功或失败。存储结构通常为顺序结构,也可为链式结构。直到成功或失败。存储结构通常为顺序结构,也可为链式结构。9顺序存储结构查找表定义如下:顺序存储结构查找表定义如下:#define MaxSize 100typedef struct ElemType dataMaxSize+1;/表元素数组表元素数
11、组表元素数组表元素数组 int length;/表长,即表中数据元素个数表长,即表中数据元素个数表长,即表中数据元素个数表长,即表中数据元素个数SqList;一、顺序查找(一、顺序查找(Linear search,又称线性查找又称线性查找)链式存储结构查找表定义如下:链式存储结构查找表定义如下:typedef struct Node ElemType data;/数值域数值域数值域数值域 struct Node*next;/指针域指针域指针域指针域NodeType;10intint SeqSearchSeqSearch (SqListSqList L,L,KeyTypeKeyType keyk
12、ey)L.data L.data0 0.key=.key=keykey;for(for(i=i=L.lengthL.length;L.dataL.data i.key i.key keykey;i i -););return return i i;算法的实现:算法的实现:将待查找的特定值将待查找的特定值keykey存入顺序表的存入顺序表的0 0号单号单元元(俗称(俗称(俗称(俗称“哨兵哨兵哨兵哨兵”),),),),并,并从后向前从后向前逐个比较。逐个比较。i 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92找找找找646464监
13、视哨监视哨iiii比较次数比较次数=5比较次数:比较次数:查找第查找第n个元素:个元素:1查找第查找第n-1个元素:个元素:2.查找第查找第1个元素:个元素:n查找第查找第i个元素:个元素:n-i+1查找失败查找失败:n+111返回特殊标志,例如返回空记录或空指针。前例中设立了返回特殊标志,例如返回空记录或空指针。前例中设立了返回特殊标志,例如返回空记录或空指针。前例中设立了返回特殊标志,例如返回空记录或空指针。前例中设立了“哨兵哨兵哨兵哨兵”,当关键字与,当关键字与,当关键字与,当关键字与L.dataL.dataL.dataL.data0 0 0 0.key.key.key.key相等则算法
14、结束,并返回相等则算法结束,并返回相等则算法结束,并返回相等则算法结束,并返回 i=0i=0i=0i=0。讨论讨论2:查找效率怎样计算?查找效率怎样计算?用平均查找长度用平均查找长度用平均查找长度用平均查找长度ASLASLASLASL衡量。衡量。衡量。衡量。讨论讨论1:查找失败怎么办?查找失败怎么办?讨论讨论3:如何计算如何计算ASL?分析:分析:查找第查找第1个元素所需的比较次数为个元素所需的比较次数为1;查找第查找第2个元素所需的比较次数为个元素所需的比较次数为2;查找第查找第n个元素所需的比较次数为个元素所需的比较次数为n;总计全部比较次数为:总计全部比较次数为:12n=(1+n)n/2
15、若求某一个元素的平均查找次数,还应当除以若求某一个元素的平均查找次数,还应当除以n(等概率),等概率),即:即:ASL(1n)/2 ,时间效率为时间效率为 O(n)12二、折半查找二、折半查找(又称(又称二分查找二分查找或或对分查找对分查找)优点:优点:算法简单,且对顺序结构或链表结构均适用。算法简单,且对顺序结构或链表结构均适用。缺点:缺点:当当n n很大时,很大时,ASL ASL 太大,时间效率太低。太大,时间效率太低。这是一种容易想到的查找方法。这是一种容易想到的查找方法。先给数据排序先给数据排序(例如按升序排好),形成(例如按升序排好),形成有序表有序表,然后再将,然后再将keykey
16、与与正中正中元素相比,若元素相比,若keykey小,则缩小至右半部内查找;再取其小,则缩小至右半部内查找;再取其中中值值比较,每次缩小比较,每次缩小1/21/2的范围,直到查找成功或失败为止。的范围,直到查找成功或失败为止。讨论讨论4:顺序查找的特点:顺序查找的特点:如何改进如何改进?13lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找找211 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 11
17、5 13 19 21 37 56 64 75 80 88 92lowhighmid例如例如 key=21 的折半查找过程的折半查找过程low 指示查找区间的下界指示查找区间的下界;high 指示查找区间的上界指示查找区间的上界;mid=(low+high)/214key=70 的查找过程的查找过程1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid找找701 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 1
18、0 115 13 19 21 37 56 64 75 80 88 92low highmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid151 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh当下界当下界lowlow大于上界大于上界highhigh时,则说明表中没有关键字等于时,则说明表中没有关键字等于keykey的元素,查找不成功。的元素,查找不成功。16 运算步骤运算步骤:(1)low=1,high=11,(1)low=1,high=11
19、,故故mid=6 mid=6,待查范围是待查范围是 1,111,11;(2)(2)若若 ST.datamid.keyST.datamid.key key keykey,说明说明keykey low,midlow,mid-1-1,则令:则令:high=mid1high=mid1;重算重算 mid mid;(4)(4)若若 ST.dataST.data mid.key mid.key=key=key,说明查找成功,元素序号说明查找成功,元素序号=mid;=mid;结束条件:结束条件:结束条件:结束条件:(1 1)查找成功)查找成功 :ST.datamid.keyST.datamid.key=key
20、=key (2 2)查找不成功查找不成功 :highlowhighlow (意即区间长度小于意即区间长度小于意即区间长度小于意即区间长度小于0 0 0 0)解:解:先设定先设定3个辅助标志个辅助标志:low,high,midlow,high,midlow,high,midlow,high,mid,折半查找举例:折半查找举例:已知如下已知如下11个元素的个元素的有序表有序表ST:(05 13 19 21 37 56 64 75 80 88 92),请查找关键字为请查找关键字为21和和85的数据元素。的数据元素。显然有:显然有:显然有:显然有:mid=(low+high)/2 171.1.设表长为
21、设表长为n n,lowlow、highhigh和和midmid分别指向待查元素所在区间分别指向待查元素所在区间的下界、上界和中点的下界、上界和中点,key key为给定值。为给定值。2.2.初始时,令初始时,令low=1,high=n,mid=low=1,high=n,mid=(low+high)/2(low+high)/2 让让keykey与与midmid指向的记录比较指向的记录比较若若key=key=ST.datamid.keyST.datamid.key,则查找成功则查找成功若若key key key ST.datamid.keyST.datamid.key,则则low=mid+1low
22、=mid+13.3.重复上述操作,直至重复上述操作,直至lowhighlowhigh时,查找失败时,查找失败。折半查找算法思想:折半查找算法思想:18折半查找算法折半查找算法int binary_search(SqList L,KeyType kx)int mid,low,high;low=1;high=L.length;/设置初始查找区间设置初始查找区间设置初始查找区间设置初始查找区间 while(low=high)mid=(low+high)/2;/得到中点得到中点得到中点得到中点 if(kx=L.datamid.key)return mid;/查找成功,返回位置查找成功,返回位置查找成功
23、,返回位置查找成功,返回位置 if(kxL.datamid.key)high=mid-1;/查找区间调整到左半区查找区间调整到左半区查找区间调整到左半区查找区间调整到左半区 else low=mid+1;/查找区间调整到右半区查找区间调整到右半区查找区间调整到右半区查找区间调整到右半区 return 0 /查找不成功,返回查找不成功,返回查找不成功,返回查找不成功,返回0 019折半查找折半查找(Binary Search)(Binary Search)含11个记录的有序表,其折半查找过程可用二叉判定树表示:1 12 23 34 45 56 67 78 89 9101011116 612121
24、515181822222525282835354646585860606710412395811比较比较1次次比较比较2次次比较比较3次次比较比较4次次ASL=(1+2+2+3+3+3+3+4+4+4+4)/11=33/11=320找到有序表中任一记录的过程就是:找到有序表中任一记录的过程就是:走了一条从根结点到与该记走了一条从根结点到与该记录对应结点的路径。录对应结点的路径。比较次数为:比较次数为:该结点在判定树上的层次数。该结点在判定树上的层次数。查找成功时查找成功时比较的关键字个数最多不超过树的深度比较的关键字个数最多不超过树的深度 d:d=log2 n +1查找不成功的过程就是:查找不
25、成功的过程就是:走了一条从根结点到走了一条从根结点到外部结点外部结点外部结点外部结点的路径。的路径。用用查找二叉树查找二叉树/判定树判定树来分析来分析ASLASL(参见教材参见教材P147P147)以以(a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11)为为例:例:a6a3a9a1a10a7a4a11a8a2a5折半查找的时间复杂度为折半查找的时间复杂度为折半查找的时间复杂度为折半查找的时间复杂度为OOOO(loglogloglog2 2 2 2n n n n)21讨论:讨论:对顺序查找除了对顺序查找除了折半折半改进法外,还有无其他改进算法?改进法外,还有无其他改进算法?三
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第七章 查找 第七
限制150内