稀疏矩阵的压缩存储

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

1、C++数组应用之特殊矩阵的压缩存储发表日期：2011-09-26矩阵:矩阵是数值程序设计中经常用到的数学模型，它是由m行和n列的数值构成（m=n时称为方阵）。在用高级语言编制的程序中，通常用二维数组表示矩阵，它使矩阵中的每个元素都可在二维数组中找到相对应的存储位置。然而在数值分析的计算中经常出现一些有下列特性的高阶矩阵，即矩阵中有很多值相同的元或零值元，为了节省存储空间，需要对它们进行"压缩存储"，即不存或少存这些值相同的元或零值元。操作：可以对矩阵作加、减、乘等运算。存储压缩目标：节约存储空间压缩的方法：零元不存储多个值相同的只存一个压缩存储的对象：稀疏矩阵特殊矩阵

2、特殊矩阵：值相同元素或者零元素分布有一定规律的矩阵称为特殊矩阵例:对称矩阵、上（下）三角矩阵都是特殊矩阵特殊矩阵压缩存储(以对称矩阵为例)对称矩阵是满足下面条件的n阶矩阵:aij=aji1<=i,j<=nk=0123456n(n+1)/2-1对称矩阵元素可以只存储下三角部分，共需n(n+1)/2个单元的空间(三角矩阵的存储方式类似）以一维数组sa[0..n(n+1)/2-1]作为n阶对称矩阵A的存储结构A中任意一元素aij与它的存储位置sa[k]之间关系：k=0123456n(n+1)/2-1例如：a42在sa[]中的存储位置是：k=4*(4+1)/2+2=12sa[

3、12]=a42带状矩阵所有非0元素都集中在以主对角线为中心的带状区域，半带宽为d时,非0元素有(2d+1)*n-(1+d)*d个（左上角与右下角补上0后，最后必须减掉），如下图所示：为计算方便，认为每一行都有2d+1个非0元素，若少则0补足存放矩阵的数组sa[]有:n(2d+1)个元素数组，元素sa[k]与矩阵元素aij之间有关系:k=i*(2d+1)+d+(j-i)（第一项i*(2d+1)表示前i行一共有几个元素，d+(j-i)这一项是用来确定第i行中，第j列前有几个元素，以i=j时，这时j-i=0，这个作为“分水岭“，左右两边的元素分别加上偏移量d。）本例：d=1

4、K=01234567891011121314（a0前以及a14处放一个0是用来表示在矩阵的左上角及右下角补上的0）稀疏矩阵：行数m=6,列数n=7,非零元素个数t=6稀疏矩阵(SparseMatrix)的抽象数据类型templateclassSparseMatrix...{intRows,Cols,Terms;//行/列/非零元素数TrituplesmArray[MaxTerms];public://三元组表SparseMatrix(intMaxRow,intMaxcol);SparseMatrixTranspose();//转置SparseMatrix//相加Add

5、(SparseMatrixb);SparseMatrix//相乘Multiply(SparseMatrixb);}A的三元组顺序表图示三元组(Trituple)类的定义templateclassSparseMatrix;templateclassTrituple...{friendclassSparseMatrixprivate:introw,col;//非零元素所在行号/列号Typevalue;//非零元素的值}稀疏矩阵转置矩阵用三元组表表示的稀疏矩阵及其转置：a.smArrayb.smArray（a.Rows=6,a.Cols=7,a.Terms=8）（b.Row

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

7、的内容，连同value中存储的值，作为新三元组存放到矩阵的三元组表中。当n次扫描完成时，算法结束。程序清单如下：稀疏矩阵的转置templateSparseMatrixSparseMatrix::Transpose()...{//将稀疏矩阵a(*this指示)转置，结果在稀疏矩阵b中。SparseMatrixb(Cols,Rows);//创建一个稀疏矩阵类的对象bb.Rows=Cols;b.Cols=Rows;//交换其row（行号）与col（列号）的内容，连同valueb.Terms=Terms;//中存储的值作为新三元组放到矩阵的三元组表中。if(