【数据结构】学生成绩条形图统计问题_实验报告

1、.东北大学信息科学与工程学院数据结构课程设计报告题目 学生成绩条形图统计问题课题组长 王健 课题组成员 张颖 刘琪 张晓雨专业名称 计算机科学与技术班级 计1307指导教师 杨雷2015 年 1月课程设计任务书题目：学生成绩条形图统计问题问题描述：条形图问题描述：给定n个数据，绘出表示这n个数据的条形统计图。即统计出这n个数据中有多少个不同的值，以及每个值出现的频率是多少。条形图常用于表示数据分布情况。例如，学生考试成绩统计、居民收入分布情况等。假设输入数据为正整数，利用二叉排序树完成输入数据频率统计。设计要求：设计基于二叉排序树的学生成绩条形图统计程序。（1）采用STL的二叉排序树等数据结构

2、。（2）实现STL的二叉排序树stree类。（3）实现学生成绩条形图统计。指导教师签字：年月日目录1 课题概述41.1 课题任务41.2 课题原理41.3 相关知识42 需求分析52.1 课题调研52.2 用户需求分析53 方案设计63.1 总体功能设计63.2 数据结构设计63.3 函数原型设计63.4 主算法设计73.5 用户界面设计94 方案实现104.1 开发环境与工具104.2 程序设计关键技术104.3 个人设计实现（按组员分工）4.3.1 刘琪设计实现104.3.2 张晓雨设计实现114.3.3 王健设计实现134.3.4 张颖设计实现145 测试与调试175.1 个人测试（按组

3、员分工）175.1.1 刘琪测试175.1.2 张晓雨测试175.1.3 王健测试175.1.4 张颖测试175.2 组装与系统测试175.3 系统运行196 课题总结216.1 课题评价216.2 团队协作216.3 下一步工作216.4 个人设计小结（按组员分工）216.4.1 刘琪设计小结216.4.2 张晓雨设计小结226.4.3 王健设计小结226.4.4 张颖设计小结227 附录A 课题任务分工23A-1 课题程序设计分工23A-2 课题报告分工24 附录B 课题设计文档（光盘）25B-1源程序代码（*.H，*.CPP）25B-2工程与可执行文件）25 附录C 用户操作手册（可选）

4、25C.1 运行环境说明25C.2 操作说明251 课题概述1.1 课题任务设计基于二叉排序树的学生成绩条形图统计程序。（1）采用STL的二叉排序树等数据结构。（2）实现STL的二叉排序树stree类。（3）实现学生成绩条形图统计。1.2 课题原理1.2.1平衡二叉树又称AVL树。它或者是一颗空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，切左子树和右子树的深度之差的绝对值不超过1。若将二叉树上的结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1.只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就

5、是不平衡的。1.2.2对树中全部结点逐一进行某种处理需要对其进行遍历。中序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则：（1） 中序遍历左子树；（2） 访问根节点；（3） 中序遍历右子树。1.3相关知识 1.3.1AVL算法构建AVL树 1.3.2平衡二叉树结点的插入与删除 1.3.3平衡二叉树数据统计 1.3.4在dos下打印表2 需求分析2.1课题调研随着现代高科技的不断发展，人们在面临大量数据的同时，必须发掘有效的方法将数据进行一点的规律统计，以便能直观的从统计中发现数据间的总体宏观表现，为下一步的数据处理提供有效的数据频率依据。2.2 用户需求分析据调查，人们对考试的成绩分布

6、有着重大需求。而一般考试均为百分制，分为五等优（>90分），良（90分<且>80分），中（80分<且>70分），及格（70分<且>60分）和不及格（<60分）。所以，我们决定利用二叉平衡树统计学生成绩分布，输出学生成绩分布情况。3 方案设计3.1 总体功能设计开始插入成绩成绩录入查看条形图插入个别插入大量结束3.2 数据结构设计/动态平衡二叉树typedef struct BSTNode char nu10; int count; int data; int bf; /平衡因子 struct BSTNode *lchild,*rchild; /左

