对称矩阵的压缩存储

矩阵对于学数学的都不陌生，说白了就是一个二维数组嘛，不过矩阵里有一些很有特色的矩阵，今天我们就来看一种——对称矩阵。

下面来看一个对称矩阵，顺便分析一下，对称矩阵的性质，以便我们随后的研究。

我们看，中间红线标出的就是对称线，既然是对称，那么首先这个矩阵得是方阵，也就是说，行数和列数相等；整个矩阵分为两部分，上三角和下三角，在上三角行号小于列号，而在下三角行号大于列号；最后就是对称表现出来的性质了：a[i][j]=a[j][i]。

那么总结一下，对称矩阵：设一个N*N的矩阵A，A中任意元素A[i][j]，当且A[i][j]==A[j][i](0 <= i <= N-1 && 0 <=j <= N-1)，则矩阵A是对称矩阵。

了解了对称矩阵，我们发现，对称矩阵里的数据有雷同的，那么我们就要想，要是将这些重复的数据去掉的话，是不是可以节省一大波空间呢？

这就是对称矩阵的压缩存储了，知道了对称矩阵的性质之后，我们再存储的时候，只需将下三角或上三角加上对角线存储就可以了。

不过压缩后的矩阵和原矩阵有一个重要的对应关系：

下三角存储i>=j，SymmetricMatrix[i][j] == Array[i*(i+1)/2+j]

那么接下来就来实践一下吧。

#include<iostream> using namespace std; template<class T> class SymmetricMatrix { public: //存储矩阵的下三角：a[i][j]=_array[i*(i+1)/2+j] //1+2+3+……+n=n*(n+1)/2 SymmetricMatrix(T(*a)[5])//一维数组指针 : N(5) { _array = new T[N*(N + 1) / 2]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { _array[i*(i + 1) / 2 + j] = a[i][j]; } } } T& Acess(int row, int col) { if (row < col)//如果是上三角，那么直接将行列数字交换即可 { swap(row, col); } return _array[row*(row + 1) / 2 + col]; } //下三角：row>col const T& Acess(int row, int col)const { if (row < col)//如果是上三角，那么直接将行列数字交换即可 { swap(row, col); } return _array[row*(row + 1) / 2 + col]; } ~SymmetricMatrix() { if (_array) { delete [] _array; //new/delete 匹配使用 _array = NULL; } } void PrintMatrix() { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (i < j) cout << _array[j*(j + 1) / 2 + i]<<" "; else //else 必须有，否则会多执行下面的语句 cout << _array[i*(i + 1) / 2 + j]<<" "; } cout << endl; } } private: T* _array; size_t N; }; void FunTest() { int a[5][5] = { { 0, 1, 2, 3, 4 }, { 1, 0, 1, 2, 3 }, { 2, 1, 0, 1, 2 }, { 3, 2, 1, 0, 1 }, { 4, 3, 2, 1, 0 } }; SymmetricMatrix<int> sm(a); int ret = sm.Acess(2, 3); cout << ret << endl; sm.PrintMatrix(); } int main() { FunTest(); return 0; }