稀疏矩阵的压缩存储

稀疏矩阵的压缩存储 稀疏矩阵的压缩存储 (1) 稀疏矩阵的定义: 在矩阵中，多数的元素为0，则称此矩阵为稀疏矩阵 三元组类: //定义三元组 public class Triple { int row;//行号 int col;//列号 double val;//元素值 //对各项数据进行初始化 public Triple(int row,int col,double val) { this.row=row; this.col=col; this.val=val; } public String toString() {//输出三元组项 return "("+row+","+col+","+val+")"; } (2)用三元组顺序实现稀疏矩阵: (3)其中包括了稀疏矩阵的转置: 注:(2)(3)放到了一块 import java.util.ArrayList; //稀疏矩阵的定义 public class SparseMatrix { private int rows;//行 private int cols;//列 private ArrayList terms;//保存三元组 //创建 public SparseMatrix(int rows,int cols,ArrayList t) { // TODO Auto-generated constructor stub this.rows=rows; this.cols=cols; terms=t; } //输出 public void output() { System.out.println("稀疏矩阵的总行数和总列数分别为:"+rows+","+cols); for(int i=0;i()); if(terms.size()==0)//空矩阵 return t; for(int k=1;k<=cols;k++) {//列数作为最外层循环的终止条件 每次扫描原稀疏 矩阵的一列 for(int j=0;j转置 import java.util.ArrayList; public class Matrix { public static void main(String[] args) { SparseMatrix的构造器 ArrayList list=new ArrayList();//辅助 list.add(new Triple(1,3,3)); list.add(new Triple(1,4,6)); list.add(new Triple(2,3,-9)); list.add(new Triple(3,1,8)); list.add(new Triple(3,3,4)); list.add(new Triple(3,5,6)); list.add(new Triple(4,2,8)); list.add(new Triple(5,3,-3)); //稀疏矩阵行列数分别为6,5 SparseMatrix s=new SparseMatrix(6,5,list); System..println("未转置之前的矩阵为，只输出非零元素，:"); out s.output(); System.out.println(); System.out.println("转置之后的矩阵为，只输出非零元素，:"); SparseMatrix ss=s.transpose(); ss.output(); } } 上述测试稀疏矩阵的转置程序中定义的矩阵的向量cpot的值以及num的值: col 1 2 3 4 5 num[col] 1 1 4 1 1 cpot[col] 1 2 3 7 8 (4)1(结构定义: ADT SparseMatrix{ 数据对象:D={aij | i=1,2,…,m; j=1,2,..,n;aij?Elemset, m和n分别称为矩阵的行数和列数} 数据关系:R={Row,Col} Row={ | 1<=i<=m, 1<=j<=n-1} Col= { | 1<=i<=m-1, 1<=j<=n} 基本操作: SparseMatrix(int rows,int cols,ArrayList t) 操作结果:创建稀疏矩阵 output() 初始条件:稀疏矩阵已存在 操作结果:打印稀疏矩阵 transpose() 初始条件:稀疏矩阵已存在 操作结果:返回稀疏矩阵的转置 }ADT SparseMatrix 2,稀疏矩阵的存储结构的定义: class SparseMatrix { private int rows;//行 private int cols;//列 private ArrayList terms;//保存三元组 } 三元组Triple: public class Triple { int row;//行号 int col;//列号 double val;//元素值 //对各项数据进行初始化 public Triple(int row,int col,double val) { this.row=row; this.col=col; this.val=val; } public String toString() {//输出三元组项 return "("+row+","+col+","+val+")"; } (5)基本操作: SparseMatrix(int rows,int cols,ArrayList t)创建稀疏矩阵 output()打印稀疏矩阵 transpose()返回稀疏矩阵的转置 (6)应用:即为(3)模块:稀疏矩阵的转置 (7)实验结果: