C++ 数据结构之对称矩阵及稀疏矩阵的压缩存储
对称矩阵及稀疏矩阵的压缩存储
1.稀疏矩阵
对于那些零元素数目远远多于非零元素数目,并且非零元素的分布没有规律的矩阵称为稀疏矩阵(sparse)。
人们无法给出稀疏矩阵的确切定义,一般都只是凭个人的直觉来理解这个概念,即矩阵中非零元素的个数远远小于矩阵元素的总数,并且非零元素没有分布规律。
实现代码:
//稀疏矩阵及其压缩存储 #pragmaonce #include#include usingnamespacestd; template structTriple { size_t_r; size_t_c; T_value; Triple(size_trow=0,size_tcol=0,constT&value=T()) :_r(row) ,_c(col) ,_value(value) {} }; template classSparseMatrix { public: SparseMatrix() :_row(0) ,_col(0) ,_illegal(T()) {} SparseMatrix(T*arr,size_trow,size_tcol,constT&illegal) :_row(row) ,_col(col) ,_illegal(illegal) { for(size_ti=0;i t(i,j,arr[i*col+j]); _matrix.push_back(t); } } } } voidDisplay() { vector
>::iteratoriter; iter=_matrix.begin(); for(size_ti=0;i<_row;++i) { for(size_tj=0;j<_col;++j) { if(iter!=_matrix.end() &&iter->_r==i &&iter->_c==j) { cout< _value<<""; ++iter; } else { cout<<_illegal<<""; } } cout< Transpose() { SparseMatrix tm; tm._row=_col; tm._col=_row; tm._illegal=_illegal; tm._matrix.reserve(_matrix.size()); for(size_ti=0;i<_col;++i) { size_tindex=0; while(index<_matrix.size()) { if(_matrix[index]._c==i) { Triple t(_matrix[index]._c,_matrix[index]._r,_matrix[index]._value); tm._matrix.push_back(t); } ++index; } } returntm; } SparseMatrix FastTranspose() { SparseMatrix tm; tm._row=_col; tm._col=_row; tm._illegal=_illegal; tm._matrix.resize(_matrix.size()); int*count=newint[_col];//记录每行的元素个数 memset(count,0,sizeof(int)*_col); int*start=newint[_col];//转置矩阵中元素的位置 start[0]=0; size_tindex=0; while(index<_matrix.size()) { count[_matrix[index]._c]++; ++index; } for(size_ti=1;i<_col;++i) { start[i]=start[i-1]+count[i-1]; } index=0; while(index<_matrix.size()) { Triple t(_matrix[index]._c,_matrix[index]._r,_matrix[index]._value); tm._matrix[start[_matrix[index]._c]++]=t;//核心代码 ++index; } delete[]count; delete[]start; returntm; } protected: vector >_matrix; size_t_row; size_t_col; T_illegal; };
2.对称矩阵
实现代码:
//对称矩阵及其压缩存储 #pragmaonce #includeusingnamespacestd; template classSymmetricMatrix { public: SymmetricMatrix(T*arr,size_tn) :_n(n) ,_matrix(newT[n*(n+1)/2]) { size_tindex=0; for(size_ti=0;i =j) { _matrix[index]=arr[i*n+j]; ++index; } else { continue; } } } } voidDisplay() { for(size_ti=0;i<_n;++i) { for(size_tj=0;j<_n;++j) { /*if(i 以上就是C++数据结构实现稀疏矩阵与对称矩阵,如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!