数据结构B实验报告-单链表的实现.doc

实 验 报 告（ 2014/ 2015 学年 第二学期）课程名称数 据 结 构B实验名称单链表的实现实验时间2015年 5 月 15日指导单位计算机学院计算机科学与技术系指导教师 学生姓名班级学号学院(系)通达学院专 业信息管理与信息系统实 验 报 告实验名称二叉树的链接表示指导教师徐鹤实验类型设计实验学时2实验时间2015.5.15一、实验目的和要求1. 理解二叉树的数据结构。2. 掌握二叉链表上实现二叉树基本运算的方法。3. 学会设计基于遍历的、求解二叉树应用问题的方法。二、实验内容:实现教材中二叉树的链接表示，并基于二叉树遍历算法实现其应用。具体如下： （一）实现教材中二叉树的链接表示，实现二叉树ADT的基本运算（先序遍历、中序遍历、后序遍历）。 （二）基于二叉树遍历算法实现其应用： 计算一棵二叉树叶子节点个数。 统计一棵二叉树的节点个数。 （三）设计main函数，测试实验内容一的运算和实验内容二的算法。三、实验环境(实验设备)Visual C+ 6.0实 验 报 告四、实验过程描述与结果分析#include #include #include typedef struct btnodechar element;struct btnode *lchild,*rchild;BTNode;BTNode * PreCreate(BTNode *Bt)/先序创建二叉树char ch;ch=getchar();if(ch=#)/输入为#表示这里建立一个空二叉树Bt=NULL;elseBt=(BTNode *)malloc(sizeof(BTNode);Bt-element=ch;Bt-lchild=PreCreate(Bt-lchild);Bt-rchild=PreCreate(Bt-rchild);return Bt;void Preorder(BTNode *Bt)/先序输出二叉树if(Bt)printf(%c ,Bt-element);Preorder(Bt-lchild);Preorder(Bt-rchild);void Inorder(BTNode *Bt)/中序输出二叉树if(Bt)Inorder(Bt-lchild);printf(%c ,Bt-element);Inorder(Bt-rchild);void Postorder(BTNode *Bt)/后序输出二叉树if(Bt)Postorder(Bt-lchild);Postorder(Bt-rchild);printf(%c ,Bt-element);int Size(BTNode *Bt)/求二叉树中的结点数int s,s1,s2;if(!Bt)/二叉树为空，结点数为0s=0;elses1=Size(Bt-lchild);s2=Size(Bt-rchild);s=s1+s2+1;/二叉树的结点数等于左右子树结点数的和在加1（根结点） return s;int Leaf(BTNode *Bt)/求二叉树中叶子个数int ll,rl,tl;if(!Bt)/二叉树为空，叶子个数为0tl=0;else if(!Bt-lchild&!Bt-rchild)/叶子满足的条件（左右孩子均为空） tl=1; else ll=Leaf(Bt-lchild); rl=Leaf(Bt-rchild); tl=ll+rl; return tl;int Depth(BTNode *Bt)/求二叉树的深度（高度）int ld,rd,td;if(!Bt)td=0;elseld=Depth(Bt-lchild);rd=Depth(Bt-rchild);if(ld=rd)/左右子树高度大的加1，即为二叉树的高度td=ld+1;elsetd=rd+1;return td;void main()BTNode *Bt;int s,tl,td;Bt=NULL;printf(nInput create order:n);Bt=PreCreate(Bt);printf(nThe preorder is:n);Preorder(Bt);printf(nThe inorder is:n);Inorder(Bt);printf(nThe postorder is:n);Postorder(Bt);s=Size(Bt);printf(nThe size of the tree is:n);printf(%dn,s);tl=Leaf(Bt);printf(nThe leaves of the tree is:n);printf(%dn,tl);td=Depth(Bt);printf(nThe depth of the tree is:n);printf(%dn,td); 实 验 报 告五、实验小结（包括问题和解决方法、心得体会、意见与建议等） 这是一门纯属于设计的科目，它需用把理论变为上机调试。刚开始学的时候确实有很多地方我很不理解，每次上课时老师都会给我们出不同的设计题目，对于我们一个初学者来说，无疑是一个具大的挑战，撞了几次壁之后，我决定静下心来，仔细去写程序。老师会给我们需要编程的内容一些讲解，顺着老师的思路，来完成自己的设计，我们可以开始运行自己的程序。 这门课结束之后，我总结了学习中遇到的一些问题，最为突出的，书本上的知识与老师的讲解都比较容易理解，但是当自己采用刚学的知识点编写程序时却感到十分棘手，有时表现在想不到适合题意的算法，有时表现在算法想出来后，只能将书本上原有的程序段誊写到自己的程序中再加以必要的连接以完成程序的编写。 刚开始学的时候确实有很多地方我很不理解，每次上上机课时老师都会给我们出不同的设计题目，对于我们一个初学者来说，无疑是一个具大的挑战，撞了几次壁之后，我决定静下心来，仔细去写程序。老师会给我们需要编程的内容一些讲解，顺着老师的思路，来完成自己的设计，我们可以开始运行自己的程序，可是好多处的错误让人看的可怕，还看不出到底是哪里出现了错误，但是程序还是得继续下去，我多次请教了老师和同学，逐渐能自己找出错误，并加以改正。TC里检查错误都是用英文来显示出来的，经过了这次课程设计，现在已经可以了解很多错误在英文里的提示，这对我来说是一个突破性的进步，眼看着一个个错误通过自己的努力在我眼前消失，觉得很是开心。此次的程序设计能够成功，我很开心。在这一段努力学习的过程中，我们的编程设计有了明显的提高。 其实