C++ 数据结构之对称矩阵及稀疏矩阵的压缩存储

对称矩阵及稀疏矩阵的压缩存储

1.稀疏矩阵

　对于那些零元素数目远远多于非零元素数目，并且非零元素的分布没有规律的矩阵称为稀疏矩阵（sparse）。

　　人们无法给出稀疏矩阵的确切定义，一般都只是凭个人的直觉来理解这个概念，即矩阵中非零元素的个数远远小于矩阵元素的总数，并且非零元素没有分布规律。

实现代码：

//稀疏矩阵及其压缩存储 
#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 t(i,j,arr[i*col+j]); 
     _matrix.push_back(t); 
    } 
   } 
  } 
 } 
 
 void Display() 
 { 
 
  vector >::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; 
 } 
 //普通转置(行优先存储) 
 //列变行，从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 > _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= 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) 
   { 
    
    cout << Access(i,j) << " "; 
   } 
   cout << endl; 
  } 
  cout << endl; 
 } 
 
 T& Access(size_t row, size_t col) 
 { 
  if(row

 以上就是C++ 数据结构实现稀疏矩阵与对称矩阵，如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！