稀疏矩阵的压缩存储.doc_第1页
稀疏矩阵的压缩存储.doc_第2页
稀疏矩阵的压缩存储.doc_第3页
稀疏矩阵的压缩存储.doc_第4页
稀疏矩阵的压缩存储.doc_第5页
已阅读5页,还剩10页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

C+数组应用之特殊矩阵的压缩存储发表日期:2011-09-26 矩阵: 矩阵是数值程序设计中经常用到的数学模型,它是由 m 行和 n 列的数值构成(m=n 时称为方阵)。在用高级语言编制的程序中,通常用二维数组表示矩阵,它使矩阵中的每个元素都可在二维数组中找到相对应的存储位置。然而在数值分析的计算中经常出现一些有下列特性的高阶矩阵,即矩阵中有很多值相同的元或零值元,为了节省存储空间,需要对它们进行压缩存储,即不存或少存这些值相同的元或零值元。 操作: 可以对矩阵作加、减、乘等运算。存储压缩目标:节约存储空间压缩的方法:零元不存储多个值相同的只存一个压缩存储的对象:稀疏矩阵特殊矩阵特殊矩阵:值相同元素或者零元素分布有一定规律的矩阵称为特殊矩阵 例:对称矩阵、 上(下)三角矩阵都是特殊矩阵特殊矩阵压缩存储(以对称矩阵为例)对称矩阵是满足下面条件的n 阶矩阵: aij= aji 1= i,j 0 ) . /非零元个数不为零 int CurrentB = 0; /转置三元组表存放指针for ( int k = 0; k Cols; k+ ) /按列号做扫描,做cols次for ( int i = 0; i Terms; i+ ) /在数组中找列号为k的三元组 if ( smArrayi.col = k) . /第i个三元组中元素的列号为k b.smArrayCurrentB.row = k; /新三元组的行号b.smArrayCurrentB.col=smArrayi.row;/新三元组的列号b.smArrayCurrentB.value=smArrayi.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 for(j=0;jTERMS;J+) 统计,注意这里用到的简洁的算法2 rowstart。用它存放事先计算出来的稀疏矩阵各行非零元素在转置矩阵的三元组表中应存放的位置。rowSize0=0;/计算矩阵b第i行非零元素的开始存放位置for(i=1;iCOLS;I+)ROWSTARTI=ROWSTARTI-1+ROWSIZEI-1快速转置算法的思想? 建立辅助数组 rowSize 和 rowStart,记录矩阵转置后各行非零元素个数和各行元素在转置三元组表中开始存放位置。? 扫描矩阵三元组表,根据某项的列号,确定它转置后的行号,查 rowStart 表,按查到的位置直接将该项存入转置三元组表中。? 转置时间代价为O(max(Terms, Cols)。若矩阵有200 列,10000个非零元素,总共需要10000次处理。对应上图的代码在就像前面所列的:for ( int i = 0; i Cols; i+ ) rowSizei = 0; for ( i = 0; i Terms; i+ )rowSizesmArrayi.col+; rowStart0 = 0; for ( i = 1; i 0 ) .for (int i = 0; i Cols; i+) rowSizei = 0;/统计矩阵b中第i行非零元素个数for ( i = 0; i Terms; i+ )/根据矩阵a中第i个非零元素的列号,将rowSize相当该列的计数加1rowSizesmArrayi.col+; rowStart0 = 0; /计算矩阵b第i行非零元素的开始存放位置for ( i = 1; i Cols; i+ ) /rowStarti=矩阵b的第i行的开始存放位置 rowStarti = rowStarti-1+rowSizei-1;for ( i = 0; i Terms; i+ ) . /从a向b传送 int j = rowStartsmArrayi.col;/j为第i个非零元素在b中应存放的位置 b.smArrayj.row = smArrayi.col;b.smArrayj.col = smArrayi.row;b.smArrayj.value = smArrayi.value;rowStartsmArrayi.col+; delete rowSize; delete rowStart;return b;在此程序中有4个并列循环,其时间复杂度分别为O(Cols),O(Terms),O(Cols),和O(Terms),则程序总的时间复杂度为O(Cols+Terms)。当Terms与Rows*Cols等数量级时,程序的时间复杂度为O(ColsTerms)O(Rows*Cols)。设Rows=500,Cols100,Terms=1

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论