2022年稀疏矩阵的压缩存储 .pdf
稀疏矩阵的压缩存储(1)稀疏矩阵的定义：在矩阵中，多数的元素为0，则称此矩阵为稀疏矩阵三元组类：/定义三元组publicclass Triple int row;/行号int col;/列号doubleval;/元素值/对各项数据进行初始化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;/稀疏矩阵的定义publicclass SparseMatrix 名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 6 页 -privateintrows;/行privateintcols;/列private ArrayList terms;/保存三元组/创建public SparseMatrix(int rows,int cols,ArrayList t)/TODO Auto-generated constructor stubthis.rows=rows;this.cols=cols;terms=t;/输出publicvoid 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(cols,rows,new ArrayList();if(terms.size()=0)/空矩阵名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 6 页 -return t;for(int k=1;k=cols;k+)/列数作为最外层循环的终止条件每次扫描原稀疏矩阵的一列for(int j=0;j转置import java.util.ArrayList;publicclass Matrix publicstaticvoid main(String args)ArrayList list=new ArrayList();/辅助 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);名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 6 页 -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，5SparseMatrix s=new SparseMatrix(6,5,list);System.out.println(未转置之前的矩阵为（只输出非零元素）：);s.output();System.out.println();System.out.println(转置之后的矩阵为（只输出非零元素）：);SparseMatrix ss=s.transpose();ss.output();上述测试稀疏矩阵的转置程序中定义的矩阵的向量cpot 的值以及num 的值：col 1 2 3 4 5 numcol 1 1 4 1 1 cpotcol 1 2 3 7 8(4)1结构定义：ADT SparseMatrix 数据对象：D=aij|i=1,2,m;j=1,2,.,n;aijElemset,m 和 n 分别称为矩阵的行数和列数 数据关系：R=Row,Col Row=|1=i=m,1=j=n-1 Col=|1=i=m-1,1=j=n 基本操作：名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 6 页 -SparseMatrix(int rows,int cols,ArrayList t)操作结果：创建稀疏矩阵output()初始条件：稀疏矩阵已存在操作结果：打印稀疏矩阵transpose()初始条件：稀疏矩阵已存在操作结果：返回稀疏矩阵的转置ADT SparseMatrix 2稀疏矩阵的存储结构的定义：class SparseMatrix privateintrows;/行privateintcols;/列private ArrayList terms;/保存三元组 三元组 Triple：publicclass Triple int row;/行号int col;/列号doubleval;/元素值/对各项数据进行初始化public Triple(int row,int col,double val)名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 6 页 -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)实验结果：名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 6 页 -
