对称矩阵及对称矩阵的压缩存储
创新互联公司是一家专业从事做网站、网站制作、网页设计的品牌网络公司。如今是成都地区具影响力的网站设计公司,作为专业的成都网站建设公司,创新互联公司依托强大的技术实力、以及多年的网站运营经验,为您提供专业的成都网站建设、营销型网站建设及网站设计开发服务!
设一个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
using namespace std;
/**************
*对称矩阵
*压缩存储:把下三角矩阵存储在一维数组中
*(二维对称矩阵 下三角阵 在一维数组中 坐标为 i * (i + 1) / 2 + j)
*
****/
template
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
SymmetricMatrix
:_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
void SymmetricMatrix
{
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< } } template SymmetricMatrix { if (_a) { delete[] _a; _n = 0; _size = 0; } } template 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 s.Display(); } int main() { test_Sym(); return 0; }
本文题目:对称矩阵压缩存储
标题来源:http://cdkjz.cn/article/jpisgd.html