《数据结构》课程实验报告

1、课 程 实 验 报 告课程名称： 数据结构 专业班级： 信息安全1302 学 号： 姓 名： 指导教师： 报告日期： 2015年5月6日 计算机科学与技术学院目 录1 课程实验概述12 实验一 基于顺序结构的线性表实现22.1 问题描述22.2 系统设计22.3 系统实现22.4 效率分析83 实验二 基于链式结构的线性表实现103.1问题描述103.2系统设计103.3系统实现103.4效率分析154 实验三 基于二叉链表的二叉树实现164.1 问题描述164.2 系统设计164.3 系统实现184.4 效率分析345 实验总结与评价36附注，相关源代码：386.1顺序结构线性表的实现：38

2、6.2链式结构线性表的实现：386.3二叉树的实现：381 课程实验概述实验概述数据结构是一门理论性和实践性都很强的科目。说其理论性强，是因为在课上会讨论顺序表、树和图等等复杂的数据结构以及有关它们的基本操作方法，而这些东西都是十分抽象的。而说其实践性强，则是因为这些在课堂上所讨论的理论知识，最终要被我们运用到各种应用程序中，去实现各种不同的功能。而为了能熟练地使用这些知识，就需要有很好的使用经验，而这使用经验，就要求我们能自己亲手实现一遍这些数据结构，来亲身体验它们工作的方式。并且在上机实践的过程中，发现自己容易犯的错误，找出问题所在，避免以后使用这些知识的时候再次犯同样的错误。这样的动手能

3、力和经验都是十分重要的。因此，说这门课实践性特别强。而为了满足课程对实践性的要求，我们就要进行这两次上机实验，来实现顺序表和二叉树这两种数据结构以及与其相关的各种操作。相信我们一定会在上机实验的过程中加深对这两种数据结构的理解，收获到在课堂上无法获得的宝贵体验，提高我们的程序编写能力和程序差错能力，同时也体会到数据结构这门课程的魅力。实验内容1. 顺序表综合实验2. 链表综合实验3. 二叉树综合实验2 实验一 基于顺序结构的线性表实现2.1 问题描述基于顺序存储结构，实现线性表 ADT,具有12种基本运算。 要求： 提供一个实现功能的演示系统 具体物理结构和数据元素类型自行选定 线性表数据可以

4、使用磁盘文件永久保存2.2 系统设计在本系统中，先创建一个结构体来作为线性表的表头，在表头中含有线性表的长度，线性表的大小以及指向线性表数组的头指针等信息。本系统所实现的对线性表的所有操作都通过这个表头来实现。2.2.1 编译环境操作系统：windows 8.1 64位编程语言：C语言，编译选项添加-std=c99编译器：CodeBlocks自带的编译器2.2.2 功能描述基本功能有：从文件初始化线性表、销毁线性表、将线性表置空、判断线性表是否为空、求线性表的表长、获取线性表中特定元素值、定位元素在线性表中的位置、返回线性表中某元素的前驱、返回线性表中某元素的后继、在特定位置插入新的元素、删除

5、线性表中特定元素、遍历线性表、将线性表内容保存到文件。2.3 系统实现2.3.1 相关的类型及宏定义#define OK 1 /函数执行成功则返回OK#define FAIL 0 /函数执行失败则返回FAIL#define LIST_INIT_SIZE 300 /线性表的容量#define EMPTY 1 /线性表为空时返回EMPTY#define NON_EMPTY 0 /线性表不为空时返回NON_EMPTYchar * FilePath = Data.dat; /存储链表数据的文件名typedef int status; /函数的执行状态的返回值typedef structint item

6、1;Elemtype; /线性表中数据域的定义typedef structElemtype * elem;int length; /线性表长度int listsize; /线性表所能存储元素的最大值SqList; /线性表的表头2.3.2 相关函数说明及基本算法思想status IntiaList(SqList * L)/功能描述：初始化线性表。/算法思想：从文件中读取数据来初始化线性表并设置表长为数据的个数。status DestroyList(SqList * L)/功能描述：销毁线性表。/算法思想：将线性表的存储空间释放掉并置表长为0。status ClearList(SqList L)

