三元组的应用

《三元组的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、三元组的应用三元组的应用主要内容1．三元组的定义2．三元组转置3．三元组相乘1．三元组的定义三元组的用途用来表示稀疏矩阵，那什么是稀疏矩阵？稀疏矩阵定义非零元素的个数<<矩阵中元素的总数。压缩策略仅存储非零元素,不存储零元素。如何准确定位一个元素呢？1、行号2、列号3、值这就是三元组稀疏矩阵三元组的C++的描述templatestructelement{introw；intcol;Titem;};1、行号2、列号3、值稀疏矩阵压缩存储012900000000000-3000014000240000

2、018000001500-7000M=ijv011202920-3251432244118501553-7稀疏矩阵三元组按行优先稀疏矩阵三元组采用顺序存储结构存储的三元组表称为三元组顺序表。（按行优先）ijv011202920-3251432244118501553-7如何用C++描述三元组顺序表三元组顺序表的C++描述#defineMAXTERM100templatestructSparseMatrix{structelement{introw;intcol;Titem;};elementdat

3、a[MAXTERM];intmu,nu,tu;//行数、列数、非零元素数};2．三元组转置转置的定义对于一个m*n的矩阵M，转置矩阵T为n*m，且T(i,j)=M(j,i)，1≤i≤n，1≤j≤m。00-3001512000180900240000000-70000000014000000000T=012900000000000-3000014000240000018000001500-7000M=矩阵转置矩阵转置常规的矩阵转置MmnTnmfor(col=0;col

4、m;++row)T[col][row]=M[row][col];其时间复杂度为:O(m×n)2．三元组转置算法1:将A转置得到Bijv011202920-3251432244118501553-7A在A的三元组顺序表中依次找第0列、第1列……直到最后一列的三元组，并将找到的三元组的行、列交换后存储在B的顺序表中。2．三元组转置voidTranspose(SparseMatrixA,SparseMatrix&B){//初始化相关信息B.mu=A.nu;//行数B.nu=A.mu;//列数B.tu=A.tu;//元素

5、数if(B.tu>0){①//开始三元组转置}}intpb=0;//B中元素的存储位置①在A中依次找第0列、第1列……直到最后一列。for(intcol=0;col

6、++;}}算法分析时间复杂度O(nu*tu)时间耗费的原因在A中依次寻找第0列、第1列……,每次都需要反复扫描A表。那么我们能不能之扫描一遍或两遍A表，而直接定位A中的元素在B中的位置？2．三元组转置（改进）算法2:将A转置得到Bijv011202920-3251432244118501553-7A在A表中依次取三元组交换行、列后直接存储在B表适当的位置。？2．三元组转置（改进）我们可以知道：1、第0列的第一个元素的存储位置2、A中每一列的元素总数经过计算，可以得到A中每一列的第一个非零元素的存储位置ijv011

7、202920-3251432244118501553-72．三元组转置（改进）需要附设两个数组num[]：每一列的元素个数for(inti=0;i

8、.nu=A.mu;//列数B.tu=A.tu;//元素数if(B.tu>0){①//初始化附设数组②//扫描A，将A中元素交换行、列存储到B中}}②//扫描A，将A中元素交换行、列存储到B中for(inti=0;i