2022.7.21 特殊矩阵压缩

什么是压缩存储？
把多个相同的元素分配一个存储空间，元素为0的不分配空间。
什么样的矩阵能够压缩？
特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。
什么叫稀疏矩阵？
矩阵中非零元素个数较少，什么是算少？一般认为非零元素个数少于5%的矩阵为稀疏矩阵。

对称矩阵

对称矩阵比较特殊，其数据元素沿着对角线对称。
对称矩阵根据其对称性，只储存其下三角或上三角就可以了。

其实公式就是由等差数列得出……so easy所以元素总个数就为i*(i-1)/2+j-1
下三角的元素用线性表来表示为：

根据对称性，上三角的元素可以表示为：a[i][j]=a[j][i]

总结：存储下标计算秘籍：如果用一维数组s[]存储（下标从0开始），则a[i][j]的存储下标k等于a[i][j]前面元素数：

k=a[ i ][ j ]前面的元素数

LOC(a[ i ][ j ])=LOC(a[ ll ]）+k*L //L为字节数

三角矩阵

三角矩阵是比较特殊，分为下三角矩阵和上三角矩阵，

1.下三角矩阵是指矩阵的下三角有数据，而其余都是常熟C或者0。

按行存储在一维数组s[ ]中：（常量为0时不存储）

2.上三角矩阵

对角矩阵（考研常考）

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

半带宽=(L-1)/2，除了带状区域，其余元素皆为0不存储。

储存方式（补0）

d就是半带宽。