看到PTA上这道《栈的算法设计 3 Dec2Bin(顺序栈)》我的第一反应是十进制转二进制不就是短除法吗小学就会算怎么还单独出一道题等你真的把代码写出来跑一遍就明白了难的不是转换本身而是你愿不愿意老老实实按栈的思路去组织数据。题目大白话讲就是给一个十进制整数用顺序栈的存储结构把它输出成二进制形式。需要的前置知识只有两条——清楚短除法怎么算清楚顺序栈的入栈出栈到底在做什么。下面按我实际做题的思路和踩坑顺序展开把这个题从题目到代码彻底吃透。1. 栈的选择思维为什么短除法天生就该用栈1.1 题面到底在问什么PTA上的这个题不同学校给出的版本略有差异但核心都跑不掉一个函数给定十进制整数 n输出它的二进制表示。有的版本是让你补全一个 Dec2Bin 函数有的版本是让你把整个顺序栈的操作都手写一遍再从主函数里调用。无论哪种考点都集中在顺序栈的五个基本操作初始化、判空、判满、入栈、出栈和一次完整的进制转换流程。很多人一开始会疑惑这题用数组也能做先算出来存数组里再倒着输出结果一模一样为什么非要套个栈这个疑问等你看完短除法的输出顺序就明白了。1.2 短除法的输出顺序藏着关键十进制转二进制标准做法是除2取余。以 n 13 为例这串计算里余数的产生顺序是 1、0、1、1但正确的二进制结果 1101 得从最后一个余数开始往前读。余数产生的顺序和最终输出的顺序正好相反。数组当然可以做到“先存后倒着输出”但它把这个反转的动作交给了程序员自己去控制下标一旦输入位数不固定代码就容易出错。栈就聪明在把“反转”这件事交给数据结构本身先产生的余数先入栈最后产生的余数在栈顶出栈时正好从最后一个余数开始输出天生匹配“后进先出”的语义。1.3 数组、递归和栈三条路怎么选处理这种逆序问题常见的还有递归方案。递归做进制转换代码更短几行就能写完。但递归本质上是在用函数调用栈系统帮你维护了压栈和弹栈。如果题目明确要求“使用顺序栈”再写递归就算跑了题判题系统可不管你的代码优雅不优雅。数组方案虽然简单直观但它暴露了一个问题你需要提前知道二进制最多有多少位。32位整数最多32个二进制位栈容量开个100完全够用可一旦你的程序要扩展成支持 long long 甚至任意大数的版本数组定长带来的限制就会反过来咬你一口。栈的好处就是把“存什么”和“取多少”分开容量管理集中在入栈函数里改动范围小。1.4 顺序栈还是链栈看题目脸色顺序栈用数组实现链栈用链表实现。这个题名里明确写了“顺序栈”那就老老实实写数组版本。顺序栈的优点是好调试、缓存友好、代码短缺点是容量固定。链栈优点是不怕容量不够代价是要写链表的初始化和节点申请。写题阶段我建议优先顺序栈因为题目给的数据规模通常友好而且 PTA 判题更关注函数逻辑而非内存表现。等以后写表达式求值、迷宫求解这些实际问题时再根据数据规模决定用哪种栈也不迟。2. 顺序栈实现的核心细节五个函数一个坑都不能踩2.1 结构体定义和栈顶指针的约定顺序栈的结构体定义网上能找到各种版本最常见的是这一种#define MAXSIZE 100 typedef int ElemType; typedef struct { ElemType data[MAXSIZE]; int top; // 栈顶下标 } SqStack;这里的 top 是整个实现最关键的地方。我见过学生写 top 初始化为 0写 top 初始化为 -1代码都能跑但判空、入栈、出栈的下标变化完全不一样。最稳妥的习惯是把 top 理解为“当前栈顶元素所在位置的下标”初始时栈是空的没有元素下标就取 -1。入栈一个元素先把 top 加 1再把元素放进去。这样做判断栈满时就是top MAXSIZE - 1判断栈空就是top -1。别小看这个约定等你在二分查找、递归转非递归的题目里来回切换时统一约定能救你半条命。2.2 初始化、判空、判满别省略返回值基础操作里最容易被轻视的是初始化。很多网上的代码用全局变量SqStack 定义在函数外面top 自动是 0那初始化确实不是必须的。但你要是把栈定义成局部变量不清零就拿来用栈顶指针是个随机值程序直接跑飞。所以不管题里给没给第一步永远先把 top 置成 -1养成肌肉记忆。判空和判满我建议写成两个独立的小函数而不是在 Dec2Bin 里用 if 直接判断。理由很简单这个题只是开始后面括号匹配、进制转换、后缀表达式求值全都要用栈基本操作封装好了后面就是复制粘贴的事。常见的写法如下void InitStack(SqStack *S) { S-top -1; } int StackEmpty(SqStack S) { return S.top -1; } int StackFull(SqStack S) { return S.top MAXSIZE - 1; }2.3 入栈出栈的返回值设计决定了你排错的速度入栈和出栈的写法网上版本五花八门。有的用 void 返回栈满直接 print 提示有的用 int 返回用 1 和 0 表示成功失败。我自己的习惯是统一返回 int成功返回 1失败返回 0。这样调用处可以用返回值做错误处理而不是程序打印一串乱码之后你还得开着调试器慢慢找。int Push(SqStack *S, ElemType e) { if (S-top MAXSIZE - 1) { return 0; // 栈满入栈失败 } S-data[S-top] e; return 1; } int Pop(SqStack *S, ElemType *e) { if (S-top -1) { return 0; // 栈空出栈失败 } *e S-data[S-top--]; return 1; }这里有个很多新手忽略的细节Pop 的参数一定得是ElemType *e把取出的元素通过指针带出来。写成int Pop(SqStack S, ElemType e)这种传值方式在外面永远拿不到弹出的元素。我每次带实验课都能看到这种错误代码编译也不报错但运行结果就是不对卡半天才反应过来。2.4 栈容量的选择不是随便拍脑袋MAXSIZE 取 100 看起来绰绰有余但考试时最好能说出理由一个 32 位 int 最多占 32 个二进制位即使再加符号位也就 33 位100 的容量足够。我见过同学把 MAXSIZE 设成 10测试普通数字没问题一测大整数就栈满Push 返回 0 又没人管输出的结果缺位很难排查。如果是扩展题要求支持更大的数我会直接把 data 的类型换成 long longMAXSIZE 相应放大到 64 或者 100。这里不推荐动态扩容版本因为 PTA 在线判题对动态内存的态度比较保守内存泄漏检测一开写不好反而扣分。定长数组在课程设计范围内已经够用。3. Dec2Bin 核心流程与完整代码3.1 先把伪代码写清楚再动手敲写代码之前我把转换流程固定成四步第一步初始化一个空栈。第二步只要 n 大于 0就用 n 对 2 取余数余数入栈n 更新为 n 除以 2 的商。第三步循环结束后不断弹出栈顶元素并输出直到栈空。第四步如果输入一开始就是 0直接输出 0因为循环一次都不会执行。这几句话看起来简单实际上恰恰是整个题最容易出 bug 的地方。第二步和第四步的顺序一旦搞反输入 0 的时候程序要么什么都不输出要么弹出一个未初始化的随机数。伪代码阶段把这些边界条件写清楚后面写 C 语言就只是翻译工作。3.2 完整可运行的 C 语言代码把上面的设计落到 C 语言里完整的程序大概是这个样子#include stdio.h #define MAXSIZE 100 typedef int ElemType; typedef struct { ElemType data[MAXSIZE]; int top; } SqStack; void InitStack(SqStack *S) { S-top -1; } int StackEmpty(SqStack S) { return S.top -1; } int Push(SqStack *S, ElemType e) { if (S-top MAXSIZE - 1) { return 0; } S-data[S-top] e; return 1; } int Pop(SqStack *S, ElemType *e) { if (S-top -1) { return 0; } *e S-data[S-top--]; return 1; } void Dec2Bin(int n) { SqStack S; InitStack(S); if (n 0) { printf(0\n); return; } while (n 0) { Push(S, n % 2); n n / 2; } while (!StackEmpty(S)) { int e; Pop(S, e); printf(%d, e); } printf(\n); } int main() { int n; scanf(%d, n); Dec2Bin(n); return 0; }这段代码在 Dev-C、Code::Blocks、VS Code 里编译运行都没有问题。PTA 上如果是函数题通常不需要你写主函数只要把上面的栈操作函数和 Dec2Bin 对应到题给的函数签名里即可。注意不同版本的题给结构体定义可能略有差异比如有的叫 SNode有的用引用传递而不是指针翻译时以题面为准。3.3 手工推演一遍执行过程以 n 13 为例把代码的执行过程走一遍比看十遍注释都管用。初始化后top -1。第一次循环n % 2 1入栈栈内元素从底到顶是 [1]栈顶下标 0n 变成 6。第二次循环6 % 2 0入栈栈内 [1, 0]栈顶下标 1n 变成 3。第三次循环3 % 2 1入栈栈内 [1, 0, 1]栈顶下标 2n 变成 1。第四次循环1 % 2 1入栈栈内 [1, 0, 1, 1]栈顶下标 3n 变成 0循环结束。输出阶段弹栈先后输出 1、1、0、1最终结果 1101。全程栈顶指针从 -1 走到 3 又走回 -1刚好对称。如果你把中间某个步骤的输出顺序搞混结果就会从 1101 变成 1011。我让学生做这道题时要求他们必须在草稿纸上把这个流程完整写一遍不许直接上机这个习惯对理解栈的“后进先出”特别管用。3.4 代码里容易被忽略的三个细节点第一个是printf(%d, e)不能换成printf(%d\n, e)。每弹出一个元素就换行的话输出会变成一列判题系统直接判格式错。我建议在 Dec2Bin 结束后统一换行中间输出不要带多余的空格或换行。第二个是栈空判断的位置。输出阶段的while (!StackEmpty(S))如果你写成while (S.top ! 0)就会漏掉栈里最底下那个元素输出的二进制会少最高位而且这个 bug 很难靠肉眼发现。老老实实用判空函数最安全。第三个是取余和除法的顺序。Push(S, n % 2); n n / 2;这两句顺序不能换先把余数取出来用掉再更新 n。反过来的话第一次取到的余数全是 0输出的结果彻底错乱。这个低级错误在赶作业的高峰期出现概率极高。4. 边界场景与踩坑记录测试用例得这么设计4.1 输入 0最容易翻车的位置我评过不少学生的代码十个里面至少有四个在输入 0 的时候输出为空。原因是他们的 Dec2Bin 里只有 while (n 0) 循环没有对 0 做特判。0 的二进制是 0这本身不需要入栈出栈但输出必须存在。前面代码里的if (n 0) { printf(0\n); return; }就是干这个用的。没有这行while 循环直接跳过后面的输出循环因为栈为空也不会执行程序一脸抱歉地什么都没打印。还有一种更隐蔽的错法特判写在了循环后面比如循环结束后再用if (n 0)但此时 n 已经被循环里的除法更新过了判断永远不成立。特判一定要放在循环之前把 0 堵在入口。4.2 负数怎么处理要提前问自己一声题目如果没有说明输入范围测试数据里可能混进负数。十进制负数转二进制常见做法是输出负号再加绝对值的二进制也就是“-1101”这种形式。实现上可以在 Dec2Bin 开始处加一段if (n 0) { printf(-); n -n; }这段代码对绝大多数测试用例可行但有一个边界坑如果 n 是 int 的最小值比如 -2147483648取绝对值后仍然超出 int 的范围后面的除法会得到一个溢出值。面对这种极端情况我通常的做法是把参数类型改成 long long或者在转字符串后再处理。但对课程作业而言负数的常规处理已经足够。你要是想稳妥一点可以这样写void Dec2Bin(int n) { unsigned int un n; // 利用无符号数的二进制表示直接转换 }把 int 转成 unsigned int 后按位处理可以让负数的二进制形式等价于其补码。但这个思路明显超出课程要求我建议只用在你实在不想处理负号逻辑的时候。4.3 栈容量和数据类型溢出前面提过 MAXSIZE 取 100是因为 int 的二进制位不会超过 32 位。万一测试数据里出现了比较大的整数比如 2147483647它的二进制是 31 个 1100 的容量依然稳稳的。但如果你把数据类型换成了 long long最大有 64 位MAXSIZE 仍然够用。这里真正要防的是另一种情况你入栈时存的是余数 0/1但如果题目扩展成转十六进制余数可能到 15打印的时候需要映射成 A-F也就是要额外准备一个字符映射表。我一直提醒学生容量问题在调试阶段基本不会暴露但 PTA 的隐藏测试点专门挑这种场景。与其到提交后才发现“运行超时”或者“答案错误”不如开题五分钟就把 MAXSIZE 设到 100 以上一次性杜绝烦恼。4.4 输出格式多一个空格都是错PTA 判题系统对输出格式非常严格。输出二进制结果时前面不能有前导空格后面不能有多余空格但换行通常可要可不要。我自己写代码的习惯是所有数字输出完后统一printf(\n)输出循环内部不打印任何空格。这样既满足大部分判题系统“忽略行末空格和换行”的宽容策略也不会因为多打空格被卡。如果题目要求一次性输出多组数据比如循环读入多个 n那每组输出后必须有换行。你可以把换行放在 Dec2Bin 函数内部也可以放在 main 的循环里选一种并保持统一。这种格式问题扣分最冤枉但每年都有一批人栽在上面。4.5 测试用例速查表我在上机前一定会准备一组测试用例按边界条件、常规值、大数三种类型分类输入期待输出测试目的00边界检查特判11最小正数210恰好为 2 的幂131101常规用例验证逆序正确255111111118 位全 1验证无多余进位1024100000000002 的 10 次方验证高位-5-101按负号方案负数处理跑测试的时候别只盯着答案对不对还要看栈顶指针在关键节点的值。最直接的办法是在 Push 和 Pop 里临时加一行 printf 打印栈顶下标和当前进制位观察是否和草稿纸上的推演一致跑通后再删掉。5. 验证与扩展思考一道简单题能挖出多少东西5.1 在 PTA 上验证时先看清题给你的是什么每个学校挂到 PTA 上的题目签名不完全一样。我这边的版本要求实现void Dec2Bin(int n)函数不需要主函数系统会自动调用。你提交前必须看清题面给的结构体定义和函数原型否则很容易出现“编译错误”。我见过一个典型错误题面给的结构体 typedef 里用了SqStack类型学生的代码里写struct SqStack编译直接报错。解决办法就是完全复刻题面给的类型名和变量名不要在题型要求之外自由发挥。还有的题要求用引用S那是 C 语法用指针*S是 C 语法两种风格混搭也是高频编译错误。5.2 从十进制转二进制扩展到任意进制二进制验证没问题后我建议你花十分钟把代码升级成通用版本把“除以 2”改成“除以 base”参数加一个进制变量。用函数签名void DecToBase(int n, int base)输出时对十进制值小于 10 的直接打印数字大于等于 10 的映射成大写字母。代码如下void DecToBase(int n, int base) { SqStack S; InitStack(S); if (n 0) { printf(0\n); return; } while (n 0) { Push(S, n % base); n / base; } while (!StackEmpty(S)) { int e; Pop(S, e); if (e 10) { printf(%d, e); } else { printf(%c, A e - 10); } } printf(\n); }这段代码的结构和前面一模一样唯一的变化是取余时的除数和字符映射。做这个扩展不是为了炫技是为了让你深刻理解“栈解决逆序问题”这个抽象能力——不管余数是 0 还是 15处理逻辑完全一致。以后遇到后缀表达式求值、括号匹配你会发现核心思路都是先把中间结果按顺序压进栈再在合适的时机弹出来。5.3 如果换个链栈代码差在哪从顺序栈改成链栈核心变化只有两个结构体从数组换成单链表节点入栈时改用malloc动态申请节点。链栈没有栈满的概念因为理论上内存足够就可以一直加。代码流程大致是typedef struct StackNode { ElemType data; struct StackNode *next; } StackNode; void Push(StackNode **top, ElemType e) { StackNode *p (StackNode *)malloc(sizeof(StackNode)); p-data e; p-next *top; *top p; }这个版本的好处是容量动态增长坏处是每入栈一个余数都要malloc一次出栈后不free会内存泄漏。对 PTA 的判题环境来说定长顺序栈往往更省心。我一般建议学有余力的同学把链栈版也写一遍不是为了交作业而是为了下次遇到“N 皇后”“表达式求值”时能根据数据规模快速决定用哪种栈。最后说点实在的带这题很多次我发现真正拉开差距的不是代码本身而是有没有耐心在草稿纸上把栈顶指针的每一步变化画清楚。很多同学代码照着抄能过但问他“为什么入栈前要判满、出栈后栈顶指针对应哪个位置”就支支吾吾了。建议你拿到这道题后先别上机找一组数把短除法、入栈、出栈的过程写一遍再去对照代码。一次调试就能看到栈顶指针从 -1 到 0 到 1 再到 0 到 -1 的变化这种直观感受比背十遍定义都深刻。后面学中缀转后缀、函数调用栈回溯你都会感谢今天把顺序栈这道题真正吃透了。