Question

数据结构特殊矩阵压缩存储问题

若将n阶上三角矩阵A按照列优先顺序存放在一维数组B[0，...，n(n+1)/2-1]中，第一个非零元素a(1,1)存于B[0]中，则应存放到B[k]中的非零元素a(i,j)(1<=i<=n，1<=j<=n)的下标i，j，k的对应关系是（k=j(j-1)/2+i-1）
设矩阵A是一个对称矩阵，为了节省存储空间，将其下三角部分按照行优先存放在一维数组B[0，...，n(n+1)/2-1]中，对于下三角部分中任意一元素ai,j(i>=j)，在一维数组B中的下标k的值是(i(i+1)/2+j)
第一题a(i,j)按照列优先，之前有j-1列，每列有j个元素，按照等比数列公式a(i,j)所在列之前有(1+j-1)*(j-1)/2个元素，然后再加上a(i,j)是本列的第i个元素，且数组B是从0开始存储，所以得到k=j(j-1)/2+i-1
但第二题按照此方法算出的是(1+i-1)*(i-1)/2+j-1即i*(i-1)/2+j-1与正确答案(i(i+1)/2+j)不符，为什么？谢谢~！

Answer 1

这个问题出在下标的问题上吧，第一个问题，明确说明第一个非零元素a(1,1)存于B[0]中，所以推导时没问题。

第二个问题并没有说第一个非零元素a(1,1)存于B[0]中，但大多教材推导是，是将第一个非零元素a(0，0)存于B[0]中，所以公式就不一样了，你的推导逻辑没问题。

追问

那请问下如何推导出第二题的答案呢？谢谢