★稀疏矩阵 今定义:非零元较零元少,且分布没有一定规律的矩阵 今压缩存储原则:只存矩阵的行列维数和每个非零元的 行列下标及其值 01290000 0000000 30000140 M 00240000 01800000 1500-7000 M由{(1,2,12)(1,39),(3,1,-3),(3,6,14),(43,24) (5,2,18),(6,1,15)(6,4,-7)}和矩阵维数(6,7)唯一确定
15 0 0 7 0 0 0 6 7 0 18 0 0 0 0 0 0 0 24 0 0 0 0 3 0 0 0 0 14 0 0 0 0 0 0 0 0 0 12 9 0 0 0 0 − − M = M由{(1,2,12), (1,3,9), (3,1,-3), (3,6,14), (4,3,24), (5,2,18), (6,1,15), (6,4,-7) } 和矩阵维数（6,7）唯一确定 稀疏矩阵 ❖定义：非零元较零元少，且分布没有一定规律的矩阵 ❖压缩存储原则：只存矩阵的行列维数和每个非零元的 行列下标及其值
心稀疏矩阵的压缩存储方法 01290000 0000000 ●顺序存储结构 30000140 ◆三元组表 #define M 20 00240000 typedef struct node 0 1800000 行列下标 非零元值{inti 0-7000 Int v JJD 678 mal 12 maO]ma[o]j,ma[0]v分别存放 矩阵行列维数和非零元个数 4324 5218 元组表所需存储单元个数为3(t+1) 其中t为非零元个数 6115 64-7 ma
❖稀疏矩阵的压缩存储方法 ⚫顺序存储结构 ◆三元组表 #define M 20 typedef struct node { int i,j; int v; }JD; JD ma[M]; 三元组表所需存储单元个数为3(t+1) 其中t为非零元个数 6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 ma i j v 0 1 2 3 4 5 6 7 8 ma[0].i,ma[0].j,ma[0].v分别存放 矩阵行列维数和非零元个数 行列下标 非零元值 15 0 0 7 0 0 0 6 7 0 18 0 0 0 0 0 0 0 24 0 0 0 0 3 0 0 0 0 14 0 0 0 0 0 0 0 0 0 12 9 0 0 0 0 − − M =
◆带辅助行向量的二元组表 增加一个辅助数组NRA[m+1,其物理意义是第i行第一个非零元 在二元组表中的起始地址(m为行数) 显然有:(NRA[=1 NRA[i]=NRA[i-1]+第i-1行非零元个数(1>2) 列下标和 NRA 非零元值 NRA[O]不用或 存矩阵行数 6 78 212 矩阵列数和 39 非零元个数 14 01290000 7 元组表需存储单元 个数为2(t+1)+m+1 63214 24 5/s/3 18 0000140 00240000 01800000 500-7000 ma
◆带辅助行向量的二元组表 增加一个辅助数组NRA[m+1],其物理意义是第i行第一个非零元 在二元组表中的起始地址（m为行数） 显然有： NRA[1]=1 NRA[i]=NRA[i-1]+第i-1行非零元个数(i2) 0 1 2 3 4 5 6 NRA 1 3 3 5 6 7 6 7 8 2 12 3 9 1 -3 6 14 3 24 2 18 1 15 4 -7 ma j v 0 1 2 3 4 5 6 7 8 矩阵列数和 非零元个数 列下标和 非零元值 NRA[0]不用或 存矩阵行数 二元组表需存储单元 个数为2(t+1)+m+1 15 0 0 7 0 0 0 6 7 0 18 0 0 0 0 0 0 0 24 0 0 0 0 3 0 0 0 0 14 0 0 0 0 0 0 0 0 0 12 9 0 0 0 0 − − M =