矩阵的压缩存储

特殊矩阵：矩阵中的元素设置有一定的规律性
稀疏矩阵：矩阵中的元素有很大一部分为零值

特殊矩阵的压缩存储

对称矩阵

对称矩阵： 矩阵中以主对角线为轴进行对称，存在 a[i][j] = a[j][i] 特点的方阵称之为对称矩阵。
例如矩阵：

该矩阵对角线上的数字为 1 8 9 10，在对角线两边的元素是对称的，整个矩阵满足a[i][j] = a[j][i]
当我们队该矩阵无压缩存储时，我们需要使用4*4 = 16个存储空间，但是由于它是对称的，因此我们可以只保存矩阵的上三角或者下三角，这样我们就可以得到整个矩阵模型，而使用的存储空间也会缩小到10.
至此，假设我们拥有一个n*n的对称矩阵，那么我们只需要 n*(n+1)/2 个存储空间就可以将整个矩阵模型保存下来。
假设我们以下三角元素进行存储，那么则有数组 arr[]
其中：
第一行： 1
第二行： 2 8
第三行： 3 5 9
第四行： 4 6 7 10
我们可以发现，当我们准备求得 a[i][j] 元素值时（当 i>=j ，即在下三角内），对应在 arr 数组内的下标为 i*(i+1)/2+j 。
即当 i>=j 时，a[i][j] = arr[i*(i+1)/2+j]；当 i<j 时，a[i][j] = arr[j*(j+1)/2+i]。
（思路：当我们在求 a[i][j] 时，由于我们保存的只是下三角元素，因此第 i 行以上的元素一共有 i*(i+1)/2 个，而 j 恰恰在最后一行的第 j 列，因此在数组中该数字的位置为 i*(i+1)/2+j）

对称矩阵压缩完成。

三角矩阵

三角矩阵：
三角矩阵分为上三角矩阵和下三角矩阵。
上三角矩阵的对角线左下方元素均为零。下三角矩阵的对角线右上方元素均为零。
例如矩阵：

上三角矩阵
下三角矩阵

下三角矩阵的压缩方式同对称矩阵的压缩方式相同，矩阵内元素与数组元素的对应位置关系也是相同的。
所以对于下三角矩阵来讲：
当 i>=j 时，a[i][j] = arr[i*(i+1)/2+j]；当 i<j 时，a[i][j] = 0；

当我们对上三角矩阵进行压缩时：
当 i<=j 时， a[i][j] = arr[i*(2*n-i+1)+j-i]；当 i>j 时，a[i][j] = 0；

PS： 当然，我们这里仅仅是把对角线的一边全部看做是零，当实际应用过程中，有可能对角线的一边不是零而是其他的一个值 C，那么我们就可以构造一个 n*(n+1)/2+1 的数组，最后一个位置保存 C 的值。

对角矩阵

对角矩阵：除了主对角线元素不为零其余所有元素均为零的矩阵。
例如矩阵：

对角矩阵
此类型的矩阵，我们只需要构建一个长度为 n 的数组 arr[] 保存对角线元素即可。
当 i==j 时，a[i][j] = arr[i]；当 i != j 时，arr[i][j] = 0；
当然，我们这里的对角矩阵可以不符合定义，假设我们主对角线的上半部分值为 C，下半部分值为 D，那么我可以构建一个长度为 n+2 的数组arr[] 保存对角线元素，同时最后两位保存C和D。
当i < j 时，a[i][j] = C；当 i == j 时，a[i][j] = arr[i]；当 i > j 时，arr[i][j] = D；

再变形一次，当我们的对角矩阵不再是只有对角线元素随机，例如我们这样子的矩阵：

变形的“对角矩阵”

这个矩阵严格意义上来讲不属于对角矩阵，但是当我们遇到这样的矩阵，我们亦可以对他进行压缩。
设矩阵的阶数为 n ，我们的矩阵斜方向的列数为 k （emmm..理解一下，上述矩阵指得就是[3,6,9][1,4,7,10][2,5,8]三列）。那么我们可以设置一个长度为 nk-2 的数组arr[] 用来保存对角数字。
压缩公式为a[i][j] = arr[2*i+j]。

稀疏矩阵的压缩存储

稀疏矩阵：稀疏矩阵是指含有大量零元素的矩阵。
在矩阵的压缩过程中，我们可以将这个条件拓宽一些，稀疏矩阵中的零元素我们也可以换做成其他的元素，但是必须满足一个条件，就是这个元素的数量必须是大量的。
例如矩阵：

稀疏矩阵
我们定义的另一种“稀疏矩阵”

三元组法

由于在稀疏矩阵中有某一个元素是大量存在的，其他元素分布并不规律，因此我们不但要保存下来元素的值，还要保存元素在矩阵中的位置信息，那么三元组便是一个保存矩阵信息极好的方式。
我们的三元组应该这样来表示：
A[][0] = 行坐标
A[][1] = 列坐标
A[][2] = 该位置的值
我们将所有的普通元素都放到一个三元组中，将其他的元素放到一个三元组中，这样子我们就可以实现一个稀疏矩阵的压缩。
假设有如上的稀疏矩阵（含有零的内个）
我们可以这样压缩：

A[0][0] = 4  // 矩阵的行数     
A[0][1] = 4  // 矩阵的列数
A[0][2] = 3  // 矩阵中非零元素的个数

A[1][0] = 0  // 1 元素的行坐标
A[1][1] = 0  // 1 元素的列坐标
A[1][2] = 1  // 1 元素的值

A[2][0] = 2  // 7 元素的行坐标
A[2][1] = 0  // 7 元素的列坐标
A[2][2] = 2  // 7 元素的值

A[3][0] = 3  // 4 元素的行坐标
A[3][1] = 3  // 4 元素的列坐标
A[3][2] = 4  // 4 元素的值

A[][] = {{4,4,3},{0,0,1},{2,0,2},{3,3,4}} //压缩后的矩阵

当然对于矩阵中含有大量的非零元素来说，我们只需要再创建一个三元组添加到压缩过后的矩阵中即可。