关于数据结构:数据结构和算法

第 1 章：稠密数组和队列

1、稠密数组

1.1、理论需要

• 编写的五子棋程序中，有存盘退出和续上盘的性能
• 因为该二维数组的很多值是默认值 0，因而 记录了很多没有意义的数据 ，咱们将其转为 稠密数组 进行存储

1.2、稠密数组利用

1.2.1、稠密数组解决办法

• 稠密数组把具备不同值的元素的 行列 及值记录在一个小规模的数组中，从而放大程序的规模
• 稠密数组也是二维数组，行数由原数组的数据决定，列数个别为 3 列

• 稠密数组的 第一行 记录原数组一共有几行几列，有多少个不为零的值

  • 第一列：原数组的行数
  • 第二列：原数组的列数
  • 第三列：原数组有多少个不为零的值

• 之后的行记录原数组中 不为零（x）的值 所在的行数、列数以及 x 的值

  • 第一列：x 在原数组中的行数
  • 第二列：x 在原数组中的列数
  • 第三列：x 的值

1.2.2、举例说明

• 原始二维数组较大，压缩后占用空间缩小
  

1.3、利用实例

1.3.1、思路剖析

• 应用稠密数组，来保留相似后面的二维数组(棋盘、地图等等)
• 把稠密数组存盘，并且能够从新复原原来的二维数组数

1.3.2、代码实现

• 代码

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;
        chessArr1[4][5] = 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 < chessArr1.length; i++) {for (int j = 0; j < chessArr1[i].length; j++) {if (chessArr1[i][j] != 0) {sum++;}
            }
        }

        // 2. 创立对应的稠密数组
        int sparseArr[][] = new int[sum + 1][3];
        // 给稠密数组赋值
        sparseArr[0][0] = chessArr1.length;
        sparseArr[0][1] = chessArr1[0].length;
        sparseArr[0][2] = sum;

        // 遍历二维数组，将非 0 的值寄存到 sparseArr 中
        int count = 0; // count 用于记录是第几个非 0 数据
        for (int i = 0; i < chessArr1.length; i++) {for (int j = 0; j < chessArr1[i].length; j++) {if (chessArr1[i][j] != 0) {
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessArr1[i][j];
                }
            }
        }

        // 输入稠密数组的模式
        System.out.println();
        System.out.println("失去稠密数组为~~~~");
        for (int i = 0; i < sparseArr.length; i++) {System.out.printf("%d\t%d\t%d\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]);
        }
        System.out.println();

        // 将稠密数组 --》复原成 原始的二维数组
        /*
         * 1. 先读取稠密数组的第一行，依据第一行的数据，创立原始的二维数组，比方下面的 chessArr2 = int [11][11] 2.
         * 在读取稠密数组后几行的数据，并赋给 原始的二维数组 即可.
         */

        // 1. 先读取稠密数组的第一行，依据第一行的数据，创立原始的二维数组

        int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];

        // 2. 在读取稠密数组后几行的数据(从第二行开始)，并赋给 原始的二维数组 即可

        for (int i = 1; i < sparseArr.length; i++) {chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }

        // 输入复原后的二维数组
        System.out.println();
        System.out.println("复原后的二维数组");

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

}

• 程序运行后果

原始的二维数组~~
0    0    0    0    0    0    0    0    0    0    0    
0    0    1    0    0    0    0    0    0    0    0    
0    0    0    2    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    2    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    

失去稠密数组为~~~~
11    11    3
1    2    1
2    3    2
4    5    2


复原后的二维数组
0    0    0    0    0    0    0    0    0    0    0    
0    0    1    0    0    0    0    0    0    0    0    
0    0    0    2    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    2    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    0