重学数据结构

线性结构和非线性结构

• 线性结构是最常见的数据结构，特点是元素间存在一对一的线性关系。
• 线性结构又分两种，一种是顺序存储（称为顺序表），另外一种是链式存储（称为链表）。顺序表中的存储元素的连续的。链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息。
• 常见的线性结构有：数组、队列、链表和栈（这里只是讲个大概，具体内容后面的文章会展开阐述）。

非线性结构就是结点元素可能存在多个直接前趋和多个直接后续（联想一下二叉树就懂了，但是非线性结构不仅仅只有二叉树）。

• 非线性结构包括：多维数组、广义表、树结构、图结构。

有这么一个场景，需要实现一个 10*10 的围棋的步数记录。那么最简单的就可以使用一个二维数组int[10][10]便可，但是在棋盘伊始，这个二维数组几乎没有意义的数据。假如能找到将这个二维数组压缩，只记录有用的数据的方法就好了。这时候稀疏数组就可以派上用场了。

像上述棋盘，开始的时候，数据中记录的大部分元素为 0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。

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

假如有如下的 10*6的棋盘，用正整数表示落子顺序，使用稀疏数组压缩该棋盘则有右侧的表示。第 0 行，分别表示：行数，列数，总有多少个值。从第 1 行开始到最后，都表示行数，列数，数值。

如此一来，本来是 610 的数组就被压缩成 37，大大节省了内存空间。

1. 遍历原始二维数组，得到有效数据的个数 sum
2. 创建稀疏数组 sparseArr[sum+1][3]
3. 把有效数据逐个填入稀疏数组 sparseArr 中

• 代码实现：

public int[][] reserveSparseArray(int[][] arr) {
    // 统计有效数据
    int sum = 0;
    // 遍历稀疏数组
    for (int[] is : arr) {
 for (int num : is) {
     if (num != 0) {
  sum++;
     }
 }
    }
    // 创建稀疏数组
    int[][] sparseArr = new int[sum + 1][3];
    sparseArr[0][0] = arr.length;
    sparseArr[0][1] = arr[0].length;
    sparseArr[0][2] = sum;
    for (int i = 0; i < arr.length; i++) {
 for (int j = 0; j < arr[i].length; j++) {
     if (arr[i][j] != 0) {
  sparseArr[sum][0] = i;
  sparseArr[sum][1] = j;
  sparseArr[sum][2] = arr[i][j];
  sum--;
     }
 }
    }
    return sparseArr;
}

public static int[][] reserveOriginalArray(int[][] sparseArr) {
    // 根据稀疏数组第一行创建原数组
    int[][] originalArr = new int[sparseArr[0][0]][sparseArr[0][1]];
    // 把稀疏数组的值放回到原数组中
    for (int i = 1; i < sparseArr.length; i++) {
 int row = sparseArr[i][0];
 int col = sparseArr[i][1];
 int value = sparseArr[i][2];
 originalArr[row][col] = value;
    }
    return originalArr;
}