第004讲：线性表（顺序存储）
第004讲：线性表（顺序存储）知识点回顾：
0. 本节视频
https://www.bilibili.com/video/BV1MX4y1p7ud?p=4
1. 线性表的概念
线性表（List），是最常用且最简单的一种数据结构，它是具有零个或多个数据元素的有限序列。
如果用数学的语言来定义，通常我们会将线性表记为 $L = (a_{1}, a_{2}, \dots, a_{i-1}, a_{i}, a_{i+1}, \dots, a_{n})$ 这么一个式子。
其中，a_{1} 是唯一的第一个数据元素，也称为表头元素，a_{n} 则是唯一的最后一个元素，又称为表尾元素。
除第一个元素之外的每一个元素，有且仅有一个直接前驱（比如 a_{i} 的直接前驱是 a_{i-1}）。
同样的道理，除最后一个元素之外的每一个元素，也会有一个直接后继（正如 a_{i} 的直接后继是 a_{i+1}）。
2. 有关线性表概念的考点
[*]有限性：线性表是零个或多个数据元素的有限序列。也就是说，一个线性表中的元素数量是有限的。
[*]有序性：线性表中的元素是有序的，每个元素都有一个唯一的前驱和后继（除了第一个元素没有前驱，最后一个元素没有后继）
[*]线性结构：也就是说，线性表的数据元素之间必须是呈现一对一的关系。
3. 抽象数据类型
抽象数据类型（Abstract Data Type，简称 ADT）其实是一种对数据和操作的封装，它只描述了数据和操作的特性，而不涉及具体的实现方法。
简单地说，ADT 就像是一件家用电器的使用手册，它会告诉你这个东西有哪些功能，以及如何操作，但它不需要告诉你这些功能背后到底是如何实现的。
线性表的 ADT：
ADT List {
数据对象：$D = { a_{i} | a_{i} \in ElemSet, i = 1, 2, \dots, n, n ≥ 0}$
数据关系：$R1 = { <a_{i-1}, a_{i} > | a_{i-1}, a_{i} \in D, i = 2, \dots, n}$
基本操作：
InitList(*L)
操作结果：构造一个空的线性表 L
ListEmpty(L)
操作结果：判断线性表是否为空
ListLength(L)
操作结果：返回线性表 L 中数据元素的个数
GetElem(L, i, *e)
操作结果：获取 L 中第 i 个数据元素的值，并通过 e 返回
LocateElem(L, e)
操作结果：在线性表 L 中查找数据元素 e 的位置
ListInsert(*L, i, e)
操作结果：在线性表 L 中第 i 个位置上插入新的数据元素 e
ListDelete(*L, i, *e)
操作结果：删除线性表 L 中第 i 个数据元素，并用 e 返回其值
ClearList(*L)
操作结果：清空线性表 L
DestroyList(*L)
操作结果：销毁线性表 L
} ADT List
数据对象：$D = { a_{i} | a_{i} \in ElemSet, i = 1, 2, \dots, n, n ≥ 0}$
定义数据对象 D 为一个元素集合，其中每个元素 $a_{i}$ 都属于一个叫 ElemSet 的元素集，通常这个元素集会被假定为一个通用集合。
在具体实现时，ElemSet 可以被指定为特定的类型，比如整数、浮点数、字符串、或者更复杂的结构等。
但在 ADT 的定义层面，ElemSet 是抽象的，它可以代表任何可能的元素集合。
然后，i 就是元素的位置，从 1 开始，表示第一个元素，n 是线性表的长度。
数据关系：$R1 = { <a_{i-1}, a_{i} > | a_{i-1}, a_{i} \in D, i = 2, \dots, n}$
定义一个数据关系 R1，它表示线性表中相邻元素之间的顺序关系。
$<a_{i-1}, a_{i}>$ 表示一个有序对（cordered pair），强调了元素之间的顺序，也就是 $a_{i-1}$，必须是在 $a_{i}$ 之前的。
基本操作
基本操作的具体实现，要取决于采用哪种存储结构，存储结构不同，算法的实现肯定也大相径庭。
那么线性表有两种不同的存储方式：顺序存储（也就是我们 C 语言中的数组），和链式存储（包括单链表、双链表、循环链表这些）。
4. 顺序存储
对于顺序存储结构来讲，假设线性表的每个数据元素需要占用 s 个存储单元，那么线性表中第 i+1 个数据元素的存储位置，和第 i 个数据元素的存储位置将满足以下关系：
$LOC(a_{i+1}) = LOC(a_{i}) + s$
因此，线性表的第 i 个数据元素 $a_{i}$ 的存储位置为：
$LOC(a_{i}) = LOC(a_{1}) + (i-1) * s$
不难看出，顺序存储结构可以通过直接寻址访问任何元素，这就意味着访问第 i 个元素的时间复杂度是 O(1)，即常数时间。
5. 顺序存储的基本操作
定义部分：
#define MAX_SIZE 100 // 定义线性表的最大长度
typedef int ElemType; // 定义元素类型
// 定义顺序线性表的结构
typedef struct {
ElemType data; // 用数组存储
int length; // 线性表当前长度
} SqList;
初始化线性表：
// 初始化线性表
void InitList(SqList *L) {
L->length = 0;
}
判断线性表是否为空：
// 判断线性表是否为空
bool ListEmpty(SqList L) {
return L.length == 0;
}
获取线性表的长度：
// 返回线性表的长度
int ListLength(SqList L) {
return L.length;
}
获取线性表中第 i 个数据元素的值：
// 获取线性表中第 i 个数据元素的值
bool GetElem(SqList L, int i, ElemType *e) {
if (L.length == 0 || i < 1 || i > L.length)
return false;
*e = L.data;
return true;
}
在线性表 L 中查找数据元素 e 的位置：
// 在线性表 L 中查找数据元素 e 的位置
int LocateElem(SqList L, ElemType e) {
for (int i = 0; i < L.length; i++) {
if (L.data == e)
return i + 1;
}
return 0;
}
在线性表 L 的第 i 个位置上，插入数据元素 e：
// 在线性表 L 中第 i 个位置上插入新的数据元素 e
bool ListInsert(SqList *L, int i, ElemType e) {
if (i < 1 || i > L->length + 1 || L->length == MAX_SIZE)
return false;
for (int j = L->length; j >= i; j--) {
L->data = L->data;
}
L->data = e;
L->length++;
return true;
}
删除线性表中的元素：
// 删除线性表 L 中第 i 个数据元素，并用 e 返回其值
bool ListDelete(SqList *L, int i, ElemType *e) {
if (L->length == 0 || i < 1 || i > L->length)
return false;
*e = L->data;
for (int j = i; j < L->length; j++) {
L->data = L->data;
}
L->length--;
return true;
}
清空线性表：
// 清空线性表 L
void ClearList(SqList *L) {
L->length = 0;
}
销毁线性表：
// 销毁线性表 L
void DestroyList(SqList *L) {
// 由于这里使用的是静态数组，实际上并不需要进行销毁操作
// 如果使用动态数组，则需要释放内存
// free(L->data);
L->length = 0;
}
6. 顺序存储相关操作的动画演示及源代码
很重要，建议保存 -> https://fishc.com.cn/thread-239016-1-1.html
7. 思维导图
页:
[1]