企业官网建设流程全解析

后台经常收到这样的问题：数据结构复习到矩阵压缩存储时，明明公式背了好几遍，可一到考试，换个数、变一下“下标从 0 开始还是从 1 开始”的设定，结果就完全不一样了。尤其是对称矩阵压缩存储后的下标计算，看起来只是套公式，实际上非常容易出现符号和边界错误。本文就把这类题的来龙去脉完整梳理一遍：从对称矩阵的数学定义，到压缩存储的核心思想，再到三种常见下标记法下的推导公式，最后配合 C 语言验证程序和高频易错清单，帮大家把这个考点彻底吃透。

这类题在期末考试、考研 408、软考以及各类数据结构习题集里都很常见，得分不难，但想稳定拿满分，靠死记硬背是不够的。下面我们从头开始推导，顺便聊聊“压缩存储”到底压缩了什么。

1. 对称矩阵压缩存储是什么

1.1 从一个经典题目引入

先看一道很多同学都见过的题：

设有一个 5 阶对称矩阵 A，采用压缩存储方式，以行序为主序存储下三角区域（含主对角线）元素，一维数组 B 的下标从 1 开始，求 A[4][2] 在 B 中的位置。

这道题如果你只是背了公式，但没画图，很容易在“第几行第几列”“下标从几开始”这些细节上翻车。有的同学算出来是 8，有的同学算出来是 7，还有的同学直接把 A[4][2] 当成了上三角元素去查公式，结果完全对不上。其实这类题的关键不在于计算量，而在于两个前置判断：第一，矩阵的行列下标是从 1 开始还是从 0 开始；第二，一维数组的下标是从 0 开始还是从 1 开始。只要把这两点想清楚，公式怎么变都能应付。

这篇文章会从原理层面推导公式，而不是直接丢给你一串速记结论。理解了“前 i-1 行有多少个元素”这个核心以后，即使考试遇到逆推题、变种题，你也能现场推出来。

1.2 对称矩阵的数学定义

对称矩阵是指一个 n 阶方阵 A，满足对于任意 0 ≤ i, j < n，都有 A[i][j] = A[j][i]。也就是说，矩阵中的元素关于主对角线对称。

例如下面这个 4 阶矩阵就是一个对称矩阵：

A = [ 1 2 3 4 ] [ 2 5 6 7 ] [ 3 6 8 9 ] [ 4 7 9 10 ]

可以看到 A[0][1] = 2，A[1][0] = 2；A[2][3] = 9，A[3][2] = 9。主对角线上的元素 A[0][0]、A[1][1]、A[2][2]、A[3][3] 与自身对称，不需要额外存储。

对称矩阵并不算一种特别稀有的数学结构，实际上在很多实际问题中都会出现。比如无向图的邻接矩阵，因为边是无向的，所以 i 到 j 有边等价于 j 到 i 有边，反映在矩阵里就是 A[i][j] = A[j][i]。再比如机器学习中常用的协方差矩阵、距离矩阵、相似度矩阵，也往往具有对称性。

1.3 为什么要压缩存储

一个 n 阶矩阵一共有 n × n 个元素，但是对称矩阵中真正“独立”的元素其实没有那么多。因为 A[i][j] 和 A[j][i] 相等，只有主对角线及其一侧的元素才是必需的。

我们数一下需要存储的元素数量：

• 第 0 行需要存储 1 个元素（A[0][0]）；
• 第 1 行需要存储 2 个元素（A[1][0]、A[1][1]）；
• 第 2 行需要存储 3 个元素；
• ……
• 第 n-1 行需要存储 n 个元素。

总数为 1 + 2 + 3 + ... + n = n(n+1)/2。

当 n = 100 时，完整矩阵需要 10000 个存储单元，而压缩后只需要 5050 个，节省了接近一半。当 n = 1000 时，完整矩阵需要 1000000 个存储单元，压缩后需要 500500 个，节约效果非常明显。在内存资源受限的嵌入式场景，或者需要同时保存多个大矩阵的科学计算场景下，这种压缩很有价值。

