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