华中科技大学数据结构实验报告..docx

课程实验报告课程名称：数据结构实验专业班级：学号：姓名：指导教师：报告日期：2015年11月20日计算机科学与技术学院1基于顺序存储结构实现线性表的基本运算1.1 问题描述叙述实验中线性表的物理结构形式，如何用物理结构表示数据元素间的逻辑关系，可用图的方式直观表示物理结构，如图1-1所示。图1-1 顺序表物理结构示意图实验要完成的顺序表算法：（1）InitaList(L)操作结果：构造一个空的线性表。（2）DestroyList(L)初始条件：线性表L已存在。操作结果：销毁线性表L。（3）ClearList (L)初始条件：线性表L已存在。操作结果：将L重置为空表。（4）ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE,否则返回FALSE。（5）ListLength(L)初始条件：线性表已存在。操作结果：返回L中数据元素的个数。（6）GetElem(L, i,e)初始条件：线性表已存在，1≤i≤ListLength(L)。操作结果：用e返回L中第i个数据元素的值。（7）LocateElem(L, e，compare（）)初始条件：线性表已存在。操作结果：返回L中第1个与e满足关系compare（）关系的数据元素的位序，若这样的数据元素不存在，则返回值为0。（8）PriorElem（L，cur_e，pre_e）初始条件：线性表L已存在。操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。（9）NextElem（L，cur_e，next_e）初始条件：线性表L已存在。操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。（10）ListInsert(L,i,e)初始条件：线性表L已存在且非空，1≤i≤ListLength(L)+1。操作结果：在L的第i个位置之前插入新的数据元素e，L的长度加1（11）ListDelete(L,i,e)初始条件：线性表L已存在且非空，1≤i≤ListLength(L)。操作结果：删除L的第i个数据元素，用e返回其值，L的长度减1.（12）ListTraverse(L，visit（）)初始条件：线性表L已存在。操作结果：依次对L的每个数据元素调用函数visit()。一旦调用失败，则操作失败。（13）ReadList(L)操作结果：读取线性表（14）SaveList(L)操作结果：保存线性表实验目标：构造成具有功能菜单的系统完成线性表基本操作。通过实验达到：（1）加深对线性表的概念、基本运算的理解；（2）熟练掌握线性表的逻辑结构与物理结构的关系；（3）物理结构采用顺序表,熟练掌握线性表的基本运算的实现。1.2 顺序表演示系统设计1.2.1 系统总体设计系统的总体架构：界面上采用简易菜单，通过switch函数进行功能的选择，进入相关功能函数执行相关操作。1.2.2 有关常量和类型定义typedef int ElemType; //数据元素类型定义#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct{ //顺序表（顺序结构）的定义ElemType * elem;int length;int listsize;}SqList; 1.2.3 算法设计（1）InitaList(L)设计：分配存储空间，并将length值设为0，listsize值设为预定义的初始存储容量。复杂度：时间复杂度T(n) = O(1)空间复杂度S(n) = O(1)DestroyList(L)设计：释放内存，并让ele指向NULL，表长及存储容量置为0。复杂度：时间复杂度T(n) = O(1)空间复杂度S(n) = O(1)（3）ClearList (L)设计：将表长设为0。复杂度：时间复杂度T(n) = O(1)空间复杂度S(n) = O(1)（4）ListEmpty(L)设计：读取表长length的值，为0则返回TRUE，否则FALSE。复杂度：时间复杂度T(n) = O(1)空间复杂度S(n) = O(1)（5）ListLength(L)设计：返回L.length的值。复杂度：时间复杂度T(n) = O(1)空间复杂度S(n) = O(1)（6）GetElem(L, i,e)设计：将L.elem[i - 1]的值赋给e，并返回OK复杂度：时间复杂度T(n) = O(1)空间复杂度S(n) = O(1)（7）LocateElem(L, e，compare（）)设计：遍历顺序表，将与给定元素e满足关系compare的元素的位序返回。复杂度：时间复杂度T(n) = O(n)空间复杂度S(n) = O(