本片博客讨论的特殊矩阵包括两部分：

（1）元素分布有特殊规律的矩阵，寻找规律对应的公式实现压缩存储。如：对称矩阵。

（2）非零元素很少的稀疏矩阵，可采用只存储非零元素的方式实现压缩存储。

首先呢，先来讨论下对称矩阵。

所谓对称矩阵呢，就是行和列相同，上矩阵和下矩阵对称。还是看图吧，一目了然。

看此矩阵，若要将其存储，会浪费空间。就对称这一特征来说，可只存储其上矩阵或者下矩阵。就以存储下矩阵为例。

在此程序中需要注意:

(1)若矩阵为N*N，则需要为其开辟N*（N+1）/2大的数组。

(2)矩阵i行j列的元素对应数组的下标为i*(i+1)/2+j的元素。

即：SymmetricMatrix[i][j] ==> Array[i*(i+1)/2+j]。

代码实现：

template<classT>classSymmetricMatrix{public://声明SymmetricMatrix(T*a,size_tsize);~SymmetricMatrix();T&Access(size_ti,size_tj);voidDisplay();protected:T*_a;//数组size_t_size;//压缩矩阵的下标size_t_n;//方阵的行，列};//函数实现template<classT>SymmetricMatrix<T>::SymmetricMatrix(T*a,size_tsize):_a(newT[size*(size+1)/2])//为_a开辟空间,_size(size*(size+1)/2)//下标,_n(size)//行，列{size_t_index=0;for(size_ti=0;i<_n;i++){for(size_tj=0;j<_n;j++){if(i>=j){_a[_index++]=a[i*_n+j];//下矩阵}else//上矩阵不存储break;}}}template<classT>SymmetricMatrix<T>::~SymmetricMatrix(){if(_a!=NULL){delete[]_a;_a=NULL;_size=0;}}template<classT>T&SymmetricMatrix<T>::Access(size_ti,size_tj)//(i,j)位置上的元素{if(i<j)//上矩阵{swap(i,j);//对称，交换}return_a[i*(i+1)/2+j];}template<classT>voidSymmetricMatrix<T>::Display()//打印对称矩阵{for(size_ti=0;i<_n;i++){for(size_tj=0;j<_n;j++){if(i>=j)//下矩阵{cout<<_a[i*(i+1)/2+j]<<"";}else//上矩阵{cout<<_a[j*(j+1)/2+i]<<"";}}cout<<endl;}cout<<endl;}

测试函数：

voidTest(){intarr[][4]={{0,1,2,3},{1,0,4,5},{2,4,0,6},{3,5,6,0}};SymmetricMatrix<int>sm((int*)arr,4);sm.Display();intret=sm.Access(2,3);cout<<ret<<endl;return0;}

测试结果：

接下来呢，我们看一下稀疏矩阵。

所谓系数矩阵呢，就是指矩阵中的大多数元素为0。当非零元素的个数低于总元素的30%时，这样的矩阵称为稀疏矩阵。如下所示：

如何存储稀疏矩阵呀，对于稀疏矩阵的存储，采取只存储非零元素的方法。由于稀疏矩阵的元素并没有规律，所以在存储元素时，还必须存储非零元素的行号和列号。这就是稀疏矩阵的三元组表示法。

三元组的结构：

template<classT>structTriple{Triple(constT&value=T(),size_trow=0,size_tcol=0)//初始化:_value(value),_row(row),_col(col){}T_value;//值size_t_row;//行size_t_col;//列}

代码实现：

template<classT>classSpareMatrix//稀疏矩阵{public:SpareMatrix();//无参构造函数SpareMatrix(T*a,size_tm,size_tn,constT&invalue);//有参构造函数voidDisplay();//打印SpareMatrix<T>Transport();//转置SpareMatrix<T>FastTransport();//快速转置protected:vector<Triple<T>>_a;//存储三元组的数组size_t_rowSize;//行size_t_colSize;//列T_invalue;//非法值};template<classT>SpareMatrix<T>::SpareMatrix(T*a,size_tm,size_tn,constT&invalue):_rowSize(m),_colSize(n),_invalue(invalue){for(size_ti=0;i<m;i++){for(size_tj=0;j<n;j++){if(a[i*n+j]!=invalue){_a.push_back(Triple<T>(a[i*n+j],i,j));}}}}template<classT>SpareMatrix<T>::SpareMatrix():_rowSize(0),_colSize(0){}template<classT>voidSpareMatrix<T>::Display(){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;}else{cout<<_invalue<<"";}}cout<<endl;}cout<<endl;}template<classT>SpareMatrix<T>SpareMatrix<T>::Transport()//从三元数组上入手，以列为主，重新存储{SpareMatrix<T>tmp;tmp._rowSize=_colSize;//行tmp._colSize=_rowSize;//列tmp._invalue=_invalue;Triple<T>t;for(size_ti=0;i<_colSize;i++){size_tindex=0;while(index<_a.size()){if(_a[index]._col==i){t._row=_a[index]._col;//交换行号，列号t._col=_a[index]._row;t._value=_a[index]._value;tmp._a.push_back(t);}++index;}}returntmp;}template<classT>SpareMatrix<T>SpareMatrix<T>::FastTransport()//快速逆置{SpareMatrix<T>tmp;tmp._rowSize=_colSize;//行tmp._colSize=_rowSize;//列tmp._invalue=_invalue;SpareMatrix<T>rowCount=newint[tmp._rowSize];//记录每一列元素的个数SpareMatrix<T>rowStart=newint[tmp._rowSize];//记录元素在数组上开始的位置memset(rowCount,0,sizeof(int)*tmp._rowSize);//初始化为0memset(rowStart,0,sizeof(int)*tmp._rowSize);size_tindex=0;while(index<_a.size())//统计每一列上的元素个数{rowCount[_a[index]._col]++;++index;}index=0;rowStart[0]=0;for(size_ti=1;i<_colSize;i++)//每个元素在数组中开始的位置{rowSize[i]=rowSize[i-1]+rowCount[i-1];}index=0;tmp._a.resize(_a.size());//开辟空间并默认为0while(index<_a.size()){size_trowIndex=_a[index]._colint&start=rowStart[rowIndex];Triple<T>t;t._value=_value;t._row=col;t._col=_row;tmp._a[start++]=t;}returntmp;}//测试函数：voidTest(){intarr[4][5]={{0,1,0,0,0},{0,0,0,2,0},{0,4,0,0,0},{0,0,3,0,0}};SpareMatrix<int>sm((int*)arr,4,5,int());sm.Display();//sm.Transport((int*)arr,4,5,int());//sm.Display(5,4);SpareMatrix<int>ret=sm.Transport();ret.Display();SpareMatrix<int>ret1=sm.FastTransport();ret1.Display();return0;}

测试结果：