• 【数据结构(二)】稀疏 sparsearray 数组（1）

    文章目录

    1. 稀疏数组的应用场景

    1.1. 一个实际的需求

    问题：
        编写的五子棋程序中，有存盘退出和续上盘的功能。

    在这里插入图片描述

    分析问题：
        因为该二维数组的很多值是默认值 0, 因此记录了很多没有意义的数据 -> 稀疏数组

    1.2. 基本介绍

         当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。

    稀疏数组的处理方法:
        ①记录数组一共有几行几列，有多少个不同的值
        ②把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

    在这里插入图片描述

    上图右表中：
        第[0]行表示：数组大小是6×7，共有8个不为0的值；下面每一行都代表不为0的数值所在的行列数，[1]~[8]共有8个。

    2. 稀疏数组转换的思路分析

    1. 步骤
        ①使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等)
        ②把稀疏数组存盘，并且可以从新恢复原来的二维数组数
        

    2. 整体思路分析

    在这里插入图片描述

    二维数组 转 稀疏数组的思路

    1. 遍历 原始的二维数组，得到有效数据的个数 sum（上图为：2）
    2. 根据sum 就可以创建 稀疏数组 sparseArr int[sum + 1] [3]（上图为：[3][3]）
    3. 将二维数组的有效数据数据存入到 稀疏数组
          

    稀疏数组 转 原始的二维数组的思路

    1. 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的 chessArr2 = int [11][11]
    2. 在读取稀疏数组后几行的数据，并赋给 原始的二维数组 即可。

    3. 稀疏数组的代码实现

    3.1. 二维数组转稀疏数组

    package sparsearray;

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;//可以在后面继续加棋子

        //输出原始的二维数组
        for(int[] row : chessArr1){
            for(int data : row){
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }

        //将二维数组 转 稀疏数组
        //1.先遍历二维数组，得到非0数据的个数
        System.out.println("数组的长度为：" + chessArr1.length);
        int sum = 0;
        for(int i = 0; i < chessArr1.length; i++){
            for(int j = 0; j < chessArr1.length; j++){
                if(chessArr1[i][j] != 0){
                    sum ++;
                }
            }
        }
        System.out.println("sum=" + sum);

        //2. 创建对应的稀疏数组
        int sparseArr[][] = new int[sum + 1][3];
        //给稀疏数组赋值
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        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.length; j++){
                if(chessArr1[i][j] != 0){
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessArr1[i][j];
                }
            }
        }

        //输出稀疏数组的形式
        System.err.println();
        System.out.println("得到的稀疏数组为~~~");

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

        System.out.println();


    }
}

    • 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

    运行结果：

    在这里插入图片描述

    如果在棋盘上继续加子，如在第5行第6列加一个黑子chessArr1[4][5] = 1;

    代码：

    package sparsearray;

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] = 1;

        //输出原始的二维数组
        for(int[] row : chessArr1){
            for(int data : row){
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }

        //将二维数组 转 稀疏数组
        //1.先遍历二维数组，得到非0数据的个数
        System.out.println("数组的长度为：" + chessArr1.length);
        int sum = 0;
        for(int i = 0; i < chessArr1.length; i++){
            for(int j = 0; j < chessArr1.length; j++){
                if(chessArr1[i][j] != 0){
                    sum ++;
                }
            }
        }
        System.out.println("sum=" + sum);

        //2. 创建对应的稀疏数组
        int sparseArr[][] = new int[sum + 1][3];
        //给稀疏数组赋值
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        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.length; j++){
                if(chessArr1[i][j] != 0){
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessArr1[i][j];
                }
            }
        }

        //输出稀疏数组的形式
        System.err.println();
        System.out.println("得到的稀疏数组为~~~");

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

        System.out.println();


    }
}

    • 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

    运行结果：

    在这里插入图片描述

    3.2. 稀疏数组转二维数组

    package sparsearray;

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] = 1;

        //输出原始的二维数组
        for(int[] row : chessArr1){
            for(int data : row){
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }

        //将二维数组 转 稀疏数组
        //1.先遍历二维数组，得到非0数据的个数
        System.out.println("数组的长度为：" + chessArr1.length);
        int sum = 0;
        for(int i = 0; i < chessArr1.length; i++){
            for(int j = 0; j < chessArr1.length; j++){
                if(chessArr1[i][j] != 0){
                    sum ++;
                }
            }
        }
        System.out.println("sum=" + sum);

        //2. 创建对应的稀疏数组
        int sparseArr[][] = new int[sum + 1][3];
        //给稀疏数组赋值
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        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.length; j++){
                if(chessArr1[i][j] != 0){
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessArr1[i][j];
                }
            }
        }

        //输出稀疏数组的形式
        System.err.println();
        System.out.println("得到的稀疏数组为~~~");

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

        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.err.println();
        System.out.println("恢复后的二维数组");

        for(int[] row : chessArr2){
            for(int data : row){
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }

    }
}

    • 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

    运行结果：

    在这里插入图片描述

    4. 课后练习

        
    要求：
    （1）在前面的基础上，将稀疏数组保存到磁盘上，比如 map.data
    （2）恢复原来的数组时，读取 map.data 进行恢复

  • 相关阅读:
    创建型-配置工厂
    新登录接口独立版变现宝升级版知识付费小程序-多领域素材资源知识变现营销系统
    Intel汇编语言程序设计(第7版)第六章编程练习题答案
    人脸解锁设备时出现相机报错
    LNMP架构之搭建Discuz论坛
    计算机组成原理（三）
    Packet Tracer - 配置 IPv6 的 EIGRP 基本设置
    记录一次Linux挂载NAS共享的SMB文件系统经历
    Eclipse 主网即将上线迎空投预期，Zepoch 节点或成受益者？
    POJ 3977 Subset 折半枚举+二分搜素+双指针
  • 原文地址：https://blog.csdn.net/weixin_44883789/article/details/134467173