二叉平衡树实现学生信息管理系统.docx
- 文档编号:16147508
- 上传时间:2023-07-10
- 格式:DOCX
- 页数:23
- 大小:313.80KB
二叉平衡树实现学生信息管理系统.docx
《二叉平衡树实现学生信息管理系统.docx》由会员分享,可在线阅读,更多相关《二叉平衡树实现学生信息管理系统.docx(23页珍藏版)》请在冰点文库上搜索。
二叉平衡树实现学生信息管理系统
课程设计报告
一、课程设计的目的与要求
1.目的:
应用数据结构和算法来设计相应的程序,培养学生问题求解模块的框架设计和详细设计、相关程序实现和调试能力,完成创新能力和实践能力的训练。
2.要求:
用高级程序设计语言C编码,用VC++开发平台调试。
二、设计正文
(一)课程设计题目
(二)需求分析
(三)概要设计
(四)详细设计
(五)调试分析
(六)使用说明
三、课程设计总结或结论
1.完成的工作
2.未完成的工作
3.所需做的改进
四、参考文献
[1]作者1,作者2书名.出版单位,版本.出版日期
附录(设计流程图、程序、测试数据等)
一、课程设计题目
编制一个用二叉平衡树实现学生信息管理系统的程序,所有信息用文件保存。
二、需求分析
本演示程序在VC++环境下用C语言编写,利用二叉平衡树完成学生信息管理系统信息的输入,显示所有的学生信息,查询指定学生信息,删除学生信息,并将所有信息以TXT文档形式保存。
1、输入的形式和输入值的范围:
创建时首先按照要求依次输入相应信息;
插入结点时需要输入插入的信息;
删除结点时输入删除结点的关键字;
查找时输入查找结点的关键字;
在所有输入中,结点信息学号、姓名、专业、班级、生日为字符串,年龄为整型。
2、输出的形式:
查找操作会输出查找成功时的信息,若不成功怎输出无此信息;
显示操作会按递归遍历显示平衡树上的所有结点信息;
3、程序所能达到的功能:
完成二叉平衡树学生信息管理系统的创建(从键盘中输入并保存到文件中)、插入、删除、查找、显示、保存操作
4、测试数据:
A.创建操作中依次输入1
01黄世晨信安1101191993
y
02许彬信安1101201992
y
03邓志光信安1101201992
n
构建二叉平衡树
输入4
浏览信息
B.查找操作中依次输入5
01
C.删除操作中依次输入3
03
D.插入操作中依次输入2
04曹廷祥信安1101211991
输入4
浏览信息
E.凹入显示操作输入7
F.保存操作输入6
G.退出操作输入0
三、概要设计
1、为了实现上述程序功能,需要定义二叉平衡树的抽象数据类型:
ADTBSTree{
数据对象D:
D是具有相同特性的数据元素的集合。
数据关系R:
若D为空集,则称为空树;
否则:
(1)在D中存在唯一的称为根的数据元素root,
(2)当n>1时,其余结点可分为m(m>0)个互
不相交的有限集T1,T2,…,Tm,其中每一
棵子集本身又是一棵符合本定义的树,
称为根root的子树。
基本操作:
voidcreat(T_N&T)
操作结果:
创建学生信息管理系统二叉平衡树并输入初始信息.
intinsertavl(T_N&T,STUdata)
操作结果:
将信息插入至二叉平衡树中,并调节二叉树平衡
intfind(T_NT,char*x,T_N&f,T_N&c)
初始条件:
二叉平衡树T已存在
操作结果:
查询学生信息
intDeleteavl(T_N&T,char*xuehao)
初始条件:
二叉平衡树T已存在
操作结果:
删除学生信息,并调节二叉树平衡
intdisp(T_NT)
初始条件:
二叉平衡树T已存在
操作结果:
显示学生信息
intmenu()
操作结果:
在屏幕上显示操作菜单
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、函数间的调用关系如下:
四、详细设计
为了实现概要设计中定义的所有的数据类型;对主程序和其他模块写出伪代码算法或者画出流程图;
1、结点类型和指针类型
//结构体定义
//学生
typedefstruct
{
charxuehao[10];
charname[20];
charzhuanye[10];
charbanji[20];
charshengri[20];
intage;
}STU;
//结点
typedefstructTreeNode
{
STUdata;
structTreeNode*lchild,*rchild;
intph;
}TreeNode,*T_N;
2)、主要算法的伪代码或者流程图
//保存
intsave(T_NT,FILE*fp)
{
if(T==NULL)
return0;
else
{
fprintf(fp,"%s\t%s\t%s\t%s\t%d\t%s\t",T->data.xuehao,T->data.name,T->data.zhuanye,T->data.banji,T->data.age,T->data.shengri);
save(T->lchild,fp);
save(T->rchild,fp);
}
}
//插入
intinsertavl(T_N&T,STUdata)
{
if(T==NULL)
{
T=newTreeNode;
T->data=data;
T->lchild=T->rchild=NULL;
T->ph=0;
returnflag=1;
}//如果是空的话就生成新节点并且返回1
else
{
result=strcmp(T->data.xuehao,data.xuehao);
if(result==0)
{
puts("该学号学生已经存在,不能插入");
getch();
flag=0;
}
elseif(result<0)//往右子树方向上插入
{
flag=insertavl(T->rchild,data);//这里传过去的是根的右子树
if(flag==1)
switch(T->ph)
{
case1:
T->ph=0;
flag=0;
break;//直接插入并改变平衡因子,并且改变标识变量flag
case0:
T->ph=-1;
break;//直接插入并改变平衡因子即可
case-1:
if(T->rchild->ph==-1)
{
RRbalance(T);//1,注意分清楚这里面的根结点
T->ph=T->lchild->ph=0;//左旋之后并进行平衡因子的更改
}
elseif(T->rchild->ph==1)
{
if(T->rchild->lchild->ph==0)
{
T->ph=T->rchild->ph=0;
}//7,注意分清这里面的根结点
elseif(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;
}
returnflag;
}
elseif(result>0)//往左子树方向上插入
{
flag=insertavl(T->lchild,data);
if(flag==1)
switch(T->ph)
{
case0:
T->ph=1;
flag=1;
break;
case-1:
T->ph=0;
flag=0;
break;
case1:
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;
}
returnflag;
}
}
}
//查找
intfind(T_NT,char*x,T_N&f,T_N&c)//T为已经存在的树,x为要查找的数据,f,c为将要返回的指针
{
if(T==NULL)
return0;
if(strcmp(T->data.xuehao,x)==0)
{
c=T;
return1;//用返回值来区别是否找到
}
elseif(strcmp(T->data.xuehao,x)<0)//由于根节点上的数据“小于”x的数据,因此到根节点的右子树上寻找
{
f=T;
returnfind(T->rchild,x,f,c);//f应该记得也就是T了
}
else
{
f=T;
returnfind(T->lchild,x,f,c);
}
}
//删除
intDeleteavl(T_N&T,char*xuehao)
{
if(T==NULL)
{
puts("没有该学生");
getch();
return0;
}
result=strcmp(T->data.xuehao,xuehao);
if(result>0)//往左子树方向上删除
{
flag=Deleteavl(T->lchild,xuehao);
if(flag==1)
flag=Leftadjust(T);
}
elseif(result<0)//往右子树方向上删除
{
flag=Deleteavl(T->rchild,xuehao);
if(flag==1)
flag=Rightadjust(T);
}
else
{
if(T->lchild==NULL)
{
p=T;
T=T->rchild;
deletep;
flag=1;
}
elseif(T->rchild==NULL)
{
p=T;
T=T->lchild;
deletep;
flag=1;
}
else
{
flag=Del(T,T->lchild);
if(flag==1)
Leftadjust(T);
}
returnflag;
}
return0;
}
//显示
intdisp(T_NT)
{
if(T==NULL)
return0;
else
{
disp(T->lchild);
printf("学号:
%s\t姓名:
%s\t专业:
%s\t班级:
%s\t生日:
%s\t年龄:
%d\n",T->data.xuehao,T->data.name,T->data.zhuanye,T->data.banji,T->data.shengri,T->data.age);
disp(T->rchild);
}
}
//创建
voidcreat(T_N&T)
{
do{
puts("输入学生\n学号姓名专业班级年龄生日:
");
scanf("%s%s%s%s%d%s",x.xuehao,x.name,x.zhuanye,x.banji,&x.age,x.shengri);
getchar();
insertavl(T,x);
printf("是否继续(y/n):
");
ch=getchar();
}while(ch=='Y'||ch=='y');
}
voidprint(T_NT,intindent)
{
if(T==NULL)return;
else
{
for(i=0;i printf("--"); printf("学号: %s\t姓名: %s\t专业: %s\t班级: %s\t生日: %s\t年龄: %d\n",T->data.xuehao,T->data.name,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.创建操作中依次输入1 01黄世晨信安1101191993 y 02许彬信安1101201992 y 03邓志光信安1101201992 n 构建二叉平衡树 输入4 浏览信息 结果: 完成输入三人的信息 B.查找操作中依次输入5 01 结果: 成功查找01号学生信息 C.删除操作中依次输入3 03 输入4 浏览信息 结果: 成功删除03号学生信息 D.插入操作中依次输入2 04曹廷祥信安1101211991 输入4 浏览信息 结果: 成功插入04号学生信息 E.凹入显示操作输入7 结果: 显示二叉平衡树 F.保存操作输入6 结果: 成功保存 G.退出操作输入0 结果: 安全退出程序
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉 平衡 实现 学生 信息管理 系统
![提示](https://static.bingdoc.com/images/bang_tan.gif)