# 第一章：概论学习笔记

本章建立课程的基本概念与分析语言：从现实问题到逻辑、存储结构，从 ADT 到算法与复杂度分析。参考《第一章 概论》课件第 1–80 页，页码用原课件页序；完整讲解见[第一章：概论](/数据结构/概论/)。本笔记可独立复习，并标注约定、前提与易错点。

## 1. 知识地图

来源：课件第 1–9 页。

本章主线是：从现实对象抽象出数据、数据元素、数据项与数据对象；加入元素间关系，得到数据结构 `(D, S)` 及其逻辑结构与存储结构；再把操作纳入，用数据类型与 ADT `(D, S, P)` 封装使用接口；用算法描述求解步骤，并用五特性、设计目标和 `T(n)`、`S(n)` 评价。

Wirth 的“算法 + 数据结构 = 程序”点明二者不可分离：结构决定能支持哪些操作，算法决定操作以多大代价完成。

## 2. 概念阶梯：数据、数据元素、数据项、数据对象

来源：课件第 10–18 页。

| 概念     | 定义                                 | 例子                             |
| -------- | ------------------------------------ | -------------------------------- |
| 数据     | 能输入计算机并被程序处理的符号总称   | 数值、文字、图像、声音           |
| 数据元素 | 数据的基本单位，通常作为一个整体处理 | 一条学生记录、一张牌、一个整数   |
| 数据项   | 数据元素中不可再分的最小单位         | 学号、姓名、课程名、成绩         |
| 数据对象 | 性质相同的数据元素集合               | 整数对象、字符对象、全体学生记录 |

数据在计算机内都表示为二进制串。包含关系是：数据包含数据对象，数据对象由数据元素组成，数据元素由数据项组成。以全校学生成绩表为例，整张表是数据对象，一行是数据元素，行中的学号、课程、成绩是数据项。易错点：数据元素是整体处理的基本单位，数据项是元素内部的最小单位。

## 3. 数据结构的定义与两个描述层次

来源：课件第 19–21 页。

数据结构是数据元素集合 `D` 与元素间关系集合 `S` 组成的二元组 `(D, S)`；逻辑结构与存储结构是它的两个描述层次。只看元素、不看关系，不足以称为数据结构。若再把操作集合 `P` 纳入定义，得到抽象数据类型 `(D, S, P)`——操作属于 ADT，不是数据结构二元组的第三项。同一批学生，按学号排成线性表、按班级组成树、按朋友关系组成图，是三种不同的数据结构。

数据结构有两个描述层次：

- **逻辑结构**：面向问题，描述元素之间的抽象关系，与计算机无关。例如把路口抽象为顶点、道路抽象为边。
- **存储结构**：面向机器，描述数据及其关系在内存中的表示，元素本身与元素间关系都要存储。

先确定逻辑结构，再选择存储结构并实现操作。同一逻辑结构可有多种存储实现，效率不同；存储结构的选择又会影响操作算法。

## 4. 四类逻辑结构及判定

来源：课件第 22–25 页。

| 逻辑结构 | 元素间关系                                         | 典型例子                 | 后续章节  |
| -------- | -------------------------------------------------- | ------------------------ | --------- |
| 集合     | 元素同属一个集合，别无其他关系                     | 同班学生、一副扑克牌     | 仅概念    |
| 线性结构 | 一对一：除首尾外，每个元素有唯一前驱和唯一后继     | 排队队伍、列车车厢、数组 | 第 2–4 章 |
| 树形结构 | 一对多：每个元素至多一个前驱，可有多个后继，呈层次 | 家谱、文件目录           | 第 5 章   |
| 图状结构 | 多对多：元素可有多个前驱和多个后继                 | 朋友圈、城市交通网       | 第 6 章   |

判定时依次追问：任意两个元素之间是否有关系？没有，是集合；每个元素至多一个直接前驱和一个直接后继，是线性；至多一个前驱但可有多个后继，是树；前驱或后继可多于一个，是图。

## 5. 顺序存储与链式存储

来源：课件第 26–30 页。

