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

河南工程学院数据结构与算法课程设计成果报告树与二叉树转换的实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程-1341 专业课程： 数据结构与算法指导教师： 2014 年 12 月 29 日题 目树与二叉树转换的实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标11.1 课程设计目标11.2 课程设计任务11.3 课程设计要求12 分析与设计22.1 题目需求分析22.2 存储结构设计22.3 算法描述22.4 程序流程图22.5 测试程序说明23 程序清单34 测试44.1 测试数据44.2 测试结果分析45 总结5参考文献71 课程设计目标与任务1.1 课程设计目标（1）通过课程设计，巩固所学的理论知识，培养综合运用所学知识解决实际问题的能力。（2）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力。 （3）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。 （4）提高综合运用所学的理论知识和方法独立分析和解决问题的能力，增强理论与实践相结合的技巧。（5）训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。（6）增强团队合作意识，初步了解软件开发的一般过程，培养学习热情以及加强自主学习。（7）训练自己动手分析，解决问题的能力，掌握调试程序，排成错误的常用技巧。（8）增强动手能力，学会结合实际解决问题。1.2 课程设计任务（1）根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相映的存储结构，并能设计出解决问题的有效算法。实现树与二叉树之间的转换。（2）掌握二叉树的结构特征，以及各种存储结构的特点及适用范围。（3）掌握用指针类型描述、访问和处理二叉树的运算。1.3 课程设计要求（1）认真阅读和掌握本实验的程序。（2）上机编写并运行本程序。（3）保存和打印出本程序的运行结果，并结合程序进行分析。（4）按照二叉树的操作需求，重新改写主程序并运行，打印出文件清单和运行结果。.2 分析与设计2.1 题目需求分析实现树与二叉树的转换，以及树的前序、后序的递归、非递归遍历算法，层次序的非递归算法的实现，应包含建树的实现。（多种遍历可以只实现一个）2.2 存储结构设计引入头文件：#include#include#include设置常量：#defineMAX_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; .2.3 算法描述1.二叉树创建用链表实现创建一个树结点的结构体，从键盘输入数据，存入数组。把下标为2*i+1 的值存入左孩子，为2*i+2的存入右孩子。 2.先序遍历二叉树的递归算法若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。void PreOrder(BiNode root)。3.后序遍历二叉树的递归算法若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树。（3）访问根结点；void PostOrder(BiNode root)。4.先序非递归算法BiNode根指针，若 BiNode!= NULL对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。5.后序非递归算法BiNode是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。void F_PostOrder(BiNode root)。6.层次序遍历算法按照树的层次从左到右访问树的结点，层序遍历用于保存结点的容器是队列。void LevelOrder(BiNode root)。.2.4 程序流程图设计如下流程图：首先根据指令，输入信息，生成一棵树后，再将生成的树转化为二叉树，然后输出生成的二叉树的结构图、二叉树的前序遍历结果以及二叉树的深度和孩子结点。在非递归遍历时，容易进入死循环，这时需要分步调试并最终找到循环结束条件，顺利输出结果。退出程序层次遍历开始双亲法建树按照格式输入各个结点输出树的结点情况1主菜单前序遍历（递归）后序遍历（递归）前序遍历（非递归）后序遍历（非递归）输出遍历结果副菜单退出程序23540069图2.4-1 程序流程图.2.5 测试程序说明在调试过程中出现了很多问题，定义表过长的，处理记录数量错误时程序的异常，记录冲突次数等等。通过问同学，查资料，我知道路定义过长则减少某些属性的字符数。处理记录数量错误时程序的异常则在被调用类（被主程序或其他类调用的类）中捕获异常记录到容器类中，然后抛出；在调用类（非主程序类）中继续捕获，然后同样是记录到错误容器继续向上抛出；依此方法直到最后在主程序中（入口程序类）捕获异常（记住这个捕获一定要捕获所有可能异常的情况）然后连同此次错误信息一并记录到错误容器，写入错误日志，给出相应提示。二叉树遍历中用到的最重要的一个思想就是递归调用，这次作业使我对递归有了深入的理解，尤其是对退回上一层后应执行的语句和结点位置的丝路更加清晰。程序调试比较顺利。.3 程序清单typedef struct #include#include#include#include#define edgetype int#define vextype int#define MAX 8typedef struct node int vextex; struct node *next;edgenode;typedef struct int vextex; int x,y; edgenode *link;vexnode;const int px8=1,2,2,1,-1,-2,-2,-1;const int py8=2,1,-1,-2,-2,-1,1,2;const int L=8,H=8;vexnode gaL*H; int visitedL*H=0; int stackL*H; int top; seqstack; seqstack s; void setnull(seqstack *s) s-top=-1; int empty(seqstack *s) if(s-toptopL*H-1) printf(stack overflow!n); return 0; else s-stack+s-top = x; return 1; int pop(seqstack *s) if(s-toptop-; return(s-stacks-top+1); void init() int n; for (int i=0;iH;i+) for (int j=0;jL;j+) n=L*i+j; gan.vextex=n; gan.x=j; gan.y=i; gan.link=NULL; for (i=0;iL*H;i+) edgenode *p; for (int k=0;kMAX;k+) int tx=gai.x+pxk; int ty=gai.y+pyk; if(tx0|ty=L|ty=H) continue; else p=(edgenode*)malloc(sizeof(edgenode); p-vextex=ty*L+tx; p-next=gai.link; gai.link=p; void show() int i; printf(n); for (i=0;i,gai.vextex); edgenode *p; p=(edgenode*)malloc(sizeof(edgenode); p=gai.link; while (p!=NULL) printf(%d ,p-vextex); p=p-next; printf(n); void showanswer() int rankL*H; int tag=s.top; for (int i=L*H-1;i=0;i-) ranks.stacktag-=i; for (i=0;ivextex) HFS(p-vextex); p=p-next; if (s.top=L*H-1) printf(answer %d:n,sum+); showanswer(); printf(n); visiteds.stacks.top=0; pop(&s); if (empty(&s) return 0; return 0; int main() int n; for (n=0;nH*L;n+) memset(visited,0,sizeof(visited); init(); show(); setnull(&s); HFS(n); getch(); return 0;4 测试4.1 测试数据图4.1-1开始界面图4.1-2 一般树初始建立图4.1-3 一般树的完善副菜单选择：选择9继续操作运用各种遍历形式遍历树：图4.1-4 一般树转化为二叉树图4.1-5 返回主菜单界面4.2 测试分析详细设计过程共有以下函数的实现：树的初始化函数（双亲法和孩子节点法两种），建树函数，输出树函数，树的前序遍历函数（递归和非递归两种），树的后序遍历函数（递归和非递归两种），树的层次遍历函数，一般树和二叉树的转换函数。主菜单和副菜单，主函数。 5 总结以前用C编程，只是注重如何编写函数能够完成所需要的功能，似乎没有明确的战术，只是凭意识和简单的语句来堆砌出一段段程序。现在变成感觉完全不同了。在编写一个程序之前，自己能够综合考虑各种因素，首先选取自己需要的数据结构，是树还是图或是别的什么。然后再选定一种或几种存储结构来具体的决定后面的函数的主要风格。最后在编写每一个函数之前，可以自习斟酌出对挑选出最合适当前状况的算法。这样，即使在完整的程序还没有写出来之前，自己心中已经有了明确的原图了。这样无形中就提高了自己编写程序的质量。另外，我还体会到深刻理解数据结构的重要性。只有真正理解这样定义数据类型的好处，才能用好这样一种数据结构。了解典型数据结构的性质是非常有用的，它往往是编写程序的关键。 这次试验也让我看到了自己的不足，还是不太用模版类。还有许多关于C+的一些比较具体的东西还不太懂，比方说指针。这次实验还让我意识到只有不管在机子上调试程序，自己的水平才能得到提高。我会继续我的兴趣编写程序的，相信在越来越多的尝试之后，自己会不断进步和提高。参考文献1 严蔚敏、吴伟民编.数据结构（C语言版）（含盘）.清华大学出版社2 严蔚敏.数据结构题集（C语言版）（第二版）.清华大学出版社3 赵坚、姜梅主编.数据结构（C语言版）学习指导与习题解答（第六版）.中国水利水电出版社4 秋叶拓哉等.挑战程序设计竞赛（第2版）. 人民邮电出版社5 严蔚敏等.数据结构（C语言版）.清华大学出版社6 Thomas H.Cormen.算法导论（第二版）. 机械工业出版社出版7 Jon Bentley.编程珠玑. 人民邮电出版社/typedef struct #include#include#include#include#define edgetype int#define vextype int#define MAX 8typedef struct node int vextex; struct node *next;edgenode;typedef struct int vextex; int x,y; edgenode *link;vexnode;const int px8=1,2,2,1,-1,-2,-2,-1;const int py8=2,1,-1,-2,-2,-1,1,2;const int L=8,H=8;vexnode gaL*H; int visitedL*H=0; int stackL*H; int top; seqstack; seqstack s; void setnull(seqstack *s) s-top=-1; int empty(seqstack *s) if(s-toptopL*H-1) printf(stack overflow!n); return 0; else s-stack+s-top = x; return 1; int pop(seqstack *s) if(s-toptop-; return(s-stacks-top+1); void init() int n; for (int i=0;iH;i+) for (int j=0;jL;j+) n=L*i+j; gan.vextex=n; gan.x=j; gan.y=i; gan.link=NULL; for (i=0;iL*H;i+) edgenode *p; for (int k=0;kMAX;k+) int tx=gai.x+pxk; int ty=gai.y+pyk; if(tx0|ty=L|ty=H) continue; else p=(edgenod