数据结构学习笔记（6）--特殊矩阵的压缩存储

1.数组的存储结构

（1）一维数组的存储结构

起始地址：LOC

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

数组元素a[i]的存放地址=LOC+i*sizeof(ElemType)    (0<=i<10)

注：除非题目特别说明，否则数组下标默认从0开始。

（2）二维数组的存储结构

M行N列的二维数组b[M][N]中，

若按行优先存储，则b[i][j]的存储地址=LOC+(i*N+j)*sizeof(ElemType);

若按列优先存储，则b[i][j]的存储地址=LOC+(j*M+i)* sizeof(ElemType).

2.特殊矩阵的存储

（1）对称矩阵的压缩存储

策略：只存储主对角线+下三角区

按行优先原则将各元素存入一维数组中，该一维数组的长度应该设置为(1+n)*n/2。

key:按行优先的原则，a[i][j]是第i(i-1)/2+j个元素，数组下标k=i(i-1)/2+j-1(数组下标从0开始)

ai,j存储在一维数组中对应B[k]

k=i(i-1)/2+j-1,i>=j(下三角区和主对角线元素)

k=j(j-1)/2+i-1,i

（2）三角矩阵的压缩存储

压缩存储策略：按行优先原则先将下三角存入一维数组中，并在最后一个位置存储常量c

一维数组的长度：n(n+1)/2+1

①上三角区是常数

ai,j转B[k],k=i(i-1)/2+j-1,i>=j(下三角区和主对角线元素)

k=n(n+1)/2,i

②下三角区是常数

ai,j转B[k],k=(i-1)(2n-i+2)/2+(j-i),j<=j(上三角区和主对角线元素)

k=n(n+1)/2,i>j(下三角区元素)

（3）三对角矩阵的压缩存储

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

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

压缩存储策略：

按行优先（或按列优先）原则，只存储带状部分

一维数组的长度：3n-2

前i-1行共3(i-1)-1个元素

ai,j是i行第j-i+2个元素

ai,j是第2i+j+2个元素

ai,j转B[k],k=2i+j-3

（4）稀疏矩阵的压缩矩阵

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

压缩存储策略：链式存储--十字链表法