数据结构-二维数组-对称矩阵压缩存储

一、什么是对称矩阵

对称矩阵，顾名思义就是矩阵中的元素是对称的，那具体是关于什么对称呢？就是关于对角线对称，即关于左上角到右下角的对角线对称，如下图：

⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ a 21 a 41 a 61 a 12 a 22 a 62 a 14 a 44 a 64 a 16 a 26 a 46 a 66 ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥

其中a22、a44、a66在对角线上，其他元素都满足aij=aji特点，类似于这样的矩阵就是对称矩阵，（其中只写出来几个示例元素，没表示出来的具有相同的特点）很容易看出只要存储矩阵中的上三角元素或者下三角元素就够了，使得对称元素共享同一存储空间。

二、对称矩阵的压缩存储

这里主要讲只存储下三角区域中的元素，包括对焦线在内总共需要n(n+1)2个存储空间，如下图所示：
数据结构-二维数组-对称矩阵压缩存储
任给aij元素，当i≥j时，从第1行到第(i−1)行共有元素(1+i−1)(i−1)2，即i(i−1)2个元素。元素aij为第i行的第j个元素，我们规定每个元素所占的空间为e，所以可得如下公式：

a d d r e s s (a i j) = a d d r e s s (a 11) + (i (i - 1) 2 + j - 1) e

同理，当i<j时可以得到如下公式：

a d d r e s s (a i j) = a d d r e s s (a 11) + (j (j - 1) 2 + i - 1) e

由于以上两个公式类似，可以合并如下公式：

a d d r e s s (a i j) = a d d r e s s (a 11) + (I (I - 1) 2 + J - 1) e

其中I=max(i,j),J=min(i,j)

以上就是对称矩阵的压缩存储介绍，写得不好，多指教。

数据结构-二维数组-对称矩阵压缩存储

数据结构-二维数组-对称矩阵压缩存储

一、什么是对称矩阵

二、对称矩阵的压缩存储

相关推荐