//稀疏矩陣及其壓縮存儲 
#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; 
 } 
 //普通轉置(行優先存儲) 
 //列變行，從0列開始，將列數據一個一個放進轉置矩陣 
 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];//記錄每行的元素個數 
  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> 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<Triple<T> > _matrix; 
 size_t _row; 
 size_t _col; 
 T _illegal; 
}; 

//對稱矩陣及其壓縮存儲 
 
#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; //對稱矩陣的行列大小 
};