《2023年数据结构与算法实验报告1.pdf》由会员分享，可在线阅读，更多相关《2023年数据结构与算法实验报告1.pdf（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、实 验 报 告课程名称_ _ _ _ _ _ _ _ _ _数据结构与算法_ _ _ _ _ _ _ _ _ _ _ _ _ _ _实验学期 2 0 2 3 年 春季 学期所在学院_ _ _ _ _ _ _交通科学与工程学院_ _ _ _ _ _ _ _ _ _ _ _所属专业 交通信息与控制工程系年级 2023 专业班级学生姓名 学号指导教师_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _实验最终成绩_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
2、_ _ _ _ _ _ _ _ _实验报告（三）实验题目二叉树的基本操作及应用实验时间2 0 2 3 年6 月 1 0 日实验地点B 0 7-B 2 1 4实验成绩实验性质应用性 口设计性 口综合性教师评阅：实验目的明确；操作环节对的D O 文稿（表格、程序、数据库、网页）符 合 规 定;保存途径对的；口实验结果对的；口实验分析总结全面；口实验报告规范；评阅教师署名：一、实验目的1 熟悉二叉树的存储结构和对二叉树的基本操作。2 掌握对二叉树前序、中序、后序遍历操作的具体实现。3 学习运用递归方法编写对二叉树这种递归数据结构进行解决的算法。4会应用二叉树的基本操作解决简朴的实际问题二、实验内容和
3、规定（说明算法的时间复杂度）1基于二叉链表的存储格式，输入二叉树的先序序列，用*代表空节点，如A B D*C E*F*建立二叉树，然后中序遍历二叉树,输出节点的值。2 针对建好的二叉树，编写递归程序，求树中叶子节点个数。3 针对建好的二叉树，编写递归程序,求二叉树的高度。4针对建好的二叉树，试编写二叉树的前序 城 侬 遍历算法。三、重要设计思想与算法(此处不够可加页，或在反面书写)该实验重要涉及一下几个函数,算法核心分别在各函数中。1.建立树的结构。t ypedef s t ruct Bi TNodeh a r e l e m e n t ;T r e e Ich i 1 d,r c h i
4、1 d ;；B数的基本结点输入 AB D*CE*F*T r e e C r ea t eBTree(v oi d)/可以返回一个 T r ee 指针T r e e pT r e e；y h a r v a 1;s c a n f (c,&v a l);叩 r i n t f (祝，v a l);“f (v a l=|v a l=二 人 p)r e t u r n NU L L;根据输入字符先序建树e l s e*代表空6 pT r e e=(T r e e)ma l l o c(s i ze o f(s t r u c t Bi T N o d e);i f(p T r e e=N UL L)
5、(。pr i n t f(内存分派失败！)；。e x i t(-l );防止程序不知道空间不够用了pT r e e-e 1 e me n t =v a 1 ；T r e e-l c h i l d=Cr e a t e BT r e e();pT r e e-r c h i 1 d =C r e a t e BT r e e O ；/递归,N L R 地创建结点or e turn pTr e e;2 .数叶结点个数i n t C o u n t L e a f(T r e e T)i f(T =N UL L )r e t u r n 0；o i f(!T l c h i l d&!T-r c
6、h i l d )(“r e t u r n 1 ;两个儿子都空则说明是叶子，返回1)e I s e(r e t u r n Co u n t L e a f(T-1 c h i I d)+Co u n t L e a f(T-r c h i I d);/数左右子树总共的叶结点)；3 .数树的深度i n t Co u n t L e v e l (T r e e T)(i f(!T)r e t u r n 0;e l s e(i n t L e f t =Co u n t L e v e l (T-1 c h i l d);i n t R i gh t=Co u n t L e v e l (
7、T-r c h i l d);r e t u r n 1+(L e f t R i gh t?L e ft：R i gh t)；/三目运算取最大)；最后数得树的最深层数，也是递归t y pe d e f s t r u c t Tree e l e m e n t s EM A XS I ZE；注意这里放的是指针i n t t o p;S t a c k；/这是一个用于装Tree指针的栈4,这是用非递归实现先序遍历的void Pr e O r d e r (T r e e T)(S t a c k S;o T r e e p；o I n i t S t a c k (&S);造一个栈待会儿用o
8、 p=T;用p 指针来不断解决结点操作w h i l e (p|!I s Em p t y (S)(w h i l e (p)*(。o pr i n t f(%c，,p e 1 e me n t);/只要不空则把p 指的数据输出Pu s h(&S,p);p=p-l c h i l d；继续往左边找。/一旦停下来说明找到了空结点，则开始往上一层的右边找一下i f(!I s E mp t y (S)。(栈非空。叩=Po p(&S)；退栈，找到刚才说的上一层p=p r c h i l d；找右边了 。/只要w h i l e 还循环说明没有遍历完,现在再一次从刚才的右边执行先序遍历)：四、实 验 结
9、 果（设计文档、文稿存放途径，可以截图描述实验结果）#i n c 1 u d e#i n e l u d e 3.h i n t ma i n(v o i d)改主程序相应上图结果0T r e e pT r e e;i n t i ,j ;o p T r e e =Cr e a t e B T r e e 0 ;/创建二叉树 pT r e e i=C o u n t L e a f(pT r e e);pr i n t f(T h e r e a r e%d 1 e a v e s!,i)；递归程序数叶节点o j=C o u n t L e v e l(p T r e e);o pr i n
10、t f(H T h e r e a r e%d l e v e 1 s!，j)；/递归程序数层数o P r e O r d e r(pT r e e);/按照前序遍历输出该书的元素r e t u r n 0 ；五、实验分析总结本次实验采用二叉树存储了一系列的字符串，通过函数T r e e Cr e a t eBT r e e(v o i d)得到一个根据输入创建的二叉树结构，时间复杂度是0 (n)；通 过 函 数i n t Co u n t L e a f(T r e e T)递归返回叶子个数，时间复杂度0 (n)；通 过i n t Co u n t L e v e 1 (T r e e T)
11、返回最深途径得到树的深度，时间复杂度 0(n)；;最 后 用v o i d Pr e O r d e r(T r e e T)实现非递归写法的二叉树先序遍历，时间复杂度为0(n).综上所述，由于都是要遍历B数的每个节点，所以程序执行的时间长度和输入的字符串长度n是线性增长的。他们的时间复杂度都是0(n).这次实验，我更深刻的理解了 B数的基本性质如递归性，运用递归，我们可以很方便的写出各种对树的操作；熟悉了创建树，遍历树的基本方法;体会了算法的代码实现细节。最后，特别是在用非递归方法实现遍历的函数中，我更加深刻的理解到了数是如何遍历的，以及递归是不断调用自己的本质，并且不仅仅对B T r e e自身有运用，之前学习的栈也用于存储遍历的节点指针，所以数据结构的学习应当是一个融会贯通的过程,我在学习的过程中越来越有信心了。