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

东北大学信息科学与工程学院数据结构课程设计报告题目 学生成绩条形图统计问题课题组长 王健 课题组成员 张颖 刘琪 张晓雨专业名称 计算机科学与技术班级 计1307指导教师 杨雷2015 年 1月课程设计任务书题目：学生成绩条形图统计问题问题描述：条形图问题描述：给定n个数据，绘出表示这n个数据的条形统计图。即统计出这n个数据中有多少个不同的值，以及每个值出现的频率是多少。条形图常用于表示数据分布情况。例如，学生考试成绩统计、居民收入分布情况等。假设输入数据为正整数，利用二叉排序树完成输入数据频率统计。设计要求：设计基于二叉排序树的学生成绩条形图统计程序。（1）采用STL的二叉排序树等数据结构。（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 个人测试（按组员分工）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 用户操作手册（可选）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，则该二叉树就是不平衡的。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 用户需求分析据调查，人们对考试的成绩分布有着重大需求。而一般考试均为百分制，分为五等优（90分），良（90分80分），中（80分70分），及格（70分60分）和不及格（data; (*nu)+; TravelAVL(T-lchild,nu); TravelAVL(T-rchild,nu); void Destroy(BSTree &T) if(T) Destroy(T-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;irchild,n+3); /遍历打印右子树/访问根节点 if(n=0) if(T-datadata=90) grade0+=T-count; else if(T-data=80) grade1+=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;i5;+i) gradei=0; printf(成绩条形图为:n); PrintAVL(T,n); for(int i=0;i5;i+) printf( |); for(int f=0;fgradei;+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 printf(*n不及格：%4d ,gradei); for(int f=0;fgradei;+f) printf( ); printf(|n); printf( |); for(int f=0;flchild; / 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变换后平衡因子为-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 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 &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(edata) /应继续在*T的左子树中进行搜索 if(!InsertAVL(T-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 /与上面类似 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; printf(请输入学生个数：); scanf(%d%c,&a,&c); printf(请输入学生成绩序列：n); for(i=0;ia;i+) / printf(学生学号：); / scanf(%s,Ai.nu); printf(学生成绩：); scanf(%d,&Ai.grade); f=0; InsertAVL(T,Ai.grade,Ai.nu,&f); 5 测试与调试5.1 个人测试（无） 5.1.1 刘琪测试 5.1.2 张晓雨测试 5.1.3 王健测试 5.1.4 张颖5.2 组装与系统测试1.设计主函数，组装功能函数#include#include#include#include#define MAX 100 #define LH 1 /平衡因子#define EH 0#define RH -1int KMAX; /用于存储平衡二叉树结点的关键码int grade5; typedef struct BSTNode char nu10; int count; 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); 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); Creat_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(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); printf(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算法，便于成绩的查找，提高查找效率。但是由于时间紧促，学生成绩统计程序虽然完成了课题要求，但是功能还不够完善，有待进一步加强。6.2 团队协作整个工程分工细致，任务明确，在组长的带领下，小组全体组员出色的完成了自己的任务。经过各个成员的反复修改，小组程序的错误越来越少，并在验收中一次通过。6.3 下一步工作提供更加友好的用户界面，让用户使用更加便捷。增添更多的压缩功能，完善它在压缩功能上的不足，使其能够成为符合压缩标准的压缩软件。在往后使用的过程中，记录它出现的debug，使其能够应对突发情况，进而更加完美。6.4 个人设计小结 6.4.1 刘琪设计小结这门课结束之后，我总结了学习中遇到的一些问题，最为突出的，书本上的知识与老师的讲解都比较容易理解，但是当自己采用刚学的知识点编写程序的时候却感到十分棘手，有时候表现在想不到适合题意的算法，有时候表现在算法想出来之后，只能将书本上原有的程序段转写到自己的程序中再加以必要的连接已完成程序的编写。 在设计软件之前，我们充分考虑到了软件的可行性、特殊性以及普遍性，本着由易到难的思想，我们先进行了全英文字符的文章的统计，而后我们则进行了其他格式的文章一起图形文件的读取，并以二进制格式存储。这次试验让我充分理解了编程的方法，提高了动手能力。 6.4.2 张晓雨设计小结 首先，通过这次的课程设计，我知道并掌握了平衡二叉树的建立方法以及其存储方法。同时通过小组其他成员的程序设计情况，我对用户界面设计有了一定的了解。同时，我对平衡二叉树的应用有了一定的认识，而不是仅仅停留在课本上的程序，而是对平衡二叉树在数据传输上的应用有了领会。同时，我也明白了团队协作的重要性。团队的合作远比几个人单独的工作效率要高。一个团队如果有一定的默契程度，那么工作起来也会事半功倍，得心应手。一个真正优秀的程序设计者，一定不是只会一个人在工作，而是有团队协作能力，与队友并肩奋战。这次的实践课，我也学会了与队友一起努力，相互沟通，在团队合作能力上有了一定的提升。 6.4.3 王健设计小结1.软件开工之前，最好查阅相关资料，观摩前任类似软件代码。在自己编写代码过程中，因为前期规划不够，导致代码编写过程中遇到各种知识欠缺问题，例如：对文件操作了解不够。2.应该做好总体设计。作为小组长，虽然讨论过整个过程如何实现，也做过一定的分析，但是后来发现，分析并不透彻，缺乏全局思考。最主要的原因在于花在总体设计时间太短。3.设计好各个接口，能够便于小组组装以及调试。由于当初规划时间过短，导致接口设计不够完美，在接下来的调试中花了大量时间，但是还未解决，最终废弃了不少代码。4.在整个工程中，本小组组员表现团结，各有分工，为工程如期完成奠定了良好的基础。 6.4.4 张颖设计小结 通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，从实践中验证理论，从而提高自己的实际动手能力和独立思考的能力。当然，在设计的过程中遇到许许多多的问题，可以说得是困难重重，毕竟这是一次课程设计，需要掌握的知识面比较广，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，通过这次课程设计之后，一定把以前所学过的知识重新温故。7附录 课题任务分工A-1课题程序设计分工学号姓名程序设计函数原型、类功能说明20133989王健1. void LeftBalance(BSTree &T); 2. void RightBalance(BSTree &T);3. 主函数1.对以指针T所指结点为根的二叉树作左平衡旋转处理，本算法结束时，指针T指向新的根结点2.对以指针T所指结点为根的二叉树作右平衡旋转处理，本算法结束时，指