C++如何實(shí)現(xiàn)稀疏矩陣的壓縮存儲(chǔ)

這篇文章給大家分享的是有關(guān)C++如何實(shí)現(xiàn)稀疏矩陣的壓縮存儲(chǔ)的內(nèi)容。小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，一起跟隨小編過來看看吧。

C++ 實(shí)現(xiàn)稀疏矩陣的壓縮存儲(chǔ)的實(shí)例

稀疏矩陣：M*N的矩陣，矩陣中有效值的個(gè)數(shù)遠(yuǎn)小于無效值的個(gè)數(shù)，且這些數(shù)據(jù)的分布沒有規(guī)律。 

稀疏矩陣的壓縮存儲(chǔ)：壓縮存儲(chǔ)值存儲(chǔ)極少數(shù)的有效數(shù)據(jù)。使用{row,col,value}三元組存儲(chǔ)每一個(gè)有效數(shù)據(jù)，三元組按原矩陣中的位置，以行優(yōu)先級先后順序依次存放。

實(shí)現(xiàn)代碼：

#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; //可以實(shí)現(xiàn)動(dòng)態(tài)增容的壓縮矩陣 
  size_t _m;  //行 
  size_t _n;  //列 
  T _invalid;   //默認(rèn)值 
 
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, 0, 2, 0, 0 }, 
    { 1, 0, 1, 0, 3 }, 
    { 2, 0, 0, 1, 2 }, 
    { 3, 0, 1, 0, 0 }, 
    { 4, 0, 2, 0, 0 }, 
    { 0, 3, 4, 0, 0 }, 
  }; 
 
  SparseMatrix<int> sm((int*)a, 6, 5, 0); 
  //SymmetricMatrix(int a[][N], size_t N) 
  sm.Display(); 
 
} 
 
 
int main() 
{ 
  test(); 
 
  system("pause"); 
  return 0; 
}

感謝各位的閱讀！關(guān)于“C++如何實(shí)現(xiàn)稀疏矩陣的壓縮存儲(chǔ)”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，讓大家可以學(xué)到更多知識，如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！