稀疏数组是我们一开始学数据结构的时候第一次有点味道的小算法了，大部分的人第一次是交代在这里。这是因为，这个需求来自于我们比较喜欢的五子棋小游戏。这个游戏主要是当年有个东西叫做电子词典，也不知道是啥规则，清一色都有这个游戏。
稀疏数组在应用在五子棋上面的一个原因是，落子不多的话格子是很少，但是我们定义全局的时候其实是一个二维数组。
棋盘中的代码其实是一个数组，但是里面会附带很多0元素，这样子保存起来其实是很划不来的，我们要实现的就是按照压缩策略去进行存储。
首先我们的数组长这个样子：
|0| |1| |2| |3| |4| |5| |6| |7| |8|
|0| 0 0 0 0 0 1 1 0 0
|1| 0 0 0 0 0 0 0 0 0
|2| 0 0 0 0 0 0 0 0 0
|3| 0 0 0 0 0 0 0 0 0
|4| 0 0 0 0 0 0 0 0 0
|5| 0 0 0 0 0 0 0 0 0
|6| 0 0 0 0 0 0 0 2 2
|7| 0 0 0 0 0 0 0 0 0
|8| 0 0 0 0 0 0 0 0 0
我们的有效数据其实只有4个，我们定义稀疏数组的规则如下：
1.首行保存数组多少行多少列
2.剩下的行按照行号+列号+原数值来保存
具体的保存效果如下：
[9][9][4] 首行表示原数组有多少行多少列
[0][5][1] 剩下的行数存储信息为行号|列号|原数值
[6][7][2]
[6][8][1]
一旦这样子去做，我们的数组一下子就减少很多，至少肉眼看过去盘面也小很多。
稀疏数组的转换，核心部分我加了详细注释
public void sparseArr(){
int count=0;
//因为需要知道稀疏数组的大小，除了首行之外我们需要有多少个有效的元素
for(int i = 0; i< chessArry.length; i++){
for (int j = 0; j < chessArry[i].length; j++) {
if(chessArry[i][j]!=0){
count++;
}
}
}
//0行用来保存原数组的大小信息
sparseArray=new int[count+1][3];
//首行赋值
sparseArray[0][0]=chessArrySize;
sparseArray[0][1]=chessArrySize;
sparseArray[0][2]=count;
//保存有效元素按照 行号|列号|值的格式去存储
int offset=1;
for (int i = 0; i < chessArry.length; i++) {
for (int j = 0; j < chessArry[i].length; j++) {
if(chessArry[i][j]!=0){
sparseArray[offset][0]=i;
sparseArray[offset][1]=j;
sparseArray[offset][2]=chessArry[i][j];
offset++;
}
}
}
}
存盘操作就是一个写文件操作，但是文件需要我们约定一下格式，以便读取的时候按照格式恢复，我这边直接用竖线分割就好了。
public void storeChess(){
if(sparseArray==null){
sparseArr();
}
//把稀疏数组保存到磁盘
File file=new File(storePath);
PrintWriter printWriter=null;
try {
printWriter=new PrintWriter(new FileOutputStream(file));
for (int i = 0; i < sparseArray.length; i++) {
for (int j = 0; j < sparseArray[i].length; j++) {
printWriter.print(sparseArray[i][j]+"|");
}
printWriter.println();
}
System.out.printf("sparse data save to %s successful!\n",storePath);
} catch (FileNotFoundException e) {
e.printStackTrace();
}finally {
if(printWriter!=null){
printWriter.close();
}
}
}
数据恢复包含两个方面，一个是从磁盘读取，另外是我们需要恢复成正常的数组，这个是数据解压的操作。
public void restoreChess(){
if(chessArry!=null){
clearChess();
}
System.out.println("准备恢复棋盘...");
//从文件中恢复数据
File file=new File(storePath);
try {
BufferedReader br=new BufferedReader(new FileReader(file));
String firstLine= br.readLine();//首行记录了棋盘的信息
String[] headSplits= firstLine.split("\\|");
int lineSize=Integer.valueOf(headSplits[0]);
int cloumnSize=Integer.valueOf(headSplits[1]);
int elCount=Integer.valueOf(headSplits[2]);
System.out.printf("棋盘行数:%d,棋盘列数%d,有效元素个数%d\n",lineSize,cloumnSize,elCount);
chessArry=new int[lineSize][cloumnSize];
for(int i=1;i<elCount+1;i++){ //第一行开始才有元素
String line= br.readLine();//数组信息
String[] lineSplit= line.split("\\|");
int xIndex=Integer.valueOf(lineSplit[0]);
int yIndex=Integer.valueOf(lineSplit[1]);
int value=Integer.valueOf(lineSplit[2]);
chessArry[xIndex][yIndex]=value;
}
System.out.println("恢复棋盘完成...");
} catch (IOException e) {
e.printStackTrace();
}
}
略去原数组
压缩后的数组
9 9 4
0 5 1
0 6 1
6 7 2
6 8 2
准备恢复棋盘...
棋盘行数:9,棋盘列数9,有效元素个数4
恢复棋盘完成...
|0| |
