对称矩阵
东营区网站制作公司哪家好，找创新互联！从网页设计、网站建设、微信开发、APP开发、自适应网站建设等网站项目制作，到程序开发，运营维护。创新互联2013年开创至今到现在10年的时间，我们拥有了丰富的建站经验和运维经验，来保证我们的工作的顺利进行。专注于网站建设就选创新互联。
设一个N*N的方阵A，A中的任意元素A[i][j]，当且仅当A[i][j]=A[j][i],则矩阵A是对称矩阵，以对角线分隔，分为上三角和下三角
压缩矩阵存储对称矩阵时只需要存储其上三角或者下三角的数据，即最多存储n(n+1)/2个数据,对应关于为：i>j,symmetricMatrix[i][j]=A[i*(i+1)/2+j]
代码实现：
template
class SymmetricMatrix
{
public:
SymmetricMatrix(T*a,size_t num)
:_a(new T[num*(num+1)/2])//开辟一块压缩矩阵的空间，n*（n+1）/2
,_size(num*(num+1)/2)
,_n(num)
{
for (size_t i = 0; i < _n; i++)
{
for (size_t j = 0; j <= i; j++)
{
_a[i*(i+1)/2+j] = a[i*num + j];//把矩阵中的元素存入压缩矩阵中
}
}
}
~SymmetricMatrix()
{
if (_a)
{
delete[]_a;
/*
_a=NULL;
_size=0;
_n=0;
*/
}
}
void Display()
{
for (size_t i = 0; i < _n; i++)
{
for (size_t j = 0; j < _n; j++)
{
/*
当i>=j打印下矩阵，当i=j)
cout<<_a[i*(i + 1) / 2 + j] << " ";
else
cout<<_a[j*(j + 1) / 2 + i] << " ";
*/
}
cout << endl;
}
cout << endl;
}
protected:
void Access(size_t i, size_t j)
{
if (i < j)
{
swap(i, j);
}
}
private:
T* _a;//数组
size_t _size;//压缩矩阵大小
size_t _n;//矩阵为N*N
};
void test()
{
int a[][4] =
{
0, 1, 2, 3,
1, 0, 5, 6,
2, 5, 0, 8,
3, 6, 8, 0
};
size_t lenth = sizeof(a)/sizeof(a[0]);
SymmetricMatrix Array((int*)a,lenth);
Array.Display();
}
int main()
{
test();
}
稀疏矩阵
M*N的矩阵，矩阵中有效值的个数远远小于无效值的个数，这些数据的分布，没有规律
压缩存储只需要存储极少的有效数据，用三元组{row，col，value}存储，三元组按原矩阵中的位置，以行优先级先后顺序依次存放。
#include
#include
using namespace std;
template
struct Triple//三元组
{
T _value;//值
size_t _row;//行
size_t _col;//列
Triple(const T&value = T(), size_t row = 0, size_t col = 0)
:_value(value)
, _row(row)
, _col(col)
{}
};
template
class SparseMatrix
{
public:
SparseMatrix(T *a,size_t m,size_t n,const T&invalid)//构造
:_rowSize(m)
, _colSize(n)
, _invalid(invalid)
{
for (size_t i = 0; i < _rowSize; i++)
{
for (size_t j = 0; j < _colSize; j++)
{
if (a[i*_colSize + j] != _invalid)
{
_a.push_back(Triple(a[i*_colSize + j],i,j));
/*
压缩矩阵，循环找到矩阵中不为_invalid的元素，存储到顺序表中
*/
}
}
}
}
void Display()
{
size_t index = 0;//顺序表中元素序号
for (size_t i = 0; i <_rowSize; i++)
{
for (size_t j = 0; j < _colSize; j++)
{
/*
循环寻找与顺序表中行号、列号相同的元素
*/
if (index<_a.size()&&_a[index]._row == i&&_a[index]._col == j)
{
cout << _a[index]._value << " ";
++index;
}
else
cout << _invalid << " ";
}
cout << endl;
}
cout << endl;
}
private:
vector> _a;
size_t _rowSize;
size_t _colSize;
T _invalid;
};
void test()
{
int a[][5] =
{
1, 0, 3, 0, 5,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0,
2, 0, 4, 0, 6,
0, 0, 0, 0, 0,
0, 0, 0, 0, 0
};
SparseMatrix Array((int*)a,6,5,0);
Array.Display();
}
int main()
{
test();
}
当前题目：对称矩阵及稀疏矩阵的压缩
浏览地址：
http://bjjierui.cn/article/ihpgjp.html
