mirror of
https://github.com/happyflyer/wangdao-data-structure.git
synced 2026-02-02 18:20:02 +08:00
195 lines
7.0 KiB
Markdown
195 lines
7.0 KiB
Markdown
# 线性表
|
||
|
||
## 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
|
||
|
||
实现线性表时，用顺序表还是链表好？
|
||
|
||
**答题思路**：
|
||
|
||
顺序表和链表的逻辑结构都是线性结构，都属于线性表。
|
||
|
||
但是二者的存储结构不同，顺序表采用顺序存储...（特点，带来的优点缺点）：链表采用链式存储...（特点、导致的优缺点）。
|
||
|
||
由于采用不同的存储方式实现，因此基本操作的实现效率也不同。当初始化时...当插入一个数据元素时...；当删除一个数据元素时...；当查找一合数据元素时...
|