矩阵的压缩存储.doc

5.3.矩阵的压缩存储
特殊矩阵是指在矩阵中有许多值相同的元素，或零元素，或非0元素、0元素的分布有一定的规律的矩阵。为了节约存储空间，对他们进行压缩。
（1）对称矩阵：
若n阶矩阵A中的元素满足

注意：这里规定矩阵的下标范围[1..n]行[1..n]列。
压缩策略：只存储上三角或下三角的元素。所需空间n(n+1)/2.。

方法一：
用一维数组sa[0..n(n+1)/2] 存储以行序为主序的下三角（包括对角线），其中sa[0]不存放矩阵元素，其地址的运算，即aij和sa[k] 之间存在如下对应关系：

方法二：
用一维数组sa[0..n(n+1)/2-1] 存储以行序为主序的下三角（包括对角线），其地址的运算：
aij和sa[k] 之间存在如下对应关系：

a11 与sa[0] 对应，即LOC(a11)=0，aij （i≥j）的位置对应于a(i-1),1 的位置后移j-1 ，即LOC(aij)= LOC(a(i-1),1)+j-1= LOC(a11)+[(1+i-1)*(i-1) ]/2+j-1= [i*(i-1) ]/2+j-1
（2）三角矩阵：
上三角矩阵：上三角矩阵的下三角元素均为常数c，

压缩策略：只存储上三角的n(n+1)/2个不同元素和下三角的一个元素c。所需空间用一维数组sa[0..n(n+1)/2] 存储以行序为主序的下三角（包括对角线），其地址的运算：

a11 与sa[0] 对应，即LOC(a11)=0，aij （i≤j）的位置对应于aii 的位置后移j-i ，即LOC(aij)= LOC(aii) +j-i= LOC(a11)+[(n+n-i+1+1)*(i-1) ]/2+j-i= [(2n-i+2)*(i-1) ]/2+j-i
第1 行放n 个元素，
第2 行放n-1个元素，
第i-1 行放n-(i-1)+1个元素，n-i+2
所以aii之前存放了[(n+(n-i+2))*(i-1)] /2个元素。
验证一下：
LOC(a11) =[(2n-i+2)*(i-1) ]/2+j-i=[(2n-1+2)*(1-1) ]/2+1-1=0
LOC(ann) =[(2n-i+2)*(i-1) ]/2+j-i=[(2n-n+2)*(n-1) ]/2+n-n=[(n+2)*(n-1) ]/2=(n2+n-2)/2
=[n*(n+1)/2]-1
aij和sa[k] 之间存在如下对应关系：
k=
下三角矩阵则反之。
（3）对角矩阵

（4）稀疏矩阵
l 稀疏矩阵：零元素个数远远大于非零元素的个数。
l 稀疏因子：在m*n的矩阵中，t个元素不为0，，称δ为矩阵的稀疏因子。通常认为δ≤0.05时称为稀疏矩阵。
M矩阵：

M矩阵的压缩存储：
三元组表示：行、列、值
（(1,2,12),(1,3,9),(3,1,-1),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,5,-7)）
M矩阵的转置T：
M是m×n矩阵，T是M矩阵的转置，T是n×m矩阵，且T(i,j)=M(j,i),1≤i≤n,1≤j≤m.

（一）稀疏矩阵的三元组顺序表存储表示p98
#define MAXSIZE 12500//非零元素最大个数
typedef struct{
int i,j;//非零元素的行下标、列下标
elemtype e;
}Triple;
typedef struct{
Triple data[MAXSIZE+1];//data[0]未用
int mu,nu,tu;//行数、列数、非零元素个数
}TSMatrix;

(以上图形由文档“表5-1”生成)
（二）行逻辑链接的顺序表p100
typedef struct{
Triple data[MAXSIZE+1];// data[0]未用
int rpos[MAXCO+1]// 各行第一个非零元的位置表,rpos [0]未用,
int mu,nu,tu;//行数、列数、非零元素个数
}RLSMatrix;

（三）稀疏矩阵的十字链表存储表示
typedef struct OLNode{
int i,j;
Elemtype e;
struct OLNode *right,*down;
} OLNode, *OLink;
typedef struct {
OLink *rhead,*chead;
int mu,nu,tu;
} CrossList;

5