数据结构2-5.3--矩阵的压缩存储new

1、5.3 矩阵的压缩存储矩阵的压缩存储压缩存储的含义: 为多个相同的元只分配一个存储空间 对零元不分配空间对称矩阵对称矩阵nji,1 jiijaa假设以数组san(n+1)/2来存储A,则sak和矩阵元aij之间有N阶对称矩阵A10974986376524321+- ji -1 21)-j(jji 2) 1(当当ij-1iika11a21a22a31.an1. annk=012321)-n(n21)n(n+-1对称矩阵的存储格式对称矩阵的存储格式三角矩阵三角矩阵mnmmaaaaaa21222111000mnnnaaaaaa00022211211(+-j)(i ) 2) 1(j-1ii*LLoc(

2、aij)=Loc(a11)+ j)i (+- ) 2) 1(i-1jj*LLoc(aij)=Loc(a11)+下三角矩阵上三角矩阵对角矩阵对角矩阵00n行n列见教材！n非零元素较少，分布稀疏 假设 m 行 n 列的矩阵含 t 个非零元素n稀疏因子： = t/(m*n) = 0.05n通常认为通常认为 0.05 的矩阵为的矩阵为稀疏矩阵稀疏矩阵。n存贮结构n顺序存贮结构n链式存贮结构稀疏矩阵稀疏矩阵稀疏矩阵例例5.6 5.6 0 12 9 0 0 0 0 0 0 -3 0 0 15 0 12 9 0 0 0 0 0 0 -3 0 0 15 0 0 0 0 0 0 0 12 0 0 0 18 0

3、0 0 0 0 0 0 0 12 0 0 0 18 0M= -3 0 0 0 0 14 0 9 0 0 24 0 0M= -3 0 0 0 0 14 0 9 0 0 24 0 0 0 0 24 0 0 0 0 T= 0 0 0 0 0 -7 0 0 24 0 0 0 0 T= 0 0 0 0 0 -7 0 18 0 0 0 0 0 0 0 0 0 0 0 0 18 0 0 0 0 0 0 0 0 0 0 0 15 0 0 -7 0 0 0 0 0 14 0 0 0 15 0 0 -7 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0M: mu x nu (6

4、x7)M: mu x nu (6x7)T: nu x mu (7x6)T: nu x mu (7x6)M M是是T T的转置的转置 以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题问题:1) 零值元素占了很大空间零值元素占了很大空间;2) 计算中进行了很多和零值的运算，计算中进行了很多和零值的运算， 遇除法，还需判别除数是否为零遇除法，还需判别除数是否为零。1) 尽可能少存或不存零值元素；解决问题的原则解决问题的原则:2) 尽可能减少没有实际意义的运算；3) 操作方便。 即： 能尽可能快地找到与下标值(i，j)对应的元素，能尽可能快地找到同一行或同一列的非零值元。稀疏矩阵稀疏矩阵ADT

5、SpareMatrix数据对象：,a n;,1,2,jm;,1,2,|ij数分别为矩阵的行数和列和nmElemSetiaDij数据关系：1 , 11 |a,a11 ,1 |a,a,j1,iji,1ji,ji,njmiColnjmiRowColRowR-+ (1) CreateSMatrix (&M) /构造稀疏矩阵M (2) DestroySMatrix (&M) / 销毁稀疏矩阵M (3) PrintSMatrix(M) /输出稀疏矩阵M (4) CopySMatrix(M,&T) /复制 (5) AddSMatrix(M,N,&Q) /Q=M+N (6) SubSMatrix(M,N,&Q

6、) /Q=M-N (7) MulSMatrix(M,N,&Q) /Q=MN (8) TransposeSMatrix(M,&T) /T=M ADT SparseMatrix基本操作：稀疏矩阵的存储结构稀疏矩阵的存储结构一一. . 三元组顺序表三元组顺序表n例例5.6 n 0 12 9 0 0 0 0 0 0 -3 0 0 15n 0 0 0 0 0 0 0 12 0 0 0 18 0M= -3 0 0 0 0 14 0 9 0 0 24 0 0n 0 0 24 0 0 0 0 T= 0 0 0 0 0 -7n 0 18 0 0 0 0 0 0 0 0 0 0 0n 15 0 0 -7 0 0

7、0 0 0 14 0 0 0n 0 0 0 0 0 0nM: mu x nu (6x7)nT: nu x mu (7x6)nM是是T的转置的转置稀 疏 矩 阵 的 存 储 结 构稀 疏 矩 阵 的 存 储 结 构一一. . 三元组顺序表三元组顺序表 M: i j e T: i j e M: i j e T: i j e 1 2 12 1 3 -3 1 2 12 1 3 -3 1 3 9 1 6 15 1 3 9 1 6 15 3 1 -3 2 1 12 3 1 -3 2 1 12 3 6 14 2 5 18 3 6 14 2 5 18 4 3 24 3 1 9 4 3 24 3 1 9 5 2

