《2023年华中科技大学数据结构实验报告.pdf》由会员分享，可在线阅读，更多相关《2023年华中科技大学数据结构实验报告.pdf（91页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、年中科技火掌课 程 实 验 报 告课程名称：数据结构实验专业班级：信息安全202302学 号：_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _姓 名：_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _指导教师:_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _报告日期：2 023年1 0 月 2 8 日计算机科学与技术学院目 录批 注11:黑体小2号加租居中.间距前后0.5行1基于顺序存储结构的线性表实
2、现1。1.1问题描述。11 .2系统设计.错误!未定义书签I 3系统实现1。1.4实验小结1。2基于二叉链表的二叉树实现.22.1问题描述.22.2系统设计.22.3系统实现.22.4实验小结.2指导教师评估意见.3附录A基于顺序存储结构线性表实现的源程序。错误!未定义书签。附录B基于二叉链表二叉树实现的源程序.5批 注12:殳为宋体小4号加粗.其余宋体小4号，行间距1.5倍,段落前后。行1基于顺序存储结构的线性表实现1.1 问题描述采用顺序表的物理结构，构造一个具有菜单的功能演示系统。其中，在主程序中完毕函数调用所需实参值的准备和函数执行结果的显示。定义了线性表的初始化表、销毁表、清空表、鉴
3、定空表、求表长和获得元素等基本运算相应的函数,并给出适当的操作提醒显示,可选择以文献的形式进行存储和加载，即将生成的线性表存入到相应的文献中，也可以从文献中获取线性表进行操作。1.1.1 线性表的基本概念线性表是最常用且最简朴的一种数据结构,即n个数据元素的有限序列。线性表中元素的个数n定义为线性表的长度，n =0时成为空表。在非空表中的每个数据元素都有一个拟定的位置，如 a l 是第一个数据元素,a n 是最后一个数据元素,a i 是 第 i 个数据元素。线性表的存储结构分为线性存储和链式存储、1.1.2逻辑结构与基本运算线性表的数据逻辑结构定义如下：A D T L i s t 数据对象：D
4、=a i l a i G E l e m S e t,i =1,2,.,n ,n e O 数据关系：R l=|a i -1,a i G D,i=2,，n)依据最小完备性和常用性相结合的原则，以函数形式定义了涉及线性表的初始化表、加载表、保存表、销毁表、清空表、鉴定空表、求表长、获得元素、查找元素、获得前驱、获得后继、插入元素、删除元素、遍 历 表 1 4个基本运算，规定分别定义函数来实现上述功能，具体功能运算如下：初始化表：函数名称是I n i t a L i s t (L)；初始条件是线性表L不存在批 注 网：黑体小2加 机 居中.间距前后0.5行 批 注 14:黑体4号加机，间距前后0.5
5、彳己存在；操作结果是构造一个空的线性表。销毁表:函数名称是De s t r o y L i s t (L);初始条件是线性表L已存在；操作结果是销毁线性表L。清空表：函数名称是Cl e a r L i s t(L);初始条件是线性表L已存在;操作结果是将L重置为空表。鉴定空表：函数名称是L is t Em p t y (L);初始条件是线性表L已存在;操作结果是若L为空表则返回T R UE,否则返回F A L S Eo求表长：函数名称是L is t L e n g t h(L);初始条件是线性表已存在；操作结果是返回L中数据元素的个数。获得元素：函数名称是G e t El e m(L,i,e)
6、；初始条件是线性表已存在，1 WiWL i s t L e n g t h(L);操作结果是用e 返回L中第i 个数据元素的值。查找元素：函数名称是L o c at e El e m (L,e ,c o m p a r e ();初始条件是线性表已存在；操作结果是返回L中 第 1 个与e满足关系c o m p ar e ()关系的数据元素的位序,若这样的数据元素不存在，则返回值为0。获得前驱：函数名称是P r io r E 1 em(L,c u r _e,p r e _e)；初始条件是线性表L已存在；操作结果是若c u r _e 是 L的数据元素，且不是第一个，则用p r e _e 返回它的前
7、驱,否则操作失败,p r e _ e 无定义。获得后继：函数名称是Ne x t E 1 e m(L,c u r _e n e x t _ e )；初始条件是线性表L己存在；操作结果是若c u r _e 是 L的数据元素，且不是最后一个，则用 n e x t e 返回它的后继，否则操作失败，n e x t _e 无定义。(1 0)插入元素:函数名称是L is t in s e r t (L,i,e)；初始条件是线性表L己存在且非空，I WiWL is t L e n g t h(L)+l ；操作结果是在L的第i 个位置之前插入新的数据元素e。(1 1)删除元素:函数名称是L i s t De l
8、 e t e(L,i,e)；初始条件是线性表L已存在且非空，1(i WL is t L e n g t h(L);操作结果:删除L 的第i个数据元素,用 e 返回其值。遍历表：函数名称是L is t Tr a v e r s e(L,v is it (),初始条件是线性表L已存在；操作结果是依次对L的每个数据元素调用函数vis i t()。1.1.3 演示系统与数据文献规定构造一个具有菜单的功能演示系统。其中，在主程序中完毕函数调用所需实参值的准备和函数执行结果的显示，并给出适当的操作提醒显示。附 录A提供了简易菜单的框架。演示系统可选择实现线性表的文献形式保存。其中，需要设计文献数据记录格式
9、，以高效保存线性表数据逻辑结构(D,R)的完整信息；需要设计线性表文献保存和加载操作合理模式。附 录B提供了文献存取的方法。演示系统可选择实现多个线性表管理。1.2系统设计批 注 ：*休4号加机.间距前后0.5 if1.2.1 数据物理结构线性表的数据物理结构如下：typedef s t r u c t /顺序表(顺序结构)的定义El e m T ype*elem;定义整型指针,为存储空间基址int 1 e ngt h;线性表的长度i n t li s ts i z e;当前分派的存储容量(以siz e of(ElemType)为单位)SqList;。要实现同时对多个线性表管理，只需要定义一个
10、结构数组即可。1.2.2 演示系统将菜单演示和用户选择写入到whi l e循环中，用0 P获取用户的选择,0P初始化为1,以便第一次能进入循环。进入循环后系统一方面显示功能菜单，然后用户输入选择0T 4,其中1-14分别代表线性表的一个基本运算，在主函数中通 过SW I TCH语句相应到相应的函数功能，执行完该功能后BR EAK跳 出S W ITCH语句，继续执行whi 1 e循环,直至用户输入0退出当前演示系统。在第一次进入循环while时一方面会询问用户对哪个线性表进行操作，直至退出演示系统之前一直对指定线性表进行操作。演示系统结构如图1 1.菜单功能演示系统T 输入数字选择功能3 输入操
11、作的线性枭的序号-*1初蛤化表f2.销盘表3清空表4判断空表T5.求表长T6.获得元素7查找元素&获得前驱一 9.获得后继T10.插入元素1 1*除元素T12遍历表13将线性表存入文件14从文件申读取线性表0.退出系统图1-1系统设计结构图1.2.3 运算算法思想与设计线性表运算算法思想与设计如下：1.初始化线性表思想：将线性表初始化过程写成函数,其中传入函数的参数是主函数中定义的结构型变量L的引用，在函数中，一方面使用malloc函 数 分 派LISTSIZE大小的连续内存空间，并将首地址返回赋值给L.elem,由于线性表的长度为0,将L.1 engt h初始化为0,即完毕了线性表的初始化。
12、经分析，算法的时间复杂度为0(l)o2.销毁线性表思想:将销毁线性表的过程写成函数,其中传入函数是主函数中定义的结构性变量L在函数中，一方面使用f r e e函数释放掉以L.e1 em为首地址的连续内存空间，再将L.1 ength,L.lis t siz e重新赋值为0。经分析，该算法的时间复杂度为0(1)。3.清空线性表的思想：将清空表的过程写成函数，其中将主函数中定义的结构性变量L的引用作为函数参数，在函数中，由于清空操作并不释放内存空间，故只需将线性表的长度置为0即可。经分许，该算法的时间复杂度为0(1).4.求线性表表长的思想:将求表长过程写成函数，其中主函数中定义的结构性变量L的引用
13、作为函数的参数,在函数中，直接返回L.1 e ngt h即为所求线性表的表长。经分析，该算法的时间复杂度为0(1)。5.获得元素的算法思想:将获得线性表元素写成函数,其中函数的参数是结构型变量L以及数据元素的序号i,由于采用的是线性存储结构，故直接通过访问数组的方式即L.来获取元素，当然，在这之前需要判断合法性。经分析，该算法的时间复杂度为0(1)。6.查找元素的算法思想:将查找线性表特定值的数据元素写成函数，其中函数的参数是主函数中定义的结构类型变量L以及查找的数据元素的值，通过循环对线性表中的每一个元素与给定值比较看是否相等，假如相等就返回该元素的顺序。经分析，该算法的时间复杂度为0(n)
14、。查找算法的流程图如图1-2所示。开始图1-2线性表查找算法流程图7.获得前驱算法思想:将获得前驱过程写成函数，函数的参数是结构体类型变量以及特定数据元素的值,接受前驱的变量作为另一个参数，一方面调用获得元素的函数判断该线性表中特定数据元素的位序，一方面判断不为1,否则的话返回FALSE,然后直接返回其前一个元素即L.elem j-2 o经分析，该算法的时间复杂度为0(n)。8.获得后继算法思想:将获得后继写成函数，函数的参数是结构体类型变量以及特定数据元素的值。一方面判断是否为最后一个元素,假如不是则直接返回其后一个元素，否则的话返回F ALSE,同样该算法需要调用获得元素的函数来拟定该特定
15、元素在线性表中的顺序。经分析,该算法的时间复杂度为0(n)。9.插入元素算法思想:将插入函数写成函数，函数的参数是结构型变量以及插入元素的值大小以及插入位置。在函数中,一方面判断插入位置的合法性,即是否在线性表中合适的位置，另一方面还要判断当前存储空间是否己满，假如满了的话要mal lo c函数重新分派空间，插入元素时从该位置起到最后一个元素从后开始以此往后移一个单元。经分析,该算法的时间 复 杂 度 为0(n)o该 算 法 的 程 序 流 程 图 如 图1-3所 示。图1-3线性表中插入元素算法流程图10.删除元素算法思想:将删除线性表中元素写成函数，函数的参数是结构类型变量,一方面判断位序
16、的合法性,在之后直接将删除元素位置后一个元素直到最后一个元素以此从前往后向前移动一个单元。经分析,该算法的时间复杂度为0(n)。11.遍历线性表算法思想：将遍历线性表写成一个函数，函数的参数是结构类型变量，直接用一个循环来对线性表中的每一个元素进行操作。经分析，该算法的时间复杂度为0(n)o1.3 系统实现1.3.1 编程环境 运营环境、项目工程描述本次实验采用M i c r。s o f t Visu a 1 Studio 2023编程软件编写，并批 注 1 6 J:图内容：字体大小参考宋体5 号，居中批 注 ：黑体4号加粗，间距前后0.5行用VS2023进行编译运营，项目名称是linear
17、d a t a structe r 01.3.2 头文献及预定义常说明1.头文献#i nc 1 u de#i n c 1 ude#inc I u de 2.预定义常量#de f ine TRUE 1#d e fin e FALS E 0#define O K 1#def i ne ERROR 0#def i ne INFEAST A B LE-1#d e f i n e O V E RF LO W -2#d e f i n e LI S T _ I N I T _ S I Z E 1 0 0#d e f i n e LI S T I N C RE M E N T 1 03.类型表达式t y p
18、 e d e f i n t s t a t u s;t y p e d e f i n t E l e m T y p e;1.3.3 系统演示操作1 .系统一开始会显示菜单提醒用户输入选择对1 9 9 号线性表哪一个进行操作。如图1-4 所示。图 1 -4系统演示12 .选择对线性表1 进行操作，进入菜单演示界面,如图1-5 所示。SI C:WINDOWSsystem32cmd.exe XMenu for Linear Table On Sequence Structure1.IntiaList2.DestroyList3.ClearList4.ListEmpty5.ListLength6
19、.GetElem7.LocateElem0.ExitPriorElemNextElemListinsertListDeleteListTrabverseSaveDataDataLoading请选择你的操作图1-5系统演示23.选择退出0,此时会退出当前演示界面，即退出对当前线性表的操作，并显示规定用户选择对哪一个线性表进行操作。如图1 6所示。图1-6演示系统3儿输入0,退出演示系统，结束操作，如图-7所示。SI C:WINDOWSsystem32cmd.exe X线性表迸仃景作卜99,欢迎下次再使用本系统!请按任意键继续.图1-7 系统演示41.3.4测试计划测试功能及序号输入要管理的线性表
20、序号输入函数的参数（具体元素）预计输出此时线性表的状态1.I n t i a L i st1无线性表初始化成功分派了连续的物理存储空间，表长度为0,表尺寸为空间大小2.D e s t r o y Li s t1无线性表删除成功线性表连续物理空间被释放，3.C l e a r Li st1无线性表清空成功线性表的物理空间保存，但表长置为0.1 0.L ist In s e r t （多次调用）1输 入1:1,2 ：2 ,3:3 ,4 ：4,5:5线性表创建成功创建了一个线性表，序列为：1,2,3,4,54.L i s t E m pt y1无输出线性表非空同上5.Li s t L eng t h
21、1无输出线性表的长度为5同上6.G e tElem1输入数据元素的位序为3输出线性表的第三个元素为3同上8.P ri o rE 1em1输入数据元素的值为4输 出 4 的前面一个元素是3同上9.NextEl e m1输入数据元素的值为2输出2的后面一个元素是3同上11.L i stDelet e1输入数据元素的置为3输出元素删除成功重新生成了一新的线性表，序列为1 2457.Loca t eEie m1输入数据元素的值为4输出4是线性表中的第三个数据元素同上1 3.Sa v e Data1输入保存到的文 献 名 为LY.txt输出文献保存成功同上1 4.D a t aL oading1输入要加
22、载的文 献 名 为 LY.txt输出文献加载成功同上1.3.5 测试1.输入对线性表1 进行操作，进入菜单演示界面，执行功能1,初始化线性表，测试结果如图1-8 所示。OS C:WINDOWSsystem32cmd.exe 一 XMenu for Linear Table On Sequence Structure1.Intiahist8.PriorEletn2.DestroyList9.NextElem3.ClearList10.Listinsert4.ListEmpty11.ListDelete5.ListLength12.ListTrabverse6.GetElem13.SaveData
23、7.LocateElem14.DataLoading0.Exit请选择你的操作1线性表创建成功！图 1-8 初始化线性表的测试结果2.执行功能2,销毁线性表,测试结果如图1 -9 所示。图 1-9 删除线性表的操作结果3.执行功能10,往线性表中添加数据元素1,2,3,4,5,测试结果如图1 -10所示。S I C:WINDOWSsystem32cmd.exeXMenu for Linear Table On Sequence Structure1.IntiaList8.PriorElem2.DestroyList9.NextElem3.ClearList10.Listinsert4.List
24、Empty11.ListDelete5.ListLength12.ListTrabverse6.GetElem13.SaveData7.LocateElem14.DataLoading0.Exit请选择你的操作10请输入插入新的数据元素位置以及数据元素值!插入成功，表的长度为5图1-10插入元素的测试结果4.执行功能4,判断线性表是否为空，测试结果如图1 T 1所示。3S C:WINDOWSsystem32cmd.exeXMenu for Linear Table On Sequence StructureIntiaListDestroyListClearListListEmptyListLe
25、ngthGetElemLocateElemExitPriorElemNextElemListinsertListDeleteListTrabverseSaveDataDataLoading请选择你的操作E0-12:戋性表不是空表！图1-1 1判断线性表非空的测试结果5.执行功能5,求线性表的长度,测试结果如图1T 2 所示。SB C:WINDOWSsystem32cmd.exeXMenu for Linear Table On Sequence Structure1.2.3.4.5.7.0.IntiaListDestroyListClearListListEmptyListLengthGetE
26、lemLocateElemExitPriorElemNextElemListinsertListDeleteListTrabverseSaveDataDataLoading请选择你的操作线性表的长度是5!图1-12求线性表长度的测试结果6.执行功能6,查找第三个数据元素的数值,测试结果如图1T 3所示。图1-1 3查找数据元素的测试结果7.执行功能8,拟定值为4的数据元素前驱数据元素,测试结果如图1 14所示。SB C:WINDOWSsystem32cmd.exeXMenu for Linear Table On Sequence Structure1.2.3.4.5.7.0.IntiaLis
27、tDestroyListClearListListEmptyListLengthGetElemLocateElemExitPriorElemNextElemListinsertListDeleteListTrabverseSaveDataDataLoading请选择你的操作请输入数据元素！数据元素4的前驱数据元素为3!图 1-1 4 查找元素的前驱数据元素8.执行功能9,拟定值为2 的数据元素的后继数据元素,测试结果如图1T5所示。1-1 5 查找元素的后继数据元素9.执行功能1 1,删除第三个数据元素，测试结果如图1-1 6 所示。SB C:WINDOWSsystem32cmd.exeXMe
28、nu for Linear Table On Sequence Structure1.2.3.4.5.7.0.IntiaListDestroyListClearListListEmptyListLengthGetElemLocateElemExitPriorElemNextElemListinsertListDeleteListTrabverseSaveDataDataLoading请选择你的操作11请输入需删除的数据元素在线性表中的位序!删除的元素为3,表的长度是4!图1-1 6删除线性表中的数据元素测试结果10.执行功能1 3,保存线性表中的数据元素值到文献名为LY.t x t的文献中，测
29、试结果如图1 17所示。图1-17保存线性表测试结果11.清空此时的线性表,在执行功能14,加载线性表，测试结果如图1-18所示。SI C:WINDOWSsystem32cmd.exe XMenu for Linear Table On Sequence Structure1.IntiaList2.DestroyList3.ClearList4.ListEmpty5.ListLength6.GetElem7.LocateElem0.ExitPriorElemNextElemListinsertListDeleteListTrabverseSaveDataDataLoading请选择你的操作14
30、请输入需加载的文件名：LY.txt文件成功加载到当前线性表!图1-1 8线性表加载的测试结果1 1.执行功能1 2,遍历并输出线性表中的元素，应当输出1 2 4 5,测试结果如图1-1 9所示。图卜1 9遍历输出线性表中元素的测试结果1.4实验小结批 注。8:黑 体4号 加 机.间 距 前 后0.5(T。通过本次实验,我充足了解到了线性表的物理结构,并且通过切身的体会纯熟掌握了线性表的基本操作,提高了自己写有关线性表的代码的能力，特别是在写的过程中碰到了许多困难，在多次寻求同学的帮助下终于解决了。还发现了自己的薄弱之处,就是在文献的解决时存在许多维漏,导致文献读取不成功。并且我还加深了对线性表
31、的存在与空的区别。尚 有 对 引 用 符 号 的 理 解，加强了其与“*”的区别，“&e”使得在函数中调用主函数中的值“e”时可以同时更改其值，如在G e t E le m 函数中调用了“e”的值然后在主函数中输出，假如要更改其值的话就 必 须 要 用 符 号。2基于二叉链表的二叉树实现2.1问题描述采用二叉链表作为二叉树的物理结构，实现二叉树的基本运算，数据元素的类型名可自行定义。规定构造一个具有菜单的功能演示系统,其中，在主程序中完毕函数调用所需实参值的准备和函数执行结果的显示，并给出适当的操作提醒。2.1.1 二叉树的基本概念二叉树是一种树型结构，即 n个结点的有限集，它的特点是每个结点
32、至多只有两棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分，其顺序不能任意颠倒。批注：黑体小2加机，居中，间距前后0.5行，每章另起页批注 110:黑体4号加粗，间距前后0.5行2.1.2 逻辑结构与基本运算抽象数据类型二叉树的定义如下：A D T B i n a r y T r e e 数据对象D:D 是具有相同特性的数据元素的集合。数据关系R：a 若 D =,则 R=，称 B i n a r y T r e e 为空二叉树；若 D#中，则 R=1 1 ,H是如下二元关系:(1)在 D 中存在唯一的成为根的数据元素r。t,它在关系H中无前驱；(2)若 D-ro o t
33、W 8,则存在 Droot =DI,D r,5.D l HDr=;(3)若 D I#中，则 D I中存在唯一的元素XI,eH,且存在D r上的关系属于H；(4)(D,Hl)是一棵符合本定义的二叉树，称为根的左子树，(Dr,Hr)是一棵符合本定义的二叉树,称为根的右子树。依据最小最小完备性和常用性相结合的原则，以函数形式定义了二叉树的初始化、销毁二叉树、创建二叉树、清空二叉树、鉴定空二叉树和求二叉树深度等2 0 种基本运算，具体运算功能定义如下：初始化二叉树:函数名称是InitBiTree(T);初始条件是二叉树T 不存在；操作结果是构造空二叉树T。销毁二叉：树函数名称是Des t royBiT
34、ree(T);初始条件是二叉树T 己存在;操作结果是销毁二叉树T。创建二叉树：函数名称是Create BiTre e(T,de f ini t io n)；初始条件是d ef i nition给出二叉树T 的定义；操作结果是按definition构造二叉树T。清空二叉树:函数名称是Cl e arBiTr e e(T);初始条件是二叉树T 存在；。操作结果是将二叉树T 清空。鉴定空二叉树:函数名称是BiTre e E mpty(T);初始条件是二叉树T 存在；操作结果是若T 为空二叉树则返回TRUE,否则返回FALSE。求二叉树深度:函数名称是B i TreeDe p th(T);初始条件是二叉
35、树T 存在;操作结果是返回T 的深度。获得根结点：函数名称是R oot(T);初始条件是二叉树T 己存在;操作结果是返回T的根。获得结点：函数名称是Valu e(T,e);初始条件是二叉树T己存在,e是T中的某个结点；操作结果是返回e的值。结点赋值:函数名称是As s ign(T,&e,valu e)；初始条件是二叉树T己存在,e是T中的某个结点;操作结果是结点e赋值为va 1 u e o获得双亲结点：函数名称是P arent(T,e);初始条件是二叉树T己存在,e是T中的某个结点;操作结果是若e是T的非根结点，则返回它的双亲结点指针，否则返回NULL。8)获得左孩子结点：函数名称是LeftC
36、hild(T,e);初始条件是二叉树T存在,e是T中某个节点；操作结果是返回e的左孩子结点指针。若e无左孩子，则返回NULL。获得右孩子结点:函数名称是Right Child(T,e)；初始条件是二叉树T己存在，e是T中某个结点；操作结果是返回e的右孩子结点指针。若e无右孩子,则返回NULL。获得左兄弟结点:函数名称是Le ftSib 1 i ng(T,e);初始条件是二叉树T存在,e是T中某个结点;操作结果是返回e的左兄弟结点指针。若e是T的左孩子或者无左兄弟,则返回NULL。获得右兄弟结点:函数名称是R i ghtSibling(T,e);初始条件是二叉树T已存在,e是T中某个结点;操作结
37、果是返回e的右兄弟结点指针。若e是T的右孩子或者无有兄弟，则返回NULL。(1 5)插入子树：函数名称是In s ertChi 1 d(T,p,LR,c)；初始条件是二叉树T存在，p指向T中的某个结点，L R为0或1,非空二叉树c与T不相交且右子树为空;操作结果是根据L R为0或 者1,插入c为T中p所指结点的左或右子树，P。所指结点的原有左子树或右子树则为c的右子树。删除子树：函数名称是DeleteChild(T.p.LR)；初始条件是二叉树T存在,p指向T中的某个结点，LR为0或1。操作结果是根据L R为0或 者1,删 除c为 T 中 p 所指结点的左或右子树。前序遍历：函数名称是Pr e
38、 Or d erTr a ve r se(T,Visi t();初始条件是二叉树T 存在,V i s i t 是对结点操作的应用函数;操作结果:先序遍历t,对每个结点调用函数Visit一次且一次，一旦调用失败,则操作失败。(18)中序遍历：函数名称是InOrde r Tr a v e rse(T,V isit);初始条件是二叉树 T 存在，V i si t 是对结点操作的应用函数;操作结果是中序遍历t,对每个结点调用函数V i s i t 一次且一次，一旦调用失败，则操作失败。后序遍历:函数名称是PostO r derTrave r se(T,V i s it);初始条件是二叉树T 存在，Vi
39、si t 是对结点操作的应用函数;操作结果是后序遍历t,对每个结点调用函数Visit一次且一次，一旦调用失败，则操作失败。按层遍历:函数名称是Level OrdefTrave r se(T,Vi s i t)；初始条件是二叉树T 存在,Vis i t 是对结点操作的应用函数;操作结果是层序遍历I,对每个结点调用函数Visit一次且一次，一旦调用失败，则操作失败。2.1.3演示系统与数据文献。规定构造一个具有菜单的功能演示系统。其中，在主函数中完毕函数调用所需实参值的准备和函数执行结果的显示，并给出适当的操作提醒。附录A 中给出了简朴菜单的框架。演示系统可选择实现线性表的文献形式保存,演示系统可
40、选择实现多个线性表的管理。2.2系统设计2.2.1数据物理结构二叉树的数据物理结构如下：ty p ede f s truct Bi T Nod e TE 1 emType d a ta;J批 注111:里、体4号加粗，间 距 前 后0,5行dstruct B i TN ode*1 c h i 1 d,*rchil d;左右孩子指针i n t i n d e x;B i T N o d e,*B i T r e e;t y p e d e f 是将结构类型定义s t r u e t B i T N o d e 取另i j 名为B i T N o d e2.2.2演示系统M各菜单演示和用户选择输入
41、写入到w h i l e 循环中，用 o p 获取用户的选择。O p初始化为1,以便第一次能进入循环。进入w h i 1 e循环后，系统一方面显示功能菜单，然后提醒用户输入选择（0 2 0）,其 中 1-2 0相应二叉树的一个基本操作，分别相应一个函数，通 过 s w i t c h 语句将用户输入的序号相应到相应的函数功能，执行完该语句后b r e a k 跳出s w i t c h 语句,执行w h i l e循环,直到用户输入 0 选择退出，退出系统。1.初始化二叉树2.销般二叉树3.创建二叉树4.清空二叉树5、和层空二叉树6.茨二叉树深度7.拓寻根培点&获 得 结 点9、结点!S值耨助
42、能砺*-输 入 蝌 序 号 卜T 输入操作线性表的序号|-A1 0.获得双亲结点-A11 获 得 左 孩 点12获得右孩子结点13获得左兄弟结点14获得右兄弟结点15、插入子捕1 6.删除子树T1 7.前序遍历1 8.中序遍历1 1 9.后段遍历2 0.层序通历图2 T系统设计结构图2.2.3运算算法思想与设计。二叉树运算算法思想与设计如下：1、初始化二叉树算法思想：将初始化二叉树过程写成函数，函数的参数是主函数中所定义的结构类型指针T(参数传递为引用方式,即取别名)，T所指向的是二叉树的根结点，将T赋值为NULL即完毕了二叉树的初始化。经分析，该算法的时间复杂度为0(1)。2、销毁二叉树算法
43、思想：将二叉树的销毁过程写成函数，函数的参数是指向二叉树根结点的结构类型指针T,采用递归的方式先销毁二叉树的左子树,在销毁二叉树的右子树,最后用f r e e函数释放掉根结点相应的内存空间。经分析，该算法的时间复杂度为0(n)。3、创建二叉树算法思想:将二叉树的创建过程写成函数，函数的参数是指向二叉树根结点的结构类型指针T,按照先序顺序输入二叉树中结点的值，假如第一个字符为#,则T为空二叉树。否则，mal 1 o c函数分派一个单元的空间作为树的根结点，并为其赋值,采用递归的方式继续创建根结点的左子树和右子树。经分析，该算法的时间复杂度为0(n)。4、清空二叉树算法思想：将二叉树的清空过程写成
44、函数，函数的参数同上,将根结点的左右孩子指针置为空，此时其左右子树的存储空间并未释放掉。经分析,该算法的时间复杂度为0(1)。5、鉴定空二叉树的算法思想:将鉴定空二叉树写成函数，对于一个二叉树，若根结点不存在则为空二叉树，否则不是空二叉树,那么只需要判断指向根结点的结构类型指针T是否为空即可。经分析,该算法的时间复杂度为0(1)。6、求二叉树的深度算法思想：将求二叉树的深度写成函数,采用递归的方式求二叉树的深度，假如根结点的左右孩子都不存在，则返回树的深度为1,否则的话返回根结点左右子树的深度的最大加上一。经分析,该算法的时间复杂度为0(n)。7、获得二叉树根结点的算法思想：将求二叉树根结点写
45、成函数，传入头结点,若其头指针不为空，则返回该结点的关键字信息。经分析，该算法的时间复杂度为0(1)。8、获得结点的算法思想是：将获得关键字结点写成函数，函数的参数是二叉树的头指针以及主函数中输入的关键字，通过递归先序遍历二叉树,即先比较根结点的关键字与给定是否一致，若一致,返回该结点的I N D E X 值，否则继续分别递归遍历其左子树和右子树。或者采用非递归的方式，即使用堆栈来存储根结点的信息,先将根结点入栈，在循环中弹出栈顶元素,比较关键字，在分别将其右子树和左子树的根结点入栈。经分析，该算法的时间复杂度为0(n)。9、结点赋值的算法思想是：将结点赋值写成函数，函数的参数是二叉树的头指针
46、，主函数中输入的关键字,根据关键字获取到根结点，并对根结点赋值，思想同8,不在赘述。经分析，该算法的时间复杂度为0 (n)o1 0、获得双亲结点的算法思想是:将获得双亲结点写成函数，函数的参数是二叉树的头指针,若头指针为空，则返回空；否则，假如头指针左孩子或右孩子不为空且关键字与给定关键字相同，返回根结点，假如不同，采用递归的方式调用原函数，传入的参数分别为根结点的左右子树的根结点。经分析，该算法的时间复杂度为0 (n)o1 1,获得左兄弟结点的算法思想是：将获得左孩子结点写成函数，函数的参数是二叉树的头指针，假如头指针为空，返回N U L L；否则，假如二叉树的根结点的右孩子关键字与给定关键
47、字一致，返回根结点的左孩子。假如不一致，继续递归调用原函数,传入的参数为二叉树根结点的左子树的根结点指针，假如函数的返回值非空，则返回该值，否则继续调用原函数,传入的参数是二叉树根结点的右子树的根结点指针,假如函数的返回值为非空，则返回该值，否则返回N U L L。经分析，该算法的时间复杂度为0(n )12、获得右兄弟结点的算法思想是:算法思想同上。经分析，该算法的时间复杂度为0(n)。13、获得左孩子结点的算法思想是:将获得左孩子结点写成函数，函数的参数是二叉树的头指针。假如根结点的关键字与给定关键字一致，且其左孩子存在,则返回其左孩子关键字,否则递归调用原函数分别将根结点的左右子树根结点指
48、针作为形参,若返回值非空则返回该值。经分析，该算法的时间复杂度为0(n)o14、获得右孩子结点的算法思想是:算法思想同上。经分析，该算法的时间复杂度为0(n)。15、插入子树的算法思想是:将插入子树写成函数，函数的形参是二叉树的头指针T,指向特定二叉树结点的指针P(在主函数中规定输入关键字,通过FIND函数找到插入点位置并将其值记录)，再调用Great e Bi T Nod e函数创建根结点c的右子树为空的二叉树，插入的过程即将P所指向结点的左子树或者右子树根结点指针赋值给c的右孩子指针域，而c吠值给P所指结点的左指针域或者右指针域。经分析，该算法的时间复杂度为0(n)。16、删除子树的算法思
49、想是：将删除子树写成函数，函数的形参是二叉树的头指针,特定结点的指针,根据指向特定结点的指针找到给结点并将其左右孩子指针域置为空，相应的还应当在这之前调用DESTROY函数将其左子树或右子树销毁。经分析，该算法的时间复杂度为0(n)。17、前序遍历的算法思想是:将前序遍历写成函数，函数的形参是二叉树的头指针,一方面访问根结点,并对其执行遍历操作，操作成功后采用递归的方式遍历根结点的左子树，返回值为0K时继续遍历其右子树，最终遍历完毕。递归方法前序遍历、中序遍历以及后序遍历的主线区别在与访问根结点的操作是在两次递归操作之间之前还是之后。经分许，该算法的时间复杂度为0(n)。18、非递归前序遍历的
50、算法思想是:将非递归前序遍历写成函数，函数的形参是二叉树的头指针,仿照递归过程堆栈的使用，一方面将根结点的值压入堆栈,执行循环体，堆栈非空,弹出根结点并执行访问操作,将其右子树根结点指针压入堆栈,再将其左子树根结点指针压入堆栈，执行循环。经分析，该算法的时间复杂度为0(n)。19、非递归中序遍历的算法思想是：将非递归中序遍历写成函数，函数的形参是二叉树的头指针,一方面将根结点的值压入堆栈,然后一直向左,将根结点依次压入堆栈，判断堆栈非空,将栈顶元素弹出，访问该结点,假如其右子树非空,对其右子树执行循环操作。经分析,该算法的时间复杂度为0(n).20、层序遍历的算法思想是：将层序遍历写成函数，函