已阅读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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026-2027学年江苏南通海安高级中学高二上10月月考化学试卷含答案
- 2025选调生考试申论刷题宝典及答案
- 2025理财规划师理财规划基础考前模拟及答案
- 2025基金从业资格证券投资基金基础知识能力提升题及答案
- 2025初级统计师统计实务真题演练题及答案
- 2025一级建造师建设工程法规及相关知识全科综合及答案
- 2026年徐州市中考道德与法治试卷(含答案)
- 通知财务预算调整事项函5篇范本
- 城市更新项目延期风险管理指南
- 化工设备安全维护规程
- 北京2026年11月小学五年级数学期中试卷及答案
- 中国中煤能源集团有限公司2027届秋季校园招聘笔试备考试题及答案解析
- 人教版八年级英语上册Unit1-Unit 8语法知识点+练习题(含答案)
- 《盘活存量土地和低效用地典型案例2026版》
- 医务人员手卫生规范(WS-T313-2019)
- 2026年特种设备安全管理人员(A证)考试练习题库(附答案)
- 2026年安全阀校验作业全真模拟题库及答案
- 2027年江苏省高职单招职业技能考试题库附完整答案详解(考点梳理)
- 减轻外周静脉补钾疼痛方法总结2026
- 中国石油天然气股份有限公司辽宁盘锦销售分公司大洼新开加油站项目水土保持方案报告表
- 《新能源专业导论》新能源相关专业全套教学课件
评论
0/150
提交评论