資料結構-稀疏矩陣

稀疏矩陣：矩陣中有效資料的個數遠遠小于無效資料的個數，則可以稱之為稀疏矩陣

如果還像以前那樣将每個稀疏矩陣的資料都存儲起來，則會造成記憶體的很大程度的浪費，是以應用特别的存儲方式。

稀疏矩陣的壓縮存儲：

使用{row,col,value}三元組存儲每一個有效資料，三元組按原矩陣中的位置，以行優先級先後順序依次存放。

矩陣的轉置：将矩陣上行列互換，原來的A[i][j]就等于現在的A[j][i] .

矩陣的快速轉置：                                 

建立rowCounts和rowStart, 統計每列的個數和每列起始位置，第i行的起始位置等于上一行的起始位置加上上一行的個數。

#pragma once
#include<vector>
//稀疏矩陣
template<class T>
struct Triple
{
  T _value;//值
  size_t _row;//行
  size_t _col;//列

  Triple(const T& value = T(), size_t row = 0, size_t col = 0)
    :_value(value)
    , _row(row)
    , _col(col)
  {}
};


template <class T>
class SparseMatrix
{
public:
  SparseMatrix()//無參
    :_rowSize(0)
    , _colSize(0)
  {}
  //a為數組   m行  n列  invalid為非法值
  SparseMatrix(T*a, size_t m, size_t n, const T& invalid)
    :_rowSize(m)
    , _colSize(n)
    , _invalid(invalid)
  {
    for (size_t i = 0; i < m; i++)
    {
      for (size_t j = 0; j < n; j++)
      {
        if (a[i*n + j] != invalid)//不等于非法值
        {
          Triple<T> tmp(a[i*n + j], i, j);//構造一個tmp
          _a.push_back(tmp);//放入vector中
        }
      }
    }
  }


  void Print()
  {
    int index = 0;
    for (int i = 0; i < _rowSize; i++)
    {
      for (int j = 0; j < _colSize; j++)
      {
        if ((index < _a.size()) &&
          (_a[index]._row == i) &&
          (_a[index]._col == j))
        {
          cout << _a[index]._value << " ";
          index++;
        }
        else
        {
          cout << _invalid << " ";
        }
      }
      cout << endl;
    }
    cout << endl;
  }


  SparseMatrix<T> Transport()
  {
    SparseMatrix<T> tmp;
    tmp._colSize = _rowSize;
    tmp._rowSize = _colSize;
    tmp._invalid = _invalid;
    for (size_t i = 0; i < _colSize; i++)
    {
      size_t index = 0;
      while (index < _a.size())
      {
        if (_a[index]._col == i)
        {
          Triple<T> t;
          t._value = _a[index]._value;
          t._row = _a[index]._col;//行列互換
          t._col = _a[index]._row;//行列互換
          tmp._a.push_back(t);//壓入tmp
        }
        ++index;
      }
    }
    return tmp;
  }


  //快速轉置的思想：建立rowCounts和rowStart, 統計每列的個數和每列起始位置，
  //第i行的起始位置等于上一行的起始位置加上上一行的個數。
  SparseMatrix<T> FastTransport()
  {
    SparseMatrix<T> result;
    //行列size互換
    result._rowSize = _colSize;
    result._colSize = _rowSize;
    result._invalid = _invalid;

    //建立rowCounts和rowStart
    int* rowCounts = new int[_colSize];
    int* rowStart = new int[_colSize];
    memset(rowCounts, 0, sizeof(int)*_colSize);
    memset(rowStart, 0, sizeof(int)*_colSize);

    result._a.resize(_a.size());//開辟與_a相同的空間，并初始化為0

    for (size_t i = 0; i < _colSize; i++)
    {
      rowCounts[_a[i]._col]++;
    }
    rowStart[0] = 0;

    for (size_t i = 1; i < _colSize; i++)
    {
      rowStart[i] = rowCounts[i - 1] + rowStart[i - 1];
    }

    //快速轉置
    size_t index = 0;
    Triple<T> tmp;
    while (index < _a.size())
    {
      int row = _a[index]._col;//行數
      int rowIndex = rowStart[row];//目前行的起始位置

      //交換行和列
      tmp._value = _a[index]._value;
      tmp._row = _a[index]._col;
      tmp._col = _a[index]._row;

      result._a[rowIndex] = tmp;
      rowStart[row]++;
      index++;
    }
    return result;
  }


protected:
  /*Triple<T>* _a;
  size_t size;*/

  vector<Triple<T>> _a;
  size_t _rowSize;   //行
  size_t _colSize;  //列
  T _invalid;  //非法值
};



void Test()
{
  int array[6][5] =
  {
    { 1, 0, 3, 0, 5 },
    { 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 0 },
    { 2, 0, 4, 0, 6 },
    { 0, 0, 0, 0, 0 },
    { 0, 0, 0, 0, 0 },
  };
  SparseMatrix<int> sm1((int*)array, 6, 5, 0);
  sm1.Print();
  SparseMatrix<int> sm2 = sm1.Transport();
  sm2.Print();

  SparseMatrix<int> sm3 = sm1.FastTransport();
  sm3.Print();


}