簡介這是一份數(shù)據(jù)結構課程設計完整報告圍繞哈夫曼碼編/譯碼系統(tǒng)、遞歸替換問題、跳馬問題與長整數(shù)運算四個經(jīng)典專題適合計算機專業(yè)學生在備考、期末復習或完成類似課程設計時作為參考。哈夫曼編碼部分詳細說明構建哈夫曼樹、生成前綴編碼及編解碼過程遞歸替換問題分析模式查找與替換的遞歸策略及邊界條件跳馬問題采用深度優(yōu)先或廣度優(yōu)先搜索遍歷棋盤路徑長整數(shù)運算則闡述用數(shù)組或鏈表存儲大數(shù)并實現(xiàn)加減乘除的方法。每個專題均按標準課程設計體例展開包含數(shù)據(jù)類型定義、算法設計、函數(shù)調(diào)用關系圖、調(diào)試分析、測試結果和帶注釋的源程序目錄結構清晰便于按步驟對照實現(xiàn)和驗證。整包為單個PDF文檔大小268KB內(nèi)容集中目前已吸引171人學習適合作為數(shù)據(jù)結構與算法實踐環(huán)節(jié)的輔助參考資料。1. 數(shù)據(jù)結構課設四題合訂到底在考什么拿到《哈夫曼碼的編譯碼系統(tǒng)遞歸替換問題跳馬問題長整數(shù)運算問題》這套課設題組第一反應通常是四個題四個方向哪個都不好糊弄。它把數(shù)據(jù)結構的主場全占了——樹與編碼考哈夫曼樹遞歸與?？歼f歸替換圖搜索考跳馬問題的 BFS 和回溯線性表與高精度考長整數(shù)運算。對正在做課設的本科生這是把數(shù)據(jù)結構教材 C 語言版里的章節(jié)串成工程題對準備數(shù)據(jù)結構 408 和考研數(shù)據(jù)結構的同學它幾乎就是樹、棧、圖、鏈表四塊的綜合練習。文章按這四個題逐個給出可復制的實現(xiàn)方案、關鍵參數(shù)和邊界處理末尾附上驗收前的測試清單照著做就能把課設從「能跑」推進到「敢演示」。2. 哈夫曼碼編譯碼系統(tǒng)從最小堆建樹到逐位譯碼2.1 先弄清編碼模型頻率表與前綴碼的關系哈夫曼碼的本質(zhì)是前綴碼任何一個字符的編碼都不是另一個字符編碼的前綴所以譯碼時不需要分隔符從根節(jié)點沿著 0/1 往下走走到葉子就是一個字符。整套系統(tǒng)分三段統(tǒng)計字符頻率、建樹生成編碼表、用編碼表壓縮電文并譯碼。課設最常見的翻車點不在建樹而在「只有一個字符」和「編碼生成方向反了」這兩個邊角料上。建樹的輸入是頻率表。常見做法是掃描輸入文本用數(shù)組統(tǒng)計每個 ASCII 字符出現(xiàn)次數(shù)把出現(xiàn)次數(shù)大于 0 的字符作為葉子節(jié)點。這里不需要先把字符排序——排序算法在這里派不上用場直接用數(shù)組下標映射字符掃一遍文本就能得到頻率復雜度 O(n)比先排序再統(tǒng)計更省事。葉子數(shù)量 n 確定后整棵哈夫曼樹的節(jié)點總數(shù)是 2n-1這個數(shù)字在建樹時要提前算清楚否則數(shù)組開小了會越界。2.2 哈夫曼樹的建樹代碼數(shù)組靜態(tài)鏈表與雙親指針課設里我一般不用動態(tài)二叉樹而是用三個數(shù)組模擬靜態(tài)鏈表lchild、rchild、parent 各開 2n 大小。選數(shù)組而不是指針好處是調(diào)試時能直接看下標打印整棵樹方便析構也不用遞歸釋放。每個節(jié)點記錄權值、左右孩子和雙親雙親字段同時充當「是否已被合并」的標記初始為 0被選中合并后改成新節(jié)點下標。#include stdio.h #include string.h #define MAX_LEAF 128 // ASCII 可見字符數(shù)量上限 #define MAX_NODE (MAX_LEAF * 2 - 1) typedef struct { int weight; // 權值葉節(jié)點是字符頻率 int parent, lchild, rchild; // 雙親、左右孩子下標0 表示空 } HTNode; HTNode ht[MAX_NODE]; char leafChars[MAX_LEAF]; // 葉節(jié)點對應的字符 int leafCnt 0; void buildHuffmanTree() { // 從 leafCnt 開始創(chuàng)建內(nèi)部節(jié)點總共需要 2*leafCnt - 1 個節(jié)點 for (int i leafCnt; i 2 * leafCnt - 1; i) { int m1 -1, m2 -1; int w1 0x7fffffff, w2 0x7fffffff; // 線性掃描找兩個最小權值節(jié)點parent 為 0 表示尚未合并 for (int j 0; j i; j) { if (ht[j].parent ! 0) continue; if (ht[j].weight w1) { w2 w1; m2 m1; w1 ht[j].weight; m1 j; } else if (ht[j].weight w2) { w2 ht[j].weight; m2 j; } } // m1 和 m2 成為新節(jié)點 i 的左右孩子 ht[m1].parent i; ht[m2].parent i; ht[i].lchild m1; ht[i].rchild m2; ht[i].weight w1 w2; ht[i].parent 0; } }這段代碼的關鍵在循環(huán)范圍i 從 leafCnt 走到 2*leafCnt - 2正好創(chuàng)建 n-1 個內(nèi)部節(jié)點。掃描時跳過 parent 非 0 的節(jié)點保證每個葉子只被合并一次。時間復雜度 O(n2)n 最大 128課設數(shù)據(jù)量下完全夠用如果追求理論性能可以換最小堆但代碼量上去后調(diào)試成本不劃算。注意 m1 和 m2 的更新順序——先用 m1 存最小值再用 m2 存次小值寫反了建出來的樹權值順序會亂編碼長度雖然可能不變但樹的形狀不對。2.3 編碼表生成與譯碼的邊界情況生成編碼時從葉子往上走到根每走一步記錄 0 或 1走完得到的串是「從葉子到根」的反向序列必須倒過來才是真正的編碼。這個倒序操作是課設里最容易忽略的細節(jié)很多人把 tmp 直接拷進編碼表結果譯碼時對不上。char codeTable[MAX_LEAF][MAX_LEAF 1]; // 每個字符的編碼字符串 void genCodes() { char tmp[MAX_LEAF 1]; for (int i 0; i leafCnt; i) { int cur i, p ht[i].parent; int pos 0; // 從葉子向根走tmp 里存的是逆序編碼 while (p ! 0) { if (ht[p].lchild cur) tmp[pos] 0; else tmp[pos] 1; cur p; p ht[p].parent; } // 倒序后才得到正確編碼 for (int j 0; j pos; j) codeTable[i][j] tmp[pos - 1 - j]; codeTable[i][pos] \0; } }譯碼則反過來從根出發(fā)遇 0 走左孩子、遇 1 走右孩子走到葉子輸出字符并回到根。判斷葉子不能依賴 parent因為根節(jié)點的 parent 也是 0常見做法是檢查 lchild 和 rchild 是否同時為 0。這里有個特例必須單獨處理當 leafCnt 1 時整棵樹只有一個葉子節(jié)點編碼是空串譯碼時不管輸入什么直接輸出那個字符。不處理這個分支建樹循環(huán)根本進不去后續(xù)代碼會訪問未初始化的節(jié)點表現(xiàn)就是隨機崩潰。void decode(char *bits, int len) { if (leafCnt 1) { // 單字符特例無編碼直接輸出 for (int i 0; i len; i) putchar(leafChars[0]); return; } int root 2 * leafCnt - 2; // 根節(jié)點下標 int cur root; for (int i 0; i len; i) { if (bits[i] 0) cur ht[cur].lchild; else cur ht[cur].rchild; if (ht[cur].lchild 0 ht[cur].rchild 0) { putchar(leafChars[cur]); cur root; } } }譯碼的輸入可以是 0/1 字符數(shù)組也可以是二進制位。課設通常要求看得見摸得著用字符 0 和 1 存就行壓縮率難看一點但便于驗證如果要求展示壓縮效果可以把 8 個 0/1 字符并成一個字節(jié)輸出解壓時再按位還原。3. 遞歸替換問題與跳馬問題遞歸和回溯的兩種考試姿勢3.1 遞歸替換問題顯式棧怎么還原函數(shù)調(diào)用遞歸替換問題的核心是「把遞歸算法改寫成非遞歸」考察對棧幀的理解。遞歸函數(shù)在運行時每次調(diào)用都會把參數(shù)、局部變量和返回地址壓入系統(tǒng)棧遞歸改非遞歸的通用套路就是自己維護一個棧把原來隱式的壓棧彈棧變成顯式的 push 和 pop。常見題型包括快速排序非遞歸化、二叉樹遍歷非遞歸化、斐波那契尾遞歸消除課設里最常抽到的是排序類。以快速排序為例遞歸版本每次處理一個區(qū)間然后遞歸處理左右兩個子區(qū)間。改成非遞歸時棧里存的不是整個數(shù)組而是一個個「待處理區(qū)間」的左右端點。每個棧幀只需要 low 和 high 兩個整數(shù)這就是遞歸函數(shù)的運行現(xiàn)場。typedef struct { int low, high; // 待排序區(qū)間 } Range; void quickSortNonRecur(int arr[], int n) { Range stack[100005]; // 顯式棧模擬系統(tǒng)調(diào)用棧 int top 0; stack[top].low 0; stack[top].high n - 1; top; while (top 0) { top--; // 彈出當前區(qū)間 int low stack[top].low, high stack[top].high; if (low high) continue; // 一趟劃分教科書版快排 int pivot arr[low]; int l low, r high; while (l r) { while (l r arr[r] pivot) r--; arr[l] arr[r]; while (l r arr[l] pivot) l; arr[r] arr[l]; } arr[l] pivot; // 先壓右區(qū)間再壓左區(qū)間出棧后先處理左側 if (l 1 high) { stack[top].low l 1; stack[top].high high; top; } if (low l - 1) { stack[top].low low; stack[top].high l - 1; top; } } }這段代碼里最重要的參數(shù)是棧頂指針 top。壓棧順序決定處理順序后進先出所以先壓右區(qū)間、再壓左區(qū)間出棧時左區(qū)間先被處理和遞歸版本從左到右的順序一致。區(qū)間邊界 low high 時直接跳過這是遞歸出口的等價物。寫這類題容易犯的錯是漏壓某個方向的區(qū)間或者把區(qū)間端點算錯一位導致排序結果不對。建議對照遞歸版本逐行翻譯遞歸調(diào)用 f(l, mid-1) 對應壓入 (l, mid-1)遞歸調(diào)用 f(mid1, r) 對應壓入 (mid1, r)一個都不能少。3.2 跳馬問題建模走法數(shù)組與約束條件跳馬問題也叫騎士巡游問題給定 n×m 棋盤和起點終點馬按「日」字走求能否到達以及最短步數(shù)。這個題表面上和圖論里的最短路是一回事但棋盤是稀疏圖每個節(jié)點最多連 8 條邊所以用 BFS 求最短步數(shù)是標準解法。如果題目只要求「找一條可行路徑」DFS 回溯也能做但棋盤一大就指數(shù)爆炸課設里優(yōu)先寫 BFS。建模分三步坐標系、走法數(shù)組、越界判斷。走法數(shù)組是 8 個偏移量寫錯一個方向整個圖就壞了這是最常見的低級錯誤。我用兩個數(shù)組分別存 x 和 y 的偏移量順序無所謂但要寫全。int dx[8] {1, 1, 2, 2, -1, -1, -2, -2}; int dy[8] {2, -2, 1, -1, 2, -2, 1, -1};坐標從 0 開始還是從 1 開始不影響算法但輸入輸出的轉(zhuǎn)換要做干凈。課設題目如果給的是 1-indexed 坐標讀入后立即減 1之后所有邏輯都用 0-indexed避免中間到處做偏移修正。3.3 跳馬最短路徑的 BFS 實現(xiàn)與路徑回溯BFS 的代碼骨架是隊列加距離數(shù)組。距離數(shù)組初始化成 -1同時充當 visited 的角色一舉兩得。這里有個關鍵點節(jié)點在入隊時就標記為已訪問而不是出隊時才標記。入隊標記能保證每個節(jié)點最多入隊一次隊列長度可控出隊標記會讓同一節(jié)點被多次入隊小棋盤看不出問題棋盤到了幾百階直接內(nèi)存膨脹加超時。#include stdio.h #include string.h #define MAXN 1005 int dist[MAXN][MAXN]; int preX[MAXN][MAXN], preY[MAXN][MAXN]; // 記錄前驅(qū)節(jié)點坐標 int bfs(int sx, int sy, int tx, int ty, int n, int m) { if (sx tx sy ty) return 0; memset(dist, -1, sizeof(dist)); int queX[MAXN * MAXN], queY[MAXN * MAXN]; int head 0, tail 0; queX[tail] sx; queY[tail] sy; tail; dist[sx][sy] 0; while (head tail) { int x queX[head], y queY[head]; head; for (int k 0; k 8; k) { int nx x dx[k], ny y dy[k]; if (nx 0 || nx n || ny 0 || ny m) continue; if (dist[nx][ny] ! -1) continue; // 已訪問過跳過 dist[nx][ny] dist[x][y] 1; preX[nx][ny] x; preY[nx][ny] y; // 記錄來源 if (nx tx ny ty) return dist[nx][ny]; queX[tail] nx; queY[tail] ny; tail; } } return -1; // 不可達 }dist 數(shù)組的意義是起點到每個格子的最短步數(shù)dist[x][y] dist[px][py] 1 成立的原因是 BFS 按層擴展第一次到達某個格子的路徑一定最短。pre 數(shù)組用于回溯路徑到達終點后從終點沿著 pre 一路回退到起點再把序列倒過來輸出。如果題目只要求輸出步數(shù)pre 數(shù)組可以去掉省不少內(nèi)存但如果要求輸出完整路徑pre 必須保留。棋盤上限要注意隊列長度n×m 最大一百萬個格子時queX 和 queY 要開到一百萬以上用變長數(shù)組或者 malloc 動態(tài)分配更穩(wěn)妥。4. 長整數(shù)運算問題萬進制鏈表幾百位加法乘法怎么落地4.1 為什么選萬進制鏈表int、數(shù)組與鏈表的選型長整數(shù)運算問題的輸入是幾百位甚至上千位的十進制數(shù)任何原生整數(shù)類型都存不下。常見方案有兩種用數(shù)組從高位到低位存每一位或者用鏈表按位存。數(shù)組實現(xiàn)簡單但課設題目明確要求「長整數(shù)」鏈表是標準答案——鏈表的好處是長度動態(tài)增長加法乘法產(chǎn)生進位時不會浪費空間也便于展示數(shù)據(jù)結構功底。參考王道或大話數(shù)據(jù)結構線性表一章鏈表的插入刪除本身就是考點這個題等于把鏈表操作和進制轉(zhuǎn)換揉在一起考。存儲基數(shù)的選擇是關鍵參數(shù)。用 BASE 10 存每一位空間浪費大且乘法效率低我一般用 BASE 10000即每個鏈表節(jié)點存 4 位十進制數(shù)稱為「萬進制」。萬進制的好處有三點同樣長度的數(shù)鏈表節(jié)點數(shù)少 4 倍節(jié)點值范圍 0~9999兩個節(jié)點相乘最大約 1e8int 放得下輸出時每個節(jié)點補零到 4 位即可。鏈表方向約定為「低位在前」即第一個節(jié)點是個位到千位下一個節(jié)點是萬位到千萬位這樣進位只會向后擴展和手工豎式一致。#define BASE 10000 // 萬進制每個節(jié)點存 4 位 #define MAXDIGIT 1000 // 最多 1000 個節(jié)點約 4000 位 typedef struct BigIntNode { int val; // 0 ~ 9999 struct BigIntNode *next; // 指向更高位 } BigIntNode;4.2 萬進制加法的實現(xiàn)從低位進位到符號分離加法邏輯和十進制豎式完全一樣從低位開始逐節(jié)點相加carry 記錄進位結果當前位是 sum % BASE進位是 sum / BASE。需要注意循環(huán)結束條件當兩個鏈表都遍歷完但 carry 不為 0 時還要再創(chuàng)建一個節(jié)點存放最高位的進位這是加法最常見的遺漏點。BigIntNode* add(BigIntNode *a, BigIntNode *b) { BigIntNode *head NULL, **tail head; int carry 0; while (a ! NULL || b ! NULL || carry ! 0) { int sum carry; if (a ! NULL) { sum a-val; a a-next; } if (b ! NULL) { sum b-val; b b-next; } carry sum / BASE; BigIntNode *node (BigIntNode*)malloc(sizeof(BigIntNode)); node-val sum % BASE; node-next NULL; *tail node; // 尾插法保持低位在前 tail node-next; } return head; }這段代碼用了二級指針 tail 做尾插法好處是不需要單獨維護頭節(jié)點的前驅(qū)。如果你不熟悉二級指針也可以用一個啞節(jié)點dummy head簡化邊界判斷返回時記得釋放啞節(jié)點。符號處理建議放在加法外層加數(shù)和被加數(shù)同號時直接調(diào) add異號時變成減法比較絕對值大小后調(diào)用減法函數(shù)結果符號取絕對值大的一方的符號。把符號和絕對值運算分離比在加法內(nèi)部處理負數(shù)干凈得多不容易出現(xiàn)「負負得正卻忘了進位」的玄學 bug。4.3 萬進制乘法與輸出補零先累加再統(tǒng)一進位乘法如果直接模仿豎式逐位相乘最直觀的做法是兩層循環(huán)把 a 的第 i 個節(jié)點和 b 的第 j 個節(jié)點的乘積累加到結果數(shù)組的下標 ij 處。這里最常踩的坑是「邊乘邊進位」一邊累加一邊處理進位會導致后續(xù)累加時數(shù)組里已經(jīng)有進位后的值再疊加就亂套。正確做法是先用一個數(shù)組把原始乘積全部累加完最后統(tǒng)一做一輪進位這也是高精度乘法的標準姿勢。BigIntNode* multiply(BigIntNode *a, BigIntNode *b) { int lenA 0, lenB 0; BigIntNode *pa; for (pa a; pa ! NULL; pa pa-next) lenA; for (pa b; pa ! NULL; pa pa-next) lenB; long long res[MAXDIGIT * 2] {0}; // 中間結果用 long long防溢出 int ai 0, bj 0; for (pa a; pa ! NULL; pa pa-next, ai) { bj 0; for (BigIntNode *pb b; pb ! NULL; pb pb-next, bj) { res[ai bj] (long long)pa-val * pb-val; } } // 統(tǒng)一進位從低位到高位依次處理 int totalLen lenA lenB; for (int i 0; i totalLen; i) { res[i 1] res[i] / BASE; res[i] % BASE; } // 把 res 數(shù)組轉(zhuǎn)回鏈表去掉高位多余的 0 int highPos totalLen; while (highPos 0 res[highPos] 0) highPos--; BigIntNode *head NULL, **tail head; for (int i 0; i highPos; i) { BigIntNode *node (BigIntNode*)malloc(sizeof(BigIntNode)); node-val (int)res[i]; node-next NULL; *tail node; tail node-next; } if (head NULL) { // 結果為 0 BigIntNode *node (BigIntNode*)malloc(sizeof(BigIntNode)); node-val 0; node-next NULL; head node; } return head; }下標映射要算清楚a 的第 i 位從 0 開始和 b 的第 j 位相乘結果貢獻到 res[ij]不是 res[ij1]。搞錯下標最典型的故障是結果恰好少了一位檢查時很難發(fā)現(xiàn)。乘法的時間復雜度 O(lenA × lenB)兩個 1000 節(jié)點的數(shù)相乘要執(zhí)行百萬次乘法C 語言在毫秒級完成課設驗收完全沒問題如果要優(yōu)化可以用 Karatsuba但普通要求用不到。輸出函數(shù)是另一個重災區(qū)。鏈表是低位在前輸出必須先從最高位節(jié)點開始。最高位節(jié)點直接輸出數(shù)值后面每個節(jié)點要用 %04d 格式補零到 4 位否則 10001 會變成 11。負數(shù)在輸出前打一個 -然后走絕對值鏈表。5. 課設常見問題排查越界、爆棧、超時與對不上的報告5.1 哈夫曼n1 時直接崩編碼表逆序和越界現(xiàn)象輸入文本只有一個字符時程序崩潰或輸出亂碼編碼表生成后某些字符的編碼是反的譯碼結果錯亂。原因單字符時哈夫曼樹只有一個根節(jié)點建樹循環(huán)不執(zhí)行后續(xù)譯碼訪問了未初始化的 ht[cur].lchild編碼生成時從葉子往根走得到的序列是倒序沒有反轉(zhuǎn)就存入編碼表。解決建樹前判斷 leafCnt 1 直接走單字符特例邏輯genCodes 里在拷貝之前把 tmp 反轉(zhuǎn)一遍。建議把編碼生成的倒序邏輯單獨抽成一個函數(shù)測試時用一個只有兩個字符的字符串驗證編碼比如 aaab手動推導一遍編碼再對照程序輸出。5.2 遞歸替換棧幀字段少壓一個結果就翻車現(xiàn)象快排非遞歸版本對小數(shù)組排序正確對大數(shù)組排序結果部分錯誤或者程序能跑完但輸出沒有完全有序。原因遞歸改非遞歸時把遞歸函數(shù)的參數(shù)和局部變量的壓棧順序搞混了?？炫诺拿總€棧幀只有 low 和 high但如果原遞歸函數(shù)里有中間的臨時變量比如劃分后的 pivot 位置非遞歸版本也必須把它存進棧幀否則子區(qū)間范圍會算錯。解決對遞歸函數(shù)做一次棧幀分析列出「入口參數(shù) 進入函數(shù)后可能被修改且后續(xù)還要用的變量」這些全部放進結構體。壓棧順序和遞歸調(diào)用順序保持一致彈棧后再按對應順序處理。驗證方法是用遞歸版快排對拍隨機生成數(shù)組反復測不要只測教材上的示例數(shù)據(jù)。5.3 跳馬 BFS入隊即標記出隊標記會超時現(xiàn)象棋盤在 20×20 以內(nèi)正常擴大到 100×100 時程序變卡甚至內(nèi)存不夠BFS 求出的步數(shù)偶爾還不對。原因在節(jié)點出隊時才標記 visited同一個節(jié)點被多個方向同時擴展到會被重復入隊多次隊列膨脹到指數(shù)級。教科書上寫的是「出隊時標記」是某些特定寫法但在棋盤這種每個節(jié)點有 8 個鄰居的圖上必須「入隊時標記」。解決在 dist[nx][ny] ! -1 判斷通過后立即給 dist[nx][ny] 賦值并入隊。這個判斷既是防重入也是距離賦值的前提。上課設驗收時用 1000×1000 的棋盤從角上跑到對角如果跑到一半卡住先查標記時機。5.4 長整數(shù)乘法一邊乘一邊進位會覆蓋結果現(xiàn)象萬進制乘法結果比預期小很多或者中間某位出現(xiàn)負數(shù)偶爾結果還正確換一組數(shù)據(jù)就錯。原因兩層循環(huán)里每乘一次就立刻處理進位把 res 數(shù)組里還沒累加完的數(shù)提前改寫。比如 res[0] 先累加了 9999×9999進位到 res[1]之后 res[0] 又要累加新的乘積原來的低位還沒參與后續(xù)累加數(shù)據(jù)就被進位破壞了。解決用 long long 數(shù)組存原始乘積兩層循環(huán)全部累加完后再從低位到高位統(tǒng)一進位。這一步里數(shù)組下標從 0 到 lenAlenB-1 都要處理進位可能產(chǎn)生到 lenAlenB 的位置數(shù)組要開到兩倍長度。輸出時注意高位補零用 %04d 不是 %d。5.5 報告與代碼版本不一致課設驗收的隱形扣分現(xiàn)象演示時運行正常但交上去的實驗報告里截圖的數(shù)據(jù)和最終代碼輸出對不上答辯時被問到測試數(shù)據(jù)答不上來。原因代碼改過多版報告里的測試結果還是早期版本沒同步更新。數(shù)據(jù)結構實驗報告最被看重的是測試數(shù)據(jù)的完整性和可復現(xiàn)性不是代碼貼圖越多越好。解決確定代碼最終版后固定一組輸入文件命名為 test1.in、test2.in把對應的輸出文件test1.out、test2.out一起放到報告附件里。報告里每個模塊放「輸入、輸出、說明」三行對齊的表格測試數(shù)據(jù)包含普通情況、邊界情況空輸入、單字符、最大長度、不可達路徑這些數(shù)據(jù)和現(xiàn)場演示保持一致。代碼每改一版就把全部測試重新跑一遍輸出存進同一目錄覆蓋舊文件。6. 驗收前最后一小時對拍、壓測與留痕6.1 用對拍腳本驗證正確性對拍是競賽選手驗證程序的標準手段課設同樣適用。思路是寫一個你認為絕對正確的參考程序再寫一個隨機數(shù)據(jù)生成器兩個程序吃同一份輸入逐條比較輸出。長整數(shù)運算用 Python 的 int 做參考最穩(wěn)哈夫曼和跳馬可以手寫一個暴力解做參考比如跳馬的參考程序用 DFS 在小棋盤上窮舉所有路徑步數(shù)逐個比較。#!/bin/bash # 對拍腳本隨機生成輸入比較兩個程序的輸出 for i in $(seq 1 1000); do python3 gen.py test.in ./ref test.in ref.out ./mine test.in mine.out if ! diff -q ref.out mine.out /dev/null; then echo Case $i failed echo --- input --- cat test.in break fi done echo finished對拍能暴露的問題很多時候是「程序邏輯正確但輸入輸出格式不對」比如多了個空格或少了個換行。比起期末復習時背結論這個習慣能直接告訴你代碼哪里和預期不一致。隨機生成器要覆蓋邊界哈夫曼的輸入要包含只有一個字符的情況長整數(shù)的輸入要包含負數(shù)、0、首位有前導零的數(shù)跳馬要生成起點等于終點的數(shù)據(jù)。6.2 邊界數(shù)據(jù)與壓力測試清單驗收前按下面的表格過一遍每一項都記錄實際輸出寫進報告里就是完整的測試小節(jié)。模塊邊界測試數(shù)據(jù)預期結果哈夫曼空文本 / 單字符文本 / 全部字符同頻空文本不崩單字符編碼為空串同頻字符樹高盡量均衡哈夫曼100 萬字符長文本建樹和編碼總耗時在 1 秒內(nèi)內(nèi)存不超 10MB遞歸替換數(shù)組長度 0 / 1 / 已有序 / 完全逆序不崩且排序結果正確跳馬起點終點 / 不可達坐標 / 1000×1000 大棋盤起點終點相同返回 0不可達返回 -1大棋盤 1 秒內(nèi)出結果長整數(shù)0 負數(shù) / 9999×9999 邊界進位 / 4000 位最大長度進位正確輸出無前導零負數(shù)符號正確大數(shù)壓測時如果發(fā)現(xiàn)乘法超時先把 BASE 從 10000 降到 1000 試試能定位是進位邏輯問題還是真的算法效率不夠。棋盤壓測的隊列數(shù)組要按最大棋盤尺寸預分配別用動態(tài)增長的小數(shù)組反復 realloc性能會差很多。最后說點題外話。我當年做跳馬問題時BFS 用的是出隊標記自己測 10×10 怎么都對課設答辯現(xiàn)場老師把棋盤調(diào)成 100×100程序卡了十幾秒才出結果場面一度尷尬。后來養(yǎng)成習慣每個模塊寫完先寫一個 10 行左右的暴力參考程序?qū)ε囊惠喸倌脴O限數(shù)據(jù)壓一次性能。這套流程看著慢實際省下的調(diào)試時間遠超預期。希望這些踩坑記錄能讓你把課設做到「敢現(xiàn)場演示」的程度。本文還有配套的精品資源點擊獲取