大数运算课程设计：用字符串模拟锤炼数据结构内功

简介本资源是面向计算机专业本科生的数据结构课程设计实践项目聚焦大数运算这一经典难点问题完整实现十进制与二进制双模式下的加、减、乘、除、乘方及取模六大核心运算适用于算法课设、密码学基础实践与高性能计算入门学习。压缩包共35个文件含5个Python脚本含testadd.py等6组验证用例、4个data测试数据集、2个C源文件BigInteger.cpp/h及对应编译产物.o/.exe另有Makefile.win和Project1.dev工程配置结构清晰支持跨平台验证与对比分析。目前已有1352人学习下载。读者可直接运行C/Python双版本代码通过inA.txt、resPowC.txt等配套输入输出文件观察运算过程掌握数组模拟进位/借位、快速幂优化、二进制位运算转换等关键实现细节并复现从底层数据结构设计到多进制兼容的完整工程逻辑。1. 大数运算课程设计为什么用字符串模拟比依赖 BigInteger 更能锤炼数据结构内功你在写「大数加法」时是不是第一反应就去查java.math.BigInteger或 Python 的int自动扩容——这恰恰是本课程设计最想破的幻觉。这不是一道“怎么算得快”的工程题而是一道“怎么把加减乘除拆解成链表/数组/栈的遍历、进位、借位、对齐、符号管理”的数据结构压测题。它强制你回到纸笔时代两个百位十进制数相加手写竖式时每一步在做什么进位怎么暂存被减数不够减时怎么向前借二进制乘法里左移等价于什么操作除法试商为什么不能暴力枚举这些动作一旦映射到线性表的索引跳转、双向链表的节点插入、栈的后进先出弹出顺序上你就不是在调 API而是在亲手组装一台微型计算引擎。适合刚学完链表、栈、队列、数组动态扩容但还没碰过高级语言内置大数类的同学也适合想验证自己是否真懂「抽象数据类型」和「物理存储实现」之间那层薄纸的同学。别急着跑通结果先让每一步进位都落在你亲手维护的carry变量里让每一次借位都触发你写的borrowFromNext()函数——这才是课程设计要钉住的肌肉记忆。2. 从零构建大数核心容器为什么选字符串而非数组如何统一十进制与二进制表示2.1 字符串表示法的不可替代性避免前置零污染与符号分离难题很多同学一上来就定义int[] digits存各位数字很快撞墙正负号怎么存塞进digits[0]当标志位那digits[0] -1和digits[0] 1就和数值本身混了前置零怎么处理00123存成[0,0,1,2,3]后续所有运算都要先trim()但trim()本身就要遍历找第一个非零位——这不又回到了字符串的逻辑二进制1010和十进制1010看似一样但语义完全不同前者是十进制的10后者是1010。用int[]无法天然区分进制上下文。正确做法用字符串存原始数字字符另设boolean isNegative和int base10 或 2。public class BigInt { private String digits; // 12345 或 101010无符号、无前置零除全零情况 private boolean isNegative; // true 表示负数 private int base; // 进制10 或 2 public BigInt(String digitStr, int base) { if (base ! 10 base ! 2) throw new IllegalArgumentException(Base must be 10 or 2); this.base base; this.isNegative digitStr.startsWith(-); this.digits isNegative ? digitStr.substring(1) : digitStr; // 关键清理去除前置零但保留0 this.digits this.digits.replaceFirst(^0(?!$), ); if (this.digits.isEmpty()) this.digits 0; } }提示replaceFirst(^0(?!$), )是 Java 字符串去前置零的可靠写法(?!)是负向先行断言确保不把0变成空字符串。这是你第一次真正用正则解决数据结构里的边界问题。2.2 统一进制处理base 决定所有运算规则而非硬编码 10所有运算函数加、减、乘…内部不再写死10而是用this.base加法进位阈值是base十进制是 10二进制是 2乘法中digit * multiplier的进位计算是sum / base除法试商时比较currentRemainder和divisor * trialDigit要用compareInBase()而非直接转int否则二进制11111111会溢出。这意味着你写的add()函数传入new BigInt(101, 2)和new BigInt(110, 2)自动按二进制算出1011传入new BigInt(999, 10)和new BigInt(1, 10)自动进位为1000。进制不是输入格式而是运算契约——这个认知转折点是本设计最硬的思维门槛。2.3 构造器健壮性支持任意进制字面量解析与标准化用户可能输入0xFF十六进制、0b1010二进制前缀但题目只要求十进制和二进制。所以构造器需做两件事识别并剥离前缀0b1010→10100B1010→10100d123→123十进制显式前缀校验字符合法性二进制只允许0,1十进制只允许0-9。private static String parseAndValidate(String input, int targetBase) { String clean input.trim(); // 剥离前缀 if (clean.toLowerCase().startsWith(0b) targetBase 2) { clean clean.substring(2); } else if (clean.toLowerCase().startsWith(0d) targetBase 10) { clean clean.substring(2); } // 校验字符 String validChars (targetBase 2) ? 01 : 0123456789; for (char c : clean.toCharArray()) { if (validChars.indexOf(c) -1) { throw new IllegalArgumentException( String.format(Invalid digit %c for base %d, c, targetBase) ); } } return clean; }参数说明targetBase是构造时指定的进制parseAndValidate不负责转换进制只做清洗和校验。这是防御性编程的第一课永远假设输入是恶意的。3. 四则运算核心实现加减法靠对齐进位/借位乘除法靠模拟手算过程3.1 大数加法从低位到高位的手算模拟进位变量是灵魂加法本质是「对齐末尾逐位相加进位暂存高位补零」。难点不在逻辑而在对齐策略12345不能直接i从 0 开始遍历必须让45左边补零变成045或更优双指针从字符串末尾反向遍历。public BigInt add(BigInt other) { if (this.base ! other.base) throw new IllegalArgumentException(Base mismatch); // 符号相同绝对值相加符号不变符号不同转为减法见3.2 if (this.isNegative other.isNegative) { String resultDigits addAbsolute(this.digits, other.digits); return new BigInt( (this.isNegative ? - : ) resultDigits, this.base ); } else { return subtractAbsolute(other, this); // |a| - |b|符号取绝对值大的 } } private String addAbsolute(String a, String b) { StringBuilder sb new StringBuilder(); int i a.length() - 1, j b.length() - 1; int carry 0; while (i 0 || j 0 || carry 0) { int digitA (i 0) ? charToDigit(a.charAt(i--)) : 0; int digitB (j 0) ? charToDigit(b.charAt(j--)) : 0; int sum digitA digitB carry; sb.append(digitToChar(sum % base)); // 当前位结果 carry sum / base; // 进位给下一位 } return sb.reverse().toString(); // 因为从低位算起结果是逆序的 }关键逻辑说明charToDigit(char c)将0-9或0,1转为0-9或0-1digitToChar(int d)反向转换carry是唯一状态变量它承载了整个加法的「时序性」——没有它你就无法把第i位的进位传递给i1位sb.reverse()是必须的因为手算时我们先写个位再写十位字符串拼接是反的。3.2 大数减法借位比进位更危险必须处理「不够借」的退位链减法比加法难在借位是「传染性」的1000 - 1中个位0-1不够向十位借十位是0再向百位借百位也是0最终千位1变0百位得10再分1给十位…… 这就是退位链borrow chain。private String subtractAbsolute(String a, String b) { // 确保 a b数值上否则交换并标记结果为负 if (compareAbsolute(a, b) 0) { String swapped subtractAbsolute(b, a); // 注意此处返回的是正数字符串调用方负责加负号 return swapped; } StringBuilder sb new StringBuilder(); int i a.length() - 1, j b.length() - 1; int borrow 0; while (i 0) { int digitA charToDigit(a.charAt(i--)); int digitB (j 0) ? charToDigit(b.charAt(j--)) : 0; int diff digitA - borrow - digitB; if (diff 0) { diff base; // 借1当base borrow 1; // 向高位借1 } else { borrow 0; // 本次没借 } sb.append(digitToChar(diff)); } // 去除结果前置零但保留0 String result sb.reverse().toString().replaceFirst(^0(?!$), ); return result.isEmpty() ? 0 : result; }血泪经验borrow必须初始化为0且每次循环结束前必须重置。曾有同学写成if (diff 0) { borrow 1; } else { borrow 0; }看似合理但若连续两次diff 0第二次borrow会被错误覆盖为0导致计算崩坏。借位是状态机不是布尔开关。3.3 大数乘法O(n²) 手算模拟二维中间结果数组是理解关键乘法不能简单套用加法多次相加效率太低必须模拟「竖式乘法」123 × 45→ 先算123×5615再算123×4492然后492左移一位即补零得4920最后61549205535。核心洞察第i位从右数0-indexed乘第j位结果落在ij位上。例如a[1]×b[2]十位×百位影响万位123即 10³ 位。private String multiplyAbsolute(String a, String b) { int[] result new int[a.length() b.length()]; // 最多 len(a)len(b) 位 for (int i a.length() - 1; i 0; i--) { for (int j b.length() - 1; j 0; j--) { int digitA charToDigit(a.charAt(i)); int digitB charToDigit(b.charAt(j)); int product digitA * digitB; int pos1 i j; // 高位位置 int pos2 i j 1; // 低位位置个位 int sum product result[pos2]; result[pos2] sum % base; result[pos1] sum / base; // 进位累加到高位 } } // 转字符串跳过前置零 StringBuilder sb new StringBuilder(); boolean leadingZero true; for (int digit : result) { if (leadingZero digit 0) continue; leadingZero false; sb.append(digitToChar(digit)); } return sb.length() 0 ? 0 : sb.toString(); }参数说明result数组长度a.length()b.length()是数学保证n 位数 × m 位数 ≤ nm 位。pos1和pos2的定位是手算乘法映射到数组索引的灵魂。3.4 大数除法试商法的三重嵌套while 循环里藏着最深的坑除法是最易翻车的模块。12345 ÷ 67手算步骤取被除数前两位1267取前三位123≥67试商123 ÷ 67 ≈ 11×6767123-6756拉下一位4得564再试商564÷67≈88×67536564-53628拉下5得285285÷67≈44×67268余17。代码落地难点如何高效「取前 k 位」用substring(0, k)但要注意k不能超长试商不能for (int q 1; q base; q)—— 二进制q只有0,1但十进制q可能到9而12345 ÷ 1的商是12345远超base所以试商必须用二分查找或牛顿迭代但课程设计要求手算故采用从 1 开始递增试探但上限设为min(base, currentDividend/baseOfDivisor)最关键每次减法后必须重新 normalize 当前余数去除前置零否则00123会被误判为123位数导致拉位错误。private BigInt[] divideAbsolute(String dividend, String divisor) { if (divisor.equals(0)) throw new ArithmeticException(Division by zero); if (dividend.equals(0)) return new BigInt[]{new BigInt(0, base), new BigInt(0, base)}; StringBuilder quotient new StringBuilder(); String current ; int idx 0; while (idx dividend.length()) { current dividend.charAt(idx); // 去除 current 前置零重要 current current.replaceFirst(^0(?!$), ); if (current.isEmpty()) current 0; // 如果 current divisor商位补0继续拉下一位 if (compareAbsolute(current, divisor) 0) { quotient.append(0); continue; } // 试商从1开始找最大 q 使得 q*divisor current int q 1; String qTimesDivisor multiplyAbsolute(divisor, String.valueOf(q)); while (compareAbsolute(qTimesDivisor, current) 0) { q; qTimesDivisor multiplyAbsolute(divisor, String.valueOf(q)); } q--; // 回退到最大合法 q quotient.append(digitToChar(q)); // 计算 current - q*divisor String product multiplyAbsolute(divisor, String.valueOf(q)); current subtractAbsolute(current, product); // 再次 normalize current current current.replaceFirst(^0(?!$), ); if (current.isEmpty()) current 0; } String qStr quotient.toString().replaceFirst(^0(?!$), ); qStr qStr.isEmpty() ? 0 : qStr; return new BigInt[]{ new BigInt(qStr, base), new BigInt(current, base) }; }注意compareAbsolute()是你必须独立实现的字符串数值比较函数不能转long会溢出必须按位比较长度和字典序。这是除法能跑通的基石。4. 高阶运算与进制桥接乘方用快速幂取模用同余优化二进制与十进制互转是刚需4.1 大数乘方不用 for 循环连乘用快速幂把 O(n) 降到 O(log n)a^b若用for (int i0; ib; i) result multiply(result, a)当b是百位数时要执行上百次大数乘法秒变龟速。快速幂Exponentiation by Squaring是必选项若b是偶数a^b (a^(b/2))^2若b是奇数a^b a × a^(b-1)。public BigInt pow(int exp) { if (exp 0) throw new IllegalArgumentException(Negative exponent not supported); if (exp 0) return new BigInt(1, this.base); BigInt base new BigInt(this.digits, this.base); base.isNegative this.isNegative (exp % 2 1); // 奇次幂保留符号 BigInt result new BigInt(1, this.base); BigInt current base; while (exp 0) { if (exp % 2 1) { result result.multiply(current); } current current.multiply(current); exp / 2; } return result; }玄学细节exp是int不是BigInt因为指数通常不会大到需要大数表示10^1000的指数1000完全在int范围内。这是对问题域的合理剪枝。4.2 大数取模利用(a × b) mod m ((a mod m) × (b mod m)) mod m避免中间值爆炸直接算a^b再% m会生成天文数字。正确姿势是边乘边模public BigInt mod(BigInt m) { // 实现 (this % m) 用除法的余数 BigInt[] divResult this.divide(m); return divResult[1]; // 余数 } // 但 powMod 需要专用函数 public BigInt powMod(int exp, BigInt m) { if (m.digits.equals(0)) throw new ArithmeticException(Mod by zero); BigInt result new BigInt(1, this.base); BigInt base this.mod(m); BigInt current base; while (exp 0) { if (exp % 2 1) { result result.multiply(current).mod(m); } current current.multiply(current).mod(m); exp / 2; } return result; }为什么有效模运算是同态的(a*b)%m ((a%m)*(b%m))%m。这让你能把10^100 % 13这种题在不生成10^100的前提下算出结果。4.3 十进制 ↔ 二进制互转不是 toString(2)而是手写除2取余与乘2取整题目要求「同时支持十进制和二进制」意味着用户可输入1010二进制并期望得到十进制10或输入255十进制得到11111111二进制。这不能靠Integer.parseInt(s, base)必须手写转换算法十进制字符串 → 二进制字符串除2取余法public String toBinaryString() { if (this.base 2) return this.digits; // 已是二进制 String dec this.digits; StringBuilder binary new StringBuilder(); while (!dec.equals(0)) { BigInt[] div new BigInt(dec, 10).divide(new BigInt(2, 10)); binary.append(div[1].digits); // 余数是0或1 dec div[0].digits; // 商作为下一轮被除数 } return binary.reverse().toString(); }二进制字符串 → 十进制字符串按权展开法public String toDecimalString() { if (this.base 10) return this.digits; String bin this.digits; String result 0; for (int i 0; i bin.length(); i) { char bit bin.charAt(i); result multiplyAbsolute(result, 2); // result * 2 if (bit 1) { result addAbsolute(result, 1); // result 1 } } return result; }踩坑预警toBinaryString()中div[1].digits可能是0或1但绝不会是2因为除以2的余数只能是0或1。这是你验证除法正确性的黄金测试点。5. 避坑指南那些让调试到凌晨三点的「幽灵 Bug」5.1 现象加法结果多一个前置零如12345得0168原因addAbsolute()中sb.append(digitToChar(sum % base))后sb.reverse()前未检查sb是否为空且carry在循环结束后未处理。当carry 0时它代表最高位进位必须追加。但你的代码在while (i0 || j0 || carry0)条件下已包含carry所以问题出在reverse()后的replaceFirst0168.replaceFirst(^0(?!$), )会把0168变168但若结果是000replaceFirst会变空字符串导致返回后续isEmpty()判断失效。解决在addAbsolute()结尾加兜底String raw sb.reverse().toString(); raw raw.replaceFirst(^0(?!$), ); return raw.isEmpty() ? 0 : raw;5.2 现象二进制减法100-11返回1正确应为1但10-1却返回0原因subtractAbsolute()中compareAbsolute(a,b)函数未正确处理等长字符串的字典序比较。10和1长度不同10更大但10和01长度相同10字典序大于01数值也大。而10和1比较时若先比长度10.length()2 1.length()1正确但若a010非法输入但parseAndValidate应已过滤010.length()3就会误判。解决compareAbsolute()必须先比长度长度相等时再按字典序比较private int compareAbsolute(String a, String b) { if (a.length() ! b.length()) { return Integer.compare(a.length(), b.length()); } return a.compareTo(b); // 字典序即数值序因无前置零 }5.3 现象乘法999 × 999返回998001正确但1000 × 1000返回1000000正确而0 × 123返回空字符串原因multiplyAbsolute()中result数组初始化为int[a.length()b.length()]当a0时a.length()1b123时b.length()3result长度为4但for循环中i,j从0开始product0result[pos2]始终为0最终sb为空。解决在multiplyAbsolute()开头加特判if (a.equals(0) || b.equals(0)) return 0;5.4 现象除法100 ÷ 3商为33余数1但100 ÷ 10商为10余数0而10 ÷ 10商为0应为1原因divideAbsolute()中quotient.append(0)的逻辑在current divisor时无条件执行但当current刚好等于0时如被除数开头是00 10成立商补0但后续idx增加current变成0x仍小于10继续补0最终商全是0。解决在while (idx dividend.length())循环内current初始化为首次current dividend.charAt(idx)后立即normalize且quotient.append(0)前加判断if (!current.equals(0) || idx dividend.length()) { quotient.append(0); }更稳妥的是商字符串只在确定有非零位时才 append否则保持空最后统一处理。5.5 现象pow(0)返回1但pow(1)返回原数pow(2)却抛NullPointerException原因pow()函数中current base但base是new BigInt(this.digits, this.base)其isNegative未赋值默认false而原this.isNegative是true导致符号丢失更致命的是multiply()内部调用addAbsolute()时若this.digits是空字符串charToDigit会charAt(0)抛异常。解决pow()开头加if (this.digits.equals(0) exp 0) return new BigInt(0, this.base);并确保所有构造器对空字符串有防御。6. 验证与压测用已知数学结论反推让测试成为你的「后悔药」6.1 构建四层验证体系单元测试、边界测试、交叉验证、压力测试不要只写main()里几个println。真正的验证是系统性的验证层级测试目标典型用例为什么有效单元测试每个私有方法独立正确addAbsolute(999,1)1000隔离逻辑快速定位addAbsolute问题边界测试极端输入下的鲁棒性0,1,0000,1000000000000暴露normalize和length()判断漏洞交叉验证与可信源结果比对new BigInt(255,10).toBinaryString()11111111用数学常识2552⁸−1验证转换压力测试大规模数据性能与内存pow(1000)计算2^1000触发StringBuilder扩容、GC、算法复杂度瓶颈实操建议用 JUnit 写Test方法每个测试只验证一件事。例如Test public void testAddZero() { BigInt a new BigInt(123, 10); BigInt b new BigInt(0, 10); assertEquals(123, a.add(b).digits); }6.2 利用数学恒等式自检你的代码必须满足(ab)-b a这是最强大的黑盒验证法。随机生成 100 对大数a,b断言assertTrue(a.add(b).subtract(b).equals(a)); assertTrue(a.multiply(b).divide(b)[0].equals(a)); // 忽略余数 assertTrue(a.pow(2).equals(a.multiply(a)));注意equals()必须重写比较digits,isNegative,base三者。若这些恒等式失败说明你的加减乘除中至少有一个存在系统性偏差——不是某个 case 错而是算法骨架歪了。6.3 二进制专项验证用位运算性质卡死逻辑二进制运算有独特守恒律是绝佳的「照妖镜」a 1左移1位必须等于a.multiply(new BigInt(2,2))a (-a)提取最低位1在二进制下应返回1,10,100等纯 2 的幂a | b按位或虽未要求实现但a.add(b)在无进位时应等于a | b例如101 010 111。写一个testBinaryShift()Test public void testBinaryShift() { BigInt a new BigInt(1010, 2); // 10 BigInt shifted a.multiply(new BigInt(10, 2)); // ×2 assertEquals(10100, shifted.digits); // 20, 即 1010 1 }6.4 性能陷阱排查当pow(1000)卡住先看multiply()的result数组是否过大multiplyAbsolute()中int[] result new int[a.length()b.length()]是安全的但若a和b都是 1000 位result数组长 2000没问题但若multiply()被pow()调用 log₂(1000)≈10 次每次生成新数组GC 压力不大。真正慢的是addAbsolute()中StringBuilder的reverse()和replaceFirst()—— 它们是 O(n)。优化点addAbsolute()中不用StringBuilder改用char[]预分配char[] res new char[Math.max(a.length(), b.length()) 1]; int idx res.length - 1; // ... 计算后new String(res, start, len)但这属于锦上添花。课程设计阶段先让逻辑 100% 正确再谈优化。我当年在某高校课程设计答辩时导师盯着我pow(50)的输出看了 30 秒然后说“2^50是1125899906842624你输出的最后 4 位是624对了。” —— 那一刻我知道所有熬夜 debug 的carry和borrow都没白费。希望帮到你。本文还有配套的精品资源点击获取