压缩存储的基本思路，就是只存下三角区域或只存上三角区域，然后设计一个映射函数，把二维下标 (i, j) 映射到一维数组的下标 k 上。这个映射函数，就是考试要考的“下标计算公式”。

2. 压缩存储的核心思想：把二维下标映射到一维

2.1 行优先与列优先

在正式推导公式之前，需要先弄清楚一个基础概念：行优先和列优先。

• 行优先（Row-major）：按行从左到右、从上到下依次存储元素。C 语言中的二维数组就是典型的行优先存储。
• 列优先（Column-major）：按列从上到下、从左到右依次存储元素。Fortran 语言默认采用列优先。

如果题目没有特别说明“以行序为主序”，通常默认是行优先。个别考试题会专门考列优先，这时公式要重新推导，千万不能直接把行优先公式拿过来用。

举一个简单例子，对于下面这个 3 阶矩阵：

B = [ 1 2 3 ] [ 4 5 6 ] [ 7 8 9 ]

行优先存储在一维数组中是：1, 2, 3, 4, 5, 6, 7, 8, 9。

列优先存储在一维数组中是：1, 4, 7, 2, 5, 8, 3, 6, 9。

可以看到，同一个矩阵，行优先和列优先得到的一维序列差异很大，下标映射自然也不一样。

2.2 存下三角还是存上三角

对称矩阵的压缩存储有两种约定：

• 下三角存储：只存储 i ≥ j 的元素，也就是主对角线下方及主对角线本身。
• 上三角存储：只存储 i ≤ j 的元素，也就是主对角线上方及主对角线本身。

考试中最常见的是下三角存储。原因也很简单：下三角区域是从左上角开始“堆”的，行号从 0 到 n-1，每行元素数量是 1、2、3、...、n，规律非常明显，公式推导起来更顺手。

但要注意，无论是存下三角还是上三角，主对角线元素都要包含进去。有些同学画图时把主对角线“漏”掉了，导致元素总数少算 n 个，最后结果一定不正确。

2.3 一维数组下标从 0 开始还是从 1 开始

这是最容易踩坑的地方。同样一个映射关系，如果一维数组下标从 1 开始，那么第一个元素对应 B[1]；如果从 0 开始，则对应 B[0]。两者之间差一个 1。

很多教材在推导公式时默认“矩阵行列从 1 开始，数组下标从 1 开始”，得出：

loc( i, j ) = i(i-1)/2 + j

而很多习题册和考试真题则默认“矩阵行列从 0 开始，数组下标从 0 开始”，此时公式变成：

loc( i, j ) = i(i+1)/2 + j

两个公式长得非常像，但使用条件不同。做题时如果不去看题目里下标起点，很容易把两个公式混用。后面的章节会针对不同记号整理一份速查对照表。

3. 下标计算公式的完整推导

这一节是全文的重点。我们用最直观的“数元素个数”方法来推导公式，先讲从 1 开始的经典版本，再讲从 0 开始的 C 语言版本。

3.1 准备：明确记号

为了不让推导过程混乱，这里先做一个约定：

• 矩阵 A 是 n 阶对称矩阵；
• 矩阵行列下标记为 i、j；
• 一维数组记为 B；
• 存储方式为行优先，且只存下三角区域（i ≥ j）。

下面分两种记号体系展开。

3.2 矩阵行列从 1 开始，一维数组下标从 1 开始

这种记号在考试大题和教材习题里最常见。假设 i ≥ j，我们要找 A[i][j] 存储到 B 中的位置。

思路分成两步：

第一步，计算前 i-1 行一共有多少个元素。

因为存储的是下三角，所以：

• 第 1 行有 1 个元素；
• 第 2 行有 2 个元素；
• ……
• 第 i-1 行有 i-1 个元素。

前 i-1 行的总元素数为：

S = 1 + 2 + ... + (i - 1) = i(i-1)/2

第二步，计算第 i 行中第 j 列是本行的第几个元素。

第 i 行的下三角元素依次是 A[i][1]、A[i][2]、...、A[i][i]，所以 A[i][j] 是本行第 j 个元素。

于是，A[i][j] 从 1 开始计数的存储位置为：

