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; 
}; 

另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。