数组--如何通过【二维数组+稀疏数组】实现五子棋盘，并且保存记忆功能？

一、应用场景

通过Java + 二维数组 + 稀疏数组实现一个五子棋盘功能，并且具有保存记忆功能。

二、实现原理

2.1 二维数组

大家都知道一维数组，不过一维数组的属于线性结构，而二维数组则属于非线性结构。

线性结构特点：

线性结构是最常用的数据结构，其特点是数据元素之间存在一对一的线性关系

线性结构有两种不同的存储结构，即 顺序存储结构( 数组)和 链式存储结构( 链表)

顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的

链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息

线性结构常见的有： 数组、链表、队列、栈、堆、散列表等

非线性结构特点：

非线性结构是相对于线性结构的，最大的特点是一个数据元素可能多个前驱元素或多个后驱元素

常用的非线性结构有二维数组，多维数组，广义表， 树结构，图结构等

一维数组创建

int oneArr[] = new int[11];

二维数组创建

int twoArr[][] = new int[11][11];

2.2 稀疏数组

稀疏数组是一种特殊的二维数组，采用压缩技术，可以减少占用的空间，降低空间复杂度

稀疏数组有多行，但只有三列，分别表示row（行）、col（列）、val（值），其中第一行比较特别，用来存放二维数组的行数，列数，有效值个数

第二行后，存放二维数组的有效值的所在的行数、列数、值

三、思路分析

创建原始一个二维数组

将二维数组转稀疏数组

将稀疏数组存到文件中

从文件中读取数据到稀疏数组

稀疏数组恢复为原始的二维数组

四、代码实现

创建原始一个二维数组

private static int[][] createTwoArr(int row, int col) { System.out.println("一、创建一个原始二维数组" + row + "*" + col); //0：表示没有棋子，1表示黑子，2表示蓝子 int twoArr[][] = new int[row][col]; twoArr[0][0] = 1; twoArr[1][1] = 2; twoArr[2][2] = 1; twoArr[3][3] = 2; //输出原始的二维数组 for (int[] r : twoArr) { for (int data : r) { System.out.printf("%d\t", data); } System.out.println(); } return twoArr; }

将二维数组转稀疏数组

private static int[][] chessArr2SparseArr(int[][] chessArr1) { System.out.println("二、将二维数组转稀疏数组"); int sum = 0; //二维数组非0数据的个数 //1.先遍历二维数组，得到非0数据的个数 for (int i = 0; i < TWO_ARR_ROW; i++) { for (int j = 0; j < TWO_ARR_COL; j++) { if (chessArr1[i][j] != 0) { sum++; } } } //2.创建对应的稀疏数组 int sparseArr[][] = new int[sum + 1][3]; //给稀疏数组赋值 sparseArr[0][0] = TWO_ARR_ROW; sparseArr[0][1] = TWO_ARR_COL; sparseArr[0][2] = sum; //遍历二维数组，将非0的值存放到稀疏数组中 int count = 0; //用于记录是第几个非0数据 for (int i = 0; i < TWO_ARR_ROW; i++) { for (int j = 0; j < TWO_ARR_COL; j++) { if (chessArr1[i][j] != 0) { count++; sparseArr[count][0] = i; sparseArr[count][1] = j; sparseArr[count][2] = chessArr1[i][j]; } } } //输出稀疏数组的形式 for (int i = 0; i < sparseArr.length; i++) { System.out.printf("%d\t%d\t%d\t\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]); } return sparseArr; }

将稀疏数组存到文件中

private static void sparseArrOutFile(File file, int[][] sparseArr) throws IOException { System.out.println("三、将稀疏数组存到文件中"); FileOutputStream fos = new FileOutputStream(file); OutputStreamWriter osw = new OutputStreamWriter(fos, "UTF-8"); for (int i = 0; i < sparseArr.length; i++) { //写入文件 if (i == sparseArr.length - 1) {//最后一行，不用加分隔符"," osw.append(sparseArr[i][0] + "," + sparseArr[i][1] + "," + sparseArr[i][2]); } else { osw.append(sparseArr[i][0] + "," + sparseArr[i][1] + "," + sparseArr[i][2] + ","); } } osw.close(); fos.close(); System.out.println(file.getAbsoluteFile()); }

从文件中读取数据到稀疏数组

private static int[][] sparseArrInfile(File file) throws IOException { System.out.println("四、从文件中读取数据到稀疏数组"); FileInputStream fis = new FileInputStream(file); InputStreamReader isr = new InputStreamReader(fis, "UTF-8"); StringBuffer sb = new StringBuffer(); while (isr.ready()) { sb.append((char) isr.read()); } isr.close(); fis.close(); String[] str = sb.toString().split(","); int[][] sparseArrFf = new int[str.length / 3][3]; int count = 0; for (String s : str) { sparseArrFf[count / 3][count % 3] = Integer.parseInt(s); count++; } //输出稀疏数组的形式 for (int i = 0; i < sparseArrFf.length; i++) { System.out.printf("%d\t%d\t%d\t\n", sparseArrFf[i][0], sparseArrFf[i][1], sparseArrFf[i][2]); } return sparseArrFf; }

稀疏数组恢复为原始的二维数组

private static int[][] sparseArr2ChessArr(int[][] sparseArrFf) { System.out.println("五、稀疏数组恢复为原始的二维数组"); //1.根据稀疏数组，创建原始的二维数组 int chessArr2[][] = new int[sparseArrFf[0][0]][sparseArrFf[0][1]]; //2.恢复稀疏的非空数据到原始二维数组中 for (int i = 1; i < sparseArrFf.length; i++) { chessArr2[sparseArrFf[i][0]][sparseArrFf[i][1]] = sparseArrFf[i][2]; } for (int[] row : chessArr2) { for (int data : row) { System.out.printf("%d\t", data); } System.out.println(); } return chessArr2; }

五、完整代码

package com.justin.datastructures.nolinear.mularray.sparsearray; import java.io.*; /** * @program: DataStructures * @description: 使用二维数组、稀疏数组实现棋盘，并且保存记忆功能 * @author: JustinQin * @create: 2021/6/27 15:19 * @version: v1.0.0 **/ public class ChessDemo { private static int TWO_ARR_ROW = 5; //二维数组行数 private static int TWO_ARR_COL = 5; //二维数组列数 public static void main(String[] args) throws IOException { //一、创建原始一个二维数组 int chessArr1[][] = createTwoArr(TWO_ARR_ROW, TWO_ARR_ROW); //二、将二维数组转稀疏数组 int sparseArr[][] = chessArr2SparseArr(chessArr1); //三、将稀疏数组存到文件中 File file = new File("C:\\Users\\Administrator\\Desktop\\temp\\map.data"); sparseArrOutFile(file, sparseArr); //四、从文件中读取数据到稀疏数组 int[][] sparseArrFf = sparseArrInfile(file); //五、稀疏数组恢复为原始的二维数组 int chessArr2[][] = sparseArr2ChessArr(sparseArrFf); } private static int[][] sparseArr2ChessArr(int[][] sparseArrFf) { System.out.println("五、稀疏数组恢复为原始的二维数组"); //1.根据稀疏数组，创建原始的二维数组 int chessArr2[][] = new int[sparseArrFf[0][0]][sparseArrFf[0][1]]; //2.恢复稀疏的非空数据到原始二维数组中 for (int i = 1; i < sparseArrFf.length; i++) { chessArr2[sparseArrFf[i][0]][sparseArrFf[i][1]] = sparseArrFf[i][2]; } for (int[] row : chessArr2) { for (int data : row) { System.out.printf("%d\t", data); } System.out.println(); } return chessArr2; } private static int[][] sparseArrInfile(File file) throws IOException { System.out.println("四、从文件中读取数据到稀疏数组"); FileInputStream fis = new FileInputStream(file); InputStreamReader isr = new InputStreamReader(fis, "UTF-8"); StringBuffer sb = new StringBuffer(); while (isr.ready()) { sb.append((char) isr.read()); } isr.close(); fis.close(); String[] str = sb.toString().split(","); int[][] sparseArrFf = new int[str.length / 3][3]; int count = 0; for (String s : str) { sparseArrFf[count / 3][count % 3] = Integer.parseInt(s); count++; } //输出稀疏数组的形式 for (int i = 0; i < sparseArrFf.length; i++) { System.out.printf("%d\t%d\t%d\t\n", sparseArrFf[i][0], sparseArrFf[i][1], sparseArrFf[i][2]); } return sparseArrFf; } private static void sparseArrOutFile(File file, int[][] sparseArr) throws IOException { System.out.println("三、将稀疏数组存到文件中"); FileOutputStream fos = new FileOutputStream(file); OutputStreamWriter osw = new OutputStreamWriter(fos, "UTF-8"); for (int i = 0; i < sparseArr.length; i++) { //写入文件 if (i == sparseArr.length - 1) {//最后一行，不用加分隔符"," osw.append(sparseArr[i][0] + "," + sparseArr[i][1] + "," + sparseArr[i][2]); } else { osw.append(sparseArr[i][0] + "," + sparseArr[i][1] + "," + sparseArr[i][2] + ","); } } osw.close(); fos.close(); System.out.println(file.getAbsoluteFile()); } private static int[][] chessArr2SparseArr(int[][] chessArr1) { System.out.println("二、将二维数组转稀疏数组"); int sum = 0; //二维数组非0数据的个数 //1.先遍历二维数组，得到非0数据的个数 for (int i = 0; i < TWO_ARR_ROW; i++) { for (int j = 0; j < TWO_ARR_COL; j++) { if (chessArr1[i][j] != 0) { sum++; } } } //2.创建对应的稀疏数组 int sparseArr[][] = new int[sum + 1][3]; //给稀疏数组赋值 sparseArr[0][0] = TWO_ARR_ROW; sparseArr[0][1] = TWO_ARR_COL; sparseArr[0][2] = sum; //遍历二维数组，将非0的值存放到稀疏数组中 int count = 0; //用于记录是第几个非0数据 for (int i = 0; i < TWO_ARR_ROW; i++) { for (int j = 0; j < TWO_ARR_COL; j++) { if (chessArr1[i][j] != 0) { count++; sparseArr[count][0] = i; sparseArr[count][1] = j; sparseArr[count][2] = chessArr1[i][j]; } } } //输出稀疏数组的形式 for (int i = 0; i < sparseArr.length; i++) { System.out.printf("%d\t%d\t%d\t\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]); } return sparseArr; } private static int[][] createTwoArr(int row, int col) { System.out.println("一、创建一个原始二维数组" + row + "*" + col); //0：表示没有棋子，1表示黑子，2表示蓝子 int twoArr[][] = new int[row][col]; twoArr[0][0] = 1; twoArr[1][1] = 2; twoArr[2][2] = 1; twoArr[3][3] = 2; //输出原始的二维数组 for (int[] r : twoArr) { for (int data : r) { System.out.printf("%d\t", data); } System.out.println(); } return twoArr; } }

运行测试类，输出结果如下：

一、创建一个原始二维数组5*5

1 0 0 0 0

0 2 0 0 0

0 0 1 0 0

0 0 0 2 0

0 0 0 0 0

二、将二维数组转稀疏数组

5 5 4

0 0 1

1 1 2

2 2 1

3 3 2

三、将稀疏数组存到文件中

C:\Users\Administrator\Desktop\temp\map.data

四、从文件中读取数据到稀疏数组

5 5 4

0 0 1

1 1 2

2 2 1

3 3 2

五、稀疏数组恢复为原始的二维数组

1 0 0 0 0

0 2 0 0 0

0 0 1 0 0

0 0 0 2 0

0 0 0 0 0

数据结构

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。