矩陣壓縮存儲(chǔ)這一章很多同學(xué)學(xué)的時(shí)候覺得“公式記一下就行”結(jié)果一到做題就翻車題目里明明寫的是上三角矩陣你按對(duì)稱矩陣的公式去套題目說的是按列優(yōu)先存儲(chǔ)你按行優(yōu)先去算題目里數(shù)組下標(biāo)從 1 開始你默認(rèn)從 0 開始最后算出來的地址差了整整一個(gè)元素。作為數(shù)據(jù)結(jié)構(gòu)里性價(jià)比極高的一塊內(nèi)容矩陣壓縮存儲(chǔ)既不像樹和圖那樣需要大量代碼訓(xùn)練也不像排序算法那樣考驗(yàn)復(fù)雜度分析但它幾乎是考研 408、期末考和軟考選擇題的“必考送分題”。前提是你真的理解了下標(biāo)換算的來龍去脈而不是背公式。這篇文章圍繞三個(gè)問題展開什么樣的矩陣值得壓縮存儲(chǔ)壓縮之后一維下標(biāo)怎么換算這些知識(shí)點(diǎn)在考試和項(xiàng)目里分別怎么用我會(huì)把對(duì)稱矩陣、三角矩陣、三對(duì)角矩陣和稀疏矩陣四種情況逐一拆解給出公式推導(dǎo)過程和可直接運(yùn)行的 C 語言示例代碼。先給一個(gè)明確判斷如果你只背公式不清楚“為什么對(duì)稱矩陣只存 n(n1)/2 個(gè)元素”“為什么三對(duì)角矩陣只需要 3n-2 個(gè)存儲(chǔ)單元”那么換一個(gè)問法你大概率還會(huì)錯(cuò)。矩陣壓縮存儲(chǔ)的本質(zhì)是一個(gè)映射關(guān)系——把邏輯上的二維坐標(biāo)映射到物理上的一維下標(biāo)。搞清楚這個(gè)映射公式不用背也能推出來。1. 矩陣壓縮存儲(chǔ)到底解決了什么問題先回到一個(gè)實(shí)際場景。假設(shè)你在做一個(gè)地圖應(yīng)用城市之間有公路相連你想用一個(gè)矩陣表示“任意兩個(gè)城市之間是否連通”這就是圖的鄰接矩陣。如果城市數(shù)量是 1000二維數(shù)組需要 1000×1000 個(gè)存儲(chǔ)單元但一個(gè)無向圖的鄰接矩陣一定是對(duì)稱的——i 到 j 連通等價(jià)于 j 到 i 連通。也就是說大約一半的元素是冗余的。再看數(shù)值計(jì)算領(lǐng)域。有限元分析、偏微分方程求解中經(jīng)常出現(xiàn)“稀疏矩陣”矩陣規(guī)?？赡苁?100 萬×100 萬但每一行非零元素只有個(gè)位數(shù)。如果老老實(shí)實(shí)開一個(gè)二維數(shù)組內(nèi)存直接爆炸但如果只存非零元素整個(gè)矩陣可能只占原來存儲(chǔ)空間的萬分之一。這就是矩陣壓縮存儲(chǔ)要解決的核心問題在邏輯上仍然把數(shù)據(jù)看作一個(gè)完整的矩陣但在物理上通過“跳過重復(fù)元素”和“跳過零元素”來節(jié)省存儲(chǔ)空間。具體收益有三點(diǎn)空間節(jié)省。對(duì)稱矩陣能省接近一半稀疏矩陣的節(jié)省效果更是數(shù)量級(jí)的。訪存效率。一維數(shù)組是連續(xù)存儲(chǔ)對(duì) CPU 緩存更友好順序遍歷時(shí)比二維數(shù)組尤其是“數(shù)組指針數(shù)組”那種實(shí)現(xiàn)更高效。傳輸與落地。在嵌入式設(shè)備、帶寬受限的場景里壓縮后的數(shù)據(jù)體積更小傳輸和持久化都更快。但也不是所有矩陣都適合壓縮。如果矩陣維度很小比如 3×3 的變換矩陣壓縮后反而要額外維護(hù)一行映射邏輯屬于得不償失。再比如頻繁寫操作的場景壓縮存儲(chǔ)通常只擅長“按坐標(biāo)讀取”寫入某個(gè)位置可能需要付出額外換算代價(jià)。這個(gè)邊界要心里有數(shù)。2. 基礎(chǔ)概念特殊矩陣、壓縮存儲(chǔ)與下標(biāo)體系2.1 什么是特殊矩陣數(shù)據(jù)結(jié)構(gòu)里討論的矩陣壓縮針對(duì)的是幾類“有規(guī)律”的矩陣矩陣類型特征可省略的元素對(duì)稱矩陣a[i][j] a[j][i]上三角或下三角的一半重復(fù)元素上三角矩陣下三角區(qū)域全為常數(shù)或零下三角區(qū)域的重復(fù)/零元素下三角矩陣上三角區(qū)域全為常數(shù)或零上三角區(qū)域的重復(fù)/零元素三對(duì)角矩陣除主對(duì)角線及相鄰兩條對(duì)角線外全為零遠(yuǎn)離主對(duì)角線的零元素稀疏矩陣非零元數(shù)量遠(yuǎn)小于總元素?cái)?shù)量大量零元素注意一個(gè)容易混淆的點(diǎn)三角矩陣的“下三角區(qū)域全為常數(shù)”和“下三角區(qū)域全為零”在存儲(chǔ)策略上有細(xì)微差別。如果下三角區(qū)域都是同一個(gè)常數(shù) c那么只需要額外存一個(gè) c如果都是零那么零元素根本不占存儲(chǔ)空間。2.2 什么是壓縮存儲(chǔ)壓縮存儲(chǔ)的定義可以概括為對(duì)多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)單元對(duì)零元素不分配存儲(chǔ)單元。注意這里有兩條不同的邏輯——對(duì)稱矩陣靠“值相同”壓掉重復(fù)元素稀疏矩陣靠“值為零”壓掉無效元素。前者損失的是冗余后者損失的是零。壓縮存儲(chǔ)后的數(shù)據(jù)仍然要支持隨機(jī)訪問也就是說給定一個(gè)矩陣坐標(biāo)你要能算出它在一維數(shù)組里的位置。這個(gè)計(jì)算過程就是“地址映射”也是考試最容易丟分的地方。2.3 行優(yōu)先與列優(yōu)先先搞清楚規(guī)則再套公式矩陣在邏輯上是二維的但內(nèi)存是一維的所以必須約定一個(gè)“展開順序”。行優(yōu)先先存第一行再存第二行依次往下。C 語言的二維數(shù)組就是行優(yōu)先。列優(yōu)先先存第一列再存第二列依次往右。Fortran、MATLAB 默認(rèn)是列優(yōu)先。很多題目不會(huì)直接告訴你“按行優(yōu)先存儲(chǔ)”而是用“按行展開”“以行序?yàn)橹餍颉薄耙粤行驗(yàn)橹餍颉边@類說法。做題第一步永遠(yuǎn)是判斷這個(gè)。另外還要搞清楚下標(biāo)起點(diǎn)。嚴(yán)蔚敏版《數(shù)據(jù)結(jié)構(gòu)》的公式里矩陣下標(biāo)通常從 1 開始一維數(shù)組 SA 的下標(biāo)從 0 開始但不同教材、不同題目可能不一樣。最穩(wěn)妥的做法是拿到題目先確定三件事——矩陣下標(biāo)從幾開始、數(shù)組下標(biāo)從幾開始、按行還是按列。3. 對(duì)稱矩陣壓縮原理、公式與易錯(cuò)點(diǎn)3.1 為什么只存一半就夠了對(duì)稱矩陣滿足 a[i][j] a[j][i]也就是說上三角區(qū)域的每個(gè)元素在下三角區(qū)域都有一個(gè)一模一樣的“鏡像”。既然值相同就沒必要存兩份。按行優(yōu)先原則只存下三角含主對(duì)角線4×4 對(duì)稱矩陣的存儲(chǔ)順序如下a[1][1] a[2][1] a[2][2] a[3][1] a[3][2] a[3][3] a[4][1] a[4][2] a[4][3] a[4][4]n 階對(duì)稱矩陣需要存儲(chǔ)的元素個(gè)數(shù)是1 2 3 ... n n(n1)/2這一行累計(jì)求和就是整個(gè)對(duì)稱矩陣壓縮存儲(chǔ)公式的來源。3.2 地址計(jì)算公式推導(dǎo)假設(shè)矩陣下標(biāo)從 1 開始一維數(shù)組 SA 下標(biāo)從 0 開始按行優(yōu)先只存下三角?，F(xiàn)在要存 a[i][j]且 i ≥ j。先算它前面有多少個(gè)元素第 1 行到第 i-1 行是完整的下三角元素個(gè)數(shù)為 1 2 ... (i-1) i(i-1)/2。第 i 行從第 1 列到第 j 列共有 j 個(gè)元素因?yàn)橹淮嫦氯堑?i 行到第 j 列為止。所以 a[i][j] 在一維數(shù)組中的下標(biāo)0-based為k i(i-1)/2 j - 1如果題目問的是字節(jié)地址假設(shè)元素占 L 個(gè)字節(jié)首元素地址為 LOC(a[1][1])則LOC(a[i][j]) LOC(a[1][1]) [i(i-1)/2 j - 1] × L當(dāng) i j 時(shí)利用對(duì)稱性把它交換成 j,i 再代入公式即可。這里有一個(gè)高頻坑如果矩陣下標(biāo)從 0 開始公式會(huì)變成 k i(i1)/2 ji ≥ j。很多同學(xué)把 1-based 的公式直接套到 0-based 的題目里一錯(cuò)就是一片。做題時(shí)先把行號(hào)列號(hào)統(tǒng)一到公式要求的體系里。3.3 對(duì)稱矩陣的還原從一維數(shù)組還原成二維矩陣時(shí)下三角直接讀上三角通過“對(duì)稱鏡像”補(bǔ)上if (i j) { mat[i][j] sa[i * (i 1) / 2 j]; // 0-based 版本 } else { mat[i][j] sa[j * (j 1) / 2 i]; }實(shí)際項(xiàng)目里如果你只是想省內(nèi)存這種還原邏輯完全正確但如果是數(shù)值計(jì)算場景更推薦用 BLAS/LAPACK 等專業(yè)庫它們會(huì)針對(duì)對(duì)稱矩陣做更精細(xì)的優(yōu)化而不是簡單省一半內(nèi)存。4. 三角矩陣壓縮上三角、下三角與常量元素4.1 下三角矩陣下三角矩陣的規(guī)則是上三角區(qū)域的元素全為同一個(gè)常數(shù) c或者全為 0。如果全為 c存儲(chǔ)時(shí)只需要在存完下三角的 n(n1)/2 個(gè)元素之后再單獨(dú)存一個(gè) c?？偞鎯?chǔ)單元數(shù)為n(n1)/2 1一維數(shù)組的最后一個(gè)位置存的就是那個(gè)常量 c。如果是全為 0 的情況連這個(gè)常量都不需要存。下三角矩陣 a[i][j]i ≥ j的下標(biāo)公式和對(duì)稱矩陣下三角部分完全一樣k i(i-1)/2 j - 1當(dāng) i j 時(shí)元素值就是常量 c不需要通過公式定位。4.2 上三角矩陣公式推導(dǎo)上三角矩陣是“下三角區(qū)域全為常數(shù)”存儲(chǔ)上三角部分同樣按行優(yōu)先。先看存儲(chǔ)順序4×4 上三角矩陣按行優(yōu)先存儲(chǔ)為a[1][1] a[1][2] a[1][3] a[1][4] a[2][2] a[2][3] a[2][4] a[3][3] a[3][4] a[4][4]元素個(gè)數(shù)仍然是 n(n1)/2另加一個(gè)常量 c?，F(xiàn)在計(jì)算 a[i][j]i ≤ j前面有多少個(gè)元素第 1 行到第 i-1 行每行元素個(gè)數(shù)分別是 n、n-1、...、n-(i-2)求和得到 (i-1)(2n - i 2)/2。第 i 行從第 i 列到第 j 列共有 j - i 個(gè)元素不含 a[i][i] 本身。所以k (i-1)(2n - i 2)/2 (j - i)這個(gè)公式看起來比對(duì)稱矩陣復(fù)雜但推導(dǎo)思路完全一致先算前面整行的元素總數(shù)再加上本行內(nèi)目標(biāo)的偏移量。4.3 上三角與下三角的對(duì)比很多同學(xué)記混這兩個(gè)公式建議這樣區(qū)分下三角矩陣行號(hào)決定“前面有多少個(gè)完整的短行”核心是 12...i 的累加。上三角矩陣行號(hào)決定“前面有哪些從長到短的整行”核心是等差數(shù)列求和每行長度從 n 開始遞減。可以先用一個(gè) 3×3 的例子手算一遍上三角矩陣 a[2][3] 的下標(biāo)按上面公式 k (2-1)(2×3 - 2 2)/2 (3-2) (1×6)/2 1 4對(duì)應(yīng)數(shù)組里第 5 個(gè)元素0-based 下標(biāo) 4正好是存儲(chǔ)順序里的 a[2][3]。手算一次能理解比背公式有用得多。5. 三對(duì)角矩陣與稀疏矩陣的存儲(chǔ)方案5.1 三對(duì)角矩陣帶狀存儲(chǔ)三對(duì)角矩陣是帶狀矩陣的一種特例除主對(duì)角線、主對(duì)角線正上方的次對(duì)角線和正下方的次對(duì)角線外其余元素全為 0。也就是說只有滿足 |i - j| ≤ 1 的位置才可能有非零值。每行最多 3 個(gè)非零元素首行和末行只有 2 個(gè)因此 n 階三對(duì)角矩陣的非零元素總數(shù)為2 3(n-2) 2 3n - 2按行優(yōu)先存儲(chǔ)時(shí)一維數(shù)組里的排列是a[1][1] a[1][2] a[2][1] a[2][2] a[2][3] a[3][2] a[3][3] a[3][4] ...坐標(biāo)到一維下標(biāo)的換算公式矩陣下標(biāo) 1-based數(shù)組下標(biāo) 0-basedk 2i j - 3驗(yàn)證一下a[2][3] → k 4 3 - 3 4數(shù)組里第 5 個(gè)位置正確。a[3][2] → k 6 2 - 3 5數(shù)組里第 6 個(gè)位置正確。如果題目給的是 1-based 數(shù)組下標(biāo)公式變成 K 2i j - 2。這類“差 1”的問題就是命題老師最喜歡的陷阱。5.2 稀疏矩陣三元組順序表當(dāng)矩陣中非零元素的個(gè)數(shù)遠(yuǎn)小于零元素個(gè)數(shù)時(shí)一般稱為稀疏矩陣。寬松的判斷標(biāo)準(zhǔn)是非零元占比低于 5%嚴(yán)格一點(diǎn)的教材用“稀疏因子”來定義。稀疏矩陣不能再用“跳過固定位置”的思路壓縮因?yàn)榉橇阍氐奈恢脹]有規(guī)律。常用的存儲(chǔ)方案是三元組順序表每個(gè)非零元素用一個(gè)三元組記錄 (行號(hào), 列號(hào), 值)所有三元組按行優(yōu)先順序存放在數(shù)組中。#define MAXSIZE 100 typedef struct { int row; // 行號(hào)從 1 開始 int col; // 列號(hào)從 1 開始 int value; // 元素值 } Triple; typedef struct { Triple data[MAXSIZE]; int mu; // 矩陣總行數(shù) int nu; // 矩陣總列數(shù) int tu; // 非零元個(gè)數(shù) } TSMatrix;三元組表的核心代價(jià)是節(jié)省了空間但失去了隨機(jī)訪問能力。想讀某個(gè)坐標(biāo)需要順序查找三元組想修改某個(gè)位置需要先找到它再改。這就是“用空間換來的確定性又用時(shí)間還了回去”。更復(fù)雜的十字鏈表可以支持矩陣在動(dòng)態(tài)變化中高效插入和刪除非零元素但它犧牲了數(shù)組的局部性實(shí)現(xiàn)也明顯更復(fù)雜?？荚囈匀M為主項(xiàng)目里則要看具體場景——靜態(tài)矩陣用三元組或直接上專業(yè)庫動(dòng)態(tài)矩陣才需要考慮十字鏈表。6. 完整示例C 語言實(shí)現(xiàn)矩陣壓縮與還原6.1 環(huán)境說明下面代碼用標(biāo)準(zhǔn) C 編寫不依賴第三方庫。操作系統(tǒng)不限Linux/macOS 下用 gcc 編譯Windows 下用 MinGW 或 VS 的 C 環(huán)境都可以。重點(diǎn)演示的是壓縮存儲(chǔ)的核心映射邏輯。6.2 對(duì)稱矩陣的壓縮、取值與還原// 文件路徑symmetric_matrix.c #include stdio.h #define N 4 // 按行優(yōu)先壓縮對(duì)稱矩陣只存下三角含對(duì)角線 // mat 為 n x n 對(duì)稱矩陣sa 為一維數(shù)組 // 返回實(shí)際存入的元素個(gè)數(shù) int compress_symmetric(int mat[N][N], int n, int sa[]) { int k 0; for (int i 0; i n; i) { for (int j 0; j i; j) { sa[k] mat[i][j]; } } return k; } // 按坐標(biāo)取值i、j 從 1 開始自動(dòng)處理上三角區(qū)域 int get_symmetric(int sa[], int n, int i, int j) { if (i j) { int tmp i; i j; j tmp; } int k i * (i - 1) / 2 j - 1; return sa[k]; } // 從一維數(shù)組還原出完整對(duì)稱矩陣 void restore_symmetric(int sa[], int n, int restored[N][N]) { int k 0; for (int i 0; i n; i) { for (int j 0; j i; j) { restored[i][j] sa[k]; restored[j][i] sa[k]; k; } } } int main() { int mat[N][N] { {1, 2, 3, 4}, {2, 5, 6, 7}, {3, 6, 8, 9}, {4, 7, 9, 10} }; int sa[N * (N 1) / 2]; int cnt compress_symmetric(mat, N, sa); printf(壓縮后一維數(shù)組\n); for (int k 0; k cnt; k) { printf(%d , sa[k]); } printf(\n元素個(gè)數(shù) %d理論值 %d\n, cnt, N * (N 1) / 2); printf(\n坐標(biāo)取值驗(yàn)證\n); printf(get_symmetric(sa, 4, 4, 2) %d原矩陣 mat[3][1] %d\n, get_symmetric(sa, N, 4, 2), mat[3][1]); printf(get_symmetric(sa, 4, 2, 4) %d原矩陣 mat[1][3] %d\n, get_symmetric(sa, N, 2, 4), mat[1][3]); int restored[N][N]; restore_symmetric(sa, N, restored); printf(\n還原驗(yàn)證\n); printf(restored[0][2] %drestored[2][0] %d\n, restored[0][2], restored[2][0]); return 0; }這段代碼里的get_symmetric就是公式的落地實(shí)現(xiàn)。注意傳入的行號(hào)列號(hào)是 1-based符合教材習(xí)慣如果到了項(xiàng)目里接口暴露給外部調(diào)用建議在接口層做一次轉(zhuǎn)換避免讓調(diào)用方去記下標(biāo)約定。6.3 上三角矩陣的壓縮與取值// 文件路徑upper_triangular_matrix.c #include stdio.h #define N 4 // 按行優(yōu)先壓縮上三角矩陣最后額外存一個(gè)常量 c int compress_upper(int mat[N][N], int n, int sa[]) { int k 0; for (int i 0; i n; i) { for (int j i; j n; j) { sa[k] mat[i][j]; } } sa[k] 0; // 常量 c這里用 0 演示 return k; } // 取值i、j 從 1 開始 // 如果坐標(biāo)在下三角區(qū)域i j返回常量 c int get_upper(int sa[], int n, int i, int j) { if (i j) { return sa[n * (n 1) / 2]; // 常量 c 存在最后一個(gè)位置 } int k (i - 1) * (2 * n - i 2) / 2 (j - i); return sa[k]; } int main() { int mat[N][N] { {1, 2, 3, 4}, {0, 5, 6, 7}, {0, 0, 8, 9}, {0, 0, 0, 10} }; int sa[N * (N 1) / 2 1]; int cnt compress_upper(mat, N, sa); printf(上三角壓縮后一維數(shù)組\n); for (int k 0; k cnt; k) { printf(%d , sa[k]); } printf(\n元素個(gè)數(shù) %d理論值 %d\n, cnt, N * (N 1) / 2 1); printf(\n坐標(biāo)取值驗(yàn)證\n); printf(get_upper(sa, 4, 2, 3) %d原矩陣 mat[1][2] %d\n, get_upper(sa, N, 2, 3), mat[1][2]); printf(get_upper(sa, 4, 3, 1) %d下三角常量\n, get_upper(sa, N, 3, 1)); return 0; }注意compress_upper里第 12 行的邏輯常量 c 存在一維數(shù)組的最后一個(gè)位置所以取值時(shí)判斷i j就直接返回這個(gè)常量。這里的“0”只是演示用實(shí)際項(xiàng)目中常量可能是任意值。6.4 三對(duì)角矩陣的壓縮與取值// 文件路徑tridiagonal_matrix.c #include stdio.h #include stdlib.h #define N 5 // 按行優(yōu)先壓縮三對(duì)角矩陣返回元素個(gè)數(shù) int compress_tridiag(int mat[N][N], int n, int sa[]) { int k 0; for (int i 0; i n; i) { for (int j 0; j n; j) { if (abs(i - j) 1) { sa[k] mat[i][j]; } } } return k; } // 取值i、j 從 1 開始 // 如果位置不在三條對(duì)角線上返回 0 int get_tridiag(int sa[], int n, int i, int j) { if (abs(i - j) 1) { return 0; } int k 2 * i j - 3; // 0-based return sa[k]; } int main() { int mat[N][N] { {1, 2, 0, 0, 0}, {3, 4, 5, 0, 0}, {0, 6, 7, 8, 0}, {0, 0, 9, 10, 11}, {0, 0, 0, 12, 13} }; int sa[3 * N - 2]; int cnt compress_tridiag(mat, N, sa); printf(三對(duì)角壓縮后一維數(shù)組\n); for (int k 0; k cnt; k) { printf(%d , sa[k]); } printf(\n元素個(gè)數(shù) %d理論值 %d\n, cnt, 3 * N - 2); printf(\n坐標(biāo)取值驗(yàn)證\n); printf(get_tridiag(sa, 5, 3, 2) %d原矩陣 mat[2][1] %d\n, get_tridiag(sa, N, 3, 2), mat[2][1]); printf(get_tridiag(sa, 5, 5, 1) %d不在三條對(duì)角線上\n, get_tridiag(sa, N, 5, 1)); return 0; }6.5 稀疏矩陣三元組表示與轉(zhuǎn)置// 文件路徑sparse_matrix.c #include stdio.h #define MAXSIZE 100 typedef struct { int row; int col; int value; } Triple; typedef struct { Triple data[MAXSIZE]; int mu; // 總行數(shù) int nu; // 總列數(shù) int tu; // 非零元個(gè)數(shù) } TSMatrix; // 普通轉(zhuǎn)置按列掃描三元組表 void transpose(TSMatrix M, TSMatrix *T) { T-mu M.nu; T-nu M.mu; T-tu M.tu; if (T-tu 0) { return; } int q 0; for (int col 1; col M.nu; col) { for (int p 0; p M.tu; p) { if (M.data[p].col col) { T-data[q].row M.data[p].col; T-data[q].col M.data[p].row; T-data[q].value M.data[p].value; q; } } } } void print_matrix(TSMatrix M) { printf(三元組表row, col, value\n); for (int i 0; i M.tu; i) { printf((%d, %d, %d)\n, M.data[i].row, M.data[i].col, M.data[i].value); } } int main() { TSMatrix M, T; M.mu 3; M.nu 4; M.tu 4; M.data[0].row 1; M.data[0].col 2; M.data[0].value 10; M.data[1].row 1; M.data[1].col 4; M.data[1].value 12; M.data[2].row 2; M.data[2].col 1; M.data[2].value 5; M.data[3].row 3; M.data[3].col 3; M.data[3].value 8; printf(原矩陣\n); print_matrix(M); transpose(M, T); printf(\n轉(zhuǎn)置后\n); print_matrix(T); return 0; }注意一個(gè)細(xì)節(jié)普通轉(zhuǎn)置的時(shí)間復(fù)雜度是 O(nu × tu)如果矩陣的列很多、非零元也很多這個(gè)代價(jià)會(huì)很高?？荚?yán)镞€有一個(gè)進(jìn)階考點(diǎn)是“快速轉(zhuǎn)置”它先用兩個(gè)數(shù)組統(tǒng)計(jì)每列非零元個(gè)數(shù)和每列第一個(gè)非零元在轉(zhuǎn)置表中的起始位置把時(shí)間復(fù)雜度降到 O(nu tu)。7. 運(yùn)行結(jié)果與驗(yàn)證方法7.1 編譯與運(yùn)行分別編譯運(yùn)行上面的代碼gcc symmetric_matrix.c -o symmetric_matrix ./symmetric_matrixgcc upper_triangular_matrix.c -o upper_triangular_matrix ./upper_triangular_matrixgcc tridiagonal_matrix.c -o tridiagonal_matrix ./tridiagonal_matrixgcc sparse_matrix.c -o sparse_matrix ./sparse_matrix7.2 預(yù)期輸出對(duì)稱矩陣示例的關(guān)鍵輸出壓縮后一維數(shù)組 1 2 5 3 6 8 4 7 9 10 元素個(gè)數(shù) 10理論值 10 坐標(biāo)取值驗(yàn)證 get_symmetric(sa, 4, 4, 2) 7原矩陣 mat[3][1] 7 get_symmetric(sa, 4, 2, 4) 7原矩陣 mat[1][3] 7上三角矩陣示例的關(guān)鍵輸出上三角壓縮后一維數(shù)組 1 2 3 4 5 6 7 8 9 10 0 元素個(gè)數(shù) 11理論值 11 坐標(biāo)取值驗(yàn)證 get_upper(sa, 4, 2, 3) 6原矩陣 mat[1][2] 6 get_upper(sa, 4, 3, 1) 0下三角常量三對(duì)角矩陣示例的關(guān)鍵輸出三對(duì)角壓縮后一維數(shù)組 1 2 3 4 5 6 7 8 9 10 11 12 13 元素個(gè)數(shù) 13理論值 13 坐標(biāo)取值驗(yàn)證 get_tridiag(sa, 5, 3, 2) 6原矩陣 mat[2][1] 6 get_tridiag(sa, 5, 5, 1) 0不在三條對(duì)角線上7.3 如何判斷成功判斷標(biāo)準(zhǔn)很簡單用get_*函數(shù)隨機(jī)取幾個(gè)坐標(biāo)和原矩陣對(duì)應(yīng)位置的值逐一對(duì)比。如果全部一致說明“壓縮-取值”這條鏈路是對(duì)的再用還原函數(shù)把一維數(shù)組還原成二維矩陣整體對(duì)比原矩陣說明“壓縮-還原”閉環(huán)成立。如果輸出不對(duì)第一步去看下標(biāo)換算打印出每個(gè)坐標(biāo)換算出的 k 值手工在紙上推一遍存儲(chǔ)順序確認(rèn)是不是“差 1”的問題。8. 考題拆解與常見問題排查8.1 典型考題一對(duì)稱矩陣坐標(biāo)換算題目設(shè)有一個(gè) 10×10 的對(duì)稱矩陣 A按行優(yōu)先只存下三角含對(duì)角線存入一維數(shù)組 SA下標(biāo)從 0 開始。若行號(hào)和列號(hào)均從 1 開始編號(hào)則 A[6][4] 對(duì)應(yīng)的存儲(chǔ)下標(biāo)是多少拆解A[6][4] 中 6 4位于下三角直接用公式k 6 × 5 / 2 4 - 1 15 3 18答案是 18。驗(yàn)算前 5 行共 1234515 個(gè)元素第 6 行從第 1 列到第 4 列還有 4 個(gè)元素按 0-based 下標(biāo) 154-118。8.2 典型考題二上三角矩陣求地址題目一個(gè) n 階上三角矩陣按行優(yōu)先壓縮存儲(chǔ)元素占 L 個(gè)字節(jié)首元素 A[1][1] 的地址是 LOC(A[1][1])求 A[i][j]i ≤ j的地址。拆解這就是直接考公式。先把偏移量算出來offset (i-1)(2n - i 2)/2 (j - i)再乘元素大小LOC(A[i][j]) LOC(A[1][1]) offset × L注意題目里“A[1][1] 的地址”是首地址不是 SA[0] 的值所以不需要再加一。如果題目把數(shù)組下標(biāo)寫成從 1 開始比如“A[1][2] 存在 SA[1]”那么公式里的 offset 要整體加 1這一步最容易出錯(cuò)。8.3 典型考題三三對(duì)角矩陣題目一個(gè) 5 階三對(duì)角矩陣按行優(yōu)先壓縮存入一維數(shù)組矩陣下標(biāo)和數(shù)組下標(biāo)都從 1 開始A[3][2] 存儲(chǔ)在數(shù)組的哪個(gè)位置拆解i3j2滿足 |i-j|1用 1-based 公式K 2 × 3 2 - 2 6答案是第 6 個(gè)位置。注意題目說的是“第幾個(gè)位置”也就是 1-based 下標(biāo)所以用 K 2i j - 2如果題目問“數(shù)組下標(biāo)”并且數(shù)組從 0 開始那才是 2i j - 3。8.4 常見問題排查表問題現(xiàn)象可能原因排查方式解決方案計(jì)算結(jié)果總是比答案大 1數(shù)組下標(biāo)從 0 開始卻套用了 1-based 公式重新確認(rèn)題目下標(biāo)起點(diǎn)統(tǒng)一轉(zhuǎn)換后再套公式對(duì)稱矩陣讀取上三角元素錯(cuò)誤沒有交換坐標(biāo)打印 i、j 是否做了鏡像處理先判斷 i j 再交換上三角矩陣返回了奇怪的大數(shù)訪問了下三角區(qū)域且未判斷越界檢查是否存在 i j 的調(diào)用增加 if (i j) 返回常量三對(duì)角矩陣坐標(biāo)換算不對(duì)用了對(duì)稱矩陣公式驗(yàn)證 k 2i j - 3 的手算結(jié)果用行列的前綴元素累加驗(yàn)算稀疏矩陣轉(zhuǎn)置順序不正確普通轉(zhuǎn)置邏輯里沒有按列掃描檢查轉(zhuǎn)置結(jié)果是否按行優(yōu)先按原矩陣列序掃描三元組表9. 最佳實(shí)踐與學(xué)習(xí)建議9.1 做題習(xí)慣做任何矩陣壓縮存儲(chǔ)的題目先寫三個(gè)決定1. 行優(yōu)先還是列優(yōu)先 2. 矩陣下標(biāo)從 0 還是 1 開始 3. 數(shù)組下標(biāo)從 0 還是 1 開始這三件事確定后再套公式。寧可多花 10 秒確認(rèn)也不要算到一半才發(fā)現(xiàn)方向錯(cuò)了。9.2 代碼實(shí)踐建議實(shí)際項(xiàng)目中優(yōu)先考慮成熟的線性代數(shù)庫。Eigen、BLAS、LAPACK 對(duì)對(duì)稱矩陣、帶狀矩陣、稀疏矩陣都有高度優(yōu)化的實(shí)現(xiàn)自己實(shí)現(xiàn)壓縮存儲(chǔ)容易出現(xiàn)以下問題只優(yōu)化了空間沒優(yōu)化訪存模式性能反而下降。邊界條件考慮不全比如三對(duì)角矩陣首行末行只有兩個(gè)元素。并發(fā)寫入場景下坐標(biāo)換算和數(shù)組擴(kuò)容的線程安全問題。自己實(shí)現(xiàn)壓縮存儲(chǔ)最有價(jià)值的場景是嵌入式開發(fā)、教學(xué)實(shí)驗(yàn)、或者你確實(shí)需要在某個(gè)特定數(shù)據(jù)布局下做極致優(yōu)化。9.3 學(xué)習(xí)路徑建議如果考研建議把矩陣壓縮存儲(chǔ)和圖的鄰接矩陣聯(lián)系起來復(fù)習(xí)。圖的鄰接矩陣天然是對(duì)稱的考試中經(jīng)常出現(xiàn)“用一維數(shù)組存儲(chǔ)鄰接矩陣判斷兩個(gè)頂點(diǎn)是否相鄰”的題目本質(zhì)上就是對(duì)稱矩陣壓縮存儲(chǔ)的應(yīng)用。如果準(zhǔn)備面試可以額外思考一個(gè)問題壓縮存儲(chǔ)后的矩陣如何支持高效的遍歷對(duì)稱矩陣按行遍歷一維數(shù)組時(shí)怎么保證每個(gè)鏡像元素只輸出一次這個(gè)問題能答清楚說明你不是背公式而是真的理解了映射關(guān)系。9.4 一個(gè)容易忽略的點(diǎn)壓縮存儲(chǔ)并沒有改變矩陣的邏輯結(jié)構(gòu)它只是改變了物理存儲(chǔ)布局。因此任何依賴“矩陣坐標(biāo)”的操作讀取、寫入、遍歷、轉(zhuǎn)置都需要通過映射函數(shù)完成。寫代碼時(shí)建議把所有映射函數(shù)集中放在一個(gè)模塊里而不是散落在業(yè)務(wù)代碼各處這樣即使后續(xù)調(diào)整存儲(chǔ)布局也只需要改一個(gè)文件。結(jié)語矩陣壓縮存儲(chǔ)是一個(gè)“小知識(shí)點(diǎn)、大考頻”的內(nèi)容。說它小是因?yàn)樗簧婕皬?fù)雜的數(shù)據(jù)結(jié)構(gòu)組合說它考頻大是因?yàn)樗瑫r(shí)出現(xiàn)在數(shù)據(jù)結(jié)構(gòu)期末、考研 408、軟考和面試手寫代碼中。這篇文章把對(duì)稱矩陣、上三角矩陣、三對(duì)角矩陣和稀疏矩陣四種壓縮方案講清楚了也給出了公式推導(dǎo)和可直接運(yùn)行的 C 代碼。建議收藏備用做題前把“行優(yōu)先/列優(yōu)先、下標(biāo)起點(diǎn)、是否含對(duì)角線”這三個(gè)判斷過一遍基本上就能避開絕大多數(shù)陷阱。下一步可以動(dòng)手實(shí)現(xiàn)一個(gè)“壓縮存儲(chǔ) ? 原矩陣互轉(zhuǎn)”的小工具用隨機(jī)矩陣做對(duì)拍驗(yàn)證這一章就算真正吃透了。