广工数据结构课设

课程设计报告课程名称 数据结构课程设计学院 计算机学院专业班级 学号 学生姓名 指导教师 苏庆 2015年7月6日一、需求分析程序《平衡二叉树的演示》是对平衡二叉树的创建、插入、删除、查找、合并、分裂功能的实现，以及用凹入表的形式将其展示给用户。（1） 输入的形式是数字，无论对功能的选则还是对数据的录入，都是以数字的形式进行输入，无需使用文件保存数据。输入值得范围在使用过程中会有说明。（2） 输出的形式是在Dos界面进行输出，（3） 程序所能达到的功能：创建一棵非空平衡二叉树创建一棵空的平衡二叉树向平衡二叉树中添加结点从平衡二叉树中删除结点在平衡二叉树中查找结点以凹入表的形式输出一棵二叉树以括号表示法输出一棵二叉树附加功能：F.合并两棵平衡二叉树分裂一棵平衡二叉树二、概要设计（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>8llm<1){system("CLS");InitView();printf("\n\t\t\t 输入错误，请重新输入!!\n");}printf("\n\t\t\t 请输入你的选择：")；scanf("%d",&m);getchar();}return0;}各模块之间的关系主程序模块创建非空

例创建空树添加结点删除结点查找结点合并平衡

二叉树分裂平衡

