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

稀疏矩 阵转置算法思想

对应上图的一个最简单的方法是把三元组表中的row与 col的内容互换，然后再按照新的row中的行号对各三元组从小到大重新排序，最 后得到上图右半部分的三元组表，但是用这样的方法其时间复杂度为平方级的， 下面再用一种方法来处理：假设稀疏矩阵A有n列，相应地，需要针对它的三元组 表中的col列进行n次扫描，第k次扫描是在数组的col列中查找列号为k的三元组 ，若找到，则意味着这个三元组所表示的矩阵元素在稀疏矩阵的第k列，需要把 它存放到转置矩阵的第k行。具体办法是：取出这个三元组，并交换其row（行号 ）与col（列号）的内容，连同value中存储的值，作为新三元组存放到矩阵的三 元组表中。当n次扫描完成时，算法结束。程序清单如下：

稀疏矩阵的转 置

　template <class Type> SparseMatrix <Type> SparseMatrix <Type>:: Transpose ( ) ...{
//将稀疏矩阵a(*this指示)转置，结果在稀疏矩阵b中。
　　 SparseMatrix<Type> b ( Cols, Rows );　//创建一 个稀疏矩阵类的对象b
　　　　 b.Rows = Cols; b.Cols = Rows;　//交换其row（行号 ）与col（列号）的内容，连同value
b.Terms = Terms;　//中存储的值作为新三元组放到矩阵的三元组 表中。
　　　　 if ( Terms > 0 ) ...{ //非零元个数不为零
　　　　　　　　 int CurrentB = 0;　//转置三元组表存放指针
for ( int k = 0; k < Cols; k++ )　//按列号做扫描，做 cols次
　　　　　　　　 for ( int i = 0; i < Terms; i++ )　// 在数组中找列号为k的三元组
　　　　　　　　　　　　　　　　 if ( smArray[i].col == k) ...{ //第i个三元组中元素的列号为k
　　　　　　　　　　　　　　　　　 b.smArray[CurrentB].row = k;　//新三元组的行号
　　　　　　　　　　　　　　　　　 b.smArray [CurrentB].col=smArray[i].row;　//新三元组的列号
　　　　　　　　　　　　　　　　　 b.smArray [CurrentB].value=smArray[i].value;　//新三元组的值
　　　　　　　　　　　　　　　　 CurrentB++;　//存放指针加 1
　　　　　　　　　　　　　　 }
　　　　 }
　　　　 return 0;
　}

若设稀疏矩阵的行数为Rows，列数为Cols，非 零元素个数为Terms，则最坏情况下的时间复杂度主要取决于二重潜套for循环内 的if语句，if语句在二重循环的作用下总的执行次数为O（Cols*Terms）。而在 if控制内的赋值语句则执行了Terms次，它取决于三元组表本身的长度。若非零 元素个数Terms与矩阵行，列数的乘积Rows*Cols等数量级，则上述程序清单的时 间复杂度为O（Cols*Terms）＝O（Rows*Cols*Cols）。设Rows=500，Cols=100， Terms=10000，则O（500*100*100）=O（5000 000），处理效率极低。

为 了提高转置效率，采用一种快速转置的方法。在此方法中，引入两个辅助数组：

1. rowSize[].用它存放事先统计出来的稀疏矩阵各列的非零元素个数， 转置以后是转置矩阵各行的非零元素个数。具体做法是：先把这个数组清零，然 后扫描矩阵A的三元组表，逐个取出三元组的列号col，把以此列号为下标的辅助 数组元素的值累加1.

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

for（j=0；j<Terms；j++） rowSize[smArray[j].col]++；// 统计，注意这里用到的简洁的算法

2. rowstart[].用它存放事先计算出 来的稀疏矩阵各行非零元素在转置矩阵的三元组表中应存放的位置。

rowSize[0]=0；//计算矩阵b第i行非零元素的开始存放位置

for （i=1；i<Cols；i++）rowStart[i]=rowStart[i-1]+rowSize[i-1]

快 速转置算法的思想

·建立辅助数组 rowSize 和 rowStart，

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