基础知识

线性结构

线性结构是最常用的数据结构，数据元素之间存在一对一的线性关系。

线性结构有两种不同的存储结构，即顺序存储结构和链式存储结构。顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的。

链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻的地址信息。

线性表结构常见的有：数组，队列，链表，栈

非线性结构

非线性结构包括：二维数组，多维数组，广义表，树结构，图结构（这就不是一对一了）

稀疏数组

基本介绍

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

eg: 可以用这种数组模拟各种棋盘,迷宫什么的.

这里用问题驱动的模式

我们现在要制作一个棋盘游戏.

先不考虑这个棋怎么玩.

我们现在必须要构建出一个二维数组.

如下面所示.
dd0727567f537bce8f14e46b3fb2d174aa009e60e280adaa7fd891636bdd93aa-image.png
类似这个就是一个棋盘

  • 用0表示没有被下过的地方.
  • 用1表示黑子.
  • 用2表示蓝子.

无疑这么大的一个棋盘所需要记录的东西有点太多了,太耗费空间了,有没有简单一点的办法?

办法就是: 稀疏矩阵

回到刚才的图片中
我们发现其中大部分的数字都是重复的, 基本都是0, 实际上我们真正在乎的就只有有棋子的部分就是上面那个二维数组中有1,2的节点.

稀疏编号 row col val
0 11 11 2
1 1 2 1
2 2 3 2

这就是图片中棋盘的稀疏矩阵(就是第二张图片的简化版本)，一个二阶数组

用这么一个简单的方式就可以轻松的描绘出那个复杂的充满了0和1的正方形棋盘。

那我们都要记录什么内容呢

  • 棋盘大小
  • 上面棋子的落点

于是我们就知道了真正的问题就是如何存储这些数据.

稀疏编号为0的那一行里面保存的是关于这个棋盘的数据.

  • 11行
  • 11列
  • 里面有2个棋子.

稀疏编号从1开始的那些行保存的是关于棋子的信息

  • col 第几列
  • row 第几行
  • val 是哪种棋子

稀疏数组处理的方法是：

  • 记录数组一共有几行几列，有多少个不同的值
  • 把具有不同值的元素的行列值记录在一个小规模的数组（稀疏数组）中，从而缩小程序的规模。

既然我们知道了这些,那么基本就可以清楚稀疏数组的运行方式:

  • 用第一行的那个数组创建整个棋盘,用剩下的数组建立各种棋子。

    代码编写思路

    创建稀疏数组

  • 遍历目标数组

    • 获取一共有多少个有效数据 (sum)
    • 获取有多少行和列
  • 根据行数和列数以及有效数据个数, 创建稀疏数组, 稀疏数组的行数为 (sum + 1)
  • 遍历目标数组, 将有效数据赋值到稀疏数组中
  • 将稀疏数组写入到磁盘中

