三元组的应用

三元组的应用三元组的应用主要内容1．三元组的定义2．三元组转置3．三元组相乘1．三元组的定义三元组的用途用来表示稀疏矩阵，那什么是稀疏矩阵？稀疏矩阵定义非零元素的个数矩阵中元素的总数。压缩策略仅存储非零元素,不存储零元素。如何准确定位一个元素呢？1、行号2、列号3、值这就是三元组稀疏矩阵三元组的C++的描述templateclassTstructelement{introw；intcol;Titem;};1、行号2、列号3、值稀疏矩阵压缩存储012900000000000-3000014000240000018000001500-7000M=ijv011202920-3251432244118501553-7稀疏矩阵三元组按行优先稀疏矩阵三元组采用顺序存储结构存储的三元组表称为三元组顺序表。（按行优先）ijv011202920-3251432244118501553-7如何用C++描述三元组顺序表三元组顺序表的C++描述#defineMAXTERM100templateclassTstructSparseMatrix{structelement{introw;intcol;Titem;};elementdata[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;coln;++col)for(row=0;rowm;++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;//元素数if(B.tu0){①//开始三元组转置}}intpb=0;//B中元素的存储位置①在A中依次找第0列、第1列……直到最后一列。for(intcol=0;colA.nu;col++)for(intpa=0;paA.tu;pa++){if(A.data[pa].col==col)②将找到的三元组的行、列交换后存储在B中。{B.data[pb].row=A.data[pa].col;B.data[pb].col=A.data[pa].row;B.data[pb].item=A.data[pa].item;pb++;}}算法分析时间复杂度O(nu*tu)时间耗费的原因在A中依次寻找第0列、第1列……,每次都需要反复扫描A表。那么我们能不能之扫描一遍或两遍A表，而直接定位A中的元素在B中的位置？2．三元组转置（改进）算法2:将A转置得到Bijv011202920-3251432244118501553-7A在A表中依次取三元组交换行、列后直接存储在B表适当的位置。？2．三元组转置（改进）我们可以知道：1、第0列的第一个元素的存储位置2、A中每一列的元素总数经过计算，可以得到A中每一列的第一个非零元素的存储位置ijv011202920-3251432244118501553-72．三元组转置（改进）需要附设两个数组num[]：每一列的元素个数for(inti=0;iA.nu;i++)num[A.data[i].col]++;cpot[]：每一列第一个非零元素的位置cpot[0]=0;for(i=1;iA.nu;i++)cpot[i]=cpot[i-1]+num[i-1];2．三元组转置（改进）voidTranspose(SparseMatrixA,SparseMatrix&B){//初始化相关信息B.mu=A.nu;//行数B.nu=A.mu;//列数B.tu=A.tu;//元素数if(B.tu0){①//初始化附设数组②//扫描A，将A中元素交换行、列存储到B中}}②//扫描A，将A中元素交换行、列存储到B中for(inti=0;iA.tu;i++){intj=A.data[i].col;B.data[cpot[j]].row=A.data[i].col;B.data[cpot[j]].col=A.data[i].row;B.data[cpot[j]].item=A.data[i].item;cpot[j]++;}算法分析时间复杂度O(nu+tu)空间复杂度O(nu)3．三元组相乘矩阵相乘ijv11314522-1312ijv12221131-2324ijv12621-13243005M=0-100200002N=10-240006Q=-1004X=矩阵相乘Q=M*N：m1*n2矩阵M：m1*n1矩阵N：m2*n2矩阵Q(i,j)=11),(*),(nkjkNkiM常规的矩阵相乘算法for(inti=0;im1;++i)for(intj=0;jn2;++j){Q[i][j]=0;for(intk=0;kn1;++k)Q[i][j]+=M[i][k]*N[k][j];}其时间复杂度为:O(m1×n1×n2)3．三元组的相乘templateclassTvoidMul(MatrixT&M,MatrixT&N,MatrixT&Q){if(M.n!=N.m)return;Tctemp[100];Q.m=M.m;Q.n=N.n;Q.t=0;3.三元组的相乘if(M.t*N.t!=0){for(introw=1;row=M.m;++row){for(inti=1;i=N.n;i++)ctemp[i]=0;for(intp1=1;p1=M.t;p1++){if(M.data[p1].i==row){for(intp2=1;p2=N.t;p2++){if(M.data[p1].j==N.data[p2].i)ctemp[N.data[p2].j]+=M.data[p1].e*N.data[p2].e;}}}3.三元组的相乘for(i=1;i=N.n;i++){if(ctemp[i]!=0){Q.data[++Q.t].i=row;Q.data[Q.t].j=i;Q.data[Q.t].e=ctemp[i];}}}性能分析时间复杂度O(M.m*M.t*N.t)3.三元组的相乘（改进）增加一个数组，记录矩阵每一行的首元素的位置，直接定位M和N中相乘的元素ijv11314522-1312rowrpos[row]123134ijv12221131-2324rowrpos[row]123412353.三元组的相乘（改进）templateclassTvoidMul(MatrixT&M,MatrixT&N,MatrixT&Q){(1)求M的rpos数组值(2)求N的rpos数组值if(M.n!=N.m)return;Tctemp[100];//累加器inttp,t;Q.m=M.m;Q.n=N.n;Q.t=0;if(M.t*N.t!=0){(3)三元组相乘}}3.三元组的相乘（改进）(1)求M的rpos数组值intnum[100];for(introw=1;row=M.m;row++)num[row]=0;for(inttu=1;tu=M.t;tu++)num[M.data[tu].i]++;//每一行的元素个数M.rpos[1]=1;//第一行首元素位置for(row=2;row=M.m;row++)M.rpos[row]=M.rpos[row-1]+num[row-1];//首元素位置=前一行首元素位置+前一行元素个数3.三元组的相乘（改进）(2)求N的rpos数组值for(row=1;row=N.m;row++)num[row]=0;for(tu=1;tu=N.t;tu++)num[N.data[tu].i]++;//每一行的元素个数N.rpos[1]=1;//第一行首元素位置for(row=2;row=N.m;row++)N.rpos[row]=N.rpos[row-1]+num[row-1];//首元素位置=前一行首元素位置+前一行元素个数for(intarow=1;arow=M.m;++arow){for(inti=1;iMAXSIZE;i++)ctemp[i]=0;//累加器清零Q.rpos[arow]=Q.t+1;if(arowM.m)tp=M.rpos[arow+1];elsetp=M.t+1;for(intp=M.rpos[arow];ptp;p++){intbrow=M.data[p].j;//找对应元在N中的行号if(browN.m)t=N.rpos[brow+1];elset=N.t+1;for(intq=N.rpos[brow];qt;q++){intccol=N.data[q].j;//乘积元素在Q中的列号ctemp[ccol]+=M.data[p].e*N.data[q].e;}}(4)遍历第arow每列的元素值，ctemp[ccol]=0清除(4)遍历第arow每列的元素值，ctemp[ccol]=0清除for(intccol=1;ccol=Q.n;ccol++)if(ctemp[ccol]!=0){if(++Q.tMAXSIZE)return;Q.data[Q.t].i=arow;Q.data[Q.t].j=ccol;Q.data[Q.t].e=ctemp[ccol];}}return;}三元组的总结三元组顺序表优点：存储结构简单缺点：对于一些操作（比如加法、乘法）非常不方便。