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

如下图所示：

一般情况下，我们会想到只要交换对应的行和列，但是这种做法很浪费时间和空间，所以我们可以利用三元组进行存储，压缩存储极少数的有效数据，使用{row，col，value}三元组存储每一个有效数据，三元组按原矩阵中的位置，以行优先级先后顺序依次存放。

#define_CRT_SECURE_NO_WARNINGS1#pragmaonce#include<vector>#include<iostream>usingnamespacestd;template<classT>structTriple//定义三元组{int_row;int_col;T_value;Triple(introw,intcol,T&value):_row(row),_col(col),_value(value){}Triple():_row(0),_col(0),_value(0){}};template<classT>classSparseMatrix{public:SparseMatrix(T*a,intm,intn,constT&invalid)//invalid为非法值:_rowsize(m),_colsize(n),_invaild(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(size_trowsize,size_tcolsize,Tinvaild):_rowsize(rowsize),_colsize(colsize),_invaild(invaild){}voiddisplay(T*a,intm,intn,constT&invalid)//打印稀疏矩阵{intp=0;for(inti=0;i<m;++i){for(intj=0;j<n;j++){if(p<_a.size()&&_a[p]._row==i&&_a[p]._col==j){cout<<_a[p]._value<<"";p++;}else{cout<<invalid<<"";}}cout<<endl;}}SparseMatrix<T>Transport()//逆转矩阵{//务必保持行优先SparseMatrix<T>sm(_colsize,_rowsize,_invaild);for(size_ti=0;i<_colsize;i++){size_tindex=0;while(index<_a.size()){if(_a[index]._col==i){Triple<T>mm;mm._col=_a[index]._row;mm._row=_a[index]._col;mm._value=_a[index]._value;sm._a.push_back(mm);}++index;}}returnsm;}SparseMatrix<T>FastTransport()//快速转置{SparseMatrix<T>temp;temp._a.resize(_a.size());int*rowcounts=newint[_col];int*rowstarts=newint[_col];memset(rowcounts,0,sizeof((int)*_col));memset(rowstarts,0,sizeof((int)*_col));size_tindex=0;while(index<_a.size()){rowcounts[_a[index]._col]++;++index;}rowstarts[0]=0;for(size_ti=0;i<_col;++i){rowstarts[i]=rowstarts[i-1]+rowcounts[i-1];}while(index<_a.size()){size_t&begin=rowstarts[_a[index]._col];Triple<T>tp;tp._row=_a[index]._col;tp._col=_a[index]._row;tp._value=_a[index]._value;tmp._a[rowstarts++]=tp;++index;}delete[]_a;returntmp;}protected:size_t_rowsize;size_t_colsize;T_invaild;vector<Triple<T>>_a;};测试代码如下：voidtest(){inta[6][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>d((int*)a,6,5,0);SparseMatrix<int>tmp=d.Transport();cout<<"转置之前："<<endl;d.display((int*)a,6,5,0);cout<<endl;cout<<"转置之后："<<endl;tmp.display((int*)a,5,6,0);}intmain(){test();system("pause");return0;}

运行结果如下：