数据结构稀疏矩阵的三元组表存储方法学习教案

1、会计学1数据结构稀疏矩阵的三元组表存储数据结构稀疏矩阵的三元组表存储(cn ch)方法方法第一页，共21页。一、什么一、什么(shn me)是稀疏矩阵是稀疏矩阵(sparse matrix) 如果矩阵如果矩阵(j zhn)M中的大多中的大多数元素均为零元素，则称矩阵数元素均为零元素，则称矩阵(j zhn)M为稀疏矩阵为稀疏矩阵(j zhn) 。一般地，当非零元素个数只占矩阵一般地，当非零元素个数只占矩阵(j zhn)元素总数的元素总数的25%30%,或或低于这个百分数时，我们称这样的低于这个百分数时，我们称这样的矩阵矩阵(j zhn)为稀疏矩阵为稀疏矩阵(j zhn)。第1页/共21页第二页，

2、共21页。 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 0M=例如例如(lr)：一、什么是稀疏一、什么是稀疏(xsh)矩阵矩阵(sparse matrix) 如果矩阵如果矩阵M中的大多数元素中的大多数元素(yun s)均为零元素均为零元素(yun s)，则称矩阵，则称矩阵M为稀疏矩阵。为稀疏矩阵。第2页/共21页第三页，共21页。 用一个三元组（用一个三元组（tupel3）存放矩阵）存放矩阵(j zhn)中的一个非零元素的行号、列号及该中的一个非零元素的行号、列号及

3、该非零元素的值。非零元素的值。 一个三元组的形式为：一个三元组的形式为：（i , j, e） 一般情况下，一个稀疏一般情况下，一个稀疏(xsh)矩阵中有若干矩阵中有若干个非零元素，所以要用一个个非零元素，所以要用一个“三元组线性表三元组线性表”来来存放一个稀疏存放一个稀疏(xsh)矩阵。矩阵。1.中心思想：仅存储矩阵中的非零元素中心思想：仅存储矩阵中的非零元素第3页/共21页第四页，共21页。2.用顺序存储结构用顺序存储结构(jigu)存放三元组存放三元组线性表线性表M=原矩阵原矩阵(j zhn):存放存放(cnfng)形式形式: （按行顺序（按行顺序存放存放(cnfng)）data p i

4、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 015 0 0 -7 0 0 0mu=6 nu=7 tu=8注意：注意：为了保存矩阵的行数、列数为了保存矩阵的行数、列数和非零元素个数，还需增设和非零元素个数，还需增设三个量：三个量：mu nu tu第4页/共21页第五页，共21页。3.三元

5、组线性表的数据类型描述三元组线性表的数据类型描述(mio sh)#define MAXSIZE 12500 /非零元素(yun s)个数的最大值typedef struct int i, j; ElemType e; Triple;typedef struct Triple data MAXSIZE+1; /三元组表，data0不用(byng) int mu , nu , tu ; /矩阵的行数、列数、非0元素个数TSMatrix /sparseness(稀疏)TSMatrix M ； 第5页/共21页第六页，共21页。用变量用变量 a 存放存放(cnfng)矩阵矩阵 M 的形式如下：的形式如

6、下： 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注意：注意： 引用引用(ynyng)i ,j ,(ynyng)i ,j ,e e 时的格式应为：时的格式应为： a .data a .data p .i p .i a .data a .data p .j p .j a .data a .dat

7、a p .e p .e例如例如 x=ax=adata6.jdata6.j 则则 x=2 x=2第6页/共21页第七页，共21页。三、实现矩阵的运算三、实现矩阵的运算(yn sun):矩矩阵转置阵转置1.实例实例(shl):求矩阵求矩阵M的转置矩阵的转置矩阵N:第7页/共21页第八页，共21页。三、实现三、实现(shxin)矩阵的运算矩阵的运算:矩矩阵转置阵转置1.实例实例(shl):求矩阵求矩阵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

8、 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=求解求解(qi ji)注意注意:用变量用变量a和和 b分别存放矩阵分别存放矩阵M和和N (TSMatrix a, TSMatrix b),即即要从已知变量要从已知变量a来求得变量来求得变量b的值。的值。第8页/共21页第九页，共21页。也既要完成也既要完成(wn chng)如下求解工如下求解工作：作： a . data p i j e a .data 1 1 2 12 a .data 2 1 3 9

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

10、=8求解求解(qi ji)第9页/共21页第十页，共21页。2.求解求解(qi ji)步骤分析：步骤分析：p=1:8, q的值的值=1,2 a . data 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

11、 .data 5 b .data 6 b .data 7 b .data 8 求得求得1Col=1注注:p=1:8,寻找寻找(xnzho) j=col 的的a.data p1 1 3 -3 1 6 15第10页/共21页第十一页，共21页。2.求解求解(qi ji)步骤分析：步骤分析：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

12、 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 5 b .data 6 b .data 7 b .data 8 求得求得22注注:p=1:8,寻找寻找(xnzho) j=col 的的a.data pCol=2 2 1 12 2 5 18第11页/共21页第十二页，共21页。2.求解步骤求解步骤(bzhu)分析：分析：p=1:8, q的值的值=5,6 a . data p i j e a .data 1 1 2 12 a .

13、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 . 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 b .data 6 b .data 7 b .data 8 求得求得33Col=3注注:p=1:8,寻找寻找(xnzho) j=col 的的

14、a.data p 3 1 9 3 4 24第12页/共21页第十三页，共21页。2.求解求解(qi ji)步骤分析：步骤分析：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 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、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,寻找寻找(xnzho) j=col 的的a.data p4 4 6 -7 第13页/共21页第十四页，共21页。2.求解求解(qi ji)步骤分析：步骤分析：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

16、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 求得求得Col=5注注:p=1:8,寻找寻找(xnzho) j=col 的的a.data p无无!第14页/共21页第十五页，共21页。2.求解步骤求解步

17、骤(bzhu)分析：分析：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 .data 2 1 6 15 b .data 3 2 1 12 b .data 4 2 5 18 b .data 5 3 1

18、 9 b .data 6 3 4 24 b .data 7 4 6 -7 b .data 8 求得求得Col=6注注:p=1:8,寻找寻找(xnzho) j=col 的的a.data p6 6 3 14 第15页/共21页第十六页，共21页。2.求解步骤求解步骤(bzhu)分析：分析：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 18 a .data 7 6 1 15 a .data

19、 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,寻找寻找(xnzho) j=col 的的a.data p无无!第16页/共21页第十七页，共21页。2.求解求解(qi ji)步骤分析：步骤分析： 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 .