普通矩阵

普通矩阵通常直接用二维数组存储。若矩阵为 m 行 n 列，需要存储 m * n 个元素。

描述矩阵元素时常写作 $a_{i,j}$，行列号通常从 1 开始；描述数组位置时通常从 0 开始。

特殊矩阵的压缩存储

特殊矩阵仍然存入一维连续内存。只是特殊矩阵中大量元素可由少量信息推出。因此可以压缩存储只保存必要元素，再通过下标映射恢复矩阵位置。

Matrix compressed storage

这里规定$a_{k}$是物理存储方式中的第$k$个元素，且$1\leqslant k\leqslant total$

对称矩阵满足：

$$
a_{i,j} = a_{j,i}
$$

只需存储主对角线和一个三角区，共$\frac{n(n+1)}{2}$个元素。

若按行优先存储下三角区和主对角线，且矩阵下标从 1 开始、一维数组 B 下标从 0 开始：

$$
k = \frac{i(i-1)}{2} + j - 1,\quad i \ge j
$$

若访问上三角区元素 $a_{i,j}$，利用对称性转成 $a_{j,i}$：

$$
k = \frac{j(j-1)}{2} + i - 1,\quad i < j
$$

下三角矩阵：主对角线和下三角区元素任意，上三角区元素都相同，通常记为常量 c。压缩时存储下三角区和主对角线，再额外存储一个 c。

按行优先存储下三角矩阵：

$$
k =
\begin{cases}
\frac{i(i-1)}{2}+j-1, & i \ge j \
\frac{n(n+1)}{2}, & i < j
\end{cases}
$$

上三角矩阵：主对角线和上三角区元素任意，下三角区元素都相同。按行优先存储上三角矩阵：

$$
k =
\begin{cases}
\frac{(i-1)(2n-i+2)}{2} + (j-i), & i \le j \
\frac{n(n+1)}{2}, & i > j
\end{cases}
$$

三角矩阵的一维数组长度通常是：

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

最后一个位置存放重复常量。

三对角矩阵又称带状矩阵，满足：

$$
|i-j| > 1 \Rightarrow a_{i,j}=0
$$

只存储主对角线、上方一条对角线、下方一条对角线，共 3n - 2 个元素。

按行优先存储，矩阵下标从 1 开始、一维数组下标从 0 开始：

$$
k = 2i + j - 3,\quad |i-j| \le 1
$$

由 k 反求行列时，先确定第 k+1 个存储元素落在哪一行：

$$
i = \left\lfloor \frac{k+1}{3} \right\rfloor + 1
$$

再由映射式得到：

$$
j = k - 2i + 3
$$

稀疏矩阵的非零元素远少于矩阵元素总数，且不一定是方阵。常见压缩方式：

三元组适合顺序扫描和转置等操作；十字链表适合按行、按列都需要快速链接非零元素的场景。