矩阵压缩存储这一章很多同学学的时候觉得“公式记一下就行”结果一到做题就翻车题目里明明写的是上三角矩阵你按对称矩阵的公式去套题目说的是按列优先存储你按行优先去算题目里数组下标从 1 开始你默认从 0 开始最后算出来的地址差了整整一个元素。作为数据结构里性价比极高的一块内容矩阵压缩存储既不像树和图那样需要大量代码训练也不像排序算法那样考验复杂度分析但它几乎是考研 408、期末考和软考选择题的“必考送分题”。前提是你真的理解了下标换算的来龙去脉而不是背公式。这篇文章围绕三个问题展开什么样的矩阵值得压缩存储压缩之后一维下标怎么换算这些知识点在考试和项目里分别怎么用我会把对称矩阵、三角矩阵、三对角矩阵和稀疏矩阵四种情况逐一拆解给出公式推导过程和可直接运行的 C 语言示例代码。先给一个明确判断如果你只背公式不清楚“为什么对称矩阵只存 n(n1)/2 个元素”“为什么三对角矩阵只需要 3n-2 个存储单元”那么换一个问法你大概率还会错。矩阵压缩存储的本质是一个映射关系——把逻辑上的二维坐标映射到物理上的一维下标。搞清楚这个映射公式不用背也能推出来。1. 矩阵压缩存储到底解决了什么问题先回到一个实际场景。假设你在做一个地图应用城市之间有公路相连你想用一个矩阵表示“任意两个城市之间是否连通”这就是图的邻接矩阵。如果城市数量是 1000二维数组需要 1000×1000 个存储单元但一个无向图的邻接矩阵一定是对称的——i 到 j 连通等价于 j 到 i 连通。也就是说大约一半的元素是冗余的。再看数值计算领域。有限元分析、偏微分方程求解中经常出现“稀疏矩阵”矩阵规模可能是 100 万×100 万但每一行非零元素只有个位数。如果老老实实开一个二维数组内存直接爆炸但如果只存非零元素整个矩阵可能只占原来存储空间的万分之一。这就是矩阵压缩存储要解决的核心问题在逻辑上仍然把数据看作一个完整的矩阵但在物理上通过“跳过重复元素”和“跳过零元素”来节省存储空间。具体收益有三点空间节省。对称矩阵能省接近一半稀疏矩阵的节省效果更是数量级的。访存效率。一维数组是连续存储对 CPU 缓存更友好顺序遍历时比二维数组尤其是“数组指针数组”那种实现更高效。传输与落地。在嵌入式设备、带宽受限的场景里压缩后的数据体积更小传输和持久化都更快。但也不是所有矩阵都适合压缩。如果矩阵维度很小比如 3×3 的变换矩阵压缩后反而要额外维护一行映射逻辑属于得不偿失。再比如频繁写操作的场景压缩存储通常只擅长“按坐标读取”写入某个位置可能需要付出额外换算代价。这个边界要心里有数。2. 基础概念特殊矩阵、压缩存储与下标体系2.1 什么是特殊矩阵数据结构里讨论的矩阵压缩针对的是几类“有规律”的矩阵矩阵类型特征可省略的元素对称矩阵a[i][j] a[j][i]上三角或下三角的一半重复元素上三角矩阵下三角区域全为常数或零下三角区域的重复/零元素下三角矩阵上三角区域全为常数或零上三角区域的重复/零元素三对角矩阵除主对角线及相邻两条对角线外全为零远离主对角线的零元素稀疏矩阵非零元数量远小于总元素数量大量零元素注意一个容易混淆的点三角矩阵的“下三角区域全为常数”和“下三角区域全为零”在存储策略上有细微差别。如果下三角区域都是同一个常数 c那么只需要额外存一个 c如果都是零那么零元素根本不占存储空间。2.2 什么是压缩存储压缩存储的定义可以概括为对多个值相同的元素只分配一个存储单元对零元素不分配存储单元。注意这里有两条不同的逻辑——对称矩阵靠“值相同”压掉重复元素稀疏矩阵靠“值为零”压掉无效元素。前者损失的是冗余后者损失的是零。压缩存储后的数据仍然要支持随机访问也就是说给定一个矩阵坐标你要能算出它在一维数组里的位置。这个计算过程就是“地址映射”也是考试最容易丢分的地方。2.3 行优先与列优先先搞清楚规则再套公式矩阵在逻辑上是二维的但内存是一维的所以必须约定一个“展开顺序”。行优先先存第一行再存第二行依次往下。C 语言的二维数组就是行优先。列优先先存第一列再存第二列依次往右。Fortran、MATLAB 默认是列优先。很多题目不会直接告诉你“按行优先存储”而是用“按行展开”“以行序为主序”“以列序为主序”这类说法。做题第一步永远是判断这个。另外还要搞清楚下标起点。严蔚敏版《数据结构》的公式里矩阵下标通常从 1 开始一维数组 SA 的下标从 0 开始但不同教材、不同题目可能不一样。最稳妥的做法是拿到题目先确定三件事——矩阵下标从几开始、数组下标从几开始、按行还是按列。3. 对称矩阵压缩原理、公式与易错点3.1 为什么只存一半就够了对称矩阵满足 a[i][j] a[j][i]也就是说上三角区域的每个元素在下三角区域都有一个一模一样的“镜像”。既然值相同就没必要存两份。按行优先原则只存下三角含主对角线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 阶对称矩阵需要存储的元素个数是1 2 3 ... n n(n1)/2这一行累计求和就是整个对称矩阵压缩存储公式的来源。3.2 地址计算公式推导假设矩阵下标从 1 开始一维数组 SA 下标从 0 开始按行优先只存下三角。现在要存 a[i][j]且 i ≥ j。先算它前面有多少个元素第 1 行到第 i-1 行是完整的下三角元素个数为 1 2 ... (i-1) i(i-1)/2。第 i 行从第 1 列到第 j 列共有 j 个元素因为只存下三角第 i 行到第 j 列为止。所以 a[i][j] 在一维数组中的下标0-based为k i(i-1)/2 j - 1如果题目问的是字节地址假设元素占 L 个字节首元素地址为 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。很多同学把 1-based 的公式直接套到 0-based 的题目里一错就是一片。做题时先把行号列号统一到公式要求的体系里。3.3 对称矩阵的还原从一维数组还原成二维矩阵时下三角直接读上三角通过“对称镜像”补上if (i j) { mat[i][j] sa[i * (i 1) / 2 j]; // 0-based 版本 } else { mat[i][j] sa[j * (j 1) / 2 i]; }实际项目里如果你只是想省内存这种还原逻辑完全正确但如果是数值计算场景更推荐用 BLAS/LAPACK 等专业库它们会针对对称矩阵做更精细的优化而不是简单省一半内存。4. 三角矩阵压缩上三角、下三角与常量元素4.1 下三角矩阵下三角矩阵的规则是上三角区域的元素全为同一个常数 c或者全为 0。如果全为 c存储时只需要在存完下三角的 n(n1)/2 个元素之后再单独存一个 c。总存储单元数为n(n1)/2 1一维数组的最后一个位置存的就是那个常量 c。如果是全为 0 的情况连这个常量都不需要存。下三角矩阵 a[i][j]i ≥ j的下标公式和对称矩阵下三角部分完全一样k i(i-1)/2 j - 1当 i j 时元素值就是常量 c不需要通过公式定位。4.2 上三角矩阵公式推导上三角矩阵是“下三角区域全为常数”存储上三角部分同样按行优先。先看存储顺序4×4 上三角矩阵按行优先存储为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]元素个数仍然是 n(n1)/2另加一个常量 c。现在计算 a[i][j]i ≤ j前面有多少个元素第 1 行到第 i-1 行每行元素个数分别是 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)这个公式看起来比对称矩阵复杂但推导思路完全一致先算前面整行的元素总数再加上本行内目标的偏移量。4.3 上三角与下三角的对比很多同学记混这两个公式建议这样区分下三角矩阵行号决定“前面有多少个完整的短行”核心是 12...i 的累加。上三角矩阵行号决定“前面有哪些从长到短的整行”核心是等差数列求和每行长度从 n 开始递减。可以先用一个 3×3 的例子手算一遍上三角矩阵 a[2][3] 的下标按上面公式 k (2-1)(2×3 - 2 2)/2 (3-2) (1×6)/2 1 4对应数组里第 5 个元素0-based 下标 4正好是存储顺序里的 a[2][3]。手算一次能理解比背公式有用得多。5. 三对角矩阵与稀疏矩阵的存储方案5.1 三对角矩阵带状存储三对角矩阵是带状矩阵的一种特例除主对角线、主对角线正上方的次对角线和正下方的次对角线外其余元素全为 0。也就是说只有满足 |i - j| ≤ 1 的位置才可能有非零值。每行最多 3 个非零元素首行和末行只有 2 个因此 n 阶三对角矩阵的非零元素总数为2 3(n-2) 2 3n - 2按行优先存储时一维数组里的排列是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数组下标 0-basedk 2i j - 3验证一下a[2][3] → k 4 3 - 3 4数组里第 5 个位置正确。a[3][2] → k 6 2 - 3 5数组里第 6 个位置正确。如果题目给的是 1-based 数组下标公式变成 K 2i j - 2。这类“差 1”的问题就是命题老师最喜欢的陷阱。5.2 稀疏矩阵三元组顺序表当矩阵中非零元素的个数远小于零元素个数时一般称为稀疏矩阵。宽松的判断标准是非零元占比低于 5%严格一点的教材用“稀疏因子”来定义。稀疏矩阵不能再用“跳过固定位置”的思路压缩因为非零元素的位置没有规律。常用的存储方案是三元组顺序表每个非零元素用一个三元组记录 (行号, 列号, 值)所有三元组按行优先顺序存放在数组中。#define MAXSIZE 100 typedef struct { int row; // 行号从 1 开始 int col; // 列号从 1 开始 int value; // 元素值 } Triple; typedef struct { Triple data[MAXSIZE]; int mu; // 矩阵总行数 int nu; // 矩阵总列数 int tu; // 非零元个数 } TSMatrix;三元组表的核心代价是节省了空间但失去了随机访问能力。想读某个坐标需要顺序查找三元组想修改某个位置需要先找到它再改。这就是“用空间换来的确定性又用时间还了回去”。更复杂的十字链表可以支持矩阵在动态变化中高效插入和删除非零元素但它牺牲了数组的局部性实现也明显更复杂。考试以三元组为主项目里则要看具体场景——静态矩阵用三元组或直接上专业库动态矩阵才需要考虑十字链表。6. 完整示例C 语言实现矩阵压缩与还原6.1 环境说明下面代码用标准 C 编写不依赖第三方库。操作系统不限Linux/macOS 下用 gcc 编译Windows 下用 MinGW 或 VS 的 C 环境都可以。重点演示的是压缩存储的核心映射逻辑。6.2 对称矩阵的压缩、取值与还原// 文件路径symmetric_matrix.c #include stdio.h #define N 4 // 按行优先压缩对称矩阵只存下三角含对角线 // mat 为 n x n 对称矩阵sa 为一维数组 // 返回实际存入的元素个数 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 开始自动处理上三角区域 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]; } // 从一维数组还原出完整对称矩阵 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(压缩后一维数组\n); for (int k 0; k cnt; k) { printf(%d , sa[k]); } printf(\n元素个数 %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就是公式的落地实现。注意传入的行号列号是 1-based符合教材习惯如果到了项目里接口暴露给外部调用建议在接口层做一次转换避免让调用方去记下标约定。6.3 上三角矩阵的压缩与取值// 文件路径upper_triangular_matrix.c #include stdio.h #define N 4 // 按行优先压缩上三角矩阵最后额外存一个常量 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 开始 // 如果坐标在下三角区域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(上三角压缩后一维数组\n); for (int k 0; k cnt; k) { printf(%d , sa[k]); } printf(\n元素个数 %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 存在一维数组的最后一个位置所以取值时判断i j就直接返回这个常量。这里的“0”只是演示用实际项目中常量可能是任意值。6.4 三对角矩阵的压缩与取值// 文件路径tridiagonal_matrix.c #include stdio.h #include stdlib.h #define N 5 // 按行优先压缩三对角矩阵返回元素个数 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(三对角压缩后一维数组\n); for (int k 0; k cnt; k) { printf(%d , sa[k]); } printf(\n元素个数 %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 稀疏矩阵三元组表示与转置// 文件路径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; // 总行数 int nu; // 总列数 int tu; // 非零元个数 } TSMatrix; // 普通转置按列扫描三元组表 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转置后\n); print_matrix(T); return 0; }注意一个细节普通转置的时间复杂度是 O(nu × tu)如果矩阵的列很多、非零元也很多这个代价会很高。考试里还有一个进阶考点是“快速转置”它先用两个数组统计每列非零元个数和每列第一个非零元在转置表中的起始位置把时间复杂度降到 O(nu tu)。7. 运行结果与验证方法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 预期输出对称矩阵示例的关键输出压缩后一维数组 1 2 5 3 6 8 4 7 9 10 元素个数 10理论值 10 坐标取值验证 get_symmetric(sa, 4, 4, 2) 7原矩阵 mat[3][1] 7 get_symmetric(sa, 4, 2, 4) 7原矩阵 mat[1][3] 7上三角矩阵示例的关键输出上三角压缩后一维数组 1 2 3 4 5 6 7 8 9 10 0 元素个数 11理论值 11 坐标取值验证 get_upper(sa, 4, 2, 3) 6原矩阵 mat[1][2] 6 get_upper(sa, 4, 3, 1) 0下三角常量三对角矩阵示例的关键输出三对角压缩后一维数组 1 2 3 4 5 6 7 8 9 10 11 12 13 元素个数 13理论值 13 坐标取值验证 get_tridiag(sa, 5, 3, 2) 6原矩阵 mat[2][1] 6 get_tridiag(sa, 5, 5, 1) 0不在三条对角线上7.3 如何判断成功判断标准很简单用get_*函数随机取几个坐标和原矩阵对应位置的值逐一对比。如果全部一致说明“压缩-取值”这条链路是对的再用还原函数把一维数组还原成二维矩阵整体对比原矩阵说明“压缩-还原”闭环成立。如果输出不对第一步去看下标换算打印出每个坐标换算出的 k 值手工在纸上推一遍存储顺序确认是不是“差 1”的问题。8. 考题拆解与常见问题排查8.1 典型考题一对称矩阵坐标换算题目设有一个 10×10 的对称矩阵 A按行优先只存下三角含对角线存入一维数组 SA下标从 0 开始。若行号和列号均从 1 开始编号则 A[6][4] 对应的存储下标是多少拆解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 阶上三角矩阵按行优先压缩存储元素占 L 个字节首元素 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] 的值所以不需要再加一。如果题目把数组下标写成从 1 开始比如“A[1][2] 存在 SA[1]”那么公式里的 offset 要整体加 1这一步最容易出错。8.3 典型考题三三对角矩阵题目一个 5 阶三对角矩阵按行优先压缩存入一维数组矩阵下标和数组下标都从 1 开始A[3][2] 存储在数组的哪个位置拆解i3j2满足 |i-j|1用 1-based 公式K 2 × 3 2 - 2 6答案是第 6 个位置。注意题目说的是“第几个位置”也就是 1-based 下标所以用 K 2i j - 2如果题目问“数组下标”并且数组从 0 开始那才是 2i j - 3。8.4 常见问题排查表问题现象可能原因排查方式解决方案计算结果总是比答案大 1数组下标从 0 开始却套用了 1-based 公式重新确认题目下标起点统一转换后再套公式对称矩阵读取上三角元素错误没有交换坐标打印 i、j 是否做了镜像处理先判断 i j 再交换上三角矩阵返回了奇怪的大数访问了下三角区域且未判断越界检查是否存在 i j 的调用增加 if (i j) 返回常量三对角矩阵坐标换算不对用了对称矩阵公式验证 k 2i j - 3 的手算结果用行列的前缀元素累加验算稀疏矩阵转置顺序不正确普通转置逻辑里没有按列扫描检查转置结果是否按行优先按原矩阵列序扫描三元组表9. 最佳实践与学习建议9.1 做题习惯做任何矩阵压缩存储的题目先写三个决定1. 行优先还是列优先 2. 矩阵下标从 0 还是 1 开始 3. 数组下标从 0 还是 1 开始这三件事确定后再套公式。宁可多花 10 秒确认也不要算到一半才发现方向错了。9.2 代码实践建议实际项目中优先考虑成熟的线性代数库。Eigen、BLAS、LAPACK 对对称矩阵、带状矩阵、稀疏矩阵都有高度优化的实现自己实现压缩存储容易出现以下问题只优化了空间没优化访存模式性能反而下降。边界条件考虑不全比如三对角矩阵首行末行只有两个元素。并发写入场景下坐标换算和数组扩容的线程安全问题。自己实现压缩存储最有价值的场景是嵌入式开发、教学实验、或者你确实需要在某个特定数据布局下做极致优化。9.3 学习路径建议如果考研建议把矩阵压缩存储和图的邻接矩阵联系起来复习。图的邻接矩阵天然是对称的考试中经常出现“用一维数组存储邻接矩阵判断两个顶点是否相邻”的题目本质上就是对称矩阵压缩存储的应用。如果准备面试可以额外思考一个问题压缩存储后的矩阵如何支持高效的遍历对称矩阵按行遍历一维数组时怎么保证每个镜像元素只输出一次这个问题能答清楚说明你不是背公式而是真的理解了映射关系。9.4 一个容易忽略的点压缩存储并没有改变矩阵的逻辑结构它只是改变了物理存储布局。因此任何依赖“矩阵坐标”的操作读取、写入、遍历、转置都需要通过映射函数完成。写代码时建议把所有映射函数集中放在一个模块里而不是散落在业务代码各处这样即使后续调整存储布局也只需要改一个文件。结语矩阵压缩存储是一个“小知识点、大考频”的内容。说它小是因为它不涉及复杂的数据结构组合说它考频大是因为它同时出现在数据结构期末、考研 408、软考和面试手写代码中。这篇文章把对称矩阵、上三角矩阵、三对角矩阵和稀疏矩阵四种压缩方案讲清楚了也给出了公式推导和可直接运行的 C 代码。建议收藏备用做题前把“行优先/列优先、下标起点、是否含对角线”这三个判断过一遍基本上就能避开绝大多数陷阱。下一步可以动手实现一个“压缩存储 ↔ 原矩阵互转”的小工具用随机矩阵做对拍验证这一章就算真正吃透了。