软件技术基础11.pptx
《软件技术基础11.pptx》由会员分享,可在线阅读,更多相关《软件技术基础11.pptx(52页珍藏版)》请在咨信网上搜索。
1、软件技术基础软件技术基础制作主讲段景山段景山段景山检索和排序段景山段景山第五章第五章 检索检索检索的基本方法检索的基本方法段景山段景山检索检索n n5.1检索索uu检索是依据元素的关索是依据元素的关键字,在字,在结构中找构中找寻元素的方法元素的方法关关键字字:元素的:元素的标志,志,检索的依据索的依据一般情况下,关一般情况下,关键字是一个元素的唯一字是一个元素的唯一标识段景山段景山检索检索n n检索的方法与数据索的方法与数据结构的关系构的关系uu数据数据数据数据结结构决定了构决定了构决定了构决定了检检索的方法索的方法索的方法索的方法uu有有有有时为时为提高提高提高提高检检索效率,需要索效率,需
2、要索效率,需要索效率,需要对对数据数据数据数据结结构采用特殊构采用特殊构采用特殊构采用特殊的的的的实现实现方式方式方式方式uu例,按成例,按成例,按成例,按成绩检绩检索学生,索学生,索学生,索学生,检检索一个学生成索一个学生成索一个学生成索一个学生成绩递绩递增的增的增的增的表格比表格比表格比表格比杂杂乱的表格效率高乱的表格效率高乱的表格效率高乱的表格效率高n n检索效率的一般索效率的一般评价依据:价依据:uu比比比比较较次数次数次数次数最多、最少和平均比最多、最少和平均比最多、最少和平均比最多、最少和平均比较较次数次数次数次数段景山段景山检索检索 顺序检索顺序检索n n5.1 顺序序检索索 顺
3、序序查找找uu从从从从头头开始逐个开始逐个开始逐个开始逐个检检索直到找到需要的索直到找到需要的索直到找到需要的索直到找到需要的结结点点点点i=0;while(i length)if(table-ai.key=our_key)break;i=i+1;找到所需的结点找到所需的结点if(i length)return i;elseerror(“no such item”);平均查找次数平均查找次数=PiCii=1n=n+12段景山段景山检索检索 二分检索二分检索n n5.2 折半(二分)折半(二分)检索索uu方法描述:方法描述:方法描述:方法描述:元素按关元素按关元素按关元素按关键键字大小排列,每次
4、字大小排列,每次字大小排列,每次字大小排列,每次查询查查询查找范找范找范找范围围内内内内的的的的“中中中中间间位置位置位置位置”结结点。点。点。点。若若若若该结该结点不是所需,点不是所需,点不是所需,点不是所需,则缩则缩小小小小查查找范找范找范找范围为围为前半部前半部前半部前半部分或后半部分分或后半部分分或后半部分分或后半部分mm=length/2(要求元素按关键字大小排列)(要求元素按关键字大小排列)ai.key am.keyai.key am.keyaj.key am.key段景山段景山检索检索 二分检索二分检索n n算法框架算法框架uu每次将每次将每次将每次将检检索范索范索范索范围缩围缩
5、小一半,直到范小一半,直到范小一半,直到范小一半,直到范围围中中中中结结点的个点的个点的个点的个数数数数为为0 0whilewhile(L=hL amid.key amid.key )L=m+1L=m+1;else if(amid.key datamid.key=key)if(table-datamid.key=key)break;break;else if(key table-data mid.key)else if(key table-data mid.key)elseelse 检索检索 二分检索二分检索int binary_search(key,table)int binary_sear
6、ch(key,table)L=0;L=0;h=table-length 1;h=table-length 1;while()while()return mid;return mid;L=hL=hh=mid 1;h=mid 1;L=mid+1;L=mid+1;if(L =h)if(L =h)elseelse return 1;return 1;L Lh h段景山段景山n n平均平均平均平均查查找次数找次数找次数找次数检索检索 二分检索二分检索n1(1+2 2+4 3+.+2k (log 2n+1)log2(n+1)-19 97 75 51 11616 181810101 1层层层层2 2层层层层
7、3 3层层层层段景山段景山检索检索 二分检索二分检索n n无序的无序的无序的无序的线线性表必性表必性表必性表必须须 才能使用二分才能使用二分才能使用二分才能使用二分检检索索索索 n n数数数数组实现组实现的的的的顺顺序表序表序表序表 用二分用二分用二分用二分检检索索索索n n单链单链表表表表 用二分用二分用二分用二分检检索索索索n n排序二叉排序二叉排序二叉排序二叉树树 用二分用二分用二分用二分查查找找找找排序排序排序排序不适合不适合不适合不适合适合适合适合适合适合适合适合适合9 97 75 51 11616 181810101 1层层层层2 2层层层层3 3层层层层段景山段景山检索检索n n
8、顺序序检索与二分索与二分检索索uu在在在在检检索有序索有序索有序索有序线线性表性表性表性表时时,顺顺序序序序检检索效率索效率索效率索效率较较低低低低uu对对于无序于无序于无序于无序线线性表,二分性表,二分性表,二分性表,二分检检索要求必索要求必索要求必索要求必须对须对无序无序无序无序线线性性性性表先表先表先表先进进行排序行排序行排序行排序段景山段景山检索检索 分块检索分块检索n n5.3 分分块检索索uu将将将将检检索索索索对对象分象分象分象分块块,块块内无序,内无序,内无序,内无序,块间块间有序。有序。有序。有序。块块内使用内使用内使用内使用较较低效的低效的低效的低效的顺顺序序序序查查找找找
9、找块间块间通通通通过过排序可使用排序可使用排序可使用排序可使用较较高效的高效的高效的高效的查查找方法找方法找方法找方法uu可做出可做出可做出可做出块块的索引表,的索引表,的索引表,的索引表,进进一步一步一步一步针对块针对块索引表索引表索引表索引表进进行折行折行折行折半半半半检检索索索索306586x=3030 x=6565 x dataindex);p=&(table-dataindex);while(p!=NULL&p-key!=key)while(p!=NULL&p-key!=key)p=p-next;p=p-next;.段景山段景山检索检索 哈希检索哈希检索n n5.4.4 线性探性探查
10、法法uu使用数使用数使用数使用数组组存存存存储储方式方式方式方式uu存放存放存放存放时时,如果,如果,如果,如果hashhash结结果冲突,将新的表果冲突,将新的表果冲突,将新的表果冲突,将新的表项项放在下放在下放在下放在下一个空一个空一个空一个空闲闲的存的存的存的存储单储单元元元元uu检检索索索索时时当当当当发现发现当前当前当前当前hashhash地址里存放的不是需要的地址里存放的不是需要的地址里存放的不是需要的地址里存放的不是需要的元素,就从元素,就从元素,就从元素,就从下一个存下一个存下一个存下一个存储单储单元元元元开始逐个探开始逐个探开始逐个探开始逐个探查查。线线性探性探性探性探查查i
11、ndex=hash(key);index=hash(key);while(table-data index !=empty)while(table-data index !=empty)index+index+;index=hash(key);index=hash(key);while(table-dataindex-key!=key)while(table-dataindex-key!=key)index+;index+;段景山段景山n n例例 关关键字模字模6的的hash运算运算uu以关以关以关以关键键字分字分字分字分别为别为6 6,1010,1212,1818,1111,1313的的的的
12、顺顺序序序序存放元素。存放元素。存放元素。存放元素。uu查查找关找关找关找关键键字字字字为为1212,1818,1313的元素的元素的元素的元素检索检索 哈希检索哈希检索0 01 12 23 34 45 5index=hash(key);index=hash(key);while(table-data index !=empty)while(table-data index !=empty)index+index+;index=hash(key);index=hash(key);while(table-dataindex-key!=key)while(table-dataindex-key!=
13、key)index+;index+;6 612121818131310101111段景山段景山检索检索 哈希检索哈希检索n n5.4.5 开放地址法开放地址法uuH Hi i(k k)(H H(K K)d di i)mod mmod mi i:第:第:第:第i i个冲突的元素个冲突的元素个冲突的元素个冲突的元素i i 1 to n1 to nuu(1 1)di di 1,2,3,1,2,3,uu(2 2)di di 1 12 2,1 12 2,2,22 2 ,2 22 2uu(3 3)di di 伪伪随机序列随机序列随机序列随机序列uu目的:使冲突分散目的:使冲突分散目的:使冲突分散目的:使冲
14、突分散线性探测线性探测线性探测线性探测二次探测二次探测二次探测二次探测随机再散列随机再散列随机再散列随机再散列段景山段景山排序的基本方法排序的基本方法第六章第六章 排序排序段景山段景山排序排序n n6.1 排序排序uu将一将一将一将一组组元素按照它元素按照它元素按照它元素按照它们们的的的的排序排序排序排序码码的大小,的大小,的大小,的大小,递递增或增或增或增或递递减排列的运算减排列的运算减排列的运算减排列的运算排序排序排序排序码码:一般是元素的关:一般是元素的关:一般是元素的关:一般是元素的关键键字,但也可以不是字,但也可以不是字,但也可以不是字,但也可以不是关关关关键键字,不同元素排序字,不
15、同元素排序字,不同元素排序字,不同元素排序码码可以相同可以相同可以相同可以相同uu排序的方法与数据排序的方法与数据排序的方法与数据排序的方法与数据结结构的关系构的关系构的关系构的关系数据数据数据数据结结构及其构及其构及其构及其实现实现方式,将影响排序方式,将影响排序方式,将影响排序方式,将影响排序过过程中元程中元程中元程中元素比素比素比素比较时较时的方便性,和元素位置的方便性,和元素位置的方便性,和元素位置的方便性,和元素位置调调整(搬移元整(搬移元整(搬移元整(搬移元素)的方便性素)的方便性素)的方便性素)的方便性vv如:如:如:如:链链表表表表对对元素位置元素位置元素位置元素位置调调整整整
16、整带带来很大方便来很大方便来很大方便来很大方便段景山段景山排序排序n n排序算法一般的排序算法一般的评价依据价依据uu平均的比平均的比平均的比平均的比较较次数(完成一次排序所需的元素次数(完成一次排序所需的元素次数(完成一次排序所需的元素次数(完成一次排序所需的元素间间排排排排序序序序码码的比的比的比的比较较次数)次数)次数)次数)uu元素搬移的次数元素搬移的次数元素搬移的次数元素搬移的次数uu算法的算法的算法的算法的稳稳定性:定性:定性:定性:对对相同排序相同排序相同排序相同排序码码的元素之的元素之的元素之的元素之间间相相相相对对位置的位置的位置的位置的维维持持持持vv保持相保持相保持相保持
17、相对对位置不位置不位置不位置不变变稳稳定算法定算法定算法定算法vv不一定保持相不一定保持相不一定保持相不一定保持相对对位置不位置不位置不位置不稳稳定算法定算法定算法定算法1212,1010,1111,1010,15151010,1010,1111,1212,15151010,1010,1111,1212,1515段景山段景山排序排序 简单插入简单插入n n6.2 线性插入算法性插入算法 简单插入算法插入算法uu基本思想基本思想基本思想基本思想:从表取一个元素,按照排序关系插入:从表取一个元素,按照排序关系插入:从表取一个元素,按照排序关系插入:从表取一个元素,按照排序关系插入到新的排序表中。到
18、新的排序表中。到新的排序表中。到新的排序表中。uu若直接在原表中若直接在原表中若直接在原表中若直接在原表中进进行:行:行:行:将表分将表分将表分将表分为为已排序子表和未排序子表。已排序子表和未排序子表。已排序子表和未排序子表。已排序子表和未排序子表。每次从未排序子表中取出表每次从未排序子表中取出表每次从未排序子表中取出表每次从未排序子表中取出表头头元素按排序关系元素按排序关系元素按排序关系元素按排序关系插入到已排序子表中,当未排序子表插入到已排序子表中,当未排序子表插入到已排序子表中,当未排序子表插入到已排序子表中,当未排序子表为为空空空空时时,排序完成。排序完成。排序完成。排序完成。3 31
19、 14 42 2已排序子表已排序子表已排序子表已排序子表未排序子表未排序子表未排序子表未排序子表教材及教案中所有的排序教材及教案中所有的排序教材及教案中所有的排序教材及教案中所有的排序算法都是按递增顺序排序算法都是按递增顺序排序算法都是按递增顺序排序算法都是按递增顺序排序注注注注意意意意段景山段景山排序排序 简单插入简单插入n n算法分析算法分析uu算法框架算法框架算法框架算法框架逐个从未排序子表中取出元素,插入排序子表逐个从未排序子表中取出元素,插入排序子表逐个从未排序子表中取出元素,插入排序子表逐个从未排序子表中取出元素,插入排序子表的算法框架。即未排序子表不断减小,已排序的算法框架。即未
20、排序子表不断减小,已排序的算法框架。即未排序子表不断减小,已排序的算法框架。即未排序子表不断减小,已排序子表不断增加的算法框架。子表不断增加的算法框架。子表不断增加的算法框架。子表不断增加的算法框架。tailtail1 13 36 67 7171745452 2whilewhile(tail length)tail length)核心算法:将核心算法:将核心算法:将核心算法:将tailtail所指的元素按序插入到前所指的元素按序插入到前所指的元素按序插入到前所指的元素按序插入到前面已排序的子表中面已排序的子表中面已排序的子表中面已排序的子表中 tail+;tail+;tail=1;tail=1
21、;tailtail是两个子表的是两个子表的是两个子表的是两个子表的分界线分界线分界线分界线段景山段景山排序排序 简单插入简单插入uu核心算法核心算法核心算法核心算法按序插入的算法按序插入的算法按序插入的算法按序插入的算法vv从已排序子表的后部逐个向前比从已排序子表的后部逐个向前比从已排序子表的后部逐个向前比从已排序子表的后部逐个向前比对对,vv如果插入元素大于表中元素,就将表中元素如果插入元素大于表中元素,就将表中元素如果插入元素大于表中元素,就将表中元素如果插入元素大于表中元素,就将表中元素后移一格,否后移一格,否后移一格,否后移一格,否则则在表中元素后放入在表中元素后放入在表中元素后放入在
22、表中元素后放入while(j -1)while(j -1)if(temp.key dataj.key)if(temp.key dataj.key)table-dataj+1=table-dataj;table-dataj+1=table-dataj;elseelsetable-dataj+1=temp;table-dataj+1=temp;break;break;j-;j-;1 12 26 67 710106 61717temptemp段景山段景山void insert_sort(table)void insert_sort(table)tail=1;tail=1;while(tail len
23、gth)while(tail length)tail=tail+1;tail=tail+1;temp=table-datatail;temp=table-datatail;j=tail-1;j=tail-1;while(j -1)while(j -1)if(temp.key table-dataj.key)if(temp.key table-dataj.key)table-dataj+1=table-dataj;table-dataj+1=table-dataj;elseelsetable-dataj+1=temp;table-dataj+1=temp;break;break;j-;j-;接近
24、接近接近接近n(n+1)/4n(n+1)/4次搬移元素次搬移元素次搬移元素次搬移元素排序排序 简单插入简单插入段景山段景山排序排序 简单选择简单选择n n6.3 选择插入排序算法插入排序算法 简单选择算法算法uu基本思想:基本思想:基本思想:基本思想:从无序表中依次从无序表中依次从无序表中依次从无序表中依次选择选择出最小的元素,出最小的元素,出最小的元素,出最小的元素,插入在新的排序表尾插入在新的排序表尾插入在新的排序表尾插入在新的排序表尾uu若直接在原有的表中若直接在原有的表中若直接在原有的表中若直接在原有的表中进进行排序!行排序!行排序!行排序!将表分将表分将表分将表分为为已排序子表和未排
25、序子表。已排序子表和未排序子表。已排序子表和未排序子表。已排序子表和未排序子表。每次从未排序子表中每次从未排序子表中每次从未排序子表中每次从未排序子表中选选出最小的元素,与未排出最小的元素,与未排出最小的元素,与未排出最小的元素,与未排序子表的表首元素交序子表的表首元素交序子表的表首元素交序子表的表首元素交换换,同,同,同,同时时未排序子表表首未排序子表表首未排序子表表首未排序子表表首成成成成为为排序子表表尾,当未排序子表排序子表表尾,当未排序子表排序子表表尾,当未排序子表排序子表表尾,当未排序子表为为空空空空时时,排,排,排,排序完成。序完成。序完成。序完成。3 31 14 42 2已排序子
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 软件技术 基础 11
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【人****来】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【人****来】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。