特殊矩阵的压缩存储（对称矩阵，三角矩阵，三对角矩阵，稀疏矩阵）
目录
- 1.数组的存储结构
- 1.—维数组
- 2.二维数组
- 1.行优先存储
- 2.列优先存储
- 2.特殊矩阵
- 1.对称矩阵
- 1.行优先存储
- 2.三角矩阵
- 1.上三角矩阵
- 2.下三角矩阵
- 3.三对角矩阵（带状矩阵）
- 4.稀疏矩阵
1.数组的存储结构
1.—维数组
各数组元素大小相同，且物理上连续存放。
数组元素a[i]的存放地址= 起始地址 L O C + i ∗ s i z e o f ( E l e m T y p e ) ( 0 < i < 10 ) 起始地址LOC+i * sizeof(ElemType)(0<i<10) 起始地址LOC+i∗sizeof(ElemType)(0<i<10)
2.二维数组
1.行优先存储
M行N列的二维数组b[M][N]中，若按
行优先存储，
则b[i][j]的存储地址= L O C + ( i ∗ N + j ) ∗ s i z e o f ( E l e m T y p e ) LOC + (i*N+ j) * sizeof(ElemType) LOC+(i∗N+j)∗sizeof(ElemType)
2.列优先存储
M行N列的二维数组b[M][N]中，若按
列优先存储，
则b[i][i]的存储地址= L O C + ( j ∗ M + i ) ∗ s i z e o f ( E l e m T y p e ) LOC+ ( j*M+i ) * sizeof(ElemType) LOC+(j∗M+i)∗sizeof(ElemType)
2.特殊矩阵
1.对称矩阵
若n阶
方阵中任意一个元素aij,都有 a i j = a j i aij=aji aij=aji则该矩阵为对称矩阵。
压缩存储策略：只存储主对角线+下三角区(或主对角线+上三角区)
1.行优先存储
1.下三角区
策略:只存储主对角线+下三角区。
①存储的数组长度： ( 1 + n ) ∗ n / 2 (1+n)*n/2 (1+n)∗n/2
②矩阵下标 a i j aij aij与一维数组下标k的映射关系： k = i ( i − 1 ) 2 + j − 1 , i > = j k=\frac{i(i-1)}{2}+j-1,i>=j k=2i(i−1)+j−1,i>=j
2.上三角区
根据对称矩阵的性质： a i j = a j i aij = aji aij=aji：
k = j ( j − 1 ) 2 + i − 1 , i < j k=\frac{j(j-1)}{2}+i-1,i<j k=2j(j−1)+i−1,i<j
2.三角矩阵
压缩存储策略：按
行优先原则将橙色区元素存入一维数组中。并在最后一个位置存储常量c。
1.上三角矩阵
除了主对角线和上三角区，其余的元素都相同。
按照行优先的原则，映射关系： k = ( i − 1 ) ( 2 n − i + 2 ) 2 + j − i ， i < = j ( 上三角区和主对角线元素 ) k=\frac{(i-1)(2n-i+2)}{2}+j-i，i<=j(上三角区和主对角线元素) k=2(i−1)(2n−i+2)+j−i，i<=j(上三角区和主对角线元素)
k = n ( n + 1 ) 2 ， i > j ( 下三角区元素 ) k = \frac{n(n+1)}{2}，i>j(下三角区元素) k=2n(n+1)，i>j(下三角区元素)
2.下三角矩阵
除了主对角线和下三角区，其余的元素都相同。
按照行优先的原则，映射关系： k = i ( i − 1 ) 2 + j − 1 ， i > = j ( 下三角区和主对角线元素 ) k=\frac{i(i-1)}{2}+j-1，i>=j(下三角区和主对角线元素) k=2i(i−1)+j−1，i>=j(下三角区和主对角线元素)
k = n ( n + 1 ) 2 ， i < j ( 上三角区元素 ) k = \frac{n(n+1)}{2}，i<j(上三角区元素) k=2n(n+1)，i<j(上三角区元素)
3.三对角矩阵（带状矩阵）
三对角矩阵，又称
带状矩阵： 当 ∣ i − j ∣ > 1 时，有 a i j = 0 ( 1 < = i , j ≤ n ) 当|i -j|>1时，有aij=0 (1<=i, j ≤n) 当∣i−j∣>1时，有aij=0(1<=i,j≤n)
压缩存储策略：按行优先（(或列优先）原则，只存储带状部分。
①已知aij求数组下标k：
前i-1行共 3 ( i − 1 ) − 1 3(i-1)-1 3(i−1)−1个元素
aij是i行第 j − i + 2 j-i+2 j−i+2个元素
aij是第 2 i + j − 2 2i+j-2 2i+j−2个元素
k = 2 i + j − 3 k=2i+j-3 k=2i+j−3(数组下标从0开始)
②若已知数组下标k，如何得到i,j?
即第k+1个元素：
i = 「 ( k + 2 ) / 3 ] i =「(k+2)/3] i=「(k+2)/3]（向上取整）
由 k = 2 i + j − 3 k=2i+j-3 k=2i+j−3得，
j = k − 2 i + 3 j=k-2i+3 j=k−2i+3
4.稀疏矩阵
稀疏矩阵:非零元素远远少于矩阵元素的个数。
压缩存储策略：
①顺序存储：三元组<行，列，值>，会失去随机存储的特性。
例如：
对应的三元组为：
②链式存储：十字链表法
结点说明：
