一、为什么要压缩存储

普通二维数组存储一个 m×nm\times n 矩阵，需要 m×nm\times n 个存储单元。

当矩阵中大量元素相同，或者大量元素为 0 时，可以只存储有意义的元素，从而：

  • 节省存储空间；
  • 减少无效运算；
  • 提高部分矩阵运算效率。

核心原则是：

相同元素只存一次，零元素尽量不存，同时建立原下标与压缩数组下标之间的映射。

二、特殊矩阵的压缩存储

特殊矩阵通常具有固定规律，因此可以用一维数组存储。设矩阵为 n×nn\times n，下标从 0 开始。

1. 对称矩阵

对称矩阵满足：

aij=ajia_{ij}=a_{ji}

因此只需要存储其中之一（下三角部分或上三角部分）。包含主对角线，等差数列求和公式得出共需存储的元素个数为：

n(n+1)2\frac{n(n+1)}{2}

按行存储下三角 假设我们有一个 3×43 \times 4 （3行4列）的二维数组 AA：

A=[A00A01A02A03A10A11A12A13A20A21A22A23]A = \begin{bmatrix} A_{00} & A_{01} & A_{02} & A_{03} \\ A_{10} & A_{11} & A_{12} & A_{13} \\ A_{20} & A_{21} & A_{22} & A_{23} \end{bmatrix}

依次存储：

a00,a10,a11,a20,a21,a22,…a_{00},a_{10},a_{11},a_{20},a_{21},a_{22},\dots

按行内存地址计算公式 设数组首地址为 Base\text{Base}，每个元素占 LL 个字节。对于 m×nm \times n （mm 行 nn 列）的数组，要计算第 ii 行第 jj 列的元素 A[i][j]A[i][j] 的内存地址，逻辑是：先跳过前 ii 行的所有元素（每行有 nn 个），再加上当前行偏移的 jj 个元素。

Address(A[i][j])=Base+(i×n+j)×L\text{Address}(A[i][j]) = \text{Base} + (i \times n + j) \times L

按列内存地址计算公式 都差不多，不多解释了。 Address(A[i][j])=Base+(j×m+i)×L\text{Address}(A[i][j]) = \text{Base} + (j \times m + i) \times L

重点： 对称矩阵访问上三角元素时，不是没有存储，而是去访问其对应的下三角元素。

2. 三角矩阵

下三角矩阵 下三角矩阵满足主对角线以上的元素全为 0：

aij=0,i<ja_{ij}=0,\quad i<j

只需存储下三角区域，共 n(n+1)2\frac{n(n+1)}{2} 个非零元素。

上三角矩阵（公式随便看看，不重要） 上三角矩阵满足：

aij=0,i>ja_{ij}=0,\quad i>j

若按行存储上三角部分，前 ii 行已经存储的元素个数为：

n+(n−1)+⋯+(n−i+1)n+(n-1)+\cdots+(n-i+1)

因此，当 i≤ji\le j 时：

k=in−i(i−1)2+j−ik=in-\frac{i(i-1)}{2}+j-i

当 i>ji>j 时，元素值为 0。

一般三角矩阵 有些题目规定三角区域外的元素不是 0，而是同一个常数 cc。此时可在一维数组末尾额外增加一个位置存储 cc。总空间为：

n(n+1)2+1\frac{n(n+1)}{2}+1

3. 三对角矩阵

三对角矩阵只有以下三条对角线上的元素可能非零：

  • 主对角线；
  • 主对角线上方一条对角线；
  • 主对角线下方一条对角线。

注意第1 行/列 与最后1 行/列 只有两个元素。例如：

[a00a0100a10a11a1200a21a22a2300a32a33]\begin{bmatrix} a_{00}&a_{01}&0&0\\ a_{10}&a_{11}&a_{12}&0\\ 0&a_{21}&a_{22}&a_{23}\\ 0&0&a_{32}&a_{33} \end{bmatrix}

压缩后为：

[a00,a01,a10,a11,a12,a21,a22,a23,a32,a33][a_{00},a_{01},a_{10},a_{11},a_{12},a_{21},a_{22},a_{23},a_{32},a_{33}]

三、稀疏矩阵

1. 基本概念

设矩阵共有 m×nm\times n 个元素，其中只有 tt 个非零元素。当 t≪mnt\ll mn 时，称该矩阵为稀疏矩阵。（不用在意 tt 为多少，感觉少就是少）。

稀疏矩阵必须同时存储：

  • 元素值；
  • 元素所在的行号；
  • 元素所在的列号。

2. 三元组表示

每个非零元素表示成 (i,j,aij)(i,j,a_{ij})，即：行号 ii、列号 jj、元素值 aija_{ij}。

本质一维数组

例如矩阵：

[005200070]\begin{bmatrix} 0&0&5\\ 2&0&0\\ 0&7&0 \end{bmatrix}

三元组表示为：

行号 列号 值
0 2 5
1 0 2
2 1 7

通常还需要保存矩阵的基本信息 (m,n)(m,n)，分别表示行数、列数和非零元素个数。

3. 三元组顺序表特点

优点：

  • 比二维数组节省空间；
  • 结构简单；
  • 适合按行顺序访问；
  • 便于进行转置、加法等运算。

缺点：

  • 随机访问某个 aija_{ij} 较慢；
  • 插入、删除元素时需要移动后续数据；
  • 查找某元素可能需要顺序扫描。

空间复杂度为 O(t)O(t)。

四、稀疏矩阵的十字链表（到了图的部分在仔细学，随便看看就行）

当稀疏矩阵需要频繁插入、删除和按行、按列访问时，可以使用十字链表。

1. 非零结点结构

每个非零元素结点通常包含：

  • row：行号
  • col：列号
  • value：元素值
  • right：指向同一行的下一个非零元素
  • down：指向同一列的下一个非零元素

同一个结点同时属于一条行链表和一条列链表，这就是“十字”的含义。

2. 头指针数组

一般设置：

  • rhead[i]：第 ii 行第一个非零结点；
  • chead[j]：第 jj 列第一个非零结点。

因此可以分别按行或按列遍历矩阵。

3. 十字链表特点

优点：

  • 插入和删除非零元素比较方便；
  • 可以按行访问，也可以按列访问；
  • 适合矩阵结构经常变化的情况。

缺点：

  • 每个结点需要额外存储两个指针；
  • 结构和算法比三元组顺序表复杂；
  • 指针会带来额外空间开销。

五、特殊矩阵与稀疏矩阵对比

对比项 特殊矩阵 稀疏矩阵
元素位置 有固定规律 通常没有固定规律
是否需要存下标 通常不需要 必须存储行、列位置
典型类型 对称、三角、三对角 任意少量非零元素矩阵
常用结构 一维数组 三元组、CSR、十字链表
空间复杂度 常为 O(n)O(n) 或 O(n2/2)O(n^2/2) 通常为 O(t)O(t)