C++实现对称矩阵的压缩存储

2017-04-21 21:23 阅读 843 次 评论 0 条

压缩存储数据是一个比较高效、节省空间的方法,当我们存储的数据足够大时,我们要尽量避免数据的冗余重复,减少空间的浪费。对阵矩阵的压缩存储就是一个简单的实例。

算法分析与设计

如下图所示,我们要存储的是一个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<j)。因此当i<j时,交换行列的位置存储于下三角区对称的位置即可。

源代码及注释

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:C++实现对称矩阵的压缩存储 | 术与道的分享
分类:编程素养 标签:,
1024do.com导航_术与道导航平台

发表评论


表情