稀疏矩阵：矩阵中大多数元素为0的矩阵（本文以行序为主序）

稀疏矩阵的三元组表述法：

类型结构：

template<typenameT>structTriple{int_row;int_col;T_value;};template<typenameT>classSparseMatrix{public:SparseMatrix<T>::SparseMatrix();SparseMatrix(constT*array,size_trow,size_tcol,constT&invalid);~SparseMatrix();voidDisplay()const;SparseMatrix<T>Transport()const;SparseMatrix<T>FastTransport()const;protected:vector<Triple<T>>_array;size_t_rowCount;size_t_colCount;T_invalid;};

代码实现压缩存储：

//稀疏矩阵template<typenameT>SparseMatrix<T>::SparseMatrix(){}template<typenameT>SparseMatrix<T>::SparseMatrix(constT*array,size_trow,size_tcol,constT&invalid):_rowCount(row),_colCount(col),_invalid(invalid){assert(array);for(size_ti=0;i<row;++i){for(size_tj=0;j<col;++j){if(array[i*col+j]!=invalid){this->_array.push_back({i,j,array[i*col+j]});}}}}template<typenameT>SparseMatrix<T>::~SparseMatrix(){}template<typenameT>voidSparseMatrix<T>::Display()const{size_tsize=this->_array.size();size_tiCount=0;for(size_ti=0;i<this->_rowCount;++i){for(size_tj=0;j<this->_colCount;++j){if(iCount<size&&i==this->_array[iCount]._row&&j==this->_array[iCount]._col){cout<<this->_array[iCount]._value<<"";++iCount;}else{cout<<this->_invalid<<"";}}cout<<endl;}}

稀疏矩阵的转置：

1）列序递增转置法：找出第i行全部元素：从头到尾扫描三元组表A，找出其中所有_col==i的三元组，转置后放入三元组表B中。代码实现如下：

template<typenameT>SparseMatrix<T>SparseMatrix<T>::Transport()const{SparseMatrix<T>ret;ret._rowCount=this->_colCount;ret._colCount=this->_rowCount;ret._invalid=this->_invalid;size_tsize=this->_array.size();for(size_tcol=0;col<this->_colCount;++col){for(size_tiCount=0;iCount<size;++iCount){if(this->_array[iCount]._col==col){ret._array.push_back({this->_array[iCount]._col,this->_array[iCount]._row,this->_array[iCount]._value});}}}returnret;}

2）一次定位快速转置法

在方法1中为了使转置后矩阵的三元组表B仍按行序递增存放，必须多次扫描被转置的矩阵的三元组表A。为了能将被转置三元组表A的元素一次定位到三元组B的正确位置上，需要预先计算以下数据：

i)待转置矩阵三元组表A每一列中非0元素的总个数，即转置后矩阵三元组元素B的每一行的非0元素总个数

ii)待转置矩阵每一列中第一个非0元素在三元组表B中的正确位置，即转置后矩阵每一行中第一个非0元素在三元组B中的正确位置

为此，需要设两个数组分别为num[] 和 pos[] ,其中num[col]用来存放三元组表A第col列中非0元素元素总个数，pos[col]用来存放转置前三元组表A中第col列中第一个非0元素在三元组表B中的存储位置。

num[col]的计算方法：将三元组表A扫描一遍，对于其中列号为col的元素，给相应的num数组中下标为col的元素加1.

pos[col]的计算方法：

i)pos[0] = 0,表示三元组表A中，列值为0的第一个非0元素在三元组表B中的下标值。

ii)pos[col] = pos[col - 1] + num[col - 1],其中1<=col<A.size();

eg:

0 1 9 0 0 0 0

0 0 0 0 0 0 0

3 0 0 0 0 4 0

0 0 2 0 0 0 0

0 8 0 0 0 0 0

5 0 0 7 0 0 0

代码实现：

template<typenameT>SparseMatrix<T>SparseMatrix<T>::Transport()const{SparseMatrix<T>ret;ret._rowCount=this->_colCount;ret._colCount=this->_rowCount;ret._invalid=this->_invalid;size_tsize=this->_array.size();for(size_tcol=0;col<this->_colCount;++col){for(size_tiCount=0;iCount<size;++iCount){if(this->_array[iCount]._col==col){ret._array.push_back({this->_array[iCount]._col,this->_array[iCount]._row,this->_array[iCount]._value});}}}returnret;}template<typenameT>SparseMatrix<T>SparseMatrix<T>::FastTransport()const{SparseMatrix<T>ret;ret._rowCount=this->_colCount;ret._colCount=this->_rowCount;ret._invalid=this->_invalid;size_tsize=this->_array.size();ret._array.resize(size);vector<int>num(this->_colCount);vector<int>pos(this->_colCount);//pos[i]=pos[i-1]+num[i-1]i>0for(size_ti=0;i<size;++i){++num[this->_array[i]._col];}for(size_tcol=1;col<this->_colCount;++col){pos[col]=pos[col-1]+num[col-1];}for(size_ti=0;i<size;++i){ret._array[pos[this->_array[i]._col]++]={this->_array[i]._col,this->_array[i]._row,this->_array[i]._value};}returnret;}

运行结果：