★ FEATURED ARTICLE 简介这份数据结构课程设计资源聚焦大数运算的完整实现面向计算机专业学生、算法初学者及需要处理超长数值的开发者。项目覆盖大数加法、减法、乘法、除法、乘方与取模六类核心操作并同时支持十进制与二进制大数运算可应用于密码学、高性能计算等场景帮助读者理解数组存储、进位借位、快速幂与长除法等关键算法。资源包共35个文件以17个txt测试数据与结果文件、5个Python验证脚本、2个C源码及头文件为主另含可执行程序与工程配置压缩包约22.24MB目录结构清晰便于对照源码与测试用例逐项验证。目前已有1353人学习下载。读者可获取完整源代码、验证数据与Python对照脚本通过阅读BigInteger相关实现与多组输入输出样例掌握大数运算的工程化写法与调试思路适合作为课程设计参考或算法练习素材。1. 大数运算课程设计从“爆 long long”到任意精度计算这套源码把加减乘除幂模全包了如果你写过阶乘、斐波那契或者 RSA 的入门作业大概率见过这个场景输入 100程序输出一个负数或者 0。原因不玄学就是long long溢出了。C/C 里最大的内置整数类型也就 64 位能表示的范围在 20 位十进制数左右而 100 的阶乘有 158 位。这个课程设计要解决的就是这类问题——不依赖任何第三方大数库用数据结构课上学到的链表、动态数组、字符串处理手写一套支持任意长度十进制和二进制的大数运算库覆盖加法、减法、乘法、除法、乘方、取模六个核心运算。适合正在做数据结构课程设计的学生也适合想理解大数底层实现、不想只调 API 的开发者。下面从项目结构、核心算法到编译运行完整拆一遍。2. 项目结构与技术选型为什么用字符串动态数组而不是链表2.1 整体目录布局拿到源码包后先看目录结构。这类课程设计通常不会太复杂但组织方式直接决定了你后面改代码顺不顺手。一个典型的布局如下bignum/ ├── include/ │ ├── bignum.h # 大数结构体定义与函数声明 │ └── base_convert.h # 进制转换接口 ├── src/ │ ├── bignum.c # 核心运算实现 │ ├── add_sub.c # 加减法 │ ├── mul_div.c # 乘除法 │ ├── power_mod.c # 乘方与取模 │ └── base_convert.c # 十进制/二进制互转 ├── tests/ │ ├── test_add.c │ ├── test_mul.c │ └── test_all.c ├── Makefile └── README.mdinclude/放头文件src/放实现tests/放测试用例Makefile统一编译。这种分法在课程设计里算比较规范的好处是加减法和乘除法分开编译改一个模块不会牵动全部。如果你的源码包结构不同比如所有代码堆在一个main.c里也不用慌核心逻辑是一样的只是找函数麻烦一点。2.2 大数的数据结构设计大数运算的第一个决策是怎么存一个超长整数常见方案有三种——字符串、动态数组、链表。这个项目用的是字符串存储十进制 动态数组存储二进制的混合方案。先看核心结构体// include/bignum.h #define MAX_DIGITS 10000 // 最大位数按需调整 typedef struct { int sign; // 符号0 正1 负 int base; // 进制10 或 2 int len; // 当前有效位数 char digits[MAX_DIGITS]; // 低位在前digits[0] 是个位 } BigNum;这里有几个设计点值得说清楚低位在前存储。digits[0]存个位digits[1]存十位依次往后。为什么反过来因为加减乘除都是从低位往高位算的进位也是往高位走。如果高位在前每次进位都要移动整个数组时间复杂度直接爆炸。低位在前的话进位只需要digits[i1]O(1) 操作。符号单独存。不要用补码那套大数运算里补码会让除法变得极其恶心。单独用一个sign字段运算时先判断符号再决定用加法还是减法逻辑清晰得多。base 字段区分进制。十进制和二进制共用同一个结构体运算时根据base决定进位阈值——十进制逢十进一二进制逢二进一。这样加法和乘法的核心代码只需要改一个常量不用写两套。固定数组 vs 动态分配。这里用了固定大小的char digits[MAX_DIGITS]好处是实现简单、不用管内存释放坏处是每个 BigNum 占 10KB 栈空间开多了会爆栈。常见做法是改成char *digits加malloc但课程设计里为了代码可读性固定数组也能接受。如果你要算几万位的数把MAX_DIGITS调大或者改成动态分配就行。注意digits里存的是数值 0-9或 0-1不是字符0-9。输入输出时需要做一次转换这是新手最容易搞混的地方。2.3 编译与运行三步跑通第一个测试在讲核心算法之前先把项目跑起来确认环境没问题。这类 C 项目通常只需要 gcc 和 make# 1. 编译 make # 2. 运行全部测试 ./test_all # 3. 或者单独跑加法测试 ./test_add如果make报错大概率是这两个原因一是Makefile里的编译器写的是gcc但你系统只有clang改成CC clang即可二是头文件路径没配好检查CFLAGS里有没有-Iinclude。编译通过后test_all会输出一组预设的测试结果比如[PASS] 12345678901234567890 98765432109876543210 111111111011111111100 [PASS] 100! 位数 158 [PASS] 2^100 mod 1000000007 976371285看到[PASS]就说明核心运算没问题可以开始看代码了。如果某个用例[FAIL]先别急着改算法用printf把中间结果打出来确认是输入解析错了还是运算逻辑错了。3. 核心运算拆解加减乘除幂模的代码实现3.1 大数加法一个循环搞定进位加法是所有运算的基础逻辑最简单但细节最多。先看代码// src/add_sub.c BigNum big_add(BigNum a, BigNum b) { BigNum res; res.sign 0; res.base a.base; int carry 0; // 进位 int max_len a.len b.len ? a.len : b.len; int i; for (i 0; i max_len || carry; i) { int da (i a.len) ? a.digits[i] : 0; // 短的那个补 0 int db (i b.len) ? b.digits[i] : 0; int sum da db carry; res.digits[i] sum % a.base; // 当前位 carry sum / a.base; // 进位 } res.len i; return res; }逐段解释循环条件i max_len || carry。前半段保证两个数的所有位都处理完后半段保证最高位的进位不会丢。比如99 1处理完两位后carry还是 1必须再循环一次把进位写进去否则结果变成00。短数补零。i a.len ? a.digits[i] : 0这行是关键。两个数长度不一样时短的那个高位补 0这样就不用写两套逻辑。比如123 4545 在i2时返回 0等价于045。取模和整除。sum % base得到当前位的值sum / base得到进位。十进制时 base10二进制时 base2同一套代码通吃。这也是为什么结构体里要存base字段。结果长度。循环结束时i的值就是结果的有效位数直接赋给res.len。注意这里没有去掉前导零因为低位在前存储高位在数组末尾前导零就是末尾的 0。如果结果实际是00123存储为32100len5但有效位只有 3 位。常见做法是在返回前加一个去零循环while (res.len 1 res.digits[res.len - 1] 0) { res.len--; }这个去零操作在减法和除法里也必须做否则后续比较大小会出错。3.2 大数减法借位与符号处理减法比加法多两个坑借位和符号。代码结构如下// src/add_sub.c int big_cmp_abs(BigNum a, BigNum b) { // 比较绝对值大小ab 返回 1ab 返回 -1相等返回 0 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; } BigNum big_sub(BigNum a, BigNum b) { // 先处理符号a - b a (-b) if (a.sign ! b.sign) { b.sign !b.sign; return big_add(a, b); } // 同号相减比较绝对值决定结果符号 int cmp big_cmp_abs(a, b); if (cmp 0) return big_zero(a.base); if (cmp 0) { BigNum tmp big_sub(b, a); tmp.sign !a.sign; return tmp; } // |a| |b|正常借位减法 BigNum res; res.sign a.sign; res.base a.base; int borrow 0; for (int i 0; i a.len; i) { int da a.digits[i] - borrow; int db (i b.len) ? b.digits[i] : 0; if (da db) { da a.base; borrow 1; } else { borrow 0; } res.digits[i] da - db; } res.len a.len; while (res.len 1 res.digits[res.len - 1] 0) res.len--; return res; }符号处理是减法的核心。a - b本质上可以转化为a (-b)所以异号相减直接翻转b的符号调加法。同号相减时如果|a| |b|结果是负数递归调用big_sub(b, a)算出绝对值再翻符号。这样就把所有情况都归约到了「大减小」这一种。借位逻辑。da a.digits[i] - borrow先减去上一位的借位如果da db就从高位借一位da baseborrow 1。注意借位是在当前位加base不是加 10这样二进制减法也能用同一套代码。比较函数big_cmp_abs。先比长度长度一样再从高位往低位逐位比。因为低位在前存储所以要从len-1往 0 遍历。这个函数在减法和除法里都会用到建议单独抽出来。3.3 大数乘法O(n²) 竖式与 Karatsuba 优化乘法用竖式模拟时间复杂度 O(n²)。对于课程设计来说这个复杂度足够了算 1000 位的乘法也就百万次操作。代码// src/mul_div.c BigNum big_mul(BigNum a, BigNum b) { BigNum res big_zero(a.base); res.len a.len b.len; // 结果最多这么多位 memset(res.digits, 0, res.len); for (int i 0; i a.len; i) { int carry 0; for (int j 0; j b.len || carry; j) { int db (j b.len) ? b.digits[j] : 0; int cur res.digits[i j] a.digits[i] * db carry; res.digits[i j] cur % a.base; carry cur / a.base; } } // 去前导零 while (res.len 1 res.digits[res.len - 1] 0) res.len--; res.sign a.sign ^ b.sign; // 同号为正异号为负 return res; }双重循环的含义。外层遍历a的每一位内层遍历b的每一位a.digits[i] * b.digits[j]的结果累加到res.digits[ij]上。这就是竖式乘法的本质第 i 位乘第 j 位结果落在第 ij 位。进位处理。cur res.digits[ij] a.digits[i] * db carry注意这里加了res.digits[ij]因为不同位的乘积可能落在同一个位置需要累加。比如a[0]*b[1]和a[1]*b[0]都落在res[1]。符号。a.sign ^ b.sign异或运算同号为 0正异号为 1负一行搞定。优化方向。如果面试或答辩被问到优化可以提 Karatsuba 算法把 O(n²) 降到 O(n^1.585)。核心思想是分治把大数拆成高低两半用三次乘法代替四次。但课程设计里 O(n²) 完全够用Karatsuba 的常数因子大位数少的时候反而更慢。3.4 大数除法与取模试商法的实现除法是最复杂的因为要模拟人工试商的过程。常见做法是「减法试商」从高位开始每次取一段被除数不断减去除数减几次商就是几。但这样效率太低更好的做法是「二分试商」或「移位试商」。这里给一个基于减法的简化版本// src/mul_div.c void big_divmod(BigNum a, BigNum b, BigNum *quotient, BigNum *remainder) { if (b.len 1 b.digits[0] 0) { // 除零处理 quotient-len 0; return; } BigNum q big_zero(a.base); BigNum r big_zero(a.base); q.len a.len; for (int i a.len - 1; i 0; i--) { // 余数左移一位加上当前位 for (int k r.len; k 0; k--) r.digits[k] r.digits[k-1]; r.digits[0] a.digits[i]; r.len; // 试商r 能减几次 b int cnt 0; while (big_cmp_abs(r, b) 0) { r big_sub(r, b); cnt; } q.digits[i] cnt; } while (q.len 1 q.digits[q.len-1] 0) q.len--; *quotient q; *remainder r; }逐位试商。从被除数的最高位开始每次把余数左移一位相当于乘 base加上当前位然后看这个数能减几次除数。减的次数就是商的当前位。这个过程和手算长除法一模一样。效率问题。内层while每次减一个除数如果商很大比如 9999就要减 9999 次。优化方法是二分试商先估算商的范围用二分查找确定最大减次数。但课程设计里数据规模不大直接减也能过。取模。取模就是除法的余数big_mod(a, b)直接调用big_divmod取remainder即可。注意取模结果的符号跟随被除数这是 C 语言的标准行为。3.5 大数乘方与快速幂取模乘方就是重复乘法但朴素做法太慢。a^n需要 n 次乘法n 是 100 的时候还行n 是 10^9 就废了。所以用快速幂// src/power_mod.c BigNum big_pow(BigNum a, long long n) { BigNum res big_from_int(1, a.base); BigNum base a; while (n 0) { if (n 1) res big_mul(res, base); base big_mul(base, base); n 1; } return res; } BigNum big_pow_mod(BigNum a, BigNum n, BigNum m) { BigNum res big_from_int(1, a.base); BigNum base big_mod(a, m); // 把 n 转成二进制逐位处理 for (int i 0; i n.len; i) { if (n.digits[i] 1) res big_mod(big_mul(res, base), m); base big_mod(big_mul(base, base), m); } return res; }快速幂的核心。把指数 n 写成二进制比如2^10 2^(1010b) 2^8 * 2^2。每次循环把底数平方如果当前二进制位是 1 就乘到结果上。这样乘法次数从 O(n) 降到 O(log n)。快速幂取模。在每一步乘法后都对 m 取模防止中间结果过大。这是 RSA 加密里的标准操作big_pow_mod就是 RSA 的核心函数。注意指数 n 本身也是大数所以用n.digits[i]逐位判断而不是n 1。参数说明。a是底数n是指数m是模数。big_from_int是把普通整数转成大数的辅助函数实现很简单就是不断取模存进digits数组。4. 避坑与排查大数运算里最容易翻车的五个地方4.1 前导零没去掉导致比较大小出错现象big_cmp_abs判断100和99时返回相等或错误结果。原因减法或除法产生的结果末尾有零len没有更新。比如100 - 1 099存储为990len3但实际有效位只有 2 位。比较时先比len3 2误判为099 99。解决每次运算返回前都加去零循环while (len 1 digits[len-1] 0) len--;。注意条件是len 1因为数字 0 本身len1不能去成len0。4.2 二进制和十进制混用导致进位错误现象二进制加法1 1得到2而不是10。原因进位时用了硬编码的 10 而不是base。sum % 10和sum / 10在二进制下就错了。解决所有涉及进位的运算都用a.base而不是字面量 10。输入输出时也要根据base做转换二进制输出时digits里只有 0 和 1。4.3 除法试商死循环现象程序卡在big_divmod里出不来。原因big_sub返回的结果没有去前导零导致big_cmp_abs(r, b)永远返回 0while循环停不下来。解决确保big_sub内部做了去零。另外在while循环里加一个计数器如果cnt超过base说明试商逻辑有问题直接 break 并打印调试信息。4.4 乘方指数溢出现象big_pow(a, n)里 n 用int存算2^100时 n100 没问题但算2^100000时 n 溢出。原因指数本身可能很大int只有 32 位。解决把指数参数改成long long或者直接用BigNum存指数。如果指数是BigNum快速幂的循环要改成遍历指数的每一位就像big_pow_mod那样。4.5 栈空间不足导致段错误现象程序运行到一半报Segmentation fault尤其是在递归调用big_sub或创建多个BigNum局部变量时。原因BigNum结构体里的digits数组是固定大小的如果MAX_DIGITS设成 10000每个BigNum占约 10KB。递归深度一大或者函数里开了多个BigNum栈就爆了。解决把digits改成动态分配char *digits在big_init里malloc在big_free里释放。或者把MAX_DIGITS调小到实际需要的位数。另一个办法是把大数组改成static或全局变量但这样就不能重入了。5. 二次开发与扩展从课程设计到可用工具库的改造思路5.1 把固定数组改成动态内存课程设计里用固定数组是为了省事但要做成能实际用的库动态内存是第一步。改造方法typedef struct { int sign; int base; int len; int cap; // 容量 char *digits; // 动态数组 } BigNum; BigNum big_init(int base, int cap) { BigNum n; n.sign 0; n.base base; n.len 1; n.cap cap; n.digits (char *)calloc(cap, sizeof(char)); return n; } void big_free(BigNum *n) { free(n-digits); n-digits NULL; n-len n-cap 0; }改造后每个BigNum只占几十字节栈压力小很多。但要注意内存泄漏——每次big_init都要对应一个big_free。常见做法是写一个big_copy函数返回新的BigNum调用者负责释放。5.2 增加更多运算GCD、进制转换、比较运算符课程设计只要求加减乘除幂模但实际用起来还需要这些最大公约数。用辗转相除法基于big_mod实现BigNum big_gcd(BigNum a, BigNum b) { while (!(b.len 1 b.digits[0] 0)) { BigNum r big_mod(a, b); a b; b r; } return a; }任意进制转换。当前只支持十进制和二进制扩展到 2-36 进制只需要改base字段和输入输出函数。核心是base_convert.c里的to_base和from_base用短除法不断取余。比较运算符。把big_cmp_abs扩展成big_cmp加上符号判断然后封装成big_gt、big_lt、big_eq等函数用起来更顺手。5.3 性能验证怎么确认你的优化真的有效改完代码后别凭感觉说「快了」。用clock()测一下实际耗时#include time.h void benchmark() { BigNum a big_from_str(123456789012345678901234567890, 10); BigNum b big_from_str(987654321098765432109876543210, 10); clock_t start clock(); for (int i 0; i 10000; i) { BigNum c big_mul(a, b); big_free(c); } clock_t end clock(); printf(10000 次乘法耗时: %.3f 秒\n, (double)(end - start) / CLOCKS_PER_SEC); }跑之前和跑之后各测一次对比数字。如果优化后反而更慢大概率是动态内存分配的开销盖过了算法优化这时候可以考虑内存池或者对象复用。5.4 一个我踩过的坑递归减法的栈溢出最后说一个血泪经验。我一开始写big_sub的时候为了代码简洁用了递归|a| |b|时递归调用big_sub(b, a)再翻符号。测试小数据没问题但算100000...0 - 1的时候直接段错误。原因是递归深度等于数字的位数10000 位的数递归 10000 层每层都有局部BigNum变量栈直接爆了。后来改成迭代版本用一个swap交换a和b算完再翻符号问题解决。从那以后我每次写递归函数都先问自己递归深度会不会跟输入规模线性相关如果是强制改迭代。希望这个教训能帮你少走一段弯路。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
