某次数据结构课程设计我抽到的题目正是“基于压缩存储的半三角矩阵乘法运算的实现”。第一反应挺不屑的矩阵乘法不就是三重循环谁不会直到把“半三角”和“压缩存储”放到一起才发现这里面的门道比想象中多得多。直接开一个n x n二维数组存矩阵再写三重循环代码很快就跑通了但这道题的意义也就消失了。压缩存储的意思是半三角矩阵里有一半元素是固定的默认值根本不用存。麻烦在于你省下了空间就要付出“每次取元素都要算下标”的代价乘法循环里每个位置都要通过下标映射去读数据这比连续访问二维数组要别扭得多。所以这道题真正考察的不是你会不会写矩阵乘法而是你能不能把“空间换时间”和“时间换空间”这对矛盾处理明白。这篇文章我会把半三角矩阵的下标映射公式怎么推导、乘法循环的有效区间怎么分析、C语言实现怎么写、正式踩坑又踩在哪里一次讲清楚。适合正在做数据结构课程设计的人准备笔试面试想快速复习压缩矩阵的人以及单纯想弄懂下标映射到底怎么回事的读者。1. 这道题真正想考你的不是“会矩阵乘法”很多同学看到“矩阵乘法”三个字就开始兴奋觉得稳了。真的把题读完看到“压缩存储”四个字才意识到这是另一回事。我先说结论只要能正确写出下标映射函数这道题就成功了一半乘法本身反而是最简单的部分。1.1 半三角矩阵到底是什么先做个约定这里说的“半三角矩阵”通俗理解就是主对角线一侧全是零、另一侧完整存储的矩阵。主对角线之上有值、之下全为零的叫上三角矩阵反过来叫下三角矩阵。两者合起来就是教材里常说的三角矩阵因为只存大约一半的元素所以有些题目里也叫“半三角”。以 n 阶上三角矩阵为例需要真正存储的元素个数是n (n - 1) ... 1 n(n 1) / 2另一个“缺失”的一半全是 0。压缩存储的思路就是只把这n(n 1)/2个有效元素按某种顺序放进一维数组其余零元素在需要时返回 0而不是真的为它们分配空间。如果题目里的“半三角”实际上是“严格三角矩阵”也就是连主对角线也不存、只剩严格上三角或严格下三角那元素总数变成n(n - 1)/2推导思路完全一样只是把对角线元素也当成默认值。本文以下都按包含对角线元素的三角矩阵处理这也是大多数教材和课程设计的默认口径。1.2 直接开二维数组就失去了这道题的意义先说一个扎心的事实如果允许直接定义int a[n][n]这道题就是纯送分题根本没有“设计”含量。正因为它要求压缩存储你才必须回答三个问题哪些元素需要存——半三角里只有n(n1)/2个有效元素。给定矩阵下标(i, j)它对应一维数组的哪个位置——这是下标映射函数。乘法循环里哪些位置的贡献必然是 0——这是循环边界收窄的依据。这三个问题才是这道题真正考察的点。尤其是第 2 个映射公式一旦写错程序运行时表现出来的症状非常隐蔽可能不崩可能不越界但结果就是错的。后面我会专门讲这种“错得无声无息”的 bug。2. 一维下标公式的完整推导从画格子到闭式公式下标映射公式看起来是某个大佬一拍脑袋写出来的其实它就是“数格子”数出来的。我建议每个做这道题的人都亲手推一遍不要死记公式因为你换个矩阵类型对称、带状推导过程还得再来一遍。2.1 上三角矩阵按剩余行元素个数累加我用 0-based 下标讨论这样写代码更自然。上三角矩阵中第 0 行的有效元素有 n 个第 1 行有 n - 1 个……第 i 行有 n - i 个。如果想求(i, j)在一维数组中的位置就先把第 0 行到第 i - 1 行的所有有效元素数出来再数第 i 行内部的有效偏移量。第 0 行到第 i - 1 行一共 i 行。它们包含的元素数可以写成n (n - 1) ... (n - i 1)这个累加式可以化简。它相当于i个 n 相加再减去0 1 ... (i - 1)也就是prefix i * n - i * (i - 1) / 2第 i 行内部(i, j)相对该行第一个有效元素(i, i)的偏移是j - i。因此上三角矩阵的映射公式就是pos(i, j) i * n - i * (i - 1) / 2 (j - i)整理一下得到更漂亮的闭式pos(i, j) i * (2 * n - i 1) / 2 (j - i)这个式子成立的条件是i j也就是访问的是上三角区域内的元素。这一点非常关键我后文会反复强调。顺手验证一下边界pos(0, 0) 0第一个元素没问题pos(n-1, n-1)按公式算一下正好等于n(n1)/2 - 1也就是数组最后一个位置。边界对上公式基本靠谱。有同学会问i * (2 * n - i 1) / 2万一除出小数怎么办不会。如果 i 是偶数i 自己就是偶数如果 i 是奇数那么2 * n - i 1就是偶数。无论哪种情况乘积都能被 2 整除。C 语言里整数除法直接取整行为是确定的不会丢精度。2.2 下三角矩阵对称地推一遍下三角矩阵的处理完全对称。第 i 行的有效元素是i 1个第 0 行 1 个第 1 行 2 个……前 i 行一共1 2 ... i i * (i 1) / 2第 i 行内部第 j 列0 j i的偏移就是 j所以pos(i, j) i * (i 1) / 2 j这个公式在很多书里更常见因为它比上三角的公式简洁。代码里两个公式我都建议写成单独的函数不要混在一起日后调试会少很多麻烦。2.3 公式写错怎么自查我见过的同学十有八九是公式背错了一个符号导致某些位置取值张冠李戴。这里分享一个我自己常用的自查方法写一个小函数把 n5 的上三角矩阵所有(i, j)坐标对应的 pos 值打印出来跟自己在纸上按“第 0 行 n 个、第 1 行 n-1 个……”排出来的序列逐项对照。比如 n5 的上三角一行排开是0 1 2 3 4 5 6 7 8 9 10 11 12 13 14第一行是(0,0)到(0,4)对应 pos 0 到 4第二行(1,1)到(1,4)对应 pos 5 到 8。只要你打印出来的映射表跟这个顺序一致公式就没问题。这个笨办法比盯公式看十分钟有效得多我每次写压缩矩阵都会先跑一遍这个自检。3. 乘法不是无脑三重循环先分析有效K区间矩阵乘法教科书定义是C[i][j] sum(A[i][k] * B[k][j]), k 0..n-1普通矩阵乘法三重循环每层都从 0 到 n-1没毛病。但半三角矩阵压缩存储后再用 0 到 n-1 去遍历会有一个尴尬的问题取A[i][k]的时候get函数要先判断 k 是否落在有效区间不在就得返回 0。这个分支判断加进去三重循环每走一步都多一层开销压缩存储节省的那点空间很快被时间上的浪费找补回去。所以真正该做的是提前用数学分析把必然为 0 的区间砍掉。3.1 矩阵乘法的基本形式与压缩存储的冲突先看一个最简单的场景A 是上三角矩阵B 是普通矩阵。C[i][j]的计算式里A 的第 i 行只有当k i时才有非零元素所以 k 的循环下限可以直接从 0 改到 ifor (k i; k n; k)这个改动是绝对安全的因为k i的那些项乘出来全是 0加了也白加。普通版本要算 n 次乘加优化后只需要算n - i次。同理如果 B 是上三角矩阵那么只有当k j时B[k][j]才非零k 的循环上限可以直接收到 jfor (k 0; k j; k)看起来只是改了循环边界放在 n 阶矩阵里省掉的是大约一半的乘加运算。这就是压缩存储矩阵乘法的主要优化思路不靠玄学靠零元素的位置分布。3.2 上三角矩阵相乘结果仍然是上三角如果 A 和 B 都是上三角矩阵情况更有意思。A[i][k]非零要求k iB[k][j]非零要求k j。当i j时这两个条件永远不可能同时满足于是C[i][j] 0。翻译成人话上三角矩阵乘上三角矩阵结果依然是上三角矩阵。这是一个数学上的封闭性。既然结果也是上三角那么结果矩阵本身也可以继续用压缩存储。写代码时遍历可以只扫i j的区域k 的循环范围收在[i, j]这个区间for (i 0; i n; i) for (j i; j n; j) for (k i; k j; k) C.data[posUpper(n, i, j)] A.data[posUpper(n, i, k)] * B.data[posUpper(n, k, j)];这个版本才是“压缩存储”真正体现价值的地方不仅空间省了一半乘法内部的无效计算也砍掉了很大一部分。我算过它的基本运算次数大约是n(n1)(n2)/6而普通矩阵乘法是n^3。n 比较大的时候能少算约 5/6 的乘加。3.3 六种组合的有效区间一目了然把常见组合全部列出来会看得更清楚。假设两个矩阵分别是 A 和 B判断 A 的类型、B 的类型就能直接得到 k 的循环区间以及结果的形态。A 的类型B 的类型有效 k 区间C 的结果形态上三角上三角[i, j]当i j上三角下三角下三角[j, i]当j i下三角上三角下三角[max(i,j), n-1]普通矩阵下三角上三角[0, min(i,j)]普通矩阵上三角普通矩阵[i, n-1]普通矩阵普通矩阵上三角[0, j]普通矩阵下三角普通矩阵[0, i]普通矩阵普通矩阵下三角[j, n-1]普通矩阵这个表值得多看两眼。有两个容易被忽略的结论第一两个三角矩阵相乘只有在同为上三角或同为下三角时结果才保持三角形态一上一下相乘结果会变成普通矩阵。第二上三角乘普通矩阵下界收到 i普通乘上三角上界收到 j。这两个正好是“半三角”压缩带来的最直接收益。写代码时你需要根据实际组合选择对应的循环边界而不是所有情况都套同一个模板。4. 可运行的C语言实现从取数函数到乘法主循环原理讲完下面给出一套能跑起来的 C 语言实现。我用两个版本第一个版本用统一的get函数代码简单、逻辑清晰适合作为第一版第二个版本针对上三角乘上三角做区间收窄体现压缩存储的优势。读者可按需取用。4.1 数据结构定义一张“说明书”存住矩阵半三角矩阵压缩存储后必须知道两件事阶数 n以及是上三角还是下三角。没有这两个信息一维数组里的数据就是一串无意义的数。所以结构体里除了数据指针还要存这两个字段。#include stdio.h #include stdlib.h #define UPPER 1 #define LOWER 0 typedef struct { int n; // 矩阵阶数 int *data; // 压缩存储的一维数组长度 n*(n1)/2 int type; // UPPER 表示上三角LOWER 表示下三角 } HalfTriMatrix; int posUpper(int n, int i, int j) { // 前提0 i j n return i * (2 * n - i 1) / 2 (j - i); } int posLower(int n, int i, int j) { // 前提0 j i n return i * (i 1) / 2 j; } HalfTriMatrix createMatrix(int n, int type) { HalfTriMatrix m; m.n n; m.type type; m.data (int *)calloc(n * (n 1) / 2, sizeof(int)); return m; }calloc会把数组清零省去手动初始化一堆 0 的麻烦。如果你用的是 C把calloc换成new int[...]再memset也一样。4.2 用get函数统一处理越界和零元素压缩存储最大的坑在于你没法直接写a[i][j]了每次取数都得先判断这个位置到底是不是有效区域。我建议把所有判断收敛到一个函数里int get(const HalfTriMatrix *m, int i, int j) { if (m-type UPPER) { if (i j) { return 0; } return m-data[posUpper(m-n, i, j)]; } else { if (i j) { return 0; } return m-data[posLower(m-n, i, j)]; } } void set(HalfTriMatrix *m, int i, int j, int value) { if (m-type UPPER) { if (i j) { m-data[posUpper(m-n, i, j)] value; } } else { if (i j) { m-data[posLower(m-n, i, j)] value; } } }get函数的逻辑一个字都不能省。为什么因为压缩数组只保存有效元素如果你在访问下三角区域时强行算posUpper(m-n, i, j)很可能得到一个“看起来合法”的下标。比如 n4 的上三角矩阵访问(3, 0)时按公式算出来 pos 是 6而 data[6] 里面存的是(1, 2)这个位置的值。程序不崩、也不错位报错但结果就是错的而且这种错误极难排查。4.3 区间收窄版乘法压缩才有意义用get写通用乘法非常安全但性能一般因为它每取一个数都要判断一次。下面给出上三角乘上三角的优化版本这也是这道题最经典的考点。注意三个循环的边界外层只扫i j内层 k 从i到j。void multiplyUpperUpper(const HalfTriMatrix *A, const HalfTriMatrix *B, HalfTriMatrix *C) { int n A-n; for (int i 0; i n; i) { for (int j i; j n; j) { int sum 0; for (int k i; k j; k) { sum A-data[posUpper(n, i, k)] * B-data[posUpper(n, k, j)]; } C-data[posUpper(n, i, j)] sum; } } }注意虽然 C 也是上三角矩阵但乘法运算是通过累加sum完成的最后才写入 C 的压缩位置。这里不能写成C-data[posUpper(n, i, j)] ...然后不初始化因为 C 是calloc创建的初始为 0直接累加也没问题。但如果 C 来自局部数组必须先清零。如果 A 是上三角、B 是普通矩阵循环边界只改一处就行。假设 B 和 C 都是普通二维数组void multiplyUpperByGeneral(const HalfTriMatrix *A, const int **B, int **C, int n) { for (int i 0; i n; i) { for (int j 0; j n; j) { int sum 0; for (int k i; k n; k) { sum A-data[posUpper(n, i, k)] * B[k][j]; } C[i][j] sum; } } }这里B[k][j]是普通二维数组的访问方式代价比压缩取数小很多。如果 B 也是压缩存储的三角矩阵那就要用get(B, k, j)来取循环边界再进一步收窄。实际编码建议不管哪种组合先保证get版本跑出来结果跟普通二维矩阵一致再改成区间收窄版本。两步走能省掉大量调试时间。4.4 测试用例拿笔手算一遍我习惯用 3 阶矩阵做手算验证因为数字小方便核对。A 是上三角A [1 2 3] [0 4 5] [0 0 6]B 也是上三角B [1 0 2] [0 1 0] [3 0 1]手算 C A * BC[0][0] 1*1 2*0 3*3 10 C[0][1] 1*0 2*1 3*0 2 C[0][2] 1*2 2*0 3*1 5 C[1][1] 4*1 5*0 4 C[1][2] 4*0 5*1 5 C[2][2] 6*1 6结果C [10 2 5] [0 4 5] [0 0 6]确实是上三角。我在代码里跑通这个例子后还会随手加一个边界用例n4、A 取第四行只有一个有效元素、B 取第四列只有一个有效元素专门验证 k 区间在边界处有没有漏算或越界。这种边界用例比随机大矩阵更能暴露下标 bug。5. 实测中的边界问题与复杂度真相写代码只花了一个下午调 bug 花了接近一整天。这里把踩过的坑和复杂度结论集中说一下。5.1 空间省了多少具体算一笔账假设矩阵阶数 n2000普通二维数组要存2000 * 2000 4000000个 int每个 int 按 4 字节算约 16 MB。压缩三角矩阵只存2000 * 2001 / 2 2001000个 int约 8 MB。省出的 8 MB 在普通电脑上不算什么但在嵌入式环境、图像处理或者课程设计限定内存的场景里可能就是能不能跑起来的区别。存储方式空间复杂度n2000 时的内存普通二维数组O(n^2)16 MB压缩三角矩阵O(n(n1)/2)约 8 MB对称矩阵压缩O(n(n1)/2)约 8 MB对称矩阵只是把(i, j)和(j, i)当成同一个元素存所以空间占用和半三角压缩一致但访问时要先判断是否需要交换下标。5.2 时间复杂度的常数差别n的三次方除以几普通矩阵乘法是标准的O(n^3)这个大家都知道。半三角压缩存储后时间复杂度形式仍然是O(n^3)但常数会因为循环边界收窄而明显变小。乘法组合乘加基本次数近似相对普通乘法的耗时普通矩阵 × 普通矩阵n^3基准上三角 × 普通矩阵n^3 / 2约一半普通矩阵 × 上三角n^3 / 2约一半上三角 × 上三角n(n1)(n2)/6约六分之一下三角 × 上三角n^3 / 3近似约三分之一上三角乘上三角的优化最明显因为有效 k 区间从[0, n-1]缩到[i, j]平均长度只有 n/3 左右再乘上外层只扫一半的(i, j)组合总计算量大幅下降。当然O(n^3)的量级没变别指望压缩一下就把时间复杂度变成O(n^2)。真要做到那一步需要换更激进的算法比如分块乘法。5.3 最常见的几个翻车点我调 bug 时最容易犯的错按踩坑频率从高到低排是下面四个。第一个是下标映射时没判断区域。posUpper只对i j有效如果你在i j时也调用它不会必然越界而是可能访问到另一个有效元素的位置导致数据错乱。这个问题隐蔽性极强强烈建议所有经过get取数不要裸调pos。第二个是结果矩阵形态判断错误。上三角乘上三角的结果还是上三角可以压缩存储但上三角乘下三角的结果是普通矩阵这时候还按压缩三角去存写入位置就全乱了。动手前先看一眼前文的组合表判断 C 到底能不能压缩。第三个是累加变量类型。矩阵乘法中间累加很容易超过 int 范围尤其是元素值比较大的时候。我在代码里用int sum那是图省事实际工程中建议用long long累加最后再根据需要截断或报溢出。第四个是循环边界写反。优化版里上三角×上三角的 k 从 i 到 j有人写成从 i 到 n-1结果还是对的只是没省到时间有人写成从 i1 到 j那就漏了主对角线元素结果立刻错。这里没有捷径只能靠测试用例去卡。6. 从半三角到对称矩阵、带状矩阵和稀疏矩阵做完这道题你会发现压缩存储不是一个孤立知识点它是一整套思路先识别默认值再把有效元素按规则映射到一维数组最后在运算时利用默认值分布缩小计算范围。这套思路可以迁移到很多数据结构场景。6.1 对称矩阵同一种映射两个名字对称矩阵的特点是A[i][j] A[j][i]所以整个矩阵的有效信息也只有n(n1)/2个。压缩时按下三角存储取数逻辑就是if (i j) swap(i, j); return data[posLower(n, i, j)];跟半三角矩阵的唯一区别在于半三角矩阵访问缺失侧元素时直接返回 0而对称矩阵访问缺失侧元素时要交换下标去取对应值。这个区别看似小实际上影响很大——对称矩阵的乘法结果不一定对称所以乘法函数里取 A 和 B 都不能简单套同一个逻辑还是要回到get函数去区分。6.2 带状矩阵半带宽的压缩套路如果把“半三角”理解成“只有主对角线附近有非零元素”的矩阵那思路的本质也一样。假设半带宽为 b那么每行最多有2b1个有效元素按行优先压缩后(i, j)的映射公式大约长这样pos i * (2b 1) (j - i b)前提是|i - j| b否则元素默认是 0。乘法循环的 k 区间也能直接收窄到[i - b, i b]和[j - b, j b]的交集。所以如果你们的题目里出现了“带状矩阵乘法”完全可以把半三角矩阵的框架搬过去只是映射公式换一下。6.3 稀疏矩阵从“根据位置省”到“根据值省”当矩阵的零元素不是集中在某个区域而是随机散布时压缩存储的依据就从“位置规律”变成了“值是否为零”这就是稀疏矩阵的三元组表或十字链表。三元组每个元素存(行, 列, 值)乘法时不再用“区间收窄”而是用“匹配行列”。这种做法比半三角复杂很多但思想一脉相承不存无效数据不遍历无效位置。对这道题而言先掌握半三角的压缩方法再去看三元组表会觉得顺理成章。我个人做这个题最大的收获不是背住了一个下标公式而是养成了一种习惯任何矩阵只要出现“大量默认值”先问自己三个问题——哪些元素需要存怎么从(i, j)快速找到位置乘法循环里哪些 k 必然贡献 0、可以跳过这三问搬到对称矩阵、带状矩阵、稀疏矩阵里都成立。最后再分享一个笨办法写完pos函数先别急着写乘法单独打印一个 n4 的映射表跟手写的一一核对再进入乘法调试。这一步能帮你省下至少一小时。千万别觉得打印映射表丢人我在实际调试里发现所有离奇错误最后都出在那几个看似简单的下标上。