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