进制转换必学：顺序栈与链栈实现十进制转2/8/16进制

简介进制转换是程序开发与数据结构学习中绕不开的基础操作十进制转二进制、八进制和十六进制看似简单却隐藏着输出顺序与计算顺序相反的核心难题。除基取余产生的余数天然是低位在前、高位在后而人类阅读数字却需要高位在前这种顺序矛盾恰好与栈的后进先出特性完美契合。理解栈的LIFO语义后顺序栈与链栈便成为实现进制转换的标准范式顺序栈以数组和top指针提供高效读写链栈则以动态节点实现灵活扩容。从进制换算到括号匹配、表达式求值乃至深度优先搜索栈都在解决同一类“先产生后处理”的序问题。本文从除基取余原理出发对比两种栈的选型差异并给出C语言源码、参数设计与边界陷阱规避方法帮助读者在课程设计与工程实践中快速落地。1. 把十进制转成 2/8/16 进制为什么“栈”会是标准答案课程设计拿到“用顺序栈、链栈将十进制转为 2、8、16 进制”这种题目第一反应多半是“这不就是除基取余吗”。真正动手时才发现算法五分钟能写完卡住你的却是另一个问题除基取余算出来的余数顺序天生是反的程序没法像草稿纸一样从最后往前读。栈的后进先出特性恰好能把“低位先生成、高位后生成”这个顺序重新掰正于是顺序栈和链栈就成了进制转换题目的标准实现范式。这篇笔记直接给你可复现的 C 语言源码思路、参数设计和踩坑记录适合正在写数据结构课程设计、或者想搞懂栈到底怎么落地的同学照着改。2. 除基取余法为什么要用栈保存结果顺序问题与两种栈选型2.1 除基取余法的输出顺序和数值顺序是反的十进制转 2、8、16 进制算法是同一个除基取余。拿 127 转 8 进制举例手工除法过程是127 除以 8商 15余 715 除以 8商 1余 71 除以 8商 0余 1。把余数从下往上读得到 177这就是 127 的八进制结果。注意这里面的顺序关系第一次除法得到的余数 7是最终结果的个位也就是最低位最后一次除法得到的余数 1才是最高位。换句话说余数的产生顺序是低位在前、高位在后但人阅读数字的顺序是高位在前、低位在后。草稿纸上可以从下往上看程序里不行——循环只能顺着往下跑先算出来的一定先碰到。这时候栈就派上用场了。栈是后进先出结构先算出的低位余数先入栈会被压到栈底后算出的高位余数后入栈反而在栈顶。转换结束时不断出栈第一个弹出的是最高位最后一个是最低位恰好把除基取余的倒序输出纠正成正序输出。这不是什么玄学而是栈的 LIFO 语义和“先产生的结果最后显示”这个需求天然匹配。还有一类实现是用数组保存余数最后倒着遍历数组输出。数组不是不能用但你需要先算出到底有多少位或者预留一个足够大的下标回填游标。栈把“到底存了多少个”这件事封装在了 top 指针或者 count 字段里业务代码不需要关心具体位数这是它在这个场景里比数组顺手的原因。递归也能做到逆序输出本质上是往系统调用栈里压栈原理相通只是不如显式栈好控制。2.2 顺序栈与链栈的选型对比固定容量、动态扩容与代码量权衡顺序栈的底层是数组加一个 top 下标入栈就是data[top] x出栈就是x data[top--]一次内存读写常数时间。缺点是容量必须提前定死定小了转大数的二进制会越界定大了有少量浪费。链栈的底层是单链表top 指针相当于链表的头指针入栈用头插法出栈把头节点摘下来。容量理论上不限每来一个元素才申请一个节点。缺点是每次 push 和 pop 都要 malloc、free频繁调用时有内存碎片指针操作也比数组下标更容易写错。对比维度顺序栈链栈底层存储数组 top 下标单链表 头指针容量固定初始化时定死动态节点随用随建入栈/出栈数组下标读写效率高每次 malloc/free有额外开销内存特征连续缓存友好节点分散可能存在碎片实现难度低几个函数就能写完略高要注意指针指向和释放课程设计如果要求两个都实现我的建议是顺序栈版本把容量按二进制满位数放大一点链栈版本重点把内存释放写对。转换逻辑本身两者完全一致区别只在 push 和 pop 内部怎么操作。这道题的得分点通常不在算法上而在栈结构定义、边界判断和内存管理这些缝里后面第三章和第四章会逐个落到代码上。3. 顺序栈实现进制转换ADT 定义、入栈出栈和转换函数参数设计3.1 顺序栈的结构体与五个基础操作怎么写顺序栈的结构体定义和基础操作是整套源码的地基。top 初始化为 -1表示空栈入栈时先移动 top 再写入数据出栈时先取数据再把 top 减一这两个写法顺序不能反否则会访问到 -1 下标。完整定义如下#define MAX_STACK_SIZE 64 typedef struct { int data[MAX_STACK_SIZE]; int top; } SeqStack; void initStack(SeqStack *s) { s-top -1; } int isFull(SeqStack *s) { return s-top MAX_STACK_SIZE - 1; } int isEmpty(SeqStack *s) { return s-top -1; } int push(SeqStack *s, int x) { if (isFull(s)) return 0; s-data[s-top] x; return 1; } int pop(SeqStack *s, int *x) { if (isEmpty(s)) return 0; *x s-data[s-top--]; return 1; }这里有几个参数设计上的细节。push 和 pop 都返回 int 作为操作是否成功的标志push 失败原因是栈满pop 失败原因是栈空。调用方拿到返回值后决定是继续转换还是报错退出。pop 的值通过出参int *x带出而不是直接 return 数据因为返回值已经被用来承载状态码了这个习惯在写更复杂的栈应用时能保持接口统一。s-top是前置自增先让 top 从 -1 变到 0再往 data[0] 写。如果写成s-data[s-top] x第一次入栈就会把数据写到 data[-1]这是顺序栈最常见的翻车点之一。容量定 64 的依据是C 语言里 int 在常见平台是 32 位二进制满位数最多 32 位加上结束符和防御余量64 个 int 足够不用为了省几个字节把 MAX_STACK_SIZE 压到 16 或 8那会给后面的转换埋坑。3.2 十进制转 2/8/16 进制的核心转换函数转换函数是整套源码的主干除基取余得到的余数依次入栈转换结束后依次出栈出栈顺序就是正确的进制位序。为了避免余数 10 到 15 映射成字符时写一堆 if-else用查表法直接映射static const char digits[] 0123456789ABCDEF; void decimalToBase(int num, int base, char *out, int outSize) { SeqStack s; initStack(s); if (num 0) { push(s, 0); } while (num 0) { push(s, num % base); num / base; } int idx 0; while (isEmpty(s) 0 idx outSize - 1) { int r; pop(s, r); out[idx] digits[r]; } out[idx] \0; }函数签名的四个参数都有讲究。num 是被转换的十进制整数base 是目标进制调用时传 2、8 或 16。out 是调用方提供的字符缓冲区outSize 是缓冲区大小用来防止出栈循环把字符串写穿。出栈循环里idx outSize - 1这个条件保证即使缓冲区偏小最终也一定会在末尾补上字符串结束符不会产生越界写。查表法digits[r]是这个函数的点睛之笔它同时处理了 0 到 9 的数字字符和 10 到 15 的字母字符。如果写成0 rr 为 10 时得到的 ASCII 码是 58对应字符是冒号而不是 A十六进制转换就会整体错乱。这段逻辑在后面链栈版本里原样复用所以我把 digits 表定义在文件顶部而不是函数内部。if (num 0)的特判是必须的否则 while 循环一次都不进出栈循环也拿不到任何数据0 转任何进制都会输出空字符串。3.3 完整调用示例与“为什么返回字符串而不是打印”转换函数写好后在 main 函数里调用验证。把同一个十进制数分别转成二进制、八进制、十六进制打印出来人工核对#include stdio.h int main(void) { char buf[80]; int n 255; decimalToBase(n, 2, buf, sizeof(buf)); printf(255 - 2进制: %s\n, buf); decimalToBase(n, 8, buf, sizeof(buf)); printf(255 - 8进制: %s\n, buf); decimalToBase(n, 16, buf, sizeof(buf)); printf(255 - 16进制: %s\n, buf); return 0; }运行结果是三行明确的输出255 转二进制是 11111111转八进制是 377转十六进制是 FF。这个结果可以和 Windows 计算器或者printf(%x, 255)对照能对上就说明转换逻辑没有根本性错误。我把结果封装成字符串返回而不是在函数内部直接 printf是考虑到调用方的真实需求转换结果可能要被其他模块拼接、比较、写入文件或者作为另一个函数的输入直接打印会把函数钉死在“只能看不能用”的位置。这也是课程设计答辩时老师大概率会问的问题提前想清楚这个接口设计理由答起来会顺很多。outSize 参数则是防御性编程的体现C 语言字符串操作最容易出的问题就是缓冲区越界多传一个容量参数出栈循环就有了刹车。4. 链栈实现进制转换头插法 push/pop、内存释放与调用差异4.1 链栈节点和栈结构top 指针加 count 的取舍链栈的每个节点就是一个 int 数据加一个指向下一个节点的指针栈结构体只需要保存栈顶指针。我在栈结构体里额外加了一个 count 字段记录当前栈内元素个数入栈加一、出栈减一这样判断栈是否为空只需要看 count 是否为 0调试时也能直接看到栈里还剩多少元素不用临时遍历链表数。定义如下typedef struct StackNode { int data; struct StackNode *next; } StackNode; typedef struct { StackNode *top; int count; } LinkStack;ststart: 这是 C 语言课程设计里很标准的链栈形态。有些教材只声明 top 指针不写 count判断栈空就用s.top NULL求元素个数才临时遍历。两种都没有错但加了 count 之后pop 和 clear 函数里维护栈大小的逻辑会更直观填代码时不容易出现“指针已经为空了但业务层还以为有数据”的错觉。4.2 链栈 push/pop/clear 实现malloc、free 与顺序栈操作差异链栈的 push 是头插法新节点的 next 指向原来的栈顶再把 top 更新到新节点。pop 的流程比顺序栈多一步——取完数据必须 free 掉被弹出的节点否则每转换一个数字就泄漏一块小内存。同时补一个 clearStack 用于一次性清空整条链int push(LinkStack *s, int x) { StackNode *node (StackNode *)malloc(sizeof(StackNode)); if (node NULL) return 0; node-data x; node-next s-top; s-top node; s-count; return 1; } int pop(LinkStack *s, int *x) { if (s-top NULL) return 0; StackNode *tmp s-top; *x tmp-data; s-top tmp-next; free(tmp); s-count--; return 1; } void clearStack(LinkStack *s) { StackNode *p s-top; while (p ! NULL) { StackNode *next p-next; free(p); p next; } s-top NULL; s-count 0; }push 和顺序栈最大的差异是不需要判满malloc 成功就有地方放malloc 返回 NULL 时才返回 0。pop 里先用临时变量 tmp 存下原栈顶取数据、移指针、free 三步缺一不可。如果直接把s-top s-top-next写在前面原栈顶节点就找不到了内存泄漏就这么来的。clearStack 里也是同理必须先用 next 变量把下一个节点存住才能 free 当前节点。链栈在进制转换这个场景里malloc/free 的频率很低——单个 int 转二进制最多入栈 32 次出栈 32 次总共 64 次内存操作几乎感觉不到性能差异。真正需要注意的只有一点无论什么时候写的链栈代码pop 必 freeclear 必遍历这是血泪经验换来的习惯。4.3 链栈版转换函数转换逻辑为什么可以原样保留链栈版的 decimalToBase 和顺序栈版的核心循环完全相同只是栈变量的类型从 SeqStack 换成了 LinkStackvoid decimalToBaseLink(int num, int base, char *out, int outSize) { LinkStack s {0}; if (num 0) { push(s, 0); } while (num 0) { push(s, num % base); num / base; } int idx 0; while (s.top ! NULL idx outSize - 1) { int r; pop(s, r); out[idx] digits[r]; } out[idx] \0; clearStack(s); } void decimalToBase(int num, int base, char *out, int outSize) { SeqStack s; initStack(s); /* 与链栈版本相同的入栈出栈循环 */ }最终我给源码组织的建议是一个 .c 文件里放顺序栈结构与操作另一个 .c 文件放链栈结构与操作各自实现一个 decimalToBasemain 函数里分别调用两个版本并打印结果。这样的组织方式在课程设计说明书里也容易写清楚。源码模块职责seq_stack.h / seq_stack.c顺序栈结构体、init/push/pop/isEmptylink_stack.h / link_stack.c链栈结构体、push/pop/clearStackconverter.cdigits 查表、两个 decimalToBase 转换函数main.c调用两个版本输出 2/8/16 进制结果两个版本的转换函数主体几乎一样这不是偷懒而是“栈逻辑和存储实现解耦”的体现。业务代码只需要知道有 push 和 pop 这两个操作存在不需要关心底层是数组还是链表。答辩时把这个道理讲清楚比反复强调你记住了多少语法更有价值。5. 避坑进制转换栈实现最容易翻车的 5 个细节5.1 余数超过 9 输出问号或乱码查表法还是 if-else现象十进制 255 转十六进制结果应该是 FF实际输出却是问号、冒号一类的字符或者整段结果错位。原因字符映射写成了out[idx] 0 r。r 是 0 到 9 时没问题因为字符 0 到 9 的 ASCII 码连续r 是 10 到 15 时0 r得到的是 58 到 63对应冒号、分号、问号不是 A 到 F。解决用查表法static const char digits[] 0123456789ABCDEF;然后out[idx] digits[r];。这一行同时覆盖数字和字母比 if-else 分支少写一堆判断还不会漏。如果你后面要扩展到 36 进制只需要把表加长别处不用动。5.2 0 转任何进制都输出空串特判入栈现象调用转换函数参数 num 为 0 时返回的字符串是空的连一个字符都没有。原因除基取余的 while 循环条件是num 00 一开始就不满足条件整个循环直接跳过栈里没入过任何余数出栈循环当然也拿不到数据。解决在进入循环之前加一行if (num 0) push(s, 0);让 0 作为一个普通余数入栈出栈时自然输出字符 0。这条特判看着不起眼却是进制转换代码里最容易漏掉的边界。5.3 转二进制时栈容量预估不足按 sizeof(int)*8 估算现象顺序栈的 MAX_STACK_SIZE 设成 16转八进制和十六进制都正常转二进制偶发崩溃或输出乱码。原因八进制一位对应 3 个二进制位十六进制一位对应 4 个二进制位同样一个 int十六进制最多 8 位二进制最多 32 位。栈容量按十六进制的余数个数估算转二进制时余数个数翻了好几倍数组下标直接越界。解决容量至少按sizeof(int) * 8 1设置。32 位 int 对应 33 个元素加上结束符的安全余量我直接设成 64。别为了省两三百字节的内存把容量卡得太死顺序栈本身就是固定开销多出的部分是买越界安全的保险。5.4 链栈 pop 忘记 free内存泄漏与野指针现象单个数值转换一次看不出问题循环调用一万次后内存占用肉眼可见地上涨用 Visual Studio 的 CRT 内存泄漏检测功能会报告泄漏。原因pop 函数里只写了s-top s-top-next没有保留原节点的地址并调用 free被弹出的节点变成了无法访问的孤儿内存。这是链栈操作里最有代表性的错误编译器不会报错程序也能继续跑但内存只会进不会出。解决pop 里先用临时变量保存旧 top取数据、移动指针之后立即free(tmp)。clearStack 也要用 next 变量暂存后才能逐个 free。把这两步养成习惯链栈代码才算真正写完整。5.5 负数输入的余数约定取模符号与 unsigned 处理现象输入 -7 转十六进制有的函数输出乱码有的输出 FFFFFFF9有的输出 -7结果五花八门。原因C 语言对负数取模的符号与被除数保持一致-7 % 16的结果是 -7 而不是 9。余数为负时查表digits[-7]访问的是数组前方内存属于未定义行为乱码就是这么来的。解决先约定语义再动手。若约定只处理非负整数在函数入口直接 if 判断并返回错误码。若想要 int 在内存里的真实位模式把参数转换成unsigned int再做除法取余-1 会输出 32 位全 1 的 FFFFFFFF和printf(%x, -1)的结果一致。我一般建议课程设计默认非负输入但把负数语义写进注释这样边界问题变成文档问题代码本身不背锅。6. 把 2/8/16 推向任意进制查表法扩展、printf 对照验证与栈的复用边界6.1 通用进制转换的查表设计把查表字符串从 16 位加长到 36 位转换函数就立刻支持 2 到 36 进制0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ。base 参数传多少都没关系余数 r 最大是 base - 1只要 r 不超过表的最大下标输出就不会错。这里唯一要注意的是目标字符集如果要求小写就把表换成小写字母版本其余代码一个字都不用改。RGB 颜色值转十六进制、权限位掩码转可读字符串、哈希摘要展示底层用的都是同一套逻辑。6.2 用 printf 做结果对照与栈场景复用验证进制转换函数最笨也最可靠的办法是和平台自带的格式化输出对拍printf(%x, 255)输出 ffprintf(%o, 255)输出 377你写的栈实现应该输出相同结果。对拍不一致时优先检查自己的出栈顺序和字符映射而不是怀疑编译器。栈解决的不只是进制转换这一道题括号匹配、表达式求值、递归改非递归、深度优先搜索的显式栈底层都是同一句话先产生的后处理后产生的先处理。进制转换是这句话最短小的实验场顺序栈和链栈两种写法都跑通之后再遇到这类序的问题就直接有肌肉记忆了。我自己写这套函数时习惯把 digits 表放在文件顶部所有字符映射收敛到一行查表代码里遇到输出异常先 printf 栈顶值核对入栈顺序。这个习惯帮我挡掉过不少次输出乱码的翻车也希望帮到你。本文还有配套的精品资源点击获取