矩阵(稀疏矩阵)压缩存储(3种方式)

发布于:2021-11-30 17:04:10

数据结构中,提供针对某些特殊矩阵的压缩存储结构。
这里所说的特殊矩阵,主要分为以下两类:



含有大量相同数据元素的矩阵,比如对称矩阵;
含有大量 0 元素的矩阵,比如稀疏矩阵、上(下)三角矩阵;

针对以上两类矩阵,数据结构的压缩存储思想是:矩阵中的相同数据元素(包括元素 0)只存储一个。


对称矩阵


? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ?图?1 对称矩阵示意图


图 1 的矩阵中,数据元素沿主对角线对应相等,这类矩阵称为对称矩阵。



矩阵中有两条对角线,其中图 1 中的对角线称为主对角线,另一条从左下角到右上角的对角线为副对角线。对称矩阵指的是各数据元素沿主对角线对称的矩阵。



结合数据结构压缩存储的思想,我们可以使用一维数组存储对称矩阵。由于矩阵中沿对角线两侧的数据相等,因此数组中只需存储对角线一侧(包含对角线)的数据即可。
对称矩阵的实现过程是,若存储下三角中的元素,只需将各元素

相关推荐

最新更新

猜你喜欢