# 数据结构前三章：跨章知识索引

这份索引把前三章的概念、复杂度、操作约定和边界条件集中在一处，可以脱离讲义单独查阅；需要完整推导和示例时，再沿各节的链接回到对应章节。三章依次对应课件第 1–80 页、第 1–95 页、第 1–105 页。

## 1. 三章的位置与阅读顺序

| 章              | 核心问题                                       | 主要产出                                                                   | 讲义                            |
| --------------- | ---------------------------------------------- | -------------------------------------------------------------------------- | ------------------------------- |
| 第一章 概论     | 数据如何被抽象，算法如何评价                   | 基本术语、四类逻辑结构、存储结构、抽象数据类型、时间复杂度与空间复杂度     | [概论](/数据结构/概论/)         |
| 第二章 线性表   | 同一个线性表抽象数据类型怎样落到两种存储表示上 | 顺序表、单链表、双向链表、循环链表、静态链表，以及插入、删除、查找的代价   | [线性表](/数据结构/线性表/)     |
| 第三章 栈和队列 | 限制操作范围后得到什么结构，能解决哪些问题     | 顺序栈、链式栈、循环队列、链队列，以及括号匹配、表达式求值、回溯和队列应用 | [栈和队列](/数据结构/栈和队列/) |

建议按顺序阅读。第一章提供描述数据结构和评价算法的共同语言；第二章第一次完整走完“抽象数据类型 → 存储表示 → 基本操作 → 复杂度与边界”的流程；第三章沿用同一方法，只允许在栈顶或队头队尾操作，用更少的合法操作换取更清楚的约束和更直接的算法。

## 2. 基本术语：从数据到抽象数据类型

- 数据是信息的载体；数据元素是数据的基本单位，通常作为一个整体处理；数据项是数据元素中不可再分的最小单位；数据对象是性质相同的数据元素的集合。
- 逻辑结构描述数据元素之间的抽象关系，常见四类为集合、线性结构、树形结构和图状结构。线性表、栈、队列都属于线性结构。
- 存储结构描述逻辑结构在计算机中的实现，基本方式包括顺序存储和链式存储；索引存储和散列存储作为扩展了解。同一种逻辑结构可以有多种存储结构。
- 抽象数据类型由数据对象、数据对象上的关系以及一组操作组成，强调“做什么”而不是“怎样做”。用抽象数据类型描述线性表时，操作以位序定义，不依赖数组下标或指针细节。
- 算法具有有穷性、确定性、可行性、输入和输出五个特性。评价算法时同时看正确性、可读性、健壮性和效率；效率通常用时间复杂度与空间复杂度衡量。

常见错误是把逻辑结构和存储结构混为一谈，例如说“线性表就是数组”；或者把抽象数据类型的操作直接写成依赖 `->next` 的代码。判断一种说法是否属于抽象数据类型，可以看它是否只描述数据对象、关系和操作，而不绑定具体存储方式。

## 3. 复杂度：记法、成立条件与常见量级

- O 记法给出增长量级的上界，Ω 给出下界，Θ 表示上界与下界同阶。严格讨论时，若一个算法的最好与最坏情况同阶，用 Θ 更准确；日常说“时间复杂度为 O(n)”通常只是量级简称。
- 分析前先固定计数口径：顺序表以元素移动次数为主，链表以访问结点次数和指针修改次数为主，递归算法先写递归式并确定边界条件。口径不同，得到的表达式可能不同，比较时必须使用同一口径。
- 常见量级从低到高为 O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ)、O(n!)。冒泡、简单选择、直接插入排序的典型复杂度为 O(n²)；二分查找为 O(log n)，但要求数据有序且能够随机存取。
- 最好、最坏和平均情况要分开说明。顺序表在第 i 个位置插入时移动 n−i+1 个元素，删除第 i 个元素时移动 n−i 个元素；按均匀位置估计，插入和删除的平均移动量都是 O(n)。

| 操作     | 顺序表                     | 单链表                             | 顺序栈或链栈                                                 | 循环队列或链队列                         |
| -------- | -------------------------- | ---------------------------------- | ------------------------------------------------------------ | ---------------------------------------- |
| 按位查找 | O(1)，随机存取             | O(n)，从头遍历                     | 只允许访问栈顶，O(1)                                         | 只允许访问队头队尾，O(1)                 |
| 按值查找 | O(n)                       | O(n)                               | 不作为基本操作                                               | 不作为基本操作                           |
| 插入     | O(n)，平均移动一半元素     | 已知前驱时 O(1)，否则先找前驱 O(n) | 栈顶入栈 O(1)；顺序栈需固定容量未满，或按比例扩容后均摊 O(1) | 队尾入队 O(1)                            |
| 删除     | O(n)，平均移动一半元素     | 已知前驱时 O(1)，否则先找前驱 O(n) | 栈顶出栈 O(1)                                                | 队头出队 O(1)                            |
| 空间     | 需要连续空间，可能预留容量 | 每个结点额外存指针                 | 顺序栈可能溢出，链栈按需分配                                 | 循环队列少用一个单元，链队列多一个头结点 |

