一、数据结构的分类
1. 数据结构两大类
线性结构和非线性结构
1) 线性结构
- 线性结构是最常见的数据结构，特点是元素间存在一对一的线性关系。
- 线性结构又分两种，一种是顺序存储（称为顺序表），另外一种是链式存储（称为链表）。顺序表中的存储元素的连续的。链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息。
- 常见的线性结构有：数组、队列、链表和栈（这里只是讲个大概，具体内容后面的文章会展开阐述）。
2) 非线性结构
非线性结构就是结点元素可能存在多个直接前趋和多个直接后续（联想一下二叉树就懂了，但是非线性结构不仅仅只有二叉树）。
- 非线性结构包括：多维数组、广义表、树结构、图结构。
二、稀疏数组
1. 稀疏数组(sparse array)
1) 分析场景
有这么一个场景，需要实现一个 10*10 的围棋的步数记录。那么最简单的就可以使用一个二维数组int[10][10]便可，但是在棋盘伊始，这个二维数组几乎没有意义的数据。假如能找到将这个二维数组压缩，只记录有用的数据的方法就好了。这时候稀疏数组就可以派上用场了。
2) 稀疏数组
像上述棋盘，开始的时候，数据中记录的大部分元素为 0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
3) 稀疏数组的处理方法是：
- 记录数组一共有几行几列，有多少个不同的值
- 把具有不同的元素的行列以及值记录在一个小规模的数组中，从而压缩小程序的规模。
4) 举个例子：
假如有如下的 10*6的棋盘，用正整数表示落子顺序，使用稀疏数组压缩该棋盘则有右侧的表示。第 0 行，分别表示：行数，列数，总有多少个值。从第 1 行开始到最后，都表示行数，列数，数值。
如此一来，本来是 610 的数组就被压缩成 37，大大节省了内存空间。
5) 代码实现
思路分析
(1) 二维数组转稀疏数组
- 遍历原始二维数组，得到有效数据的个数 sum
- 创建稀疏数组 sparseArr[sum+1][3]
- 把有效数据逐个填入稀疏数组 sparseArr 中
- 代码实现：
/**
* 二维数组转稀疏数组
*
* @param arr 原数组
* @return 稀疏数组
*/
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;
}
(2) 稀疏数组转原始数组
- 读取稀疏数组的第 1 行，取出第一 row、第二个数 col，创建二维数组 shessArr[row][col]
- 遍历稀疏数组后面几行，把有效值填入原数组 chessArr
- 代码实现：
/**
* 稀疏数组转二位数组
*
* @param sparseArr 稀疏数组
* @return 原数组
*/
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;
}