折半查找及其改进

《折半查找及其改进》由会员分享，可在线阅读，更多相关《折半查找及其改进（8页珍藏版）》请在装配图网上搜索。

1、折半查找及其改进一、问题描述查找是在一个数据元素集合中查找关键字等于某个给个数据元素关键字的过程，也称为检索。给出一个特定的元素x,在含有n个元素的数列中判断是否存在这个元素，如果存在，返回此元素在数列中的位置，否则返回零。数列查找在实际中的应用十分广泛，因此数列查找算法的好坏直接影响到程序的优劣。本设计要求读取文件中的数据建立查找表，并设计算法实现折半查找及其改进查找。二、基本要求1、选择合适的存储结构，读取已知文件数据建立查找表；2、完成基于递归和非逆归的折半查找算法的设计；3、完成基于区间约束对折半查找算法的改进算法的设计；4、完成三分查找算法的设计。三、测试数据文件in.txt中100

2、个数据：1,2,3-98,99,100。中前50位数，查找元素:58中前50位数，查找元素:18中前100位数，查找元素：18中前100位数，待查元素：581、读取文件in.txt2、读取文件in.txt3、读取文件in.txt4、读取文件in.txt四、算法思想1、折半查找的算法思想是以处于区间中间位置记录的关键字和给定值比较，若相等，则查找成功，如不等，则缩小范围，直至新的区间中间位置记录的关键字等于给定值或区间大小小于零时为止。2、缩小区间查找算法的思想是先求出有序数列中每相邻两个元素之差的最大值的一个上界，设为m.要查找的数值为key,然后在每次循环做折半之前先进行一次筛选工作，即将l

3、ow右移(key-alow/m)位，high值左移(ahigh-key)/m位，从而把尽可能多的不必要的元素过滤掉，缩小查找范围继续查找，直至新的区间中间位置记录的关键字等于给定值或区间大小小于零时为止。3、三分查找的算法思想是在给出n个已经排好序的数，在n/3和2n/3处各取一个数,跟给定值key比较，确定待查数所在的范围，直至新的区间中间位置记录的关键字等于给定值或区间大小小于零时为止。五、模块划分1、voidread_dat(SSTable*ST,intn),读取文件in.dat中的数据并建立一个含文件in.dat中前n个数据的静态查找表ST。2、voidDestroyList(SSTa

4、ble*ST),销毁表ST。3、intSearchB1(SSTableST,KeyTypekey),利用折半查找的非递归算法，查找关键字等于key的数据元素，若存在，返回该元素在表中的位置，否则为0。4、SearchB2(SSTableST,intkey,intlow,inthigh),利用折半查找的递归算法，查找关键字等于key的数据元素，若存在，返回该元素在表中的位置，否则为0。5、SearchB3(SSTableST,KeyTypekey),对折半查找算法的一种改进6、SearchB4(SSTableST,KeyTypekey),利用三分查找法，查找关键字等于key的数据元素，若存在，返

5、回该元素在表中的位置，否则为0。7、voidMainMenue(),主菜单。8、main(),主函数。六、数据结构查找表类型定义如下：typedefintKeyType;typedefstructKeyTypekey;/*其它域：略*/ElemType;typedefstructElemType*elem;intlength;SSTable;七、源程序/*查找*/#includestdio.h#includestdlib.h#defineEQ(a,b)(a)=(b)#defineLT(a,b)(a)(b)#defineLQ(a,b)(a)elem=(ElemType*)malloc(n+1)*

