对称矩阵压缩存储是个很经典的C数据结构题目也是面试里常被拿出来考的基本功。它表面上考你“矩阵怎么存”实际上考的是数学公式到代码的映射能力、边界条件的处理以及你对内存开销的敏感度。我前后用这个题目带过不少新人也在面试中反复遇到这次把完整的思路、公式推导、可运行的源码以及我实践过程中踩过的坑一起整理出来。这篇文章适合几类人准备C后端或嵌入式面试的、正在学数据结构的在校生、以及做数值计算或图像处理时需要手动管理矩阵内存的开发者。不需要你有多深的线性代数基础只要你见过二维数组、知道类的基本写法就能跟着一步步实现。核心内容就三块为什么对称矩阵要压缩、坐标映射公式是怎么推出来的、以及一份完整可编译运行的C实现。1. 对称矩阵压缩存储到底解决了什么问题1.1 先搞清楚什么是对称矩阵对称矩阵的定义很简单一个n阶方阵A如果满足 A[i][j] A[j][i] 对任意的 i、j 都成立那它就是对称矩阵。换句话说沿着主对角线对折上下两部分是完全重合的。举一个5阶的例子0 10 20 30 40 10 11 21 31 41 20 21 22 32 42 30 31 32 33 43 40 41 42 43 44看第1行第2列是10第2行第1列也是10第3行第2列是21第2行第3列也是21。主对角线两侧的值完全镜像。这类矩阵在现实中出现频率很高距离矩阵、相似度矩阵、图论里无向图的邻接矩阵还有机器学习里协方差矩阵都是天然对称的。如果你做数值计算尤其是涉及到几百上千阶矩阵的时候它的存储问题就非常现实。1.2 不压缩的代价有多大一个n阶矩阵用二维数组最直观int a[n][n];乍一看没什么问题但n稍微大一点就不行了。一个int占4字节n等于10000时需要的内存是10000 * 10000 * 4 400,000,000 字节 ≈ 400MB400MB只为了存一个矩阵。如果是在嵌入式的单片机环境里flash和RAM都按KB计算这基本是灾难级别的开销。就算在PC上频繁访问这么大的数组也会不断触发缺页中断cache命中率惨不忍睹程序跑起来明显变慢。但对称矩阵有一半数据是冗余的。A[i][j] 和 A[j][i] 存两个一模一样的数纯粹是在浪费内存。压缩存储的核心思路就是既然数据成对重复我干脆只存一边用到的时候再到对应位置去取。1.3 压缩存储的三条路线往大了说矩阵压缩存储一般有三类做法对称矩阵压缩利用 A[i][j] A[j][i]只存下三角或上三角空间从 n² 降到 n(n1)/2。三角矩阵压缩矩阵本身只有上三角或下三角有非零值另一侧全是0也只需要 n(n1)/2 个空间。稀疏矩阵压缩非零元极少用三元组、行逻辑链接或CSR等结构只存非零元素的行号、列号和值。这篇文章的核心是第一类也就是对称矩阵的压缩存储。后面第5节我会把三角矩阵、带状矩阵和稀疏矩阵也顺带讲一下因为面试官常常把这几个概念放一起问很容易把人绕晕。2. 下标映射公式是怎么一步步推出来的2.1 先定一个统一规则只存下三角既然只存一半那到底存哪一半存上三角也行存下三角也行但必须定一个明确规则否则读写都乱套。我在实现里选择存下三角也就是只保留满足 i j 的元素。为什么没有绝对的原因只是大多数人习惯从第0行开始往下数下三角存储的公式更直观手算验证也更方便。如果你乐意存上三角也完全可以底层逻辑一模一样。确定了“只存下三角”之后原来的二维数组(n, n) 大小就可以压成一维数组size 1 2 ... n n * (n 1) / 2这里要特别留意为什么是 n(n1)/2 而不是 n(n-1)/2 或者别的因为下三角包含主对角线上的元素。第0行有1个元素第1行有2个第2行有3个……第n-1行有n个。加起来是1到n的和也就是 n(n1)/2。2.2 下三角行优先公式的完整推导这是整个压缩存储最核心的一步给定一个二维坐标 (i, j)怎么知道它对应一维数组的哪个下标 k我采用行优先的方式也就是一维数组里先放第0行的元素再放第1行的元素逐行往下排。对于下三角区域第0行有1个元素第0行a[0][0] - 下标 0 第1行a[1][0] a[1][1] - 下标 1, 2 第2行a[2][0] a[2][1] a[2][2] - 下标 3, 4, 5依此类推。现在要求 a[i][j]i j在一维数组中的位置分两步先数清楚前面所有行一共有多少个元素。再加上当前行内、a[i][j] 前面有几个元素。前面 i 行也就是第0行到第 i-1 行每行元素个数分别是 1, 2, 3, ..., i所以前 i 行合计1 2 ... i i * (i 1) / 2当前是第 i 行a[i][j] 在该行内位于第 j 列前面因为列号从0开始所以它前面正好有 j 个元素。于是得到公式k i * (i 1) / 2 j i j用5阶矩阵验证一下。前面第2节里的矩阵物理上只存下三角一维数组长这样一维下标对应元素0a[0][0]1a[1][0]2a[1][1]3a[2][0]4a[2][1]5a[2][2]6a[3][0]7a[3][1]8a[3][2]9a[3][3]10a[4][0]11a[4][1]12a[4][2]13a[4][3]14a[4][4]我随机挑一个位置a[4][2]套公式k 4 * 5 / 2 2 10 2 12查表下标12正好是 a[4][2]完全正确。再试 a[3][1]k 3 * 4 / 2 1 6 1 7查表也正确。2.3 如果对称位置传来的是 i j 怎么办公式要求 i j但实际使用时不可能保证调用者每次都老老实实传下三角。比如你想读 a[2][4]它在上三角区域物理上根本没存。解决办法很简单既然对称矩阵满足 a[i][j] a[j][i]那遇到 i j 时交换 i 和 j 再套公式就行了。int indexOf(int i, int j) const { if (i j) { std::swap(i, j); } return i * (i 1) / 2 j; }这是整个类里最关键的函数set、get 都会调它。这里有个很容易被忽略的细节i 和 j 是按值传进来的在函数内部交换不会影响外部调用者的任何状态。如果你手贱改成引用传参那外部变量都被改了后果非常诡异。2.4 上三角存储的公式如果面试官问你“用上三角存怎么写”你得能现场推。同样是行优先只存上三角第0行有 n 个元素第1行有 n-1 个……在访问 a[i][j]i j时前面 i 行的元素个数是n (n-1) ... (n-i1) i * n - i * (i-1) / 2当前行内a[i][j] 前面还有 j - i 个元素所以k i * n - i * (i-1) / 2 (j - i)化简一下k i * n - i * (i1) / 2 j验证n5a[1][3]k 1 * 5 - 1 * 2 / 2 3 5 - 1 3 7上三角行优先的一维数组是 a[0][0], a[0][1], a[0][2], a[0][3], a[0][4], a[1][1], a[1][2], a[1][3]下标7确实是 a[1][3]。这个公式其实不需要死记硬背。理解推导链路之后遇到任何奇怪的存储方式都能按“前面行数 当前行偏移”的思路现场推出来。3. 完整 C 源码实现与逐段精讲3.1 类设计先把接口想清楚动手写代码之前第一步应该想清楚对外提供什么接口而不是直接上来写循环。我给这个压缩矩阵设计的最小接口是构造函数指定阶数 n按 n(n1)/2 分配一维数组。set(i, j, val)写入矩阵某个位置。get(i, j)读取矩阵某个位置。print()把压缩存储的矩阵还原打印成完整的 n 阶方阵。order()返回矩阵阶数。storedSize()返回物理存储的元素个数主要用来验证。这里有两个设计细节值得展开。第一为什么用 std::vector 而不是裸指针 new[]因为 vector 能自动管理内存异常安全不需要手动 delete不会出现析构时忘记释放导致内存泄漏的问题。面试时如果你主动说出这一点是非常加分的。第二构造函数里做了一次校验assert(n_ 0);阶数不可能是0传入非法值就直接触发断言尽早暴露问题。不过C里 assert 在 release 版本定义了 NDEBUG下会被预处理掉所以正式项目里通常还要加一层运行时校验。这里作为练习assert 够用。3.2 indexOf 是心脏坐标映射写对了后面全对整个压缩存储类里最核心的代码就是 indexOf五六行而已但决定了所有读写操作的正确性。我也是在实际写代码时被坑过之后才意识到与其在 set 和 get 里各写一遍判断逻辑不如把坐标映射收敛到一个函数里所有地方只管调用。int indexOf(int i, int j) const { if (i j) { std::swap(i, j); } return i * (i 1) / 2 j; }这个函数做的事情就是第2节推导的公式。第一步统一坐标把上三角位置转换成下三角第二步套公式算一维下标。把映射集中在一个函数里有个很大的好处如果存储方案要改比如从上三角改为下三角只需要改这一个函数set 和 get 完全不用动。再强调一遍第2节提过的细节参数 i 和 j 必须按值传递。我看到有人图省事写成引用参数int i然后内部 swap 之后调用者发现自己的变量也被换了。对于这个场景来说这几乎肯定不是你想要的行为。3.3 set 和 get 实现对称性在这里体现有了 indexOfset 和 get 就非常简单了int get(int i, int j) const { assert(i 0 i n_ j 0 j n_); return data_[indexOf(i, j)]; } void set(int i, int j, int val) { assert(i 0 i n_ j 0 j n_); data_[indexOf(i, j)] val; }注意 get 是一个 const 成员函数。这一点面试官很爱问为什么 get 能是 const因为 get 只是读取元素不会修改 data_ 和 n_所以在逻辑上是 const 安全的。如果你这里不写 const外部拿到一个 const SymmetricMatrix 对象就没法调用 get 了很不方便。而 set 不是 const因为它要改 data_ 里的内容这是合理的接口设计。还有个容易踩的点如果你用裸的 int* 而不是 vector那么 get 里要额外处理空指针情况。用 vector 的话返回引用之后也不需要担心vector 自己知道大小我们只需要保证传入的 i、j 不越界。越界检查这里我用 assert好处是不额外支付性能成本。生产环境里如果允许越界访问这是巨大的安全隐患建议在正式代码中改成运行时抛异常或返回错误码。3.4 完整源码可以直接粘贴编译运行我把完整的实现汇总一下包括测试用的 main 函数。代码可以在任何支持C11及以上的编译器上编译运行。#include iostream #include vector #include cassert #include algorithm #include iomanip using std::cout; using std::endl; using std::vector; class SymmetricMatrix { public: // 构造 n 阶对称矩阵只存储下三角部分 explicit SymmetricMatrix(int n) : n_(n) { assert(n_ 0); data_.resize(n_ * (n_ 1) / 2, 0); } // 二维坐标 (i, j) - 一维下标 k int indexOf(int i, int j) const { // 统一映射到下三角保证 i j if (i j) { std::swap(i, j); } // 前 i 行元素个数 当前行内偏移 return i * (i 1) / 2 j; } int get(int i, int j) const { assert(i 0 i n_ j 0 j n_); return data_[indexOf(i, j)]; } void set(int i, int j, int val) { assert(i 0 i n_ j 0 j n_); data_[indexOf(i, j)] val; } // 打印成完整的 n 阶方阵方便肉眼验证 void print() const { for (int i 0; i n_; i) { for (int j 0; j n_; j) { cout std::setw(4) get(i, j); } cout \n; } } int order() const { return n_; } // 物理上到底存了多少个元素 int storedSize() const { return static_castint(data_.size()); } private: int n_; vectorint data_; }; int main() { // 构造 5 阶对称矩阵 SymmetricMatrix m(5); // 只设置下三角和主对角线值为 i * 10 j // 这是一种带规律的数据方便验证 for (int i 0; i 5; i) { for (int j 0; j i; j) { m.set(i, j, i * 10 j); } } cout 5 阶对称矩阵压缩存储打印为完整方阵:\n; m.print(); cout \n物理存储元素个数 m.storedSize() \n; cout 理论值 n*(n1)/2 5 * 6 / 2 \n\n; // 上三角位置读取验证对称性 cout get(4, 2) m.get(4, 2) \n; cout get(2, 4) m.get(2, 4) \n\n; // 修改上三角位置底层对应下三角同一个位置 m.set(1, 4, 99); cout 执行 set(1, 4, 99) 后\n; cout get(1, 4) m.get(1, 4) \n; cout get(4, 1) m.get(4, 1) \n\n; cout 更新后的完整矩阵:\n; m.print(); return 0; }编译方式很简单。如果你用的是 Linux 或 Mac 自带的 g在终端执行g -stdc11 -o symmetric symmetric.cpp ./symmetricWindows 下用 MinGW 的话命令一样用 Visual Studio 就直接把源代码文件拖进项目里运行。下面是程序的实际输出5 阶对称矩阵压缩存储打印为完整方阵: 0 10 20 30 40 10 11 21 31 41 20 21 22 32 42 30 31 32 33 43 40 41 42 43 44 物理存储元素个数15 理论值 n*(n1)/2 15 get(4, 2) 42 get(2, 4) 42 执行 set(1, 4, 99) 后 get(1, 4) 99 get(4, 1) 99 更新后的完整矩阵: 0 10 20 30 40 10 11 21 31 99 20 21 22 32 42 30 31 32 33 43 40 99 42 43 44输出里最值得注意的地方是 set(1, 4, 99) 之后get(1,4) 和 get(4,1) 同时变成了99。这正好印证了对称矩阵压缩存储的行为上三角只不过是对下三角的“镜像引用”并没有独立的物理存储空间。写入一侧另一侧读出来自然也跟着变。3.5 调试建议从5阶开始不要上来就怼大矩阵我用这个例子带人时最常看到的问题之一就是想一口气写一个1000阶或者10000阶的矩阵来“测试”结果程序崩了或者结果不对完全没法定位。正确的调试路径是先用5阶甚至3阶的小矩阵手工算好几个关键位置的期望下标再逐个验证。等小矩阵全部通过再去测大矩阵的存储大小是否等于 n(n1)/2。另外print() 这个函数在调试时极其有用。你可以在 set 之后把矩阵整个打出来肉眼看对角线两侧的数字是否对称。我写这类代码时一定先实现 print 再实现复杂逻辑就是因为它能给我最快的反馈。如果是在 VS Code 里写这段代码配好 C/C 扩展后新建一个 .cpp 文件终端里两条命令就能跑。不需要 IDE 项目也不需要额外的 CMake 配置核心就一个文件。4. 踩坑记录边界、面试与概念辨析4.1 我见过的六个经典错误写这个类时新手甚至一些工作两三年的同学都容易在下面这些地方翻车。我列出来算是提前给你排雷。把 size 算成 n*(n-1)/2。这是最经典的错。n*(n-1)/2 是不含主对角线时的元素个数但对称矩阵的下三角是包含主对角线的。5阶矩阵的大小是15不是10。在 indexOf 里忘记处理 i j 的情况。一旦调用 get(2,4)i*(i1)/2j 会算出7对应到矩阵里根本不是 a[2][4] 的位置数据直接读乱。把 i*(i1)/2 的乘除顺序写错或者写成 i*(i-1)/2。i4时前者是10后者是6差得很远。越界检查只写在 set 里没写在 get 里。只读场景照样可能越界别偷懒。用了 new[] 分配内存却忘了在析构函数里 delete[]。用 vector 就没这个问题这也是我推荐 vector 的原因。在 const 成员函数里试图修改 data_。get 写成非 const结果外面拿到 const 对象调用不了回头又改一遍。这些坑大多不是“不会做”而是“不细心”。写这个题的时候建议自己在代码里加上 assert让问题尽早爆炸别等数据都乱了才回头查。4.2 面试现场怎么把这道题答完整对称矩阵压缩存储是C面试里一道常见的“八股”题但它不像简单背诵题笔试或手写代码时很能看出功底。我建议按下面这个顺序回答逻辑清晰且不容易漏点先答内存节省量n阶矩阵原本需要 n² 个元素对称矩阵只需存下三角或上三角元素个数变成 n(n1)/2。如果n10000从4亿个元素降到约5000万个省了一半左右。再答坐标映射关键公式是 k i(i1)/2 j下三角行优先ij遇到上三角位置先交换 i、j。这里如果能把推导过程也讲出来面试官会认为你是真懂不是在背答案。最后补充工程细节选择 vector 管理内存确保异常安全get 设计为 const越界检查与断言打印函数辅助调试。这些东西未必是面试官明确要求的但说出来了能展现工程思维。如果时间充裕还可以主动提类似思路可以扩展到三角矩阵、带状矩阵乃至稀疏矩阵的CSR存储。这句话会让人印象很深因为它说明你不是只背了一个题而是理解了一类内存优化的思路。4.3 对称矩阵、三角矩阵、正交矩阵……别搞混标题的热词搜索里经常有人同时搜“对称矩阵和初等矩阵正交矩阵以及对角矩阵各是什么样的”说明很多人把这些概念放一起记结果越记越乱。我用一个表格把它们区分清楚矩阵类型判定条件存储特点对称矩阵A[i][j] A[j][i]存下/上三角n(n1)/2上三角矩阵主对角线以下全为0存上三角区域下三角矩阵主对角线以上全为0存下三角区域对角矩阵非对角线元素全为0只需存n个对角线元素正交矩阵A^T A A A^T I无特殊三角压缩行向量为单位正交向量初等矩阵单位矩阵做一次初等变换得到一般无需压缩注意对称矩阵的两个镜像位置值相等而三角矩阵则是一侧固定为0。这两种矩阵虽然存储大小相同但语义完全不同。正交矩阵和对角矩阵是另一个维度的概念考试和面试里经常混在一起出选择题把它们放在一张表里对比记会清晰很多。4.4 对称矩阵的性质考点除了存储面试里关于对称矩阵还常考性质。最重要的几个对称矩阵的转置等于它本身实对称矩阵的特征值都是实数实对称矩阵一定能被正交对角化也就是存在正交矩阵Q使得 Q^T A Q 是对角矩阵。这些性质在数学题里经常和别的条件组合。网上搜“设A为n阶实对称幂等矩阵 r(A)r 求 |A-2I|”这类题也能看到它的影子。幂等矩阵满足 A^2A结合实对称矩阵可对角化特征值只能是0或1秩为r说明特征值1出现r次0出现n-r次那么 A-2I 的特征值就是 -1 和 -2行列式等于所有特征值相乘结果是 (-1)^n * 2^(n-r)。这道题看着唬人实际上就是“对称矩阵性质特征值运算”的组合。压缩存储本身虽然不涉及这些性质但理解对称矩阵的数学背景能帮助你在设计存储方案时想明白“为什么只需要存一半”也能在面试或笔试时更快抓住考察意图。5. 进阶变式三角矩阵、带状矩阵和稀疏矩阵5.1 三角矩阵的压缩三角矩阵和对称矩阵一样存储大小也是 n(n1)/2。区别在于对称矩阵是靠“镜像相等”去重三角矩阵是靠“固定为0”去重。比如一个上三角矩阵下三角全是0那你就只需要存上三角部分原理和对称矩阵存上三角一致。公式沿用第2.4节k i * n - i * (i 1) / 2 j i j下三角矩阵则对称地使用k i * (i 1) / 2 j i j有些三角矩阵还额外存一个常数 d用来表示对角线的偏移那就比标准情况多一个变量实际存储大小为 n(n1)/2 1。这类结构在求解线性方程组、LU分解里很常见所以很多数值计算库里都会涉及。5.2 带状矩阵的压缩还有一种矩阵叫带状矩阵非零元素集中在主对角线附近的一个带状区域里。最典型的例子是三对角矩阵也就是只有主对角线、以及紧邻主对角线上下两条对角线有非零值。三对角矩阵每一行最多3个非零元素n阶矩阵最多只有 3n-2 个非零元素。你可以用一个 n×3 的数组vectorvectorint band(n, vectorint(3));或者直接用一维数组按下标映射。对角线存储还有一个经典做法是压缩到 n 行 3 列后每一行三个槽位分别存 a[i][i-1]、a[i][i]、a[i][i1]。带状的存储公式不像对称矩阵那么统一通常要按带宽 b 具体设计。带宽为b的矩阵每行非零元素最多 2b1 个总存储量约 O(n*b)。当 b 远小于 n 时省内存效果同样非常可观。5.3 稀疏矩阵为什么不能只靠对称压缩对称矩阵压缩解决的是“数据成对重复”的问题但有些矩阵不仅对称而且大部分元素都是0。比如一张图的邻接矩阵一万个节点真实边数只有几千条。这时候就算压缩成一半依然是海量的0值占着位置继续压缩的意义不大。正确的做法是稀疏矩阵存储。基础方案是三元组struct Triple { int row; int col; int value; };只存非零元素的 (行, 列, 值)。更工程化的方案是CSRCompressed Sparse Row用三个数组分别记录每行起始偏移、列号和值查询时按行快速定位。这也是很多数学库的底层存储格式。学习对称矩阵压缩其实是为理解这些更复杂的存储方案打基础。核心思路一脉相承不要存储冗余信息通过索引计算把二维逻辑映射到一维物理存储上。你只要吃透前者的公式推导后面看 CSR 的偏移数组时会有一种“原来如此”的熟悉感。我在实际带人的过程中通常会让他们把“只存下三角”的版本跑通之后再自己改成“只存上三角”然后加上一个限制set 只允许写入下三角区域上三角写入直接抛异常。这两个小改动成本很低但对理解坐标映射和接口设计帮助非常大。如果你自己练完这段代码不妨也按这个方向扩展一下比单纯看十遍文章有效得多。