简介一份用于数据结构课程设计的大数运算完整工程面向高校学生、算法初学者以及需要完成同类课题的开发者。资源以 C 实现为主同时支持十进制与二进制大数的加法、减法、乘法、除法、乘方、取模六类运算包含快速幂、长除法、逐位进位与借位等典型算法思路可直接作为课设源码、算法学习素材或二次开发基础。包体共 35 个文件压缩包大小 22.24MB主要包含 C 源文件与头文件、Python 验证脚本、txt 输入输出样例、data 数据文件以及可执行程序从核心算法到测试验证形成完整链条目前已有 1351 人学习下载适合数据结构课程设计、期末项目及算法进阶练习。通过阅读源码可以理解大数在数组/字符串存储下的逐位运算、商与余数的迭代生成、快速幂减少乘法次数等关键实现配套的多种测试数据与 Python 对照结果便于自查正确性并生成实验报告。工程内模块划分清晰按运算类型即可快速定位对应代码实用性较强。1. 大数运算课程设计先想清楚“大”在哪再写第一行代码大数运算课程设计是数据结构课里最容易被低估的一道题题目就六个大字“大数加法大数减法”可真上手就会发现int 连 21 亿都装不下随便喂一个 30 位的输入数组、链表、进位借位这些基础结构立刻被逼出原形。我见过太多人把六个运算写成六个互相独立的字符串处理函数代码跑通了却讲不清每条复杂度答辩一追问就翻车。这份资源把减法先比较大小、乘法先乘后进位、除法按位试商、乘方用二进制扩展法、取模直接复用除法结果以及十进制和二进制两种输入的解析封装串在了一条完整的链路上适合期末课程设计、数据结构与算法自测也想用一道题把线性表玩透的 408 考研党。2. 大数存储与加减法数组逆序存放是实现高精度的第一课2.1 存储设计为什么逆序存低位、为什么不用链表大数运算的第一步不是写加法而是决定“一个超长整数在内存里长什么样”。最经典的做法是用 int 数组每个元素存一位十进制数字下标 0 存个位下标 1 存十位依此类推。这么做的理由很实在加法进位是从低位往高位传播的逆序存储后进位方向正好和数组下标增长方向一致循环写起来就是正向遍历不需要从尾巴往头倒着摸。链表也能做严蔚敏《数据结构C 语言版》里不少习题也鼓励用链表表达多项式和大整数。但我的建议是课程设计如果没有额外要求优先用定长数组。原因是链表每个节点额外带一个 next 指针内存不连续遍历时 cache 命中率差而且大数运算的瓶颈在进位和借位的连续扫描数组的随机访问比链表快得多。链表更适合展示“插入删除”的场景大数运算这种高频遍历场景数组天然更合适。#define MAX_DIGITS 1024 typedef struct { int digits[MAX_DIGITS]; // 下标0存个位digits[i] 取值范围 0~9 int len; // 当前有效位数digits[0]~digits[len-1] int sign; // 1 表示正-1 表示负0 表示数值为 0 } BigInt;说明MAX_DIGITS设成 1024 意味着最大支持 1024 位十进制数课程设计够用如果题目要求 10000 位直接改宏即可。len是有效长度比如数字 100 存下来是 digits[0]0、digits[1]0、digits[2]1len3。sign单独存符号避免把负号揉进数字位里后面做减法比较时省很多事。这里每个元素只存一位十进制是“一位一存”的朴素方案代码最好懂、进位最好写缺点是空间利用率低真正追求性能的版本会每个元素存 9 位也就是“万进制”这个放到最后一章说。2.2 大数加法进位传播与结果长度修正加法是最不需要思考的运算但也是第一个容易出细节问题的地方。两个数相加每一位上最多出现99119所以进位 carry 只可能是 0 或 1。很多初版代码喜欢在每一位算完立刻把 carry 写进下一位这没问题但要注意循环结束后如果还有 carry结果长度必须加一否则 999 1 会算成 000。void addBigInt(BigInt *a, BigInt *b, BigInt *res) { int maxLen (a-len b-len) ? a-len : b-len; int carry 0; for (int i 0; i maxLen; i) { int sum carry; if (i a-len) sum a-digits[i]; if (i b-len) sum b-digits[i]; res-digits[i] sum % 10; carry sum / 10; } if (carry 0) { res-digits[maxLen] carry; res-len maxLen 1; } else { res-len maxLen; } }逻辑说明循环从低位到高位逐位累加短的那个数下标越界后自动补 0这样 123 45678 也能正确算出 45801。sum % 10留下当前位sum / 10作为进位传给下一位。参数说明a、b是输入res是输出允许res和a指向同一个变量函数内部逐位写入不会读到脏数据。唯一要注意的是函数调用前最好把res-len清 0避免旧数据残留。这个实现的时间复杂度是 O(n)n 是较长的那个数的位数和手算加法完全一致。2.3 大数减法先比较再相减符号用 sign 字段兜底减法比加法麻烦一个量级麻烦不在借位而在“谁减谁”。如果直接拿小数减大数借位会借到天上去。正确的套路是先比较两个数的绝对值大小保证大数在前、小数在后只算“大减小”再把符号记在 sign 字段里。这也是为什么我在结构体里单独留了sign。int compareBigInt(BigInt *a, BigInt *b) { if (a-len ! b-len) return a-len - b-len; for (int i a-len - 1; i 0; i--) { if (a-digits[i] ! b-digits[i]) return a-digits[i] - b-digits[i]; } return 0; // 完全相等 } void subBigInt(BigInt *a, BigInt *b, BigInt *res) { int neg 0; if (compareBigInt(a, b) 0) { BigInt *tmp a; a b; b tmp; // 交换指针保证 a b neg 1; } int borrow 0; for (int i 0; i a-len; i) { int dif a-digits[i] - borrow; if (i b-len) dif - b-digits[i]; if (dif 0) { dif 10; borrow 1; } else { borrow 0; } res-digits[i] dif; } res-len a-len; while (res-len 1 res-digits[res-len - 1] 0) { res-len--; // 去掉高位多余的 0比如 100-99001要变成 1 } res-sign neg ? -1 : 1; }逻辑说明compareBigInt先比长度再比高位长度长的绝对值一定大长度相同就从最高位往低位逐位比。减法主循环里borrow表示上一位有没有借位当前位不够减就10并把borrow置 1。每次用a-len作为循环上限是因为我们保证a是较大的那个。参数说明两个指针a、b的交换用的是指针交换不复制数组内容效率高。注意这里只处理了“绝对值比较后大减小”如果输入本身就带符号比如负数减正数需要在调用层额外处理符号叠加课程设计通常可以约定输入都是非负数或者在 main 里先统一转成正数再调用。3. 大数乘法与除法竖式算法的两个落地方向3.1 大数乘法先累加后进位避免每轮都处理进位大数乘法最直观的写法是模拟小学竖式a的第 i 位乘以b的第 j 位结果放在结果的第ij位。第一次写的时候很容易写成“每乘一位就立刻把进位加到下一位”这样也能跑通但进位处理会和下一轮累加纠缠在一起代码极易出错。我常用的做法是分两步第一步只做乘法和累加先让tmp[ij]把该加的都加上第二步再统一处理进位。void mulBigInt(BigInt *a, BigInt *b, BigInt *res) { int tmp[MAX_DIGITS * 2] {0}; for (int i 0; i a-len; i) { for (int j 0; j b-len; j) { tmp[i j] a-digits[i] * b-digits[j]; } } int carry 0; res-len a-len b-len; // 两个 n 位、m 位数相乘最多 nm 位 for (int i 0; i res-len; i) { int value tmp[i] carry; res-digits[i] value % 10; carry value / 10; } while (res-len 1 res-digits[res-len - 1] 0) { res-len--; // 比如 0 * 999 的结果应该是 0不是 000 } }逻辑说明tmp[ij]累加的是所有能贡献到第ij位的乘积累加和。举个例子a123、b456那么tmp[2]会收到a[0]*b[2] a[1]*b[1] a[2]*b[0]也就是3*4 2*5 1*6 28。第二步统一进位carry从低位往高位滚最终每个元素都变成 0~9。参数说明tmp数组长度取MAX_DIGITS*2是因为两个 1024 位数相乘最多 2048 位定成两倍最大长度能防越界如果实际位数更短循环也只遍历到a-len b-len。时间复杂度是 O(n*m)n 和 m 是两个数的位数这也是朴素乘法的理论下限之内的常见实现如果追求更快可以上 Karatsuba但课程设计阶段竖式足够。3.2 大数除法按位试商二进制大数每商位只有 0/1除法是六个运算里最容易写崩的。手算除法的本质是从被除数最高位开始每次“取一部分不够除就往后拼一位”够除就试商。放到大数里就是维护一个余数累加器cur每次把cur整体乘 10相当于左移一位再拼上被除数的下一位然后看cur最多能减几个除数这个次数就是商的当前位。void trimZero(BigInt *x) { while (x-len 1 x-digits[x-len - 1] 0) { x-len--; } } void divBigInt(BigInt *a, BigInt *b, BigInt *q, BigInt *r) { BigInt cur {0}; // 余数累加器 q-len a-len; for (int i a-len - 1; i 0; i--) { // 余数乘 10相当于把商位左移一位 mulSmall(cur, 10, cur); addSmall(cur, a-digits[i], cur); int qd 0; while (compareBigInt(cur, b) 0) { subBigInt(cur, b, cur); qd; // 当前商位最多减 9 次 } q-digits[i] qd; } trimZero(q); trimZero(cur); *r cur; }逻辑说明mulSmall(cur, 10, cur)是给余数乘一个一位数 10实现上就是从高位逆向进位或者直接手写一个乘小数的函数addSmall同理给余数加上一位数字。内层while每减一次除数商位加一理论上一位最多减 9 次所以整体复杂度约等于 O(n*m)n 是被除数位数m 是除数位数。参数说明q是商r是余数函数结束时r一定满足0 r b。这里有个容易被忽略的点商的长度初始设成a-len因为被除数有几位商的位数最多也就是几位最后trimZero把高位 0 去掉比如 100/50 的商初始是“002”trim 后是“2”。这个结构对二进制大数有个天然的好处如果内部存的是二进制位那么试商时每商位只可能是 0 或 1内层while可以直接退化成一次if判断——cur够大就减一次、商位置 1不够大商位直接置 0。这也是为什么很多高精度代码库会把十进制和二进制两条路径分别实现二进制的除法性能要好得多。3.3 大数取模直接复用除法商留着不用也行取模运算单独写一份算法是典型的重复劳动。取模的定义就是“除法剩下的余数”所以最省事的做法是调一次除法把商丢掉把余数返回。代码少而且正确性跟着除法走除法测过之后取模就不用单独测了。void modBigInt(BigInt *a, BigInt *b, BigInt *res) { BigInt q; divBigInt(a, b, q, res); }逻辑说明这里直接让divBigInt的r参数指向res商q是个局部变量运行完就被丢弃。要注意divBigInt内部最后*r cur是结构体整体赋值只要r不是和q指向同一块内存就不会互相干扰。参数说明如果后续要频繁取模比如快速幂里的模乘建议把divBigInt的商参数传一个临时变量而不是每次都声明新的 BigInt因为结构体整体赋值也有一份内存拷贝开销。另外除数为 0 要在divBigInt入口做防御返回一个错误码或者直接打印提示不然while会死循环。4. 大数乘方与进制转换二进制扩展法把幂运算从线性降到对数4.1 快速幂原理把指数拆成二进制位逐位平方大数乘方最容易踩的性能坑是“老老实实乘 n 次”。如果算 a^1000朴素循环要做 1000 次大数乘法而大数乘法本身又是 O(m²)总开销直接起飞。二进制扩展法也叫快速幂的核心思想是把指数看成二进制数比如 13 的二进制是 1101那么 a^13 a^8 × a^4 × a^1也就是只挑二进制位为 1 的那些“a 的 2^k 次方”乘起来。实现时从左到右或从右到左都行课程设计里最常见的写法是从最低二进制位开始指数右移一位底数平方一次遇到当前位为 1 就把底数乘进结果。4.2 快速幂实现平方、乘底、指数右移三步循环void powBigInt(BigInt *base, BigInt *exp, BigInt *res) { BigInt b *base; BigInt e *exp; setSmall(res, 1); // res 1 while (e.len 1 || e.digits[0] 0) { if (e.digits[0] % 2 1) { // 当前二进制最低位是 1 mulBigInt(res, b, res); // res res * b } mulBigInt(b, b, b); // b b * b即底数平方 divSmall(e, 2, e); // e e / 2二进制右移一位 } }逻辑说明循环不变量是“b 始终等于 base 的 2^k 次方”。每轮先看指数当前最低位是 1 就把 b 乘进 res是 0 就不乘然后无条件把 b 平方同时指数除以 2。以 2^13 为例指数二进制 1101按低位到高位依次是 1、0、1、1res 依次乘上 2^1、2^4、2^8最终得到 2^13。参数说明e.digits[0] % 2能直接判断整个大数的奇偶性是因为我们的存储是十进制位个位数字的奇偶决定整个数的奇偶。divSmall(e, 2, e)是关键很多人在这里踩坑因为每个元素存的是十进制位不能直接e.digits[0] 1那样会把十位的值错误地挪到个位。正确写法是模拟一次“除以 2”的竖式从最高位到最低位逐位带余数计算。4.3 十进制与二进制统一封装输入解析与输出转换题目要求同时支持十进制和二进制大数运算这里有个设计选择内部统一存成十进制 BigInt输入输出时做进制转换。好处是加减乘除的代码只写一套进制只影响解析和打印。二进制字符串转内部十进制数采用“每读一位整体乘 2 再加当前位”的霍纳方法即可。void parseBinary(const char *s, BigInt *out) { setSmall(out, 0); for (int i 0; s[i]; i) { mulSmall(out, 2, out); if (s[i] 1) { addSmall(out, 1, out); } } } void parseDecimal(const char *s, BigInt *out) { setSmall(out, 0); for (int i 0; s[i]; i) { mulSmall(out, 10, out); addSmall(out, s[i] - 0, out); } }逻辑说明parseBinary处理“111”的逻辑是先得到 1然后乘 2 得 2、加 1 得 3再乘 2 得 6、加 1 得 7正好是二进制 111 对应的十进制 7。parseDecimal是同样的套路只是乘 10。这两段代码共用mulSmall和addSmall说明存储层抽象得好上层逻辑可以根本不管进制。输出二进制则需要反着来不断除以 2、取余数余数倒序排列就是二进制串。注意纯二进制输出天然会丢前导零如果题目要求按输入宽度补零打印函数需要接收一个最小宽度参数这个坑在下一章展开。void printBinary(BigInt *a) { BigInt tmp *a; char out[MAX_DIGITS * 8]; int idx 0; while (tmp.len 1 || tmp.digits[0] 0) { out[idx] (tmp.digits[0] % 2) 0; divSmall(tmp, 2, tmp); } for (int i idx - 1; i 0; i--) { putchar(out[i]); } }逻辑说明tmp.digits[0] % 2取个位数字的奇偶性也就是当前最低二进制位每取一位就把整个数除以 2循环直到数变成 0。倒序输出是因为先取到的是最低位。这里divSmall和快速幂里用的是同一个函数一次实现两处复用。5. 大数运算常见问题排查五个我真实踩过的坑5.1 二进制输入解析时数组越界现象解析一个 500 位的二进制字符串“111...111”时parseBinary跑到一半程序崩溃或者解析出的数值明显不对偶尔结果是负数。原因mulSmall和addSmall的实现里进位循环只跑到当前len就停了。比如当前值已经是 999乘 2 得到 1998长度从 3 变成 4如果没处理这个新增长位最高位的 1 就丢了再加 1 的时候又可能再次进位。几轮下来要么数组越界写坏相邻内存要么进位丢失数据错误。解决给mulSmall和addSmall加上统一的长度修正逻辑。乘完或加完后从当前len开始检查高一位是否非零是就len同时判断len不能超过MAX_DIGITS。我一般把这段封装成一个updateLen函数所有修改 digits 的运算结束都调一次。5.2 减法输出 “-0” 和多余前导零现象1 - 1 输出“-0”100 - 99 输出“001”更离谱的是 123 - 123 输出“-000”。原因两个问题叠加。第一个是去前导零时把循环条件写成了while (digits[len-1] 0) len--没保留最后一位导致 0 被清成空串打印时乱套。第二个是符号处理compareBigInt返回 0两数相等时代码仍然按neg1走了于是给 0 加了个负号。解决去前导零强制保底一位条件写成while (len 1 digits[len-1] 0) len--;。减法主函数开头先比较如果compareBigInt(a, b) 0直接res-sign 1并退出不进交换逻辑。从那以后我写所有涉及符号的运算都会先问一句“结果为零时符号应该是什么”。5.3 除法里商位不进位的死循环现象123 / 12 算出商 1正确答案是 10有时候程序直接卡死CPU 跑满不退出。原因按位试商的循环里cur在拼入被除数当前位之前忘了乘 10。比如被除数处理到“12”这一位时cur存的是上一次的余数 0直接加 1 得到 1而不是 0×1011最后一位 3 进来时 cur 只是从 1 变成 3而不是 1×10313于是商位少算了一轮。死循环的情况多半是除数为 0或者compareBigInt写错导致 cur 永远不小于除数。解决每次循环第一步先mulSmall(cur, 10, cur)再addSmall(cur, a-digits[i], cur)顺序不能反。除数为 0 在函数入口直接判掉打印“除数不能为 0”并返回错误码。这个坑我印象最深因为表面上看代码每一行都对只有把竖式每一步打印出来才发现 cur 缺了左移。5.4 快速幂的指数右移写错导致结果错乱现象2^10 用快速幂算出来是 2^6或者 2^4打印中间过程发现指数序列变成 10、4、1、0而不是 10、5、2、1、0。原因因为我们的 BigInt 每个元素存的是十进制位直接写e.digits[0] 1是完全错误的——十进制个位右移一位只是把个位数除以 2不是把整个大数除以 2。比如 10 的个位是 0右移还是 0整个数却应该是 5。指数右移的正确姿势是调用divSmall(e, 2, e)它会从最高位向最低位逐位带余数计算等价于对整个大数做一次十进制除法。解决把快速幂里的右移统一改走divSmall同时策略上每次右移前先判断奇偶再右移保证循环不变量正确。另外快速幂里mulBigInt(res, b, res)一定要允许res和b是同一个值我的乘法实现里是先完整算进临时数组再复制回 res所以安全如果你的乘法是边乘边写这里要格外小心别名问题。5.5 二进制输出丢了前导零现象输入“00001111”转成内部大数再打印变成“1111”和输入宽度对不上。如果题目要求按固定字长输出这块直接丢分。原因printBinary的反向取余逻辑天然丢前导零因为内部 BigInt 只保存数值不保存“输入字符串原来有多长”这个信息。解决在解析入口记录原始字符串长度或者给打印函数加一个minWidth参数输出前先补零。我常用的做法是在主程序里保存 raw 输入字符串的长度打印二进制结果时传入max(minWidth, 实际位数)手动在前面补 0。这个坑不踩一次很难意识到因为大多数自测用例都会用不带前导零的二进制串。6. 验证与进阶用六个用例把整套大数运算过一遍6.1 边界回归用例与没有写在题目里的加分项写完六个运算不要急着交先跑一组能同时覆盖“进位、借位、截断、符号、进制边界”的用例。我每次都会把这几个用例固定放在 main 函数里当回归测试运算输入期望输出验证点加法999999999999 11000000000000跨位连续进位长度加一减法1000000000 - 1999999999连续借位去掉前导零减法123 - 1230结果为零时符号不能是负乘法99999 × 999999999800001高位进位与长度修正除法123456789012345 / 123459999747595按位试商、商位补零取模2^100 mod 9718快速幂和取模的联合调用最后一行是我的习惯用快速幂算乘方时顺手把取模也验一遍。因为题目只要求“大数乘方”和“大数取模”分开实现但真正实战里这两者几乎总是搭配出现。在快速幂的三步循环里把mulBigInt换成modBigInt(mulBigInt(...), mod)就能得到模幂结果这其实是很多密码学算法的基础用法。如果你想把代码做厚这是最容易的加分点。验证方式上建议把十进制和二进制各跑一遍同样的运算确认结果一致比如十进制输入13 * 7 91二进制输入1101 * 111也应该输出1011011。这能同时验证解析、运算、打印三段逻辑没有互相污染。从那以后我每写完一个课程设计版本都强制自己先把这组用例在 main 里跑一遍再随机生成两个大数交叉验证一次最后才敢交给老师。这种“先回归、再提交”的习惯帮我在答辩前少改了很多低级错误。如果你手头这份资源里的代码也出现了类似问题照着第五章的五个坑逐条对照应该能省下不少调试时间。希望帮到你。本文还有配套的精品资源点击获取
