C++ 实现稀疏矩阵的压缩存储的实例

C++ 实现稀疏矩阵的压缩存储的实例

稀疏矩阵：M*N的矩阵，矩阵中有效值的个数远小于无效值的个数，且这些数据的分布没有规律。 

稀疏矩阵的压缩存储：压缩存储值存储极少数的有效数据。使用{row,col,value}三元组存储每一个有效数据，三元组按原矩阵中的位置，以行优先级先后顺序依次存放。

实现代码：

#include <iostream> 
#include <vector> 
using namespace std; 
 
template<class T> 
struct Triple    //三元组 
{ 
  size_t _row;  //行 
  size_t _col;  //列 
  T _value;  //值 
 
  Triple(size_t row,size_t col,const T& value) 
    :_row(row),_col(col),_value(value) 
  {} 
}; 
 
 
template<class T> 
class SparseMatrix   //稀疏矩阵 
{ 
protected: 
  vector<Triple<T>> _matrix; //可以实现动态增容的压缩矩阵 
  size_t _m;  //行 
  size_t _n;  //列 
  T _invalid;   //默认值 
 
public: 
  SparseMatrix(T* a,size_t m,size_t n,const T& invalid= T()) 
    :_m(m),_n(n),_invalid(invalid) 
  { 
    for (size_t i = 0; i < m; ++i) 
    { 
      for (size_t j = 0; j < n; ++j) 
      { 
        Triple<T> t(i,j,a[i*n + j]); 
        _matrix.push_back(t); 
      } 
    } 
  } 
 
  void Display() 
  { 
    size_t index = 0; 
    for (size_t i = 0; i < _m; ++i) 
    { 
      for (size_t j = 0; j < _n; ++j) 
      { 
        if (index < _matrix.size() 
          && _matrix[index]._row== i 
          &&_matrix[index]._col ==j) 
        { 
          cout << _matrix[index]._value << " "; 
          ++index; 
        } 
        else 
        { 
          cout << _invalid << " "; 
        } 
      } 
      cout << endl; 
    } 
    cout << endl; 
  } 
 
 
 
}; 

#include <windows.h> 
 
void test() 
{ 
  int a[6][5] = 
  { 
    { 1,2,0 },{ 1,1,3 },{ 2,2 },{ 3,{ 4,{ 0,3,4,}; 
 
  SparseMatrix<int> sm((int*)a,6,5,0); 
  //SymmetricMatrix(int a[][N],size_t N) 
  sm.Display(); 
 
} 
 
 
int main() 
{ 
  test(); 
 
  system("pause"); 
  return 0; 
} 

以上就是稀疏矩阵的压缩存储的实例详解，如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

（编辑：核心网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!