稀疏矩阵的存储压缩.ppt

《稀疏矩阵的存储压缩.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、稀疏矩阵的存储压缩稀疏矩阵(SparseMatrix)行数m=6,列数n=7,非零元素个数t=62.4稀疏矩阵稀疏矩阵(SparseMatrix)的抽象数据类型templateclassSparseMatrix{intRows,Cols,Terms;//行/列/非零元素数TrituplesmArray[MaxTerms];public://三元组表SparseMatrix(intMaxRow,intMaxcol);SparseMatrixTranspose();//转置SparseMatrix//相加Add(S

2、parseMatrixb);SparseMatrix//相乘Multiply(SparseMatrixb);}A的三元组顺序表图示A=012900000000000-3000014000240000018000001500-7000rowcolval01234567831-3611512125218139432464-73614三元组(Trituple)类的定义templateclassSparseMatrix;templateclassTrituple{friendclass

3、SparseMatrixprivate:introw,col;//非零元素所在行号/列号Typevalue;//非零元素的值}稀疏矩阵转置矩阵用三元组表表示的稀疏矩阵及其转置稀疏矩阵转置算法思想设矩阵列数为Cols，对矩阵三元组表扫描Cols次。第k次检测列号为k的项。第k次扫描找寻所有列号为k的项，将其行号变列号、列号变行号，顺次存于转置矩阵三元组表。设矩阵三元组表总共有Terms项，其时间代价为O(Cols*Terms)。若矩阵有200行，200列，10,000个非零元素，总共有2,000,000次处理。稀疏矩阵的转置template

4、e>SparseMatrixSparseMatrix::Transpose(){SparseMatrixb(Cols,Rows);b.Rows=Cols;b.Cols=Rows;b.Terms=Terms;//转置矩阵的列数,行数和非零元素个数if(Terms>0){intCurrentB=0;//转置三元组表存放指针for(intk=0;k

5、tB].col=smArray[i].row;b.smArray[CurrentB].value=smArray[i].value;CurrentB++;}}returnb;}用三元组表表示的稀疏矩阵及其转置快速转置算法建立辅助数组rowSize和rowStart，记录矩阵转置后各行非零元素个数和各行元素在转置三元组表中开始存放位置。扫描矩阵三元组表，根据某项的列号，确定它转置后的行号，查rowStart表，按查到的位置直接将该项存入转置三元组表中。转置时间代价为O(max(Terms,Cols))。若矩阵有200列，10000个非零元素，总共需要10000次处理。f

6、or(inti=0;iSparseMatrixSparseMatrix::FastTranspos(){int*rowSize=newint[Cols];int*rowStart=newint[Cols];Spa

7、rseMatrixb(Cols,Rows);b.Rows=Cols;b.Cols=Rows;b.Terms=Terms;if(Terms>0){for(inti=0;i