2023年数据结构B实验报告单链表的实现.pdf

《2023年数据结构B实验报告单链表的实现.pdf》由会员分享，可在线阅读，更多相关《2023年数据结构B实验报告单链表的实现.pdf（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实 验 报 告（202 3/2 0 2 3学年 第二学期）课程名称 数 据 结 构B实验名称 单链表的实现实验时间 2 0 23 年 5 月 1日5指导单位 计算机学院计算机科学与技术系指导教师学生姓名 班级学号学院（系）通达学院 专 信息管理与信息业 系统实 验 报 告实验名称二叉树的链接表达指导教师徐鹤实验类型设计 实验学时 2实验时间2023.5.15一、实验目的和规定1.理解二叉树的数据结构。2.掌握二叉链表上实现二叉树基本运算的方法。3.学会设计基于遍历的、求解二叉树应用问题的方法。二、实验内容：实现教材中二叉树的链接表达，并基于二叉树遍历算法实现其应用。具体如下：（一）实现教材中二

2、叉树的链接表达，实现二叉树ADT的基本运算（先序遍历、中序遍历、后序遍历）。（二）基于二叉树遍历算法实现其应用：计算一棵二叉树叶子节点个数。记录一棵二叉树的节点个数。（三）设计m a in函数，测试实验内容一的运算和实验内容二的算法。三、实验环境（实验设备）V isual C+6.0实 验 报 告四、实验过程描述与结果分析#inc 1 ude#i n c lude#inc 1 ude typedef struc t bt n o de(c ha r e 1 e m e n t;st r u ct btn o d e*l c h i 1 d,*rch i Id;BTNode;BTNode*Pre

3、Create(BT N o de*B t)。/先序创建二叉树(oc h ar ch;ch=getchar()oif(ch=#)输入为#表 达 这里建立一个空二叉树。B t=NU LL;*e Ise(。Bt=(BTNode*)malloc(siz e of(BTNo d e);。B t-e1e m e n t=c h;B t -l c h i 1 d=P r e C r e a t e (B t-l c h i I d);s B t -r c h i l d =P r e C r e a t e (B t-r c h i l d);r e t u r n B t;)v o i d P r e o

4、 r d e r (BTNode*B t)必先序输出二叉树(i f (B t)8 p r i n t f(%c ,B t-e 1 e m e n t)；Pre o r d e r (B t 1 c h i l d);s P r e ord e r(B t-r c h i 1 d)；void I n o r d e r (B T N o d e *B t )。中序输出二叉树 i f(B t )o l n o r d e r (B t -1 c h i l d );p r i n t f (，/%c r，,B t-e l e m e n t);。I n o r d e r (B t-r c h i

5、 1 d)；)v o i d P o s t o r d e r (B T N o d e *B t )B 后序输出二叉树(i f (B t )0 P o s t o r d e r (B t-l c h i l d)；Posto r d e r (B t-r c h i l d);p r i n t f C%c ”,B t-e l e m e n t)；i n t S i z e (B T N o d e *B t)。求二叉树中的结点数(i n t s ,s i,s 2 ;i f (!B t)抽 。/二叉树为空,结点数为0s=0；e l s e。s l=S i z e(B t l c h i

6、 l d);。s 2 =S i z e(B t r c h i l d)；o s=s l +s 2+l；g /二叉树的结点数等于左右子树结点数的和在加1 (根结点)r e t u r n s；i n t L e a f (B T N o d e *B t)*求二叉树中叶子个数(i n t 1 1,r l,t l;o i f (!B t)-“/二叉树为空，叶子个数为0t 1 =0;o e l s e i f(!B t-l c h i 1 d&!B t-r c h i l d)叶子满足的条件(左右孩子均为空)。t 1 =1;e l s e。l l =L e a f (B t-l c h i 1 d

7、);o o r 1 =L e a f (B t r c h i l d);8 t l=l 1 +r 1；r e t u r n t 1 ;i n t D e p t h (B T N o d e*B t)。/求二叉树的深度(高度)(i n t 1 d ,r d,t d;i f(!B t )。t d=0 ；e l s eo l d=D e p t h(B t-1 c h i l d );r d =D e p t h (B t-r c h i l d);-i f (l d =r d)。左右子树高度大的加1 ,即为二叉树的高度t d=l d+1 ；ooe 1 s ewt d=r d+1;r e t

8、ur n t d；void main()(BTNode*B t;oi n t s,t 1 ,td；Bt=NULL;pri n t f(nlnput create o rd e r:n )；B t=PreCrea t e(B t);p rintf(nT he p re o r d e r is:n);oPreorder(B t)；oprin t f(，z nT h e inorder i s:n)；Ino r d e r(B t);printf(nThe post o r d er is:n);P o s t o r d e r(B t);s=S i z e (B t);o p r i n t

9、f (，z n The s i z e o f t h e tree i s :n );o p r i n t f (%d n ,s )；t l =L e a f (B t);叩 r i n t f (n T h e l e a v e s o f t h e t r e e i s：n);p r i n t f (%d n ,t 1 )；t d=D e p t h (B t);p r i n t f (，z n T h e d e p t h o f t h e t r e e i s:n );o p r i n t f (%d n/,t d );1232历历历点右历历itwt子先中后叶交中

10、后DAE后JUJ4叔.子KCynctKyE H F J G B CJ F G D A B KG F E D K C B：1.先序遍历:B A D G F J EB G J F H E DcontinueKCAA B C K D E F G J HHA实 验 报 告五、实验结（涉及问题和解决方法、心得体会、意见与建议等）这是一门纯属于设计的科目，它需用把理论变为上机调试。刚开始学的时候的确有很多地方我很不理解，每次上课时老师都会给我们出不同的设计题目,对于我们一个初学者来说，无疑是一个具大的挑战，撞了几次壁之后，我决定静下心来，仔细去写程序。老师会给我们需要编程的内容一些讲解，顺着老师的思绪，来

11、完毕自己的设计,我们可以开始运营自己的程序。这门课结束之后，我总结了学习中碰到的一些问题，最为突出的，书本上的知识与老师的讲解都比较容易理解，但是当自己采用刚学的知识点编写程序时却感到十分棘手,有时表现在想不到适合题意的算法，有时表现在算法想出来后，只能将书本上原有的程序段誉写到自己的程序中再加以必要的连接以完毕程序的编写。刚开始学的时候的确有很多地方我很不理解，每次上上机课时老师都会给我们出不同的设计题目，对于我们一个初学者来说，无疑是一个具大的挑战，撞了几次壁之后，我决定静下心来，仔细去写程序。老师会给我们需要编程的内容一些讲解，顺着老师的思绪,来完毕自己的设计，我们可以开始运营自己的程序

12、，可是好多处的错误让人看的可怕,还看不出到底是哪里出现了错误，但是程序还是得继续下去，我多次请教了老师和同学,逐渐能自己找犯错误，并加以改正。T C里检查错误都是用英文来显示出来的，通过了这次课程设计，现在已经可以了解很多错误在英文里的提醒，这对我来说是一个突破性的进步，眼看着一个个错误通过自己的努力在我眼前消失，觉得很是开心。本次的程序设计可以成功，我很开心。在这一段努力学习的过程中，我们的编程设计有了明显的提高。其实现在想起来，收获还真是不少，虽然说以前非常不懂这门语言，在它上面花费了好多心血，觉得它很难，是需用花费了大量的时间编写出来的。现在真正的明白了一些代码的应用，每个程序都有一些共同点，通用的结构,相似的格式。只要努力去学习，就会灵活的去应用它。六、指导教师评语成 批阅人 日 期绩