| 比较项         | 顺序存储                       | 链式存储                     |
| -------------- | ------------------------------ | ---------------------------- |
| 逻辑关系的表示 | 物理位置相邻隐含逻辑相邻       | 结点中的指针显式指出后继     |
| 存储单元       | 连续分配，需预先确定容量       | 结点可分散，按需分配         |
| 随机访问       | 可按下标直接计算地址，`O(1)`   | 必须从头沿指针查找，`O(n)`   |
| 插入删除       | 平均需移动约一半元素，`O(n)`   | 已知前驱时只需改指针，`O(1)` |
| 空间开销       | 无指针开销，存储密度高         | 每个结点额外存指针，密度较低 |
| 适用场景       | 长度稳定、频繁查找、按下标访问 | 频繁插删、长度变化大、树与图 |

顺序存储的地址公式为“基址 + 下标 × 元素长度”，随机访问 `O(1)` 的前提是元素等长、下标可直接计算。链式存储插删 `O(1)` 的前提是已定位前驱；若还要按序号找前驱，定位仍是 `O(n)`。

选择原则：查找多、规模稳定，优先顺序存储；插删多、规模变化大，优先链式存储。也可组合两种思想，如索引表、散列表、块状链表。

## 6. 数据类型与抽象数据类型

来源：课件第 31–35 页。

**数据类型**是同类数据值的集合以及定义在其上的一组操作的总称。基本类型（原子类型）不可再分，如 32 位有符号整数值域为 `[-2³¹, 2³¹−1]`，操作为加、减、乘、除、取模等，超出范围会溢出；结构类型由基本类型组合而成。

**抽象数据类型（ADT）**是用户定义的、表示应用问题的数据模型以及定义在该模型上的一组操作。它只描述“是什么”和“能做什么”，不规定“怎样存储、怎样实现”。ADT 最重要的性质是**抽象**：使用与实现分离，通过封装隐藏内部细节；外部视图给出名称、数据对象与可用操作，内部视图才涉及存储与代码。

ADT 可用三元组 `(D, S, P)` 表示：`D` 是数据对象，`S` 是关系集，`P` 是基本操作集。操作分三类：初始化与销毁（`Init`、`Destroy`、`Clear`）；访问型（查询、遍历、打印，不修改数据）；加工型（插入、删除、修改、合并，会改变数据）。每个操作按“操作名（参数表）：初始条件 → 操作结果”描述；初始条件不满足时操作失败，返回错误信息。

## 7. ADT 书写模板与复数例子

来源：课件第 36–42 页。

以复数为例，ADT 可写成（按课件第 36–37 页的分量模型，`(a, b)` 表示对象内部由两个实数分量组成，`<a, b>` 表示分量的角色与次序，两者都是内部表示）：

```text
ADT Complex {
    数据对象：D = { (a, b) | a, b ∈ Real }
    数据关系：S = { <a, b> | a 是实部、b 是虚部 }
    基本操作：InitComplex(Z, a, b)、DestroyComplex(Z)、
              GetComplex(Z, a, b)、PrintComplex(Z)、
              PutReal(Z, x)、PutImaginary(Z, y)、
              AddComplex(Z, Z1, Z2)、SubComplex(Z, Z1, Z2)
} // ADT Complex
```

对外部使用者，复数是一个整体值，只能通过操作观察，不能把实部、虚部当作两个独立对象。C 风格实现：

```c
typedef double ElemType;

typedef struct {
    ElemType real;
    ElemType imaginary;
} ComplexNumber;

typedef int Status;
#define OK 1
#define ERROR 0
#define OVERFLOW -1

Status InitComplex(ComplexNumber *Z, ElemType a, ElemType b) {
    Z->real = a;
    Z->imaginary = b;
    return OK;
}

Status GetComplex(ComplexNumber Z, ElemType *a, ElemType *b) {
    *a = Z.real;
    *b = Z.imaginary;
    return OK;
}
```

调用时对输出参数取地址：`InitComplex(&z, 1.0, 2.0); GetComplex(z, &re, &im);`。

要点与约定：

- 本课程代码用 C 风格：需要写回的参数用指针 `T *x`，调用时对实参取地址 `&x`，函数内用 `*x` 或 `x->成员` 写回；不要写 C++ 的 `T &x`（它不是 C 语法）。
- 只读参数按值传递（如 `GetComplex` 的 `Z`），需要返回或修改的数据用指针参数（如 `InitComplex` 的 `Z`）。访问型操作只读，加工型操作写回，参数方向由操作语义决定。
- `Status` 统一返回状态，`OK`、`ERROR`、`OVERFLOW` 分别表示成功、一般失败、分配失败，调用者应检查。
- 静态复数销毁时清零即可；若有动态分配，`Destroy` 必须释放内存。调用 `GetComplex` 前应先 `InitComplex`，未初始化就读取，结果没有定义。