8、 18 3 4 24 5 2 18 3 4 24 6 1 15 4 6 -7 6 1 15 4 6 -7 6 4 -7 6 3 14 6 4 -7 6 3 14 三元组指不仅存储矩阵的非三元组指不仅存储矩阵的非0元，元，同时记录它们的行列位置，即（同时记录它们的行列位置，即（i,j,aij）唯一）唯一确定一个非确定一个非0元，进而确定稀疏矩阵元，进而确定稀疏矩阵1.三元组顺序表三元组顺序表#define MAXSIZE 12500 /假设非零元素的最大值typedef struct int i, j; /非零元素的行下标和列下标 ElemType e;Triple;typedef union

9、Triple dataMAXSIZE+1; /非零元三元组表，data0未用未用 int mu,nu,tu; /矩阵的行数，列数和非零元个数TSMatrix-0 0070 0 150 00 0 018 0 0 00 0240 0 0140 0 0 030 00 0 0 0 0 0 00 0 912 0 MTSMatrix t; t.mu=XX; t.nu=XX; t.tu=XX; t.dataXXX.i=XXXX; t.dataXXX.j=XXXX; t.dataXXX.e=XXX;对比行逻辑链接的顺序表 (1)从一个二维矩阵创建其三元组表示从一个二维矩阵创建其三元组表示 以行序方式扫描二维矩

10、阵以行序方式扫描二维矩阵A,将其非零将其非零的元素插入到三元组的元素插入到三元组t的后面。算法如下：的后面。算法如下：nvoid CreateSMatrix(TSMatrix &t, ElemType AMN)n t.mu=M; t.nu=N; t.tu=0;n for (int i=0;iM;i+)n for (int j=0;jN;j+) n if(Aij!=0) /*只存储非零元素*/n t.datat.tu+1.i=i+1; n t.datat.tu+1.j=j+1;n t.datat.tu+1.e=Aij;n t.tu+;n n n n void PrintSMatrix(TSMat

11、rix M)n / 按矩阵形式输出Mn int i,j,k=1; / 非零元计数器，初值为1n Triple *p=M.data+1; / p指向M的第1个非零元素data0未用未用n for(i=1;i=M.mu;i+) / 从第1行到最后一行n for(j=1;j=M.nu;j+) / 从第1列到最后一列n if(ki=i&p-j=j) / p指向非零元，且p所指元素为当前循环在处理元素n printf(%3d,(p+)-e); / 输出p所指元素的值，p指向下一个元素n k+; / 计数器+1n n else / p所指元素不是当前循环在处理元素n printf(%3d,0); / 输出

12、0n printf(n);n n (2) PrintSMatrix(M) /输出稀疏矩阵输出稀疏矩阵M按矩阵形式输出M(M:三元组顺序表三元组顺序表):矩阵的转置矩阵的转置（1）将矩阵的行列值相互交换（2）将每个三元组中的i和j相互调换（3）重排三元组之间的次序i j v1 3 -31 6 152 1 122 5 183 1 93 4 244 6 -7 6 3 14-0 0070 0 150 00 0 018 0 0 00 0240 0 0140 0 0 030 00 0 0 0 0 0 00 0 912 0 M 0 0 0 0 0 0 0 0 0140 0 0 0 0 0 0 0 7-0 0

13、 0 0 0 0 0240 0 9 0 18 0 0 012 15 0 0 3-0 0 Ti j v1 2 121 3 93 1 -33 6 144 3 245 2 186 1 15 6 4 -7M.dataT.data点将法Status TransposeSMatrix(TSMatrix M,TSMatrix &T) /采用三元组表存储表示，求稀疏矩阵M的转置矩阵T T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if(T.tu) q=1; for(col=1;col=M.nu;+col) /对 M的每一列 for(p=1;p=M.tu;+p) /扫描M.data if(M

14、.datap.j=col) T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; +q; return OK; /TransposeSMatrix稀疏矩阵转置算法算法5.1Status TransposeSMatrix(TSMatrix M,TSMatrix &T) /采用三元组表存储表示，求稀疏矩阵M的转置矩阵T T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if(T.tu) q=1; for(col=1;col=M.nu;+col) for(p=1;p=M.tu;+p) if(M.datap.j=c

15、ol) T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; +q; return OK;/TransposeSMatrixM.dataT.datai j v1 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -7i j v算法5.13.十字链表十字链表typedef struct OLNode int i, j; /该非零元的行和列下标该非零元的行和列下标 ElemType e; struct OLNode *right, *down; /非零元所在行表和列表的后继链域非零元所在行表和列表的后继链域OLNo