华中科技大学数据结构实验实验1-4综合

等中利技火掌课程实验报告课程名称： 数据结构实验专业班级：计算机科学与技术学号： U201414596姓名： 卢振兴指导教师： 周时阳报告日期： 2016年12月8日.计算机科学与技术学院目录TOC\o"1-5"\h\z\o"CurrentDocument"1基于顺序存储结构的线性表实现 1\o"CurrentDocument"实验目的 1\o"CurrentDocument"线性表演示系统设计 1\o"CurrentDocument"系统测试与结果 8\o"CurrentDocument"实验小结 14\o"CurrentDocument"2基于链式存储结构的线性表实现 15\o"CurrentDocument"实验目的 15\o"CurrentDocument"程序设计概要 15\o"CurrentDocument"系统测试与结果 23\o"CurrentDocument"实验小结 28\o"CurrentDocument"3基于二叉链表的二叉树实现 30\o"CurrentDocument"实验目的 30\o"CurrentDocument"程序设计概要 30\o"CurrentDocument"系统测试与结果 45\o"CurrentDocument"实验小结 55\o"CurrentDocument"4基于邻接表的图实现 56\o"CurrentDocument"4.1实验目的 56\o"CurrentDocument"程序设计概要 56\o"CurrentDocument"系统测试与结果 63\o"CurrentDocument"实验小结 75\o"CurrentDocument"参考文献 76\o"CurrentDocument"附录A顺序表实现程序清单 77\o"CurrentDocument"附录B链表实现程序清单 97\o"CurrentDocument"附录C二叉树实现程序清单 120\o"CurrentDocument"附录D基于邻接表的图实现程序清单 1611基于顺序存储结构的线性表实现实验目的通过构建对线性表操作的运算函数，理解线性表的概念以及基本的运算，并掌握线性表逻辑结构与物理结构的关系。与此同时，构建简易的菜单框架，实现对线性表的管理和操作。线性表演示系统设计设计目标本实验旨在设计一个能对顺序存储的线性表进行运算的系统。本演示系统提供的操作包括：表的初始化、销毁、清空、判空，求表长、获取数据元素、查找数据元素、获得前驱、获得后继、创建线性表、插入数据元素、删除数据元素以及表的遍历。与此同时，本系统支持数据的加载以及数据的保存。本系统在程序进行时可实现消息处理，其中包括数据的输入和输出以及程序的退出。有关常量和类型的定义首先，需要定义函数的返回状态。这些状态包括正确、错误、可行、运行非法、不可实行和溢出。这些状态分别用TRUE、FALSE,OK、ERROR,INFEASTABLE和OVERFLOW表示。defineTRUE1defineFALSE0defineOK1defineERROR0defineINFEASTABLE-1defineOVERFLOW-2其次，需要定义线性表的初始大小以及线性表满后所需要的增加量。分别用LISTJNIT_SIZEftlLISTINCREMENT表示。#defineLIST_INIT_SIZE100defineLISTINCREMENT10另外，需要对数据元素类型进行定义。这包括函数的返回类型Status,以及所用到的参数类型ElemType。typedefintStatus;typedefintElemType;函数定义、算法设计及分析实验需要对线性表进行初始化、销毁、清空、判空，求表长、获取数据元素、查找数据元素、获得前驱、获得后继、创建线性表、插入数据元素、删除数据元素、遍历线性表、数据加载以及数据保存等操作。为实现这些操作，需要对功能函数进行如下的定义。InitList(&L)操作结果：构造一个空的线性表。DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。ClearList(&L)初始条件：线性表L已存在。操作结果：将L重置为空表。ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE,否则返回FALSE。ListLength(L)初始条件：线性表已存在。操作结果：返回L中数据元素的个数。GetElem(L,i,&e)初始条件：线性表已存在，iWiWListLength(L)。操作结果：用e返回L中第i个数据元素的值。LocateElem(L,e.mode)初始条件：线性表L已存在。操作结果：返回L中第1个与e满足关系mode关系的数据元素的位序,若这样的数据元素不存在，则返回值为0。PriorElem(L,cur_e,&pre_e)初始条件：线性表L已存在。操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。NextElem(L,cur_e.&next_e)初始条件：线性表L已存在。操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。ListInsert(&L,i,e)初始条件：线性表L已存在且非空，1Wi《ListLength(L)+l。操作结果：在L的第i个位置之前插入新的数据元素e,L的长度加1ListDelete(&L,i,&e)初始条件：线性表L已存在且非空，l《i〈ListLength(L)。操作结果：删除L的第i个数据元素，用e返回其值，L的长度减1.ListTraverse(L)初始条件：线性表L己存在。操作结果：依次访问线性表L中的每个数据项，并将将数据项依次打印出来。SaveList(L,char*filename);初始条件：线性表L已存在。操作结果：将线性表以二进制储存的方式保存到指定文件中。LoadList(&L,char*filename);初始条件：线性表L已存在。操作结果：从指定文件中读取线性表信息。功能函数的源代码详见附录Ao在上述定义的函数中，InitList(&L)、ListInsert(&L,i,e)、LocateElem(L,e>mode)和ListDelete(&L,i,&e)是最为重要的四个函数。它们分别对应着线性表的构造、数据的添加、数据的定位以及数据的删除。InitList(&L)函数为已定义的线性表L分配存储空间，并设定初始长度值和初始空间大小。其程序流程如图1-1所示。

图1-1InitList(&L)程序流程ListInsert(&L,i,e)函数负责向已初始化的线性表的具体位置插入元素。若所插入的位置超过了线性表现有的总长度加1,则返回错误。其流程图如图1-2所

图1-2ListInsert(&L,i,e)程序流程LocateElem(L,e,mode)函数负责寻找线性表表中与e满足mode关系的元素的序号。mode关系分为三种，分别是大于、小于和等于。函数返回满足条件的元素在线性表中的序号。其程序流程如图1-3所示。

图1・3LocateElem(L,e,mode)程序流程ListDelete(&L,i,&e)用于删除线性表中相应序号的元素，用e值返回被删除的元素，与此同时，将线性表的长度减去1。其程序流程如图1.4所示。图1-4ListDelete(&L,i,&e)流程图1.2.4复杂性分析在线性表的存储结构中，插入或者删除一个元素的主要时间会耗费在移动元素上；因此，可以通过分析移动元素的操作来预估算法时间复杂度。在顺序存储结构的线性表中插入或删除一个元素，平均需要移动表中一半的元素，因此，其时间复杂度为O(n)。确定元素位置以及列出表中所有元素都最多需要遍历表中所有的元素，因此，它们的时间复杂度也是O(n)。其他的算法不需要遍历元素，也不需要移动元素；因此，它们的时间复杂度均为0(1)。线性表操作函数的时间复杂度如表1-1所示。表1-1线性表操作函数时间复杂度函数时间复杂度函数时间复杂度InitialList0(1)LocatElem0(n)DestroyList0(1)PriorElem0(1)ClearList0(1)NextElem0(1)ListEmpy0(1)ListinsertO(n)ListLenth0(1)ListDelete0(n)GetElem0(1)ListTrabverse0(n)1.3系统测试与结果系统的测试主要检查①系统是否能够不报错地正常运行；②线性表的各项操作是否正确，包括插入元素、删除元素、确定元素位置等等；③线性表是否具有容错性；比如，在表未初始化时，进行插入元素操作能够提示“线性表不存在”，④线性表的保存与读取是否正常。具体的测试用例方案如图表1-2所示。

