假设在m*n的矩阵中，有t个元素不为0。令稀疏因子s=t/(m*n)，通常认为s<0.05时称为稀疏矩阵。

有时为了节省存储空间，可以对这类矩阵进行压缩存储。所谓的压缩存储就是，为多个相同的值分配存储在一个空间，对零元不分配空间。而稀疏矩阵是只存储有效值，无效值只分配一个空间。

在这里我们用一个顺序表vector存储稀疏矩阵的有效值的行，列，值三个元素。

structTriple{int_cow;int_col;T_value;Triple(intcow,intcol,Tvalue):_cow(cow),_col(col),_value(value){}Triple():_cow(0),_col(0){}};

classSparseMatrix{public:SparseMatrix(T*a,intm,intn,constT&invalid):_cow(m),_col(n),_invalue(invalid){for(inti=0;i<m;++i){for(intj=0;j<n;++j){if(a[i*n+j]!=invalid){Triple<T>tmp(i,j,a[i*n+j]);_a.push_back(tmp);}}}}protected:vector<Triple<T>>_a;int_cow;//矩阵行数int_col;//矩阵列数T_invalue;//无效值};

下面我们来讨论一下稀疏矩阵的转置，转置运算时最简单的一种矩阵运算。要得到转置矩阵，我们只要做到三点。

将矩阵的行列值相互交换

每个三元组的i和j相互交换

重排三元组之间的次序便可以实现转置

SparseMatrix<T>Transport(){SparseMatrix<T>tmp;tmp._cow=_col;tmp._col=_cow;tmp._invalue=_invalue;for(size_ti=0;i<_col;++i)//遍历每一列，找到每一列有效值{size_tindex=0;while(index<_a.size()){if(_a[index]._col==i){Triple<T>tp;tp._col=_a[index]._cow;tp._cow=_a[index]._col;tp._value=_a[index]._value;tmp._a.push_back(tp);}index++;}}returntmp;}

对于矩阵的转置，我们首先得要了解转置后行列的变化。转置前的行变成了转置后的列。对于三元组顺序表中的元素是遵循行优先存储的。所以要得到转置后的每一行的有效值，只要循环遍历转置前的每一列即可。

矩阵的转置可以优化，使用快速转置。

SparseMatrix<T>FastTransport(){SparseMatrix<T>tmp;tmp._cow=_col;tmp._col=_cow;tmp._invalue=_invalue;tmp._a.resize(_a.size());int*cowCount=newint[_col];int*cowStart=newint[_col];memset(cowCount,0,sizeof(int)*_col);memset(cowStart,0,sizeof(int)*_col);size_tindex=0;while(index<_a.size()){cowCount[_a[index++]._col]++;cowStart[0];for(size_ti=1;i<_col;++i){cowStart[i]=cowStart[i-1]+cowCount[i-1];}}index=0;while(index<_a.size()){int&cowBegin=cowStart[_a[index]._col];Triple<T>tp;tp._col=_a[index]._cow;tp._cow=_a[index]._col;tp._value=_a[index]._value;tmp._a[cowBegin]=tp;cowBegin++;index++;}returntmp;}

快速转置的思想是开辟两个数组用来存每一行有效值的个数，另一个用来存每个有效值在转置后顺序表vector中的起始位置。使用数组可以快速找到有效数据在转置后顺序表中的位置

以下是完整代码：

#pragmaonce#include<iostream>#include<vector>usingnamespacestd;template<classT>structTriple{int_cow;int_col;T_value;Triple(intcow,intcol,Tvalue):_cow(cow),_col(col),_value(value){}Triple():_cow(0),_col(0){}};template<classT>classSparseMatrix{public:SparseMatrix(T*a,intm,intn,constT&invalid):_cow(m),_col(n),_invalue(invalid){for(inti=0;i<m;++i){for(intj=0;j<n;++j){if(a[i*n+j]!=invalid){Triple<T>tmp(i,j,a[i*n+j]);_a.push_back(tmp);}}}}SparseMatrix():_cow(0),_col(0){}SparseMatrix<T>Transport(){SparseMatrix<T>tmp;tmp._cow=_col;tmp._col=_cow;tmp._invalue=_invalue;for(size_ti=0;i<_col;++i){size_tindex=0;while(index<_a.size()){if(_a[index]._col==i){Triple<T>tp;tp._col=_a[index]._cow;tp._cow=_a[index]._col;tp._value=_a[index]._value;tmp._a.push_back(tp);}index++;}}returntmp;}SparseMatrix<T>FastTransport(){SparseMatrix<T>tmp;tmp._cow=_col;tmp._col=_cow;tmp._invalue=_invalue;tmp._a.resize(_a.size());int*cowCount=newint[_col];int*cowStart=newint[_col];memset(cowCount,0,sizeof(int)*_col);memset(cowStart,0,sizeof(int)*_col);size_tindex=0;while(index<_a.size()){cowCount[_a[index++]._col]++;cowStart[0];for(size_ti=1;i<_col;++i){cowStart[i]=cowStart[i-1]+cowCount[i-1];}}index=0;while(index<_a.size()){int&cowBegin=cowStart[_a[index]._col];Triple<T>tp;tp._col=_a[index]._cow;tp._cow=_a[index]._col;tp._value=_a[index]._value;tmp._a[cowBegin]=tp;cowBegin++;index++;}returntmp;}voidDisplay(){size_tindex=0;for(inti=0;i<_cow;i++){for(intj=0;j<_col;j++){if(index<_a.size()//此处必须加index<_a.size()这个条件，//并且在最前面访问到最后一个有效值后再_a[index]会访问越界&&_a[index]._cow==i&&_a[index]._col==j){cout<<_a[index]._value<<"";++index;}else{cout<<_invalue<<"";}}cout<<endl;}cout<<endl;}protected:vector<Triple<T>>_a;int_cow;//矩阵行数int_col;//矩阵列数T_invalue;};