數(shù)組和廣義表這兩個東西放在數(shù)據(jù)結(jié)構(gòu)的第三章看起來平平無奇。數(shù)組嘛天天寫代碼都在用廣義表嘛概念繞得人頭疼。但說實(shí)話這一章恰恰是從“會寫代碼的人”過渡到“懂?dāng)?shù)據(jù)結(jié)構(gòu)的人”的第一道門檻。數(shù)組背后的存儲邏輯、下標(biāo)為什么會從0開始、矩陣壓縮到底在壓縮什么、稀疏矩陣的轉(zhuǎn)置算法為什么有個“快速轉(zhuǎn)置”的版本以及廣義表那種遞歸定義的思維方式——這些東西不搞透后面樹、圖、哈希表你都會學(xué)得磕磕絆絆。我當(dāng)初學(xué)這一章的時(shí)候有一個很深的感受數(shù)組的代碼誰都會寫但問你“一個二維數(shù)組 a[m][n] 里a[i][j] 到底在內(nèi)存的哪個位置”很多人就答不上來了。而廣義表更是勸退神器它不像是前面學(xué)的線性表那樣“直來直去”元素套著元素一下子就把線性思維給擊穿了。所以這篇博文我打算把這一章拆開揉碎把那些教材里一筆帶過、但實(shí)際理解起來很關(guān)鍵的地方講清楚。內(nèi)容不多但這幾個點(diǎn)的分量值得你真的坐下來好好推一遍。1. 數(shù)組看似簡單實(shí)則是存儲世界的基石1.1 數(shù)組的“隨機(jī)訪問”能力靠的是一條公式數(shù)組在C語言里的聲明很簡單int a[10]編譯器就給你分配了連續(xù) 40 個字節(jié)如果int是 4 字節(jié)。為什么我們能直接寫a[3]就拿到第 4 個元素因?yàn)榫幾g器計(jì)算的是地址地址(a[i]) 首地址 i * sizeof(int)就這么簡單的一條公式構(gòu)成了“隨機(jī)訪問”的基礎(chǔ)——只要給下標(biāo)就能算出位置不用從頭遍歷。這就是數(shù)組和鏈表的本質(zhì)區(qū)別鏈表找第 5 個元素必須從頭往后數(shù)數(shù)組不用直接算。這里有個關(guān)鍵點(diǎn)經(jīng)常被忽略數(shù)組在 C 語言中不是一種“動態(tài)結(jié)構(gòu)”它在聲明那一刻長度就固定了。這跟 Python 里的列表完全不同Python 的 list 實(shí)際上是一個動態(tài)數(shù)組。很多從 Python 轉(zhuǎn) C 的同學(xué)會在這里踩坑以為可以像 Python 那樣往數(shù)組里隨便塞東西結(jié)果就出現(xiàn)了緩沖區(qū)溢出問題。C 語言的數(shù)組本質(zhì)上是這塊連續(xù)內(nèi)存的“帶類型視圖”它不會幫你做越界檢查也不會自動擴(kuò)容這就是為什么后來會出現(xiàn)鏈表、動態(tài)數(shù)組這些結(jié)構(gòu)——它們解決的都是數(shù)組“靜態(tài)”這個天然約束。1.2 下標(biāo)從0開始不只是“C語言習(xí)慣”這么簡單幾乎每本教材都會專門講一下數(shù)組下標(biāo)為什么從 0 開始。很多同學(xué)的理解是“慣例”“C 語言就是這樣定的”其實(shí)真實(shí)原因是下標(biāo)本質(zhì)上是“偏移量”。如果下標(biāo)從 1 開始地址公式就變成地址(a[i]) 首地址 (i-1) * sizeof(int)每次訪問都要多一次減法運(yùn)算。聽起來不多但在數(shù)組大規(guī)模訪問的場景下比如圖遍歷、矩陣運(yùn)算這樣一次多余的減法也是額外開銷。下標(biāo)從 0 開始意味著下標(biāo)本身就是偏移量不用做任何轉(zhuǎn)換。所以教材里說“數(shù)組的下標(biāo)是偏移量”這句話不是隨口說的它直接決定了地址計(jì)算公式的形式。我當(dāng)初在學(xué)校做實(shí)驗(yàn)的時(shí)候用二維數(shù)組模擬矩陣乘法老師讓我們憋編譯器優(yōu)化打開手動寫三層循環(huán)。當(dāng)時(shí)我就在想如果能把內(nèi)層循環(huán)的下標(biāo)計(jì)算簡化一下性能提升會很明顯。后來才理解下標(biāo)表達(dá)式寫得好不好直接決定了生成的匯編代碼質(zhì)量。雖然現(xiàn)在編譯器優(yōu)化很厲害但理解這層邏輯對你的代碼性能直覺很有幫助。1.3 多維數(shù)組的存儲行優(yōu)先還是列優(yōu)先必須搞清楚C 語言里int a[3][4]在內(nèi)存里是怎么排的答案是按行優(yōu)先row-major先存完一行再存下一行。具體來說a[0][0], a[0][1], a[0][2], a[0][3], a[1][0], a[1][1], a[1][2], a[1][3], a[2][0], a[2][1], a[2][2], a[2][3]而 Fortran 用的是列優(yōu)先。這兩種存儲方式不僅影響內(nèi)存布局也影響你寫循環(huán)時(shí)的訪問模式——a[i][j]和a[j][i]的訪問模式完全不同。如果你按列優(yōu)先的方式去訪問一個行優(yōu)先存儲的數(shù)組每次訪問都會跳著走緩存命中率會慘不忍睹。二維數(shù)組的地址公式地址(a[i][j]) 首地址 (i * 列數(shù) j) * sizeof(類型)再推廣到三維int a[L][M][N]地址(a[i][j][k]) 首地址 (i * M * N j * N k) * sizeof(類型)這個嵌套公式的模式很明顯就是一層一層展開。每次多一維就等于多一個乘積。這個公式最好不要死記而是理解“按照行優(yōu)先的順序前面所有完整行/面的元素總數(shù) 當(dāng)前行內(nèi)的偏移量”。我見過很多考研的朋友在這類“求某個數(shù)組元素地址”的題目上反復(fù)失分錯的從來不是公式是對存儲順序的理解。1.4 C語言實(shí)操數(shù)組設(shè)計(jì)里面那些“無聲的設(shè)計(jì)決策”數(shù)組的聲明在 C 語言里必須是編譯期常量這其實(shí)是個設(shè)計(jì)決策不是懶。C 語言設(shè)計(jì)時(shí)面對的是 PDP-11 這類內(nèi)存極其寶貴的機(jī)器動態(tài)長度數(shù)組需要額外的運(yùn)行時(shí)信息會顯著增加實(shí)現(xiàn)復(fù)雜度。相比之下定長數(shù)組的地址計(jì)算可以在編譯期優(yōu)化到寄存器運(yùn)算級別代價(jià)就是你必須自己管好內(nèi)存。當(dāng)然C99 引入了變長數(shù)組VLA允許int a[n]這種寫法。但在實(shí)際項(xiàng)目里VLA 不受待見——它在棧上分配大小運(yùn)行時(shí)才確定一旦n很大直接就爆棧了。我自己以前寫過一個圖像處理的 Demo用 VLA 存一張大圖的灰度值運(yùn)行到一半直接段錯誤排查了很久才發(fā)現(xiàn)是棧溢出。后來老老實(shí)實(shí)用malloc在堆上分配問題解決。這個經(jīng)歷讓我記住一件事數(shù)組的“靜態(tài)性”不是缺陷而是一種約束下的最優(yōu)選擇。你后續(xù)學(xué)棧和堆、學(xué)動態(tài)內(nèi)存管理很多套路本質(zhì)上都是在模擬“動態(tài)數(shù)組”的能力。而理解數(shù)組的靜態(tài)性是理解這一切的起點(diǎn)。2. 矩陣壓縮存儲把重復(fù)數(shù)據(jù)關(guān)進(jìn)小黑屋2.1 對稱矩陣只需要存一半實(shí)際應(yīng)用中很多矩陣是稀疏的或者有某種規(guī)則結(jié)構(gòu)。比如無向圖的鄰接矩陣一定是對稱矩陣。A[i][j] A[j][i]那存儲整個矩陣時(shí)一半空間存的是同一個數(shù)據(jù)太浪費(fèi)了。對稱矩陣壓縮的思路很簡單只存下三角部分含對角線大小從n*n變成n*(n1)/2。關(guān)鍵是下標(biāo)換算。假設(shè)我們用一維數(shù)組sa[k]存下三角的數(shù)據(jù)當(dāng)i j時(shí)k i*(i1)/2 j當(dāng)i j時(shí)利用對稱性交換i和j再套同一個公式為什么i*(i1)/2因?yàn)榍癷行第 0 行到第i-1行有1 2 ... i i*(i1)/2個元素加上第i行里第j列之前的j個元素就是當(dāng)前元素的偏移量。這公式本質(zhì)上就是等差數(shù)列求和。我在實(shí)際項(xiàng)目里真用過這個。當(dāng)時(shí)要給某個存儲受限的嵌入式環(huán)境處理一個 100x100 的對稱矩陣原始要 10KB 浮點(diǎn)數(shù)壓完變成 5050 個浮點(diǎn)數(shù)省了差不多一半空間。別小看這在嵌入式上能省下的幾百字節(jié)有時(shí)候就是能塞進(jìn)去和不能塞進(jìn)去的區(qū)別。2.2 三角矩陣和下三角的邊界情況三角矩陣分上三角、下三角兩種。下三角矩陣上三角部分全是常數(shù)通常為 0存儲方案是sa[0..n*(n1)/2] 存下三角元素 sa[n*(n1)/2] 存那個常數(shù)下標(biāo)映射和對稱矩陣下三角公式一樣。上三角矩陣則反過來k i*(2*n - i 1)/2 (j - i)這個公式看著復(fù)雜推一遍就懂了——從最后一行往上推第i行前面有多少個元素列出來數(shù)一數(shù)比背公式牢靠得多。做這類題目的時(shí)候我很推薦一個方法先畫一個 3x3 或 4x4 的小矩陣手動把每個位置的下標(biāo) K 寫出來再看規(guī)律。比單純對著公式套靠譜十倍而且真的遇到考試、面試的時(shí)候你可以現(xiàn)場推導(dǎo)不用賭自己有沒有記錯公式。2.3 帶狀矩陣的存儲方案還有一種比較常見的壓縮對象是帶狀矩陣對角矩陣非零元素只集中在主對角線附近的一兩條對角線上。比如三對角矩陣每一行最多只有 3 個非零元素。壓縮思路是按對角線存或者按行存但只存這幾個非零位置。按行存儲時(shí)地址公式Loc(a[i][j]) 首地址 (2*(i-1) (j - i 1)) * L這個公式里的2*(i-1)是前i-1行的非零元素個數(shù)第一行 2 個之后每行 3 個(j - i 1)是當(dāng)前行偏移。行業(yè)里有大量這類實(shí)際存儲模型的應(yīng)用比如有限元分析中的剛度矩陣很多就是帶狀稀疏矩陣。掌握壓縮存儲的思路不是為了考試做題而是為了讓你真正遇到內(nèi)存緊張的場景時(shí)有個明確的優(yōu)化方向。3. 稀疏矩陣當(dāng)數(shù)據(jù)大部分是零就該換個思路了3.1 怎么能判斷它該壓縮了稀疏矩陣的定義很簡單非零元素個數(shù)遠(yuǎn)遠(yuǎn)少于零元素。教材里常給一個比例比如非零元素占比小于 5% 就算稀疏。但在實(shí)際工程里真正的標(biāo)準(zhǔn)是用三元組表存儲后省下的空間是否足夠覆蓋存儲索引的開銷。三元組表的結(jié)構(gòu)C 語言定義大致長這樣#define MAXSIZE 12500 typedef struct { int i, j; // 行號、列號從1開始 ElemType e; // 非零元素值 } Triple; typedef struct { Triple data[MAXSIZE 1]; int mu, nu, tu; // 行數(shù)、列數(shù)、非零元個數(shù) } TSMatrix;特別注意編號從 1 開始data[0]經(jīng)常留作“哨兵”或不用。這種結(jié)構(gòu)下存一個非零元素需要兩個 int 和一個 ElemType通常也是 4 字節(jié)也就是 12 字節(jié)。如果原來的矩陣一個元素占 4 字節(jié)那么只有非零元素零零散散分布時(shí)三元組表才劃算。如果你的矩陣非零元太多三元組表反而比直接存完整矩陣更占空間因?yàn)闆]有省下內(nèi)存反而新增了索引開銷。3.2 三元組表的轉(zhuǎn)置為什么要搞出兩個版本轉(zhuǎn)置是稀疏矩陣最經(jīng)典的操作。原理很簡單把(i, j, e)換成(j, i, e)再保證行優(yōu)先順序即可。樸素轉(zhuǎn)置的算法邏輯掃描原矩陣的三元組表對列號j從 1 到nu每次都從原三元組表里把列號為j的元素提取出來放到轉(zhuǎn)置后的三元組表里。每個列號要完整掃描一遍原表復(fù)雜度為O(nu * tu)。如果nu很大而且tu也很大的時(shí)候這個算法完全不能用。舉個例子一個 1000 列的矩陣1 萬個非零元復(fù)雜度就是 1000 * 10000 10^7 量級雖然還不算災(zāi)難但明顯有更好的方案。快速轉(zhuǎn)置的思路是先數(shù)出每一列有多少個非零元算出每一列第一個非零元應(yīng)該放到新表的哪個位置然后一遍掃描原表把每個元素直接放到正確位置。關(guān)鍵實(shí)現(xiàn)int cpot[MAXSIZE]; // 記錄每一列第一個非零元在新表中的位置 // 第一遍統(tǒng)計(jì)各列非零元個數(shù) num[col] for (int col 1; col S.nu; col) num[col] 0; for (int t 1; t S.tu; t) num[S.data[t].j]; // 第二遍計(jì)算每列第一個非零元在新表中的位置 cpot[1] 1; for (int col 2; col S.nu; col) cpot[col] cpot[col-1] num[col-1]; // 第三遍掃描原表邊掃邊放邊更新 cpot for (int t 1; t S.tu; t) { int col S.data[t].j; int pos cpot[col]; M.data[pos].i S.data[t].j; M.data[pos].j S.data[t].i; M.data[pos].e S.data[t].e; cpot[col]; // 同一列的下一個元素順延 }這個算法的精妙之處在于cpot[col]這一句。每一次放完一個元素就把該列的“下一個可用位置”往后挪一位這樣同一列的元素自然就按行號遞增的順序排好了。時(shí)間復(fù)雜度降到了O(nu tu)。我當(dāng)初自己寫這個算法的時(shí)候總覺得cpot數(shù)組初始化很繞后來想通了它本質(zhì)上就是一個“列號 → 新表下標(biāo)”的映射函數(shù)只不過這個函數(shù)需要先掃一遍矩陣才能建立起來。建立映射的思路在以后學(xué)哈希表、學(xué)索引結(jié)構(gòu)時(shí)到處都在用。3.3 十字鏈表當(dāng)稀疏矩陣需要頻繁增刪時(shí)三元組表適合靜態(tài)矩陣。如果有一個稀疏矩陣需要不斷地插入或刪除非零元素用三元組表存儲每次增刪都要移動后面的元素代價(jià)很大。這時(shí)候該用十字鏈表。十字鏈表每個非零元素是一個結(jié)點(diǎn)有 5 個字段typedef struct OLNode { int i, j; ElemType e; struct OLNode *right, *down; // 同行后繼、同列后繼 } OLNode;所有結(jié)點(diǎn)通過right指針串成行鏈表通過down指針串成列鏈表。還要額外搞一個行頭節(jié)點(diǎn)數(shù)組和列頭節(jié)點(diǎn)數(shù)組用來記錄每一行、每一列鏈表的起始位置。這樣插入、刪除一個非零元素只需要調(diào)整所在行和所在列的鏈指針完全不需要搬移數(shù)據(jù)。不過說實(shí)話如果只是應(yīng)付課程設(shè)計(jì)十字鏈表用得不多。但如果你之后學(xué)操作系統(tǒng)、學(xué)文件系統(tǒng)里面很多組織方式都跟十字鏈表的思想沾邊。如果跟稀疏矩陣打交道的場景是幾十萬行幾十萬列的超大型矩陣直接上十字鏈表往往是最優(yōu)解。4. 廣義表遞歸的思維聽著繞但能一下打開思路4.1 廣義表的定義讓人第一次見到遞歸廣義表的定義廣義表是 nn0個元素的有限序列其中每個元素既可以是原子單個數(shù)據(jù)元素也可以是子表又是一個廣義表。注意這定義里出現(xiàn)了“廣義表”自己。這種自指式定義就叫遞歸定義。之前學(xué)的單鏈表可以叫“遞歸定義”但它的遞歸發(fā)生在表節(jié)點(diǎn)層面沒有打破“元素都是同一種數(shù)據(jù)”的假設(shè)。廣義表則徹底打破了“表的元素必須是同一類型”的限制——元素可以是不同類型甚至可以嵌套成子表。這就給數(shù)據(jù)處理帶來極大的靈活性。舉幾個典型例子F ()空表長度為 0。L (a, b)兩個原子長度為 2。A (x, (a, b))一個原子 x一個子表 (a, b)長度為 2。D ((a, b), ((c, d)))兩個子表第二個子表里又套了一個子表。這些例子的麻煩在于你要區(qū)分“長度”和“深度”。長度是看這一層有幾個元素是水平方向的概念深度是看嵌套了多少層括號是垂直方向的概念。D的表長為 2深度為 3你們可以數(shù)一下括號。4.2 表頭表尾理解廣義表的鑰匙教材里會給出兩個重要的操作定義表頭Head廣義表的第一個元素可能是原子也可能是子表表尾Tail廣義表去掉第一個元素后剩下的部分它一定是一個廣義表為什么表尾一定還是廣義表因?yàn)槿サ舯眍^后剩下的那部分依然可以看作一個元素序列也就是一個廣義表。這一點(diǎn)特別重要因?yàn)樗菑V義表遞歸處理能夠持續(xù)的根源。舉個例子L (a, b, c) Head(L) a Tail(L) (b, c)注意Tail(L)的結(jié)果仍然帶括號是(b, c)不是b, c。繼續(xù)Tail(Tail(L)) (c) Tail(Tail(Tail(L))) ()到空表為止遞歸結(jié)束。這套“取表頭、取表尾”的操作就是廣義表所有運(yùn)算的基礎(chǔ)。求表長可以一直Tail直到空表求深度也可以遞歸下去。我學(xué)的時(shí)候最大的誤區(qū)是以為Tail(L)等于(a, b)這種是保留括號后來才發(fā)現(xiàn)取出表尾必須重新組合成廣義表于是對“表尾必為表”這個性質(zhì)有了真正認(rèn)識。4.3 廣義表的存儲結(jié)構(gòu)兩種方案都得懂廣義表的元素可能是原子也可能是子表所以存儲結(jié)構(gòu)要能區(qū)分這兩類數(shù)據(jù)。常見的說法是兩種方案頭尾鏈表存儲結(jié)構(gòu)和擴(kuò)展線性鏈表存儲結(jié)構(gòu)。頭尾鏈表存儲結(jié)構(gòu)把每個廣義表結(jié)點(diǎn)分成表結(jié)點(diǎn)和原子結(jié)點(diǎn)。表結(jié)點(diǎn)包括一個標(biāo)記位和一個指針域指向“表頭”和“表尾”而原子結(jié)點(diǎn)則是標(biāo)記位加一個值域。經(jīng)典的 C 語言定義typedef enum { ATOM, LIST } ElemTag; typedef struct GLNode { ElemTag tag; // 當(dāng)前元素是原子還是子表 union { char atom; // 原子結(jié)點(diǎn)的值 struct { struct GLNode *hp; // 表頭指針 struct GLNode *tp; // 表尾指針 } ptr; } un; } GLNode;這里用了一個union因?yàn)橐粋€結(jié)點(diǎn)要么是原子要么是子表不會同時(shí)是。這個設(shè)計(jì)在數(shù)據(jù)結(jié)構(gòu)的書里是經(jīng)典案例值得反復(fù)研究。union是 C 語言里省內(nèi)存的手段同一個內(nèi)存位置可以存不同類型的值只要你自己保證當(dāng)前讀的是正確的那一類型。擴(kuò)展線性鏈表存儲結(jié)構(gòu)也差不多區(qū)別在于表結(jié)點(diǎn)里不區(qū)分表頭和表尾所有子表都按線性鏈表的“下一個元素”方式串起來。兩種方案各有優(yōu)劣考試可能考畫圖題或?qū)懰惴}需要熟練掌握其中一種并且能快速轉(zhuǎn)換成另一種。4.4 求深度、建表和遍歷遞歸一上手就有意義廣義表算法里最典型的三個求深度、求長度、復(fù)制。求深度的遞歸定義很明確int GListDepth(GLNode *L) { if (!L) return 1; // 空表深度為1 if (L-tag ATOM) return 0; // 原子深度為0 int max 0; GLNode *p L; while (p) { int d GListDepth(p-un.ptr.hp); // 遞歸求表頭深度 if (d max) max d; p p-un.ptr.tp; // 遍歷表尾 } return max 1; }邊界條件要理清楚原子結(jié)點(diǎn)深度為 0空表深度為 1非空表是“表頭深度 1”。這里有幾個約定俗成的東西需要按教材口徑來定否則很容易算錯深淺。建表的算法書里給的是CreateGList實(shí)際上就是一個遞歸建表過程遇到左括號則創(chuàng)建子表結(jié)點(diǎn)遇到原子則創(chuàng)建原子結(jié)點(diǎn)遇到逗號則繼續(xù)處理同一個表的下一個元素。整個過程本身就是一個帶狀態(tài)機(jī)的遞歸下降解析我們每個人在畢業(yè)設(shè)計(jì)里遇到嵌套 JSON 解析時(shí)這東西會再次出現(xiàn)?？吹竭@里你已經(jīng)能從廣義表里看到一個極其重要的思維轉(zhuǎn)變學(xué)樹之前先學(xué)會“遞歸描述數(shù)據(jù)”。廣義表比樹更容易理解遞歸它是遞歸定義的完美入門。如果你把這一章的遞歸算法真正寫明白了后面的二叉樹遍歷、圖的深度優(yōu)先搜索學(xué)起來會絲滑很多。5. 常見問題與排查心得5.1 地址計(jì)算題公式記得住一算就錯考試?yán)镒畛３霈F(xiàn)的坑是這幾種第一分不清行列下標(biāo)是從 0 開始還是從 1 開始。如果題目沒有明確說默認(rèn)“從 0 開始”但它經(jīng)常不按套路出牌比如“一個 n 階矩陣下標(biāo)從 1 到 n”你如果不仔細(xì)讀題直接套行優(yōu)先公式就會差一行。第二忘了sizeof。有些題目給的是“每個元素占 4 個字節(jié)”有的給“占 L 個存儲單元”有的直接問“第幾個元素”不乘單位會得出完全不一樣的東西。第三多維數(shù)組的計(jì)算會漏維度。三維數(shù)組求元素地址我建議先畫小例子比如 2x3x4 的數(shù)組手動寫出幾個元素的位置再對照公式就非常清晰。5.2 C語言數(shù)組越界編譯不會報(bào)錯運(yùn)行時(shí)才出問題C 語言數(shù)組越界是未定義行為。你寫int a[5]; a[5] 1;編譯大概率通過但運(yùn)行時(shí)會怎樣誰也不知道可能改了一個相鄰的變量、可能直接段錯誤、可能在 debug 模式下崩、在 release 模式下就靜靜躺著事情更大。排查方法往往是不確定時(shí)先檢查數(shù)組的每個循環(huán)邊界。我之前調(diào)試過一個排序模塊數(shù)據(jù)偶爾會冒出一個超大值花了很長時(shí)間排查才發(fā)現(xiàn)是冒泡排序里內(nèi)層循環(huán)某個下標(biāo)多走了一步越界寫到了相鄰數(shù)組的第一個元素上在特定數(shù)據(jù)規(guī)模下才復(fù)現(xiàn)。這個問題用 ASANAddressSanitizer一跑就抓出來了。如果你在做 C 項(xiàng)目編譯時(shí)記得加-fsanitizeaddress這個工具能抓住很多只在運(yùn)行時(shí)才現(xiàn)形的越界。5.3 稀疏矩陣轉(zhuǎn)置效率換空間的取舍快速轉(zhuǎn)置算法的代價(jià)是引入輔助數(shù)組num[]和cpot[]額外空間開銷 O(nu)。如果矩陣列數(shù)極大比如 10 萬列額外 10 萬個 int也就是 400KB在某些單片機(jī)環(huán)境下可能就撐不住了。所以需要根據(jù)實(shí)際矩陣規(guī)模來判斷該用樸素轉(zhuǎn)置還是快速轉(zhuǎn)置。極端情況下如果矩陣非零元數(shù)量極小比如 100 個樸素轉(zhuǎn)置O(nu*tu)可能反而更省時(shí)間——因?yàn)閠u太小多掃幾遍也沒多少開銷。數(shù)據(jù)規(guī)模不同最優(yōu)解就不同這是很多教程不會教你的經(jīng)驗(yàn)。算法分析課教的是漸近復(fù)雜度但實(shí)際優(yōu)化要考慮常數(shù)項(xiàng)和存儲代價(jià)。5.4 廣義表遞歸的邊界條件永遠(yuǎn)是第一優(yōu)先級寫廣義表遞歸算法最常見的報(bào)錯是無限遞歸導(dǎo)致棧溢出。根子出在邊界沒寫對或者遞歸推進(jìn)寫錯了。寫遞歸的基本三要素明確終止條件空表、原子明確遞歸推進(jìn)方向取表頭或表尾表會變小先處理終止再處理推進(jìn)順序不能反另外廣義表可以根據(jù)需要一個元素一個元素地構(gòu)建但產(chǎn)出順序跟讀取順序不一定一樣。有些考試題目問“構(gòu)造廣義表的過程”本質(zhì)上就是遞歸入棧和出棧的過程建議在紙上手動模擬一遍遞歸調(diào)用棧印象會非常深。還有一種情況是廣義表里面出現(xiàn)“共享子表”——多個地方引用了同一個子表存儲結(jié)構(gòu)用指針的話可能會形成環(huán)遍歷時(shí)就死循環(huán)了。如果出現(xiàn)這種現(xiàn)象去查一下是否有人在創(chuàng)建子表時(shí)多次調(diào)用同一個指針而沒有refcount一類的引用計(jì)數(shù)這個坑在系統(tǒng)設(shè)計(jì)里很經(jīng)典。寫在最后的幾點(diǎn)體會這一章學(xué)完之后我自己的感受是數(shù)組不難難的是理解它背后的存儲邏輯和代價(jià)廣義表不難難的是第一次接觸遞歸定義時(shí)的思維轉(zhuǎn)換。很多時(shí)候我們覺得數(shù)據(jù)結(jié)構(gòu)“難”不是因?yàn)榇a寫不出來而是因?yàn)槟X子里沒有建立起對“數(shù)據(jù)在內(nèi)存里如何組織”的直觀認(rèn)識。我建議你把數(shù)組的地址公式、對稱矩陣的壓縮、稀疏矩陣的快速轉(zhuǎn)置、廣義表的求深度這四件事都用手工模擬跑一遍——寫在紙上畫出來拿個小矩陣自己算一遍。這個過程花不了多長時(shí)間但它建立的直覺會讓后面學(xué)習(xí)二叉樹、圖、查找表時(shí)受益無窮。實(shí)際寫代碼的時(shí)候如果遇到越界、爆棧、內(nèi)存占用過高回頭想一想這一章的存儲模型很多問題自然就有排查方向了。