# 线性表

## 1. 定义

线性表（Linear List）是具有相同数据类型的 $n$ $(n \geq 0)$ 个数据元素的有序序列。

- **相同数据类型**
- **有序**
- **序列**

其中 $n$ 为**表长**。当 $n=0$ 时线性表是一个**空表**。

$$
L=(\alpha_1,\alpha_2,...,\alpha_i,\alpha_{i+1},...,\alpha_n)
$$

- $\alpha_i$ 是线性表中的 “第 $i$ 个” 元素线性表中的**位序**。
- $\alpha_1$ 是**表头元素**，$\alpha_n$ 是**表尾元素**。
- 出第一个元素外，每个元素有且仅有一个**直接前驱**；除最后一个元素外，每个元素有且仅有一个**直接后继**。

> 注意：位序是从 $1$ 开始的，而数组下标是从 $0$ 开始的。

## 2. 基本操作

- `InitList(&L)`：初始化表。构造一个空的线性表 $L$，分配内存空间。
- `DestroyList(&L)`：销毁操作。销毁线性表，并释放线性表 $L$ 所占用的内存。
- `ListInsert(&L,i,e)`：插入操作。在表 $L$ 中的第 $i$ 个位置插入指定元素 $e$。
- `ListDelete(&L,i,&e)`：插入操作。删除表 $L$ 中的第 $i$ 个位置的元素，并用 $e$ 返回删除元素的值。
- `GetElem(L,i)`：按位查找操作。获取表 $L$ 中的第 $i$ 个位置的元素的值。
- `LocateElem(L,e)`：按值查找操作。在表 $L$ 中查找查找具有给行关键字值的元素。
- `Length(L)`：求表长。返回线性表 $L$ 的长度，即 $L$ 中所有元素的个数。
- `PrintList(L)`：输出操作。按前后顺粗输出线性表 $L$ 的所有元素值。
- `Empty(L)`：判空操作。若 $L$ 为空表，则返回 `true`，否则返回 `false`。

Tips：

- 对数据的操作（记忆思路）：创销、增删改查。
- C 语言函数的定义：<返回值类型> 函数名(<参数 1 类型> 参数 1, <参数 2 类型> 参数 2, ...)。
- 实际开发中，可根据实际需求定义其他的基本操作。
- 函数名和参数的形式、命名都可改变（参考：严蔚敏《数据结构》）。（可读性）
- 什么时候要传入引用 `&`：对参数的修改结果需要 “带回来”。（C++ 语法）

为什么要实现对数据结构的基本操作：

- 团队合作编程，你定义的数据结构要让别人能够很方便的使用（封装）。
- 将常用的操作、运算封装成函数，避免重复工作，降低出错风险。

## 3. 按照存储/物理结构分类

- 顺序表（顺序存储）
- 链表（链式存储）
  - 单链表
  - 双链表
  - 循环链表
  - 静态链表

## 4. [顺序表](sequence/README.md#顺序表)

- 优点：可随机存取，存储密度高。
- 缺点：要求大片连续空间，改变容量不方便。

## 5. [单链表](single-link/README.md#单链表)

- 缺点：无法逆向检索，有时候不太方便。

## 6. [双链表](double-link/README.md#双链表)

### 6.1. [初始化](double-link/README.md#1-初始化)

头结点 `prior`、`next` 都指向 `NULL`。

### 6.2. [插入（后插）](double-link/README.md#2-插入)

- 注意新插入结点、前驱结点、后继结点的指针修改。
- 边界情况：新插入结点在最后一个位置，需特殊处理。

### 6.3. [删除（后删）](double-link/README.md#3-删除)

- 注意删除结点的前驱结点、后继结点的指针修改。
- 边界情况：如果被删除结点是最后一个数据结点，需特殊处理。

### 6.4. [遍历](double-link/README.md#4-遍历)

- 从一个给定结点开始，后向遍历、前向遍历的实现（循环的终止条件）。
- 双链表不可随机存取，按位查找、按值查找都只能用遍历的方式实现。

## 7. [循环链表](circular-link/README.md#循环链表)

- 如何判空
- 如何判断结点 `p` 是否是表尾、表头结点
- 如何在表头、表中、表尾插入、删除一个结点

## 8. [静态链表](static-link/README.md#静态链表)

用数组的方式实现的链表。

- 优点：增、删操作不需要大量移动元素。
- 缺点：不能随机存取，只能从头结点开始一次往后查找，容量固定不可变。

适用场景：

- 不支持指针的低级语言。
- 数据元素数量固定不变的场景（如操作系统的文件分配表 FAT）。

## 9. 顺序表 V.S 链表

三要素：

1. 逻辑结构
2. 物理结构/存储结构
3. 数据的运算/基本操作

|          | 顺序表   | 链表         |
| -------- | -------- | ------------ |
| 随机存取 | **支持** | 不支持       |
| 存储密度 | **高**   | 不高         |
| 存储空间 | 大片连续 | **小且离散** |
| 改变容量 | 麻烦     | **方便**     |

基本操作

- **创**
- 销
- **增**
- **删**
- 改
- **查**

### 9.1. 创建

- 顺序表：需要预分配大片联系空间。若分配空间过小，则之后不方便扩展容量；若分配空间过大，则浪费内存资源。
  - 静态分配，静态数据，容量不可改变。
  - 动态分配，动态数据（`malloc`，`free`），容量可以改变，但需要移动大量元素，时间代价高。
- **链表**：只需要分配一个头结点（也可以不要头结点，只声明一个头指针），之后方便扩展。

### 9.2. 销毁

- 顺序表：修改 `Length=0`。
  - 静态分配，静态数组，系统自动回收空间。
  - 动态分配，动态数组，需要手动 `free`。（属于内存模型的堆区）
- 链表：依次删除各个结点（`free`）。

成对出现：

```cpp
L.data = (ElemType *)malloc(sizeof(ElemType * InitSize));
```

```cpp
free(L.data);
```

### 9.3. 增、删

- 顺序表：插入/删除元素要将后续元素都后移/前移。时间复杂度为 $O(n)$，时间开销主要来自移动元素。
- **链表**：插入/删除元素只需要修改指针即可。时间复杂度为 $O(n)$，时间开销主要来自查找目标元素。

> 若数据元素很大，则移动的时间代价很高；查找元素的时间代价更低。

### 9.4. 查找

- **顺序表**
  - 按位查找：时间复杂度为 $O(1)$。
  - 按值查找：时间复杂度为 $O(n)$，若表内元素有序，则时间复杂度为 $O(log_2n)$。
- 链表：
  - 按位查找：时间复杂度为 $O(n)$。
  - 按值查找：时间复杂度为 $O(n)$。

### 9.5. 总结

|                | 顺序表 | 链表 |
| -------------- | ------ | ---- |
| 弹性（可扩容） | ×      | √    |
| 增、删         | ×      | √    |
| 查             | √      | ×    |

根据场景选择顺序表或链表：

- 表长难于预估、经常要增加/删除元素：链表
- 表长可预估、查询（搜索）操作较多：顺序表

**问题**：

请描述顺序表和链表的 bla bla bla

实现线性表时，用顺序表还是链表好？

**答题思路**：

顺序表和链表的逻辑结构都是线性结构，都属于线性表。

但是二者的存储结构不同，顺序表采用顺序存储...（特点，带来的优点缺点）：链表采用链式存储...（特点、导致的优缺点）。

由于采用不同的存储方式实现，因此基本操作的实现效率也不同。当初始化时...当插入一个数据元素时...；当删除一个数据元素时...；当查找一合数据元素时...