【数据结构】特殊矩阵的压缩存储

特殊矩阵的压缩存储

1. 一维数组的存储结构

一维数组各元素大小相同，且物理上连续存放。

数组元素a[i]的存放地址=LOC+i*sizeof(ElecType) (0<=i<10)(没有特殊说明，默认下标从0开始)

2. 二维数组的存储结构

• M行N列的二维数组b[M][N]中，若按行优先存储，则：b[i][j]的存储地址=LOC+(i*N+j)*sizeof(ElecType)

• M行N列的二维数组b[M][N]中，若按列优先存储，则：b[i][j]的存储地址=LOC+(j*M+i)*sizeof(ElemType)

3. 普通矩阵存储

普通矩阵的存储可用二维数组。

注意：描述矩阵元素时，行、列号通常从1开始。而描述数组时通常从下标0开始。具体问题具体分析。

4. 对称矩阵的压缩存储

压缩存储策略：只存储主对角线+下三角区，按行优先原则将各元素存入一维数组中。

当i>=j时，矩阵对应的一维数组下标B[k]

当i<j时，矩阵对应的一维数组下标B[k]

综上可得：

5. 三角矩阵的压缩存储

下三角矩阵:除了主对角线和下三角区，其余的元素都相同

压缩存储策略：按行优先原则将橙色区域存入一维数组中。并在最后一个位置存储常量c。

上三角矩阵:除了主对角线和上三角区，其余的元素都相同

压缩存储策略：按行优先原则将绿色区元素存入一维数组中。并在最后一个位置存储常量c。

6. 三对角矩阵的压缩存储

三对角矩阵，又称带状矩阵：

当|i-j|>1时，有ai,j=0(1<=i,j<=n)

压缩存储策略：按行优先（或列优先）原则，只存储带状部分。

思考：若已知数组下标k，如何得到i,j?

第k+1个元素，在第几行？在第几列？

前i-1行共3(i-1)-1个元素。前i行共3i-1个元素。显然3(i-1)-1<k+1<=3i-1

i>=(k+2)/3

i=(k+2)/3 向上取整。

由k=2i+j-3，得：j=k-2i+3

7. 稀疏矩阵的压缩存储

稀疏矩阵：非零元素远远少于矩阵元素的个数。

压缩存储策略一：

顺序存储——三元组<行，列，值>

压缩存储策略二：

链式存储——十字链表法

8. 小结

另外还需关注：

1. 矩阵的压缩存储需要多长数组。
2. 由矩阵行列号<i,j>推出对应的数组下标号k。
3. 由k推出<i,j>。