|
特殊矩阵 所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵常见的有对称矩阵三角矩阵和对角矩阵等 ．对称矩阵（）对称矩阵 在一个n阶方阵A中若元素满足下述性质 aij=aji ≤ij≤n 则称A为对称矩阵 【例】下图便是一个阶对称矩阵 （）对称矩阵的压缩存储 对称矩阵中的元素关于主对角线对称故只要存储矩阵中上三角或下三角中的元素让每两个对称的元素共享一个存储空间这样能节约近一半的存储空间 ①按行优先顺序存储主对角线(包括对角线)以下的元素 即按aaa……anan…ann次序存放在一个向量sa[．．n(n+)／]中（下三角矩阵中元素总数为n(n+)／） 其中 sa[]= a sa[] = a …… sa[n(n+)／]= ann ②元素aij的存放位置 aij元素前有i行(从第行到第i行)一共有 ++…+i=i×(i+)／个元素 在第i行上aij之前恰有j个元素(即aiail…aij)因此有 sa[i×(i+)／+j]= aij ③aij和sa[k]之间的对应关系 若i≥jk=i×(i+)／+j ≤k<n(n+)／ 若i＜jk=j×(j+)／+i ≤k<n(n+)／ 令I=max(ij)J=min(ij)则k和ij的对应关系可统一为 k=i×(i+)／+j ≤k<n(n+)／ （）对称矩阵的地址计算公式 LOC(aij)=LOC(sa[k]) =LOC(sa[])+k×d=LOC(sa[])+[I×(I+)／+J]×d 通过下标变换公式能立即找到矩阵元素aij在其压缩存储表示sa中的对应位置k因此是随机存取结构 【例】a和a均存储在sa[]中这是因为 k=I×(I+)／+J=×(+)／+= 三角矩阵 （）三角矩阵的划分 以主对角线划分三角矩阵有上三角矩阵和下三角矩阵两种 ①上三角矩阵 如下图(a)所示它的下三角(不包括主角线)中的元素均为常数c ②下三角矩阵 与上三角矩阵相反它的主对角线上方均为常数c如下图(b)所示 注意 在多数情况下三角矩阵的常数c为零 （）三角矩阵的压缩存储 三角矩阵中的重复元素c可共享一个存储空间其余的元素正好有n×(n+)／个因此三角矩阵可压缩存储到向量sa[．．n(n+)／]中其中c存放在向量的最后一个分量中 ① 上三角矩阵中aij和sa[k]之间的对应关系 上三角矩阵中主对角线之上的第p行(≤p<n)恰有np个元素按行优先顺序存放上三角矩阵中的元素aij时 aij元素前有i行(从第行到第i行)一共有 (n)+(n)+(n)+…+(ni)=i×(ni+)／个元素 在第i行上aij之前恰有ji个元素(即aijaij+l…aij)因此有 sa[i×(ni+)／+ji]= aij 所以 ┌i×(ni+)／+ji 当i≤j k=│ └n×(n+)/ 当i＞j ②下三角矩阵中aij和sa[k]之间的对应关系 ┌i×(i+)／+j 当i≥j k=│ └n×(n+)/ 当i＜j 注意 三角矩阵的压缩存储结构是随机存取结构 ．对角矩阵 所有的非零元素集中在以主对角线为中心的带状区域中即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外其余元素皆为零的矩阵为对角矩阵 【例】下图给出了一个三对角矩阵 其中 非零元素仅出现在主对角上(aii≤i≤n)紧邻主对角线上面的那条对角线上(aii+ ≤i≤n)和紧邻主对角线下面的那条对角线上(a i+i≤i≤n)当|ij|>时元素aij= 由此可知一个k对角线矩阵(k为奇数)A是满足下述条件的矩阵 若|ij|>(k)／则元素aij= 对角矩阵可按行优先顺序或对角线的顺序将其压缩存储到一个向量中并且也能找到每个非零元素和向量下标的对应关系具体【参见练习】 |
