括号匹配检查几乎是每个学数据结构的人都要碰一遍的经典例子。而用C语言手写链式栈又是把指针、结构体、动态内存这几块硬骨头一起炖了。很多人会在这一步卡住数组栈能写链表栈就懵看代码能看懂自己写就各种“无法运行”。这篇文章就用括号匹配这个场景把链式栈的初始化、入栈、出栈、显示从设计思路到完整代码拆开讲顺便把我在实操里踩过的坑也一并交代清楚。适合正在学C语言和数据结构的同学也适合期末复习时想彻底搞懂“链式栈到底怎么用”的人。1. 为什么括号匹配能讲透链式栈1.1 链式栈是什么先搞懂这三点链式栈本质就是用链表结构来实现“后进先出”的栈。栈这个逻辑结构记住三个特征只在栈顶操作、后进先出、元素个数动态变化。而链式栈只是在物理存储上不依赖一整块连续内存而是用一个个节点串起来每个节点里存一个数据元素和一个指向下一个节点的指针。要理解链式栈必须抓住三点。第一栈顶在哪。链表的头部是插入删除最方便的位置所以链式栈把栈顶放在链表头部。入栈就是头插法出栈就是头删法。这一点一旦想通后面所有代码都顺了。第二节点怎么定义。每个节点包含数据域和指针域。在括号匹配这个场景里数据域就是一个char用来存放左括号。如果以后要做计算器数据域换成int或double都行结构体不变变的是数据域类型。第三栈本身怎么表示。常见写法有两种一种是只用一个StackNode *top指针栈就是指针本身另一种是定义个结构体LinkStack里面放top和size。我强烈推荐第二种。因为你还可能需要记录栈的大小也方便以后扩展。比如调试时打印size或者判断栈空不需要遍历。1.2 为什么用链式栈而不是顺序栈如果你只是应付代码题数组栈完全够用一个数组加一个top变量几行就搞定。但这里讲链式栈不是炫技而是链式栈在真实场景里有一个无法被替代的优势不需要预估最大值。顺序栈需要提前开数组开小了不够用开大了浪费内存。括号匹配的输入是任意字符串嵌套深度你控制不了。比如一个字符串里有1000层嵌套的括号你开个100大小的数组瞬间溢出。链式栈是“用多少malloc多少”理论上只受堆内存限制。这一点在实际处理未知长度的数据流时特别重要。另一个原因是指针训练。链式栈强迫你面对几个C语言的硬核问题malloc返回的指针怎么管理、结构体指针如何访问成员、free之后指针的指向如何避免悬空。这些都是后续学链表、二叉树甚至操作系统的地基。数组栈太温柔了不会让你意识到内存是“借来的要还的”。代价也不是没有。每个节点额外占一个next指针8字节频繁malloc和free比数组的索引切换慢。但在括号匹配这种教学例子中这点性能损失完全无所谓。2. 核心数据结构与接口设计2.1 结构体定义节点和栈顶指针先定义节点结构体这是链式栈的地基。typedef struct StackNode { char data; struct StackNode *next; } StackNode;注意这里不能写成typedef struct StackNode { char data; StackNode *next; } StackNode;因为在结构体内部还没定义完StackNode这个名字还不存在。这是新手最容易踩的坑。然后是栈结构体。有人会问只用一个top指针不行吗行但加一个size会让很多操作变得优雅。比如判断栈空可以直接看s.size 0也可以遍历看top是否为NULL。size还能帮助你在显示栈时知道栈里有多少元素调试时一眼看出入栈出栈的次数对不对。typedef struct { StackNode *top; int size; } LinkStack;注意LinkStack里面放的是指针不是节点。也就是说你的主程序里定义一个LinkStack s;这个s本身不是malloc出来的只有它的成员top才指向堆内存。理解这句话后面就不会出现“栈指针到底怎么初始化”的困惑。2.2 五个基础函数初始化、入栈、出栈、取栈顶、显示接口设计讲究单一职责每个函数只干一件事。我习惯把这五个函数作为链式栈的标配括号匹配只需要其中四个但取栈顶和显示在调试时非常有用。初始化最简单但是绝对不能省。void initStack(LinkStack *s) { s-top NULL; s-size 0; }为什么要传指针因为你要修改的是s这个结构体本身。如果传值形参是实参的拷贝你在函数里改了top主程序的s还是原来的野值后面用必崩。这是一个很经典的“传值还是传址”的问题。Linus有一句名言“Talk is cheap, show me the code.” 传错指针类型code直接给你看段错误。入栈头插法三步走创建节点、把新节点的next指到当前top、把top移到新节点上。void push(LinkStack *s, char c) { StackNode *newNode (StackNode *)malloc(sizeof(StackNode)); if (newNode NULL) { printf(内存分配失败\n); exit(1); } newNode-data c; newNode-next s-top; s-top newNode; s-size; }这里有个很多人忽略的细节入栈不检查栈是否已满。因为链式栈动态分配只要malloc成功就说明有空间。如果malloc返回NULL就是堆内存耗尽一般处理是直接退出或者输出错误信息。出栈头删法也要三步先判断栈空然后保存top指向的节点把top往下挪释放节点。char pop(LinkStack *s) { if (s-top NULL) { printf(栈为空无法出栈\n); return \0; } StackNode *tmp s-top; char ch tmp-data; s-top tmp-next; free(tmp); s-size--; return ch; }这里有个设计上的妥协用返回\0表示空栈。但如果你的数据本身可能是\0这种设计就有问题。更严谨的做法是让pop函数返回一个状态码通过传出参数返回数据。不过在括号匹配这个场景栈里存的都是可见字符\0不会出现可以接受。如果你想写通用栈建议改成int pop(LinkStack *s, char *out)这样的形式。取栈顶也叫peek跟出栈的区别是只看不删。char peek(LinkStack *s) { if (s-top NULL) return \0; return s-top-data; }显示栈这个函数在调试时太重要了。括号匹配失败时如果能把栈里剩余的元素打出来你一眼就能看出是哪里多了一个左括号。void displayStack(LinkStack *s) { if (s-top NULL) { printf([空栈]\n); return; } StackNode *p s-top; while (p ! NULL) { printf(%c , p-data); p p-next; } printf(\n); }注意显示栈不需要修改任何节点所以用一个遍历指针p就够了。如果你直接拿s-top去遍历遍历完栈顶指针就丢了栈也就废了。3. 括号匹配主流程与完整代码3.1 匹配逻辑右括号去栈里找“对象”括号匹配的规则很简单从左往右扫描字符串遇到左括号([{就压栈遇到右括号)]}就从栈顶弹出一个左括号看它们是不是一对。如果栈空说明右括号没有对应的左括号如果弹出的左括号和当前右括号不配对比如(和]说明类型不匹配。扫描完后如果栈非空说明有左括号没被匹配。我们可以把栈想象成“等待区”。左括号进去排队右括号一来就跟最近的一个左括号配对。最近的一个就是栈顶。如果这个“最近”都配不上那更早的更是白搭。这个直觉就是“后进先出”在括号匹配里的体现。有人会问为什么匹配失败时弹出的左括号就是“最近”的因为括号嵌套的结构决定了最内层的右括号一定对应最内层的左括号。比如{ [ ( ) ] }第一个右括号是)栈顶是(正好配对。这是栈结构的最佳应用场景。3.2 完整代码可以直接抄把上面的函数拼起来再加上一个匹配判断函数就是一个完整的链式栈括号匹配程序。我建议你直接敲一遍不要复制粘贴。有些错误只有自己敲出来才能记住。#include stdio.h #include stdlib.h typedef struct StackNode { char data; struct StackNode *next; } StackNode; typedef struct { StackNode *top; int size; } LinkStack; void initStack(LinkStack *s) { s-top NULL; s-size 0; } void push(LinkStack *s, char c) { StackNode *newNode (StackNode *)malloc(sizeof(StackNode)); if (newNode NULL) { printf(内存分配失败\n); exit(1); } newNode-data c; newNode-next s-top; s-top newNode; s-size; } char pop(LinkStack *s) { if (s-top NULL) { printf(栈为空无法出栈\n); return \0; } StackNode *tmp s-top; char ch tmp-data; s-top tmp-next; free(tmp); s-size--; return ch; } int isEmpty(LinkStack *s) { return s-top NULL; } void displayStack(LinkStack *s) { if (s-top NULL) { printf([空栈]\n); return; } StackNode *p s-top; while (p ! NULL) { printf(%c , p-data); p p-next; } printf(\n); } int match(char left, char right) { if (left ( right )) return 1; if (left [ right ]) return 1; if (left { right }) return 1; return 0; } int checkBrackets(const char *expr) { LinkStack s; initStack(s); int i 0; while (expr[i] ! \0) { char c expr[i]; if (c ( || c [ || c {) { push(s, c); printf(入栈 %c当前栈, c); displayStack(s); } else if (c ) || c ] || c }) { if (isEmpty(s)) { printf(右括号 %c 没有匹配的左括号\n, c); return 0; } char left pop(s); printf(出栈 %c 与 %c 匹配当前栈, left, c); displayStack(s); if (!match(left, c)) { printf(匹配失败%c 与 %c 不配对\n, left, c); return 0; } } i; } if (!isEmpty(s)) { printf(栈中还有未匹配的左括号); displayStack(s); return 0; } return 1; } int main() { char expr[200]; printf(请输入包含括号的表达式); fgets(expr, sizeof(expr), stdin); // 去掉fgets读入的换行符 int len 0; while (expr[len] ! \0) len; if (len 0 expr[len - 1] \n) expr[len - 1] \0; if (checkBrackets(expr)) { printf(括号匹配结果是成功\n); } else { printf(括号匹配结果是失败\n); } return 0; }这段代码有点啰嗦故意在每个入栈出栈后显示一次栈内容目的就是让你能看到整个过程。跑一次输入{([])}输出会很直观入栈 {当前栈{ 入栈 (当前栈( { 入栈 [当前栈[ ( { 出栈 [ 与 ] 匹配当前栈( { 出栈 ( 与 ) 匹配当前栈{ 出栈 { 与 } 匹配当前栈[空栈] 括号匹配结果是成功调试完这些打印你其实就已经理解了链式栈的入栈出栈过程。3.3 代码逐段说明每一步在做什么主函数里接收输入用fgets而不是gets。因为gets已经被C标准移除了它只给你一个缓冲区却不知道缓冲区多大字符串一长就是缓冲区溢出属于网络安全里必须避免的漏洞。fgets安全但会把换行符\n也读进来。我后面用一个循环找到字符串末尾把换行符改成\0。这一步叫“去除尾部换行符”很多新手会忘记然后发现括号匹配怎么都不对——因为把换行符合法地忽略了但如果你不看它不会影响你的逻辑。其实在这个例子里换行符不影响因为checkBrackets只处理括号字符换行符会被忽略。但养成清理输入的习惯总是好的。checkBrackets的返回值虽然是int但语义上是“成功/失败”。C语言没有内建的bool用int是常规操作。也可以包含stdbool.h然后返回true/false那是C99引入的。但很多老代码风格还是用int。匹配函数match里三个if看起来很傻但清晰地表达了配对关系。你也能用一个查表法把左右括号映射成数字比如(和)都映射成1[和]映射成2{和}映射成3然后判断映射值是否相等。不过那个做法不如直接的if好理解教学场合没必要。3.4 栈的清理被很多人忽略的操作上面的代码在匹配失败时直接return了这是有隐患的。如果栈里还有节点return之后没人去free它们就会造成内存泄漏。C语言没有垃圾回收你malloc了就必须有人free。在函数里局部变量LinkStack s本身是栈内存但它指向的节点是堆内存。函数结束时s的栈内存自动释放但堆内存不会。所以面试官很爱问“你这里退出时栈没清空怎么办”。正确的做法是写一个clearStack或者freeStackvoid clearStack(LinkStack *s) { while (s-top ! NULL) { StackNode *tmp s-top; s-top tmp-next; free(tmp); } s-size 0; }然后在checkBrackets的每一个失败return之前调用clearStack(s);成功返回前也要调用。不是在main里调用因为那时候s已经是局部变量了。更稳妥的设计是checkBrackets内部不直接return而是设置一个结果变量最后统一清理再return。比如int checkBrackets(const char *expr) { LinkStack s; initStack(s); int result 1; // ... 匹配逻辑中若失败result 0; 然后 goto done; 或者 break; // 最后统一处理 done: if (!isEmpty(s)) { displayStack(s); result 0; } clearStack(s); return result; }这个模式在嵌入式开发里很常见函数开头初始化资源如果有多个错误分支不要到处return而是跳到一个统一清理点。C语言用goto做错误处理其实是正路Linux内核代码里到处都是。4. 常见问题与排查技巧实录4.1 野指针与段错误数组栈的老手初写链式栈最容易遇到“段错误”。原因基本就几个结构体没初始化top是个野值入栈时 newNode-next 没有正确赋值出栈后没有把原top节点free或者free了但没有把top更新。我见过一个特别典型的错误StackNode *p; p-data c; // p没分配内存 p-next s-top; s-top p;这写法编译会通过但运行必崩。因为p是一个野指针你往野指针指向的地方写数据就是非法访问。正确做法是先malloc(sizeof(StackNode))拿到一块合法的堆内存。另一个常见错误是初始化时忘记把top设NULL。LinkStack s;是一个局部变量它的值是随机的。如果你直接push(s, c)push里执行newNode-next s-top;这个top是一个随机值链表就串到了一个非法地址。所以initStack必须在任何操作之前调用。4.2 空栈出栈的边界处理pop函数里一定要判断s-top NULL否则你试图从空栈里取数据访问的是NULL指针的成员段错误。有人心存侥幸“我匹配流程里不会出现空栈出栈的”但括号匹配最需要的就是这个判断——比如输入字符串以右括号开头第一个字符就要出栈栈是空的。没有空栈判断程序直接崩而不是打印“右括号没有匹配”。更隐蔽的是free之后使用。比如char ch s-top-data; free(s-top); s-top s-top-next; // 错s-top已经变成野指针了必须先取next再free。好多人顺序写反一跑就随机崩溃现象还不稳定。这种错误在单链表插入删除里也经常见。核心原则先接好链再拆节点。4.3 内存泄漏怎么自查内存泄漏不像段错误那么明显。你写了个循环入栈一万次但出栈不到位程序占内存越来越大最后被系统杀掉。自查工具在Linux下用valgrindWindows可以用Visual Studio的CRT内存泄漏检测。不过也别急着上工具先肉眼检查代码每个malloc是否有对应的free。括号匹配里最容易漏的就是前面说的失败分支直接return。你可以跑一个故意不匹配的输入比如((如果程序退出后你用valgrind跑它会显示definitely lost多少字节。加上clearStack之后再跑就干净了。我自己的习惯是在clearStack里free每一个节点然后在函数结束前把s-top NULL。这不只是防御也是给未来维护者看的这个栈已经彻底清空可以再用了。4.4 scanf和fgets的坑顺便说清楚还有一种常见的输入方式用scanf(%s, expr)。注意scanf(%s)读到空格会停所以表达式里如果含空格比如{ [ ] }会把表达式截断。括号表达式一般没空格但你测试时可能想输入{ [ ] }结果匹配结果莫名其妙。fgets则会把整行都读进来包括空格更合适。另外fgets的第二个参数是缓冲区大小这个大小必须和你定义的数组尺寸匹配否则会截断。如果你输入特别长超过sizeof(expr)-1可能把表达式的右半截丢掉导致匹配失败。这就是为什么在不确定输入长度时链式栈的结构优势值得考虑——你可以用动态增长的字符串缓冲区不过那是另一个话题了。4.5 调试技巧善用“显示栈”我在checkBrackets里加了入栈出栈时的打印。实际使用时你可能会嫌它太吵。那至少保留一个displayStack函数方便在可疑位置手动打印。有一个我常用来验证栈操作的小技巧检查栈顶指针的地址。打印%p格式看每次入栈后top的值是新节点地址出栈后恢复成前一个节点地址。这种指纹式的验证比看代码查逻辑更可靠。比如printf(top 地址: %p\n, (void *)s.top);这个技巧在链式数据结构调试中特别好用能让你确认链表的指向关系是不是对的。最后分享一个我的习惯每次写完链式栈我都会顺手做两个压力测试一个测试超级长的嵌套括号比如500个(后跟500个)看能否正常完成且不超内存另一个测试乱序输入比如([)]确认返回“不匹配”。这两个用例基本能排除掉大部分逻辑错误。另外如果是在Windows上跑记得编译时开/W3或/W4警告级别Linux下用-Wall -Wextra。编译器警告里经常藏着问题比如“未初始化变量”之类的别忽视。链式栈本身不难难的是养成“分配和释放成对出现”、“先改指针再接链”、“空栈必判断”这几个肌肉记忆。有了它们后面学二叉树的节点删除、图的邻接表你会轻松很多。