简介一份面向C学习者的数据结构实践资料以顺序栈与链栈两种方式实现十进制到二进制、八进制、十六进制的转换适合正在学习栈、链表及算法设计的读者也为后续理解表达式求值、括号匹配等应用打下基础。资源整合了完整源码、Visual Studio 6.0项目工程与编译调试产物共13个文件以cpp源码、dsp/dsw工程文件、exe可执行程序及pdb调试信息为主要类型压缩包大小约1.06MB。已有6167人学习项目精简但清晰覆盖了栈的定义、入栈出栈操作、取余逆序输出等关键环节。通过对照transData.cpp源码与可运行程序能直观看到顺序栈基于数组连续存储、链栈基于节点指针分配的差异并理解栈的LIFO特性在进制转换中如何实现余数的逆序排列。同时Debug目录与工程配置等附属文件也展示了旧版Visual Studio项目的组织方式有助于还原编译环境、排查构建问题适合自主修改基数和测试数据来加深掌握。1. 顺序栈、链栈做进制转换为什么这道课设题藏着最多翻车点顺序栈、链栈将10进制转为2、8、16进制源码是数据结构课设里被选中次数最多的一类组合题。题目本身不复杂把输入的十进制整数通过栈的后进先出特性输出成二进制、八进制或十六进制字符串。可正因为看着简单很多人把精力全放在“转换算法”上忽略了栈本身的各种边界条件——16进制怎么输出A到F、输入0时栈里压什么、负数要不要带负号、顺序栈扩容后栈顶指针怎么重定位任何一个点都能让程序当场翻车。本文给出两套能直接编译运行的C语言源码与参数说明把顺序栈和链栈的实现差异、必调的参数、以及最常见的踩坑记录讲清楚。适合正在做课程设计的学生也适合想确认自己写的是否严谨的在职开发者。2. 除基取余法与栈的匹配关系先搞懂为什么再动手写栈2.1 除基取余法产生的余数为什么天然要逆序输出十进制转任意进制数学上的标准做法叫“除基取余法”。以十进制13转二进制为例13除以2得商6余16除以2得商3余03除以2得商1余11除以2得商0余1一直除到商为0为止。把余数从下往上读得到1101这就是13的二进制形式。注意一个关键点先除出来的余数对应的是二进制的最低位最后除出来的余数才是最高位。而输出的时候必须从最高位开始写。也就是说计算顺序是“先算低位”输出顺序是“先写高位”信息顺序与输出顺序完全相反。这个“先算出来的后输出”的逆序关系恰好就是栈的入栈、出栈语义入栈时先压进去的余数在栈底出栈时最后才被弹出来最后算出来的最高位在栈顶弹出时反而是第一个被打印。常见的错误做法是用数组存余数等全部算完再反向遍历数组。这么做的问题在于你得先知道一共会产生多少个余数才能确定数组下标从哪开始往前写不知道位数就得先做一次循环数位数或者用固定的“从数组末尾往前存”的技巧。这两种方案都能跑但代码里充满了下标的偏移计算。用栈的话完全不需要关心总共有几位压进去几个就弹出几个代码和数学推导一一对应这是数据结构这门课上栈的核心应用场景。2.2 顺序栈与链栈的选型内存模型和数据规模决定选择顺序栈底层是一块连续的内存用一个数组模拟栈空间栈顶指针在数组里移动。链栈每个节点单独malloc一块内存节点之间用指针串起来。对进制转换这个具体的场景两者的差异要落在三个维度上是否判满、扩容成本、节点分配成本。进制转换的输入是一个int型整数在32位int下二进制最多30个有效位去掉符号位八进制最多11位十六进制最多8位。这个数据规模非常小意味着顺序栈初始容量给16个元素就基本够用几乎不会真正触发扩容链栈每次push都要malloc一次而这题最多也就malloc三十次性能差异肉眼不可见。所以从工程角度看顺序栈的实现更简洁、更容易一次写对链栈更适合作为“换一种存储方式再来一遍”的课设要求用来训练指针操作和内存释放。内存模型上还有一点值得注意顺序栈的栈顶指针是“int*”类型可以做指针减法top - base得到当前元素个数判满和判空都极其直观。链栈没有“容量”这个概念只要malloc成功就能压入但代价是必须自己保证每个节点都被释放否则课程设计跑完一次转换就泄漏几十个节点连续运行多次内存只会越用越多。2.3 栈的基本接口设计能跑通课设的最小函数集无论是顺序栈还是链栈我都建议把栈操作收敛成四个函数初始化、入栈、出栈、判空。转换算法只需要调用这四个函数不需要直接操作栈的内部结构。这样做的直接好处是顺序栈版本和链栈版本的转换主逻辑几乎一模一样唯一区别是调用的栈函数名不同后面切换实现时只改初始化那一处。两个版本的接口我统一约定为init返回0表示成功、-1表示内存分配失败push接收数据值返回0成功、-1失败pop从栈中取出一个数据并写到出参里返回0成功、-1表示栈空isEmpty返回1表示空栈。出参方式比返回值直接返回int更稳妥因为压入栈的数据本身可能有任何int值用一个出参可以避免“用特殊值表示失败”的歧义。下面的章节先给顺序栈完整实现再给链栈版本。3. 用顺序栈实现十进制转二、八、十六进制完整源码与参数说明3.1 顺序栈的结构定义与初始化先约定好栈顶指针的语义顺序栈的结构体需要三个成员存储数据的数组指针base、栈顶指针top、以及已分配容量capacity。这里最关键的约定是top的语义——我写成“top指向下一个可写入的位置”而不是“top指向栈顶元素”。这两种约定都能写但判空和入栈的写法完全不同。指向下一位置时栈空的条件是top base入栈时先把数据写到*top再执行top指向栈顶元素时栈空条件变成top base - 1入栈时先top再写。我推荐前一种因为它让空栈状态恰好对应“两个指针相等”检查起来最直观。#include stdio.h #include stdlib.h #define INIT_STACK_SIZE 16 #define GROWTH_FACTOR 2 typedef struct { int *base; // 栈底指针始终指向数组起始位置 int *top; // 栈顶指针指向下一个可写入位置 int capacity; // 当前已分配的元素个数 } SeqStack; int initSeqStack(SeqStack *s) { s-base (int *)malloc(INIT_STACK_SIZE * sizeof(int)); if (s-base NULL) { return -1; } s-top s-base; s-capacity INIT_STACK_SIZE; return 0; } int isSeqStackEmpty(SeqStack *s) { return s-top s-base; }INIT_STACK_SIZE给16已经能容纳一个int在二进制下的全部有效位。如果只是做8进制和16进制转换这个初始容量绰绰有余把容量设小一点是为了让扩容代码有机会被执行到方便调试。capacity不是“栈的实际长度”而是“已分配的内存能装多少元素”实际长度随时用top - base算出来。初始化失败时malloc返回NULL这时不能让程序继续跑返回-1让调用方终止或重新处理。3.2 入栈判满与动态扩容直接realloc是最省事的后悔药顺序栈最容易被忽略的是判满。很多简化写法完全不判满初始容量给一个很大的数组比如int data[1024]这在课设演示时没问题但本质上已经限制了能处理的数据规模。既然栈已经定义成动态的就应该把扩容逻辑写完整。扩容的时机很明确当top - base capacity时当前数组已经装满需要重新分配一块更大的内存。int pushSeqStack(SeqStack *s, int value) { if (s-top - s-base s-capacity) { int newCapacity s-capacity * GROWTH_FACTOR; int *newBase (int *)realloc(s-base, newCapacity * sizeof(int)); if (newBase NULL) { return -1; // 扩容失败原栈数据仍有效 } s-base newBase; s-top newBase s-capacity; // 注意重新计算top s-capacity newCapacity; } *s-top value; s-top; return 0; } int popSeqStack(SeqStack *s, int *out) { if (isSeqStackEmpty(s)) { return -1; } s-top--; *out *s-top; return 0; }push函数里最值得讲的是扩容后重新计算top。realloc可能把原有数据搬到另一块内存地址搬移之后旧的top指针指向的地址已经不再属于我们所以必须用新的base地址加上旧的元素个数也就是原来的s-capacity重新得到top。很多人只写了s-base newBase忘记更新top结果入栈位置跑到错误地址上程序不崩才奇怪。另外realloc的返回值不应该直接赋给s-base必须先用临时变量newBase接住如果直接赋值且realloc失败原来的栈指针就丢了后续再也无法释放这块内存。出栈的顺序同样有讲究先top--再取top。因为top指向的是“下一个可写入位置”入栈时最后一次自增已经让top越过了最后一个元素所以必须先回退再取值。如果把顺序写成out *s-top读到的就是栈外的数据。3.3 转换主流程从十进制数字到目标进制字符串转换算法的核心逻辑对二、八、十六进制完全一致循环对数字取模、压栈、除以基数直到数字变成0最后反复弹出栈顶拼接成字符串。唯一不同的是把数字映射成字符的过程这个单独放到下一节。这里还要处理两个边界数字是0时循环一次都不执行栈里没有内容得先把0压进去数字是负数时C语言的取模结果会是负数压进栈的余数全是负值所以转换前先取绝对值。void convertWithSeqStack(int number, int base, char *result, int resultSize) { SeqStack s; if (initSeqStack(s) ! 0) { result[0] \0; return; } int idx 0; if (number 0) { result[idx] -; number -number; } int positive number; if (positive 0) { pushSeqStack(s, 0); } else { while (positive ! 0) { pushSeqStack(s, positive % base); positive / base; } } while (!isSeqStackEmpty(s) idx resultSize - 1) { int digit; popSeqStack(s, digit); result[idx] digitToChar(digit); } result[idx] \0; free(s.base); }resultSize是调用方传入的缓冲区大小目的是防止弹栈字符串过长写出边界。32位int最大值的二进制刚好31个位加上负号和一个结尾符缓冲区给到40就绝对安全习惯上我会给64。函数最后必须free(s.base)因为init时malloc过内存课设里最容易出现的“运行一次没事、反复调用报错”就是漏了这一行。pushSeqStack的返回值在这里没有逐一检查因为输入是int二进制位最多31个初始容量16就会触发一次扩容而扩容失败的概率极低严谨的写法是每次push后检查返回值发现失败立刻终止并输出错误信息。3.4 输出16进制时的字符映射digitToChar这个小函数别嫌麻烦10进制转2进制和8进制余数范围分别是0到1和0到7转换成字符时直接加0即可。但16进制的余数范围是0到15超过9的部分要映射成A到F。如果直接在转换循环里写if判断代码会显得很啰嗦我习惯用一个独立的查表函数把数字0到15映射成对应的字符。char digitToChar(int digit) { const char *digits 0123456789ABCDEF; if (digit 0 digit 15) { return digits[digit]; } return ?; }查表法比if-else链清晰得多而且为后面的扩展留下了伏笔——如果把digits这个字符串换成0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ同一个函数就能支持到36进制。digitToChar的入参是int但实际使用时只会传入0到base-1的范围也就是0到15。如果未来想支持更大的进制需要把判断范围同时扩大并且确保传入的digit不越界否则digits[digit]会读到字符串末尾之外的内存。4. 用链栈改一版指针操作没有想象中那么玄4.1 链栈的节点定义与初始化头节点存不存数据要想清楚链栈的每个节点包含一个数据域和一个指针域。链表有两种组织方式带头节点的哨兵链表和不带头节点的普通链表。对栈这种只在头部操作的结构我会选择不带头节点直接用top指针指向第一个元素空栈时top为NULL。带头节点的写法在插入时少一个分支判断但栈顶指针指向的是哨兵节点而不是真实数据出栈逻辑要多绕一层对新手反而难理解。typedef struct StackNode { int data; struct StackNode *next; } StackNode; typedef struct { StackNode *top; // 指向栈顶节点空栈时为NULL } LinkedStack; int initLinkedStack(LinkedStack *s) { s-top NULL; return 0; } int isLinkedStackEmpty(LinkedStack *s) { return s-top NULL; }链栈的初始化比顺序栈简单得多不需要分配任何空间只需要把top置为NULL。判断栈空也直接看top是否为NULL。这种“空栈就是一个空指针”的模型非常直观。注意LinkedStack结构体里只存了一个指针没有像顺序栈那样存capacity——链栈的容量在理论上不受预先分配的限制只要malloc能成功就可以继续压入。4.2 入栈出栈的头插法操作每一步都要先画图再写代码链栈的入栈本质是头插法新节点指向当前的top节点然后把top移动到新节点上。出栈是逆操作先用临时变量保存top节点把top移到下一个节点最后释放临时节点。这里最容易写错的是出栈时释放节点的顺序。int pushLinkedStack(LinkedStack *s, int value) { StackNode *node (StackNode *)malloc(sizeof(StackNode)); if (node NULL) { return -1; } node-data value; node-next s-top; // 新节点指向原栈顶 s-top node; // 栈顶移动到新节点 return 0; } int popLinkedStack(LinkedStack *s, int *out) { if (isLinkedStackEmpty(s)) { return -1; } StackNode *temp s-top; // 1. 先保存待删除节点 *out temp-data; // 2. 再取数据 s-top temp-next; // 3. 栈顶指向下一个节点 free(temp); // 4. 最后释放内存 return 0; }入栈的两行指针操作建议在心里默念一遍node-next先接上旧的top再让top指向node。这个顺序不能反过来——如果先执行s-top node那么旧的top节点就找不到了入栈就变成了覆盖。出栈代码里的四步顺序是死规矩尤其第4步free(temp)必须放在最后提前释放temp之后再去访问temp-data或temp-next就是典型的悬空指针访问程序不是必然崩溃而是“有时能跑、有时乱跑”这类问题最难排查。4.3 链栈版转换函数与内存回收课程设计扣分最多的一环链栈版的转换主流程和顺序栈版几乎一样只换了初始化、判空和出入栈的函数名。这也正是用四个基础函数封装的意义——转换算法本身和栈的实现是解耦的。多出来的一个关键是destroy函数因为链栈的每个节点都是独立malloc的不能像顺序栈那样一次性free一整块数组。void destroyLinkedStack(LinkedStack *s) { StackNode *cur s-top; while (cur ! NULL) { StackNode *temp cur; cur cur-next; free(temp); } s-top NULL; } void convertWithLinkedStack(int number, int base, char *result, int resultSize) { LinkedStack s; initLinkedStack(s); int idx 0; if (number 0) { result[idx] -; number -number; } int positive number; if (positive 0) { pushLinkedStack(s, 0); } else { while (positive ! 0) { pushLinkedStack(s, positive % base); positive / base; } } while (!isLinkedStackEmpty(s) idx resultSize - 1) { int digit; popLinkedStack(s, digit); result[idx] digitToChar(digit); } result[idx] \0; destroyLinkedStack(s); }destroyLinkedStack的写法是典型的“边遍历边删除”用cur记录当前节点先把下一个节点地址存到temp的next里已经来不及了因为temp马上要释放所以代码里用cur cur-next先推进再free旧的cur指向的节点。释放完成后把s-top置为NULL避免留下悬空指针。这里值得说明的是链栈版本没有扩容逻辑因为每次push都从堆上新申请一个节点这既是优点也是缺点优点是代码里少一个扩容分支缺点是频繁malloc和free在嵌入式或内存受限环境里会产生碎片而顺序栈没有这个问题。5. 顺序栈和链栈通用的一组避坑记录现象、原因与解决5.1 输入0时输出结果是空串而不是字符串“0”现象convert(0, 2, result)执行后result是一个空字符串调试时发现转换循环一次都没执行。原因while (positive ! 0)的条件在输入为0时直接不成立栈里从头到尾没压入任何余数弹栈阶段自然一个字符都打印不出来。解决在转换函数里显式处理0单独把数字0压入栈中再进入弹栈流程。这条是所有进制转换实现里出现频率最高的问题因为写代码时默认了“正常输入”是正整数忘掉了0这个边界。5.2 负数转换后输出一串错误数字或补码形态现象convert(-13, 2, result)输出的不是“-1101”而是一串看似随机、有时又像补码的二进制位。原因C语言里负整数对正数取模商向0取整余数的符号与被除数相同所以(-13) % 2的结果是-1而不是1。把-1压进栈后续除以2逐步逼近0最终弹出来的是负数余数映射出的错误字符。解决转换前先判断正负为负时先输出一个负号到result再把数字取绝对值后进入正常的除基取余流程。如果对INT_MIN取绝对值要格外小心int的最小值是-2147483648直接写number -number会产生有符号整数溢出严谨的做法是把负数先转成unsigned int再处理课设里可以先声明函数“仅支持INT_MIN以上的负整数”来规避但注释里要写清楚这个限制。5.3 16进制输出里出现了“10”“11”而不是“A”“B”现象十进制255转16进制预期是FF实际输出是15 15这样两个数字拼在一起或者输出一个乱码字符。原因弹栈得到的余数是int型直接用printf(%d)输出或者直接做了int到char的强转10被强转成换行符11被强转成垂直制表符。解决所有余数必须经过digitToChar查表映射后再存进字符串。这个坑在2进制和8进制时不会暴露因为余数0到9恰好和字符‘0’到‘9’的编码连续很多人写完2进制版本直接改个基数就提交到16进制就翻车。5.4 顺序栈扩容后程序崩溃或输出乱码现象压入超过16个数据后程序在push或free时报错有时报“double free”有时报段错误。原因realloc把数组搬到了新地址但代码只更新了base和capacity没有重新计算top或者realloc的返回值直接赋给base一旦分配失败原指针丢失后续free操作的就是一个无效地址。解决用临时指针newBase接收realloc返回值判断非NULL后再更新base更新后立刻执行s-top newBase oldCapacity其中oldCapacity是扩容前的capacity记得在调用realloc之前先保存起来。这条是顺序栈实现里最经典的内存错误课堂上演示时数据量小不触发交上去用随机大数测试立刻崩。5.5 链栈出栈后偶尔崩溃且崩溃位置飘忽不定现象popLinkedStack函数在连续运行多次后偶尔崩溃用调试器看时发现有时是free时报错有时是后续push时报错。原因出栈时先free(temp)再访问temp-data或者temp-next来更新指针产生了悬空指针访问。另一个常见原因是destroy函数里释放节点后没有把s-top置为NULL下次convert再次调用destroy时对已释放的内存重复free。解决严格按“保存节点—取数据—更新指针—释放”四步写出栈代码destroy函数结束时务必将top置为NULL。这个问题的隐蔽之处在于悬空指针在内存未被复用时不报错一旦中间插入了其他malloc原来的内存被重新分配指针访问就会落在不可预期的地址上。6. 用随机数据与边界值验证转换结果3个测试思路与扩展方向转换函数的正确性不能光靠眼睛看建议写一个校验函数做反向验证把生成的进制字符串按每一位还原成十进制数再与原始输入比较。下面这个verify函数把“按位展开再累加”的过程写回来只要转换函数输出字符串它就能独立判断对错。int verifyConversion(int expectAbs, int base, const char *result) { int value 0; for (int i 0; result[i] ! \0; i) { char c result[i]; int digit; if (c 0 c 9) { digit c - 0; } else if (c A c F) { digit c - A 10; } else { return -1; } value value * base digit; } return value expectAbs; }测试时在循环里随机生成0到100000之间的数字分别转2、8、16进制每次用verify校验跑一万次不能有一次失败。边界值方面我固定测这组数据0、1、-1、255、256、INT_MAX、INT_MIN如果函数注释声明了不支持INT_MIN就跳过。注意verify只校验绝对值因为转换函数已经把符号写进了result字符串校验时传入原始数字的绝对值即可。扩展到任意进制时只需要做两处小修改把digitToChar里的digits字符串扩展成36位把convert函数里的base参数从固定的2、8、16放开成全范围校验。栈本身不需要任何改动。往后如果你做课程设计答辩老师大概率会追问“这个栈能不能反过来用”比如用栈判断括号匹配、用栈计算后缀表达式核心都是“逆序处理”这四个字栈的操作接口一份都不需要改。我自己的习惯是任何一个牵扯到栈的转换函数永远先测0再测负数再测最大值。这三个输入能过再谈随机测试。这套习惯帮我拦下了不少课设现场才暴露的边界问题。希望帮到你。本文还有配套的精品资源点击获取