• Java数据结构与算法---稀疏数组(二)

    实际需求

      例如编写一个五子棋的程序，有存盘退出 和 续上盘 的功能，可以使用二维数组进行储存，如下图
    在这里插入图片描述
      从图上看，这个二维数组的大部分值都是0，因此记录了很多没有意义的数据。这个时候就可以使用稀疏数组对这个二维数组进行压缩，只保留有意义的数据。

    基本介绍

      当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组
      稀疏数组的处理方式是：记录数组一共有几行几列，有多少个不同的值；把具有不同值的元素的行列以及值记录在一个小规模的数组中，从而缩小程序的规模。

      如下图：用原始二维数组一共需要记录六行七列，但是用稀疏数组来记录时，第一行记录有几行，有几列，一共有多少个值，从第二行开始记录每个非零值在二维数组中的坐标以及值。最后就将一个六行七列的二维数组转变为九行三列的稀疏数组
    在这里插入图片描述

    应用实例

      1. 使用稀疏数组来保留类似前面的二维数组(棋盘、地图等)
      2. 把稀疏数组存盘，并且可以重新恢复成原来的二维数组
      3. 整体思路：
    在这里插入图片描述
    二维数组 转 稀疏数组：
      1). 遍历原始的二维数组，得到有效数据的个数sum
      2). 根据sum就可以创建稀疏数组 sparseArr int [sum + 1] [3]
      3). 将二维数组的有效数据存入到稀疏数组

    稀疏数组 转 二维数组：
      1). 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，例如上面的 chessArr2 = int [11] [11]
      2). 读取稀疏数组第二行开始的数据，并赋值给原始的二维数组即可

    代码实现

    1. 创建原始的二维数组

    // 创建原始的二维数组
