簡介一份用于數(shù)據(jù)結(jié)構(gòu)課程設計的大數(shù)運算完整工程面向高校學生、算法初學者以及需要完成同類課題的開發(fā)者。資源以 C 實現(xiàn)為主同時支持十進制與二進制大數(shù)的加法、減法、乘法、除法、乘方、取模六類運算包含快速冪、長除法、逐位進位與借位等典型算法思路可直接作為課設源碼、算法學習素材或二次開發(fā)基礎。包體共 35 個文件壓縮包大小 22.24MB主要包含 C 源文件與頭文件、Python 驗證腳本、txt 輸入輸出樣例、data 數(shù)據(jù)文件以及可執(zhí)行程序從核心算法到測試驗證形成完整鏈條目前已有 1351 人學習下載適合數(shù)據(jù)結(jié)構(gòu)課程設計、期末項目及算法進階練習。通過閱讀源碼可以理解大數(shù)在數(shù)組/字符串存儲下的逐位運算、商與余數(shù)的迭代生成、快速冪減少乘法次數(shù)等關鍵實現(xiàn)配套的多種測試數(shù)據(jù)與 Python 對照結(jié)果便于自查正確性并生成實驗報告。工程內(nèi)模塊劃分清晰按運算類型即可快速定位對應代碼實用性較強。1. 大數(shù)運算課程設計先想清楚“大”在哪再寫第一行代碼大數(shù)運算課程設計是數(shù)據(jù)結(jié)構(gòu)課里最容易被低估的一道題題目就六個大字“大數(shù)加法大數(shù)減法”可真上手就會發(fā)現(xiàn)int 連 21 億都裝不下隨便喂一個 30 位的輸入數(shù)組、鏈表、進位借位這些基礎結(jié)構(gòu)立刻被逼出原形。我見過太多人把六個運算寫成六個互相獨立的字符串處理函數(shù)代碼跑通了卻講不清每條復雜度答辯一追問就翻車。這份資源把減法先比較大小、乘法先乘后進位、除法按位試商、乘方用二進制擴展法、取模直接復用除法結(jié)果以及十進制和二進制兩種輸入的解析封裝串在了一條完整的鏈路上適合期末課程設計、數(shù)據(jù)結(jié)構(gòu)與算法自測也想用一道題把線性表玩透的 408 考研黨。2. 大數(shù)存儲與加減法數(shù)組逆序存放是實現(xiàn)高精度的第一課2.1 存儲設計為什么逆序存低位、為什么不用鏈表大數(shù)運算的第一步不是寫加法而是決定“一個超長整數(shù)在內(nèi)存里長什么樣”。最經(jīng)典的做法是用 int 數(shù)組每個元素存一位十進制數(shù)字下標 0 存?zhèn)€位下標 1 存十位依此類推。這么做的理由很實在加法進位是從低位往高位傳播的逆序存儲后進位方向正好和數(shù)組下標增長方向一致循環(huán)寫起來就是正向遍歷不需要從尾巴往頭倒著摸。鏈表也能做嚴蔚敏《數(shù)據(jù)結(jié)構(gòu)C 語言版》里不少習題也鼓勵用鏈表表達多項式和大整數(shù)。但我的建議是課程設計如果沒有額外要求優(yōu)先用定長數(shù)組。原因是鏈表每個節(jié)點額外帶一個 next 指針內(nèi)存不連續(xù)遍歷時 cache 命中率差而且大數(shù)運算的瓶頸在進位和借位的連續(xù)掃描數(shù)組的隨機訪問比鏈表快得多。鏈表更適合展示“插入刪除”的場景大數(shù)運算這種高頻遍歷場景數(shù)組天然更合適。#define MAX_DIGITS 1024 typedef struct { int digits[MAX_DIGITS]; // 下標0存?zhèn)€位digits[i] 取值范圍 0~9 int len; // 當前有效位數(shù)digits[0]~digits[len-1] int sign; // 1 表示正-1 表示負0 表示數(shù)值為 0 } BigInt;說明MAX_DIGITS設成 1024 意味著最大支持 1024 位十進制數(shù)課程設計夠用如果題目要求 10000 位直接改宏即可。len是有效長度比如數(shù)字 100 存下來是 digits[0]0、digits[1]0、digits[2]1len3。sign單獨存符號避免把負號揉進數(shù)字位里后面做減法比較時省很多事。這里每個元素只存一位十進制是“一位一存”的樸素方案代碼最好懂、進位最好寫缺點是空間利用率低真正追求性能的版本會每個元素存 9 位也就是“萬進制”這個放到最后一章說。2.2 大數(shù)加法進位傳播與結(jié)果長度修正加法是最不需要思考的運算但也是第一個容易出細節(jié)問題的地方。兩個數(shù)相加每一位上最多出現(xiàn)99119所以進位 carry 只可能是 0 或 1。很多初版代碼喜歡在每一位算完立刻把 carry 寫進下一位這沒問題但要注意循環(huán)結(jié)束后如果還有 carry結(jié)果長度必須加一否則 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; } }邏輯說明循環(huán)從低位到高位逐位累加短的那個數(shù)下標越界后自動補 0這樣 123 45678 也能正確算出 45801。sum % 10留下當前位sum / 10作為進位傳給下一位。參數(shù)說明a、b是輸入res是輸出允許res和a指向同一個變量函數(shù)內(nèi)部逐位寫入不會讀到臟數(shù)據(jù)。唯一要注意的是函數(shù)調(diào)用前最好把res-len清 0避免舊數(shù)據(jù)殘留。這個實現(xiàn)的時間復雜度是 O(n)n 是較長的那個數(shù)的位數(shù)和手算加法完全一致。2.3 大數(shù)減法先比較再相減符號用 sign 字段兜底減法比加法麻煩一個量級麻煩不在借位而在“誰減誰”。如果直接拿小數(shù)減大數(shù)借位會借到天上去。正確的套路是先比較兩個數(shù)的絕對值大小保證大數(shù)在前、小數(shù)在后只算“大減小”再把符號記在 sign 字段里。這也是為什么我在結(jié)構(gòu)體里單獨留了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先比長度再比高位長度長的絕對值一定大長度相同就從最高位往低位逐位比。減法主循環(huán)里borrow表示上一位有沒有借位當前位不夠減就10并把borrow置 1。每次用a-len作為循環(huán)上限是因為我們保證a是較大的那個。參數(shù)說明兩個指針a、b的交換用的是指針交換不復制數(shù)組內(nèi)容效率高。注意這里只處理了“絕對值比較后大減小”如果輸入本身就帶符號比如負數(shù)減正數(shù)需要在調(diào)用層額外處理符號疊加課程設計通?？梢约s定輸入都是非負數(shù)或者在 main 里先統(tǒng)一轉(zhuǎn)成正數(shù)再調(diào)用。3. 大數(shù)乘法與除法豎式算法的兩個落地方向3.1 大數(shù)乘法先累加后進位避免每輪都處理進位大數(shù)乘法最直觀的寫法是模擬小學豎式a的第 i 位乘以b的第 j 位結(jié)果放在結(jié)果的第ij位。第一次寫的時候很容易寫成“每乘一位就立刻把進位加到下一位”這樣也能跑通但進位處理會和下一輪累加糾纏在一起代碼極易出錯。我常用的做法是分兩步第一步只做乘法和累加先讓tmp[ij]把該加的都加上第二步再統(tǒng)一處理進位。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 位數(shù)相乘最多 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 的結(jié)果應該是 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。第二步統(tǒng)一進位carry從低位往高位滾最終每個元素都變成 0~9。參數(shù)說明tmp數(shù)組長度取MAX_DIGITS*2是因為兩個 1024 位數(shù)相乘最多 2048 位定成兩倍最大長度能防越界如果實際位數(shù)更短循環(huán)也只遍歷到a-len b-len。時間復雜度是 O(n*m)n 和 m 是兩個數(shù)的位數(shù)這也是樸素乘法的理論下限之內(nèi)的常見實現(xiàn)如果追求更快可以上 Karatsuba但課程設計階段豎式足夠。3.2 大數(shù)除法按位試商二進制大數(shù)每商位只有 0/1除法是六個運算里最容易寫崩的。手算除法的本質(zhì)是從被除數(shù)最高位開始每次“取一部分不夠除就往后拼一位”夠除就試商。放到大數(shù)里就是維護一個余數(shù)累加器cur每次把cur整體乘 10相當于左移一位再拼上被除數(shù)的下一位然后看cur最多能減幾個除數(shù)這個次數(shù)就是商的當前位。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}; // 余數(shù)累加器 q-len a-len; for (int i a-len - 1; i 0; i--) { // 余數(shù)乘 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)是給余數(shù)乘一個一位數(shù) 10實現(xiàn)上就是從高位逆向進位或者直接手寫一個乘小數(shù)的函數(shù)addSmall同理給余數(shù)加上一位數(shù)字。內(nèi)層while每減一次除數(shù)商位加一理論上一位最多減 9 次所以整體復雜度約等于 O(n*m)n 是被除數(shù)位數(shù)m 是除數(shù)位數(shù)。參數(shù)說明q是商r是余數(shù)函數(shù)結(jié)束時r一定滿足0 r b。這里有個容易被忽略的點商的長度初始設成a-len因為被除數(shù)有幾位商的位數(shù)最多也就是幾位最后trimZero把高位 0 去掉比如 100/50 的商初始是“002”trim 后是“2”。這個結(jié)構(gòu)對二進制大數(shù)有個天然的好處如果內(nèi)部存的是二進制位那么試商時每商位只可能是 0 或 1內(nèi)層while可以直接退化成一次if判斷——cur夠大就減一次、商位置 1不夠大商位直接置 0。這也是為什么很多高精度代碼庫會把十進制和二進制兩條路徑分別實現(xiàn)二進制的除法性能要好得多。3.3 大數(shù)取模直接復用除法商留著不用也行取模運算單獨寫一份算法是典型的重復勞動。取模的定義就是“除法剩下的余數(shù)”所以最省事的做法是調(diào)一次除法把商丟掉把余數(shù)返回。代碼少而且正確性跟著除法走除法測過之后取模就不用單獨測了。void modBigInt(BigInt *a, BigInt *b, BigInt *res) { BigInt q; divBigInt(a, b, q, res); }邏輯說明這里直接讓divBigInt的r參數(shù)指向res商q是個局部變量運行完就被丟棄。要注意divBigInt內(nèi)部最后*r cur是結(jié)構(gòu)體整體賦值只要r不是和q指向同一塊內(nèi)存就不會互相干擾。參數(shù)說明如果后續(xù)要頻繁取模比如快速冪里的模乘建議把divBigInt的商參數(shù)傳一個臨時變量而不是每次都聲明新的 BigInt因為結(jié)構(gòu)體整體賦值也有一份內(nèi)存拷貝開銷。另外除數(shù)為 0 要在divBigInt入口做防御返回一個錯誤碼或者直接打印提示不然while會死循環(huán)。4. 大數(shù)乘方與進制轉(zhuǎn)換二進制擴展法把冪運算從線性降到對數(shù)4.1 快速冪原理把指數(shù)拆成二進制位逐位平方大數(shù)乘方最容易踩的性能坑是“老老實實乘 n 次”。如果算 a^1000樸素循環(huán)要做 1000 次大數(shù)乘法而大數(shù)乘法本身又是 O(m2)總開銷直接起飛。二進制擴展法也叫快速冪的核心思想是把指數(shù)看成二進制數(shù)比如 13 的二進制是 1101那么 a^13 a^8 × a^4 × a^1也就是只挑二進制位為 1 的那些“a 的 2^k 次方”乘起來。實現(xiàn)時從左到右或從右到左都行課程設計里最常見的寫法是從最低二進制位開始指數(shù)右移一位底數(shù)平方一次遇到當前位為 1 就把底數(shù)乘進結(jié)果。4.2 快速冪實現(xiàn)平方、乘底、指數(shù)右移三步循環(huán)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即底數(shù)平方 divSmall(e, 2, e); // e e / 2二進制右移一位 } }邏輯說明循環(huán)不變量是“b 始終等于 base 的 2^k 次方”。每輪先看指數(shù)當前最低位是 1 就把 b 乘進 res是 0 就不乘然后無條件把 b 平方同時指數(shù)除以 2。以 2^13 為例指數(shù)二進制 1101按低位到高位依次是 1、0、1、1res 依次乘上 2^1、2^4、2^8最終得到 2^13。參數(shù)說明e.digits[0] % 2能直接判斷整個大數(shù)的奇偶性是因為我們的存儲是十進制位個位數(shù)字的奇偶決定整個數(shù)的奇偶。divSmall(e, 2, e)是關鍵很多人在這里踩坑因為每個元素存的是十進制位不能直接e.digits[0] 1那樣會把十位的值錯誤地挪到個位。正確寫法是模擬一次“除以 2”的豎式從最高位到最低位逐位帶余數(shù)計算。4.3 十進制與二進制統(tǒng)一封裝輸入解析與輸出轉(zhuǎn)換題目要求同時支持十進制和二進制大數(shù)運算這里有個設計選擇內(nèi)部統(tǒng)一存成十進制 BigInt輸入輸出時做進制轉(zhuǎn)換。好處是加減乘除的代碼只寫一套進制只影響解析和打印。二進制字符串轉(zhuǎn)內(nèi)部十進制數(shù)采用“每讀一位整體乘 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、取余數(shù)余數(shù)倒序排列就是二進制串。注意純二進制輸出天然會丟前導零如果題目要求按輸入寬度補零打印函數(shù)需要接收一個最小寬度參數(shù)這個坑在下一章展開。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取個位數(shù)字的奇偶性也就是當前最低二進制位每取一位就把整個數(shù)除以 2循環(huán)直到數(shù)變成 0。倒序輸出是因為先取到的是最低位。這里divSmall和快速冪里用的是同一個函數(shù)一次實現(xiàn)兩處復用。5. 大數(shù)運算常見問題排查五個我真實踩過的坑5.1 二進制輸入解析時數(shù)組越界現(xiàn)象解析一個 500 位的二進制字符串“111...111”時parseBinary跑到一半程序崩潰或者解析出的數(shù)值明顯不對偶爾結(jié)果是負數(shù)。原因mulSmall和addSmall的實現(xiàn)里進位循環(huán)只跑到當前l(fā)en就停了。比如當前值已經(jīng)是 999乘 2 得到 1998長度從 3 變成 4如果沒處理這個新增長位最高位的 1 就丟了再加 1 的時候又可能再次進位。幾輪下來要么數(shù)組越界寫壞相鄰內(nèi)存要么進位丟失數(shù)據(jù)錯誤。解決給mulSmall和addSmall加上統(tǒng)一的長度修正邏輯。乘完或加完后從當前l(fā)en開始檢查高一位是否非零是就len同時判斷l(xiāng)en不能超過MAX_DIGITS。我一般把這段封裝成一個updateLen函數(shù)所有修改 digits 的運算結(jié)束都調(diào)一次。5.2 減法輸出 “-0” 和多余前導零現(xiàn)象1 - 1 輸出“-0”100 - 99 輸出“001”更離譜的是 123 - 123 輸出“-000”。原因兩個問題疊加。第一個是去前導零時把循環(huán)條件寫成了while (digits[len-1] 0) len--沒保留最后一位導致 0 被清成空串打印時亂套。第二個是符號處理compareBigInt返回 0兩數(shù)相等時代碼仍然按neg1走了于是給 0 加了個負號。解決去前導零強制保底一位條件寫成while (len 1 digits[len-1] 0) len--;。減法主函數(shù)開頭先比較如果compareBigInt(a, b) 0直接res-sign 1并退出不進交換邏輯。從那以后我寫所有涉及符號的運算都會先問一句“結(jié)果為零時符號應該是什么”。5.3 除法里商位不進位的死循環(huán)現(xiàn)象123 / 12 算出商 1正確答案是 10有時候程序直接卡死CPU 跑滿不退出。原因按位試商的循環(huán)里cur在拼入被除數(shù)當前位之前忘了乘 10。比如被除數(shù)處理到“12”這一位時cur存的是上一次的余數(shù) 0直接加 1 得到 1而不是 0×1011最后一位 3 進來時 cur 只是從 1 變成 3而不是 1×10313于是商位少算了一輪。死循環(huán)的情況多半是除數(shù)為 0或者compareBigInt寫錯導致 cur 永遠不小于除數(shù)。解決每次循環(huán)第一步先mulSmall(cur, 10, cur)再addSmall(cur, a-digits[i], cur)順序不能反。除數(shù)為 0 在函數(shù)入口直接判掉打印“除數(shù)不能為 0”并返回錯誤碼。這個坑我印象最深因為表面上看代碼每一行都對只有把豎式每一步打印出來才發(fā)現(xiàn) cur 缺了左移。5.4 快速冪的指數(shù)右移寫錯導致結(jié)果錯亂現(xiàn)象2^10 用快速冪算出來是 2^6或者 2^4打印中間過程發(fā)現(xiàn)指數(shù)序列變成 10、4、1、0而不是 10、5、2、1、0。原因因為我們的 BigInt 每個元素存的是十進制位直接寫e.digits[0] 1是完全錯誤的——十進制個位右移一位只是把個位數(shù)除以 2不是把整個大數(shù)除以 2。比如 10 的個位是 0右移還是 0整個數(shù)卻應該是 5。指數(shù)右移的正確姿勢是調(diào)用divSmall(e, 2, e)它會從最高位向最低位逐位帶余數(shù)計算等價于對整個大數(shù)做一次十進制除法。解決把快速冪里的右移統(tǒng)一改走divSmall同時策略上每次右移前先判斷奇偶再右移保證循環(huán)不變量正確。另外快速冪里mulBigInt(res, b, res)一定要允許res和b是同一個值我的乘法實現(xiàn)里是先完整算進臨時數(shù)組再復制回 res所以安全如果你的乘法是邊乘邊寫這里要格外小心別名問題。5.5 二進制輸出丟了前導零現(xiàn)象輸入“00001111”轉(zhuǎn)成內(nèi)部大數(shù)再打印變成“1111”和輸入寬度對不上。如果題目要求按固定字長輸出這塊直接丟分。原因printBinary的反向取余邏輯天然丟前導零因為內(nèi)部 BigInt 只保存數(shù)值不保存“輸入字符串原來有多長”這個信息。解決在解析入口記錄原始字符串長度或者給打印函數(shù)加一個minWidth參數(shù)輸出前先補零。我常用的做法是在主程序里保存 raw 輸入字符串的長度打印二進制結(jié)果時傳入max(minWidth, 實際位數(shù))手動在前面補 0。這個坑不踩一次很難意識到因為大多數(shù)自測用例都會用不帶前導零的二進制串。6. 驗證與進階用六個用例把整套大數(shù)運算過一遍6.1 邊界回歸用例與沒有寫在題目里的加分項寫完六個運算不要急著交先跑一組能同時覆蓋“進位、借位、截斷、符號、進制邊界”的用例。我每次都會把這幾個用例固定放在 main 函數(shù)里當回歸測試運算輸入期望輸出驗證點加法999999999999 11000000000000跨位連續(xù)進位長度加一減法1000000000 - 1999999999連續(xù)借位去掉前導零減法123 - 1230結(jié)果為零時符號不能是負乘法99999 × 999999999800001高位進位與長度修正除法123456789012345 / 123459999747595按位試商、商位補零取模2^100 mod 9718快速冪和取模的聯(lián)合調(diào)用最后一行是我的習慣用快速冪算乘方時順手把取模也驗一遍。因為題目只要求“大數(shù)乘方”和“大數(shù)取?！狈珠_實現(xiàn)但真正實戰(zhàn)里這兩者幾乎總是搭配出現(xiàn)。在快速冪的三步循環(huán)里把mulBigInt換成modBigInt(mulBigInt(...), mod)就能得到模冪結(jié)果這其實是很多密碼學算法的基礎用法。如果你想把代碼做厚這是最容易的加分點。驗證方式上建議把十進制和二進制各跑一遍同樣的運算確認結(jié)果一致比如十進制輸入13 * 7 91二進制輸入1101 * 111也應該輸出1011011。這能同時驗證解析、運算、打印三段邏輯沒有互相污染。從那以后我每寫完一個課程設計版本都強制自己先把這組用例在 main 里跑一遍再隨機生成兩個大數(shù)交叉驗證一次最后才敢交給老師。這種“先回歸、再提交”的習慣幫我在答辯前少改了很多低級錯誤。如果你手頭這份資源里的代碼也出現(xiàn)了類似問題照著第五章的五個坑逐條對照應該能省下不少調(diào)試時間。希望幫到你。本文還有配套的精品資源點擊獲取