对称矩阵

对于一个矩阵结构显然用一个二维数组来表示是非常恰当的，但在有些情况下，比如常见的一些特殊矩阵，如三角矩阵、对称矩阵、带状矩阵、稀疏矩阵等，从节约存储空间的角度考虑，这种存储是不太合适的。下面从这一角度来考虑这些特殊矩阵的存储方法。

对称矩阵的特点是：在一个n 阶方阵中，有aij=aji ，其中1≤i , j≤n，如图5.5 所示是一个５阶对称矩阵。对称矩阵关于主对角线对称，因此只需存储上三角或下三角部分即可，比如，我们只存储下三角中的元素aij，其特点是j≤i 且1≤i≤n，对于上三角中的元素aij ，它和对应的aji 相等，因此当访问的元素在上三角时，直接去访问和它对应的下三角元素即可，这样，原来需要n*n 个存储单元，现在只需要n(n+1)/2 个存储单元了，节约了n(n-1)/2个存储单元，当n 较大时，这是可观的一部分存储资源。

如何只存储下三角部分呢？对下三角部分以行为主序顺序存储到一个向量中去，在下三角中共有n*(n+1)/2 个元素，因此，不失一般性，设存储到向量SA[n(n+1)/2]中，存储顺序可用图5.6 示意，这样，原矩阵下三角中的某一个元素aij 则具体对应一个sak，下面的问题是要找到k 与i、j 之间的关系。

对于下三角中的元素aij，其特点是：i≥j 且1≤i≤n，存储到SA 中后，根据存储原则，它前面有i-1行，共有1+2+…+i-1=i*(i-1)/2 个元素，而aij 又是它所在的行中的第j 个，所以在上面的排列顺序中，aij 是第i*(i-1)/2+j 个元素，因此它在SA 中的下标k 与i、j 的关系为：
k=i*(i-1)/2+j-1 (０≤k<n*(n+1)/2 )

若i<j，则aij 是上三角中的元素，因为aij=aji ，这样，访问上三角中的元素aij 时则去访问和它对应的下三角中的aji 即可，因此将上式中的行列下标交换就是上三角中的元素在SA 中的对应关系：
k=j*(j-1)/2+i-1 (０≤k<n*(n+1)/2 )

综上所述，对于对称矩阵中的任意元素aij，若令I=max(i,j)，J=min(i,j)，则将上面两个式子综合起来得到： k=I*(I-1)/2+J-1。

三角矩阵

形如图5.7 的矩阵称为三角矩阵，其中c 为某个常数。其中5.7(a)为下三角矩阵：主队角线以上均为同一个常数；(b)为上三角矩阵，主队角线以下均为同一个常数；下面讨论它们的压缩存储方法。

1. 下三角矩阵

与对称矩阵类似，不同之处在于存完下三角中的元素之后，紧接着存储对角线上方的常量，因为是同一个常数，所以存一个即可，这样一共存储了n*(n+1)+1 个元素，设存入向量：SA[n*(n+1)+1]中，这种的存储方式可节约n*(n-1)-1 个存储单元，sak 与aji 的对应关系为：

2. 上三角矩阵

对于上三角矩阵，存储思想与下三角类似，以行为主序顺序存储上三角部分，最后存储对角线下方的常量。对于第1 行，存储n 个元素，第2 行存储n-1 个元素，…，第p 行存储(n-p+1)个元素，aij 的前面有i-1 行，共存储：

个元素，而aij 是它所在的行中要存储的第（j-i+1）个；所以，它是上三角存储顺序中的第(i-1)*(2n-i+2)/2+(j-i+1)个，因此它在SA中的下标为：k=(i-1)*(2n-i+2)/2+j-i。综上， sak 与aji 的对应关系为：

特殊矩阵的压缩存储（转自chunlanse2014）