生如风
github icon

数据结构与算法—稀疏数组

author icon生如风calendar icon2022年12月2日category icon
tag icon
timer icon大约 9 分钟

数据结构与算法—稀疏数组

稀疏数组

稀疏数组与二维数组

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

二维数组转成稀疏数组：

在这里插入图片描述

从图中可以看出： 稀疏数组的行、列、值的 （1）[0]行：二维数组 a（6*7）的行值，列值，以及元素值不为0的个数（8个） （2）[1]行：二维数组的值 22 是第 a[0] 行，第 a[3] 列 （3）[2]行：二维数组的值 15 是第 a[0] 行，第 a[6] 列 （4）[3]行：二维数组的值 11 是第 a[1] 行，第 a[1] 列

从而知道： 稀疏数组的value 值，就是二维数组中不为0的元素值，一行一行，从上到下记 稀疏数组的行，列，就是对应value值在二维数组中的位置，比如22 在a[0][3]，11在a[1][1]，-6在a[2][3]。

稀疏数组和二维数组的转换

在这里插入图片描述 根据思路可以书写代码进行测试：

  1. 创建二维数组
public class Demo {

    public static void main(String[] args) {
        // 创建二维数组
        int[][] array = new int[11][11];
        array[1][2] = 1;
        array[2][3] = 2;
        array[3][4] = 2;
        // 遍历数组打印看看
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                System.out.print(a[i][j] + " ");
            }
            System.out.println();
        }
    }
}

可以得到如下的数组：

  1. 将得到的二维数组转换成稀疏数组
class ArrayUtil {
    // 传入二维数组
    public void convert(int[][] a) {
        // 记录二维数组不为0的个数
        int sum = 0;
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                if (a[i][j] != 0) {
                    sum++;
                }
            }
        }

        // 根据sum创建稀疏数组，稀疏数组固定列为 3 列，包括row, col, val
        int[][] sparseArray = new int[sum + 1][3];
        // 行 row
        sparseArray[0][0] = a.length;
        // 列 col
        sparseArray[0][1] = a[0].length;
        // 值 val
        sparseArray[0][2] = sum;

        // 遍历二维数组，将不为 0 的值放入稀疏数组中
        // count 用于在稀疏数组中记录是第几个非 0 的数值
        int count = 0;
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                // 遍历稀疏数组并赋值
                if (a[i][j] != 0) {
                    count++;
                    sparseArray[count][0] = i;
                    sparseArray[count][1] = j;
                    sparseArray[count][2] = a[i][j];
                }
            }
        }

        // 输出稀疏数组
        System.out.println("二维数组对应的稀疏数组：");
        for (int i = 0; i < sparseArray.length; i++) {
            System.out.printf("%d\t%d\t%d\t\n", sparseArray[i][0], sparseArray[i][1], sparseArray[i][2]);
        }
    }

}
  1. 完整代码
public class Demo {

    public static void main(String[] args) {
        // 创建二维数组
        int[][] array = new int[11][11];
        array[1][2] = 1;
        array[2][3] = 2;
        array[3][4] = 2;
        // 遍历数组打印看看
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                System.out.print(array[i][j] + " ");
            }
            System.out.println();
        }
        new ArrayUtil().convert(array);
    }
}

class ArrayUtil {
    // 传入二维数组
    public void convert(int[][] a) {
        // 查询二维数组不为0的个数
        int sum = 0;
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                if (a[i][j] != 0) {
                    sum++;
                }
            }
        }

        // 根据sum创建稀疏数组，稀疏数组固定列为 3 列，包括row, col, val
        int[][] sparseArray = new int[sum + 1][3];
        // 行 row
        sparseArray[0][0] = a.length;
        // 列 col
        sparseArray[0][1] = a[0].length;
        // 值 val
        sparseArray[0][2] = sum;

        // 遍历二维数组，将不为0的值放入稀疏数组中
        // count 用于在稀疏数组中记录是第几个非 0 的数值
        int count = 0;
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                // 遍历稀疏数组并赋值
                if (a[i][j] != 0) {
                    count++;
                    sparseArray[count][0] = i;
                    sparseArray[count][1] = j;
                    sparseArray[count][2] = a[i][j];
                }
            }
        }

        // 输出稀疏数组
        System.out.println("二维数组对应的稀疏数组：");
        for (int i = 0; i < sparseArray.length; i++) {
            System.out.printf("%d\t%d\t%d\t\n", sparseArray[i][0], sparseArray[i][1], sparseArray[i][2]);
        }
    }

}

