折半查找及其改进.docx

《折半查找及其改进.docx》由会员分享，可在线阅读，更多相关《折半查找及其改进.docx（11页珍藏版）》请在三一办公上搜索。

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

2、测试数据 文件in.txt中100个数据：1,2,398,99,100。 1、 读取文件in.txt中前50位数，查找元素:58 2、 读取文件in.txt中前50位数，查找元素:18 3、 读取文件in.txt中前100位数，查找元素：18 4、 读取文件in.txt中前100位数，待查元素：58 四、算法思想 1、折半查找的算法思想是以处于区间中间位置记录的关键字和给定值比较，若相等，则查找成功，如不等，则缩小范围，直至新的区间中间位置记录的关键字等于给定值或区间大小小于零时为止。 2、缩小区间查找算法的思想是先求出有序数列中每相邻两个元素之差的最大值的一个上界，设为m要查找的数值为key

3、，然后在每次循环做折半之前先进行一次筛选工作，即将low右移(key-alow/m)位，high值左移(ahigh-key)/m位，从而把尽可能多的不必要的元素过滤掉，缩小查找范围继续查找，直至新的区间中间位置记录的关键字等于给定值或区间大小小于零时为止。 3、三分查找的算法思想是在给出n个已经排好序的数，在n/3和2n/3处各取一个数，跟给定值key比较，确定待查数所在的范围, 直至新的区间中间位置记录的关键字等于给定值或区间大小小于零时为止。 五、模块划分 1、void read_dat(SSTable *ST,int n),读取文件in.dat中的数据并建立一个含文件in.dat中前n个

4、数据的静态查找表ST。 wilyes11收集 博客(与学习无关)： 2、void DestroyList(SSTable *ST) ,销毁表ST。 3、int SearchB1(SSTable ST, KeyType key),利用折半查找的非递归算法，查找关键字等于key的数据元素，若存在，返回该元素在表中的位置，否则为0。 4、SearchB2(SSTable ST,int key,int low,int high),利用折半查找的递归算法，查找关键字等于key的数据元素，若存在，返回该元素在表中的位置，否则为0。 5、SearchB3(SSTable ST, KeyType key),对

5、折半查找算法的一种改进 6、SearchB4(SSTable ST, KeyType key ),利用三分查找法，查找关键字等于key的数据元素，若存在，返回该元素在表中的位置，否则为0。 7、void MainMenue,主菜单。 8、main,主函数。 六、数据结构 查找表类型定义如下： typedef int KeyType; typedef struct KeyType key; /*其它域:略*/ ElemType; typedef struct ElemType *elem; int length; SSTable; 七、源程序 /* 查找 */ #include stdio.h

6、#include stdlib.h #define EQ(a,b) (a)=(b) #define LT(a,b) (a)(b) #define LQ(a,b) (a)elem=(ElemType*)malloc(n+1)*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.销毁查找表 */ void DestroyList(SSTable *S

