《数组的转置》PPT课件.ppt

1,稀疏矩阵的操作,已知三元组表a.data,求三元组表b.data,M,T,（转置运算）,目的：,2,除了：（1）每个元素的行下标和列下标互换（即三元组中的i和j互换）；还需要：（2）T的总行数mu和总列数nu也要互换；（3）重排三元组内各元素顺序，使转置后的三元组也按行（或列）为主序有规律的排列。,上述（1）和（2）容易实现，难点在（3）。,有两种实现转置的方法,压缩转置快速(压缩)转置,3,方法1：压缩转置,思路：反复扫描a表（记为a.data）中的列序，从j=1n依次进行转置。,已知三元组表a.data,求三元组表b.data,1,1,2,2,col,q,1,2,3,4,每个元素的列分量表示为：a.datap.j,.,4,方法2 快速转置,已知三元组表a.data,求三元组表b.data,思路：依次把a.data中的元素直接送入b.data的恰当位置上（即M三元组的p指针不回溯）。,关键：怎样寻找b.data的“恰当”位置？,q,3,5,5,如果能预知M矩阵每一列(即T的每一行)的非零元素个数，又能很快得知第一个非零元素在b.data中的位置,则扫描a.data时便可以将每个元素准确定位(因已知若干参考点),技巧：为实现转置运算，应当按列生成 M 矩阵三元组表的两个辅助向量，让它携带每列的非零元素个数 NUM(i)以及每列的第一个非零元素在三元组表中的位置POS(i)等信息。,设计思路：,计算式：POS(1)1POS(i)POS(i-1)+NUM(i-1),辅助向量的样式：,请注意a.data特征：每列首个非零元素必定先被扫描到。,6,令：M矩阵中的列变量用col表示；num col：存放M中第col 列中非0元素个数 cpot col：存放M中第col列的第一个非0元素的位置（即b.data中待计算的“恰当”位置所需参考点）,讨论：求出按列优先的辅助向量后，如何实现快速转置？,计算式：cpot(1)1cpotcol cpotcol-1+numcol-1,3 5 7 8 9,由a.data中每个元素的列信息，可以直接从辅助向量cpotcol中查出在b.data中的“基准”位置，进而得到当前元素之位置。,7,Status FastTransposeSMatrix（TSMatirx M,TSMatirx,快速转置算法描述：,/M是顺序存储的三元组表，求M的转置矩阵T,/先清0再统计每列非零元素个数,/再生成每列首元位置辅助向量,/p指向a.data，循环次数为非0元素总个数tu,/查辅助向量得q，即T中位置,前3个for循环用来产生两个辅助向量,重要！修改向量内容（列坐标加1），预备给同列的下一非零元素定位之用,元素转置,8,1.与常规算法相比，附加了生成辅助向量表的工作。增开了2个长度为列长的数组(num 和cpos）。,传统转置：O(mu*nu)压缩转置：O(mu*tu)压缩快速转置：O(nu+tu),快速转置算法的效率分析：,2.从时间上，此算法用了4个并列的单循环，而且其中前3个单循环都是用来产生辅助向量表的。for(col=1;col=M.nu;col+);循环次数nu（列数）;for(i=1;i=M.tu;i+);循环次数tu（非0元素个数）;for(col=2;col=M.nu;col+);循环次数nu;for(p=1;p=M.tu;p+);循环次数tu;该算法的时间复杂度nu+tu+nu+tu=O(nu+tu）,讨论：最恶劣情况是矩阵中全为非零元素，此时tu=nu*mu而此时的时间复杂度也只是O(mu*nu)，并未超过传统转置算法的时间复杂度。,小结：,增设辅助向量，牺牲空间效率换取时间效率。,