压缩存储数据是一个比较高效、节省空间的方法，当我们存储的数据足够大时，我们要尽量避免数据的冗余重复，减少空间的浪费。对阵矩阵的压缩存储就是一个简单的实例。
算法分析与设计
如下图所示，我们要存储的是一个5×5的矩阵，方阵的特点是红色对称轴的对称位置的数据相同，比如(1,0)与(0,1)处的数据相同，(2,3)与(3,2)处的数据相同，即Aij==Aji(0 <= i <= N-1 && 0 <= j <= N-1)。因此，我们只需要存储红色三角形内的数据，即下三角区，当查找上三角区的数据时，我们通过一个坐标的转换来得到数据。
这样一来，原N×N的矩阵含有数据元素为N×N个，现在就转换成N×(N+1)/2个数据元素的存储，当N足够大时，节省的空间是非常可观的。
仔细观察列与行的关系可知：下三角区行大于等于列(i>=j)，上三角区行小于列(i
源代码及注释
#pragma once
#include
using namespace std;
template
class SymmetricMatrix
{
public:
SymmetricMatrix(int *a, size_t N) //构造函数
:_pData(new T[N*(N + 1) / 2])
,_N(N)
{
size_t idx = 0;
for (size_t i = 0; i < N; ++i)
{
for (size_t j = 0; j < N; ++j)
{
//存入下三角数据
if (i >= j)
{
_pData[idx] = a[i*N + j];
++idx;
}
else
break;
}
}
}
~SymmetricMatrix()//析构函数
{
delete[] _pData;
_pData = NULL;
_N = 0;
}
//重载输出运算符
template
friend ostream& operator<& s)
{
for (size_t i = 0; i < _N; ++i)
{
for (size_t j = 0; j < _N; ++j)
{
_cout << s.Access(i, j) << " ";
}
_cout << endl;
}
return _cout;
}
void Display()//打印矩阵
{
for (size_t i = 0; i < _N; ++i)
{
for (size_t j = 0; j < _N; ++j)
{
cout << Access(i, j) << " ";
}
cout << endl;
}
}
T& Access(size_t i, size_t j)
{
//上三角转为转下三角
if (i < j)
swap(i, j);
return _pData[i*(i + 1) / 2 + j];
}
const T& Access(size_t i, size_t j) const
{
//上三角元素转下三角
if (i < j)
swap(i, j);
return _pData[i*(i + 1) / 2 + j];
}
protected:
T* _pData;//压缩存储的一维数组
size_t _N;//N*N的矩阵
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#pragma once
#include
usingnamespacestd;
template
classSymmetricMatrix
{
public:
SymmetricMatrix(int*a,size_tN)//构造函数
:_pData(newT[N*(N+1)/2])
,_N(N)
{
size_tidx=0;
for(size_ti=0;i
{
for(size_tj=0;j
{
//存入下三角数据
if(i>=j)
{
_pData[idx]=a[i*N+j];
++idx;
}
else
break;
}
}
}
~SymmetricMatrix()//析构函数
{
delete[]_pData;
_pData=NULL;
_N=0;
}
//重载输出运算符
template
friendostream&operator<&s)
{
for(size_ti=0;i<_n>
{
for(size_tj=0;j<_n>
{
_cout<
}
_cout<
}
return_cout;
}
voidDisplay()//打印矩阵
{
for(size_ti=0;i<_n>
{
for(size_tj=0;j<_n>
{
cout<
}
cout<
}
}
T&Access(size_ti,size_tj)
{
//上三角转为转下三角
if(i
swap(i,j);
return_pData[i*(i+1)/2+j];
}
constT&Access(size_ti,size_tj)const
{
//上三角元素转下三角
if(i
swap(i,j);
return_pData[i*(i+1)/2+j];
}
protected:
T*_pData;//压缩存储的一维数组
size_t_N;//N*N的矩阵
};
//test.c
#include "SymmetricMatrix.h"
void Func()
{
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((int*)a, 5);
s.Display();
cout << s.Access(0,1) << endl;
cout << s.Access(1,0) << endl;
}
int main()
{
Func();
system("pause");
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//test.c
#include "SymmetricMatrix.h"
voidFunc()
{
inta[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};
SymmetricMatrixs((int*)a,5);
s.Display();
cout<
cout<
}
intmain()
{
Func();
system("pause");
return0;
}
