第1章：链表
问题引入
在日常生活中，我们常会遇到需要动态调整队伍大小的场景。例如，幼儿园老师带小朋友们排队出行：
老师 -> [小明] -> [小红] -> [小强] -> nullptr
如果采用“排成一排固定椅子”（类似于静态数组）的方式，一旦有一个新小朋友要加入到队伍中间，所有后面的小朋友都必须向后挪动一个座位；同样，如果一个小明中途离开，后面的所有人都需要向前挪动一步。这种频繁的挪动在计算机中需要进行大量的内存数据拷贝，效率较低。
为了解决这个问题，老师让小朋友们“手拉手”。每个小朋友（结点）只需要记住他后面是谁。 - 当新小朋友 [小刚] 想要插队到 [小明] 和 [小红] 之间时，只需要： 1. [小明] 松开拉着 [小红] 的手。 2. [小明] 去拉住 [小刚] 的手。 3. [小刚] 去拉住 [小红] 的手。 - 这个过程中，其他小朋友的位置完全不需要发生任何改变。这就是链表（Linked List）的核心思想：通过指针（手）将不连续的内存空间（小朋友）串联起来，从而实现高效的动态插入与删除。
概念介绍
1. 链表的核心要素
- 结点（Node）：链表中的基本单位，包含两部分：
- 数据域（Data）：存储具体的数据。
- 指针域（Next）：存储下一个结点的内存地址。
- 头指针（Head）：指向链表第一个结点的指针。通过头指针可以遍历整条链表。
- 空指针（nullptr）：链表末尾结点的指针域指向空，表示链表的结束。
内存地址: 0x100 0x250 0x300
+---------+ +---------+ +---------+
Head -> | 10 |0x250| -> | 20 |0x300| -> | 30 |nullptr|
+---------+ +---------+ +---------+
2. 动态内存分配
在 C++ 中，我们使用 new 运算符在堆区（Heap）动态申请内存，使用 delete 释放内存，避免内存泄漏。
3. 完整的动态单链表 C++ 实现
以下是标准的、不带头结点的动态单链表实现，包含了建表（头插法、尾插法）、遍历、插入、删除、查找、清空等所有核心操作。
#include <iostream>
// 定义链表结点结构体
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
// 链表类定义
class LinkedList {
private:
Node* head;
public:
LinkedList() : head(nullptr) {}
// 1. 头插法建表：新结点始终插入到头部
void insertHead(int val) {
Node* newNode = new Node(val);
newNode->next = head;
head = newNode;
}
// 2. 尾插法建表：新结点始终插入到尾部
void insertTail(int val) {
Node* newNode = new Node(val);
if (!head) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next) {
temp = temp->next;
}
temp->next = newNode;
}
// 3. 在指定位置插入（从0开始计数）
bool insertAt(int index, int val) {
if (index < 0) return false;
if (index == 0) {
insertHead(val);
return true;
}
Node* temp = head;
for (int i = 0; temp && i < index - 1; ++i) {
temp = temp->next;
}
if (!temp) return false; // 索引越界
Node* newNode = new Node(val);
newNode->next = temp->next;
temp->next = newNode;
return true;
}
// 4. 删除指定位置的结点
bool deleteAt(int index) {
if (!head || index < 0) return false;
if (index == 0) {
Node* toDelete = head;
head = head->next;
delete toDelete;
return true;
}
Node* temp = head;
for (int i = 0; temp->next && i < index - 1; ++i) {
temp = temp->next;
}
if (!temp->next) return false; // 索引越界
Node* toDelete = temp->next;
temp->next = toDelete->next;
delete toDelete;
return true;
}
// 5. 查找值，返回索引（若未找到返回 -1）
int search(int val) const {
Node* temp = head;
int index = 0;
while (temp) {
if (temp->data == val) return index;
temp = temp->next;
index++;
}
return -1;
}
// 6. 显示链表内容
void display() const {
Node* temp = head;
while (temp) {
std::cout << temp->data << " -> ";
temp = temp->next;
}
std::cout << "nullptr\n";
}
// 7. 清空链表释放内存
void clear() {
Node* temp = head;
while (temp) {
Node* nextNode = temp->next;
delete temp;
temp = nextNode;
}
head = nullptr;
}
~LinkedList() {
clear();
}
};
4. 静态链表与栈优化
在某些不支持指针的旧语言、或在追求极致性能竞赛（如算法竞赛避免 new 的高额开销）时，我们常用数组来模拟链表（即静态链表）。
为了避免无序申请带来的空间浪费，我们引入栈优化：用一个栈结构保存当前所有闲置的数组下标。当需要新建结点时，从栈顶弹出一个可用下标（O(1)）；当删除结点时，将该下标压回栈中（O(1)）。
#include <vector>
#include <stack>
#include <iostream>
class StaticLinkedList {
private:
struct StaticNode {
int data;
int next; // 用数组下标代替指针，-1表示空指针
};
std::vector<StaticNode> nodes;
std::stack<int> free_list; // 栈优化：管理空闲内存块
int head;
public:
StaticLinkedList(int capacity) {
nodes.resize(capacity);
for (int i = 0; i < capacity; ++i) {
free_list.push(i); // 初始化所有下标为空闲
}
head = -1;
}
// 申请结点空间
int allocateNode(int val) {
if (free_list.empty()) {
std::cerr << "Error: Out of Static Memory!\n";
return -1;
}
int idx = free_list.top();
free_list.pop();
nodes[idx].data = val;
nodes[idx].next = -1;
return idx;
}
// 释放结点空间
void deallocateNode(int idx) {
free_list.push(idx);
}
// 头插法
void insertHead(int val) {
int idx = allocateNode(val);
if (idx == -1) return;
nodes[idx].next = head;
head = idx;
}
void display() {
int curr = head;
while (curr != -1) {
std::cout << nodes[curr].data << " -> ";
curr = nodes[curr].next;
}
std::cout << "nullptr\n";
}
};
5. 指针链表与数组静态链表的性能对比
| 特性 | 指针链表（动态内存） | 数组链表（静态模拟） |
|---|---|---|
| 内存分配方式 | 运行期在堆区动态申请（new） |
预先在栈区或静态区开辟连续大数组 |
| 分配耗时 | 较慢（涉及操作系统底层堆内存寻址） | 极快（仅为数组下标变换） |
| CPU缓存友好度 | 极差 | 较好 |
CPU缓存局部性（Cache Locality）分析
CPU 访问内存时，并非一次只读一个字节，而是会将该字节所在的整块数据（Cache Line，通常为 64 字节）一次性加载到高速缓存中。
- 指针链表的结点物理地址通常是离散分布的。遍历链表时，每次 temp = temp->next 极易引发 Cache Miss（缓存未命中），导致 CPU 必须去主存中读取数据。
- 静态链表存储在连续的数组中。虽然逻辑结构上结点的 next 指向可能在数组中跳跃，但因其物理上仍局限在同一块大数组内，被装入 Cache 的概率显著高于离散的堆结点，因此在海量数据遍历时通常具有更优的响应时间。
它的性质
- 非连续存储：物理存储位置不连续，逻辑顺序通过指针维系。
- 动态性：无需预先分配固定大小的空间，随用随申请。
- 操作时间复杂度：
- 访问/查找第 $i$ 个元素：$O(N)$
- 已知前驱结点，插入/删除指定结点：$O(1)$
解决的问题
典型应用：一元多项式相加
一元多项式如 $A(x) = 5x^{10} + 3x^2 + 1$。因为多项式的项数是不确定的，且可能存在大量的“零系数项”（例如只有 $x^{100}$ 和常数项），如果用数组存会造成极大的空间浪费。链表非常适合存储这种稀疏的多项式。
C++ 核心代码实现
#include <iostream>
struct PolyNode {
int coef; // 系数
int exp; // 指数
PolyNode* next;
PolyNode(int c, int e) : coef(c), exp(e), next(nullptr) {}
};
// 两个有序（指数递减）多项式链表相加
PolyNode* addPolynomials(PolyNode* p1, PolyNode* p2) {
PolyNode dummy(0, 0); // 哑结点
PolyNode* tail = &dummy;
while (p1 && p2) {
if (p1->exp > p2->exp) {
tail->next = new PolyNode(p1->coef, p1->exp);
p1 = p1->next;
tail = tail->next;
} else if (p1->exp < p2->exp) {
tail->next = new PolyNode(p2->coef, p2->exp);
p2 = p2->next;
tail = tail->next;
} else {
int sumCoef = p1->coef + p2->coef;
if (sumCoef != 0) {
tail->next = new PolyNode(sumCoef, p1->exp);
tail = tail->next;
}
p1 = p1->next;
p2 = p2->next;
}
}
// 处理剩余结点
while (p1) {
tail->next = new PolyNode(p1->coef, p1->exp);
p1 = p1->next;
tail = tail->next;
}
while (p2) {
tail->next = new PolyNode(p2->coef, p2->exp);
p2 = p2->next;
tail = tail->next;
}
return dummy.next;
}
它的缺点
- 不支持随机访问：无法像数组那样通过
arr[i]在 $O(1)$ 时间定位元素，必须从头指针顺藤摸瓜。 - 额外内存开销：每个结点都要额外存储一个或多个指针域，当数据域体积较小时，指针所占的内存比重较大。
- 容易造成内存碎片：频繁申请和释放小块堆内存，会导致系统内存碎片化，降低分配效率。
学习难点
- 指针“断链”与丢失：在插入或删除结点时，改变指针指向的先后顺序极其重要。例如，在 $A \to B$ 中间插入 $X$。必须先让 $X \to B$（
X->next = A->next），再让 $A \to X$（A->next = X）。如果顺序反了，先执行了A->next = X，那么 $B$ 結点的地址就再也找不到了。 - 边界条件处理：链表为空时、只有一个结点时、对头结点进行操作时，往往需要写额外的
if分支。设计代码时引入哑结点（Dummy Node）可以有效合并这些特例。
课后提问
- 学生成绩管理系统：请利用本章学习的动态链表，设计一个简易成绩系统。支持添加学生（学号、姓名、成绩）、删除学生、根据学号查找，并计算全体学生的平均分。
- 双向链表设计：单链表只能单向寻找后继。请设计一个双向链表结点
DoubleNode（包含prev和next两个指针），并实现其插入和反向遍历。 - 一元多项式乘法：基于本章的多项式加法，尝试利用链表实现两个一元多项式的乘法算法。
- 性能实测：请编写测试程序，在你的电脑上比较“指针链表”与“数组静态链表”在进行 100,000 次随机插入和删除操作时的耗时差异，加深对高速缓存局部性的理解。
第二章：堆栈
问题引入
在装弹枪械中，子弹是如何被压入弹匣并射出的？
压入子弹 (Push): [ 子弹3 ] -> [ 子弹2 ] -> [ 子弹1 ] (最先压入)
---------------------------------
弹匣开口 (栈顶): => [ 子弹3 ] 最先被击发 (Pop)
最先装入弹匣的子弹被压到了弹匣最底部，而最后装入的一颗子弹则停留在最上方，也是最先被射击出去的那一颗。这种后进先出（Last In, First Out，简称 LIFO）的逻辑模型，在计算机科学中被称为堆栈（Stack）。
概念介绍
1. 核心概念
- 栈顶（Top）：栈中允许进行插入和删除操作的唯一一端。
- 栈底（Bottom）：固定不动、不允许操作的另一端。
- 入栈（Push）：将新元素加入栈顶。
- 出栈（Pop）：将栈顶元素移出。
空栈 Push(10) Push(20) Pop()
| | | | | 20 |<-Top | |
| | | | |------| |------|
| | | 10 |<-Top | 10 | | 10 |<-Top
+------+ +------+ +------+ +------+
2. 指针仿真堆栈（链式栈）
利用链表头部作为栈顶，可以实现无容量限制的动态栈。
#include <iostream>
#include <stdexcept>
class LinkStack {
private:
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
Node* topNode;
public:
LinkStack() : topNode(nullptr) {}
// 入栈
void push(int val) {
Node* newNode = new Node(val);
newNode->next = topNode;
topNode = newNode;
}
// 出栈
void pop() {
if (isEmpty()) {
throw std::underflow_error("Stack Underflow");
}
Node* temp = topNode;
topNode = topNode->next;
delete temp;
}
// 取栈顶元素
int top() const {
if (isEmpty()) {
throw std::underflow_error("Stack is empty");
}
return topNode->data;
}
bool isEmpty() const {
return topNode == nullptr;
}
~LinkStack() {
while (!isEmpty()) {
pop();
}
}
};
3. 数组仿真堆栈（顺序栈）
顺序栈内部使用一块连续的数组，并通过一个整型变量 topIdx 维护当前栈顶的索引。
class ArrayStack {
private:
int* arr;
int capacity;
int topIdx; // 始终指向栈顶元素
public:
ArrayStack(int cap) : capacity(cap), topIdx(-1) {
arr = new int[capacity];
}
void push(int val) {
if (topIdx >= capacity - 1) {
std::cerr << "Stack Overflow\n";
return;
}
arr[++topIdx] = val;
}
void pop() {
if (isEmpty()) {
std::cerr << "Stack Underflow\n";
return;
}
--topIdx;
}
int top() const {
if (isEmpty()) {
throw std::underflow_error("Stack is empty");
}
return arr[topIdx];
}
bool isEmpty() const {
return topIdx == -1;
}
~ArrayStack() {
delete[] arr;
}
};
它的性质
- 后进先出（LIFO）：访问受到严格限制，只允许在栈顶一端操作。
- 时间复杂度：基本的
push、pop、top均为 $O(1)$ 操作。 - 空间开销：顺序栈具有固定大小，可能浪费空间或发生溢出；链式栈虽然没有大小限制，但需要保存额外的结点指针。
解决的问题
1. 数制转换（除基取余法）
将十进制数 $N$ 转换为 $d$ 进制数。基本步骤为将 $N$ 连续除以 $d$ 并取其余数。最先算出来的余数其实是目标进制数的低位，最后算出来的余数才是高位。利用栈先存起来再全部弹出，刚好完成逆序输出。
#include <stack>
#include <iostream>
void decimalToDBase(int num, int d) {
std::stack<int> s;
while (num > 0) {
s.push(num % d);
num /= d;
}
while (!s.empty()) {
int val = s.top();
if (val < 10) std::cout << val;
else std::cout << (char)('A' + val - 10); // 兼容十六进制
s.pop();
}
std::cout << "\n";
}
2. 行编辑程序
用户在终端输入字符时，输入 # 代表退格（Backspace），输入 @ 代表清除当前整行。栈非常适合处理这种“回溯撤销”操作。
#include <string>
std::string lineEditor(const std::string& rawInput) {
std::stack<char> s;
for (char ch : rawInput) {
if (ch == '#') {
if (!s.empty()) s.pop(); // 退格
} else if (ch == '@') {
while (!s.empty()) s.pop(); // 清空整行
} else {
s.push(ch);
}
}
std::string cleanStr = "";
while (!s.empty()) {
cleanStr = s.top() + cleanStr; // 逆序组合回原字符串
s.pop();
}
return cleanStr;
}
3. 中缀表达式转后缀表达式（逆波兰式）并求值
由于中缀表达式（如 3 + 4 * 2）含有运算符优先级和括号，直接计算需要扫描多次。后缀表达式（如 3 4 2 * +）消除了括号，计算机仅需从左到右扫描一次即可利用栈完成求值。
转换与求值过程对照表（中缀：a + b * c）
| 扫描字符 | 运算符栈内状态 | 输出（后缀表达式） | 备注 |
|---|---|---|---|
a |
空 | a |
操作数直接输出 |
+ |
[+] |
a |
压入栈 |
b |
[+] |
a b |
操作数直接输出 |
* |
[+, *] |
a b |
* 优先级高于 +，直接压栈 |
c |
[+, *] |
a b c |
操作数直接输出 |
| 结束 | 空 | a b c * + |
依次弹出栈中所有运算符 |
C++ 完整求值代码实现（含中缀转后缀与后缀计算）
#include <iostream>
#include <stack>
#include <string>
#include <cctype>
// 获取操作符优先级
int getPriority(char op) {
if (op == '+' || op == '-') return 1;
if (op == '*' || op == '/') return 2;
return 0;
}
// 1. 中缀表达式转后缀表达式
std::string infixToPostfix(const std::string& infix) {
std::stack<char> s;
std::string postfix = "";
for (char ch : infix) {
if (std::isspace(ch)) continue;
if (std::isdigit(ch)) {
postfix += ch; // 简单起见，这里假设个位数
postfix += " ";
} else if (ch == '(') {
s.push(ch);
} else if (ch == ')') {
while (!s.empty() && s.top() != '(') {
postfix += s.top();
postfix += " ";
s.pop();
}
if (!s.empty()) s.pop(); // 弹出 '('
} else { // 运算符
while (!s.empty() && getPriority(s.top()) >= getPriority(ch)) {
postfix += s.top();
postfix += " ";
s.pop();
}
s.push(ch);
}
}
while (!s.empty()) {
postfix += s.top();
postfix += " ";
s.pop();
}
return postfix;
}
// 2. 后缀表达式求值
int evaluatePostfix(const std::string& postfix) {
std::stack<int> s;
for (size_t i = 0; i < postfix.length(); ++i) {
char ch = postfix[i];
if (std::isspace(ch)) continue;
if (std::isdigit(ch)) {
s.push(ch - '0');
} else {
int val2 = s.top(); s.pop();
int val1 = s.top(); s.pop();
switch (ch) {
case '+': s.push(val1 + val2); break;
case '-': s.push(val1 - val2); break;
case '*': s.push(val1 * val2); break;
case '/': s.push(val1 / val2); break;
}
}
}
return s.top();
}
它的缺点
- 访问受限：无法像链表或数组那样，访问或修改栈中间甚至底部的某个元素。如果你非要看第三个元素，你必须将排在它前面的元素全部
pop掉（通常会丢失数据，除非用另一个辅助栈暂存）。 - 数组大小限制：顺序栈需要提前预估空间大小，空间给小了容易爆栈（Stack Overflow），给大了又浪费物理内存。
学习难点
- 括号匹配与算符优先级解析：如何用计算机思维去模拟人类的运算法则。理解并推导中缀转后缀中对“左括号”、“右括号”以及“优先级高低”的处理边界。
- 隐式调用栈（系统栈）：我们在写递归程序（如快速排序、DFS）时，计算机内部就是利用了隐式的系统调用栈来保存每一层的局部变量和返回地址。理解系统栈的工作流程，是写好递归和将其改写为非递归（手动压栈）的关键。
课后提问
- 全括号匹配检查：输入一个包含
()、[]、{}的字符串，请利用栈设计一个算法，检查该括号组合是否合法。 - 最小栈设计：设计一个支持
push、pop、top的栈，并且能在 $O(1)$ 时间复杂度内检索到当前栈中的最小值（提示：使用辅助栈）。 - 中缀转前缀：前缀表达式（波兰式）将操作符置于操作数之前，如
+ 3 * 4 2。请尝试设计算法将中缀表达式转换为前缀表达式。 - 非递归汉诺塔：汉诺塔（Hanoi）经典解法是递归。请尝试使用一个或多个自定义堆栈，模拟并输出汉诺塔的圆盘移动轨迹。
—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com
