数据结构(C语言版)严蔚敏吴伟民经典教材实战解析
简介：《数据结构(C语言版)》是严蔚敏和吴伟民编著的经典教材，系统讲解线性表、栈、队列、树、图、散列表等核心数据结构，并结合C语言实现，配以丰富实例与习题。本书深入浅出，涵盖排序与查找算法，帮助读者掌握数据的高效组织与操作方法，提升编程与算法设计能力，是计算机科学学习和软件开发实践中的必备参考书。
1. 数据结构基础概念与重要性
数据结构的基本定义与分类
数据结构是计算机中组织和存储数据的方式，它不仅定义了数据元素之间的逻辑关系，还决定了数据在内存中的物理布局。根据数据元素之间关系的不同，数据结构可分为线性结构（如数组、链表）和非线性结构（如树、图）。逻辑结构关注“数据间的关系”，而物理结构则体现“数据在内存中的存储方式”。例如，线性表在逻辑上是线性的，但可通过顺序存储（连续内存）或链式存储（指针连接）实现。
抽象数据类型（ADT）的核心思想
抽象数据类型（ADT）从接口层面定义数据结构的行为，封装数据与操作，屏蔽底层实现细节。一个典型的ADT List应提供 Insert 、 Delete 、 Search 等操作，并规定其行为规范，而不依赖具体语言或存储方式。这种“设计接口先行”的思想有助于提升代码的可维护性和复用性，在C语言中可通过结构体与函数指针模拟实现：
typedef struct {
int* data;
int length;
int capacity;
} ArrayList;
该结构体结合配套函数（如 list_insert() 、 list_delete() ），构成了ADT的实现基础。
数据结构对程序性能的影响
良好的数据结构选择能显著提升算法效率。例如，在频繁插入删除的场景下，链表优于数组；而在随机访问为主的应用中，数组更具优势。时间复杂度从O(n)到O(1)的优化往往源于结构本身的特性。通过理解“结构决定效率”的核心理念，开发者可在实际工程中避免误用——如用数组实现队列导致大量搬移，应改用循环队列或链式队列。这为后续学习各类数据结构奠定了实践导向的认知框架。
2. 线性表（顺序表与链表）设计与实现
线性表是数据结构中最基础且最广泛应用的逻辑结构之一，它体现了元素之间“一对一”的前驱后继关系。在实际开发中，无论是数组、栈、队列还是更复杂的图和树结构，其底层都可能依赖于线性表的思想进行建模与实现。本章将从抽象定义出发，深入剖析线性表的两种主要物理实现方式——顺序表与链表，并通过C语言的具体编码展示其构建过程、操作机制以及性能差异。重点在于理解不同存储结构背后的内存管理策略、时间空间复杂度权衡以及工程实践中的选型依据。
2.1 线性表的逻辑结构与抽象定义
线性表作为一种典型的线性结构，其核心特征在于数据元素之间的逻辑顺序呈线性排列。这种结构不仅形式简洁，而且为后续高级数据结构的设计提供了基本范式。理解线性表的抽象模型是掌握其多种实现方式的前提。
2.1.1 线性表的基本特征与数学模型
线性表是由 $ n $ 个具有相同类型的数据元素组成的有限序列，记作：
$$ L = (a_1, a_2, …, a_i, a_{i+1}, …, a_n) $$
其中，$ a_1 $ 是表头元素，$ a_n $ 是表尾元素，每个元素 $ a_i $ 都有唯一的直接前驱（除 $ a_1 $ 外）和唯一的直接后继（除 $ a_n $ 外）。这一结构满足以下四个基本特征：
- 有穷性 ：表中元素个数 $ n \geq 0 $，当 $ n=0 $ 时称为空表。
- 有序性 ：元素之间存在严格的先后顺序，位置由索引唯一确定。
- 同质性 ：所有元素属于同一数据类型，便于统一处理。
- 单对一关联 ：任意非端点元素仅有一个前驱和一个后继。
该数学模型可被广泛应用于电话簿、任务列表、日志记录等现实场景。例如，在一个用户登录历史记录系统中，每条记录按时间顺序构成一个线性表，支持按序遍历或查找特定时间段内的活动。
进一步地，线性表的逻辑结构不关心具体的存储方式，只关注元素间的逻辑关系。这意味着同一个线性表可以用不同的物理结构来实现，如连续存储的顺序表或离散存储的链表。正是这种“逻辑与物理分离”的思想，使得我们可以基于应用场景灵活选择最优实现方案。
此外，线性表的操作具有高度一致性。常见的基本操作包括：
- 初始化（InitList）
- 判空（IsEmpty）
- 获取长度（GetLength）
- 按位查找（GetElem）
- 按值查找（LocateElem）
- 插入（Insert）
- 删除（Delete）
这些操作构成了线性表的核心行为集，无论采用何种实现方式，都应保证接口的一致性和语义的正确性。这也引出了下一节关于抽象数据类型ADT List的规范定义。
2.1.2 抽象数据类型ADT List的接口规范
抽象数据类型（Abstract Data Type, ADT）是一种强调“做什么”而非“怎么做”的程序设计思想。对于线性表而言，ADT List 提供了一组清晰的操作契约，使上层应用无需了解底层实现细节即可安全调用。以下是用伪代码形式描述的标准 ADT List 接口：
ADT List {
数据：
ElemType data[MAXSIZE]; // 元素集合（示例，具体实现可变）
int length; // 当前长度
操作：
InitList(&L); // 初始化线性表
DestroyList(&L); // 销毁线性表
ClearList(&L); // 清空线性表
IsEmpty(L); // 判断是否为空
GetLength(L); // 返回元素个数
GetElem(L, i, &e); // 获取第i个元素
LocateElem(L, e); // 查找元素e的位置
PriorElem(L, cur_e, &pre_e); // 获取前驱
NextElem(L, cur_e, &next_e); // 获取后继
ListInsert(&L, i, e); // 在第i个位置插入元素e
ListDelete(&L, i, &e); // 删除第i个元素并返回
ListTraverse(L, visit()); // 遍历所有元素执行visit函数
}
| 函数名 | 功能说明 | 时间复杂度（典型实现） |
|---|---|---|
InitList | 分配初始资源，设置length为0 | O(1) |
IsEmpty | 判断length是否为0 | O(1) |
GetLength | 返回length值 | O(1) |
GetElem | 根据索引访问元素 | O(1)（顺序表），O(n)（链表） |
LocateElem | 找到第一个匹配元素的下标 | O(n) |
ListInsert | 插入新元素，其余后移 | O(n)（平均） |
ListDelete | 删除元素，其余前移 | O(n)（平均） |
上述接口的设计遵循了模块化与封装原则，使用者只需包含头文件并调用相应函数，而不必关心内部是如何使用数组还是指针实现的。这极大提升了代码的可维护性和可复用性。
为了更好地理解接口背后的行为逻辑，下面是一个简单的 mermaid 流程图，展示了插入操作的控制流程：
graph TD
A[开始插入操作] --> B{检查位置i是否合法}
B -- 否 --> C[返回错误码]
B -- 是 --> D{表是否已满?}
D -- 是 --> E[扩容或返回失败]
D -- 否 --> F[从末尾起向右移动元素]
F --> G[在位置i放入新元素]
G --> H[length++]
H --> I[结束]
此流程图清晰表达了插入操作的关键判断路径：合法性校验 → 空间检查 → 数据搬移 → 新元素写入 → 长度更新。虽然具体实现因结构而异，但整体逻辑框架保持一致。
值得注意的是，ADT 的定义并不限定语言或平台。在现代C++中，可通过类模板实现泛型List；而在C语言中，则常借助结构体与函数指针模拟面向对象特性。无论哪种方式，目标都是提供稳定、高效、易于扩展的数据访问接口。
2.2 顺序表的设计与C语言实现
顺序表是线性表的一种物理实现方式，其本质是利用一段连续的内存空间存储数据元素。由于其随机访问特性优异，顺序表在许多实时性要求高、读操作频繁的系统中占据重要地位。
2.2.1 静态数组与动态数组的实现策略
顺序表的实现可分为静态分配与动态分配两种策略。静态数组在编译期固定大小，适合已知最大容量的场景；而动态数组则在运行时根据需要调整空间，灵活性更高。
静态顺序表实现示例：
#define MAXSIZE 100
typedef int ElemType;
typedef struct {
ElemType data[MAXSIZE];
int length;
} SqList;
这种方式的优点是实现简单、访问速度快，但由于 MAXSIZE 固定，容易造成空间浪费或溢出风险。
动态顺序表实现：
typedef struct {
ElemType *data;
int length;
int capacity; // 当前最大容量
} DynamicSqList;
// 初始化动态顺序表
void InitDynamicList(DynamicSqList *L, int init_capacity) {
L->data = (ElemType*)malloc(init_capacity * sizeof(ElemType));
if (!L->data) exit(EXIT_FAILURE);
L->length = 0;
L->capacity = init_capacity;
}
参数说明 ：
-data：指向堆区分配的连续内存块，用于存放元素。
-length：当前有效元素个数。
-capacity：当前可容纳的最大元素数量。逻辑分析 ：
此处使用malloc在堆上申请内存，避免栈溢出问题。初始化后可通过realloc实现动态扩容。相比静态版本，动态顺序表更具实用性。
接下来是插入操作的完整实现：
int ListInsert(DynamicSqList *L, int i, ElemType e) {
if (i < 1 || i > L->length + 1) return 0; // 位置非法
if (L->length >= L->capacity) { // 空间不足
ElemType *newBase = (ElemType*)realloc(L->data,
(L->capacity + 10) * sizeof(ElemType)); // 扩容10个单位
if (!newBase) return -1;
L->data = newBase;
L->capacity += 10;
}
for (int j = L->length; j >= i; j--) {
L->data[j] = L->data[j - 1]; // 元素后移
}
L->data[i - 1] = e;
L->length++;
return 1;
}
逐行解读 ：
1. 第一行检查插入位置合法性（从1开始计数）；
2. 若当前长度已达容量上限，则尝试扩容；
3. 使用realloc增加10个元素空间，失败返回-1；
4. 从最后一个元素开始向前移动，腾出位置i；
5. 将新元素赋值到data[i-1]（数组下标从0起）；
6. 更新长度并返回成功标志。
该实现兼顾了健壮性与效率，适用于大多数中小型应用场景。
2.2.2 插入、删除、查找操作的时间复杂度分析
顺序表的操作效率与其内存布局密切相关。由于元素连续存储，支持O(1)随机访问，但在插入和删除时需大量移动数据。
| 操作 | 最好情况 | 平均情况 | 最坏情况 | 说明 |
|---|---|---|---|---|
| 查找（按值） | O(1) | O(n) | O(n) | 需遍历比较 |
| 插入 | O(1) | O(n) | O(n) | 表尾插入最快，表头最慢 |
| 删除 | O(1) | O(n) | O(n) | 同样涉及元素前移 |
以插入为例，假设在第 $ i $ 个位置插入，需后移 $ n - i + 1 $ 个元素。平均移动次数为：
\frac{1}{n+1} \sum_{i=1}^{n+1}(n-i+1) = \frac{n}{2}
故平均时间复杂度为 $ O(n) $。
相比之下，查找操作若结合二分法（前提是有序），可优化至 $ O(\log n) $，但普通线性查找仍为 $ O(n) $。
2.2.3 内存扩容机制与空间利用率优化
动态顺序表的扩容策略直接影响性能表现。常见的做法包括：
- 固定增量扩容 ：每次增加固定数量（如+10），优点是可控，缺点是频繁 realloc。
- 倍增扩容 ：每次容量翻倍（如×2），摊销时间复杂度更低。
下面是比较两种策略的表格：
| 扩容策略 | 总复制次数（n次插入） | 摊销成本 | 空间利用率 |
|---|---|---|---|
| 固定+10 | $ O(n^2) $ | O(n) | 较低（易碎片） |
| 倍增（×2） | $ 2n $ | O(1) | 较高（接近50%） |
推荐使用倍增策略。修改代码如下：
if (L->length >= L->capacity) {
L->capacity *= 2;
L->data = (ElemType*)realloc(L->data, L->capacity * sizeof(ElemType));
if (!L->data) exit(EXIT_FAILURE);
}
这样可在长期运行中显著降低内存重分配频率，提升整体性能。
2.3 单链表与双向链表的构建实践
链表通过节点间的指针链接实现逻辑顺序，克服了顺序表插入删除效率低的问题，尤其适合频繁变动的场景。
2.3.1 结点结构定义与动态内存分配
单链表节点定义如下：
typedef struct ListNode {
ElemType data;
struct ListNode *next;
} ListNode, *LinkList;
创建节点示例：
ListNode* CreateNode(ElemType e) {
ListNode *p = (ListNode*)malloc(sizeof(ListNode));
p->data = e;
p->next = NULL;
return p;
}
参数说明 ：
-data存储元素值；
-next指向下一个节点，末尾为NULL；
- 使用malloc动态分配，必须配对free防止泄漏。
2.3.2 头插法、尾插法及指定位置插入的编码实现
头插法（逆序插入）：
void HeadInsert(LinkList *L, ElemType e) {
ListNode *s = CreateNode(e);
s->next = *L;
*L = s;
}
特点：新节点总位于链表头部，适合快速构造反向序列。
尾插法（保持原序）：
void TailInsert(LinkList *L, ElemType e) {
ListNode *s = CreateNode(e), *rear = *L;
if (!*L) {
*L = s;
return;
}
while (rear->next) rear = rear->next;
rear->next = s;
}
需遍历至尾部，时间复杂度O(n)，但维持了输入顺序。
指定位置插入：
int InsertAtPos(LinkList *L, int i, ElemType e) {
if (i < 1) return 0;
ListNode *p = *L;
for (int j = 1; j < i - 1 && p; j++) p = p->next;
if (!p && i > 1) return 0;
ListNode *s = CreateNode(e);
s->next = p->next;
p->next = s;
return 1;
}
类似于顺序表，但无需移动元素，仅修改指针。
2.3.3 链表遍历、删除与逆置操作的递归与非递归写法
非递归遍历：
void Traverse(LinkList L, void (*visit)(ElemType)) {
ListNode *p = L;
while (p) {
visit(p->data);
p = p->next;
}
}
递归删除最小值节点：
ListNode* DeleteMinRecursive(ListNode *L) {
if (!L) return NULL;
if (!L->next) {
free(L);
return NULL;
}
ListNode *min_prev = NULL, *p = L, *prev = NULL;
while (p->next) {
if (p->next->data < L->data)
min_prev = p;
p = p->next;
}
if (min_prev) {
ListNode *del = min_prev->next;
min_prev->next = del->next;
free(del);
} else {
ListNode *tmp = L->next;
free(L);
L = tmp;
}
return L;
}
非递归逆置：
LinkList ReverseList(LinkList L) {
ListNode *pre = NULL, *cur = L, *next;
while (cur) {
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
利用三指针技巧原地反转，时间O(n)，空间O(1)。
graph LR
A[原始链表] --> B[pre=NULL, cur=head]
B --> C{cur != NULL?}
C -- 是 --> D[next = cur->next]
D --> E[cur->next = pre]
E --> F[pre = cur]
F --> G[cur = next]
G --> C
C -- 否 --> H[新头结点pre]
该流程图展示了链表逆置的核心迭代逻辑，清晰表达了指针变换的过程。
2.4 线性表的应用对比与选型建议
2.4.1 顺序表与链表在不同场景下的性能比较
| 场景 | 推荐结构 | 理由 |
|---|---|---|
| 频繁查询、少量修改 | 顺序表 | 支持O(1)随机访问 |
| 频繁插入/删除 | 链表 | 无需移动元素 |
| 内存受限 | 顺序表 | 无额外指针开销 |
| 不确定数据量 | 动态顺序表或链表 | 支持弹性扩展 |
综合来看，选择应基于“读多写少”还是“写多读少”的业务特征。
2.4.2 实际工程中常见误用案例与改进方案
- 误用1 ：在链表中频繁按索引访问 → 应改用顺序表或引入索引缓存。
- 误用2 ：静态顺序表溢出 → 改为动态扩容机制。
- 误用3 ：未释放链表节点导致内存泄漏 → 使用智能指针或手动遍历释放。
合理评估需求，才能发挥线性表的最大效能。
3. 栈的“后进先出”机制与应用场景
3.1 栈的抽象定义与基本操作
3.1.1 栈的LIFO特性及其数学描述
栈（Stack）是一种受限的线性数据结构，其最显著的特征是 后进先出 （Last In, First Out, LIFO）。这种机制意味着最后一个被压入栈的数据元素将最先被弹出。这一行为类似于现实中的一叠盘子：你只能从顶部取走或放入盘子，不能从中部或底部直接操作。
从数学角度看，栈可以形式化地定义为一个有序集合 $ S = {a_1, a_2, …, a_n} $，其中所有操作仅限于在某一端进行——通常称为“栈顶”（Top），而另一端则称为“栈底”（Bottom）。设栈顶指针为 $ top $，初始时 $ top = -1 $（空栈），每当有新元素入栈时，$ top $ 自增；出栈时自减。若栈的最大容量为 $ MAXSIZE $，则当 $ top = MAXSIZE - 1 $ 时表示栈满。
更精确地，我们可以用三元组 $ (D, R, F) $ 来描述栈的抽象结构：
- $ D $：数据元素的有限集合；
- $ R $：唯一的前驱/后继关系，构成线性序列；
- $ F $：受限的操作集，仅允许在栈顶进行插入和删除。
LIFO 行为的本质来源于操作位置的唯一性。由于每次插入和删除都发生在同一端（栈顶），因此最近加入的元素总是处于最容易访问的位置。这与队列的 FIFO 形成鲜明对比，也决定了栈适用于需要回溯、嵌套处理等场景。
例如，在函数调用过程中，当前执行上下文必须等待内层函数返回才能继续，这就天然符合 LIFO 模式。再如浏览器的“返回”功能，用户浏览页面的历史记录以栈的形式保存，点击“返回”即相当于一次 pop 操作。
为了进一步理解 LIFO 的数学意义，考虑如下状态转移过程：
初始状态: Stack = [], top = -1
push(A): Stack = [A], top = 0
push(B): Stack = [A, B], top = 1
push(C): Stack = [A, B, C], top = 2
pop(): Stack = [A, B], top = 1, 返回 C
pop(): Stack = [A], top = 0, 返回 B
上述过程展示了栈如何通过单一指针控制数据流动，并始终保持最新元素优先被处理。正是这种简洁而强大的逻辑模型，使得栈成为程序设计中不可或缺的基础构件。
此外，LIFO 还隐含了“撤销”语义。比如文本编辑器中的 Ctrl+Z 功能，每按一次就撤销最近一次操作，本质上就是不断从操作历史栈中弹出条目。这类应用广泛依赖于栈的时间局部性优势——越是近期的操作，越可能被立即反向执行。
3.1.2 Push、Pop、Top等核心操作的形式化定义
栈的核心操作主要包括三个： Push （入栈）、 Pop （出栈）和 Top （查看栈顶元素）。这些操作构成了栈 ADT（Abstract Data Type）的基本接口，其行为必须严格遵循 LIFO 原则。下面给出它们的形式化定义与约束条件。
1. Push(x)
将元素 x 插入栈顶。
- 前置条件 ：栈未满（对于固定大小栈）
- 后置条件 ：
- 栈中元素数量增加 1；
- 新元素成为新的栈顶；
- 原栈顶变为次栈顶；
- 栈底不变。
形式化表示为：
S’ = S \cup {x}, \quad \text{top}’ = \text{top} + 1
其中 $ S $ 是原栈，$ S’ $ 是操作后的栈。
2. Pop()
删除并返回栈顶元素。
- 前置条件 ：栈非空
- 后置条件 ：
- 栈中元素数量减少 1；
- 原次栈顶成为新栈顶；
- 若原栈只有一个元素，则操作后栈为空。
形式化表示为：
S’ = S \setminus {\text{top_element}}, \quad \text{top}’ = \text{top} - 1
3. Top() / Peek()
仅读取栈顶元素，不修改栈结构。
- 前置条件 ：栈非空
- 后置条件 ：栈状态保持不变
这三个操作共同构成了栈的行为契约。任何实现都必须保证其原子性和正确性。例如，连续两次 Pop() 应该依次返回最后两个入栈的元素，且顺序相反。
下表总结了各操作的时间复杂度及常见异常情况：
| 操作 | 时间复杂度 | 可能异常 | 处理建议 |
|---|---|---|---|
| Push(x) | O(1) | 栈溢出（Overflow） | 动态扩容或抛出异常 |
| Pop() | O(1) | 栈下溢（Underflow） | 判空检查，避免非法访问 |
| Top() | O(1) | 栈为空 | 提供默认值或抛出 runtime_error |
在实际编程中，良好的栈实现应包含健全的错误检测机制。例如，在 C 语言中可以通过返回布尔类型指示操作是否成功：
typedef struct {
int data[100];
int top;
} Stack;
int push(Stack* s, int x) {
if (s->top >= 99) return 0; // 失败
s->data[++(s->top)] = x;
return 1; // 成功
}
int pop(Stack* s, int* x) {
if (s->top < 0) return 0;
*x = s->data[(s->top)--];
return 1;
}
代码逻辑逐行解读 ：
- 第4行：判断是否栈满，防止数组越界；
- 第6行：先递增top指针，再赋值，确保新元素位于正确位置；
- 第11行：检查栈空状态，避免负索引访问；
- 第13行：先取出值，再递减top，维护栈结构一致性。
此实现虽简单，但体现了栈操作的关键原则： 边界检查 + 指针管理 + 状态同步 。后续章节将进一步扩展至动态栈与链式栈，解决静态容量限制问题。
3.2 基于数组和链表的栈结构实现
3.2.1 顺序栈的边界判断与溢出处理
顺序栈使用数组作为底层存储结构，具有内存连续、访问高效的优势。但由于数组长度固定，容易面临“栈溢出”问题。因此，合理的边界判断与溢出处理策略至关重要。
一个典型的顺序栈结构体定义如下：
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE];
int top;
} SeqStack;
初始化时需将 top 设置为 -1 ，表示空栈：
void initStack(SeqStack* s) {
s->top = -1;
}
边界判断规则
| 条件 | 判断方式 | 含义 |
|---|---|---|
| 栈空 | top == -1 | 无元素可弹出 |
| 栈满 | top == MAX_SIZE-1 | 无法再压入新元素 |
| 元素个数 | top + 1 | 当前有效元素数量 |
每次 push 和 pop 都必须先进行条件判断：
int isFull(SeqStack* s) {
return s->top == MAX_SIZE - 1;
}
int isEmpty(SeqStack* s) {
return s->top == -1;
}
溢出处理策略
当 push 操作触发栈满时，常见的处理方法包括：
- 静态拒绝 ：直接返回错误码，要求调用者自行处理；
- 动态扩容 ：重新分配更大数组，复制原有数据；
- 自动增长 ：类似 C++
std::vector，按倍数扩容（如 2 倍）。
以下是一个支持动态扩容的 push 实现：
typedef struct {
int* data;
int top;
int capacity;
} DynamicStack;
void resize(DynamicStack* s) {
s->capacity *= 2;
s->data = (int*)realloc(s->data, s->capacity * sizeof(int));
}
int push(DynamicStack* s, int x) {
if (s->top == s->capacity - 1) {
resize(s);
}
s->data[++(s->top)] = x;
return 1;
}
参数说明 ：
-capacity：当前最大容量；
-realloc：重新分配内存，保留原有内容；
-resize()被调用时，容量翻倍，降低频繁分配开销。
该策略的空间利用率随使用量动态调整，平均时间复杂度仍为 O(1)，摊还分析成立。
流程图：顺序栈 push 操作
graph TD
A[开始 Push(x)] --> B{栈是否满?}
B -- 否 --> C[top++]
C --> D[data[top] = x]
D --> E[返回成功]
B -- 是 --> F[调用 resize()]
F --> C
此流程清晰展示了条件分支与扩容机制的结合，确保操作安全性与灵活性并存。
3.2.2 链式栈的结点管理与内存释放策略
链式栈采用单向链表实现，每个节点包含数据域和指向下一个节点的指针。相比顺序栈，它无需预设容量，动态伸缩能力强，适合不确定数据规模的场景。
节点结构定义如下：
typedef struct StackNode {
int data;
struct StackNode* next;
} StackNode;
typedef struct {
StackNode* top;
int size;
} LinkedStack;
初始化时头指针为空：
void initStack(LinkedStack* s) {
s->top = NULL;
s->size = 0;
}
入栈操作（Push）
int push(LinkedStack* s, int x) {
StackNode* node = (StackNode*)malloc(sizeof(StackNode));
if (!node) return 0; // 分配失败
node->data = x;
node->next = s->top;
s->top = node;
s->size++;
return 1;
}
逻辑分析 ：
- 第2行：动态申请内存，失败则返回 0；
- 第6行：新节点的next指向原栈顶，形成链接；
- 第7行：更新top指针，完成“头插”；
- 整个过程时间复杂度为 O(1)，无需遍历。
出栈操作（Pop）
int pop(LinkedStack* s, int* x) {
if (!s->top) return 0; // 空栈
StackNode* temp = s->top;
*x = temp->data;
s->top = temp->next;
free(temp);
s->size--;
return 1;
}
关键点 ：
- 必须先保存旧节点地址，再更新指针；
- 使用free()主动释放内存，防止泄漏；
- 若忘记释放，会导致严重内存问题。
内存释放策略
程序结束前应清空整个栈：
void clear(LinkedStack* s) {
while (s->top) {
StackNode* temp = s->top;
s->top = s->top->next;
free(temp);
}
s->size = 0;
}
该函数循环释放所有节点，确保资源完全回收。
对比表格：顺序栈 vs 链式栈
| 特性 | 顺序栈 | 链式栈 |
|---|---|---|
| 存储方式 | 数组 | 动态链表 |
| 空间预分配 | 是 | 否 |
| 扩展能力 | 有限（需扩容） | 无限（只要内存足够） |
| 访问速度 | 快（连续内存） | 稍慢（指针跳转） |
| 内存碎片 | 低 | 可能产生 |
| 实现复杂度 | 简单 | 稍复杂（需手动管理指针） |
| 适用场景 | 数据量已知、频繁访问 | 数据量未知、频繁增删 |
综上，链式栈更适合对内存灵活性要求高的系统级应用，如编译器符号表管理、表达式求值引擎等。
3.3 栈在表达式求值中的应用实践
3.3.1 中缀表达式转后缀表达式的算法流程
表达式求值是栈的经典应用场景之一。计算机更擅长处理 后缀表达式 （又称逆波兰表达式），因为它无需括号即可明确运算优先级。因此，常需将人类习惯的中缀表达式（如 3 + 4 * 2 ）转换为后缀形式（如 3 4 2 * + ）。
转换算法基于 Dijkstra 的调度场算法 （Shunting Yard Algorithm），主要依赖两个栈： 操作数栈 （此处不用）和 操作符栈 。
算法规则
- 从左到右扫描中缀表达式；
- 遇到操作数，直接输出；
- 遇到操作符，比较其与栈顶操作符的优先级：
- 若当前操作符优先级更高，入栈；
- 否则，弹出栈顶并输出，直到满足入栈条件； - 遇到左括号
(，无条件入栈； - 遇到右括号
)，持续弹出并输出，直到遇到(； - 扫描结束后，将剩余操作符全部弹出并输出。
示例： 3 + 4 * 2
| 字符 | 操作 | 输出队列 | 操作符栈 |
|---|---|---|---|
| 3 | 输出 | 3 | |
| + | 入栈 | 3 | + |
| 4 | 输出 | 3 4 | + |
| * | 优先级高于 +，入栈 | 3 4 | + * |
| 2 | 输出 | 3 4 2 | + * |
| end | 弹出所有 | 3 4 2 * + |
结果： 3 4 2 * +
优先级表
| 操作符 | 优先级 |
|---|---|
+ , - | 1 |
* , / | 2 |
( | 0 |
注意：左括号在栈外优先级最低，但在栈内不参与比较，仅作为标记。
3.3.2 利用栈进行后缀表达式计算的完整C代码实现
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#define MAX_EXPR 100
int evaluatePostfix(char* expr) {
int stack[MAX_EXPR];
int top = -1;
char* token = strtok(expr, " ");
while (token != NULL) {
if (isdigit(token[0])) {
stack[++top] = atoi(token);
} else {
int b = stack[top--];
int a = stack[top--];
switch (token[0]) {
case '+': stack[++top] = a + b; break;
case '-': stack[++top] = a - b; break;
case '*': stack[++top] = a * b; break;
case '/': stack[++top] = a / b; break;
}
}
token = strtok(NULL, " ");
}
return stack[top];
}
int main() {
char expr[] = "3 4 2 * +";
printf("Result: %d\n", evaluatePostfix(expr)); // Output: 11
return 0;
}
逻辑分析 ：
- 第8行：使用strtok按空格分割表达式；
- 第12行：判断是否为数字，是则压入栈；
- 第16–23行：遇到操作符，弹出两操作数，计算后压回；
- 注意操作数顺序：先弹出的是右操作数b；
- 最终栈中仅剩一个元素，即结果。
此实现假设输入格式规范，实际应用中应加入语法校验。
3.4 栈在函数调用与递归模拟中的深层应用
3.4.1 函数调用栈的工作原理剖析
现代程序运行依赖于 调用栈 （Call Stack），它是操作系统为每个线程分配的一块连续内存区域，用于跟踪函数调用层级。每当函数被调用，系统会创建一个 栈帧 （Stack Frame），包含：
- 返回地址
- 参数值
- 局部变量
- 临时寄存器备份
函数返回时，栈帧被销毁，控制权交还给调用者。
例如，以下调用链：
void funcC() { ... }
void funcB() { funcC(); }
void funcA() { funcB(); }
int main() { funcA(); }
对应的栈帧变化如下：
graph TD
subgraph Call Stack (Top to Bottom)
A["funcC()"] --> B["funcB()"]
B --> C["funcA()"]
C --> D["main()"]
end
随着 funcC 返回，其栈帧弹出， funcB 继续执行。这种机制天然契合 LIFO，保障了执行流的正确恢复。
3.4.2 使用显式栈模拟递归过程的经典案例（如阶乘、斐波那契数列）
递归本质上是隐式使用调用栈。我们可用显式栈模拟其行为，避免栈溢出风险。
阶乘模拟（非递归版）
#include <stdio.h>
typedef struct {
int n;
int result;
} Frame;
int factorial(int n) {
Frame stack[100];
int top = -1;
// 初始调用
stack[++top] = (Frame){n, 1};
while (top >= 0) {
Frame curr = stack[top--];
if (curr.n <= 1) {
// 基础情况
stack[++top] = (Frame){0, 1};
} else {
// 模拟递归调用 f(n-1)
stack[++top] = (Frame){curr.n - 1, 1};
// 回溯时乘以 n
stack[++top] = (Frame){0, curr.n};
}
}
return 1; // 略去完整实现，示意思想
}
此处简化展示思路，完整实现需记录中间状态与乘法时机。
通过手动管理栈帧，可实现尾递归优化甚至无限深度调用，突破系统栈限制。
4. 队列的“先进先出”机制与应用实践
在计算机科学中， 队列（Queue） 是一种典型的线性数据结构，其操作遵循“先进先出”（First In, First Out, FIFO）的基本原则。这种机制天然地模拟了现实世界中的排队行为——最早进入队列的元素将最先被处理。从操作系统任务调度到网络请求处理，再到图遍历算法的设计，队列作为一种基础而强大的抽象工具，广泛存在于各类系统和算法实现中。
队列的核心价值在于它提供了一种可控、有序的数据访问方式，尤其适用于需要按时间或优先级顺序处理事件的场景。例如，在多线程编程中，生产者-消费者模型依赖于阻塞队列来协调线程间的通信；在广度优先搜索（BFS）中，队列确保节点按照层级顺序被探索；而在Web服务器中，客户端请求通常被放入请求队列中等待处理。这些实际应用的背后，都离不开对队列结构深入理解和高效实现。
本章将系统剖析队列的逻辑结构与抽象定义，详细讲解顺序队列与循环队列的设计难点及其解决方案，并通过链式队列的动态内存管理展示灵活性优势。最后结合操作系统任务调度与图遍历两大典型应用场景，揭示队列如何作为底层支撑机制驱动复杂系统的运行。整个过程不仅涵盖理论建模，更注重C语言层面的具体编码实现、边界条件处理以及性能优化策略。
4.1 队列的逻辑结构与ADT定义
4.1.1 队列的FIFO原则与基本操作集
队列是一种受限的线性表，只允许在一端进行插入操作（称为 入队 ，enqueue），另一端进行删除操作（称为 出队 ，dequeue）。这一限制使得所有元素必须严格按照进入的先后顺序被处理，形成严格的FIFO行为模式。该特性使其区别于栈（LIFO）和其他无序集合类型。
为了形式化描述队列的行为，我们引入 抽象数据类型 （Abstract Data Type, ADT）的概念框架。ADT不关心具体实现细节，而是关注接口定义和操作语义。一个完整的队列ADT应包含以下基本操作：
| 操作名称 | 参数类型 | 返回值类型 | 功能说明 |
|---|---|---|---|
InitQueue | Queue* | void | 初始化空队列 |
Enqueue | Queue*, ElemType | Status | 将元素插入队尾 |
Dequeue | Queue , ElemType | Status | 删除队首元素并返回其值 |
Front | Queue* | ElemType* | 获取队首元素引用（不删除） |
IsEmpty | Queue* | Boolean | 判断队列是否为空 |
IsFull | Queue* | Boolean | 判断队列是否已满（仅适用于固定容量） |
Size | Queue* | int | 返回当前队列中元素个数 |
上述接口设计体现了模块化思想：使用者无需了解内部存储结构即可调用功能。例如，无论是基于数组还是链表实现，只要满足此ADT规范，上层代码均可无缝切换。
FIFO行为的形式化建模
设队列为 $ Q = \langle e_1, e_2, …, e_n \rangle $，其中 $ e_1 $ 是最早入队的元素，$ e_n $ 是最新入队的元素。当执行一次 Dequeue 操作时，结果为：
Q’ = \langle e_2, e_3, …, e_n \rangle, \quad \text{返回 } e_1
而一次 Enqueue(e_{n+1}) 后变为：
Q’’ = \langle e_1, e_2, …, e_n, e_{n+1} \rangle
这表明队列维护了一个严格的偏序关系，保证了数据处理的时间一致性。
4.1.2 入队、出队、判空、获取队首元素的标准接口
下面以C语言为例，定义一个通用的队列ADT接口。我们将使用指针封装的方式实现模块化设计，便于后期扩展不同底层结构。
// queue.h —— 队列ADT头文件声明
#ifndef QUEUE_H
#define QUEUE_H
#include <stdio.h>
#include <stdlib.h>
// 数据元素类型定义（可根据需求修改）
typedef int ElemType;
// 操作状态码
typedef enum {
SUCCESS = 0,
FAILURE = -1,
QUEUE_EMPTY = -2,
QUEUE_FULL = -3
} Status;
// 队列结构前向声明（隐藏实现细节）
typedef struct QueueNode QueueNode;
typedef struct Queue Queue;
// 函数接口声明
Status InitQueue(Queue** q);
Status Enqueue(Queue* q, ElemType x);
Status Dequeue(Queue* q, ElemType* x);
ElemType* Front(Queue* q);
int IsEmpty(Queue* q);
int IsFull(Queue* q);
int Size(Queue* q);
void DestroyQueue(Queue** q);
#endif // QUEUE_H
代码逻辑逐行解读：
- 第7–11行 ：定义
ElemType为整型，方便示例演示；实际项目中可替换为结构体或其他复合类型。 - 第14–19行 ：自定义状态码枚举，增强错误处理能力。相比单纯返回布尔值，能更精确反映失败原因。
- 第22–23行 ：使用不透明指针（opaque pointer）技术，将具体结构体定义放在
.c文件中，实现信息隐藏。 - 第26–35行 ：标准队列操作函数原型，采用二级指针初始化（如
InitQueue(Queue**)）支持动态分配；Front返回指针以便直接读取但不移除元素。
该接口设计具备良好的可移植性和安全性，是工业级队列实现的基础模板。
接口调用流程图（Mermaid）
graph TD
A[程序启动] --> B[调用 InitQueue()]
B --> C{成功?}
C -->|是| D[执行 Enqueue 插入数据]
C -->|否| Z[报错退出]
D --> E[调用 IsEmpty 判断状态]
E --> F{非空?}
F -->|是| G[调用 Dequeue 取出数据]
F -->|否| H[提示队列为空]
G --> I[调用 Front 查看下一个元素]
I --> J[继续操作或销毁队列]
J --> K[调用 DestroyQueue 释放资源]
该流程图清晰展示了典型队列使用的生命周期：初始化 → 插入/删除 → 查询状态 → 销毁。每个步骤均对应ADT中的标准接口，体现了高内聚、低耦合的设计理念。
接下来，我们可以基于此接口分别实现顺序队列与链式队列，从而在不同场景下权衡空间效率与时间性能。
4.2 顺序队列与循环队列的实现技巧
4.2.1 普通顺序队列的假溢出问题分析
顺序队列使用数组作为底层存储结构，具有内存连续、访问速度快的优点。然而，若不做特殊处理，会出现所谓的“ 假溢出 ”现象：即使数组未完全填满，也无法继续入队。
考虑如下简单实现：
// 简化的顺序队列结构定义
#define MAXSIZE 100
struct Queue {
ElemType data[MAXSIZE];
int front; // 队首索引
int rear; // 队尾索引（指向下一个插入位置）
};
Status Enqueue(SeqQueue* q, ElemType x) {
if (q->rear >= MAXSIZE) {
return QUEUE_FULL; // 错误：无法判断是否真满
}
q->data[q->rear++] = x;
return SUCCESS;
}
Status Dequeue(SeqQueue* q, ElemType* x) {
if (q->front == q->rear) {
return QUEUE_EMPTY;
}
*x = q->data[q->front++];
return SUCCESS;
}
假溢出实例分析：
假设 MAXSIZE=5 ，依次执行：
1. 入队 A, B, C → rear=3
2. 出队 A, B → front=2
3. 此时仍有两个空位（索引0~1），但后续入队仍可能因 rear==5 被拒绝。
即：虽然物理空间有剩余，但由于 front 不归零，导致可用区域碎片化。
这个问题的本质是 单向移动指针造成的空间浪费 。解决思路有两种：
1. 每次出队后整体前移元素 （低效，O(n)）
2. 采用循环队列结构
前者破坏了O(1)的出队效率，不可取；后者则是主流解决方案。
4.2.2 循环队列的下标计算与满/空状态判定方法
循环队列通过将数组“首尾相连”的方式解决假溢出问题。关键在于利用模运算（%）实现索引回绕。
结构定义与核心变量
typedef struct {
ElemType* data; // 动态数组
int front; // 队首索引
int rear; // 队尾索引（下一个插入位置）
int capacity; // 容量
int count; // 当前元素数量（推荐方案）
} CircularQueue;
注：也可不用
count，改用特殊标记区分满/空，但会牺牲一个存储单元。
核心操作实现
Status InitCircularQueue(CircularQueue* q, int cap) {
q->data = (ElemType*)malloc(cap * sizeof(ElemType));
if (!q->data) return FAILURE;
q->front = 0;
q->rear = 0;
q->capacity = cap;
q->count = 0;
return SUCCESS;
}
Status Enqueue(CircularQueue* q, ElemType x) {
if (q->count == q->capacity) {
return QUEUE_FULL;
}
q->data[q->rear] = x;
q->rear = (q->rear + 1) % q->capacity;
q->count++;
return SUCCESS;
}
Status Dequeue(CircularQueue* q, ElemType* x) {
if (q->count == 0) {
return QUEUE_EMPTY;
}
*x = q->data[q->front];
q->front = (q->front + 1) % q->capacity;
q->count--;
return SUCCESS;
}
参数说明与逻辑分析：
-
front和rear初始化为0 ：初始状态下队列为空。 -
rear = (rear + 1) % capacity：实现索引回绕。例如当rear == capacity-1时，加1后自动回到0。 -
count字段的作用 ：避免“满”与“空”状态混淆。否则front == rear既表示空也可能是满。 - 时间复杂度 ：所有操作均为 O(1)，包括扩容时若采用倍增策略亦可摊销为 O(1)。
满/空判断对比表
| 方法 | 判空条件 | 判满条件 | 优缺点说明 |
|---|---|---|---|
使用 count 计数 | count == 0 | count == capacity | 实现清晰，推荐做法 |
| 浪费一个存储单元 | front == rear | (rear+1)%cap == front | 简洁但牺牲空间 |
| 设置标志位 flag | front==rear && !flag | front==rear && flag | 复杂，易出错 |
推荐使用第一种方法（带计数器），因其逻辑最清晰且易于调试。
循环队列工作原理流程图（Mermaid）
graph LR
A[front=0, rear=0] --> B[Enqueue: 插入A]
B --> C[rear=(0+1)%5=1]
C --> D[Enqueue: 插入B,C,D]
D --> E[rear=4]
E --> F[Enqueue: 插入E → rear=0]
F --> G[Dequeue: 取出A → front=1]
G --> H[Dequeue: 取出B → front=2]
H --> I[继续插入F → rear=(0+1)%5=1]
I --> J[形成循环缓冲区]
此图展示了索引如何在数组边界处回绕，有效利用全部空间，彻底消除假溢出问题。
4.3 链式队列的设计与动态管理
4.3.1 带头结点与不带头结点的链队实现差异
链式队列采用链表结构实现，天然支持动态扩容，适合不确定数据规模的场景。根据是否设置“头结点”（dummy node），可分为两种实现方式。
结构定义对比
// 不带头结点的链队
struct ListNode {
ElemType data;
struct ListNode* next;
};
typedef struct {
struct ListNode* front; // 指向第一个实际节点
struct ListNode* rear; // 指向最后一个节点
} LinkedQueue_NoDummy;
// 带头结点的链队
typedef struct {
struct ListNode* head; // 指向头结点（不存数据）
struct ListNode* rear; // 指向最后一个实际节点
} LinkedQueue_WithDummy;
| 特性 | 不带头结点 | 带头结点 |
|---|---|---|
| 初始状态 | front = NULL, rear = NULL | head->next = NULL, rear = head |
| 空队判断 | front == NULL | head->next == NULL |
| 插入首个元素 | 需单独处理指针赋值 | 统一处理，无需分支 |
| 内存开销 | 少一个节点 | 多一个无效头结点 |
| 编码复杂度 | 较高（需判断NULL） | 较低（统一逻辑） |
实现示例：带头结点的链队
Status InitLinkedQueue(LinkedQueue_WithDummy* q) {
q->head = (ListNode*)malloc(sizeof(ListNode));
if (!q->head) return FAILURE;
q->head->next = NULL;
q->rear = q->head;
return SUCCESS;
}
Status Enqueue(LinkedQueue_WithDummy* q, ElemType x) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
if (!newNode) return FAILURE;
newNode->data = x;
newNode->next = NULL;
q->rear->next = newNode;
q->rear = newNode;
return SUCCESS;
}
Status Dequeue(LinkedQueue_WithDummy* q, ElemType* x) {
if (q->head->next == NULL) {
return QUEUE_EMPTY;
}
ListNode* tmp = q->head->next;
*x = tmp->data;
q->head->next = tmp->next;
if (tmp == q->rear) { // 最后一个元素被删除
q->rear = q->head;
}
free(tmp);
return SUCCESS;
}
关键点解析：
- 第18行 ：新节点挂接在
rear后，保持 FIFO 顺序。 - 第27–34行 ：出队后检查是否删到最后一个元素，若是则更新
rear指回头结点。 - 内存安全 ：每次出队必须
free节点，防止泄漏。
4.3.2 入队出队操作的指针调整细节与异常处理
链式队列的关键在于指针的正确维护。任何一处疏漏都会导致内存泄漏、野指针或逻辑错误。
异常情况处理表
| 操作 | 异常类型 | 处理方式 |
|---|---|---|
Enqueue | malloc失败 | 返回FAILURE，上层决定重试或终止 |
Dequeue | 队列为空 | 返回QUEUE_EMPTY，避免解引用NULL |
Destroy | 非空队列 | 遍历释放所有节点后再释放头结点 |
void DestroyLinkedQueue(LinkedQueue_WithDummy* q) {
while (q->head->next) {
ListNode* tmp = q->head->next;
q->head->next = tmp->next;
free(tmp);
}
free(q->head);
q->head = NULL;
q->rear = NULL;
}
此函数确保所有动态分配的节点都被回收，符合RAII原则。
4.4 队列在实际系统中的典型应用
4.4.1 操作系统任务调度中的就绪队列管理
现代操作系统使用 就绪队列 （Ready Queue）管理处于就绪状态的进程。每个CPU核心维护一个或多个队列，调度器从中选择下一个执行的进程。
Linux中常见的是 完全公平调度器 （CFS），虽主要基于红黑树，但在某些子系统（如实时任务）仍使用FIFO队列。
简化模型如下：
typedef struct PCB {
int pid;
char state[10]; // "ready", "running"
struct PCB* next;
} PCB;
PCB* ready_queue_front = NULL;
PCB* ready_queue_rear = NULL;
void add_to_ready_queue(PCB* proc) {
proc->next = NULL;
if (!ready_queue_front) {
ready_queue_front = proc;
ready_queue_rear = proc;
} else {
ready_queue_rear->next = proc;
ready_queue_rear = proc;
}
}
PCB* schedule_next() {
if (!ready_queue_front) return NULL;
PCB* next = ready_queue_front;
ready_queue_front = next->next;
if (!ready_queue_front) ready_queue_rear = NULL;
return next;
}
该机制保证了任务按提交顺序被处理，适用于批处理系统。
4.4.2 广度优先搜索（BFS）中队列的角色与编码实现
BFS依赖队列实现层级遍历。以下是二叉树层次遍历的完整实现：
#include "queue.h"
void LevelOrderTraversal(TreeNode* root) {
if (!root) return;
Queue* q;
InitQueue(&q);
Enqueue(q, (long)root); // 存储指针地址
while (!IsEmpty(q)) {
TreeNode* curr;
Dequeue(q, (ElemType*)&curr);
printf("%d ", curr->val);
if (curr->left) Enqueue(q, (long)curr->left);
if (curr->right) Enqueue(q, (long)curr->right);
}
DestroyQueue(&q);
}
执行流程分析：
- 根节点入队
- 循环取出队首并访问
- 左右子节点依次入队
- 直至队列为空
此算法时间复杂度 O(n)，空间复杂度 O(w)，w为最大宽度。
BFS流程图（Mermaid）
graph TB
A[根节点入队] --> B{队列非空?}
B -->|是| C[取出队首节点]
C --> D[访问该节点]
D --> E[左孩子入队]
D --> F[右孩子入队]
E --> B
F --> B
B -->|否| G[结束遍历]
该图直观展示了BFS如何借助队列实现“层层推进”的搜索策略。
综上所述，队列不仅是基础数据结构，更是连接理论与工程实践的重要桥梁。掌握其多种实现方式及典型应用场景，是构建高性能软件系统不可或缺的能力。
5. 二叉树与平衡树结构与操作
5.1 二叉树的基本概念与存储结构
5.1.1 二叉树的递归定义与性质分析
二叉树是n（n ≥ 0）个有限节点的集合，它或者为空树，或者由一个根节点加上两棵互不相交的、分别称为左子树和右子树的二叉树组成。这种 递归定义 使得二叉树天然适合用递归算法进行处理。
一个高度为 $ h $ 的满二叉树拥有 $ 2^h - 1 $ 个节点；而完全二叉树则是在前 $ h-1 $ 层为满层，最后一层从左到右连续填充的二叉树。这些结构性质直接影响存储效率与遍历性能。
常见性质包括：
- 第 $ i $ 层最多有 $ 2^{i-1} $ 个节点（$ i \geq 1 $）
- 深度为 $ k $ 的二叉树最多有 $ 2^k - 1 $ 个节点
- 对于任意一棵二叉树，若其叶子数为 $ n_0 $，度为2的节点数为 $ n_2 $，则有 $ n_0 = n_2 + 1 $
这些数学关系在构建高效索引结构时具有重要意义。
5.1.2 二叉链表与三叉链表的C语言表示方法
在C语言中，最常用的二叉树存储方式是 二叉链表 ，每个节点包含数据域和两个指针域：
typedef struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
该结构简洁明了，适用于大多数遍历与搜索场景。但在需要频繁向上追溯父节点的操作中（如后序非递归遍历或删除操作），缺乏父指针会增加时间开销。
为此可采用 三叉链表 改进：
typedef struct ThreadNode {
int data;
struct ThreadNode* left;
struct ThreadNode* right;
struct ThreadNode* parent; // 新增父指针
} ThreadNode;
| 存储方式 | 空间复杂度 | 是否支持反向查找 | 典型应用场景 |
|---|---|---|---|
| 二叉链表 | O(n) | 否 | 遍历、BST实现 |
| 三叉链表 | O(n) + O(n)指针 | 是 | AVL树、红黑树 |
| 数组存储（完全二叉树） | O(n) | 是（通过下标计算） | 堆结构 |
例如，在堆排序中使用数组存储完全二叉树，父子节点可通过如下公式快速定位：
- 父节点下标： parent(i) = (i - 1) / 2
- 左孩子下标： left(i) = 2 * i + 1
- 右孩子下标： right(i) = 2 * i + 2
这种方式极大提升了访问速度，但仅适用于形态规则的树结构。
此外，还可引入线索二叉树（Threaded Binary Tree），利用空指针指向中序前驱或后继，从而实现无需栈的遍历。
5.2 二叉树的遍历算法与实现
5.2.1 先序、中序、后序遍历的递归与非递归实现
三种深度优先遍历的核心区别在于 根节点的访问时机 ：
- 先序（DLR） ：根 → 左 → 右
- 中序（LDR） ：左 → 根 → 右
- 后序（LRD） ：左 → 右 → 根
递归实现示例（以中序为例）：
void inorder_recursive(TreeNode* root) {
if (root == NULL) return;
inorder_recursive(root->left); // 访问左子树
printf("%d ", root->data); // 处理根节点
inorder_recursive(root->right); // 访问右子树
}
递归版本代码清晰，但存在函数调用开销大、栈溢出风险等问题，尤其在偏斜树上表现不佳。
非递归实现（使用显式栈模拟调用过程）：
#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK 100
typedef struct {
TreeNode* items[MAX_STACK];
int top;
} Stack;
void push(Stack* s, TreeNode* node) {
if (s->top < MAX_STACK - 1) {
s->items[++(s->top)] = node;
}
}
TreeNode* pop(Stack* s) {
return s->top >= 0 ? s->items[(s->top)--] : NULL;
}
void inorder_iterative(TreeNode* root) {
Stack stack = {.top = -1};
TreeNode* curr = root;
while (curr != NULL || stack.top != -1) {
while (curr != NULL) {
push(&stack, curr);
curr = curr->left; // 沿左链入栈
}
curr = pop(&stack);
printf("%d ", curr->data); // 输出当前节点
curr = curr->right; // 转向右子树
}
}
执行逻辑说明 ：此非递归中序遍历通过栈保存待处理的“根”节点，优先深入左子树到底部，再逐层弹出并转向右子树，完美模拟递归行为。
5.2.2 层次遍历中队列的引入与节点访问控制
层次遍历（广度优先遍历）需借助 队列 实现：
#include "queue.h" // 假设已实现链式队列
void level_order(TreeNode* root) {
if (!root) return;
Queue q;
init_queue(&q);
enqueue(&q, root);
while (!is_empty(&q)) {
TreeNode* node = dequeue(&q);
printf("%d ", node->data);
if (node->left) enqueue(&q, node->left);
if (node->right) enqueue(&q, node->right);
}
}
该策略确保每一层节点按从左至右顺序输出，常用于求树高、判断完全二叉树等场景。
mermaid格式流程图描述遍历过程：
graph TD
A[根节点入队]
B{队列非空?}
C[出队并访问]
D[左孩子入队]
E[右孩子入队]
F[继续循环]
A --> B
B -->|是| C
C --> D
C --> E
D --> F
E --> F
F --> B
B -->|否| G[结束]
该模型清晰展示了BFS的迭代推进机制。
简介：《数据结构(C语言版)》是严蔚敏和吴伟民编著的经典教材，系统讲解线性表、栈、队列、树、图、散列表等核心数据结构，并结合C语言实现，配以丰富实例与习题。本书深入浅出，涵盖排序与查找算法，帮助读者掌握数据的高效组织与操作方法，提升编程与算法设计能力，是计算机科学学习和软件开发实践中的必备参考书。
更多推荐
17
0- 0
已为社区贡献6条内容
所有评论(0)