C++数组应用之特殊矩阵的压缩存储

·扫描矩阵三元组表，根据某项的列号，确定它转置后的行号， 查 rowStart 表，按查到的位置直接将该项存入转置三元组表中。

·转置时间代价为O（max（Terms， Cols））。若矩阵有200 列 ，10000个非零元素，总共需要10000次处理。

对应上图的代码在就像前面所列的：

for （ int i = 0 ； i < Cols； i++ ） rowSize[i] = 0；

for （ i = 0； i < Terms； i++ ）

rowSize[smArray[i].col]++；

rowStart[0] = 0 ；

for （ i = 1； i < Cols； i++ ）

rowStart[i] = rowStart[i-1]+rowSize[i-1]；

稀疏矩阵的快速转置

　 template <class Type> SparseMatrix<Type>
SparseMatrix<Type>::FastTranspos ( ) ...{
//对稀疏矩阵a(*this指示)做快速转置，结果放在b中，时间代价 为O(Terms+Columns)。
　　　 int *rowSize = new int[Cols];　//辅助数组，统计各列 非零元素个数
　　　 int *rowStart = new int[Cols];　//辅助数组，预计转 置后各行存放位置
　　　 SparseMatrix<Type> b ( Cols, Rows );　//存放 转置结果
　　　 b.Rows = Cols;　　 b.Cols = Rows;
　　 b.Terms = Terms;
　　　 if ( Terms > 0 ) ...{
　　　　　　　 for (int i = 0; i < Cols; i++) rowSize [i] = 0;　//统计矩阵b中第i行非零元素个数
for ( i = 0; i < Terms; i++ )
//根据矩阵a中第i个非零元素的列号，将rowSize相当该列的计数 加1
　　　　　　　 rowSize[smArray[i].col]++;
rowStart[0] = 0;　//计算矩阵b第i行非零元素的开始存放位置
　　　　　　　　 for ( i = 1; i < Cols; i++ ) 　//rowStart[i]=矩阵b的第i行的开始存放位置
　　　　　　　　　　 rowStart[i] = rowStart[i-1]+rowSize [i-1];
　　　　　　 for ( i = 0; i < Terms; i++ ) ...{　　　　 　 //从a向b传送
　　　　　　　　　　 int j = rowStart[smArray[i].col]; 　//j为第i个非零元素在b中应存放的位置
　　　　　　　　　　 b.smArray[j].row = smArray[i].col;
　　　　　　　　　　 b.smArray[j].col = smArray[i].row;
　　　　　　　　　　 b.smArray[j].value = smArray [i].value;
　　　　　　　　　　 rowStart[smArray[i].col]++;
　　　　　　 }
　　　 }
　　　 delete[ ] rowSize;　　 delete [ ] rowStart;
　　　 return b;
}

在此程序中有4个并列循环，其时间复杂度分别为 O（Cols），O（Terms），O（Cols），和O（Terms），则程序总的时间复杂度为 O（Cols+Terms）。当Terms与Rows*Cols等数量级时，程序的时间复杂度为O （Cols＋Terms）＝O（Rows*Cols）。设Rows=500，Cols＝100，Terms=10000， 则O（500*100）=O（50000）。当Terms远远小于Rows*Cols时，此程序会更省时 间，但程序中需要增加两个体积为Cols的辅助数组。一般Terms总是大于Cols的 ，如果能够大幅度提高速度，这点空间存储上的开销是值得的。

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!