第8章 查找(精品).ppt
《第8章 查找(精品).ppt》由会员分享,可在线阅读,更多相关《第8章 查找(精品).ppt(29页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、数据结构课程的内容数据结构课程的内容11 1 基本概念基本概念2 2 静态查找表静态查找表3 3 动态查找表动态查找表4 4 哈希表哈希表第第6,76,7章章 查找查找21 1 基本概念基本概念若表中存在特定元素,称查找成功,应输出该记录;若表中存在特定元素,称查找成功,应输出该记录;否则,称查找不成功(也应输出失败标志或失败位置)否则,称查找不成功(也应输出失败标志或失败位置)查找表查找表查查 找找查找成功查找成功查找不成功查找不成功静态查找静态查找动态查找动态查找关键字关键字主关键字主关键字次关键字次关键字由同一类型的数据元素(或记录)构成的集合。由同一类型的数据元素(或记录)构成的集合。
2、查询查询(Searching)特定元素特定元素是否在表中。是否在表中。只查找,不改变集合内的数据元素。只查找,不改变集合内的数据元素。既查找,又改变(增减)集合内的数据元素。既查找,又改变(增减)集合内的数据元素。记录中某个数据项的值,可用来识别一个记录记录中某个数据项的值,可用来识别一个记录 (预先确定的记录的某种标志预先确定的记录的某种标志)可以可以唯一唯一标识一个记录的关键字标识一个记录的关键字例如例如“学号学号”例如例如“女女”是一种数据结构是一种数据结构识别若干记录的关键字识别若干记录的关键字3(2)对查找表常用的操作有)对查找表常用的操作有哪些?哪些?v查询某个查询某个“特定的特定
3、的”数据元素是否在表中;数据元素是否在表中;v查询某个查询某个“特定的特定的”数据元素的各种属性;数据元素的各种属性;v在查找表中插入一元素;在查找表中插入一元素;v从查找表中删除一元素。从查找表中删除一元素。讨论:讨论:(1)查找的过程是怎样的?)查找的过程是怎样的?给定一个值给定一个值K K,在含有在含有n n个记录的文件中进行搜索,寻找个记录的文件中进行搜索,寻找一个关键字值等于一个关键字值等于K K的记录,如找到则输出该记录,否则输出的记录,如找到则输出该记录,否则输出查找不成功的信息。查找不成功的信息。“特定的特定的”=关键关键字字4typedef struct KeyType ke
4、y;/关键字域关键字域 /其它域其它域(3)有哪些查找方法?有哪些查找方法?查找方法取决于表中数据的排列方式查找方法取决于表中数据的排列方式;数据元素类型定义为:数据元素类型定义为:例如查字典例如查字典针对静态查找表和动态查找表的查找方法也有所不同针对静态查找表和动态查找表的查找方法也有所不同。5(4)如何评估查找方法的优劣?)如何评估查找方法的优劣?明确:明确:查找的过程就是将给定的查找的过程就是将给定的K K值与文件中各记录的关键字项比值与文件中各记录的关键字项比较的过程。故用比较次数的平均值来评估算法优劣。称为较的过程。故用比较次数的平均值来评估算法优劣。称为平均查找长度平均查找长度(A
5、SLASL:Average Search LengthAverage Search Length)。)。其中:其中:n n文件记录个数;文件记录个数;P Pi i查找第查找第i i个记录的概率(可取等概率个记录的概率(可取等概率,P,Pi i=1/n=1/n);C Ci i找到找到第第i i个记录时所经历的比较次数。个记录时所经历的比较次数。统计意义上的统计意义上的数学期望值数学期望值物理意义:物理意义:假设每一元素被查找的概率相同,则查找每一元假设每一元素被查找的概率相同,则查找每一元素所需的比较次数之总和再取平均,即为素所需的比较次数之总和再取平均,即为ASLASL。显然,显然,ASLAS
6、L值越小,时间效率越高。值越小,时间效率越高。6针对静态查找表的查找算法主要有:针对静态查找表的查找算法主要有:2 2 静态查找表静态查找表静态查找表的抽象数据类型参见教材静态查找表的抽象数据类型参见教材一、一、顺序查找(线性查找)顺序查找(线性查找)二、二、折半查找(二分或对分查找)折半查找(二分或对分查找)三、三、静态树表的查找静态树表的查找四、四、分块查找(索引顺序查找)分块查找(索引顺序查找)7一、顺序查找(一、顺序查找(Linear search,又称线性查找又称线性查找)(1)顺序表的机内存储结构:顺序表的机内存储结构:typedef struct ElemType *elem;/
7、表基址,表基址,0 0号单元留空。表容量为全部元素号单元留空。表容量为全部元素 int length;/表长,即表中数据元素个数表长,即表中数据元素个数 int maxsize;SSTable;顺序查找:即用逐一比较的办法顺序查找关键字,这显然是最顺序查找:即用逐一比较的办法顺序查找关键字,这显然是最直接的办法。直接的办法。v对对顺序结构顺序结构如何线性查找?如何线性查找?v对对单单链链表表结结构构如如何何线线性性查查找找?函函数数虽虽未未给给出出,但但也也很很容容易易编写;只要知道头指针编写;只要知道头指针headhead就可以就可以“顺藤摸瓜顺藤摸瓜”;v对对非线性树结构非线性树结构如何顺
8、序查找如何顺序查找?可借助各种遍历操作!可借助各种遍历操作!8(2)算法的实现:算法的实现:技巧:技巧:把待查关键字把待查关键字keykey存入表头或表尾(俗称存入表头或表尾(俗称“哨兵哨兵”),),这样可以加快执行速度。这样可以加快执行速度。例:例:若将待查找的特定值若将待查找的特定值keykey存入存入顺序表的顺序表的首部首部(如(如0 0号单元)号单元),则顺序查找的实现方案为:,则顺序查找的实现方案为:从后向前从后向前逐个比较!逐个比较!int Search_Seq(SSTable ST,KeyType key)/在顺序表在顺序表STST中,查找关键字与中,查找关键字与keykey相同
9、的元素;若成功,返回其位相同的元素;若成功,返回其位置信息,否则返回置信息,否则返回0 0 ST.elem0.key=key;/设立哨兵,可免去查找过程中每一步设立哨兵,可免去查找过程中每一步都要检测是否查找完毕。当都要检测是否查找完毕。当n1000n1000时,查找时间将减少一半。时,查找时间将减少一半。for(i=ST.length;ST.elem i.key!=key;-i );/不要用不要用for(i=n;i0;-i)for(i=n;i0;-i)或或 for(i=1;i=n;i+)for(i=1;i=n;i+)return i;/若到达若到达0 0号单元才结束循环,说明不成功,返回号单
10、元才结束循环,说明不成功,返回0 0值值(i=0)(i=0)。成功时则返回找到的那个元素的位置成功时则返回找到的那个元素的位置i i。/Search_Seq9返回特殊标志,例如返回空记录或空指针。前例中设立了返回特殊标志,例如返回空记录或空指针。前例中设立了“哨哨兵兵”,就是将关键字送入末地址,就是将关键字送入末地址ST.elemST.elem0 0.key.key使之结束并返回使之结束并返回 i=0i=0。讨论讨论 查找效率怎样计算?查找效率怎样计算?用平均查找长度用平均查找长度ASL衡量。衡量。讨论讨论 查不到怎么办?查不到怎么办?讨论讨论 如何计算如何计算ASL?分析:分析:查找第查找第
11、1个元素所需的比较次数为个元素所需的比较次数为1;查找第查找第2个元素所需的比较次数为个元素所需的比较次数为2;查找第查找第n个元素所需的比较次数为个元素所需的比较次数为n;总计全部比较次数为:总计全部比较次数为:12n=(1+n)n/2未考虑查找不成功的未考虑查找不成功的情况:查找哨兵所需情况:查找哨兵所需的比较次数为的比较次数为n+1n+1这是查找成功的情况这是查找成功的情况若求某一个元素的平均查找次数,还应当除以若求某一个元素的平均查找次数,还应当除以n(等概率),等概率),即:即:ASL(1n)/2 ,时间效率为时间效率为 O(n)10二、折半查找(又称二分查找或对分查找)二、折半查找
12、(又称二分查找或对分查找)优点:优点:算法简单,且对顺序结构或链表结构均适用。算法简单,且对顺序结构或链表结构均适用。缺点:缺点:ASL 太长,时间效率太低。太长,时间效率太低。这是一种容易想到的查找方法。这是一种容易想到的查找方法。先给数据排序先给数据排序(例如按升序排好),形成(例如按升序排好),形成有序表有序表,然后再将,然后再将keykey与正中元素相比,若与正中元素相比,若keykey小,则缩小至右半部内查找;再取其中小,则缩小至右半部内查找;再取其中值比较,每次缩小值比较,每次缩小1/21/2的范围,直到查找成功或失败为止。的范围,直到查找成功或失败为止。v对对顺序表结构顺序表结构
13、如何编程实现折半查找算法?如何编程实现折半查找算法?见下页之例见下页之例v对对单链表结构单链表结构如何折半查找?如何折半查找?无法实现!无法实现!因全部元素的定位只能从头指针因全部元素的定位只能从头指针headhead开始开始v对对非线性非线性(树树)结构结构如何折半查找?如何折半查找?可借助二叉排序树来查找(属动态查找表形式)。可借助二叉排序树来查找(属动态查找表形式)。如何改进?如何改进?讨论讨论 顺序查找的特点:顺序查找的特点:11 运算步骤运算步骤:(1)low=1,high=11,mid=6(1)low=1,high=11,mid=6,待查范围是待查范围是 1,111,11;(2)(
14、2)若若 ST.elemmid.keyST.elemmid.key key keykey,说明说明keykey low,midlow,mid-1-1,则令:则令:high=mid1high=mid1;重算重算 mid mid;(4)(4)若若 ST.elemST.elem mid.key mid.key=key=key,说明查找成功,元素序号说明查找成功,元素序号=mid;=mid;结束条件:结束条件:(1 1)查找成功)查找成功 :ST.elemmid.keyST.elemmid.key=key=key (2 2)查找不成功查找不成功 :highlowhighlow (意即区间长度小于意即区
15、间长度小于0 0)解:解:先设定先设定3个辅助标志个辅助标志:low,high,midlow,high,mid,折半查找举例:折半查找举例:LowLow指向待查元素指向待查元素所在区间的下界所在区间的下界highhigh指向待查元素所指向待查元素所在区间的上界在区间的上界midmid指向待查元素所在指向待查元素所在区间的中间位置区间的中间位置 已知如下已知如下11个元素的个元素的有序表有序表:(05 13 19 21 37 56 64 75 80 88 92),请查找关键字为请查找关键字为21 和和85的数据元素。的数据元素。显然有:显然有:mid=(low+high)/2 12讨论讨论 若关
16、键字不在表中,怎样得知和停止?若关键字不在表中,怎样得知和停止?典型标志是:当查找范围的上界典型标志是:当查找范围的上界下界时停止查找。下界时停止查找。讨论讨论 二分查找的效率(二分查找的效率(ASLASL)1次比较就查找成功的元素有次比较就查找成功的元素有1个个(20),),即即中间值;中间值;2次比较就查找成功的元素有次比较就查找成功的元素有2个个(21),),即即1/4处(或处(或3/4)处;)处;3次比较就查找成功的元素有次比较就查找成功的元素有4个个(22),),即即1/8处(或处(或3/8)处)处 4次比较就查找成功的元素有次比较就查找成功的元素有8个个(23),),即即1/16处
17、(或处(或3/16)处)处 则第则第m次比较时查找成功的元素会有次比较时查找成功的元素会有(2m-1)个个;为方便起见,假设表中全部为方便起见,假设表中全部n个元素个元素 2m-1个,个,此时就不讨论第此时就不讨论第m次次比较后还有剩余元素的情况了。比较后还有剩余元素的情况了。全部比较总次数为全部比较总次数为120221322423m2m1 推推导导过过程程13平均每个数据的查找时间还要除以平均每个数据的查找时间还要除以n,所以:所以:课堂练习课堂练习(多项选择):(多项选择):采用链式存贮结构采用链式存贮结构 记录的长度记录的长度128 采用顺序存贮结构采用顺序存贮结构 记录按关键字递增有序
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第8章 查找精品 查找 精品
限制150内