查找PPT课件.ppt
《查找PPT课件.ppt》由会员分享,可在线阅读,更多相关《查找PPT课件.ppt(91页珍藏版)》请在咨信网上搜索。
1、查找查找v基本概念基本概念查找表:由同一类型的数据元素(或记录)构成的集合。静态查找表:只进行查询某个数据元素是否在查找表中,或检索某个数据元素的各种属性的查找表。动态查找表:在查找过程中同时插入查找表中不存在的数据元素,或从查找表中删除已存在的某个数据元素。关键字(key):是数据元素(或记录)中某个数据项的值,用它可以标识(或识别)一个数据元素。主关键字:能唯一标识一个数据元素的关键字。次关键字:用以识别若干记录的关键字。查找:就是根据给定的值,在一个表中查找出其关键字等于给定值的数据元素。若表中有这样的元素,则称查找成功,此时查找的信息为给定整个数据元素的输出或指出该元素在表中的位置;若
2、表中不存在这样的记录,则称查找不成功,或称查找失败查找方法评价v查找速度v占用存储空间多少v算法本身复杂程度v平均查找长度ASL(Average Search Length):为确定记录在表中的位置,需和给定值进行比较的关键字的个数的期望值叫查找算法的9.1 静态查找表9.1.1 顺序表的查找顺序表的查找顺序查找的基本思想顺序查找的基本思想 顺序查找是一种最简单的查找方法,它的基本思想是:从表的一端开始,顺序扫描线性表,依次将扫描到的结点关键字和待找的值相比较,若相等,则查找成功,若整个表扫描完毕,仍末找到关键字等于的元素,则查找失败。顺序查找既适用于顺序表,也适用于链表。若用顺序表,查找可从
3、前往后扫描,也可从后往前扫描,但若采用单链表,则只能从前往后扫描。另外,顺序查找的表中元素可以是无序的。i例 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92找6464监视哨iiii比较次数=5比较次数:查找第n个元素:1查找第n-1个元素:2.查找第1个元素:n查找第i个元素:n+1-i查找失败:n+1算法描述类型定义与算法实现类型定义与算法实现 typedef struct keytype key;/*关键字类型关键字类型*/elemtype other;/*其他的域其他的域*/sqlist;sqlist Rn+1;/*顺序
4、表顺序表*/顺序检索算法:顺序检索算法:int seqsrch(sqlist R ,keytype k)int i;R0.key=k;/*将将R0作为监视哨作为监视哨*/i=n;/*从第从第n个记录起向前扫描个记录起向前扫描*/while(Ri.key!=k)i-;if(i=0)return(0);else return i;/*seqsrch*/顺序查找方法的ASLn n顺序查找的缺点:顺序查找的缺点:n n平均查找长度较大,特别是当待查找集合中元素较多时,查平均查找长度较大,特别是当待查找集合中元素较多时,查平均查找长度较大,特别是当待查找集合中元素较多时,查平均查找长度较大,特别是当待查
5、找集合中元素较多时,查找效率较低。找效率较低。找效率较低。找效率较低。n n顺序查找的优点:顺序查找的优点:n n算法简单而且使用面广。算法简单而且使用面广。算法简单而且使用面广。算法简单而且使用面广。n n对表中记录的存储没有任何要求,顺序存储和链接存储均可;对表中记录的存储没有任何要求,顺序存储和链接存储均可;对表中记录的存储没有任何要求,顺序存储和链接存储均可;对表中记录的存储没有任何要求,顺序存储和链接存储均可;n n对表中记录的有序性也没有要求,无论记录是否按关键码有对表中记录的有序性也没有要求,无论记录是否按关键码有对表中记录的有序性也没有要求,无论记录是否按关键码有对表中记录的有
6、序性也没有要求,无论记录是否按关键码有序均可。序均可。序均可。序均可。9.1.2 有序表的查找有序表的查找折半查找折半查找折半查找的基本思想折半查找的基本思想 折半查找,是一种高效率的查找方法。但要求表中元素必须按关键字有序(升序或降序)。不妨假设表中元素为升序排列。折半查找的基本思想是:首先将待查值K与有序表array1到arrayn的中点mid上的关键字arraymid.key进行比较,若相等,则查找成功;否则,若arraymid.keyk ,则在array1到arraymid-1中继续查找,若有arraymid.key1418147221822low=4mid=4 21high算法实现v
7、设表长为n,low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值v初始时,令low=1,high=n,mid=(low+high)/2v让k与mid指向的记录比较l若k=rmid.key,查找成功l若krmid.key,则low=mid+1v重复上述操作,直至lowhigh时,查找失败算法描述lowhighmid例 1 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
8、 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid例 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 10 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
9、 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh折半查找算法折半查找算法int bin_search(NODE array,int n,int k)int low=1,high=n,mid;while(lowk)high=mid-1;/在在左左子子区区间间中中查查找找 else low=mid+1;/在右子区间中查找在右子区间中查找 return(0);/查找失败查找失败折半查找的性能分析折半查找的性能分析 为了分析折半查找的性能,可以用二叉树来描述折半查找过程。把当前查找区间的中点
10、作为根结点,左子区间和右子区间分别作为根的左子树和右子树,左子区间和右子区间再按类似的方法,由此得到的二叉树称为折半查找的判定树。1185210741936判定树:1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92例:n n判定树的构造方法判定树的构造方法n n 当当当当n n=0=0时,折半查找判定树为空;时,折半查找判定树为空;时,折半查找判定树为空;时,折半查找判定树为空;n n 当当当当n n0 0时,折半查找判定树的根结点是时,折半查找判定树的根结点是时,折半查找判定树的根结点是时,折半查找判定树的根结点是有序表中序号为有序表
11、中序号为有序表中序号为有序表中序号为mid=(n+1)/2mid=(n+1)/2的记录,根的记录,根的记录,根的记录,根结点的左子树是与有序表结点的左子树是与有序表结点的左子树是与有序表结点的左子树是与有序表r1 rmid1r1 rmid1相对应的折半查找判定树,根结点的右子树相对应的折半查找判定树,根结点的右子树相对应的折半查找判定树,根结点的右子树相对应的折半查找判定树,根结点的右子树是与是与是与是与rmid+1 rnrmid+1 rn相对应的折半查找判相对应的折半查找判相对应的折半查找判相对应的折半查找判定树。定树。定树。定树。11223344510111191089785667内部结点
12、内部结点外部结点外部结点3691011784512具有具有具有具有n n个结个结个结个结点的折半查找判定树的深度为点的折半查找判定树的深度为点的折半查找判定树的深度为点的折半查找判定树的深度为 查查查查找找找找成成成成功功功功:在在在在表表表表中中中中查查查查找找找找任任任任一一一一记记记记录录录录的的的的过过过过程程程程,即即即即是是是是折折折折半半半半查查查查找找找找判判判判定定定定树树树树中中中中从从从从根根根根结结结结点点点点到到到到该该该该记记记记录录录录结结结结点点点点的的的的路路路路径径径径,和和和和给给给给定定定定值值值值的比较次数等于该记录结点在树中的层数。的比较次数等于该记
13、录结点在树中的层数。的比较次数等于该记录结点在树中的层数。的比较次数等于该记录结点在树中的层数。查查查查找找找找不不不不成成成成功功功功:查查查查找找找找失失失失败败败败的的的的过过过过程程程程就就就就是是是是走走走走了了了了一一一一条条条条从从从从根根根根结结结结点点点点到到到到外外外外部部部部结结结结点点点点的的的的路路路路径径径径,和和和和给给给给定定定定值值值值进进进进行行行行的的的的关关关关键键键键码码码码的的的的比比比比较次数等于该路径上内部结点的个数。较次数等于该路径上内部结点的个数。较次数等于该路径上内部结点的个数。较次数等于该路径上内部结点的个数。1log2+n折半查找的性能
14、分析折半查找的性能分析v有n个结点的判定树的深度为log2n+1v折半查找法在查找过程中进行的比较次数最多不超过其判定树的深度v折半查找的时间复杂度为O(log2n)v折半查找的ASL 设设设设有有有有序序序序顺顺顺顺序序序序表表表表中中中中的的的的元元元元素素素素依依依依次次次次为为为为017,017,094,094,154,154,170,170,275,275,503,503,509,509,512,512,553,553,612,612,677,677,765,765,897,897,908908。试试试试画画画画出出出出对对对对其其其其进进进进行行行行折折折折半半半半搜搜搜搜索索索索
15、时时时时的的的的二二二二叉叉叉叉判判判判定定定定树树树树,并并并并计计计计算算算算搜搜搜搜索索索索成成成成功功功功的的的的平平平平均均均均搜搜搜搜索索索索长长长长度度度度和和和和搜搜搜搜索索索索不不不不成成成成功功功功的的的的平平平平均均均均搜搜搜搜索索索索长度。长度。长度。长度。练习练习 设设设设有有有有序序序序顺顺顺顺序序序序表表表表中中中中的的的的元元元元素素素素依依依依次次次次为为为为017,017,094,094,154,154,170,170,275,275,503,503,509,509,512,512,553,553,612,612,677,677,765,765,897,89
16、7,908908。试试试试画画画画出出出出对对对对其其其其进进进进行行行行折折折折半半半半搜搜搜搜索索索索时时时时的的的的二二二二叉叉叉叉判判判判定定定定树树树树,并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。练习练习 9.1.4 索引顺序表的查找索引顺序表的查找 索引顺序表查找索引顺序表查找 的思想的思想 索引顺序表查找,是顺序查找的一种改进方法,又称分块查找。具体实现如下:将一个主表分成n个子表,要求子表之间元素是
17、按关键字有序排列的,而子表中元素可以无序的,用每个子表最大关键字和指示块中第一个记录在表中位置建立索引表。typedef struct int key;NODE;typedef struct int key,pos;INDEX;例 如,给 定 关 键 字 序 列 如 下:22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53,假设n=3,即将该序列分成3个子表,每个子表有6个元素,则得到的主表和索引表如图所 示。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1822 12 13 8 9 20 33 42 44
18、 38 24 48 60 58 74 57 86 5322 48 861 7 13索引表查38 索引查找的过程是先确定待查记录所在的块,然后在块中顺序查找。假设给定k=38,则先在索引表中按顺序比较,因为22k48,则可确定38应该在第二块中,从第二块的第一个记录 array7 顺序查起.索引查找的时间复杂度是O(m+n)m是块长度,n是索引表长度。查找38分块查找方法的ASL分块检索算法分块检索算法 (1)当顺序检索索引表时:)当顺序检索索引表时:#define M 99typedef struct keytype key;int stadr;int len;indexlist;/*索引表的
19、类型定义索引表的类型定义*/indexlist IDM;/*ID为具有为具有indexlist类型的类型的R上的一个索引表上的一个索引表*/int Blocksrch(R,ID,m,k)sqlist R ;indexlist ID ;/*索引表索引表ID*/keytype k;int m;int i,j i=0;while(i IDi.key)/*顺序检索索引表顺序检索索引表*/i+;if(im-1)retutn(0)/*检索失败检索失败*/else j=Ri.stadr;/*待检索块的第一个记录的下标待检索块的第一个记录的下标*/while(j IDi.stadr+IDi.len)&(k!=
20、Rj.key)j+;/*第第i块中顺序检索给定值为块中顺序检索给定值为K的记录元素的记录元素*/if(j=IDi.stadr+IDi.len)retutn(0)/*块中检索失败块中检索失败*/else return(j);/*检索成功检索成功*/*Blocksrch*/(2)当折半检索索引表时:indexlist IDM;/*ID为具有indexlist类型的R上的一个索引表*/int Blocksrch(sqlist R,indexlist ID,int m,keytype k)int i,j,low1,low2,mid,high1,high2;low1=0;high1=m-1;/*置折半检
21、索区间的下、上界的初值*/while(low1=high1)/*在索引表中检索*/mid=(low1+high1)/2;/*求当前区间的中间位置*/if(k=IDmid.key)high1=mid-1;/*在左区间上检索*/else low1=mid+1;/*在右区间上检索*/*检索结束,low1为块号*/if(low1m)low2=IDlow1.stadr;/*块起始地址*/if(low1=m-1)high2=n-1;/*块末地址*/else high2=IDlow1+1.stadr-1;for(i=low2;ikey=k)return(p);/查找成功 else if(p-keyk)p=p
22、-lch;/进入左子树查找 else p=p-rch;/进入右子树查找 return(NULL);二叉排序树的插入二叉排序树的插入在一棵二叉排序树中插入值为在一棵二叉排序树中插入值为在一棵二叉排序树中插入值为在一棵二叉排序树中插入值为k k的结点,步骤如下:的结点,步骤如下:的结点,步骤如下:的结点,步骤如下:若二叉排序树为空,则生成值为若二叉排序树为空,则生成值为若二叉排序树为空,则生成值为若二叉排序树为空,则生成值为k k的新结点的新结点的新结点的新结点s s,同时将新结,同时将新结,同时将新结,同时将新结点点点点s s作为根结点插入。作为根结点插入。作为根结点插入。作为根结点插入。若若若
23、若k k小于根结点的值,则在根的左子树中插入值为小于根结点的值,则在根的左子树中插入值为小于根结点的值,则在根的左子树中插入值为小于根结点的值,则在根的左子树中插入值为k k的结点。的结点。的结点。的结点。若若若若k k大于根结点的值,则在根的右子树中插入值为大于根结点的值,则在根的右子树中插入值为大于根结点的值,则在根的右子树中插入值为大于根结点的值,则在根的右子树中插入值为k k的结点。的结点。的结点。的结点。若若若若k k等于根结点的值,表明二叉排序树中已有此关键字,等于根结点的值,表明二叉排序树中已有此关键字,等于根结点的值,表明二叉排序树中已有此关键字,等于根结点的值,表明二叉排序树
24、中已有此关键字,则无须插入。则无须插入。则无须插入。则无须插入。P228 P228 算法算法算法算法9.69.6。例:插入值为例:插入值为例:插入值为例:插入值为9898的结点的结点的结点的结点63559058 7098root sroot二叉排序树的构造二叉排序树的构造从空的二叉排序树开始,依次插入一个个结点从空的二叉排序树开始,依次插入一个个结点从空的二叉排序树开始,依次插入一个个结点从空的二叉排序树开始,依次插入一个个结点 。例:关键码集合为例:关键码集合为例:关键码集合为例:关键码集合为6363,9090,7070,5555,5858,二二二二叉排序树的构造过程为:叉排序树的构造过程为
25、:叉排序树的构造过程为:叉排序树的构造过程为:63559058 70n n一个无序序列可以通过构造一棵二叉排序树而一个无序序列可以通过构造一棵二叉排序树而一个无序序列可以通过构造一棵二叉排序树而一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列变成一个有序序列变成一个有序序列变成一个有序序列;n n每次插入的新结点都是二叉排序树上新的叶子每次插入的新结点都是二叉排序树上新的叶子每次插入的新结点都是二叉排序树上新的叶子每次插入的新结点都是二叉排序树上新的叶子结点结点结点结点;n n找到插入位置后,不必移动其它结点,仅需修找到插入位置后,不必移动其它结点,仅需修找到插入位置后,不必移动其它结
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 查找 PPT 课件
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精***】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精***】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。