201447 §5.2矩阵的压缩存储 §5.2矩阵的压缩存储 3.对角矩阵 85.2.2稀疏矩阵 ■，定义：设A中有r个非零元素，若t<m×n,称A为 稀琉矩阵。 稀疏因子：6=兰≤05一般非零元素分布无规律性 mXR 总结：这类矩阵压缩存储后能找到地址计算公式， 。:压缩存储： 使其保持随机存取的功能。 只存储非零元，故须存储辅助信息，才能确 定其位置。 D隐提年线.行号列号，非零元的 当用三元组表示非零元时，有两种压缩方式： 顺序和链式。 §5.2矩阵的压缩存储 §5.2矩阵的压缩存储 1.三元组顺序表（三元组表） typedef struct(//3三元组表 以行主序（或列主序）的顺序存储非零元，跳 TripleNode data[MaxSize]: 过零元。得到一个其节点均是三元组的线性表， intm,n,t/行数，列数，非零元总数 称此顺序存储结构为三元组表。 )TripleTable: #define MaxSize 10000 设a,b是TripleTable型变量。 typedef int DataType 0106 [05008 50-20 typedef struct/E元组 10300 030 A-0-2000 000 inti,j月 60000 DataType v: 。转里运算 )TripleNode: An→B 4[门=L[时0≤1≤m-1,0≤j≤m-1 §5.2矩阵的压缩存储 s5.2矩阵的压缩存储 用 ①方法一：按B的次序或按A的列序转置。 800 ,A的列是B的行，故按A的列序转置，所得B是按 行主序存放的。 基本思想：对A中每列，从头至尾扫描a.data,找出 所有列号为co的三元组(0scos-1),将它们的行、 列号互换后依次放入b.data,即可得行主序表示的B 2 的三元组。 2 √正确性：按A的列号递增序转置，保证B按行号增 序排列，B中同一行号的三元组，扫描A时所得三元 组G,eo,》,(,eol,v2必有，转置后保证按B的列 号增序排列。 √例，上图。 MaxSize-l 32014/4/7 3 §5.2 矩阵的压缩存储 3. 对角矩阵 总结：这类矩阵压缩存储后能找到地址计算公式 13 ， 使其保持随机存取的功能。 §5.2 矩阵的压缩存储 § 5.2.2 稀疏矩阵  定义：设Amn中有t个非零元素，若 ，称A为 稀疏矩阵。  稀疏因子： 一般非零元素分布无规律性  压缩存储： 14 只存储非零元，故须存储辅助信息，才能确 定其位置。 三元组(i，j，aij)：（行号，列号，非零元的 值）唯一确定一个非零元。 当用三元组表示非零元时，有两种压缩方式： 顺序和链式。 §5.2 矩阵的压缩存储 1. 三元组顺序表（三元组表） 以行主序（或列主序）的顺序存储非零元，跳 过零元。得到一个其节点均是三元组的线性表， 称此顺序存储结构为三元组表。 #define MaxSize 10000 15 typedef int DataType typedef struct{//三元组 int i, j； DataType v; }TripleNode; §5.2 矩阵的压缩存储 typedef struct{//三元组表 TripleNode data[MaxSize]; int m, n, t; //行数，列数，非零元总数 }TripleTable; 设a，b是TripleTable型变量。 16  转置运算 §5.2 矩阵的压缩存储 17 §5.2 矩阵的压缩存储 ① 方法一：按B的次序或按A的列序转置。 ∵A的列是B的行，故按A的列序转置，所得B是按 行主序存放的。  基本思想：对A中每列，从头至尾扫描a.data，找出 所有列号为col的三元组(0≤col≤n-1)，将它们的行、 列号互换后依次放入b.data，即可得行主序表示的B 18 列号互换后依次放入 的三元组。  正确性：∵按A的列号递增序转置，保证B按行号增 序排列，B中同一行号的三元组，扫描A时所得三元 组 必有i<j，转置后保证按B的列 号增序排列。  例，上图