數組--如何通過【二維數組+稀疏數組】實現五子棋盤，并且保存記憶功能？

一、應用場景

通過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小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。