特殊矩阵的压缩存储（对称矩阵，三角矩阵，三对角矩阵，稀疏矩阵）

1.数组的存储结构

1.—维数组

各数组元素大小相同，且物理上连续存放。
数组元素a[i]的存放地址=$起始地址LOC+i\ast sizeof(ElemType)(0<i<10)$

2.二维数组

1.行优先存储

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

2.列优先存储

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

2.特殊矩阵

1.对称矩阵

若n阶方阵中任意一个元素aij,都有$aij=aji$则该矩阵为对称矩阵。
压缩存储策略：只存储主对角线+下三角区(或主对角线+上三角区)

1.行优先存储

1.下三角区
策略:只存储主对角线+下三角区。
①存储的数组长度：$(1+n)\ast n/2$
②矩阵下标$aij$与一维数组下标k的映射关系：$$k=\frac{i(i-1)}{2}+j-1,i>=j$$

2.上三角区
根据对称矩阵的性质：$aij=aji$：
$$k=\frac{j(j-1)}{2}+i-1,i<j$$

2.三角矩阵

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

1.上三角矩阵

除了主对角线和上三角区，其余的元素都相同。
按照行优先的原则，映射关系：$$k=\frac{(i-1)(2n-i+2)}{2}+j-i，i<=j(上三角区和主对角线元素)$$
$$k=\frac{n(n+1)}{2}，i>j(下三角区元素)$$

2.下三角矩阵

除了主对角线和下三角区，其余的元素都相同。
按照行优先的原则，映射关系：$$k=\frac{i(i-1)}{2}+j-1，i>=j(下三角区和主对角线元素)$$
$$k=\frac{n(n+1)}{2}，i<j(上三角区元素)$$

3.三对角矩阵（带状矩阵）

三对角矩阵，又称带状矩阵：$当|i-j|>1时，有aij=0(1<=i,j\le n)$
压缩存储策略：按行优先（(或列优先）原则，只存储带状部分。
①已知aij求数组下标k：
前i-1行共$3(i-1)-1$个元素
aij是i行第$j-i+2$个元素
aij是第$2i+j-2$个元素
$k=2i+j-3$(数组下标从0开始)
②若已知数组下标k，如何得到i,j?
即第k+1个元素：
$i=「(k+2)/3]$（向上取整）
由$k=2i+j-3$得，
$j=k-2i+3$

4.稀疏矩阵

稀疏矩阵:非零元素远远少于矩阵元素的个数。
压缩存储策略：
①顺序存储：三元组<行，列，值>，会失去随机存储的特性。
例如：

对应的三元组为：

②链式存储：十字链表法
结点说明：