Chapter5(2)_稀疏矩阵转置.ppt

《Chapter5(2)_稀疏矩阵转置.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、稀疏矩阵所谓稀疏矩阵,是指矩阵中有大部分的值相同或值为零的元素,且这些元素的分布没有规律.只需存储非零元,或再用一个单元存储值相同的元素以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题:1)零值元素占了很大空间;2)计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零;1)尽可能少存或不存零值元素;解决问题的原则:2)尽可能减少没有实际意义的运算;3)操作方便;即:能尽可能快地找到与下标值(i,j)对应的元素;能尽可能快地找到同一行或同一列的非零值元;随机稀疏矩阵的压缩存储方法:一、三元组顺序表二、行逻辑联接的顺序表三、十字链表类型定义矩阵转置稀疏

2、矩阵转置快速稀疏矩阵转置一、三元组顺序表#defineMAXSIZE12500typedefstruct{inti,j;//该非零元的行下标和列下标ElemTypee;//该非零元的值}Triple;//三元组类型一、三元组顺序表typedefunion{Tripledata[MAXSIZE+1];intmu,nu,tu;}TSMatrix;//稀疏矩阵类型可以这样存储munutu678ije121213931-3361443245218611564-7行数列数元素数值所在行所在列元素值保持行序如何求转置矩阵？用“三元组”表示时如何实现？121415-522-

3、731363428211451-522-713364328用常规的二维数组表示时的算法其时间复杂度为:O(mu×nu)for(col=1;col<=nu;++col)for(row=1;row<=mu;++row)T[col][row]=M[row][col];实现三元组表存储的稀疏矩阵的转置运算munutu678ijv121213931-3361443245218611564-7munutu768ijv211231913-3631434242518161546-7munutu768ijv13-3161521122518319342446-76314munut

4、u678ijv121213931-3361443245218611564-7算法1的转置过程munutu768ijv13-3161521122518319342446-76314算法分析(M--T)q=0;以原始矩阵的列K(1---M.nu)开始查询并转换1)从第一列开始,扫描一切非零的数据总数目为M.tu(p=0…M.nu-1)M.data[p].j==K的话,则将M.data[p]-T.data[q]转换,其中变换其(I,j,data)—(j,I,data),并且p++,q++;如果M.data[p].j!=K时,p++K++;2)从第二列开始,扫描一切

5、非零的数据总数目为M.tu(p=0…M.nu-1)M.data[p].j==K的话,则将M.data[p]-T.data[q]转换,其中变换其(I,j,data)—(j,I,data),并且p++,q++;如果M.data[p].j!=K时,p++……规律：循环执行为O(M.nu*M.tu)算法1:按照矩阵A的列序进行转置StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){q:=1;for(col=0;col<=M.nu;col++)for（p

6、=1；p<=M.tu;p++)if(M.data[p].j==col){T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;q++;}}returnOK;}//TransposeSMatrix首先应该确定转置矩阵中每一行的第一个非零元在三元组中的位置。cpot[1]=1;for(col=2;col<=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];Col=M.data[p].j;q=cpot[col];T.data[q].i=M.

7、data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++cpot[col]分析算法FastTransposeSMatrix的时间复杂度：时间复杂度为:O(M.nu+M.tu)for(col=1;col<=M.nu;++col)……for(t=1;t<=M.tu;++t)……for(col=2;col<=M.nu;++col)……for(p=1;p<=M.tu;++p)……StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=

8、M.mu;T.tu=M.tu;if(T