7、/功能描述：清空线性表。/算法思想：直接置表长为0。status ListEmpty(SqList L)/功能描述：线性表是否为空。/算法思想：检查表长，如果位0，则线性表为空，否则不为空。int ListLength(SqList L)/功能描述：求线性表的长度。/算法思想：直接返回表长。status GetElem(SqList L,int i,Elemtype * e)/功能描述：获取线性表中指定元素。/算法思想：直接利用数组下标来返回指定的元素，如果下标不合法（大于表长或小于0），则返回空。status LocatElem(SqList L,Elemtype e,status (* c

8、ompare)(Elemtype x,Elemtype y)/功能描述：定位指定元素在线性表中的位置。/算法思想：对线性表进行扫描，若找到所求的元素则返回元素在表中次序，否则返回0。status PriorElem(SqList L,Elemtype cur,Elemtype * pre_e)/功能描述：获取指定元素的前驱。/算法思想：对线性表进行扫描，若指定元素存在且不为第一个元素，则返回其前一个元素的值，否则返回空。status NextElem(SqList L,Elemtype cur,Elemtype * next_e)/功能描述：获取指定元素的后继。/算法思想：对线性表进行扫描，若

9、指定元素存在且不为最后一个元素，则返回其后一个元素的值，否则返回空。status ListInsert(SqList * L,int position, Elemtype e)/功能描述：在线性表的position处插入新的元素。/算法思想：利用循环将position处之后的元素后移，再在position出插入新元素。status ListDelete(SqList * L,int position,Elemtype * e)/功能描述：删除线性表position处指定元素。/算法思想：通过循环直接将position之后的元素前移。status ListTrabverse(SqList L,v

10、oid (* visit)(Elemtype e)/功能描述：遍历线性表。/算法思想：在线性表中利用一个循环输出线性表的全部元素。status StoreToFile( SqList L)/功能描述：将线性表的内容保存到文件中去/算法思想：利用循环将线性表中的内容全部写入文件中。2.3.3 部分算法流程图status LocatElem(SqList L,Elemtype e,status (* compare)(Elemtype x,Elemtype y)函数核心算法流程图status ListInsert(SqList * L,int position, Elemtype e)函数核心算法

11、流程图2.3.4 部分运行截图图2.1 ListLength运行结果图2.2 GetElem运行结果图2.3 LocatElem运行结果图2.4 PriorElem运行结果图2.5 NextElem运行结果图2.6 ListTrabverse运行结果图2.7(a) ListInsert操作前图2.7(b) ListInsert操作图2.7(c) ListInsert操作后图2.8(a) ListDelete操作前图2.8(a) ListDelete操作图2.8(a) ListDelete操作后2.4 效率分析status IntiaList(SqList * L)算法的绝大部分时间用在从文件中

12、读数据上，与表长有关，复杂度为O(n)status DestroyList(SqList * L)算法时间为定值，复杂度为O(1)status ClearList(SqList L)算法时间为定值，复杂度为O(1)status ListEmpty(SqList L)算法时间为定值，复杂度为O(1)int ListLength(SqList L)算法时间为定值，复杂度为O(1)status GetElem(SqList L,int i,Elemtype * e)算法时间为定值，复杂度为O(1)status LocatElem(SqList L,Elemtype e,status (* compa

13、re)(Elemtype x,Elemtype y)算法的绝大部分时间用在线性表的遍历上，与表长有关，复杂度为O(n)status PriorElem(SqList L,Elemtype cur,Elemtype * pre_e)算法的绝大部分时间用在线性表的遍历上，与表长有关，复杂度为O(n)status NextElem(SqList L,Elemtype cur,Elemtype * next_e)算法的绝大部分时间用在线性表的遍历上，与表长有关，复杂度为O(n)status ListInsert(SqList * L,int position, Elemtype e)算法的绝大部分时间

14、用在元素的移动上，与表长有关，复杂度为O(n)status ListDelete(SqList * L,int position,Elemtype * e)算法的绝大部分时间用在元素的移动上，与表长有关，复杂度为O(n)status ListTrabverse(SqList L,void (* visit)(Elemtype e)算法的绝大部分时间用在线性表的遍历上，与表长有关，复杂度为O(n)status StoreToFile( SqList L)算法的绝大部分时间用在线性表的遍历上，与表长有关，复杂度为O(n)3 实验二 基于链式结构的线性表实现3.1 问题描述基于链式存储结构，实现链表

15、 ADT,具有13种基本运算。 要求： 提供一个实现功能的演示系统 具体物理结构和数据元素类型自行选定 线性表数据可以使用磁盘文件永久保存3.2 系统设计在本系统中，先创建一个结构体来作为线性表的表头，在表头中含有线性表的长度，线性表的大小以及指向线性表链表的头节点等信息。本系统所实现的对线性表的所有操作都通过这个表头来实现。3.2.1编译环境：操作系统：windows 8.1 64位编程语言：C语言，编译选项添加-std=c99编译器：CodeBlocks自带的编译器3.2.2实现的函数：基本功能有：从文件初始化线性表、销毁线性表、将线性表置空、判断线性表是否为空、求线性表的表长、获取线性表

16、中特定元素值、定位元素在线性表中的位置、返回线性表中某元素的前驱、返回线性表中某元素的后继、在特定位置插入新的元素、删除线性表中特定元素、遍历线性表。3.3 系统实现2.3.1 相关的类型及宏定义#define OK 1 /函数执行成功则返回OK#define FAIL 0 /函数执行失败则返回FAIL#define LIST_INIT_SIZE 300 /线性表的容量#define EMPTY 1 /线性表为空时返回EMPTY#define NON_EMPTY 0 /线性表不为空时返回NON_EMPTYchar * FilePath = Data.dat; /存储链表数据的文件名typede

17、f int status; /函数的执行状态的返回值typedef struct _Elemtypeint item1; /线性链表节点的数据域struct _Elemtype * next; Elemtype;typedef structElemtype * elem; /线性表链表头指针节点int length; /线性表内元素个数int listsize; /线性表最大元素个数SqList;3.3.2 相关函数说明及基本算法思想status IntiaList(SqList * L)/功能描述：初始化线性表。/算法思想：从文件中读取数据来初始化线性表并置表长为数据个数。status De

18、stroyList(SqList * L)/功能描述：销毁线性表。/算法思想： 利用链表操作将线性表所占空间释放掉status ClearList(SqList L)/功能描述：清空线性表。/算法思想：将线性表的节点数据域置0。status ListEmpty(SqList L)/功能描述：线性表是否为空。/算法思想：检查表长，如果位0，则线性表为空，否则不为空。int ListLength(SqList L)/功能描述：求线性表的长度。/算法思想：直接返回表长。status GetElem(SqList L,int i,Elemtype * e)/功能描述：获取线性表中指定元素。/算法思想：

19、利用循环，从线性表中第一个元素找起，若存在指定元素，则返回，否则返回空status LocatElem(SqList L,Elemtype e,status (* compare)(Elemtype x,Elemtype y)/功能描述：定位指定元素在线性表中的位置。/算法思想：对线性表进行扫描，若找到所求的元素则返回元素在表中次序，否则返回0。status PriorElem(SqList L,Elemtype cur,Elemtype * pre_e)/功能描述：获取指定元素的前驱。/算法思想：对线性表进行扫描，若指定元素存在且不为第一个元素，则返回其前一个元素的值，否则返回空。statu

20、s NextElem(SqList L,Elemtype cur,Elemtype * next_e)/功能描述：获取指定元素的后继。/算法思想：对线性表进行扫描，若指定元素存在且不为最后一个元素，则返回其后一个元素的值，否则返回空。status ListInsert(SqList * L,int position, Elemtype e)/功能描述：在线性表的position处插入新的元素/算法思想：利用链表的插入节点操作插入新元素status ListDelete(SqList * L,int position,Elemtype * e)/功能描述：删除线性表position处指定元素/算

21、法思想：利用链表的删除节点操作删除新元素status ListTrabverse(SqList L,void (* visit)(Elemtype e)/功能描述：遍历线性表/算法思想：在线性表中利用一个循环输出线性表的全部元素3.3.3 部分算法流程图PriorElem(SqList L,Elemtype cur,Elemtype * pre_e)函数核心算法流程图3.3.4 运行截图图3.1 ListLength运行结果图3.2 GetElem运行结果图3.3 LocatElem运行结果图3.4 PriorElem运行结果图3.5 NextElem运行结果图3.6 ListTraverse

22、运行结果图3.7(a) ListInsert运行前图3.7(b) ListInert运行图3.7(c) ListInsert运行后图3.8(a) ListDelete运行前图3.8 (b) ListDelete运行图3.8 (c) ListDelete运行后3.4效率分析status IntiaList(SqList * L)算法的绝大部分时间用在从文件中读数据上，与表长有关，复杂度为O(n)status DestroyList(SqList * L)算法的绝大部分时间用在从文件中读数据上，与表长有关，复杂度为O(n)status ClearList(SqList L)算法的绝大部分时间用在从

23、文件中读数据上，与表长有关，复杂度为O(n)status ListEmpty(SqList L)算法时间为定值，复杂度为O(1)int ListLength(SqList L)算法时间为定值，复杂度为O(1)status GetElem(SqList L,int i,Elemtype * e)算法的绝大部分时间用在线性表的遍历上，与表长有关，复杂度为O(n)status LocatElem(SqList L,Elemtype e,status (* compare)(Elemtype x,Elemtype y)算法的绝大部分时间用在线性表的遍历上，与表长有关，复杂度为O(n)status Pr

24、iorElem(SqList L,Elemtype cur,Elemtype * pre_e)算法的绝大部分时间用在线性表的遍历上，与表长有关，复杂度为O(n)status NextElem(SqList L,Elemtype cur,Elemtype * next_e)算法的绝大部分时间用在线性表的遍历上，与表长有关，复杂度为O(n)status ListInsert(SqList * L,int position, Elemtype e)算法的绝大部分时间用在线性表的遍历上，与表长有关，复杂度为O(n)status ListDelete(SqList * L,int position,El

25、emtype * e)算法的绝大部分时间用在线性表的遍历上，与表长有关，复杂度为O(n)status ListTrabverse(SqList L,void (* visit)(Elemtype e)算法的绝大部分时间用在线性表的遍历上，与表长有关，复杂度为O(n)4 实验三 基于二叉链表的二叉树实现4.1 问题描述实验（三）基于二叉链表，实现二叉树的基本的、常见的运算：提示：（1）提供一个实现功能的演示系统；（2）具体物理结构和数据元素类型自行选定；（3）可采用递归和非递归算法实现。4.2 系统设计4.2.1编译环境：操作系统：windows 8.1 64位编程语言：C+，编译时向VS编译器

26、传递/D _CRT_SECURE_NO_WARNINGS参数编译器：Visual Studio2013所带编译器4.2.2实现的函数：void InitBiTree( ) /功能描述：初始化二叉树为只有根节点。/算法思想：若二叉树存在，则先销毁在赋值，否则直接赋值。void DestroyBiTree( PntBT * root )/功能描述：销毁二叉树。/算法思想：利用递归访问二叉树的每一个节点，访问完成后释放掉其占用的内存。void CreateBiTree( )/功能描述：从文件创建二叉树。/算法思想：利用文件中读取的先序遍历序列和中序遍历序列生成一个二叉树。void ClearBiTr

27、ee(PntBT * root)/功能描述：清空二叉树。/算法思想：利用递归访问二叉树的每一个节点，将其数据域释放掉后置指针为空。int BiTreeEmpty(int a = 1 )/功能描述：判断二叉树是否为空。/算法思想：直接判断其节点数和非空结点数，只要有一个为0则二叉树为空。int BiTreeDepth( )/功能描述：返回二叉树的深度。/算法思想：利用递归来访问二叉树的所有节点，递归调用次数最多的一条路径上的递归调用次数就是二叉树的层数。PntBT *Root( int a )/功能描述：返回二叉树的根。/算法思想：直接返回根节点指针的地址。PntBT *Value( )/功能描

28、述：返回二叉树中指定节点的值。/算法思想：递归遍历二叉树，若发现所寻找的节点，则输出其值。PntBT *Assign()/功能描述：为二叉树指定节点赋值。/算法思想：递归遍历二叉树，若发现所寻找的节点，则为其赋值。PntBT *Parent()/功能描述：返回指定节点的父节点。/算法思想：递归遍历二叉树，若某节点的左孩子或右孩子为所寻找的节点，则返回此节点PntBT *LeftChild()/功能描述：返回二叉树的左孩子。/算法思想：递归遍历二叉树，若发现所寻找的节点，则返回其左孩子。PntBT *RightChild()/功能描述：返回指定节点的右孩子。/算法思想：递归遍历二叉树，若发现所寻

29、找的节点，则返回其右孩子。PntBT *LeftSibling()/功能描述：返回指定节点的左兄弟。/算法思想：递归遍历二叉树，若某节点的右孩子为所寻找的节点，则返回其左孩子。PntBT *RightSibling()/功能描述：返回指定节点的右兄弟。/算法思想：递归遍历二叉树，若某节点的左孩子为所寻找的节点，则返回其右孩子。void InsertChild( )/功能描述：在指定节点的左或右孩子处插入子树，并将节点原有的左或右孩子作为插入节点的右孩子。/算法思想：遍历二叉树，先找到所寻找的节点，再利用链表操作完成插入功能void DeleteChild( )/功能描述：删除二叉树中以指定节点

30、为根的子树。/算法思想：遍历二叉树，先找到所要寻找的子树，再利用DestroyBiTree来完成销毁操作。void PreOrderTraverse( )/功能描述：非递归先序遍历二叉树。/算法思想：利用栈来模仿递归操作，最终实现非递归先序遍历二叉树。void InOrderTraverse()/功能描述：非递归中序遍历二叉树。/算法思想：利用栈来模仿递归操作，最终实现非递归中序遍历二叉树。void PostOrderTraverse()/功能描述：非递归后序遍历二叉树。/算法思想：利用双栈法来非递归后序遍历二叉树。PntBT * LevelOrderTraverse(int isVisit)

31、/功能描述：层序遍历二叉树，并给二叉树的节点编号。/算法思想：利用队列来暂存二叉树某层的层序遍历序列，并将其中的节点编号并输出。 4.3 系统实现4.3.1本节内容简介：1.由于代码较长，为阅读方便起见，特专门列出二叉树的部分实现代码。由于主程序中以及一些基本的操作函数的实现代码大家都是大同小异的，故不再列出。2.在本系统中，多次使用了栈和队列这两种数据结构，但是为了方便起见，本系统并未按照相应的规范来实现这两种数据结构的操作，而是直接通过相应的指针来进行操作。并且，出于防止内存泄露的目的，本系统创建的栈和队列都是环状的，这样的设计便于由任意一个指针来销毁整个数据结构。同时，由于环状结构的特点

32、，为了防止极端情况下数据的丢失，本系统在为栈和队列这两种数据结构分配环状存储链的时候，分别多分配了几个空间来作为冗余缓冲。4.3.2相应的文件内容：BiTreeHeader.h头文件：#ifndef BITREEHEADER_H_INCLUDED#define BITREEHEADER_H_INCLUDED#include#include#include/-#define FALSE 0 #define TRUE 1#define GET_NODE 1#define TRAVEL 0/从PARENT开始定义的宏是用于TravelToGetMember函数的，用来标识要获取的节点类型#defin

33、e PARENT 0 #define LCHILD 1#define RCHILD 2#define LSIBLING 3#define RSIBLING 4#define SELF 5typedef struct struct_data char ele1;PntData; /二叉树节点中的数据域类型typedef struct struct_Bitreeint Number; /节点在二叉树中的编号，编号从1开始 PntData *data; struct struct_Bitree * LChild; struct struct_Bitree * RChild; PntBT; /二叉树的

34、节点类型typedef struct struct_queue PntBT * Node; struct struct_queue * next; PntQueue; /队列结构typedef struct struct_stackPntBT * Node;struct struct_stack * next,*prev; PntStack; /栈结构class BiTreepublic: BiTree(); /构造函数，初始化二叉树节点为空 BiTree();/析构函数，用来在二叉树对象销毁前回收内存 void InitBiTree( ); /初始化二叉树 void DestroyBiTre

35、e( PntBT * root ); /销毁二叉树 void CreateBiTree( ); /构造二叉树void ClearBiTree(PntBT * root); /清空二叉树 int BiTreeEmpty( ); /二叉树是否为空 int BiTreeDepth( ); /返回二叉树的深度 PntBT *Root( ); /返回二叉树的根 PntBT *Value( ); /返回二叉树中某节点的值PntBT *Assign(); /为二叉树中某节点赋值PntBT *Parent(); /若Cur_e是T的非根节点，则返回其双亲，否则返回空PntBT *LeftChild(); /返

36、回某节点的左孩子PntBT *RightChild(); /返回某节点的右孩子PntBT *LeftSibling();/返回某节点的左兄弟PntBT *RightSibling();/返回某节点的右兄弟 void InsertChild( ); /插入某节点为树中节点的子树 void DeleteChild( ); /删除某节点 void PreOrderTraverse( ); /先序遍历void InOrderTraverse(); /中序遍历void PostOrderTraverse(); /后序遍历PntBT * LevelOrderTraverse(int isVisit); /

37、层序遍历，编号从1开始private:PntBT *header = NULL; /二叉树的头指针 int isEmpty = TRUE; /标识二叉树是否为空 int NumberOfPoint = 0; /二叉树节点个数 int NumberOfMember = 0; /二叉树非空节点个数int isSorted = 0; /标识二叉树中的节点是否已有编号 void visit( PntBT * pBT); /访问节点并输出结果 void FreeBT( PntBT * root );/用在DestroyBiTree函数中，用来递归销毁二叉树PntBT * TravelToGetMembe

38、r(PntBT*root,int Number, int Member);/获取二叉树中特定节点的执行函数。通过传入的Member的值来判断要获取给定节点中哪种类型的成员，并返回相应的结果PntBT * GetMember(int Member);/一个中间层函数，用来处理用户执行获取某节点的指定成员的数据时相应的输出，具体的寻找节点的工作则由上面的TravelToGetMember函数来完成 void do_CreateBiTree( PntBT * root, /从文件中读取数据来创建二叉树int * Pre_arr, /先序遍历序列int * In_arr, /中序遍历序列char *

39、Content, /二叉树数据序列，以先序遍历序列组织 int Number ); /遍历序列的长度，也就是二叉树元素个数void do_GetDepth(PntBT * root ,int level, int * depth); /这是获取二叉树深度的执行函数PntQueue * CreateQueue(int n); /创建队列void DestroyQueue(PntQueue * p); /销毁队列PntStack * CreateStack(int n); /创建队列void DestroyStack(PntStack *p); /销毁队列PntBT * AllocMem(); /

40、为二叉树的节点分配内存空间;void menu(); /输出目录#endif / BITREEHEADER_H_INCLUDED4.3.3 部分算法流程图void PostOrderTraverse()函数核心算法流程图void PostOrderTraverse()函数核心算法流程图PntBT * LevelOrderTraverse(int isVisit)函数核心算法流程图4.3.4部分运行结果图4.1 BiTreeDepth运行结果图4.2 Value运行结果图4.3(a) Assign运行前图4.3(b) Assign运行图4.3(c) Assign运行后图4.4 Parent运行结

41、果图4.5 LeftChild运行结果图4.6 RightChild运行结果图4.7 LeftSibling运行结果图4.8 RightSibling运行结果图4.9(a) InsertChild运行前图4.9(b) InsertChild运行图4.9(c) InsertChild运行后图4.10(a) DeleteChild运行前图4.10(b) DeleteChild运行图4.10(c) DeleteChild运行后图4.11 PreOrderTraverse运行结果图4.12 InOrderTraverse运行结果图4.13 PostOrderTraverse运行结果图4.14 Leve

42、lOrderTraverse运行结果4.4 效率分析void InitBiTree 算法仅仅是给链表头赋值，时间复杂度为O(1)。void DestroyBiTree 算法递归销毁二叉树，递归的次数为二叉树的节点数n，时间复杂度为O(n)。 void CreateBiTree算法根据先序遍历序列和中序遍历序列递归地创建二叉树，递归次数为二叉树的节点数n，时间复杂度为O(n)。void ClearBiTree 算法递归清空二叉树，递归的次数为二叉树的节点数n，时间复杂度为O(n)。 int BiTreeEmpty 算法根据二叉树内部的节点及数据计数器判断二叉树是否为空，时间复杂度为O(1)。in

43、t BiTreeDepth 算法递归遍历二叉树，并且每次递归将层数计数器加1，递归的次数为节点数n，故时间复杂度为O(n)。 PntBT *Root算法返回二叉树的根地址，时间复杂度为O(1)。 PntBT *Value算法递归遍历二叉树，将指定节点的值返回，时间复杂度为O(n)。 PntBT *Assign 算法递归遍历二叉树，将指定节点进行修改，时间复杂度为O(n)。 PntBT *Parent 算法递归遍历二叉树，返回指定节点的父节点或空，时间复杂度为O(n)。 PntBT *LeftChild算法递归遍历二叉树，返回指定节点的左孩子或空，时间复杂度为O(n)。 PntBT *Right

44、Child 算法递归遍历二叉树，返回指定节点的右孩子或空，时间复杂度为O(n)。 PntBT *LeftSibling算法递归遍历二叉树，返回指定节点的左兄弟或空，时间复杂度为O(n)。PntBT *RightSibling 算法递归遍历二叉树，返回指定节点的右兄弟或空，时间复杂度为O(n)。void InsertChild算法递归遍历二叉树，找到符合要求的节点，并在指定的位置插入新的子节点，将此处原有的节点置为新节点的右孩子，时间复杂度为O(n)。void DeleteChild 算法递归遍历二叉树，删除以指定节点为根的二叉树，时间复杂度为O(n)。 void PreOrderTravers

45、e 算法非递归先序遍历二叉树，所做的操作次数与二叉树的节点个数线性相关，时间复杂度为O(n)。void InOrderTraverse 算法非递归中序遍历二叉树，所做的操作次数与二叉树的节点个数线性相关，时间复杂度为O(n)。void PostOrderTraverse 算法非递归后序遍历二叉树，所做的操作次数与二叉树的节点个数有关，时间复杂度为O(n)。PntBT * LevelOrderTraverse 算法层序遍历二叉树，所做的操作次数与二叉树的节点个数线性相关，时间复杂度为O(n)。5 实验总结与评价本次实验分为三个部分，第一部分是实现线性表的顺序结构的基本运算，第二部分是线性表的链式

46、结构的基本运算，第三部分是二叉树的基本运算。实验一，是基于线性表顺序存储结构的基本运算操作的实现。由于顺序存储结构在C语言实现上就是一个数组，而关于线性表的运算也较为基本，所以这个部分特别简单，基本上没费多少时间就完成了。并且由于并不涉及链表等操作，因此程序运行时基本没有崩溃的现象，出现的错误都是由于细节上的不注意引起的，改正起来也较为简单。我在这个试验中明白了细节的重要性。实验二，是基于线性表链式存储结构的基本运算操作的实现。虽然这个实验和第一个实验有所区别，链表的相关操作也比数组要复杂一些，但是这个实验和实验一还是有很多的相似性。因此我完成这个实验的时间也比较快。虽然在debug阶段程序会

47、出现崩溃现象，但是凭借我在C语言课上打下的功底，这些崩溃错误也很快被我解决了。我在这个试验中明白了基础的重要性。实验三，是基于二叉链表的二叉树的实现。相比起实验一和实验二，实验三就复杂多了，原因有三。一来是老师并没有给特定的程序框架，二来是书上的有些函数的参数类型并没有特定的说明，三来是二叉树的操作繁多，程序结构略显复杂。因此，整个系统的构架和相关的一些算法需要自己独立思考。这个思考的过程虽然挺累，但是特别有成就感。尤其是在独立思考出层序遍历的一种算法、根据先序遍历序列和中序遍历序列生成二叉树的算法，以及借鉴了网上的算法思想后写出的后序遍历的非递归算法之后，感觉自己的能力又进了一步。而在编程语

48、言的选取上，我选择了C+，因为利用其对象特性，方便对二叉树的相关信息和操作进行管理，在思考上也来得方便一些。而且由于这个实验中用到了队列和栈等数据结构，再加上二叉树本来的二插链表存储结构，使得系统中的大部分操作都是指针操作，并且由于在生成二叉树和一些寻找成员的函数上，递归操作用得比较多，因此程序的错误就比较多。在编译成功后，程序基本上在一半左右的函数运行的时候都会崩溃，因此这个实验的debug工作还是耗费了一些时间的。不过在整个系统完成后，看着自己的作品，还是蛮有成就感的，而之前的辛苦调试也就没有什么了。对于这三个实验，其实过程都差不多，都是痛苦调试之后的小小成就感。每个实验中，都有些部分可以进一步优化，减少时间空间复杂度，让程序运行更流畅。而我也正是在做这些实验、研究存储结构、子函数功能等的过程中得到了锻炼，更好的运用所学的知识，也掌握的更劳固，同时对数据结构这门课程的理解也得到了升华。相信在今后的学习生活中，数据结构这门课程的知识会带给我更多意想不到的惊喜。附注，相关源代码：6.1顺序结构线性表的部分代码：status IntiaList(SqList * L) FILE * pFile; L-length = -1;if( L-elem )DestroyList( L );L-elem = ( Elemtype *)malloc(LIST_INIT_S