对称矩阵的压缩算法

矩阵是很多科学与工程计算问题中研究的数学对象，在实际应用中，经常出现一些阶数很高的矩阵，同时在矩阵中有很多值相同的元素并且它们的分布有一定的规律——称为特殊矩阵（special matrix），对称矩阵就是其中一种。对称矩阵的特点是：在一个n阶方阵中，有aij=aji(1≤i，j≤n)。可以对这类矩阵进行压缩存储，从而节省存储空间，并使矩阵的各种运算能有效进行。

基本信息

中文名
对称矩阵的压缩算法

分析过程

对称矩阵关于主对角线对称，因此只需存储下三角部分（包括主对角线）即可。这样，原来需要存储n×n个存储单元，现只需要n×(n+1)/2个存储单元，节约了大约一半的存储单元。当n较大时，这是比较可观的一部分存储单元。

如何只存储下三角部分的元素呢？由于下三角中共有n×(n+1)/2个元素，可将这些元素按行存储到一个数组SA[n(n+1)/2]中。这样，下三角中的元素aij(i≥j)存储到SA[k]中，在数组SA中的下标k和i、j的关系为：k=i×(i-1)/2+j-1，寻址的计算方法如图所示。1

1/2

算法实现

#include <iostream>

using namespace std;const int N = 5;1

int main( )

{

int a[N][N], SA[N * (N + 1) / 2] = {0};int i, j;cin>>i;

for (j = 0; j < N; j++)

for (i = 0; i < N; i++)

for (j = 0; j <= i; j++)

a[i][j] = a[j][i] = i + j;

for (i = 0; i < N; i++)

{

cout<<a[i][j]<<" ";

cout<<endl;

}