稀疏矩陣的壓縮存儲(chǔ)

1、稀疏矩陣的壓縮存儲(chǔ)(1) 稀疏矩陣的定義：在矩陣中，多數(shù)的元素為0，則稱(chēng)此矩陣為稀疏矩陣三元組類(lèi)：/定義三元組public class Triple int row;/行號(hào)int col;/列號(hào)double val;/元素值/對(duì)各項(xiàng)數(shù)據(jù)進(jìn)行初始化public Triple(int row,int col,double val) this.row=row;this.col=col;this.val=val;public String toString() /輸出三元組項(xiàng)return "("+row+","+col+","+val+&qu

2、ot;)"(2)用三元組順序表實(shí)現(xiàn)稀疏矩陣：(3)其中包括了稀疏矩陣的轉(zhuǎn)置： 注：(2)(3)放到了一塊import/稀疏矩陣的定義public class SparseMatrix private int rows;/行private int cols;/列private ArrayList<Triple> terms;/保存三元組/創(chuàng)建public SparseMatrix(int rows,int cols,ArrayList<Triple> t) / TODO Auto-generated constructor stubthis.rows=rows;

3、this.cols=cols;terms=t;/輸出public void output() System.out.println("稀疏矩陣的總行數(shù)和總列數(shù)分別為："+rows+","+cols);for(int i=0;i<terms.size();i+) System.out.print(terms.get(i);/轉(zhuǎn)置 返回結(jié)果為SparseMatrix型public SparseMatrix transpose() /保存轉(zhuǎn)置后的結(jié)果SparseMatrix t=new SparseMatrix(cols,rows,new ArrayLi

4、st<Triple>();if(terms.size()=0)/空矩陣return t;for(int k=1;k<=cols;k+) /列數(shù)作為最外層循環(huán)的終止條件 每次掃描原稀疏矩陣的一列for(int j=0;j<terms.size();j+) /都取出來(lái)了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;測(cè)試稀疏矩陣的轉(zhuǎn)置：/稀疏矩陣應(yīng)用->轉(zhuǎn)置importpublic cla

5、ss Matrix public static void main(String args) ArrayList<Triple> list=new ArrayList<Triple>();/輔助SparseMatrix的構(gòu)造器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

6、 Triple(4,2,8);list.add(new Triple(5,3,-3);/稀疏矩陣行列數(shù)分別為6，5SparseMatrix s=new SparseMatrix(6,5,list);System.out.println("未轉(zhuǎn)置之前的矩陣為（只輸出非零元素）：");s.output();System.out.println();System.out.println("轉(zhuǎn)置之后的矩陣為（只輸出非零元素）：");SparseMatrix ss=s.transpose();ss.output();上述測(cè)試稀疏矩陣的轉(zhuǎn)置程序中定義的矩陣的向量cp

7、ot的值以及num的值：col12345numcol11411cpotcol12378(4)1結(jié)構(gòu)定義：ADT SparseMatrix 數(shù)據(jù)對(duì)象：D=aij | i=1,2,m; j=1,2,.,n;aijElemset, m和n分別稱(chēng)為矩陣的行數(shù)和列數(shù)       數(shù)據(jù)關(guān)系：R=Row,Col         Row=<ai,j , ai,j+1> | 1<=i<=m, 1<=j<=n-1 Col= <ai,j

8、 , ai+1,j> | 1<=i<=m-1, 1<=j<=n 基本操作： SparseMatrix(int rows,int cols,ArrayList<Triple> t) 操作結(jié)果：創(chuàng)建稀疏矩陣 output() 初始條件：稀疏矩陣已存在 操作結(jié)果：打印稀疏矩陣 transpose() 初始條件：稀疏矩陣已存在 操作結(jié)果：返回稀疏矩陣的轉(zhuǎn)置ADT SparseMatrix 2稀疏矩陣的存儲(chǔ)結(jié)構(gòu)的定義：class SparseMatrix private int rows;/行private int cols;/列private ArrayList<Triple> terms;/保存三元組 三元組Triple：public class Triple int row;/行號(hào)int col;/列號(hào)double val;/元素值/對(duì)各項(xiàng)數(shù)據(jù)進(jìn)行初始化public Triple(int row,int col,double val) this.row=row;this.col=col;this.val=val;public String toString() /輸出三元組項(xiàng)return "("+row+","+col+","+val+")&q