稀疏数组
先来看一个实际需求 编写的五子棋程序中，有存盘退出和续上盘的功能 那么存盘退出与续上盘应该怎样实现？
可以看到棋盘是11*11的，并且棋盘上面分布了黑子和蓝子 第一种最简单的办法是将这个棋盘以二维数组的形式保存起来 1代表黑子。2代表蓝子
但是这样的做法存在一个问题 二维数组中很多值是默认值0，因此记录了很多没有意义的数据 这个时候就可以使用稀疏数组对数据进行压缩。
稀疏数组
当一个数组大部分为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组 稀疏数组的处理办法是： 1.记录数组一共有几行几列，有多少个不同的值 2.把具有不同值的元素的行列及值记录在一个小规模的数组（稀疏数组 ）中，从而缩小程序的规模
如下例：将一个二维数组转换为稀疏数组
稀疏数组第一行保存的值是二维数组有多少行和列，有多少个不同的值。 在往后，每一行分别记录二维数组中每一个非0值的行列和具体值。 原先的二维数组是7*6 = 42，转换为稀疏数组后变成了13*3 = 39
注意点
1.可以看到原来的二维数组经过压缩后变成了39，似乎也没有减少多少，当然这里还好至少压缩了吧 可如果原来二维数组有13个有意义的值，那么原来的二维数组还是 7*6=42,而转换后稀疏数组则是 14*3=42,如果原来的二维数组有14、15、16、...个等有意义的值，那么稀疏数组的大小将会超过原先二维数组的大小，这里就得不偿失了。 2.如果反过来原来二维数组的有效值只有8个，那么原来的二维数组还是 7*6=42，如果转换为稀疏数组则是9*3=27，可以看到有明显的压缩了。 这里就得到两个结论： 二维数组的有效值越少，转换为对应的稀疏数组就越高效 稀疏数组适用于空数据较多的情况下 在使用稀疏数组之前一定要具体问题具体分析，不能一股脑的用！
代码实现
还是以一个五子棋盘为例
为了对棋盘进行压缩，我们将原来的二维数组的方式转换为稀疏数组的方式 稀疏数组第一行存储的是原来二维数组的行和列以及有效的数据 第二行后存储的是每一个数据的位置和具体值
思路分析 二维数组转换为稀疏数组 1.遍历原始的二维数组，得到要保存的有效数据的个数（sum) 2.根据sum就可以创建稀疏数组 sparseArr int[sum+1][3]，即行=sum+1行，列永远等于3列 3.将二维数组的有效数据存入到稀疏数组即可
public static void main(String[] args) {
//1.创建一个原始的二维数组
//1代表黑子，2代码蓝子
int[][] chess = new int[11][11];
chess[1][3] = 1;
chess[2][4] = 2;
System.out.println("原二维数组");
//获取原二维数组的有效数据个数
int sum = 0;
for(int[] items:chess){
for(int item :items){
if(item!=0)sum++;
System.out.printf("%d\t",item);
}
System.out.println();
}
//根据有效数据的个数创建稀疏数组
int[][] sparse = new int[sum+1][3];
//填充稀疏数组第一行数据
sparse[0][0] = 11;
sparse[0][1] = 11;
sparse[0][2] = sum;
//将原二维数组转换为稀疏数组
int count = 0;//记录当前累计的行数
for(int i = 0;i<11;i++){
for(int j = 0;j<11;j++){
if(chess[i][j]!=0){
count++;
sparse[count][0] = i; //行
sparse[count][1] = j; //列
sparse[count][2] = chess[i][j]; //值
}
}
}
System.out.println("生成后的稀疏数组");
for(int[] items:sparse){
for(int item :items){
System.out.printf("%d\t",item);
}
System.out.println();
}
}
}稀疏数组转换为二维数组 1.先读取稀疏数组的第一行（因为第一行数据保存了原来二维数组的行列和有效数据的个数）
2.根据第一行的数据数据创建原始的二维数组 chessArr2 = int[11][11]
3.在读取稀疏数组后几行的数据，并赋给原始的二维数组即可
...
int[][] chess2 = new int[sparse[0][0]][sparse[0][1]];//读取稀疏数组第一行创建二维数组
//从稀疏数组第二行开始填充原始二维数组
for(int i = 1 ; i<sparse.length;i++){
// 行 列 值
chess2[sparse[i][0]][sparse[i][1]] = sparse[i][2];
}
//转换后的原始二维数组
System.out.println("稀疏数组转换后的原始二维数组");
for(int[] items:chess2){
for(int item :items){
System.out.printf("%d\t",item);
}
System.out.println();
}运行结果如下：
原二维数组
0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 2 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
生成后的稀疏数组
11 11 2
1 3 1
2 4 2
稀疏数组转换后的原始二维数组
0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 2 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0