## 8. 算法及其五个特性

来源：课件第 43–47 页。

算法是对特定问题求解步骤的描述，是有限条指令的序列。程序设计等于数据组织加求解策略；数据结构与算法相互依存，结构的优劣要通过实现其操作的算法来体现。

算法必须同时满足五个特性：

| 特性   | 含义                                 |
| ------ | ------------------------------------ |
| 有穷性 | 有穷步后结束，每步在有穷时间内完成   |
| 确定性 | 指令含义确切，相同输入产生相同输出   |
| 可行性 | 每步都能由已实现的基本运算有限次完成 |
| 输入   | 零个、一个或多个，取自明确集合       |
| 输出   | 至少一个，且与输入有确定关系         |

典型反例：死循环或无终止递归违反有穷性；依赖未说明的随机数或外部状态违反确定性；把“求最优解”写成一个未定义的步骤违反可行性。有穷不等于实用：理论上终止但需指数级步骤的算法，实际无法完成。确定性也不等于“结果唯一”，而是相同输入与执行条件给出相同结果；显式使用随机数的算法属于随机算法，需另行分析。

## 9. 设计目标与正确性层次

来源：课件第 48–51 页。

算法设计追求四个目标：正确性、可读性、健壮性、高效性。

正确性分四个层次：①无语法错误，能运行；②常规输入符合规格；③精心选择的苛刻数据（含边界）也正确；④一切合法输入都正确。本课程要求达到第 3 层；第 4 层需形式化证明。

健壮性要求对非法输入适当处理：返回错误状态、给出明确提示、保持数据对象可接受，而不是打印错误后中止；但也不等于容忍错误数据继续计算。

高效性要求执行时间短、存储空间少。规模小时差异可能不明显，规模增大后低效算法会迅速不可用。常用“以空间换时间”，例如建立索引、缓存或散列表。

## 10. 时间与空间复杂度

来源：课件第 52–54 页。

时间复杂度 `T(n)` 用基本操作执行次数衡量，而非运行秒数；语句频度是各语句执行次数之和。例 1.3 用首行行和初始化 `max_sum` 并检查 `n` 的范围，频度表合计 `2n² + 4n + 1`（首行累加与其余 `n−1` 行分组统计）；最频繁的是内层 `sum += A[i][j]`，故 `T(n) = n²`。若 `max_sum` 无条件置 0，全负矩阵会错误地返回 0，例如 1×1 矩阵元素为 −3 时应返回 −3。

空间复杂度 `S(n)` 包括指令、常数与变量、输入数据及辅助空间，通常只关心辅助空间。额外空间相对输入为常数时称原地工作，记 `S(n) = O(1)`，即额外空间不随 `n` 增长，并非不使用空间。

## 11. 大 O、Θ 与常见增长阶

来源：课件第 55–58 页。

大 O 记号描述渐近上界：若存在正常数 `c` 和 `n₀`，使 `n ≥ n₀` 时恒有 `f(n) ≤ c·g(n)`，则记 `f(n) = O(g(n))`。它忽略常数因子与低次项，如 `2n² + 4n + 1 = O(n²)`。Θ 记号描述紧界：若 `c₁·g(n) ≤ f(n) ≤ c₂·g(n)` 对足够大的 `n` 恒成立，则 `f(n) = Θ(g(n))`；例 1.3 是 `Θ(n²)`。只关心上界时用 O，上下界一致时用 Θ 更精确。

| 增长阶       | 典型来源                   |
| ------------ | -------------------------- |
| `O(1)`       | 数组下标存取               |
| `O(log n)`   | 二分查找、减半或倍增循环   |
| `O(n)`       | 遍历、顺序查找             |
| `O(n log n)` | 归并排序、堆排序           |
| `O(n²)`      | 冒泡排序、选择排序         |
| `O(n³)`      | 朴素矩阵乘法               |
| `O(2ⁿ)`      | 子集枚举、朴素递归斐波那契 |
| `O(n!)`      | 全排列枚举                 |

