【数据结构】特殊矩阵的压缩存储（对称矩阵，三角矩阵和三对角矩阵）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构】特殊矩阵的压缩存储（对称矩阵，三角矩阵和三对角矩阵）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.对阵矩阵

2.三角矩阵

3.三对角矩阵（带状矩阵）

均假设数组的下标从0开始

1.对阵矩阵

定义：若对一个n阶矩阵A中的任意一个元素 aᵢ,ⱼ 都有aᵢ,ⱼ=aⱼ,ᵢ （1≤i,j≤n），则称其为对称矩阵。

三对角矩阵行优先存储,数据结构,矩阵,数据结构,数组

存储策略：只存储主对角线＋下三角区（或主对角线+上三角区），以主对角线+下三角区为例，按照行优先把这些元素放入到一维数组中，就得到了下面的样子的一维数组：

a₁₁

a₂₁

a₂₂

a₃₁

...

aₙ,ₙ₋₂

aₙ,ₙ₋₁

aₙ,ₙ

一维数组的大小应该定义为 (1+n)*n/2, 此公式通过求和公式，将每行元素相加即可得到。

根据性质aᵢ,ⱼ=aⱼ,ᵢ可以得到矩阵所有元素与一维数组下标k的对应关系如下：

三对角矩阵行优先存储,数据结构,矩阵,数据结构,数组

按照行优先存储原则，aᵢ,ⱼ是第几个元素？

答：因为是行优先，所以 aᵢ,ⱼ是第 1+2+...+i-1+j 个元素，即第 i*(i-1)/2+j-1个元素。

按照列优先存储原则，aᵢ,ⱼ是第几个元素？

答：因为是列优先，所以先算出前 j-1 行有多少个元素，由每列元素个数与列数 j 有关，可知每列的元素个数为 n-(j-1) 个，前 j-1 行即 n-(1-1) + n-(2-1) + n-(3-1) + ··· + n-(j-1-1)个元素，化简得前 j-1行有 n+(n-1)+...+(n-j+2) 个元素。接下来再加上第 j 行的元素，也就是 aᵢ,ⱼ 所处的那一行中，前面的元素个数，个数为 i - j 个，综上 aᵢ,ⱼ 是第 n+(n-1)+...+(n-j+2)+(i-j)+1 个元素。