简介头歌数据结构链栈基本操作与应用学习资料包面向正在学习数据结构与C实现的学生以链栈这一动态栈结构为主线展开讲解。内容详细梳理链表节点定义、链栈结构体设计以及初始化、销毁、清空、判空、求长、取栈顶、入栈、出栈、遍历等9个基本操作并结合括号匹配、表达式求值等典型应用说明链栈的实际价值。配套代码示例以不带头结点的单链表改造为链栈主函数演示入栈、遍历、出栈、置空完整流程便于理解栈的LIFO特性和链式存储优势。压缩包仅含1个docx文档约15KB文字与关键代码结合适合快速复习或用做课设参考。资源虽小巧但重点突出课程实验、期末复习或考研备考时均可快速查阅目前已有7874人浏览学习是入门链栈及链表操作的实用补充。1. 头歌链栈实验最容易拿分也最容易翻车的一道题在头歌实践教学平台上“链栈的基本操作及应用”几乎是数据结构单元里的标配关卡。很多同学前面顺序表做得顺手一到链栈就开始出各种怪问题本地编译运行明明正确交上去却是0分或者一跑就段错误连是链表写错了还是输入读错了都分不清。这道题真正的门槛不在链栈算法本身而在你对链表指针约定、评测输入输出格式和内存释放这三件事的理解。适合正在做头歌实训的学生、准备王道408代码题的同学以及想快速带完实验课的助教。2. 链栈为什么值得在头歌反复做从顺序栈的假溢出到链表结构约定链栈在严蔚敏《数据结构C语言版》里是栈的链式存储实现在王道408的代码题里也属于“408数据结构代码必背”那一档。头歌链栈实训一般会要求你自己定义结构体、补全基本操作函数再把栈套到括号匹配或数制转换的应用题上。动手写代码之前先厘清两个问题为什么要用链栈以及链表头节点到底怎么约定。2.1 顺序栈与链栈的本质差别三个选链栈的现实理由顺序栈用数组存元素top 只是一个下标最大容量 MaxSize 在编译期就写死了。入栈前要判满top 到顶就溢出。链栈用单链表存元素栈顶指针就是链表表头指针入栈等于在表头做一次头插法不需要判满只有 malloc 失败这一种极端情况。这是两者最本质的区别顺序栈有容量上限链栈没有。选链栈有三个现实理由。第一栈的大小无法预估时只能用链栈典型场景是表达式求值中缀转后缀过程中运算符栈的深度取决于表达式复杂度用顺序栈要么开大了浪费空间要么开小了直接溢出。第二程序里需要同时维护多个栈的时候链栈创建销毁更灵活每个栈彼此独立不用像共享栈那样小心翼翼地分边界。第三从考试角度说考研408的数据结构代码题很少考数组实现的顺序栈链栈的指针操作才是常客头歌这道题正好帮你把链表复习一遍。顺序栈还有“假溢出”的说法判满条件通常写成 top MaxSize - 1哪怕数组低地址段空着一大片只要 top 到顶就进不去。链栈完全没有这个问题每个节点都是现用现分配。理论上只要内存足够入栈可以一直进行。这个特性在头歌应用关卡里很关键因为它允许你只写操作逻辑不用花心思处理“栈满了怎么办”这类分支。如果你手头有严蔚敏教材链栈章节的核心代码其实不到三十行。头歌平台把这道题设置成实训关卡主要就是想让你把这几行指针操作写到肌肉记忆里。实验报告里如果让你对比顺序栈和链栈的时间复杂度也能答得干脆入栈出栈都是 O(1)区别只在空间分配方式上。2.2 带头节点还是不带头节点结构体定义决定后面所有操作链栈的链表结构有两种约定头歌平台两种都出现过做题前第一件事就是确认题目模板用的是哪一种。第一种不带头节点栈顶指针 S 直接指向第一个元素节点栈空条件是 S NULL。第二种带头节点链表有一个不存数据的头节点头节点的 next 指向真正的栈顶元素栈空条件是 S-next NULL。这两种约定会连带影响入栈、出栈、判空三处代码。不带头节点时入栈是“新节点插在 S 前面然后 S 指向新节点”带头节点时入栈是“新节点插在头节点后面”。出栈同理不带头节点需要更新 S 本身所以要么函数传二级指针要么用一个带有返回值的设计带头节点的操作全部通过 S-next 完成不需要改 S 的值。我给个对照表做题时直接对着检查操作不带头节点带头节点栈空判断S NULLS-next NULL入栈p-next S; S p;p-next S-next; S-next p;出栈p S; S S-next; free(p);p S-next; S-next p-next; free(p);取栈顶返回 S-data返回 S-next-data头歌的填空题模板最常见的是带头节点版本大概是因为严蔚敏教材代码示例习惯这么做评测函数也好写。但你不能默认这一点打开关卡页面先看它给出的结构体定义和函数签名模板里写了 typedef struct StackNode... 就照着它的指针层级写。一个非常容易翻车的细节如果你用的是带头节点版本初始化时必须让头节点的 next 为 NULL否则入栈第一个元素时p-next S-next 会把一个野指针接进链表后面遍历和判空直接乱套。严格来说带头节点的链栈是“头节点 栈体”的组合头节点的 data 字段通常不用但有些同学会顺手把头节点的 data 也当作栈元素输出结果多出一个垃圾值——这个问题我再后面避坑部分单独说。3. 链栈五个基本操作的最小实现照着补进头歌就能跑下面代码用带头节点的单链表版本为准理由上面讲了头歌模板最常见。如果你拿到的模板是不带头节点的对照2.2的表格把判空、入栈、出栈三处改掉即可函数整体思路不变。3.1 结构体与初始化先定 ElemType 再建空栈链栈的结构体定义在头歌里通常是给你一半让你补一半。完整版本是这样的#include stdio.h #include stdlib.h #define ElemType int typedef struct StackNode { ElemType data; struct StackNode *next; } StackNode; typedef StackNode *LinkStack; // 初始化一个带头节点的空链栈 void InitStack(LinkStack *S) { *S (StackNode *)malloc(sizeof(StackNode)); if (*S NULL) { exit(1); // 分配失败直接终止 } (*S)-next NULL; // 空栈时头节点没有后继 }把 LinkStack 定义成 StackNode * 而不是结构体本身是为了让“栈”这个逻辑概念在代码里就是一个指针变量。后续 Push、Pop 操作只需要操作这个指针的 next 链。InitStack 的参数是 LinkStack *也就是二级指针因为函数内部要给调用者的 S 赋值C 语言里想在函数内修改指针本身的值就必须传指针的地址。初始化完之后栈空的状态是 S 不是 NULL而是 S-next NULL。这一点新手很容易搞混以为 InitStack 之后 S 应该等于 NULL结果后面判空写成了 S NULL整个逻辑全反。记住带头节点版本里头节点始终存在S 永远不为空判空只看 next。有些头歌关卡不让你写 InitStack而是直接给一个已经初始化好的 S那你只需要检查题目是否在主函数里调用了 InitStack。如果模板里没调用你需要在 main 开头补上否则下面所有操作都建立在野指针上。3.2 入栈与出栈改指针顺序是全部考点入栈和出栈是链栈基本操作的核心考试也最爱在这两处挖坑。先看标准实现// 入栈头插法把新节点插在头节点后面 void Push(LinkStack S, ElemType e) { StackNode *p (StackNode *)malloc(sizeof(StackNode)); if (p NULL) { exit(1); } p-data e; p-next S-next; // 新节点的 next 指向原来的栈顶 S-next p; // 头节点的 next 指向新节点新节点成为栈顶 } // 出栈删除头节点后面的第一个节点并用 e 带回栈顶值 int Pop(LinkStack S, ElemType *e) { if (S-next NULL) { return 0; // 栈空出栈失败 } StackNode *p S-next; *e p-data; S-next p-next; // 先改链再释放避免断链 free(p); return 1; }Push 里那两行赋值顺序不能换。如果先执行 S-next p那么原来的栈顶节点就丢了后面 p-next S-next 等于是让新节点指向自己链表成环。正确顺序永远是“新节点先指向旧栈顶再把头节点指向新节点”。Pop 的关键在于出栈值的带回方式。这里用了一个 int *e 指针参数函数返回值表示成功失败。为什么不能直接写成 ElemType Pop(LinkStack S)因为栈空时你找不到一个合法的返回值来做错误标记万一栈里存的元素本身就包含 -1那 -1 是算元素还是算错误带状态码的设计是数据结构教材里的标准做法头歌大多数关卡也按照这个风格出题。出栈的改链顺序同样有讲究先用临时变量 p 记住要释放的节点然后 S-next p-next最后 free(p)。有个常见的错误是写成free(p); S-next p-next;free 之后再访问 p-next 就是访问已释放内存虽然很多编译器在优化级别低的时候碰巧能跑出正确结果但这是标准的未定义行为Valgrind 一查一个准。头歌评测环境偶尔会开内存检测这种写法可能直接导致评测失败。顺带把清空栈的函数也写出来很多头歌关卡把这当作独立的基本操作void ClearStack(LinkStack S) { StackNode *p S-next; while (p ! NULL) { StackNode *q p-next; // 先保存下一个节点的地址 free(p); p q; } S-next NULL; // 清空后栈要回到空栈状态 }这里必须用 q 提前保存 p-next否则 free(p) 之后 p-next 已经不可访问。清空不等于销毁清空之后栈还可以继续 Push所以头节点不能释放。如果题目要求的是 DestroyStack那还要多一步 free(S) 并把栈指针置空。3.3 取栈顶与遍历调试输出比你想的更关键取栈顶和出栈的区别在于出栈删节点取栈顶只读数据。实现如下// 取栈顶元素只读不删 int GetTop(LinkStack S, ElemType *e) { if (S-next NULL) { return 0; } *e S-next-data; return 1; } // 判空 int StackEmpty(LinkStack S) { return S-next NULL; } // 从栈顶到栈底遍历输出调试专用 void PrintStack(LinkStack S) { StackNode *p S-next; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); }GetTop 的实现比 Pop 少一步 free其他逻辑几乎一样。头歌关卡里经常让你“取栈顶并输出”这时候直接调 GetTop 就行别去调 Pop否则输出完栈也空了后面的测试数据全错。PrintStack 这个函数是我特别建议你加上的。头歌评测不会调用它但你在本地调试时它是帮你判断入栈出栈逻辑正确与否的最快工具。做法很简单依次 Push 1、2、3然后调用 PrintStack如果输出是“3 2 1”说明栈的顺序是对的。如果输出“1 2 3”说明你的入栈写成了尾插法方向反了。遍历时用临时指针 p 是必须的。如果直接拿 S 去循环while (S-next ! NULL) { printf(%d , S-next-data); S S-next; }这段代码每输出一个元素就把 S 往后移最后 S 指向了原来的栈底。看起来只是遍历实际上把整个栈结构给“走丢了”头节点也没了。Debug 版程序可能看不出问题但后面任何一次 Push 或 Pop 都会在错误的位置上操作。4. 链栈的两个经典应用括号匹配与数制转换怎么做链栈本身是工具头歌应用关卡通常把它接到括号匹配、数制转换、表达式求值这些经典题目上。这些题的共同点都需要“最近出现的元素最先被处理”的能力这正是栈后进先出的语义。下面挑两个最常考的说清楚。4.1 括号匹配为什么必须用栈而不是计数器括号匹配题面一般是给你一串包含圆括号、方括号或花括号的字符串让你判断括号是否匹配。很多新手第一反应是用计数器左括号加一右括号减一最后看结果是不是 0。这个思路处理不了像“([)]”这种输入——左右括号数量恰好相等但右括号 ) 匹配的是左括号 [类型对不上。栈的做法是把“最近未匹配的左括号”记下来。遇到左括号就入栈遇到右括号就从栈顶弹出一个左括号比对类型。代码完整版本如下// 判断括号串是否匹配返回 1 匹配0 不匹配 int bracketMatch(char *str) { LinkStack S; InitStack(S); for (int i 0; str[i] ! \0; i) { if (str[i] ( || str[i] [ || str[i] {) { Push(S, str[i]); } else if (str[i] ) || str[i] ] || str[i] }) { char top; if (!Pop(S, top)) { // 栈空说明右括号多了 return 0; } if (str[i] ) top ! () return 0; if (str[i] ] top ! [) return 0; if (str[i] } top ! {) return 0; } } return StackEmpty(S); // 栈空才匹配否则左括号多了 }这段代码里ElemType 要定义成 char或者你直接把 3.1 里的 #define ElemType int 改成 char。因为入栈的是字符出栈时跟当前右括号做比对。最后的 StackEmpty(S) 是很多同学容易漏掉的一步如果输入的字符串是“((())”循环结束后栈里还剩一个左括号这时候必须返回不匹配。头歌的填空版关卡经常这样设计把“栈空判断”和“类型比对”挖掉让你补。你写的时候注意Pop 之后 top 变量里存的是左括号不要拿它跟 str[i] 做相等判断要匹配的是“成对关系”。我还见过有人把左括号入栈时按数字 1、2、3 编码出栈时再比对数字这样也可以但代码可读性差实验报告不好写。这个案例里链栈的优势体现得很明显每个字符处理完栈自动回到处理前的状态括号嵌套多深都不怕因为栈天然保存了嵌套层次。4.2 数制转换与中缀转后缀短除法和运算符优先级数制转换是栈应用里代码量最小的一道十进制转二进制用短除法余数先算出来但要倒着输出。比如 10 转二进制10%205%212%201%21倒过来是 1010。这个“先算后输出”的顺序就是栈的语义。// 十进制转二进制结果直接打印 void dec2bin(int n) { LinkStack S; InitStack(S); if (n 0) { printf(0); return; } while (n 0) { Push(S, n % 2); n / 2; } while (!StackEmpty(S)) { int bit; Pop(S, bit); printf(%d, bit); } }注意 n 0 的边界必须单独处理。如果直接进入循环余数为 0循环一次都不执行后面 Pop 也拿不到东西输出是空的。头歌的测试点一般都会覆盖 n 0 这种用例。中缀转后缀逆波兰式是链栈应用里更进阶的题头歌有些实训章节会放到下一关。它的思路是遇到操作数直接输出遇到运算符如果栈顶运算符优先级不低于当前运算符就先把栈顶弹出输出再把当前运算符入栈遇到左括号直接入栈遇到右括号一直弹出直到左括号。这里保存运算符的栈用链栈实现非常自然因为你提前不知道表达式里有多少运算符。我建议你动手之前先把运算符优先级表列出来乘除高于加减同优先级左结合。这是整个算法里最容易写错的地方。入栈时不用动态扩容想清楚这一层链栈的“链式结构 头插法”就成了表达式求值这道题最顺手的容器。4.3 头歌应用题的常见关卡形式先看输入格式再动笔头歌链栈应用关卡的输入输出形式大致有三种。第一种是固定数据题目在 main 函数里已经写死了测试数据只要你的 Push、Pop 实现正确程序跑完输出就是答案。第二种是动态读入第一行给一个整数 n第二行给 n 个数要求按某种顺序入栈出栈并输出。第三种是字符串输入比如括号匹配给一行括号串输出匹配结果。我做题的习惯是先把 main 函数完整读一遍再决定怎么写功能函数。比如第二种形式如果题目要求“读入 n 个数依次入栈再依次出栈输出”那你只需要一个循环 Push一个循环 Pop中间不用加任何多余的逻辑。但有些题目会反过来要求“读入 n 个数输出这 n 个数经过栈之后的逆序”本质一样别被题面绕进去。输出格式同样在动手前确认。头歌比对的是标准输出样例里写的是“3 2 1”你打印“3 2 1\n”就对多打一个空格都可能判错。字符串输出题要注意有没有要求输出“OK”或“YES”这类标记大小写也必须和样例一致。还有一类关卡不让你写 main只让你补 LintCode 风格的函数比如给你一个已经建好的栈你只需要补 Push 和 Pop。这时候所有的输入输出都由评测端处理你只要保证函数行为正确。判断方法是看关卡描述里有没有“输入格式”“输出格式”这两个标题没有的话多半是函数补全题。5. 链栈实验避坑指南段错误、缓冲区与头歌判分失败链栈这道题的错误很有规律我把带学生做实训时最常见的五类问题都列出来。每条都按“现象、原因、解决”的顺序讲你照着排查比漫无目的地试快得多。5.1 段错误出栈和取栈顶的判空顺序现象程序编译通过一运行就报 Segfault用 gdb 定位发现崩在 Pop 或 GetTop 里。有时前面几次调用没问题连续出栈到空才崩。原因出栈前没有判断栈是否为空。栈里已经没有元素了S-next 是 NULL你还去取 S-next-data等于访问了空指针。另一种情况是初始化没做好头节点 next 是野指针第一次出栈就直接踩到非法地址。解决在 Pop 和 GetTop 的开头加上 S-next NULL 的判空分支。我一般会把判空写在函数第一行宁可多了也不能少。初始化函数里 (*S)-next NULL 也要确认执行了。如果是头歌的填空模板注意看它有没有在 InitStack 里把这行补上没有就自己补。另外排查段错误时不要只盯着出栈函数。如果入栈时 p-next S-next 这一行写反了链表成环后面任何一次遍历都会死循环直到栈溢出表现同样是段错误。先用 PrintStack 检查链表结构再怀疑指针访问越界。5.2 输出格式不匹配本地有输出但头歌0分现象本地用终端跑输入测试数据输出和题目样例一模一样提交到头歌后整题 0 分或只过一两个测试点。原因头歌的评测器按标准输出做严格比对任何多余的字符都会导致该测试点失败。最常见的多余字符是 printf(请输入...) 这类提示语。另一个高频原因是每行末尾多了一个空格。比如 Push 了三个数你写 printf(%d , e) 在循环里最后一次输出也带空格样例里没有这个空格判错。解决先看题目给出的“输出样例”确认有没有行尾空格。没有的话循环里只输出数字加空格循环结束后单独补一个 printf(\n)。提示语一律不写。还有一类格式问题是换行符Windows 下编译器可能把 \n 输出成 \r\n头歌评测环境是 Linux一般不会有这个问题但如果你在本机用记事本改过代码再传上去要注意文件换行符格式。我个人的习惯是交之前先跑一遍头歌自带的“评测用例”如果平台允许查看错误输出看它实际拿到的输出和你预期的差在哪里。很多时候错误输出会尾部多一个看不出的小字符右上角切换“可见输出”就能发现。5.3 字符输入错乱scanf 混用 %d 和 %c现象括号匹配这种需要读入字符串的题或者需要单个字符入栈的题总会少读一个字符。比如输入一个数字 n 后想读入 n 个字符第一个字符总是读不到。原因scanf(%d, n) 读完后缓冲区里还剩一个换行符。紧接着 scanf(%c, ch) 读到的不是下一个有效字符而是这个换行符。这其实是 C 语言输入的老问题头歌实训里碰上链栈的字符应用就更明显。解决在 %c 前面加一个空格写成 scanf( %c, ch)。格式串里的空格会让 scanf 跳过所有空白字符空格、换行、制表符直接读到有效输入。也可以用 getchar() 手动吃掉换行但那个容易多吞字符我更喜欢前导空格这个写法。如果是整行字符串输入用 fgets 或 gets 会省很多事。注意头歌平台如果启用了安全检查gets 可能编译不过建议用 fgets(buf, sizeof(buf), stdin)。fgets 会保留末尾换行用 str[strcspn(str, \n)] 0 把它去掉不然 str[i] 循环会多处理一个换行符。5.4 内存泄漏清空栈时节点链断裂现象程序跑完功能全对但用 valgrind 检测报 definitely lost。头歌有些实训项目会开内存泄漏检测一旦报错整题扣分或判定失败。原因最常见的泄漏点是 ClearStack 里释放节点的顺序写错。比如先 free(p)再 p p-next后面的 p 已经是野指针最终这些节点既没被释放而且已经无法再被访问。另一个泄漏点在 main 函数结束时没有回收整个栈。解决ClearStack 里用一个临时变量 q 先保存下一个节点地址释放当前节点后再把 p 移动到 q。main 结束前先 ClearStack 释放所有元素节点再 free(S) 释放头节点最后把 S 置 NULL。这个习惯养成后不仅头歌评测稳过实验报告里写内存管理部分也有的写。漏掉 free(S) 这种现象很普遍因为很多教材的示例代码为了简略只写 ClearStack你照着抄就漏了最后一步。头歌的判分器一般不会因为你没释放全局变量就扣分但几个测试用例连续跑下来内存占用会累积极少数情况下会触发资源超限。5.5 判空约定不一致多一个元素或少一个元素现象入栈三个数PrintStack 输出四个数第一个数是个垃圾值。或者判空函数返回值一直不对明明 Empty 却返回 0。原因结构体定义用的是带头节点版本但你在初始化或者判空时按不带头节点的逻辑写了。带头节点的头节点 data 字段没有被赋值里面是 malloc 留下的随机值遍历从 S 开始而不是从 S-next 开始就会把这个随机值也当栈顶输出。解决对一遍 2.2 的对照表确认自己的版本。带头节点版本判空S-next NULL遍历从 S-next 开始取栈顶S-next-data不带头节点版本判空S NULL遍历从 S 开始取栈顶S-data还有第三种情况模板里定义的是 LinkStack 结构体而不是指针那所有的操作都要用 S.top 这类字段去访问相当于在结构体里封装了链表头。这种封装的版本头歌偶尔也用操作时注意别把结构体变量和指针变量混着用。6. 用 GDB 和 Valgrind 验证链栈正确性提交前十分钟的检查清单链栈这种指针密集的代码光靠人眼检查不够得让工具替你找问题。我带学生做实验时要求他们提交前必须跑两步检查GDB 跑一个崩溃场景Valgrind 跑一次完整程序。6.1 用 GDB 看指针挂在哪遇到段错误最快的方法是编译时加 -g 参数然后进 GDBgcc -g linkstack.c -o linkstack gdb ./linkstack run btbt 会打印当前崩溃时的调用栈直接告诉你崩在哪个函数的哪一行。如果显示崩在 Pop 里的 S-next-data不用犹豫先检查调用 Pop 之前栈是不是空的。如果想看入栈后链表结构在 Push 函数里打 break 然后 print S-next-data能看到每个节点的值是否符合预期。6.2 用 Valgrind 查泄漏内存泄漏的排查命令就一条valgrind --leak-checkfull ./linkstack重点看输出后半部分的 definitely lost 和 still reachable。链栈实验里如果报了 definitely lost十有八九是 ClearStack 或 Pop 里释放顺序写错。still reachable 一般是 main 里没 free(S)补上就好。清理干净后再跑一次Valgrind 输出会显示 no leaks are possible这时候提交头歌基本不会在内存检查上翻车。6.3 一个能少改代码的 ElemType 习惯链栈的应用题经常在 int 和 char 之间切换括号匹配要 char数制转换要 int表达式求值可能还要 float。我的习惯是永远不直接写死数据类型而是用 typedef 定义在文件开头typedef int ElemType;一道题换成另一道题只改这一行。如果题目本身给了 typedef那更好直接用它。这个习惯在头歌平台特别实用因为很多关卡会让你在同一个实验里先写基本操作再做括号匹配中间只隔着几行代码改数据类型时越省事越好。我自己带学生做这个实验一定会让他们先把 PrintStack 写出来再干别的。数据结构的题九成错误用一次遍历输出就能暴露剩下的交给 GDB 也够了。这比起对着屏幕猜“为什么本地能跑平台跑不了”要省半个晚上。希望帮到你。本文还有配套的精品资源点击获取