稀疏数组（SparseArray）

1、基本介绍

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

1）稀疏数组的处理方法是：

• 记录数组一共有几行几列，有多少个不同的值
• 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

2）举例说明

• 稀疏数组的第一行分别记录总行数、总列数和有效值的个数
• 接着每一行分别存储有效值所在二维数组的行、列和具体值

3）稀疏数组其实就是一种压缩过后的数组，为什么要进行压缩数组存储呢？

• 原数组存在大量无效数据，占用存储空间大
• 压缩存储可以节省存储空间，避免不必要的资源浪费
• 在数据序列化到磁盘时，压缩存储可以提高IO效率

2、实际需求例子：

1）使用场景：

• 编写的五子棋程序中，有存盘退出和续上盘的功能需求。
• 0表示无棋子，1表示黑色棋子，2表示蓝色棋子

• 分析问题：因为该二维数组的很多值是默认值0，因此记录了很多重复且没有意义的数据。这时可以采用稀疏数组。

2）思路分析：

1、二维数组转稀疏数组

• 遍历原始的二维数组，得到有效数据的个数sum
• 根据sum就可以创建稀疏数组sparseArr int[sum+1][3]
• 将二维数组的有效数据存入到稀疏数组

2、将稀疏数组序列化到磁盘中，并且可以从磁盘中读取稀疏数组

3、稀疏数组转原始二维数组

• 先读取稀疏数组第一行的数据，根据第一行的数据创建原始的二维数组，例如 int chessArr2[][] = new int[11][11]
• 再读取稀疏数组后几行的数据（行、列、值），并赋值给刚创建的二维数组(chessArr2)即可

3）代码实现

package com.sumu.sparsearray;

import java.io.*;

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;
        // 输出原始二维数组
        System.out.println("原始二维数组：");
        for (int[] row : chessArr1) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }

        /**
         * 将 二维数组 转为 稀疏数组
         */
        // 1、先遍历二维数组，得到非0数据个数
        int sum = 0;
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if (chessArr1[i][j] != 0) {
                    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 < 11; i++) {
            for (int j = 0; j < 11; 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 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]);
        }

        /**
         * 利用IO流将稀疏数组存储到磁盘中（sparsearray.data文件）
         */
        FileWriter writer = null;
        try {
            writer = new FileWriter("D:\\Data\\sparsearray.data");
            for (int[] row : sparseArr) {
                writer.write(row[0] + "\t" + row[1] + "\t" + row[2] + "\r\n");
            }
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (writer != null) {
                try {
                    writer.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }

        /**
         * 利用IO流从磁盘中读取sparsearray.data文件，并将读取到的数据转为稀疏数组
         */
        int[][] sparseArr2 = null;
        boolean flag = false;
        BufferedReader bufferedReader = null;
        try {
            bufferedReader = new BufferedReader(new FileReader(new File("D:\\Data\\sparsearray.data")));
            String lineStr = null;
            int reaCount = 0;
            while ((lineStr = bufferedReader.readLine()) != null) {
                String[] tempStr = lineStr.split("\t");
                if (!flag) {
                    sparseArr2 = new int[Integer.parseInt(tempStr[2]) + 1][3];
                    sparseArr2[reaCount][0] = Integer.parseInt(tempStr[0]);
                    sparseArr2[reaCount][1] = Integer.parseInt(tempStr[1]);
                    sparseArr2[reaCount][2] = Integer.parseInt(tempStr[2]);
                    reaCount++;
                    flag = true;
                } else {
                    sparseArr2[reaCount][0] = Integer.parseInt(tempStr[0]);
                    sparseArr2[reaCount][1] = Integer.parseInt(tempStr[1]);
                    sparseArr2[reaCount][2] = Integer.parseInt(tempStr[2]);
                    reaCount++;
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (bufferedReader != null) {
                try {
                    bufferedReader.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }

        // 输出稀疏数组
        System.out.println("从文件中读取的稀疏数组：");
        for (int[] row : sparseArr2) {
            System.out.printf("%d\t%d\t%d\t\n", row[0], row[1], row[2]);
        }

        /**
         * 将 稀疏数组 恢复为 原始二维数组
         */
        // 1、先读取稀疏数组第一行的数据，根据第一行的数据创建原始的二维数组，例如 int chessArr2[][] = new int[11][11]
        int chessArr2[][] = new int[sparseArr2[0][0]][sparseArr[0][1]];
        // 2、再读取稀疏数组后几行的数据（行、列、值），并赋值给刚创建的二维数组(chessArr2)即可
        for (int i = 1; i < sparseArr2.length; i++) {
            chessArr2[sparseArr2[i][0]][sparseArr2[i][1]] = sparseArr2[i][0];
        }
        // 输出恢复后的二维数组
        System.out.println("恢复后的二维数组为：");
        for (int[] row: chessArr2) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }
    }
}

程序运行结果图

Q.E.D.