# 数据结构 第一章 绪论
> Arietids Learn · 个人课程复习笔记
> 在线阅读：https://learn.arietids.net/courses/data-structures/chapter-01/
## 本章框架
- 本章包含两大部分：**1 数据结构**（1.1 逻辑结构、1.2 存储结构）与 **2 算法**（2.1 时间复杂度、2.2 空间复杂度）。
- 程序 = 数据结构 + 算法。
## 1 数据结构
### 数据与数据元素
- **数据**：外界信息进入计算机后，统称为数据；一般分为数值型（int, float）和非数值型（bool, char, string）。
- **数据元素**：是数据处理的**基本单位**，通常作为整体处理的一个数据个体；不可再分的字段通常称为数据项。
- 示例：定义 `Student` 类（含 name、age、studentID 三个成员）并创建对象后，`student` 可视为一个**数据元素**（数据个体），`student.age` 是该元素的一个**成员字段/数据项**。
代码
```cpp
class Student {
public:
string name; // 姓名
int age; // 年龄
string studentID; // 学号
};
int main() {
Student student{"Alice", 20, "S123456"};
cout << student.age << endl; return 0;
}
```
### 数据结构的定义与研究内容
- **数据结构**：一组具有**特定关系**的**同类**数据元素的**集合**。
- 数据结构的研究内容包括三方面：
- **逻辑结构**：由生活经验总结而来、与计算机无关的数据间关系；
- **存储结构**：逻辑关系的存储（例如：数组存储、链表存储）；
- **基本操作**：对于特定的逻辑关系和存储实现，数据上定义的操作（例如：增加数据、删除数据）。
- 实例（图书馆书架）：每本书可视为一个**数据元素**；书按主题分类摆放（如文学、历史）属于**集合关系**（相同类别的书属于同一个集合），即逻辑结构；**存储结构**可用数组或链表存储书的信息；**基本操作**如查找某本书是否属于某个类别、查看某类别下所有书的名字。
- 代码实例：定义 `Book` 类（数据元素，含 name、publisher 与 print() 方法）；书分历史、文学两个主题，对应两个集合；存储实现用 `std::vector`（数组）存储（`std::vector history; std::vector literature;`）；操作为向集合 `push_back` 添加书籍并打印历史类所有书的名字。
### 1.1 逻辑结构
- **逻辑结构**：指**类型相同**的一组元素和元素间的**关系**。根据关系不同，可分为四种：
| 类型 | 定义 | 资料举例 |
|---|---|---|
| 集合关系 | 不同元素除了同属于一个集合，相互间无其他关系，次序任意 | 水果的集合、动物的集合、颜色的集合；同班级中同学间的关系 |
| 线性关系 | 元素间呈现你先我后的顺序，是一种**一对一**的关系 | 一天里要上的课、排队、一段话里所有的词、大语言模型生成的 token（如 [LLM, is, based, on, next, token, prediction]） |
| 树形关系 | 元素间呈现**一对多**的关系 | 公司团队架构、文件系统、大模型对话上下文；家谱中成员间关系 |
| 图关系 | 元素间呈现**多对多**的关系 | 社交网络、航线网络、贸易网络 |
- 前驱与后继（讲稿备注补充）：
- 线性关系中（如队列）：除了队首，每个元素有一个唯一的**直接前驱**元素（简称前驱）；除了队尾，每个元素有一个唯一的**直接后继**元素（简称后继）。
- 树形关系中：一个人可以有多个孩子，却只能有一个父亲；把父亲看作前驱、孩子看作后继，则树中每个元素可以有**多个后继**，除了根，每个元素有**唯一的前驱**。
- 图关系中：每个元素可以有**多个前驱**，也可以有**多个后继**（如上海、北京、西安三个城市中任何两个城市间都有直飞航线）。
- 四种关系的示意图：(a) 集合关系——若干散落节点同属一框、互不相连；(b) 线性关系——节点连成一条链；(c) 树形关系——节点呈一对多的分层分叉；(d) 图关系——节点间多对多互连成网。
### 定义在数据上的基本操作
| 操作 | 含义 |
|---|---|
| 创建 | 创建一个数据结构 |
| 清除 | 删除一个数据结构 |
| 插入（增） | 向数据结构中增加一个数据元素 |
| 删除（删） | 将数据结构中的一个数据元素删除 |
| 更新（改） | 将数据结构中的一个数据元素的值进行修改 |
| 查找（查） | 访问数据结构中的一个数据元素 |
| 遍历 | 访问数据结构中的每一个数据元素，且使得每个数据元素**仅被访问一次** |
- 备注示例：对队列而言，建队操作、数队列中元素个数、观察队列首部是哪个元素、进队操作、出队操作、逐一访问队列中的每个元素，都是基本操作。
### 1.2 存储结构
#### 什么是存储结构
- 数据要得到处理首先必须进入内存。内存中不仅要存储数据元素的**值**，还要存储元素间的**关系**。
- 任何一种数据结构基本操作的**设计**取决于其**逻辑结构**，但基本操作的**实现**依赖其**存储结构**。
- 元素及其关系在内存中用什么结构存储，原则是**存储方式要有利于基本操作的实现**。
- 关系的两种表示方式：在**数组**中，元素间的关系通常以**存储空间连续性**表示；在**链表**中，元素间的关系通常通过**指针**表示。
- 示意（一队人）：数组将"第一个人、第二个人、第三个人……"放在连续单元中；链表用箭头（指针）从一个人指向下一个人。访问第二个人的信息：数组写作 `people[1].info`，链表写作 `people.next.next.info`。
- 课堂类比（备注）：试卷题——数组；密室逃脱游戏——链表。
#### 顺序存储
- **顺序存储**：用一块**连续的空间**存储数据，**不直接表示**数据之间的关系，而是借助空间地址上的**有序性**存储元素间的关系（例如，用存储地址上的先后顺序表示数据之间的先后顺序）。
- 高级语言中，**数组**是地址连续的空间，有助于实现顺序结构。
- 数组还可表达更复杂的关系：用二维数组表示图中节点的相连关系——示例图中节点 0–1、1–2 相连，对应 `graph[0][1]=1; graph[1][0]=1; graph[1][2]=1; graph[2][1]=1;`，整体构成 0/1 矩阵（第 0 行 0 1 0、第 1 行 1 0 1、第 2 行 0 1 0）。
- 备注延伸：完全二叉树也可以通过数组方式表示。
- **数组的存储结构**：设首地址为 a、每个数组元素占 k 个存储单元（如 int16 对应 k=16），则序号 0、1、2、…、5 的元素地址依次为 a、a+k、a+2k、a+3k、a+4k、a+5k（图中元素 a0–a3 依次存放在前四个位置），即序号为 i 的元素地址为 a+i·k。
- 数组中不同元素所占内存空间是**连续**的。
- 优点：可以直接通过序号访问（a[0], a[1] 等）。
- 缺点：① 需要预先声明数组占据的空间大小；② 需要连续的内存空间；③ 对于插入和删除的效率低。
#### 链式存储
- **链式存储**：**不要求**不同数据存储的内存空间连续，元素间的关系**显式地存储**在对应的空间中（例如，用链表中的指针表示元素间的关系）。典型代表：链表。
- **链表的存储结构**：表头指针指向第一个结点；每个结点含数据（a1、a2、a3）和**指针域**，指针域指向下一个结点，最后一个结点的指针域为 NULL。
- 链表中不同元素所占内存空间是**不连续**的。
- 优点：① 可以动态地增加或缩短链表的长度；② 插入删除操作高效；③ 不同节点可以存储在内存的不同位置上，存储利用率更高。
- 缺点：① 无法通过序号直接访问，为了访问一个元素，需要从头遍历；② 为了存储一个元素，还需要对应消耗一个指针域的空间。
- 备注示例（队列的两种存储）：用数组存队列时，可让队列中元素的先后顺序和数组下标顺序一致（第一个元素存下标 0、第二个存下标 1，以此类推）；用链式结构存队列时，先声明一个结构数据类型，每个变量称作一个**结点**，结点含一个存储元素值的字段和一个**指针字段**，指针字段存储队列中下一个元素结点的地址（指向下一个结点）。
#### 常见存储方式总结与思考
- 逻辑关系：集合结构、线性结构、树型结构、图型结构；操作：创建、清除、增删改查、遍历、其它；存储方式：顺序存储、链式存储、其它。
- 思考题：如果一个数据结构在使用时的**随机查询操作极多、插入删除操作极少**，应该选择数组还是链表？——依据"数组可直接通过序号访问、链表随机访问需从头遍历"，应选**数组**。
- 后续课程的基本逻辑（以树型结构为例）：① 树型结构的**逻辑关系**定义；② 树型结构上可以进行的**操作类型**；③ 树型结构用数组和链表分别**如何存储、如何实现各种操作**。
## 2 算法
### 算法的定义与五个特性
- **算法**：是解决一个具体问题的**方法和步骤**。
- 算法具有 **5 个特性**：
| 特性 | 含义 | 资料中的反例/说明 |
|---|---|---|
| 确定性 | 每一步有**确定的含义**，没有二义性 | "If a 比 b 大很多, then …"、"If a 是一张猫的图像, then …" |
| 有穷性 | 每一步在**有限的时间内完成**，整个算法必须在**有限步**之后完成 | `While True: Print("Hello World");` |
| 可行性 | 每一步都是经过**有限次基本操作**可以完成，自身没有复杂的算法 | `a=power(2, +∞);` |
| 有输入 | 一个算法可以有**零个或者若干个输入**作为解决问题的已知条件 | — |
| 有输出 | 通常应有**一个或若干个可观察输出**（返回值、打印或状态改变等）作为算法运行结果 | — |
- 备注：无穷算法是"一种最简单的病毒"；思考——什么算法可以没有输出？有意义吗？
### 算法的基本要求
| 要求 | 含义 |
|---|---|
| 正确性 | 准确反映并能满足具体问题的要求（答案正确） |
| 可读性 | 可供人们阅读的容易程度（详细的注释，易维护） |
| 健壮性 | 对各种不同的输入都要有相应的反应（注意边界条件，特殊值） |
| 时间效率 | 算法的执行时间（OJ 系统中的 Time Limit Exceed） |
| 空间效率 | 算法执行期间所需要最大内存空间（OJ 中的 Memory Limit Exceed） |
- 健壮性的形象说明——"测试工程师走进酒吧"系列笑话与其对应的测试含义（备注给出对应关系）：
| 笑话情形 | 测试类型 | 测试目的 |
|---|---|---|
| 要了一杯啤酒 | 正常功能测试 | 验证系统能处理标准有效输入 |
| 要了一杯咖啡 | 边界值测试 | 测试系统对菜单外项目的处理 |
| 要了 0.7 杯啤酒 | 无效输入测试 | 检查系统对小数数量（非整数）的容错 |
| 要了 -1 杯啤酒 | 异常输入测试 | 验证系统对负数的处理（应报错或拒绝） |
| 要了 2^32 杯啤酒 | 压力/溢出测试 | 测试极大数值是否导致整数溢出或资源耗尽 |
| 要了一杯洗脚水 | 荒谬输入测试 | 检查系统对完全无意义物品的响应 |
| 要了一杯蜥蜴 | 无效数据类型测试 | 测试非饮品输入 |
| 要了一份乱码字符 | 安全测试（注入攻击） | 检测系统是否容易受到攻击或病毒注入 |
| 什么也没要 | 空输入测试 | 验证系统对空订单的处理 |
| 从非常规路径进出 | 安全性/路径测试 | 模拟非标准操作流程，检测安全漏洞 |
- **时间效率**（算法的执行时间）——影响运行时间的主要因素：① **问题的规模**（数据量的大小，如 100 条数据 vs 1,000,000 条数据）；② **程序采用的算法的优劣**；③ 编译器生成的目标代码的质量；④ 计算机系统的性能（AI 研究中的显卡）。其中前两项为幻灯片重点标示。
### 算法效率引例：二分查找 vs 从前向后查找
- 问题：对一个**有序**序列（A–Z 共 26 个字母，下标 0–25），查找字母 P 的位置。
- **二分查找**过程：
- 第一步：从中间的字母开始找，(0+25)/2=12.5，取整得 12，对应 M；M 在 P 的前面，所以 P 仅会在 [13,25] 出现。
- 第二步：(13+25)/2=19，对应 T；T 在 P 的后面，所以 P 仅会在 [13,18] 出现。
- 第三步：(13+18)/2=15.5，取整得到 15，对应 P，成功找到。
- 仅需要三次操作就可以找到，**最多需要 $\log_2(N)+1$ 次**。
- **从前向后查找**：从数组中第一个元素开始比较，A, B, C, D, E…, O, P，一共访问 16 次；最差情况下，需要访问 N=26 次。
- 对比结论：同样的查找操作，二分法最多需要 $\log_2 N+1$ 次访问，从前向后查找最多需要 N 次访问。当 N=10000 时，后者访问的次数是前者的 **1000 倍还多**。
- 不同时间函数的增长对比（以计算机 1 秒处理 1000 条指令估算）：
| 时间函数 | N=20 | N=50 | N=100 | N=500 |
|---|---|---|---|---|
| $N$ | 0.02秒 | 0.05秒 | 0.1秒 | 0.5秒 |
| $N\log(N)$ | 0.09秒 | 0.3秒 | 0.6秒 | 4.5秒 |
| $N^2$ | 0.4秒 | 2.5秒 | 10秒 | 250秒 |
| $N^3$ | 8秒 | 2分 | 17分 | 35小时 |
| $2^N$ | 约17.5分钟 | 约$3.6\times 10^4$年 | 约$4.0\times 10^{19}$年 | 约$1.0\times 10^{140}$年 |
### 2.1 时间复杂度
#### 时间频度
- 用算法中**基本语句的执行次数**来度量运行时间：基本语句执行次数越多，时间花费越多，执行次数称**时间频度**；时间频度和处理的**数据规模 n** 有关，可表示为 n 的函数 **T(n)**。
- 例：
代码
```cpp
s = 0;
for (i=0; i
`s=0` 执行 1 次，`i=0` 执行 1 次，`i
- 度量原则：
- **循环语句**：需要计算**实际运行**的次数，不是看语句书写的次数。
- **分支语句**：按照**执行语句多**的那个分支计算。
- 分支例：
代码
```cpp
if (n>0) {
for (i=0; i
n>0 时为 3n+3 次；n<=0 时为 2 次；时间频度取 **3n+3**。
#### 渐进表示法：大 O 表示法
- **定义**：如果存在常数 C 和 $n_0$，满足当 $n > n_0$ 时，$T(n) \le C \cdot F(n)$，则 $T(n)$ 可以表示为 **$O(F(n))$**，称为算法的**时间复杂度**。
- 例：$T(n)=3n+3 \le C\cdot n$，所以可以表示为 $O(n)$；$T(n)=\log_2 n + 1 \le C\cdot \log_2 n$，所以可以表示为 $O(\log_2 n)$，也可以近似写为 $O(\log n)$。
- 对数底数可略去的依据是换底公式（备注提示）。
- **时间复杂度由时间频度函数中的最高次项决定，不带系数**。
#### 时间复杂度的计算
- 两条简化规则：① 执行次数和数据规模 n 的变化没有关系的语句，可不计入；② 当内外循环次数**没有关联**时，只需要看**循环体**的执行次数即可。
- 例（内外循环无关联）：
代码
```cpp
s=0;
for (i=0; i
只需计算循环体执行次数 $\sum_{i=0}^{n-1}\sum_{j=0}^{n-1} 1 = \sum_{i=0}^{n-1} n = n^2$，时间复杂性为 **$O(n^2)$**。
- 例（内外循环次数相互关联）：
代码
```cpp
s=0;
for (i=0; i
循环体执行次数：$\sum_{i=0}^{n-1}\sum_{j=0}^{i-1} 1 = \sum_{i=0}^{n-1} i = n(n-1)/2$，故时间复杂度 **$O(n^2)$**。
- **计算方法总结**：
1. 找算法中和数据规模 n 有关的**循环语句**，计算**循环体的执行次数**获得时间频度函数。
2. 观察时间频度函数中关于 n 的**最高次项**，**去掉其系数**，即是时间复杂度的大 O 表示。
- 特殊地：如果算法中无执行次数和数据规模 n 相关的语句，即时间频度函数是一个**常量**，则时间复杂度为 **O(1)**。
#### 常见算法的时间复杂度
- 常见量阶（按时间效率**由高到低**排列）：常量阶 $O(1)$、对数阶 $O(\log_2 n)$、线性阶 $O(n)$、线性对数阶 $O(n\log_2 n)$、平方阶 $O(n^2)$、立方阶 $O(n^3)$、幂阶 $O(2^n)$、阶乘阶 $O(n!)$、N 幂阶 $O(n^N)$。注意：不仅限于这几种。
- 到达**立方阶**之后，一旦数据规模大些，时间就已经是不能忍受了，是一个**顽性算法**；从**常量级到平方级**，通常称**易性算法**。
- 增长曲线图：横轴为规模、纵轴为耗时，O(1) 与 O(log n) 几乎水平，O(n)、O(n log n) 平缓上升，O(x²)、O(x³)、O(2ˣ)、O(n!) 依次陡峭爆炸式上升。
#### 计算时间复杂度的简化工具：两个定理
- **求和定理**：假定 $T_1(n)$、$T_2(n)$ 是程序 P1、P2 的运行时间，并且 $T_1(n)$ 是 $O(f(n))$ 的，而 $T_2(n)$ 是 $O(g(n))$ 的。那么，先运行 P1、再运行 P2 的总的运行时间是：$T_1(n)+T_2(n)=O(\mathrm{MAX}(f(n), g(n)))$。
- 例：第一段 `for (i=0; i
- **求积定理**：如果 $T_1(n)$ 和 $T_2(n)$ 分别是 $O(f(n))$ 和 $O(g(n))$ 的，那么 $T_1(n)\times T_2(n)$ 是 $O(f(n)\times g(n))$ 的。
- 例：双重 n 次循环按照求积定理为 $O(n\times n)=O(n^2)$。
- 当内外循环次数**相互关联**时，也可利用求积公式简化：外层 `for (i=0; i
#### 量阶与三种情况
- $O(f(n))$ 并不描述运行时间的**精确值**，只给出一个**数量级**。它表示：当问题规模很大时，算法运行时间的增长**受限于哪一个数量级的函数**，简称为**量阶**。
- 通常考虑三个方面：**最好、最坏和平均情况**的时间复杂度；一般用**最坏情况**作为算法的时间复杂度。
- 备注类比：考虑最坏情况，就像上课需要照顾没有任何基础的同学。
### 2.2 空间复杂度
- 算法的**空间消耗**包括三个方面：① 实现算法的程序本身需要占据存储空间；② 待处理的数据需要在内存中存储，占据一定的空间；③ 处理数据的过程中需要一些**额外的辅助空间**。通常一和二是不可避免的，在设计算法时主要关注**额外的辅助空间**。
- **渐进空间复杂度**（也称**空间复杂度**）：是当数据规模 n 趋于无穷时**使用辅助空间的量阶**，计为 $S(n)=O(f(n))$。
- 示例（数据序列逆置）——方法一，借助辅助数组：
代码
```cpp
int a[10]={1,6,2,5,8,9,5,4,3,12},b[10];
int i;
for (i=0; i<10; i++)
b[i] = a[10-i-1];
for (i=0; i<10; i++)
a[i] = b[i];
```
为完成 n=10 个元素的逆置，使用了具有 n 个元素空间的数组 b 作为辅助空间，**空间复杂度为 O(n)**。
- 方法二，原地交换：
代码
```cpp
int a[10]={1,6,2,5,8,9,5,4,3,12};
int t, i;
for (i=0; i<5; i++)
{ t=a[i];
a[i]=a[10-i-1];
a[10-i-1]=t;
}
```
使用的辅助空间为一个临时变量 t，辅助空间数量和元素个数没有关系，**故其空间复杂度为 O(1)**。
- 延伸：无需临时变量的两数交换的四种方案：
代码
```cpp
// 方案一（加减） // 方案二（乘除）
a = a + b; a = a * b;
b = a - b; b = a / b;
a = a - b; a = a / b;
// 方案三（异或）
a = a ^ b;
b = a ^ b;
a = a ^ b;
// 不建议写成链式 a ^= b ^= a ^= b;
```
代码
```python
# 方案四（Python）
a, b = b, a
```
- 注意：加减和乘除方案可能溢出；乘除方案还要求参与除法时除数非 0；异或方案只适用于整数，且链式 `a ^= b ^= a ^= b` 在旧 C/C++ 标准中有求值顺序风险，复习时以三行写法为准。
- 说明：在**内存足够大**的情况下，算法更加注重**时间效率**，忽略空间复杂度的计算；或者仅当算法的**时间复杂度一致**的情况下，才可能比较空间复杂度的优劣。
#### 延伸：时间与空间的相互转换
- **用空间换时间——哈希算法**：把任意长度的输入通过**散列算法**变换成键值（例如位置编号），该输出就是**散列值**。为了降低"**哈希冲突**"（两个数据算出同一个位置），哈希表必须保持**大量空位**（浪费空间）来保证运转效率。
- 示意图：Keys（152、104、212）经哈希函数 $h(x)=x \bmod 10$ 映射到哈希表位置；152 与 212 求模后落在同一位置，图中标红为 Collision（冲突）。
- 备注：哈希表常用于集合/字典类数据的快速查找；不应理解为只能用于“集合关系”。
- **用时间换空间——操作系统的虚拟内存**：操作系统会把硬盘划出一部分，假装它是内存来用，把当前不常用的数据悄悄移到硬盘上，腾出真正的内存给急需的程序。硬盘的读写速度比真实的内存**慢成百上千倍**，当程序突然需要用到被放进硬盘的数据时，系统必须花费大量时间去硬盘里把它"搬"回内存——这就是为什么**内存不够时电脑会变得非常卡顿**：系统在用卡顿（时间）来弥补内存不足（空间）。
- 示意图：Physical RAM（Fast, Limited Space）与 Hard Disk / Swap Space（Slow, Huge Space）之间通过 Swap Out（Free up space）与 Swap In（Time Penalty）交换页面。
## 本章小结
- 数据元素及元素间关系称作**数据结构**。
- 数据结构研究具有某种**制约关系**的一组元素及元素间关系在内存中**如何存储**、在各种存储方式下**关系操作如何实现**，以及各种数据结构的**典型应用**。
- 具体研究分**逻辑结构及基本操作、物理结构、基本操作实现、典型应用**四个方面。
- 在分析**逻辑结构和基本操作**时，要**完全脱离计算机**而仅仅依赖现实生活中的元素特征来分析元素、元素关系及基本操作，最后给出用**伪代码描述的抽象数据类型**。
- 在**物理结构**分析阶段，讨论元素及元素关系在内存中如何存储。存储可以分**顺序存储**和**链式存储**：顺序存储使用一块连续的空间存储元素和元素之间的关系；链式存储使用各自独立的空间存储每个元素，并在每个独立的空间中**附加字段**以存储元素之间关系。
- 在**基本操作实现**分析阶段，研究在各种存储方式下基本操作的实现方法和步骤即**算法**。对于算法提出了**时间复杂度**和**空间复杂度**的概念及计算方法，并以此为依据，对不同算法进行**性能比较**。
- 在**典型应用**阶段，给出所研究的数据结构最适合的实际应用问题。