## 4. 表示与操作约定

### 4.1 位序与数组下标

讲义用位序描述抽象数据类型中的元素位置，位序从 1 开始，范围为 1 到 n；讲义伪代码中的数组下标从 0 开始，范围为 0 到 n−1。第 i 个元素存放在下标 i−1 处。顺序表插入位置 i 的合法范围是 1 到 n+1，删除位置 i 的合法范围是 1 到 n；判断合法位置时不能直接套用下标范围。

### 4.2 链表的头结点

单链表带头结点：头指针指向头结点，头结点不保存数据，首元结点是头结点的后继。空表条件是头结点的后继为空，而不是头指针为空。头结点的作用是统一在表头插入、删除时的指针操作，并让空表和非空表的处理保持一致。插入和删除都要先保存后继结点的地址，再修改前驱的指针，避免丢失剩余链表。已知前驱时插入和删除为 O(1)，只知道位序时仍要 O(n) 找前驱；逆置要单独处理空表和只有一个结点的情况。

### 4.3 栈顶约定

栈是后进先出的线性表，只允许在栈顶插入和删除，栈底固定。本课程讲义中的顺序栈统一采用 `pTop` 指向栈顶元素的下一个空位：空栈为 `pTop == pBase`，元素个数为 `pTop − pBase`，入栈先写 `*pTop` 再让 `pTop++`，出栈先读 `*(pTop−1)` 再让 `pTop--`（也可以先 `pTop--` 再读 `*pTop`，两种写法等价），取栈顶读 `*(pTop−1)` 且不移动指针。双端共享栈采用另一套下标约定：`top1`、`top2` 分别是两个栈的栈顶元素下标，`top1 == -1`、`top2 == M` 表示空，`top1 + 1 == top2` 表示满；它不是 `pTop` 下一空位写法，公式不能混用。阅读其他材料时先看初始化，再套对应公式。

### 4.4 队头与队尾约定

队列是先进先出的线性表，只允许在队尾入队、在队头出队。循环队列用一段连续空间首尾相接：`front` 指向队头元素，`rear` 指向队尾元素的下一个位置。为了区分空和满，循环队列少用一个存储单元：容量为 m 时最多存放 m−1 个元素，空队条件为 `front == rear`，满队条件为 `(rear + 1) % m == front`，队长为 `(rear - front + m) % m`。链队列带头结点，空队时 `front` 和 `rear` 都指向头结点；出队后若队列变空，要把 `rear` 重新指向头结点。

### 4.5 课件与两本教材的接口差异

课件第 1 章的复数接口属于类 C/C++ 混写，其 ADT 形式定义里若出现 `&`，只表达输出参数的方向，形式定义不是 C 代码。讲义正文统一采用 C 风格伪代码：需要写回的参数用 `T *x` 指针表示，调用时写 `&x`，代码调用中的 `&` 就是取地址运算符；第 2、3 章统一用 C 风格结构体、指针参数和 `malloc/free`。C++ 引用的写法是在类型后加 `&`（如 `T &x`），它不是 C 语法，讲义正文不使用，只在与教材比较时提及，不能把 C++ 引用语法当成 C 的取地址写法。补充核对用的两本教材分别使用 C++ 和 C 语言版本：C++ 版用引用参数、模板与类描述接口，C 版用指针和 `malloc/free`；两书的页序、位序与下标、头结点、栈顶指针、队头队尾约定也可能不同。阅读时先确认接口语言和约定，再与讲义公式换算，也不能把教材页码当作“课件第 x–y 页”。

## 5. 边界与常见错误

| 结构或算法   | 必须检查的边界                                                                 | 常见错误                                                                                                                          |
| ------------ | ------------------------------------------------------------------------------ | --------------------------------------------------------------------------------------------------------------------------------- |
| 顺序表       | n=0、插入到表尾、删除最后一个元素、容量已满、位置非法                          | 插入时从前向后移动导致元素被覆盖；删除时从后向前移动；位序与下标混用                                                              |
| 单链表       | 空表、表头插入、表尾插入、删除首元结点、删除后释放结点                         | 先改前驱指针再保存后继；头结点被当作数据结点计数；空表访问 `head->next->next`                                                     |
| 栈           | 空栈出栈、栈满入栈、取空栈栈顶                                                 | 判空与判满公式和 `top` 约定不配套；出栈后继续读取栈内旧槽位，或链栈删除结点后仍解引用已释放的结点（出栈返回的值副本可以继续使用） |
| 括号匹配     | 右括号到来时栈空、扫描结束时栈非空、左右括号类型不匹配                         | 只检查总数是否相等；遇到不匹配仍继续扫描而不立即报告                                                                              |
| 表达式求值   | 多位数、空白字符、一元负号、除数为零、同级运算符左结合、结果可为负数或有限小数 | 把每个字符当成一个操作数；弹出操作数时左右顺序颠倒；负号被当作减号处理；把除法按整数截断                                          |
| 循环队列     | 队空出队、队满入队、容量为 1、入队或出队后 front/rear 回绕                     | 用 `front == rear` 判满；实际容量按 m 计算而没有少用一个单元；满队入队仍修改 rear                                                 |
| 链队列       | 空队出队、出队后队列变空、入队到空队                                           | 出队后忘记重置 rear；头结点被当作数据结点；删除结点后未释放                                                                       |
| N 皇后与回溯 | n=1 到 n=6、n=2 和 n=3 无解、逐行放置、列与两条对角线冲突                      | 只检查列不检查对角线；失败回退时未撤销标记；把搜索树按指数级全部展开                                                              |

