华中科技大学计算机11级数据结构实验报告

1、0 / 19 文档可自由编辑打印课课 程程 设设 计计 报报 告告课程名称课程名称： 数据结构数据结构 专业班级：专业班级： 学学 号：号： 姓姓 名：名： 指导教师：指导教师： 报告日期：报告日期： 计算机科学与技术计算机科学与技术1 / 19 文档可自由编辑打印目录目录实验一实验一 基于顺序结构的线性表实现基于顺序结构的线性表实现11.1 问题描述11.2 系统设计11.3.系统实现11.4 效率分析5实验二实验二 基于链式结构的线性表实现基于链式结构的线性表实现62.1 问题描述62.2 系统设计62.3 系统实现62.4 效率分析10实验三实验三 基于二叉链表的二叉树实现基于二叉链表的

2、二叉树实现113.1 问题描述113.2 系统设计113.3 系统实现113.4 效率分析17四四 实验总结与评价实验总结与评价170 / 19 文档可自由编辑打印实验一实验一 基于顺序结构的线性表实现基于顺序结构的线性表实现1.1 问题描述问题描述基于顺序存储结构，实现线性表的基本的、常见的运算。1.2 系统设计系统设计1.2.1 提供 14 个功能，分别是： 1. InitiaList 8. PriorElem 2. DestroyList 9. NextElem 3. ClearList 10. ListInsert 4. ListEmpty 11. ListDelete 5. List

3、Length 12. ListTrabverse 6. GetElem 13.Savelist 7. LocatElem 14.Loadlist 0. Exit1.2.2 物理结构为顺序存储结构，数据元素为包含一个整型变量的结构体：1.2.3 构建线性表之前先声明一个头结点，用于存储该表的基本信息和首结点地址：1.3.系统实现系统实现1.3.1InitialList 功能初始化线性表，传入的是头结点地址。申请一个大小为 LIST_INT_SIZE、类型为 Elemtype 的线性存储空间，并用头结点中的首结点指针指向该空间首地址。具体实现如下：1.3.2DestroyList 功能销毁头结点中

4、首结点址针指向的线性存储空间，传入的是头结点地址。具1 / 19 文档可自由编辑打印体实现如下：1.3.3ClearList 功能与 Destroy 类似但是又有不同，ClearList 并不销毁物理空间，而是修改逻辑关系值：1.3.4ListEmpt 功能判空功能，判断表是否为空表。传入的是头结点值，而非地址，因为不需要对头结点进行修改。实现如下：1.3.5ListLenth 功能求表长功能，由于创建过程中已经把表长信息包含在头结点中，所以直接调用并显示即可：1.3.6GetElem 功能获取第 i 号元素，传入的是头结点值、元素编号 i、以及出口表结点地址。1.3.7LocatElem 功

