第 1 章：稠密数组和队列
1、稠密数组
1.1、理论需要
- 编写的五子棋程序中，有存盘退出和续上盘的性能
- 因为该二维数组的很多值是默认值 0 ，因而记录了很多没有意义的数据，咱们将其转为稠密数组进行存储
1.2、稠密数组利用
1.2.1、稠密数组解决办法
- 稠密数组把具备不同值的元素的行列及值记录在一个小规模的数组中，从而放大程序的规模
- 稠密数组也是二维数组，行数由原数组的数据决定，列数个别为 3 列
稠密数组的第一行记录原数组一共有几行几列，有多少个不为零的值
- 第一列：原数组的行数
- 第二列：原数组的列数
- 第三列：原数组有多少个不为零的值
之后的行记录原数组中不为零（x）的值所在的行数、列数以及 x 的值
- 第一列：x 在原数组中的行数
- 第二列：x 在原数组中的列数
- 第三列：x 的值
1.2.2、举例说明
- 原始二维数组较大，压缩后占用空间缩小
1.3、利用实例
1.3.1、思路剖析
- 应用稠密数组， 来保留相似后面的二维数组(棋盘、 地图等等)
- 把稠密数组存盘， 并且能够从新复原原来的二维数组数
1.3.2、代码实现
- 代码
public class SparseArray { public static void main(String[] args) { // 创立一个原始的二维数组 11 * 11 // 0: 示意没有棋子， 1 示意 黑子 2 表蓝子 int chessArr1[][] = new int[11][11]; chessArr1[1][2] = 1; chessArr1[2][3] = 2; chessArr1[4][5] = 2; // 输入原始的二维数组 System.out.println("原始的二维数组~~"); for (int[] row : chessArr1) { for (int data : row) { System.out.printf("%d\t", data); } System.out.println(); } // 将二维数组 转 稠密数组的思 // 1. 先遍历二维数组 失去非0数据的个数 int sum = 0; for (int i = 0; i < chessArr1.length; i++) { for (int j = 0; j < chessArr1[i].length; j++) { if (chessArr1[i][j] != 0) { sum++; } } } // 2. 创立对应的稠密数组 int sparseArr[][] = new int[sum + 1][3]; // 给稠密数组赋值 sparseArr[0][0] = chessArr1.length; sparseArr[0][1] = chessArr1[0].length; sparseArr[0][2] = sum; // 遍历二维数组，将非0的值寄存到 sparseArr中 int count = 0; // count 用于记录是第几个非0数据 for (int i = 0; i < chessArr1.length; i++) { for (int j = 0; j < chessArr1[i].length; j++) { if (chessArr1[i][j] != 0) { count++; sparseArr[count][0] = i; sparseArr[count][1] = j; sparseArr[count][2] = chessArr1[i][j]; } } } // 输入稠密数组的模式 System.out.println(); System.out.println("失去稠密数组为~~~~"); for (int i = 0; i < sparseArr.length; i++) { System.out.printf("%d\t%d\t%d\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]); } System.out.println(); // 将稠密数组 --》 复原成 原始的二维数组 /* * 1. 先读取稠密数组的第一行，依据第一行的数据，创立原始的二维数组，比方下面的 chessArr2 = int [11][11] 2. * 在读取稠密数组后几行的数据，并赋给 原始的二维数组 即可. */ // 1. 先读取稠密数组的第一行，依据第一行的数据，创立原始的二维数组 int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]]; // 2. 在读取稠密数组后几行的数据(从第二行开始)，并赋给 原始的二维数组 即可 for (int i = 1; i < sparseArr.length; i++) { chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2]; } // 输入复原后的二维数组 System.out.println(); System.out.println("复原后的二维数组"); for (int[] row : chessArr2) { for (int data : row) { System.out.printf("%d\t", data); } System.out.println(); } }}- 程序运行后果
原始的二维数组~~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 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 失去稠密数组为~~~~11 11 31 2 12 3 24 5 2复原后的二维数组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 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