简介头歌平台数据结构实训中链栈的实现与操作是不少学生容易卡壳的关卡。这份Word学习笔记正是针对该关卡整理适合数据结构课程学习者、考研复习者及头歌平台实训参与者使用。内容从链表基础入手逐步过渡到链栈的定义与九种基本操作代码注释清晰可直接复制到编译环境中运行验证。文档不仅覆盖初始化、销毁、清空、判空、长度统计、获取栈顶、入栈、出栈、遍历等函数实现还提供了完整的编程调用流程细致展示输入输出、状态返回与内存释放等关键步骤。同时资源以括号匹配为例具体说明链栈在解决表达式问题时的应用方法有助于理解栈的后进先出现象与动态内存管理。资源包仅含一个Word文档约15KB内容精炼无冗余便于打印复习或碎片时间学习。目前已有7874人学习下载在同类资料中颇具参考价值。通过这份文档读者既能夯实链栈的编码基本功也能将相同思路迁移到表达式求值、递归转非递归等后续算法学习之中。1. 头歌链栈这关到底要做什么一个实验题背后的三个核心问题“头歌数据结构链栈的基本操作及应用”这关是很多学校数据结构课必做的链式存储实验。它考察的不是“你会不会写栈”而是你能否把一个栈从数组实现迁移到链表实现初始化一个栈、判断空栈、入栈、出栈、取栈顶再把这些操作拼成一个像括号匹配这样的小应用。实际做这关的人分两类一类是正在补头歌实训和实验报告的学生卡在输出格式和函数签名上另一类是准备面试或复习数据结构的人想在链栈上把指针操作练扎实。链栈真正的难点不是栈的逻辑而是链表的指针重连顺序、空栈边界和内存释放。这篇文章按这几个核心问题展开把从设计到提交的完整路径走一遍。2. 链栈的结构设计为什么顺序栈不能覆盖实验要求空栈怎么判2.1 链栈和顺序栈的本质差异容量与插入位置顺序栈用数组存储栈顶指针 top 指向当前栈顶元素在数组中的下标。入栈时先判断 top 是否等于 MAXSIZE-1出栈时判断 top 是否等于 -1。这个模型简单但有一个先天限制数组容量固定。如果你在头歌平台上处理一组很长的输入或者做一个需要动态增长的括号匹配场景顺序栈就可能在运行时溢出。更麻烦的是顺序栈的“栈顶”在数组尾部入栈是写数组的高地址方向出栈时虽然逻辑上删除了元素但数组空间无法归还给系统。链栈直接把栈的语义套在单链表上。链表的头节点就是栈顶入栈等于在链表头部插入一个节点出栈等于删除头部节点。容量完全由堆内存决定只要 malloc 成功就能继续入栈。对比下来数据结构课程里布置链栈这关的意图很明显让你体会同一抽象数据类型在不同物理存储结构下的实现差异。这也是王道408里反复强调的一个考点——栈是逻辑结构顺序栈和链栈是两种存储实现它们的操作时间复杂度虽然都是 O(1)但空间特性完全不同。两个结构还有一个容易被忽略的区别入栈位置。顺序栈从尾部入栈链栈从头部入栈。如果你先写过顺序栈再写链栈很容易把“追加”的惯性带进来新节点总是接到链表尾部然后在出栈时从尾部往上找前驱——这样一来每次操作都要遍历到最后一个节点时间复杂度从 O(1) 变成 O(n)。这正是很多人在头歌这关第一次翻车的地方。对比项顺序栈链栈存储位置连续的数组空间散列在堆内存中的节点容量固定 MAXSIZE可能溢出动态取决于可用堆内存入栈位置数组尾部top 处链表头部新节点设为栈顶空栈判断top -1栈顶指针 NULL出栈后空间下标回移空间仍在数组内free 节点内存归还堆典型使用场景大小可控、频繁访问大小不可预估、需要频繁创建销毁栈2.2 节点结构定义从单链表到栈顶指针链栈的节点结构跟单链表完全一样只是操作接口换成了栈的语义。我用严蔚敏《数据结构C语言版》里的命名习惯来写因为头歌上不少关卡沿用这套函数名。节点里放一个数据域和一个指针域数据域类型用 typedef 定义这样后面改类型只需要动一行。#include stdio.h #include stdlib.h typedef int SElemType; // 栈元素类型这里先用 int typedef struct StackNode { SElemType data; // 数据域 struct StackNode *next; // 指针域指向栈顶的下一层节点 } StackNode, *LinkStack;逻辑说明LinkStack 本质上是 StackNode 的指针类型。在链栈里这个指针的值就是当前栈顶节点的地址。栈顶节点没有前驱它的 next 指向栈内下一个节点依次往下最后一个节点的 next 为 NULL。整个链栈用“栈顶指针是否为空”来区分空栈和非空栈。参数说明typedef int SElemType 这行决定了栈元素的数据类型。如果实验题要求处理字符型括号匹配把 int 改成 char 即可节点结构不用动。LinkStack 这个别名在函数声明里很有用它直接表达了“这是一个链栈类型”的语义而不是一个普通链表指针。我习惯在所有操作函数里都用 LinkStack 类型声明参数代码可读性会好很多。这里要注意一个细节链栈本体只是一个指针这个指针本身不作为栈的一个节点。也就是说LinkStack S 是栈顶节点的地址而不是一个哨兵节点。判断 S NULL 就是判断栈空这个约定贯穿所有操作函数。2.3 空栈判断与头节点的取舍两种写法谁更适合评测链栈可以带头节点也可以不带头节点。带头节点的写法是让 LinkStack 指向一个不存数据的哨兵节点真正的栈顶元素在哨兵的 next 后面。这样做的好处是空栈判定变成 S-next NULL入栈出栈的逻辑在边界处更统一坏处是每个函数都要多走一次指针间接访问而且在头歌这类在线评测平台上如果题目模板给定的函数签名是按照“无头节点”设计的你强行带头节点会把返回值逻辑搞乱。我在头歌的习惯是采用无头节点写法原因有三个。第一栈的操作只发生在栈顶这一端不需要像单链表那样为了在表头插入而保留哨兵第二无头节点写法的空栈判断就是一次指针判空效率最高第三多数教材和实训平台的模板代码默认这个写法提交时不用改函数签名。LinkStack InitStack(void) { return NULL; // 初始化即空栈栈顶指针置 NULL }逻辑说明链栈初始化不需要像顺序栈那样分配一片连续空间并置 top 为 -1。链栈的存储空间是随入栈操作临时分配的所以初始化的全部工作就是让栈顶指针指向空。这个函数在无头节点设计下只有这一行如果有平台模板要求返回 int 表示成功就把返回类型改成 int返回 1 即可。参数说明InitStack 没有参数因为它操作的对象是“这个栈”而链栈在初始化时还没有任何资源。初始化完成后使用方要把返回值赋给 LinkStack 变量例如 LinkStack S InitStack()。后面所有需要修改栈顶指针的操作比如 Push 和 Pop都要传二级指针 LinkStack *S因为函数内部要修改的不是节点内容而是“栈顶指针本身的值”。3. 五个基本操作逐个写初始化、入栈、出栈、取栈顶、清空3.1 入栈操作头插法的指针顺序为什么不能换入栈的本质是在链表头部插入一个新节点让新节点成为栈顶。这个操作在严蔚敏教材里叫 Push。实现时分三步malloc 一个新节点、把数据写进新节点、把新节点的 next 指向当前栈顶、把栈顶指针更新为新节点。前两步好理解第三步的指针顺序是考察重点。int Push(LinkStack *S, SElemType e) { LinkStack p (LinkStack)malloc(sizeof(StackNode)); if (p NULL) { return 0; // 分配失败返回 0 表示入栈失败 } p-data e; // 新节点装入数据 p-next *S; // 新节点指向原栈顶完成“压”的动作 *S p; // 栈顶指针移向新节点 return 1; // 入栈成功 }逻辑说明p-next *S 这行是把新节点接在旧栈顶前面。如果先执行 *S p再执行 p-next *S那 p-next 会指向 p 自己链表直接在栈顶处断裂成环。这种错误在编译器层面查不出来运行时的症状是第一次入栈正常第二次入栈后栈内只有一个节点而且它的 next 指向自己后续出栈会陷入死循环或者打印出无法解释的重复数据。参数说明S 是 LinkStack 的指针也就是二级指针因为它要改动 *S 的值让栈顶指针从旧节点跳到新节点。如果题目模板给的签名是 LinkStack Push(LinkStack S, SElemType e) 并返回新栈顶那实现方式就变成LinkStack Push(LinkStack S, SElemType e) { LinkStack p (LinkStack)malloc(sizeof(StackNode)); p-data e; p-next S; // 新节点指向旧栈顶 return p; // 返回新栈顶 }两种签名等价区别是内存管理责任不同。第二种写法调用方必须接收返回值否则入栈丢失第一种写法不需要返回值但必须传二级指针。头歌的题目模板一般会把签名写清楚提交前先确认自己写的是模板要求的那一种。3.2 出栈操作先取值还是先移指针出栈要删掉栈顶节点并把它的数据通过指针参数带出来。这个函数最容易写错的地方在于把栈顶指针移动和 free 的顺序搞反。正确的是先用临时变量保存待删除节点地址然后把栈顶指针指向下一个节点最后才 free 临时变量。如果先 free(temp)temp-next 就是访问已释放内存属于典型 use-after-free。int Pop(LinkStack *S, SElemType *e) { if (*S NULL) { return 0; // 空栈不能出栈 } LinkStack temp *S; // 先保存当前栈顶节点的地址 *e temp-data; // 取出数据交给调用者 *S temp-next; // 栈顶指针跳到下一个节点 free(temp); // 释放原栈顶节点 return 1; // 出栈成功 }逻辑说明temp 的作用是记住“谁需要被释放”。*S temp-next 完成栈顶切换之后原栈顶节点已经不在链表上了但它的内存还在堆里必须 free 归还。这里 free 的顺序放在最后因为前面三行都要访问 temp 指向的节点一旦 free 再访问就是未定义行为。出栈函数对空栈的处理是返回 0这是链栈与顺序栈一致的约定——不能在 top 为 -1 时继续取元素。参数说明*e 是值参数用指针接收是因为 C 语言函数无法直接返回两个值状态和元素。常规调用方式SElemType x; if (Pop(S, x)) { printf(%d\n, x); // 只有返回值为 1 时 x 才有效 }如果把出栈改成不需要返回数据、只弹出节点的版本可以直接删掉 e 参数但头歌的题目通常要求带回元素值。还有一个隐藏考点出栈后栈为空时*S 被更新为 NULL这正好是下一次调用 Pop 时判断空栈的依据所以空栈判断不需要额外的布尔标志。3.3 取栈顶与清空只读操作和内存释放的边界取栈顶 GetTop 只读数据不修改栈结构所以不需要二级指针。它和出栈的区别是出栈会把节点从链上摘下来并 free取栈顶则原封不动。还有一个细节取栈顶传入的指针参数只用来携带数据不会改变栈的状态因此用一级指针 LinkStack S 就够了。int GetTop(LinkStack S, SElemType *e) { if (S NULL) { return 0; // 空栈无栈顶可取 } *e S-data; // 只读不修改栈顶指针 return 1; } int StackEmpty(LinkStack S) { return S NULL; // 空栈返回 1非空返回 0 }逻辑说明GetTop 和 Pop 的返回状态逻辑一致都是空栈返回 0、成功返回 1。区别在于实现上少了两行——不移动栈顶指针、不释放节点。StackEmpty 直接用指针判空这个函数写在 GetTop 前面可以做防御性检查但其实 GetTop 内部已经有了判空分支调用方也可以不额外判空二选一即可。参数说明GetTop 的第二个参数 *e 是输出参数函数执行后 e 指向的变量里存的是栈顶元素的值。StackEmpty 的参数是一级指针因为它只读栈顶指针的值不需要修改它。这个函数的返回值虽然是 int但语义是布尔值调用时可以直接用在条件里if (StackEmpty(S)) printf(栈空\n)。清空栈和出栈不同。出栈只弹出一个元素清空要释放栈内所有节点而且最后要让栈顶指针回到 NULL表示这个栈可以被重新使用。实现上用一个循环遍历链表逐个 free。void ClearStack(LinkStack *S) { LinkStack p *S; // p 是遍历指针 while (p ! NULL) { LinkStack temp p; // 记录当前要释放的节点 p p-next; // 先移动到下一个节点 free(temp); // 再释放当前节点 } *S NULL; // 栈顶指针置空栈回到初始化状态 }逻辑说明这个循环的精髓在于“先移后删”。每次循环先用 temp 记住当前节点然后把 p 移到 next最后 free temp。如果反过来先 free(p) 再 p p-next那 p-next 就是在访问野指针程序通常会在第二次循环时崩溃。循环结束后所有节点都已归还堆内存*S 置为 NULL 保证这个 LinkStack 变量不再指向任何已释放内存。参数说明ClearStack 必须传二级指针因为它要把栈顶指针本身置空。如果只传 LinkStack S函数结束只会把局部副本置空调用方的 S 仍然指向已释放的地址后续再用它判断空栈会得出错误结论。清空后的栈理论上可以继续 Push 使用因为 Push 只要求栈顶指针指向 NULL 或一个有效节点不关心这个栈是否曾经有数据。4. 把基本操作拼成应用括号匹配完整实现4.1 括号匹配的算法设计栈在这里为什么不可替代这是头歌链栈实验最常见的应用题给定一个只包含小括号、中括号、大括号的字符串判断括号是否按正确的嵌套顺序闭合。算法思路是用栈保存所有遇到的左括号遇到右括号时弹出栈顶元素检查是否匹配最后看栈是否为空。这个过程依赖“后出现的左括号先匹配”的规则即后进先出正好是栈的定义。栈在这里不可替代的原因在于括号的嵌套结构具有递归性而线性扫描的一次性匹配无法处理嵌套。比如字符串 “([{}])” 的处理过程读到 “(” 入栈读到 “[” 入栈读到 “{” 入栈读到 “}” 弹出栈顶 “{” 匹配成功继续 “]” 弹出 “[” 匹配成功最后 “)” 弹出 “(” 匹配成功栈空表示全部匹配。如果换成只记录出现次数像 “([)]” 这种左右括号数量正确但交叉嵌套的错误字符串就识别不出来——这正是括号匹配必须要栈的原因。匹配函数里对每一种右括号要配对对应的左括号。这个对应关系可以用 if-else 写也可以用映射数组。以下实现兼容三种括号输入包含其他字符时直接跳过不参与匹配。4.2 可提交的完整代码与测试用例把第 3 章的基本操作组合起来写成完整可编译的命令行程序。这个版本用字符型栈元素直接把 SElemType 改成 char括号匹配的语义就出来了。#include stdio.h #include stdlib.h typedef char SElemType; typedef struct StackNode { SElemType data; struct StackNode *next; } StackNode, *LinkStack; LinkStack InitStack(void) { return NULL; } int StackEmpty(LinkStack S) { return S NULL; } int Push(LinkStack *S, SElemType e) { LinkStack p (LinkStack)malloc(sizeof(StackNode)); if (p NULL) return 0; p-data e; p-next *S; *S p; return 1; } int Pop(LinkStack *S, SElemType *e) { if (*S NULL) return 0; LinkStack temp *S; *e temp-data; *S temp-next; free(temp); return 1; } int GetTop(LinkStack S, SElemType *e) { if (S NULL) return 0; *e S-data; return 1; } void ClearStack(LinkStack *S) { LinkStack p *S; while (p ! NULL) { LinkStack temp p; p p-next; free(temp); } *S NULL; } int match(char left, char right) { if (left ( right )) return 1; if (left [ right ]) return 1; if (left { right }) return 1; return 0; } int BracketMatch(const char *expr) { LinkStack S InitStack(); int i 0; while (expr[i] ! \0) { char c expr[i]; if (c ( || c [ || c {) { Push(S, c); // 左括号无条件入栈 } else if (c ) || c ] || c }) { char top; if (StackEmpty(S)) { ClearStack(S); return 0; // 右括号先出现匹配失败 } GetTop(S, top); if (!match(top, c)) { ClearStack(S); return 0; // 栈顶括号不匹配当前右括号 } Pop(S, top); // 匹配成功弹出栈顶左括号 } i; } int ok StackEmpty(S); // 扫描完栈空才说明全部闭合 ClearStack(S); return ok; } int main(void) { const char *test[] {([{}]), ([)], ((())), ((() , {[()()]}, NULL}; for (int i 0; test[i] ! NULL; i) { printf(%s - %s\n, test[i], BracketMatch(test[i]) ? OK : FAIL); } return 0; }逻辑说明BracketMatch 是应用入口它把链栈的操作函数按“遇左入栈、遇右比较、最后判空”的顺序组合起来。两个失败分支里都要先清空栈再返回避免 malloc 出来的节点泄漏。这里清空栈不是必须的因为程序结束时系统会回收全部内存但在实验报告中写出这一步是一种好习惯也是评测平台检查内存泄漏时的加分项。参数说明match 函数接收左括号和右括号两个字符返回 1 表示这一对括号是正确闭合的。BracketMatch 接收字符串指针用一个 while 循环扫描字符函数结束后返回 1 或 0。main 里的测试用例覆盖了四种情况完全嵌套匹配、交叉错误、纯小括号、未闭合。其中 “{[()()]}” 是王道408栈那章的经典例题输入本地跑通这组用例基本操作和应用的组合就没有大问题了。5. 头歌链栈踩坑记录评测不通过时先查这五件事5.1 现象本地输出正确平台上显示答案错误原因是头歌的在线评测环境和本地不同。最常见的是题目模板的函数签名跟你写的不一致——比如模板要求 Pop(LinkStack S, SElemType e) 却把 e 当普通值参数而你写的是指针参数或者模板固定了入栈函数必须返回新栈顶你却写了 void 版本。第二种常见原因是平台用预置输入跑程序对输出格式的判定严格到连换行符都算。解决提交前先看题目给出的函数声明严格按照声明改自己的实现。输出部分按题目要求的样例格式来不要在 printf 里多加提示文字。这个坑卡住的往往是第一次用头歌的人本地对着一次运行结果看很舒服但评测只看 stdout 有没有按要求输出。5.2 现象入栈后头指针丢失第二次操作全乱原因是指针更新的顺序写错了。典型错误是 Push 函数写成 *S p 之后再 p-next *S导致新节点自己指向自己。此时第一次入栈结果正常第二次入栈后栈顶节点的 next 不是旧节点而是自己任何遍历或清空操作都会死循环。解决记住头插法的固定顺序——“新节点先指向旧栈顶再让栈顶指针指向新节点”。你可以在 Push 函数入口和出口各打一行 printf 打印 *S 的地址值入栈两次后如果两个地址相同且节点的 next 等于自身就说明这行写反了。这种错误本地编译不报错运行也可能不崩溃但逻辑已经完全错了。5.3 现象程序正常跑完却报内存泄漏原因是链栈节点是用 malloc 创建的但只释放了部分节点。最常见的情况是 ClearStack 函数里只做了 *S NULL没有把每个节点 free 掉。另一个常见场景是 BracketMatch 里某个提前 return 的分支忘了调用 ClearStack。头歌的评测系统如果开启了内存检测会在报告里标出“Memory Leak”。解决所有可能提前退出的分支逐个检查是否释放了栈。一个保险的做法是在 main 的最后统一调用一次 ClearStack并确认 BracketMatch 内部所有 return 0 之前都清过栈。也可以本地用 valgrind 跑一遍看到 “no leaks are possible” 再提交。这条经验不只针对头歌所有涉及 malloc 的数据结构实验都要养成习惯。5.4 现象空栈时调用 GetTop 直接崩溃原因是 GetTop 函数里没有判空分支直接访问 S-data而 S 是 NULL导致空指针解引用。有些同学的写法是 GetTop 里只写了取数据把判空交给外部调用者而外部又没判评测用例一旦出现“从一开始右括号就多于左括号”的输入时程序立刻段错误。解决在 GetTop 和 Pop 内部都做空栈判断返回 0 表示失败。这个防御性写法虽然多两行代码却能让你的函数在任何异常输入下都安全返回而不是把错误留给上层。头歌评测里有些测试用例是攻击性的专测空栈输入不写判空的函数基本过不了。5.5 现象评测要求输出单一数字却打了一堆提示文字原因是 main 函数里写了类似 “请输入表达式” 或 “匹配成功” 的中文提示。头歌评测会拿你的程序输出和标准答案逐字符比对多出的任何字符都会导致答案错误。解决实验题如果只要求输出结果main 函数除了必要的测试代码什么都不要打印。括号匹配这关我一般只输出 OK 或 FAIL或者按题目要求直接输出 1 和 0。如果你习惯在本地调试时打印中间状态提交前把那些 printf 注释掉只保留题目要求的输出。这种问题在第一次提交时几乎必翻车但检查起来也最快。6. 让链栈代码经得起复用验证方法、哨兵写法与内存排错习惯6.1 带哨兵节点的链栈变体与适用边界无头节点是链栈的经典写法但如果你把链栈封装成库给别人用带头节点的版本会更稳。哨兵节点固定存在栈顶指针 S 永远指向这个哨兵空栈判定变成 S-next NULL代码里不再出现“栈顶指针本身为 NULL”的分支。代价是入栈出栈各多一次指针跳转性能略低。头歌题目如果是让补全函数体且模板没提哨兵就不要用这个变体因为函数签名里 LinkStack S 在哨兵设计下指向哨兵而在无头设计下指向栈顶节点两种对同一变量的语义完全不同混用会导致空栈判断彻底失效。适合用哨兵的场景是配置链栈的通用库或者团队里有人习惯在链表前面放空头节点时。6.2 五操作组合测试与内存检查写完链栈后我习惯先跑一组组合场景再跑一次 memcheck。组合场景覆盖“空栈出栈返回 0、空栈取栈顶返回 0、连续入栈再连续出栈、清空后继续入栈”四条路径。用代码验证比看文字更可靠写一个 main先调用 Pop(S, x) 期望返回 0然后 Push 五个元素再 Pop 五个元素每次 Pop 打印取出的值确认是 LIFO 顺序。这组测试跑完基本操作的应用层逻辑就稳了。接着用 valgrind 跑一次valgrind --leak-checkfull ./program观察输出是否包含 definitely lost 为 0 字节。如果有泄漏定位方式是从 BracketMatch 的所有 return 分支开始查确认每个分支都调用了 ClearStack。我自己写链栈实验时吃过一次亏一个分支里 Pop 成功但忘记把弹出的节点 freevalgrind 报了几百字节泄漏。从那以后凡是 malloc 的操作函数我都会在 free 后面加一行注释标明“内存已归还不能再访问该指针”。链栈这关做完顺序栈、链栈、循环队列的存储差异就打通了一半。如果你把这篇里的每个函数都手敲一遍再跑一遍括号匹配的用例对“什么时候传一级指针、什么时候传二级指针”会有一个直观的判断。写代码时先想清楚“这个函数会不会改变栈顶指针本身”再决定签名就不容易在指针参数上翻车。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/10/14 10:43:59 · 阅读 1.2k 头歌链栈实验全攻略：从结构设计到括号匹配的C语言实现
简介头歌平台数据结构实训中链栈的实现与操作是不少学生容易卡壳的关卡。这份Word学习笔记正是针对该关卡整理适合数据结构课程学习者、考研复习者及头歌平台实训参与者使用。内容从链表基础入手逐步过渡到链栈的定义与九种基本操作代码注释清晰可直接复制到编译环境中运行验证。文档不仅覆盖初始化、销毁、清空、判空、长度统计、获取栈顶、入栈、出栈、遍历等函数实现还提供了完整的编程调用流程细致展示输入输出、状态返回与内存释放等关键步骤。同时资源以括号匹配为例具体说明链栈在解决表达式问题时的应用方法有助于理解栈的后进先出现象与动态内存管理。资源包仅含一个Word文档约15KB内容精炼无冗余便于打印复习或碎片时间学习。目前已有7874人学习下载在同类资料中颇具参考价值。通过这份文档读者既能夯实链栈的编码基本功也能将相同思路迁移到表达式求值、递归转非递归等后续算法学习之中。1. 头歌链栈这关到底要做什么一个实验题背后的三个核心问题“头歌数据结构链栈的基本操作及应用”这关是很多学校数据结构课必做的链式存储实验。它考察的不是“你会不会写栈”而是你能否把一个栈从数组实现迁移到链表实现初始化一个栈、判断空栈、入栈、出栈、取栈顶再把这些操作拼成一个像括号匹配这样的小应用。实际做这关的人分两类一类是正在补头歌实训和实验报告的学生卡在输出格式和函数签名上另一类是准备面试或复习数据结构的人想在链栈上把指针操作练扎实。链栈真正的难点不是栈的逻辑而是链表的指针重连顺序、空栈边界和内存释放。这篇文章按这几个核心问题展开把从设计到提交的完整路径走一遍。2. 链栈的结构设计为什么顺序栈不能覆盖实验要求空栈怎么判2.1 链栈和顺序栈的本质差异容量与插入位置顺序栈用数组存储栈顶指针 top 指向当前栈顶元素在数组中的下标。入栈时先判断 top 是否等于 MAXSIZE-1出栈时判断 top 是否等于 -1。这个模型简单但有一个先天限制数组容量固定。如果你在头歌平台上处理一组很长的输入或者做一个需要动态增长的括号匹配场景顺序栈就可能在运行时溢出。更麻烦的是顺序栈的“栈顶”在数组尾部入栈是写数组的高地址方向出栈时虽然逻辑上删除了元素但数组空间无法归还给系统。链栈直接把栈的语义套在单链表上。链表的头节点就是栈顶入栈等于在链表头部插入一个节点出栈等于删除头部节点。容量完全由堆内存决定只要 malloc 成功就能继续入栈。对比下来数据结构课程里布置链栈这关的意图很明显让你体会同一抽象数据类型在不同物理存储结构下的实现差异。这也是王道408里反复强调的一个考点——栈是逻辑结构顺序栈和链栈是两种存储实现它们的操作时间复杂度虽然都是 O(1)但空间特性完全不同。两个结构还有一个容易被忽略的区别入栈位置。顺序栈从尾部入栈链栈从头部入栈。如果你先写过顺序栈再写链栈很容易把“追加”的惯性带进来新节点总是接到链表尾部然后在出栈时从尾部往上找前驱——这样一来每次操作都要遍历到最后一个节点时间复杂度从 O(1) 变成 O(n)。这正是很多人在头歌这关第一次翻车的地方。对比项顺序栈链栈存储位置连续的数组空间散列在堆内存中的节点容量固定 MAXSIZE可能溢出动态取决于可用堆内存入栈位置数组尾部top 处链表头部新节点设为栈顶空栈判断top -1栈顶指针 NULL出栈后空间下标回移空间仍在数组内free 节点内存归还堆典型使用场景大小可控、频繁访问大小不可预估、需要频繁创建销毁栈2.2 节点结构定义从单链表到栈顶指针链栈的节点结构跟单链表完全一样只是操作接口换成了栈的语义。我用严蔚敏《数据结构C语言版》里的命名习惯来写因为头歌上不少关卡沿用这套函数名。节点里放一个数据域和一个指针域数据域类型用 typedef 定义这样后面改类型只需要动一行。#include stdio.h #include stdlib.h typedef int SElemType; // 栈元素类型这里先用 int typedef struct StackNode { SElemType data; // 数据域 struct StackNode *next; // 指针域指向栈顶的下一层节点 } StackNode, *LinkStack;逻辑说明LinkStack 本质上是 StackNode 的指针类型。在链栈里这个指针的值就是当前栈顶节点的地址。栈顶节点没有前驱它的 next 指向栈内下一个节点依次往下最后一个节点的 next 为 NULL。整个链栈用“栈顶指针是否为空”来区分空栈和非空栈。参数说明typedef int SElemType 这行决定了栈元素的数据类型。如果实验题要求处理字符型括号匹配把 int 改成 char 即可节点结构不用动。LinkStack 这个别名在函数声明里很有用它直接表达了“这是一个链栈类型”的语义而不是一个普通链表指针。我习惯在所有操作函数里都用 LinkStack 类型声明参数代码可读性会好很多。这里要注意一个细节链栈本体只是一个指针这个指针本身不作为栈的一个节点。也就是说LinkStack S 是栈顶节点的地址而不是一个哨兵节点。判断 S NULL 就是判断栈空这个约定贯穿所有操作函数。2.3 空栈判断与头节点的取舍两种写法谁更适合评测链栈可以带头节点也可以不带头节点。带头节点的写法是让 LinkStack 指向一个不存数据的哨兵节点真正的栈顶元素在哨兵的 next 后面。这样做的好处是空栈判定变成 S-next NULL入栈出栈的逻辑在边界处更统一坏处是每个函数都要多走一次指针间接访问而且在头歌这类在线评测平台上如果题目模板给定的函数签名是按照“无头节点”设计的你强行带头节点会把返回值逻辑搞乱。我在头歌的习惯是采用无头节点写法原因有三个。第一栈的操作只发生在栈顶这一端不需要像单链表那样为了在表头插入而保留哨兵第二无头节点写法的空栈判断就是一次指针判空效率最高第三多数教材和实训平台的模板代码默认这个写法提交时不用改函数签名。LinkStack InitStack(void) { return NULL; // 初始化即空栈栈顶指针置 NULL }逻辑说明链栈初始化不需要像顺序栈那样分配一片连续空间并置 top 为 -1。链栈的存储空间是随入栈操作临时分配的所以初始化的全部工作就是让栈顶指针指向空。这个函数在无头节点设计下只有这一行如果有平台模板要求返回 int 表示成功就把返回类型改成 int返回 1 即可。参数说明InitStack 没有参数因为它操作的对象是“这个栈”而链栈在初始化时还没有任何资源。初始化完成后使用方要把返回值赋给 LinkStack 变量例如 LinkStack S InitStack()。后面所有需要修改栈顶指针的操作比如 Push 和 Pop都要传二级指针 LinkStack *S因为函数内部要修改的不是节点内容而是“栈顶指针本身的值”。3. 五个基本操作逐个写初始化、入栈、出栈、取栈顶、清空3.1 入栈操作头插法的指针顺序为什么不能换入栈的本质是在链表头部插入一个新节点让新节点成为栈顶。这个操作在严蔚敏教材里叫 Push。实现时分三步malloc 一个新节点、把数据写进新节点、把新节点的 next 指向当前栈顶、把栈顶指针更新为新节点。前两步好理解第三步的指针顺序是考察重点。int Push(LinkStack *S, SElemType e) { LinkStack p (LinkStack)malloc(sizeof(StackNode)); if (p NULL) { return 0; // 分配失败返回 0 表示入栈失败 } p-data e; // 新节点装入数据 p-next *S; // 新节点指向原栈顶完成“压”的动作 *S p; // 栈顶指针移向新节点 return 1; // 入栈成功 }逻辑说明p-next *S 这行是把新节点接在旧栈顶前面。如果先执行 *S p再执行 p-next *S那 p-next 会指向 p 自己链表直接在栈顶处断裂成环。这种错误在编译器层面查不出来运行时的症状是第一次入栈正常第二次入栈后栈内只有一个节点而且它的 next 指向自己后续出栈会陷入死循环或者打印出无法解释的重复数据。参数说明S 是 LinkStack 的指针也就是二级指针因为它要改动 *S 的值让栈顶指针从旧节点跳到新节点。如果题目模板给的签名是 LinkStack Push(LinkStack S, SElemType e) 并返回新栈顶那实现方式就变成LinkStack Push(LinkStack S, SElemType e) { LinkStack p (LinkStack)malloc(sizeof(StackNode)); p-data e; p-next S; // 新节点指向旧栈顶 return p; // 返回新栈顶 }两种签名等价区别是内存管理责任不同。第二种写法调用方必须接收返回值否则入栈丢失第一种写法不需要返回值但必须传二级指针。头歌的题目模板一般会把签名写清楚提交前先确认自己写的是模板要求的那一种。3.2 出栈操作先取值还是先移指针出栈要删掉栈顶节点并把它的数据通过指针参数带出来。这个函数最容易写错的地方在于把栈顶指针移动和 free 的顺序搞反。正确的是先用临时变量保存待删除节点地址然后把栈顶指针指向下一个节点最后才 free 临时变量。如果先 free(temp)temp-next 就是访问已释放内存属于典型 use-after-free。int Pop(LinkStack *S, SElemType *e) { if (*S NULL) { return 0; // 空栈不能出栈 } LinkStack temp *S; // 先保存当前栈顶节点的地址 *e temp-data; // 取出数据交给调用者 *S temp-next; // 栈顶指针跳到下一个节点 free(temp); // 释放原栈顶节点 return 1; // 出栈成功 }逻辑说明temp 的作用是记住“谁需要被释放”。*S temp-next 完成栈顶切换之后原栈顶节点已经不在链表上了但它的内存还在堆里必须 free 归还。这里 free 的顺序放在最后因为前面三行都要访问 temp 指向的节点一旦 free 再访问就是未定义行为。出栈函数对空栈的处理是返回 0这是链栈与顺序栈一致的约定——不能在 top 为 -1 时继续取元素。参数说明*e 是值参数用指针接收是因为 C 语言函数无法直接返回两个值状态和元素。常规调用方式SElemType x; if (Pop(S, x)) { printf(%d\n, x); // 只有返回值为 1 时 x 才有效 }如果把出栈改成不需要返回数据、只弹出节点的版本可以直接删掉 e 参数但头歌的题目通常要求带回元素值。还有一个隐藏考点出栈后栈为空时*S 被更新为 NULL这正好是下一次调用 Pop 时判断空栈的依据所以空栈判断不需要额外的布尔标志。3.3 取栈顶与清空只读操作和内存释放的边界取栈顶 GetTop 只读数据不修改栈结构所以不需要二级指针。它和出栈的区别是出栈会把节点从链上摘下来并 free取栈顶则原封不动。还有一个细节取栈顶传入的指针参数只用来携带数据不会改变栈的状态因此用一级指针 LinkStack S 就够了。int GetTop(LinkStack S, SElemType *e) { if (S NULL) { return 0; // 空栈无栈顶可取 } *e S-data; // 只读不修改栈顶指针 return 1; } int StackEmpty(LinkStack S) { return S NULL; // 空栈返回 1非空返回 0 }逻辑说明GetTop 和 Pop 的返回状态逻辑一致都是空栈返回 0、成功返回 1。区别在于实现上少了两行——不移动栈顶指针、不释放节点。StackEmpty 直接用指针判空这个函数写在 GetTop 前面可以做防御性检查但其实 GetTop 内部已经有了判空分支调用方也可以不额外判空二选一即可。参数说明GetTop 的第二个参数 *e 是输出参数函数执行后 e 指向的变量里存的是栈顶元素的值。StackEmpty 的参数是一级指针因为它只读栈顶指针的值不需要修改它。这个函数的返回值虽然是 int但语义是布尔值调用时可以直接用在条件里if (StackEmpty(S)) printf(栈空\n)。清空栈和出栈不同。出栈只弹出一个元素清空要释放栈内所有节点而且最后要让栈顶指针回到 NULL表示这个栈可以被重新使用。实现上用一个循环遍历链表逐个 free。void ClearStack(LinkStack *S) { LinkStack p *S; // p 是遍历指针 while (p ! NULL) { LinkStack temp p; // 记录当前要释放的节点 p p-next; // 先移动到下一个节点 free(temp); // 再释放当前节点 } *S NULL; // 栈顶指针置空栈回到初始化状态 }逻辑说明这个循环的精髓在于“先移后删”。每次循环先用 temp 记住当前节点然后把 p 移到 next最后 free temp。如果反过来先 free(p) 再 p p-next那 p-next 就是在访问野指针程序通常会在第二次循环时崩溃。循环结束后所有节点都已归还堆内存*S 置为 NULL 保证这个 LinkStack 变量不再指向任何已释放内存。参数说明ClearStack 必须传二级指针因为它要把栈顶指针本身置空。如果只传 LinkStack S函数结束只会把局部副本置空调用方的 S 仍然指向已释放的地址后续再用它判断空栈会得出错误结论。清空后的栈理论上可以继续 Push 使用因为 Push 只要求栈顶指针指向 NULL 或一个有效节点不关心这个栈是否曾经有数据。4. 把基本操作拼成应用括号匹配完整实现4.1 括号匹配的算法设计栈在这里为什么不可替代这是头歌链栈实验最常见的应用题给定一个只包含小括号、中括号、大括号的字符串判断括号是否按正确的嵌套顺序闭合。算法思路是用栈保存所有遇到的左括号遇到右括号时弹出栈顶元素检查是否匹配最后看栈是否为空。这个过程依赖“后出现的左括号先匹配”的规则即后进先出正好是栈的定义。栈在这里不可替代的原因在于括号的嵌套结构具有递归性而线性扫描的一次性匹配无法处理嵌套。比如字符串 “([{}])” 的处理过程读到 “(” 入栈读到 “[” 入栈读到 “{” 入栈读到 “}” 弹出栈顶 “{” 匹配成功继续 “]” 弹出 “[” 匹配成功最后 “)” 弹出 “(” 匹配成功栈空表示全部匹配。如果换成只记录出现次数像 “([)]” 这种左右括号数量正确但交叉嵌套的错误字符串就识别不出来——这正是括号匹配必须要栈的原因。匹配函数里对每一种右括号要配对对应的左括号。这个对应关系可以用 if-else 写也可以用映射数组。以下实现兼容三种括号输入包含其他字符时直接跳过不参与匹配。4.2 可提交的完整代码与测试用例把第 3 章的基本操作组合起来写成完整可编译的命令行程序。这个版本用字符型栈元素直接把 SElemType 改成 char括号匹配的语义就出来了。#include stdio.h #include stdlib.h typedef char SElemType; typedef struct StackNode { SElemType data; struct StackNode *next; } StackNode, *LinkStack; LinkStack InitStack(void) { return NULL; } int StackEmpty(LinkStack S) { return S NULL; } int Push(LinkStack *S, SElemType e) { LinkStack p (LinkStack)malloc(sizeof(StackNode)); if (p NULL) return 0; p-data e; p-next *S; *S p; return 1; } int Pop(LinkStack *S, SElemType *e) { if (*S NULL) return 0; LinkStack temp *S; *e temp-data; *S temp-next; free(temp); return 1; } int GetTop(LinkStack S, SElemType *e) { if (S NULL) return 0; *e S-data; return 1; } void ClearStack(LinkStack *S) { LinkStack p *S; while (p ! NULL) { LinkStack temp p; p p-next; free(temp); } *S NULL; } int match(char left, char right) { if (left ( right )) return 1; if (left [ right ]) return 1; if (left { right }) return 1; return 0; } int BracketMatch(const char *expr) { LinkStack S InitStack(); int i 0; while (expr[i] ! \0) { char c expr[i]; if (c ( || c [ || c {) { Push(S, c); // 左括号无条件入栈 } else if (c ) || c ] || c }) { char top; if (StackEmpty(S)) { ClearStack(S); return 0; // 右括号先出现匹配失败 } GetTop(S, top); if (!match(top, c)) { ClearStack(S); return 0; // 栈顶括号不匹配当前右括号 } Pop(S, top); // 匹配成功弹出栈顶左括号 } i; } int ok StackEmpty(S); // 扫描完栈空才说明全部闭合 ClearStack(S); return ok; } int main(void) { const char *test[] {([{}]), ([)], ((())), ((() , {[()()]}, NULL}; for (int i 0; test[i] ! NULL; i) { printf(%s - %s\n, test[i], BracketMatch(test[i]) ? OK : FAIL); } return 0; }逻辑说明BracketMatch 是应用入口它把链栈的操作函数按“遇左入栈、遇右比较、最后判空”的顺序组合起来。两个失败分支里都要先清空栈再返回避免 malloc 出来的节点泄漏。这里清空栈不是必须的因为程序结束时系统会回收全部内存但在实验报告中写出这一步是一种好习惯也是评测平台检查内存泄漏时的加分项。参数说明match 函数接收左括号和右括号两个字符返回 1 表示这一对括号是正确闭合的。BracketMatch 接收字符串指针用一个 while 循环扫描字符函数结束后返回 1 或 0。main 里的测试用例覆盖了四种情况完全嵌套匹配、交叉错误、纯小括号、未闭合。其中 “{[()()]}” 是王道408栈那章的经典例题输入本地跑通这组用例基本操作和应用的组合就没有大问题了。5. 头歌链栈踩坑记录评测不通过时先查这五件事5.1 现象本地输出正确平台上显示答案错误原因是头歌的在线评测环境和本地不同。最常见的是题目模板的函数签名跟你写的不一致——比如模板要求 Pop(LinkStack S, SElemType e) 却把 e 当普通值参数而你写的是指针参数或者模板固定了入栈函数必须返回新栈顶你却写了 void 版本。第二种常见原因是平台用预置输入跑程序对输出格式的判定严格到连换行符都算。解决提交前先看题目给出的函数声明严格按照声明改自己的实现。输出部分按题目要求的样例格式来不要在 printf 里多加提示文字。这个坑卡住的往往是第一次用头歌的人本地对着一次运行结果看很舒服但评测只看 stdout 有没有按要求输出。5.2 现象入栈后头指针丢失第二次操作全乱原因是指针更新的顺序写错了。典型错误是 Push 函数写成 *S p 之后再 p-next *S导致新节点自己指向自己。此时第一次入栈结果正常第二次入栈后栈顶节点的 next 不是旧节点而是自己任何遍历或清空操作都会死循环。解决记住头插法的固定顺序——“新节点先指向旧栈顶再让栈顶指针指向新节点”。你可以在 Push 函数入口和出口各打一行 printf 打印 *S 的地址值入栈两次后如果两个地址相同且节点的 next 等于自身就说明这行写反了。这种错误本地编译不报错运行也可能不崩溃但逻辑已经完全错了。5.3 现象程序正常跑完却报内存泄漏原因是链栈节点是用 malloc 创建的但只释放了部分节点。最常见的情况是 ClearStack 函数里只做了 *S NULL没有把每个节点 free 掉。另一个常见场景是 BracketMatch 里某个提前 return 的分支忘了调用 ClearStack。头歌的评测系统如果开启了内存检测会在报告里标出“Memory Leak”。解决所有可能提前退出的分支逐个检查是否释放了栈。一个保险的做法是在 main 的最后统一调用一次 ClearStack并确认 BracketMatch 内部所有 return 0 之前都清过栈。也可以本地用 valgrind 跑一遍看到 “no leaks are possible” 再提交。这条经验不只针对头歌所有涉及 malloc 的数据结构实验都要养成习惯。5.4 现象空栈时调用 GetTop 直接崩溃原因是 GetTop 函数里没有判空分支直接访问 S-data而 S 是 NULL导致空指针解引用。有些同学的写法是 GetTop 里只写了取数据把判空交给外部调用者而外部又没判评测用例一旦出现“从一开始右括号就多于左括号”的输入时程序立刻段错误。解决在 GetTop 和 Pop 内部都做空栈判断返回 0 表示失败。这个防御性写法虽然多两行代码却能让你的函数在任何异常输入下都安全返回而不是把错误留给上层。头歌评测里有些测试用例是攻击性的专测空栈输入不写判空的函数基本过不了。5.5 现象评测要求输出单一数字却打了一堆提示文字原因是 main 函数里写了类似 “请输入表达式” 或 “匹配成功” 的中文提示。头歌评测会拿你的程序输出和标准答案逐字符比对多出的任何字符都会导致答案错误。解决实验题如果只要求输出结果main 函数除了必要的测试代码什么都不要打印。括号匹配这关我一般只输出 OK 或 FAIL或者按题目要求直接输出 1 和 0。如果你习惯在本地调试时打印中间状态提交前把那些 printf 注释掉只保留题目要求的输出。这种问题在第一次提交时几乎必翻车但检查起来也最快。6. 让链栈代码经得起复用验证方法、哨兵写法与内存排错习惯6.1 带哨兵节点的链栈变体与适用边界无头节点是链栈的经典写法但如果你把链栈封装成库给别人用带头节点的版本会更稳。哨兵节点固定存在栈顶指针 S 永远指向这个哨兵空栈判定变成 S-next NULL代码里不再出现“栈顶指针本身为 NULL”的分支。代价是入栈出栈各多一次指针跳转性能略低。头歌题目如果是让补全函数体且模板没提哨兵就不要用这个变体因为函数签名里 LinkStack S 在哨兵设计下指向哨兵而在无头设计下指向栈顶节点两种对同一变量的语义完全不同混用会导致空栈判断彻底失效。适合用哨兵的场景是配置链栈的通用库或者团队里有人习惯在链表前面放空头节点时。6.2 五操作组合测试与内存检查写完链栈后我习惯先跑一组组合场景再跑一次 memcheck。组合场景覆盖“空栈出栈返回 0、空栈取栈顶返回 0、连续入栈再连续出栈、清空后继续入栈”四条路径。用代码验证比看文字更可靠写一个 main先调用 Pop(S, x) 期望返回 0然后 Push 五个元素再 Pop 五个元素每次 Pop 打印取出的值确认是 LIFO 顺序。这组测试跑完基本操作的应用层逻辑就稳了。接着用 valgrind 跑一次valgrind --leak-checkfull ./program观察输出是否包含 definitely lost 为 0 字节。如果有泄漏定位方式是从 BracketMatch 的所有 return 分支开始查确认每个分支都调用了 ClearStack。我自己写链栈实验时吃过一次亏一个分支里 Pop 成功但忘记把弹出的节点 freevalgrind 报了几百字节泄漏。从那以后凡是 malloc 的操作函数我都会在 free 后面加一行注释标明“内存已归还不能再访问该指针”。链栈这关做完顺序栈、链栈、循环队列的存储差异就打通了一半。如果你把这篇里的每个函数都手敲一遍再跑一遍括号匹配的用例对“什么时候传一级指针、什么时候传二级指针”会有一个直观的判断。写代码时先想清楚“这个函数会不会改变栈顶指针本身”再决定签名就不容易在指针参数上翻车。希望帮到你。本文还有配套的精品资源点击获取