稀疏矩阵的压缩存储

1、稀疏矩阵的压缩存储(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+&qu

2、ot;)"(2)用三元组顺序表实现稀疏矩阵：(3)其中包括了稀疏矩阵的转置： 注：(2)(3)放到了一块import java.util.ArrayList;/稀疏矩阵的定义public class SparseMatrix private int rows;/行private int cols;/列private ArrayList<Triple> terms;/保存三元组/创建public SparseMatrix(int rows,int cols,ArrayList<Triple> t) / TODO Auto-generated constructo

3、r stubthis.rows=rows;this.cols=cols;terms=t;/输出public void output() System.out.println("稀疏矩阵的总行数和总列数分别为："+rows+","+cols);for(int i=0;i<terms.size();i+) System.out.print(terms.get(i);/转置 返回结果为SparseMatrix型public SparseMatrix transpose() /保存转置后的结果SparseMatrix t=new SparseMatrix(

4、cols,rows,new ArrayList<Triple>();if(terms.size()=0)/空矩阵return t;for(int k=1;k<=cols;k+) /列数作为最外层循环的终止条件 每次扫描原稀疏矩阵的一列for(int j=0;j<terms.size();j+) /都取出来了Triple x=(Triple)terms.get(j);if(x.col=k)/如果x是第k列的元素t.terms.add(new Triple(k,x.row,x.val);/行列互换 值不变/if/forreturn t;测试稀疏矩阵的转置：/稀疏矩阵应用-&

5、gt;转置import java.util.ArrayList;public class Matrix public static void main(String args) ArrayList<Triple> list=new ArrayList<Triple>();/辅助SparseMatrix的构造器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,

6、4);list.add(new Triple(3,5,6);list.add(new Triple(4,2,8);list.add(new Triple(5,3,-3);/稀疏矩阵行列数分别为6，5SparseMatrix s=new SparseMatrix(6,5,list);System.out.println("未转置之前的矩阵为（只输出非零元素）：");s.output();System.out.println();System.out.println("转置之后的矩阵为（只输出非零元素）：");SparseMatrix ss=s.transp

7、ose();ss.output();上述测试稀疏矩阵的转置程序中定义的矩阵的向量cpot的值以及num的值：col12345numcol11411cpotcol12378(4)1结构定义：ADT SparseMatrix 数据对象：D=aij | i=1,2,m; j=1,2,.,n;aijElemset, m和n分别称为矩阵的行数和列数       数据关系：R=Row,Col         Row=<ai,j , ai,j+1> | 1&

8、lt;=i<=m, 1<=j<=n-1 Col= <ai,j , ai+1,j> | 1<=i<=m-1, 1<=j<=n 基本操作： SparseMatrix(int rows,int cols,ArrayList<Triple> t) 操作结果：创建稀疏矩阵 output() 初始条件：稀疏矩阵已存在 操作结果：打印稀疏矩阵 transpose() 初始条件：稀疏矩阵已存在 操作结果：返回稀疏矩阵的转置ADT SparseMatrix 2稀疏矩阵的存储结构的定义：class SparseMatrix private int

9、rows;/行private int cols;/列private ArrayList<Triple> 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+")