7、T) free(ST-elem); void Destroy(SSTable *ST) if (ST-elem) free(ST-elem); ST-length=0; /* 3.折半查找的非递归算法 */ int SearchB1(SSTable ST, KeyType key) int low,high,mid; low=1; high=ST.length; while(lowhigh) return 0; mid=(low+high)/2; wilyes11收集 博客(与学习无关)： if (EQ(key,ST.elemmid.key) return mid; else if (LT(k

8、ey,ST.elemmid.key) return SearchB2(ST,key,low,mid-1); else return SearchB2(ST,key,mid+1,high); /*5.对折半查找算法的一种改进*/ int MAX(SSTable ST) int max,i; max=ST.elem2.key-ST.elem1.key; for(i=2;iST.length-1;i+) if(maxST.elemi+1.key-ST.elemi.key) max=ST.elemi+1.key-ST.elemi.key; return max; int SearchB3(SSTabl

9、e ST, KeyType key) int low,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) return mid; else if (LT(key,ST.elemmid.key) high=mid-1; else low=mid+1; return 0; /*6.三分查找*/ int SearchB4(S

10、STable ST, KeyType key ) int mid1,mid2,low=1,high=ST.length; if(ST.elemlow.keykey|ST.elemhigh.keykey) return 0; while(low=high) mid1=(high+low)/3; mid2=(2*high+low)/3; if(EQ(key,ST.elemmid1.key) return mid1; else if(LT(key,ST.elemmid1.key) high=mid1-1; else if(EQ(key,ST.elemmid2.key) return mid2; el

11、se if(LT(key,ST.elemmid2.key) low=mid1+1;high=mid2-1; else low=mid2+1; wilyes11收集 博客(与学习无关)： return 0; /*7.主菜单*/ void MainMenue printf(n*MainMenue*n); printf(* 1. 折半查找的非递归算法 *n); printf(* 2. 折半查找的递归算法 *n); printf(* 3. 对折半查找算法的一种改进 *n); printf(* 4. 三分查找 *n); printf(* 5. Exit. *n); printf(*n); /* 主函数

12、*/ main SSTable T; KeyType x; int n,flag=1; char c; printf(n请输入表长:); scanf(%d,&n); read_dat(&T,n); MainMenue; while ( flag ) printf(nPlease input your choice: ); scanf(%s,&c); switch ( c ) case 1: printf(n折半查找的非递归算法:) printf(n请输入待查元素:); scanf(%d,&x); printf(n元素%d在表中的位置:%d,x,SearchB1(T,x); break; cas

13、e 2: printf(n折半查找的递归算法:); printf(n请输入待查元素:); scanf(%d,&x); printf(n元素%d在表中的位置:%d,x,SearchB2(T,x,1,T.length)；break; case 3: printf(n对折半查找算法的一种改进:); printf(n请输入待查元素:); scanf(%d,&x); printf(n元素%d在表中的位置:%d,x,SearchB3(T,x); break; case 4: wilyes11收集 博客(与学习无关)： printf(n 三分查找:); printf(n请输入待查元素:); scanf(%d

14、,&x); printf(n元素%d在表中的位置:%d,x,SearchB4(T,x); break; case 5: exit(1); default: printf(Input error!n); break; return 0; Destroy(&T); 八、测试情况 测试结果： 1、 读取文件in.txt中前50位数，查找元素:58 输出文件中前50位数和主菜单，运行正确。 wilyes11收集 博客(与学习无关)： 查找58在表中位置，因为58不在表中，所以输出0，程序运行结果 正确。 2、 读取文件in.txt中前50位数，查找元素:18 元素18在表中位置为18，结果正确 3、

15、读取文件in.txt中前100位数，查找元素：18 wilyes11收集 博客(与学习无关)： 输出文件中前100位数和主菜单，运行正确。 元素18在表中位置为18，运行结果正确。 4、 读取文件in.txt中前100位数，待查元素：58 wilyes11收集 博客(与学习无关)： 元素58在表中位置为58，运行结果正确。 九、参考文献 1、严蔚敏，数据结构 C语言，清华大学出版社。 2、谭浩强，c语言程序设计，清华大学出版社。 wilyes11收集 博客(与学习无关)： 小结 通过本次课程设计，我学到了很多。它让我真正的理解了什么是程序，程序=算法+结构。编程的第一要务是把事物分析清楚，把事

16、件先后的逻辑关系和依赖关系搞清楚，从而确定相应的数据结构，然后写代码去实现。所以只有学好数据结构，才能编好程序。 编程不像做其它事，它要求编程人员有非常缜密的思维，很好的整体把握能力和很好的调试程序的能力等。决定程序成功与否的往往不是程序的整体思路和整体算法，而是细节，细节错误往往是程序失败的终级杀手，我在此次课程设计中深有体会。如不同输入法下的分号不同，有个分号我是在中文输入法下输入的，导致我的程序运行的结果出错，花了我一定时间才检查出来错误。同时我也认识到编译工具的重要性，我用的是VC+6.0环境，提高我编写程序的效率，如按回车后，它能自动空出一定距离，体现出程序的结构，不用人工输入空格、

17、制表符，还有它的调试功能，不用我人工输出中间变量来查错，就能看到中间变量。在实验编写程序的过程中，遇到了很多的问题，这些在我以前的实验中都是没遇到的，比如三分查找，在给出n个已经排好序的数，在n/3和2n/3处各取一个数，跟给定值key比较，由于比较时会出现很多的情况，每一种情况都需要仔细考虑到，在编程中，因为没有认真分析，考虑不周全，导致一些情况遗漏了，程序出现了错误，经过后来认真分析，最终找到了遗漏的情况，程序运行成功。还有在编写基于区间约束对折半查找算法的改进算法的设计过程中，也遇到了类似的错误，考虑条件不周全，程序无法运行，后改正。可见编程过程中一定要认真分析各种条件，考虑周全，细节决

18、定成败。 通过这次课程设计，我领略到分工合作精神，集体编程和个人编程有很大不同，相互间独立而又紧密联系在一起，如编写三分查找时，我是独立编写，但是我要知道相应的存储结构，进而完成编写。编程过程中要能体现创新精神，在编写读取文件数据函数的程序中，由于读取的数据需要相应的存储结构存取，所以我将建立查找表的程序加在文件数据函数的程序中，即将读取的数据直接建立一个查找表，避免了另外编写建立查找表的繁琐，自认为不失为一种创新。这次课程设计还让懂得如何利用以前所学的知识，例如，在验证实验结果时，为了能更好验证实验准确性，我想到了以前其他实验中采取的控制变量法，使实验结果正确性更具说服力。 经过这次课程设计

19、，我学到了很多东西，不仅巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力，而且培养了我选用参考书，查阅手册及文献资料的能力，培养独立思考，深入研究，分析问题、解决问题的能力。课程设计是把我们所学的理论知识进行系统的总结并应用于实践的良好机会，有利于加强我们用知识理论来分析实际问题的能力，进而加强了我们对知识认识的实践度，巩固了我们的理论知识，深化了对知识的认识，并为走向社会打下一个良好的基础。在这次课程设计中我遇到许多问题和麻烦，得到了老师的帮助和指导，才能够使得这次课程设计顺利的进行下去，另外，在程序调试过程中，也得到很多同学的帮助 ，给我及时指出错误，提出许多宝贵意见。在此对老师和同学们表示感谢！ wilyes11收集 博客(与学习无关)：