打印：

  1. 将稀疏数组转二维数组

    在上面的基础上，在后面添加代码

        // 稀疏数组转成二维数组
        System.out.println("稀疏数组转成二维数组：");

        // 创建二维数组
        int[][] chessArr2 = new int[sparseArray[0][0]][sparseArray[0][1]];
        // 遍历稀疏数组非 0 值的行,并赋值
        for (int i = 1; i < sparseArray.length; i++) {
            // 将稀疏数组中0, 1列的值对应到二维数组下标；2列的值对应到所在下标的值
            chessArr2[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }

        // 遍历数组打印看看
        for (int i = 0; i < chessArr2.length; i++) {
            for (int j = 0; j < chessArr2[i].length; j++) {
                System.out.print(chessArr2[i][j] + " ");
            }
            System.out.println();
        }
  1. 完整代码：
public class Demo {

    public static void main(String[] args) {
        // 创建二维数组
        int[][] array = new int[11][11];
        array[1][2] = 1;
        array[2][3] = 2;
        array[3][4] = 2;
        // 遍历数组打印看看
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                System.out.print(array[i][j] + " ");
            }
            System.out.println();
        }
        new ArrayUtil().convert(array);
    }
}

class ArrayUtil {

    public void convert(int[][] a) {
        // 查询二维数组不为0的个数
        int sum = 0;
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                if (a[i][j] != 0) {
                    sum++;
                }
            }
        }

        // 根据sum创建稀疏数组，稀疏数组固定列为 3 列，包括row, col, val
        int[][] sparseArray = new int[sum + 1][3];
        // 行 row
        sparseArray[0][0] = a.length;
        // 列 col
        sparseArray[0][1] = a[0].length;
        // 值 val
        sparseArray[0][2] = sum;

        // 遍历二维数组，将不为0的值放入稀疏数组中
        // count 用于在稀疏数组中记录是第几个非 0 的数值
        int count = 0;
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                // 遍历稀疏数组并赋值
                if (a[i][j] != 0) {
                    count++;
                    sparseArray[count][0] = i;
                    sparseArray[count][1] = j;
                    sparseArray[count][2] = a[i][j];
                }
            }
        }

        // 输出稀疏数组
        System.out.println("二维数组对应的稀疏数组：");
        for (int i = 0; i < sparseArray.length; i++) {
            System.out.printf("%d\t%d\t%d\t\n", sparseArray[i][0], sparseArray[i][1], sparseArray[i][2]);
        }

        // 稀疏数组转成二维数组
        System.out.println("稀疏数组转成二维数组：");

        // 创建二维数组
        int[][] chessArr2 = new int[sparseArray[0][0]][sparseArray[0][1]];
        // 遍历稀疏数组非 0 值的行,并赋值
        for (int i = 1; i < sparseArray.length; i++) {
            // 将稀疏数组中0, 1列的值对应到二维数组下标；2列的值对应到所在下标的值
            chessArr2[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }

        // 遍历数组打印看看
        for (int i = 0; i < chessArr2.length; i++) {
            for (int j = 0; j < chessArr2[i].length; j++) {
                System.out.print(chessArr2[i][j] + " ");
            }
            System.out.println();
        }

    }


}

将稀疏数组写入磁盘（类五子棋游戏的保存）

到这，完成了稀疏数组和二维数组的转化。接下来，可以将稀疏数组 sparseArray 写入磁盘

        // 将稀疏数组写到磁盘中 map.data
        // 创建缓冲字符输出流
        BufferedWriter bw;
        try {
            bw = new BufferedWriter(new FileWriter("D:\\work\\workspace\\java-learn\\sparseArray\\map.data"));
            // 遍历稀疏数组，写入数据
            for (int i = 0; i < sparseArray.length; i++) {
                bw.write(sparseArray[i][0]+"\t"+sparseArray[i][1]+"\t"+sparseArray[i][2]+"\n");
            }
            // 写完后，将内存缓冲区的数据，刷新到文件中
            bw.flush();
            // 释放资源
            bw.close();
        } catch (IOException e) {
            e.printStackTrace();
        }

上述代码执行后，会在相应目录下产生一个map.data文件，直接用txt打开，可以看到有4行3列的数据

从磁盘将数据取出

        // 从map.data中读取数据
        // 创建缓冲字符输入流
        System.out.println("------------------------------------");
        System.out.println("从文件中读出的稀疏数组：");
        BufferedReader br;
        List<String> list = new ArrayList<>();
        try {
            br = new BufferedReader(new FileReader("D:\\work\\workspace\\java-learn\\sparseArray\\map.data"));
            String line;
            while ((line = br.readLine()) != null) {
                // 可以将数据放入list或其他集合中，进行遍历还原出稀疏数组
                list.add(line);
            }
            // 释放资源
            br.close();

            // 创建稀疏数组
            int[][] sarr = new int[list.size()][3];
            // 遍历list数据
            for (int i = 0; i < list.size(); i++) {
                // 根据写入文件时的 \t 制表符分开放入数组中
                String[] s = list.get(i).trim().split("\t");
                sarr[i][0] = Integer.valueOf(s[0]);
                sarr[i][1] = Integer.valueOf(s[1]);
                sarr[i][2] = Integer.valueOf(s[2]);
            }
            // 遍历稀疏数组
            for (int i = 0; i < sarr.length; i++) {
                System.out.printf("%d\t%d\t%d\t\n", sarr[i][0], sarr[i][1], sarr[i][2]);
            }

        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }

