广工数据结构课设平衡二叉树演示文档尾部含源码下载地址.docx
- 文档编号:9961586
- 上传时间:2023-05-22
- 格式:DOCX
- 页数:33
- 大小:310.82KB
广工数据结构课设平衡二叉树演示文档尾部含源码下载地址.docx
《广工数据结构课设平衡二叉树演示文档尾部含源码下载地址.docx》由会员分享,可在线阅读,更多相关《广工数据结构课设平衡二叉树演示文档尾部含源码下载地址.docx(33页珍藏版)》请在冰点文库上搜索。
广工数据结构课设平衡二叉树演示文档尾部含源码下载地址
课程设计报告
课程名称数据结构课程设计
学院计算机学院
专业班级计科9班
学号
学生姓名
指导教师苏庆
2015年7月6日
一、需求分析
程序《平衡二叉树的演示》是对平衡二叉树的创建、插入、删除、查找、合并、分裂功能的实现,以及用凹入表的形式将其展示给用户。
(1)输入的形式是数字,无论对功能的选则还是对数据的录入,都是以数字的形式进行输入,无需使用文件保存数据。
输入值得范围在使用过程中会有说明。
(2)输出的形式是在Dos界面进行输出,
(3)程序所能达到的功能:
A.创建一棵非空平衡二叉树
B.创建一棵空的平衡二叉树
C.向平衡二叉树中添加结点
D.从平衡二叉树中删除结点
E.在平衡二叉树中查找结点
F.以凹入表的形式输出一棵二叉树
G.以括号表示法输出一棵二叉树
附加功能:
F.合并两棵平衡二叉树
H.分裂一棵平衡二叉树
二、概要设计
(1)本程序涉及到的数据类型有:
链栈,链队列,平衡二叉树,
结构体数组
(2)主程序是负责对各个功能进行展示,然后根据输入来选择进行相对应的功能,代码如下:
intmain(){
intm;
BBSTreeT=NULL;
SetColor();
InitView();
printf("\n\t\t\t请输入你的选择:
");
scanf("%d",&m);
getchar();
while
(1){
switch(m){
case1:
T=item_1();
break;
case2:
item_2(T);
break;
case3:
item_3(T);
break;
case4:
item_4(T);
break;
case5:
item_5(T);
break;
case6:
item_6();
break;
case7:
item_7();
break;
}
if(m==8){
item_8();
break;
}elseif(m>8||m<1){
system("CLS");
InitView();
printf("\n\t\t\t输入错误,请重新输入!
!
\n");
}
printf("\n\t\t\t请输入你的选择:
");
scanf("%d",&m);
getchar();
}
return0;
}
(3)各模块之间的关系
三、详细设计
(1)数据类型的定义
/*存放输入数据的数组结构体*/
typedefstructArrayNode{
RcdTypedata;
ArrayNode*next;
}ArrayNode,*Array;
/*平衡二叉树结构体*/
typedefstructBBSTNode{
RcdTypedata;
intbf;
BBSTNode*lchild,*rchild;
}BBSTNode,*BBSTree;
/*链队列结构体*/
typedefstructLQNode{
BBSTreeelem;
structLQNode*next;
}LQNode,*QueuePtr;
/*队列结点结构体*/
typedefstruct{
QueuePtrfront;
QueuePtrrear;
}LQueue;
/*栈结点结构体*/
typedefstructLSNode{
BBSTreedata;//数据域
structLSNode*next;//指针域
}LSNode,*LStack;//结点和链栈类型
(2)伪代码:
A.建树操作
begin
BBSTreeT
Arraya
a=GetInputToArray();//获取到输入的数组
Whilea!
=NULL{
InsertAVL(T,a->data)
a=>a->next
}
End
B.插入结点
begin
if(NULL==T){
T->data=e
T->bf=EH
T->lchild=NULL
T->rchild=NULL
}elseif(e==T->data){//书中已存在和e相等的结点
returnFALSE;
}elseif(e
if(!
InsertAVL(T->lchild,e))returnFALSE;
if(TRUE==taller){
switch(T->bf){
caseLH:
LeftBalance(T);taller=FALSE;break;
caseEH:
T->bf=LH;taller=TRUE;break;
caseRH:
T->bf=EH;taller=FALSE;break;
}
}
}else{
if(FALSE==InsertAVL(T->rchild,e))returnFALSE;
if(TRUE==taller){
switch(T->bf){
caseLH:
T->bf=EH;taller=FALSE;break;
caseEH:
T->bf=RH;taller=TRUE;break;
caseRH:
RightBalance(T);taller=FALSE;break;
}
}
}
returnTRUE;
End
C.删除操作
begin
//当被删结点是有两个孩子,且其前驱结点是左孩子时,tag=1
staticinttag=0;
if(t==NULL){
returnFALSE;//如果不存在元素,返回失败
}elseif(e==t->data){
BBSTNode*q=NULL;
//如果该结点只有一个孩子,则将自子树取代该结点
if(t->lchild==NULL){
q=t;
t=t->rchild;
free(q);
shorter=TRUE;
}
elseif(t->rchild==NULL){
q=t;
t=t->lchild;
free(q);
shorter=TRUE;
}
//如果被删结点有两个孩子,则找到结点的前驱结点,
//并将前驱结点的值赋给该结点,然后删除前驱结点
else{
q=t->lchild;
while(q->rchild){
q=q->rchild;
}
t->data=q->data;
if(t->lchild->data==q->data){
tag=1;
}
DeleteAVL(t->lchild,q->data,shorter);
if(tag==1){
BBSTreer=t->rchild;
if(NULL==r)t->bf=0;
else{
switch(r->bf){
caseEH:
t->bf=-1;break;
default:
RightBalance(t);break;
}
}
}
}
}elseif(e
if(!
DeleteAVL(t->lchild,e,shorter)){
returnFALSE;
}
//删除完结点之后,调整结点的平衡因子
if(shorter&&(tag==0)){
switch(t->bf){
caseLH:
t->bf=EH;
shorter=TRUE;
break;
caseEH:
t->bf=RH;
shorter=FALSE;
break;
//如果本来就是右子树较高,删除之后就不平衡,需要做右平衡操作
caseRH:
RightBalance(t);//右平衡处理
if(t->rchild->bf==EH)
shorter=FALSE;
else
shorter=TRUE;
break;
}
}
}elseif(e>t->data){//右子树中继续查找
if(!
DeleteAVL(t->rchild,e,shorter)){
returnFALSE;
}
//删除完结点之后,调整结点的平衡因子
if(shorter&&(tag==0)){
switch(t->bf){
caseLH:
LeftBalance(t);//左平衡处理
if(t->lchild->bf==EH)
shorter=FALSE;
else
shorter=TRUE;
break;
caseEH:
t->bf=LH;
shorter=FALSE;
break;
caseRH:
t->bf=EH;
shorter=TRUE;
break;
}
}
if(tag==1){
intdepthLeft=BBSTreeDepth(t->lchild);
intdepthRight=BBSTreeDepth(t->rchild);
t->bf=depthLeft-depthRight;
}
}
returnTRUE;
End
D.查找操作
Begin
if(T==NULL)returnNULL;
if(e==T->data){
returnT;
}elseif(e>T->data){
returnSearchAVL(T->rchild,e);
}else{
returnSearchAVL(T->lchild,e);
}
End
E.合并操作
Begin
Statustaller=TRUE;
Arraya=NULL;
a=GetArrayFromTree(T2);
while(a!
=NULL){
taller=TRUE;
InsertAVL(T1,a->data,taller);
a=a->next;
}
returnT1;
End
F.分裂操作
Begin
Arraya=NULL;
Statustaller;
a=GetArrayFromTree(Tt1);//获取到树转化为的数组
if(Tt1==NULL)returnFALSE;
else{
while(a!
=NULL){
if(a->data<=x){
taller=TRUE;
InsertAVL(Tt2,a->data,taller);
a=a->next;
}else{
taller=TRUE;
InsertAVL(Tt3,a->data,taller);
a=a->next;
}
}
}
returnTRUE;
End
(3)关系图
A.建树操作
B.添加结点操作
C.删除结点操作
D.查找结点操作
E.合并操作
F.分裂操作
四、调试分析
1.调试过程中所遇到的问题:
运行过程中程序停止运行。
遇到这个情况一开始我以为是编译器有问题,但是换了个编译器还是同样的问题,后来我上网查询了有关资料,大概明白了是自己的代码出现了问题。
所以只能将新增的代码注释掉,一条一条测试,调试过程很漫长,最后才发现是内存泄露和空指针异常,将指针不适用之后指向为NULL,才把问题解决了。
2.经验和体会
a)在做一个比较大的程序过程中,应该学会边编写程序边运行,即当你完成了一个比较小的功能时便对其调试,这样有助于我们高效地完成项目,而且在调试BUG的过程也可以大大减小其难度。
b)必须要有良好的编程习惯。
首先编码风格一定要规范,这样不仅有利于读者和编程者对代码的阅读,更有利于对代码的维护。
其次要对代码要细心,比较一些指针的初始化和不需要时指为空,这些都是可以极大减少我们出现BUG的几率。
c)写的程序一定要人性化,现在的应用都讲究与人交互的重要性,其避免不了使用各种炫酷的图形界面,但我们要考虑的是,即便是C语言,没有什么图形界面,我们也一定要考虑人性化的问题。
五、使用说明
1.本程序的可执行文件是:
平衡二叉树的演示.exe
2.双击exe文件,进入主界面:
3.然后我们应该先创建一棵非空二叉树或者是空的二叉树,输入1或者2,按回车键,此处我们输入1,如下:
4.此时,程序提示我们输入树的序列,我们可以以此输入数字,不同数字用空格隔开,按回车表示输入完成,例如,我们输入102030405060回车,得到如下,程序提示我们创建成功,并输出了该平衡二叉树,此时按任意键返回。
5.返回到了首页,此时我们可以输入3,往此树中添加结点,按回车确认。
此时,程序会把平衡二叉树展示出来,然后提示用户输入要删除的元素,假如我们要添加5,输入5,按回车。
6.此时提示添加失败,是因为5重复了,假如我们重新添加,选择功能3,此时添加8,按回车,得到如下:
7.提示添加成功,此时我们再此时删除功能,我们选择功能4,得到如下界面,假如我们要删除4,输入4,按回车:
8.得到界面如下,提示删除成功,我们发现平衡二叉树更新了,每个节点的平衡因子也更新了。
9.我们再输入5,测试查找功能。
提示输入查找元素,我们输入6。
10.程序便把原来的平衡二叉树和以查找结点为根节点的子树都输出来。
此时我们再运行合并平衡二叉树的功能。
选择6,回车。
11.此时系统提示我们输入第一棵树的序列,假如我们输入12345
然后系统会提示我们输入第二棵树的序列,假如我们输入789
12.程序会把T1T2T3用括号表示法输出
13.此时提示按回车会输出要合并的两棵树和合并后的树的凹入表
14.我们再输入7来此时分裂一棵平衡二叉树的功能
15.此时提示我们输入树的序列,输入完将提示我们输入x的值,即树T将分裂成一棵均是小于等于x的树,和一棵均大于x的树。
假如我们测试数据是:
T:
12345678910x:
5
此时输出的是:
16.最后便是退出功能,选择8,程序提示我们是否退出,
输入Y(y)退出程序,输入N(n)返回主界面
六、测试结果
测试数据:
平衡二叉树T:
12345678910
添加元素:
11
删除元素:
5
查找元素:
8
添加11
删除8
测试数据
T1:
5841062T2:
562034
合并两树得到:
测试数据
T:
-2080901068x:
5
分裂平衡二叉树得到:
七、附录
源程序文件名清单:
dataStruction.cpp//源程序代码
AVL_head.h//自定义的头文件
平衡二叉树的演示.exe//可执行文件
源码下载地址:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 平衡 二叉 演示 文档 尾部 源码 下载 地址