企业官网建设流程全解析

某次数据结构课程设计，我抽到的题目正是“基于压缩存储的半三角矩阵乘法运算的实现”。第一反应挺不屑的：矩阵乘法不就是三重循环，谁不会？直到把“半三角”和“压缩存储”放到一起，才发现这里面的门道比想象中多得多。

直接开一个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]，这道题就是纯送分题，根本没有“设计”含量。正因为它要求压缩存储，你才必须回答三个问题：

1. 哪些元素需要存？——半三角里只有n(n+1)/2个有效元素。
2. 给定矩阵下标(i, j)，它对应一维数组的哪个位置？——这是下标映射函数。
3. 乘法循环里哪些位置的贡献必然是 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(n+1)/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 公式写错怎么自查

我见过的同学，十有八九是公式背错了一个符号，导致某些位置取值张冠李戴。这里分享一个我自己常用的自查方法：写一个小函数，把 n=5 的上三角矩阵所有(i, j)坐标对应的 pos 值打印出来，跟自己在纸上按“第 0 行 n 个、第 1 行 n-1 个……”排出来的序列逐项对照。

比如 n=5 的上三角一行排开是：

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 改到 i：

for (k = i; k < n; k++)

这个改动是绝对安全的，因为k < i的那些项乘出来全是 0，加了也白加。普通版本要算 n 次乘加，优化后只需要算n - i次。

同理，如果 B 是上三角矩阵，那么只有当k <= j时B[k][j]才非零，k 的循环上限可以直接收到 j：

for (k = 0; k <= j; k++)

看起来只是改了循环边界，放在 n 阶矩阵里，省掉的是大约一半的乘加运算。这就是压缩存储矩阵乘法的主要优化思路：不靠玄学，靠零元素的位置分布。

3.2 上三角矩阵相乘，结果仍然是上三角

如果 A 和 B 都是上三角矩阵，情况更有意思。A[i][k]非零要求k >= i，B[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(n+1)(n+2)/6，而普通矩阵乘法是n^3。n 比较大的时候，能少算约 5/6 的乘加。

3.3 六种组合的有效区间一目了然

把常见组合全部列出来，会看得更清楚。假设两个矩阵分别是 A 和 B，判断 A 的类型、B 的类型，就能直接得到 k 的循环区间以及结果的形态。

这个表值得多看两眼。有两个容易被忽略的结论：

第一，两个三角矩阵相乘，只有在同为上三角或同为下三角时，结果才保持三角形态；一上一下相乘，结果会变成普通矩阵。

第二，上三角乘普通矩阵，下界收到 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*(n+1)/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)，很可能得到一个“看起来合法”的下标。比如 n=4 的上三角矩阵，访问(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 * B：

C[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]

确实是上三角。我在代码里跑通这个例子后，还会随手加一个边界用例：n=4、A 取第四行只有一个有效元素、B 取第四列只有一个有效元素，专门验证 k 区间在边界处有没有漏算或越界。这种边界用例比随机大矩阵更能暴露下标 bug。

5. 实测中的边界问题与复杂度真相

写代码只花了一个下午，调 bug 花了接近一整天。这里把踩过的坑和复杂度结论集中说一下。

5.1 空间省了多少，具体算一笔账

假设矩阵阶数 n=2000，普通二维数组要存2000 * 2000 = 4000000个 int，每个 int 按 4 字节算，约 16 MB。压缩三角矩阵只存2000 * 2001 / 2 = 2001000个 int，约 8 MB。省出的 8 MB 在普通电脑上不算什么，但在嵌入式环境、图像处理或者课程设计限定内存的场景里，可能就是能不能跑起来的区别。

对称矩阵只是把(i, j)和(j, i)当成同一个元素存，所以空间占用和半三角压缩一致，但访问时要先判断是否需要交换下标。

5.2 时间复杂度的常数差别：n的三次方除以几

普通矩阵乘法是标准的O(n^3)，这个大家都知道。半三角压缩存储后，时间复杂度形式仍然是O(n^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，结果还是对的，只是没省到时间；有人写成从 i+1 到 j，那就漏了主对角线元素，结果立刻错。这里没有捷径，只能靠测试用例去卡。

6. 从半三角到对称矩阵、带状矩阵和稀疏矩阵

做完这道题，你会发现压缩存储不是一个孤立知识点，它是一整套思路：先识别默认值，再把有效元素按规则映射到一维数组，最后在运算时利用默认值分布缩小计算范围。这套思路可以迁移到很多数据结构场景。

6.1 对称矩阵：同一种映射，两个名字

对称矩阵的特点是A[i][j] = A[j][i]，所以整个矩阵的有效信息也只有n(n+1)/2个。压缩时按下三角存储，取数逻辑就是：

if (i < j) swap(i, j); return data[posLower(n, i, j)];

跟半三角矩阵的唯一区别在于：半三角矩阵访问缺失侧元素时直接返回 0，而对称矩阵访问缺失侧元素时要交换下标去取对应值。这个区别看似小，实际上影响很大——对称矩阵的乘法结果不一定对称，所以乘法函数里取 A 和 B 都不能简单套同一个逻辑，还是要回到get函数去区分。

6.2 带状矩阵：半带宽的压缩套路

如果把“半三角”理解成“只有主对角线附近有非零元素”的矩阵，那思路的本质也一样。假设半带宽为 b，那么每行最多有2b+1个有效元素，按行优先压缩后，(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函数先别急着写乘法，单独打印一个 n=4 的映射表，跟手写的一一核对，再进入乘法调试。这一步能帮你省下至少一小时。千万别觉得打印映射表丢人，我在实际调试里发现，所有离奇错误最后都出在那几个看似简单的下标上。