2022年2022年矩阵的压缩存储 .pdf

1 5.3.矩阵的压缩存储特殊矩阵是指在矩阵中有许多值相同的元素，或零元素，或非0 元素、 0 元素的分布有一定的规律的矩阵。为了节约存储空间，对他们进行压缩。（1）对称矩阵：若 n 阶矩阵 A 中的元素满足),1 (njiaajiij注意：这里规定矩阵的下标范围1.n 行1.n列。压缩策略：只存储上三角或下三角的元素。所需空间n(n+1)/2.。ijiiiiiaaaaaaaaaaa1)1)(1(21333231222111.方法一：用一维数组sa0.n(n+1)/2 存储以行序为主序的下三角（包括对角线），其中 sa0不存放矩阵元素，其地址的运算，即aij和 sak 之间存在如下对应关系：时（上三角元素）当素对角线元素和下三角元时当jiijjjijiik2)1()(2) 1(方法二：用一维数组sa0.n(n+1)/2-1 存储以行序为主序的下三角（包括对角线），其地址的运算：aij和 sak 之间存在如下对应关系：时（上三角元素）当素对角线元素和下三角元时当jiijjjijiik12)1()(12) 1(a11与 sa0 对应，即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，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - 2 nnijninnaccccacacccaccaaaacaaaaa.),1(332242322114131211压缩策略：只存储上三角的n(n+1)/2 个不同元素和下三角的一个元素c。所需空间用一维数组 sa0.n(n+1)/2 存储以行序为主序的下三角（包括对角线），其地址的运算：a11与 sa0 对应， 即 LOC(a11)=0， aij（ij） 的位置对应于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和 sak 之间存在如下对应关系：k=时当时当jnnjijinii2) 1(*i2)22(*) 1(下三角矩阵则反之。（3）对角矩阵77766766655655544544433433322322211211000000000000000000000000000000aaaaaaaaaaaaaaaaaaa名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - 3 77766766655655544544433433322322211211000000000000000000000000000000aaaaaaaaaaaaaaaaaaa（4）稀疏矩阵稀疏矩阵：零元素个数远远大于非零元素的个数。稀疏因子：在m*n 的矩阵中， t 个元素不为0，nmt，称为矩阵的稀疏因子。通常认为 0.05 时称为稀疏矩阵。M 矩阵：00070015000001800000240001400003000000000009120M 矩阵的压缩存储：三元组表示：行、列、值（(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 是 mn 矩阵， T 是 M 矩阵的转置， T 是 nm 矩阵，且T(i,j)=M(j,i),1in,1jm. 00000000014000000007000000024009018000121500300（一）稀疏矩阵的三元组顺序表存储表示p98 #define MAXSIZE 12500/ 非零元素最大个数typedef struct int i,j;/ 非零元素的行下标、列下标elemtype e; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - 4 Triple; typedef struct Triple dataMAXSIZE+1;/data0未用int mu,nu,tu;/ 行数、列数、非零元素个数TSMatrix; (以上图形由文档“表5-1”生成 ) （二）行逻辑链接的顺序表p100 typedef struct Triple dataMAXSIZE+1;/ data0未用int rposMAXCO+1/ 各行第一个非零元的位置表,rpos 0 未用 , int mu,nu,tu;/ 行数、列数、非零元素个数RLSMatrix; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - 5 （三）稀疏矩阵的十字链表存储表示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 页，共 5 页 - - - - - - - - -