c语言课程设计.docx

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

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

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

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

4、块划分原理框图2.1.3 函数表函数名称函数原型主要功能Ma i nvoid ma in ()主函数InitBitreestatus InitBiTree (BiTree &T)初始化二叉树TraverseBiTreStatus树形输出eTraverseBi Tree (Bi Tree &T)Depthint depth (BiTree &T)求树的深度表2.1函数表开始int e,m=O;int i,n,k；i=O;/输入数据/If (in)InsertAVL(T,e,taller);TraverseB iTree(T);2.2 系统流程图2.2.1 平衡二叉树的建立结束图2. 2平衡二叉树

5、的建立2.2.2二叉树结点的插入图2. 3二叉树结点的插入2.2.3左平衡操作V图2. 4左平衡操作2.2.4右平衡操作图2. 5右平衡操作2.2.5树形输出结束V2. 6树形输出3调试分析3.1 函数组建问题在编写函数时，遇到了多种选择，但是往往选择的都有或多或少的问题，导致在调用时出现许多问题。经过多次调试最终编写出符合条件的函数。例如，对于函数的类型就时常搞混乱，不知道什么时候用void类型，什么时候用status类型。除此以外，在函数调用时经常将返回值的类型弄混。这些问题给程序的编写带来了很大的困扰。3.2 运行问题在运行时，一开始都会有许多的语法错误，比如函数定义的错误，结构体定义错

6、误等等，还经常将“；等符号漏掉或错用。不过经过细心修改，这些问题都得到了解决。经过一番努力，语法错误没有了，但在算法上的错误还存在，这是比较头痛的，例如循环队列的编写、递归算法的运用等等。在循环队列的编写中，对于判空和判满把握的不好，在进队和出队过程中，队头和队尾指针的改变不满足循环队列的要求。而对于递归算法这是经常将我的头绕晕，使我不能很快的找到问题的根源，浪费了很多时间。不过经过一次次的演算、验证，最终达到了课设题目的要求。4测试及运行结果4.1主界面显示主界面，输入所要进行的操作。4.2创建及结果按提示输入一组数，得到创建过程和结果。30第2次3028第3次30I 2829，该恻不平铺？

7、平栖化后的树为：2928 30第4次2928300第5次292830|1056平衡二叉树创建结束。.Press any key to continue参考文献1谭浩强等.c语言程序设计M.北京:清华大学出版社,20012金永平.数据结构（C+描述）M,北京:清华大学出版社,20053严蔚敏,吴伟明.数据结构（C语言版）M.北京清华大学出版社,20074吕国英.算法设计与分析M天津科技大学出版社,20065李兰友,Turbo C实用图形程序设计M.天津科技翻译出版社，1994附录（程序清单）#include#include#include#include#includettdefine LH +

8、1#dcfincEH 0#defineRH -1#defineNULL 0#defineQueue INIT SIZE 100#defineSElemType BiTree#defineStatus booltypedef struct BiTNodeint data;int bf;struct BiTNode *lchild, *rchildjBiTNode, *BiTree;int depth(BiTree T)(int m, n;if(!T)return 0;m=depth(T-lchild);m+;n=depth(T-rchild);n+;if (mn)return m;elseret

9、urn n;)typedef struct(BiTree *base;int front;int rear;SqQueue;Status InitQueue (SqQueue &Q)Q. base=(BiTree*)malloc(Queue_INIT_SIZE*sizeof(BiTree);if (!Q. base)return 0;Q. front=Q. rear=0;return 1;)Status DestroyQueue(SqQueue &Q)(free(Q. base);Q.base=NULLjStatus QueueEmpty(SqQueue &Q)if (Q. front=Q.

10、rear)return 1;elsereturn 0;Status EnQueue(SqQueue &Q,BiTree &e)(if (Q. rear+l)%Queue_INIT_SIZE=Q. front)(printf (队列已满n);return 0;)Q. baseQ. rear=e;Q. rear=(Q. rear+l)%Queue INTT SIZE;return 1;)Status DeQueue(SqQueue &Q, BiTree &e)(if (Q. front=Q. rear)return 0;e=Q. baseQ. front;Q. front=(Q. front+1)

11、%Queue_INIT_SIZE;return 1;Status TraverseBiTree(BiTree &T)树形输出int i, j, m, n;int k, si;BiTree aaa;SqQueue s;Tni tQueue (s);EnQueue (s, T);m=depth(T);for (n=l;n=m;n+)k=(int) (pow(2, m+l-n)-l);for(i=0;ilchiId);EnQueue(s,aaa-rchiId);)if(i=0)(for(j=0;jdata);)elsefor(j=0;jdata);)printf TV);)return 1;void R_Rotate(BiTree &p)BiTree Lc;Lc=p-lchild;p-lchild=Lc-rchild;Lc-rchild=p;P=Lc;void L Rotate(BiTree &p)BiTree Rc;Rc=p-rchild;p-rchild=Rc-lchild;Rc-lchild=pjP=Rc;)void LcftBalance (BiTrec &T)左旋平衡(BiTree Lc, Rd;Lc=T-lchild;switch(Lc-bf)(case