對稱矩陣、稀疏矩陣及矩陣的逆置與加法

                                                      矩陣之對稱矩陣、稀疏矩陣逆置與加法

一、對稱矩陣及壓縮存儲

由于對稱矩陣對角線上下相同，是以我們可以采取壓縮存儲。

我們先了解一下壓縮存儲，對稱矩陣存儲時隻需要存儲上三角或下三角的資料，是以最多存儲n*(n+1)/2個資料。

我們就知道了我們需要空間的大小。

代碼如下：

#include<iostream>
using namespace std;
#include<vector>

//對稱矩陣
template<class T,size_t N=5>
class SymmetricMatrix
{
public:
  SymmetricMatrix(T(&arr)[N][N])
    :_N(N)
  {
    int index = 0;
    _arr.resize((1 + N)*N >> 1);
    for (size_t i = 0; i < _N; i++)
    {
      for (size_t j = 0; j <= i; j++)
      {
        _arr[index++] = arr[i][j];
      }
    }
  }
  T& Acess(int row, int col)
  {
    if (row < col)
      swap(row, col);
    return _arr[row*(row + 1) / 2 + col];
  }
  void Print()
  {
    for (size_t i = 0; i < N; i++)
    {
      for (size_t j = 0; j < N; j++)
      {
        cout << Acess(i, j) << " ";
      }
      cout << endl;
    }
    cout << endl;
  }
private:
  vector<T> _arr;
  size_t _N;
};

int main()
{
  int a[5][5] = { 
    { 0, 1, 2, 3, 4 },
    { 1, 0, 1, 2, 3 },
    { 2, 1, 0, 1, 2 },
    { 3, 2, 1, 0, 1 },
    { 4, 3, 2, 1, 0 } };
  SymmetricMatrix<int> s(a);
  cout << s.Acess(2, 3) << endl;
  cout << s.Acess(3, 2) << endl;

  s.Acess(3, 2);
  s.Print();

  system("pause");
  return 0;
}      

測試結果如下：

二、稀疏矩陣

1、稀疏矩陣的壓縮存儲和還原

稀疏矩陣：矩陣中有效值的個數遠小于無效值的個數，且這些資料的分布沒有規律。

是以可以采用隻存儲非零元素（有效值）的方法來進行壓縮存儲。在進行壓縮存儲的時侯還要存儲非零元素在矩陣中的位置。是以我們要使用

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

三元組如下：

template<class T>
struct Trituple
{
  size_t _row;
  size_t _col;
  T _value;

  Trituple(int row,int col,int data)
    :_row(row)
    , _col(col)
    , _value(data)
  {}
};      

我們需要一個容器存儲每個節點的内容，代碼如下：

template<class T,int M,int N>
class SparseMatrix
{
public:
  SparseMatrix(int row,int col,T inValid)                  
    :_row(row)
    , _col(col)
    , _inValid(inValid)
  {}
  SparseMatrix(T arr[M][N], T inValid)                 //存儲稀疏矩陣
    :_row(M)
    , _col(N)
    , _inValid(inValid)
  {
    for (size_t i = 0; i < _row; i++)
    {
      for (size_t j = 0; j < _col; j++)
      {
        if (arr[i][j] != inValid)
        {
          Trituple<T> t(i, j, arr[i][j]);
          _v.push_back(t);
        }
      }
    }
  }
  //列印壓縮矩陣
  void display()
  {
    for (size_t i = 0; i < _v.size(); i++)
    {
      cout << _v[i]._value << " ";
    }
  }
  //列印
  void Print()
  {
    size_t index = 0;
    for (size_t i = 0; i < _row; i++)
    {
      for (size_t j = 0; j < _col; j++)
      {
        if (index < _v.size())
        {
          if (_v[index]._row == i&&_v[index]._col == j)
          {
            cout << _v[index++]._value << " ";
          }
          else
          {
            cout << _inValid << " ";
          }
        }
        else
          cout << _inValid << " ";
      }
      cout << endl;
    }
    cout << endl;
  }
  //重載輸出運算符
  friend ostream& operator<<(ostream& cout, SparseMatrix<T, M, N>& Matrix)
  {
    size_t index = 0;
    for (size_t i = 0; i < Matrix._row; i++)
    {
      for (size_t j = 0; j < Matrix._col; j++)
      {
        if (index < Matrix._v.size())
        {
          if (Matrix._v[index]._row == i&&Matrix._v[index]._col == j)
          {
            cout << Matrix._v[index++]._value << " ";
          }
          else
          {
            cout << Matrix._inValid << " ";
          }
        }
        else
          cout << Matrix._inValid << " ";
      }
      cout << endl;
    }
    return cout;
  }
private:
  vector<Trituple<T>> _v;        //儲存有效節點
  size_t _row;
  size_t _col;
  T _inValid;                   //無效值
};      

