简介这份数据结构课程设计资源聚焦大数运算的完整实现面向计算机专业学生及需要处理超长数值的开发者。项目覆盖大数加法、减法、乘法、除法、乘方与取模六类核心操作并同时支持十进制与二进制大数运算可应用于密码学、高性能计算等场景帮助读者理解数组存储、进位借位、快速幂与长除法等算法细节。资源包共35个文件以17个txt验证数据、5个Python测试脚本、4个data数据文件及2个cpp源文件为主另含头文件、可执行程序与工程配置压缩包约22.24MB目录结构便于对照源码与测试用例。目前已有1352人学习下载。通过阅读BigInteger核心实现与配套Python验证代码读者可掌握大数运算的完整设计思路、算法优化策略及跨语言结果比对方法适合作为课程设计参考或算法练习素材。1. 大数运算课程设计为什么 64 位整数一撞就碎得自己造轮子做数据结构课程设计大数运算是被选得最多、也最容易翻车的一类题。C 语言里unsigned long long顶天 1.8×10¹⁹Java 的long也就 9.2×10¹⁸一旦题目要求算 100 的阶乘、2 的 1000 次方或者两个 200 位十进制数相乘内置类型直接溢出结果变成负数或者垃圾值。这不是玄学是位数不够。大数运算要解决的核心问题就一句话把数字拆成一位一位存进数组或字符串自己实现加减乘除、乘方、取模并且同时兼容十进制和二进制两种进制。它适合正在做数据结构课设的本科生也适合想搞明白高精度算法底层逻辑的开发者。下面我按自己带课设的经验把选型、实现、参数和踩坑一次讲透。2. 存储结构怎么选十进制和二进制大数的底层表示2.1 为什么不用字符串直接算而要先想清楚存储很多人第一反应是用字符串存大数因为输入输出方便。字符串确实能存但每次运算都要做字符到数字的转换乘法和除法里反复取位、进位代码会变得又长又慢。更常见的做法是用整型数组每个元素存一位或者若干位。这里有个关键分叉十进制大数和二进制大数的存储粒度不一样。十进制大数我一般用int数组每个元素存 0 到 9 的一位数字低位放在数组前面也就是下标 0 存个位。这样进位方向是从低下标往高下标走和手算一致。二进制大数则每个元素存 0 或 1或者为了效率每个元素存 30 位、60 位但课设阶段建议老老实实一位一存先把逻辑跑通。提示低位在前、高位在后是所有大数运算的默认约定。如果你反过来存进位和借位方向全乱后面除法会写到怀疑人生。2.2 结构体定义与初始化一份能同时吃十进制和二进制的骨架下面这份 C 语言结构体是我课设里反复用过的版本同时支持两种进制靠一个base字段区分。#include stdio.h #include stdlib.h #include string.h #define MAX_DIGITS 2000 // 支持约 2000 位十进制二进制可到 6000 位左右 typedef struct { int digits[MAX_DIGITS]; // 低位在前digits[0] 是个位/最低位 int len; // 当前有效位数 int base; // 10 表示十进制2 表示二进制 int sign; // 1 正数-1 负数0 表示零 } BigNum; // 初始化把字符串转成大数自动识别进制 void initBigNum(BigNum *n, const char *str, int base) { memset(n-digits, 0, sizeof(n-digits)); n-len 0; n-base base; n-sign 1; int start 0; if (str[0] -) { n-sign -1; start 1; } else if (str[0] ) { start 1; } int L strlen(str); for (int i L - 1; i start; i--) { char c str[i]; int v; if (c 0 c 9) v c - 0; else if (c A c F) v c - A 10; else if (c a c f) v c - a 10; else continue; n-digits[n-len] v; } // 去掉高位多余的零 while (n-len 1 n-digits[n-len - 1] 0) n-len--; if (n-len 1 n-digits[0] 0) n-sign 0; }这段代码的逻辑很直白从字符串末尾往前扫因为末尾是个位。遇到负号先记符号。十六进制字符也顺手支持了虽然标题只要求十进制和二进制但多支持一个不费事。参数base决定后续运算时进位阈值是 10 还是 2。len始终维护有效位数高位零全部砍掉否则比较大小和除法会出错。2.3 十进制与二进制共存的三个设计约束同时支持两种进制不是把base一改就完事。我踩过的坑集中在三点。第一进位阈值必须跟着base走十进制满 10 进 1二进制满 2 进 1写死 10 的话二进制加法直接错。第二输出函数要按base决定打印字符二进制只打印 0 和 1十进制打印 0 到 9。第三比较大小的时候先比lenlen相同再从高位往低位逐位比这个逻辑和进制无关可以复用。把这三条守住后面加减乘除乘方取模都能共用一套底层。3. 加减乘除四件套从手算竖式到可复现代码3.1 大数加法和减法符号处理才是真正的难点加法本身不难难的是带符号。我的做法是先写一个无符号加法addAbs只负责绝对值相加符号另外判断。减法同理先写subAbs保证大减小如果实际是小减大就交换再取负。// 绝对值加法c |a| |b| void addAbs(const BigNum *a, const BigNum *b, BigNum *c) { c-base a-base; c-len 0; int carry 0; int maxLen (a-len b-len) ? a-len : b-len; for (int i 0; i maxLen || carry; i) { int sum carry; if (i a-len) sum a-digits[i]; if (i b-len) sum b-digits[i]; c-digits[c-len] sum % c-base; // 关键按 base 取余 carry sum / c-base; // 关键按 base 进位 } c-sign (c-len 1 c-digits[0] 0) ? 0 : 1; } // 绝对值减法要求 |a| |b|结果 c |a| - |b| void subAbs(const BigNum *a, const BigNum *b, BigNum *c) { c-base a-base; c-len 0; int borrow 0; for (int i 0; i a-len; i) { int diff a-digits[i] - borrow - (i b-len ? b-digits[i] : 0); if (diff 0) { diff c-base; borrow 1; } else borrow 0; c-digits[c-len] diff; } while (c-len 1 c-digits[c-len - 1] 0) c-len--; c-sign (c-len 1 c-digits[0] 0) ? 0 : 1; }注意sum % c-base和sum / c-base这两行它们就是十进制和二进制共用的关键。base是 10 时满十进一是 2 时满二进一同一份代码不用改。减法里的diff c-base同理借位时借的是base不是固定的 10。很多人二进制减法算错就是这里写死了 10。带符号的加减法规则和初中数学一样同号相加取相同符号异号相减取绝对值大的符号。我一般写一个compareAbs先比绝对值大小再分四种情况调用addAbs或subAbs。这块逻辑不复杂但分支多建议单独写测试用例把5 -3、-5 3、-5 -3、5 -5全跑一遍。3.2 大数乘法O(n²) 竖式乘法和它的参数边界乘法用竖式两层循环c[ij] a[i] * b[j]最后统一处理进位。这是最稳的写法复杂度 O(n²)2000 位乘 2000 位大概 400 万次内层操作课设完全够用。void mulBig(const BigNum *a, const BigNum *b, BigNum *c) { c-base a-base; c-len a-len b-len; c-sign (a-sign 0 || b-sign 0) ? 0 : a-sign * b-sign; memset(c-digits, 0, sizeof(c-digits)); for (int i 0; i a-len; i) { for (int j 0; j b-len; j) { c-digits[i j] a-digits[i] * b-digits[j]; } } // 统一进位 int carry 0; for (int i 0; i c-len; i) { int tmp c-digits[i] carry; c-digits[i] tmp % c-base; carry tmp / c-base; } while (c-len 1 c-digits[c-len - 1] 0) c-len--; if (c-len 1 c-digits[0] 0) c-sign 0; }参数上要注意c-len初始设为a-len b-len这是乘积位数的上界。进位循环必须覆盖整个c-len因为内层累加后c-digits[i]可能远大于base比如十进制下最大是 9×9×2000不统一进位会溢出。二进制下每个元素最大是 1×1×位数同样要进位。这个统一进位的写法比边乘边进位更不容易错代价是多一次遍历。3.3 大数除法试商法是唯一靠谱的路除法是四件套里最难的。我试过二分试商也试过逐位试商最后发现课设阶段最稳的是「逐位试商」从被除数最高位开始每次拉一位下来用减法不断试出当前位的商。// 无符号除法q a / b, r a % b void divModAbs(const BigNum *a, const BigNum *b, BigNum *q, BigNum *r) { q-base a-base; q-len a-len; q-sign 1; memset(q-digits, 0, sizeof(q-digits)); r-base a-base; r-len 0; r-sign 0; memset(r-digits, 0, sizeof(r-digits)); for (int i a-len - 1; i 0; i--) { // 余数左移一位乘以 base加上当前位 for (int k r-len; k 0; k--) r-digits[k] r-digits[k - 1]; r-digits[0] a-digits[i]; r-len; while (r-len 1 r-digits[r-len - 1] 0) r-len--; // 试商用减法数出这一位商 int cnt 0; while (compareAbs(r, b) 0) { BigNum tmp; subAbs(r, b, tmp); *r tmp; cnt; } q-digits[i] cnt; } while (q-len 1 q-digits[q-len - 1] 0) q-len--; if (q-len 1 q-digits[0] 0) q-sign 0; }这段代码里compareAbs是比较绝对值的辅助函数返回 1、0、-1。试商用减法循环十进制下每位最多减 9 次二进制下最多减 1 次所以二进制除法反而更快。参数上要注意余数r在每轮开始前要左移一位左移就是所有位往高位挪一格低位补当前被除数的位。这个左移在十进制下相当于乘 10二进制下相当于乘 2和base一致。注意除法里q-digits[i] cnt直接赋值因为试商结果一定小于base。如果你发现商位大于等于base说明试商循环写错了检查compareAbs的边界。3.4 乘方和取模复用乘法与除法的组合拳乘方就是快速幂把指数转成二进制不断平方。取模就是除法取余数。这两个都是前面四件套的组合不需要新算法。// 快速幂c a^e结果可能很大课设里一般配合取模使用 void powBig(const BigNum *a, int e, BigNum *c) { BigNum base *a; initBigNum(c, 1, a-base); while (e 0) { if (e 1) { BigNum tmp; mulBig(c, base, tmp); *c tmp; } e 1; if (e 0) { BigNum tmp; mulBig(base, base, tmp); base tmp; } } } // 取模r a % m void modBig(const BigNum *a, const BigNum *m, BigNum *r) { BigNum q; divModAbs(a, m, q, r); r-sign a-sign; // 余数符号跟随被除数 }快速幂里e 1判断当前二进制位是否为 1是就乘进结果然后指数右移一位底数平方。这个算法把 O(e) 次乘法降到 O(log e) 次算 2 的 1000 次方只需要约 10 次乘法。取模直接调除法余数符号跟随被除数这是 C 语言%的语义保持一致。参数上注意powBig的指数用int就够课设里指数很少超过 10000真要超大指数可以把指数也做成大数但那是另一个难度了。4. 避坑与排查大数运算课设里最容易翻车的 5 个点4.1 现象二进制加法结果比预期多一位或者十进制减法出现负数位原因进位或借位阈值写死了 10。二进制加法里sum % 10和sum / 10会让结果错乱因为二进制满 2 就该进位。减法里diff 10在二进制下借多了。解决所有涉及进位、借位、取余、整除的地方统一用base字段不要出现字面量 10。写完后用base2跑一组1011 0110验证。4.2 现象乘法结果高位全是零或者长度不对原因c-len初始化成a-len b-len后没有在最后砍掉高位零。或者进位循环只跑到a-len b-len - 1漏了最高位的进位。解决进位循环范围用c-len循环结束后用while砍高位零。如果最高位进位没处理结果会少一位比如99 * 99 9801变成980。4.3 现象除法死循环程序卡住原因试商循环里compareAbs(r, b) 0一直成立因为减法结果没有正确更新r或者subAbs要求|a| |b|但传参反了。解决在试商循环里每次减完把tmp赋回r确保r真的变小。另外检查compareAbs的实现先比lenlen相同再从高位往低位比不要从低位比。4.4 现象取模结果符号不对或者余数大于模数原因余数符号没有跟随被除数或者除法里余数没有最终规范化。解决modBig最后加一行r-sign a-sign。如果余数绝对值大于等于模数绝对值说明试商没试够检查试商循环条件。4.5 现象同时跑十进制和二进制时输出乱码或位数错乱原因输出函数没有按base分支或者初始化时base字段没传对。解决输出函数里判断n-base 10打印0digitn-base 2只打印0或1。初始化时显式传base不要靠全局变量。5. 验证与进阶用对拍和边界用例把大数运算钉死课设验收的时候老师不会只看你跑通一个例子。我一般会准备三组验证。第一组是边界用例0 加 0、0 减 0、1 乘 0、0 除以非零、非零除以 1、负数乘负数、二进制全 1 加 1。第二组是对拍用 Python 的int做参照随机生成 100 组大数把 C 程序的结果和 Python 结果逐位比对。第三组是性能边界2000 位十进制乘法跑 100 次看耗时是否在可接受范围。对拍脚本可以这样写用 Python 生成测试数据并调用编译好的 C 程序import random, subprocess def gen_big(base, length): if base 10: return .join(random.choice(0123456789) for _ in range(length)) else: return .join(random.choice(01) for _ in range(length)) for _ in range(100): base random.choice([10, 2]) a gen_big(base, random.randint(1, 50)) b gen_big(base, random.randint(1, 50)) # 调用 C 程序传入 a b base拿回结果 result subprocess.run([./bignum, a, b, str(base)], capture_outputTrue, textTrue) c_result result.stdout.strip() # Python 按进制解析后计算再转回字符串比对 py_result str(int(a, base) int(b, base)) if base 2: py_result bin(int(a, 2) int(b, 2))[2:] assert c_result py_result, fFAIL: {a} {b} base {base} print(all pass)这个脚本的关键是int(a, base)按指定进制解析二进制结果用bin()转回字符串时去掉0b前缀。对拍能抓出 90% 的进位和符号 bug比手算靠谱得多。进阶一点如果你想让除法更快可以把试商从逐次减法改成二分试商在0到base-1之间二分找商十进制下最多 4 次比较比最多 9 次减法快一倍。二进制下没区别因为商只能是 0 或 1。另一个技巧是压位十进制下每个数组元素存 4 位数字乘法内层循环减少 4 倍但进位和输出要额外处理课设里看时间够不够再决定。我自己的习惯是每写完一个运算函数先不急着写下一个而是用对拍脚本单独跑这个函数 100 组随机数据全过了再往下走。大数运算的 bug 会传染加法错了乘法必错除法错了取模必错。把每个环节钉死最后组合起来才稳。希望帮到你。本文还有配套的精品资源点击获取
