数组
稀疏数组
引入案例
编写的五子棋程序中，有存盘退出和续上盘的功能
分析问题：该二维数组的很多值是默认值0，记录了很多没有意义的数据，因此可以将其转化为稀疏数组
稀疏数组基本介绍
当一个数组中大部分元素为0，或者大部分元素为同一个值的数组时，可以使用稀疏数组来保存该数组
稀疏数组的原理：
- 稀疏数组是一个行数为原数组有效元素+1 ，列数为3的数组
- 稀疏数组的第一行的分别保存原数组的行数、列数和有效值的个数
- 稀疏数组从第二行开始，分别保存每一个有效元素所在的行标和列表以及其数值
案例的分析和代码实现
案例分析
- 先用一个二维数组来模拟棋盘，其中黑子可以用1表示，蓝子可以用2表示，没有其中的格子默认为0。案例中的棋盘是\(11\times11\)，所以用一个创建一个\(11\times11\)的二维数组来表示棋盘
int[][] chessArray1 = new int[1][1];
chessArray1[1][2] = 1;
chessArray1[2][3] = 2;
- 创建稀疏数组之前，要先确定稀疏数组的大小，设原数组中有效原的个数为sum，则稀疏数组的行高为sum+1，列宽为3
int sum; //记录原数组有效元素的个数
for (int i = 0; i < chessArray1.length; i++) {
for (int j = 0; j < chessArray1[i].length; j++) {
if (chessArray1[i][j] != 1) {
sum++
}
}
}
- 创建稀疏数组并给稀疏数组赋值。
int sparseArray[][] = new int[sum+1][3];
//给稀疏数组第一行赋值
sparseArray[0][0] = chessArray1.length;
sparseArray[0][1] = chessArray1[0].length;
sparseArray[0][2] = sum;
//给稀疏数组其余行赋值
int count = 1;//count 用于记录是第几个有效数据，一个有效数据的信息占一行
for (int i = 0; i < chessArray.length; i++) {
for (int j = 0; j < chessArray[i].length; j++) {
if (chessArray[i][j] != 0) {
sparseArray[count][0] = i;
sparseArray[count][1] = j;
sparseArray[count][2] = chessArray1[i][j];
count++;
}
}
}
- 可以遍历稀疏数组，看看是否是想要的样子
for (int i 0; i< sparseArray.length; i++) {
System.out.printf(printf("%d\t%d\t%d\t\n", sparseArray[i][0], sparseArray[i][1], sparseArray[i][2]);
}
- 把稀疏数组还原成原数组。稀疏数组的第一行的第一个元素和第二个元素存储了原数组的大小
int[][] chessArray2 = new int[sparse[0][0]][sparse[0][1]];
//从第二行开始遍历稀疏数组，根据稀疏数组里面存储的数据来还原数组
for (int i = 0; i < sparseArray.length; i++) {
chessArray2[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
}
代码实现
public class SparseArray {
public static void main(String[] args) {
//创建一个原始的二维数组
//0表示没有棋子，1表示黑子，2表示蓝子
int[][] chessArray1 = new int[11][11];
chessArray1[1][2] = 1;
chessArray1[2][3] = 2;
//输出检查原二维数组
for(int[] row: chessArray1) {
for (int data: row) {
System.out.printf("%d\t", data);
}
System.out.println();
}
//将二维数组转换为稀疏数组
//1. 先遍历二维数组得到非0元素的个数
int sum = 0;
for (int i = 0; i < chessArray1.length; i++) {
for (int j = 0; j < chessArray1[i].length; j++) {
if (chessArray1[i][j] != 0) {
sum++;
}
}
}
//2.创建对应的稀疏数组
int[][] sparseArray = new int[sum + 1][3];
//3.给稀疏数组的第一行赋值
sparseArray[0][0] = chessArray1.length;
sparseArray[0][1] = chessArray1[0].length;
sparseArray[0][2] = sum;
//4.遍历二维数组，将非0的值存放到sparseArray中
int count = 1; //count 用于记录是第几个非0数据
for (int i = 0; i < chessArray1.length; i++) {
for (int j = 0; j < chessArray1[0].length; j++) {
if (chessArray1[i][j] != 0) {
sparseArray[count][0] = i;
sparseArray[count][1] = j;
sparseArray[count][2] = chessArray1[i][j];
count++;
}
}
}
//输出检查稀疏数组
for (int i = 0; i < sparseArray.length; i++) {
System.out.printf("%d\t%d\t%d\t\n", sparseArray[i][0], sparseArray[i][1], sparseArray[i][2]);
}
//将稀疏数组还原
//1.先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组
int[][] chessArray2 = new int[sparseArray[0][0]][sparseArray[0][1]];
//2.在读取稀疏数组后几行的数据(从第二行开始)，并赋给原始的二维数组
for (int i = 1; i < sparseArray.length; i++) {
chessArray2[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
}
//输出恢复后的二维数组
for (int[] ints : chessArray2) {
for (int anInt : ints) {
System.out.printf("%d\t", anInt);
}
System.out.println();
}
}
}
以上实现没有没有实现结构化编程，下面给出结构化编程的实现方式
public class SparseArrayDemo {
public static void main(String[] args) {
//创建一个原始的二维数组
//0表示没有棋子，1表示黑子，2表示蓝子
int[][] chessArray1 = new int[11][11];
chessArray1[1][2] = 1;
chessArray1[2][3] = 2;
//输出检查原二维数组
SparseArray.printArray(chessArray1);
int[][] sparseArray = SparseArray.toSparseArray(chessArray1);
SparseArray.printArray(sparseArray);
int[][] chessArray2 = SparseArray.toOriginalArray(sparseArray);
SparseArray.printArray(chessArray2);
}
}
class SparseArray {
//通过传入的二维数组成绩并返回一个稀疏数组
public static int[][] toSparseArray(int[][] array) {
//先遍历二维数组得到非0元素的个数
int sum = 0;
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[i].length; j++) {
if (array[i][j] != 0) {
sum++;
}
}
}
//创建稀疏数组
int[][] sparseArray = new int[sum + 1][3];
sparseArray[0][0] = array.length;
sparseArray[0][1] = array[0].length;
sparseArray[0][2] = sum;
//给稀疏数组赋值
int count = 1;
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[0].length; j++) {
if (array[i][j] != 0) {
sparseArray[count][0] = i;
sparseArray[count][1] = j;
sparseArray[count][2] = array[i][j];
count++;
}
}
}
return sparseArray;
}
//将稀疏数组转化为原数组的方法
public static int[][] toOriginalArray(int[][] sparseArray) {
int[][] originalArray = new int[sparseArray[0][0]][sparseArray[0][1]];
for (int i = 1; i < sparseArray.length; i++) {
originalArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
}
return originalArray;
}
//打印二维数组的方法
public static void printArray(int[][] array) {
for (int[] ints : array) {
for (int anInt : ints) {
System.out.print(anInt + "\t");
}
System.out.println();
}
System.out.println();
}
}