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!