c语言课程设计.docx

《c语言课程设计.docx》由会员分享，可在线阅读，更多相关《c语言课程设计.docx（28页珍藏版）》请在第一文库网上搜索。

1、课程设计报告课程设计名称：数据结构课程设计课程设计题目：不带父亲结点的平衡二叉树的建立院（系）：计算机学院专业：计算机科学与技术班级：学号：姓名指导教师:1需求分析21.1 问题描述21.2 问题理解22系统设计32.1 总体方案设计3数据结构设计3模块划分3函数表42.2 系统流程图5平衡二叉树的建立5二叉树结点的插入6左平衡操作7右平衡操作8树形输出93调试分析103.1 函数组建问题103.2 运行问题104测试及运行结果114.1 主界面114.2 创建及结果12参考文献13附录（程序清单）141需求分析1.1 问题描述平衡二叉树又叫AV1树，它或则是一颗空树，或则是具有下列性质的二叉

2、：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过U若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子可能是-1、0和1,只要二叉树上有一个结点的平衡因子的绝对值大于1,则该二叉树就是不平衡的。从键盘上输入一个整数序列，建立一科平衡二叉树。要求：（1）要能够形象方便地观察树的结构；（2）要能够形象地演示树的平衡过程；（3）课程设计报告必须符合课程设计报告规范；（4）提交合格的课设报告后，经指导教师测试（验收）程序，课设完成。12问题理解按照平衡二叉树的概念，结合教科书的内容，进行二叉树的建立，并且能够完成树形

