对称矩阵

设一个N*N的方阵A，A中的任意元素A[i][j]，当且仅当A[i][j]=A[j][i],则矩阵A是对称矩阵，以对角线分隔，分为上三角和下三角

压缩矩阵存储对称矩阵时只需要存储其上三角或者下三角的数据，即最多存储n(n+1)/2个数据,对应关于为：i>j,symmetricMatrix[i][j]=A[i*(i+1)/2+j]

代码实现：

template<classT>classSymmetricMatrix{public:SymmetricMatrix(T*a,size_tnum):_a(newT[num*(num+1)/2])//开辟一块压缩矩阵的空间，n*（n+1）/2,_size(num*(num+1)/2),_n(num){for(size_ti=0;i<_n;i++){for(size_tj=0;j<=i;j++){_a[i*(i+1)/2+j]=a[i*num+j];//把矩阵中的元素存入压缩矩阵中}}}~SymmetricMatrix(){if(_a){delete[]_a;/*_a=NULL;_size=0;_n=0;*/}}voidDisplay(){for(size_ti=0;i<_n;i++){for(size_tj=0;j<_n;j++){/*当i>=j打印下矩阵，当i<j，交换i,j打印上矩阵*/if(i<j)Access(i,j);cout<<_a[i*(i+1)/2+j]<<"";if(i<j)Access(i,j);/*if(i>=j)cout<<_a[i*(i+1)/2+j]<<"";elsecout<<_a[j*(j+1)/2+i]<<"";*/}cout<<endl;}cout<<endl;}protected:voidAccess(size_ti,size_tj){if(i<j){swap(i,j);}}private:T*_a;//数组size_t_size;//压缩矩阵大小size_t_n;//矩阵为N*N};voidtest(){inta[][4]={0,1,2,3,1,0,5,6,2,5,0,8,3,6,8,0};size_tlenth=sizeof(a)/sizeof(a[0]);SymmetricMatrix<int>Array((int*)a,lenth);Array.Display();}intmain(){test();}


稀疏矩阵

M*N的矩阵，矩阵中有效值的个数远远小于无效值的个数，这些数据的分布，没有规律

压缩存储只需要存储极少的有效数据，用三元组{row，col，value}存储，三元组按原矩阵中的位置，以行优先级先后顺序依次存放。

#include<iostream>#include<vector>usingnamespacestd;template<classT>structTriple//三元组{T_value;//值size_t_row;//行size_t_col;//列Triple(constT&value=T(),size_trow=0,size_tcol=0):_value(value),_row(row),_col(col){}};template<classT>classSparseMatrix{public:SparseMatrix(T*a,size_tm,size_tn,constT&invalid)//构造:_rowSize(m),_colSize(n),_invalid(invalid){for(size_ti=0;i<_rowSize;i++){for(size_tj=0;j<_colSize;j++){if(a[i*_colSize+j]!=_invalid){_a.push_back(Triple<T>(a[i*_colSize+j],i,j));/*压缩矩阵，循环找到矩阵中不为_invalid的元素，存储到顺序表中*/}}}}voidDisplay(){size_tindex=0;//顺序表中元素序号for(size_ti=0;i<_rowSize;i++){for(size_tj=0;j<_colSize;j++){/*循环寻找与顺序表中行号、列号相同的元素*/if(index<_a.size()&&_a[index]._row==i&&_a[index]._col==j){cout<<_a[index]._value<<"";++index;}elsecout<<_invalid<<"";}cout<<endl;}cout<<endl;}private:vector<Triple<T>>_a;size_t_rowSize;size_t_colSize;T_invalid;};voidtest(){inta[][5]={1,0,3,0,5,0,0,0,0,0,0,0,0,0,0,2,0,4,0,6,0,0,0,0,0,0,0,0,0,0};SparseMatrix<int>Array((int*)a,6,5,0);Array.Display();}intmain(){test();}