可以看到打印出来的数据：

完整代码

package com.liwang.sparseArray;

import java.io.*;
import java.util.ArrayList;
import java.util.List;

/**
 * @Author LiWang Chen
 * @Version 1.0
 */
public class Demo {

    public static void main(String[] args) {
        // 创建二维数组
        int[][] array = new int[11][11];
        array[1][2] = 1;
        array[2][3] = 2;
        array[3][4] = 2;
        // 遍历数组打印看看
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                System.out.print(array[i][j] + " ");
            }
            System.out.println();
        }
        new ArrayUtil().convert(array);
    }
}

class ArrayUtil {

    public void convert(int[][] a) {
        // 查询二维数组不为0的个数
        int sum = 0;
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                if (a[i][j] != 0) {
                    sum++;
                }
            }
        }

        // 根据sum创建稀疏数组，稀疏数组固定列为 3 列，包括row, col, val
        int[][] sparseArray = new int[sum + 1][3];
        // 行 row
        sparseArray[0][0] = a.length;
        // 列 col
        sparseArray[0][1] = a[0].length;
        // 值 val
        sparseArray[0][2] = sum;

        // 遍历二维数组，将不为0的值放入稀疏数组中
        // count 用于在稀疏数组中记录是第几个非 0 的数值
        int count = 0;
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                // 遍历稀疏数组并赋值
                if (a[i][j] != 0) {
                    count++;
                    sparseArray[count][0] = i;
                    sparseArray[count][1] = j;
                    sparseArray[count][2] = a[i][j];
                }
            }
        }

        // 输出稀疏数组
        System.out.println("二维数组对应的稀疏数组：");
        for (int i = 0; i < sparseArray.length; i++) {
            System.out.printf("%d\t%d\t%d\t\n", sparseArray[i][0], sparseArray[i][1], sparseArray[i][2]);
        }

        // 将稀疏数组写到磁盘中 map.data
        // 创建缓冲字符输出流
        BufferedWriter bw;
        try {
            bw = new BufferedWriter(new FileWriter("D:\\work\\workspace\\java-learn\\sparseArray\\map.data"));
            // 遍历稀疏数组，写入数据
            for (int i = 0; i < sparseArray.length; i++) {
                bw.write(sparseArray[i][0]+"\t"+sparseArray[i][1]+"\t"+sparseArray[i][2]+"\n");
            }
            // 写完后，将内存缓冲区的数据，刷新到文件中
            bw.flush();
            // 释放资源
            bw.close();
        } catch (IOException e) {
            e.printStackTrace();
        }


        // 从map.data中读取数据
        // 创建缓冲字符输入流
        System.out.println("------------------------------------");
        System.out.println("从文件中读出的稀疏数组：");
        BufferedReader br;
        List<String> list = new ArrayList<>();
        try {
            br = new BufferedReader(new FileReader("D:\\work\\workspace\\java-learn\\sparseArray\\map.data"));
            String line;
            while ((line = br.readLine()) != null) {
                // 可以将数据放入list或其他集合中，进行遍历还原出稀疏数组
                list.add(line);
            }
            // 释放资源
            br.close();

            // 创建稀疏数组
            int[][] sarr = new int[list.size()][3];
            // 遍历list数据
            for (int i = 0; i < list.size(); i++) {
                // 根据写入文件时的 \t 制表符分开放入数组中
                String[] s = list.get(i).trim().split("\t");
                sarr[i][0] = Integer.valueOf(s[0]);
                sarr[i][1] = Integer.valueOf(s[1]);
                sarr[i][2] = Integer.valueOf(s[2]);
            }
            // 遍历稀疏数组
            for (int i = 0; i < sarr.length; i++) {
                System.out.printf("%d\t%d\t%d\t\n", sarr[i][0], sarr[i][1], sarr[i][2]);
            }

        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }


        // 稀疏数组转成二维数组
        System.out.println("------------------------------------");
        System.out.println("稀疏数组转成二维数组：");

        // 创建二维数组
        int[][] chessArr2 = new int[sparseArray[0][0]][sparseArray[0][1]];
        // 遍历稀疏数组非 0 值的行,并赋值
        for (int i = 1; i < sparseArray.length; i++) {
            // 将稀疏数组中0, 1列的值对应到二维数组下标；2列的值对应到所在下标的值
            chessArr2[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }

        // 遍历数组打印看看
        for (int i = 0; i < chessArr2.length; i++) {
            for (int j = 0; j < chessArr2[i].length; j++) {
                System.out.print(chessArr2[i][j] + " ");
            }
            System.out.println();
        }

    }


}

在这里插入图片描述

在这里插入图片描述

可以看看我的个人博客： 网站：https://www.fuzm.wangopen in new window / https://liwangc.gitee.ioopen in new window —————————————————————————

作为初学者，很多知识都没有掌握，见谅，如有错误请指出，以期进步，感谢！。后续有新的学习，继续补充上来。

默认页脚
Copyright © 2026 生如风