折半查找及其改进(算法与数据结构课程设计).doc

折半查找及其改进一、问题描述 查找是在一个数据元素集合中查找关键字等于某个给个数据元素关键字的过程，也称为检索。给出一个特定的元素x，在含有n个元素的数列中判断是否存在这个元素，如果存在，返回此元素在数列中的位置，否则返回零。数列查找在实际中的应用十分广泛，因此数列查找算法的好坏直接影响到程序的优劣。本设计要求读取文件中的数据建立查找表,并设计算法实现折半查找及其改进查找。二、基本要求1、选择合适的存储结构，读取已知文件数据建立查找表；2、完成基于递归和非逆归的折半查找算法的设计；3、完成基于区间约束对折半查找算法的改进算法的设计；4、完成三分查找算法的设计。三、测试数据 文件in.txt中100个数据：1,2,398,99,100。1、 读取文件in.txt中前50位数，查找元素:582、 读取文件in.txt中前50位数，查找元素:183、 读取文件in.txt中前100位数，查找元素：184、 读取文件in.txt中前100位数，待查元素：58四、算法思想1、折半查找的算法思想是以处于区间中间位置记录的关键字和给定值比较，若相等，则查找成功，如不等，则缩小范围，直至新的区间中间位置记录的关键字等于给定值或区间大小小于零时为止。2、缩小区间查找算法的思想是先求出有序数列中每相邻两个元素之差的最大值的一个上界，设为m要查找的数值为key，然后在每次循环做折半之前先进行一次筛选工作，即将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个数据的静态查找表ST。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),对折半查找算法的一种改进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#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 *ST)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; if (EQ(key,ST.elemmid.key) return mid; else if (LT(key,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(SSTable 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(SSTable 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;else if(LT(key,ST.elemmid2.key) low=mid1+1;high=mid2-1;else low=mid2+1; 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);/* 主函数 */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;case 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:printf(n 三分查找:); printf(n请输入待查元素:); scanf(%d,&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位数和主菜单，运行正确。查找58在表中位置，因为58不在表中，所以输出0，程序运行结果正确。2、 读取文件in.txt中前50位数，查找元素:18元素18在表中位置为18，结果正确3、 读取文件in.txt中前100位数，查找元素：18输出文件中前100位数和主菜单，运行正确。元素18在表中位置为18，运行结果正确。4、 读取文件in.txt中前100位数，待查元素：58元素58在表中位置为58，运行结果正确。九、参考文献1、严蔚敏，数据结构 C语言，清华大学出版社。2、谭浩强，c语言程序设计，清华大学出版社。小结 通过本次课程设计，我学到了很多。它让我真正的理解了什么是程序，程序=算法+结构。编程的第一要务是把事物分析清楚，把事件先后的逻辑关系和依赖关系搞清楚，从而确定相应的数据结构，然后写代码去实现。所以只有学好数据结构，才能编好程序。编程不像做其它事，它要求编程人员有非常缜密的思维，很好的整体把握能力和很好的调试程序的能力等。决定程序成功与否的往往不是程序的整体思路和整体算法，而是细节，细节错误往往是程序失败的终级杀手，我在此次课程设计中深有体会。如不同输入法下的分号不同，有个分号我是在中文输入法下输入的，导致我的程序运行的结果出错，花了我一定时间才检查出来错误。同时我也认识到编译工具的重要性，我用的是VC+6.0环境，提高我编写程序的效率，如按回车后，它能自动空出一定距离，体现出程序的结构，不用人工输入空格、制表符，还有它的调试功能，不用我人工输出中间变量来查错，就能看到中间变量。在实验编写程序的过程中，遇到了很多的问题，这些在我以前的实验中都是没遇到的，比如三分查找，在给出n个已经排好序的数，在n/3和2n/3处各取一个数，跟给定值key比较，由于比较时会出现很多的情况，每一种情况都需要仔细考虑到，在编程中，因为没有认真分析，考虑不周全，导致一些情况遗漏了，程序出现了错误，经过后来认真分析，最终找到了遗漏的情况，程序运行成功。还有在编写基于区间约束对折半查找算法的改进算法的设计过程中，也遇到了类似的错误，考虑条件不周全，程序无法运行，后改正。可见编程过程中一定要认真分析各种条件，考虑周全，细节决定成败。 通过这次课程设计，我领略到分工合作精神，集体编程和个人编程有很大不同，相互间独立而又紧密联系在一起，如编写三分查找时，我是独立编写，但是我要知道相应的存储结构，进而完成编写。编程过程中要能体现创新精神，在编写读取文件数据函数的程序中，由于读取的数据需要相应的存储结构存取，所以我将建立查找表的程序加在文件数据函数的程序中，即将读取的数据直接建立一个查找表，避免了另外编写建立查找表的繁琐，自认为不失为一种创新。这次课程设计还让懂得如何利用以前所学的知识，例如，在验证实验结果时，为了能更好验证实验准确性，我想到了以前其他实验中采取的控制变量法，使实验结果正确性更具说服力。 经过这次课程设计，我学到了很多东西，不仅巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力，而且培养了我选用参考书，查阅手册及文献资料的能力，培养独立思考，深入研究，分析问题、解决问题的能力