// 0-没有棋子  1-黑子  2-蓝子
int[][] chessArr1 = new int[11][11];
chessArr1[1][2] = 1;
chessArr1[2][3] = 2;
chessArr1[4][3] = 1;
System.out.println("原始数组打印：");
for (int[] row : chessArr1) {
    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

      输出结果
    在这里插入图片描述

    2. 二维数组 转 稀疏数组

    // 二维数组 转 稀疏数组
// 1. 遍历二维数组等到非零值个数
int sum = 0;
for (int[] row : chessArr1) {
    for (int data : row) {
        if (data != 0) {
            sum++;
        }
    }
}
System.out.println("sum = " + sum);
// 2. 创建对应的稀疏数组
int[][] sparseArr = new int[sum + 1][3];
// 3. 稀疏数组赋值
// 第一行数据
sparseArr[0][0] = chessArr1.length;
sparseArr[0][1] = chessArr1[0].length;
sparseArr[0][2] = sum;
// 遍历二维数组，将非零值存入稀疏数组
int 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("打印稀疏数组: ");
for (int[] row : sparseArr) {
    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

      输出结果
    在这里插入图片描述

    3. 将稀疏数组存储到本地磁盘

    /**
 * 将数组写入文件
 */
public static void write(int[][] sparaseArray, String path) {
    //创建文件
    File file = new File(path);
    FileWriter write = null;
    try {
        write = new FileWriter(file);
        //写入数据
        for (int i = 0; i < sparaseArray.length; i++) {
            write.write(sparaseArray[i][0] + " ");
            write.write(sparaseArray[i][1] + " ");
            write.write(sparaseArray[i][2] + " \n");
        }
    } catch (
            IOException e) {
        e.printStackTrace();
    }
    if (write != null) {
        try {
            write.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

    • 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

      输出结果
    在这里插入图片描述

    4. 从本地磁盘读取稀疏数组文件

    /**
 * 从磁盘读取稀疏数组数据
 */
public static int[][] readTxt(String path) {
    File file = new File(path);
    //创建稀疏数组
    int[][] sparseArray;
    //建立 缓冲流
    BufferedReader buffReader = null;
    try {
        buffReader = new BufferedReader(new FileReader(file));
        //给稀疏数组初始化
        int row = 0;
        while (buffReader.readLine() != null) {
            row++;
        }
        sparseArray = new int[row][3];
        //将文件的内容读完之后，关闭流，不然读下去会读到空值
        buffReader.close();
        //重新将流打开
        buffReader = new BufferedReader(new FileReader(file));

        String str; //因为读取文件是字符串类型 所以用String接收
        int i = 0; //稀疏数组行指针
        int j = 0; //稀疏数组列指针
        while ((str = buffReader.readLine()) != null) {
            String[] sr = str.split(" ");
            for (String s : sr) {
                sparseArray[i][j] = Integer.parseInt(s);
                j++;
            }
            //下一行重新开始
            j = 0;
            i++;
        }
        return sparseArray;
    } catch (IOException e) {
        e.printStackTrace();
    }
    if (buffReader != null) {
        try {
            buffReader.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
    return null;
}

    • 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

    5. 将读取的稀疏数组还原为二维数组

            // 稀疏数组 转 二维数组
        // 1. 根据稀疏数组第一行创建原始数组
        int[][] sparseArr1 = readTxt("D:\\temp\\sparseArr.data");
        int row = sparseArr1[0][0];
        int column = sparseArr1[0][1];
        int[][] chessArr2 = new int[row][column];
        // 2. 从第二行开始将稀疏数组的值赋值给原始数组
        for (int i = 1; i < sparseArr1.length; i++) {
            int row1 = sparseArr1[i][0];
            int column1 = sparseArr1[i][1];
            int value = sparseArr1[i][2];
            chessArr2[row1][column1] = value;
        }
        System.out.println("打印恢复后的数组：");
        for (int[] row3 : chessArr2) {
            for (int data : row3) {
                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

      输出结果
    在这里插入图片描述

    完整文件

    public class SparseArray {
    public static void main(String[] args) {
        // 创建原始的二维数组
        // 0-没有棋子  1-黑子  2-蓝子
        int[][] chessArr1 = new int[11][11];
        chessArr1[1][2] = 1;
        chessArr1[2][3] = 2;
        chessArr1[4][3] = 1;
        System.out.println("原始数组打印：");
        for (int[] row : chessArr1) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }

        // 二维数组 转 稀疏数组
        // 1. 遍历二维数组等到非零值个数
        int sum = 0;
        for (int[] row : chessArr1) {
            for (int data : row) {
                if (data != 0) {
                    sum++;
                }
            }
        }
        System.out.println("sum = " + sum);
        // 2. 创建对应的稀疏数组
        int[][] sparseArr = new int[sum + 1][3];
        // 3. 稀疏数组赋值
        // 第一行数据
        sparseArr[0][0] = chessArr1.length;
        sparseArr[0][1] = chessArr1[0].length;
        sparseArr[0][2] = sum;
        // 遍历二维数组，将非零值存入稀疏数组
        int 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("打印稀疏数组: ");
        for (int[] row : sparseArr) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }
        write(sparseArr, "D:\\temp\\sparseArr.data");

        // 稀疏数组 转 二维数组
        // 1. 根据稀疏数组第一行创建原始数组
        int[][] sparseArr1 = readTxt("D:\\temp\\sparseArr.data");
        int row = sparseArr1[0][0];
        int column = sparseArr1[0][1];
        int[][] chessArr2 = new int[row][column];
        // 2. 从第二行开始将稀疏数组的值赋值给原始数组
        for (int i = 1; i < sparseArr1.length; i++) {
            int row1 = sparseArr1[i][0];
            int column1 = sparseArr1[i][1];
            int value = sparseArr1[i][2];
            chessArr2[row1][column1] = value;
        }
        System.out.println("打印恢复后的数组：");
        for (int[] row3 : chessArr2) {
            for (int data : row3) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }
    }

    /**
     * 将数组写入文件
     */
    public static void write(int[][] sparaseArray, String path) {
        //创建文件
        File file = new File(path);
        FileWriter write = null;
        try {
            write = new FileWriter(file);
            //写入数据
            for (int i = 0; i < sparaseArray.length; i++) {
                write.write(sparaseArray[i][0] + " ");
                write.write(sparaseArray[i][1] + " ");
                write.write(sparaseArray[i][2] + " \n");
            }
        } catch (
                IOException e) {
            e.printStackTrace();
        }
        if (write != null) {
            try {
                write.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

    /**
     * 从磁盘读取稀疏数组数据
     */
    public static int[][] readTxt(String path) {
        File file = new File(path);
        //创建稀疏数组
        int[][] sparseArray;
        //建立 缓冲流
        BufferedReader buffReader = null;
        try {
            buffReader = new BufferedReader(new FileReader(file));
            //给稀疏数组初始化
            int row = 0;
            while (buffReader.readLine() != null) {
                row++;
            }
            sparseArray = new int[row][3];
            //将文件的内容读完之后，关闭流，不然读下去会读到空值
            buffReader.close();
            //重新将流打开
            buffReader = new BufferedReader(new FileReader(file));

            String str; //因为读取文件是字符串类型 所以用String接收
            int i = 0; //稀疏数组行指针
            int j = 0; //稀疏数组列指针
            while ((str = buffReader.readLine()) != null) {
                String[] sr = str.split(" ");
                for (String s : sr) {
                    sparseArray[i][j] = Integer.parseInt(s);
                    j++;
                }
                //下一行重新开始
                j = 0;
                i++;
            }
            return sparseArray;
        } catch (IOException e) {
            e.printStackTrace();
        }
        if (buffReader != null) {
            try {
                buffReader.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return null;
    }
}

    • 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

       源码地址：https://gitee.com/peachtec/data-structure-and-algorithm/tree/master/src/com/hxz/dataStructure/sparseArray

  • 相关阅读:
    ThreadPoolExecutor BlockingQueue讲解
    大厂面试-美团高频考察算法之重排链表
    C高级 shell指令分支和循环
    leetcode-627. 变更性别
    双一流高校全球通邮经验：Coremail安全海外中继提升科研效率
    TCP协议
    Object.defineProperty和Proxy分别实现响应式原理的简单示例
    mac上配置maven
    Source Map知多少？Golang手写SourceMap转换过程
    Nginx的location和rewrite
  • 原文地址：https://blog.csdn.net/weixin_45481406/article/details/126014522