loc = i(i-1)/2 + j

举个例子。假设 i = 4，j = 2，那么：

loc = 4 × 3 / 2 + 2 = 6 + 2 = 8

也就是说，A[4][2] 被存储在一维数组 B[8] 中（从 1 开始计数的第 8 个位置）。

这里要注意：如果 i < j，也就是 A[i][j] 属于上三角区域，那么先利用对称性 A[i][j] = A[j][i]，把 (j, i) 代入公式。因为 i < j 时，显然 j ≥ i，所以：

loc = j(j-1)/2 + i

比如 A[2][4] 和 A[4][2] 相等，都应该存储在 loc = 8 的位置。

3.3 矩阵行列从 1 开始，一维数组下标从 0 开始

很多题会说“数组 B 的下标从 0 开始”，这时上一小节的 B[8] 就要变成 B[7]。

公式很简单，就是在从 1 开始的结果上整体减 1：

loc0 = i(i-1)/2 + j - 1

还是 i = 4，j = 2 的例子：

loc0 = 4 × 3 / 2 + 2 - 1 = 6 + 2 - 1 = 7

所以 A[4][2] 存储在一维数组 B[7] 中。这个结果其实也很好理解：B[1] 对应 B[0]，B[2] 对应 B[1]，所以从 1 开始的序号减去 1，就是数组从 0 开始的下标。

3.4 矩阵行列从 0 开始，一维数组下标从 0 开始

这种记号最符合 C 语言的习惯。矩阵行号、列号都从 0 到 n-1，一维数组下标也从 0 开始。

现在找 A[i][j]（i ≥ j）的存储位置。

前 i 行一共有多少个元素？因为第 0 行有 1 个，第 1 行有 2 个，...，第 i-1 行有 i 个，所以前 i 行总元素数为：

S = 1 + 2 + ... + i = i(i+1)/2

注意这里和 3.2 的差别：由于下标从 0 开始，A[i][j] 之前一共有 i 行，而不是 i-1 行。

第 i 行中，A[i][0] 是第 0 个元素，A[i][1] 是第 1 个元素，...，A[i][j] 是第 j 个元素（从 0 计数）。

因此：

loc = i(i+1)/2 + j

例如 i = 3，j = 1：

loc = 3 × 4 / 2 + 1 = 6 + 1 = 7

用画图的方式验证：第 0 行 1 个，第 1 行 2 个，第 2 行 3 个，前三行共 6 个；第 3 行的第 1 个元素（从 0 数）就是第 7 个元素。完全一致。

3.5 上三角存储的公式（扩展）

虽然大多数题目默认下三角存储，但偶尔也会遇到“按上三角压缩存储”的题。如果题目明确要求存上三角，可以有两种处理方式：

第一种，利用对称性。A[i][j] 如果满足 i ≤ j，那它在上三角区域，但 A[j][i] 在下三角区域。所以直接用下三角公式，把 (i, j) 交换成 (j, i) 代入即可。这是最推荐的做法，因为下三角公式不容易记混。

第二种，单独推导上三角公式。假设矩阵行列从 0 开始，一维数组下标从 0 开始，按行优先存储上三角区域，即只存 i ≤ j 的元素。

第 0 行有 n 个元素，第 1 行有 n-1 个元素，第 2 行有 n-2 个元素，...，第 i 行有 n-i 个元素。

前 i 行总元素数为：

S = n + (n-1) + ... + (n-i+1) = i(2n - i + 1) / 2

A[i][j] 在第 i 行中的位置是第 j - i 个（从 0 计数）。

因此：

loc = i(2n - i + 1) / 2 + (j - i)

这个公式比下三角公式复杂，考试时如果你不想背，最好的策略就是“不管上三角还是下三角，都统一交换下标，放到下三角公式里算”。

3.6 公式速查表

为了方便复习，这里把最常见的三种记号体系汇总成一张表：

做题时先圈出题目里的下标起点，再选公式，基本就不会错。

4. 典型题目解析

这一节我们通过几道典型题目，把公式的使用场景和逆推方法都过一遍。

4.1 题目 1：基础正向计算

