矩阵 | 小菜鸟

矩阵的特殊存储结构与压缩策略

矩阵是线性代数的核心数据结构，在计算机中通常以二维数组存储。但对于特殊矩阵（如对称矩阵、三对角矩阵）和稀疏矩阵，直接使用二维数组会导致大量空间浪费。因此，针对这些矩阵的特性，需要设计专门的压缩存储方案。

对称矩阵的压缩存储

对称矩阵的核心特性是 A[i][j] = A[j][i]（元素关于主对角线对称），因此只需存储主对角线及一侧的元素（通常选择下三角区 + 主对角线），即可完整表示矩阵，空间复杂度从 O(n²) 降至 O(n²/2)。

存储规则

设矩阵为 n×n 阶对称矩阵，仅存储满足 i ≥ j（下三角区及主对角线）的元素：

按行优先顺序存储，将二维坐标 (i, j) 映射到一维数组 sa[k] 中。
映射公式：
对于 i ≥ j，k = i×(i+1)/2 + j
（推导：第 0 行存 1 个元素，第 1 行存 2 个元素，…，第 i 行存 i+1 个元素，前 i 行共 i×(i+1)/2 个元素，加上第 i 行的第 j 个元素，总索引为 i×(i+1)/2 + j）。

元素访问

当 i ≥ j 时，直接通过 k = i×(i+1)/2 + j 访问 sa[k]。
当 i < j 时，利用对称性 A[i][j] = A[j][i]，通过 k = j×(j+1)/2 + i 访问。

示例：3×3 对称矩阵

原矩阵       压缩存储（sa[6]）
[1 2 3]     sa[0]=1（0,0）, sa[1]=4（1,0）, sa[2]=5（1,1）,
[4 5 6]     sa[3]=7（2,0）, sa[4]=8（2,1）, sa[5]=9（2,2）
[7 8 9]

访问 A[0][1] 时，因 0 < 1，等价于 A[1][0]，对应 sa[1] = 4。

三对角矩阵的压缩存储

三对角矩阵（带状矩阵）的特性是：仅主对角线、主对角线上下邻接的对角线（次对角线）上有非零元素，其余位置均为 0。对于 n×n 阶三对角矩阵，非零元素集中在 |i-j| ≤ 1 的区域，总非零元素约为 3n-2 个，空间复杂度可从 O(n²) 降至 O(n)。

存储规则

按行优先顺序存储三条对角线上的元素，将二维坐标 (i, j) 映射到一维数组 sa[k] 中：

映射公式：k = 2i + j（i从 0 开始，j满足i-1 ≤ j ≤ i+1且0 ≤ j < n）。
- 第 0 行有 2 个元素（j=0,1）。
- 第 1 至 n-2 行每行有 3 个元素（j=i-1,i,i+1）。
- 第 n-1 行有 2 个元素（j=n-2,n-1）。

元素访问

对于非零元素（|i-j| ≤ 1），直接通过 k = 2i + j 访问。
对于零元素（|i-j| > 1），无需存储，直接返回 0。

示例：5×5 三对角矩阵

原矩阵（非零元素）      压缩存储（sa[13]）
[ a  b  0  0  0 ]     sa[0]=a, sa[1]=b,
[ c  d  e  0  0 ]     sa[2]=c, sa[3]=d, sa[4]=e,
[ 0  f  g  h  0 ]     sa[5]=f, sa[6]=g, sa[7]=h,
[ 0  0  i  j  k ]     sa[8]=i, sa[9]=j, sa[10]=k,
[ 0  0  0  l  m ]     sa[11]=l, sa[12]=m

稀疏矩阵的压缩存储

稀疏矩阵的定义是：非零元素数量远小于矩阵总元素数量（通常非零元素占比 < 5%）。直接存储会浪费大量空间，需通过仅记录非零元素实现压缩。常见方案有三元组表和十字链表。

三元组表（顺序存储）

核心思想：用一个一维数组存储所有非零元素，每个元素记录其 (行号, 列号, 值) 三元组，同时记录矩阵的总行数、总列数和非零元素总数。

结构定义：

typedef struct {
    int i, j;  // 非零元素的行、列下标
    ElemType val;  // 非零元素值
} Triple;

typedef struct {
    Triple data[MAXSIZE];  // 三元组数组
    int rows, cols, cnt;  // 矩阵行数、列数、非零元素数
} TSMatrix;  // 三元组顺序表

优缺点：
- 优点：结构简单，节省空间。
- 缺点：不便于动态插入 / 删除非零元素，适合静态稀疏矩阵。

十字链表（链式存储）

核心思想：为每个非零元素创建一个节点，同时按行和列维护链表（每行、每列的非零元素构成一条链表），便于动态操作。

节点结构：

typedef struct OLNode {
    int i, j;  // 行、列下标
    ElemType val;  // 元素值
    struct OLNode *right, *down;  // 向右（同列下一个）、向下（同行下一个）指针
} OLNode, *Olink;

typedef struct {
    Olink *row_head, *col_head;  // 行、列链表头指针数组
    int rows, cols, cnt;  // 矩阵行数、列数、非零元素数
} CrossList;  // 十字链表

优缺点：
- 优点：支持高效的插入 / 删除操作，适合动态稀疏矩阵（如矩阵运算过程中）。
- 缺点：结构复杂，实现难度较高。

总结

矩阵类型	存储策略	空间复杂度	适用场景
对称矩阵	存储下三角区 + 主对角线	O(n²)→O(n²/2)	元素关于主对角线对称（如协方差矩阵）
三对角矩阵	存储三条对角线元素	O(n²)→O(n)	带状矩阵（如微分方程离散化结果）
稀疏矩阵	三元组表（静态）、十字链表（动态）	O (n²)→O (k)（k 为非零元素数）	非零元素极少的大型矩阵（如神经网络权重矩阵）

选择压缩存储方案时，需权衡空间效率与操作复杂度：静态场景优先选顺序存储（如三元组表），动态场景需选链式存储（如十字链表）