矩阵压缩存储这道题很多人第一次遇到是在期末考场上第二次是在考研 408 的模拟卷里。它的题干通常很短往往就一句话“将对称矩阵按行优先存入一维数组求A[i][j]的下标。”但错误率一直不低。原因不是公式本身难而是下标起点一变整个映射关系就得跟着改。本文把压缩存储的目的、适用矩阵、地址公式推导、C 语言实现和做题步骤一次性讲清楚。这个专题在解题栈 Hub 中属于“数组与矩阵”部分的必刷题学完就能直接套用到对称矩阵、三角矩阵、三对角矩阵三类高频考法上。如果你正在准备期末考试或考研数据结构建议先看第 4、5 章的公式推导再动手写第 6 章的代码最后用第 7 章的题型步骤做自检。1. 核心考点速览考点难度出现频率常见教材考查方式压缩存储的目的低选填题高频严蔚敏《数据结构》、王道判断哪些矩阵值得压缩对称矩阵地址计算中高频408、王道、期末卷按行优先求A[i][j]的下标三角矩阵地址计算中中频严蔚敏、王道上三角或下三角的映射推导三对角矩阵地址计算中高高频408、王道带状矩阵元素个数和下标公式稀疏矩阵存储低选填题严蔚敏三元组、十字链表的优缺点从考查趋势看矩阵压缩存储的题目难度不算大但区分度很高。很多学生能背出n*(n1)/2或者k i*(i1)/2 j一旦题目把矩阵下标换成“从 0 开始”或者把数组位置换成“从 1 开始”就会算错。这说明死记公式没有用必须理解公式是怎么推出来的。2. 矩阵压缩存储的目的与适用场景先回答题目最常问的问题为什么要压缩存储核心目的是节省存储空间。一个n×n的普通矩阵直接存储需要n^2个空间但很多矩阵内部存在大量重复元素或零元素。比如对称矩阵中A[i][j]和A[j][i]完全相等存两份就浪费了三对角矩阵中有大量元素是零逐个存储同样浪费。压缩存储的思想很简单只存储有用的、不重复的数据也就是把二维矩阵映射到一个一维数组中让一维数组的每个位置都对应一个必须保留的矩阵元素。哪些矩阵值得压缩常考的有四类。第一对称矩阵。元素关于主对角线对称A[i][j] A[j][i]因此只需要存储下三角或上三角加对角线上的元素就能完整还原整个矩阵。第二上三角矩阵和下三角矩阵。三角矩阵的特点是半个矩阵的所有元素都等于同一个常数通常为 0所以只需要存储包含数据的那一半再加一个位置保存那个常数即可。第三三对角矩阵也叫带状矩阵。非零元素集中在主对角线以及两条相邻对角线上其余位置全是零因此只需要存中间这条“带子”。第四稀疏矩阵。零元素数量远多于非零元素常见稀疏因子低于一定阈值。稀疏矩阵一般不用一维数组映射而是用三元组表或十字链表因为零元素占比太高继续按行优先映射依旧浪费。反过来说普通满矩阵如果元素没有重复、也没有明显的零元素分布规律强行压缩反而会增加下标换算的复杂度这时候直接二维存储更合适。从数据结构课程的角度看矩阵压缩存储的目的除了节省空间还有一个隐藏考点空间换时间还是时间换空间。压缩存储牺牲了直接按下标随机访问的便利性换来存储空间的减少。所以考题才会反复围绕“下标关系”命题这正是压缩存储的核心成本。3. 压缩存储核心思路二维映射到一维无论处理哪类矩阵压缩存储的通用步骤都是三步。第一步确定保留区域。对称矩阵只保留下三角下三角矩阵只保存下三角三对角矩阵只保存中间三条对角线。第二步确定映射方式。常考的是行优先存储和列优先存储其中行优先出现频率最高。行优先的含义是按行从上到下、每行从左到右把二维元素依次放进一维数组。第三步推导下标公式。假设矩阵下标从 1 开始一维数组下标也从 1 开始那么A[i][j]在一维数组中的位置k就等于“它前面的元素个数 1”。这里的关键是“它前面的元素个数”。分两步算计算前i-1行一共有多少个保留元素计算第i行中A[i][j]之前有几个保留元素。两个数量相加就得到A[i][j]前面有多少个保留元素再加 1就是它在一维数组中的位置。如果矩阵下标从 0 开始一维数组下标也从 0 开始那么k直接等于“它前面的元素个数”不需要加 1。这个由“前几行元素数 本行偏移量”组成的推导过程是解决矩阵压缩存储题目的通用方法论。把对称矩阵、三角矩阵、三对角矩阵分别套进这个方法所有公式都能自己推出来。4. 对称矩阵压缩存储与地址计算对称矩阵具有性质A[i][j] A[j][i]所以一旦访问到A[i][j]且i j就可以直接交换i和j转而去访问它的对称位置。常规做法是只存储下三角区域也就是满足i j的元素。下面以矩阵下标从 1 开始、一维数组下标从 1 开始、下三角行优先存储为例推导公式。先算前i-1行的保留元素数第 1 行保留 1 个元素第 2 行保留 2 个元素第i-1行保留i-1个元素。前i-1行合计为1 2 ... (i-1) i*(i-1)/2再算第i行中第j列前面有几个保留元素。因为下三角区域第i行保留前i个元素A[i][j]在行内正好是第j个位置所以行内偏移量为j。因此k i*(i-1)/2 j这里k是从 1 开始计数的位置。举一个例子验证。A[2][1]代入公式k 2*(2-1)/2 1 1 1 2手动列一下第 1 行存A[1][1]第 2 行存A[2][1]、A[2][2]。A[2][1]确实在第 2 个位置公式正确。再看矩阵下标从 0 开始、一维数组下标从 0 开始的情况。此时第i行前面已经有i行前i行合计元素数为1 2 ... i i*(i1)/2第i行中A[i][j]在行内前面有j个元素所以k i*(i1)/2 j这两个公式在选择题里最容易混。要判断题目给的是从 0 开始还是从 1 开始再使用对应公式不要硬套。如果题目要求的是“一维数组下标从 1 开始、矩阵下标从 0 开始”那么公式需要再调整。稳妥的做法是重新走一遍三步推导而不是背更多衍生公式。存储元素总数也需要记住。对称矩阵只存下三角元素个数为1 2 ... n n*(n1)/2这一步经常和后续的栈、队列数组容量题结合所以也属于必会内容。5. 三角矩阵与三对角矩阵压缩5.1 三角矩阵的元素总数下三角矩阵只保留下三角中等于自身值的元素上三角区域全部是同一个常数。存储时下三角部分占用n*(n1)/2个位置另外还需要一个位置保存那个公共常数总共n*(n1)/2 1上三角矩阵同理数量也是n*(n1)/2 1。考试常考两类问题。第一类是给定A[i][j]求它在一维数组中的位置。第二类是反推给定一维数组位置k求i和j。5.2 上三角矩阵地址计算上三角矩阵保留区域满足j i。按行优先存储时第i行从对角线元素A[i][i]开始后续依次是A[i][i1]到A[i][n]。以矩阵下标从 1 开始、一维数组下标从 1 开始为例前i-1行的元素数并不像下三角那样是12...(i-1)因为每一行保留的数量是递减的。第 1 行保留n个元素第 2 行保留n-1个元素。前i-1行合计为n (n-1) ... (n-i2)这个等差数列共i-1项首项n末项n-i2求和得到(i-1)*(2n - i 2)/2第i行内A[i][j]前面有j-i个元素。所以k (i-1)*(2n - i 2)/2 (j - i) 1同样如果题目下标从 0 开始要重新推导不能直接沿用这个公式。5.3 三对角矩阵的地址计算三对角矩阵也叫带状矩阵非零元素满足|i - j| 1。按行优先存储时第 1 行有 2 个元素中间每一行有 3 个元素最后一行有 2 个元素。先算三对角矩阵需要存储的元素总数。每一行最多 3 个元素第一行和最后一行只有 2 个因此总元素数 3n - 2这一步是选择题和填空题的常客。接下来计算地址。以矩阵下标从 1 开始、一维数组下标从 1 开始为例。先算前i-1行的元素数第 1 行2 个第 2 行到第i-1行每行 3 个。前i-1行合计2 (i-2)*3 3i - 4第i行内满足三对角条件的元素从左到右是A[i][i-1]、A[i][i]、A[i][i1]。A[i][j]在行内前面有j - (i-1)个元素。所以k (3i - 4) (j - i 1) 1 2i j - 2注意这里是“一维数组位置”从 1 开始。如果一维数组下标从 0 开始则前面推导结果需要减 1k 2i j - 3如果矩阵下标也从 0 开始则最简洁的形式是k 2i j三种下标组合对应三个不同公式。做题时先确认下标起点再决定用哪一种。5.4 如何快速判断是否属于三对角区域给定A[i][j]先判断|i - j| 1是否成立。如果不成立则它不是三对角矩阵的保留元素题目可能要求将其视为 0直接用 0 表示即可。这个判断不仅用于地址计算也可能出现在稀疏矩阵或带状矩阵的综合题中。如果题目给出A[3][1]对于三对角矩阵来说|3 - 1| 2 1它就不在一维数组中。6. C 语言代码实现从公式到存取函数公式推导完再用代码验证一遍记忆会更牢固。下面给出两个 C 语言实现示例。6.1 对称矩阵压缩存储假设矩阵为n×n只存下三角一维数组下标从 0 开始。定义结构体#include stdio.h #include stdlib.h typedef struct { int n; // 矩阵阶数 int *data; // 压缩存储的一维数组 } SymmetricMatrix; // 初始化 SymmetricMatrix* initSymmetricMatrix(int n) { SymmetricMatrix *m (SymmetricMatrix*)malloc(sizeof(SymmetricMatrix)); m-n n; int count n * (n 1) / 2; m-data (int*)malloc(sizeof(int) * count); return m; } // 写入对称矩阵的下三角元素 void setValue(SymmetricMatrix *m, int i, int j, int value) { if (i j) { int temp i; i j; j temp; } // 下三角 i j下标从 0 开始 int k i * (i 1) / 2 j; m-data[k] value; } // 读取元素 int getValue(SymmetricMatrix *m, int i, int j) { if (i j) { int temp i; i j; j temp; } int k i * (i 1) / 2 j; return m-data[k]; } int main() { SymmetricMatrix *m initSymmetricMatrix(3); setValue(m, 0, 0, 1); setValue(m, 1, 0, 2); setValue(m, 1, 1, 3); setValue(m, 2, 0, 4); setValue(m, 2, 1, 5); setValue(m, 2, 2, 6); // 验证 A[0][1] 和 A[1][0] 指向同一个位置 printf(A[0][1] %d\n, getValue(m, 0, 1)); printf(A[1][0] %d\n, getValue(m, 1, 0)); free(m-data); free(m); return 0; }这里下标从 0 开始所以地址公式使用的是k i*(i1)/2 j与第 4 章推导的第二组公式一致。6.2 三对角矩阵压缩存储三对角矩阵按行优先存入一维数组数组下标从 0 开始。#include stdio.h #include stdlib.h typedef struct { int n; int *data; } TridiagonalMatrix; TridiagonalMatrix* initTridiagonalMatrix(int n) { TridiagonalMatrix *m (TridiagonalMatrix*)malloc(sizeof(TridiagonalMatrix)); m-n n; int count 3 * n - 2; m-data (int*)malloc(sizeof(int) * count); return m; } int isInBand(int i, int j) { int diff i - j; if (diff 0) diff -diff; return diff 1; } void setValue(TridiagonalMatrix *m, int i, int j, int value) { if (!isInBand(i, j)) { printf(元素 A[%d][%d] 不在三对角区域内无需存储\n, i, j); return; } int k 2 * i j; m-data[k] value; } int getValue(TridiagonalMatrix *m, int i, int j) { if (!isInBand(i, j)) { return 0; } int k 2 * i j; return m-data[k]; } int main() { TridiagonalMatrix *m initTridiagonalMatrix(4); setValue(m, 0, 0, 1); setValue(m, 0, 1, 2); setValue(m, 1, 0, 3); setValue(m, 1, 1, 4); setValue(m, 1, 2, 5); printf(A[1][2] %d\n, getValue(m, 1, 2)); printf(A[3][1] %d\n, getValue(m, 3, 1)); free(m-data); free(m); return 0; }这里使用k 2*i j前提是矩阵下标从 0 开始、数组下标从 0 开始。如果题目给的矩阵下标从 1 开始可以先把i和j减 1再代入代码中的公式也可以直接把公式改成k 2*i j - 3。这类代码实现到这一步已经可以直接运行验证。如果要做批量测试建议把矩阵阶数和所有元素放到文件里用循环读取再逐个输出A[i][j]对应的数组下标和手算结果比对。7. 典型题型与解题步骤矩阵压缩存储的题目可以归纳为四类。7.1 题型一求压缩后的数组长度这类题最简单。对称矩阵答案是n*(n1)/2三角矩阵是n*(n1)/2 1三对角矩阵是3n - 2。解题步骤判断矩阵类型套对应元素总数公式注意题中是否包含“加一个存储常数的位置”。7.2 题型二给定A[i][j]求一维数组下标这是最常考的题型。以三对角矩阵为例题目可能给出矩阵下标从 1 开始、一维数组下标从 0 开始求A[3][2]的下标。解题步骤先判断|i - j| 1计算前i-1行元素数3i - 4计算本行内偏移量j - i 1求出位置k 3i - 4 j - i 1如果题目要求数组下标从 0 开始则结果再减 1。把i3, j2代入3*3 - 4 2 - 3 1 5一维数组下标从 0 开始则为 4。7.3 题型三给定一维数组下标k反求矩阵下标这种题考查对称矩阵最明显。给定下三角按行优先存储的一维数组已知某个元素在一维数组中的位置k要求确定它是哪个A[i][j]。解题思路是“先定行再定列”。因为下三角第i行之前有i*(i-1)/2个元素所以从k反推i时要找到最大的i使得i*(i-1)/2 k i*(i1)/2找到行号后再计算列号。注意题目给出的数组下标起点不一样反推结果也不同。7.4 题型四判断是否适合压缩存储这类题考查对压缩存储目的的理解。看到矩阵中重复元素或零元素较多时才值得压缩。如果一个普通矩阵元素分布没有规律强行压缩会让随机访问变慢。解答这类题时要说清楚两点一是节省了多少空间二是访问代价是否增加。空间换了访问的复杂度这是压缩存储的固有代价。7.5 统一的五步做题法把所有题型浓缩成五步写出矩阵类型对应的保留区域确认矩阵下标起点确认一维数组下标起点手工推导“前几行元素数 本行偏移”代入题目给定的i、j或k验证边界。边界验证非常有用。比如对称矩阵公式算出来的k用对角线元素A[i][i]验证通常结果应该正好等于某个已知的累加值。8. 常见错误与做题排查做题时的错误不像程序运行时会报错排查主要靠自我检查。下面的表格列出了高频错误现象、可能原因和纠正方法。错误现象可能原因排查思路纠正方法对称矩阵地址算出来比实际偏大或偏小矩阵下标或数组下标起点判断错误用A[1][1]或A[2][1]手工验证重新按“前几行元素数 本行偏移”推导三对角矩阵A[1][2]下标算错第一行只有 2 个元素仍然按 3 个计算单独手写前三行元素序列记住每行元素数是 2、3、3、...、2把下三角公式用到上三角矩阵没有分清保留区域是ij还是ji画出矩阵并标出保留区域按保留区域重新推导前几行元素数n*(n1)/2和n*(n-1)/2混用不理解对角线是否包含在保留区域内从第 1 行开始枚举推导时先写前两行的元素个数反推矩阵行列时解方程出错方程组出现两个解时没有舍掉不合理的用矩阵边界条件判断i和j的范围先确定行号再算列号避免解二次方程时遗漏约束三对角矩阵把非三对角区域元素当成 0 后仍强行求下标没有判断 i-j 1题目要求一维数组下标从 0 开始结果加了 1对“位置”和“下标”的概念混淆确认题目问的是“第几个位置”还是“下标是什么”位置从 1 开始下标从 0 开始二者恰好差 1如果是在刷题平台上反复出错建议把同一道题用两种下标起点各做一遍比较两个结果差多少。这样能形成敏锐的下标直觉。9. 总结与刷题建议矩阵压缩存储是数据结构中少有的“数学推导 代码验证”结合得很紧的考点。它不依赖复杂算法也不需要额外的抽象能力但要求做题人非常清楚下标关系。在解题栈 Hub 中这道题往往和栈、队列放在同一个复习周期里。原因很简单数组和矩阵是线性结构的延伸栈和队列又是基于数组或链表实现的。掌握矩阵压缩存储的下标换算其实是在训练“数据在连续存储空间中的定位能力”而这种能力在栈的顺序存储、循环队列的队尾指针计算中同样需要。建议的刷题顺序是先手推对称矩阵公式再手推三对角矩阵公式用第 6 章的代码验证自己的手算结果找 5 道选择题和 2 道大题分别用从 0 开始和从 1 开始两种下标做两遍遇到错误先不急着对答案回到“前几行元素数 本行偏移”的推导起点重新算。最容易踩的坑不是公式不会而是下标起点没看清楚。考试时可以用一个笨办法把题目里最小的元素比如A[1][1]或A[0][0]代入公式看结果是不是 0 或 1。这个边界检查十次能救回九次。后续可以继续扩展的方向包括稀疏矩阵的三元组存储、十字链表存储以及基于压缩矩阵实现的矩阵乘法。如果能把矩阵压缩存储的思维迁移到稀疏矩阵的批量处理上算法题的很多空间优化思路也会变得更清晰。建议收藏备用下次做到对称矩阵、三对角矩阵相关题目时直接对照本文的推导步骤检查。