式如图所示: 50800 a 8926 a a 30251 70613 an-10an-11an-12 n-1n-1 图5.1对称矩阵 在这个下三角矩阵中,第i行恰有i+1个元素, 元素总数为:(i+1)=n(n+1)/2 因此,我们可以按图中箭头所指的次序将这些 元素存放在一个向量sa[0.n(n+1)/2-1]中。为了便 于访问对称矩阵A中的元素,我们必须在ai和sa[k]
式如图所示： 1 5 1 3 7 a00 5 0 8 0 0 a10 a 11 1 8 9 2 6 a20 a21 a22 3 0 2 5 1 ……………….. 7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 …a n-1 n-1 图 5.1 对称矩阵 在这个下三角矩阵中，第i行恰有i+1个元素， 元素总数为：(i+1)=n(n+1)/2 因此，我们可以按图中箭头所指的次序将这些 元素存放在一个向量sa[0..n(n+1)/2-1]中。为了便 于访问对称矩阵A中的元素，我们必须在aij和sa[k]
之间找一个对应关系。 若三j,则a在下三角形中。a;;之前的i行 (从第0行到第i-1行)一共有1+2+.+i=i(i+1)/2个元 素,在第i行上,a1之前恰有个元素 (即a0,a1,a…,aij-1),因此有: k=i*(i+1)/2+j0≡k<n(n+1)/2 若<,则a1是在上三角矩阵中。因为a1=a1,所 以只要交换上述对应关系式中的和j即可得到 k=j*(j+1)/2+10≡k<n(n+1)/2 令I=max(i,j,J=min(i,j),则k和i,j的对 应关系可统一为: k=1*(I+1)/2+J0≡k<n(n+1)/2
之间找一个对应关系。 若i≧j，则ai j在下三角形中。 ai j之前的i行 （从第0行到第i-1行）一共有1+2+…+i=i(i+1)/2个元 素，在第i行上， ai j之前恰有j个元素 （即ai0,ai1,ai2,…,aij-1），因此有： k=i*(i+1)/2+j 0≦k<n(n+1)/2 若i<j，则aij是在上三角矩阵中。因为aij=aji，所 以只要交换上述对应关系式中的i和j即可得到： k=j*(j+1)/2+i 0≦ k<n(n+1)/2 令 I=max(i,j)， J=min(i,j)，则 k 和 i, j的对 应关系可统一为： k=I*(I+1)/2+J 0≦ k<n(n+1)/2
因此,a1的地址可用下列式计算: LoC(aij=LOC (sa[k1) =L0C(sa[0])+k*d=L0C(sa[0]+[*(工+1)/2+]*d 有了上述的下标交换关系,对于任意给定一组下 标(i,j),均可在sa[k]中找到矩阵元素aij,反之,对 所有的k=0,1,2,n(n-1)/2-1,都能确定sa[k]中的元 素在矩阵中的位置(i,j。由此,称sa[n(n+1)/2为阶 对称矩阵A的压缩存储,见下图: a00 a10 a1l a20 n-10 n-1n-1 k=- f25 m(m-)/21 例如、a21和a12均存储在sa[4]中,这是因为 k=I*(I+1)/2+J=2米(2+1)/2+1=4
因此，aij的地址可用下列式计算： LOC(aij)=LOC(sa[k]) =LOC(sa[0])+k*d=LOC(sa[0]+[I*(I+1)/2+J]*d 有了上述的下标交换关系，对于任意给定一组下 标(i，j)，均可在sa[k]中找到矩阵元素aij，反之，对 所有的k=0,1,2,…n(n-1)/2-1，都能确定sa[k]中的元 素在矩阵中的位置(i,j)。由此，称sa[n(n+1)/2]为阶 对称矩阵A的压缩存储，见下图： k= 0 1 2 3 n(n-)/2-1 例如、a21和a12均存储在 sa[4]中，这是因为 k=I*(I+1)/2+J=2*(2+1)/2+1=4 a00 a10 a11 a20 … … an-1 0 …… an-1,n-1
2、三角矩阵 以主对角线划分,三角矩阵有上三角和下三角两种 上三角矩阵如图所示,它的下三角(不包括主对角线) 中的元素均为常数。下三角矩阵正好相反,它的主对角 线上方均为常数,如图所示。在大多数情况下,三角矩 阵常数为零。 aooa01…aon-1 a00 c a a aT a CC…an-1n-1 an-10an-11…an-1n-1 (a)上三角矩阵(b)下三角矩阵 图5.2三角矩阵
2、三角矩阵 以主对角线划分，三角矩阵有上三角和下三角两种。 上三角矩阵如图所示，它的下三角（不包括主对角线） 中的元素均为常数。下三角矩阵正好相反，它的主对角 线上方均为常数，如图所示。在大多数情况下，三角矩 阵常数为零。 a00 a01 … a 0 n-1 a00 c … c c a11 … a 1 n-1 a10 a11 … c ………………….. …………….. c c … a n-1 n-1 an-1 0 an-1 1 … an-1 n-1 (a)上三角矩阵 (b)下三角矩阵 图5.2 三角矩阵
角矩阵中的重复元素c可共享一个存储空间, 其余的元素正好有n(n+1)/2个,因此,三角矩阵 可压缩存储到向量sa[0..n(n+1)/2]中,其中c存 放在向量的最后一个分量中, 上三角矩阵中,主对角线之上的第p行 (0≡p<n)恰有n-p个元素,按行优先顺序存放上 角矩阵中的元素a1时,a;之前的行一共有 (n-p)=i(2n-i+1)/2 个元素,在第i行上,a1前恰好有-i个元素: :计1,…a1因此,sa[k]和a1的对应关系 i(2n-i+1)/2+j-i当i≡j ke n(n+1)/2 当ij
三角矩阵中的重复元素c可共享一个存储空间， 其余的元素正好有n(n+1)/2个，因此，三角矩阵 可压缩存储到向量sa[0..n(n+1)/2]中，其中c存 放在向量的最后一个分量中， 上三角矩阵中，主对角线之上的第p行 (0≦p<n)恰有n-p个元素，按行优先顺序存放上 三角矩阵中的元素aij时，aij之前的i行一共有 (n-p)=i(2n-i+1)/2 个元素，在第i行上，aij前恰好有j-i个元素： aij,aij+1,…aij-1。因此，sa[k]和aij的对应关系 是： i(2n-i+1)/2+j-i 当i≦j n(n+1)/2 当i>j k=