《数据结构-稀疏矩阵的三元组表存储方法.ppt》由会员分享，可在线阅读，更多相关《数据结构-稀疏矩阵的三元组表存储方法.ppt（21页珍藏版）》请在金锄头文库上搜索。
1、 稀疏矩阵的压缩存储稀疏矩阵的压缩存储 三元组表三元组表一、什么是稀疏矩阵一、什么是稀疏矩阵(sparse matrix) 如果矩阵如果矩阵M中的大多数元素均中的大多数元素均为零元素，则称矩阵为零元素，则称矩阵M为稀疏矩阵为稀疏矩阵 。一般地，当非零元素个数只占矩。一般地，当非零元素个数只占矩阵元素总数的阵元素总数的25%30%,或低于或低于这个百分数时，我们称这样的矩阵这个百分数时，我们称这样的矩阵为稀疏矩阵。为稀疏矩阵。 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 015 0 0 -7 0
2、0 0M=例如：例如：一、什么是稀疏矩阵一、什么是稀疏矩阵(sparse matrix) 如果矩阵如果矩阵M中的大多数元素均中的大多数元素均为零元素，则称矩阵为零元素，则称矩阵M为稀疏矩阵。为稀疏矩阵。 用一个三元组（用一个三元组（tupel3）存放矩阵中的存放矩阵中的一个非零元素的行号、列号及该非零元素一个非零元素的行号、列号及该非零元素的值。的值。 一个三元组的形式为：（一个三元组的形式为：（i , j, e）二、三元组线性表存储结构 一般情况下，一个稀疏矩阵中有若干个一般情况下，一个稀疏矩阵中有若干个非零元素，所以要用一个非零元素，所以要用一个“三元组线性表三元组线性表”来存放一个稀疏矩
3、阵。来存放一个稀疏矩阵。1.中心思想：仅存储矩阵中的非零元素中心思想：仅存储矩阵中的非零元素2.用顺序存储结构存放三元组线性表用顺序存储结构存放三元组线性表M=原矩阵原矩阵:存放形式存放形式: （按行顺序存放）（按行顺序存放）data p i j edata 1 1 2 12data 2 1 3 9data 3 3 1 -3data 4 3 6 14data 5 4 3 24data 6 5 2 18data 7 6 1 15data 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
4、 015 0 0 -7 0 0 0mu=6 nu=7 tu=8注意：注意：为了保存矩阵的行数、列为了保存矩阵的行数、列数和非零元素个数，还需数和非零元素个数，还需增设三个量：增设三个量：mu nu tu3.三元组线性表的数据类型描述三元组线性表的数据类型描述#define MAXSIZE 12500 /非零元素个数的最大值typedef struct int i, j; ElemType e; Triple;typedef struct Triple data MAXSIZE+1; /三元组表，data0不用 int mu , nu , tu ; /矩阵的行数、列数、非0元素个数TSMatri
5、x /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 i ,j ,e 时的格式应为：时的格式应为： a .data p .ia .data
6、p .i a .data p .j a .data p .j a .data p .e a .data p .e例如例如 x= x=a adata6.jdata6.j 则则 x=2x=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 015 0 0 -7 0 0 0 M= 0 0 -3
7、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
8、 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求解求解2.求解步骤分析：求解步骤分析：p=1:8, q的值的值=1,2 a . dat
9、a p i j e a .data 1 1 2 12 a .data 2 1 3 9 a .data 3 3 -3 a .data 4 3 6 14 a .data 5 4 3 24 a .data 6 5 2 18 a .data 7 6 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 b .data 2 b .data 3 b .data 4 b .data 5 b .data 6 b .data 7 b .data 8 求得求得1Col=1注注:p=1:8,寻找寻找 j=col 的的a.data
10、 p1 1 3 -3 1 6 152.求解步骤分析：求解步骤分析：p=1:8, q的值的值=3,4 a . data p i j e a .data 1 1 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 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 b .data 4 b .data
11、 5 b .data 6 b .data 7 b .data 8 求得求得22注注:p=1:8,寻找寻找 j=col 的的a.data pCol=2 2 1 12 2 5 182.求解步骤分析：求解步骤分析：p=1:8, q的值的值=5,6 a . data p i j e a .data 1 1 2 12 a .data 2 1 9 a .data 3 3 1 -3 a .data 4 3 6 14 a .data 5 4 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 . dat
12、a 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 b .data 6 b .data 7 b .data 8 求得求得33Col=3注注:p=1:8,寻找寻找 j=col 的的a.data p 3 1 9 3 4 242.求解步骤分析：求解步骤分析：p=1:8, q的值的值=7 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
13、 24 a .data 6 5 2 18 a .data 7 6 1 15 a .data 8 6 -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 b .data 8 求得求得Col=4注注:p=1:8,寻找寻找 j=col 的的a.data p4 4 6 -7 2.求解步骤分析：求解步骤分析：p=1:8, q的值的值=7 a . da
14、ta 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
15、6 -7 b .data 8 求得求得Col=5注注:p=1:8,寻找寻找 j=col 的的a.data p无无!2.求解步骤分析：求解步骤分析：p=1:8, q的值的值=8 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 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 .d
16、ata 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 求得求得Col=6注注:p=1:8,寻找寻找 j=col 的的a.data p6 6 3 14 2.求解步骤分析：求解步骤分析：p=1:8, q的值的值=8 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
17、 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 求得求得Col=7注注:p=1:8,寻找寻找 j=col 的的a.data p无无!2.求解步骤分析：求解步骤分析： a . data p i j e a .data 1
18、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
19、 求得求得b. Mu=7 b.nu=6 b.tu=83.算法描述算法描述status TransposeSMatrix(TSMatrix a, TSMatrix *b) (*b).mu=a.nu; (*b).nu=a.mu; (*b).tu=a.tu; if (*b).tu) q= 1; for (col= 1 ; col= a.nu ; + + col) for (p= 1 ; p= a.tu ; + +p) if (a.datap .j = =col) b.dataq.i=a.datap .j; b.dataq.j=a.datap .i; b.dataq.e=a.datap.e; +q; return OK;/TransposeSMatrix4.4.小结：小结： 1. 试编写一程序，将一已知的稀疏矩阵输试编写一程序，将一已知的稀疏矩阵输入至变量入至变量 A中中,其中变量其中变量 A为为TSMatrix类型。类型。求出其转置矩阵。求出其转置矩阵。Many thanks to you！ End