表1-2测试用例总体规划表测试用例程序输入理论结果用例1输入’1'成功新建一个线性表，并能够执行其他操作用例2输入’10',并按表1-2输入数据成功向线性表中插入了一系列的参数，共6个元素用例3输入’11',并输入'6'成功删除线性表中的第6个元素用例4输入’⑵列出线性表中的所有元素用例5输入'6',并输入'1'读取线性表中的第二个元素用例6输入’7',输入’1',再输入‘168’读出‘168'元素所在序号用例7输入'8',并输入'168'读出‘168'元素的前一个元素用例8输入'9',并输入‘168'读出‘168'元素的后一个元素用例9输入’5'读出线性表的长度用例10输入4线性表非空用例11输入’88',输入文件名称"dataList.datJ提示保存线性表成功用例12输入’3'再输入'12'成功清除线性表输入’12'后提示线性表为空用例13输入’99',并输入文件名称'dataList.dat'；再输入‘12'成功导入线性表，并成功列出线性表用例14输入‘2'成功销毁线性表进入系统后，会显示如图1-5所示的简易菜单界面。选择操作项目1,即可新建一个空的线性表。

欢迎使用顺序线性表菜单IntiaListDestroyListClearListListEinptyListLengthGetElem0.ExitLocateElemPriorElemNextElemListinsertListDeleteListTrabverse88.保存线性表99.加载线性表请选择你的操作[0~12/88,99]:1新建线性表成功！（按任意键继续……）图1-5用例1成功新建线性表实行插入元素操作时，需要在不同位置进行插入操作，以确保插入操作函数的有效性。系统测试时，应用了如表1-3所示的用例。表1-3插入数据用例表测试用例程序输入理论结果实验结果用例2.1输入'168',T成功向线性表插入第一个元素插入成功，目前线性表中的数据为：168（按任意键继续……）用例2.2输入'99',T成功在线性表的第一个位置插入元素插入成功.目前线性表中的数据为：99 168（按任意键继续……）用例2.3输入‘76','2'成功在线性表的第二个位置插入元素插入成功，目前线性表中的数据为：9976 168安任意健继续……）用例2.4输入'1009','4'成功在线性表的第四个位置插入元素插入成功，目前线性表中的数据为：99 76 168 1009（按任意键继续……）用例2.5输入‘8','5'成功在线性表的第五个位置插入元素插入成功,目前线性表中的数据为：9976 168 10098（按任意键继续……）用例2.6输入*20",'5，成功在线性表的第五个位置插入元素插入成功，目前线性表中的数据为：9976 168 1009208（按任意键继续……）

删除线性表、列出线性表个元素、读取线性表对应元素、确定相关元素的位置以及寻找相应元素前驱的操作结果如表1-4所示。表1-4用例3-用例7的实验结果表1请输入你想要删除数据的位置：6删除成功,目前线性表中的数据为：99 76 168 1009 20（按任意键继续……）11目前线性表内的数据为：99 76 168 1009 20（按任意键继续……）11请输入元素的序号：1第1个数的数值为：99（按任忌键继续 ）1请输入需要参与比较的数:168请输入比较的模式输入’1'：找到第一个相等数的位置输入'2':找到第一个比该数小的数的位置输入'3'：找到第一个比该数大的数的位置输入其他数无效！输入：1与168满足关系的数据元素序号为:3请输入你想要找的数据数值：168168的前驱是76（按任意键继续……）

寻找相应元素后继、求表长、判断表是否为空以及线性表的保存与读取的操作结果如表1-5所示。表1-5用例8-用例14实验结果请输入你想要找的数据数值：168168的后继是1009（按任意键继续……）请选择你的操作991:5该线性表的长度为：5请选择你的操作[0~12/8899]:4该线性表非空！请输入保存到的文件名称，以.dat结尾dataList.dat保存成功！（按任意键继续 ）请选择你的操作[0~12/88,99]:3清空线性表成功！（按任意键继续……）■目前线性表内的数据为：99 76 168 1009 20（按任意键继续……）I

