十字链表8稀疏矩阵的压缩存储数据结构Java语言描述.PPT

1) 尽可能少存或不存零值元素； 解决问题的原则: 2) 尽可能减少没有实际意义的运算； 3) 操作方便。 即：能尽可能快地找到与下标值(i，j) 对应的元素，能尽可能快地找到同一 行或同一列的非零值元。 4.8 稀疏矩阵的压缩存储 稀疏矩阵的压缩存储方法: 1、三元组顺序表 2、 十字链表 4.8 稀疏矩阵的压缩存储 0 1 14 0 4 -5 1 1 -7 2 0 36 2 3 28 row column value 3 5 5 data rows cols nums M= M 4.8.1 稀疏矩阵的三元组表存储—定义 class TripleNode { } 三元组顺序表存储结构描述： 4.8.1 稀疏矩阵的三元组表存储—定义 public int row; //行号 public int column; //列号 public int value; //元素值 …… 三元组表中的结点类 （见教材） public class SparseMatrix { } 三元组顺序表存储结构描述： 4.8.1 稀疏矩阵的三元组表存储—定义 public TripleNode data[]; //三元组表 public int rows; //行数 public int cols; //列数 public int nums; //非零元素个数 …… 稀疏矩阵三元组顺序表类（见教材） 4.8.1 稀疏矩阵的三元组表存储—基本操作 1. 初始化三元组顺序表操作 （算法 4.9) 1）操作要求： 按行序优先的原则依次扫描已知稀疏矩阵的所有元素，并把非零元素插入到三元组顺序表中。 2）操作方法： 根据已知的一个稀疏矩阵mat（二维数组），构造一个与其对应的三元组顺序表。 a.统计出稀疏矩阵mat中非零元素的个数 (只要按行优先的顺序对mat扫描一遍即可完成） 3）算法步骤： for(i=0; imat.length; i++) { } for(j=0; jmat[i].length; j++){ } if( mat[i][j]!=0 ) count++; b.完成对rows,cols,nums的赋值 rows= mat.length; //行数 cols=mat[0].length; //列数 nums=count; //非零元素的个数 1. 初始化三元组顺序表操作 （算法 4.9) 3）算法步骤： d.将mat中的非零元素依次存放到三元组 顺序表中（即建立三元组表）。 for(i=0; imat.length; i++) { } for(j=0; jmat[i].length; j++){ } if( mat[i][j]!=0 ) data[k]=new TripleNode(i,j,mat[i][j]); k++; c.申请三元组顺序表的存储空间 data=new TripleNode[nums]; 1. 初始化三元组顺序表操作 （算法 4.9) 4）算法：(算法4.9) public SparseMatrix (int mat[ ][ ]) { int i,j,k=0,count=0; } //算法4.9结束 for(i=0; imat.length; i++) { //统计非零元素的个数 } for(j=0; jmat[i].length; j++){ } if( mat[i][j]!=0 ) count++; rows= mat.length; //行数 cols=mat[0].length; //列数 nums=count; //非零元素的个数 data=new TripleNode[nums]; //申请空间 for(i