课程实验报告
课程名称：数据结构实验
专业班级：信息安全201502 学号： 姓名： 指导教师：
报告日期： 2016年10月 28 日
计算机科学与技术学院
华中科技大学计算机学院数据结构实验报告
目录
1基于顺序存储结构的线性表实现 ..................................... 1 1.1问题描述 ........................................................ 1 1.2系统设计 ........................................................ 3 1.3系统实现 ........................................................ 7 1.4实验小结 ....................................................... 16 2 基于二叉链表的二叉树实现 ....................................... 17 2.1问题描述 ....................................................... 17 2.2系统设计 ....................................................... 20 2.3系统实现 ....................................................... 23 2.4实验小结 ....................................................... 40 指导教师评定意见 ................................................. 42 附录A 基于顺序存储结构线性表实现的源程序 ......................... 44 附录B 基于二叉链表二叉树实现的源程序 ............................. 52
华中科技大学计算机学院数据结构实验报告
1基于顺序存储结构的线性表实现
1.1问题描述
采用顺序表的物理结构，构造一个具有菜单的功能演示系统。其中，在主程序中完成函数调用所需实参值的准备和函数执行结果的显示。定义了线性表的初始化表、销毁表、清空表、判定空表、求表长和获得元素等基本运算对应的函数，并给出适当的操作提示显示，可选择以文件的形式进行存储和加载，即将生成的线性表存入到相应的文件中，也可以从文件中获取线性表进行操作。 1.1.1线性表的基本概念
线性表是最常用且最简单的一种数据结构，即n个数据元素的有限序列。线性表中元素的个数n定义为线性表的长度，n=0时成为空表。在非空表中的每个数据元素都有一个确定的位置，如a1是第一个数据元素，an是最后一个数据元素，ai是第i个数据元素。线性表的存储结构分为线性存储和链式存储。 1.1.2 逻辑结构与基本运算 线性表的数据逻辑结构定义如下:
ADT List｛
数据对象：D=｛ai|ai∈ElemSet，i=1，2，??，n，n≥0｝ 数据关系：R1=｛ | ai-1，ai∈D，i=2，??，n｝ ｝
依据最小完备性和常用性相结合的原则，以函数形式定义了包括线性表的初 始化表、加载表、保存表、销毁表、清空表、判定空表、求表长、获得元素、查 找元素、获得前驱、获得后继、插入元素、删除元素、遍历表 14 个基本运算， 要求分别定义函数来实现上述功能，具体功能运算如下：
⑴初始化表：函数名称是InitaList(L)；初始条件是线性表L不存在已存在；操作结果是构造一个空的线性表。
⑵销毁表：函数名称是DestroyList(L)；初始条件是线性表L已存在；操作结果是销毁线性表L。
1
华中科技大学计算机学院数据结构实验报告
⑶清空表：函数名称是ClearList(L)；初始条件是线性表L已存在；操作结果是将L重置为空表。
⑷判定空表：函数名称是ListEmpty(L)；初始条件是线性表L已存在；操作结果是若L为空表则返回TRUE,否则返回FALSE。
⑸求表长：函数名称是ListLength(L)；初始条件是线性表已存在；操作结果是返回L中数据元素的个数。
⑹获得元素：函数名称是GetElem(L,i,e)；初始条件是线性表已存在，1≤i≤ListLength(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返回它的前驱，否则操作失败，pre_e无定义。
⑼获得后继：函数名称是NextElem(L,cur_e,next_e)；初始条件是线性表L已存在；操作结果是若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。
⑽插入元素：函数名称是ListInsert(L,i,e)；初始条件是线性表L已存在且非空，1≤i≤ListLength(L)+1；操作结果是在L的第i个位置之前插入新的数据元素e。
⑾删除元素：函数名称是ListDelete(L,i,e)；初始条件是线性表L已存在且非空，1≤i≤ListLength(L)；操作结果：删除L的第i个数据元素，用e返回其值。
⑿遍历表：函数名称是ListTraverse(L,visit())，初始条件是线性表L已存在；操作结果是依次对L的每个数据元素调用函数visit()。 1.1.3 演示系统与数据文件
要求构造一个具有菜单的功能演示系统。其中，在主程序中完成函数调用所 需实参值的准备和函数执行结果的显示，并给出适当的操作提示显示。附录 A 提 供了简易菜单的框架。
2
华中科技大学计算机学院数据结构实验报告
演示系统可选择实现线性表的文件形式保存。其中，①需要设计文件数据记 录格式，以高效保存线性表数据逻辑结构(D,{R})的完整信息；②需要设计线性 表文件保存和加载操作合理模式。附录 B 提供了文件存取的方法。演示系统可选择实现多个线性表管理。
1.2系统设计
1.2.1 数据物理结构
线性表的数据物理结构如下：
typedef struct { //顺序表（顺序结构）的定义 ElemType *elem; //定义整型指针，为存储空间基址
int length; //线性表的长度
int listsize; //当前分配的存储容量(以 sizeof(ElemType)为单位) }SqList;
要实现同时对多个线性表管理，只需要定义一个结构数组即可。
1.2.2演示系统
将菜单演示和用户选择写入到while循环中，用OP获取用户的选择，OP初始化为1，以便第一次能进入循环。进入循环后系统首先显示功能菜单，然后用户输入选择0-14，其中1-14分别代表线性表的一个基本运算，在主函数中通过SWITCH语句对应到相应的函数功能，执行完该功能后BREAK跳出SWITCH语句，继续执行while循环，直至用户输入0退出当前演示系统。在第一次进入循环while时首先会询问用户对哪个线性表进行操作，直至退出演示系统之前一直对指定线性表进行操作。演示系统结构如图1-1.
3