5、能2 / 19 文档可自由编辑打印获取指定元素编号，传入头结点值、存储了所需元素信息的一个临时表结点值、equal 函数地址。采用顺序比较法从表头遍历并比较，一旦找到，返回编号 i。时间复杂度为,O(n)。n/2/)1(nn1.3.8PriorElem 功能求指定元素的前一个元素的内容，传入头结点值、包含指定元素信息的一个临时表结点值、存储前一个元素的表结点地址。主要思路是先调用 LocatElem确定指定元素的位置，如果不是首结点则可直接取到 PriorElem 的地址。时间复杂度为 O(n)。具体实现如下：1.3.9NextElem 功能与 PriorElem 功能类似，不再赘述。1.3.

6、10 ListInset 功能插入一个数据元素，传入头结点地址、插入位置 i、临时表结点值。在调用插入函数前构造一个临时表结点，用于存储数据元素信息。进入插入子函数，插入前先判断插入位置是否合理，再判断是否“满载” 。如果满载则重新申请更大的存储空间。接下来正式插入数据元素， “先空位置再插入” 。平均时间复杂度为 ，O(n)，n 即 listlenth。n/2/)1(nn1.3.11 ListDelete 功能3 / 19 文档可自由编辑打印删除指定编号的数据元素，传入头结点地址、编号 i、表结点类型结构体地址来返回被删除元素内容。执行前先判断传入的编号是否在可寻找范围内。执行删除操作之后，

7、进行“移位”运算。时间复杂度仍为 O(n)。如下：1.3.12 ListTraverse 功能顺序遍历顺序表元素，传入头结点值、display 函数地址。时间复杂度为O(n)1.3.13 SaveList 功能将顺序表保存到文件，通过 C 中文件函数 fprintf 实现格式化写入。时间复杂度同遍历。1.3.14 LoadList 功能读取功能，通过 fscanf 实现格式化读取，同时结合 CreateList 函数实现顺序表建立。4 / 19 文档可自由编辑打印1.3.15display 与 equal 函数1.4 效率分析效率分析在上面介绍各功能时已经提到时间复杂度的计算了，这里再简单分析

8、一下。具有同数量级复杂度的功能在实现方法上一般近似。比如 ListTraverse、SaveList、LoadList，它们都是基于 ListTraverse 来设计的，所以效率都是 O(n)；而 LocatElem、PriorElem、NextElem 是基于 LocatElem，平均效率为 O(n)； 由于在头结点结构体中已经包含了 ListEmpty、ListLength 所需信息，所以效率为 O(1)；ListInsert、ListDelete 都要对顺序表进行“移位”运算，平均效率为 O(n)。5 / 19 文档可自由编辑打印实验二实验二 基于链式结构的线性表实现基于链式结构的线性表

9、实现2.1 问题描述问题描述基于链式存储结构，实现线性表的基本的、常见的运算。2.2 系统设计系统设计2.2.1同样提供 14 个功能 2.2.2 物理结构为链式结构，数据元素包含一个整型变量以及自身类型的指针 2.2.3 类似与线性表，也使用一个头结点存储链首和链表信息：2.3 系统实现系统实现2.3.1InitiaList由于链表的创建是动态的，因此初始化不需要创建一个巨大的存储空间。2.3.2DestroyList需要遍历链表，同时释放掉每个元素。6 / 19 文档可自由编辑打印2.3.3ClearList由于链表不同于数序表，这里不仅要在逻辑上清空，还要在物理结构上清空，实现上与 De

10、stroy 类似。2.3.4ListEmpty判空操作，L.elem 不为 NULL 即不空。2.3.5ListLength求表长，由于在插入元素的同时已经记录了表长信息，所以只要读取L.length 即可。2.3.6GetElem取第 i 号元素并用一个数据元素类型结构体指针传出其信息。7 / 19 文档可自由编辑打印2.3.7LocatElem基于遍历链表实现定位。2.3.8PriorElem基于遍历找到指定元素的前一个元素。2.3.9NextElem与 PriorElem 思路同，不赘述。8 / 19 文档可自由编辑打印2.3.10ListInsert插入一个新元素。2.3.11List

11、Delete删除第 i 号元素。2.3.12ListTraverse顺序遍历链表。2.3.14SaveList调用块写入函数 fwrite 写入整个结构体信息。9 / 19 文档可自由编辑打印2.3.13LoadList调用 fread 读取块信息。2.3.14display 与 equal 函数2.4 效率分析效率分析同样地，分类分析各功能效率。很多功能都基于遍历：DestroyList、Clearlist、ListTraverse、SaveList、LoadList，效率为 O(n);GetElem、LocatElem、PriorElem、NextElem、ListInsert、ListD

12、elete，平均效率也为 O(n)。10 / 19 文档可自由编辑打印实验三实验三 基于二叉链表的二叉树实现基于二叉链表的二叉树实现3.1 问题描述问题描述基于二叉链表，实现二叉树的下列运算：二叉树生成前序、中序和后序遍历计算叶子数目按层遍历计算二叉树高度3.2 系统设计系统设计3.2.1 使用链式结构，树结点类型为结构体：3.2.2 运算分别采用递归和非递归算法实现。3.2.3 使用一个 BiTNode 型指针 T 指向根节点，T 的初值为 NULL。3.3 系统实现系统实现3.3.1CreateBitree基于递归先序遍历创建二叉树，比如二叉树：则创建时输入 ABC D E F #回车。A

13、BECDF具体实现如下:11 / 19 文档可自由编辑打印3.3.2Traverse下设子菜单：3.3.2.1递归先序遍历利用递归的特点，每次访问完根节点后，分别把其左儿子和右儿子设为根节点，递归调用，如果为空则不访问。非递归先序利用堆栈的特点实现，根节点入栈，每次循环先访问栈顶元素，访问完毕立即出栈，接着把非空右儿子和左儿子分别入栈，直到全部访问完毕。12 / 19 文档可自由编辑打印3.3.2.2递归中序遍历思路与递归先序相同。非递归中序同样是利用堆栈的巧妙特点，先按照“深度优先”将左子树根结点全部入栈而不立即访问，到达“最左端”时进行访问并出栈，然后把该结点右儿子入栈，再重复上述过程。1

14、3 / 19 文档可自由编辑打印3.3.2.3递归后序遍历非递归后序遍历这里同样用堆栈的方法实现，但是比之前两个都复杂。先构造一个结构体，作为栈元素：总的思路是左子树的根结点全部入栈，这和非递归中序相似，接着为了先把根结点右儿子入栈并访问，就要回到上一个根结点，这样的话加入一个标记flag，以判断是否访问根节点。同时值得注意的是，在执行过程中会修改元素内的指向关系，所以这些关系放在 A、B 两个临时存储空间内保存，到最后还原。14 / 19 文档可自由编辑打印3.3.2.4 层遍历使用循环队列。15 / 19 文档可自由编辑打印3.3.3 计算叶子数目递归实现按照“总叶子数=左子树叶子数+右子

15、树椰子树”思路设计，递归出口为“左右子树均不存在时返回 1，根节点为空返回 0” 。实现如下：非递归实现基于“非递归先序遍历”设计，只是加了一个计数变量 LeavesNum，遍历时加了一个判断。3.3.4 求二叉树高度递归思想， “当前二叉树树高度=左子树高度与右子树高度最大值+1”3.3.5 打印函数16 / 19 文档可自由编辑打印3.4 效率分析效率分析3.4.1 建立二叉树由于是基于递归先序遍历建立二叉树，所以效率为 O(n)。3.4.2 Traverse对于递归实现的三种遍历、非递归实现的先序和中序遍历以及队列法实现的层遍历，由于每个元素被访问到且仅访问一次，且不要进行其他额外大型运

16、算，所以效率为 O(n)。对于非递归堆栈的后序遍历，每个元素被访问到的次数为 2，而且还要把所有左子树的指向关系保存，假设结点数为 n，则左子树个数平均为 n(n-1)/2n，综上，平均时间复杂度为 O(5n/2)=O(n)。3.4.3 求叶子数基于遍历实现，效率也为 O(n)。3.4.4 求深度也是基于遍历，所以也是 O(n)。Error! No bookmark name given.四四 实验总结与评价实验总结与评价首先不得不提到的是，三个实验虽然都经过细心推敲，但是由于懒惰和能力问题，必然存在很多大 BUG、小 BUG，特别是第三个“基于二叉链表的二叉树实现” ，在建立二叉链表时只默认输入是按要求的，一旦没有按要求就会报错退出，这个是由于懒惰了。对于前两个线性表的实验，功能都实现了，而且质量也不错，按要求加的保存与读取也有，而且还根据线性物理空间和链式空间的不同特点，选择了不同的保存方案，这一点是我自己开始也没想到的。开始都想用“块存入与读取”方式实现，因为之前做过很熟悉，后来发现线性物理结构上实现不方便也没必要，所以才想到用“格式化写入与读取” 。在第三个实验中，由于心思都花在考虑如何实现非递归三种遍历和层遍历上，再想回过头写那些小功能就不太情