简介这是一份面向高校计算机专业学生的数据结构课程设计完整方案围绕大数运算这一经典课题实现了大数加法、减法、乘法、除法、乘方与取模六类核心运算并同时兼容十进制与二进制两种进制的大数处理可有效解决超出普通整型或浮点型范围的高精度计算问题适用于课程设计、算法实验与期末项目参考。压缩包共35个文件涵盖C核心源码与头文件、Python验证脚本、多组输入输出测试数据以及编译配置和可执行程序等整体约22.24MB目录结构清晰便于按需查阅。目前已有1351人学习下载在同类课程设计资料中具有一定参考热度。通过研读代码可深入理解大数运算中的逐位进位、借位处理、快速幂分治策略以及进制转换等关键算法同时借助Python对照脚本和验证数据检验C实现结果的正确性为独立完成类似高精度运算项目提供直接可用的模板与排错思路。1. 数据结构课程设计里的大数运算为什么越早动手越少掉头发数据结构课程设计里的大数运算算是最容易让人误判工作量的一道题。光是听名字——大数加法、大数减法、大数乘法、大数除法、大数乘方、大数取模还同时支持十进制和二进制——很多人第一反应是“这不就是循环加一下、乘一下嘛”。真写到第三天地被除数卡住才明白问题出在“数”本身的表示上C语言里连最大的 unsigned long long 也就到 2^64-1十进制下大约是 1.8×10^19稍微乘两个十位数的乘积就爆了。于是整个作业的核心矛盾浮现出来你要先解决“这个数怎么存”然后才轮得到“这个数怎么算”。这篇笔记顺着一个能直接交差的实现路径往下讲用动态数组线性表当底层结构把加减乘除、乘方、取模逐个大数运算算子拆开再处理十进制和二进制的进位差异。适合正在写课程设计、或者想把“数组模拟竖式”这一套路彻底吃透的人。照着这个方案走你能拿到一个能跑、能演示、能扩展的完整大数运算包至于里面有多少坑我用亲身翻车经历替你探了一遍。2. 大数运算的存储设计决定后面所有算法能不能落地的关键一步2.1 为什么大数运算必须先解决“数怎么存”内置类型的边界太近了大数运算的第一步不是写加法而是选存储结构。C语言内置的 int 范围在 32 位下是 -2147483648 到 2147483647long long 大一些但也逃不过 64 位的上限。一旦被乘数、乘数都超过十位乘积直接溢出更隐蔽的是减法里的借位和除法里的试商溢出的表现不是报错而是静默地算出错误结果这在课程设计验收时极难排查。常见做法是用数组模拟竖式。十进制大数和二进制大数在这儿的差别只是“逢十进一”还是“逢二进一”的问题底层数据结构完全共用。我一般选择 C 语言实现因为它是数据结构课的主流语言如果你用 C可以把下面的结构体换成 vector 思路完全一样。存储结构有两个方案定长数组比如int num[1000]简单粗暴但长度上限写死算 1000 位的数就尴尬乘方运算时位数增长极快容易越界。动态数组用指针 长度按需扩容。这是工程上的常规做法也是数据结构课程“线性表”知识的直接应用。我推荐动态数组。原因不是“高级”而是大数乘法和乘方会不断产生更长的中间结果事先猜长度属于玄学动态扩容虽然多几行 realloc但后续所有算子都不用担心位数上限。2.2 低位在前还是高位在前一个影响所有算法复杂度的选择存储顺序是第二个关键决定。有两种存法高位在前num[0]存最高位符合人类阅读习惯打印方便但做加法时要从数组尾部往前遍历不够自然。低位在前num[0]存个位num[1]存十位依此类推。这和竖式计算的顺序一致——从个位开始逐位相加进位自然往后扩展数组尾部就是新的最高位直接 push 即可。我采用低位在前。第一次写大数运算的读者往往觉得高位在前更好读但真写到加法和乘法时低位在前会让循环逻辑直白得多。二进制的处理同样如此只是把进位基值从 10 改成 2。2.3 结构体定义与进制抽象让十进制和二进制共用同一套算子先定义结构体同时把“进制”抽象成一个全局参数#include stdio.h #include stdlib.h #include string.h #include ctype.h #define BASE 10 // 当前进制10 表示十进制2 表示二进制 #define INIT_CAP 64 // 初始容量 typedef struct { int *digits; // 低位在前digits[0] 是个位 int len; // 当前有效位数不含前导零 int cap; // 已分配容量 } BigNum;这里的BASE是核心抽象。加减乘除的代码内部只依赖BASE控制进位不写死 10。当需要切换二进制时把BASE改成 2输入输出部分做相应处理四则运算的代码一行不用动。这种设计在课程设计答辩时是一个加分项——说明你理解了“进制只是进位规则不是数据结构差异”。初始化函数需要注意分配内存后要把digits全置零否则 realloc 出来的内存是垃圾值加法进位时会出现随机数混入的诡异现象。void big_init(BigNum *n) { n-digits (int *)calloc(INIT_CAP, sizeof(int)); n-len 0; // 0 表示为空后续符号单独处理 n-cap INIT_CAP; } void big_free(BigNum *n) { free(n-digits); n-digits NULL; n-len 0; n-cap 0; }calloc在这里比malloc稳妥因为大数运算的中间结果经常只有低几位被写入高位的 0 是安全默认值。符号问题我单独用一个int sign存一是便于减法实现二是避免“0 的符号”这种边界脏数据。3. 大数加法与大数减法进位和借位的边界细节3.1 大数加法实现竖式加法的代码化加法是所有运算的地基。竖式加法的核心是从低位到高位逐位相加每位的和加上进位后除以BASE得到新进位取余得到本位值。代码实现如下void big_add(BigNum *res, const BigNum *a, const BigNum *b) { int max_len (a-len b-len) ? a-len : b-len; big_ensure_cap(res, max_len 1); // 确保容量够放最高位进位 int carry 0; int i; for (i 0; i max_len; i) { int da (i a-len) ? a-digits[i] : 0; int db (i b-len) ? b-digits[i] : 0; int sum da db carry; res-digits[i] sum % BASE; carry sum / BASE; } if (carry) { res-digits[max_len] carry; res-len max_len 1; } else { res-len max_len; } }逻辑说明max_len取两者最大长度循环逐位相加da和db取当前位时用i len判断越界就当 0这样不需要单独处理长度不同的情况。carry是上一位的进位sum / BASE得到进位到高位的值。最后一次循环结束后如果还有进位说明结果比最长的操作数多一位要单独补上。参数说明BASE是全局常量十进制为 10二进制为 2。注意当BASE2时sum / 2得到的是二进制进位只有 0 或 1 两种情况sum % 2得到当前位。这套代码对两种进制完全通用。big_ensure_cap是一个扩容函数检查res的容量是否满足需求不够就 realloc。这里有一个常见翻车点res可能和a或b是同一个变量比如big_add(x, x, y)这时先取a-len再修改res会读到被污染的数据。解决办法是在函数入口处用局部变量保存a-len和b-len这个细节在验收时很容易被追问。3.2 大数减法实现借位与符号的博弈减法比加法麻烦因为存在“谁减谁”和“结果为负”两种情况。我先实现一个只处理“非负且 a b”的内部函数再在外层做符号判断// 内部函数计算 |a| - |b|前提是 |a| |b| static void big_sub_abs(BigNum *res, const BigNum *a, const BigNum *b) { int borrow 0; int i; big_ensure_cap(res, a-len); for (i 0; i a-len; i) { int db (i b-len) ? b-digits[i] : 0; int diff a-digits[i] - db - borrow; if (diff 0) { diff BASE; borrow 1; } else { borrow 0; } res-digits[i] diff; } // 去掉高位前导零 while (res-len 1 res-digits[res-len - 1] 0) res-len--; }外层封装需要先比较绝对值大小。比较规则是长度不同长度大者绝对值大长度相同从高位往低位逐个比。int big_abs_compare(const BigNum *a, const BigNum *b) { if (a-len ! b-len) return (a-len b-len) ? 1 : -1; for (int i a-len - 1; i 0; i--) { if (a-digits[i] ! b-digits[i]) return (a-digits[i] b-digits[i]) ? 1 : -1; } return 0; } void big_sub(BigNum *res, const BigNum *a, const BigNum *b) { int cmp big_abs_compare(a, b); if (cmp 0) { big_sub_abs(res, a, b); res-sign 1; // 非负 } else { big_sub_abs(res, b, a); // 交换顺序 res-sign -1; // 结果为负 } }这里res-len的正确性依赖big_sub_abs最后那段“去前导零”的逻辑。比如 100 - 99 1如果不去前导零结果可能是“001”长度 3打印出来是“001”看起来没错但参与后续乘法时会多出无效的 0 位导致进位错乱。所以去前导零不是优化是正确性的必需条件。3.3 加减法里进制相关的隐藏共性符号与进位分开处理加减法的实现让人意识到大数运算的核心其实只有两个动作逐位计算 跨位传递进位/借位。无论是十进制还是二进制这两个动作的代码完全一样因为BASE已经封装了进位的数值差异。符号处理是加减法最容易写乱的地方。我建议单独一个int sign字段而不是把负数编码在 digits 里。这样做的原因是乘法、除法、乘方都要用到“绝对值相乘最后再定符号”的策略如果符号混在 digits 里每一次进位都会变得不可预测。实际调试时我习惯先写一个big_print函数专门用来打印大数当前状态包括len和每一位的值。加法做完打一次减法做完打一次很快就能定位是哪个环节的位数出了问题。这比你盯着代码空想要快得多。4. 大数乘法与大数除法从竖式到试商的复杂度跨越4.1 大数乘法O(n*m) 的双层循环与进位后处理乘法的思路依然是模拟竖式a的第 i 位乘以b的第 j 位乘积加到结果的第 ij 位。注意这个“乘积是一位数乘以一位数最大为 (BASE-1)^2”十进制下最大 81二进制下最大 1但多个乘积累加在同一位置时可能超过BASE所以进位不能边乘边处理要等全部累加完再统一进位。void big_mul(BigNum *res, const BigNum *a, const BigNum *b) { big_ensure_cap(res, a-len b-len 1); // 先把结果清零因为下面用的是累加 for (int i 0; i a-len b-len 1; i) res-digits[i] 0; res-len a-len b-len 1; for (int i 0; i a-len; i) { for (int j 0; j b-len; j) { res-digits[i j] a-digits[i] * b-digits[j]; } } // 统一进位 for (int i 0; i res-len; i) { int carry res-digits[i] / BASE; res-digits[i] % BASE; if (carry i 1 res-len) res-digits[i 1] carry; } // 去前导零 while (res-len 1 res-digits[res-len - 1] 0) res-len--; }逻辑说明内层循环把 a[i] * b[j] 累加到 ij 位累加完后统一处理进位避免在累加过程中修改同一数组导致“进位没算完又继续累加”的连环错误。有一点要注意res-digits[i j] a-digits[i] * b-digits[j];这行当BASE10时乘积最大 81但同一个 ij 位可能被累加多次值可能超过 100所以统一进位必须在累加结束后进行。参数说明结果长度初始化为a-len b-len 1这是理论上乘法的最大可能位数比如 99*9998012位乘2位得4位正好2241 是安全余量。二进制下同理比如 1117乘以 1015最多 7 位这个公式依然成立。这里一个常见的低效写法是内层循环里直接res-digits[ij] product; if (res-digits[ij] BASE) { … 立即进位 }。这种做法問題很大——进位后当前位虽然小于 BASE 了但后面的累加还会再加导致进位失控。我在第一次实现时就犯过这个错打印出来一位是负数检查才发现是进位没等累加完就处理了。4.2 大数除法模拟长除法的试商过程除法是大数运算五个算子里最复杂的因为要用“减法”来模拟“除法试商”。核心思想是从被除数的高位往低位走维护一个当前余数每次把被除数的一个新位追加到余数末尾然后减去足够多的“除数 × BASE^shift”直到余数小于除数。这个“足够多”就是商在这一位的值。课程设计常见的实现方式是“按位试商法”商从高位到低位逐位确定每一位的取值范围是 0 到 BASE-1用循环减去除数的倍数来找最大可减次数。这种方法直观但比较慢另一种方案是二分试商把每一位的取值范围用二分查找逼近能稍微快一点但代码复杂度高不少。对于课程设计按位试商完全够用。void big_div(BigNum *q, BigNum *r, const BigNum *a, const BigNum *b) { // q 存放商r 存放余数调用前需确保 b 非零外部判断 big_init(q); big_init(r); // 从 a 的最高位开始 for (int i a-len - 1; i 0; i--) { // 余数左移一位相当于乘 BASE 后追加当前位 big_shl_base(r, 1); // r r * BASE big_set_digit(r, 0, a-digits[i]); // r.digits[0] 当前位注意低位在前 // 试商从 q_i BASE-1 往下找只要 除数 * q_i r就减 int qi 0; BigNum tmp, cmp; for (int trial BASE - 1; trial 1; trial--) { big_mul_small(tmp, b, trial); // tmp b * trial if (big_abs_compare(tmp, r) 0) { qi trial; break; } } big_set_digit(q, i, qi); // 商第 i 位 big_mul_small(tmp, b, qi); big_sub_abs(r, r, tmp); // 余数减去已商部分 } // 去前导零 big_trim(q); big_trim(r); }这段代码里我用了三个辅助函数big_shl_base整体乘 BASE、big_mul_small大数乘单个数、big_set_digit设置特定位。它们本身很简单但逻辑说明一下big_shl_base(r, 1)把余数每一位往高位挪一位等价于 r * BASE。因为低位在前实际就是从后往前把 digits[i] 赋给 digits[i1]再把 digits[0] 设为当前被除数位。这里有个容易踩的坑如果 r 的容量不够扩容要在移位前完成否则越界写。big_mul_small(tmp, b, trial)大数乘法里有一个特例——乘数是一位数。这时可以用简化版O(n) 循环即可不需要 O(n^2)。试商循环从BASE-1往下试最多试 BASE 次。十进制下最多试 9 次二进制下最多试 1 次因为商只可能是 0 或 1。这看起来不是个漂亮的算法但胜在简单可靠如果你在答辩时被问“能不能优化”可以提二分试商但没必要为课程设计去写。除法中还有一个容易忽略的点被除数的长度可能大于除数的长度很多这时商的最高位可能为 0。比如 1 除以 999商的位数是 0。所以最后必须用big_trim把所有前导零去掉否则商的长度不正确后续乘方、取模会继续传播错误。4.3 除法里试商失败的两种典型症状试商过程隐蔽的问题有两类我都在调试时遇到过。第一类是“试商值偏高”。理论上从BASE-1往下一路找到第一个满足b * trial r的就是正确商但如果你先前把 r 的位数算错那么b * trial的实际值会偏大导致trial偏小商偏小余数偏大——而且这个现象不会立即报错因为余数最后也在安全范围内。这个问题的排查方法是商乘除数加余数必须等于被除数。我在big_div之后写了一个big_verify_div函数用乘法加法做反向校验一旦不等就打印中间状态。第二类是“余数左移时把旧的最高位弄丢”。big_shl_base如果按从前往后的顺序移位低位会在第一次赋值时被覆盖。正确写法必须从最高位开始往低位方向移动或者用一个临时变量保存。这类 bug 在二进制下特别容易发生因为位数短肉眼不容易发现但结果会相差很大。5. 大数乘方、大数取模与避坑五个让大数运算翻车的常见问题5.1 大数乘方快速幂的核心是“把指数拆成二进制”乘方运算如果直接循环乘 N 次时间复杂度是 O(N * M^2)N 是指数大小M 是底数位数指数稍微大一点比如 2 的 100 次方指数 N100问题还不大但课程设计里常见题目要求算“大数的 100 次方”直接用循环乘 100 次性能勉强能看如果是指数 1000000就完全跑不动了。因此标准实现是快速幂把指数拆成二进制位利用“底数的平方”逐位乘起来。void big_pow(BigNum *res, const BigNum *base, int exp) { // 用临时变量避免 res 和 base 重叠的问题 BigNum result, cur, tmp; big_init(result); big_set_one(result); // result 1 big_copy(cur, base); // cur base while (exp 0) { if (exp 1) { // 指数当前位为 1 big_mul(tmp, result, cur); big_copy(result, tmp); } big_mul(tmp, cur, cur); // cur cur^2 big_copy(cur, tmp); exp 1; } big_copy(res, result); big_free(result); big_free(cur); big_free(tmp); }逻辑说明exp 1判断指数二进制的最低位是否为 1。如果为 1说明这一位的“贡献”要乘进结果如果不为 1说明这一位的底数平方结果不需要累乘但底数依然要平方因为下一位的值是当前位的平方。每处理完一位exp右移一位直到 exp 变为 0。这里有一个关键的数学原理快速幂之所以叫“快速”是因为乘法的次数从指数次数 O(exp) 降到了 O(log exp)。比如计算 2^100循环乘法要乘 100 次快速幂只用约 8 次平方和 3 次乘法。这个提升在处理大数时意义重大因为大数乘法的成本本来就高少一次是一次。使用快速幂时要注意如果exp是负数大数乘方一般不考虑这个情况。课程设计要求“大数乘方”通常默认指数是正整数如果你要处理负指数需要先求倒数而不是简单套这个函数。我建议在big_pow入口加一个断言或检查免得忘了。5.2 大数取模除法余数的复用与特判取模运算的本质是除法的一组副产品上面第 4.2 的big_div函数里r就是 a mod b 的结果。所以最直接的做法是调用big_div丢掉商保留余数。代码很简单void big_mod(BigNum *r, const BigNum *a, const BigNum *b) { BigNum q; // 商我们不需要 big_init(q); big_div(q, r, a, b); // 这里 q 被计算出来但丢弃 big_free(q); }但这里有两个效率上的小优化也是答辩时能讲的点第一如果 b 的位数远小于 a商的位数会非常大但商对我们没有意义。这时可以只计算余数不需要完整保存商的每一位。做法是把除法里的“商位”去掉只保留余数部分。代码可以简化成只维护 r 数组的“模拟除法余数版”。不过课程设计场景下商的位数一般不会超过几千完整计算也能接受所以我直接用big_div拿余数省得写两套。第二取模运算有一个特判如果 b 的长度为 1即 b 是一位数余数可以直接用 a 的每一位对这个一位数求模。这个优化很实用因为大量取模运算的场景是“对一个不太大的数取模”。但要不要为它单独写分支取决于你有没有时间我一般不加因为big_div已经够快。5.3 避坑大数运算常见的五个问题记录问题一加法函数里 res 与 a 是同一个变量时数据污染现象big_add(x, x, y)调用后x 的值变成随机数有时甚至崩溃。原因big_add在函数开头读取了 a-len、b-len但随后写 res-digits 时如果 res 与 a 指向同一块内存循环还没结束a-digits 的内容就被 res 覆盖了。比如res-digits[0]被写成了新值下一轮循环读a-digits[0]时读到的是新值相加结果自然错乱。解决在big_add函数内部先用临时变量保存a-digits的地址、a-len、b-len、b-digits 的地址。或者干脆约定调用时禁止传同一个变量。我建议第一种因为每次调用都检查太容易出错。问题二去前导零不彻底导致乘法结果包含无效高位现象某次乘法结果看起来比预期多一位比如 99*99 算出“09801”多了一个前导 0。更麻烦的是这个多出来的 0 会让下一次乘法结果的位数公式失效连锁出错。原因乘法统一进位后理论上最高位可能是 0但去前导零的条件写成了while (res-len 1 res-digits[res-len - 1] 0) res-len--;如果res-len初始值偏大那么这个循环能正确去掉高位零但如果某次操作的res-len在过程中被错误地缩短过这个循环可能不会触发。解决在所有算子加减乘除、乘方、取模的输出端统一调用big_trim(res)。不要手动在各个函数里零散地写去零逻辑统一封装成一个函数每条算子收尾时调用一次。这样排查时只需检查一个地方。问题三二进制模式下换行打印看到的是乱码现象BASE2 时打印函数输出为“0 1 0 0 1 0”而不是一个连贯的二进制串。用户看习惯十进制后以为代码显示错误。原因这不是代码 bug而是打印函数没按进制做格式化。十进制下每位的值是 0-9二进制下每位是 0 或 1十进制打印的位宽是 1二进制也是 1但中间如果不加分隔符人眼读不清。更隐形的问题是如果你用printf(%d, digits[i])打印一个大数所有位连在一起十进制可能“123456789”可读二进制“10101010”也可读但一旦位数超过 32 位人眼很难核对。解决写一个big_print_bin专门用于二进制大数每 8 位加一个空格分组十进制则每 3 位加一个逗号。不要图省事用同一个格式化函数应付两种进制。问题四除数为零时程序崩溃且没有提示现象运行到big_div时直接段错误。原因big_div内部试商时如果 b 为 0b * trial恒为 0与 r 比较时永远相等理论上不会崩但big_mul_small里如果 b-len0 且 b-digits[0]0会访问b-digits[0]这一块分配了但未初始化的内存更常见的是调用方在 b 为 0 时没有检查先去做big_div然后内部出现除零比如r / BASE这种本身不是除零但while (exp 0)里 exp 是 0 被单独处理的其他函数处崩溃。解决所有循环和除法的入口先判断除数为零并返回错误码。我一般习惯在big_div、big_mod的入口加if (big_is_zero(b)) return -1;让调用方提前处理而不是在内部段错误后花半天查栈。问题五big_shl_base移位顺序写反导致余数低位被清空现象除法结果商正确但余数全是 0且商每次都比正确值小一点。原因big_shl_base如果写成for (int i 0; i len; i) digits[i1] digits[i];那么最后一次循环时digits[1]被digits[0]覆盖但下一次循环digits[1]的值已经被覆盖为旧的 digits[0]等于把低位往高位复制了而真正的高位被丢弃。正确写法是for (int i len; i 0; i--) digits[i] digits[i-1];从最高位往最低位移这样每个低位都有机会保留旧值。解决所有移位操作统一按“从最高位开始”写循环。这类 bug 在二进制下特别隐蔽因为二进制下位数短错一位从结果上看可能是乘以 2 或除以 2 的关系容易被误判为“正常误差”。6. 用随机对拍和进制转换把每一个边界拿出来验一遍写完全套算子最怕的不是代码 bug而是“看起来对实际上边界没覆盖”。我在课程设计答辩前吃过这个亏十进制加减乘除全对一换成二进制乘法除法全军覆没。原因很简单——二进制和十进制的区别不仅仅是进位基值不同对位数的敏感性更高前导零、进位、试商循环的边界差异全暴露出来。验证思路分三层成本从低到高第一层固定用例。挑几个手工能算的数加法用 999 1验证连续进位减法用 1000 - 1验证借位链乘法用 123456789 * 987654321 对比 Python 算出的结果除法用 1000000 / 3 验证商和余数。这一层能在半小时内暴露 80% 的基础问题。第二层随机对拍。写一个测试函数生成两个随机大数长度在 1 到 50 位之间先转成 C 语言的unsigned long long范围用内置运算符算一遍再用你的大数函数算一遍对比结果。超出unsigned long long范围的数改用 Python 脚本先算好参考值存成文件再让 C 程序读入对比。这是最有效的验证方式能覆盖除法和二进制下的所有边界。同理调试二进制运算时每次把一个二进制大数手动换算成十进制来对照能直观定位。第三层交叉验证。利用“商 × 除数 余数 被除数”这个恒等式对每组除法和取模结果再乘一次、加一次看是否还原。这个恒等式是检验除法正确性的金标准我在big_div外面包一层big_assert每次算完都验证一旦触发断言能精确说明问题出在试商、余数还是去零环节。最后一层是进制互转验证。把同一个大数分别按十进制、二进制存储用两种进制的算子分别计算结果再把二进制结果转回十进制看是否与十进制结果一致。这一步能直接验证你“BASE 抽象”是否真的做对了——如果因为某个函数里写死了 10 而不是用 BASE二进制下必然对不上。我自己的使用习惯是把随机对拍写成一个独立函数每次修改完任意一个算子跑一遍回归。课程设计做到后期改动一个微小的地方比如优化big_mul_small循环很可能影响除法、取模、乘方的正确性没有回归测试翻车是早晚的事。有一次我为了优化乘法里的内层循环改成从低位向高位累加结果除法模拟长除法时用了这个乘法商的一位差 1找了三个小时最后靠对拍定位。顺带一提如果你在做课程设计时追求效率可以用 Python 的int类型直接算出参考大数然后用 C 程序输出你的大数让脚本对比。Python 的int任意精度是一条免费的验证快车道。但这只用于验证交作业的代码还是要 C 或 C 实现因为课程设计要求你用数据结构数组/链表自己管理存储而不是用语言内置的大整数。这套方案做完你的收获不只是“会写大数四则运算”而是理解了为什么数据结构这门课要先讲线性表、顺序表——因为一切复杂运算最后都落回最基础的存储与遍历。祝你调得快答辩顺。希望帮到你。本文还有配套的精品资源点击获取