6、sizeof(ElemType);ST-length=n;fp=fopen(in.txt,r);for(i=0;ielemi.key);printf(SSTable:(%d)t,ST-elem0.key);for(i=1;ielemi.key);fclose(fp);/*2.销毁查找表*/voidDestroyList(SSTable*ST)(free(ST-elem);voidDestroy(SSTable*ST)(if(ST-elem)(free(ST-elem);ST-length=0;/*3.折半查找的非递归算法*/intSearchB1(SSTableST,KeyTypekey)(i

7、ntlow,high,mid;low=1;high=ST.length;while(lowhigh)return0;mid=(low+high)/2;if(EQ(key,ST.elemmid.key)returnmid;elseif(LT(key,ST.elemmid.key)returnSearchB2(ST,key,low,mid-1);elsereturnSearchB2(ST,key,mid+1,high);/*5.对折半查找算法的一种改进*/intMAX(SSTableST)intmax,i;max=ST.elem2.key-ST.elem1.key;for(i=2;iST.leng

8、th-1;i+)if(maxST.elemi+1.key-ST.elemi.key)max=ST.elemi+1.key-ST.elemi.key;returnmax;intSearchB3(SSTableST,KeyTypekey)intlow,high,mid,l=0,h=0,m=MAX(ST);low=1;high=ST.length;while(low=0&h=0)l=(key-ST.elemlow.key)/m;h=(ST.elemhigh.key-key)/m;mid=(low+high)/2;if(EQ(key,ST.elemmid.key)returnmid;elseif(LT

9、(key,ST.elemmid.key)high=mid-1;elselow=mid+1;return0;/*6.三分查找*/intSearchB4(SSTableST,KeyTypekey)intmid1,mid2,low=1,high=ST.length;if(ST.elemlow.keykey|ST.elemhigh.keykey)return0;while(low=high)mid1=(high+low)/3;mid2=(2*high+low)/3;if(EQ(key,ST.elemmid1.key)returnmidi;elseif(LT(key,ST.elemmid1.key)hi

10、gh=mid1-1;elseif(EQ(key,ST.elemmid2.key)returnmid2;elseif(LT(key,ST.elemmid2.key)low=mid1+1;high=mid2-1;elselow=mid2+1;return0;/*7,主菜单*/voidMainMenue()(printf(nt*MainMenue*n);printf(*1.折半查找的非递归算法*n);printf(*2.折半查找的递归算法*n);printf(*3.对折半查找算法的一种改进*n);printf(*4.三分查找*n);printf(*5.Exit.*n);printf(*n);/*主函

11、数*/main()(SSTableT;KeyTypex;intn,flag=1;charc;printf(n请输入表长:);scanf(%d”,&n);read_dat(&T,n);MainMenue();while(flag)(printf(nPleaseinputyourchoice:);scanf(%s,&c);switch(c)(case1:printf(-n折半查找的非递归算法:)printf(n请输入待查元素:);scanf(%d”,&x);printf(n元素g表中的位置：d”,x,SearchB1(T,x);break;case2:printf(-n折半查找的递归算法：，pri

12、ntf(n请输入待查元素:);scanf(%d,&x);printf(n元素g表中的位置：d”,x,SearchB2(T,x,1,T.length)break;case3:printf(n对折半查找算法的一种改进：”)；printf(n请输入待查元素:);scanf(%d,&x);printf(n元素游表中的位置：d”,x,SearchB3(T,x);break;case4:printf(n三分查找:);printf(n请输入待查元素：，scanf(%d”,&x);printf(n元素%d在表中的位置：d”,x,SearchB4(T,x);break;case5:exit(1);default

13、:printf(Inputerror!n);break;return0;Destroy(&T);八、测试情况测试结果:1、读取文件in.txt中前50位数，查找元素：58请输入表长活SSTAhle：314151693H3245&2621223G373B1H26421127122&4412345eUU女岫注初in是一枇归！一的HrtliB法f的黑MH我投查戋f主寿itHK1二EKStMWMMHMKMMMHMMMHJNMMMMMMMWM1*1IfWtMMRM；MMamfM=M=H；l(MMM9tM1It-useinputourcJhuice；输出文件中前50位数和主菜单，运行正确。1=3回.趴栖女

14、件吗学事谭程设计、课:廷设计罚皿bu的林心leasEinputwuic.hoice1杏A半鞍kp，的斐理归算法:查元圭;孙元素换在表中的血置溷l*leaseinputuouretwice:Z昕半查挥的递归算法:诺福兀社查元煮泓四素我年表中的tz宜溜Flei!SEinputtoufc1vdeb=3度近半套找算法的一种祯进，诘新人侍查T聿瞰丞素就在表中的位置:（JlttAEHiiipu.1yuui1dfwuiiEH-4元幸M在汞中的位置：*PlifH出白vouacKoiffi=5Prfsgnnnukeutncnint:ipuRi查找58在表中位置，因为58不在表中，所以输出0,程序运行结果正确。2

15、、读取文件in.txt中前50位数，查找元素:18.E:gc曾学小演痉疆计VJI担诞计.Id回5Ple*sBinputg瞄1choiGB=1近去查决E韭谣归算法二情槁入宥查元豢g元素1日在表中的位置:1EPleaseinput驶u炉ciica:24置摧的递归算法:SSaW查元素部在表中的位置:博FludLEginyiityviiFcliuis-3板扳半凳找鼻醐种改谜，浦嫡入蒂查元事哥无茹咬表中的位宣&FieaseinputyvuFclioicH=4三分童找：清箱入待查元素元素1$在表中的位置：博Fleaseinputyourchoice5|Pr尊零enyemfiEirHiB元素18在表中位置为

16、18,结果正确3、读取文件in.txt中前100位数，查找元素：18I芷；宙建文停夹俘习V8I1S设计设t+&D*buEirji广oSJ输出文件中前100位数和主菜单，运行正确。E带餐丈卓那学g啧莅计谡祚设H冲#bogGn.exFPleaseLnjputanrchoice-1亢素IE在声中的位置:以PleaseinDutyourchoice:2醺濯醇元素IB在表中的位置=诵Pleaseinipmtyourhoice:3尊瞧藐曲元素1*在裹洋的位置:isFluiii；t2-JjifpiLit事011;buIciB-4二分霎找L清输X祷查元素浏元素皓任表中的位置:疏1Jledure-inputur

17、-chuice5Pressanykeytocontinue元素18在表中位置为18,运行结果正确。4、读取文件in.txt中前100位数，待查元素：58元素58在表中位置为58,运行结果正确。九、参考文献1、严蔚敏，数据结构C语言，清华大学出版社。2、谭浩强，c语言程序设计，清华大学出版社。小结通过本次课程设计，我学到了很多。它让我真正的理解了什么是程序，程序=算法+结构。编程的第一要务是把事物分析清楚，把事件先后的逻辑关系和依赖关系搞清楚，从而确定相应的数据结构，然后写代码去实现。所以只有学好数据结构，才能编好程序。编程不像做其它事，它要求编程人员有非常缜密的思维，很好的整体把握能力和很好的

18、调试程序的能力等。决定程序成功与否的往往不是程序的整体思路和整体算法，而是细节，细节错误往往是程序失败的终级杀手，我在此次课程设计中深有体会。如不同输入法下的分号不同，有个分号我是在中文输入法下输入的，导致我的程序运行的结果出错，花了我一定时间才检查出来错误。同时我也认识到编译工具的重要性，我用的是VC+6.0环境，提高我编写程序的效率，如按回车后，它能自动空出一定距离，体现出程序的结构，不用人工输入空格、制表符，还有它的调试功能，不用我人工输出中间变量来查错，就能看到中间变量。在实验编写程序的过程中，遇到了很多的问题，这些在我以前的实验中都是没遇到的，比如三分查找，在给出n个已经排好序的数，

19、在n/3和2n/3处各取一个数，跟给定值key比较，由于比较时会出现很多的情况，每一种情况都需要仔细考虑到，在编程中，因为没有认真分析，考虑不周全，导致一些情况遗漏了，程序出现了错误，经过后来认真分析，最终找到了遗漏的情况，程序运行成功。还有在编写基于区间约束对折半查找算法的改进算法的设计过程中，也遇到了类似的错误，考虑条件不周全，程序无法运行，后改正。可见编程过程中一定要认真分析各种条件，考虑周全，细节决定成败。通过这次课程设计，我领略到分工合作精神，集体编程和个人编程有很大不同，相互间独立而又紧密联系在一起，如编写三分查找时，我是独立编写，但是我要知道相应的存储结构，进而完成编写。编程过程

20、中要能体现创新精神，在编写读取文件数据函数的程序中，由于读取的数据需要相应的存储结构存取，所以我将建立查找表的程序加在文件数据函数的程序中，即将读取的数据直接建立一个查找表，避免了另外编写建立查找表的繁琐，自认为不失为一种创新。这次课程设计还让懂得如何利用以前所学的知识，例如，在验证实验结果时，为了能更好验证实验准确性，我想到了以前其他实验中采取的控制变量法，使实验结果正确性更具说服力。经过这次课程设计，我学到了很多东西，不仅巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力，而且培养了我选用参考书，查阅手册及文献资料的能力，培养独立思考，深入研究，分析问题、解决问题的能力。课程设计是把我们所学的理论知识进行系统的总结并应用于实践的良好机会，有利于加强我们用知识理论来分析实际问题的能力，进而加强了我们对知识认识的实践度，巩固了我们的理论知识，深化了对知识的认识，并为走向社会打下一个良好的基础。在这次课程设计中我遇到许多问题和麻烦，得到了老师的帮助和指导，才能够使得这次课程设计顺利的进行下去，另外，在程序调试过程中，也得到很多同学的帮助，给我及时指出错误，提出许多宝贵意见。在此对老师和同学们表示感谢！