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