基于顺序存储结构的线性表实现1.问题描述

62 阅读 0 评论 41 点赞

我是靠谱客的博主拉长秀发，最近开发中收集的这篇文章主要介绍基于顺序存储结构的线性表实现1.问题描述，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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；如果成功就返回 OK；
- 线性表已存在，则清空该表；（如图 1-5 所示）
- 线性表不存在，则返回操作失败；

图 1-5 线性表清空成功

ListEmpty：判断表是否为空，判断表长是否为 0；为验证该功能，调用后面函数；
- 新建一个表，插入元素，遍历；（如图 1-6 所示）
- 此时表不为空，返回表不为空；（如图 1-7 所示）
- 使用 ClearList 清空表后，返回表为空；（如图 1-8 所示）
- 线性表不存在，则返回操作失败；

图 1-6 线性表内含有元素

图 1-7 线性表判定不为空

图 1-8 线性表为空

ListLength：返回当前表长；
- 使用（4）中第一步建立的表，返回表长为 4；（如图 1-9 所示）
- 线性表不存在，则返回操作失败；

图 1-9 返回线性表长

GetElem：获取元素位置。输入一个位置数，如果该位置数不小于 1 且在表长范围内，则用 e 返回此位置数据元素的值；否则返回 ERROR；
- 使用（4）中第一步建立的表，遍历表；（如图 1-10 所示）
- 输入 2，获取到第二个元素值，返回为 24；（如图 1-11 所示）
- 输入 7，返回获取失败；（如图 1-12 所示）
- 线性表不存在，则返回操作失败；

图 1-10 遍历表

图 1-11 返回线性表第 2 个元素

图 1-12 输入超出范围

LocateElem：定位元素。输入一个元素，遍历全表，如果表内有与之满足 Compare()关系的元素则把元素的位置赋值给 e，返回 e 的值；否则返回 ERROR；
- 使用（4）中第一步建立的表，遍历表；（如图 1-13 所示）
- 输入想查找的元素值，返回为 3；（如图 1-14 所示）
- 输入表内没有的元素值，返回定位失败；（如图 1-15 所示）
- 线性表不存在，则返回操作失败；

图 1-13 遍历表

图 1-14 查找位置成功

图 1-15 查找位置失败

PriorElem：获得前驱。输入一个元素，遍历全表，如果找到该元素且位置不在表头，将该元素的前驱元素赋值给 pre_e，并返回 OK；否则返回 ERROR；
- 使用（4）中第一步建立的表，遍历表；
- 输入表头值，返回失败；（如图 1-16 所示）
- 输入表内存在的元素值，返回前驱；（如图 1-17 所示）
- 输入表内没有的元素值，返回失败；（如图 1-18 所示）
- 线性表不存在，则返回操作失败；

图 1-16 表头无前驱

图 1-17 返回前驱成功

图 1-18 返回前驱失败

NextElem：获得后继。输入一个元素，遍历全表，如果找到该元素且位置不在表尾，将该元素的后继元素赋值给 next_e，并返回 OK；否则返回 ERROR；
- 使用（4）中第一步建立的表，遍历表；
- 输入表尾值，返回失败；（如图 1-19 所示）
- 输入表内存在的元素值，返回后继；（如图 1-20 所示）
- 输入表内没有的元素值，返回失败；（如图 1-21 所示）
- 线性表不存在，则返回操作失败；

图 1-19 最后的元素

图 1-20 返回后继成功

图 1-21 返回后继失败

ListInsert：插入元素。输入插入位置、插入元素的值，如果表内空间不足则开辟新空间；如果该位置数不小于 1 且在表长范围内，则将该位置后的数逐个后移一位次，在空出的位置插入元素，表长加 1 并返回 OK；否则返回 ERROR；
- 使用（4）中第一步建立的表，遍历表；
- 在第 2 位插入元素，并遍历表进行检查；（如图 1-22，1-23 所示）
- 在表长外插入元素，返回插入失败；（如图 1-24 所示）
- 线性表不存在，则返回操作失败；

图 1-22 插入元素

图 1-23 插入后遍历检查

图 1-24 插入元素失败

ListDelete：删除元素。输入删除位置，如果该位置数不小于 1 且在表长范围内，则删除该元素，并将该位置后的数逐个前移一位次；表长减 1 并将删除元素值赋给 e，返回 e 的值；否则返回 ERROR；
- 使用（10）中第二步建立的表，遍历表；（如图 1-25 所示）
- 删除位置 3 的元素，并遍历表；（如图 1-26，1-27 所示）
- 删除位置 9 的元素，返回删除失败；（如图 1-28 所示）
- 线性表不存在，则返回操作失误；