这篇文章主要介绍了C++ 数据结构之对称矩阵及稀疏矩阵的压缩存储的相关资料,这里实现稀疏矩阵和对称矩阵的压缩存储的实例，需要的朋友可以参考下
对称矩阵及稀疏矩阵的压缩存储
1.稀疏矩阵
对于那些零元素数目远远多于非零元素数目，并且非零元素的分布没有规律的矩阵称为稀疏矩阵（sparse）。
人们无法给出稀疏矩阵的确切定义，一般都只是凭个人的直觉来理解这个概念，即矩阵中非零元素的个数远远小于矩阵元素的总数，并且非零元素没有分布规律。
实现代码：
//稀疏矩阵<a style="color:transparent">来源gao($daima.com搞@代@#码(网</a>及其压缩存储 #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<row; ++i) { for(size_t j = 0; j<col; ++j) { if(arr[i*col+j] != illegal) { Triple t(i,j,arr[i*col+j]); _matrix.push_back(t); } } } } void Display() { vector<Triple >::iterator iter; iter = _matrix.begin(); for(size_t i = 0; i<_row; ++i) { for(size_t j = 0; j_r == i &&iter->_c == j) { cout <_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<Triple > _matrix; size_t _row; size_t _col; T _illegal; };
2.对称矩阵
实现代码：
//对称矩阵及其压缩存储 #pragma once #include using namespace std; template class SymmetricMatrix { public: SymmetricMatrix(T* arr, size_t n) :_n(n) ,_matrix(new T[n*(n+1)/2]) { size_t index = 0; for(size_t i = 0; i<n; ++i) { for(size_t j=0; j= j) { _matrix[index] = arr[i*n+j]; ++index; } else { continue; } } } } void Display() { for(size_t i =0; i <_n; ++i) { for(size_t j = 0; j <_n; ++j) { /* if(i<j) { swap(i,j); cout<<_matrix[i*(i+1)/2+j]<<" "; swap(i,j); } else cout<<_matrix[i*(i+1)/2+j]<<" "; */ cout << Access(i,j) << " "; } cout << endl; } cout << endl; } T& Access(size_t row, size_t col) { if(row<col) { swap(row, col); } return _matrix[row*(row+1)/2+col]; } ~SymmetricMatrix() { if(_matrix != NULL) { delete[] _matrix; _matrix = NULL; } } protected: T* _matrix; size_t _n; //对称矩阵的行列大小 };
以上就是C++ 数据结构实现稀疏矩阵与对称矩阵，如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
以上就是C++ 数据结构之对称矩阵及稀疏矩阵的压缩存储的详细内容，更多请关注gaodaima搞代码网其它相关文章！
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：C++ 数据结构之对称矩阵及稀疏矩阵的压缩存储
转载请注明原文链接：C++ 数据结构之对称矩阵及稀疏矩阵的压缩存储