题目：设有一个 6 阶对称矩阵 A，采用行优先压缩存储下三角元素到一维数组 B，B 的下标从 1 开始。求 A[5][3] 在 B 中的位置。

解析：题目没有特殊说明，默认矩阵行列从 1 开始。A[5][3] 满足 i = 5, j = 3，且 i ≥ j，属于下三角区域。

代入公式：

loc = 5 × 4 / 2 + 3 = 10 + 3 = 13

所以 A[5][3] 存储在 B[13] 中。

如果题目改成“B 的下标从 0 开始”，答案就变成 12。所以做题时一定要看清下标起点。

4.2 题目 2：上三角元素的处理

题目：设有一个 5 阶对称矩阵 A，采用行优先压缩存储下三角元素到一维数组 B，B 的下标从 0 开始。求 A[2][4] 在 B 中的位置。

解析：A[2][4] 中 i = 2, j = 4，属于上三角区域。由于矩阵对称，A[2][4] = A[4][2]。

把 (i, j) 交换为 (4, 2)，使用从 0 开始的公式：

loc = 4 × (4 + 1) / 2 + 2 = 4 × 5 / 2 + 2 = 10 + 2 = 12

所以 A[2][4] 存储在 B[12] 中。

这道题的关键就是“对称交换”。很多同学看到上三角直接套用下三角公式，结果算出来的位置对应到了 A[2][4] 本不应存在的存储单元，这是常见的失分点。

4.3 题目 3：压缩后数组长度

题目：设有一个 100 阶对称矩阵，采用压缩存储方式存储下三角元素，问需要多大的数组？

解析：不管下标从几开始，压缩后的元素总数都是：

n(n+1)/2 = 100 × 101 / 2 = 5050

所以需要长度为 5050 的一维数组。如果数组下标从 0 开始，就是 B[0] 到 B[5049]；如果下标从 1 开始，就是 B[1] 到 B[5050]。

4.4 题目 4：逆推矩阵下标

题目：设有一个 5 阶对称矩阵 A，采用行优先压缩存储下三角元素到一维数组 B，B 的下标从 0 开始。已知 B[8] 中存储的元素在矩阵中的位置是 A[i][j]，求 i 和 j。

解析：这是反向题。已知 loc = 8，对应公式：

i(i+1)/2 + j = 8，其中 0 ≤ j ≤ i < 5。

我们从小到大试探 i：

• 当 i = 0 时，前 1 行元素数 1，太小；
• 当 i = 1 时，前 2 行元素数 3；
• 当 i = 2 时，前 3 行元素数 6；
• 当 i = 3 时，前 4 行元素数 10，已经超过 8。

所以第 3 行之前一共有 6 个元素，B[8] 在第 3 行内。于是：

j = 8 - 6 = 2

所以 B[8] 对应 A[3][2]。反过来验证一下：

loc = 3 × 4 / 2 + 2 = 6 + 2 = 8

完全正确。

5. 完整 C 语言验证程序

公式推导再多，也不如自己跑一遍代码来得踏实。下面我用 C 语言实现一个对称矩阵压缩存储的验证程序，覆盖写入和读取两个核心操作。

5.1 代码目标

• 输入一个 n 阶对称矩阵；
• 只存储下三角元素到一维数组；
• 提供 get 函数，读取任意 A[i][j]；
• 最后打印每个二维下标对应的一维下标，验证公式正确性。

为了简单，这里矩阵行列和一维数组下标都采用从 0 开始的 C 语言习惯。

