二叉平衡树实现学生信息管理系统.doc

课程设计报告( 20112012年度第2学期)实验名称：数据结构与算法 题 目：二叉平衡树学生信息管理系统 院 系：控制与计算机工程学院 班 级：信安1101 学 号：1111290110 学生姓名：黄世晨 指导教师：焦润海 设计周数： 1周 成 绩： 日期： 2012年 6 月 28 日 课程设计报告一、课程设计的目的与要求1 目的: 应用数据结构和算法来设计相应的程序，培养学生问题求解模块的框架设计和详细设计、相关程序实现和调试能力，完成创新能力和实践能力的训练。2 要求: 用高级程序设计语言C编码，用VC+开发平台调试。二、设计正文（一） 课程设计题目（二） 需求分析（三） 概要设计（四） 详细设计（五） 调试分析（六） 使用说明三、课程设计总结或结论1 完成的工作2 未完成的工作3 所需做的改进四、参考文献 1 作者1, 作者2. 书名. 出版单位, 版本. 出版日期附录（设计流程图、程序、测试数据等） 一、课程设计题目编制一个用二叉平衡树实现学生信息管理系统的程序，所有信息用文件保存。二、需求分析本演示程序在VC+环境下用C语言编写，利用二叉平衡树完成学生信息管理系统信息的输入，显示所有的学生信息，查询指定学生信息，删除学生信息，并将所有信息以TXT文档形式保存。1、 输入的形式和输入值的范围：创建时首先按照要求依次输入相应信息；插入结点时需要输入插入的信息；删除结点时输入删除结点的关键字；查找时输入查找结点的关键字；在所有输入中，结点信息学号、姓名、专业、班级、生日为字符串，年龄为整型。2、 输出的形式：查找操作会输出查找成功时的信息，若不成功怎输出无此信息；显示操作会按递归遍历显示平衡树上的所有结点信息；3、 程序所能达到的功能：完成二叉平衡树学生信息管理系统的创建（从键盘中输入并保存到文件中）、插入、删除、查找、显示、保存操作4、测试数据：A 创建操作中依次输入 101 黄世晨 信安 1101 19 1993 y 02 许彬 信安 1101 20 1992 y 03 邓志光 信安 1101 20 1992 n 构建二叉平衡树 输入 4 浏览信息B 查找操作中依次输入 5 01C 删除操作中依次输入 3 03D插入操作中依次输入 2 04 曹廷祥 信安 1101 21 1991 输入 4 浏览信息E 凹入显示操作输入 7F 保存操作输入 6G 退出操作输入 0三、概要设计 1、为了实现上述程序功能，需要定义二叉平衡树的抽象数据类型：ADT BSTree 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D为空集，则称为空树； 否则: (1) 在D中存在唯一的称为根的数据元素root, (2) 当n1时，其余结点可分为m (m0)个互 不相交的有限集T1, T2, , Tm, 其中每一 棵子集本身又是一棵符合本定义的树， 称为根root的子树。基本操作：void creat(T_N &T)操作结果：创建学生信息管理系统二叉平衡树并输入初始信息.int insertavl(T_N &T,STU data)操作结果：将信息插入至二叉平衡树中，并调节二叉树平衡int find(T_N T,char *x,T_N &f,T_N &c)初始条件：二叉平衡树T已存在操作结果：查询学生信息 int Deleteavl(T_N &T,char *xuehao)初始条件：二叉平衡树T已存在操作结果：删除学生信息，并调节二叉树平衡 int disp(T_N T) 初始条件：二叉平衡树T已存在操作结果：显示学生信息int menu()操作结果：在屏幕上显示操作菜单 2、本程序包含16个函数：1 主函数 main()2 删除结点并调平函数Deleteavl(T_N &,char * );3 删除辅助函数Del(T_N ,T_N &);4 调平函数LLbalance(T_N &);5 调平函数RRbalance(T_N &);6 调平函数LRbalance(T_N &);7 调平函数RLbalance(T_N &);8 查找函数find(T_N ,char *,T_N &,T_N &);9 插入信息并调平函数insertavl(T_N &,STU);10 在右子树上删除后的调平函数Rightadjust(T_N &);11 在左子树上删除后的调平函数Leftadjust(T_N &);12 菜单函数menu();13 保存函数save(T_N,FILE *);14 凹入显示二叉平衡树函数print(T_N ,int );15 创建函数creat(T_N &);16 显示函数disp(T_N );3、函数间的调用关系如下：mainmenucreatinsertavlDeleteavldispfindsaveprint四、详细设计为了实现概要设计中定义的所有的数据类型；对主程序和其他模块写出伪代码算法或者画出流程图； 1、结点类型和指针类型/结构体定义/学生typedef structchar xuehao10;char name20;char zhuanye10;char banji20;char shengri20;int age;STU;/结点typedef struct TreeNodeSTU data;struct TreeNode *lchild,*rchild;int ph;TreeNode,*T_N;2)、主要算法的伪代码或者流程图/保存int save(T_N T,FILE *fp)if(T=NULL)return 0;elsefprintf(fp,%st%st%st%st%dt%st,T-data.xuehao,T-,T-data.zhuanye,T-data.banji,T-data.age,T-data.shengri);save(T-lchild,fp);save(T-rchild,fp);/插入int insertavl(T_N &T,STU data)if(T=NULL)T=new TreeNode; T-data=data;T-lchild=T-rchild=NULL;T-ph=0;return flag=1;/如果是空的话就生成新节点并且返回1elseresult=strcmp(T-data.xuehao,data.xuehao);if(result=0)puts(该学号学生已经存在，不能插入);getch();flag=0;else if(resultrchild,data);/这里传过去的是根的右子树if(flag=1)switch(T-ph)case 1:T-ph=0;flag=0;break;/直接插入并改变平衡因子，并且改变标识变量flagcase 0:T-ph=-1;break;/直接插入并改变平衡因子即可case -1:if(T-rchild-ph=-1)RRbalance(T);/1，注意分清楚这里面的根结点T-ph=T-lchild-ph=0;/左旋之后并进行平衡因子的更改else if(T-rchild-ph=1)if(T-rchild-lchild-ph=0)T-ph=T-rchild-ph=0;/7,注意分清这里面的根结点else if(T-rchild-lchild-ph=1)T-ph=0;T-rchild-ph=-1;T-rchild-lchild-ph=0;/3,注意分清这里面的根结点if(T-rchild-lchild-ph=-1)T-ph=1;T-rchild-ph=0;T-rchild-lchild-ph=0;/2,注意分清这里面的根结点RLbalance(T);/这里要分情况讨论是因为旋转过后平衡因子的改变是不一样的flag=0;break;return flag;else if(result0)/往左子树方向上插入flag=insertavl(T-lchild,data);if(flag=1)switch(T-ph) case 0:T-ph=1;flag=1;break;case -1:T-ph=0;flag=0;break;case 1:if(T-lchild-ph=1)LLbalance(T);T-ph=T-rchild-ph=0;/4,注意分清这里面的根结点if(T-lchild-ph=-1)if(T-lchild-rchild-ph=-1)T-ph=0;T-lchild-ph=1;T-lchild-rchild-ph=0;/5,注意分清这里面的根结点if(T-lchild-rchild-ph=1)T-ph=-1;T-lchild-ph=0;T-lchild-rchild-ph=0;/6,注意分清这里面的根结点if(T-lchild-rchild-ph=0)T-ph=T-lchild-ph=0;/8,注意分清这里面的根结点LRbalance(T);flag=0;break;return flag;/查找int find(T_N T,char *x,T_N &f,T_N &c)/T为已经存在的树，x为要查找的数据，f,c为将要返回的指针 if(T=NULL)return 0;if(strcmp(T-data.xuehao,x)=0)c=T;return 1;/用返回值来区别是否找到else if(strcmp(T-data.xuehao,x)rchild,x,f,c);/f应该记得也就是T了else f=T;return find(T-lchild,x,f,c);/删除int Deleteavl(T_N &T,char *xuehao)if(T=NULL)puts(没有该学生);getch();return 0;result=strcmp(T-data.xuehao,xuehao);if(result0)/往左子树方向上删除flag=Deleteavl(T-lchild,xuehao);if(flag=1)flag=Leftadjust(T);else if(resultrchild,xuehao);if(flag=1)flag=Rightadjust(T);elseif(T-lchild=NULL)p=T;T=T-rchild;delete p; flag=1;else if(T-rchild=NULL)p=T;T=T-lchild;delete p;flag=1;elseflag=Del(T,T-lchild);if(flag=1)Leftadjust(T);return flag;return 0;/显示int disp(T_N T)if(T=NULL)return 0;elsedisp(T-lchild);printf(学号：%st姓名：%st专业：%st班级：%st生日：%st年龄：%dn,T-data.xuehao,T-,T-data.zhuanye,T-data.banji,T-data.shengri,T-data.age);disp(T-rchild);/创建void creat(T_N &T)do puts(输入学生n学号 姓名 专业 班级 年龄 生日:); scanf(%s%s%s%s%d%s,x.xuehao,,x.zhuanye,x.banji,&x.age,x.shengri);getchar();insertavl(T,x); printf(是否继续（y/n）：);ch=getchar();while(ch=Y | ch=y);void print(T_N T,int indent) if(T=NULL ) return;elsefor(i=0;idata.xuehao,T-,T-data.zhuanye,T-data.banji,T-data.shengri,T-data.age);print(T-lchild,indent+1);print(T-rchild,indent+1);五、 调试分析1、原程序在结束创建时需输入五次#才能结束，后调整为“y/n”判断是否继续。六、使用说明程序名为二叉平衡树_学生信息管理系统.exe，运行环境为VC+。程序执行后显示 +-+ | | | 欢迎使用学生信息管理系统 | | | +-+ 温馨提示：为保证您的操作得到保存，请按正常顺序退出系统 - + 学生信息管理系统 + - + 1-建立数据存储 + + 2-插入学生信息 + + 3-删除学生信息 + + 4-浏览学生信息 + + 5-查询学生信息 + + 6-保存学生信息 + + 7-查二叉平衡树 + + 0-安全退出系统 + +*+ -请输入您的选择：在select后输入数字选择执行不同的功能。要求首先输入足够多的插入元素，才可以进行其他的操作。选择0：退出程序选择1：创建系统并输入初始信息选择2：插入新信息选择3：删除指定学生信息 选择4：浏览全部学生信息选择5：查询指定学生信息选择6：保存全部学生信息选择7：查看二叉平衡树（凹入显示）七、测试结果A 创建操作中依次输入 101 黄世晨