資料結構_對稱矩陣

對稱矩陣是資料結構中矩陣的一種，設A為N*N方陣，當Aij=Aji時，稱為對稱矩陣。

矩陣又可分為上三角矩陣和下三角矩陣，（常用下三角矩陣，行優先順序周遊較為友善）

當壓縮存儲對稱矩陣時，隻需存儲n*(n+1)/2個資料

SymmertricMatrix[i][j]==Array[i*(i+1)/2+j]

#pragma once

//對稱矩陣
//對稱矩陣的特征是以主對角線為對稱軸，對應相等。
//對稱矩陣和壓縮存儲對應的關系：下三角存儲i>=j, SymmetricMatrix[i][j] ==
//Array[i*(i + 1) / 2 + j]
template<class T>
class SymmetricMatrix
{
public:
  SymmetricMatrix(T* a, size_t size)//對稱矩陣隻需存儲上三角或下三角矩陣
    :_a(new T[size*(size + 1) / 2])//是以隻需存儲n(n+1)/2
    , _size(size*(size + 1) / 2)//
    , _n(size) //友善以後用作出書列印
  {
    size_t index = 0;
    for (size_t i = 0; i < size; i++)
    {
      for (size_t j = 0; j < size; j++)
      {
        if (i >= j)//下三角對稱矩陣存儲
        {
          _a[index++] = a[i*size + j];//_a是一個一維數組，存儲有效數
          //二維數組下标轉換為一維數組下标
        }
        else
        {
          break;//直接跳出内層循環。
        }
      }
    }
  }
  ~SymmetricMatrix()
  {
    if (_a)
    {
      delete[]_a;
      _a = NULL;
      _size = 0;
    }
  }

public:
  void Display()//列印函數
  {
    for (size_t i = 0; i < _n; i++)
    {
      for (size_t j = 0; j < _n; j++)
      {
        if (i >= j)//下三角矩陣
        {
          cout << _a[i*(i + 1) / 2 + j] << " ";
        }
        else//上三角情況，[i,j]和[j,i]對稱相等，是以是這種寫法
        {
          cout << _a[j*(j + 1) / 2 + i] << " ";
        }
      }
      cout << endl;
    }
    cout << endl;


  }

protected:
  T* _a;
  size_t _size;
  size_t _n;
};

void Test()
{
  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 },
  };
  //若以對稱矩陣存儲，則以一維數組存儲為0 1 0 2 1 0 3 2 1 0 4 3 2 1 0
  SymmetricMatrix<int> sm((int*)a, 5);//二維數組強制轉換為一維數組
  sm.Display();
}