java数据结构至对称矩阵压缩存储

时间:2023-09-24 15:53:44

刚刚刷java选择题,遇到的对称矩阵压缩存储问题,我们知道对称矩阵是aij=aji的矩阵,压缩存储可以采用一维数组和二维数组存储。

此处只讨论一维数组存储的形式,设数组下标从0开始,对称矩阵为n维矩阵。

此矩阵有n*n个元素,主对角线上有n个,因为aij=aji,所以只需要存储上三角或者下三角的元素即可,所以数组的容量为(n*n-n)/2+n=n(n+1)/2

(注:-n是先去除主对角线上的元素)

n阶对称矩阵的压缩存储对应关系

  aij=aji   1<=i<=n,1<=j<=n

 元素个数m = n*(n+1)/2

打印对称矩阵第i行,第j列的元素,与一维数组的下标关系为:

i*(i-1)/2+j-1  当i>=j

k=

j*(j-1)/2+i-1  当i<j