一、名词解释

1、稀疏矩阵

 

矩阵阵中非零元素较少且分布的没有规律

 

2、三元组存储 

矩阵中的一个元素有三个属性：

行号，列号，元素的值，成为三元组

3、顺序结构

 

对于每一个三元组而已，根据行号优先或者列号优先排序起来，便于后期针对矩阵的运算

 

二、压缩与还原

 

  1、压缩

逐行扫描矩阵，遇见非零元素就记录下来即可

2、还原

遍历顺序存储的数据，将每一个数据放入到矩阵的合适位置即可

 

代码实现

 

 

1、三元组抽象结构

package org.Stone6762.entity; 

/** 

* @Stone6762 

*/ 

public class TripleNode { 

/** 

* @Fields row : TODO(该元素所在的行) 

*/ 

private int row; 

/** 

* @Fields column : TODO(该元素所在的列) 

*/ 

private int column; 

/** 

* @Fields value : TODO(该位置所储存的内容) 

*/ 

private double value; 

/** 

* @构造器 

* @param row 

* @param column 

* @param value 

*/ 

public TripleNode(int row, int column, double value) { 

super(); 

this.row = row; 

this.column = column; 

this.value = value; 

} 

/** 

* @构造器 

*/ 

public TripleNode() { 

this(0, 0, 0); 

} 

public int getRow() { 

return row; 

} 

public void setRow(int row) { 

this.row = row; 

} 

public int getColumn() { 

return column; 

} 

public void setColumn(int column) { 

this.column = column; 

} 

public double getValue() { 

return value; 

} 

public void setValue(double value) { 

this.value = value; 

} 

@Override 

public String toString() { 

return "[ (" + row + "," + column + "), " 

+ value + " ]"; 

} 

}

---

2、三元组的顺序存储及其还原过程

import org.Stone6762.Utils.ArrayUtils; 

import org.Stone6762.entity.TripleNode; 

/** 

* @Stone6762 

*/ 

public class SparseArray { 

/** 

* @Fields data : TODO(储存数据的地方) 

*/ 

private TripleNode data[]; 

/** 

* @Fields rows : TODO(原始数据的行数) 

*/ 

private int rows; 

/** 

* @Fields cols : TODO(原始数据的列数) 

*/ 

private int cols; 

/** 

* @Fields nums : TODO(现存数据的个数) 

*/ 

private int nums; 

public TripleNode[] getData() { 

return data; 

} 

public void setData(TripleNode[] data) { 

this.data = data; 

this.nums = data.length; 

} 

public int getRows() { 

return rows; 

} 

public void setRows(int rows) { 

this.rows = rows; 

} 

public int getCols() { 

return cols; 

} 

public void setCols(int cols) { 

this.cols = cols; 

} 

public int getNums() { 

return nums; 

} 

public void setNums(int nums) { 

this.nums = nums; 

} 

public SparseArray() { 

super(); 

} 

/** 

* @构造器 

* @param maxSize 

*/ 

public SparseArray(int maxSize) { 

data = new TripleNode[maxSize]; 

for (int i = 0; i < data.length; i++) { 

data[i] = new TripleNode(); 

} 

rows = 0; 

cols = 0; 

nums = 0; 

} 

/** 

* @构造器 

* @param arr 

*/ 

public SparseArray(double arr[][]) { 

this.rows = arr.length; 

this.cols = arr[0].length; 

// 统计有多少非零元素，以便于下面空间的申请 

for (int i = 0; i < arr.length; i++) { 

for (int j = 0; j < arr[0].length; j++) { 

if (arr[i][j] != 0) { 

nums++; 

} 

} 

} 

// 根据上面统计的非零数据的个数，将每一个非零元素的信息进行保存 

data = new TripleNode[nums]; 

for (int i = 0, k = 0; i < arr.length; i++) { 

for (int j = 0; j < arr[0].length; j++) { 

if (arr[i][j] != 0) { 

data[k] = new TripleNode(i, j, arr[i][j]); 

k++; 

} 

} 

} 

} 

/** 

* @Title: printArray 

* @Description: TODO(打印储存后的稀疏矩阵) 

*/ 

public void printArrayOfRC() { 

System.out.println("稀疏矩阵的三元组储存结构为： "); 

System.out.println("行数" + rows + ", 列数为：" + cols + " ,非零元素个数为： " 

+ nums); 

System.out.println("行下标 列下标 元素值 "); 

for (int i = 0; i < nums; i++) { 

System.out.println(" " + data[i].getRow() + " " 

+ data[i].getColumn() + " " + data[i].getValue()); 

} 

} 

/** 

* @Description: TODO( ) 

*/ 

public void printArr() { 

System.out.println("稀疏矩阵的三元组储存结构为： "); 

System.out.println("行数" + rows + ", 列数为：" + cols + " ,非零元素个数为： " 

+ nums); 

double origArr[][] = reBackToArr(); 

ArrayUtils.printMulArray(origArr); 

} 

/** 

* @Description: TODO(将稀疏矩阵还原成影视矩阵 ) 

* @return 

*/ 

public double[][] reBackToArr() { 

double arr[][] = new double[rows][cols]; 

for (int i = 0; i < nums; i++) { 

arr[data[i].getRow()][data[i].getColumn()] = data[i].getValue(); 

} 

return arr; 

} 

}

 

提醒：稀疏矩阵的源码下载：

http://www.cnblogs.com/tanlon/p/4164295.html