5.3矩阵的压缩存储 在科学与工程计算问题中，矩阵是一种常用的 数学对象，在高级语言编制程序时，简单而又自 然的方法，就是将一个矩阵描述为一个二维数组。 矩阵在这种存储表示之下，可以对其元素进行随 机存取，各种矩阵运算也非常简单，并且存储的 密度为1。但是在矩阵中非零元素呈某种规律分 布或者矩阵中出现大量的零元素的情况下，看起 来存储密度仍为1，但实际上占用了许多单元去 存储重复的非零元素或零元素，这对高阶矩阵会 造成极大的浪费，为了节省存储空间，我们可 以对这类矩阵进行压缩存储：即为多个相同的非 零元素只分配一个存储空间；对零元素不分配空 间
5.3 矩阵的压缩存储 在科学与工程计算问题中，矩阵是一种常用的 数学对象，在高级语言编制程序时，简单而又自 然的方法，就是将一个矩阵描述为一个二维数组。 矩阵在这种存储表示之下，可以对其元素进行随 机存取，各种矩阵运算也非常简单，并且存储的 密度为1。但是在矩阵中非零元素呈某种规律分 布或者矩阵中出现大量的零元素的情况下，看起 来存储密度仍为1，但实际上占用了许多单元去 存储重复的非零元素或零元素，这对高阶矩阵会 造成极大的浪费，为了节省存储空间， 我们可 以对这类矩阵进行压缩存储：即为多个相同的非 零元素只分配一个存储空间；对零元素不分配空 间
5.3.1特殊矩阵 所谓特殊矩阵是指非零元素或零元素的分布有 定规律的矩阵，下面我们讨论几种特殊矩阵的压 缩存储。 1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aj=aji 1si,jsn 则称A为对称矩阵。 对称矩阵中的元素关于主对角线对称，故只要存 储矩阵中上三角或下三角中的元素，让每两个对 称的元素共享一个存储空间，这样，能节约近一 半的存储空间。不失一般性，我们按"行优先
5.3.1特殊矩阵 所谓特殊矩阵是指非零元素或零元素的分布有一 定规律的矩阵，下面我们讨论几种特殊矩阵的压 缩存储。 1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij=aji 1≦i,j≦n 则称A为对称矩阵。 对称矩阵中的元素关于主对角线对称，故只要存 储矩阵中上三角或下三角中的元素，让每两个对 称的元素共享一个存储空间，这样，能节约近一 半的存储空间。不失一般性，我们按“行优先
顺序”存储主对角线（包括对角线）以下的元素，其 存储形式如图所示 13 5 080 a21 a22 1 8 92 6 a31 a32 a33 3 0 25 1 。”。”。”。0 0 6 13 an1an2an3.ann 图5.1对称矩阵 在这个下三角矩阵中，第行恰有个元素，元素总 数为： 1+2+.+n=n(n+1)/2 因此，我们可以按图中箭头所指的次序将这些元素 存放在一个向量sa[0.n(n+1)/2-1]中。为了便于访 问对称矩阵A中的元素，我们必须在a和sa[k]
顺序”存储主对角线（包括对角线）以下的元素，其 存储形式如图所示： 1 5 1 3 7 a11 5 0 8 0 0 a21 a 22 1 8 9 2 6 a31 a32 a33 3 0 2 5 1 . 7 0 6 1 3 an 1 a n 2 a n 3 .a n n 图 5.1 对称矩阵 在这个下三角矩阵中，第i行恰有i个元素，元素总 数为： 1+2+.+n=n(n+1)/2 因此，我们可以按图中箭头所指的次序将这些元素 存放在一个向量sa[0.n(n+1)/2-1]中。为了便于访 问对称矩阵A中的元素，我们必须在aij和sa[k]
之间找一个对应关系。 若i≥j,则a在下三角形中。a之前的-1行（从第1 行到第-1行)一共有1+2+.+i-1=ii-1)/2个元素，在第1 行上，a之前恰有j-1个元素（即a,a2,aj-1),因此 有： k=i*(i-1)/2+j-1 0sk<n(n+1)/2 若ij,则a;是在上三角矩阵中。因为a,a,所以只要 交换上述对应关系式中的和即可得到： k=j*(0-1)/2+i-1 0≤k≤n(n+1)/2 令=max(,j),J=min(,),则k和i,j油的对应关系可统 一为： k=I*I-1)/2+J-1 0≤k<nn+1)/2
之间找一个对应关系。 若i≧j，则ai j在下三角形中。 ai j之前的i-1行（从第1 行到第i-1行）一共有1+2+.+i-1=i(i-1)/2个元素，在第i 行上， ai j之前恰有j-1个元素（即ai1,ai2,.,ai j-1），因此 有： k=i*(i-1)/2+j-1 0≦k<n(n+1)/2 若i<j，则aij是在上三角矩阵中。因为aij=aji，所以只要 交换上述对应关系式中的i和j即可得到： k=j*(j-1)/2+i-1 0≦ k<n(n+1)/2 令 I=max(i,j)， J=min(i,j)，则k和 i, j的对应关系可统 一为： k=I*(I-1)/2+J-1 0≦ k<n(n+1)/2
因此，a的地址可用下列式计算： LOC(aij)=LOC(sa[k]) =LOC(sa[0])+k*L=LOC(sa[0])+[I*(L-1)/2+J-1]*L 有了上述的下标交换关系，对于任意给定一组下标 (,j),均可在sa[k]中找到矩阵元素a,反之，对所有 的k=0,1,2,.n(n-1)/2-1,都能确定sa[k]中的元素在矩阵 中的位置ij)。由此，称sa[n(n+1)/2]为阶对称矩阵A的 压缩存储，见下图： a11 a21 a22 a31 ”。 An1 Ann k=0 < 3 n(n-1)/2 n(n+1)/2
因此，aij的地址可用下列式计算： LOC(aij)=LOC(sa[k]) =LOC(sa[0])+k*L=LOC(sa[0])+[I*(I-1)/2+J-1]*L 有了上述的下标交换关系，对于任意给定一组下标 (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-1)/2 n(n+1)/2-1 a11 a21 a22 a31 . an 1 . . an,n