1、课 程 实 验 报 告课程名称： 数据结构实验 专业班级： 信息安全 201502 学 号： 姓 名： 指导教师： 报告日期： 2016 年 10 月 28 日 计算机科学与技术学院华中科技大学计算机学院数据结构实验报告目 录1 基于顺序存储结构的线性表实现 .11.1 问题描述 .11.2 系统设计 .11.3 系统实现 .11.4 实验小结 .12 基于二叉链表的二叉树实现 .22.1 问题描述 .22.2 系统设计 .22.3 系统实现 .22.4 实验小结 .2指导教师评定意见 .3附录 A 基于顺序存储结构线性表实现的源程序 .4附录 B 基于二叉链表二叉树实现的源程序 .5华中科技
2、大学计算机学院数据结构实验报告11 基于顺序存储结构的线性表实现1.1 问题描述采用顺序表的物理结构，构造一个具有菜单的功能演示系统。其中，在主程序中完成函数调用所需实参值的准备和函数执行结果的显示。定义了线性表的初始化表、销毁表、清空表、判定空表、求表长和获得元素等基本运算对应的函数，并给出适当的操作提示显示，可选择以文件的形式进行存储和加载，即将生成的线性表存入到相应的文件中，也可以从文件中获取线性表进行操作。1.1.1 线性表的基本概念线性表是最常用且最简单的一种数据结构，即 n 个数据元素的有限序列。线性表中元素的个数 n 定义为线性表的长度，n=0 时成为空表。在非空表中的每个数据元
3、素都有一个确定的位置，如 a1 是第一个数据元素，an 是最后一个数据元素，ai 是第 i 个数据元素。线性表的存储结构分为线性存储和链式存储。1.1.2 逻辑结构与基本运算线性表的数据逻辑结构定义如下:ADT List 数据对象：D=ai|aiElemSet，i=1，2，n，n0 数据关系：R1= | ai-1，aiD，i=2，n 依据最小完备性和常用性相结合的原则，以函数形式定义了包括线性表的初始化表、加载表、保存表、销毁表、清空表、判定空表、求表长、获得元素、查华中科技大学计算机学院数据结构实验报告2找元素、获得前驱、获得后继、插入元素、删除元素、遍历表 14 个基本运算，要求分别定义函
4、数来实现上述功能，具体功能运算如下：初始化表：函数名称是 InitaList(L)；初始条件是线性表 L 不存在已存在；操作结果是构造一个空的线性表。销毁表：函数名称是 DestroyList(L)；初始条件是线性表 L 已存在；操作结果是销毁线性表 L。清空表：函数名称是 ClearList(L)；初始条件是线性表 L 已存在；操作结果是将 L 重置为空表。判定空表：函数名称是 ListEmpty(L)；初始条件是线性表 L 已存在；操作结果是若 L 为空表则返回 TRUE,否则返回 FALSE。求表长：函数名称是 ListLength(L)；初始条件是线性表已存在；操作结果是返回 L 中数
5、据元素的个数。获得元素：函数名称是 GetElem(L,i,e)；初始条件是线性表已存在，1iListLength(L)；操作结果是用 e 返回 L 中第 i 个数据元素的值。查找元素：函数名称是 LocateElem(L,e,compare()；初始条件是线性表已存在；操作结果是返回 L 中第 1 个与 e 满足关系 compare（）关系的数据元素的位序，若这样的数据元素不存在，则返回值为 0。获得前驱：函数名称是 PriorElem(L,cur_e,pre_e)；初始条件是线性表L 已存在；操作结果是若 cur_e 是 L 的数据元素，且不是第一个，则用 pre_e返回它的前驱，否则操作
6、失败，pre_e 无定义。获得后继：函数名称是 NextElem(L,cur_e,next_e)；初始条件是线性表L 已存在；操作结果是若 cur_e 是 L 的数据元素，且不是最后一个，则用next_e 返回它的后继，否则操作失败，next_e 无定义。Comment l1: 黑体 4号加粗， 间距前后 0.5行华中科技大学计算机学院数据结构实验报告3插入元素：函数名称是 ListInsert(L,i,e)；初始条件是线性表 L已存在且非空，1iListLength(L)+1；操作结果是在 L的第 i个位置之前插入新的数据元素 e。删除元素：函数名称是 ListDelete(L,i,e)；初
7、始条件是线性表 L已存在且非空，1iListLength(L)；操作结果：删除 L的第 i个数据元素，用 e返回其值。遍历表：函数名称是 ListTraverse(L,visit()，初始条件是线性表 L已存在；操作结果是依次对 L的每个数据元素调用函数 visit()。1.1.3 演示系统与数据文件要求构造一个具有菜单的功能演示系统。其中，在主程序中完成函数调用所需实参值的准备和函数执行结果的显示，并给出适当的操作提示显示。附录 A 提供了简易菜单的框架。 演示系统可选择实现线性表的文件形式保存。其中，需要设计文件数据记录格式，以高效保存线性表数据逻辑结构(D,R)的完整信息；需要设计线性表
8、文件保存和加载操作合理模式。附录 B 提供了文件存取的方法。 演示系统可选择实现多个线性表管理。1.2 系统设计1.2.1 数据物理结构线性表的数据物理结构如下：华中科技大学计算机学院数据结构实验报告4typedef struct /顺序表（顺序结构）的定义 ElemType *elem; /定义整型指针，为存储空间基址 int length; /线性表的长度 int listsize; /当前分配的存储容量 (以 sizeof(ElemType)为单位) SqList;要实现同时对多个线性表管理，只需要定义一个结构数组即可。1.2.2 演示系统将菜单演示和用户选择写入到 while 循环中，
9、用 OP 获取用户的选择，OP 初始化为 1，以便第一次能进入循环。进入循环后系统首先显示功能菜单，然后用户输入选择 0-14，其中 1-14 分别代表线性表的一个基本运算，在主函数中通过 SWITCH 语句对应到相应的函数功能，执行完该功能后 BREAK 跳出 SWITCH语句，继续执行 while 循环，直至用户输入 0 退出当前演示系统。在第一次进入循环 while 时首先会询问用户对哪个线性表进行操作，直至退出演示系统之前一直对指定线性表进行操作。演示系统结构如图 1-1.华中科技大学计算机学院数据结构实验报告51.2.3 运算算法思想与设计线性表运算算法思想与设计如下：1. 初始化线
10、性表思想：将线性表初始化过程写成函数，其中传入函数的参数是主函数中定义的结构型变量 L 的引用，在函数中，首先使用 malloc函数分配 LISTSIZE 大小的连续内存空间，并将首地址返回赋值给L.elem，由于线性表的长度为 0，将 L.length 初始化为 0，即完成了线性表的初始化。经分析，算法的时间复杂度为 O(1)。2. 销毁线性表思想：将销毁线性表的过程写成函数，其中传入函数是主函数中定义的结构性变量 L。在函数中，首先使用 free 函数释放掉以L.elem 为首地址的连续内存空间，再将 L.length,L.listsize 重新赋值为 0。经分析，该算法的时间复杂度为 O
11、(1)。3. 清空线性表的思想：将清空表的过程写成函数，其中将主函数中定义的结构性变量 L 的引用作为函数参数，在函数中，由于清空操作并不释放内存空间，故只需将线性表的长度置为 0 即可。经分许，该算法的时间华中科技大学计算机学院数据结构实验报告6复杂度为 O(1)。4. 求线性表表长的思想：将求表长过程写成函数，其中主函数中定义的结构性变量 L 的引用作为函数的参数，在函数中，直接返回 L.length 即为所求线性表的表长。经分析，该算法的时间复杂度为 O（1） 。5. 获得元素的算法思想：将获得线性表元素写成函数，其中函数的参数是结构型变量 L 以及数据元素的序号 i，由于采取的是线性存
12、储结构，故直接通过访问数组的方式即 L.elemi-1来获取元素，当然，在这之前需要判断合法性。经分析，该算法的时间复杂度为 O（1） 。6. 查找元素的算法思想：将查找线性表特定值的数据元素写成函数，其中函数的参数是主函数中定义的结构类型变量 L 以及查找的数据元素的值，通过循环对线性表中的每一个元素与给定值比较看是否相等，如果相等就返回该元素的次序。经分析，该算法的时间复杂度为 O（n） 。查找算法的流程图如图 1-2 所示。华中科技大学计算机学院数据结构实验报告7图 1-2 线性表查找算法流程图7. 获得前驱算法思想：将获得前驱过程写成函数，函数的参数是结构体类型变量以及特定数据元素的值
13、，接受前驱的变量作为另一个参数，首先调用获得元素的函数判断该线性表中特定数据元素的位序，首先判断不为 1，否则的话返回 FALSE，然后直接返回其前一个元素即 L.elemj-2。经分析，该算法的时间复杂度为 O（n） 。8. 获得后继算法思想：将获得后继写成函数，函数的参数是结构体类型变量以及特定数据元素的值。首先判断是否为最后一个元素，如果不是则直接返回其后一个元素，否则的话返回 FALSE，同样该算法需要调用获得元素的函数来确定该特定元素在线性表中的次序。经分析，该算法的时间复杂度为 O（n） 。9. 插入元素算法思想：将插入函数写成函数，函数的参数是结构型变量以及插入元素的值大小以及插入位置。在函数中，首先判断插入位置的合法性，即是否在线性表中合适的位置，其次还要判断当前存储空间是否已满，如果满了的话要 malloc 函数重新分配空间，插入元素时从该位置起到最后一个元素从后开始以此往后移一个单元。经分析，该算法的时间复杂度为 O（n） 。该算法的程序流程图如图 1-3 所示。
