学习思维导图：
# 线性表
## 线性表的基本概念
## 线性表的实现
- 顺序存储
- 链式存储
## 线性表的应用
线性表
本章是后序内容的基础，可能会涉及到在选择题中的概念考察。除此外，需要能够手写代码实现基于数组或链表的相关操作。
1 - 定义和基本操作
线性表可分为顺序表和链表，本节讨论线性表的定义和操作。
线性表定义
线性表是L数据结构中的一种基本结构。它是零个或多个数据元素的有限序列。通常，线性表中的数据元素之间是有序的，它们之间存在着前驱和后继的关系。
$$L = (a_1, a_2, \cdots, a_i, a_{i+1}, \cdots, a_n)$$
特点：
- 个数有限
- 表中元素数据类型都相同，每个元素占有相同大小的存储空间
- 仅讨论元素间的逻辑关系，表中元素有先后顺序
操作
- 初始化 (
InitList): 创建一个空的线性表。 - 插入 (
Insert): 在线性表的指定位置插入一个新的元素。 - 删除 (
Delete): 删除线性表中的指定位置的元素。 - 查找 (
LocateElem): 根据给定的条件查找线性表中的元素。 - 获取元素 (
GetElem): 获取线性表中指定位置的元素。 - 设置元素 (
SetElem): 修改线性表中指定位置的元素的值。 - 长度 (
Length): 返回线性表中的元素数量。 - 判空 (
IsEmpty): 判断线性表是否为空。 - 清空 (
ClearList): 清除线性表中的所有元素。 - 遍历 (
Traverse): 对线性表中的每个元素执行某种操作。
2 - 顺序表示
需熟练掌握顺序表的定义，并且能够用手写代码实现顺序表上的各种操作。
顺序表定义
顺序表（Sequential List） 是一种常见的数据结构，用于存储一组元素，并按照它们在内存中的物理顺序来排列和访问这些元素。顺序表通常由一个数组或列表构成，其中每个元素都占据一个连续的内存位置，并且可以通过索引值来访问。
假设线性表 A 存储的其实位置为LOC(A)，每个元素占用的存储空间的大小为sizeof(Elem)，则 A 所对应的顺序存储结构为：
- 顺序表 优点：
- 随机访问性强：顺序表支持通过索引直接访问元素，访问速度快，时间复杂度为O(1)。
- 空间使用连续：顺序表中的元素存储在连续的内存块中，这有助于提高缓存的局部性，从而提高访问速度。
- 操作简单：无需处理复杂的指针操作。
- 顺序表 缺点：
- 固定大小或调整大小的开销：对于静态数组，大小是固定的，如果预分配的空间不足或过大，会导致内存浪费或数组溢出。动态数组可以重新分配大小，但这会增加时间和空间开销。
- 插入和删除的时间开销：如果要在顺序表的中间插入或删除元素，可能需要移动大量的元素，时间复杂度为O(n)。
操作
#define MAXSIZE 100
typedef struct {
ElementType data[MAXSIZE];
int length;
} SeqList;
void InitList(SeqList *L) {
L->length = 0;
}bool Insert(SeqList *L, int pos, ElementType e) {
if (L->length == MAXSIZE || pos < 1 || pos > L->length + 1) {
return false;
}
for (int i = L->length; i >= pos; i--) {
L->data[i] = L->data[i - 1];
}
L->data[pos - 1] = e;
L->length++;
return true;
}bool Delete(SeqList *L, int pos, ElementType *e) {
if (pos < 1 || pos > L->length) {
return false;
}
*e = L->data[pos - 1];
for (int i = pos; i < L->length; i++) {
L->data[i - 1] = L->data[i];
}
L->length--;
return true;
}int LocateElem(SeqList L, ElementType e) {
for (int i = 0; i < L.length; i++) {
if (L.data[i] == e) {
return i + 1; // 返回元素位置，而不是下标
}
}
return 0; // 未找到返回0
}bool GetElem(SeqList L, int pos, ElementType *e) {
if (pos < 1 || pos > L.length) {
return false;
}
*e = L.data[pos - 1];
return true;
}bool IsEmpty(SeqList L) {
return L.length == 0;
}void ClearList(SeqList *L) {
L->length = 0;
}int Length(SeqList L) {
return L.length;
}3 - 链式表示
需熟练掌握链表的定义，并且能够用手写代码实现链表上的各种操作。
单链表定义
线性表的链式表示通常指的是使用链表来实现线性表。链表是由一系列结点组成的，每个结点都包含一个数据元素和一个指向下一个结点的指针。这种结构允许我们动态地插入和删除元素，而不需要移动其他元素。
与顺序表不同，单链表中每个结点的存储空间都是动态分配的，即使用 c 语言中的 malloc() 函数或者 c++ 中的 new 操作符。
动态分配的空间存储在 进程的堆 中，这些结点占用的存储空间不是连续的，而是离散的，如下图所示：
由于堆的这种动态内存分配特性，所以单链表具备如下优点：
- 链表大小可以动态变化：链表的结点是在需要时动态分配的，因此在使用过程中不需要提前分配固定大小的存储空间，可以随时插入或删除结点。
- 插入和删除方便：只要知道了某个结点的位置，就可以在O(1)的时间复杂度内插入或删除该结点。而顺序表可能需要移动大量的元素。
- 无需预估数据大小：链表可以灵活地增长，而顺序表需要预先定义一个固定大小，或者使用动态数组实现，但重新分配和拷贝的开销可能会很大。
数组（顺序表）与链表不同，由于数组一般是直接作为函数的局部变量使用 int a[N] 定义的，所以数组存储在 进程的栈 中，数组中的相邻元素是连续地存储在栈上，如下图所示：
由于数组在内存中的存储是连续的，所以这有利于程序的空间局部性，当访问一个元素时，相邻的元素也会被加载到 CPU 缓存中，这提高了访问速度。 此外，通过数组的起始地址和一个偏移，我们可以快速地定位到某个数组元素在内存中的地址，实现随机访问。
相比而言，链表则不具备以上特性，链表的缺点如下：
- 随机访问较慢：链表不支持直接通过索引进行随机访问，必须从头部开始逐个遍历结点，直到找到所需的结点，所以访问链表中的元素需要O(n)的时间复杂度。
- 空间开销较大：除了数据元素的存储外，每个结点还需要额外的空间存储一个指针，这增加了链表的存储开销。
操作
链表的操作经常考察，需要熟练掌握，并且能够手写代码。
数据结构定义
可以使用如下结构体来描述单链表中的结点：
// 链表定义
typedef struct Node {
int data;
struct Node *next;
} Node;
其中结构体中包含两个元素，一个是数据，另一个指向下一个结点的指针。 通过这种方式，链表可以在内存中以非连续的方式存储数据，每个结点通过指针连接起来。
在这个例子中，data 的类型是 int，意味着这个链表用于存储整数。但是，你可以根据需要更改 data 的类型，例如 float、char 或者自定义的结构体类型，以存储不同类型的数据。
next 指针的作用是连接链表中的各个结点。它存储了下一个结点的内存地址。通过 next 指针，我们可以从一个结点访问到下一个结点，从而遍历整个链表。
初始化链表
在初始化链表时我们需要为其创建一个头结点，并将头结点的 next 设置为空。
// 初始化
Node* init_linkedlist() {
Node *head = (Node *)malloc(sizeof(Node)); // 创建头结点
if (head == NULL) exit(1); // 内存分配失败
head->next = NULL; // 初始为空链表
return head;
}
头结点的目的在于 简化空链表的处理 和 统一链表的操作：
- 引入头结点后，即使链表为空，头指针也始终指向头结点。
- 通过引入头结点，可以使链表的第一个结点（实际数据结点）的操作与其他结点的操作保持一致。
判空
如果头指针的 next 为空的话，说明单链表为空：
bool is_empty(Node *head) {
return head->next == NULL;
}
插入
对于在链表的一个结点 p 之后插入一个新结点 n 可以抽象下如下操作：
void insert_node_after(Node *p, Node *n) {
Node *q = p->next;
n->next = q;
p->next = n;
}void insert_value_after(Node *n, int value) {
Node *p = malloc(sizeof(Node));
p->value = value;
Node *q = n->next;
n->next = p;
p->next = q;
}当然，如果我们想插入一个实际值 value 的话，你需要通过 Node *p = malloc(sizeof(Node)); p->data = value; 来创建一个新结点，然后再将新创建的结点通过以上函数插入。
在实际考察插入操作的过程中，可能会涉及到三种情况：在链表头部插入、在链表尾部插入 或 在任意位置插入。
void insert_after_head(Node *head, int value) {
// 调用上文定义的插入函数
insert_value_after(head, value);
}void insert_after_tail(Node *head, int value) {
// 找到链表的尾部结点
Node *tail = head;
while (tail->next != NULL) {
tail = tail->next;
}
// 在该位置插入
insert_value_after(tail, value);
}// 在链表的第 pos 个位置插入（位置从 0 开始计数），返回值 bool 表示插入是否成功
bool insert_at_pos(Node *head, int pos, int value) {
Node *p = head;
int i = 0;
// 找到第 pos-1 个结点
while (p && i < pos - 1) {
p = p->next;
i++;
}
// 如果该位置不存在的话，返回 false
if (!p || i > pos - 1) return false;
insert_value_after(p, value);
return true;
}删除
假设指针 p 指向链表中的某个结点，如果我们想删除 p 的下一个结点的话，可以通过如下代码：
void delete_node_after(Node *p) {
Node *q = p->next;
// 需要判断 q 是否存在
if (q) {
// 设置 p 的下一个结点跳过 q
p->next = q->next;
// 释放 q 的空间
free(q);
}
}
如果我们想删除单链表中的第 pos 个结点的话，可以通过如下代码：
// 返回 true 表示删除成功，返回 false 表示删除失败。
bool delete(Node *head, int pos) {
Node *p = head;
int i = 0;
while (p->next && i < pos - 1) { // 找到第 pos-1 个结点
p = p->next;
i++;
}
// 如果 p 是链表中最后一个结点，或者 pos-1 的结点不存在的话，返回 false
if (!(p->next) || i > pos - 1) return false;
// 删除下一个结点
Node *q = p->next;
p->next = q->next;
free(q);
return true;
}
查找
如果要查找链表中是否有结点存储有 value 的值的话，可以通过如下函数：
// 返回 0 表示未找到
int Find(Node *head, int value) {
Node *p = head->next;
int i = 1;
// 遍历链表判断是否有结点值域 value 相同
while (p) {
if (p->data == value) return i;
p = p->next;
i++;
}
return 0;
}
清空
清空链表需要删除链表中的每一个结点，并且将链表设置为空，可以通过如下函数：
void ClearList(Node *head) {
Node *p = head->next, *q;
head->next = NULL;
// 遍历每个结点，并且 free 结点
while (p) {
q = p->next; // 暂存下一个结点
free(p);
p = q;
}
}