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