数据结构-稀疏矩阵的三元组表存储方法.ppt

稀疏矩阵的压缩存储 ———三元组表,一、什么是稀疏矩阵(sparse matrix),如果矩阵M中的大多数元素均为零元素，则称矩阵M为稀疏矩阵。,0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 -7 0 0 0,,,,,,,M=,例如：,一、什么是稀疏矩阵(sparse matrix),如果矩阵M中的大多数元素均为零元素，则称矩阵M为稀疏矩阵。,用一个三元组（tupel3）存放矩阵中的一个非零元素的行号、列号及该非零元素的值。一个三元组的形式为：（i , j, e）,二、三元组线性表存储结构,一般情况下，一个稀疏矩阵中有若干个非零元素，所以要用一个“三元组线性表”来存放一个稀疏矩阵。,,,,1.中心思想：仅存储矩阵中的非零元素,2.用顺序存储结构存放三元组线性表,,,,,,,M=,原矩阵:,存放形式: （按行顺序存放）,data p i j e data 1 1 2 12 data 2 1 3 9 data 3 3 1 -3 data 4 3 6 14 data 5 4 3 24 data 6 5 2 18 data 7 6 1 15 data 8 6 4 -7,,0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 -7 0 0 0,,,,,,,,,,,,,,,,,,,,,,mu=6 nu=7 tu=8,,注意：为了保存矩阵的行数、列数和非零元素个数，还需增设三个量：mu nu tu,,3.三元组线性表的数据类型描述,#define MAXSIZE 12500 //非零元素个数的最大值 typedef struct{ int i, j; ElemType e; }Triple;,typedef struct{ Triple data [MAXSIZE+1]; //三元组表，data[0]不用 int mu , nu , tu ; //矩阵的行数、列数、非0元素个数 }TSMatrix //sparseness(稀疏),TSMatrix M ；,用变量 a 存放矩阵 M 的形式如下：,a . data p i j e a .data 1 1 2 12 a .data 2 1 3 9 a .data 3 3 1 -3 a .data 4 3 6 14 a .data 5 4 3 24 a .data 6 5 2 18 a .data 7 6 1 15 a .data 8 6 4 -7 a. mu=6 a. nu=7 a. tu=8,,,,,,,,,,,,,,,,,,,,,,,,,,注意：引用i ,j ,e 时的格式应为： a .data [ p] .i a .data [ p] .j a .data [ p] .e 例如 x=a．data[6].j 则 x=2,三、实现矩阵的运算:矩阵转置,1.实例:求矩阵M的转置矩阵N:,,,三、实现矩阵的运算:矩阵转置,1.实例:求矩阵M的转置矩阵N:,0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 -7 0 0 0,,,,,,,M=,,,0 0 -3 0 0 15 12 0 0 0 18 0 9 0 0 24 0 0 0 0 0 0 0 -7 0 0 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0,,,,,,,,N=,求解,,注意:用变量a和 b分别存放矩阵M和N (TSMatrix a, TSMatrix b),即要从已知变量a来求得变量b的值。,,也既要完成如下求解工作：,a . data p i j e a .data 1 1 2 12 a .data 2 1 3 9 a .data 3 3 1 -3 a .data 4 3 6 14 a .data 5 4 3 24 a .data 6 5 2 18 a .data 7 6 1 15 a .data 8 6 4 -7 a. mu=6 a. nu=7 a. tu=8,b . data q i j e b .data 1 1 3 -3 b .data 2 1 6 15 b .data 3 2 1 12 b .data 4 2 5 18 b .data 5 3 1 9 b .data 6 3 4 24 b .data 7 4 6 -7 b .data 8 6 3 14 b. mu=7 b. nu=6 b. tu=8,