尧图网站建设 
简介这份资源面向正在学习数据结构课程的高校学生与算法入门者聚焦链栈这一基于链表实现的栈结构帮助读者掌握其定义方式与九类基本操作。内容围绕C实现展开涵盖初始化、销毁、清空、判空、求长度、取栈顶、入栈、出栈与遍历等核心接口并配有main函数演示完整调用流程同时延伸至括号匹配、表达式求值等典型应用场景适合课程实验与头歌平台练习参考。资源包内含1个docx文档约15KB以文字讲解与代码示例为主结构紧凑便于快速查阅。目前已有7878人学习下载读者可从中获得链栈的完整代码框架、操作逻辑说明与调试思路为后续算法设计与复杂问题求解打下基础。1. 链栈到底解决什么问题从顺序栈翻车说起如果你在头歌实践教学平台刷过数据结构实训大概率见过这道题用链式存储实现一个栈完成入栈、出栈、取栈顶、判空、清空这几个基本操作再拿它做进制转换或者括号匹配。很多人第一反应是——顺序栈我都写烂了链栈不就是把数组换成链表吗然后随手一写提交编译报错或者运行结果对不上开始怀疑人生。链栈真正要解决的不是「栈」的问题而是「栈容量不确定」的问题。顺序栈用数组你得提前给一个 MAXSIZE给小了溢出给大了浪费链栈用节点动态申请理论上只要内存够就能一直压。头歌上那些进制转换的关卡输入可能是一个很大的十进制数转成二进制后位数远超你预设的数组长度这时候链栈的优势就出来了。这篇文章面向正在做头歌数据结构实训、或者准备考研数据结构手写代码的同学把链栈从结构体定义到实际应用完整走一遍代码可以直接在头歌的 C 语言环境里跑。2. 链栈的结构体怎么定义带头结点还是不带2.1 两种定义方式的取舍链栈本质是只能在栈顶插入和删除的链表。这里有一个新手最容易纠结的问题到底要不要带头结点头歌的题目里两种写法都出现过但评分标准通常只看功能对不对不强制某一种。不过从工程角度我建议统一用带头结点的版本原因有两个。第一带头结点后空栈和非空栈的判断逻辑一致都是top-next NULL不需要单独处理「栈为空时入栈要修改头指针」这种边界。第二出栈和入栈的代码可以完全对称不用写两套分支。不带头的版本在第一个节点入栈时要写if (top NULL)出栈到最后一个节点时又要写if (top-next NULL)多出来的分支就是 bug 的温床。先看结构体定义#include stdio.h #include stdlib.h typedef int ElemType; // 栈元素类型头歌题目里通常是 int 或 char // 链栈节点 typedef struct StackNode { ElemType data; // 数据域 struct StackNode *next; // 指针域指向下一个节点 } StackNode, *LinkStackPtr; // 链栈结构体带头结点 typedef struct { LinkStackPtr top; // 栈顶指针始终指向头结点 int count; // 栈中元素个数可选但很有用 } LinkStack;这里top指向的是头结点真正的栈顶元素是top-next。count字段不是必须的但加上它之后判空和求长度都是 O(1)头歌有些题目会要求返回栈的长度有这个字段就不用遍历。2.2 初始化与判空初始化就是创建一个头结点让top指向它next置空// 初始化链栈 int InitStack(LinkStack *S) { S-top (LinkStackPtr)malloc(sizeof(StackNode)); // 创建头结点 if (S-top NULL) { return 0; // 内存分配失败 } S-top-next NULL; // 头结点的 next 置空表示空栈 S-count 0; return 1; } // 判空头结点 next 为 NULL 即为空 int StackEmpty(LinkStack *S) { return (S-top-next NULL) ? 1 : 0; }注意InitStack的参数是LinkStack *S因为要修改S-top本身。如果你写成LinkStack S传值函数里改了外面看不到这是头歌上非常高频的翻车点。判空函数不修改栈传指针只是为了访问传值也行但统一用指针更省心。3. 入栈出栈的完整实现每一步都要能跑通3.1 入栈头插法 计数更新链栈的入栈就是链表的头插法新节点插在头结点和原栈顶之间// 入栈将元素 e 压入栈顶 int Push(LinkStack *S, ElemType e) { LinkStackPtr newNode (LinkStackPtr)malloc(sizeof(StackNode)); if (newNode NULL) { return 0; // 内存分配失败入栈失败 } newNode-data e; // 赋值 newNode-next S-top-next; // 新节点指向原栈顶 S-top-next newNode; // 头结点指向新节点 S-count; // 计数加一 return 1; }三行核心操作赋值、接链、改头。顺序不能乱如果先写S-top-next newNode再写newNode-next S-top-next新节点的 next 就指向自己了形成自环出栈时死循环。这个错误在头歌上不会报编译错但运行会超时或者输出异常排查起来很费时间。3.2 出栈先判空再摘链出栈要先把栈顶元素取出来然后释放节点// 出栈弹出栈顶元素用 e 返回 int Pop(LinkStack *S, ElemType *e) { if (S-top-next NULL) { return 0; // 栈空出栈失败 } LinkStackPtr p S-top-next; // p 指向栈顶节点 *e p-data; // 取出数据 S-top-next p-next; // 头结点跳过 p free(p); // 释放节点内存 S-count--; // 计数减一 return 1; }出栈必须判空否则p-data就是空指针解引用程序直接崩溃。头歌的测试用例里通常会有「空栈出栈」这一项不判空必挂。另外free(p)之后不要再访问p有些同学 free 完还写p NULL这没问题但写p-next就是野指针访问。3.3 取栈顶与清空取栈顶不弹元素只读数据// 取栈顶元素不弹出 int GetTop(LinkStack *S, ElemType *e) { if (S-top-next NULL) { return 0; // 栈空 } *e S-top-next-data; return 1; } // 清空栈释放所有节点保留头结点 void ClearStack(LinkStack *S) { LinkStackPtr p S-top-next; while (p ! NULL) { LinkStackPtr temp p; p p-next; free(temp); } S-top-next NULL; S-count 0; }清空和销毁的区别清空保留头结点栈还能继续用销毁要连头结点一起 free之后栈就不能用了。头歌题目如果要求「销毁栈」记得把头结点也释放掉并且把S-top置为 NULL。4. 链栈的两个经典应用进制转换与括号匹配4.1 十进制转二进制为什么用栈进制转换的原理是不断取余余数从低位到高位产生但输出要从高位到低位正好是栈的后进先出。用链栈实现// 十进制转二进制输出到屏幕 void DecToBin(int n) { LinkStack S; InitStack(S); if (n 0) { printf(0\n); ClearStack(S); return; } while (n 0) { Push(S, n % 2); // 余数入栈 n n / 2; } ElemType bit; while (!StackEmpty(S)) { Pop(S, bit); printf(%d, bit); } printf(\n); ClearStack(S); }注意n 0的边界如果不单独处理while 循环一次都不进最后什么都不输出。头歌的测试用例里 0 是必测的。另外Push和Pop的返回值在实际应用中最好检查这里为了简洁省略了但正式代码里建议加上。4.2 括号匹配栈的经典考场括号匹配是考研和头歌都爱考的题逻辑是遇到左括号入栈遇到右括号看栈顶是否匹配// 括号匹配检测s 为待检测字符串 int BracketMatch(char *s) { LinkStack S; InitStack(S); for (int i 0; s[i] ! \0; i) { if (s[i] ( || s[i] [ || s[i] {) { Push(S, s[i]); // 左括号入栈 } else if (s[i] ) || s[i] ] || s[i] }) { if (StackEmpty(S)) { ClearStack(S); return 0; // 右括号多余 } ElemType top; Pop(S, top); // 检查是否配对 if ((s[i] ) top ! () || (s[i] ] top ! [) || (s[i] } top ! {)) { ClearStack(S); return 0; // 括号类型不匹配 } } } int result StackEmpty(S); // 栈空说明全部匹配 ClearStack(S); return result; }这里有个细节匹配失败返回前一定要ClearStack否则内存泄漏。头歌虽然不检查内存泄漏但养成习惯没坏处。另外字符串里可能包含非括号字符上面的代码直接跳过这是正确的处理方式。5. 链栈避坑指南头歌上最容易翻车的 5 个点5.1 传值 vs 传址栈指针没改到现象初始化之后调用 Push程序没报错但 StackEmpty 一直返回 1或者 Pop 取不到数据。原因函数参数写成了LinkStack S而不是LinkStack *S。C 语言传值调用函数内修改S.top不影响外面的变量。解决所有会修改栈结构的函数参数一律用LinkStack *S调用时传S。只有只读操作可以传值但统一用指针更不容易错。5.2 入栈顺序写反自环导致死循环现象Push 几个元素后程序卡死或者出栈时输出一堆重复数据。原因newNode-next S-top-next和S-top-next newNode写反了。先改头结点指针新节点的 next 就指向了自己。解决记住口诀「先接后断」——新节点先指向原栈顶再让头结点指向新节点。画个图就清楚了。5.3 出栈不判空空指针解引用现象程序运行到 Pop 时直接崩溃报 Segmentation fault。原因栈已经空了S-top-next是 NULL还去访问p-data。解决Pop 和 GetTop 开头必须判空空栈返回 0 表示失败。头歌的测试用例一定会测空栈操作。5.4 内存泄漏Pop 后忘记 free现象头歌上不会报错但如果你在本地用 Valgrind 检查会看到一堆 definitely lost。原因Pop 时只改了指针没有释放被摘除的节点。解决Pop 里摘链之后立刻free(p)。ClearStack 里要遍历释放所有节点。注意 free 之后不要再访问该节点的任何字段。5.5 头结点重复释放ClearStack 和 DestroyStack 混用现象调用 ClearStack 之后再调用 DestroyStack程序崩溃。原因ClearStack 保留了头结点DestroyStack 如果直接 free(S-top) 没问题但如果先 ClearStack 再 DestroyStack头结点被 free 两次。解决明确两个函数的语义。ClearStack 只清数据节点保留头结点DestroyStack 先 ClearStack 再 free 头结点并把S-top置 NULL。调用 DestroyStack 之后不要再对栈做任何操作。6. 用链栈做表达式求值一个能写进实验报告的进阶技巧表达式求值是栈最经典的综合应用也是头歌数据结构实训里区分度最高的一类题。核心思路是用两个栈一个操作数栈一个运算符栈。遍历表达式遇到数字入操作数栈遇到运算符则根据优先级决定是入栈还是弹出栈顶运算符进行计算。这里不展开完整代码重点讲一个我踩过的坑多位数和负数的处理。很多同学写的表达式求值只能处理个位数遇到1234就歇菜了。正确的做法是在扫描到数字时继续往后看把连续的数字字符拼成一个完整的数// 在表达式求值中解析多位数 int parseNumber(char *s, int *i) { int num 0; while (s[*i] 0 s[*i] 9) { num num * 10 (s[*i] - 0); (*i); } (*i)--; // 回退一格因为外层循环会 i return num; }负数的问题更隐蔽。如果表达式以-开头或者(后面紧跟-这个-是负号而不是减号。判断方法是看-前面是不是数字或者右括号如果不是就当负号处理可以压一个 0 进操作数栈然后把-当减号或者直接标记下一个数为负。我一般用前者代码改动最小。验证方法很简单构造几组测试用例34*2/(1-5)应该得 1((23)*4)应该得 20-35应该得 2。如果结果不对先检查优先级表再检查多位数解析最后检查负数判断。优先级表建议用二维数组写死比一堆 if-else 清晰得多运算符-*/()-*/()无表中表示栈顶运算符优先级高弹出计算表示当前运算符优先级高入栈表示左右括号相遇弹出左括号。这张表我考研时背了不下十遍手写代码时直接照着填比现场推优先级靠谱得多。最后说一个习惯每次写完链栈相关代码我都会在本地用gcc -g -fsanitizeaddress编译跑一遍AddressSanitizer 能直接定位内存越界和泄漏比在头歌上反复提交试错快得多。头歌的评测机不会告诉你哪里越界只会说「运行错误」有了 ASan大部分问题一眼就能看出来。希望帮到你。本文还有配套的精品资源点击获取 链栈从实现到应用：头歌实训避坑与表达式求值
简介这份资源面向正在学习数据结构课程的高校学生与算法入门者聚焦链栈这一基于链表实现的栈结构帮助读者掌握其定义方式与九类基本操作。内容围绕C实现展开涵盖初始化、销毁、清空、判空、求长度、取栈顶、入栈、出栈与遍历等核心接口并配有main函数演示完整调用流程同时延伸至括号匹配、表达式求值等典型应用场景适合课程实验与头歌平台练习参考。资源包内含1个docx文档约15KB以文字讲解与代码示例为主结构紧凑便于快速查阅。目前已有7878人学习下载读者可从中获得链栈的完整代码框架、操作逻辑说明与调试思路为后续算法设计与复杂问题求解打下基础。1. 链栈到底解决什么问题从顺序栈翻车说起如果你在头歌实践教学平台刷过数据结构实训大概率见过这道题用链式存储实现一个栈完成入栈、出栈、取栈顶、判空、清空这几个基本操作再拿它做进制转换或者括号匹配。很多人第一反应是——顺序栈我都写烂了链栈不就是把数组换成链表吗然后随手一写提交编译报错或者运行结果对不上开始怀疑人生。链栈真正要解决的不是「栈」的问题而是「栈容量不确定」的问题。顺序栈用数组你得提前给一个 MAXSIZE给小了溢出给大了浪费链栈用节点动态申请理论上只要内存够就能一直压。头歌上那些进制转换的关卡输入可能是一个很大的十进制数转成二进制后位数远超你预设的数组长度这时候链栈的优势就出来了。这篇文章面向正在做头歌数据结构实训、或者准备考研数据结构手写代码的同学把链栈从结构体定义到实际应用完整走一遍代码可以直接在头歌的 C 语言环境里跑。2. 链栈的结构体怎么定义带头结点还是不带2.1 两种定义方式的取舍链栈本质是只能在栈顶插入和删除的链表。这里有一个新手最容易纠结的问题到底要不要带头结点头歌的题目里两种写法都出现过但评分标准通常只看功能对不对不强制某一种。不过从工程角度我建议统一用带头结点的版本原因有两个。第一带头结点后空栈和非空栈的判断逻辑一致都是top-next NULL不需要单独处理「栈为空时入栈要修改头指针」这种边界。第二出栈和入栈的代码可以完全对称不用写两套分支。不带头的版本在第一个节点入栈时要写if (top NULL)出栈到最后一个节点时又要写if (top-next NULL)多出来的分支就是 bug 的温床。先看结构体定义#include stdio.h #include stdlib.h typedef int ElemType; // 栈元素类型头歌题目里通常是 int 或 char // 链栈节点 typedef struct StackNode { ElemType data; // 数据域 struct StackNode *next; // 指针域指向下一个节点 } StackNode, *LinkStackPtr; // 链栈结构体带头结点 typedef struct { LinkStackPtr top; // 栈顶指针始终指向头结点 int count; // 栈中元素个数可选但很有用 } LinkStack;这里top指向的是头结点真正的栈顶元素是top-next。count字段不是必须的但加上它之后判空和求长度都是 O(1)头歌有些题目会要求返回栈的长度有这个字段就不用遍历。2.2 初始化与判空初始化就是创建一个头结点让top指向它next置空// 初始化链栈 int InitStack(LinkStack *S) { S-top (LinkStackPtr)malloc(sizeof(StackNode)); // 创建头结点 if (S-top NULL) { return 0; // 内存分配失败 } S-top-next NULL; // 头结点的 next 置空表示空栈 S-count 0; return 1; } // 判空头结点 next 为 NULL 即为空 int StackEmpty(LinkStack *S) { return (S-top-next NULL) ? 1 : 0; }注意InitStack的参数是LinkStack *S因为要修改S-top本身。如果你写成LinkStack S传值函数里改了外面看不到这是头歌上非常高频的翻车点。判空函数不修改栈传指针只是为了访问传值也行但统一用指针更省心。3. 入栈出栈的完整实现每一步都要能跑通3.1 入栈头插法 计数更新链栈的入栈就是链表的头插法新节点插在头结点和原栈顶之间// 入栈将元素 e 压入栈顶 int Push(LinkStack *S, ElemType e) { LinkStackPtr newNode (LinkStackPtr)malloc(sizeof(StackNode)); if (newNode NULL) { return 0; // 内存分配失败入栈失败 } newNode-data e; // 赋值 newNode-next S-top-next; // 新节点指向原栈顶 S-top-next newNode; // 头结点指向新节点 S-count; // 计数加一 return 1; }三行核心操作赋值、接链、改头。顺序不能乱如果先写S-top-next newNode再写newNode-next S-top-next新节点的 next 就指向自己了形成自环出栈时死循环。这个错误在头歌上不会报编译错但运行会超时或者输出异常排查起来很费时间。3.2 出栈先判空再摘链出栈要先把栈顶元素取出来然后释放节点// 出栈弹出栈顶元素用 e 返回 int Pop(LinkStack *S, ElemType *e) { if (S-top-next NULL) { return 0; // 栈空出栈失败 } LinkStackPtr p S-top-next; // p 指向栈顶节点 *e p-data; // 取出数据 S-top-next p-next; // 头结点跳过 p free(p); // 释放节点内存 S-count--; // 计数减一 return 1; }出栈必须判空否则p-data就是空指针解引用程序直接崩溃。头歌的测试用例里通常会有「空栈出栈」这一项不判空必挂。另外free(p)之后不要再访问p有些同学 free 完还写p NULL这没问题但写p-next就是野指针访问。3.3 取栈顶与清空取栈顶不弹元素只读数据// 取栈顶元素不弹出 int GetTop(LinkStack *S, ElemType *e) { if (S-top-next NULL) { return 0; // 栈空 } *e S-top-next-data; return 1; } // 清空栈释放所有节点保留头结点 void ClearStack(LinkStack *S) { LinkStackPtr p S-top-next; while (p ! NULL) { LinkStackPtr temp p; p p-next; free(temp); } S-top-next NULL; S-count 0; }清空和销毁的区别清空保留头结点栈还能继续用销毁要连头结点一起 free之后栈就不能用了。头歌题目如果要求「销毁栈」记得把头结点也释放掉并且把S-top置为 NULL。4. 链栈的两个经典应用进制转换与括号匹配4.1 十进制转二进制为什么用栈进制转换的原理是不断取余余数从低位到高位产生但输出要从高位到低位正好是栈的后进先出。用链栈实现// 十进制转二进制输出到屏幕 void DecToBin(int n) { LinkStack S; InitStack(S); if (n 0) { printf(0\n); ClearStack(S); return; } while (n 0) { Push(S, n % 2); // 余数入栈 n n / 2; } ElemType bit; while (!StackEmpty(S)) { Pop(S, bit); printf(%d, bit); } printf(\n); ClearStack(S); }注意n 0的边界如果不单独处理while 循环一次都不进最后什么都不输出。头歌的测试用例里 0 是必测的。另外Push和Pop的返回值在实际应用中最好检查这里为了简洁省略了但正式代码里建议加上。4.2 括号匹配栈的经典考场括号匹配是考研和头歌都爱考的题逻辑是遇到左括号入栈遇到右括号看栈顶是否匹配// 括号匹配检测s 为待检测字符串 int BracketMatch(char *s) { LinkStack S; InitStack(S); for (int i 0; s[i] ! \0; i) { if (s[i] ( || s[i] [ || s[i] {) { Push(S, s[i]); // 左括号入栈 } else if (s[i] ) || s[i] ] || s[i] }) { if (StackEmpty(S)) { ClearStack(S); return 0; // 右括号多余 } ElemType top; Pop(S, top); // 检查是否配对 if ((s[i] ) top ! () || (s[i] ] top ! [) || (s[i] } top ! {)) { ClearStack(S); return 0; // 括号类型不匹配 } } } int result StackEmpty(S); // 栈空说明全部匹配 ClearStack(S); return result; }这里有个细节匹配失败返回前一定要ClearStack否则内存泄漏。头歌虽然不检查内存泄漏但养成习惯没坏处。另外字符串里可能包含非括号字符上面的代码直接跳过这是正确的处理方式。5. 链栈避坑指南头歌上最容易翻车的 5 个点5.1 传值 vs 传址栈指针没改到现象初始化之后调用 Push程序没报错但 StackEmpty 一直返回 1或者 Pop 取不到数据。原因函数参数写成了LinkStack S而不是LinkStack *S。C 语言传值调用函数内修改S.top不影响外面的变量。解决所有会修改栈结构的函数参数一律用LinkStack *S调用时传S。只有只读操作可以传值但统一用指针更不容易错。5.2 入栈顺序写反自环导致死循环现象Push 几个元素后程序卡死或者出栈时输出一堆重复数据。原因newNode-next S-top-next和S-top-next newNode写反了。先改头结点指针新节点的 next 就指向了自己。解决记住口诀「先接后断」——新节点先指向原栈顶再让头结点指向新节点。画个图就清楚了。5.3 出栈不判空空指针解引用现象程序运行到 Pop 时直接崩溃报 Segmentation fault。原因栈已经空了S-top-next是 NULL还去访问p-data。解决Pop 和 GetTop 开头必须判空空栈返回 0 表示失败。头歌的测试用例一定会测空栈操作。5.4 内存泄漏Pop 后忘记 free现象头歌上不会报错但如果你在本地用 Valgrind 检查会看到一堆 definitely lost。原因Pop 时只改了指针没有释放被摘除的节点。解决Pop 里摘链之后立刻free(p)。ClearStack 里要遍历释放所有节点。注意 free 之后不要再访问该节点的任何字段。5.5 头结点重复释放ClearStack 和 DestroyStack 混用现象调用 ClearStack 之后再调用 DestroyStack程序崩溃。原因ClearStack 保留了头结点DestroyStack 如果直接 free(S-top) 没问题但如果先 ClearStack 再 DestroyStack头结点被 free 两次。解决明确两个函数的语义。ClearStack 只清数据节点保留头结点DestroyStack 先 ClearStack 再 free 头结点并把S-top置 NULL。调用 DestroyStack 之后不要再对栈做任何操作。6. 用链栈做表达式求值一个能写进实验报告的进阶技巧表达式求值是栈最经典的综合应用也是头歌数据结构实训里区分度最高的一类题。核心思路是用两个栈一个操作数栈一个运算符栈。遍历表达式遇到数字入操作数栈遇到运算符则根据优先级决定是入栈还是弹出栈顶运算符进行计算。这里不展开完整代码重点讲一个我踩过的坑多位数和负数的处理。很多同学写的表达式求值只能处理个位数遇到1234就歇菜了。正确的做法是在扫描到数字时继续往后看把连续的数字字符拼成一个完整的数// 在表达式求值中解析多位数 int parseNumber(char *s, int *i) { int num 0; while (s[*i] 0 s[*i] 9) { num num * 10 (s[*i] - 0); (*i); } (*i)--; // 回退一格因为外层循环会 i return num; }负数的问题更隐蔽。如果表达式以-开头或者(后面紧跟-这个-是负号而不是减号。判断方法是看-前面是不是数字或者右括号如果不是就当负号处理可以压一个 0 进操作数栈然后把-当减号或者直接标记下一个数为负。我一般用前者代码改动最小。验证方法很简单构造几组测试用例34*2/(1-5)应该得 1((23)*4)应该得 20-35应该得 2。如果结果不对先检查优先级表再检查多位数解析最后检查负数判断。优先级表建议用二维数组写死比一堆 if-else 清晰得多运算符-*/()-*/()无表中表示栈顶运算符优先级高弹出计算表示当前运算符优先级高入栈表示左右括号相遇弹出左括号。这张表我考研时背了不下十遍手写代码时直接照着填比现场推优先级靠谱得多。最后说一个习惯每次写完链栈相关代码我都会在本地用gcc -g -fsanitizeaddress编译跑一遍AddressSanitizer 能直接定位内存越界和泄漏比在头歌上反复提交试错快得多。头歌的评测机不会告诉你哪里越界只会说「运行错误」有了 ASan大部分问题一眼就能看出来。希望帮到你。本文还有配套的精品资源点击获取