二分法查找.docx
《二分法查找.docx》由会员分享，可在线阅读，更多相关《二分法查找.docx（18页珍藏版）》请在冰点文库上搜索。
二分法查找
吉林工业职业技术学院
（数据结构实训报告）
（2012~2013学年第1学期）
实训地点:
软件开发实训室
指导教师:
赵秀艳、刘文宏
专业班级:
计算机3111
*******
2012年12月13日
数据结构实训报告
实训项目
1.个人项目：
二分法查找演示
问题描述：
用箭头表示指针，模拟出二分法查找的指针变化过程。
要求：
给定一组数据。
可以动态地显示二分法查找的过程。
用到函数：
setcolor（WHITE）－画颜色，line（x1,y1,x2,y2）－画直线;，bar（x1,y1,x2,y2）－画矩形，settextstyle（0,0,2）－字体大小，outtextxy（x,y,变量或常量）－输出内容;initgraph（&gd,&gm,"c:
\\tc"）－tc所在目录的路径，setfillstyle（SOLID_FILL,0）－每次演示的时候先将下面显示的文字给去处掉，等等。
2.小组项目：
学生成绩管理
问题描述：
编写一个学生成绩管理系统，实现计算每个学生的总分、平均分，班级的总分、平均分，按分数高低排序。
包含插入、删除、修改、查询、显示模块。
要求：
成绩包括本学期所开设的课程（数据结构、计算机网络、数据库原理、……），采用菜单程序编写。
包含插入、删除、修改、查询、显示模块。
实训目的
通过本次实训，能够进一步巩固、掌握程序设计基础和数据结构课程的基本知识、基本技能。
运用算法分析与程序设计的一般方法进行实际项目的开发。
本项目需要具备熟练的数组和线性表知识，具备程序编写、调试的基本能力，具有一定的文字表达和报告撰写能力，具备办公软件使用能力。
设计分析
1.个人项目：
二分法查找演示
用户在键盘上输入任意一组无限制的数据，即想输入什么数或想输入几个数，如：
输入5个数而这五个数是你想输入什么数就行。
最后输入你要查找的数，即用二分查找演示系统查找的数，最后屏幕便出现你一开始输入的5个数和用函数画好的三个准备用于演示查找的指针，最后点击键盘任意键即可运行二分法查找演示。
因本系统涉及到画图，不同的显示适配器有不同的图像分辨率，因此在屏幕作图之前应设置屏幕为图形模式，将图形初始化。
2.小组项目：
学生成绩管理
本系统是为了方面统计与管理各个学生的成绩，采用了学生成绩录入、学生成绩插入、学生成绩信息表导入与导出、学生成绩删除与修改、学生成绩总分、平均分的统计、学生成绩的显示、学生成绩的综合排名与按科目排名等模块。
设计方案
1.个人项目：
二分法查找演示
把算法分成三个个部分：
一是利用比较排序法将输入的一组数据进行排序；二是利用绘图函数绘好指针与确定指针位置；三是利用折半查找将想要查找的数字在数组中查找的演示过程在屏幕上显示出来。
实现第一个算法思想：
定义一个数组a[h]（h=0,1,2,3、、、，K-2）与临时变量，将数组元素a[h]与后边的每一个元素a[j]逐个比较凡有a[j]重复这个过程N-1次，最后a数组中元素便被升序排列。
算法的基本思想是：
（1）定义数组a[K]，小标h、j，临时变量temp；
（2）初始化a数组，并令h=0；
（3）确定各个a[h]的位置：
h<=K-2；
（4）令j=h+1~K-1，凡a[j]（5）输出排序后的a数组，结束执行第二个算法图形的画法。
实现第二个算法的思想：
利用绘图函数setcolor（WHITE）－画颜色，line（x1,y1,x2,y2）－画直线，bar（x1,y1,x2,y2）－画矩形，settextstyle（0,0,2）－字体大小，outtextxy（x,y,变量或常量）－输出内容，initgraph（&gd,&gm,"c:
\\tc"）－tc所在目录的路径，setfillstyle（SOLID_FILL,0）－每次演示的时候先将下面显示的文字给去处掉，主要利用这些函数画出查找演示所需的三个指针。
实现第三个算法思想：
在上面两个算法执行完成后，取中间元素作为比较对象，若给定值与中间元素的关键字相等，则查找成功，若给定的值小于中间元素的关键字，则在中间元素的左半区继续查找；若给定值大于中间元素的关键字，则在中间元素右半区继续查找。
不断重复过程，直到查找成功，或所查找的区域无数据元素，查找失败，程序结束。
算法的基本思想是：
（1）设置初始区间low=0;high=n-1；
（2）确定基本算法，mid=（low+high）/2；
（3）当low>high时，查找失败，结束查找；
（4）当low<=high时，mid=（low+high）/2。
若ya[mid],low=mid+1;若y=a[mid],查找成功，结束；
数据结构定义：
Mid=（low<=high）;//取中点
if（yIf（y>a[mid]）low=mid+1;//在右半区查找。
2.小组项目：
学生成绩管理
学生成绩管理系统结构图：
如图1所示
图一学生成绩管理系统结构图
（1）建立一个明了的管理菜单，管理菜单包括：
✋录入学生成绩（输入学生成绩菜单）；
✋导入学生成绩（在外界表中的学生成绩信息导入到系统中）；
✋查询学生成绩（利用学号、姓名进行查询学生成绩信息）；
✋删除学生记录、追加学生记录（插入与修改学生成绩信息）；
✋显示学生记录（对每总体学生成绩信息进行显示查询）；
✋统计学生成绩（利用个人平均分和总分、单科平均分、总分最高分、总分最低分进行对各个学生成绩的汇总与排名）；
✋保存输入记录（将输入完整的学生信息导出一张表进行保存）；
✋成绩进行排序（有按学号排序、学生姓名排序和按单科成绩进行排序）；
✋退出。
（2）使操作人员很容易的完成对学生成绩的查询、修改、添加、保存和导入。
（3）在统计与排序这一模块中又可分为多个可操作模块，大大增加了此系统的功能，如统计学生成绩中可分为按个人总分和平均分统计、按单科平均分统计、按总分最高分和总分最低分统计；而在排序这一模块中又分为按学生学号、学生姓名、学生各单科成绩排序，大大减少了工作量。
（4）和以往系统不同，在它的模块中新增加拉保存与导入记录这两个模块，运用这两个模块可以将外界数据导入系统中或将本系统中的数据导入外界进行保存工作，以防数据丢失。
（5）对要查询的数据要有准确性。
数据结构定义：
定义主函数main（）；在main（）里定义变量，使用do-while设计程序的容错性，定义被调函数fun1、fun2、fun3、fun4、fun5、fun6和fun7判断所要进行的操作。
if（choose==1||choose==2||choose==3||choose==4||choose==5||choose==6||choose==7||choose==8||choose==0）
switch（choose）
{
case1:
fun1（）;break;//添加
case2:
fun2（）;break;//计算个人总分、平均分，班级总分、平均分
case3:
fun3（）;break;//排序
case4:
fun4（）;break;//查询
case5:
fun5（）;break;//修改
case6:
fun6（）;break;//删除
case7:
fun7（）;break;//插入
case8:
fun8（）;break;/*调用保存函数*/
case9:
fun8（）;break;/*调用排序函数*/
case0:
fun0（）;/*退出系统，返回主界面*/
default:
printf（"输入错误,请重试!
"）;
}
详细设计
1.个人项目：
二分法查找演示
源程序代码如下：
{
inta[N],x;
Init（a,&x）;/*x为要查找的数*/
Put（a,N）;
find（a,x,N）;
Close（）;
exit（0）;
}
voidMid（intn）/*画中间键*/
{
setcolor（WHITE）;/*中间箭的颜色为白色,以下三条线画成了箭头,以下两个函数一样*/
line（25+n*40,120,25+n*40,80）;
line（25+n*40,120,20+n*40,110）;
line（25+n*40,120,30+n*40,110）;
}
voidDown（intn）/*画上箭*/
{
setcolor（6）;
line（25+n*40,120,25+n*40,80）;
line（25+n*40,120,20+n*40,110）;
line（25+n*40,120,30+n*40,110）;
}
voidUp（intn）/*画下箭*/
{
setcolor（6）;
line（25+n*40,180,25+n*40,220）;
line（25+n*40,180,20+n*40,190）;
line（25+n*40,180,30+n*40,190）;
}
voidClr（inty）/*擦除画面上的一些内容*/
{
setfillstyle（SOLID_FILL,0）;/*每次演示的时候先将下面显示的文字给去处掉*/
bar（0,y+50,640,y-50）;/*这里是用矩形的方式*/
}
voidPut（inta[],intn）/*输出数值*/
{
inti;
charnum[5];
setcolor（GREEN）;
settextstyle（0,0,2）;/*设置字体的大小*/
for（i=0;i{
sprintf（num,"%d",a[i]）;/*将数字转换成字符串输出*/
outtextxy（20+i*40,150,num）;
}
settextstyle（0,0,1）;
setcolor（BLUE）;
outtextxy（250,250,"anykeytocontinue"）;
getch（）;
}
voidfind（inta[],inty,intn）/*具体的查找*/
{
intlow,high,mid,i;
charstr1[5],str2[5];
sprintf（str1,"%d",y）;
low=0;
high=n-1;
setcolor（RED）;
settextstyle（0,0,2）;
outtextxy（200,10,"FIND"）;
outtextxy（330,10,str1）;
while（low<=high）
{
Clr（250）;
Clr（80）;
Clr（230）;/*这里三个Clr是为了把屏幕上的箭头和文字删了*/
mid=（high+low）/2;/*计算中间位置*/
Up（high）;/*显示上边箭头*/
Down（low）;/*显示右边箭头*/
Mid（mid）;/*画好了三个箭头后开始查找*/
if（a[mid]==y）/*如果找到跳出循环*/
break;
if（a[mid]{
low=mid+1;/*修改左边界*/
sprintf（str2,"%d",a[mid]）;
outtextxy（250,250,str2）;/*显示比较数据的情况*/
outtextxy（300,250,"<"）;
outtextxy（350,250,str1）;
}
else
………..
2.小组项目：
学生成绩管理
voidDisp（Linkl）
{
intcount=0;
Node*p;
p=l->next;
if（!
p）
{
printf（"\n=====>提示:
没有资料可以显示!
\n"）;
return;
}
printf（"\t\t\t\t显示结果\n"）;
printstart（）;
printc（）;
printf（"\n"）;
while（p）
{
printe（p）;
p=p->next;
}
printstart（）;
printf（"\n"）;
}
voidTongji（Linkl）
{
Node*pm,*pe,*pc,*pt,*pa;//用于指向分数最高的接点
Node*r=l->next;
if（!
r）
{
printf（"\n=====>提示:
没有资料可以统计!
\n"）;
return;
}
pm=pe=pc=pt=pa=r;
while（r）
{
if（r->data.cgrade>=pc->data.cgrade）
pc=r;
if（r->data.mgrade>=pm->data.mgrade）
pm=r;
if（r->data.egrade>=pe->data.egrade）
pe=r;
if（r->data.totle>=pt->data.totle）
pt=r;
if（r->data.ave>=pa->data.ave）
pa=r;
r=r->next;
}
printf（"------------------------------统计结果--------------------------------\n"）;
printf（"总分最高者:
\t%s%d分\n",pt->data.name,pt->data.totle）;
printf（"平均分最高者:
\t%s%d分\n",pa->data.name,pa->data.ave）;
printf（"英语最高者:
\t%s%d分\n",pe->data.name,pe->data.egrade）;
printf（"数学最高者:
\t%s%d分\n",pm->data.name,pm->data.mgrade）;
printf（"c语言最高者:
\t%s%d分\n",pc->data.name,pc->data.cgrade）;
printstart（）;
}
voidSort（Linkl）
{
Linkll;
Node*p,*rr,*s;
ll=（Link）malloc（sizeof（Node））;//用于做新的连表
ll->next=NULL;
if（l->next==NULL）
{
printf（"\n=====>提示:
没有资料可以排序!
\n"）;
return;
}
p=l->next;
while（p）
{
s=（Node*）malloc（sizeof（Node））;//新建接点用于保存信息
s->data=p->data;
s->next=NULL;
rr=ll;
while（rr->next!
=NULL&&rr->next->data.totle>=p->data.totle）
rr=rr->next;
if（rr->next==NULL）
rr->next=s;
else
{
s->next=rr->next;
rr->next=s;
}
p=p->next;
}
free（l）;
l->next=ll->next;
printf（"\n=====>提示:
排序已经完成!
\n"）;
}
voidSave（Linkl）
{
FILE*fp;
Node*p;
intflag=1,count=0;
fp=fopen（"g:
\\student","wb"）;
if（fp==NULL）
{
printf（"\n=====>提示:
重新打开文件时发生错误!
\n"）;
exit
（1）;
}
p=l->next;
……….
使用说明
1.个人项目：
二分法查找演示
本程序在turboc2.0环境下运行通过。
运行后,根据提示输入数据即可。
可以输入任意一组数据和多组数据。
数据输入结束时按回车键。
在屏幕上输出数据经过比较排序输出数据的排序结果，排序完成经过三秒钟后则会弹出一个叫你输入查找的数的窗口，输完以后按回车接着就会弹出带有三个指针的窗口，再按回车则演示过程开始。
2.小组项目：
学生成绩管理
本程序在VisualC++6.0（*C）环境下运行通过。
运行后,则会弹出有10个子菜单的菜单窗体。
每个子菜单都有它的作用。
菜单1是录入学生成绩信息；菜单2是导入学生成绩信息，即从外界表中把学生成绩信息数据导入到本系统中来；菜单3是查询学生成绩，即根据学生学号或者姓名查找出某名学生的成绩信息；菜单4是删除学生记录，即删除或修改某名学生的成绩信息；菜单5是追加学生成绩记录（插入学生成绩信息）；菜单6是显示学生成绩，即把所有的学生成绩一一显示在屏幕中；菜单7是统计学生成绩，它可分为四个子菜单即个人总分和平均分、单科平均分、总分最高分、总分最低分，根据在这些菜单可以对总体学生和个别学生成绩信息进行管理操作；菜单8是保存学生记录，即将该系统中的学生成绩信息数据导出一张表加以保存，防止文件数据的丢失；菜单9是成绩进行排序，此菜单可分为按学生学号排序、学生姓名排序和按学生每科成绩进行排序的多个子菜单，此功能可以对每名同学成绩进行汇总和名次的排序；菜单10即（0），是退出结束程序的功能。
运行调试
1.个人项目：
二分法查找演示
运行可执行文件visualc++6.0或在turboc2.0下同时运行08-二分法查找.c文件即可。
测试数据一：
数据排列如图2所示
图2数据排序结果
测试数据二：
输入在这几个数中要查找的某个数或这个数以外的数字，运行结果如图3所示
图3运行结果界面
测试数据三：
输入操作完毕后，点击回车则进行查找演示，如图4所示：
图4二分查找演示
以上即为二分查找演示的全过程。
2.小组项目：
学生成绩管理
运行可执行文件visualc++6.0或在turboc2.0下同时运行学生成绩管理.c文件即可。
测试数据一：
运行界面如图5所示
图5运行界面
测试数据二：
统计学生成绩运行界面如图6所示
如图6统计学生成绩运行界面
实训心得
通过两周的实训，使我对程序设计基础和数据结构两门课程的基本知识有了进一步的理解，特别数组和顺序表知识尤为深刻，学到了程序设计的一般方法和步骤，对于曾经在课堂上没有熟练掌握，甚至是没有掌握的知识，在实训周里都不同程度的得到了巩固。
通过实训，我在算法分析与设计、程序编制与调试、报告撰写等方面有了极大的收获，有助于培养自己良好的编程思想，提高了自己的操作能力、专业能力和职业能力，为今后课程的学习和毕业设计打下了基础。
虽然在实训期间我遇到了很多问题，但是通过老师的指点与同学之间的探讨，我们都在愉快中解决了出现的问题，让我感觉到了程序设计中的奥妙与乐趣。
次实训最具有挑战性的就是个人题目，我抽到的题目是数据结构中的二分法查找演示系统，这个项目是一个非常复杂的项目，它容C语言中的序列排序与绘图和数据结构中的二分查找中的折半查找于一体，大大增加了题目的难度与复杂系数，但是我没有被这种困难所屈服，通过我每天的努力与课下收集的大量资料在同学老师的帮助下，我克服了种种难关，最终制作出来一个很灵活的查询演示系统，它比以前系统的不同之处就是它可以人一定以数组，也可以任意定以要查找演示的数字，所以这比这以前的系统有了很大的提高与创新，同时也是我人生中的一大喜悦，同时也增强了我对数据结构和C语言的学习的兴趣。
参考文献
[1]闵敏.数据结构.高等教育出版社.2007.7
[2]严蔚敏.数据结构—C语言.清华大学出版社
[3]杨秀金.数据结构.西安电子科技大学出版社
[4]李春葆.数据结构习题与解析.清华大学出版社
[5]谭浩强.C程序设计.清华大学出版
[6]http:
//www.123.45.68.9
[7]赵文静等编著 数据结构与算法 ,科学出版社,2005.08
[8]姜仲秋等主编，C语言程序设计，南京大学出版社，1998年1月。
教师评语：
成绩评定
注：
教师评定内容
1．实践操作技能
2．实训报告质量
3．实训期间表现
升级会员 