最后，对线性表进行删除。选择操作2,提示删除线性表成功。如图1-6所欢迎使用顺序线性表菜单1234560IntiaListDestroyListClearListListEinptyListLengthGetElemExit789.1.0121XLocateEleinPriorElemNextElemListinsertListDeleteListTrabverse88.保存线性表99.加载线性表请选择你的操作[012/88,99]:2删除线性表成功！（按任意键继续……）图1-6用例14线性表删除成功再次进行其他操作时，提示线性表不存在，证明删除线性表的操作是成功的。如图1-7所示。请选择你的操作[0~12/88,99]:7线性表不存在！（按任意键继续……）1*图1-7线性表不存在证明线性表删除成功1.4实验小结经过本次实验，实验者对线性表的基本操作有了较好的掌握，以及对C++中*和&用法的相同点和不同点有了更深刻的理解。线性表的操作较为简单，但需要注意的是，在进行元素添加和删除的时候需要对表内元素进行较大规模的移动；在移动的时候必须要注意移动的初末范围。另外，由于线性表的大小是预先确定的，所以在添加元素时必须要考虑是否会溢出。如果空间不足，需要追加空间。在追加时需要用到realloc函数。'*'和'&'的用法也是值得关注的。'*'可以用来表示指针。指针从本质上讲是存放变量地址的一个变量。指针在逻辑上是独立的，所以指针可以被改变，包括指针所指向的对象以及指针所指对象的值。可用来表示一个变量的别名。它在逻辑上并不独立，所以引用在一开始就需要被初始化，而且引用在它的生命周期内无法改变自身的引用对象。指针和引用的相同点在于它们都有地址的概念。前者指向一块内存；它的内容是所指内存的地址。而后者则是某块内存的别名。指针和引用的不同点在于前者是一个实体，而后者只是一个别名。引用没有const,而指针有consto引用不能为空,而指针可以为空。“sizeof引用”得到的是引用对象的大小，而“sizeof指针”得到的是指针本身的大小。引用是类型安全的，而指针不是。2基于链式存储结构的线性表实现实验目的用单链表构建线性表，并设计包括8种针对单链表的运算方式在内的12种基本功能。通过对这些功能的实现，加深对线性表概念的理解，并充分理解链表逻辑结构和物理结构之间的关系。程序设计概要设计目标本实验旨在设计一个能对基于链式存储的线性表进行运算及进行文件操作的系统。本演示系统提供的操作包括：表的初始化、销毁、清空、判空，求表长、获取数据元素、查找数据元素、获得前驱、获得后继、创建链表、插入数据元素、删除数据元素以及表的遍历。与此同时，本系统支持数据的加载以及数据的保存。本系统在程序进行时可实现消息处理，其中包括数据的输入和输出以及程序的退出。有关常量、类型以及函数的定义常量包括函数的返回状态和数据元素类型。函数的返回状态包括正确、错误、可行、运行非法、不可实行和溢出；数据的元素类型包括函数的返回类型Status,以及所用到的参数类型ElemType。相应的定义内容与122基本一致。defineTRUE1defineFALSE0defineOK1defineERROR0defineINFEASTABLE-1defineOVERFLOW-2typedefintStatus;typedefintElemType;实验需要对链表进行初始化、销毁、清空、判空，求表长、获取数据元素、查找数据元素、获得前驱、获得后继、创建链表、插入数据元素、删除数据元素、遍历链表、数据加载以及数据保存等操作。为实现这些操作，需要对功能函数进行如下的定义。InitList(&L)操作结果：初始化链表。DestroyList(&L)初始条件：链表L的头结点已存在。操作结果：销毁链表L。ClearList(&L)初始条件：链表L的头结点已存在。操作结果：将L重置为空表。ListEmpty(L)初始条件：链表L的头结点已存在。操作结果：若L为空表，则返回TRUE,否则返回FALSE。ListLength(L)初始条件：链表L的头结点已存在。操作结果：返回L中数据元素的个数。GetElem(L,i,&e)初始条件：链表已存在，1WiWListLength(L)。操作结果：用e返回L中第i个数据元素的值。LocateElem(L,e,mode)初始条件：链表L的头结点已存在。操作结果：返回L中第1个与e满足关系mode关系的数据元素的位序,若这样的数据元素不存在，则返回值为0。PriorElem(L,cur_e>&pre_e)初始条件：链表L的头结点已存在。操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。NextElem(L,cur_e>&next_e)初始条件：链表L的头结点已存在。操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。ListInsert(&L,i,e)初始条件：链表L已存在且非空，1WiWListLength(L)+l。操作结果：在L的第i个位置之前插入新的数据元素e,L的头节点记录长度加loListDelete(&L,i,&e)初始条件：链表L已存在且非空，l〈i〈ListLength(L)。操作结果：删除L的第i个数据元素，用e返回其值，L的头节点记录长度减loListTraverse(L)初始条件：链表L的头结点已存在。操作结果：依次访问链表L中的每个数据项，并将将数据项依次打印出来。SaveList(L,char*filename);初始条件：链表L的头结点已存在。操作结果：将链表以二进制储存的方式保存到指定文件中。LoadList(&L,char*filename);初始条件：链表L的头结点已存在。操作结果：从指定文件中读取链表信息。功能函数的源代码详见附录B。2.2.3数据结构的设计以及函数的设计上述2.2.2中定义的14个函数均属于对链表的操作；链表由一个个独立的结点构成，每个结点包括存储地址、数据域以及指针域。在本实验中，链表包含头节点；头节点用于储存链表所包含的数据元素个数。该链表的逻辑结构如图2-1所示。图2-1线性链表的逻辑状态单链表是非随机存取的存储结构，因此对其中的元素操作必须从头指针出发寻找。相关的函数也需要根据这种性质来进行设计。除了InitList函数外，其余的13个函数在调用前均经过判断链表是否存在；只有在链表存在时，才会调用这13个函数。InitList(LinkList&L)初始化链表函数传入头节点指针的引用，释放其储存空间，并给它分配新的存储空间。指针的指针域指向NULL,数据域设置为0。头节点的数据域用于存储链表中元素的个数。DestroyList(LinkList&L)删除链表函数传入头节点指针的引用。如果链表内元素为0,则直接释放头节点储存空间。如果链表的元素不为0,则依次释放链表内的所有元素。其函数流程如图2-2所示。图2-2销毁链表函数流程ClearList(LinkList&L)清空链表清空链表的操作方式与销毁链表类似；不同的是，清空链表操作保留了头结点，转而从第二个结点开始对结点进行释放存储空间的处理。在清空完成后，把头结点的L->elem置为0,表示链表内的元素为空。ListEmpty(LinkListL)判断链表是否为空运用L->elem的数值进行判断。若数值为0,则表示链表内不存在元素，即链表为空。若数值不为0,则不为空。ListLength(LinkListL)求链表长度头结点中储存了链表的长度信息，直接返回L->elem的数值即可。GetElem(LinkListL,inti,ElemType&e)获取指定位置链表元素的数值首先判断序号i的范围是否合理；如果不合理，返回ERROR；如果合理，则继续运算。设置一个计数器k以及一个指向头结点的指针；顺指针向后查找，直到指向第i个元素为止。取第i个元素。程序流程图如2-3所示。returnERROR; returnOK：•(结束图2-3GetElem函数流程LocateElem(LinkListL,ElemTypee,intmode)确定元素的位置参数mode确定了匹配的模式，1表示等于，2表示大于，3表示小于。用switch转换相应数字，并用一个函数指针p指向对应的匹配函数。设置一个指向第一个元素的指针和一个计数器k,并顺指针向后查找，并对每个结点与e进行匹配判断。若匹配成功，则返回所计的数匕若未找到，则返回OoPriorElem(LinkListL,ElemTypecur_e,ElemType&pre_e)求指定元素的前驱首先对L->elem的值进行判定。若L->elem==0,则链表为空，返回FALSE。设置一个计数器k,并设置两个指针Lp,Lq„其中Lp初始指向L。Lp顺指针向后查找，Lq一直指向Lp的前驱。若Lp所指结点与cur_e相等，且Lp不为第一

个元素，则给pre_e赋上当前所指指针的值，并返回OK。若未能查找到，则返回FALSEo相关流程如图2-4所示。继与PriorElem函数类似。首先对L->elem的值进行判定。若L->elem==0,则链表为空，返回FALSE。设置一个指向L的指针Lp,Lp顺指针向后查找。将当前指针所指结点的数据与cur_e进行比较。若找到相等的元素，则判断Lp是否为最后一个结点。若不为最后一个结点，则给next_e附上该结点后继元素的值,并返回OK。若为最后一个结点，则返回ERROR。若未找到，则返回FALSE。ListInsert(LinkList&L,inti,ElemTypee)插入元素首先判断i是否符合条件；若i<l或大于表长加1,则返回ERROR。设置一个新节点newNode,并为它分配空间。与此同时，设置一个指向头指针的结点p和一个指向p的前驱的指针q，并设置一个计数器k。顺指针进行移动，直到p指向第i个元素。此时q指向p的前驱。将q的后继指向新元素，并将新元素指向p即可完成插入操作。最后，让头结点的元素记录数加上1,表示链表中增加了一个元素。ListDelete(LinkList&L,inti,ElemType&e)删除元素首先判断i是否符合条件；若i<l或大于表长，则返回ERROR。设置一个指向头指针的结点P，并设置一个计数器k。顺指针进行移动，直到p最终指向第i个元素的前驱。用q指向p的后继，并让p的后继指向q的后继。接着，释放q所指向结点的存储空间，这便完成了删除操作。最后，让头结点的元素记录数减去1,表示链表中删除了一个元素。ListTraverse(LinkListL)遍历元素首先对链表进行判定，看是否为空。若为空，提示链表为空。若不为空，设置一个指向头结点的指针P。让p顺指针逐个移动，并逐个打印每个结点中的元素，直到p为空。SaveList(LinkListL,char*filename)首先设置一个指向头结点的指针。打开文件，让p顺指针逐个移动，并向文件中逐一结点数据，直至p为空。最后，关闭文件。LoadList(LinkList*L,char*filename)首先新建链表L,并设置一个指向头结点的指针p。打开文件，给p的后继分配存储空间，并将文件中的一个结点数据写入p的后继。让p顺指针逐个移动，并将数据一一对应地写入p的后继。每写入一个数据，头结点中记录表长的变量就自增1。待文件读到末尾后，关闭文件，即载入链表数据成功。2.2.4复杂性分析在链表存储结构中，程序的时间主要耗费在寻找结点上。无论是获取元素、查找指定元素、添加元素、删除元素还是遍历元素，都需要对链表进行顺指针查找，因此GetElem(L,i,&e),LocateElem(L,e.mode)>PriorElem(L,cur_e,&pre_e)>NextElem(L.cur_e,&next_e)、ListInsert(&L,i,e)>ListDelete(&L,i,&e)、ListTraverse(L)函数的时间复杂度都为O(n)。特别的，在进行插入和删除时，都需要找到第i-1个结点，因此它们的时间复杂度会为O(n)。在本次实验中，链表的长度信息被保存到了头节点中。因此，求表长的函数无需遍历整个链表。这使得ListLength(L)函数的时间复杂度简化为了0(1)。主要函数的时间复杂度如表2-1所示。表2-1链表操作函数时间复杂度函数时间复杂度函数时间复杂度InitialList0(1)LocatElem0(n)DestroyList0(1)PriorElemO(n)ClearList0(1)NextElem0(n)ListEmpy0(1)Listinsert0(n)ListLenth0(1)ListDelete0(n)GetElemO(n)ListTrabverseO(n)SaveListO(n)LoadListO(n)系统测试与结果系统的测试主要检查①系统是否能够不报错地正常运行；②链表的各项操作是否正确，包括插入元素、删除元素、确定元素位置等等；③链表是否具有容错性；比如，在表未初始化时，进行插入元素操作能够提示“线性表不存在”，④线性表的保存与读取是否正常。具体的测试用例方案如图表2-2所示。

表2-2测试用例总体规划表测试用例程序输入理论结果用例1输入'1'成功新建一个线性表，并能够执行其他操作用例2输入’10',并按表1-2输入数据成功向线性表中插入了一系列的参数，共6个元素用例3输入’11',并输入‘6'成功删除线性表中的第6个元素用例4输入'12'列出线性表中的所有元素用例5输入'6',并输入’1'读取线性表中的第二个元素用例6输入’7',输入’1',再输入4168,读出‘168'元素所在序号用例7输入’8',并输入‘168'读出‘168'元素的前一个元素用例8输入'9',并输入‘168'读出‘168'元素的后一个元素用例9输入'5'读出线性表的长度用例10输入4线性表非空用例11输入’88',输入文件名称'dataLisl.dal'提示保存线性表成功用例12输入'3'再输入'12'成功清除线性表输入’12'后提示线性表为空用例13输入’99',并输入文件名称4dataList.dat*；再输入'12'成功导入线性表，并成功列出线性表用例14输入’2'成功销毁线性表进入系统后，会显示如图2-5所示的简易菜单界面。选择操作项目1,即可新建

一个空的链表欢迎使用顺序线性表菜单1.IntiaList7.LocateElem2.DestroyList8.PriorElem3.ClearList9.NextElem4.ListEmpty10.Listinsert5.ListLength11.ListDelete6.GetElem12.ListTrabverse0.Exit88.保存链表99.加载链表请选择你的操作[0“12/88,99]:图2-5简易菜单界面实行插入元素操作时，需要在不同位置进行插入操作，以确保插入操作函数的有效性。系统测试时，应用了如表2-3所示的用例。表2-3插入数据用例表测试用例程序输入理论结果实验结果用例2.1输入'168',T成功向链表插入第一个元素插入成功，目前链表中的数据为：168（按任意键继续•…”）用例2.2输入'99',T成功在链表的第一个位置插入元素插入成功，目前楂表中的数据为：99 168按任意键继续……）用例2.3输入‘76','2'成功在链表的第二个位置插入元素插入成功，目前链表中的数据为：99 76 168（按任意键继续……）用例2.4输入'1009','4'成功在链表的第四个位置插入元素插入成功，目前楂表中的数据为：9976 168 1009（按任意键继续……）用例2.5输入‘8','5'成功在链表的第五个位置插入元素插入成功，目前链表中的数据为：9976 168 10098（按任意键继续……）用例2.6输入*20','5，成功在链表的第五个位置插入元素插入成功，目前链表中的数据为：9976 168 1009208（按任意键继续……）

删除线性表、列出线性表个元素、读取线性表对应元素、确定相关元素的位置以及寻找相应元素前驱的操作结果如表2-4所示表2-4用例3-用例7的实验结果表用例实验结果用例3删除成功，目前链表中的数据为：99 76 168 1009 20（按任意键继续……）用例4链表中的儿素为：99 76 168 1009 20（按任意键继续……）用例5请输入元素的序号：1第1个数的数值为：99（按任忌键继续 ）用例6请输入需要参与比较的数:168请输入比较的模式输入’1'：找到第一个相等数的位置输入'2':找到第一个比该数小的数的位置输入'3'：找到第一个比该数大的数的位置输入其他数无效！输入：1与168满足关系的数据元素序号为:3用例7请输入你想要找的数据数值：168168的前驱是76（按任意键继续……）寻找相应元素后继、求表长、判断表是否为空以及线性表的保存与读取的操表2-5用例8-用例14实验结果1请输入你想要找的数据数值：168168的后继是1009（按任意键继续……）1■该链表的长度为:5（按任意键继续……）■■该链表非空！（按任意键继续……）■1请输入保存到的文件名称，以.dat结尾linkList.dat保存成功！（按任意键继续……）1■［青空链表成功！（按任意键继续……）■1请输入要加载的文件名称，以.dat结尾linkList.dat文件读取成功！1链表中的兀素为：99 76 168 1009 20（按任意键继续……）最后，对线性表进行删除。选择操作2,提示删除线性表成功。如图2-6所欢迎使用顺序线性表菜单123451234560IntiaListDestroyListClearListListEinptyListLengthGetElemExit789.1.0121XLocateEleinPriorElemNextElemListinsertListDeleteListTrabverse88.保存线性表99.加载线性表请选择你的操作[012/88,99]:2删除线性表成功！（按任意键继续……）图2-6用例14线性表删除成功再次进行其他操作时，提示线性表不存在，证明删除线性表的操作是成功的。如图2-7所示。请选择你的操作12/88,99]:7线性表不存在！（按任意键继续……）1 图2-7线性表不存在证明线性表删除成功实验小结经过本次实验，实验者对链表的操作有了更好的掌握，特别是在一些细节上,比如头结点的设置、存储空间的分配以及野指针的避免。链表最好设置一个头结点，这样可以更简便地进行插入和删除操作。另外,可以在头结点中存入一些信息，比如链表的长度信息。这样一来可以大大地简化某些函数的算法复杂度，比如求表长。原本需要对全表进行遍历，而若将表长信息存入头结点，那么直接读取长度信息即可。另外，在给结点分配存储空间时，可以适当地增加一些空间，以免某些编译器会产生的溢出的现象。在对链表的结点进行操作时（比如删除），务必注意要对特定结点进行重指向，比如让其指向NULL,否则会产生野指针，从而造成程序运行错误。3基于二叉链表的二叉树实现实验目的通过构造一个二叉链表，加深对二叉树概念和基本运算的理解。与此同时，熟练掌握二叉树逻辑结构和物理结构之间的关系。程序设计概要设计目标本实验旨在设计一个基于二叉链表的二叉树存储系统。本演示系统不仅提供对二叉树的整体操作运算，包括构造空二叉树、销毁二叉树、创建二叉树、清空二叉树、判定空二叉树、求二叉树的深度以及前中后序遍历和按层遍历，而且支持对二叉树的结点进行运算，包括获得根结点、获得结点、结点赋值、获得双亲结点、获得左孩子结点、获得右孩子结点、获得左兄弟结点、获得右兄弟结点、插入子树和删除子树。此外，本系统可对多棵树进行管理。在程序进行时，可实现消息处理，其中包括数据的输入和输出以及程序的退出。有关常量、类型、结构体以及函数的定义常量包括函数的返回状态和数据元素类型。函数的返回状态包括正确、错误、可行、运行非法、不可实行和溢出；数据的元素类型包括函数的返回类型Status,以及所用到的参数类型TElemType。相应的定义内容除了TElemType为char别名外，其余的与2.2.2基本一致。defineTRUE1defineFALSE0defineOK1defineERROR0defineINFEASTABLE-1defineOVERFLOW-2typedefintStatus;typedefcharTElemType;本系统采用了线性表来管理多个树。因此，需要定义线性表的初始大小以及线性表满后所需要的增加量。分别用LIST_INIT_SIZE和LISTINCREMENT表/J\OdefineLISTJNIT_SIZE100defineLISTINCREMENT10实验定义了多个结构体，其中包括用于存取二叉树的顺序表结构、存放二叉树的头结点的结构、用于存放每个树结点的结构以及树结点存放的数据类型的结构。用于存放二叉树的顺序表除了包含树的内容外，还可以存储顺序表长度和顺序表大小的信息。用于存放二叉树的头结点的结构除了指向树根外，还用于保存树名的信息。typedefstruct{structTree*elem;intlength;intlistsize;JSqList;typedefstructTree{charname[20];structBiTNode*HeadNode;}Tree;二叉树的每个结点的结构，包含数据类型以及左右子树的指针。存放树结点数据类型的结构包含树结点名称以及树结点的值。typedefstructBiTNode{TreeElemTypedata;structBiTNode*lchild,*rchild;JBiTNode,*TNode,*BiTree;typedefstructTreeElemType(chartag;charnumber;charislnit;}TreeElemType;系统能够对二叉树进行构造(包括构造空树和构造完整的树)、销毁、清空、插入子树、删除子树等基本操作。此外，对已经构造的树，还能提供判空、求深度、求根、给特定结点赋值、求特定结点的值、求特定结点的父母结点、求特定结点的左右子女结点、求特定结点的左右兄弟结点。并且，系统支持前序、中序、后序、层序等遍历操作。InitBiTree(&T)操作结果：构造空二叉树T。DestroyBiTree(&T)初始条件：二叉树T已存在。操作结果：销毁二叉树T。CreateBiTree(&T,definition)初始条件：definition给出二叉树T的定义。操作结果：按definition构造二叉树T。ClearBiTree(&T)初始条件：二叉树T存在。操作结果：将二叉树T清空。BiTreeEmpty(T)初始条件：二叉树T存在。操作结果：若T为空二叉树，则返回TRUE,否则返回FALSE.BiTreeDepth(T)初始条件：二叉树T存在。操作结果：返回T的深度。Root(T)初始条件：二叉树T已存在。操作结果：返回T的根。Value(T,e)初始条件：二叉树T已存在，e是T中的某个结点。操作结果：返回e的值。Assign(T.&e,value)初始条件：二叉树T已存在，e是T中的某个结点。操作结果：结点e赋值为value。Parent(T,e)初始条件：二叉树T已存在，e是T中的某个结点。操作结果：若e是T的非根结点，则返回它的双亲结点指针，否则返回NULLoLeftChild(T,e)初始条件：二叉树T存在，e是T中某个节点。操作结果：返回e的左孩子结点指针。若e无左孩子，则返回NULL。RightChild(T,e)初始条件：二叉树T已存在，e是T中某个结点。操作结果：返回e的右孩子结点指针。若e无右孩子，则返回NULL。LeftSibling(T,e)初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的左兄弟结点指针。若e是T的左孩子或者无左兄弟，则返回NULLoRightSibling(T,e)初始条件：二叉树T已存在，e是T中某个结点。操作结果：返回e的右兄弟结点指针。若e是T的右孩子或者无有兄弟，则返回NULLoInsertChild(T,p,LR,c)初始条件：二叉树T存在，p指向T中的某个结点，LR为0或1,,非空二叉树c与T不相交且右子树为空。操作结果：根据LR为0或者1,插入c为T中p所指结点的左或右子树,p所指结点的原有左子树或右子树则为c的右子树。DeleteChild(T,p,LR)初始条件：二叉树T存在，p指向T中的某个结点，LR为。或1。操作结果：根据LR为0或者1,删除c为T中p所指结点的左或右子树。PreOrderTraverse(T,Visit())初始条件：二叉树T存在，Visit是对结点操作的应用函数。操作结果：先序遍历3对每个结点调用函数Visit-•次且一次，一旦调用失败，则操作失败。InOrderTraverse(T,Visit())初始条件：二叉树T存在，Visit是对结点操作的应用函数。操作结果：中序遍历3对每个结点调用函数Visit一次且一次，一旦调用失败，则操作失败。PostOrderTraverse(T,Visit())初始条件：二叉树T存在，Visit是对结点操作的应用函数。操作结果：后序遍历3对每个结点调用函数Visit一次且一次，一旦调用失败，则操作失败。LevelOrderTraverse(T,Visit())初始条件：二叉树T存在，Visit是对结点操作的应用函数。操作结果：层序遍历t,对每个结点调用函数Visit一次且一次，一旦调用失败，则操作失败。SaveBiTree(T,filename)初始条件：二叉树T存在，filename是所输入的文件名。操作结果：先序遍历二叉树，将结点和空以先序存入文件。ReadBiTree(filename)操作结果：读取文件中储存的二叉树信息，并构建新二叉树。3.2.3数据结构的设计以及函数的设计(1)数据结构的设计3.2.2节中定义的22个函数均属于对二叉树的操作。二叉树由一个头结点和若干个树枝结点构成。头结点不仅用于指向树根，还用于保存树名。该二叉树的逻辑结构如图3.1所示。

图3.1二叉树的存储结构(2)函数的设计函数的设计可以分为四大类：①构造类函数：包括创建、销毁、清空、插入子树和删除子树。②遍历函数：进行前序、中序、后序、层序等遍历操作。②求值函数：判空、求深度、求根、给特定结点赋值、求特定结点的值、求特定结点的父母结点、求特定结点的左右子女结点、求特定结点的左右兄弟结点。④系统功能函数：包括保存、读取二叉树以及更换当前操作的二叉树。除构造和销毁函数外，其余的函数在调用前均会判断二叉树是否已被构造。a)构造类函数构造类函数即是对二叉树进行的创建、销毁、清空、插入子树和删除子树的功能。在本系统中，创建二叉树运用的是先序序列，用‘#'表示结点的不存在。