恢复稀疏数组

  • 从磁盘中读取稀疏数组
  • 通过获取稀疏数组的第一行数据, 创建原数组
  • 遍历稀疏数组, 将值赋值到原数组中

    代码实现

    ```java /**
  • @author shenguangyang

  • @date 2022-02-27 8:17 */ public class SparseArray { @Test public void create() throws IOException {

    1.   // 创建一个原始的二维数11*11
    2.   // 0表示没有旗子，1表示黑子，2表示蓝子
    3.   int[][] chessArr1 = new int[11][11];
    4.   chessArr1[1][2] = 1;
    5.   chessArr1[2][3] = 2;
    7.   // 输出原始数组
    8.   System.out.println("原始数组: ");
    9.   int targetRow = 0;
    10.   int targetCol = 0;
    11.   for (int[] row : chessArr1) {
    12.       targetRow = 0;
    13.       for (int data : row) {
    14.           targetRow++;
    15.           System.out.printf("%d\t", data);
    16.       }
    17.       targetCol++;
    18.       System.out.println();
    19.   }
    21.   System.out.println();
    22.   int sum = 0;
    23.   for (int i = 0; i < targetRow; i++) {
    24.       for (int j = 0; j < targetCol; j++) {
    25.           if (chessArr1[i][j] != 0) {
    26.               sum++;
    27.           }
    28.       }
    29.   }
    30.   System.out.printf("sum = %d", sum);
    31.   System.out.println();
    33.   // 将得到的值放入稀疏数组
    34.   int sparseArr[][] = new int[sum + 1][3];//sum是一共有多少个棋
    35.   //给稀数组赋值
    36.   //这是稀疏数组的第一行，也就是存放标准二维数组（棋盘）信息的地方
    37.   sparseArr[0][0] = targetRow;//有多少行
    38.   sparseArr[0][1] = targetCol;//有多少列
    39.   sparseArr[0][2] = sum;//必须拿到sum才能创建数组（sum在棋盘上有几个棋子）
    41.   int count = 0;
    42.   for (int i = 0; i < targetRow; i++) {
    43.       for (int j = 0; j < targetCol; j++) {
    44.           if (chessArr1[i][j] != 0) {
    45.               count++;
    46.               sparseArr[count][0] = i;
    47.               sparseArr[count][1] = j;
    48.               sparseArr[count][2] = chessArr1[i][j];
    49.           }
    50.       }
    51.   }
    53.   System.out.print("\n稀疏数组: \n");
    54.   for (int[] row : sparseArr) {
    55.       for (int data : row) {
    56.           System.out.printf("%d\t", data);
    57.       }
    58.       System.out.println();
    59.   }
    61.   // 将稀疏数组保存到磁盘中
    62.   saveSparseArr(sparseArr);
    64.   // 从磁盘中加载稀疏数组
    65.   int[][] recoverSparseArr = getSparseArr();
    67.   System.out.println("还原后的稀疏数组为：\n");
    68.   for (int[] ints : recoverSparseArr) {
    69.       System.out.printf("%d\t%d\t%d\n", ints[0], ints[1], ints[2]);
    70.   }
    72.   //恢复原始二维数组
    73.   int[][] chessArr3 = new int[recoverSparseArr[0][0]][recoverSparseArr[0][1]];
    74.   for (int i = 1; i < recoverSparseArr.length; i++) {
    75.       chessArr3[recoverSparseArr[i][0]][recoverSparseArr[i][1]] = recoverSparseArr[i][2];
    76.   }
    78.   System.out.println("恢复原始二维数组: \n");
    79.   for (int[] row : chessArr3) {
    80.       for (int data : row) {
    81.           System.out.printf("%d\t", data);
    82.       }
    83.       System.out.println();
    84.   }

    }

    private void saveSparseArr(int[][] sparseArr) throws IOException {

    1.   File file = new File("sparse-arr.txt");
    2.   if (file.exists()) {
    3.       file.delete();
    4.   }
    5.   if (!file.createNewFile()) {
    6.       throw new RuntimeException("createNewFile fail");
    7.   }
    9.   try (FileOutputStream fos = new FileOutputStream(file);
    10.        OutputStreamWriter osw = new OutputStreamWriter(fos, StandardCharsets.UTF_8)) {
    11.       for (int[] row : sparseArr) {
    12.           osw.write(row[0] + "," + row[1] + "," + row[2] + ",");
    13.       }
    14.   } catch (IOException e) {
    15.       e.printStackTrace();
    16.   }

    }

    private int[][] getSparseArr() throws IOException {

    1.   StringBuilder sb = new StringBuilder();
    2.   try (FileInputStream fis = new FileInputStream("sparse-arr.txt");
    3.        InputStreamReader isr = new InputStreamReader(fis, StandardCharsets.UTF_8);) {
    4.       while(isr.ready()) {
    5.           sb.append((char)isr.read());
    6.       }
    7.       String[] split = sb.toString().split(",");
    8.       int[][] sparseArr = new int[split.length/3][3];
    9.       sparseArr[0][0] = Integer.parseInt(split[0]);
    10.       sparseArr[0][1] = Integer.parseInt(split[1]);
    11.       sparseArr[0][2] = Integer.parseInt(split[2]);
    13.       int count = 0;
    14.       for (int i = 3; i < split.length; i += 3) {
    15.           count++;
    16.           sparseArr[count][0] = Integer.parseInt(split[i]);
    17.           sparseArr[count][1] = Integer.parseInt(split[i+1]);
    18.           sparseArr[count][2] = Integer.parseInt(split[i+2]);
    19.       }
    20.       return sparseArr;
    21.   } catch (Exception e) {
    22.       throw e;
    23.   }

    } }

```