数据结构与算法_特殊矩阵压缩存储

什么是压缩存储？

把多个相同的元素分配一个存储空间，元素为0的不分配空间。

什么样的矩阵能够压缩？

特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。

什么叫稀疏矩阵？

矩阵中非零元素的个数较少，一般认为非零元素的个数小于5%的矩阵为稀疏矩阵。

1.对称矩阵

对称矩阵比较特殊，其数据元素沿着对角线对称。

对称矩阵根据其对称性，只存储其下三角或者上三角就可以了

如果按行序存储下三角，怎么找到aij的存储位置呢？

把这个矩阵存在一维数组里：

而上三角的元素（i>j），根据对称性，aij = aji，可以直接读取下三角中的aji就可以了，因此按行序存储下三角时，aij的下标为：

存储下标计算秘籍：若果用一维数组s[]存储（下标从0开始），则aij的存储下标k等于aij前面的元素个数：

                        k = aij 前面的元素个数

                        计算地址：

                        LOC(aij) = LOC(a11)+k*L (L:每个元素所占的字节数)

2.三角矩阵

三角矩阵比较特殊，分为下三角矩阵和上三角矩阵，下三角矩阵是指矩阵的下三角有数据，而其余的都是常数c或者为0.

下三角矩阵按行存储在一维数组 s[] 中：

一维数组存储：

下三角矩阵按行序存储时，aij 的下标为：

上三角矩阵按行序存储时：

上三角矩阵按行序存储时， aij 的下标为：

3.对角矩阵

对角矩阵又称为带状矩阵，是指在n*n 的矩阵中，非零元素集中在对角线及其两侧，共L（奇数）条对角线的带状区域内，称为L对角矩阵。

为了节省空间，第一行前面和最后一行后面的d个0可以不存储。"掐头去尾"，需要 L*n - 2*d个空间。