Question

请问一下数据结构中对称矩阵的压缩存储的一 一对应关系怎么算的呀。

可以把过程写在纸上吗。浪费你时间了。

Answer 1

其实书本上说的已经够了，我就不再赘述了，下面说说不明白的地方吧！

书本上说了 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

Answer 2

先看上面一个：
下三角有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)，即行列互换，代入上式即可得