1. 数据结构【逻辑层面】A. 线性结构- 线性结构作为做最常用的数据结构，其特点是数据元素之间存在一对一的先行关系
- 线性结构有两种不同的存储结构，即【顺序存储】和【链式存储】
- 顺序存储的线性表成为顺序表，顺序表钟的存储元素是连续的
- 链式存储的线性表成为链表，链表钟的存储元素不一定是连续的，元素节点钟存放数据元素以及相邻元素的地址信息
- 线性结构常见的有：数组，队列，链表，栈
B. 非线性结构- 非线性结构包括：二维数组，多为数组，广义表，树结构，图结构
2. 稀疏数组(SparseArray)的应用场景- 编写五子棋的程序中，有【存盘退出】和【继续上盘】的功能
[AppleScript] 纯文本查看 复制代码 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 1 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，因此记录了很多没有意义的数据
A. 稀疏数组基本介绍- 当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组
- 稀疏数组的处理方法：
- 记录数组一共有几行几列，有多少个不同的值
- 吧具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模
[AppleScript] 纯文本查看 复制代码 [6 X 7 = 42]
0 0 0 22 0 0 15
0 11 0 0 0 17 0
0 0 0 -6 0 0 0
0 0 0 0 0 39 0
91 0 0 0 0 0 0
0 0 28 0 0 0 0
[AppleScript] 纯文本查看 复制代码 [9 * 3 = 27]
| 行 | 列 | 值 |
|row |col |val |
---|----|----|----|
[0]| 6 | 7 | 8 | # 第一行第一列记录着【行】【列】【一共有多少个值】
---|----|----|----|
[1]| 0 | 3 | 22 | # 第0行第3列的值为22
[2]| 0 | 6 | 15 | # 第0行第6列的值为15
[3]| 1 | 1 | 11 | # 第1行第1列的值为11
[4]| 1 | 5 | 17 | # .....
[5]| 2 | 3 | -6 |
[6]| 3 | 5 | 39 |
[7]| 4 | 0 | 91 |
[8]| 5 | 2 | 28 |
- 由 6 X 7 的数组转成 9 X 3 的稀疏数组
B. 应用实例- 使用稀疏数组，来保留类似前面的二位数组(棋盘，地图等)
- 把稀疏数组存盘，并且可以重新恢复原来的二位数组
C. 代码实现[AppleScript] 纯文本查看 复制代码 "二维数组 -> 稀疏数组 -> 二维数组"
public class SparseArray {
public static void main(String[] args) {
"创建一个原始的二维数组 【11 X 11】"
"0 表示没有棋子，1表示黑子，2表示蓝子"
int[][] chessArray = new int[11][11];
chessArray[1][2] = 1; // 1 个黑子
chessArray[2][3] = 2; // 1 个蓝子
"打印棋盘"
for (int[] arr : chessArray) {
System.out.println(Arrays.toString(arr));
}
"转稀疏数组"
System.err.println("---------------------------------");
"遍历二维数组获取非零个数"
int totalCount = 0;
for (int[] arr : chessArray) {
for (int ele : arr) if (ele != 0) totalCount++;
}
"创建稀疏数组"
int[][] sparseArray = new int[totalCount + 1][3];
sparseArray[0][0] = chessArray.length; // 行
sparseArray[0][1] = chessArray[0].length; // 多少列
sparseArray[0][2] = totalCount; // 有多少个元素
int count = 1;
outer:
for (int i = 0; i < chessArray.length; i++) {
for (int j = 0; j < chessArray[i].length; j++) {
if (chessArray[i][j] != 0) {
sparseArray[count][0] = i;
sparseArray[count][1] = j;
sparseArray[count][2] = chessArray[i][j];
if (++count == totalCount + 1) {
System.err.println("all element had put into sparseArray");
break outer;
}
}
}
}
"打印稀疏数组"
for (int[] arr : sparseArray) {
System.out.println(Arrays.toString(arr));
}
System.err.println("---------------------------------");
int[][] resultArr = new int[sparseArray[0][0]][sparseArray[0][1]];
for (int i = 1; i < sparseArray.length; i++) {
int row = sparseArray[i][0];
int col = sparseArray[i][1];
int val = sparseArray[i][2];
resultArr[row][col] = val;
}
for (int[] arr : resultArr) {
System.out.println(Arrays.toString(arr));
}
}
}
| 
收藏
淘帖
踩
