|
特殊矩阵 所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵常见的有对称矩阵三角矩阵和对角矩阵等 对称矩阵 ()对称矩阵 在一个n阶方阵A中若元素满足下述性质 a ij =a ji ≤ij≤n 则称A为对称矩阵 【例】下图便是一个阶对称矩阵 ()对称矩阵的压缩存储 对称矩阵中的元素关于主对角线对称故只要存储矩阵中上三角或下三角中的元素让每两个对称的元素共享一个存储空间这样 能节约近一半的存储空间 ①按行优先顺序存储主对角线(包括对角线)以下的元素 即按a a a ……a n a n …a nn 次序存放在一个向量sa[n(n+)/]中(下三角矩阵 中元素总数为n(n+)/) 其中 sa[]= a sa[] = a …… sa[n(n+)/]= a nn ②元素a ij 的存放位置 a ij 元素前有i行(从第行到第i行)一共有 ++…+i=i×(i+)/个元素; 在第i行上aij之前恰有j个元素(即a i a il …a ij )因此有 sa[i×(i+)/+j]= a ij ③a ij 和sa[k]之间的对应关系 若i≥jk=i×(i+)/+j ≤k 若i 令I=max(i，j)，J=min(i，j)，则k和i，j的对应关系可统一为： k=i×(i+1)/2+j 0≤k (3)对称矩阵的地址计算公式 LOC(a ij )=LOC(sa[k]) =LOC(sa[0])+k×d=LOC(sa[0])+[I×(I+1)/2+J]×d 通过下标变换公式，能立即找到矩阵元素a ij 在其压缩存储表示sa中的对应位置k。TW.WInGWIT.cOm因此是随机存取结构。 【例】a 21 和a 12 均存储在sa[4]中，这是因为 k=I×(I+1)/2+J=2×(2+1)/2+1=4 |
