简介这份资源面向正在学习数据结构的高校学生与算法初学者聚焦链栈这一基于链表实现的栈结构帮助读者掌握其基本操作与典型应用。内容围绕链栈的初始化、销毁、清空、判空、求长度、取栈顶、入栈、出栈与遍历九类操作展开并配有完整C代码示例演示从输入整数压栈、遍历打印、弹出栈顶到判空、取栈顶与长度、清空及销毁的完整流程同时延伸至括号匹配、表达式求值等实际应用场景。资源包内含1个docx文档大小约15KB以文字讲解与代码片段为主结构紧凑便于对照头歌平台实验任务逐项练习。目前已有7878人学习下载适合需要巩固链栈原理、理清指针操作细节并完成课程实验的读者参考。1. 链栈到底解决什么问题从一次头歌实训翻车说起在头歌实践教学平台上做数据结构实训链栈这一关是很多人第一次真正被指针和内存管理按在地上摩擦的地方。标题里说的「链栈的基本操作及应用」拆开看就是三件事用链表实现栈、把 push/pop/取栈顶这些操作写对、再拿它去解决一个具体问题表达式求值、括号匹配、进制转换是头歌上最常见的三个应用场景。它适合正在跟头歌数据结构实训较劲的在校生也适合考研复习到栈和队列这一章、想动手把链式存储写一遍的备考人。链栈相比顺序栈最大的好处是不用预先估容量、不会假溢出代价是每个节点多一个指针域、频繁 malloc/free 有开销。头歌的判题机制对内存泄漏和野指针零容忍所以这一关真正卡人的不是算法思路而是指针操作的边界。下面按「先想清楚结构、再动手写、最后避坑」的顺序把我在头歌上反复调试后稳定通过的方案讲一遍。2. 链栈的结构选型与头歌判题环境适配2.1 为什么链栈用「头插法 不带头结点」最省事链栈的本质是只能在表头做插入和删除的单链表。头歌的链栈题目通常给出一个LinkStack结构体或类要求你实现Push、Pop、GetTop、StackEmpty这几个函数。这里第一个要做的决策是带不带头结点。带头结点的话top指针永远指向一个哑节点push 和 pop 都不用改top本身代码里少一层判空但每次操作多一次top-next的间接访问。不带头结点的话top直接指向栈顶元素push 时新节点next指向旧top再更新toppop 时先存top再让top后移。头歌的参考答案和大多数教材严蔚敏版、王道用的都是不带头结点的写法判题时如果结构体定义固定你也没得选。我一般推荐不带头结点的写法原因是它和「栈顶就是第一个元素」的直觉一致调试时看top指向谁一目了然。代价是 pop 和 GetTop 必须先判空这个判空如果漏了头歌直接给你段错误连错误信息都不给全。// 链栈节点定义头歌常见形式 typedef struct StackNode { int data; // 数据域头歌多为 int 或 char struct StackNode *next; // 指针域指向下一个节点 } StackNode, *LinkStack; // 初始化不带头结点top 置空 void InitStack(LinkStack *top) { *top NULL; // 空栈的标志就是 top NULL }这段代码的关键在于InitStack接收的是LinkStack *也就是二级指针因为你要修改top本身的值。头歌有些题目把初始化写好了只让你填 Push/Pop那就跳过这一步。参数说明top是栈顶指针的地址*top NULL表示空栈。如果你写成top NULL那只是改了函数内的局部副本外面的栈顶指针根本没动这是头歌上第一个高频翻车点。2.2 头歌判题环境的三个隐性约束头歌的 C/C 判题和我们本地写代码有几个不一样的地方不提前知道会浪费大量提交次数。第一头歌的测试用例通常包含「对空栈执行 Pop」和「对空栈执行 GetTop」这两种非法操作它期望你的函数返回一个特定值比如ERROR或-1而不是崩溃。所以你的 Pop 和 GetTop 必须有判空分支返回约定好的错误码。第二头歌的内存检测会检查你有没有 free 掉 pop 出来的节点。如果你 pop 时只移动了top指针而没有free旧节点多次 push/pop 后内存持续增长某些严格模式下会判你不通过。这一点和很多教材上「pop 只返回数据不释放」的简化写法冲突以头歌题目要求为准。第三头歌的输入输出格式是固定的。如果题目要求你写一个完整的进制转换程序那main函数里的输入读取方式、输出格式必须严格匹配多一个空格都可能判错。建议先把题目给的输入输出样例抄下来本地跑通再提交。提示头歌每道题都有提交次数限制但通常足够你调试。真正浪费次数的是不看题目要求就凭教材记忆写结果接口签名对不上。3. 链栈基本操作的完整实现与逐行拆解3.1 Push 和 Pop两行核心代码背后的指针顺序链栈的 push 和 pop 核心逻辑各只有两三行但指针的赋值顺序错了就是灾难。先看代码。// 入栈头插法 int Push(LinkStack *top, int e) { StackNode *newNode (StackNode *)malloc(sizeof(StackNode)); if (newNode NULL) return 0; // 内存分配失败 newNode-data e; // 1. 填数据 newNode-next *top; // 2. 新节点指向原栈顶 *top newNode; // 3. 更新栈顶指针 return 1; } // 出栈返回栈顶元素并通过 e 带出 int Pop(LinkStack *top, int *e) { if (*top NULL) return 0; // 空栈直接返回失败 StackNode *p *top; // 1. 暂存栈顶节点 *e p-data; // 2. 取出数据 *top p-next; // 3. 栈顶下移 free(p); // 4. 释放旧栈顶 return 1; }Push 的三步顺序不能乱必须先让新节点的next指向当前栈顶再更新top。如果你先写*top newNode那原来的栈顶就丢了新节点的next指向的是它自己或者野指针整个栈断裂。这是链栈最经典的错误没有之一。Pop 的四步里第 1 步暂存p是必须的因为第 3 步*top p-next之后你就找不到旧栈顶了没法 free。第 4 步 free 在头歌上要不要写看题目要求但写了不会错。参数说明e是int *因为 C 语言函数只能通过指针带回多个值如果你用 C 的引用int e也可以头歌的 C 环境支持。3.2 GetTop 和 StackEmpty看起来简单但最容易丢分// 取栈顶元素不删除 int GetTop(LinkStack top, int *e) { if (top NULL) return 0; // 空栈 *e top-data; // 直接读栈顶数据 return 1; } // 判空返回 1 表示空0 表示非空 int StackEmpty(LinkStack top) { return top NULL ? 1 : 0; }注意 GetTop 的第一个参数是LinkStack top而不是LinkStack *top因为取栈顶不修改栈顶指针本身传一级指针就够了。头歌有些题目会把这里写成二级指针以题目给的函数签名为准不要自作主张改。StackEmpty 的返回值约定也要看题目有的题目要求空返回 1有的要求空返回 0还有的用bool。头歌的判题是精确匹配返回反了整个测试用例全挂。我一般会先把题目里的函数声明复制到本地照着签名写避免这种低级错误。3.3 用链栈做进制转换头歌最常考的应用头歌链栈的应用题里十进制转二进制/八进制/十六进制出现频率最高。原理是利用栈的后进先出不断对十进制数取余余数依次入栈最后依次出栈就是转换结果。// 十进制转任意进制2-16用链栈实现 void Conversion(int n, int base) { LinkStack top; InitStack(top); int rem; // 取余入栈 while (n ! 0) { rem n % base; // 取余数 Push(top, rem); // 余数入栈 n n / base; // 整除准备下一轮 } // 出栈输出 int e; while (!StackEmpty(top)) { Pop(top, e); if (e 10) printf(%d, e); // 0-9 直接输出 else printf(%c, A e - 10); // 10-15 输出 A-F } printf(\n); }逻辑说明以十进制 10 转二进制为例10%20 入栈10/255%21 入栈5/222%20 入栈2/211%21 入栈1/20 结束。栈里从底到顶是 0、1、0、1出栈顺序是 1、0、1、0正好是 1010。参数说明base取值 2 到 16超过 10 的余数用字母 A-F 表示这是头歌进制转换题的通用约定。注意如果输入的 n 是 0while 循环一次都不执行栈是空的最后什么都不输出。头歌有些测试用例会包含 n0正确输出应该是「0」。所以要在循环前加一个特判if (n 0) { printf(0\n); return; }。4. 链栈在头歌上翻车的五个真实场景4.1 现象提交后提示「段错误」或「运行时错误」原因最常见的是对空栈执行了 Pop 或 GetTop没有判空就直接访问top-data。其次是 Push 里 malloc 失败没处理或者 Pop 里 free 之后又访问了那块内存。解决在所有会解引用top的地方前面加if (top NULL)判断。Pop 里 free 之后不要再碰p养成「free 之后置 NULL」的习惯。头歌的段错误不告诉你行号只能靠自己在每个指针操作前加打印来定位。4.2 现象输出结果正确但判题不通过原因函数返回值不对。头歌的判题不仅看输出还看你的函数返回 0 还是 1。比如 Pop 成功应该返回 1失败返回 0你如果返回了别的值即使输出对也不通过。解决把题目给的函数声明和返回值约定仔细读三遍。头歌的题目描述里通常会写「成功返回 1失败返回 0」或「返回 ERROR」照着写。不要凭教材记忆不同教材的约定不一样。4.3 现象多次 push/pop 后程序变慢或崩溃原因Pop 时没有 free 旧节点内存泄漏。头歌的测试用例可能循环几万次泄漏累积后 malloc 返回 NULL你的 Push 没处理就崩溃了。解决Pop 里必须 free。如果题目明确说「不要求释放」那可以不 free但大多数头歌题目是要求的。判断方法看题目有没有提「释放节点」或「内存管理」。4.4 现象进制转换结果顺序反了原因把余数直接输出了没有经过栈。或者入栈和出栈的顺序搞反了先出栈再入栈。解决记住「先入后出」——先算出来的余数是低位后算出来的是高位低位先入栈高位后入栈出栈时高位先出正好是正确顺序。如果你输出反了检查是不是把 Push 和 Pop 的顺序写反了。4.5 现象本地跑通头歌提交报「编译错误」原因头歌的编译环境可能和你本地不一样。常见的有用了 C99 的for(int i...)但头歌用 C89用了bool但没#include stdbool.h函数签名和题目给的不一致。解决把头歌题目里的函数声明原样复制到你的代码里不要改参数类型和个数。如果题目给的是void Push(LinkStack *top, int e)你就不能写成int Push(LinkStack top, int e)。头歌的编译错误信息通常比较详细仔细看第一行。5. 链栈进阶用头歌的判题思路反推代码质量头歌的判题机制其实是一个很好的代码质量训练器因为它逼你考虑所有边界情况。我在头歌上刷完链栈这一关后养成了一个习惯每写一个操作函数先问自己三个问题——空栈时怎么办只有一个节点时怎么办malloc 失败时怎么办这三个问题覆盖了链栈 90% 的 bug。进阶用法上链栈可以扩展到「多栈共享」和「栈的应用之表达式求值」。头歌有些题目会让你用两个链栈分别存操作数和运算符实现一个简单的四则运算计算器。这个场景下链栈的优势是不用预估表达式长度来多少存多少。实现时注意运算符优先级判断和括号处理这是表达式求值的两个核心难点。验证方法上我一般会写一个小的测试驱动把 Push/Pop/GetTop 组合起来跑一遍打印每一步的栈顶和栈大小。头歌不让你看中间状态但本地可以。下面这个测试代码可以帮你快速定位问题// 本地测试驱动验证链栈基本操作 int main() { LinkStack top; InitStack(top); int e; // 测试空栈 Pop printf(空栈Pop返回: %d\n, Pop(top, e)); // 应为 0 // 测试 Push 和 GetTop Push(top, 1); Push(top, 2); Push(top, 3); GetTop(top, e); printf(栈顶: %d\n, e); // 应为 3 // 测试 Pop 顺序 while (!StackEmpty(top)) { Pop(top, e); printf(%d , e); // 应为 3 2 1 } printf(\n); return 0; }这个驱动跑通基本操作就没问题了。头歌的测试用例比这个严格但核心逻辑一致。最后说一个我自己的教训头歌上链栈这一关我前三次提交都挂在「空栈 Pop 返回错误码」上因为我教材上看的版本是「空栈 Pop 直接返回栈顶元素不判空」但头歌要求返回 0。后来我养成了一个习惯——先把题目里的函数声明和返回值约定抄到纸上再动手写代码。这个习惯让我后面做队列、树、图的时候少挂了很多次。链栈是数据结构里最简单的一类结构但它的指针操作是所有链式结构的基础这一关的踩坑经验在后面的单链表、二叉树、图的邻接表里都会反复用到。希望帮到你。本文还有配套的精品资源点击获取