对称矩阵的压缩存储-数组下标计算-Toy模板网

这篇具有很好参考价值的文章主要介绍了对称矩阵的压缩存储-数组下标计算。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1、对称矩阵的压缩存储

设矩阵的阶数为n，由于n阶对称矩阵中的数据元素基于其主对角线或副对角线对称，故而在存储时可将对称的两个相同数值的矩阵数据元素存储在同一个存储单元中。这样可以将个元素压缩在 $对称矩阵在一维数组中的表示,矩阵,算法,数据结构$ 即 $对称矩阵在一维数组中的表示,矩阵,算法,数据结构$ 个存储单元中。其元素下标与元素以及隐含元素在一维数组中的对应关系如下：

对称矩阵在一维数组中的表示,矩阵,算法,数据结构

2、下标计算

假设以一维数组存储压缩后的矩阵，则要求一维数组有 $对称矩阵在一维数组中的表示,矩阵,算法,数据结构$ 个存储单元。有如下图堆成矩阵v，设为对称矩阵中的第i行第j列元素，k为一维数组中元素索引下标，此处以行序为主序存储下三角矩阵元素为例进行分析，何为行序大家可自行查询，此处不做分析，观察下列矩阵，在一维数组中的下标应当为0，下标为1，下标为3，以此类推，假设要求元素下标，其下标即为一维数组中在它前面的元素个数。

对称矩阵在一维数组中的表示,矩阵,算法,数据结构

仔细观察该矩阵可发现该矩阵的下三角可发现，每一行元素个数都是有规律的递增，且增量为1，这与等差数列的性质不谋而合，假设现要求的下标，无论在它所在行的什么位置，除去它之后它所在行都不是完整的行，因而计算其下标时应当使用等差数列前n项和公式计算它所在行的前面所有行元素个数之和再加上它所在行在它前面的元素个数之和，即为的下标，由此可总结出如下规律：

$对称矩阵在一维数组中的表示,矩阵,算法,数据结构$