為了測試友善我加了一個display()函數，是為了檢測壓縮存儲是否正确，列印函數和輸出運算符重載都是輸出稀疏矩陣。

測試：

int main()
{
  int array[5][5] = {
  { 0, 0, 1, 0, 2 },
  { 1, 0, 0, 0, 8 },
  { 0, 0, 0, 1, 3 },
  { 1, 0, 0, 0, 0 },
  { 0, 0, 0, 3, 0 } };

  SparseMatrix<int,5,5> sm(array, 0);
  sm.display();

  sm.Print();
  cout << sm << endl;
  system("pause");
  return 0;
}      

結果以下，有效元素以及整個稀疏矩陣。

三、矩陣的逆置

以上面稀疏矩陣為例，逆置就是将array[i][j]和array[j][i]的值交換。若我們直接将有效節點中的行列交換，輸出的話，能得到我們想要的結果嗎？

函數如下：

//矩陣逆置
  void ReverseMatrix()
  {
    for (size_t index = 0; index < _v.size();index++)
    {
      swap(_v[index]._row, _v[index]._col);
    }
    swap(_row, _col);
  }      

運作結果：

并沒有成功，為什麼呢？

因為首次存儲時是按照行優先的存儲順序，若交換完依然按照行優先順序進行輸出，則不能全部輸出。

我們可以将交換後的有效元素按照行的大小排序，再輸出，如下（冒泡排序）：

//矩陣逆置
  void ReverseMatrix()
  {
    for (size_t index = 0; index < _v.size();index++)
    {
      swap(_v[index]._row, _v[index]._col);
    }
    swap(_row, _col);

    for (size_t i = 0; i < _v.size(); i++)
    {
      for (size_t j = 0; j < _v.size() - i - 1; j++)
      {
        if (_v[j]._row>_v[j + 1]._row)
          swap(_v[j], _v[j + 1]);
      }
    }
  }      

運作結果：

四、矩陣的加法

兩個矩陣相加，即行列相對應的數相加。是以兩個矩陣必須行和列分别相等。

因為我們隻存儲了有效元素，我們可以通過算出各個元素在原矩陣的偏移量，周遊兩個矩陣，偏移量相等時相加；第一個矩陣元素偏移量小時，證明第二個矩陣沒有對應元素。反之亦然。

代碼如下：

SparseMatrix& operator+(SparseMatrix& Matrix)
  {
    //行列分别相等
    if (_row != Matrix._row || _col != Matrix._col)
    {
      cout << "兩個矩陣不能相加" << endl;
      exit(EXIT_FAILURE);
    }

    SparseMatrix* ret = new SparseMatrix(_row, _col, _inValid);
    size_t leftIndex = 0, rightIndex = 0;
    size_t addL = 0, addR = 0;
    while (leftIndex < _v.size() && rightIndex < Matrix._v.size())
    {
      //在原矩陣中的偏移量
      addL = _v[leftIndex]._row*_col + _v[leftIndex]._col;
      addR = Matrix._v[rightIndex]._row*_col + Matrix._v[rightIndex]._col;
      if (addL < addR)
      {
        ret->_v.push_back(_v[leftIndex]);
        leftIndex++;
      }
      else if (addL > addR)
      {
        ret->_v.push_back(Matrix._v[rightIndex]);
        rightIndex++;
      }
      else
      {
        Trituple<T> t(_v[leftIndex]._row, _v[leftIndex]._col,
          _v[leftIndex]._value + Matrix._v[rightIndex]._value);
        ret->_v.push_back(t);
        leftIndex++;
        rightIndex++;
      }
    }
    while (leftIndex < _v.size())   //第二個已經無有效元素
    {
      ret->_v.push_back(_v[leftIndex]);
      leftIndex++;
    }
    while (rightIndex < _v.size())   //第一個已經無有效元素
    {
      ret->_v.push_back(Matrix._v[rightIndex]);
      rightIndex++;
    }
    return *ret;
  }      

測試結果如下：