




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、 稀疏矩阵的压缩存储稀疏矩阵的压缩存储 三元组表三元组表一、什么是稀疏矩阵一、什么是稀疏矩阵(sparse matrix) 如果矩阵如果矩阵M中的大多数元素均中的大多数元素均为零元素,则称矩阵为零元素,则称矩阵M为稀疏矩阵。为稀疏矩阵。 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 015 0 0 -7 0 0 0M=例如:例如:一、什么是稀疏矩阵一、什么是稀疏矩阵(sparse matrix) 如果矩阵如果矩阵M中的大多数元素均中的大多数元素均为零元素,则称矩阵为零元素,则称矩阵M为稀疏矩阵。为
2、稀疏矩阵。 用一个三元组(用一个三元组(tupel3)存放矩阵中的存放矩阵中的一个非零元素的行号、列号及一个非零元素的行号、列号及该该非零元素非零元素的值。的值。 一个三元组的形式为:(一个三元组的形式为:(i , j, e) 一般情况下,一个稀疏矩阵中有若干个一般情况下,一个稀疏矩阵中有若干个非零元素,所以要用一个非零元素,所以要用一个“三元组线性表三元组线性表”来存放一个稀疏矩阵。来存放一个稀疏矩阵。1.中心思想:仅存储矩阵中的非零元素中心思想:仅存储矩阵中的非零元素2.用顺序存储结构存放三元组线性表用顺序存储结构存放三元组线性表M=原矩阵原矩阵:存放形式存放形式: (按行顺序存放)(按行
3、顺序存放)data p i j edata 1 1 2 12data 2 1 3 9data 3 3 1 -3data 4 3 6 14data 5 4 3 24data 6 5 2 18data 7 6 1 15data 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 015 0 0 -7 0 0 0mu=6 nu=7 tu=8注意:注意:为了保存矩阵的行数、列为了保存矩阵的行数、列数和非零元素个数,还需数和非零元素个数,还需增设三个量:增设三个量:mu nu tu3.三元组线性
4、表的数据类型描述三元组线性表的数据类型描述#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
5、 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 i ,j ,e 时的格式应为:时的格式应为: a .data p .ia .data p .i a .data p .ja .data p .j a .data p . a .data p .e e例如例如 x x= =a adata6.jdata6.j 则则 x=2x=2三、实现矩阵的运算三、实现矩
6、阵的运算:矩阵转置矩阵转置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 015 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分
7、别存放矩阵分别存放矩阵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
8、 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 1
9、8 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 求得求得1Col=1注注:p=1:8,寻找寻找 j=col 的的a.data p1 1 3 -3 1 6 152.求解步骤分析:求解步骤分析: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
10、 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 求得求得22注注:p=1:8,寻找寻找 j=col 的的a.data pCol=2 2 1 12 2 5 182.求解步骤分析:求解步骤分析:p=1
11、: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
12、 b .data 8 求得求得33Col=3注注:p=1:8,寻找寻找 j=col 的的a.data p 3 1 9 3 4 242.求解步骤分析:求解步骤分析: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
13、 -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 p4 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
14、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
15、.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
16、求得求得Col=6注注:p=1:8,寻找寻找 j=col 的的a.data p6 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
17、 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
18、 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=83.算法描述算法描述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 ; col= a.nu ; + + col) for (p= 1 ; p= a.tu
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 建筑工程安全管理措施方案
- 交通运输安全生产强化年实施方案
- 火灾事故责任认定标准
- 社区居委会2025年工作总结
- 收费站安全生产开展情况
- 甘肃省庆阳长庆中学2025年物理高二第二学期期末经典试题含解析
- 2025届福建省罗源一中高一物理第二学期期末学业水平测试试题含解析
- 绩效管理员岗位面试问题及答案
- 调酒师岗位面试问题及答案
- 关于员工福利申请书范文
- 改进维持性血液透析患者贫血状况PDCA
- 公司岗位职级管理制度
- 漏肩风(肩周炎)中医临床路径及入院标准2020版
- 光面爆破知识讲座课件
- 高铁站装饰装修方案
- DB4401-T 112.1-2021 城市道路占道施工交通组织和安全措施设置+第1部分:交通安全设施设置-(高清现行)
- 质量整改通知单(样板)
- 杭州市高级中学2022年高一新生素质测试(分班考)模拟试卷
- 《碳纤维片材加固混凝土结构技术规程》(2022年版)
- 智能建筑项目设计方案(模板)
- 短视频:策划+拍摄+制作+运营课件(完整版)
评论
0/150
提交评论