C++数据结构之对称矩阵及稀疏矩阵的压缩存储-创新互联
对称矩阵及稀疏矩阵的压缩存储
创新互联公司主营哈密网站建设的网络公司,主营网站建设方案,app软件开发公司,哈密h5微信平台小程序开发搭建,哈密网站营销推广欢迎哈密等地区企业咨询1.稀疏矩阵
对于那些零元素数目远远多于非零元素数目,并且非零元素的分布没有规律的矩阵称为稀疏矩阵(sparse)。
人们无法给出稀疏矩阵的确切定义,一般都只是凭个人的直觉来理解这个概念,即矩阵中非零元素的个数远远小于矩阵元素的总数,并且非零元素没有分布规律。
实现代码:
//稀疏矩阵及其压缩存储 #pragma once #include#include using namespace std; template struct Triple { size_t _r; size_t _c; T _value; Triple(size_t row = 0, size_t col = 0, const T& value = T()) :_r(row) ,_c(col) ,_value(value) {} }; template class SparseMatrix { public: SparseMatrix() :_row(0) ,_col(0) ,_illegal(T()) {} SparseMatrix(T* arr, size_t row, size_t col, const T& illegal) :_row(row) ,_col(col) ,_illegal(illegal) { for(size_t i = 0; i t(i,j,arr[i*col+j]); _matrix.push_back(t); } } } } void Display() { vector
>::iterator iter; iter = _matrix.begin(); for(size_t i = 0; i<_row; ++i) { for(size_t j = 0; j<_col; ++j) { if(iter!=_matrix.end() &&iter->_r == i &&iter->_c == j) { cout << iter->_value <<" "; ++iter; } else { cout << _illegal <<" "; } } cout << endl; } cout << endl; } //普通转置(行优先存储) //列变行,从0列开始,将列数据一个一个放进转置矩阵 SparseMatrix Transpose() { SparseMatrix tm; tm._row = _col; tm._col = _row; tm._illegal = _illegal; tm._matrix.reserve(_matrix.size()); for(size_t i = 0; i<_col; ++i) { size_t index = 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; } } return tm; } SparseMatrix FastTranspose() { SparseMatrix tm; tm._row = _col; tm._col = _row; tm._illegal = _illegal; tm._matrix.resize(_matrix.size()); int* count = new int[_col];//记录每行的元素个数 memset(count, 0, sizeof(int)*_col); int* start = new int[_col];//转置矩阵中元素的位置 start[0] = 0; size_t index = 0; while(index < _matrix.size()) { count[_matrix[index]._c]++; ++index; } for(size_t i=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; return tm; } protected: vector > _matrix; size_t _row; size_t _col; T _illegal; };
另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
文章名称:C++数据结构之对称矩阵及稀疏矩阵的压缩存储-创新互联
路径分享:http://scyanting.com/article/cddcsp.html