《(5.3.1)--chapter5-3三元组矩阵的快速转置.pdf》由会员分享,可在线阅读,更多相关《(5.3.1)--chapter5-3三元组矩阵的快速转置.pdf(10页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 数据结构与算法Data Structures and Algorithms 三元组矩阵的快速转置Fast Inversion of Triple Sequence TableData StructuresData StructuresChapter5 Array and Generalized Table 1.Triple Sequence#define MAXSIZE 1000typedef struct int row,col;ElementType e ;Triple;typedef struct Triple dataMAXSIZE+1;int m,n,len;TSMatrix;or
2、iginal matrixtriple sequence table1-028003600070500140 1 2 14 2 2 -7 3 1 36 3 4 28 1 5 -5row cole2Data StructuresData StructuresChapter5 Array and Generalized Table-028003600070500140-005280000007143600for(row=1;row=m;+row)for(col=1;col=n;+col)destcolrow=sourcerowcol;Time complexity:O(mn)Inversion a
3、lgorithm for matrix in 2-dimension array:2.Matrix inversion3Data StructuresData StructuresChapter5 Array and Generalized TableConventional strategy:Exchange row and column numbers,and then sort by row number.-028003600070500140-005280000007143600Its not Its not stored stored by row by row order!orde
4、r!reorder1 2 142 2 -73 1 363 4 281 5 -5row cole2 1 142 2 -71 3 364 3 285 1 -5row cole3.Matrix inversion of triple sequence table Data StructuresChapter5 Array and Generalized TableFast inversionBasic strategy3.Matrix inversion of triple sequence tabler1,j,v1r2,j,v2rk,j,vkMj,r1,v1j,r2,v2j,rk,vkTSuppo
5、se j-th column has k non-zero elements.The j-th column of M constitutes the j-th row of the transposed matrix T.(1)r1 r2 m=M-n;T-n=M-m;T-len=M-len;if(M-len)/*(1)Count the number of nonzero elements in each column of matrix*/for(j=1;jn;+j)numj=0;for(t=1;tlen;+t)+numM-datat.col;/*(2)Compute the 1st el
6、ements position of each row in matrix T*/for(pos1=1,j=1;jn-1;+j)posj+1=posj+numj;/*(3)inverse each element of thematrix in turn*/for(t=1;plen;t+)inverse matrix elements col=M-datat.col;T-data poscol.row=M-datat.col;T-data poscol.col=M-datat.row;T-data poscol.e=M.datat.e;poscol+;78Data SData Structur
7、estructuresChapter5 Array and Generalized Table4.SummarylAdvantage of triple sequence table:Efficiently store a sparse matrix into the memory.lDisadvantage of triple sequence table:The matrix elements cannot be accessed directly,which brings a lot of inconvenience for matrix manipulation.lWith examp
8、le of the matrix inversion:The algorithms for compressed storage are quite different from the ordinary one;An excellent algorithm is quite skillful in design,and looks rather elegant.Exercise after class:Write out the other matrix operation algorithms for triple sequence.Thank you!D Da at ta a S St tr ru uc ct tu ur re es s