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

折半查找及其改善
一、 问题描述
查找是在一个数据元素集合中查找关键字等于某个给个数据元素关键字过程, 也称为检索。给出一个特定元素x, 在含有n个元素数列中判定是否存在这个元素, 假如存在, 返回此元素在数列中位置, 不然返回零。数列查找在实际中应用十分广泛, 所以数列查找算法好坏直接影响到程序优劣。本设计要求读取文件中数据建立查找表,并设计算法实现折半查找及其改善查找。
二、 基础要求
1、 选择适宜存放结构, 读取已知文件数据建立查找表;
2、 完成基于递归和非逆归折半查找算法设计;
3、 完成基于区间约束对折半查找算法改善算法设计;
4、 完成三分查找算法设计。
三、 测试数据
文件in.txt中100个数据: 1,2,3…98,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, 然后在每次循环做折半之前优异行一次筛选工作, 立即low右移(key-a[low]/m)位, high值左移(a[high]-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)<=(b))

/* 查找表类型定义 */
typedef int KeyType;
typedef struct
{ KeyType key;
/*其它域:略*/
} ElemType;
typedef struct
{ ElemType *elem;
int length;
} SSTable;

/*1.读取文件数据并建立查找表*/
void read_dat(SSTable *ST,int n)
{ int i;
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("%5d",ST->elem[i].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(low<=high)
{ mid=(low+high)/2;
if (EQ(key,ST.elem[mid].key))
return mid;
else if (LT(key,ST.elem[mid].key))
high=mid-1;
else low=mid+1;}
return 0;
}
/*4.折半查找递归算法 */
int SearchB2(SSTable ST,int key,int low,int high)
{ int mid;
if(low>high) return 0;
mid=(low+high)/2;
if (EQ(key,ST.elem[mid].key))
return mid;
else if (LT(key,ST.elem[mid].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.elem[2].key-ST.elem[1].key;
for(i=2;i<ST.length-1;i++)
if(max<ST.elem[i+1].key-ST.elem[i].key)
max=ST.elem[i+1].key-ST.elem[i].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<=high&&l>=0&&h>=0)
{ l=(key-ST.elem[low].key)/m;
h=(ST.elem[high].key-key)/m;
mid=(low+high)/2;
if (EQ(key,ST.elem[mid].key)) return mid;
else if (LT(key,ST.elem[mid].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.elem[low].key>key||ST.elem[high].key<key) return 0;
while(low<=high)
{ mid1=(high+low)/3;
mid2=(2*high+low)/3;
if(EQ(key,ST.elem[mid1].key)) return mid1;
else if(LT(key,ST.elem[mid1].key))
high=mid1-1;
else
{ if(EQ(key,ST.elem[mid2].key)) return mid2;
else if(LT(key,ST.elem[mid2].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比较, 因为比较时会出现很多情况, 每一个情况都需要仔细考虑到, 在编程中, 因为没有认真分析, 考虑不周全, 造成部分情况遗漏了, 程序出现了错误, 经过以后认真分析, 最终找到了遗漏情况, 程序运行成功。还有在编写基于区间约束对折半查找算法改善算法设计过程中, 也碰到了类似错误, 考虑条件不周全, 程序无法运行, 后更正。可见编程过程中一定要认真分析多种条件, 考虑周全, 细节决定成败。
经过这次课程设计, 我领会到分工合作精神, 集体编程和个人编程有很大不一样, 相互间独立而又紧密联络在一起, 如编写三分查找时, 我是独立编写, 不过我要知道对应存放结构, 进而完成编写。编程过程中要能表现创新精神, 在编写读取文件数据函数程序中, 因为读取数据需要对应存放结构存取, 所以我将建立查找表程序加在文件数据函数程序中, 立即读取数据直接建立一个查找表, 避免了另外编写建立查找表繁琐, 自认为不失为一个创新。这次课程设计还让知道怎样利用以前所学知识, 比如, 在验证试验结果时, 为了能愈加好验证试验正确性, 我想到了以前其她试验中采取控制变量法, 使试验结果正确性更具说服力。
经过这次课程设计, 我学到了很多东西, 不仅巩固和加深了对数据结构了解, 提升综合利用本课程所学知识能力, 而且培养了我选择参考书, 查阅手册及文件资料能力, 培养独立思索, 深入研究, 分析问题、 处理问题能力。课程设计是把我们所学理论知识进行系统总结并应用于实践良好机会, 有利于加强我们用知识理论来分析实际问题能力, 进而加强了我们对知识认识实践度, 巩固了我们理论知识, 深化了对知识认识, 并为走向社会打下一个良好基础。在这次课程设计中我碰到很多问题和麻烦, 得到了老师帮助和指导, 才能够使得这次课程设计顺利进行下去, 另外, 在程序调试过程中, 也得到很多同学帮助 , 给我立刻指犯错误, 提出很多宝贵意见。在此对老师和同学们表示感谢!