對稱矩陣 壓縮存儲

對稱矩陣及對稱矩陣的壓縮存儲

設一個N*N的方陣A，A中任意元素Aij，當且僅當Aij == Aji(0 <= i <= N-1 && 0 <= j <= N-1)，則矩陣A是對稱矩陣。以矩陣的對角線為分隔，分為上三角和下三角。

壓縮存儲稱矩陣存儲時只需要存儲上三角/下三角的數據，所以最多存儲n(n+1)/2個數據。

對稱矩陣和壓縮存儲的對應關系：下三角存儲i>=j,  SymmetricMatrix[i][j] == Array[i*(i+1)/2+j]

#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>

using namespace std;

/**************

 *對稱矩陣

 *壓縮存儲：把下三角矩陣存儲在一維數組中

 *（二維對稱矩陣 下三角陣 在一維數組中 坐標為 i * (i + 1) / 2 + j）

 *

 ****/

template<class T>

class SymmetricMatrix

{

public:

SymmetricMatrix(T* a, size_t n);

~SymmetricMatrix();

T& Access(size_t i, size_t j);

void Display() const;

protected:

size_t _size;

T* _a;

size_t _n;//維數

};

template<class T>

SymmetricMatrix<T>::SymmetricMatrix(T* a, size_t n)

:_size((n * (n + 1))/2)// 注意數據定義順序

,_a(new T[_size])

,_n(n)

{

size_t index = 0;

for (size_t i = 0; i < n; i++)

{

for (size_t j = 0; j < n; j++)

{

if (j <= i)

{

_a[index++] = a[i * n + j];

}

else

{

break;//存下三角

}

}

}

}

template<class T>

void SymmetricMatrix<T>::Display() const

{

for (size_t i = 0; i < _n; ++i)

{

for (size_t j = 0; j < _n; j++)

{

if (j <= i)

{

cout<<_a[i * (i + 1) / 2 + j]<<" ";

}

else

{

cout<<_a[j * (j + 1) / 2 + i]<<" "; // 巧妙

}

}

cout<<endl;

}

}

template<class T>

SymmetricMatrix<T>::~SymmetricMatrix()

{

if (_a)

{

delete[] _a;

_n = 0;

_size = 0;

}

}

template<class T>

T& Access(size_t i, size_t j)

{

if (j > i)

{

swap(i, j);

}

return _a[i * (i + 1) / 2 + j];

}

void test_Sym()

{

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((int*)a,5);

s.Display();

}

int main()

{

test_Sym();

return 0;

}