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