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

2020-02-21 阅读量

稀疏数组是一种压缩后的数组，由于原数组中存在大量的无效数据，占据了大量的存储空间，真正有用的数据却少之又少,所以使用压缩存储可以节省存储空间以避免资源的不必要的浪费，在数据序列化到磁盘时，压缩存储可以提高IO效率

稀疏数组

思路

代码实现

/**
 * author:小刘
 * 日期: 2020/2/18 16:00
 */
public class Demo01 {
    public static void main(String[] args) throws IOException {
        int row = 5;
        int col = 5;
        int[][] arrayChess = new int[row][col];
        arrayChess[1][2] = 1;
        arrayChess[2][3] = 2;
        System.out.println("========原始的二维数组==========");
        int sum = 0;
        for (int[] chess : arrayChess) {
            for (int data : chess) {
                System.out.printf("%d\t", data);
                if (data != 0) {
                    sum++;
                }
            }
            System.out.println();
        }

        System.out.println("=========化为稀疏数组========");
        //创建一个稀疏数组
        int[][] array = new int[sum + 1][3];
        array[0][0] = row;
        array[0][1] = col;
        array[0][2] = sum;
        //定义数值个数
        int count = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (arrayChess[i][j] != 0) {
                    count++;
                    array[count][0] = i;
                    array[count][1] = j;
                    array[count][2] = arrayChess[i][j];

                }
            }
        }

        for (int i = 0; i < array.length; i++) {
            System.out.printf("%d\t%d\t%d\t\n", array[i][0], array[i][1], array[i][2]);
        }
        //将数组转化为流保存在电脑上
        System.out.println("将稀疏数组写入本地完成");
        BufferedWriter bw = new BufferedWriter(new FileWriter("D:\\map.data"));
        for (int i = 0; i < array.length; i++) {
            bw.write(String.valueOf(array[i][0]));
            bw.write(",");
            bw.write(String.valueOf(array[i][1]));
            bw.write(",");
            bw.write(String.valueOf(array[i][2]));
            bw.newLine();
        }
        bw.close();
        System.out.println("将读取本地文件并转化为稀疏数组");
        BufferedReader br = new BufferedReader(new FileReader("D:\\map.data"));
        String len;
        int row1 = 0;
        int col1 = 0;
        ArrayList<String> list = new ArrayList();
        while ((len = br.readLine()) != null) {
            System.out.println(len);
            row1++;
            //将每一行的数据存储起来
            list.add(len);
        }
        col1 = list.size();
        int[][] array2 = new int[row1][col1];
        for (int i = 0; i <col1; i++) {
            String[] strings = list.get(i).split(",");
            for (int j = 0; j < col1; j++) {
                array2[i][j]=Integer.valueOf(strings[j]);
            }
        }
        //读取转化后的稀疏数组
        System.out.println("解析为稀疏数组");
        int row2 = array2.length;
        for (int i = 0; i < row2; i++) {
            System.out.printf("%d\t%d\t%d\t\n", array2[i][0], array2[i][1], array2[i][2]);
        }

        System.out.println("========转回来的二维数组==========");
        int[][] arrayChess2=null ;
        for (int i = 0; i < row2; i++) {
            if(i==0){
                arrayChess2 = new int[array2[0][0]][array2[0][1]];
            }else {
                arrayChess2[i][array2[i][1]]=array2[i][2];
            }
        }

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