Compressed storage of symmetric and sparse matrices of C++ data structures

Compression storage of symmetric and sparse matrices

1. Sparse matrix

For those matrices where the number of zero elements is much more than the number of non-zero elements, and the distribution of non-zero elements is irregular, it is called sparse matrix (sparse).

People can not give the exact definition of sparse matrix, 1 is generally only based on personal intuition to understand the concept, that is, the number of non-zero elements in the matrix is much smaller than the total number of elements in the matrix, and there is no distribution law of non-zero elements.

Implementation code:

// Sparse matrix and its compressed storage  
#pragma once 
 
#include <vector> 
#include <iostream> 
using namespace std; 
 
template<class T> 
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 T> 
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> t(i,j,arr[i*col+j]); 
     _matrix.push_back(t); 
    } 
   } 
  } 
 } 
 
 void Display() 
 { 
 
  vector<Triple<T> >::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; 
 } 
 // Ordinary transpose ( Row first storage ) 
 // The column changes to the row from 0 The column starts and columns the data 1 a 1 Let's put 1, 2 into the transpose  
 SparseMatrix<T> Transpose() 
 { 
  SparseMatrix<T> 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> t(_matrix[index]._c, _matrix[index]._r, _matrix[index]._value); 
     tm._matrix.push_back(t); 
    } 
    ++index; 
   } 
  } 
  return tm; 
 } 
 
 SparseMatrix<T> FastTranspose() 
 { 
  SparseMatrix<T> tm; 
  tm._row = _col; 
  tm._col = _row; 
  tm._illegal = _illegal; 
  tm._matrix.resize(_matrix.size()); 
 
  int* count = new int[_col];// Records the number of elements per row  
  memset(count, 0, sizeof(int)*_col); 
  int* start = new int[_col];// The position of the elements in the transpose  
  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> t(_matrix[index]._c, _matrix[index]._r, _matrix[index]._value); 
   tm._matrix[start[_matrix[index]._c]++] = t; // The core code  
   ++index; 
  } 
 
  delete[] count; 
  delete[] start; 
  return tm; 
 } 
protected: 
 vector<Triple<T> > _matrix; 
 size_t _row; 
 size_t _col; 
 T _illegal; 
}; 

2. Symmetric matrix

Implementation code:

// Symmetric matrices and their compressed storage  
 
#pragma once 
#include <iostream> 
using namespace std; 
 
template <class T> 
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<n;++j) 
   { 
    if(i >= 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; // The size of the columns and columns of a symmetric matrix  
}; 


 

The above is C++ data structure to achieve sparse matrix and symmetric matrix, if you have any questions, please leave a message or to the site community to exchange discussion, thank you for reading, hope to help you, thank you for your support of the site!