7、右孩子结点BSTNode,*BSTree; /二叉树结点、树typedef struct /学生信息结构体 int grade; /分数 char nu10; /学号Stu;3.3 函数原型设计void LeftBalance(BSTree &T); /对以指针T所指结点为根的二叉树作左平衡/旋转处理，本算法结束时，指针T指向新的根结点void RightBalance(BSTree &T); /对以指针T所指结点为根的二叉树作右平衡/旋转处理，本算法结束时，指针T指向新的根结点void Creat_AVL(BSTree &T); /生成AVLvoid Insert_A

8、VL(BSTree &T); /插入结点函数void Delet_AVL(BSTree &T); /删除结点函数void Combine_AVL(BSTree &T,BSTree &T1); /合并两棵平衡树函数void Veiw_AVL(BSTree T); /显示平衡二叉树函数3.4 主算法设计基本思想：在构造二叉排序树的过程中，每插入一个结点时，首先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。一般情况下，假设由于在二叉排序树上插入

9、结点而失去平衡的最小树根结点的指针为a（即a是离插入结点最近，且平衡因子绝对值超过1的祖先结点），则失去平衡后进行调整的规律如下：（1） 单向右旋平衡处理：由于在*a的左子树根结点的左子树上插入结点，*a的平衡因子由 1增至2，致使以*a为根的子树失去平衡，则需进行一次向右的顺时针旋转操作。（2） 单向左旋平衡处理：由于在*a的右子树根结点的右子树上插入结点，*a的平衡因子由 -1增至-2，致使以*a为根的子树失去平衡，则需进行一次向左的逆时针旋转操作。（3） 双向旋转（先左后右）平衡处理：由于在*a的左子树根结点的右子树上插入结点，*a的平衡因子由 1增至2，致使以*a为根的子树失去平衡，则

10、需进行两次向旋转（先左旋后右旋）操作。（4） 双向旋转（先右后左）平衡处理：由于在*a的右子树根结点的左子树上插入结点，*a的平衡因子由- 1增至-2，致使以*a为根的子树失去平衡，则需进行两次向旋转（先右旋后左旋）操作。在平衡的二叉排序树AVL上插入一个新的数据元素e的递归算法，可描述为：（一） 若AVL为空树，则插入一个数据元素为e的新结点作为AVL的根结点，树的深度增1；（二） 若e的关键字和AVL的根结点的关键字相等，则不进行插入；（三） 若e的关键字小于AVL的根结点的关键字，而且在AVL的左子树中不存在和e有相同关键字的结点，则将e插入在AVL的左子树上，并且当插入之后的左子树深度

11、增加（+1）时，分别就下列不同情况处理之：（1） AVL的根结点的平衡因子为-1（右子树的深度大于左子树的深度）：则将根结点的平衡因子更改为0，AVL的深度不变；（2） AVL的根结点的平衡因子为0（左、右子树的深度相等）：则将根结点的平衡因子更改为1，AVL的深度增1；（3） AVL的根结点的平衡因子为1（左子树的深度大于右子树的深度）：则若AVL的左子树根结点的平衡因子为1：则需进行单向右旋平衡处理，并且在右旋处理后，将根结点和其右子树根结点的平衡因子更改为0，AVL的深度不变；（四） 若e的关键字小于AVL的根结点的关键字，而且在AVL的左子树中不存在和e有相同关键字的结点，则将e插入在

12、AVL的左子树上，并且当插入之后的左子树深度增加（+1）时，分别就不同情况处理之。 3.5 用户界面设计1.输入学生成绩2.在dos下打印表4 方案实现4.1 开发环境与工具硬件：个人PC软件：Dev C+开发环境：C+4.2 程序设计关键技术AVL算法；统计AVL树；dos界面打印表；4.3 个人设计实现 4.3.1 刘琪设计实现void Insert_AVL(BSTree &T) int e2,f=0; char a; char nu10; printf("请输入个别录入成绩："); scanf("%d%c",&e2,&a);

