簡介這份資源是《數(shù)據(jù)結(jié)構(gòu)與算法分析C語言描述》第二版的配套習(xí)題解答手冊面向正在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法分析課程、準(zhǔn)備考試或希望對照課后練習(xí)查漏補缺的讀者。壓縮包內(nèi)僅含1個PDF文件大小約233KB集中呈現(xiàn)原書多數(shù)練習(xí)的參考答案便于按章節(jié)檢索。內(nèi)容覆蓋算法分析、表棧與隊列、樹、哈希、優(yōu)先隊列、排序、不相交集合、圖算法、算法設(shè)計技巧及攤還分析等主題解答以偽C代碼和思路說明為主細(xì)節(jié)多留給讀者自行補全。已有142人學(xué)習(xí)下載。它適合在完成課后題后核對結(jié)論、理解復(fù)雜度推導(dǎo)與經(jīng)典結(jié)構(gòu)實現(xiàn)思路也能幫助讀者發(fā)現(xiàn)理解偏差并深化對數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計的掌握。1. 一份習(xí)題解答手冊真正的用法先跑通再對拍最后改參數(shù)很多人拿到 C 語言數(shù)據(jù)結(jié)構(gòu)與算法分析的教材和配套習(xí)題解答手冊第一反應(yīng)是當(dāng)小說翻看完 AVL 旋轉(zhuǎn)覺得自己懂了合上書寫不出三行。真正有用的用法是把解答手冊當(dāng)成一份“規(guī)范文檔 測試用例庫”而不當(dāng)成閱讀材料。手冊里出現(xiàn)的每一種結(jié)構(gòu)都要落成能編譯、能被 sanitizer 檢查、能被隨機數(shù)據(jù)反復(fù)錘打的一份 C 代碼每一個復(fù)雜度結(jié)論都要在自己的機器上換成可測的數(shù)字。這條路徑適合兩類人正在用 C 語言補數(shù)據(jù)結(jié)構(gòu)底子的開發(fā)者以及面試或工程里需要手寫鏈表、堆、散列的熟手。后面從偽代碼落地講到差分對拍把手冊里的答案變成你倉庫里能回歸的資產(chǎn)。2. 從偽代碼到能編譯的 CADT 骨架、指針與內(nèi)存的三條線解答手冊里的代碼片段多半是“示意性”的函數(shù)簽名省略了錯誤返回節(jié)點定義省略了 typedef內(nèi)存分配干脆寫成new或者一句話帶過。這些片段作為思路無誤直接貼進(jìn)編輯器就會連鎖翻車。這一章解決的是最底層的一步把手冊里的抽象數(shù)據(jù)類型ADT描述還原成一份結(jié)構(gòu)清晰、內(nèi)存可控、能開告警編譯的 C 工程骨架。2.1 為什么解答里的偽代碼不能直接抄成 CC 語言版教材的行文習(xí)慣是先用 ADT 定義接口再給實現(xiàn)思路最后給一段接近 C 但不等同于 C 的代碼。最容易出問題的是三處。第一處是節(jié)點定義。手冊里常寫“設(shè)節(jié)點包含一個元素和兩個指針”實際落地要考慮 key 的類型、是否需要父指針、是否需要維護(hù) size 和 height 這類附加字段。這些字段一旦寫進(jìn)結(jié)構(gòu)體所有旋轉(zhuǎn)、刪除、重建邏輯都要跟著改所以結(jié)構(gòu)體定義必須在動手前一次定清楚中途加字段的代價很高。第二處是錯誤處理。手冊里的Insert往往只關(guān)心“插入成功”這一條路徑?jīng)]有說明分配失敗怎么辦、重復(fù)鍵怎么辦、刪除不存在的鍵怎么辦。真實代碼里這三條路徑都必須有明確返回值否則調(diào)用方只能靠全局變量猜狀態(tài)。第三處是所有權(quán)。手冊講鏈表刪除節(jié)點時寫“釋放該節(jié)點”但沒講清楚被刪除節(jié)點里的數(shù)據(jù)指針由誰釋放。這在單向鏈表上不致命在多級結(jié)構(gòu)散列表的桶、圖的鄰接表上就會變成連鎖泄漏。我一般的做法是先寫頭文件把接口和錯誤返回定死再寫實現(xiàn)。接口定下來之后實現(xiàn)怎么寫都不會跑偏。2.2 一個可復(fù)用的 ADT 頭文件骨架下面這份骨架是從手冊里最常見的“帶哨兵的單向鏈表”抽象出來的可以直接當(dāng)模板用/* list.h —— 接口先行所有權(quán)、返回碼、不變量寫清楚 */ #ifndef LIST_H #define LIST_H #include stddef.h typedef int ElementType; /* 元素類型集中在這里改實現(xiàn)文件不用動 */ typedef enum { LIST_OK 0, LIST_ERR_ALLOC -1, /* 內(nèi)存分配失敗 */ LIST_ERR_NOT_FOUND -2, /* 刪除/查找目標(biāo)不存在 */ LIST_ERR_INVALID -3 /* 空指針、越界等調(diào)用方錯誤 */ } ListStatus; typedef struct ListNode { ElementType value; struct ListNode *next; } ListNode; typedef struct { ListNode *head; /* 哨兵頭節(jié)點不存有效數(shù)據(jù) */ size_t size; /* 維護(hù)長度避免每次都遍歷 */ } List; ListStatus list_init(List *l); ListStatus list_push_front(List *l, ElementType v); ListStatus list_remove(List *l, ElementType v); void list_destroy(List *l); /* 釋放全部節(jié)點調(diào)用后 size 歸零 */ #endif邏輯說明ElementType單獨 typedef 是手冊里 ADT 思想最值錢的一條——換元素類型時只改一行。哨兵頭節(jié)點讓插入和刪除都不需要特判空鏈表這是教材里反復(fù)強調(diào)的“啞節(jié)點”技巧在 C 里收益尤其明顯因為省掉的是最容易寫錯的指針分支。參數(shù)說明size用size_t而不是int避免長度比較時的隱式符號轉(zhuǎn)換ListStatus用枚舉而不是返回布爾值調(diào)用方能區(qū)分“分配失敗”和“目標(biāo)不存在”排錯時少走很多彎路。list_destroy不返回狀態(tài)因為釋放失敗在 C 里沒有可恢復(fù)的語義直接交給 sanitizer 檢查更實際。2.3 把 malloc 和 free 收攏到兩個函數(shù)手冊里每次插入都是一句malloc從不檢查返回值。工程里更糟的做法是到處if (p NULL) return散落各處的判斷沒人維護(hù)。我習(xí)慣把分配和釋放收攏成兩個帶診斷的函數(shù)/* mem.c —— 所有節(jié)點分配都走這里泄漏和重復(fù)釋放能一眼看到 */ #include stdio.h #include stdlib.h #include list.h void *xmalloc(size_t n) { void *p malloc(n); if (p NULL) { fprintf(stderr, xmalloc: out of memory (%zu bytes)\n, n); abort(); /* 教學(xué)與實驗階段直接終止便于定位 */ } return p; } void xfree(void *p) { if (p NULL) return; /* free(NULL) 合法但顯式返回更易讀 */ free(p); } ListStatus list_push_front(List *l, ElementType v) { if (l NULL || l-head NULL) return LIST_ERR_INVALID; ListNode *n xmalloc(sizeof *n); /* sizeof *n 比 sizeof(ListNode) 更抗改類型 */ n-value v; n-next l-head-next; /* 哨兵之后插入無需特判空表 */ l-head-next n; l-size; return LIST_OK; } void list_destroy(List *l) { if (l NULL || l-head NULL) return; ListNode *cur l-head-next; while (cur ! NULL) { ListNode *next cur-next; /* 先存后繼再釋放當(dāng)前 */ xfree(cur); cur next; } xfree(l-head); l-head NULL; l-size 0; }邏輯說明xmalloc把“分配失敗”這件事從每個調(diào)用點收攏到一個地方實驗階段直接 abort 是最省時間的選擇因為你不需要為內(nèi)存耗盡設(shè)計恢復(fù)路徑。list_destroy里先保存next再釋放cur是鏈表釋放的標(biāo)準(zhǔn)寫法順序?qū)懛淳褪墙炭茣壍?use-after-free。參數(shù)說明sizeof *n是防御性寫法結(jié)構(gòu)體字段變化時不用同步修改分配語句list_push_front里的l-head NULL判斷是防御“未初始化就使用”因為list_init之后head一定非空這條分支正常不會觸發(fā)一旦觸發(fā)說明調(diào)用方的生命周期管理有問題。2.4 用固定的編譯選項把問題提前暴露手冊從不提編譯選項但這一步?jīng)Q定了你后面調(diào)試要花多少時間。我固定用下面這組# Makefile —— 告警當(dāng)錯誤sanitizer 常開 CC cc CFLAGS -stdc99 -g -O1 -Wall -Wextra -Werror \ -fsanitizeaddress,undefined -fno-omit-frame-pointer LDFLAGS -fsanitizeaddress,undefined test_list: test_list.o list.o mem.o $(CC) $(LDFLAGS) -o $ $^邏輯說明-O1配合-g是調(diào)試期的甜點-O2會把部分變量優(yōu)化掉導(dǎo)致斷點跳躍-O0又會掩蓋部分未定義行為。-fsanitizeaddress抓越界和 use-after-free-fsanitizeundefined抓有符號溢出、空指針解引用、錯位對齊這兩類問題在數(shù)據(jù)結(jié)構(gòu)代碼里出現(xiàn)頻率極高。參數(shù)說明-Werror把告警升級為錯誤能強制你處理“未使用變量”“隱式聲明”這類問題后者在 C99 里是真正的坑——函數(shù)沒聲明就調(diào)用編譯器會按 int 返回處理指針被截斷成 32 位時只有在特定機器上才崩。-fno-omit-frame-pointer保證 sanitizer 的?；厮菘勺x。3. 復(fù)雜度分析落到實測把 O() 換成計數(shù)器和計時器教材里最容易被跳過的是復(fù)雜度分析這一章因為它“看起來不產(chǎn)出代碼”。但手冊里幾乎所有解答都在用 O() 描述代價如果你不把抽象階數(shù)和實測數(shù)字對上后面選結(jié)構(gòu)就是憑感覺。這一章把 O() 變成可測的量怎么插樁、測什么、怎么判斷你測出來的是階數(shù)而不是噪聲。3.1 上界、常數(shù)因子與“實際更快”的錯覺解答手冊給出的是漸進(jìn)上界它丟掉了常數(shù)因子和低階項。這在 n 很大時成立在你實際處理的規(guī)模上經(jīng)常不成立。典型的例子是插入排序和歸并排序前者是 O(n2)后者是 O(n log n)但在 n 小于幾十、且數(shù)據(jù)基本有序時插入排序往往跑得更快因為歸并排序的分配和拷貝開銷擺在那里。手冊不會告訴你這個交叉點在哪因為它依賴機器。我的處理方式是把“階數(shù)結(jié)論”和“常數(shù)結(jié)論”分開驗證階數(shù)用雙對數(shù)坐標(biāo)的斜率驗證常數(shù)用同一規(guī)模下的絕對耗時或操作計數(shù)驗證。前者回答“這個算法能不能擴展”后者回答“在 n1000 時該選誰”。兩個問題答案不一致是常態(tài)不是手冊錯了。3.2 用計數(shù)器替代 clock()統(tǒng)計比較與賦值次數(shù)clock()的抖動在小規(guī)模下能到 30% 以上測出來的曲線沒法看。更可靠的辦法是插樁計數(shù)把“比較次數(shù)”和“賦值次數(shù)”當(dāng)成代價的代理指標(biāo)/* count.h —— 極輕量的插樁release 時改成空宏即可 */ #ifndef COUNT_H #define COUNT_H extern unsigned long g_cmp, g_assign; #define CMP_LT(a, b) (g_cmp, (a) (b)) #define ASG(dst, val) (g_assign, (dst) (val)) #endif/* sort_measure.c —— 插入排序的插樁版本只改比較和賦值兩處 */ #include count.h void insertion_sort(int *a, int n) { for (int i 1; i n; i) { int key a[i]; /* 取元素不計入交換代價 */ int j i - 1; while (j 0 CMP_LT(key, a[j])) { /* 每次成功比較都計數(shù) */ ASG(a[j 1], a[j]); /* 每次后移都計數(shù) */ j--; } ASG(a[j 1], key); } }邏輯說明把比較和賦值包裝成宏而不是函數(shù)是為了讓計數(shù)器停留在寄存器層面的開銷可忽略同時保證-O1下不會被內(nèi)聯(lián)后優(yōu)化掉宏展開后是真實的全局變量自增編譯器不會刪。用計數(shù)器而不是計時器是為了讓“插入排序在 n50 時比歸并快”這個結(jié)論可以復(fù)現(xiàn)——同樣的輸入、同樣的代碼計數(shù)結(jié)果永遠(yuǎn)一致。參數(shù)說明g_cmp和g_assign定義為全局變量跑完一個用例前必須清零否則數(shù)據(jù)會串。CMP_LT只覆蓋“小于”這一種比較是因為手冊里絕大多數(shù)排序的判定條件都能歸約成小于如果你要測三路快排需要再加一個相等比較的宏否則計數(shù)會偏小。3.3 三個必須釘死的測量參數(shù)同樣的代碼換三個參數(shù)就能測出三條完全不同的曲線。這三個參數(shù)不控制住后面所有結(jié)論都不可信。參數(shù)取值建議不控制會怎樣數(shù)據(jù)規(guī)模 n從 2^8 起每步乘 2至少 8 個點點太少無法判斷斜率擬合出來的階數(shù)隨機性極大初始分布隨機、升序、降序、全等值四組分別測只測隨機數(shù)據(jù)會掩蓋快排在有序輸入上的退化重復(fù)次數(shù)每個規(guī)模至少跑 5 次取中位數(shù)單次測量受緩存和調(diào)度影響小規(guī)模下偏差可達(dá)數(shù)倍第三項容易被忽略。n256 這種規(guī)模一次運行只有微秒級進(jìn)程啟動和頁錯誤的開銷占比很高。我一般在外層套一個循環(huán)把同一組數(shù)據(jù)重復(fù)跑 1000 次再除以次數(shù)讓單次代價落到毫秒級抖動就被攤薄了。3.4 用雙對數(shù)斜率判斷階數(shù)測完數(shù)據(jù)之后不要靠眼睛看曲線“像不像拋物線”直接算斜率。若 T(n) 近似為 c·n^k則 log T 與 log n 是直線斜率為 k# slope.py —— 用相鄰兩點的雙對數(shù)斜率判斷階數(shù) import math def slopes(points): points: [(n, cost), ...] 按 n 升序 out [] for (n1, t1), (n2, t2) in zip(points, points[1:]): if t1 0 or t2 0: continue out.append(math.log2(t2 / t1) / math.log2(n2 / n1)) return out data [(256, 32_100), (512, 128_400), (1024, 513_800), (2048, 2_055_000)] print([round(s, 2) for s in slopes(data)]) # 期望接近 [2.0, 2.0, 2.0]邏輯說明相鄰點斜率比整體擬合更能暴露“小規(guī)模常數(shù)項主導(dǎo)”的區(qū)間。如果前兩個斜率明顯小于后面的說明這一段還在常數(shù)項影響范圍內(nèi)不能用來判斷階數(shù)只有當(dāng)斜率穩(wěn)定在某個值附近才能說這段數(shù)據(jù)呈現(xiàn)該階數(shù)的行為。參數(shù)說明用 log2 而不是自然對數(shù)是因為 n 每次翻倍時斜率正好是 k 本身讀起來直觀斜率 2.0 就是平方階。數(shù)據(jù)里出現(xiàn) cost 為 0 的點要跳過通常是規(guī)模太小、編譯器把整個循環(huán)優(yōu)化掉了這類點留著會污染斜率。4. 樹與散列的復(fù)現(xiàn)AVL 旋轉(zhuǎn)、散列沖突與再散列手冊里平衡樹和散列這兩章篇幅最重也是抄錯率最高的地方旋轉(zhuǎn)的四種情形代碼長得幾乎一樣散列的探測序列一旦寫錯表現(xiàn)是“大部分情況對、偶爾查不到”。這一章把這兩塊的落地細(xì)節(jié)釘死。4.1 AVL先寫不變量再寫旋轉(zhuǎn)AVL 的代碼之所以容易寫崩是因為大多數(shù)人是照著四種情形的圖去湊指針。更穩(wěn)的路徑是先聲明不變量再讓旋轉(zhuǎn)去滿足它。不變量只有兩條任意節(jié)點的左右子樹高度差絕對值不超過 1節(jié)點存儲的 height 字段等于左右子樹高度的較大值加 1空樹高度定義為 -1。有了這兩條四種情形可以歸約成兩個基本操作單旋轉(zhuǎn)和雙旋轉(zhuǎn)雙旋轉(zhuǎn)就是兩次單旋轉(zhuǎn)的組合。/* avl.c —— 高度定義為 -1 起步葉子節(jié)點高度為 0 */ #include stdlib.h #include count.h typedef struct AvlNode { int key; int height; struct AvlNode *left, *right; } AvlNode; static int h(const AvlNode *t) { return t ? t-height : -1; } static int imax(int a, int b) { return a b ? a : b; } /* 左-左情形對 k2 右旋返回新的子樹根 */ static AvlNode *rotate_right(AvlNode *k2) { AvlNode *k1 k2-left; k2-left k1-right; k1-right k2; k2-height imax(h(k2-left), h(k2-right)) 1; /* 先更新下層 */ k1-height imax(h(k1-left), h(k1-right)) 1; /* 再更新新根 */ return k1; } /* 右-右情形對 k1 左旋 */ static AvlNode *rotate_left(AvlNode *k1) { AvlNode *k2 k1-right; k1-right k2-left; k2-left k1; k1-height imax(h(k1-left), h(k1-right)) 1; k2-height imax(h(k2-left), h(k2-right)) 1; return k2; } /* 左右情形先對左兒子左旋再整體右旋 */ static AvlNode *double_left_right(AvlNode *k3) { k3-left rotate_left(k3-left); return rotate_right(k3); }邏輯說明旋轉(zhuǎn)里最容易錯的是高度更新的順序。必須先把下沉的那個節(jié)點的高度算出來再算新根的高度因為新根的高度依賴下沉節(jié)點更新后的值。順序反了不會立刻崩但高度會偏大 1幾輪插入之后平衡判斷就失效表現(xiàn)是“樹越長越歪”。h()對空指針返回 -1 而不是 0是為了讓葉子節(jié)點高度為 0 的約定自洽這也是教材里用的約定換成 0 起步會導(dǎo)致所有平衡因子差一位。參數(shù)說明key用 int 是為了和前面的計數(shù)器配合實際項目里換成ElementType即可。函數(shù)返回新的子樹根而不是原地修改是因為插入和刪除需要把新根掛回父節(jié)點用返回值寫法能避免維護(hù)父指針。插入函數(shù)的關(guān)鍵在回溯路徑上更新高度并判斷平衡因子四個分支的判定條件要寫清楚/* 插入后回溯平衡因子 左高 - 右高 */ AvlNode *avl_insert(AvlNode *t, int key) { if (t NULL) { AvlNode *n calloc(1, sizeof *n); /* 新葉子高度為 0calloc 后需修正 */ if (!n) return NULL; n-key key; n-height 0; return n; } if (CMP_LT(key, t-key)) { t-left avl_insert(t-left, key); if (h(t-left) - h(t-right) 2) { if (CMP_LT(key, t-left-key)) t rotate_right(t); else t double_left_right(t); } } else if (key t-key) { t-right avl_insert(t-right, key); if (h(t-right) - h(t-left) 2) { if (key t-right-key) t rotate_left(t); else t double_left_right_sym(t); } } t-height imax(h(t-left), h(t-right)) 1; return t; }邏輯說明判等分支故意留空即重復(fù)鍵不插入這是手冊里常見的一種約定如果你的場景需要允許重復(fù)改成在相等時往右子樹走即可但要注意這樣會讓刪除邏輯復(fù)雜一檔。平衡因子的判定用 2而不是 2是因為一次插入最多讓高度差從 1 變成 2用等號能在斷言層面盡早發(fā)現(xiàn)邏輯錯誤。參數(shù)說明calloc之后仍顯式設(shè)height 0是因為調(diào)用方可能把節(jié)點高度約定改成 1 起步顯式賦值比依賴零初始化安全。遞歸實現(xiàn)的好處是回溯路徑天然存在壞處是深樹會爆棧生產(chǎn)代碼里一般改成帶父指針的迭代版本但學(xué)習(xí)階段先用遞歸把不變量吃透。4.2 散列裝填因子和再散列閾值必須成對出現(xiàn)手冊講開放定址散列時給的是平方探測并提到“表不能太滿”。這句話在落地時會被簡化成“裝填因子別超過 0.5”然后就沒了。真正的坑是裝填因子閾值和再散列邏輯必須寫在一起只設(shè)閾值不寫再散列插入在表滿時會死循環(huán)。平方探測的探測序列是 i2 而不是 i寫錯這一處查找就會在“應(yīng)該有元素”的位置停下并返回未找到。判定條件要寫成i table_size / 2因為平方探測在表大小為質(zhì)數(shù)且裝填因子低于 0.5 時前一半探測序列就能覆蓋到空位。/* hash.c —— 開放定址平方探測裝填因子超過 0.5 觸發(fā)再散列 */ #define EMPTY_KEY (-2147483647) /* 用哨兵標(biāo)記空槽比額外數(shù)組省空間 */ typedef struct { int *keys; size_t capacity; /* 容量取質(zhì)數(shù)且盡量是 4k3 形 */ size_t size; /* 已用槽數(shù)不包含墓碑 */ } HashTable; static size_t next_prime(size_t n) { while (1) { int ok 1; for (size_t d 2; d * d n; d) if (n % d 0) { ok 0; break; } if (ok) return n; n; } } static void rehash(HashTable *h); void hash_insert(HashTable *h, int key) { if ((double)(h-size 1) / h-capacity 0.5) rehash(h); size_t i (size_t)key % h-capacity; for (size_t k 0; k h-capacity / 2; k) { size_t pos (i k * k) % h-capacity; /* 平方探測注意取模 */ if (h-keys[pos] EMPTY_KEY) { h-keys[pos] key; h-size; return; } if (h-keys[pos] key) return; /* 重復(fù)鍵直接忽略 */ } }邏輯說明rehash放在插入之前判斷而不是插入失敗之后補救這樣保證任何一次插入都有至少一半的空槽可用。k * k用size_t計算避免 n 很大時int溢出成負(fù)數(shù)導(dǎo)致取模結(jié)果為負(fù)這個坑在容量超過 46341 時會真實觸發(fā)。參數(shù)說明容量選 4k3 形的質(zhì)數(shù)是因為平方探測在質(zhì)數(shù)容量下探測序列覆蓋更均勻這是數(shù)論結(jié)論手冊里通常只在注釋里提一句。EMPTY_KEY用INT_MIN是因為題目數(shù)據(jù)都是正整數(shù)實際項目里應(yīng)該用單獨的occupied位圖或者允許存儲任意 int 時改用線性探測加墓碑標(biāo)記。4.3 同一組鍵分別跑 AVL 與散列該看什么跑對比實驗時很多人只比較“插入耗時”這個維度信息量很低散列插入是均攤常數(shù)AVL 是對數(shù)結(jié)論在寫代碼之前就知道了。真正值得看的三個量是觀察量AVL開放定址散列說明最壞一次查找的比較次數(shù)約 1.44 log?n探測次數(shù)不定接近滿載時急劇上升最壞情況才是工程里要防的有序遍歷中序 O(n) 直接輸出需要額外排序散列犧牲了順序性內(nèi)存占用每節(jié)點 3 個字段加對齊槽數(shù)與裝填因子成反比裝填因子 0.5 意味著近 2 倍冗余第三行最容易被忽略。手冊里說散列查找是常數(shù)沒提這個常數(shù)是用空間換來的。裝填因子壓到 0.5意味著容量要是元素數(shù)的兩倍壓到 0.25 會讓探測更快但內(nèi)存直接翻四倍。如果你的場景是百萬級元素、內(nèi)存受限把裝填因子調(diào)到 0.7 以上、同時改用線性探測提升緩存命中率實測往往比教科書參數(shù)更快代價是最壞情況的探測次數(shù)變長。這類結(jié)論靠讀手冊得不出來只能自己壓測。5. 照抄解答最容易翻車的五個現(xiàn)場現(xiàn)象、原因與解法這一章集中處理復(fù)現(xiàn)過程中真實會卡住人的幾類問題。寫代碼的時間可能只占三成剩下七成都在和這些東西耗。每條按現(xiàn)象、原因、解決三段說。5.1 段錯誤與內(nèi)存類現(xiàn)場現(xiàn)象鏈表刪除操作單獨測都能過連續(xù)刪 1000 個節(jié)點后在list_destroy里隨機崩?；厮葜赶騠ree看不出哪一行。原因刪除節(jié)點時先free(cur)再取cur-next。單次刪除時free之后那塊內(nèi)存通常還沒被復(fù)寫next恰好還能讀到所以看不出來連續(xù)刪除時分配器把釋放的塊掛回空閑鏈表會在塊頭寫入指針cur-next讀到的就是空閑鏈表指針再去解釋成節(jié)點就是野指針。解決讀后繼和釋放嚴(yán)格分兩步用臨時變量保存next。這條規(guī)則在雙向鏈表、樹的刪除、散列表的桶鏈上同樣適用。另外把 sanitizer 常開這類問題會在第一次越界時就被 ASan 攔下來不用等到崩潰現(xiàn)場。現(xiàn)象程序跑完不崩但valgrind或 ASan 報告 still reachable罪魁禍?zhǔn)资且粋€只在插入路徑上分配的臨時數(shù)組。原因手冊里的算法描述常常只講主體回收寫在別處或者干脆省略。只按主體實現(xiàn)臨時緩沖區(qū)就漏了。解決把“誰分配誰釋放”寫進(jìn)函數(shù)注釋并在每個返回路徑上核對。我一般的習(xí)慣是讓malloc和free在同一屏代碼內(nèi)出現(xiàn)跨越一屏的分配就要重新審視結(jié)構(gòu)劃分。5.2 結(jié)果對不上類現(xiàn)場現(xiàn)象快速排序在隨機數(shù)據(jù)上結(jié)果正確在“大量重復(fù)元素”的測試集上跑出非遞增序列或者直接崩。原因樸素的快排按“小于 pivot 放左、大于等于放右”劃分遇到全等值數(shù)據(jù)時每次劃分都退化成 1 和 n-1遞歸深度變成 n。崩是棧溢出結(jié)果錯是劃分邊界寫錯時把 pivot 覆蓋了。解決劃分改用雙指針相向掃描遇到相等元素就交換讓相等值均勻分布到兩側(cè)或者直接實現(xiàn)三路劃分把區(qū)間分成小于、等于、大于三段。同時給遞歸加深度上限超過 2 log n 時切換到堆排序這也是很多標(biāo)準(zhǔn)庫的兜底策略。手冊里通常只給基礎(chǔ)版本邊界處理要自己補?，F(xiàn)象圖的最短路徑算法在小圖上正確在帶負(fù)權(quán)邊的圖上給出錯誤答案但沒有報錯。原因Dijkstra 的貪心前提是非負(fù)權(quán)邊手冊在這一節(jié)通常會寫一句前提條件很容易被當(dāng)成廢話跳過。解決加斷言或者前置檢查發(fā)現(xiàn)負(fù)權(quán)邊就切換到能處理負(fù)權(quán)的算法如果只是用來驗證理解至少在測試用例里顯式包含一條負(fù)權(quán)邊看它怎么錯比只在正確輸入上跑通更有價值。5.3 復(fù)雜度與性能類現(xiàn)場現(xiàn)象歸并排序?qū)崿F(xiàn)完n 取到十萬時反而比插入排序慢懷疑自己寫錯了。原因歸并的每次遞歸都在malloc一個臨時數(shù)組分配開銷蓋過了 O(n log n) 的優(yōu)勢。手冊里的偽代碼默認(rèn)“合并用的輔助空間已就緒”沒說明這個空間要在遞歸外一次性分配。解決在排序入口分配一塊與輸入等長的緩沖區(qū)遞歸過程中只做拷貝不在遞歸內(nèi)分配。這一處改動在十萬級數(shù)據(jù)上通常能帶來數(shù)倍差距。順帶把邊界條件改成 n 小于閾值時直接插入排序交叉點實測在 16 到 32 之間?，F(xiàn)象同一份代碼在自己機器上跑 3 秒換臺機器跑 12 秒開始懷疑算法選錯。原因大規(guī)模順序訪問的結(jié)構(gòu)數(shù)組、堆對緩存敏感同樣階數(shù)的算法在緩存命中率上能差一個數(shù)量級。編譯優(yōu)化等級和 CPU 頻率策略也會帶來數(shù)倍差異。解決跨機比較時只比操作計數(shù)不比墻上時間。要比時間就在同一臺機器上、同一編譯選項下、用中位數(shù)比較。這條在選結(jié)構(gòu)時尤其重要手冊里兩個 O(n log n) 的排序?qū)嶋H差三倍是正?，F(xiàn)象別急著推翻階數(shù)結(jié)論。6. 用差分測試把解答手冊變成回歸用例庫手冊里每道題的答案本質(zhì)上都是一個“預(yù)期輸出”。把這層關(guān)系利用起來就能把整本手冊變成回歸測試集一邊寫自己的實現(xiàn)一邊寫一個慢但絕對正確的暴力版本用隨機數(shù)據(jù)喂給兩邊對拍。這個做法在樹、散列、圖算法上都能用尤其是最大子序列和、最短路、拓?fù)渑判蜻@類“結(jié)論唯一、實現(xiàn)容易錯”的題目。最典型的是最大子序列和。手冊給了四種解法復(fù)雜度從立方到線性彼此可以互相驗證/* difftest.c —— 暴力 O(n^3) 作為基準(zhǔn)與分治 O(n log n) 對拍 */ #include stdio.h #include stdlib.h #include time.h #include assert.h static int brute(const int *a, int n) { int best 0; /* 空子序列和為 0與教材約定一致 */ for (int i 0; i n; i) for (int j i; j n; j) { int sum 0; for (int k i; k j; k) sum a[k]; if (sum best) best sum; } return best; } static int max3(int x, int y, int z) { int m x y ? x : y; return m z ? m : z; } static int dc(const int *a, int lo, int hi) { /* 區(qū)間 [lo, hi) */ if (lo hi) return 0; if (hi - lo 1) return a[lo] 0 ? a[lo] : 0; int mid lo (hi - lo) / 2; int left dc(a, lo, mid), right dc(a, mid, hi); int ls 0, lb 0; /* 左半含邊界最大值 */ for (int i mid - 1; i lo; i--) { ls a[i]; if (ls lb) lb ls; } int rs 0, rb 0; for (int i mid; i hi; i) { rs a[i]; if (rs rb) rb rs; } return max3(left, right, lb rb); } int main(void) { srand(20240501); for (int round 0; round 20000; round) { int n 1 rand() % 40; /* 小規(guī)模多輪覆蓋更多形態(tài) */ int a[40]; for (int i 0; i n; i) a[i] rand() % 21 - 10; /* 含負(fù)數(shù)才有意義 */ assert(brute(a, n) dc(a, 0, n)); } puts(diff ok); return 0; }邏輯說明暴力版復(fù)雜度立方但邏輯直白幾乎不可能寫錯適合當(dāng)基準(zhǔn)。分治版是全篇最容易在跨中點的循環(huán)邊界上翻車的地方左半從mid-1向前累加右半從mid向后累加兩邊的初始值都是 0這樣全負(fù)數(shù)組返回 0 與暴力版一致。斷言放在循環(huán)里而不是循環(huán)外是為了在第一次不一致時就能定位到具體的隨機種子和輸入。參數(shù)說明rand() % 21 - 10保證正負(fù)混合全正數(shù)會讓所有版本都返回總和測不出邊界錯誤。規(guī)模限制在 40 以內(nèi)是因為立方復(fù)雜度在 40 上單輪只有 6 萬次運算兩萬輪也才 12 億次幾秒內(nèi)跑完。如果被測算法是百萬級才暴露問題的類型就換方法固定種子、放大規(guī)模、減少輪數(shù)但始終保留至少一個“小規(guī)模多種子”的階段。測試維度建議取值能抓出的問題元素取值全正、全負(fù)、正負(fù)混合、全零初始值約定錯誤、邊界返回錯誤規(guī)模1、2、3、2 的冪、質(zhì)數(shù)附近單元素特判遺漏、遞歸拆分不均勻排列形態(tài)隨機構(gòu)造、已升序、已降序、全等值退化路徑、劃分不均、無限遞歸重復(fù)運行固定隨機種子讓失敗可以精確復(fù)現(xiàn)我踩過最深的一個坑是把對拍腳本的隨機種子設(shè)成time(NULL)。某次跑了兩小時才發(fā)現(xiàn)一個不一致回頭重跑再也復(fù)現(xiàn)不出來因為種子已經(jīng)變了。從那以后所有隨機測試都固定種子把種子號寫進(jìn)日志失敗時直接改一行重放。另外就是別急著上大規(guī)模——小規(guī)模多輪次幾乎總能更快地暴露邏輯錯誤而大規(guī)模只能告訴你性能問題。手冊里的答案只是起點真正吃透一個結(jié)構(gòu)靠的是你自己的對拍腳本跑綠的那一刻。希望幫到你。本文還有配套的精品資源點擊獲取