版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、数据结构实验报告三题目:试编写利用折半查找确定记录所在块的分块查找算法。提示:读入各记录建立主表;按L个记录/块建立索引表;对给定关键字k进行查找;测试实例:设主表关键字序列:12221382833384287765063991019796,L=4,依次查找K=13,K=86,K=88算法思路题意要求对输入的关键字序列先进行分块,得到分块序列。由于序列不一定有序,故对分块序列进行折半查找,找到关键字所在的块,然后对关键字所在的块进行顺序查找,从而找到关键字的位置。故需要折半查找和顺序查找两个函数,考虑用C+中的类函数实现。因为序列一般是用数组进行存储的,这样可以调用不同类型的数组,程序的可适用
2、性更大一些。折半查找函数:ints,d,ss,dd;声明一些全局变量,方便函数与主函数之间的变量调用。templateintBinSearch(TA,intlow,inthigh,Tkey)/递归实现折半查找intmid;/初始化中间值的位置Tmidvalue;/初始化中间值if(lowhigh)s=Ahigh;d=Alow;ss=high;dd=low;return-1;/如果low的值大于high的值,输出-1,并且将此时的low与high的值存储。elsemid=(low+high)/2;/中间位置为低位与高位和的一半取整。midvalue=Amid;if(midvalue=key)re
3、turnmid;elseif(midvaluekey)/如果关键字的值大于中间值returnBinSearch(A,mid+1,high,key);/递归调用函数,搜索下半部分elsereturnBinSearch(A,low,mid-1,key);/否则递归调用哦个函数,搜索上半部分以上为通用的折半查找的函数代码,这里引入了几个全局变量,主要是方便在搜索关键字在哪一个分块中时,作为判断条件。顺寻查找函数:templateintshuxuSearch(TA,inthigh,Tkey)/顺序查找inti=0;Ahigh=key;初始化i,使A的最高位为key值while(Ai!=key)i+;r
4、eturni;如果A中有key值,则在i不到n+1时就会输出,否则,返回high值,说明搜索失败。主函数中,首先对所需要的参数变量进行初始化,由键盘输入关键字,分块的多少,每一块有多少个关键字。为了用户的人性化考虑,这里由用户自己决定分块的多少和数目。为了实现这一功能,引入了一个动态存储的二维数组:int*p2;p2=newint*row;/声明一个二维数组for(i=0;irow;i+)p2i=newintcol;for(i=0;irow;i+)for(j=0;jBi;j+)p2ij=Ak;k=k+1;/将所有关键字,按块的不同存入二维数组中coutvv分块情况为endl;for(i=0;i
5、row;i+)for(j=0;jBi;j+)coutp2ij=Mi)Mi=p2ij;coutendl;/输出二维数组,检验分块是否为预期将各种信息用各种数组加以存储,在需要时不断调用。另外,由于题目中需要多次查找,为了避免每次查找的反复输入,引入了一个while循环,保证可以多次查找并输出结果。在关键字等信息输入完毕后,进行查找,可以得到该关键字所在块的序号,以及该关键字在整个关键字序列中的位置。程序结构输入每个分块中的关键字的个数调用顺序查找函数,对关键字所判断函数返回至是否等于输入数组长YES输出位置输出无该关键字YES.询问用户是否再次查找”1源代码:#includeusingnames
6、pacestd;ints,d,ss,dd;声明一些全局变量,方便函数与主函数之间的变量调用。templateintBinSearch(TA,intlow,inthigh,Tkey)/递归实现折半查找intmid;/初始化中间值的位置Tmidvalue;/初始化中间值if(lowhigh)s=Ahigh;d=Alow;ss=high;dd=low;return-1;/如果low的值大于high的值,输出-1,并且将此时的low与high的值存储。elsemid=(low+high)/2;/中间位置为低位与高位和的一半取整。midvalue=Amid;if(midvalue=key)returnm
7、id;elseif(midvaluekey)/如果关键字的值大于中间值returnBinSearch(A,mid+1,high,key);/递归调用函数,搜索下半部分elsereturnBinSearch(A,low,mid-1,key);/否则递归调用哦个函数,搜索上半部分templateintshuxuSearch(TA,inthigh,Tkey)/顺序查找inti=0;Ahigh=key;初始化i,使A的最高位为key值while(Ai!=key)i+;returni;如果A中有key值,则在i不到n+1时就会输出,否则,返回high值,说明搜索失败。intmain()inti,key,
8、pos,length,fen,k,j,a,kuai,e;/定义一些变量a=0;k=0;coutvv请输入关键字的个数length;intAlength-1;/根据输入关键字的个数初始化一个数组进行存储coutvv请输入要分块的个数vvendl;cinfen;intBfen-1;intMfen-1;for(i=0;ivfen;i+)Mi=0;/初始化两个数组,一个用来存储每一块元素的大小,另一个用来存储每一块的中元素的最大值coutvv请输入每个分块关键字的个数vvendl;for(i=0;ivfen;i+)cinBi;使数组B中表示每块中关键字的个数coutvv请输入关键字endl;for(i
9、=0;iAi;输入所有的关键字,存在数组A中introw,col;row=fen;col=length;int*p2;p2=newint*row;/声明一个二维数组for(i=0;irow;i+)p2i=newintcol;for(i=0;irow;i+)for(j=0;jBi;j+)p2ij=Ak;k=k+1;/将所有关键字,按块的不同存入二维数组中coutvv分块情况为endl;for(i=0;i=Mi)Mi=p2ij;coutvvendl;/输出二维数组,检验分块是否为预期coutvv每个块最大元素为vvendl;for(i=0;ivfen;i+)coutvvMivvendl;将每一组的
10、最大元素存入数组M中coutvvendlvv请输入要查找的元素;cinkey;将要查找的关键字赋值给keypos=BinSearch(M,O,length-1,key);调用折半查找函数,查找关键字处于哪个块中coutvv该元素所处的块是vvendl;if(pos!=-1)kuai=pos;coutvvkuaivvendl;elsekuai=dd;coutvvkuaivvendl;将关键字所在的块输出。int*S;S=newintkuai;for(i=0;iBkuai;i+)Si=p2kuaii;/初始化一个一维数组,将关键字所在快的元素重新定义为一个数组Spos=shuxuSearch(S,
11、Bkuai,key);在S中顺序查找关键字intq=0;for(i=0;ikuai;i+)q=q+Bi;if(pos!=Bkuai)coutvv该元素的位置为vvpos+qvvendl;如果关键字存在,输出其位置elsecoutvv不存在该元素endl;若不存在,输出“不存在该元素”coutvv还要继续查找吗?是的话,输入1,不是的话输入0e;/引入判断条件,以便多次查找while(e!=1)&(e!=0)coutvv输入不合法,请重新输入ee;保证输入合法while(e=1)coutvvendlvv请输入要查找的元素;cinkey;pos=BinSearch(M,0,length-1,key
12、);coutvv该元素所处的块是vvendl;if(pos!=-1)kuai=pos;coutvvkuaivvendl;elsekuai=dd;coutvvkuaivvendl;for(i=0;ivBkuai;i+)Si=p2kuaii;pos=shuxuSearch(S,Bkuai,key);intq=0;for(i=0;ivkuai;i+)q=q+Bi;if(pos!=Bkuai)coutvv该元素的位置为vvpos+qvvendl;elsecoutvv不存在该元素vvendl;coutvv还要继续查找吗?是的话,输入1,不是的话输入0vvendl;cine;/与上面程序一致,通过循环条件
13、保证可以多次进行查system(pause);return0;输出结果:胃辆人天键土旳八机善输入要分块的个数當轴入毎个分块关链自的八数4444请输入关键土122213828333842877&5063991019796分庚情饥为122213828333B4287765363亦101779G莓八块最大元素为224287101吗1是的话,吗?是的话,输人1输人1不是的话输入不是的话输入0C:U5ersAdministratorDeskto|嘗三次数揭结啕作ik,exeKffl=義查处元查人素墓输元存要请该3不还耗的-B杳处元查W所1丛素1输一兀存要请该2不还1IlIlS是的话,输入不是的话输入回1请技任邕犍继缜-说明:可见,按照16=4*4分块的选择方式,13元素在第0块,处于关键字序列中的第2位。86和88元素都不在关键字序列中。另外,由于程序中引入了可以由用户自己选择分块数目和大小的功能,因此,选择16=5+5+6的分块方法可以得到一样的结果:发现结果完全一致。心得体会:本次实验程序结构
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026年汽车后市场内容营销策略研究报告
- 智慧餐饮系统智能优化手册
- 交通管理能力考核表
- 媒体推广经纪业务绩效考核表
- 三农产品网络销售广告投放策略手册
- 航天器发射流程技术手册
- 2025-2026车间安全培训考试模拟题含完整答案
- 2025年工会招聘笔试题及答案
- 2025年德阳辅警考试题库(含答案)
- 2025年G2电站锅炉司炉考试题库(附答案)
- 拔罐疗法适应症与禁忌专家共识(2025版)
- 慢性阻塞性肺疾病科普
- 2024儿童口腔分龄护理和科学防龋专家共识解读
- NBT 10209-2019《风电场工程道路设计规范》
- 2026春季学期国家开放大学专科《统计与数据分析基础》一平台在线形考形成性考核一至五试题及答案
- 中班安全:《玩火真危险-我们不玩火》课件
- 卫生部病历书写基本规范2025年版
- 2025年宜都社区专职工作人员招聘真题
- 超星尔雅学习通《人工智能与创业智慧(北京林业大学)》章节测试含答案
- PC塑料培训课件
- 2024年辽宁机电职业技术学院招聘笔试真题
评论
0/150
提交评论