13、 InsertAVL(T,e2,nu,&f); printf("成功录入！n"); printf("nnnnnnnnnnn"); printf("nnnn按任意键返回菜单. "); getchar();void TravelAVL(BSTree T,int *nu) if(T) K*nu=T->data; (*nu)+; TravelAVL(T->lchild,nu); TravelAVL(T->rchild,nu); void Destroy(BSTree &T) if(T) Destroy(T-&

14、gt;lchild); Destroy(T->rchild); free(T); void Combine_ALV(BSTree &T,BSTree &T1) int nu,i,f; char nu110; nu=0; Creat_AVL(T1); getchar(); TravelAVL(T1,&nu); Destroy(T1); T1=NULL; for(i=0;i<nu;i+) f=0; InsertAVL(T,Ki,nu1,&f); printf("大量成绩录入成功，菜单查看！n "); printf("nnnn

15、nnnnnnn"); printf("nnnn按任意键返回菜单. "); getchar(); 4.3.2 张晓雨设计实现void PrintAVL(BSTree T,int n) /中序遍历 int i; if(!T) return; /递归出口PrintAVL(T->rchild,n+3); /遍历打印右子树/访问根节点 if(n>=0) if(T->data<=100&&T->data>=90) grade0+=T->count; else if(T->data>=80) grade1+=

16、T->count; else if(T->data>=70) grade2+=T->count; else if(T->data>=60) grade3+=T->count; else grade4+=T->count; PrintAVL(T->lchild,n+3); /便利打印左子树void Veiw_AVL(BSTree T) int n; TravelAVL(T,&n); for(int i=0;i<5;+i) gradei=0; printf("成绩条形图为:n"); PrintAVL(T,n);

17、 for(int i=0;i<5;i+) printf(" |"); for(int f=0;f<gradei;+f) printf(""); if(i=0) printf("*n 优：%4d",gradei); else if(i=1) printf("*n 良：%4d",gradei); else if(i=2) printf("*n 中：%4d ",gradei); else if(i=3) printf("*n 及格：%4d ",gradei); else

18、 printf("*n不及格：%4d ",gradei); for(int f=0;f<gradei;+f) printf(" "); printf("|n"); printf(" |"); for(int f=0;f<gradei;+f) printf(""); printf("*nn"); printf("按任意键返回菜单. "); getchar(); getchar(); 4.3.3 王健设计实现void LeftBalance(BST

19、ree &T) BSTNode *lc,*rd;lc=T->lchild; / lc指向*T的左子树switch(lc->bf) /检查*T的左子树的平衡度，并作相应平衡处理 case LH: /新结点插入在*T的左孩子的左子树上，要作单右旋处理 T->bf=lc->bf=EH; R_Rotate(T); break; case RH: /新结点插入在*T的左孩子的右子树上，要作双旋处理 rd=lc->rchild; / rd指向*T的左孩子的右子树根 switch(rd->bf) /修改*T及其左子树的平衡因子 case LH: / *T变换后平衡

20、因子为-1 T->bf=RH; lc->bf=EH; break; case EH: /平衡因子都为0 T->bf=lc->bf=EH; break; case RH: / lc平衡因子为1 T->bf=EH; lc->bf=LH; break; rd->bf=EH; L_Rotate(T->lchild); /左旋 R_Rotate(T); /右旋 void RightBalance(BSTree &T) /与上面过程类似 BSTNode *rc,*ld; rc=T->rchild; switch(rc->bf) case

21、RH: T->bf=rc->bf=EH; L_Rotate(T); break; case LH: ld=rc->lchild; switch(ld->bf) case RH: T->bf=LH; rc->bf=EH; break; case EH: T->bf=rc->bf=EH; break; case LH: T->bf=EH; rc->bf=RH; break; ld->bf=EH; R_Rotate(T->rchild); L_Rotate(T); 4.3.4 张颖设计实现int InsertAVL(BSTree

22、 &T,int e,char nu,int *taller)if(!T) /插入新结点 T=(BSTree)malloc(sizeof(BSTNode); T->data=e; T->lchild=T->rchild=NULL; T->bf=EH; *taller=1; T->count=1; else if(e=T->data) /树中已存在和e有相同关键码的结点 *taller=0; T->count+; return 0; /不再插入 if(e<T->data) /应继续在*T的左子树中进行搜索 if(!InsertAVL(T

23、->lchild,e,nu,taller) /递归 return 0; /未插入 if(*taller) /已插入到*T的左子树中且左子树“长高” switch(T->bf) /检查*T的平衡度 case LH: /原本左子树比右子树高，需要作左平衡处理 LeftBalance(T); *taller=0; break; case EH: /原本左右子树等高，现因左子树增高而使树增高 T->bf=LH; *taller=1; break; case RH: /原本右子树比左子树高，现左右子树等高 T->bf=EH; *taller=0; break; else /与上面

24、类似 if(!InsertAVL(T->rchild,e,nu,taller) return 0; if(*taller) switch(T->bf) case LH: T->bf=EH; *taller=0; break; case EH: T->bf=RH; *taller=1; break; case RH: RightBalance(T); *taller=0; break; return 1;/InsertAVLvoid Creat_AVL(BSTree &T) int i,f; int a; char c; Stu AMAX; T=NULL; pri

25、ntf("请输入学生个数："); scanf("%d%c",&a,&c); printf("请输入学生成绩序列：n"); for(i=0;i<a;i+) / printf("学生学号："); / scanf("%s",Ai.nu); printf("学生成绩："); scanf("%d",&Ai.grade); f=0; InsertAVL(T,Ai.grade,Ai.nu,&f); 5 测试与调试5.1 个人测试（无

26、） 5.1.1 刘琪测试 5.1.2 张晓雨测试 5.1.3 王健测试 5.1.4 张颖5.2 组装与系统测试1.设计主函数，组装功能函数#include<stdio.h>#include<malloc.h>#include<stdlib.h>#include<string.h>#define MAX 100 #define LH 1 /平衡因子#define EH 0#define RH -1int KMAX; /用于存储平衡二叉树结点的关键码int grade5; typedef struct BSTNode char nu10; int c

27、ount; int data; int bf; struct BSTNode *lchild,*rchild;BSTNode,*BSTree; /二叉树结点、树typedef struct int grade; char nu10;Stu;int main() BSTree T=NULL,T1; int a,n=0; printf("tt 【学生成绩条形图统计问题】nnn"); printf("tt*菜单*n"); printf("tt* 1.成绩录入 *n"); printf("tt* 2.插入个别学生成绩 *n"

28、;); printf("tt* 3.插入大量学生成绩 *n"); printf("tt* 4.查看成绩条形统计图 *n"); printf("tt* 5.退出 *n"); printf("请输入选项："); while(scanf("%d",&a)!=EOF) system("cls"); printf("tt 【学生成绩条形图统计问题】nnn"); switch(a) case 1: printf("成绩录入功能n"); Cr

29、eat_AVL(T); break; case 2: printf("插入个别学生成绩功能n"); Insert_AVL(T); break; case 3: printf("插入大量学生成绩功能n"); Combine_ALV(T,T1); break; case 4: printf("查看成绩条形统计图功能n"); Veiw_AVL(T); break; case 5: printf("nnnnnn"); printf("tt学生成绩条形图程序演示结束，谢谢您的使用！"); printf(&

30、quot;nnnnnnn"); exit(0); default: break; system("cls"); printf("tt学生成绩条形图程序演示结束，谢谢您的使用！"); printf("tt*菜单*n"); printf("tt* 1.成绩录入 *n"); printf("tt* 2.插入个别学生成绩 *n"); printf("tt* 3.插入大量学生成绩 *n"); printf("tt* 4.查看成绩条形统计图 *n"); pr

31、intf("tt* 5.退出 *n"); printf("请输入选项："); return 0;2.设计各种数据，验证程序的可靠性和稳定性，经检验，程序可靠性和稳定性均良好5.3 系统运行1.准备一组学生成绩2.运行程序3.选择成绩录入，输入一组成绩90 80 80 70 70 70 50 60 504.运行结果5.再次插入学生成绩50，打印结果为（不及格多一人）6.同时输入多个成绩80 70 50，打印统计结果6 课题总结6.1 课题评价小组设计的学生成绩统计程序小巧，使用方便。利用AVL算法，便于成绩的查找，提高查找效率。但是由于时间紧促，学生成绩统

32、计程序虽然完成了课题要求，但是功能还不够完善，有待进一步加强。6.2 团队协作整个工程分工细致，任务明确，在组长的带领下，小组全体组员出色的完成了自己的任务。经过各个成员的反复修改，小组程序的错误越来越少，并在验收中一次通过。6.3 下一步工作提供更加友好的用户界面，让用户使用更加便捷。增添更多的压缩功能，完善它在压缩功能上的不足，使其能够成为符合压缩标准的压缩软件。在往后使用的过程中，记录它出现的debug，使其能够应对突发情况，进而更加完美。6.4 个人设计小结 6.4.1 刘琪设计小结这门课结束之后，我总结了学习中遇到的一些问题，最为突出的，书本上的知识与老师的讲解都比较容易理解，但是当

33、自己采用刚学的知识点编写程序的时候却感到十分棘手，有时候表现在想不到适合题意的算法，有时候表现在算法想出来之后，只能将书本上原有的程序段转写到自己的程序中再加以必要的连接已完成程序的编写。 在设计软件之前，我们充分考虑到了软件的可行性、特殊性以及普遍性，本着由易到难的思想，我们先进行了全英文字符的文章的统计，而后我们则进行了其他格式的文章一起图形文件的读取，并以二进制格式存储。这次试验让我充分理解了编程的方法，提高了动手能力。 6.4.2 张晓雨设计小结 首先，通过这次的课程设计，我知道并掌握了平衡二叉树的建立方法以及其存储方法。同时通过小组其他成员的程序设计情况，我对用户界面设计有了一定的了

34、解。同时，我对平衡二叉树的应用有了一定的认识，而不是仅仅停留在课本上的程序，而是对平衡二叉树在数据传输上的应用有了领会。同时，我也明白了团队协作的重要性。团队的合作远比几个人单独的工作效率要高。一个团队如果有一定的默契程度，那么工作起来也会事半功倍，得心应手。一个真正优秀的程序设计者，一定不是只会一个人在工作，而是有团队协作能力，与队友并肩奋战。这次的实践课，我也学会了与队友一起努力，相互沟通，在团队合作能力上有了一定的提升。 6.4.3 王健设计小结1.软件开工之前，最好查阅相关资料，观摩前任类似软件代码。在自己编写代码过程中，因为前期规划不够，导致代码编写过程中遇到各种知识欠缺问题，例如：

35、对文件操作了解不够。2.应该做好总体设计。作为小组长，虽然讨论过整个过程如何实现，也做过一定的分析，但是后来发现，分析并不透彻，缺乏全局思考。最主要的原因在于花在总体设计时间太短。3.设计好各个接口，能够便于小组组装以及调试。由于当初规划时间过短，导致接口设计不够完美，在接下来的调试中花了大量时间，但是还未解决，最终废弃了不少代码。4.在整个工程中，本小组组员表现团结，各有分工，为工程如期完成奠定了良好的基础。 6.4.4 张颖设计小结 通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，从实践中验证理论，从而提高自己的