南开大学 数据结构Week8 的矩阵与列表.pdf

矩阵的压缩存储 在科学与工程计算问题中，矩阵是一种常用的数学 对象，在高级语言编程时，通常将一个矩阵描述为一个 二维数组。这样，可以对其元素进行随机存取，各种矩 阵运算也非常简单。 对于高阶矩阵，若其中非零元素呈某种规律分布或 者矩阵中有大量的零元素，若仍然用常规方法存储，可 能存储重复的非零元素或零元素，将造成存储空间的大 量浪费。对这类矩阵进行压缩存储： ◆ 多个相同的非零元素只分配一个存储空间； ◆ 零元素不分配空间。 特殊矩阵 特殊矩阵：是指非零元素或零元素的分布有一定规律 的矩阵。 1 对称矩阵 若一个n阶方阵A=(a ) 中的元素满足性质： ij nn aij=aji 1≦i,j≦n且i≠j 则称A为对称矩阵，如图5-3所示。 1 5 1 3 7 a11 5 0 8 0 0 a21 a22 A 1 8 9 2 6 A a31 a32 a33 … … … … 3 0 2 5 1 an1 an2 … ann 7 0 6 1 3 对称矩阵示例 对称矩阵中的元素关于主对角线对称，因此，让每一对对 2 称元素a 和a (i≠j)分配一个存储空间，则n 个元素压缩存储 ij ji 到n(n+1)/2个存储空间，能节约近一半的存储空间。 不失一般性，假设按“行优先顺序”存储下三角形(包括对角 线)中的元素。 设用一维数组(向量)sa[1…n(n+1)/2]存储n阶对称矩 阵，如图所示。为了便于访问，必须找出矩阵A中的元素的下标 值 （i,j ）和向量sa[k]的下标值k之间的对应关系。 k 1 2 3 4 … n(n-1)/2 … n(n+1)/2 sa a11 a21 a22 a31 a32 a33 … an1 an2 … ann 对称矩阵的压缩存储示例 若i ≧j ：ai j在下三角形中，直接保存在sa 中。ai j之前的i-1行 共有元素个数： 1+2+…+(i-1)=i(i-1)/2 而在第i行上，ai j之前恰有j-1个元素，因此，元素ai j保存在向量 sa中时的下标值k之间的对应关系是： k=i(i-1)/2+j-1 i ≧j 若ij ：则a 是在上三角矩阵中。因为a =a ，在向量sa 中保 ij ij ji 存的是aji 。依上述分析可得： k=j(j-1)/2+i-1 ij 对称矩阵元素ai j保存在向量sa 中时的下标值k与（i,j ）之间 的对应关系是： i(i-1)/2+j-1 当i≧j 时 K