第一章：综合实战——学生成绩管理系统、表达式计算器与文件压缩
各位同学，欢迎来到《C语言数据结构与算法实现指南》的第一章。说实话，每次讲到综合实战这一块，我都特别兴奋。为什么？因为前面学了一堆链表、栈、队列、树，终于到了真正干活的时候了。
这一章，我们要一口气拿下三个项目：学生成绩管理系统、表达式计算器、文件压缩与解压。这三个项目分别对应了不同的数据结构——链表、栈与队列、哈夫曼树。我当年刚入行时，就是靠这几个项目在面试中站稳了脚跟。嗯，咱们一个一个来。
1.1 学生成绩管理系统——链表 + 排序 + 查找
先说说学生成绩管理系统。这个项目说白了就是一个动态数据管理工具。你想想看，一个班级几十号人，成绩录入、删除、修改、查询、排序，如果用数组来做，增删操作会非常痛苦。链表就派上用场了。
核心思路：用单向链表存储学生信息，每个节点包含学号、姓名、成绩。支持插入、删除、查找、排序、遍历。
我个人习惯把学生信息定义成一个结构体，然后链表节点里放这个结构体。这样扩展性最好。比如以后要加个「班级」字段，改结构体就行，链表逻辑不用动。
typedef struct {
int id; // 学号
char name[20]; // 姓名
float score; // 成绩
} Student;
typedef struct Node {
Student data;
struct Node* next;
} Node;排序这块，我建议用冒泡排序或插入排序。为什么不用快排？因为链表是单向的，快排的随机访问特性在链表上施展不开。我曾经在项目中试过用快排处理链表，结果指针绕来绕去把自己绕晕了。后来老老实实用了归并排序——链表归并排序其实很优雅，时间复杂度 O(n log n)，而且不需要额外数组。
避坑指南：我曾经在删除节点时忘记释放内存，导致程序跑着跑着内存暴涨。记住：free() 之前一定要先保存下一个节点的指针，否则链表就断了。
查找功能，我一般用学号作为关键字，因为学号唯一。如果数据量不大（几千以内），顺序查找就够了。如果数据量大，可以考虑用哈希表或二叉搜索树，但那是后面章节的内容了。
1.2 表达式计算器——栈 + 队列
表达式计算器，这个项目很有意思。你输入一个中缀表达式，比如 "3 + 5 * ( 2 - 8 )"，程序要能算出正确结果。这里的关键是：中缀表达式转后缀表达式（逆波兰式），然后用栈计算。
为什么会这样？因为计算机处理中缀表达式很麻烦——要考虑运算符优先级和括号。而后缀表达式没有括号，优先级天然体现在顺序里。我当年第一次实现时，被括号匹配搞到怀疑人生。后来发现，只要把栈用好了，一切都很清晰。
核心流程：
- 用队列存储输入的中缀表达式（每个元素是一个 token）
- 用栈实现中缀转后缀（运算符栈）
- 用另一个栈计算后缀表达式（操作数栈）
中缀转后缀的规则，我总结成一句话：数字直接输出，运算符看栈顶，左括号直接入栈，右括号弹到左括号为止。 你想想看，是不是这个理？
// 中缀转后缀核心逻辑（伪代码）
while (有token) {
if (token是数字) 输出到队列;
else if (token是左括号) 入栈;
else if (token是右括号) {
while (栈顶不是左括号) 弹出并输出;
弹出左括号;
}
else { // 运算符
while (栈不空 && 栈顶优先级 >= 当前优先级) 弹出并输出;
当前运算符入栈;
}
}
while (栈不空) 弹出并输出;注意：浮点数处理是个坑。我建议把数字统一用 double 存储，不要用 int。否则 "3 / 2" 会算出 1，而不是 1.5。另外，负数处理也要小心——比如 "-3 + 5"，需要特殊判断。
计算后缀表达式就简单了：遇到数字入栈，遇到运算符弹出两个数计算，结果再入栈。最后栈顶就是答案。
1.3 文件压缩与解压——哈夫曼树
文件压缩，这个项目是数据结构的集大成者。哈夫曼树（最优二叉树）的核心思想是：出现频率高的字符用短编码，频率低的用长编码。这样整体压缩率最高。
我记得第一次实现哈夫曼压缩时，被位操作折磨得不轻。因为编码是变长的，而且不是字节对齐的，你得一个 bit 一个 bit 地往文件里写。C 语言没有直接的 bit 流操作，得自己拼字节。
核心步骤：
- 统计每个字符的出现频率
- 用频率构建哈夫曼树（最小堆实现）
- 从哈夫曼树生成每个字符的编码（左0右1）
- 将编码写入压缩文件（注意位对齐）
- 解压时读取编码，从哈夫曼树根节点开始走，遇到叶子就输出字符
构建哈夫曼树时，我建议用最小堆（优先队列）来取频率最小的两个节点。每次合并后重新插入堆，直到堆里只剩一个节点——那就是根节点。
// 哈夫曼树节点
typedef struct HuffmanNode {
char ch; // 字符
int freq; // 频率
struct HuffmanNode *left, *right;
} HuffmanNode;
// 最小堆（优先队列）用于构建哈夫曼树
// 每次取两个最小频率节点合并避坑指南：我曾经在解压时忘记处理文件末尾的填充位，导致解压出来的文件多了几个乱码字符。解决办法是：在压缩文件头部记录原始文件的总位数，解压时只读取那么多位。
另外，压缩文件头要保存哈夫曼树的结构信息，否则解压时无法重建树。我一般用先序遍历的方式保存树结构，每个节点用 1 个字节标记是叶子还是内部节点，叶子节点后面跟字符本身。
知识体系总览
下面这张图，是我画的本章节知识体系结构。你可以看到三个项目分别对应了哪些数据结构，以及它们之间的关联。
从这张图你可以看到，三个项目虽然各自独立，但背后的数据结构是相通的。链表、栈、队列、树，这些基础结构一旦掌握，任何项目都能拆解成「用什么结构 + 用什么算法」的问题。
本章小结
这一章我们讲了三个实战项目：
- 学生成绩管理系统——链表增删改查 + 排序查找，适合练手入门
- 表达式计算器——栈和队列的经典应用，考验逻辑严谨性
- 文件压缩与解压——哈夫曼树 + 位操作，综合难度最高
我个人建议你按这个顺序来写代码。先搞定链表，再挑战栈和队列，最后啃哈夫曼树。每个项目都自己手写一遍，不要复制粘贴。相信我，写一遍和看十遍的效果完全不同。
最后提醒：代码写完一定要测试边界情况。比如链表为空时删除、表达式除数为零、压缩文件只有一个字符……这些边界最容易出 bug。我曾经在演示项目时，就因为没处理空链表，当着面试官的面程序崩溃了……嗯，那场面，记忆犹新。
好了，第一章就到这里。代码写起来吧，有问题随时翻回来看。