1.对称矩阵的压缩存储 (1)对称矩阵的定义: 若一个n阶方阵mm中的元素满足a1ai (0≤i,jn-1则称其为n阶对称矩阵 如矩阵 4=12 036 是个对称矩阵。 16
16 1. 对称矩阵的压缩存储 (1)对称矩阵的定义： 若一个n阶方阵A[n][n]中的元素满足ai,j=aj,j (0≤i, j≤n-1),则称其为n阶对称矩阵。 如矩阵 A= 1 1 0 1 2 3 0 3 6 是个对称矩阵
1.对称矩阵的压缩存储 (2)对称矩阵元素分布的规律: 2元素关于主对角元素对称A 0 2…3 即上三角元素a与下三角元素036 相等。 (3)对称矩阵的压缩存储思路: 仅存储上三角元素a;ij) 或 仅存储下三角元素a1;ij) (4)对称矩4|mn下(或上)三角元素个数为 1+2+3+,,+n=n(n+1)2 17
17 (2)对称矩阵元素分布的规律： 元素关于主对角元素对称。 即上三角元素ai,j与下三角元素aj,i 相等。 (3)对称矩阵的压缩存储思路： 仅存储上三角元素(ai,j i≤j) 或 仅存储下三角元素(ai,j i≥j) (4) 对称矩A[n][n]下(或上)三角元素个数为 1+2+3+,…,+n=n(n+1)/2 1. 对称矩阵的压缩存储 A= 1 1 0 1 2 3 0 3 6
1.对称矩阵的压缩存储 (5对称矩阵A压缩为一维数组B的算法 0. 040.1 0,n-1 1.0a1 1,n-1 1,0an-1,1 a n-Nn-1 仅存储下三角元素(a1;j B=be 0501,9Um(m+1)/2 18
18 (5)对称矩阵A压缩为一维数组B的算法 1. 对称矩阵的压缩存储 A= a0,0 a0,1 … a0,n-1 a1,0 a1,1 … a1,n-1 … … … … an-1,0 an-1,1 … an-1,n-1 B=[b0 ,b1 ,…,bn(n+1)/2-1 ] 仅存储下三角元素(ai,j i≥j)
压缩算法(供参考) void Compa(int bl, int*a, int n) int i,i,k0; for(i=0;i<=n-1;i++) for(j=0; j<=i;j++) bkg=(a+n+(a+n+相当于aijl k++ 00、a0,1 0,n-1 1.0a11 I,n-1 A ●●● B=be 0901Um(m+1)2 19 n-1,0an-1,1an-1,m1
19 压缩算法(供参考) void CompA(int b[], int *a , int n) { int i, j, k=0; for(i=0;i<=n-1;i++) for(j=0;j<=i;j++) { b[k]=*(a+i*n+j); k++; } } A= a0,0 a0,1 … a0,n-1 a1,0 a1,1 … a1,n-1 … … … … an-1,0 an-1,1 … an-1,n-1 B=[b0 ,b1 ,…,bn(n+1)/2-1 ] //*(a+i*n+j)相当于 a[i,j]
(6)将压缩后的一维数组B解压为对称矩阵A B=lbo,b 05U19um(m+1)/2-1 bk a0,0a0,1… a 0,n-1 a a11 1,0a1 A n-10an-1.1…an-1,n-1 20
20 A= a0,0 a0,1 … a0,n-1 a1,0 a1,1 … a1,n-1 … … … … an-1,0 an-1,1 … an-1,n-1 (6)将压缩后的一维数组B解压为对称矩阵A B=[b0 ,b1 ,…,bn(n+1)/2-1 ] bk ? ai,j