目录
1 摘要 3
1.1 设计题目... 3
1.2 设计内容... 3
1.3 开发工具... 3
1.4 应用平台... 3
2 详细设计... 3
2.1 程序结构... 3
2.2 主要功能... 3
2.3 函数实现... 3
2.4 开发日志... 4
3 程序调试及运行... 4
3.1 程序运行结果... 4
3.2 程序使用说明... 4
3.3 程序开发总结... 4
4 附件(源程序)... 4
1 摘要
1.1 设计题目
折半法查找演示程序
1.2 设计内容
本程序是一个演示折半查找算法的演示程序。由用户输入查找的数据表列和查找的数据,系统在将数表排序后可以在屏幕上演示在排序后的表列中按折半查找法查找该数据的具体过程(通过每次查找的中间数据、下次查找表列等,具体效果见下图),支持多次演示、错误提醒,程序暂停演示功能。
1.3 开发工具
Visual C++ 6.0和Win32。
1.4 应用平台
Windows 2000/XP/Vista 32位
2 详细设计
2.1 程序结构
程序功能模块:
本程序主要由五大模块组成:程序说明模块、输入模块、排序模块、折半法查找及显示模块、进程选择模块。各模块的主要功能如下:
程序说明模块:给使用者营造一个较为友好的界面,同时提供程序开发人员的相关信息以及程序操作的相关说明信息。
此部分模块主函数源代码如下:
int a[N]; /*存储要查找的数表,用户输入*/
int i,n,num,count; /*count为折半次数计数器,n为数表数据个数,num存储所查数据*/
int top,bottom,mid;
char c; /*存储选择函数中的输入的字符y或n*/
int flag=1; /*折半法循环标志变量*/
int loc=-1; /*存储所查找数据位置*/
double k=0;
p_s(76);puts("\n"); /*引用p_s函数,打出一行'*'*/(p_s函数位于print_star.cpp文件中,参见下文)
printf("****欢****迎****使****用****折****半****查****找****法****演****示****器****\n");
puts("\n"); /*程序欢迎语*/
p_s(13);
printf("制作者:***************** "); /*作者信息*/
p_s(4);
printf("Email:************************ "); /*电子邮件*/
p_s(11);puts("\n");
p_s(76);puts("\n"); /*再次引用p_s函数,程序说明部分结束*/
附:print_star.cpp文件源代码
#include<stdio.h>
void p_s(int k)
{
int i;
for(i=1;i<=k;i++)
/*连续输出ka个'*'*/
printf("*");
}
输入模块:引导使用者输入要在其中查找数据的数表的数据个数和数表数据。并通过一个judge函数判断输入是否合法,若不合法提醒用户继续输入。
此部分模块主函数源代码如下:
printf("请输入你想要在其中查找数据的数据表列的数据个数(1--50):\n");//
scanf("%d",&n);
n=judge(n); /*引用judge函数,判断n值是否合法*/ (judge函数位于judge.cpp文件,参见下文)
printf("请输入你要在其中查找数据的数据表列(%d个数据 用空格间隔 大小排序不限):\n",n); /*输入要查找的n 个数据*/
for(i=0;i<=n-1;i++)
scanf("%d",&a[i]); /*将要查找的n个数据存入数组a*/
sort(a,n); /*引用sort函数,将数表排序*/
printf("\n输出表列(从小到大排列)\n");
附:judge.cpp文件源代码
#include <stdio.h>
int judge(int n2)
/*函数作用:判断n2的值是否在1—50范围内*/
{ int n3;
while(n2<1 || n2>50)
{
printf("你输入的数不正确,请重新输入。\n");
printf("请输入你想要在其中查找数据的数据表列的数据个数(1--50):\n");
/*不合法重新输入并传递给主函数*/
scanf("%d",&n3);
return n3;
}
return n2;
}
排序模块:将用户输入数表的按升序排列并输出,为接下来的折半法查找做准备。
此部分模块主要通过sort.cpp文件中的sort函数实现
此部分模块主函数源代码如下:
sort(a,n); /*引用sort函数,将数表排序*/
printf("\n输出表列(从小到大排列)\n");
putout(a,0,n-1); /*引用putout函数,输出排序后数表*/
附:sort.cpp 文件源代码
#include <stdio.h>
void sort(int A[],int n1) /*将数组A的元素按从下到大顺序排序 */
{
int x,y,z;
for(x=0;x<n1;x++)
for(y=0;y<n1-x-1;y++)
{
if(A[y]>A[y+1]) /*二重循环将n1个数据由小到大排序*/
{
z=A[y]; /*z暂时存储a[y]的值*/
A[y]=A[y+1];
A[y+1]=z;
}
}
}
折半法查找及显示模块:提醒用户输入要查找的数据并判断是否合法。若合法则进入折半法查找循环,在每次折半法查找过程中输出数表中间数据、查找数据与该数据的大小关系、下次再左还是右部分查找,并输出该次折半法后要查找的数表的,用来演示折半法的查找过程,并在每次折半过程中设定程序暂停一次,方便演示,最后输出该数据在排序后数表的位置,然后进入进程选择模块;若非法,则输出“这个数在表列中没有找到”,然后进入进程选择模块。
此部分模块主函数源代码如下:
r_s: printf("请你输入要查找的数:\n"); /*输出要查找的数据*/
scanf("%d",&num);
count=0; /*折半次数计数器初值赋0*/
flag=1;
top=n-1;
bottom=0;
mid=(top+bottom)/2;
while(flag)
{
count++; /*折半次数计数器自加1*/
if( (num>a[top]) || (num<a[bottom]) ) /*查找数据非法,loc为1*/
{
loc=-1;
flag=0;
}
else if(a[mid]==num) /*折半法查找到该数据*/
{
loc=mid;
printf("第%d次折半\n",count); /*输出此次折半后中间数据*/
printf(" 中间数据为%d\n",a[mid]);
system("pause"); /*利用该语句暂停程序,便于演示,以下同理*/
printf("找到数 %6d 排序后的位置%2d\n",num,loc+1); /*输出结果*/
loc=1;
goto c_e; /*转至选择语句c_e,判断是否继续查找*/
}
else if(a[mid]>num)
{
printf("第%d次折半\n",count); /*利用折半次数计数器和循环显示每次折半查找后的表列*/
printf(" 中间数据为%d\n",a[mid]); /*输出此次折半后中间数据*/
printf(" 因为 %d<%d ",num,a[mid]); /*说明下步折半查找原因*/
printf("所以在左半部分查找\n 折半后查找数表为:\n");
top=mid-1;
mid=(top+bottom)/2;
putout(a,bottom,top); /*引用putout函数,输出该次折半后数表*/
system("pause");
}
else if(a[mid]<num)
{
printf("第%d次折半\n",count); /*利用折半次数计数器和循环显示每次折半查找后的表列*/
printf(" 中间数据为%d\n",a[mid]); /*输出此次折半后中间数据*/
printf(" 因为 %d>%d ",num,a[mid]); /*说明下步折半查找原因*/
printf("所以在右半部分查找\n 折半后查找数表为:\n");
bottom=mid+1;
mid=(top+bottom)/2;
putout(a,bottom,top); /*引用putout函数,输出该次折半后数表*/
system("pause");
}
}
if(loc==-1)
{
printf("%d 这个数在表列中没有找到。\n",num); /*若查找数据非法,提示查找错误*/
printf("请重新输入要查找的数据\n");
goto r_s; /*利用goto语句转职r_s语句重新查找*/
}
此段函数会用到putout函数,因上文已经提到,在此不做赘述。
进程选择模块:通过判断用户输入的字符决定程序下一步的走向,若为“y”则进入下一次折半法查找演示过程,若为“n”则进入程序退出模块。
此部分模块主函数源代码如下:
c_e:{ fflush(stdin); /*利用fflush语句清除按键缓存*/
printf("请选择是否继续查找\n");
printf("是——y,否——n\n"); /*选择步骤操作说明*/
c=getchar();
if(c!='y'&&c!='n')
{
printf("选择错误!"); /*若选择错误,继续选择*/
goto c_e;
}
else
{
if(c=='y') goto r_s; /*选择y,转至r_s语句继续查找*/
else goto end; /*选择n,转至end语句结束程序*/
}
}
程序退出模块:与程序说明模块呼应,友好的退出程序。
此部分模块源代码如下:
end: printf("程序结束\n");
system("pause");
printf("谢谢使用,再见!\n");
for(k=0;k<1.9e8;k++) /*延时程序*/
;
exit(0); /*利用exit语句退出主函数*/
工程文件结构
本程序的工程含有6个文件,其中main.cpp、print_stars.cpp、judge.cpp、sort.cpp、putout.cpp5个cpp文件和include.h1个头文件(参见下图),两者共同存在于工程“折半法查找演示程序”中。其中main.cpp文件包含了程序的主体部分,程序说明模块、输入、排序、折半查找及显示、程序退出模块按线性排列,进程选择模块穿插于其中,根据用户操作决定进程执行。其中输入、排序模块一般执行一次,进程选择模块可调控程序多次执行折半查找及显示模块,也可以调控执行程序退出模块。
2.2 主要功能
本程序的主要功能是演示折半法在一组升序排列的数表中查找某个数据的查找过程,同时兼有数表排序、多次演示、错误提醒等功能。各功能的实现具体说明如下:
演示折半法查找功能:运用计数器的规律和选择、循环结构实现折半法的程序特点,在一般折半法的程序模块上加以改动,增加一个折半次数计数器(程序中用count变量表示),同时在每次折半的选择结构中加入一个for循环语句,输出此次折半后的查找数表,配上相关的printf语句、程序暂停语句并输出相关文字说明,就能很好的演示折半法的查找原理和过程。具体参见下图。
数表排序功能:通过一个简单的二重循环将无序的数表按升序排列,主要运用冒泡算法。运行效果如下图。
多次演示功能:通过提示用户做相应的操作,实现程序的多次演示或者退出,提高程序的实用性。程序中主要通过goto语句和若干标号的语句实现。此部分程序运行截图如下:
多次演示及程序结束的运行效果:
错误提醒功能:判断用户输入的数据及相关操作是否合法,如不合法提醒用户改正,增加了程序德使用性和操作便捷性。主要是通过while循环和输入输出函数实现。相关运行截图如下:
n值输入错误的错误提醒及修正:
进程选择错误的错误提醒及修正:
程序暂停功能:主要运用system(pause)语句和一段延时小程序,增加程序演示时的可操作性和可讲解性。运行效果如下;
2.3 函数实现
本程序中含有一个主函数,四个子函数以及主函数中若干个起重要作用的函数语句,现将它们的功能、算法、数据结构等说明如下:
主函数:
参数:
主要思想为:
由用户自主输入n个数据,将其排序后,在传统折半法的基础上,增加一些必要的输入输出及控制语句,输出不同阶段循环控制变量所决定的数、特征值,伴以相关文字说明,延时折半法的原理过程。再嵌套一些进程控制的语句,达到多次使用的效果。
主函数代码及相关说明如下:
p_s(76);puts("\n");
printf("****欢****迎****使****用****折****半****查****找****法****演****示****器****\n");
puts("\n");
p_s(13);
printf("制作者:*************** ");
p_s(4);
printf("Email:********************* ");
p_s(11);puts("\n");
p_s(76);puts("\n"); 以上为程序说明部分,主要通过程简单的输入输出函数序说明程序功能和操作信息。
printf("请输入你想要在其中查找数据的数据表列的数据个数(1--50):\n");//
scanf("%d",&n);
n=judge(n); 在此调用judge函数,将输入n值代入judge函数检验是否合法 。
printf("请输入你要在其中查找数据的数据表列(%d个数据 用空格间隔 大小排序不限):\n",n); /
for(i=0;i<=n-1;i++)
scanf("%d",&a[i]); sort(a,n); 在此引用sort函数,将数组a[N],n代入sort函数,将数表排序。
printf("\n输出表列(从小到大排列)\n");
putout(a,0,n-1); ***** ——以“*****”标记的三处都引用了putout函数,输出一个一维数组
r_s: printf("请你输入要查找的数:\n"); scanf("%d",&num);
count=0;
***************************************************************************
flag=1;
top=n-1;
bottom=0;
mid=(top+bottom)/2;
while(flag)
{
count++;
if( (num>a[top]) || (num<a[bottom]) ) {
loc=-1;
flag=0;
}
else if(a[mid]==num)
{
loc=mid;
printf("第%d次折半\n",count);
printf(" 中间数据为%d\n",a[mid]);
system("pause"); 利用该语句暂停程序,便于演示,以下同理 printf("找到数 %6d 排序后的位置%2d\n",num,loc+1); loc=1;
goto c_e;
}
else if(a[mid]>num)
{
printf("第%d次折半\n",count);
printf(" 中间数据为%d\n",a[mid]);
printf(" 因为 %d<%d ",num,a[mid]);
printf("所以在左半部分查找\n 折半后查找数表为:\n");
top=mid-1;
mid=(top+bottom)/2;
putout(a,bottom,top); *****
system("pause");
}
else if(a[mid]<num) 以***间隔部分主要运用了折半法查找数据
{
printf("第%d次折半\n",count); printf(" 中间数据为%d\n",a[mid]);
printf(" 因为 %d>%d ",num,a[mid]);
printf("所以在右半部分查找\n 折半后查找数表为:\n");
bottom=mid+1;
mid=(top+bottom)/2;
putout(a,bottom,top); *****
system("pause");
}
}
if(loc==-1)
{
printf("%d 这个数在表列中没有找到。\n",num);
printf("请重新输入要查找的数据\n");
goto r_s; 利用goto语句(文中绿色部分)和标记语句(文中黄色部分)和循环语句实现进程的控制
}
*********************************************************************************
end: printf("程序结束\n");
system("pause");
printf("谢谢使用,再见!\n");
for(k=0;k<1.9e8;k++) 延时程序,延时约二秒 ;
exit(0); 利用exit语句直接退出主函数
c_e:{ fflush(stdin); fflush语句清除按键缓存,避免程序进程混乱
printf("请选择是否继续查找\n");
printf("是——y,否——n\n"); c=getchar();
if(c!='y'&&c!='n')
{
printf("选择错误!"); goto c_e;
}
else
{
if(c=='y')
goto r_s;
else
goto end;
}
}
}
judge函数:
参数:n2 n3
数据交换:导入main函数n的值,导出n2或n3的值
函数代码及相关说明:
#include <stdio.h>
int judge(int n2) 函数作用:判断n2的值是否在1—50范围内
{ int n3;
while(n2<1 || n2>50)
{
printf("你输入的数不正确,请重新输入。\n");
printf("请输入你想要在其中查找数据的数据表列的数据个数(1--50):\n");
不合法重新输入并传递给主函数
scanf("%d",&n3);
return n3;
}
return n2; 合法直接传回主函数
}
putout函数:
参数: B[], m1, m2
数据传递:B导入a[N的值,m1、m2视情况而定
函数代码及相关说明:
#include <stdio.h>
void putout(int B[],int m1,int m2)
函数作用:将数组B的第m1到m2个元素在一行输出
{
int x1;
for(x1=m1;x1<=m2-1;x1++)
printf("%6d",B[x1]);
printf("%6d\n",B[x1]);
}
sort函数:
参数:A[], n1;
数据传递:A[]导入a[N],然后导出,n1导入n的值
函数代码及相关说明:
#include <stdio.h>
void sort(int A[],int n1) 将数组A的元素按从下到大顺序排序
{
int x,y,z;
for(x=0;x<n1;x++)
for(y=0;y<n1-x-1;y++)
{
if(A[y]>A[y+1])
{
z=A[y];
A[y]=A[y+1]; 冒泡算法
A[y+1]=z;
}
}
}
p_s函数:
参数: k
代码及相关说明:
#include<stdio.h>
void p_s(int k)
{
int i;
for(i=1;i<=k;i++) 函数作用:连续输出k个'*'
printf("*");
}
2.4 开发日志
程序开发从构思到完成共历时二十天左右,基本过程如下:
6.1——6.4 开始基本构思,考虑大体的程序算法,并分段编写、调试部分程序。
6.5——6.7 编写主要程序,并且不断调试,直至达到了最基本的折半法演示功能。
图片如下:
6.8——6.10 完善演示功能,加入更多的描述性语句和控制语句,使程序基本达到了如今程序演示折半法的效果。如图示:
6.11——6.13 加入了程序说明模块和程序退出模块,完善了程序的引导性说明信息,完善程序的可操作性。
6.14 接受同学的意见,加入了进程选择模块,使程序可以多次演示。加入system语句,使演示过程中可以暂停,使演示效果优化。
6.15 完善源代码,将部分程序从主函数剥离,写进子函数,将程序工程变为多文件工程,增加头文件,使程序更易维护。
6.16 总体调试检查程序。
6.17 完成开发报告。
3 程序调试及运行
3.1 程序运行结果
程序开始运行:
排序模块结束:
多次执行折半查找及显示模块:
执行进程选择模块和程序退出模块:
3.2 程序使用说明
本程序使用较为简单,只需要按照程序提示做符合要求的操作,就可以完成折半法演示的功能,若不小心做了错误的操作,在程序允许的范围内可以重新操作,因此要仔细阅读程序说明部分和运行中的相关提示,按要求操作。另外,在程序演示过程中有很多暂停语句,用户只要按任意键就可继续运行。
3.3 程序开发总结
通过这次程序开发,我对程序员有了更深刻的认识。我意识到程序员不仅要有过人的思维,还要有足够的耐心,以及合作的意识、独立解决困难的意识。
通过这次程序开发,我明白了网络对与学习,特别是程序设计方面的巨大推动作用,通过上网搜索,我基本了解了system、exit、fllush等语句的一些用法,还知晓了很多有用的网站,以后在学习中我会更多的利用这点。
通过这次程序开发,我明白了创造性工作的魅力,虽然这段时间经常在数字化一待就是几个小时,但看着程序在自己手里不断完善,心里有说不出的喜悦。创造性的工作更能激发我们的热情。
通过这次程序开发,我明白了自己有很多的不足,程序也有缺陷,但这本来就是一个不断尝试、不断完善的过程,有了这次的体验,以后我会在这条路上走的更远。
4 附件(源程序)
源程序代码分为6个文件,main.cpp、judge.cpp、sort.cpp、putout.cpp和print_stars.cpp以及一个头文件include.h,六者共同存在于工程“折半法查找演示程序”中。
各文件源代码如下:
main.cpp文件源代码:
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define N 51
#include "include.h" /*声明头文件include.h*/
void main()
{
int a[N]; /*存储要查找的数表,用户输入*/
int i,n,num,count; /*count为折半次数计数器,n为数表数据个数,num存储所查数据*/
int top,bottom,mid;
char c; /*存储选择函数中的输入的字符y或n*/
int flag=1; /*折半法循环标志变量*/
int loc=-1; /*存储所查找数据位置*/
double k=0;
p_s(76);puts("\n"); /*引用p_s函数,打出一行'*'*/
printf("****欢****迎****使****用****折****半****查****找****法****演****示****器****\n");
puts("\n"); /*程序欢迎语*/
p_s(13);
printf("制作者:**************************** "); /*作者信息*/
p_s(4);
printf("Email:************************************ "); /*电子邮件*/
p_s(11);puts("\n");
p_s(76);puts("\n"); /*再次引用p_s函数,程序说明部分结束*/
printf("请输入你想要在其中查找数据的数据表列的数据个数(1--50):\n");//
scanf("%d",&n);
n=judge(n); /*引用judge函数,判断n值是否合法*/
printf("请输入你要在其中查找数据的数据表列(%d个数据 用空格间隔 大小排序不限):\n",n); /*输入要查找的n 个数据*/
for(i=0;i<=n-1;i++)
scanf("%d",&a[i]); /*将要查找的n个数据存入数组a*/
sort(a,n); /*引用sort函数,将数表排序*/
printf("\n输出表列(从小到大排列)\n");
putout(a,0,n-1); /*引用putout函数,输出排序后数表*/
r_s: printf("请你输入要查找的数:\n"); /*输出要查找的数据*/
scanf("%d",&num);
count=0; /*折半次数计数器初值赋0*/
flag=1;
top=n-1;
bottom=0;
mid=(top+bottom)/2;
while(flag)
{
count++; /*折半次数计数器自加1*/
if( (num>a[top]) || (num<a[bottom]) ) /*查找数据非法,loc为1*/
{
loc=-1;
flag=0;
}
else if(a[mid]==num) /*折半法查找到该数据*/
{
loc=mid;
printf("第%d次折半\n",count); /*输出此次折半后中间数据*/
printf(" 中间数据为%d\n",a[mid]);
system("pause"); /*利用该语句暂停程序,便于演示,以下同理*/
printf("找到数 %6d 排序后的位置%2d\n",num,loc+1); /*输出结果*/
loc=1;
goto c_e; /*转至选择语句c_e,判断是否继续查找*/
}
else if(a[mid]>num)
{
printf("第%d次折半\n",count); /*利用折半次数计数器和循环显示每次折半查找后的表列*/
printf(" 中间数据为%d\n",a[mid]); /*输出此次折半后中间数据*/
printf(" 因为 %d<%d ",num,a[mid]); /*说明下步折半查找原因*/
printf("所以在左半部分查找\n 折半后查找数表为:\n");
top=mid-1;
mid=(top+bottom)/2;
putout(a,bottom,top); /*引用putout函数,输出该次折半后数表*/
system("pause");
}
else if(a[mid]<num)
{
printf("第%d次折半\n",count); /*利用折半次数计数器和循环显示每次折半查找后的表列*/
printf(" 中间数据为%d\n",a[mid]); /*输出此次折半后中间数据*/
printf(" 因为 %d>%d ",num,a[mid]); /*说明下步折半查找原因*/
printf("所以在右半部分查找\n 折半后查找数表为:\n");
bottom=mid+1;
mid=(top+bottom)/2;
putout(a,bottom,top); /*引用putout函数,输出该次折半后数表*/
system("pause");
}
}
if(loc==-1)
{
printf("%d 这个数在表列中没有找到。\n",num); /*若查找数据非法,提示查找错误*/
printf("请重新输入要查找的数据\n");
goto r_s; /*利用goto语句转职r_s语句重新查找*/
}
end: printf("程序结束\n");
system("pause");
printf("谢谢使用,再见!\n");
for(k=0;k<1.9e8;k++) /*延时程序*/
;
exit(0); /*利用exit语句退出主函数*/
c_e:{ fflush(stdin); /*利用fflush语句清除按键缓存*/
printf("请选择是否继续查找\n");
printf("是——y,否——n\n"); /*选择步骤操作说明*/
c=getchar();
if(c!='y'&&c!='n')
{
printf("选择错误!"); /*若选择错误,继续选择*/
goto c_e;
}
else
{
if(c=='y') goto r_s; /*选择y,转至r_s语句继续查找*/
else goto end; /*选择n,转至end语句结束程序*/
}
}
}
print_stars.cpp文件源代码:
#include<stdio.h>
void p_s(int k)
{
int i;
for(i=1;i<=k;i++)
printf("*");
}
judge.cpp文件源代码:
#include <stdio.h>
int judge(int n2) /*函数作用:判断n2的值是否在1—50范围内*/
{ int n3;
while(n2<1 || n2>50)
{
printf("你输入的数不正确,请重新输入。\n");
printf("请输入你想要在其中查找数据的数据表列的数据个数(1--50):\n");
/*不合法重新输入并传递给主函数*/
scanf("%d",&n3);
return n3;
}
return n2;
}
sort.cpp文件源代码:
#include <stdio.h>
void sort(int A[],int n1) /*将数组A的元素按从下到大顺序排序 */
{
int x,y,z;
for(x=0;x<n1;x++)
for(y=0;y<n1-x-1;y++)
{
if(A[y]>A[y+1]) /*二重循环将n1个数据由小到大排序*/
{
z=A[y]; /*z暂时存储a[y]的值*/
A[y]=A[y+1];
A[y+1]=z;
}
}
}
putout.cpp文件源代码:
#include <stdio.h>
void putout(int B[],int m1,int m2) /*函数作用:将数组B的第m1到m2个元素在一行输出*/
{
int x1;
for(x1=m1;x1<=m2-1;x1++)
printf("%6d",B[x1]);
printf("%6d\n",B[x1]);
}
include.h文件源代码:
int judge(int n2); /*声明judge函数*/
void sort(int A[],int n1); /*声明sort函数*/
void putout(int B[],int m1,int m2); /*声明putout函数*/
void p_s(int k); /*声明p_s函数