已阅读5页,还剩16页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
稀疏矩阵的压缩存储 三元组表,一、什么是稀疏矩阵(sparse matrix),如果矩阵M中的大多数元素均为零元素,则称矩阵M为稀疏矩阵 。一般地,当非零元素个数只占矩阵元素总数的25%30%,或低于这个百分数时,我们称这样的矩阵为稀疏矩阵。,0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 -7 0 0 0,M=,例如:,一、什么是稀疏矩阵(sparse matrix),如果矩阵M中的大多数元素均为零元素,则称矩阵M为稀疏矩阵。,用一个三元组(tupel3)存放矩阵中的一个非零元素的行号、列号及该非零元素的值。 一个三元组的形式为:(i , j, e),二、三元组线性表存储结构,一般情况下,一个稀疏矩阵中有若干个非零元素,所以要用一个“三元组线性表”来存放一个稀疏矩阵。,1.中心思想:仅存储矩阵中的非零元素,2.用顺序存储结构存放三元组线性表,M=,原矩阵:,存放形式: (按行顺序存放),data p i j e data 1 1 2 12 data 2 1 3 9 data 3 3 1 -3 data 4 3 6 14 data 5 4 3 24 data 6 5 2 18 data 7 6 1 15 data 8 6 4 -7,0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 -7 0 0 0,mu=6 nu=7 tu=8,注意: 为了保存矩阵的行数、列数和非零元素个数,还需增设三个量:mu nu tu,3.三元组线性表的数据类型描述,#define MAXSIZE 12500 /非零元素个数的最大值 typedef struct int i, j; ElemType e; Triple;,typedef struct Triple data MAXSIZE+1; /三元组表,data0不用 int mu , nu , tu ; /矩阵的行数、列数、非0元素个数 TSMatrix /sparseness(稀疏),TSMatrix M ;,用变量 a 存放矩阵 M 的形式如下:,a . data p i j e a .data 1 1 2 12 a .data 2 1 3 9 a .data 3 3 1 -3 a .data 4 3 6 14 a .data 5 4 3 24 a .data 6 5 2 18 a .data 7 6 1 15 a .data 8 6 4 -7 a. mu=6 a. nu=7 a. tu=8,注意: 引用i ,j ,e 时的格式应为: a .data p .i a .data p .j a .data p .e 例如 x=adata6.j 则 x=2,三、实现矩阵的运算:矩阵转置,1.实例:求矩阵M的转置矩阵N:,三、实现矩阵的运算:矩阵转置,1.实例:求矩阵M的转置矩阵N:,0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 -7 0 0 0,M=,0 0 -3 0 0 15 12 0 0 0 18 0 9 0 0 24 0 0 0 0 0 0 0 -7 0 0 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0,N=,求解,注意:用变量a和 b分别存放矩阵M和N (TSMatrix a, TSMatrix b),即要从已知变量a来求得变量b的值。,也既要完成如下求解工作:,a . data p i j e a .data 1 1 2 12 a .data 2 1 3 9 a .data 3 3 1 -3 a .data 4 3 6 14 a .data 5 4 3 24 a .data 6 5 2 18 a .data 7 6 1 15 a .data 8 6 4 -7 a. mu=6 a. nu=7 a. tu=8,b . data q i j e b .data 1 1 3 -3 b .data 2 1 6 15 b .data 3 2 1 12 b .data 4 2 5 18 b .data 5 3 1 9 b .data 6 3 4 24 b .data 7 4 6 -7 b .data 8 6 3 14 b. mu=7 b. nu=6 b. tu=8,求解,2.求解步骤分析:p=1:8, q的值=1,2,a . data p i j e a .data 1 1 2 12 a .data 2 1 3 9 a .data 3 3 -3 a .data 4 3 6 14 a .data 5 4 3 24 a .data 6 5 2 18 a .data 7 6 15 a .data 8 6 4 -7 a. mu=6 a. nu=7 a. tu=8,b . data q i j e b .data 1 b .data 2 b .data 3 b .data 4 b .data 5 b .data 6 b .data 7 b .data 8,求得,1,Col=1,注:p=1:8,寻找 j=col 的a.data p,1,1 3 -3,1 6 15,2.求解步骤分析:p=1:8, q的值=3,4,a . data p i j e a .data 1 1 12 a .data 2 1 3 9 a .data 3 3 1 -3 a .data 4 3 6 14 a .data 5 4 3 24 a .data 6 5 18 a .data 7 6 1 15 a .data 8 6 4 -7 a. mu=6 a. nu=7 a. tu=8,b . data q i j e b .data 1 1 3 -3 b .data 2 1 6 15 b .data 3 b .data 4 b .data 5 b .data 6 b .data 7 b .data 8,求得,2,2,注:p=1:8,寻找 j=col 的a.data p,Col=2,2 1 12,2 5 18,2.求解步骤分析:p=1:8, q的值=5,6,a . data p i j e a .data 1 1 2 12 a .data 2 1 9 a .data 3 3 1 -3 a .data 4 3 6 14 a .data 5 4 24 a .data 6 5 2 18 a .data 7 6 1 15 a .data 8 6 4 -7 a. mu=6 a. nu=7 a. tu=8,b . data q i j e b .data 1 1 3 -3 b .data 2 1 6 15 b .data 3 2 1 12 b .data 4 2 5 18 b .data 5 b .data 6 b .data 7 b .data 8,求得,3,3,Col=3,注:p=1:8,寻找 j=col 的a.data p,3 1 9,3 4 24,2.求解步骤分析:p=1:8, q的值=7,a . data p i j e a .data 1 1 2 12 a .data 2 1 3 9 a .data 3 3 1 -3 a .data 4 3 6 14 a .data 5 4 3 24 a .data 6 5 2 18 a .data 7 6 1 15 a .data 8 6 -7 a. mu=6 a. nu=7 a. tu=8,b . data q i j e b .data 1 1 3 -3 b .data 2 1 6 15 b .data 3 2 1 12 b .data 4 2 5 18 b .data 5 3 1 9 b .data 6 3 4 24 b .data 7 b .data 8,求得,Col=4,注:p=1:8,寻找 j=col 的a.data p,4,4 6 -7,2.求解步骤分析:p=1:8, q的值=7,a . data p i j e a .data 1 1 2 12 a .data 2 1 3 9 a .data 3 3 1 -3 a .data 4 3 6 14 a .data 5 4 3 24 a .data 6 5 2 18 a .data 7 6 1 15 a .data 8 6 4 -7 a. mu=6 a. nu=7 a. tu=8,b . data q i j e b .data 1 1 3 -3 b .data 2 1 6 15 b .data 3 2 1 12 b .data 4 2 5 18 b .data 5 3 1 9 b .data 6 3 4 24 b .data 7 4 6 -7 b .data 8,求得,Col=5,注:p=1:8,寻找 j=col 的a.data p,无!,2.求解步骤分析:p=1:8, q的值=8,a . data p i j e a .data 1 1 2 12 a .data 2 1 3 9 a .data 3 3 1 -3 a .data 4 3 14 a .data 5 4 3 24 a .data 6 5 2 18 a .data 7 6 1 15 a .data 8 6 4 -7 a. mu=6 a. nu=7 a. tu=8,b . data q i j e b .data 1 1 3 -3 b .data 2 1 6 15 b .data 3 2 1 12 b .data 4 2 5 18 b .data 5 3 1 9 b .data 6 3 4 24 b .data 7 4 6 -7 b .data 8,求得,Col=6,注:p=1:8,寻找 j=col 的a.data p,6,6 3 14,2.求解步骤分析:p=1:8, q的值=8,a . data p i j e a .data 1 1 2 12 a .data 2 1 3 9 a .data 3 3 1 -3 a .data 4 3 6 14 a .data 5 4 3 24 a .data 6 5 2 18 a .data 7 6 1 15 a .data 8 6 4 -7 a. mu=6 a. nu=7 a. tu=8,b . data q i j e b .data 1 1 3 -3 b .data 2 1 6 15 b .data 3 2 1 12 b .data 4 2 5 18 b .data 5 3 1 9 b .data 6 3 4 24 b .data 7 4 6 -7 b .data 8 6 3 14,求得,Col=7,注:p=1:8,寻找 j=col 的a.data p,无!,2.求解步骤分析:,a . data p i j e a .data 1 1 2 12 a .data 2 1 3 9 a .data 3 3 1 -3 a .data 4 3 6 14 a .data 5 4 3 24 a .data 6 5 2 18 a .data 7 6 1 15 a .data 8 6 4 -7 a. mu=6 a. nu=7 a. tu=8,b . data q i j e b .data 1 1 3 -3 b .data 2 1 6 15 b .data 3 2 1 12 b .data 4 2 5 18 b .data 5 3 1 9 b .data 6 3 4 24 b .data 7 4 6 -7 b .data 8 6 3 14,求得,b. Mu=7 b.nu=6 b.tu=8,3.算法描述,status TransposeSMatrix(TSMatrix a, TSMatrix *b) (*b).mu=a.nu; (*b).nu=a.mu; (*b).tu=a.tu; if (*b).tu) q= 1; for (col
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 4-trans-Hydroxy-glibenclamide-d5-生命科学试剂-MCE
- 2024年吉林省长春市中考一模英语试题
- 业主公约中物业管理服务费用与住宅公共维修基金参考模板全套
- 研发部管理制度
- 紧急抢救用血应急预案演练脚本
- 中考复习阅读材料的文本剖析
- 消防安全教育教案
- 冷热循环的模具注塑技术
- 车辆定点维修询价函
- 【信息技术】开发网络聊天系统 课件 2023-2024学年人教-+中图版(2019)高中信息技术必修2
- 2024年土地及房屋租赁合同简单版(2篇)
- 内蒙古新街台格庙矿区新街一井及选煤厂新建项目环境影响报告书
- 2024年高考语文备考之名校模考题汇编(9):语言文字运用
- 进企业宣讲民法典
- 你好,无废校园主题班会
- 初中物理人教版八年级下册 第1节杠杆2 课件
- 《软件开发费用测算规范》标准文本(征求意见稿)
- .患者发生输液反应时的应急预案、流程
- 新生儿围手术期护理.ppt
- 《辅行诀》范志良1965年抄本
- 虹吸原理(修改版)PPT课件.ppt
评论
0/150
提交评论