特殊矩阵与稀疏矩阵

特殊矩阵的压缩存储

压缩存储：指为多个值相同的元素只分配一个存储空间，对零元素不分配空间。

特殊矩阵：指具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。常见的特殊矩阵有对称矩阵、上（下）三角矩阵、对角矩阵等。

特殊矩阵的压缩存储方法：找出特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律性分布的、值相同的多个矩阵元素压缩存储到一个存储空间中。

对一个 $n$ 阶矩阵 $A$ 的任意一个元素 $a_{i,j}$ 都有 $a_{i,j} = a_{j,i}(1\le i,j\le n)$

对称矩阵中的元素可以划分为3个部分，即上三角区（i < j）、主对角线（i = j）和下三角区（i > j）。

对于 $n$ 阶对称矩阵，上三角区的所有元素和下三角区的对应元素相同，若仍采用二维数组存放，则会浪费几乎一半的空间，为此将 $n$ 阶对称矩阵 $A$ 存放在数组B[n(n+1)/2]中，即元素 $a_{i,j}$ 存放在 $b_k$ 中。比如只存放下三角部分（含主对角线）的元素。

元素 $a_{i,j}$ 在数组B中的下标 $k = 1 + 2+ ...+(i-1)+j-1=i(i-1)/2+j-1$ （数组下标从0开始）

因此，元素下标之间的对应关系如下：

k = \begin{cases} \frac{i(i-1)}{2}+j-1, &i\ge j \ (下三角区和主对角线元素) \\ \frac{j(j-1)}{2}+i-1,&i\lt j \ (上三角区元素a_{i,j}=a_{j,i})\end{cases}

以下图为例。

将 $a_{3,2}$ 映射到一位数组中，那么此时i = 3, j = 2，前i - 1行的元素是可以通过行数（i）得到的，第i行元素的个数通过j得到。

因此前i - 1行的元素个数为 $1 + 2 + ... +(i -1 )$ ，第i行的元素个数为 $j$ 。

整理之后可得元素 $a_{i,j}$ 在数组B中的下标 $k=\frac{i(i-1)}{2} + j - 1$ ，此处 -1 是因为一维数组B的下标从0开始，若从1开始，则不需要减一。

将 $a_{n,3}$ 映射到一位数组中，那么此时i = n, j = 3，前j - 1列的元素是可以通过列数（j）得到的，第j列元素的个数通过i得到。

因此前j - 1列的元素个数为 $n+(n-1)+...+(n-j+2)$ ，第j列的元素个数为 $i-j$ 。

这里的n - j + 2递推可以得到，第j列的元素个数是 $n-j+1$ 个，那么显然第j - 1列的元素比第j列要多一个。

若数组下标从0开始，则映射为 $k=\frac{(j-1)(2n-j+2)}{2} + (i-j)$ ，若从1开始，则无需-1.

对于矩阵，若另一边的三角区均为同一常量，则成为三角矩阵。

三角矩阵分为上三角矩阵和下三角矩阵。

可以将n阶三角矩阵 $A$ 压缩存储在B[n(n+1)/2+1]中，+ 1 是为了存储那个均为同一常量的三角区的元素。

元素下标之间的对应关系为：

k = \begin{cases} \frac{i(i-1)}{2}+j-1, &i\ge j \ (下三角区和主对角线元素) \\ \frac{n(n+1)}{2},&i\lt j \ (上三角区元素)\end{cases}

元素下标之间的对应关系为：

k = \begin{cases} \frac{(i-1)(2n-i+2)}{2} + (j-i), &i\le j \ (上三角区和主对角线元素) \\ \frac{n(n+1)}{2},&i\gt j \ (下三角区元素)\end{cases}

此处的上三角区和主对角线的映射关系和上述的列优先存储思想类似。

三对角矩阵也称带状矩阵。

对 $n$ 阶矩阵 $A$ 中的任意一个元素 $a_{i,j}$ ，当 $|i-j|\gt 1$ 时，若有 $a_{i,j}=0(1\le i,j\le n)$ ，则成为三对角矩阵。

在三对角矩阵中，所有非零元素都集中在以主对角线为中心的3条对角线的区域，其他区域的元素都为0。

可以计算矩阵 $A$ 中3条对角线上的元素 $a_{i,j}(1\le i,j\le n ,|i-j|\le 1)$ 在一维数组B中存放的下标为 $k=2i+j-3$ 。

反之，若已知三对角矩阵中的某个元素 $a_{i,j}$ 存放在一维数组B的第 $k$ 个位置，则有 $i=\lfloor \frac{k+1}{3}+1 \rfloor,j=k-2i+3$ 。

矩阵中非零元素的个数 $t$ ，相对矩阵元素的个数 $s$ 来说非常少，即 $s \gt t$ 的矩阵称为稀疏矩阵。

若采用常规的方法存储稀疏矩阵，则相当浪费时间，因此仅存储非零元素。但通常非零元素的分布无规律可言，所以仅存储非零元素的值是不够的，还应该存储它的位置，即所在的行和列。

因此，将非零元素及其相应的行和列构成一个三元组（行标，列表，值）。按照某种规律存储这些三元组线性表。

稀疏矩阵压缩存储后便失去了随机存取特性。

稀疏矩阵的三元组表既可以采用数组存储，又可以采用十字链表存储。

当存储稀疏矩阵时，不仅要保存三元组表，而且要保存稀疏矩阵的行数、列数和非零元素的个数。