简介C实现的顺序栈与链栈源码演示将十进制数依次转换为二进制、八进制和十六进制面向正在学习数据结构与算法、希望从代码层面理解栈的原理的读者可帮助巩固线性表与链表知识。压缩包共13个文件包含核心C源码文件、Visual Studio工程配置文件、编译链接生成的可执行程序以及pdb/obj等调试信息整体约1.06MB解压后可直接运行查看效果。目前已有6167人学习下载。阅读源码可以对比顺序栈基于数组的连续存储与链栈基于链表的动态内存分配两种实现掌握压栈、弹栈操作并通过短除法逐次取余、入栈、出栈组合结果直观体会栈的LIFO特性在进制转换中的运用。配套工程文件方便还原Visual Studio编译环境便于自行修改除数、扩展更多进制转换或继续完善边界处理是初学者兼顾理论与动手的优质实例。1. 为什么拿顺序栈和链栈练进制转换这份源码解决的不只是“转进制”如果你刚把C的线性表、链表学完正愁找不到一个能把这两种结构同时练透的小项目那“用顺序栈和链栈把十进制转成2、8、16进制”这份源码值得你花一晚上敲一遍。表面看它只是做进制转换但骨子里它逼着你把栈的“后进先出”逻辑、数组模拟栈的容量管理、链表节点的内存释放这些基本功全部过一遍。除基取余法算出来的余数是逆序的而这恰好和栈的弹出顺序一致所以用栈实现进制转换几乎是教科书级的匹配。这份源码适合刚学完栈和链表、想用最小代码量验证自己理解程度的初学者也适合正在准备数据结构课程设计、需要一份能讲清楚设计思路的参考实现的人。它不复杂但能炸出的坑不少。2. 进制转换与栈的选型从除基取余法到两种存储结构的分工2.1 除基取余法为什么余数要倒着读十进制数转任意基数的核心算法叫“除基取余法”不断用目标进制数去除原数记下每次的余数直到商为0最后把所有余数从后往前排列。举个例子把十进制13转成二进制13 除以2商6余16除以2商3余03除以2商1余11除以2商0余1。正向得到的余数是1、0、1、1但正确结果是1101正好是反过来的。这个“倒过来”就是栈存在的意义。如果按顺序把每次的余数压进栈当除法结束时栈顶恰好是最新得到的余数也就是最终结果的最左边一位。依次出栈就能得到正确的进制字符串。所以栈在这个场景下不是可有可无的装饰而是把“后进先出”特性和数学计算过程天然对齐的工具。2.2 顺序栈与链栈选型静态数组还是动态节点顺序栈底层是连续数组出栈入栈只改变栈顶指针操作时间复杂度O(1)但需要预先分配容量一旦超过就得扩容。链栈底层是单链表节点每次入栈都要new一个新节点出栈要delete旧节点不存在“栈满”问题但频繁申请和释放内存会带来额外开销。在这个进制转换任务里一次转换产生的余数个数最多也就是十进制数在目标进制下的位数。比如32位int转2进制最多31位转16进制最多8位。所以顺序栈完全够用甚至可以把容量固定为32。链栈的价值在于让你体验另一种存储结构下的接口设计——如何用头插法模拟入栈如何判断空栈以及如何避免内存泄漏。我建议你把两种都实现一遍因为面试里经常会被问到“顺序栈和链栈在什么场景下选哪个”自己亲手写过之后这个问题的答案就不再是背出来的。3. 顺序栈实现10进制转2/8/16进制数组模拟栈的完整代码3.1 顺序栈的结构体设计与初始化顺序栈我习惯用动态数组而不是固定数组这样还能顺手练一下realloc式的扩容思路。结构体里三个成员存储元素的指针data、栈顶下标top、当前容量capacity。注意top指向的是栈顶元素的位置还是下一个空位不同写法会影响入栈出栈的判断条件。这里我统一采用top指向当前栈顶元素空栈时top -1。#include iostream #include cstdlib using namespace std; typedef struct { int *data; int top; int capacity; } SeqStack; void initStack(SeqStack s, int cap) { s.data (int*)malloc(sizeof(int) * cap); s.top -1; s.capacity cap; } int isFull(SeqStack s) { return s.top s.capacity - 1; } int isEmpty(SeqStack s) { return s.top -1; } void push(SeqStack s, int val) { if (isFull(s)) { // 扩容为原来的两倍实际应用中不能忽略这一步 s.capacity * 2; s.data (int*)realloc(s.data, sizeof(int) * s.capacity); } s.data[s.top] val; } int pop(SeqStack s) { if (isEmpty(s)) { cout 栈空无法出栈 endl; return -1; } return s.data[s.top--]; }这里初始化时如果cap给32转32位int的二进制刚好够用但为了避免极端大数我写了扩容逻辑。push时先判满满了就把容量翻倍这比直接在main里写死一个数组要稳妥。pop返回栈顶值同时top减一。注意这段代码没有做malloc失败检查教学代码可以这样但实际工程里一定要判断返回指针是否为nullptr。3.2 入栈、出栈与进制转换函数核心转换函数接收十进制数num和目标进制base只要base在2到16之间就行。循环里不断取余数压栈结束后再依次出栈把余数转成对应的字符输出。void convertBySeqStack(int num, int base) { if (base 2 || base 16) { cout 只支持2到16进制 endl; return; } SeqStack s; initStack(s, 8); // 初始容量8后面会自动扩容 int n num; if (n 0) { cout 0 endl; return; } while (n 0) { push(s, n % base); n / base; } cout 转换结果: ; while (!isEmpty(s)) { int digit pop(s); if (digit 10) { cout char(0 digit); } else { cout char(A digit - 10); } } cout endl; }这段代码最关键的是循环退出条件n 0。如果你把条件写成 n 0就会多算一位且永远跳不出去因为n / base最终会变成0然后一直除下去还是0造成死循环。另一个细节是0的特殊处理因为0不需要进入while循环但结果不能是空串所以要单独输出。3.3 主函数调用与输出演示主函数里可以读入用户输入的十进制数和目标进制也可以直接写死几个测试用例。为了快速看到效果我一般会让它连续转换多个进制。int main() { int num; cout 请输入一个十进制整数: ; cin num; for (int base : {2, 8, 16}) { convertBySeqStack(num, base); } return 0; }这里用C11的初始化列表遍历2、8、16三个进制把同一个十进制数分别转换。如果你用的是老编译器可以改成普通数组循环。这样跑一次就能同时看到三种进制的输出方便对照。注意这种转换方式只适合非负整数负数处理我会在第6章专门讲。4. 链栈实现同样的转换用链表节点代替数组边界要更小心4.1 链栈节点结构与入栈出栈实现链栈的每个节点包含数据域和指针域。栈顶指针top是指向第一个节点的指针入栈时新节点插到最前面出栈时删掉第一个节点。这里和单链表的头插法完全一致区别只是限制只能在栈顶操作。#include iostream using namespace std; typedef struct StackNode { int data; struct StackNode *next; } StackNode; typedef struct { StackNode *top; int size; } LinkStack; void initLinkStack(LinkStack s) { s.top nullptr; s.size 0; } void pushLink(LinkStack s, int val) { StackNode *newNode new StackNode; newNode-data val; newNode-next s.top; s.top newNode; s.size; } int popLink(LinkStack s) { if (s.top nullptr) { cout 链栈为空 endl; return -1; } StackNode *temp s.top; int val temp-data; s.top s.top-next; delete temp; s.size--; return val; }这里有个常见误区有人会把LinkStack直接定义成一个节点指针也就是StackNode *top然后写push时修改的是top本身。那样不是不行但不方便同时维护栈大小。我加了size字段后面打印栈长或调试时会很方便。入栈时要注意new出来的节点必须先用new分配内存不能用局部变量否则函数结束后栈顶指向的内存就失效了。出栈时先把栈顶指针指向下一个节点再delete原栈顶节点顺序不能反否则你就丢了后续节点的地址。4.2 进制转换函数与内存释放链栈版的转换函数和顺序栈版逻辑完全一样只是调用不同的入栈出栈函数。因为链栈没有容量上限少了一半扩容的心思但多了内存释放的责任。void convertByLinkStack(int num, int base) { if (base 2 || base 16) { cout 只支持2到16进制 endl; return; } LinkStack s; initLinkStack(s); if (num 0) { cout 0 endl; return; } while (num 0) { pushLink(s, num % base); num / base; } cout 转换结果: ; while (s.top ! nullptr) { int digit popLink(s); if (digit 10) { cout char(0 digit); } else { cout char(A digit - 10); } } cout endl; // 转换完成后栈已经空所有节点都已通过popLink释放 // 但为了安全再归零一次 s.top nullptr; s.size 0; }这里我在最后加了两行归零操作其实popLink已经把节点删完了但如果你曾经在循环里跳过某些节点这里就能兜底。链栈版最需要记住的是每一个new出来的节点必须对应一次delete。popLink里已经做了delete所以正常流程不会泄漏。但如果你自己写了一个清空函数只把top设为nullptr那所有剩余节点全泄漏了。主函数和顺序栈版几乎一样只是调用不同的函数。你也可以把两个版本放进同一个工程用注释切换观察两种实现的输出是否一致。5. 避坑顺序栈扩容、链栈判空、字符映射这些坑一次说清5.1 顺序栈栈满不扩容直接溢出写坏内存现象转一个很大的十进制数成二进制时程序崩溃或者输出乱码但小数字正常。原因初始化顺序栈时容量只给了8或16而一个int转成二进制最多有31位如果没写扩容逻辑当top增加到capacity-1后再push就会越界写入破坏相邻的内存。可能当时没崩但后续malloc或free报错说“heap corruption”。解决在push函数里强制加一个isFull判断满了就realloc翻倍。这是我在第3.1节已经写过的做法。千万别指望输入的数字不会太大用户随手输入2147483647转成二进制正好31位你容量32勉强够但如果写的是转成2进制同时又要存其他中间值就不保险了。统一扩容最省心。5.2 链栈出栈后不释放内存跑完程序内存不降现象循环转换几千个数字后任务管理器里进程内存一直涨甚至报内存不足。原因链栈用new创建节点如果你只做top top-next来模拟出栈而不delete旧节点每个节点占的内存就成了无主垃圾。C不像Java有自动垃圾回收这种泄漏会一直累积。解决出栈时先保存指针再移动top然后delete旧指针。我想强调一下这个顺序先让临时指针指向top节点然后toptop-next最后delete临时指针。如果你先delete再移动你访问了已经释放的内存是未定义行为。代码在第4.1节已经给全。5.3 10到15转成A到F时用数字直接输出会乱码现象转16进制时余数是10、11、12输出却成了冒号、分号等字符。原因字符0到9的ASCII码是48到57而10到15对应ASCII码是58到63也就是:, ;, , , , ?。直接cout 10输出的是数字文本“10”但如果你用了cout (char)digit就会把10当成ASCII码转字符出来是换行符之类的控制字符或冒号。解决做字符映射。digit 10时输出0digitdigit 10时输出Adigit-10。也就是我第3.2节那段if-else逻辑。更简洁的写法是直接用数组char digits[] 0123456789ABCDEF;然后输出digits[digit]这也是很多教科书推荐的做法能避免手写ASCII偏移出错。5.4 链栈的top与顺序栈的top语义不同判断条件写反现象链栈判空用了s.top s.capacity - 1这种顺序栈的写法编译不过或者运行异常。原因顺序栈的top是整型下标链栈的top是指针。两者一个指向数组内位置一个指向链表节点。新手很容易混。比如链栈空栈应该是top nullptr而非top -1顺序栈空栈则是top -1而非top nullptr。解决写代码前明确告诉自己顺序栈top是int链栈top是地址。建议给两类结构体取不同的字段名比如顺序栈用topIndex链栈用topNode从命名上强制区分。我在第3、4章的代码里已经用不同的上下文区分开实际工程中命名更要刻意。5.5 用int接收转换结果大数直接溢出变成负号现象把十进制数转换成二进制后想把它当成一个整数存回int变量里结果输出变成负数或者完全不匹配。原因比如十进制1024转二进制是10000000000这有11位如果你把出栈字符拼成整数这个值已经超过int能表示的语义范围。再比如十进制2147483647转成二进制结果有31位转成int会出错或溢出。进制转换的结果本质上是字符串不是数值。解决输出时逐字符打印或者用std::string拼接返回。不要试图把二进制结果再解析成int。如果你的目标是得到某进制的数值表达字符串就是终点。我在第3章的代码只打印不存储正是这个原因。6. 把这套栈再往前走一步负数、小数、任意进制与单元验证前面实现的转换都限定在非负整数而且只输出不返回。实际应用里往往要处理负数和小数还要把结果封装成可复用的函数。这里我至少会把转换结果改造成std::string返回而不是直接在控制台打印。负数处理非常简单先取绝对值按整数方法转换最后在前边加负号。比如-13转二进制先转13得1101再加负号成-1101——注意这只是数值表达的符号不是计算机补码。如果想要补码那是另一个话题通常要先把负数转换成无符号整数再做位运算这个就不在纯数据结构范围内展开了。小数转进制用“乘基取整法”小数部分不断乘base取出整数位作为结果。把整数部分和小数部分分开处理最后用小数点连接。如果你想把这份源码升级成支持任意进制的工具我建议把转换函数参数改成基数和正负标记并添加一个验证函数核心代码不超过20行。验证方法比你想象的重要。我一般会写一个断言式测试把0、1、127、255、1024、2147483647这些边界值分别用2、8、16进制转换再和系统自带的计算器结果比对。特别注意0的转换结果不能是空串1的转换结果每个进制下都应该是单字符。条件允许的话再用随机数生成几组数据手动转成对应进制和程序输出对照。这里给一个返回字符串和验证函数的最小示例帮助你把这套栈代码真正变成自己的工具string convertBase(int num, int base) { if (num 0) return 0; bool negative num 0; unsigned int absNum negative ? -num : num; string result; while (absNum 0) { result char(0123456789ABCDEF[absNum % base]) result; absNum / base; } if (negative) result - result; return result; } bool verifyConvert(int num, int base) { // 用最基本的方式验证手动拼一个期望值或者用itoa对比 char buf[64]; itoa(num, buf, base); // Windows下可用Linux下自己实现或跳过 string expected(buf); return convertBase(num, base) expected; }这个示例跳过了栈因为当你想要的只是“结果”时直接用字符串头插法更高效。但你依然可以保留栈版本把它封装成内部函数重点理解“后进先出”在算法中的天然拟合。从那以后我每次写栈相关的代码都会强制先跑一遍空栈、栈满、大数、0、负数这几个用例确认没有边界问题再去谈优化。这个习惯帮我省掉了不少调试时间希望你也能把验证嵌进自己的练习流程里希望帮到你。本文还有配套的精品资源点击获取