基于顺序存储结构的线性表实现（C++）.zip

# 1.问题描述 通过实验达到： - 加深对线性表的概念、基本运算的理解； - 熟练掌握线性表的逻辑结构与物理结构的关系； - 物理结构采用顺序表,熟练掌握线性表的基本运算的实现。 ## 1.1 具体问题 依据最小完备性和常用性相结合的原则，以函数形式定义了线性表的初始化表、销毁表、清空表、判定空表、求表长和获得元素等 12 种基本运算，具体运算功能定义如下。 - 初始化表：函数名称是 InitList(L)；初始条件是线性表 L 不存在；操作结果是构造一个空的线性表。 - 销毁表：函数名称是 DestroyList(L)；初始条件是线性表 L 已存在；操作结果是销毁线性表 L。 - 清空表：函数名称是 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.2系统设计 ### 1.2.1总体设计 - 使用一个大的 while 语句实现整体功能； - 使用 switch 语句实现菜单栏的操作选择； - 在每个 case 语句先进行对表是否存在的判断； ### 1.2.2算法设计 （1）InitList(*L); 设计思路：给 L.elem 分配存储空间；使表长的值为 0；修改全局变量 isNull 为 false（表存在）； （2）DestroyList(*L); 设计思路：使表长的值为 0；修改 isNull 为 true（表不存在）；释放 L.elem 的空间； （3）ClearList(*L); 设计思路：使表长的值为 0； （4）ListEmpty(L); 设计思路：判断表长是否为 0，是则返回 true，否则返回 false； （5）ListLength(L); 设计思路：返回表长 L.length； （6）GetElem(L,i,*e)； 设计思路：如果线性表为空，则显示获取失败；然后判断输入 i 是否在已有数据的位置范围内；将 L.elem[i-1]赋值给 e； （7）LocateElem(L,e,Compare()); 设计思路：遍历表中数据，返回满足 Compare 函数条件的元素位置； （8）PriorElem(L,cur_e,*pre_e); 设计思路：遍历表中数据，如果输入元素为第一个元素或未找到元素则返回错误；将 L.elem[i-1]赋值给 pre_e； （9）NextElem(L,cur_e,*next_e); 设计思路：遍历表中数据，如果输入元素为最后一个元素或未找到元素则返回错误；将 L.elem[i+1]赋值给 next_e； （10）ListInsert(*L,i,e); 设计思路：如果位置 i 不合理则报错；如果顺序表已满则分配新的存储空间；将插入位置后的元素整体右移，表长增加 1，再插入 e； （11）ListDelete(*L,i,&e); 设计思路：如果位置 i 不合理则报错；将要删除元素赋值给 e，将删除位置后的元素整体左移；表长减少 1，返回 e 的值； （12）ListTraverse(L); 设计思路：利用 for 循环语句遍历顺序表并输出。 ## 1.3 系统实现 ### 1.3.1函数实现 - InitList：为表分配存储空间，若存储分配成功，头地址 L 为存储空间基址,表长为 0，表的存储容量为 100，返回 OK；否则返回 ERROR； - DestroyList：表长置零，表存在变量设置为否，释放存储空间，使头地址指空，成功则返回 OK； - ClearList：清空表，令表长为 0；如果成功就返回 OK；否则返回 ERROR； - ListEmpty：判断表是否为空，即判断表长是否为 0； - ListLength：返回当前表长值； - GetElem：获取元素位置。输入一个位置数，如果该位置数不小于 1 且在表长范围内，则用 e 返回此位置数据元素的值；否则返回 ERROR； - LocateElem：定位元素。输入一个元素，遍历全表，如果表内有与之满足 Compare()关系的元素则把元素的位置赋值给 e，返回 e 的值；否则返回 ERROR； - PriorElem：获得前驱。输入一个元素，遍历全表，如果找到该元素且位置不在表头，将该元素的前驱元素赋值给 pre_e，并返回 OK；否则返回 ERROR； - NextElem：获得后继。输入一个元素，遍历全表，如果找到该元素且位置不在表尾，将该元素的后继元素赋值给 next_e，并返回 OK；否则返回 ERROR； - ListInsert：插入元素。输入插入位置、插入元素的值，如果表内空间不足则开辟新空间；如果该位置数不小于 1 且在表长范围内，则将该位置后的数逐个后移一位次，在空出的位置插入元素，表长加 1 并返回 OK；否则返回 ERROR； - ListDelete：删除元素。输入删除位置，如果该位置数不小于 1 且在表长范围内，则删除该元素，并将该位置后的数逐个前移一位次；表长减 1 并将删除元素值赋给 e，返回 e 的值；否则返回 ERROR； - ListTrabverse：遍历全表。使用 For 循环将表内元素顺序输出； ### 1.3.2 源代码 （源代码详细见附录 A） ## 1.4 系统测试 编程环境：Win10 编译器：Visual Studio 2019 主模块运行如图 1-1 所示：  图 1-1 主模块图 功能操作： - InitList：为表分配存储空间，若存储分配成功，头地址 L 为存储空间基址,表长为 0，表的存储容量为 100，返回 OK；否则返回 ERROR； - 线性表不存在，则创建新表成功；（如图 1-2 所示） - 线性表已存在，则清除之前的表并新建空表；（如图 1-3 所示）  图 1-2 顺序表创建  图 1-3 清除之前的表并创建新表 - DestroyList：表长置零，表存在变量设置为否，释放存储空间，使头地址指空，成功则返回 OK； - 线性表已存在，则销毁该表；（如图 1-4 所示） - 线性表不存在，则返回操作失败；  图 1-4 线性表销毁成功 - ClearList：清空表，令表长为 0；