XMD

无语

算法基础01：数据结构

发表于 更新于 分类于 ，
本文字数： 4k 阅读时长 ≈ 4 分钟

线性结构和非线性结构

数据结构包括：线性结构和非线性结构

线性结构

非线性结构

稀疏数组和队列

稀疏数组

基本介绍

一个案例

应用实例

稀疏数组是要保存到磁盘中去。当需要时，从磁盘中获取稀疏数组，解析为二维数组，输出为自己想要的数据。

代码实现

原始的二维数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class SpareArray {

    public static void main(String[] args) {
        int[][] chassArr1 =new int[11][11];
        chassArr1[1][2] = 1;
        chassArr1[2][3] = 2;

        for (int[] ints : chassArr1) {
            for (int anInt : ints) {
                System.out.printf("%d\t" ,anInt);
            }
            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
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
public class SpareArray {

    public static void main(String[] args) {
        //生产原始二维数组
        int[][] chassArr1 = new int[11][11];
        chassArr1[1][2] = 1;
        chassArr1[2][3] = 2;
        System.out.println("生产原始二维数组---");
        for (int[] ints : chassArr1) {
            for (int anInt : ints) {
                System.out.printf("%d\t", anInt);
            }
            System.out.println();
        }

        //将二维数组 转 稀疏数组
        //1。先遍历二维数组 得到非0的个数
        int sum = 0;
//        for (int[] ints : chassArr1) {
//            for (int anInt : ints) {
//                if (anInt != 0){
//                    sum ++;
//                }
//            }
//        }
        for (int i = 0; i < chassArr1.length; i++) {
            for (int j = 0; j < chassArr1.length; j++) {
                if (chassArr1[i][j] != 0) {
                    sum++;
                }
            }
        }
        //创建对应的稀疏数组
        int[][] sparseArr = new int[sum + 1][3];
        //设置第一行数据
        //多少行
        sparseArr[0][0] = 11;
        //多少列
        sparseArr[0][1] = 11;
        //有效数据个数
        sparseArr[0][2] = sum;

        //记录递增的行
        int count = 0;
        for (int i = 0; i < chassArr1.length; i++) {
            for (int j = 0; j < chassArr1.length; j++) {
                if (chassArr1[i][j] != 0) {
                    count ++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chassArr1[i][j];
                }
            }
        }
        System.out.println("稀疏数组---");

        for (int[] ints : sparseArr) {
            for (int anInt : ints) {
                System.out.printf("%d\t", anInt);
            }
            System.out.println();
        }

        System.out.println("稀疏数组--->>>");
        for (int i = 0; i < sparseArr.length; i++) {
            int[] ints = sparseArr[i];
            for (int j = 0; j < sparseArr.length; j++) {
                int anInt = ints[j];
                System.out.printf("%d\t", anInt);
            }
            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
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
public class SpareArray {

    public static void main(String[] args) {
        //生产原始二维数组
        int[][] chassArr1 = new int[11][11];
        chassArr1[1][2] = 1;
        chassArr1[2][3] = 2;
        System.out.println("生产原始二维数组---");
        for (int[] ints : chassArr1) {
            for (int anInt : ints) {
                System.out.printf("%d\t", anInt);
            }
            System.out.println();
        }

        //将二维数组 转 稀疏数组
        //1。先遍历二维数组 得到非0的个数
        int sum = 0;
//        for (int[] ints : chassArr1) {
//            for (int anInt : ints) {
//                if (anInt != 0){
//                    sum ++;
//                }
//            }
//        }
        for (int i = 0; i < chassArr1.length; i++) {
            for (int j = 0; j < chassArr1.length; j++) {
                if (chassArr1[i][j] != 0) {
                    sum++;
                }
            }
        }
        //创建对应的稀疏数组
        int[][] sparseArr = new int[sum + 1][3];
        //设置第一行数据
        //多少行
        sparseArr[0][0] = 11;
        //多少列
        sparseArr[0][1] = 11;
        //有效数据个数
        sparseArr[0][2] = sum;

        //记录递增的行
        int count = 0;
        for (int i = 0; i < chassArr1.length; i++) {
            for (int j = 0; j < chassArr1.length; j++) {
                if (chassArr1[i][j] != 0) {
                    count ++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chassArr1[i][j];
                }
            }
        }
        System.out.println("稀疏数组---");

        for (int[] ints : sparseArr) {
            for (int anInt : ints) {
                System.out.printf("%d\t", anInt);
            }
            System.out.println();
        }

        System.out.println("稀疏数组--->>>");
        for (int i = 0; i < sparseArr.length; i++) {
            int[] ints = sparseArr[i];
            for (int j = 0; j < sparseArr.length; j++) {
                int anInt = ints[j];
                System.out.printf("%d\t", anInt);
            }
            System.out.println();
        }

        //稀疏数组转化为二维数组
        //1.先读取稀疏数组的第一行。根据第一行数据，创建原始的二维数组
        //2.在读取稀疏数组后几行的数据，并赋予原始二维数组即可

        int[] inta = sparseArr[0];
        int[][] chaessArr2 = new int[inta[0]][inta[1]];
        for (int i = 1; i < sparseArr.length; i++) {
            int[] ints = sparseArr[i];
            chaessArr2[ints[0]][ints[1]] = ints[2];
        }
        
        //输出恢复后的二维数组
        System.out.println("恢复后的二维数组 ----");
        for (int[] ints : chaessArr2) {
            for (int anInt : ints) {
                System.out.printf("%d\t", anInt);
            }
            System.out.println();
        }

    }
}

打印：

-------------本文结束感谢您的阅读-------------

相关文章