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

举报
吾日三省贾斯汀 发表于 2021/09/09 22:57:43 2021/09/09
【摘要】 一、应用场景 通过Java + 二维数组 + 稀疏数组实现一个五子棋盘功能，并且具有保存记忆功能。 二、实现原理 2.1 二维数组 大家都知道一维数组，不过一维数组的属于线性结构，而二维数组则属...

一、应用场景

通过Java + 二维数组 + 稀疏数组实现一个五子棋盘功能，并且具有保存记忆功能。
在这里插入图片描述

二、实现原理

2.1 二维数组

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

  • 线性结构是最常用的数据结构，其特点是数据元素之间存在一对一的线性关系
  • 线性结构有两种不同的存储结构，即 顺序存储结构( 数组)和 链式存储结构( 链表)
  • 顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的
  • 链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息
  • 线性结构常见的有： 数组、链表、队列、栈、堆、散列表等

非线性结构特点：

  • 非线性结构是相对于线性结构的，最大的特点是一个数据元素可能多个前驱元素或多个后驱元素
  • 常用的非线性结构有二维数组，多维数组，广义表， 树结构，图结构等

一维数组创建

int oneArr[] = new int[11];

  
 
    
  
  • 1
    •

二维数组创建

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

  
 
    
  
  • 1
    •

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;
    }

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    • 
  
  • 5
    • 
  
  • 6
    • 
  
  • 7
    • 
  
  • 8
    • 
  
  • 9
    • 
  
  • 10
    • 
  
  • 11
    • 
  
  • 12
    • 
  
  • 13
    • 
  
  • 14
    • 
  
  • 15
    • 
  
  • 16
    • 
  
  • 17
    • 
  
  • 18
    •
  • 将二维数组转稀疏数组
    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;
    }

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    • 
  
  • 5
    • 
  
  • 6
    • 
  
  • 7
    • 
  
  • 8
    • 
  
  • 9
    • 
  
  • 10
    • 
  
  • 11
    • 
  
  • 12
    • 
  
  • 13
    • 
  
  • 14
    • 
  
  • 15
    • 
  
  • 16
    • 
  
  • 17
    • 
  
  • 18
    • 
  
  • 19
    • 
  
  • 20
    • 
  
  • 21
    • 
  
  • 22
    • 
  
  • 23
    • 
  
  • 24
    • 
  
  • 25
    • 
  
  • 26
    • 
  
  • 27
    • 
  
  • 28
    • 
  
  • 29
    • 
  
  • 30
    • 
  
  • 31
    • 
  
  • 32
    • 
  
  • 33
    • 
  
  • 34
    • 
  
  • 35
    • 
  
  • 36
    • 
  
  • 37
    •
  • 将稀疏数组存到文件中
    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());
    }

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    • 
  
  • 5
    • 
  
  • 6
    • 
  
  • 7
    • 
  
  • 8
    • 
  
  • 9
    • 
  
  • 10
    • 
  
  • 11
    • 
  
  • 12
    • 
  
  • 13
    • 
  
  • 14
    • 
  
  • 15
    • 
  
  • 16
    • 
  
  • 17
    •
  • 从文件中读取数据到稀疏数组
    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;
    }

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    • 
  
  • 5
    • 
  
  • 6
    • 
  
  • 7
    • 
  
  • 8
    • 
  
  • 9
    • 
  
  • 10
    • 
  
  • 11
    • 
  
  • 12
    • 
  
  • 13
    • 
  
  • 14
    • 
  
  • 15
    • 
  
  • 16
    • 
  
  • 17
    • 
  
  • 18
    • 
  
  • 19
    • 
  
  • 20
    • 
  
  • 21
    • 
  
  • 22
    • 
  
  • 23
    • 
  
  • 24
    •
  • 稀疏数组恢复为原始的二维数组
    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;
    }

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    • 
  
  • 5
    • 
  
  • 6
    • 
  
  • 7
    • 
  
  • 8
    • 
  
  • 9
    • 
  
  • 10
    • 
  
  • 11
    • 
  
  • 12
    • 
  
  • 13
    • 
  
  • 14
    • 
  
  • 15
    • 
  
  • 16
    • 
  
  • 17
    • 
  
  • 18
    • 
  
  • 19
    •

