压缩存储值存储极少数的有效数据。使用{row,col,value}三元组存储每一个有效数据,三元组按原矩阵中的位置,以行优先级先后顺序依次存放。#define_CRT_SECURE_NO_WARNINGS1#include<vector>#include<iostream>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():_colSize(0),_rowSize(0){}//矩阵的压缩SparseMatrix(T*a,size_tm,size_tn,constT&invalid):_rowSize(m),_colSize(n),_invalid(invalid){for(size_ti=0;i<m;++i)//行遍历{for(size_tj=0;j<n;++j)//列遍历{if(a[i*n+j]!=invalid){_a.push_back(Triple<T>(a[i*n+j],i,j));}}}}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;}else{cout<<_invalid<<"";}}cout<<endl;}cout<<endl;}SparseMatrix<T>Transport()//列转置{SparseMatrix<T>tmp;tmp._colSize=_rowSize;tmp._rowSize=_colSize;tmp._invalid=_invalid;for(size_ti=0;i<_colSize;++i){size_tindex=0;while(index<_a.size()){if(_a[index]._col==i){Triple<T>t;t._value=_a[index]._value;t._row=_a[index]._col;t._col=_a[index]._row;tmp._a.push_back(t);}++index;}}returntmp;}SparseMatrix<T>FastTransport()//快速转置{SparseMatrix<T>tmp;tmp._colSize=_rowSize;tmp._rowSize=_colSize;tmp._invalid=_invalid;int*rowCounts=newint[_colSize];int*rowStart=newint[_colSize];memset(rowCounts,0,sizeof(int)*_colSize);memset(rowStart,0,sizeof(int)*_colSize);size_tindex=0;while(index<_a.size()){rowCounts[_a[index]._col]++;++index;}rowStart[0]=0;for(size_ti=1;i<_colSize;++i){rowStart[i]=rowStart[i-1]+rowCounts[i-1];}index=0;tmp._a.resize(_a.size());while(index<_a.size()){size_trowIndex=_a[index]._col;int&start=rowStart[rowIndex];Triple<T>t;t._value=_a[index]._value;t._row=_a[index]._col;t._col=_a[index]._row;tmp._a[start++]=t;++index;}returntmp;}protected:vector<Triple<T>>_a;//三元组类型的顺序表size_t_rowSize;//行size_t_colSize;//列T_invalid;//非法值};voidTestSparseMatrix(){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>sm1((int*)a,6,5,0);sm1.Display();SparseMatrix<int>sm2=sm1.Transport();sm2.Display();SparseMatrix<int>sm3=sm1.FastTransport();sm3.Display();}intmain(){TestSparseMatrix();getchar();return0;}