引入
- 当在网页上下棋类游戏时,玩到中途想要离开,但是我们需要保存进度,方便下次继续
- 我们应该怎么实现 ?
- 以围棋举例
- 使用二维数组将棋盘记下 ,如 0 为 没有棋子 ,1 为 黑子 , 2为白子
- 但是没有棋子的地方都为 0 ,整个二维数组充斥着大量的无效数据 0
- 我们需要想一个办法来 优化存储的方式
基本介绍
- 当一个数组中大部分元素是同一个值时,我们可以使用稀疏数组来保存该数组
- 稀疏数组:是将一个有效元素 的 坐标 和 值 记录在一个小规模数组中
- 该有效数组的头部(第一行)
- 记录了原数组一个 有几行,几列,有多少个有效值
- 该数组剩下的行数
- 是由有效值的个数来决定的 ,即 一个有效数占据一行
代码实现
- main方法
public static void main(String[] args) {
// 定义一个全是0的数组
int[][] array = new int[11][11];
// 向数组中添加几个 有效元素
array[2][3] = 1;
array[3][4] = 2;
array[2][5] = 2;
array[5][5] = 2;
// 遍历该数组查看效果
for (int[] row : array) {
for (int data : row) {
System.out.print(data + " ");
}
System.out.println();
}
int[][] sparse = toSparseArray(array);
int[][] toArray = toArray(sparse);
}
- 数组转稀疏数组
public static int[][] toSparseArray(int[][] array) {
/*
* 思路:
* 1.根据传入的二维数组,创建稀疏数组
* 2.遍历二维数组 ,如果当前元素值为有效值(不为0) ,就将该元素的坐标和值保存到稀疏数组中
* 3.因为需要坐标,所以使用普通for循环
*/
// 1. 根据传入的二维数组创建稀疏数组 ,并给稀疏数组第一行赋值
// 1.1 遍历二维数组,获取有效元素个数
int num = 0;
for (int i = 0; i < array.length; i++) {
int[] row = array[i];
for (int j = 0; j < row.length; j++) {
if (row[j] != 0) {
num++;
}
}
}
// 1.2 创建稀疏数组
int[][] sparse = new int[num + 1][3];
// 1.3 给稀疏数组第一行赋值
sparse[0][0] = array.length; // 原数组行数
sparse[0][1] = array[0].length; // 原数组列数
sparse[0][2] = num; // 有效元素个数值
// 2.1 定义一个值 ,记录稀疏数组实际的行数
num = 0;
// 2.2 再次遍历二维数组 ,并给稀疏数组赋值
for (int i = 0; i < array.length; i++) {
int[] row = array[i];
for (int j = 0; j < row.length; j++) {
if (row[j] != 0) {
++num;
sparse[num][0] = i;
sparse[num][1] = j;
sparse[num][2] = array[i][j];
}
}
}
// 遍历该数组查看效果
for (int[] row : sparse) {
for (int data : row) {
System.out.print(data + " ");
}
System.out.println();
}
return sparse;
}
- 稀疏数组转数组
private static int[][] toArray(int[][] sparse) {
// 根据稀疏数组的第一行,创建二维数组
int[][] array = new int[sparse[0][0]][sparse[0][1]];
// 遍历稀疏数组 ,从第二行开始将稀疏数组中的值 赋给 创建好的二维数组
for (int i = 1; i < sparse.length; i++) {
int[] row = sparse[i];
array[row[0]][row[1]]=row[2];
}
// 遍历二维数组,打印值
for (int[] row : array) {
for (int data : row) {
System.out.print(data + " ");
}
System.out.println();
}
return array;
}
原文链接:https://www.cnblogs.com/fzdkx/p/17317366.html
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:稀疏数组 - Python技术站