数据结构实训报告-二分查找学生管理实训报告.doc

吉林工业职业技术学院（ 数据结构实训报告 ）（ 2011 2012 学年第1 学期）实训地点: 数据库实训室 指导教师: 专业班级: 计算机3101 学生姓名: 2011年12月16日28吉林工业职业技术学院 数据结构实训报告目 录实训项目2实训目的2设计分析2设计方案3详细设计6使用说明18运行调试18实训心得25参考文献27数据结构实训报告实训项目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. 个人项目：二分法查找演示把算法分成三个个部分：一是利用比较排序法将输入的一组数据进行排序；二是利用绘图函数绘好指针与确定指针位置；三是利用折半查找将想要查找的数字在数组中查找的演示过程在屏幕上显示出来。实现第一个算法思想：定义一个数组ah(h=0,1,2,3、，k-2)与临时变量，将数组元素ah与后边的每一个元素aj逐个比较凡有ajah者则交换二者的值（以保证ah比任何aj都小）。重复这个过程n-1次，最后a数组中元素便被升序排列。算法的基本思想是：（1） 定义数组ak，小标h、j，临时变量temp；（2） 初始化a数组，并令h=0；（3） 确定各个ah的位置：h=k-2；（4） 令j=h+1k-1，凡ajhigh时，查找失败，结束查找；（4） 当low=high时，mid=(low+high)/2。若yamid,low=mid+1;若y=amid,查找成功，结束；数据结构定义：mid=(low=high);/取中点if(yamid) low=mid+1;/在右半区查找2. 小组项目：学生成绩管理 学生成绩管理系统结构图：学生管理系统录入学生成绩导入学生成绩查询学生成绩删除学生记录追加学生记录显示学生成绩统计学生成绩保存输入记录成绩进行排序退出个人总分和平均分单科平均分总分最高分总分最低分按学生学号排序按学生姓名排序按数据结构成绩进行排序按计算机成绩排序按数据库成绩排序（1）建立一个明了的管理菜单，管理菜单包括：录入学生成绩（输入学生成绩菜单）、导入学生成绩（在外界表中的学生成绩信息导入到系统中）、查询学生成绩（利用学号、姓名进行查询学生成绩信息）、删除学生记录、追加学生记录（插入与修改学生成绩信息）、显示学生记录（对每总体学生成绩信息进行显示查询）、统计学生成绩（利用个人平均分和总分、单科平均分、总分最高分、总分最低分进行对各个学生成绩的汇总与排名）、保存输入记录（将输入完整的学生信息导出一张表进行保存）、成绩进行排序（有按学号排序、学生姓名排序和按单科成绩进行排序）、退出。（2）使操作人员很容易的完成对学生成绩的查询、修改、添加、保存和导入。（3）在统计与排序这一模块中又可分为多个可操作模块，大大增加了此系统的功能，如统计学生成绩中可分为按个人总分和平均分统计、按单科平均分统计、按总分最高分和总分最低分统计；而在排序这一模块中又分为按学生学号、学生姓名、学生各单科成绩排序，大大减少了工作量。（4）和以往系统不同，在它的模块中新增加拉保存与导入记录这两个模块，运用这两个模块可以将外界数据导入系统中或将本系统中的数据导入外界进行保存工作，以防数据丢失。（5）对要查询的数据要有准确性。数据结构定义：定义主函数main( )；在main( )里定义变量，使用do-while设计程序的容错性，定义被调函数creat2311、load2311、search2311、dell2311、add2311、printf2311、statistics2311、save2311、taxis2311和exit(0)判断所要进行的操作。while(1)k=menu2311(k);switch(k)case 1: head=creat2311();break;/*调用创建链表函数*/ case 2: head=load2311(head);break;/*从文件调入记录函数*/ case 3: head=search2311(head);break;/*调用成绩查询函数*/ case 4: head=del2311(head); break;/*调用删除学生资料函数*/ case 5: head=add2311(head,stu);break;/*调用追加学生资料函数*/ case 6: print2311(head); break;/*调用显示学生资料函数*/ case 7: statistics2311(head); break;/*调用统计函数*/ case 8: save2311(head);break;/*调用保存函数*/ case 9: taxis2311(head);break;/*调用排序函数*/ case 0: exit(0);/*退出系统，返回主界面*/ default: printf(输入错误,请重试!);详细设计1. 个人项目：二分法查找演示源程序代码如下：排序过程算法：void main(void) int n,h,l,j,temp,ak; int gd=detect,gm; initgraph(&gd,&gm,c:jmsoftcyuyantc); clrscr(); setbkcolor(9); setcolor(3); printf(input n=n); scanf(%d,&n); printf(input n numbers: n); for(h=0;hn;h+) scanf(%d,&ah); for(h=0;hn-1;h+) for(j=h+1;jn;j+) if(ajah) temp=aj; aj=ah; ah=temp; for(h=0;hn;h+) printf(%dt,ah); sleep(3); init(); printf(iputt find: l=); scanf(%d,&ah); put(a,n); fun(a,ah,n); close();运行结果如下图所示：图1 数组排序界面图2 输入要查找的数界面绘图指针与演示查找算法：void mid(int n)/*画中间键*/ setcolor(15);/*中间箭的颜色为白色,以下三条线画成了箭头,以下两个函数一样*/ 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); void down(int n)/*画上箭*/ 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); void up(int n)/*画下箭*/ 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); void clr(int y)/*擦除画面上的一些内容*/ setfillstyle(solid_fill,0);/*每次演示的时候先将下面显示的文字给去处掉*/ bar(0,y+50,640,y-50);/*这里是用矩形的方式*/ void put(int a,int n)/*一开始的输出函数*/ int i; char num5 ; setcolor(green); settextstyle(0,0,2);/*设置字体的大小*/ for(i=0;ihigh) break; while(low=high) clr(250); clr(80); clr(230);/*这里三个clr是为了把屏幕上的箭头和文字删了*/ mid=(high+low)/2; up(high); down(low); mid(mid);/*画好了三个箭头后开始查找*/ if(amid=y) outtextxy(300,250,find); break; if(amidy) low=mid+1; sprintf(str2,%d,amid); outtextxy(250,250,str2); outtextxy(300,250,y) high=mid-1; sprintf(str2,%d,amid); outtextxy(250,250,str2); outtextxy(300,250,); outtextxy(350,250,str1); 运行结果如下图所示：图3 二分查找演示界面2. 小组项目：学生成绩管理 本系统是有我们三个人共同合作完成，在做此系统之前我们各有各的分工，而我主要负责系统界面的整理、显示学生成绩、统计学生成绩、成绩进行排序这些项目，我负责项目代码源如下：void print2311(score *head)/*函数print2311,功能：显示学生成绩*/ score *p; if(head=null) printf(没有任何学生资料!); else printf(%dn,n); printf(学号 姓名 数据结构 计算机网络 数据库原理n); p=head; do printf(%-8d%-10s%-13.1f%-14.1f%-14.1fn,p-number,p-name,p-cyuyan,p-vbyuyan,p-sqlyuyan);p=p-next;while (p!=null);/*打印完成了*/ score *statistics2311(score *head)/*函数statistics2311,功能：统计学生成绩*/ float sum1=0,sum2=0,sum3=0,ave1=0,ave2=0,ave3=0,max=0,min; score *p; int x,y=0,i=0; p=head; printf( 1 个人总分和平均分nn); printf( 2 单科平均分nn); printf( 3 总分最高分nn); printf( 4 总分最低分nn); scanf(%d,&x); getchar(); switch(x)/*用switch语句实现功能选择*/ case 1: if(head=null) printf(没有任何学生资料!);return(head);/*链表为空*/ else printf(学号 姓名 数据结构 计算机网络 数据库原理 总分 平均分n);/*打印表格域*/ while(p!=null) sum1=p-cyuyan+p-vbyuyan+p-sqlyuyan; /*计算个人总分*/ ave1=sum1/3;/*计算个人平均分*/ printf(%-8d%-10s%-13.1f%-14.1f%-11.1f%-8.1f%-6.1fn,p-number,p-name,p-cyuyan,p-vbyuyan,p-sqlyuyan,sum1,ave1);/*打印结果*/*打印表格域*/ p=p-next;return(head); break; case 2: if(head=null) printf(没有任何学生资料!n);return(head);/*链表为空*/ while(p!=null) sum1=sum1+p-cyuyan; sum2=sum2+p-vbyuyan; sum3=sum3+p-sqlyuyan;/*计算总分*/ y=y+1; ave1=sum1/y; ave2=sum2/y; ave3=sum3/y;/*计算平均分*/ p=p-next;/*使p指向下一个结点*/ printf(数据 结构平均分是: %.1fnn,ave1); printf(计算机网络平均分是: %.1fnn,ave2); printf(数据库原理平均分是: %.1fnn,ave3);/*打印结果*/ return(head); break; case 3: if(head=null) printf(没有任何学生资料!);return(head);/*链表为空*/ max=p-cyuyan+p-vbyuyan+p-sqlyuyan; while(icyuyan+p-vbyuyan+p-sqlyuyan; /*计算个人总分*/ if(maxnext; printf(总分最高分:%.1f,max); printf(/n); return(head); break; case 4: if(head=null) printf(没有任何学生资料!n);return(head);/*链表为空*/ while(p!=null) min=p-cyuyan+p-vbyuyan+p-sqlyuyan; while(p!=null) sum2=p-cyuyan+p-vbyuyan+p-sqlyuyan; if(minsum2) min=sum2; p=p-next; printf(总分最低分:%.1f,min); printf(/n); return(head); break; default :printf(输入错误,请重试!); return(head); save2311(score *p1) /*函数save2311,功能：保存学生的资料*/ file *fp;char filepn20;/*用来存放文件保存路径以及文件名*/printf(请输入文件路径及文件名:); scanf(%s,filepn); if(fp=fopen(filepn,w+)=null) printf(不能打开文件!); return 0; fprintf(fp,nn=学生成绩管理系统=nn); fprintf(fp, 软件开发小组：计算机3101班 学号：08 11 22 nnn n); fprintf(fp,-n); fprintf(fp,学号/姓名/数据结构/计算机网络/数据库原理n); /*打印表格域*/ while(p1!=null) printf(学号 姓名 数据结构 计算机网络 数据库原理n); fprintf(fp,%-8d%-10s%-13.1f%-14.1f%-14.1f,p1-number,p1-name,p1-cyuyan,p1-vbyuyan,p1-sqlyuyan); p1=p1-next;/*下移一个结点*/ fclose(fp); printf(文件已经保存!n); return 0;score *taxis2311(score *head) /*定义排序函数。此函数带回一个指向链表头的指针*/ score *p,*max; int i,j,x; float fen; char t10; if(head=null) printf(/n没有任何学生资料，请先建立链表!/n);return(head);/*链表为空*/ max=p=head; for(i=0;i80;i+) printf(-); printf( 1 按学生学号排序nn); printf( 2 按学生姓名排序nn); printf( 3 按数据结构绩排序nn); printf( 4 按计算机网络成绩排序nn); printf( 5 按数据库原理nn); for(i=0;i80;i+) printf(-); printf(请选择操作:); scanf(%d,&x);/*选择操作*/ getchar(); switch(x) /*用switch语句实现功能选择*/ case 1 : for(i=1;in;i+) for(j=i+1;jnext; if(max-numberp-number) k=max-number; max-number=p-number; p-number=k; /*交换前后结点中的学号值，使得学号大者移到后面的结点中*/ strcpy(t,max-name); strcpy(max-name,p-name); strcpy(p-name,t); /*交换前后结点中的姓名，使之与学号相匹配*/ fen=max-cyuyan; max-cyuyan=p-cyuyan; p-cyuyan=fen;/*交换前后结点中的数据结构成绩，使之与学号相匹配*/fen=max-vbyuyan; max-vbyuyan=p-vbyuyan; p-vbyuyan=fen; /*交换前后结点中的计算机网络成绩，使之与学号相匹配*/ fen=max-sqlyuyan; max-sqlyuyan=p-sqlyuyan; p-sqlyuyan=fen;/*交换前后结点中的数据库原理成绩，使之与学号相匹配*/ max=head;p=head;/*重新使max,p指向链表头*/ print2311(head);break;/*打印值排序后的链表内容*/ case 2 : for(i=1;in;i+) for(j=i+1;jnext; if(strcmp(max-name,p-name)0)/*strcmp=字符串比较函数*/ strcpy(t,max-name);/*strcpy=字符串复制函数*/ strcpy(max-name,p-name); strcpy(p-name,t); /*交换前后结点中的姓名，使得姓名字符串的值大者移到后面的结点中*/ k=max-number; max-number=p-number; p-number=k; /*交换前后结点中的学号值，使之与姓名相匹配*/ fen=max-cyuyan; max-cyuyan=p-cyuyan; p-cyuyan=fen;/*交换前后结点中的c成绩，使之与姓名相匹配*/ fen=max-vbyuyan; max-vbyuyan=p-vbyuyan; p-vbyuyan=fen;/*交换前后结点中的vb成绩，使之与姓名相匹配*/ fen=max-sqlyuyan; max-sqlyuyan=p-sqlyuyan; p-sqlyuyan=fen; /*交换前后结点中的sql成绩，使之与姓名相匹配*/ p=head;max=head; print2311(head); break; case 3 : for(i=1;in;i+) for(j=i+1;jnext; if(max-cyuyanp-cyuyan) fen=max-cyuyan; max-cyuyan=p-cyuyan; p-cyuyan=fen;/*交换前后结点中的c成绩，使得c成绩高者移到后面的结点中*/ k=max-number; max-number=p-number; p-number=k; /*交换前后结点中的学号，使之与c成绩相匹配*/ strcpy(t,max-name); strcpy(max-name,p-name); strcpy(p-name,t);/*交换前后结点中的姓名，使之与c成绩相匹配*/fen=max-vbyuyan; max-vbyuyan=p-vbyuyan; p-vbyuyan=fen;/*交换前后结点中的vb成绩，使之与c成绩相匹配*/ fen=max-sqlyuyan; max-sqlyuyan=p-sqlyuyan; p-sqlyuyan=fen;/*交换前后结点中的sql成绩，使之与c成绩相匹配*/ p=head; max=head; print2311(head); break;case 4 : for(i=1;in;i+) for(j=i+1;jnext; if(max-vbyuyanp-vbyuyan) fen=max-vbyuyan; max-vbyuyan=p-vbyuyan; p-vbyuyan=fen; /*交换前后结点中的vb成绩，使得vb成绩高者移到后面的结点中*/ k=max-number; max-number=p-number; p-number=k;/*交换前后结点中的学号，使之与vb成绩相匹配*/strcpy(t,max-name); strcpy(max-name,p-name); strcpy(p-name,t); /*交换前后结点中的姓名，使之与vb成绩相匹配*/fen=max-cyuyan; max-cyuyan=p-cyuyan; p-cyuyan=fen;/*交换前后结点中的c成绩，使之与vb成绩相匹配*/ fen=max-sqlyuyan; max-sqlyuyan=p-sqlyuyan; p-sqlyuyan=fen;/*交换前后结点中的sql成绩，使之与vb成绩相匹配*/ p=head;max=head; print2311(head); break;case 5 : for(i=1;in;i+) for(j=i+1;jnext; if(max-sqlyuyanp-sqlyuyan) fen=max-sqlyuyan; max-sqlyuyan=p-sqlyuyan; p-sqlyuyan=fen; /*交换前后结点中的sql成绩，使得sql成绩高者移到后面的结点中*/ k=max-number; max-number=p-number; p-number=k; /*交换前后结点中的学号，使之与sql成绩相匹配*/strcpy(t,max-name); strcpy(max-name,p-name); strcpy(p-name,t); /*交换前后结点中的姓名，使之与sql成绩相匹配*/ fen=max-cyuyan; max-cyuyan=p-cyuyan; p-cyuyan=fen; /*交换前后结点中的c成绩，使之与sql成绩相匹配*/ fen=max-vbyuyan; max-vbyuyan=p-vbyuyan; p-vbyuyan=fen; /*交换前后结点中的vb成绩，使之与sql成绩相匹配*/ p=head;max=head; print2311(head); break;default :printf(输入错误,请重试! ); return (0);使用说明1. 个人项目：二分法查找演示本程序在turboc 2.0环境下运行通过。运行后,根据提示输入数据即可。可以输入任意一组数据和多组数据。数据输入结束时按回车键。在屏幕上输出数据经过比较排序输出数据的排序结果，排序完成经过三秒钟后则会弹出一个叫你输入查找的数的窗口，输完以后按回车接着就会弹出带有三个指针的窗口，再按回车则演示过程开始。2. 小组项目：学生成绩管理 本程序在visual c+6.0(*c)环境下运行通过。运行后,则会弹出有10个子菜单的菜单窗体。每个子菜单都有它的作用。菜单1是录入学生成绩信息；菜单2是导入学生成绩信息，即从外界表中把学生成绩信息数据导入到本系统中来；菜单3是查询学生成绩，即根据学生学号或者姓名查找出某名学生的成绩信息；菜单4是删除学生记录，即删除或修改某名学生的成绩信息；菜单5是追加学生成绩记录（插入学生成绩信息）；菜单6是显示学生成绩，即把所有的学生成绩一一显示在屏幕中；菜单7是统计学生成绩，它可分为四个子菜单即个人总分和平均分、单科平均分、总分最高分、总分最低分，根据在这些菜单可以对总体学生和个别学生成绩信息进行管理操作；菜单8是保存学生记录，即将该系统中的学生成绩信息数据导出一张表加以保存，防止文件数据的丢失；菜单9是成绩进行排序，此菜单可分为按学生学号排序、学生姓名排序和按学生每科成绩进行排序的多个子菜单，此功能可以对每名同学成绩进行汇总和名次的排序；菜单10即（0），是退出结束程序的功能。 运行调试1. 个人项目：表达式求值运行可执行文件08计算机刘超凡.exe或在turboc2.0下同时按住ctrl+f9运行08计算机刘超凡.c文件即可。运行实例如下：测试数据一：输入要查找的几个数的数目，接着输入要查找的这几个数，运行结果如图示：图4 输入数据测试数据二：在上面程序执行操作以后则对这些数据进行排序，运行结果如图所示图8 数据排序结果测试数据三：输入在这几个数中要查找的某个数或这个数以外的数字，运行结果如图所示：图9 输入要查找的数测试数据四：输入操作完毕后，点击回车则进行查找演示，如图所示：图10 二分查找演示以上即为二分查找演示的全过程。2. 小组项目：学生成绩管理 运行可执行文件学生成绩管理系统.exe或在visual c+6.0(*c)环境下同时运行学生成绩管理系统.c文件即可。运行实力如下： 测试数据一：学生管理系统运行界面如图所示：图11 学生管理系统总界面测试数据二：在下方请选（0-9）进行操作后面输入1，按回车，运行结果如图所示：图12 录入学生成绩界面测试数据三：在上面操作后输入0按回车键返回主界面，在输入2回车运行结果如图所示：图13 导入学生成绩测试数据四：在上面操作执行完后，输入0回车，在输入3回车运行结果如图所示：图14 查询学生成绩（1）图15 查询学生成绩（2）测试数据五：上面完成操作后返回主菜单，输入4回车运行结果如图所示：图16 删除学生记录测试数据六：上面操作完后，输入5回车运行结果如图所示：图17 追加学生记录测试数据七：上面操作完成后，输入6回车运行结果如图所示：图18 显示学生成绩测试数据八：上面操作完成后，输入7回车运行结果如下：图19 统计学生成绩输入1回车运行结果如图所示：图20 个人总分和平均分 在图19中操作输入2运行结果如下：图21 单科平均分在图19操作下输入3运行结果如下：图22 总分最高分在图19操作下输入4回车运行结果如下：图23 总分最低分测试数据九：在测试数据八结束后，返回主菜单输入8回车运行结果如图所示：图24 保存输入记录测试数据十：上面操作完成后返回主菜单，输入9回车运行结果如图所示：图25 成绩进行排序接着上面输入1回车运行结果如图所示：图26 按学生学号排序返回图25界面输入2回车运行界面如下：图27 按学生姓名排序返回图25，输入3或4或5回车运行结果如下图所示：图28 按数据结构成绩排序图29 按计算机网络成绩查询图30 按数据库原理成绩查询测试数据十：上面操作结束完成后返回主菜单，输入0回车，即程序结束。实训心得 在初学数据结构的一个学期后，我们进行了数据结构实训阶段，尝试自己和小组编写两个比较复杂的程序系统。在为期一周的时间中，我们同组的同学共同的感受是：数据结构实训和平时上课所接触的程序是有很大不同的，所经受的考验和克服的困难是平时所无法比拟的。我自己做的二分法查找演示系统，通过课下收集大量有关资料与代码和在同学老师的帮助下最终成果的做出来一个属于自己的二分法查找演示系统。关于小组合作题好在同组的搭档们精诚合作，分工明确，有问题共同解决，攻克了数据结构