《数据结构与算法》课程设计成果报告-树与二叉树转换的实现2.doc

河南工程学院数据结构与算法课程设计成果报告树与二叉树转换的实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1341班 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目树与二叉树转换的实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录第1章 课程设计目标与任务11.1 课程设计目标11.2 课程设计任务11.3 课程设计所用设施1第2章 分析与设计22.1 题目需求分析22.2 存储结构设计22.3 算法描述32.4 程序流程图5第3章 程序清单6第4章 测试104.1 测试数据104.2 测试结果分析12第5章 总结13第1章 课程设计目标与任务1.1 课程设计目标通过本课程设计，使学生在数据结构的选择和应用、算法的设计与实现方面得到训练，加深对数据结构基本内容的理解和灵活应用，同时，在程序设计方法及上机操作方面受到比较系统严格的训练，培养软件工作所需要的动手能力。数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学是软件设计的综合训练,包括问题分析，总体结构设计用户界面设计，程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的软件工作方法学生通过数据结构课程设计各方面得到锻炼：(1)能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法；(2)通过上机实习,验证自己设计的算法的正确性，学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改；(3)培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平；(4)尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来，获得算法的直观感受。1.2 课程设计任务根据提供的实习题目，认真完成软件设计的全部过程，并以最终软件设计成果来证明其独立完成实际任务的能力，从而，反映出理解和运用数据结构与算法的水平和能力，最后完成软件设计和程序调试并提交文档：课程设计报告书，报告书中包含设计的算法及部分程序代码。1.3 课程设计所用设施PC机、VC6.0语言编辑、编译运行工具、文档编辑软件等。第2章 分析与设计根据课程实训要求，分析和设计能够完成实验要求的程序，下面是每个具体操作过程的主要内容。2.1 题目需求分析根据所提供的题目，是要实现树与二叉树的转换，而且可以在程序设计中调用使用。学生要认真完成能够实现题目要求的函数库。由于二叉树和树都可以使用二叉链表作为存储结构，则二叉链表作为媒介可导出树与二叉树之间的一个对应关系。给定一棵树，可以找到唯一的一棵二叉树与之对应。2.2 存储结构设计(1)设置头文件：#includestdio.h#includemalloc.h#includestdlib.h(2)设置常量：#define MAX_TREE_SIZE 100(3)一般树的存储结构有以下几种：双亲结点，孩子结点，孩子兄弟结点，本实验运用到的是双亲结点和孩子兄弟结点，具体存储结构如下：Typedef structint data,parent/双亲位置域;PTNode;双亲表示法树结构：Typedef structPTNode nodeMAX_TREE_SIZE;int count;PTree;树的孩子兄弟结点表示结点结构定义：Typedef struct node int data; struct node *firstchild;struct node *rightsib;BTNode,*BTree;2.3 算法描述按照程序执行先后顺序进行描述(1)树的构建完成后，用孩子兄弟表示法对树进行初始化结点，所用到的方法是：BTNode GetTreeNode(int x) BTNode t;t.data =x;t.firstchild =t.rightsib =NULL;return t;(2)树创建成功后，进行树的先序遍历，如果树不为空，先访问根结点，再先序遍历左子树，然后先序遍历右子树。先序遍历二叉树基本操作方法是递归算法，使用的方法是：void preorder(BTNode *T) if(T!=NULL)preorder(T-firstchild );preorder(T-rightsib );(3)树的后序遍历中，如果树不为空，首先后序遍历左子树，再后序遍历右子树，然后访问根结点，使用的方法是：void inoeder(BTNode *T) int i;for(;i=T.count-1;i-)printf(%d,T.nodei);(4)树的层次遍历,如果二叉树非空，将根指针入队进行循环，直到队列为空，其方法是：void level(PTree T) int i;for(i=0;iT.count;i+)printf(%d,T.nodei);(5)用双亲表示法表示树，创建一维数组表示法，数组的元素具有两个数据域data和双亲位置域parent，每一个元素对应一个数组下标，其方法是：PTree CreatTree(PTree T) int i=1;int fa,ch;PTNode p;for(i=1;ch!=-1;i+)T.nodeT.count.data=p.data;T.nodeT.count.parent=p.parent;(6)实现一般树转换成二叉树，树中的每个结点最多只有一个最左边的孩子和一个右邻的兄弟，每个结点的兄弟指针指向它的一个兄弟，每个结点仅有一个孩子指针，让它指向自己最左边的孩子，这样就可以呈现出一棵二叉树，其方法是：BTNode *change(PTree T) int i,j=0;BTNode pMAX_TREE_SIZE;BTNode *ip,*is,*ir,*Tree;ip=(BTNode*)malloc(sizeof(BTNode);is=(BTNode*)malloc(sizeof(BTNode);Tree=(BTNode*)malloc(sizeof(BTNode);Tree=p0;return Tree;(7)实现调用功能的主函数,可以实现对一般树的转换，进行先序遍历、后序遍历、层次遍历、水平输出二叉树、返回主菜单以及退出程序等功能，方法是：void main()int i=0,c1,c2;PTree T;BTNode *Tree;init_ptree(T);loop:Menu();scanf(%d,c1);switch(c1)case 1:Menu2();scanf(%d,c2);if(c2=9)goto loop;else if(c2=0)exit(1);最后进行调试和修改，进行执行操作。2.4 程序流程图根据课程要求，整理出思维路线。首先创建一个覆盖全部操作功能的“主菜单”，在菜单中，可以调用各个操作的方法，其中的方法包含完成课程要求的创建树，遍历树。在一般树创建成功之后，按照格式输入各个结点，运行之后显示出所要求的内容。最后调用“副菜单”方法，进行接续执行或退出程序操作，从而达到最终实现整个课程要求的目的。开始退出程序主菜单双亲法建树先序遍历（递归）后序遍历（递归）先序遍历（非递归）后序遍历（非递归）层次遍历按照格式输入各个结点输出遍历结果输出树的结点情况副菜单退出程序图2.4.1 程序流程图第3章 程序清单#include stdio.h#include malloc.h#include stdlib.h#define MAX_TREE_SIZE 100/树的双亲表示结点结构定义typedef structint data;int parent;/双亲位置域PTNode;/双亲表示法树结构typedef structPTNode nodeMAX_TREE_SIZE;int count;/根的位置和结点个数PTree;/树的孩子兄弟表示结点结构定义typedef struct nodeint data;struct node *firstchild;struct node *rightsib;BTNode,*BTree;void init_ptree(PTree *tree)tree-count =-1; /初始化树结点(孩子兄弟表示法)BTNode GetTreeNode(int x)BTNode t;t.data =x;t.firstchild =t.rightsib =NULL;return t;/树的先序遍历(递归)void preorder(BTNode *T)if(T!=NULL)printf(%d,T-data );preorder(T-firstchild );preorder(T-rightsib );/树的先序遍历（非递归）void preorder2(PTree T)int i;for(i=0;iT.count ;i+)printf(%d,T.nodei);/树的后序遍历（递归）void inoeder(BTNode *T)if(T!=NULL)inoeder(T-firstchild);printf(%d,T-data);inoeder(T-rightsib );/树的后序遍历void inoeder2(PTree T)int i;for(;i=T.count-1;i-)printf(%d,T.nodei);/层次遍历void level(PTree T)int i;for(i=0;iT.count;i+)printf(%d,T.nodei);/水平输出二叉树void PrintBTree(BTNode *root,int level)int i;if(root!=NULL)PrintBTree (root-rightsib,level+1);for(i=1;i=8*level;i+)printf( );printf(-%dn,root-data);PrintBTree(root-firstchild,level+1);/输出树void print_ptree(PTree tree)int i;printf( 序号 结点 双亲n);for(i=0;i=tree.count;i+)printf(%8d%8d%8d,i,tree.nodei.data,tree.nodei.parent);printf(n);/用双亲表示法表示树 PTree CreatTree(PTree T)int i=1;int fa,ch;PTNode p;for(i=1;ch!=-1;i+)printf(输入第%d个结点n,i);scanf(%d%d,fa,ch);printf(n);p.data=ch;p.parent=fa;T.count+;T.nodeT.count.data=p.data;T.nodeT.count.parent=p.parent;printf(n);printf(创建的树具体情况如下：n);print_ptree(T);return T;/一般树转换成二叉树BTNode *change(PTree T)int i,j=0;BTNode pMAX_TREE_SIZE;BTNode *ip,*is,*ir,*Tree;ip=(BTNode*)malloc(sizeof(BTNode);is=(BTNode*)malloc(sizeof(BTNode);Tree=(BTNode*)malloc(sizeof(BTNode);for(i=0;iT.count;i+)pi=GetTreeNode(T.nodei.data);for(i=1;iT.count;i+)ip=pi;is=pj;while(T.nodei.parent!=is-data)j+;is=pj;if(!(is-firstchild)is-firstchild=ip;ir=ip;elseir-rightsib=ip;ir=ip;Tree=p0;return Tree;/主菜单void Menu()printf(=主菜单=n);printf(*输入1-以双亲法创建一般树 *n);printf(*输入2-树的先序遍历（递 归）*n);printf(*输入3-树的后序遍历（递 归）*n);printf(*输入4-树的先序遍历（非递归）*n);printf(*输入5-树的后序遍历（非递归）*n);printf(*输入6-层次序的非递归遍历 *n);printf(*输入0-退出程序 *n);printf(=请输入执行的指令=n);/副菜单void Menu2()printf(=副菜单=n);printf(*输入9-返回菜单继续工作 *n);printf(*输入0-退出程序 *n);/主函数void main()int i=0,c1,c2;PTree T;BTNode *Tree;init_ptree(T);loop:Menu();scanf(%d,c1);switch(c1)case 1:printf(建立一般树，依次输入各个结点情况：n);printf(输入结点方式：双亲数据，整型数据（第一个结点双亲数据为-1，最后以-1，-1结束）n);T=CreatTree(T);Tree=change(T);printf(一般树转换成二叉树后的情况n);PrintBTree(Tree,i);getchar();break;case 2:printf(树的先序遍历（递归）：n);preorder(Tree);printf(n);break;case 3:printf(树的后序遍历（递归）：n);inoeder(Tree);printf(n);break;case 4:printf(树的先序遍历（非递归）：n);preorder2(T);printf(n);break;case 5:printf(树的后序遍历（非递归）：n);inoeder2(T);printf(n);break;case 6:printf(树的层次遍历:n);level(T);printf(n);break;case 0:exit(1);break;Menu2();scanf(%d,c2);if(c2=9)goto loop;else if(c2=0)exit(1);第4章 测试4.1 测试数据（1） 运行前面提到的程序后，会在计算机窗口显示出程序所涉及的操作流程“主菜单”。其内部包含用双亲法创建一般树、树的先序遍历等操作功能，如下图所示。图4.1.1 主菜单（2）按照操作提示，首先输入1建立一般树，然后根据窗口提示一次输入各个结点（示例是依次输入-1，1；1，2；1，3；2,4和-1，-1），工作平台会显示出下图所示的操作过程。图4.1.2 示例操作数据（3）输入上述所提供的示例之后，该程序会在工作平台显示运行结果，自动生成一般树，并且输出树的具体情况（包括序号、结点和双亲）。在建立好一般树之后，系统会自动把它转化为二叉树，并输出新形成的树的具体情况。同时，程序主函数内部的“副菜单”也会被调用（如下图所示），从而显示出来，让操作者根据自身情况进行操作。图4.1.3 树与二叉树的转换（4）当进行完以上操作后，按照提示输入9后会重新显示一个如图4.1.1所示的主菜单，然后输入3（此为示例操作），会自动调用“树的后序遍历（递归）”方法，在工作平台上显示此树的后序遍历结果，具体情形如下图所示。图4.1.4 树的后序遍历4.2 测试结果分析(1) 按照课程要求，成功的进行了相关要求的操作和输入。在运行程序后，主函数会自动调用“void Menu()”方法，在工作平台显示出该方法所设计的主要操作功能，显示的内容就如图4.1.1所示，从而更直观的让操作者进行操作。(2)根据主菜单显示的操作提示，可以根据个人需要进行相关输入，在此之前要建立一棵一般树，使用“void init_ptree(PTree *tree)”方法进行结点结构定义，然后初始化树结点就可以创建一棵树。(3) 进行遍历二叉树，先序遍历二叉树时，首先访问根结点，依次进行先序遍历左子树和右子树，其二叉链表可以显示如下图所示。1234 图4.2.1二叉链表(4)之后会生成一棵新的二叉树，本树的各个结点是1,2,3和4，本次试验所使用的示例所显示的二叉树如下图所示。1324图4.2.2 生成的二叉树(5)创建成功后，可以输入数据进行接下来的各项操作，比如进行输出二叉树和转换成二叉树等操作，系统会自动调用各个项目所涉及的方法，从而达到最终的目的来完成实验。第5章 总结课程设计体会在这次实训中，我们的设计还不够特别完善，由于自己对知识的掌握不够娴熟，运用起来不是那么灵活，导致了有些功能不能够实现，这中间也做了不少的无用功。不过，在这一段时间里，自己所掌握的知识范围有所扩大，知识水平也有很大的提高。在这次实训中，大家也学到了不少的东西，每个人的独立思考解决问题的能力有所提高。与此同时，大家的合作显得格外的重要，对以后的工作、学习都会有很大的帮助。对我们软件专业的学生来说，实际动手能力的培养至关重要，必须从课堂走向实践，通过实训，让我们找出了自身状况和实际的差距，从而更好的发现自己的不足，才能够及时改正过来，做好对以后发展的良好基础。 参考文献1彭军等.数据结构与算法（第一版）.机械工业出版社2赵坚，姜梅.数据结构（C语言版）.清华大学出版社 3吴伟民等.数据结构 （C语言版）.清华大学出版社 4MarkAllenWeiss.数据结构与算法（C语言版）（第二版）.机械工业出版社#include stdio.h#include malloc.h#include stdlib.h#define MAX_TREE_SIZE 100/树的双亲表示结构定义typedef structint data;int parent;/双亲位置域PTNode;/双亲表示法树结构typedef structPTNode nodeMAX_TREE_SIZE;int count;/根的位置和节点个数PTree;/树的孩子兄弟表示节点结构定义typedef struct nodeint data;struct node *firstchild;struct node *rightsib;BTNode,*BTree;void init_ptree(PTree *tree)tree-count =-1;/初始化树节点(孩子兄弟表示法)BTNode GetTreeNode(int x)BTNode t;t.data =x;t.firstchild =t.rightsib =NULL;return t;/树的前序遍历(递归)void preorder(BTNode *T)if(T!=NULL)printf(%d,T-data );preorder(T-firstchild );preorder(T-rightsib );/树的前序遍历（非递归）void preorder2(PTree T)int i;for(i=0;iT.count ;i+)printf(%d,T.nodei);/树的后序遍历（递归）void inoeder(BTNode *T)if(T!=NULL)inoeder(T-firstchild);printf(%d,T-data);inoeder(T-rightsib );/树的后序遍历void inoeder2(PTree T)int i;for(;i=T.count-1;i-)printf(%d,T.nodei);/层次遍历void level(PTree T)int i;for(i=0;iT.count;i+)printf(%d,T.nodei);/水平输出二叉树void PrintBTree(BTNode *root,int level)int i;if(root!=NULL)PrintBTree (root-rightsib,level+1);for(i=1;i=8*level;i+)printf( );printf(-%dn,root-data);PrintBTree(root-firstchild,level+1);/输出树void print_ptree(PTree tree)int i;printf(双亲);for(i=0;i=tree.count;i+)printf(%8d%8d%8d,i,tree.nodei.data,tree.nodei.parent);printf(n);/用双亲表示法表示树 PTree CreatTree(PTree T)int i=1;int fa,ch;PTNode p;for(i=1;ch!=-1;i+)printf(输入第%d 个结点n,i);scanf(%d%d,fa,ch);printf(n);p.data=ch;p.parent=fa;T.count+;T.nodeT.count.data=p.data;T.nodeT.count.parent=p.parent;printf(n);printf(创建的树具体情况如下：n);print_ptree(T);return T;/一般树转换成二叉树BTNode *change(PTree T)int i,j=0;BTNode pMAX_TREE_SIZE;BTNode *ip,*is,*ir,*Tree;ip=(BTNode*)malloc(sizeof(BTNode);is=(BTNode*)malloc(sizeof(BTNode);Tree=(BTNode*)malloc(sizeof(BTNode);for(i=0;iT.count;i+)pi=GetTreeNode(T.nodei.data);for(i=1;iT.count;i+)ip=pi;is=pj;while(T.nodei.parent!=is-data)j