java 稀疏数组运用
2019-11-08 本文已影响0人
坑逼的严
最近工作中用到了稀疏数组，怕忘记了，做下笔记。
稀疏数组含义：
他是一个N行3列的一个数值，当一个二位数组有大部分数据为空数据时，可以压缩压缩记录有效数据的位置，从而形成一个占据内存小的稀疏数组
举个栗子
image.png
有这一个88的表格，我们可以看做他是一个棋盘，1代表黑棋2代表白旗，没有下棋子的地方为0，那么我们保存游戏的时候，就要把整个二维数组保存，也就88=64格。那么有什么办法减小保存的数量吗？答案就是稀疏数组。
那么上面的表格转稀疏数组是什么样呢？
image.png
如图所示：
稀疏数组的第一行一次代表的是：二维数组的行数，列数，有效数字个数
后面的行中数据格式一次代表：有效数字所在的行数 ，列数 ，具体值。
自己根据上面的棋盘对一对，是不是呢？
然后我们写个工具类，直接上代码了。
public class SparseArrayTool {
/**
* 存入一个二维数组，返回一个稀疏数组
* @param args
*/
public static int[][] getSparseArray(int args[][],int rows,int clos){
int sum = 0;//记录有多少个非0的有效数据
//得到稀疏数组
for (int[] row : args) {
for (int item : row) {
if(item!=0){
sum+=1;
}
}
}
//稀疏数组固定3列，第一行固定表示二维数组的 长 宽 有效个数，后面是具体记录，所以要行数加一
int sparseArgs [][] = new int [sum+1][3];
//完成稀疏数组第一列
sparseArgs[0][0] = rows;
sparseArgs[0][1] = clos;
sparseArgs[0][2] = sum;
int count = 0;//稀疏数组从第二列才是记录
for(int x=0;x<rows;x++){
count+=1;
for(int y = 0;y<clos;y++){
if(args[x][y] != 0){
//存入
sparseArgs[count][0] = x;
sparseArgs[count][1] = y;
sparseArgs[count][2] = args[x][y];
}
}
}
//保存稀疏数组
saveSparseArray(sparseArgs,"c:\\ALL PROJECT\\array.txt");
return sparseArgs;
}
public static void saveSparseArray(int[][] sparseArgs, String path){
FileWriter fileWriter = null;
try {
fileWriter = new FileWriter(path);
for (int[] row : sparseArgs) {
for (int item : row) {
fileWriter.write(item+"&&");
}
fileWriter.write("\r\n");
}
} catch (IOException e) {
e.printStackTrace();
}finally {
if(fileWriter!=null){
try {
fileWriter.close();
fileWriter = null;
} catch (IOException e) {
e.printStackTrace();
}
}
}
}
/**
* 一个稀疏数组文件，我们不知道他的长度的情况下，要先通过io得到他的行数。
* @param path
* @return
*/
public static int getSparseArrayFileRows(String path){
File file = new File(path);
if(!file.exists()){
return 0;
}
BufferedReader bufferedReader = null;
int row = 0;
try {
bufferedReader = new BufferedReader(new FileReader(file));
String line = null;
//先来为了测出行数
while((line = bufferedReader.readLine())!=null){
row+=1;
}
} catch (Exception e) {
e.printStackTrace();
}finally {
if(bufferedReader!=null){
try {
bufferedReader.close();
bufferedReader = null;
} catch (IOException e) {
e.printStackTrace();
}
}
}
return row;
}
/**
* 读取稀疏数组文件，转化为数组
* @param path
*/
public static int [][] openSparseArrayFile(String path) {
File file = new File(path);
if(!file.exists()){
return null;
}
int fileRows = getSparseArrayFileRows(path);
int args[][]=new int[fileRows][3];
BufferedReader bufferedReader = null;
try {
bufferedReader = new BufferedReader(new FileReader(file));
//取值
int row = 0;
String line = null;
while((line = bufferedReader.readLine())!=null){
String[] temp = line.split("&&");
for(int j=0;j<temp.length;j++){
args[row][j] = Integer.parseInt(temp[j]);
}
row+=1;
}
} catch (Exception e) {
e.printStackTrace();
}finally {
if(bufferedReader!=null){
try {
bufferedReader.close();
bufferedReader = null;
} catch (IOException e) {
e.printStackTrace();
}
}
}
return args;
}
/**
* 拿到一个稀疏数组转为普通二维数组
* @param sparseArray
* @return
*/
public static int[][] getTwoArray(int[][] sparseArray,int rows,int clos) {
int[][] args = new int[rows][clos];
for (int r = 1;r<sparseArray.length;r++) {
// for (int l = 0;l<sparseArray[r].length;l++) {
//
// }
args[sparseArray[r][0]][sparseArray[r][1]] = sparseArray[r][2];
}
return args;
}
}
测试下：
二维数组转稀疏数组，并且存到file文件中
public static void main(String ar[]) {
//创建一个二维数组，并放入一些数据
int args[][] = new int [11][11];
args[0][0] = 1;
args[1][1] = 2;
args[2][1] = 1;
for (int[] row : args) {
for (int i : row) {
System.out.print(" "+i);
}
System.out.println();
}
int[][] sparseArray = SparseArrayTool.getSparseArray(args, 11, 11);
System.out.println("稀疏数组---------");
for (int[] row : sparseArray) {
for (int i : row) {
System.out.print(" "+i);
}
System.out.println();
}
}
image.png
稀疏数组的file文件转为普通二维数组
public static void main(String ar[]) {
//读取稀疏数组文件，转化为数组
int[][] sparseArray = SparseArrayTool.openSparseArrayFile("c:\\ALL PROJECT\\array.txt");
System.out.println("稀疏数组---------");
for (int[] row : sparseArray) {
for (int i : row) {
System.out.print(" " + i);
}
System.out.println();
}
System.out.println("普通数组---------");
int args[][] = SparseArrayTool.getTwoArray(sparseArray,11,11);
for (int[] row : args) {
for (int i : row) {
System.out.print(" "+i);
}
System.out.println();
}
}
image.png
