（c1）栈应用：进制转换

官官方信息技术老师·11 页·深入（追求细节与边界）·0 次浏览·38 天前

✦ （c1）栈应用：进制转换信息技术（c1）栈应用：进制转换应用

数据结构栈进制转换算法实现

栈应用：进制转换

看完你能亲手用栈把除基取余的倒序余数变成正序输出，并写出实现

按空格/→ 演示下一步

问一句

1 / 11 页

全部页面点击任意一页，跳回舞台从这页播放

数据结构栈进制转换算法实现

栈应用：进制转换

看完你能亲手用栈把除基取余的倒序余数变成正序输出，并写出实现

1第 1 页 · 栈应用：进制转换

回顾：进制与余数

上一页我们知道了栈擅长「后进先出」。那进制转换为什么用得上它？先回忆小学做过的事：把十进制数不断除以 2，记下每一步的余数——但为什么余数要倒着读？

除基取余

十进制数不断除以目标进制基数，每次记下余数，直到商为 0

余数倒序读

最先算出的余数是最低位，最后算出的才是最高位，必须逆序拼读

倒序的自然来源

拆解顺序从低位开始，而书写习惯从高位开始，方向相反

剥洋葱对应 →除基取余

剥下最外层对应最低位，最后剥到的核心才是最高位

13 \div 2 = 6 \cdots 1,\; 6 \div 2 = 3 \cdots 0,\; 3 \div 2 = 1 \cdots 1,\; 1 \div 2 = 0 \cdots 1 \;\Rightarrow\; (1101)_2

2第 2 页 · 回顾：进制与余数

为什么需要栈

上一页我们用短除法把 13 转成二进制：依次除 2 取余。可你有没有注意到，最先算出来的余数排在最低位，最后算出的反而排在最高位？产生顺序和输出顺序刚好相反。

余数先算后用

短除法中余数按计算顺序依次产生，但不能按此顺序直接输出

顺序恰好相反

输出要低位在前，而余数产生是高位在前，两者正好倒置

倒置即后进先出

后产生的先输出，正是栈的后进先出（LIFO）特性

餐厅餐盘摞对应 →栈存余数

后洗好的餐盘放在最上层、先被取走，对应后算出的余数先被输出

13 = 1101_2,\quad (13 \bmod 2)^{(1)}(13\div2 \bmod 2)^{(2)}\cdots \text{逆序输出}

3第 3 页 · 为什么需要栈

算法流程图

从上往下读：循环中每次取余入栈，n 变 0 后进入出栈输出阶段。菱形是判断分支。

图解渲染中…

d1：栈顶保存的余数按低位到高位排列g1：出栈顺序即从高位到低位，得到结果

4第 4 页 · 算法流程图

用顺序栈实现转换

用 C 实现核心函数 convert：余数依次入栈，再逆序出栈打印，完成进制转换。

代码高亮加载中…

convert 中：n%base 的余数依次入栈；n/=base 更新商；栈空后逐个出栈打印，天然实现低位到高位的逆序。

5第 5 页 · 用顺序栈实现转换

逐行走读代码

逐行走读转换代码，跟踪 1348→2504 过程中栈的每一步变化。

循环取余

1348%8=4，余数 4 先入栈；除法保证下轮处理商 168

余数继续入栈

168%8=0，栈底追加 0；0 也是有效数位，不能跳过

商为 0 退出

依次再压 6、2，1348/8/8/8/8=0，入栈循环结束

逆序出栈

弹栈顺序 2、5、0、4，恰好是高位到低位

拼接输出

边弹边拼成字符串 "2504"，与余数正序 4052 相反

6第 6 页 · 逐行走读代码

两个循环怎么写

同样是转换算法，while 和 do-while 只差在循环条件判断的时机，n=0 这个边界直接暴露区别。

while 写法

先判断条件，再执行入栈
n=0 时不进循环，栈为空
必须单独处理 n=0，否则输出为空

do-while 写法

先执行入栈，再判断条件
n=0 也至少入栈一次余数 0
天然覆盖 n=0，无需特判

当 n 可能为 0 时选 do-while（至少执行一次）；当 n 保证非零时，两者等价，while 更常见。

7第 7 页 · 两个循环怎么写

大于十进制怎么办

前页代码里余数直接当数字打印，转二进制、八进制都没问题。可一旦换成十六进制，余数会出现 10~15——总不能打印「13」冒充一位数，得有办法表示这六种新「数字」。

余数越界

base=16 时余数取 0~15，超出 0~9 的字符范围

约定映射

10~15 分别记作 A~F，一个字符表示一位

静态字符表

预先存好 "0123456789ABCDEF"，按下标查字符

查表代替计算

pop 出余数 r 后，输出 table[r] 而非 r 本身

身份证省份代码对应 →数字查表映射

代码 11 代表北京，同样用编号查表换出真实含义

8第 8 页 · 大于十进制怎么办

自测：栈顶是谁

点击作答

把 n=13 转为二进制：13÷2 余 1，6÷2 余 0，3÷2 余 1，1÷2 余 1。余数依次入栈后，第一个出栈的元素是？

9第 9 页 · 自测：栈顶是谁

要点收束

✓进制转换本质：不断除基取余，逆序输出
✓余数产生顺序与输出顺序天然相反，正是栈的形状
✓顺序栈把这个'逆序'变成数组下标问题
✓边界在余数≥10与n=0，而非算法本身
✓'逆序输出需求→栈'是可迁移的识别模式

延伸主题：队列：先来先服务的另一面递归调用为什么也靠栈栈实现表达式求值

10第 10 页 · 要点收束

课后思考

先合上讲义自己想五分钟，再对照下面的参考思路。

1倒序输出余数必须用栈吗？如果只存余数到数组、最后倒着打印，效果一样吗？

参考答案效果等价。数组倒序遍历和栈的弹出都是逆序，栈的价值在于它把这个「后进先出」的动作封装成了固定接口，不必自己维护下标。

2转换成负数进制（如 -2 进制）时，余数可能为负，这个算法还成立吗？

参考答案不直接成立。商和余数的定义会变：要保证余数非负，需调整商（如 c = -⌈n / d⌉ 这类修正）。压栈-弹出的框架不变，变的是取余规则。

3「算好后先存、再逆序取出」这个模式，除了进制转换还能用在哪里？

参考答案凡是处理顺序与产出顺序相反的场景：递归调用的调用栈、括号匹配、函数返回地址、浏览器后退。识别出「逆序需求」，就找到了栈的用武之地。

11第 11 页 · 课后思考