五、完整代码

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;
    }
}


  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    • 
  
  • 5
    • 
  
  • 6
    • 
  
  • 7
    • 
  
  • 8
    • 
  
  • 9
    • 
  
  • 10
    • 
  
  • 11
    • 
  
  • 12
    • 
  
  • 13
    • 
  
  • 14
    • 
  
  • 15
    • 
  
  • 16
    • 
  
  • 17
    • 
  
  • 18
    • 
  
  • 19
    • 
  
  • 20
    • 
  
  • 21
    • 
  
  • 22
    • 
  
  • 23
    • 
  
  • 24
    • 
  
  • 25
    • 
  
  • 26
    • 
  
  • 27
    • 
  
  • 28
    • 
  
  • 29
    • 
  
  • 30
    • 
  
  • 31
    • 
  
  • 32
    • 
  
  • 33
    • 
  
  • 34
    • 
  
  • 35
    • 
  
  • 36
    • 
  
  • 37
    • 
  
  • 38
    • 
  
  • 39
    • 
  
  • 40
    • 
  
  • 41
    • 
  
  • 42
    • 
  
  • 43
    • 
  
  • 44
    • 
  
  • 45
    • 
  
  • 46
    • 
  
  • 47
    • 
  
  • 48
    • 
  
  • 49
    • 
  
  • 50
    • 
  
  • 51
    • 
  
  • 52
    • 
  
  • 53
    • 
  
  • 54
    • 
  
  • 55
    • 
  
  • 56
    • 
  
  • 57
    • 
  
  • 58
    • 
  
  • 59
    • 
  
  • 60
    • 
  
  • 61
    • 
  
  • 62
    • 
  
  • 63
    • 
  
  • 64
    • 
  
  • 65
    • 
  
  • 66
    • 
  
  • 67
    • 
  
  • 68
    • 
  
  • 69
    • 
  
  • 70
    • 
  
  • 71
    • 
  
  • 72
    • 
  
  • 73
    • 
  
  • 74
    • 
  
  • 75
    • 
  
  • 76
    • 
  
  • 77
    • 
  
  • 78
    • 
  
  • 79
    • 
  
  • 80
    • 
  
  • 81
    • 
  
  • 82
    • 
  
  • 83
    • 
  
  • 84
    • 
  
  • 85
    • 
  
  • 86
    • 
  
  • 87
    • 
  
  • 88
    • 
  
  • 89
    • 
  
  • 90
    • 
  
  • 91
    • 
  
  • 92
    • 
  
  • 93
    • 
  
  • 94
    • 
  
  • 95
    • 
  
  • 96
    • 
  
  • 97
    • 
  
  • 98
    • 
  
  • 99
    • 
  
  • 100
    • 
  
  • 101
    • 
  
  • 102
    • 
  
  • 103
    • 
  
  • 104
    • 
  
  • 105
    • 
  
  • 106
    • 
  
  • 107
    • 
  
  • 108
    • 
  
  • 109
    • 
  
  • 110
    • 
  
  • 111
    • 
  
  • 112
    • 
  
  • 113
    • 
  
  • 114
    • 
  
  • 115
    • 
  
  • 116
    • 
  
  • 117
    • 
  
  • 118
    • 
  
  • 119
    • 
  
  • 120
    • 
  
  • 121
    • 
  
  • 122
    • 
  
  • 123
    • 
  
  • 124
    • 
  
  • 125
    • 
  
  • 126
    • 
  
  • 127
    • 
  
  • 128
    • 
  
  • 129
    • 
  
  • 130
    • 
  
  • 131
    • 
  
  • 132
    • 
  
  • 133
    • 
  
  • 134
    • 
  
  • 135
    • 
  
  • 136
    • 
  
  • 137
    • 
  
  • 138
    • 
  
  • 139
    • 
  
  • 140
    • 
  
  • 141
    • 
  
  • 142
    • 
  
  • 143
    • 
  
  • 144
    • 
  
  • 145
    • 
  
  • 146
    • 
  
  • 147
    • 
  
  • 148
    • 
  
  • 149
    • 
  
  • 150
    • 
  
  • 151
    • 
  
  • 152
    • 
  
  • 153
    • 
  
  • 154
    • 
  
  • 155
    • 
  
  • 156
    • 
  
  • 157
    •

运行测试类，输出结果如下：
一、创建一个原始二维数组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

文章来源: blog.csdn.net，作者：吾日三省贾斯汀，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/JustinQin/article/details/119081884

【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
数据结构
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入