创建二叉树函数分为两个部分：①对线性表进行的操作，包括判断线性表的存储空间(若不足，则分配新的空间)以及给新的树命名并分配头结点。②将输入的字符串转化为树。针对②的主要算法如图3.2所示。图3.2(a)将输入的字符串转化成树第一部分图3.2(b)将输入的字符串转化成树第二部分图3.2(c)将输入的字符串转化成树第三部分图3.2(d)将输入的字符串转化成树第四部分至于销毁树，则让二叉树中的每个元素依次进入数组，类似于队列的处理方式，先入先出，先入数组的结点先被释放掉，后入数组的结点后被释放，直到整个二叉树的元素都被释放完。特别的，如果T的左子树是空的，那么直接释放掉T的存储空间即可。清空树与销毁树类似，只不过在销毁的最后需要保留头结点。类似的，删除子树相当于是对树的某一结点的左子树或右子树进行的销毁树操作。插入子树与创建树的方式类似，同样也需要创建一个新的子树，只不过在创建之后，需要将原树对应结点的子树指针指向子树的根结点；与此同时，将子树根结点的右子树指向原来母树结点所指的树枝结点一一因为整个原因，插入的子树的右子树必须为空。b)遍历函数对二叉树的遍历包括前序遍历、中序遍历、后序遍历以及层序遍历。其中前序遍历的步骤为：①访问根结点。②按前序遍历根结点的左子树。③按前序遍历根结点的右子树。由此，可以用递归的方式对二叉树进行前序遍历。StatusPreOrderTraverse(BiTreeT){if(T!=NULL){if(T->data.tag)printf("%c",T->data.tag);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);returnOK;}returnFALSE;)中序遍历的步骤为：①按中序遍历根结点的左子树。②访问根结点。③按中序遍历根结点的右子树。StatusInOrderTraverse(BiTreeT){if(T!=NULL){InOrderTraverse(T->lchild);printf(n%c",T->data.tag);InOrderTraverse(T->rchild);returnOK;}returnFALSE;)后序遍历的步骤为：①按后序遍历根结点的左子树。②按后序遍历根结点的右子树。③访问根结点。StatusPostOrderTraverse(BiTreeT){if(T!=NULL){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);

printf(n%c",T->data.tag);returnOK;returnFALSE;)上述三种算法都采取了递归的方式，每个结点访问一次，因此，时间复杂度为O(N)。采用递归的方法时，无需辅助的空间就能够实现对二叉树的遍历。因此，算法的空间复杂度为0(1).层序遍历即让二叉树表中的各个元素按从上到下从左到右的顺序依次收入数组，类似于队列的操作方式，先入的先读取，直到元素被读完。其算法如图3.3所示。图3.3层序遍历算法流程图c）求值函数各种求值函数主要还是用到二叉树的遍历。在本系统中，主要运用的遍历方式为先序遍历，用栈来实现先序。核心算法如图3.4所示。图3.4求值函数核心算法流程图给特定结点赋值、求特定结点的值、求特定结点的父母结点、求特定结点的左右子女结点、求特定结点的左右兄弟结点都主要应用上述的核心算法。其中的差别在于需要被判定的结点的位置与返回的值。求父母结点需要由p->rchild->data.tag==e和p->lchild->data.tag==e共同判定，求特定结点的左右兄弟需要分别由p->rchild->data.tag==e,p->lchild->data.tag==e进行判定。给特定结点赋值、求特定结点的值以及求特定结点的左右子女结点都用p->data.tag==e进行判定。判空和求根函数的算法都极其简单。由于头结点中记录了二叉树的结点个数，若记录个数为零，则树为空；反之，则树不空。求根函数直接返回头结点的左子树即可。求深度函数运用了递归的算法，首先判定传入的树是否为空，若为空则返回Oo再递归调用函数，分别求左子树和右子树的深度i和j,最后，返回i、j中较大的数。其算法如下。intBiTreeDepth(BiTreeT)(•nti,j;if(T==NULL)return0;i=BiTreeDepth(T->lchild);j=BiTreeDepth(T->rchild);if(i>j)return(i+1);return(j+1);)d)系统功能函数系统功能函数包括二叉树的保存、二叉树的读取以及改变当前操作的二叉树。二叉树的保存，即将当前操作树以先序序列存入文件(包含结点以及空)。二叉树的读取，即将文件中的内容按字符串的形式读出，并重新构造二叉树。改变当前操作的二叉树，即要求用户输入其希望寻找的二叉树名称，若找到，则将线性表的下标改为该二叉树所对应的位置。若未找到，则提示错误，并保持现二叉树不变。在上述运算中，初始化二叉树、判空函数、求根函数的算法均只需常数运算;因此，他们的时间复杂度均为0(1)。而求深度、先序遍历、中序遍历、后序遍历都用到了递归的算法，它们都需要对整棵树的每个结点进行操作一次，因此时间复杂度为O(n),而它们每次递归都要储存返回信息，因此空间复杂度为O(n)。其余函数在最坏情况下都需要遍历整棵树,因此,它们的时间复杂度也都为O(n)。复杂度如表3.1和表3.2所示。表3.1(a)二叉树功能函数时间复杂度函数时间复杂度函数时间复杂度InitBiTree0(1)RightChild0(n)DestroyBiTreeO(n)LeftSiblingO(n)CreateBiTree0(n)RightSibling0(n)ClearBiTree0(1)InsertChild0(n)BiTreeEmpty0(1)DeleteChild0(n)BiTreeDepth0(n)PreOrderTraverse0(n)Root0(1)InOrderTraverseO(n)ValueO(n)PostOrderTraverseO(n)Assign0(n)LevelTraverse0(n)Parent0(n)SaveBiTree0(n)LeftChild0(n)ReadBiTree0(n)表3.1(b)二叉树功能函数空间复杂度函数空间复杂度BiTreeDepth0(n)PreOrderTraverseO(n)InOrderTraverseO(n)PostOrderTraverse0(n)3.3系统测试与结果系统的测试主要检查①系统是否能够不报错地正常运行；②二叉树的各项操作是否正确，包括创建二叉树、销毁二叉树、确定某树枝位置、遍历二叉树等等;③二叉树是否具有容错性；比如，在二叉树未初始化时，进行插入元素操作能够提示“二叉树不存在”，④二叉树的保存与读取是否正常。（1）对初始状态的容错性进行测试测试系统的容错性，看在二叉树未创建时，调用功能函数的提示是否正常。理论值应当提示“当前二叉树不存在，请先创建二叉树”。相关用例与结果如表3.2所示。表3.2初始状态容错性测试测试用例程序输入实验结果用例1输入4请选择你的操作12/70,88,99]:4当前无二叉树存在，请先创建二叉树！（按任意键返回……）用例2输入T请选择你的操作[0〜12/70,88,99]:7当前无二叉树存在，请先创建二叉树！（按任意键返回……）用例3输入'12'请选择你的操作[0~12/70,88,99]:12当前无二叉树存在，请先创建二叉树！（按任意键返回……）用例4输入’17，请选择你的操作[0~12/70,88,99]:17当前无二叉树存在，请先创建二叉树！（按任意键返回……）用例5输入'20'请选择你的操作12/70,88,99]:20当前无二叉树诙，请先创建二叉树！（按任意键返回……）用例6输入,88,请选择你的操作12/70,88,99]:88当前无二叉树存在，请先创建二叉树！（按任意键返回……）（2）对二叉树的创建和二叉树的遍历的测试

创建一个二叉树，并对其进行遍历，看遍历结果是否符合理论结果。所创建的二叉树，如图3.5所示。图3.5创建的二叉树按照上图创建二叉树，则输入ABC##D#E##F##,创建成功，结果如图3.6所示。请选择你的操作12/70,88,99]:3请输入你希望构造的二叉树名称，lemonTree请按照先序顺序，依次输入各个结点的元素(char), 表示该结点为空|成功构造二叉树！(按任意键继续……)图3.6成功构造二叉树

相关的遍历测试如表3.3所示。表3.3二叉树的遍历用例与结果测试用例程序输入理论结果实验结果用例1输入‘17'打印序列ABCDEF请选择你的操作[0-12/70,88,99]:17所有元素ABCDEF 结束 用例2输入’18，打印序列CBDEAF请选择你的操作[0—2/70,88,99]:18 所有待 CBDEAF 结束 用例3输入'19'打印序列CEDBFA请选择你的操作12/70,88,99]:19 所有元素 CEDBFA外尔用例4输入‘20'打印序列ABFCDE请选择你的操作[。〜12/70,88,99]:20 树中所有元素 ABFCDE 结束 (3)对二叉树查询功能的测试所涉及的功能包括，判空、求根结点、求深度、求特定结点的父母结点、求特定结点的左右子女结点、求特定结点的左右兄弟结点。相关用例与结果如表3.4和表3,5所示。

表3.4二叉树判空/求深度/求根节点的用例与结果测试用例程序输入理论结果实验结果用例1输入5提示二叉树非空请选择你的操作12/70,88,99］：5当前二叉树不是空的。（按任意键继续……）输入‘6'提示深度为4用例2请选择你的操作12/70,88,99］：6当前操作的二叉树的深度为：［4］（按任意键继续……）用例3输入‘7'提示根节点为A请选择你的操作［0~12/70,88,99］:7当前二叉树根结点标记为：A（按任意键继续……）

表3.5求各种结点的用例与结果测试用例程序输入理论结果实验结果用例1输入’10'再输入'B'返回A请选择你的操作12/70,88,99]:10输入你希望双亲结点的结点的标记，（字符）B所输入结点的双亲结点的标记是：A用例2输入'11'再输入'B'返回'C'-请选择你的操作[0~12/70,88,99]:11输入你希望找到其左孩子的结点的标记，（字符）B所输入结点的左孩子的标记为：C用例3输入T2，再输入'D'返回'E'请选择你的操作12/70,88,99]:12输入你希望找到其右孩子的结点的标记，（字符）D所输入结点的右孩子的标记为，E用例4输入’13'再输入B提示不存在请选择你的操作[0~12/70,88,99]:13输入你希望找到其左兄弟的结点的标记，（字符）B此结点没有左兄弟，或该二叉树不含所输入结点！用例5输入’13'再输入’F返回'B'—请选择你的操作[0~12/70,88,99]:13输入你希望找到其左兄弟的结点的标记，（字符）F该结点的左兄弟的标记为，B用例6输入’14'再输入‘C'返回'D'请选择你的操作[0~12/70,88,99]:14请输入你希望找到其右兄弟的结点的标记，（字符）C所输入结点的右兄弟的值为，D

(4)对插子子树功能和删除子树功能的测试插入子树功能和删除子树功能是二叉树功能函数中的两个重要组成部分。在本次测试中，试图在B的右结点下插入如下子树。图3.7插入的子树得到新的树如图3.8所示。图3.8得到的新树按上图进行插入子树，提示插入成功。如图3.9所示。请输入你希望插入子树的结点(字符)B插入到该结点的左子树，请输入0,右子树，请输入1。1请按照先序输入插入树的各个结点的数据(char),表示此节点不存在!注意：插入树不能为空且它的右子树必须为空成功插入子树！图3.9成功插入子树对新树进行遍历，测试用例如表3.6。表3.6对新树进行遍历的用例与结果测试用例程序输入理论结果实验结果用例1输入'17'打印序列ABCGHIJDEF请选择你的操作[0~12/70,88,99]:17 所有斌 ABCGHIJDEF-结束-用例2输入‘⑻打印序列CBIHJGDEAF请选择你的操作12/70,88,99]:18 所有元素 3BIHJGDEAF 结束 用例3输入‘19'打印序列CIJHEDGBFA请选择你的操作[0~12/70,88,99]:19 所有元素 CIJHEDGBFA 结束 用例4输入‘20'打印序列ABFCGHDIJE请选择你的操作[0~12/70,88,99]:20- - 树巾所有元素 ABFCGHDIJE 结束 删除结点G,剩余的树的前序遍历应该是ABCF,中序遍历应该是CBAF。如图请选择你的操作[0〜12/70,88,99]:16请输入你希望删除子节点的字符标记(char)B删除该结点的左结点，请输入0;删除该结点的右结点，请输入11成功删除结点！3.10(a)成功删除子节点请选择你的操作12/70,88,99]:17 所有元素 ABCF 结束 (按任意键继续 )3.10(b)删除子节点后进行的先序遍历请选择你的操作[0〜12/70,88,99]:18 所有元素 AF 结束 3.10(c)删除子节点后进行的中序遍历（5）对树结点赋值的测试对树节点进行赋值的用例如表3.7所示。表3.7对树结点进行赋值的用例与结果测试用例程序输入理论结果实验结果用例1输入'9'输入'AI再输入'8，成功为“A”赋上'8'值请选择你的操作[0~12/70,88,99]:9输入你希望赋值结点（char）A输入你希望附的值（char）：8给结点赋值成功！用例2输入’8'再输入，A，成功打印出A的值‘8'请选择你的操作[0〜12/70,88,99]:8输入你想查找的结点标记：（char）A在当前二叉树中，此二叉树结点A的值为:8（6）对多树切换和树的保存和读取进行测试对当前树进行保存，保存成功如图3.11所示请选择你的操作[0〜12/70,88,99]:88请输入你希望存放的文件的名称（以.dat结尾）lemon,dat保存二叉树leinonTree成功！（按任意键继续……）图3.11保存二叉树成功创建新树pearTree,创建成功如图3.12所示。

请选择你的操作[0~12/70,88,99]:3请输入你希望构造的二叉树名称：pearTree请按照先序顺序，依次输入各个结点的元素（char）, 表示该结点为空,UW##X##Y##成功构造二叉树！（按任意键继续……）图3.12pearTree创建成功对新树进行先序遍历，如图3.13所示。请选择你的操作［0〜12/70,88,99］:17 所有元素 JVVXY 结束 （按任意键继续……）图3.13对新树进行的先序遍历请选择你的操作［0T2/70,88,99］：请选择你的操作［0T2/70,88,99］：70输入你希望更换的二叉树的名称：

leinonTree成功将当前操作树转为：lemonTree（按任意键继续……）请选择你的操作［0-12/70,88,99］ 所有元素 ABCF 结束 图3.14多树管理•切换树成功对当前的lemonTree进行清空处理，并发现清空成功，如图3.15所示。请选择你的操作[0~12/70,88,请选择你的操作[0~12/70,88,99]:4成功清空二叉树！（按任意键继续……）请选择你的操作[0〜12/70,88,99]:5

当前二叉树是空二叉树。（按任意键继续……）图3.15清空当前二叉树成功重新载入先前保存的lemonTree结点信息，加载成功。如图3.16所示请选择你的操作[0~12/70,88,99]:99

请输入载人的文件的名称（以.dat结尾）lemon,dat请给载人的二叉树取一个名称：newLeinon载入二叉树newLemon成功！（按任意键继续……）请选择你的操作[0~12/70,88,99]:17 所有元素 ABCF 结束 （按任意键继续……）图3.16加载二叉树成功3.4实验小结在本次实验中，对二叉树的基本操作有了一个整体的理解。其中，二叉树的构造和二叉树的遍历是两个的最为重要的内容。在本次实验中，二叉树的构造采用了先序构造的方式。构造时，路线沿着先序的方向，用‘#'号表示所指子树为NULLo若当前读取的字符不为空，则按先序依次构造树。在构造时，若上一次读取的字符不为空，则在左子树下插入本次读取的结点，否则，在右子树下插入。若当前读取的字符为空，则另当前所在结点指向NULL（上一字符不为空，左子树为NULL；反之，右子树为NULL）„除层序遍历外，二叉树的其他3种遍历都用到了递归的方式。事实上，三种遍历方法的算法基本相同，都是依次对左子树结点和右子树结点进行递归调用，只不过访问根结点的时机不同。先序遍历在两次调用递归前访问根节点，中序在中间，后序在最后。层序遍历主要用到了队列的思想，先入先出，从而使得每层能有序地输出。4基于邻接表的图实现实验目的通过实验加深对图的概念以及图的基本运算的理解；与此同时，熟练掌握图的逻辑结构与物理结构的关系，并以邻接表作为物理结构实现图的基本运算。程序设计概要设计目标本实验旨在设计一个基于邻接表的有向图和有向网的管理系统。本演示系统提供的操作包括：图的新建、图的销毁、顶点位置信息的确定、找到某顶点的第一个邻接顶点、找到某顶点一邻接顶点的下一顶点、对顶点进行赋值、获取顶点的值、新增一个顶点、删除一个顶点、插入一条邻边、删除一条邻边、对图进行深度优先遍历、对图进行广度优先遍历。本系统在程序进行时可实现消息处理，其中包括数据的输入和输出以及程序的退出。有关常量、类型、结构体以及函数的定义常量包括函数的返回状态和数据元素类型。函数的返回状态包括正确、错误、可行、运行非法、不可实行和溢出；数据的元素类型包括函数的返回类型Status,以及所用到的弧的信息参数类型InfoType。其中MAX_CHAR用于限定顶点名称的最大字符数，MAX_VERTEX_NUM用于限定图中的顶点数目。GraphKind用于定义图的类型。defineTRUE1defineFALSE0defineOK1defineERROR0#defineINFEASTABLE-1#defineOVERFLOW-2

typedefintStatus;typedefintInfoType;typedefenum{DG,DNJGraphKind#defineMAX_CHAR3#defineMAX_VERTEX_NUM20实验定义了多个结构体，其中包括用于储存图的结构ALGmph,用于储存顶点的结构VNode以及用于储存弧的结构ArcNodeotypedefstructVertexType{charkey[MAX_CHAR];intvalue;intislnit;}；typedefstructArcNode{intadjvex;structArcNode*nextarc;typedefstructArcNode{intadjvex;structArcNode*nextarc;InfoType*infb;);〃该弧所指向的顶点的位置〃指向下一条弧的指针〃该弧相关信息的指针typedefstructVNode{VertexTypedata;typedefstructVNode{VertexTypedata;ArcNode*firstare;〃顶点信息〃指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;//图的当前顶点数和弧数//图的当前顶点数和弧数intkind; //图的种类标志}ALGraph;系统能够新建一个图、销毁一个图；确定一个顶点的位置、确定一个顶点的首个邻接顶点、确定一个顶点中某个邻接顶点的下一个邻接顶点；给一个顶点赋值，获得一个顶点的值；插入一个顶点，删除一个顶点；插入一条弧，删除一条弧；对图进行深度优先遍历；对图进行广度优先遍历。CreateCraph(&G,V,VR)初始条件：V是图的顶点集，VR是图的关系集。操作结果：按V和VR的定义构造图G。DestroyCraph(&G)初始条件：图G存在。操作结果：销毁图G。LocateVex(Gu)初始条件：图G存在，u和G中的顶点具有相同特征。操作结果：若u在图G中存在，返回顶点u的位置信息，否则返回其它信息。GetVex(G,v)初始条件：图G存在，v是G中的某个顶点操作结果：返回v的值PutVex(G,v,value)初始条件：初始条件是图G存在，v是G中的某个顶点操作结果：对v赋值valueFirstAdjVex(&G,v)初始条件：图G存在，v是G的一个顶点。操作结果：返回v的第一个邻接顶点，如果v没有邻接顶点，返回空。NextAdjVex(&G,v,w)初始条件：图G存在，v是G的一个顶点,w是v的邻接顶点。操作结果：返回V的(相对于W)下一个邻接顶点，如果W是最后一个邻接顶点，返回空。InsertVex(&G,v)初始条件：图G存在，v和G中的顶点具有相同特征。操作结果：在图G中增加新顶点V。DeleteVex(&Gv)初始条件：图G存在，v是G的一个顶点。操作结果：在图G中删除顶点v和与v相关的弧。InsertArc(&G,v,w)初始条件：图G存在，v、w是G的顶点。操作结果:在图G中增加弧＜v,w＞,如果图G是无向图，还需要增加＜w,v＞。DeleteArc(&G,v,w)初始条件：图G存在，v、w是G的顶点。操作结果：在图G中删除弧＜v,w＞,如果图G是无向图，还需要删除＜w,v＞。DFSTraverse(G,visit())初始条件：图G存在。操作结果：对图G进行深度优先搜索遍历，依次对图中的每一个顶点使用函数visit访问一次，且仅访问一次。BFSTraverse(G,visi