算法与数据结构课程设计--折半查找及其改进

《算法与数据结构课程设计--折半查找及其改进》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

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

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

4、立一个含文件in.dat中前n个数据的静态查找表ST。wilyes11收集博客(与学习无关)：http://blog.sina.com.cn/u/18102318022、voidDestroyList(SSTable*ST),销毁表ST。3、intSearchB1(SSTableST,KeyTypekey),利用折半查找的非递归算法，查找关键字等于key的数据元素，若存在，返回该元素在表中的位置，否则为0。4、SearchB2(SSTableST,intkey,intlow,inthigh),利用折半查找的递归算法，查找关键字等于key的数据元素，若存在，返回该元

5、素在表中的位置，否则为0。5、SearchB3(SSTableST,KeyTypekey),对折半查找算法的一种改进6、SearchB4(SSTableST,KeyTypekey),利用三分查找法，查找关键字等于key的数据元素，若存在，返回该元素在表中的位置，否则为0。7、voidMainMenue(),主菜单。8、main(),主函数。六、数据结构查找表类型定义如下：typedefintKeyType;typedefstruct{KeyTypekey;/*其它域:略*/}ElemType;typedefstruct{ElemType*elem;intlengt

6、h;}SSTable;七、源程序/*查找*/#include"stdio.h"#include"stdlib.h"#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)<=(b))/*查找表类型定义*/typedefintKeyType;typedefstruct{KeyTypekey;/*其它域:略*/}ElemType;typedefstruct{ElemType*elem;wilyes11收集博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

7、intlength;}SSTable;/*1.读取文件数据并建立查找表*/voidread_dat(SSTable*ST,intn){inti;FILE*fp;ST->elem=(ElemType*)malloc((n+1)*sizeof(ElemType));ST->length=n;fp=fopen("in.txt","r");for(i=0;i<=n;i++)fscanf(fp,"%d,",&ST->elem[i].key);printf("SSTable:(%d)t",ST->elem[0].key);for(i=1;i<=n;i++)printf("%

8、5d",S