特殊矩阵

矩阵在内存中通常按二维数组存放。若大量元素是相同的「默认值」（如 0），可以用压缩存储只保存必要信息，这就是特殊矩阵关注的内容。

本文解决什么问题

• 哪些矩阵适合压缩
• 对称 / 三角矩阵如何映射到一维
• 稀疏矩阵三元组表示
• 压缩换来的是什么、失去了什么

常见类型

类型	特点	压缩思路
对称矩阵	$a_{ij} = a_{ji}$	只存下（或上）三角
三角矩阵	上/下三角为常数	存非常数三角
对角 / 带状矩阵	非零集中在对角线附近	按对角线映射到一维
稀疏矩阵	非零元很少	三元组 $(i,j,value)$ 表

压缩的目标：把 $O(n^2)$ 空间降下来；代价是下标换算变复杂，随机访问常数变大。

对称矩阵：下三角压缩

只存下三角（含对角线），$n \times n$ 对称矩阵需要的元素个数为：

$$1 + 2 + \cdots + n = \frac{n(n+1)}{2}$$

约定行、列下标从 0 起，且 $i \ge j$ 时元素在一维数组中的下标 $k$ 可为：

$$k = \frac{i(i+1)}{2} + j$$

当 $i < j$ 时，改读 $a_{ji}$ 对应位置即可。

/* 访问对称矩阵 a[i][j]，下三角存在一维 s[] 中 */
int sym_get(const int *s, int i, int j) {
    if (i < j) { int t = i; i = j; j = t; }
    int k = i * (i + 1) / 2 + j;
    return s[k];
}

备注

不同教材对下标从 0/1 起、存上三角还是下三角，公式会差一个偏移。实现时以你自己的约定为准，并写单元测试核对。

稀疏矩阵：三元组

非零元很少时，存整张表浪费。用三元组表记录每个非零元：

typedef struct {
    int row;
    int col;
    int val;
} Triple;

typedef struct {
    Triple data[100];  /* 非零元列表 */
    int rows, cols, nums;
} SparseMatrix;

/* 例如 3x3 矩阵仅三个非零 */
SparseMatrix M = {
    .data = {{0, 2, 5}, {1, 0, 3}, {2, 2, 1}},
    .rows = 3, .cols = 3, .nums = 3
};

转置、相加、相乘可以在三元组上定义算法；朴素做法往往要扫描列表，复杂度与非零元个数相关，而不是 $n^2$。

和其他结构的关系

• 仍是「数组思想」：连续表 + 下标映射
• 极度稀疏且动态增删时，也可能用哈希表 (i,j) -> value（工程里常见）

小结

特殊矩阵用「规律」或「只存非零」换空间。先分清矩阵类型，再选映射公式或三元组表；写清下标约定，避免公式抄混。

下一篇：串。