增长速度由慢到快为 `O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)`。

同一算法在不同输入上的代价不同，故区分最好、平均与最坏情况。以冒泡排序为例：正序最好，带提前结束优化时为 `O(n)`；随机排列平均为 `O(n²)`；逆序最坏为 `O(n²)`。若用不设标志的朴素双重循环，任何输入都比较 `n(n−1)/2` 次，最好情况仍是 `O(n²)`。工程上通常按最坏情况估计，因为它给出确定上界；平均情况须说明输入分布。

## 12. 频度计算与易错点

来源：课件第 59–62 页。

频度计算有三条常用规则：

1. **独立嵌套相乘**：内外层互不影响时总次数为各层次数之积，双重 `n` 循环为 `n²`。
2. **依赖外层求和**：内层上界随外层变化时逐项相加，`for (i = 0; i < n; i++) for (j = i; j < n; j++)` 的频度为 `n + (n−1) + … + 1 = n(n+1)/2`，仍为 `O(n²)`。
3. **倍增或减半取对数**：`while (i < n) i = i * 2;` 执行 `⌈log₂n⌉` 次，为 `O(log n)`；每次规模减半的递归也属对数阶。

易错点：把运行秒数当复杂度；认为嵌套循环一定 `O(n²)`（还要看内层范围与变化规律）；把 `O(1)` 理解为不花时间；把上界当紧界；忽略最坏情况；只算辅助空间却漏掉递归栈；纠结对数底数。

## 13. 自测清单与易混对照

来源：课件第 63–80 页。

自测：

- 区分数据、数据对象、数据元素、数据项，并各举一例。
- 给定场景，判断属于集合、线性、树形还是图状结构，并说明理由。
- 说明数据结构 `(D, S)` 与 ADT `(D, S, P)` 的区别，以及逻辑结构与存储结构的区别。
- 比较顺序与链式存储的随机访问、插删、空间开销和适用场景。
- 写出 ADT 三元组、操作分类与操作描述格式，说明指针输出参数的方向与调用处的取地址。
- 判断一个过程是否满足算法五特性，并给出反例。
- 独立推导例 1.3 的 `2n² + 4n + 1`，说明为何取 `O(n²)`，并说明全负矩阵的初值处理。
- 设计 4000 个百分制成绩的统计方案，求降序第 2000 名（次序统计量，不是通常中位数），达到 `O(n)` 时间与 `O(101)`（相对 n 为常数）辅助空间。

| 易混项                | 区别                                                            |
| --------------------- | --------------------------------------------------------------- |
| 数据对象 / 数据结构   | 数据对象是同类元素的集合；数据结构是 `(D, S)`，ADT 才含操作 `P` |
| 逻辑结构 / 存储结构   | 前者面向问题、与机器无关；后者是内存中的表示                    |
| 时间复杂度 / 执行时间 | 前者是基本操作次数的增长阶；后者是具体环境下的秒数              |
| 大 O / Θ              | O 给上界，Θ 给上下界一致的紧界                                  |
| 最好 / 最坏情况       | 前者是代价最小的输入，后者是代价最大的输入                      |

## 14. 延伸阅读

来源：课件第 74–80 页。

渐近记号（`O`、`Ω`、`Θ`）来自 19 世纪末至 20 世纪初的解析数论与分析学，20 世纪中期以后被系统地引入算法分析；计算复杂性在 20 世纪 60 年代前后成为独立研究方向。数据结构与算法分析的体系随编译器、操作系统和大型程序的发展而逐步形成：线性表、栈、队列、树、图等结构及其算法在 20 世纪 50—60 年代被大量研究并整理成教材；Knuth 的《计算机程序设计艺术》从 1960 年代末起陆续出版；Wirth 以“算法 + 数据结构 = 程序”为题写作教材，Hoare 在快速排序、程序逻辑与并发理论等方面有重要贡献。更详细的年表与人物资料见课件第 74–80 页所列文献，本笔记不再展开考据。

课件列出的参考文献包括 Wirth 的《Algorithms + Data Structures = Programs》、Knuth 的《The Art of Computer Programming》以及严蔚敏、吴伟民的《数据结构（C 语言版）》。