几个容易忽略的细节：顺序表的插入移动方向必须从后向前，删除必须从前向后，否则会覆盖尚未处理的数据；单链表插入和删除的第一步都是保存后继；括号匹配的错误要在发现时立即报告，结束时栈非空说明还有左括号没有闭合；表达式求值中操作数按从左到右入栈，弹出时先得到右操作数；循环队列的空和满不能只靠 `front` 与 `rear` 是否相等区分，必须牺牲一个单元或增加计数；N 皇后的回溯要在递归返回后恢复列和对角线标记。

## 6. 各章阅读入口与自测

### 第一章：概论

阅读[第一章讲义](/数据结构/概论/)。读完后应能用自己的话区分数据项、数据元素和数据对象，说明逻辑结构与存储结构的区别，写出抽象数据类型的组成，并判断一段算法描述是否满足有穷性。自测：为什么说“数组是线性表的一种存储实现”而不是“线性表就是数组”？顺序表和链表在按位查找上的差异来自什么条件？

### 第二章：线性表

阅读[第二章讲义](/数据结构/线性表/)。重点是顺序表和单链表上的查找、插入、删除，以及带头结点链表的空表判断。课件的主例是城市清单差集：`La` 是小文去过的城市，`Lb` 是小明去过的城市，输出 `Lb − La`，即小明去过而小文没去过的城市；朴素做法 O(|La||Lb|)，两表有序后双指针降为 O(|La|+|Lb|)。自测：顺序表插入和删除分别移动多少个元素？单链表在什么条件下插入和删除为 O(1)？逆置一个带头结点的单链表需要几个指针，空表和单结点表如何处理？

### 第三章：栈和队列

阅读[第三章讲义](/数据结构/栈和队列/)。重点是后进先出与先进先出的操作限制、顺序栈与链式栈的实现、循环队列的判空判满，以及栈在括号匹配、表达式求值和回溯中的应用。表达式求值允许负数和有限小数的中间结果与最终结果（如 `5/2 = 2.5`），不能按整数截断；界面上的小数位数只是显示约定。队列的温度滑动窗口按“最近 k 个采样、总和随入出队增减”理解；课件不同页给出的采样频率与窗口数值并不一致，不要把不同题设的数字拼在一起。平均值有两种预热口径：**暖启动**在窗口未满时分母取当前样本数，**预热期不输出**则分母恒为 k；本课程的实验采用暖启动，采用另一种口径时必须在题设和界面上写明分母，不能混用。自测：循环队列容量为 m 时为什么只能存 m−1 个元素？中缀表达式转后缀时运算符的优先级和结合性如何体现？N 皇后在 n=2 和 n=3 时为什么无解？

## 7. 一页速查

| 项目             | 公式或结论                                                                                       |
| ---------------- | ------------------------------------------------------------------------------------------------ |
| 顺序表元素地址   | 设首元素地址为 base、每个元素占 c 个单元，位序 i 的地址为 base + (i−1)·c                         |
| 顺序表插入移动量 | 在第 i 个位置插入（1 ≤ i ≤ n+1），移动 n−i+1 个元素                                              |
| 顺序表删除移动量 | 删除第 i 个元素（1 ≤ i ≤ n），移动 n−i 个元素                                                    |
| 单链表空表       | 带头结点时 `head->next == NULL`                                                                  |
| 循环队列判空     | `front == rear`                                                                                  |
| 循环队列判满     | `(rear + 1) % m == front`                                                                        |
| 循环队列队长     | `(rear - front + m) % m`                                                                         |
| 顺序栈 pTop 约定 | 指向栈顶元素的下一个空位；空栈 `pTop == pBase`，长度 `pTop − pBase`                              |
| 双端共享栈 top   | `top1`、`top2` 为元素下标；空 `top1 == -1`、`top2 == M`，满 `top1 + 1 == top2`                   |
| 表达式结果       | 中间结果与最终结果可为负数或有限小数；界面最多显示固定小数位，不做整数截断                       |
| 温度窗口分母     | 本课程实验采用暖启动，未满窗口的分母是当前样本数；课件第 82 页的预热期不输出口径分母恒为窗口常量 |
| 二分查找条件     | 数据有序且支持随机存取，时间复杂度 O(log n)                                                      |
| 单链表按位查找   | O(n)，必须从头结点出发沿后继逐个访问                                                             |

复杂度记法、操作代价和边界条件最终都要回到具体存储表示上判断；遇到不同教材或不同代码的写法时，先确认位序与下标、头结点、栈顶和队头队尾的约定，再使用相应公式。