《某科技大学数据结构实验报告》由会员分享，可在线阅读，更多相关《某科技大学数据结构实验报告（104页珍藏版）》请在金锄头文库上搜索。
1、课 程 实 验 报 告课程名称： 数据结构实验 专业班级： 信息安全201502 学 号： 姓 名： 指导教师： 报告日期： 2016年 10月 28 日 计算机科学与技术学院目 录黑体小2号加粗居中.间距前后0.5行1基于顺序存储结构的线性表实现11.1问题描述11.2系统设计11.3系统实现11.4实验小结12 基于二叉链表的二叉树实现22.1问题描述22.2系统设计22.3系统实现22.4实验小结2指导教师评定意见3附录A 基于顺序存储结构线性表实现的源程序4附录B 基于二叉链表二叉树实现的源程序5章为宋体小4号加粗，其余宋体小4号，行间距1.5倍,段落前后0行1 基于顺序存储结构的线性
2、表实现黑体小2加粗，居中，间距前后0.5行1.1 问题描述黑体4号加粗，间距前后0.5行采用顺序表的物理结构，构造一个具有菜单的功能演示系统。其中，在主程序中完成函数调用所需实参值的准备和函数执行结果的显示。定义了线性表的初始化表、销毁表、清空表、判定空表、求表长和获得元素等基本运算对应的函数，并给出适当的操作提示显示，可选择以文件的形式进行存储和加载，即将生成的线性表存入到相应的文件中，也可以从文件中获取线性表进行操作。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 依据最小完备性和常用性相结合的原则，以函数形式定义了包括线性表的初始化表、加载表、保存表、销毁表、清空表、判定空表、求表长、获得元素、查找元素、获得前驱、获得后继、插入元素、删除元素、遍历表 14 个基本运算，要求分别定义函数来实现上述功能，具体功能运算如下：初始化表：函数名
4、称是InitaList(L)；初始条件是线性表L不存在已存在；操作结果是构造一个空的线性表。销毁表：函数名称是DestroyList(L)；初始条件是线性表L已存在；操作结果是销毁线性表L。清空表：函数名称是ClearList(L)；初始条件是线性表L已存在；操作结果是将L重置为空表。判定空表：函数名称是ListEmpty(L)；初始条件是线性表L已存在；操作结果是若L为空表则返回TRUE,否则返回FALSE。求表长：函数名称是ListLength(L)；初始条件是线性表已存在；操作结果是返回L中数据元素的个数。获得元素：函数名称是GetElem(L,i,e)；初始条件是线性表已存在，1iLi
5、stLength(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
6、是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。插入元素：函数名称是ListInsert(L,i,e)；初始条件是线性表L已存在且非空，1iListLength(L)+1；操作结果是在L的第i个位置之前插入新的数据元素e。删除元素：函数名称是ListDelete(L,i,e)；初始条件是线性表L已存在且非空，1iListLength(L)；操作结果：删除L的第i个数据元素，用e返回其值。遍历表：函数名称是ListTraverse(L,visit()，初始条件是线性表L已存在；操作结果是依次对L的每个数据元素调用函数visit()。1.1.3 演示
7、系统与数据文件要求构造一个具有菜单的功能演示系统。其中，在主程序中完成函数调用所需实参值的准备和函数执行结果的显示，并给出适当的操作提示显示。附录 A 提供了简易菜单的框架。 演示系统可选择实现线性表的文件形式保存。其中，需要设计文件数据记录格式，以高效保存线性表数据逻辑结构(D,R)的完整信息；需要设计线性表文件保存和加载操作合理模式。附录 B 提供了文件存取的方法。 演示系统可选择实现多个线性表管理。1.2 系统设计黑体4号加粗，间距前后0.5行1.2.1 数据物理结构线性表的数据物理结构如下：typedef struct /顺序表（顺序结构）的定义 ElemType *elem; /定义
8、整型指针，为存储空间基址 int length; /线性表的长度 int listsize; /当前分配的存储容量(以 sizeof(ElemType)为单位) SqList;要实现同时对多个线性表管理，只需要定义一个结构数组即可。1.2.2 演示系统将菜单演示和用户选择写入到while循环中，用OP获取用户的选择，OP初始化为1，以便第一次能进入循环。进入循环后系统首先显示功能菜单，然后用户输入选择0-14，其中1-14分别代表线性表的一个基本运算，在主函数过SWITCH语句对应到相应的函数功能，执行完该功能后BREAK跳出SWITCH语句，继续执行while循环，直至用户输入0退出当前演示
9、系统。在第一次进入循环while时首先会询问用户对哪个线性表进行操作，直至退出演示系统之前一直对指定线性表进行操作。演示系统结构如图1-1.1.2.3 运算算法思想与设计线性表运算算法思想与设计如下：1. 初始化线性表思想：将线性表初始化过程写成函数，其中传入函数的参数是主函数中定义的结构型变量L的引用，在函数中，首先使用malloc函数分配LISTSIZE大小的连续存空间，并将首地址返回赋值给L.elem，由于线性表的长度为0，将L.length初始化为0，即完成了线性表的初始化。经分析，算法的时间复杂度为O(1)。2. 销毁线性表思想：将销毁线性表的过程写成函数，其中传入函数是主函数中定义
10、的结构性变量L。在函数中，首先使用free函数释放掉以L.elem为首地址的连续存空间，再将L.length,L.listsize重新赋值为0。经分析，该算法的时间复杂度为O(1)。3. 清空线性表的思想：将清空表的过程写成函数，其中将主函数中定义的结构性变量L的引用作为函数参数，在函数中，由于清空操作并不释放存空间，故只需将线性表的长度置为0即可。经分许，该算法的时间复杂度为O(1)。4. 求线性表表长的思想：将求表长过程写成函数，其中主函数中定义的结构性变量L的引用作为函数的参数，在函数中，直接返回L.length即为所求线性表的表长。经分析，该算法的时间复杂度为O（1）。5. 获得元素的
11、算法思想：将获得线性表元素写成函数，其中函数的参数是结构型变量L以及数据元素的序号i，由于采取的是线性存储结构，故直接通过访问数组的方式即L.elemi-1来获取元素，当然，在这之前需要判断合法性。经分析，该算法的时间复杂度为O（1）。6. 查找元素的算法思想：将查找线性表特定值的数据元素写成函数，其中函数的参数是主函数中定义的结构类型变量L以及查找的数据元素的值，通过循环对线性表中的每一个元素与给定值比较看是否相等，如果相等就返回该元素的次序。经分析，该算法的时间复杂度为O（n）。查找算法的流程图如图1-2所示。图1-2 线性表查找算法流程图7. 获得前驱算法思想：将获得前驱过程写成函数，函
12、数的参数是结构体类型变量以及特定数据元素的值，接受前驱的变量作为另一个参数，首先调用获得元素的函数判断该线性表中特定数据元素的位序，首先判断不为1，否则的话返回FALSE，然后直接返回其前一个元素即L.elemj-2。经分析，该算法的时间复杂度为O（n）。8. 获得后继算法思想：将获得后继写成函数，函数的参数是结构体类型变量以及特定数据元素的值。首先判断是否为最后一个元素，如果不是则直接返回其后一个元素，否则的话返回FALSE，同样该算法需要调用获得元素的函数来确定该特定元素在线性表中的次序。经分析，该算法的时间复杂度为O（n）。9. 插入元素算法思想：将插入函数写成函数，函数的参数是结构型变
13、量以及插入元素的值大小以及插入位置。在函数中，首先判断插入位置的合法性，即是否在线性表中合适的位置，其次还要判断当前存储空间是否已满，如果满了的话要malloc函数重新分配空间，插入元素时从该位置起到最后一个元素从后开始以此往后移一个单元。经分析，该算法的时间复杂度为O（n）。该算法的程序流程图如图1-3所示。图1-3 线性表中插入元素算法流程图10. 删除元素算法思想：将删除线性表中元素写成函数，函数的参数是结构类型变量，首先判断位序的合法性，在之后直接将删除元素位置后一个元素直到最后一个元素以此从前往后向前移动一个单元。经分析，该算法的时间复杂度为O（n）。11. 遍历线性表算法思想：将遍
14、历线性表写成一个函数，函数的参数是结构类型变量，直接用一个循环来对线性表中的每一个元素进行操作。经分析，该算法的时间复杂度为O(n)。图内容：字体大小参考宋体5号，居中1.3 系统实现黑体4号加粗，间距前后0.5行1.3.1 编程环境、运行环境、项目工程描述本次实验采用Microsoft Visual Studio 2015编程软件编写，并用VS2015进行编译运行，项目名称是linear datastructer。1.3.2 头文件及预定义常量说明1.头文件#include #include #include 2.预定义常量#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASTABLE -1#define OVERFLOW -2#define LIST_INIT_SIZE 100#define LISTINCREMENT 103.类型表达式typedef int status;typedef int ElemType;1.3.3 系统演示操作1.系统一开始会显示菜单提示用户输入选择对1-99号线性表哪一个进行操作。如图1-4所示。图1-4 系统演示12.选择对线性表1进行操作，进入菜单演示界面，如
