SparseArray

稀疏矩阵的原理及java实现

原理

如上图，在一个11X11的二维数组中，其实只有几个有效数字，如果全部存储，会造成空间上的浪费，使用3X3的稀疏数组存储有效值，会节约大量空间。

其中稀疏数组的 row[0][0] ：原始二维数组的行 数；row[0][1]：原始二维数组的列数；row[0][2]：原始二维数组有效值的个数。稀疏数组从第二行开始：row[1][0]代表原始二维数组第一个有效值所在的行索引 ；row[1][0]：原始二维数组第一个有效值所在的列索引；row[1][2]：原始二维数组第一个有效值

代码实现

/**
 * @author: zsf
 * @date: 2023/6/18 9:56
 * @description:
 */
public class SparseArray {

    public static void main(String[] args) throws IOException {
//      创建一个原始的二维数组  11*11
//        0表示无棋子 1：黑子 2：白子
        int chesssArr1[][] = new int[11][11];

//        给有棋子的位置赋值
        chesssArr1[1][2] = 1;
        chesssArr1[2][3] = 2;
        System.out.println("原始二维数组：");
        for (int[] row : chesssArr1) {
            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 (chesssArr1[i][j] != 0) {
                    sum++;
                }
            }
        }
//        2 创建对应的稀疏数组
        int sparseArry[][] = new int[sum + 1][3];  //第二行开始记录值
//        3 给稀疏数组第一行赋值
        sparseArry[0][0] = 11;
        sparseArry[0][1] = 11;
        sparseArry[0][2] = sum;
//        4 ,遍历二维数组 ，将非0的数放入稀疏数组
        int count = 0; //用于记录第几个非0的数据
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if (chesssArr1[i][j] != 0) {
                    count++;  //从第二行稀疏数组开始记录非0值所在的行与列
                    sparseArry[count][0] = i;  //行的位置
                    sparseArry[count][1] = j;//列的位置
                    sparseArry[count][2] = chesssArr1[i][j];//值
                }
            }
        }

//        5 输出稀疏数组
        System.out.println("得到的稀疏的数组：");

        for (int i = 0; i < sparseArry.length; i++) {
            System.out.printf("%d\t%d\t%d\t\n", sparseArry[i][0], sparseArry[i][1], sparseArry[i][2]);
        }
        System.out.println();
//        将稀疏数组还原成原始二维数组
//        1.先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的 chessArr2=int[11][11]
//        2.在读取稀疏数组后几行的数据，并赋给原始的二维数组即可.

        int chesssArr2[][] = new int[sparseArry[0][0]][sparseArry[0][1]];

        for (int i = 1; i < sparseArry.length; i++) {

            chesssArr2[sparseArry[i][0]][sparseArry[i][1]] = sparseArry[i][2];
        }

        System.out.println("恢复后的二维数组");
        for (int[] row : chesssArr2) {
            for (int data : row) {

                System.out.printf("%d\t", data);
            }
            System.out.println();
        }

        SparseArray a = new SparseArray();
//        a.save_sparseArray(sparseArry,"src\\com\\zsf\\day01\\sparse.txt");
        int[][] load_sparseArray = a.load_sparseArray("src\\com\\\\zsf\\day01\\sparse.txt");

        System.out.println("读入的稀疏矩阵为~~~~~~~~");
        for (int i = 0; i < load_sparseArray.length; i++) {
            System.out.printf("%d\t%d\t%d\t\n", load_sparseArray[i][0], load_sparseArray[i][1], load_sparseArray[i][2]);
        }
    }
}

稀疏数组的保存与加载

    public int[][] save_sparseArray(int sparseArry[][], String file_path) throws IOException {
        //    将稀疏数组保存下来 "./sparse.txt";
        String save_dir = file_path;
        File file = new File(save_dir);
        if (!file.exists()) {
            file.createNewFile();
            FileWriter fileWriter = new FileWriter(save_dir);
            for (int i = 0; i < sparseArry.length; i++) {
                for (int j = 0; j < sparseArry[i].length; j++) {
                    fileWriter.write(sparseArry[i][j] + "\t");
                }
//                    一行输出完后添加换行符
                fileWriter.write("\r\n");
            }
            fileWriter.close();
            System.out.println("保存成功");
        }
//        加载
        return null;
    }

    public int[][] load_sparseArray(String file_path) throws IOException {
        File file = new File(file_path);
        BufferedReader in = new BufferedReader(new FileReader(file));
        String line;
        int row = 0;
        String[] tem;
//            在使用一次in.lines/readline后，文件指针指向文件末尾，即都是0
//        long num_row = in.lines().count();
        int sparseArry[][] = new int[3][3];
        int count = 0;
//       1 要确定文件中稀疏数组有多少行
        while ((line = in.readLine()) != null) {
//          line  接收了每一行的 字符 ,即稀疏数组的 行数
            tem = line.split("\t");
            System.out.printf("%d\t%d\t%d\t\n", Integer.parseInt(tem[0]), Integer.parseInt(tem[1]), Integer.parseInt(tem[2]));
            sparseArry[count][0] = Integer.parseInt(tem[0]);  //行的位置
            sparseArry[count][1] = Integer.parseInt(tem[1]);//列的位置
            sparseArry[count][2] = Integer.parseInt(tem[2]);//值
            count++;
        }
        return sparseArry;
    }

实现效果

容易踩坑的点

1. 使用 BufferedReader 的api 时要注意，你只要调用过一次 in.read或in.read()文件指针指向文件末尾，即都是0
2. 时时记住模块化开发，提高程序的复用性