《存储结构与基本运算的算法 顾云康E01114300.doc》由会员分享，可在线阅读，更多相关《存储结构与基本运算的算法 顾云康E01114300.doc（27页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计报告 数据结构课程设计实验报告树的存储结构与基本运算的算法 姓名：顾云康 学号：E1114300 指导老师：王爱平 日期：2013.9.17目录一 课程设计的目的.二 需求分析.三 课程设计报告内容.1 概要设计.2 详细设计.3 调试分析.4 程序清单.四 小结.五 参考文献.六 附录一 课程设计的目的(1) 熟练使用 C语言编写程序，解决实际问题;(2) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力;(3) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力;二 需求分析（1）设置二叉树的存储结构（2）编写二叉树的输出函数（3）编写二叉树的建立、先
2、序、中序、后序遍历函数（4）编写二叉树与数的转化函数 (5 ) 编写主函数，控制程序运行三 课程设计报告内容 3.1 概要设计（1）设置二叉树的存储结构typedef struct btree btree *lchild,*rchild; char data; *BiNode; 3.2 详细设计1.主函数：int main() int k; do cout*; coutn 1.创建二叉树 ; coutn 2.前序递归遍历算法 ; coutn 3.中序递归遍历算法 ; coutn 4.后序递归遍历算法 ; coutn 5.前序非递归遍历算法 ; coutn 6.中序非递归遍历算法 ; coutn
3、 7.后序非递归遍历算法 ; coutn 8.层序非递归遍历算法 ; coutn 9. 树与二叉树的转换; coutn 10.退出操作n;cout*n; coutk; switch(k) case 1: p=creat(); break; case 2: cout二叉树的前序递归遍历 :; PreOrder(p); break; case 3: cout二叉树的中序递归遍历 :; InOrder(p); break; case 4: cout二叉树的后序递归遍历 :; PostOrder(p); break; case 5: cout二叉树前序非递归遍历:; F_PreOrder(p); br
4、eak; case 6: cout二叉树中序非递归遍历:; F_inOrder(p); break; case 7: cout二叉树后序非递归遍历:; F_PostOrder(p); break; case 8: cout=0 & k9);return 0;2. 先序遍历二叉树的递归算法若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。void PreOrder(BiNode root)。3中序遍历二叉树的递归算法若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。void InOrder(BiNode root)。
5、4先序遍历二叉树的递归算法若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树。（3）访问根结点；void PostOrder(BiNode root)。5先序非递归算法BiNode根指针，若 BiNode!= NULL对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。6中序非递归算法BiNode是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。7后序非递归算法BiNode是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。void F_PostOrder(BiNode root)。8层次序遍历算法按照树
6、的层次从左到右访问树的结点，层序遍历用于保存结点的容器是队列。void LevelOrder(BiNode root)。9树与二叉树的转换算法 转换时结点的第一个孩子变为它的左孩子，兄弟节点变为他的有孩子。void exchange()，class Tree.3.3 调试分析（1） 四 总结 通过本次程序设计，让我更深层次地了解到了树各种函数的运用，如何运用各种存储结构创建树，以及在实验中还涉及到递归的运用，递归的思想省去了复杂的算法设计。在实验中不可避免的出现了大大小小的问题，在调试中透彻领悟各种算法的真谛，同样的错误在下次遇到时就可以避免了。 五 程序清单见附录六 参考文献（1)严蔚敏，吴
7、伟民 编著. 数据结构(C 语言版)-北京: 清华大学出版社，2007. (2)严蔚敏，吴伟民 米 宁 编著. 数据结构题集(C 语言版)-北京: 清华大学出版社，2007.（3）部分代码网上参考7 程序运行结果（1）接收用户输入：（2）二叉树与树的转化： （2）前序递归遍历的实现：（3）中序递归遍历的实现：（4）后序递归遍历的实现：（5）前序非递归遍历的实现：（6）中序非递归遍历的实现：（7）后序非递归遍历的实现：（8）层次非递归遍历的实现： 26 附 录程序清单：#includeusing namespace std;#include #include #define maxsize 10
8、0#include tree.h#define LEN sizeof(struct btree) int max=1;typedef struct btree btree *lchild,*rchild; char data; *BiNode; typedef struct StackElemTypeBiNode ptr;int flag;StackElemType;BiNode p ;/二叉树的;建立BiNode stree_creat(char *a,int k) BiNode root; max+;if(ak=0|kmaxsize) return NULL; else root=(BiN
9、ode)malloc(LEN); root-data=ak; root-lchild=stree_creat(a,2*k+1); root-rchild=stree_creat(a,2*k+2); return root; void print(BiNode root) BiNode hmaxsize=NULL; int top=0,base=0,j=0,k=0,n=0,m=0; htop=root; j=log(max+1)/log(2)-1;if(pow(2,j+1)-1max) j+; coutlchild; h+top=hbase-rchild; base+; for(top=0;hk!=NULL;top+) m=pow(2,j)-top; if(top!=0) m=m-top; for(n=0;nm;n+) cout ; for(base=0;basedata=0) cout; else coutdata ; k+; coutn; for(n=0;n(m-1);n+) cout ; for(base=0;basepow(2,top)&hk!=NU
