c++矩阵的转置和快速转置

2025-01-12 技术教程

矩阵的转置

将原矩阵的行、列对换，也就是将[i][j]和[j][i]位置上的数据对换。

程序代码：

#include<vector>//稀疏矩阵pushpopoperator[]和顺序表一致template<classT>structTriple//定义一个三元组可以直接访问的定义成struct{size_t_row;size_t_col;T_value;Triple(size_trow,size_tcol,constT&value):_row(row),_col(col),_value(value){}};template<classT>classSparseMatrix{public:SparseMatrix(size_tM,size_tN,constT&invalid):_M(M),_N(N),invalid(invalid){}SparseMatrix(constT*a,size_tM,size_tN,constT&invalid)//constT&invalid表示哪个是无效数据:_M(M),_N(N),invalid(invalid){for(size_ti=0;i<M;++i){for(size_tj=0;j<N;++j){if(a[i*N+j]!=invalid)//不等于无效值{Triple<T>t(i,j,a[i*N+j]);_a.push_back(t);}}}}voidDisplay(){size_tindex=0;for(size_ti=0;i<_M;++i){for(size_tj=0;j<_N;++j){if(index<_a.size()&&i==_a[index]._row&&j==_a[index]._col){cout<<_a[index].value<<"";++index;}else{cout<<_invalid<<"";}}cout<<endl;}cout<<endl;}SparseMatrix<T>Transport()//转置{//时间复杂度O(有效数据的个数*N（列））SparseMatrix<T>sm(_N,_M,_invalid);for(size_ti=0;i<N;++i){size_tindex=0;while(index<_a.size()){if(_a[index].col==i){Triple<T>t(_a[index]._col,_a[index]._row,_a[index]._value);sm._a.push_back(t);}++index;}}returnsm;}protected://存三元组数组//Triple<T>*_a;直接用动态顺序表vector<Triple<T>>_a;size_t_M;size_t_N;T_invalid;};voidTest2(){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>sm((int*)a,6,5,0);//强制转换成一维数组数组6行5列非法值0sm.Display();SparseMatrix<int>sm2=sm.Transport();sm2.Display();}#include<iostream>usingnamespacestd;#include<stdlib.h>#include"Matrix.h"intmain(){//Test1();Test2();system("pause");return0;}

运行结果：

1 0 0 2 0 0

0 0 0 0 0 0

3 0 0 4 0 0

0 0 0 0 0 0

5 0 0 6 0 0

快速转置

程序代码：

#include<vector>//稀疏矩阵pushpopoperator[]和顺序表一致template<classT>structTriple//定义一个三元组可以直接访问的定义成struct{size_t_row;size_t_col;T_value;Triple(size_trow=0,size_tcol=0,constT&value=T())//const临时对象具有常性:_row(row),_col(col),_value(value){}};template<classT>classSparseMatrix{public:SparseMatrix(size_tM,size_tN,constT&invalid):_M(M),_N(N),invalid(invalid){}SparseMatrix(constT*a,size_tM,size_tN,constT&invalid)//constT&invalid表示哪个是无效数据:_M(M),_N(N),invalid(invalid){for(size_ti=0;i<M;++i){for(size_tj=0;j<N;++j){if(a[i*N+j]!=invalid)//不等于无效值{Triple<T>t(i,j,a[i*N+j]);_a.push_back(t);}}}}voidDisplay(){size_tindex=0;for(size_ti=0;i<_M;++i){for(size_tj=0;j<_N;++j){if(index<_a.size()&&i==_a[index]._row&&j==_a[index]._col){cout<<_a[index].value<<"";++index;}else{cout<<_invalid<<"";}}cout<<endl;}cout<<endl;}SparseMatrix<T>FastTransport()//快速转置{//时间复杂度O(有效数据个数+N)SparseMatrix<T>sm(_N,_M,_invalid);int*rowCounts=newint[_N];//统计转置后数据个数memset(rowCounts,0,sizeof(int)*_N);size_tindex=0;while(index<_a.size()){rowCounts[_a[index].col]++;++index;}introwStart=newint[_N];rowStart[0]=0;for(size_ti=1;i<_N;++i){rowStart[i]=rowStart[i-1]+rowCounts[i-1];}index=0;sm._a.resize(_a.size())';'//不能用pushbackwhile(index<_a.size())//_a.size有效数据的个数{size_trow=_a[index]._col;int&start=rowStart[row];Triple<T>t(_a[index]._col,_a[index]._row,_a[index]._value);sm._a[start]=t;++start;//rowStart[row]里的值++++index；}delete[]rowCounts;delete[]rowStart;returnsm;}protected://存三元组数组//Triple<T>*_a;直接用动态顺序表vector<Triple<T>>_a;size_t_M;size_t_N;T_invalid;};voidTest2(){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>sm((int*)a,6,5,0);//强制转换成一维数组数组6行5列非法值0sm.Display();SparseMatrix<int>sm2=sm.Transport();sm2.Display();SparseMatrix<int>sm3=sm.FastTransport();sm3.Display();}#include<iostream>usingnamespacestd;#include<stdlib.h>#include"Matrix.h"intmain(){//Test1();Test2();system("pause");return0;}

运行结果：

1 0 0 2 0 0

0 0 0 0 0 0

3 0 0 4 0 0

0 0 0 0 0 0

5 0 0 6 0 0