二叉树退出三、详细设计(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)伪代码：建树操作beginBBSTreeTArrayaa=GetInputToArray();〃获取到输入的数组Whilea!=NULL{InsertAVL(T,a->data)a=>a->next}End插入结点beginif(NULL==T){T->data=eT->bf=EHT->lchild=NULLT->rchild=NULL}elseif(e==T->data){〃书中已存在和e相等的结点returnFALSE;}elseif(e<T->data){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;EndC.删除操作begin〃当被删结点是有两个孩子，且其前驱结点是左孩子时，tag=1staticinttag=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<t->data){ 〃左子树中继续查找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;elseshorter=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;elseshorter=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;EndD.查找操作Beginif(T==NULL)returnNULL;if(e==T->data){returnT;}elseif(e>T->data){returnSearchAVL(T->rchild,e);}else{returnSearchAVL(T->lchild,e);}End合并操作BeginStatustaller=TRUE;Arraya=NULL;a=GetArrayFromTree(T2);while(a!=NULL){taller=TRUE;InsertAVL(T1,a->data,taller);a=a->next;}returnT1;End分裂操作BeginArraya=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.合并操作四、调试分析调试过程中所遇到的问题:运行过程中程序停止运行。遇到这个情况一开始我以为是编译器有问题，但是换了个编译器还是同样的问题，后来我上网查询了有关资料，大概明白了是自己的代码出现了问题。所以只能将新增的代码注释掉，一条一条测试，调试过程很漫长，最后才发现是内存泄露和空指针异常，将指针不适用之后指向为NULL，才把问题解决了。经验和体会a） 在做一个比较大的程序过程中，应该学会边编写程序边运行，即当你完成了一个比较小的功能时便对其调试，这样有助于我们高效地完成项目，而且在调试BUG的过程也可以大大减小其难度。b） 必须要有良好的编程习惯。首先编码风格一定要规范，这样不仅有利于读者和编程者对代码的阅读，更有利于对代码的维护。其次要对代码要细心，比较一些指针的初始化和不需要时指为空，这些都是可以极大减少我们出现BUG的几率。c） 写的程序一定要人性化，现在的应用都讲究与人交互的重要性，其避免不了使用各种炫酷的图形界面，但我们要考虑的是，即便是C语言，没有什么图形界面，我们也一定要考虑人性化的问题。五、使用说明本程序的可执行文件是：平衡二叉树的演示.exe双击exe文件，进入主界面：

然后我们应该先创建一棵非空二叉树或者是空的二叉树，输入1或者2,按回车键，此处我们输入1,如下:TOC\o"1-5"\h\z* 欢迎来到平衡二叉树的演示界面 *1•创建一愣斐空二叉网 *创建一棵空的二叉树 *添加结点5二叉树Z吾富蒯平1"5二叉树am.说明：」夜捌EE德5地亟案坦差尊输△昉直箍幽？am.一— — _ —E,系统自动创建一棵空树!功能六「七写所能二；'二一兰"西，五无关联厂并相互独豆，请输入你的选择：1请输入生成树的数字序列〈按，回车建结束》4.此时，程序提示我们输入树的序列，我们可以以此输入数字，不同数字用空格隔开，按回车表示输入完成，例如，我们输入102030405060回车，得到如下，程序提示我们创建成功，并输出了该平衡二叉树，此时按任意键返回。**说明1234%*荻迎来到平衡二叉树的演示界面12345&7S叉还叉叉----二二vffi1Epul-LL工TTT1ZC『裳3箱颗-建挂血舞并希创创漆ffll查合争厂乂J二义**说明1234%*荻迎来到平衡二叉树的演示界面12345&7S叉还叉叉----二二vffi1Epul-LL工TTT1ZC『裳3箱颗-建挂血舞并希创创漆ffll查合争厂乂J二义虹系荽自动创建一棵空树!你的平衡二叉树为,

4C2Cl.,35,5Ctt,B>>S*平衡二一叉树展示**6<bfs0>5Ch£s-l>4<bf：0>3<bf=0>2Ch£=©>l(bf=0>•创建成功!请按任意键返回上一层.…

返回到了首页，此时我们可以输入3,往此树中添加结点，按回车确认。此时，程序会把平衡二叉树展示出来，然后提示用户输入要删除的元素，假如我们要添加5，输入5，按回车。欢迎来到平衡二叉树的演示界面说明，「本程序平衡二莲寸的元素12345678平平霜点点点棵颗--结结结两-建建如鉴并列茁添紫合盆.I:叉叉----空的悲工叉叉说明，「本程序平衡二莲寸的元素12345678平平霜点点点棵颗--结结结两-建建如鉴并列茁添紫合盆.I:叉叉----空的悲工叉叉----为釐仃三

均空进.一可密餐5意括”棵空树'请输入你的选择：3你的平衡二叉树为：4<2<1,3>,5<#,6)>6<bf：0>5<bf：-1>4<bf：0>3<bf：0>2<bf：0)l(b£：0>请输入要添加的元素：5添加失败！

请输入你的选择:

此时提示添加失败，是因为5重复了，假如我们重新添加，选择功能3,此时添加8,按回车，得到如下：7.提示添加成功，此时我们再此时删除功能，我们选择功能4，得到如下界面，假如我们要删除4，输入4，按回车:得到界面如下，提示删除成功，我们发现平衡二叉树更新了，每个节点的平衡因子也更新了。你的平衡二叉树为：3<2<1,#>,6<5,8>>8<bf：@>6<bf：0>5<bf：0>3<bf：0>2<bf：1>l<bf我们再输入5，测试查找功能。提示输入查找元素，我们输入6。你的平衡二叉树为中瞻瞒,0〉〉8<bf：0>6<bf；0>5<b£：G>3<bf：0>2<bf：1>l<bfs0>平衡二又树你的查找子树为8<bf：0>6<bf：0>5<h£:0>查找子树请爵漓驾择：■

程序便把原来的平衡二叉树和以查找结点为根节点的子树都输出来。此时我们再运行合并平衡二叉树的功能。选择6,回车。欢迎来到平衡二叉树的演示界面W添〃合盆123456781=80*加结点W伊口杼*开两棵平食二叉岐裂一颗平稀二叉树:1234二K建与需创七眉丁、一^■.'■■115序警六程入不能本薯功-RI数诉添，为釐仃二均空进，M一小加四欢迎来到平衡二叉树的演示界面W添〃合盆123456781=80*加结点W伊口杼*开两棵平食二叉岐裂一颗平稀二叉树:1234二K建与需创七眉丁、一^■.'■■115序警六程入不能本薯功-RI数诉添，为釐仃二均空进，M一小加四鼬遍互独立i假系统自动创建一棵空树!请输入你的选择：6请输人树口的数字序列《按，回车躇结束》11.此时系统提示我们输入第一棵树的序列，假如我们输入12345然后系统会提示我们输入第二棵树的序列，假如我们输入789请输入树T1的教字序列〈按」回车键，结束“123456请输入树塑的救字序列〈按』回车键，结束789_12.程序会把12.程序会把T1T2T3用括号表示法输出此时提示按回车会输出要合并的两棵树和合并后的树的凹入表平衡二叉树T1为:9Cbf：0>8<bf：0>7<bf：0>6<bf：-1>5<bf：0>4<bf：-l>3<bf：0>2<bf：0>l<bf：0>平衡二叉树T2为:9<bf：0>8<bf：0>7<bf：0>合并后的平彳野二叉树T3为:9<bf：0>8<bf：0>7<bf：0>6<bf：-1>5<bf：0>4<bf：-1>3<bf：0>2<bf：0>l<bf：0>请按任意键返回上一层…

我们再输入7来此时分裂一棵平衡二叉树的功能欢迎来到平梅二叉树的演示界面一：----空的普一：----空的普一：一.：,叉叉----flfl平平疆占苫g点棵颗--结结菁-建建加隽开列茁耳添耍合八县12345678:1透建庆芳街*鸠元素起为此时输出的是:分割后小于等于S:1透建庆芳街*鸠元素起为此时输出的是:分割后小于等于S的平衡二叉树T2为:2<1,4<3,5»思住瞰嘻找操作，系第自动创建一棵空树!,四，五无天联，开相互独豆？请输入你的选择：？请输入树的数子序列〈按，回车键，结束n此时提示我们输入树的序列，输入完将提示我们输入x的值，即树T将分裂成一棵均是小于等于x的树，和一棵均大于x的树。假如我们测试数据是：T:12345678910 x:5分菖房壬于曲平衡二叉祐3彖按回车键查看T1,T2,T3的凹入表….分割前的平衡二叉.树T1为:4<2<1,3>,8<6<5,7),9<#,10>»一务曲奇南港三反&去二19Cb£：0>9<bF：-l>BClifs0>7Cbf：B>6<bf：9)5<bf：B>4<hf：-t>3<bf：9>2Cbf：0>l<bf：0)分割后小于等于5的平衢二叉树T2为:4<2<1,3>^<6<5.7>„9<#„10>»芬菖房不苇至等:而苹新三灵两；；；5<bf：B)4(1]£:0)3<h£s0)2CJjf：-1>l<hf=3)分割后大于S的平衡二叉树T3为：4<2(1.3>,8<6<5.7>.9<».10>»10<hf：0>9<h£:-l>BCb£：0>7<hf=0>6<hf=-1>甬茹蓄嬴云百工二直二最后便是退出功能，选择8,程序提示我们是否退出，输入Y(y)退出程序，输入N(n)返回主界面欢迎来到平衡二叉树的演示界面说明12345678XX--空的非空X民----说明12345678XX--空的非空X民----平平黑点占罟g棵颗--结结结两-建建加嚎开番添馨一合蕾:1.本程序平衡元素均为数字工—素可可用；工格W隔2•鲤入乾据甲..=一 4•功能K,壬与功能一，一，二，四,果5-

IfeS找案目互独立?拒，系绿自动创建一棵空树!请输尔的诜择，8请选泽:请选泽:六、测试结果测试数据：平衡二叉树T:12345678910添加元素：11删除元素：5查找元素：8你的平衡二叉树为:4<2<1,3>,8<6<5,7>,9<#,10>>>g平衡二叉甜展