3、的输出。二叉树色建立较为简单，书上有介绍并且能搞完成建立，充分利用递归就能完成。而二叉树的树形输出就较为困难，需要仔细思考，充分利用二叉树的结构特点，以此为基本完成课设题目的要求。2系统设计2.1 总体方案设计2.1.1 数据结构设计不带父亲结点的平衡二叉树的储存结构如下：typedefstructBiTNode(intdata;intbf;平衡因子structBiTNode*1Chi1d,*rchi1d;左、右孩子指针BiTNode,*BiTree;2.1.2 模块划分本程序共分为两个版块，分别是信息录入、建立平衡二叉树和输出。模块划分如图2.1所示：图2.1平衡二叉树模块划分原理框图函数名

4、称函数原型主要功能Mainvoidmain()主函数InitBitreestatusInitBiTree(BiTree&T)初始化二叉树TraverseBiTreeStatusTraverseBiTree(BiTree&T)树形输出Depthintdepth(BiTree&T)求树的深度表2.1函数表2.2系统流程图2.2.1平衡二叉树的建立图2.2平衡二叉树的建立2.6树形输出3调试分析3.1 函数组建问题在编写函数时，遇到了多种选择，但是往往选择的都有或多或少的问题，导致在调用时出现许多问题。经过多次调试最终编写出符合条件的函数。例如，对于函数的类型就时常搞混乱，不知道什么时候用Void类

5、型，什么时候用StatUS类型。除此以外，在函数调用时经常将返回值的类型弄混。这些问题给程序的编写带来了很大的困扰。3.2 运行问题在运行时，一开始都会有许多的语法错误，比如函数定义的错误，结构体定义错误等等，还经常将等符号漏掉或错用。不过经过细心修改，这些问题都得到了解决。经过一番努力，语法错误没有了，但在算法上的错误还存在，这是比较头痛的，例如循环队列的编写、递归算法的运用等等。在循环队列的编写中，对于判空和判满把握的不好，在进队和出队过程中，队头和队尾指针的改变不满足循环队列的要求。而对于递归算法这是经常将我的头绕晕，使我不能很快的找到问题的根源，浪费了很多时间。不过经过一次次的演算、验

6、证，最终达到了课设题目的要求。4测试及运行结果4.1主界面显示主界面，输入所要进行的操作。4.2创建及结果按提示输入一组数，得到创建过程和结果。参考文献1谭浩强等.C语言程序设计M.北京:清华大学出版社,20012金永平.数据结构（C+描述）M.北京:清华大学出版社,20053严蔚敏,吴伟明.数据结构（C语言版）M.北京清华大学出版社,20074吕国英.算法设计与分析M.天津科技大学出版社,20065李兰友,TurboC实用图形程序设计M.天津科技翻译出版社，1994附录（程序清单）#inc1udeinc1ude#inc1ude#inc1udeinc1udedefine1H+1defineEH

7、0defineRH-1#defineNU110defineQUeUe_INr1S1ZE100JtdefineSE1emTypeBiTree#(JefineStatusboo1typedefstructBiTNode(intdata;intbf;structBiTNode*1chi1d,*rchi1d;)BiTNode,*BiTree;intdepth(BiTreeT)(intm,n;if(!T)returnO;m=depth(T-1chiId);m+;n=depth(T-rchiId);n+;if(mn)returnm;e1sereturnn;typedefstruct(BiTree*base

8、;intfront：intrear;SqQueue;StatusInitQueue(SqQueue&Q)(Q.base=(BiTree*)ma1Ioc(QueueN1TsIZE*sizeof(BiTree);if(!Q.base)returnO;Q.front=Q.rear=O;return1;StatusDestroyQueue(SqQueue&Q)(free(Q.base);Q.base=NU11;StatusQueueEmpty(SqQueue&Q)if(Q.front=Q.rear)return1;e1sereturn0;StatusEnQueue(SqQueue&Q,BiTree&e

9、)(if(Q.rear+1)%Queue_INIT_SIZE=Q.front)(Printf(队列已满n);return0;)Q.baseQ.rear=e;Q.rear=(Q.rear+1)%Queue_INITSIZE;return1;)StatusDeQueue(SqQueue&Q,BiTree&e)(if(Q.front=Q.rear)return0;e-Q.baseQ.front;Q.front=(Q.front+1)%Queue_INIT_SIZE;StatusTraverseBiTree(BiTree&T)树形输出inti,j,m,n;intk,si;BiTreeaaa;SqQue

10、ues;InitQueue(s);EnQueue(s,T);m=depth(T);for(n=1;n=m;n+)(k=(int)(pow(2,m+1-n)-1);for(i=0;i1chi1d);EnQueue(s,aaa-rchi1d);)if(i=0)(for(j=0;jdata);e1se(for(j=0;jdata);)Printf(n);)return1;voidRRotate(BiTree&p)(BiTree1c;1c=p-1chi1d;p-1chi1d=1c-rchiId;1c-rchi1d=p;P=1c;)void1_Rotate(BiTree&p)BiTreeRe;Rc=p-

11、rchi1d;p-rchi1d=Rc-1chiId;Rc-1chi1d=p;P=Rc;)void1eftBa1ance(BiTree&T)左旋平衡BiTree1c,Rd;1c=T-1chi1d;switch(1c-bf)(case1H:TraverseBiTree(T)：Printf(该树不平衡!n);PrinIf(平衡化后的树为:n);T-bf=1c-bf=EH;RRotate(T);break;caseEH:break;caseRH:Rd=1c-rchi1d;switch(Rd-bf)(case1H:T-bf=RH;1c-bf=EH;break;caseEH:T-bf=1c-bf=EH;b

12、reak;caseRH:T-bf=EH;1c-bf=1H;break;)TraverseBiTree(T);Printf(该树不平衡!n)；Printf(平衡化后的树为:n);Rd-bf=EH;1.Rotate(T-1chiId);RRotate(T);voidRightBa1ance(BiTree&T)右旋平衡BiTreeRe,1d;Rc=T-rchi1d;switch(Rc-bf)(caseRH:TraverseBiTree(T);printf(该树不平衡！r);Printf(平衡化后的树为:n);T-bf=Rc-bf=EH;1Rotate(T);break;caseEH:break;ca

13、se1H:1d=Rc-1chi1d;switch(1d-bf)(case1H:T-bf=EH;Rc-bf=RH;break;caseEH:T-bf=Rc-bf=EH;break;caseRH:T-bf=1H;Rc-bf=EH;break;TraverseBiTree(T);printf(该树不平衡!n);Printf(平衡化后的树为:n);1d-bf=EH;RRotate(T-rchiId);1Rotate(T);)intInsertAV1(BiTree&T,int&e,boo1&ta11er)结点插入if(1T)T=(BiTree)ma11oc(sizeof(BiTNode);T-data=e;T-1ch