// 文件路径：main.c #include <stdio.h> #include <stdlib.h> // 计算下三角元素 (i >= j) 在一维数组中的下标 // 返回值为从 0 开始的下标 int getIndexForLower(int i, int j) { if (i < j) { // 如果传入的是上三角元素，先交换到对称位置 int temp = i; i = j; j = temp; } return i * (i + 1) / 2 + j; } // 根据一维数组下标 k，反推矩阵行列下标 (i, j) // 参数 n 为矩阵阶数 void getMatrixIndex(int k, int n, int *pi, int *pj) { int i = 0; // 找到第一个使前 i 行元素总数大于 k 的行号 while ((i + 1) * (i + 2) / 2 <= k) { i++; } // 此时 i 就是行号，j 是行内偏移 int j = k - i * (i + 1) / 2; *pi = i; *pj = j; } int main() { int n = 4; // 一个 4 阶对称矩阵 int A[4][4] = { {1, 2, 3, 4}, {2, 5, 6, 7}, {3, 6, 8, 9}, {4, 7, 9, 10} }; // 压缩存储数组长度 = n * (n + 1) / 2 int total = n * (n + 1) / 2; int *B = (int *)malloc(sizeof(int) * total); if (B == NULL) { printf("内存分配失败\n"); return 1; } // 将下三角元素写入一维数组 for (int i = 0; i < n; i++) { for (int j = 0; j <= i; j++) { int k = getIndexForLower(i, j); B[k] = A[i][j]; } } // 验证：通过压缩存储读取任意 A[i][j]，包括上三角区域 printf("二维下标 -> 一维下标 -> 存储值\n"); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int k = getIndexForLower(i, j); printf("A[%d][%d] -> B[%d] -> %d\n", i, j, k, B[k]); } } // 反推验证：遍历一维数组下标，打印对应二维下标 printf("\n一维下标 -> 二维下标\n"); for (int k = 0; k < total; k++) { int i, j; getMatrixIndex(k, n, &i, &j); printf("B[%d] -> A[%d][%d]\n", k, i, j); } free(B); return 0; }

5.2 运行与验证

用 gcc 编译并运行：

gcc main.c -o sym_matrix ./sym_matrix

输出结果（部分）如下：

二维下标 -> 一维下标 -> 存储值 A[0][0] -> B[0] -> 1 A[0][1] -> B[1] -> 2 A[1][0] -> B[1] -> 2 A[1][1] -> B[2] -> 5 A[2][0] -> B[3] -> 3 A[2][1] -> B[4] -> 6 A[2][2] -> B[5] -> 8 A[3][0] -> B[6] -> 4 A[3][1] -> B[7] -> 7 A[3][2] -> B[8] -> 9 A[3][3] -> B[9] -> 10

从输出可以看到，A[0][1] 和 A[1][0] 都对应 B[1]，说明对称元素共享同一个存储单元，这正是压缩存储的核心意义。反推部分的输出也会验证 B[k] 与 A[i][j] 的对应关系。

5.3 代码说明

• getIndexForLower是核心映射函数，内部会自动处理“上三角交换到下三角”的情况。调用方不需要关心传入的是上三角还是下三角，对外统一暴露矩阵语义。
• getMatrixIndex是逆映射函数，用于回答考试中的“B[k] 对应矩阵哪个元素”这一类题目。
• 程序中的二维数组 A 只是为了方便演示和初始化数据，真正的核心存储结构是一维数组 B。

6. 高频易错点与排查思路

这类题目之所以容易失分，往往不是公式本身难记，而是各种下标起点和存储方向容易混。下面把最常见的几个坑整理出来。

6.1 易错点：矩阵行列从 1 开始还是从 0 开始

不同题目给出的下标体系可能不同。从 1 开始是最常见的“教材版本”，公式为 i(i-1)/2 + j；从 0 开始是“C 语言版本”，公式为 i(i+1)/2 + j。

做题前先看题目里有没有类似“下标从 1 开始”“数组 B[1]、B[2]...”的描述。如果没有明确说明，看看题目中的矩阵元素写法：如果出现 A[1][1] 作为第一个元素，那就是从 1 开始；如果出现 A[0][0]，就是从 0 开始。

6.2 易错点：上三角元素直接套下三角公式

例如 A[2][5] 是上三角元素，直接套公式会得到一个偏小的下标。正确做法是先交换成 A[5][2]，再代入公式。本质上利用的是对称矩阵的核心性质：A[i][j] 和 A[j][i] 相等。

6.3 易错点：忘记包含主对角线元素

主对角线元素 A[i][i] 在下三角存储中也属于“要存的那一半”。统计元素总数时，是 n(n+1)/2 而不是 n(n-1)/2。很多同学在做总长度、总容量题目时，会少算 n 个元素。

