数值分析中经常出现一些高阶的矩阵，同时在矩阵中有很多值相同的的元素或零元素，有时为了节省空间，可以对这类矩阵进行压缩存储。
压缩存储是指为多个值相同的元素只分配一个空间，对零元素不分配空间。
如果值相同的元素或零元素在矩阵中的分布具有一定规律性，称此类矩阵为特殊矩阵，反之，没有规律的称为稀疏矩阵。
常见的特殊矩阵有对称矩阵、上/下三角矩阵、对角矩阵。
特殊矩阵
如下三种特殊矩阵均为方阵。
对称矩阵
对称矩阵：aij = aji
$$
\begin{bmatrix}
a_0,_0&a_0,_1&…&a_0,_{n-1}\\
a_1,_0&a_1,_1&…&a_1,_{n-1}\\
…&…&a_i,_j&…\\
a_{n-1},_0&a_{n-1},_1&…&a_{n-1},_{n-1}
\end{bmatrix}$$
为一对对称元素分配一个存储空间，于是可将 n2 个元素存储到 n(n+1)/2 个空间中，以行序为主序存储下三角中（包括对角线）的元素。
以一维数组 sa[n(n+1)/2] 作为 n 阶对称对称矩阵的存储结构，于是 sa[k] 与 a[i][j] 之间的映射关系为：
$$k =
\begin{cases}
\frac{i(i+1)}{2}+j& \text{i≥j（下三角及对角线）}\\
\frac{j(j+1)}{2}+i& \text{i<j（下三角）}
\end{cases}$$
对于任意给定一组下标 (i, j)，均可在 sa[] 中找到矩阵元素 aij；
反之，对所有 k = 0, 1, 2,…, n(n+1)/2-1，都能确定 sa[k] 中的元素在矩阵中的位置 (i, j)
。
注：0 ≤ i, j ≤ n-1，0 ≤ k ≤ n(n+1)/2-1
由此，称 sa[n(n+1)/2] 是 n 阶对称矩阵 A 的压缩存储。
三角矩阵
对称矩阵的压缩存储适用于三角矩阵。
下（上）三角矩阵是指矩阵的上（下）三角（不包括对角线）中的元素均为常数 c 或 0 的 n 阶矩阵，于是除了和对称矩阵一样，存储下（上）三角中的元素之外，再加一个存储常数的空间即可。
所以，可以将三角矩阵存储在 sa[n(n+1)/2+1] 中。
(1) 下三角矩阵
$$
\begin{bmatrix}
a_0,_0& & & \\
a_1,_0&a_1,_1& & \\
…&…&a_i,_j& \\
a_{n-1},_0&a_{n-1},_1&…&a_{n-1},_{n-1}
\end{bmatrix}$$
可以计算，下三角矩阵 sa[k] 与 a[i][j] 之间的映射关系为（0 ≤ i, j ≤ n-1，0 ≤ k ≤ n(n+1)/2）：
$$k =
\begin{cases}
\frac{i(i+1)}{2}+j& \text{i≥j（下三角及对角线）}\\
\frac{n(n+1)}{2}& \text{i<j（上三角常数）}
\end{cases}$$
前面 sa[0 ~ n(n+1)/2-1] 空间和对阵矩阵压缩一样存储下三角区域元素，最后一个空间 sa[n(n+1)/2] 存储上三角区域常数。
| k=0 | 1 | 2 | 3 | 4 | … | n(n+1)/2-1 | n(n+1)/2 |
|---|---|---|---|---|---|---|---|
| a00 | a10 | a11 | a20 | a21 | … | an-1n-1 | c |
| i=0 | i=1 | i=1 | i=2 | i=2 | … | i=n-1 |
(2)上三角矩阵
$$
\begin{bmatrix}
a_0,_0&a_0,_1&…&a_0,_{n-1}\\
&a_1,_1&…&a_1,_{n-1}\\
& &a_i,_j&…\\
& & &a_{n-1},_{n-1}
\end{bmatrix}$$
可以计算，上三角矩阵 sa[k] 与 a[i][j] 之间的映射关系为（0 ≤ i, j ≤ n-1，0 ≤ k ≤ n(n+1)/2）：
$$k =
\begin{cases}
\frac{i(2n+1-i)}{2}+j-i& \text{i≤j（上三角及对角线）}\\
\frac{n(n+1)}{2}& \text{i>j（下三角常数）}
\end{cases}$$
前面 sa[0 ~ n(n+1)/2-1] 空间和对阵矩阵压缩一样存储下三角区域元素，最后一个空间 sa[n(n+1)/2] 存储上三角区域常数。
| k=0 | 1 | 2 | 3 | 4 | … | n(n+1)/2-1 | n(n+1)/2 |
|---|---|---|---|---|---|---|---|
| a00 | a10 | a11 | a20 | a21 | … | an-1n-1 | c |
| i=0 | i=1 | i=1 | i=2 | i=2 | … | i=n-1 |
三对角矩阵
对角矩阵也称为带状矩阵，在这种矩阵中，所有非零元素集中在 以主对角线为中心的带状区域 中，即除了主对角线和直接在对角线上、下方若干对角线上的元素外，所有其余元素均为零。一种最常见对角矩阵是三对角矩阵。
对于 n 阶矩阵 A 中的任一元素 aij，满足如下条件则称为三对角矩阵。
当 | i - j | > 1 时，aaij = 0 ( 0 ≤ i, j ≤ n-1 )。
在三对角矩阵中，所有非零元素均集中在以主对角线为中心的 3 条对角线区域，其他区域的元素均为零。
$$
\begin{bmatrix}
a_0,_0&a_0,_1& & & \\
a_1,_0&a_1,_1&a_1,_2& & \\
&a_2,_1&a_2,_2&a_2,_3& & \\
& &…&…&…& \\
& &…&…&…& \\
& & &a_{n-2},_{n-3}&a_{n-2},_{n-2}&a_{n-2},_{n-1}\\
& & & &a_{n-1},_{n-2}&a_{n-1},_{n-1}
\end{bmatrix}$$
三对角矩阵也可进行压缩存储，将 3 条对角线上的元素按照行序为主序的当时存放在一维数组 sa[3n-2] 中，a00 存放在 sa[0] 中。（也可以按照对角线的顺序存储）
可以计算 sa[k] 与 a[i][j] 之间的映射关系为（0 ≤ i, j ≤ n-1，0 ≤ k ≤ 3n-3）：
$$k =
\begin{cases}
2i+j& \text{|i-j|≤1（3 对角线区域）}\\
3n-2& \text{（其他，如果为0可以不存储）}
\end{cases}$$
| k=0 | 1 | 2 | 3 | 4 | … | 3n-4 | 3n-3 |
|---|---|---|---|---|---|---|---|
| a00 | a01 | a10 | a11 | a12 | … | an-1n-2 | an-1n-1 |
| i=0 | i=0 | i=1 | i=1 | i=1 | … | i=n-1 | i=n-1 |
稀疏矩阵
矩阵中非零元素数量 t 相对于矩阵元素数量 m×n 非常小，即 t << m×n 的矩阵称为稀疏矩阵。
三元组顺序表
三元组存储元素在矩阵中的行、列位置信息和值信息，失去了数组随机存储的特性。
行逻辑链接顺序表
在三元组顺序表基础上增加辅助信息 —— 每一行首元素在顺序表中的位置（行链接信息），称这种“带行链接信息”的三元组顺序表为行逻辑链接顺序表。
十字链表
矩阵非零元素个数和位置在操作过程中变化很大时，不宜采用顺序存储结构存储，因为在进行插入和删除操作时会引起元素的移动，增加了时间消耗，此时因采用链式存储结构。
DONE！