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

课课 程程 设设 计计 报报 告告 课程名称课程名称： 数据结构数据结构 专业班级：专业班级： 学学 号：号： 姓姓 名：名： 指导教师：指导教师： 报告日期：报告日期： 计算机科学与技术计算机科学与技术 目录目录 实验一实验一 基于顺序结构的线性表实现基于顺序结构的线性表实现1 1.1 问题描述1 1.2 系统设计1 1.3.系统实现1 1.4 效率分析5 实验二实验二 基于链式结构的线性表实现基于链式结构的线性表实现6 2.1 问题描述6 2.2 系统设计6 2.3 系统实现6 2.4 效率分析10 实验三实验三 基于二叉链表的二叉树实现基于二叉链表的二叉树实现11 3.1 问题描述11 3.2 系统设计11 3.3 系统实现11 3.4 效率分析17 四四 实验总结与评价实验总结与评价17 0 实验一实验一 基于顺序结构的线性表实现基于顺序结构的线性表实现 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. ListLength 12. ListTrabverse 6. GetElem 13.Savelist 7. LocatElem 14.Loadlist 0. Exit 1.2.2 物理结构为顺序存储结构，数据元素为包含一个整型变量的结构体： 1.2.3 构建线性表之前先声明一个头结点，用于存储该表的基本信息和首结 点地址： 1.3.系统实现系统实现 1.3.1InitialList 功能 初始化线性表，传入的是头结点地址。申请一个大小为 LIST_INT_SIZE、类 型为 Elemtype 的线性存储空间，并用头结点中的首结点指针指向该空间首地址。 具体实现如下： 1.3.2DestroyList 功能 1 销毁头结点中首结点址针指向的线性存储空间，传入的是头结点地址。具 体实现如下： 1.3.3ClearList 功能 与 Destroy 类似但是又有不同，ClearList 并不销毁物理空间，而是修改逻辑 关系值： 1.3.4ListEmpt 功能 判空功能，判断表是否为空表。传入的是头结点值，而非地址，因为不需 要对头结点进行修改。实现如下： 1.3.5ListLenth 功能 求表长功能，由于创建过程中已经把表长信息包含在头结点中，所以直接 调用并显示即可： 1.3.6GetElem 功能 获取第 i 号元素，传入的是头结点值、元素编号 i、以及出口表结点地址。 2 1.3.7LocatElem 功能 获取指定元素编号，传入头结点值、存储了所需元素信息的一个临时表结 点值、equal 函数地址。采用顺序比较法从表头遍历并比较，一旦找到，返回编 号 i。时间复杂度为,O(n)。n/2/)1(nn 1.3.8PriorElem 功能 求指定元素的前一个元素的内容，传入头结点值、包含指定元素信息的一 个临时表结点值、存储前一个元素的表结点地址。主要思路是先调用 LocatElem 确定指定元素的位置，如果不是首结点则可直接取到 PriorElem 的地址。时间复 杂度为 O(n)。具体实现如下： 1.3.9NextElem 功能 与 PriorElem 功能类似，不再赘述。 1.3.10 ListInset 功能 插入一个数据元素，传入头结点地址、插入位置 i、临时表结点值。在调用 插入函数前构造一个临时表结点，用于存储数据元素信息。进入插入子函数， 插入前先判断插入位置是否合理，再判断是否“满载” 。如果满载则重新申请更 大的存储空间。接下来正式插入数据元素， “先空位置再插入” 。平均时间复杂 度为 ，O(n)，n 即 listlenth。 n/2/)1(nn 3 1.3.11 ListDelete 功能 删除指定编号的数据元素，传入头结点地址、编号 i、表结点类型结构体地 址来返回被删除元素内容。执行前先判断传入的编号是否在可寻找范围内。执 行删除操作之后，进行“移位”运算。时间复杂度仍为 O(n)。如下： 1.3.12 ListTraverse 功能 顺序遍历顺序表元素，传入头结点值、display 函数地址。时间复杂度为 O(n) 1.3.13 SaveList 功能 将顺序表保存到文件，通过 C 中文件函数 fprintf 实现格式化写入。时间复 杂度同遍历。 1.3.14 LoadList 功能 4 读取功能，通过 fscanf 实现格式化读取，同时结合 CreateList 函数实现顺序 表建立。 1.3.15display 与 equal 函数 1.4 效率分析效率分析 在上面介绍各功能时已经提到时间复杂度的计算了，这里再简单分析一下。 具有同数量级复杂度的功能在实现方法上一般近似。 比如 ListTraverse、SaveList、LoadList，它们都是基于 ListTraverse 来设计的， 所以效率都是 O(n)； 而 LocatElem、PriorElem、NextElem 是基于 LocatElem，平均效率为 O(n)； 由于在头结点结构体中已经包含了 ListEmpty、ListLength 所需信息，所以效 率为 O(1)； ListInsert、ListDelete 都要对顺序表进行“移位”运算，平均效率为 O(n)。 5 实验二实验二 基于链式结构的线性表实现基于链式结构的线性表实现 2.1 问题描述问题描述 基于链式存储结构，实现线性表的基本的、常见的运算。 2.2 系统设计系统设计 2.2.1同样提供 14 个功能 2.2.2 物理结构为链式结构，数据元素包含一个整型变量以及自身类型的指 针 2.2.3 类似与线性表，也使用一个头结点存储链首和链表信息： 2.3 系统实现系统实现 2.3.1InitiaList 由于链表的创建是动态的，因此初始化不需要创建一个巨大的存储空间。 2.3.2DestroyList 需要遍历链表，同时释放掉每个元素。 6 2.3.3ClearList 由于链表不同于数序表，这里不仅要在逻辑上清空，还要在物理结构上清 空，实现上与 Destroy 类似。 2.3.4ListEmpty 判空操作，L.elem 不为 NULL 即不空。 2.3.5ListLength 求表长，由于在插入元素的同时已经记录了表长信息，所以只要读取 L.length 即可。 2.3.6GetElem 取第 i 号元素并用一个数据元素类型结构体指针传出其信息。 7 2.3.7LocatElem 基于遍历链表实现定位。 2.3.8PriorElem 基于遍历找到指定元素的前一个元素。 2.3.9NextElem 与 PriorElem 思路同，不赘述。 8 2.3.10ListInsert 插入一个新元素。 2.3.11ListDelete 删除第 i 号元素。 2.3.12ListTraverse 顺序遍历链表。 2.3.14SaveList 调用块写入函数 fwrite 写入整个结构体信息。 9 2.3.13LoadList 调用 fread 读取块信息。 2.3.14display 与 equal 函数 2.4 效率分析效率分析 同样地，分类分析各功能效率。 很多功能都基于遍历： DestroyList、Clearlist、ListTraverse、SaveList、LoadList，效率为 O(n); GetElem、LocatElem、PriorElem、NextElem、ListInsert、ListDelete，平均效率也 为 O(n)。 10 实验三实验三 基于二叉链表的二叉树实现基于二叉链表的二叉树实现 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 B E C DF 具体实现如下: 11 3.3.2Traverse 下设子菜单： 3.3.2.1 递归先序遍历 利用递归的特点，每次访问完根节点后，分别把其左儿子和右儿子设为根 节点，递归调用，如果为空则不访问。 非递归先序 利用堆栈的特点实现，根节点入栈，每次循环先访问栈顶元素，访问完毕 12 立即出栈，接着把非空右儿子和左儿子分别入栈，直到全部访问完毕。 3.3.2.2 递归中序遍历 思路与递归先序相同。 非递归中序 同样是利用堆栈的巧妙特点，先按照“深度优先”将左子树根结点全部入栈而 不立即访问，到达“最左端”时进行访问并出栈，然后把该结点右儿子入栈，再 重复上述过程。 13 3.3.2.3 递归后序遍历 非递归后序遍历 这里同样用堆栈的方法实现，但是比之前两个都复杂。先构造一个结构体， 作为栈元素： 总的思路是左子树的根结点全部入栈，这和非递归中序相似，接着为了先 把根结点右儿子入栈并访问，就要回到上一个根结点，这样的话加入一个标记 flag，以判断是否访问根节点。同时值得注意的是，在执行过程中会修改元素内 的指向关系，所以这些关系放在 A、B 两个临时存储空间内保存，到最后还原。 14 3.3.2.4 层遍历 使用循环队列。 15 3.3.3 计算叶子数目 递归实现 按照“总叶子数=左子树叶子数+右子树椰子树”思路设计，递归出口为 “左右子树均不存在时返回 1，根节点为空返回 0” 。实现如下： 非递归实现 基于“非递归先序遍历”设计，只是加了一个计数变量 LeavesNum，遍历时 加了一个判断。 16 3.3.4 求二叉树高度 递归思想， “当前二叉树树高度=左子树高度与右子树高度最大值+1” 3.3.5 打印函数 3.4 效率分析效率分析 3.4.1 建立二叉树 由于是基于递归先序遍历建立二叉树，所以效率为 O(n)。 3.4.2 Traverse 对于递归实现的三种遍历、非递归实现的先序和中序遍历以及队列法实现 的层遍历，由于每个元素被访问到且仅访问一次，且不要进行其他额外大型运 算，所以效率为 O(n)。 对于非递归堆栈的后序遍历，每个元素被访问到的次数为 2，而且还要把所 有左子树的指向关系保存，假设结点数为 n，则左子树个数平均为 n(n-1)/2n， 综上，平均时间复杂度为 O(5n/2)=O(n)。 3.4.3 求叶子数 基于遍历实现，效率也为 O(n)。 3.4.4 求深度 17 也是基于遍历，所以也是 O(n)。Error! No bookmark name given. 四四 实验总结与评价实验总结与评价 首先不得不提到的是，三个实验虽然都经过细心推敲，但是由于懒惰和能 力问题，必然存在很多大 BUG、小 BUG，特别是第三个“基于二叉链表的二叉 树实现” ，在建立二叉链表时只默认输入是按要求的，一旦没有按要求就会报错 退出，这个是由于懒惰了。 对于前两个线性表的实验，功能都实现了，而且质量也不错，按要求加的 保存与读取也有，而且还根据线性物理空间和链式空间的不同特点，选择了不 同的保存方案，这一点是我自己开始也没想到的。开始都想用“块存入与读取” 方式实现，因为之前做过很熟悉，后来发现线性物理结构上实现不方便也没必 要，所以才想到用“格式化写入与读取” 。 在第三个实验中，由于心思都花在考虑如何实现非递归三种遍历和层遍历 上，再想回过头写那些小功能就不太情愿，所以最后还是决定把