关于稀疏矩阵的压缩存储与基本运算
对于基本类型数组，比如int数组，如果new了之后没有显式的初始化，数组中的元素值将自动初始化为0，如果是float数组值为0.0，
而对于对象数组将被初始化为null。
稀疏矩阵可以说是存在较多的0(int数组)或null值(对象数组)，手动化初始的值较少的二维数组
(或多阶数组)，稀疏矩阵的压缩存储是为了节省空间而对这类矩阵进行压缩存储。
所谓的压缩存储是：为多个相同的值分配一个存储空间，为null或0不分配空间。
前者只能是对特殊矩阵(比如对称矩阵或特殊矩阵)的压缩，这里只讨论的是后者。
直接上代码，注释完善

import java.util.Arrays;/** * 关于稀疏矩阵的压缩存储与基本运算 * 压缩存储只存储矩阵的非空元素 * 数组索引都是从0开始 */public class MatrixDemo<E> {public static void main(String[] args) {MatrixDemo<Integer> md = new MatrixDemo<Integer>();Integer[][] M = new Integer[6][7];M[0][1] = 12; M[0][2] = 9;M[2][0] = -3; M[2][5] = 14;M[3][2] = 24; M[4][1] = 18;M[5][0] = 15; M[5][3] = -7;    //md.compreMatrix(M);        Integer[][] m = new Integer[3][4];    m[0][0]=3;m[0][3]=5;    m[1][1]=-1;m[2][0]=2;    Integer[][] n = new Integer[4][2];    n[0][0]=5;n[0][1]=2;  n[1][0]=1;    n[2][0]=-2; n[2][1]=4;    md.multiMatrix(m, n);    System.out.println();    md.multiMatrix(md.compreMatrix(m), md.compreMatrix(n));}/** * 把稀疏矩阵进行压缩 */public Matrix compreMatrix(E[][] e){Matrix matrix = new Matrix();int mu = e.length;int nu = e[0].length;for(int i=0;i<mu;i++){for(int j=0;j<nu;j++){if(e[i][j] != null){//压缩非空元素Triple<E> triple = new Triple<E>(i,j,e[i][j]);matrix.add(triple);}}}matrix.mu = mu;matrix.nu = nu;//下面是查看元素for(int i=0;i<matrix.tu;i++){Triple<E> t = matrix.data[i];System.out.print(t.i + " " + t.j + " " + t.e);System.out.println();}System.out.println("----------");//transMatrix(matrix);//transMatrix2(matrix);return matrix;}/** * 压缩矩阵的转置，方法一 * 原理：1.将矩阵的行列对应的值相互交换 *  2.将矩阵的行列下标交换 *  3.重新排列新矩阵的顺序(按行排，即行中非空元素出现的次序) */public Matrix transMatrix(Matrix m){Matrix t = new Matrix();//转置后的矩阵t.mu = m.nu;t.nu = m.mu;if(m.tu == 0) return null;for(int col=0; col<m.nu;col++){//根据m的列的顺序排列转换矩阵的顺序for(int p=0;p<m.tu;p++){if(m.data[p].j == col){Triple<E> triple = new Triple<E>(m.data[p].j, m.data[p].i, (E)m.data[p].e);t.add(triple);}}}System.out.println("矩阵置换方法一");for(int i=0;i<t.tu;i++){Triple<E> tr = t.data[i];System.out.print(tr.i + " " + tr.j + " " + tr.e);System.out.println();}return t;}/** * 压缩矩阵的转置，方法二 * 原理：欲求得转置后的矩阵t的顺序，可以先求得m的每一列的第一个非空元素在 * t中的索引cpot[col]，并确定m每一列中的非空元素的个数num[col] * 公式很容易得到：1.cpot[0] = 0; *    2.cpot[col] = cpot[col - 1]+ num[col-1] (1<col<m.nu) */public Matrix transMatrix2(Matrix m){Matrix t = new Matrix();//转置后的矩阵t.mu = m.nu;t.nu = m.mu;//num和cpot数组的初始化int[] num = new int[m.nu];for(int ti=0;ti<m.tu;ti++){//num初始化num[m.data[ti].j]++;}int[] cpot = new int[m.nu];cpot[0] = 0;//求第col列中第一个非空元素在t中的位置for(int col=1;col<m.nu;col++){//cpot初始化cpot[col] = cpot[col-1] + num[col - 1];}//进行转换for(int p=0;p<m.tu;p++){int col = m.data[p].j;int q = cpot[col];Triple<E> triple = new Triple<E>(m.data[p].j, m.data[p].i, (E)m.data[p].e);t.add(q, triple);cpot[col]++;//这个位置的下一个位置存储此列的下一个元素}//查看System.out.println("矩阵置换方法二");for(int i=0;i<t.tu;i++){Triple<E> tr = t.data[i];System.out.print(tr.i + " " + tr.j + " " + tr.e);System.out.println();}return t;}/** * 两稀疏矩阵相乘。 * 前提：1.矩阵元素能够相乘  *  2.一个矩阵的列等于另一个矩阵的行 * 原理：假设两矩阵M与N相乘，前提M的列M.col要等于N的行N.row(反之亦可) * 得到结果矩阵Q, Q.row=M.row, Q.col = N.col  * 而且Q[i][j] += M[i][k] * N[k][j]  0<i<M.row,0<j<N.col,0<k<M.col或N.row   */public Integer[][] multiMatrix(Integer[][] m,Integer[][] n){Integer[][] q = new Integer[m.length][n[0].length];for(int i=0;i<m.length;i++){for(int j=0;j<n[0].length;j++){int num = 0;for(int k=0;k<n.length;k++){num += (m[i][k]==null?0:m[i][k]) * (n[k][j]==null?0:n[k][j]); }q[i][j] = num;}}//打印结果for(int i=0;i<q.length;i++){for(int j=0;j<q[0].length;j++){System.out.print(q[i][j]+" ");}System.out.println();}return q;}/** * 压缩矩阵的乘法运算 * 稀疏矩阵进行乘法运算时即使含有0元素也相乘了， * 为避免这种情况，进行矩阵压缩后再相乘 * 压缩矩阵相乘原理： * 1.先把稀疏矩阵进行压缩 * 2.求出m与n的每一行的第一个非0元素在m与n中的位置 * 3.遍历m每行的非0元素， */public Matrix multiMatrix(Matrix m,Matrix n){Matrix q = new Matrix();q.mu = m.mu;q.nu = n.nu;//初始化各行第一个非0元素的位置表int[] mNum = new int[m.mu];for(int len=0;len<m.tu;len++){//每行有多少个非0元素mNum[m.data[len].i]++;}m.rpos = new int[m.mu];m.rpos[0] = 0;for(int mRow=1;mRow<m.mu;mRow++){//每行第一个非0元素在m中的位置m.rpos[mRow] = m.rpos[mRow-1] + mNum[mRow-1];}int[] nNum = new int[n.mu];for(int len=0;len<n.tu;len++){//每行有多少个非0元素nNum[n.data[len].i]++;}n.rpos = new int[n.mu];n.rpos[0] = 0;for(int nRow=1;nRow<n.mu;nRow++){//每行第一个非0元素在n中的位置n.rpos[nRow] = n.rpos[nRow-1] + nNum[nRow-1];}//初始化完毕，开始计算if(m.tu * n.tu !=0){for(int arow=0;arow<m.mu;arow++){  //一行一行处理int mlast=0;if(arow < m.mu-1)mlast = m.rpos[arow+1];elsemlast = m.tu;for(int p=m.rpos[arow];p<mlast;p++){//从这一行第一个非0索引到最后一个非0索引int brow = m.data[p].j;//由于m.j=n.i，由此可以求出与此m元素相乘的n元素int nlast=0;if(brow < n.mu-1)nlast = n.rpos[brow+1];elsenlast = n.tu;for(int w=n.rpos[brow];w<nlast;w++){int ccol = n.data[w].j;//同一行的非0元素的列索引必然不相同int sum = (Integer)m.data[p].e * (Integer)n.data[w].e;if(sum!=0){//除去0元素Triple<Integer> triple = new Triple<Integer>(arow, ccol , sum);q.add(triple);}}}}}//打印结果for(int i=0;i<q.tu;i++){Triple<E> tr = q.data[i];System.out.print(tr.i + " " + tr.j + " " + tr.e);System.out.println();}return q;}/** * 非空元素用三元组表示 */class Triple<E>{int i;//元素的行下标int j;//元素的列下标E e;//元素值Triple(int i,int j,E e) {this.i = i;this.j = j;this.e = e;}}/** * 压缩矩阵 */class Matrix{Triple[] data; //存储三元组的数组int mu;//矩阵的行数int nu;//矩阵的列数int tu;//非空个数int[] rpos; //各行第一个非0元素的位置表public Matrix(){this(10);}public Matrix(int capacity) {data = new Triple[capacity];}/** * 是否需要扩充容量 */public void ensureCapacity(int minCapacity) {int oldCapacity = data.length;if (minCapacity > oldCapacity) {//指定最小容量比原来容量大才扩充int newCapacity = (oldCapacity * 3) / 2 + 1;//扩充原容量的1.5倍加1if (newCapacity < minCapacity)//扩充后还是小于要求的最小容量，则扩充容量为最小容量newCapacity = minCapacity;data = Arrays.copyOf(data, newCapacity);}}//添加元素到压缩矩阵public boolean add(Triple triple){ensureCapacity(tu + 1); data[tu++] = triple;//size++return true;}//在指定位置添加元素（此添加非彼添加）public boolean add(int index,Triple triple){if (index >= tu || index < 0)//检查是否越界throw new IndexOutOfBoundsException("Index: " + index + ", Size: "+ tu);ensureCapacity(tu + 1); data[index] = triple;tu++;return true;}}}