请问一下数据结构中对称矩阵的压缩存储的一 一对应关系怎么算的呀。
发布网友
发布时间：2022-05-01 20:14
共2个回答
热心网友
时间：2022-06-22 14:02
其实书本上说的已经够了，我就不再赘述了，下面说说不明白的地方吧！
书本上说了 1<=i,j<=n,所以矩阵下标ij是以1开始的，但书本上的k是从0开始的
则下三角区和主对角线下标ij和一维向量下标k的关系式为i(i-1)/2+j -1 ，如果k从1开始，则关系式为i(i-1)/2+j。
好，进入正题思路：
第1行一个，第2行两个，。。。，第i-1行i-1个；第i行元素位置在第j，也就是说，第i行截止到它有j个。
所以要分开思考，1到i-1行的元素之和+本行截止到它的元素之和=它在一维数组的位置。
第i行前面i-1行的总和为i(i-1)/2,本行第i行截止到所求元素总数为j，所以加起来为i(i-1)/2+j。然后-1，代表k从0开始。
比如想取第3行第2列矩阵元素隐射到一维数组的位置
本行第3行之前2行的元素总数为3*2/2=3 对应 [i(i-1)/2]
然后j是在本行的位置是2 对应[+j]
总的等于5
这个第3行第2列的元素应该在一维数组的第五个位置，但是一维是从零开始的，所以5-1，得到对应一维数组的下标为4.
王道书上和楼上的答案都是正确的，只不过思路和我的有点不同，我的是处的位置，他们是要求元素之前位置，区别也就+-1
热心网友
时间：2022-06-22 14:03
下三角有i>=j
第1行一个，第2行两个，。。。，第i-1行i-1个（i, j下标都是从1开始的）
所以第i行前有1+2+...+(i-1)= i(i-1)/2个元素
再看本行，本元素前有j-1个元素
因为计算的是元素之间的位置差，因此就是i(i-1)/2+(j-1)了
下面一个上三角i<j：
对于对称矩阵有a(i,j)=a(j,i)，即行列互换，代入上式即可得
