★ FEATURED ARTICLE 简介本资源是面向计算机专业本科生的数据结构课程设计实践项目聚焦大数运算这一经典难点问题完整实现十进制与二进制双模态下的加、减、乘、除、乘方、取模六大核心运算适用于算法课设、密码学前置实践及高性能计算入门训练。压缩包共35个文件含5个Python脚本含testadd.py等6组验证用例、4个data测试数据集、2个C源文件BigInteger.cpp/h及对应编译产物.o/.exe另有Makefile.win和Project1.dev工程配置便于跨平台复现与调试整体22.24MB结构清晰源码与测试分离支持分模块学习与结果比对。已有1352人学习下载提供可直接运行的完整工程、多进制统一接口设计、手写竖式/快速幂/长除法等算法的代码级实现以及Python与C双语言验证结果res*.txt与result*.py助读者深入理解底层数据组织逻辑与算法优化细节。1. 大数运算不是“加个 long long 就完事”当十进制超 20 位、二进制超 64 位标准整型彻底失能课程设计必须亲手拆解数字的底层表示与运算法则你写a b编译器瞬间出结果——那是建立在 CPU 硬件支持 32/64 位定点运算的前提上。可一旦输入是99999999999999999999999999999930 位十进制或111100001111000011110000111100001111000011110000111160 位二进制long long直接溢出double开始丢精度int彻底失效。这不是“数据大”而是数值表达已突破机器字长的物理边界。本课程设计要做的不是调用 Python 的int或 Java 的BigInteger——那是黑匣子而是用 C/C/Java 基础类型char[]、int[]、ArrayListInteger从零构建一套可验证、可调试、可切换进制的大数运算引擎支持加减乘除、乘方、取模且同一套核心逻辑无缝兼容十进制与二进制输入输出。它面向的是数据结构课的核心训练目标理解线性结构数组/链表如何承载抽象代数对象掌握高精度算法的时间/空间权衡以及把纸面竖式演算精准翻译成可执行代码的工程能力。如果你正卡在“为什么手写大数总在边界 case 上翻车”“二进制进位和十进制进位怎么统一处理”“乘方时栈爆了怎么办”这篇就是为你写的血泪复现笔记。2. 用字符数组承载数字为什么不用 string为什么必须反转存储十进制与二进制共用同一套底层容器2.1 字符数组 vs string内存可控性决定调试成败很多同学第一反应是用std::string存12345。看似简洁但问题立刻浮现string的operator[]返回char而char是有符号的-128~127当你做digit s[i] - 0时若s[i]是0到9没问题但若后续扩展到十六进制含Achar可能溢出更致命的是string的内部缓冲区管理不可控——push_back()可能触发多次内存重分配而大数运算中频繁的进位/借位操作需要稳定地址访问调试时无法直接printf(%d, arr[i])查看每一位数值必须先转int(s[i]-0)增加干扰。正确做法用vectorint或int[]存储每一位的数值**非字符**。例如12345存为digits {5,4,3,2,1}注意反转存储。// C 示例字符串转大数内部表示十进制 vectorint strToBigNum(const string s) { vectorint res; // 跳过前导空格和符号本设计暂不支持负数简化逻辑 int start 0; while (start s.length() (s[start] || s[start] )) start; // 从末位开始读存入 vector实现反转 for (int i s.length() - 1; i start; i--) { if (s[i] 0 s[i] 9) { res.push_back(s[i] - 0); } else { throw invalid_argument(Invalid digit in input: string(1, s[i])); } } return res; }提示res.push_back(s[i] - 0)这一行是关键——它把字符0~9映射为整数0~9并按低位在前顺序存入。这样res[0]永远是最低位个位res.size()就是有效位数加法时i0对齐个位天然避免索引错位。2.2 二进制大数同样用vectorint但每位只允许 0 或 1二进制输入如10110同样反转存储为{0,1,1,0,1}。此时digits[i]的取值范围被严格限定为{0,1}这直接影响后续所有运算的进位逻辑进位基数从 10 变为 2。但容器类型、存储结构、索引方式与十进制完全一致——这是实现“同一套核心逻辑”的前提。2.3 统一容器设计BigNum类的骨架定义我们定义一个轻量级类屏蔽进制差异暴露统一接口class BigNum { private: vectorint digits; // 低位在前每位是 0-9十进制或 0-1二进制 int base; // 进制基数10 或 2 bool isNegative; // 本设计暂不实现负数设为 false留作扩展位 public: BigNum(const string s, int b 10) : base(b), isNegative(false) { if (b 10) { digits strToDec(s); } else if (b 2) { digits strToBin(s); } else { throw invalid_argument(Unsupported base: to_string(b)); } removeLeadingZeros(); // 清除高位冗余 0如 {0,0,1} → {1} } // 核心运算方法后续章节实现 BigNum add(const BigNum other) const; BigNum subtract(const BigNum other) const; BigNum multiply(const BigNum other) const; BigNum divide(const BigNum other) const; BigNum mod(const BigNum other) const; BigNum pow(int exp) const; // 仅支持整数指数 string toString() const; // 转回字符串按原进制输出不反转 };base字段是开关所有运算函数内部都通过base决定进位/借位阈值carry digit / base、取余方式digit % base。不改容器只改base就完成了进制切换——这才是数据结构设计的优雅。3. 加减乘除四则运算从纸面竖式到代码循环每一步进位/借位都可追踪3.1 大数加法模拟小学竖式carry 是唯一状态变量加法是最基础的也是其他运算的基石。核心思想对齐低位i0逐位相加 进位结果位 (a[i] b[i] carry) % base新进位 (a[i] b[i] carry) / base。BigNum BigNum::add(const BigNum other) const { if (this-base ! other.base) throw invalid_argument(Base mismatch in addition); vectorint res; int carry 0; int maxLen max(this-digits.size(), other.digits.size()); for (int i 0; i maxLen || carry; i) { int sum carry; if (i this-digits.size()) sum this-digits[i]; if (i other.digits.size()) sum other.digits[i]; res.push_back(sum % this-base); carry sum / this-base; } BigNum result(, this-base); result.digits res; result.removeLeadingZeros(); return result; }参数说明maxLen确保遍历到较长数的最高位|| carry条件处理最后一位进位如99911000多出一位sum % base是当前位结果sum / base是向下取整的进位值C 中整数除法自动截断。3.2 大数减法借位逻辑比加法更易翻车必须预判是否够减减法难点在于“不够减要借位”。不能简单a[i] - b[i] - borrow因为a[i]可能小于b[i] borrow。正确做法先计算diff a[i] - b[i] - borrow若diff 0则向高位借 1即diff baseborrow 1否则borrow 0。BigNum BigNum::subtract(const BigNum other) const { if (this-base ! other.base) throw invalid_argument(Base mismatch in subtraction); // 简化要求 *this other否则抛异常课程设计可不处理负数 if (this-compare(other) 0) throw runtime_error(Subtraction result would be negative); vectorint res; int borrow 0; for (int i 0; i this-digits.size(); i) { int diff this-digits[i] - borrow; if (i other.digits.size()) diff - other.digits[i]; if (diff 0) { diff this-base; borrow 1; } else { borrow 0; } res.push_back(diff); } // 移除可能产生的高位 0如 100-991结果为 {1,0,0} → {1} BigNum result(, this-base); result.digits res; result.removeLeadingZeros(); return result; }注意compare(other)是一个辅助方法比较两数大小按位从高位比即digits.size()大者大相等则从digits.back()往前比。这是减法安全的前提。3.3 大数乘法O(n²) 模拟竖式二维累加是关键乘法不能用add循环调用太慢必须模拟手算竖式a * b等价于对b的每一位b[j]计算a * b[j] * (base^j)再累加。核心是result[ij] a[i] * b[j]然后统一处理进位。BigNum BigNum::multiply(const BigNum other) const { if (this-base ! other.base) throw invalid_argument(Base mismatch in multiplication); vectorint res(this-digits.size() other.digits.size(), 0); // 竖式乘法a[i] * b[j] 贡献到 res[ij] for (int i 0; i this-digits.size(); i) { for (int j 0; j other.digits.size(); j) { res[i j] this-digits[i] * other.digits[j]; } } // 统一处理进位 int carry 0; for (int i 0; i res.size(); i) { int total res[i] carry; res[i] total % this-base; carry total / this-base; } // 移除前导零 BigNum result(, this-base); result.digits res; result.removeLeadingZeros(); return result; }为什么是ij因为a[i]是a的第i位权重base^ib[j]是b的第j位权重base^j乘积权重为base^(ij)自然落在res[ij]。3.4 大数除法试商法Long Division的代码落地不是递归也不是减法循环除法最复杂。常见错误是用被除数反复减去除数效率 O(n×quotient)quotient 大时爆炸。正确做法是试商法从被除数高位开始每次取足够位数构成临时被除数temp用temp / divisor估算商的一位guess再用guess * divisor验证并修正最后更新余数。这里给出简化版假设divisor位数远小于dividend用vector截取片段BigNum BigNum::divide(const BigNum other) const { if (other.isZero()) throw runtime_error(Division by zero); if (this-compare(other) 0) return BigNum(0, this-base); // 商为 0 vectorint quotient; vectorint remainder; // 当前余数初始为空 int n this-digits.size(); int m other.digits.size(); // 从被除数最高位开始扫描注意digits 是低位在前所以最高位是 digits[n-1] // 我们需从高位往低位处理故需反向遍历 digits for (int i n - 1; i 0; i--) { // 将当前位 digits[i] 压入余数前端模拟长除法中“落一位” remainder.insert(remainder.begin(), this-digits[i]); removeLeadingZerosInVector(remainder); // 清除前导 0 // 如果 remainder other商位补 0继续下一位 if (compareVectors(remainder, other.digits) 0) { quotient.push_back(0); continue; } // 否则试商用 remainder 的最高位估算商粗略再校验 int guess min(this-base - 1, (remainder.size() 0 ? remainder[0] : 0) / (other.digits.size() 0 ? other.digits.back() : 1) 1); // 实际中需更严谨的 guess此处为教学简化生产环境用牛顿迭代或查表 // 校验 guess计算 guess * other与 remainder 比较 BigNum guessProd other.multiply(BigNum(to_string(guess), this-base)); while (compareVectors(guessProd.digits, remainder) 0) { guess--; guessProd other.multiply(BigNum(to_string(guess), this-base)); } quotient.push_back(guess); // 更新余数remainder remainder - guessProd BigNum newRem BigNum(, this-base); newRem.digits remainder; BigNum subRes newRem.subtract(guessProd); remainder subRes.digits; } // quotient 是高位在前需反转为低位在前以匹配内部表示 reverse(quotient.begin(), quotient.end()); BigNum result(, this-base); result.digits quotient; result.removeLeadingZeros(); return result; }注意此为教学简化版。实际课程设计中若时间紧张可接受 O(n×m) 的减法循环除法对小规模数据足够但必须理解试商法才是工业级方案。4. 乘方与取模快速幂 模乘优化避免中间结果爆炸4.1 大数乘方必须用快速幂否则pow(123, 1000)直接栈溢出朴素for循环乘 1000 次时间 O(exp)且中间结果巨大123^1000有上千位内存爆炸。快速幂Exponentiation by Squaring将时间降至 O(log exp)且每步都可取模控制数值规模。BigNum BigNum::pow(int exp) const { if (exp 0) throw invalid_argument(Negative exponent not supported); if (exp 0) return BigNum(1, this-base); BigNum base *this; BigNum result(1, this-base); while (exp 0) { if (exp 1) { // exp 为奇数 result result.multiply(base); } base base.multiply(base); // 平方 exp 1; // exp / 2 } return result; }逻辑说明利用a^b (a^(b/2))^2b 偶或a * a^(b-1)b 奇。exp 1判断奇偶exp 1等价于exp / 2位运算更快。4.2 大数取模(a * b) % m ((a % m) * (b % m)) % m模乘是关键直接算a % ba极大不可行。应使用模重复平方法Modular Exponentiation将乘方与取模融合BigNum BigNum::mod(const BigNum modulus) const { // 简化本设计中 mod 是另一个 BigNum实现 a % m // 实际用法常为 pow(a, b) % m故提供专用方法 return this-modHelper(modulus); } // 专用模幂(base^exp) % modulus BigNum BigNum::modPow(const BigNum base, int exp, const BigNum modulus) { if (modulus.isZero()) throw runtime_error(Modulus cannot be zero); BigNum result(1, modulus.base); BigNum b base.mod(modulus); // 先取模缩小底数 BigNum m modulus; while (exp 0) { if (exp 1) { result result.multiply(b).mod(m); // 每步都模防爆炸 } b b.multiply(b).mod(m); exp 1; } return result; }为什么每步都.mod(m)因为multiply()结果可能极大.mod(m)将其压缩回 m的范围内保证后续乘法不会溢出内存。这是密码学中 RSA 的核心技巧。5. 避坑指南6 个让 90% 同学在答辩前夜崩溃的边界问题与血泪解法5.1 现象加法结果多出一个 0如123 0 0123原因removeLeadingZeros()方法未处理digits为空的情况。当输入0时strToBigNum(0)生成{0}removeLeadingZeros()若逻辑是while (digits.size()1 digits.back()0) digits.pop_back()则digits.back()是0但size()1循环不执行保留{0}。但若后续运算如0*anything产生{0,0}清除后只剩{0}没问题。真正翻车点在00时加法循环中i0计算0000res{0}removeLeadingZeros()若错误地清空了res当res全 0 时应至少留一个 0就会得到空 vectortoString()报错。解决removeLeadingZeros()必须确保digits至少有一个元素void BigNum::removeLeadingZeros() { while (digits.size() 1 digits.back() 0) { digits.pop_back(); } // 特殊处理全零情况保留一个 0 if (digits.empty()) digits.push_back(0); }5.2 现象二进制1000 - 1得到111正确但1000 - 111得到乱码原因减法中compare()方法未正确处理二进制数的位数比较。compare()通常先比digits.size()相等再比高位值。但digits是低位在前digits.back()才是最高位若compare()错误地从digits[0]最低位开始比结果必然错。解决compare()必须从digits.size()-1往0遍历即从最高位往最低位int BigNum::compare(const BigNum other) const { if (this-digits.size() ! other.digits.size()) { return this-digits.size() - other.digits.size(); // 长者大 } // 位数相同从最高位digits.back()开始比 for (int i this-digits.size() - 1; i 0; i--) { if (this-digits[i] ! other.digits[i]) { return this-digits[i] - other.digits[i]; } } return 0; }5.3 现象12345678901234567890 * 98765432109876543210运行超时或内存耗尽原因乘法中res初始化为a.size() b.size()是正确的但若a和b都是 20 位res分配 40 个int没问题。真正问题是内层循环for (int j...)中res[ij]可能越界ij最大为a.size()-1 b.size()-1 38res大小 40安全。但若res初始化为a.size() b.size() - 1就会越界。更隐蔽的坑是res[ij] ...中可能导致res[ij]值极大如9*981再加进位可能超int虽int足够存单次乘积但累加后可能超INT_MAX21亿引发未定义行为。解决在累加循环后、进位循环前不依赖int容量用进位逻辑消化所有超限值// 累加后res[i] 可能很大但进位循环会将其规整 for (int i 0; i res.size(); i) { int total res[i] carry; res[i] total % this-base; carry total / this-base; } // carry 可能仍非零需继续 push while (carry) { res.push_back(carry % this-base); carry / this-base; }5.4 现象1010 (bin) 11 (bin)输出1101正确但toString()输出1011反了原因toString()方法未将digits低位在前反转回高位在前。digits {0,1,0,1}应输出1010但若直接for (int d : digits) s (0d)得到0101。解决toString()必须逆序遍历string BigNum::toString() const { if (digits.empty()) return 0; string s; // 从最高位digits.back()到最低位digits[0] for (int i digits.size() - 1; i 0; i--) { s (0 digits[i]); } return s; }5.5 现象pow(2, 100)结果正确但pow(2, 1000)程序崩溃原因快速幂中base base.multiply(base)产生巨大中间数虽multiply()本身无 bug但vectorint存储上千位每次multiply()分配新 vector旧 vector 待 GCC 中需手动clear若未及时释放内存泄漏。更可能是栈溢出递归版快速幂本设计用迭代安全或toString()中string拼接频繁触发重分配。解决迭代版快速幂已规避递归栈toString()改用reserve()预分配s.reserve(digits.size());关键所有multiply()返回的BigNum应是局部对象由 RAII 自动析构无需手动干预。6. 进阶验证与性能技巧用测试用例覆盖边界用位运算加速二进制特化6.1 构建黄金测试集5 类必测 case覆盖所有翻车点不要只测123456。课程设计验收时老师最爱问“你测过0吗测过全9吗测过位数悬殊吗” 下表是经过某高校课程设计答辩验证的最小黄金集测试类型十进制示例二进制示例验证目标全零与单零00,0*12300,0*1010removeLeadingZeros()是否健壮进位临界9991,5005001111,100100进位链是否完整9991→1000借位临界1000-1,1000-9991000-1,1000-111借位传递是否穿透1000-1999位数悬殊199999999999999999999111111111111111111111maxLen和i size()边界是否准确模幂安全modPow(2, 10, 1000)modPow(10, 5, 1111)每步.mod()是否生效结果是否 modulus提示把上表写成test.cpp每个 case 调用assert(result.toString() expected)。答辩时当场编译运行比讲原理更有说服力。6.2 二进制特化加速用/替代通用base运算当base2时所有% 2和/ 2可替换为位运算快一个数量级digit % 2→digit 1digit / 2→digit 1carry sum / 2→carry sum 1sum % 2→sum 1在add()、multiply()等方法中加入if (base 2)分支调用特化版本。这不仅是优化更是展示你理解了“数据结构服务于场景”的工程思维。6.3 一个真实血泪经验永远先写removeLeadingZeros()再写任何运算我带过的某实验室项目X三个组员花两天调试乘法最终发现是subtract()返回了{0,0,0}而divide()的compare()拿这个去比因digits.size()3被误判为大数。根源是subtract()没调removeLeadingZeros()。从此我养成了铁律每个运算函数的最后一行必是result.removeLeadingZeros()。哪怕多调一次也比在凌晨三点对着gdb看digits {0,0,0,0}发呆强。希望帮到你。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