6.4 易错点：逆推时找不到正确的行号

逆推题需要“找最大的 i 使得前 i 行元素总数 ≤ k”。可以用循环，也可以解一元二次方程：

i(i+1)/2 ≤ k < (i+1)(i+2)/2

解出 i 之后，j = k - i(i+1)/2。最后一定要验证：0 ≤ j ≤ i < n。

下面是一个常见问题速查表：

7. 从做题到工程：压缩存储的真实应用场景

7.1 无向图的邻接矩阵

无向图可以用邻接矩阵表示，矩阵中 A[i][j] = 1 表示顶点 i 和 j 之间有边。由于是无向图，这条边同时也是 j 到 i 的边，所以矩阵天然满足对称性。对于节点数很多的图，比如社交网络、交通网络，直接存储完整矩阵会浪费大量内存。

使用对称矩阵压缩存储，可以把 n 个节点的无向图邻接矩阵从 n² 压缩到 n(n+1)/2，在大规模图算法中能显著降低内存占用。不过要注意，如果需要频繁修改图中边的状态，还要考虑增删边时的维护成本。

7.2 机器学习和数值计算中的对称矩阵

距离矩阵、协方差矩阵、相似度矩阵通常都是对称的。在机器学习中，n 个样本两两之间的欧氏距离可以组织成一个 n 阶距离矩阵 D，其中 D[i][j] = D[j][i]。当 n 很大的时候，完整矩阵可能占据数 GB 内存，而压缩存储可以省下一半，同时还能保证数据一致性——因为两个对称位置共享一个存储单元，不会出现“一边改了一边没改”的问题。

7.3 工程实现的几条建议

如果你要在真实项目里实现对称矩阵的压缩存储，不要直接对外暴露一维数组和下标映射，因为调用方很容易把行列传错。更推荐封装成一个类或结构体，对外提供统一的 get/set 接口：

typedef struct { int n; int *data; } SymMatrix; // 初始化 n 阶对称矩阵 SymMatrix* sym_create(int n); // 设置 A[i][j] = value，内部自动处理对称性 void sym_set(SymMatrix *m, int i, int j, int value); // 获取 A[i][j] int sym_get(SymMatrix *m, int i, int j); // 销毁矩阵 void sym_destroy(SymMatrix *m);

在sym_set内部，如果传入的 i > j，就交换 i 和 j，保证只写一次下三角区域。这样做的好处是，调用方不需要关心“我传的是上三角还是下三角”，只要语义上是对称矩阵，内部就能自动保证数据正确。这也是工程封装中“把复杂逻辑收敛在内部，对外保持简单接口”的典型例子。

8. 总结与下一步训练建议

对称矩阵压缩存储的下标计算，本质是“数元素个数”的问题。只要你愿意在草稿纸上把前几行的元素数量列出来，公式并不需要死记硬背。

本文的核心结论可以浓缩成几点：压缩后的元素总数是 n(n+1)/2；下三角存储时，从 0 开始记下标的公式是 i(i+1)/2 + j；从 1 开始记下标的公式是 i(i-1)/2 + j；遇到上三角元素，先利用对称性交换行列，再代入下三角公式；逆推题的关键是定位行号，即找到最大的 i 使得前 i 行元素总数不超过给定下标。

这类题目背后反映的是一种更通用的能力：把一个二维结构映射到一维存储时，如何通过等差数列求和快速计算偏移量。这个能力在三角矩阵、带状矩阵、稀疏矩阵三元组、二维数组的地址计算等知识点里都能用到。下一步可以把三角矩阵、三对角矩阵、稀疏矩阵的压缩存储一起整理到你的“解题栈”里，形成一套完整的矩阵压缩复习笔记。

这篇笔记也是我数据结构“解题栈”系列的第一篇。后续会继续补充栈、队列、树、图等章节的经典题目和易错点，争取把考试里高频的“小计算题”做成一个可检索、可复习的题库。如果你在刷题过程中遇到过其他让人头疼的下标计算题，欢迎在评论区补充，一起把坑点补全。