数据结构之

2023-05-18 19:47| 来源: 网络整理| 查看: 265

一、稀疏数组概念？

稀疏数组是一种数据结构，当一个数组中有大量的元素都是同一个值时，我们可以对数组进行压缩存储为新的数组，以便于节省存储空间，这种存储结构就是稀疏数组

稀疏数组的处理方法是： 1、记录数组一共有几行几列，有多少不同的值； 2、把具有不同值的元素的行、列及值记录在一个小规模二维数组中（稀疏数组），从而缩小存储数据的规模。

二、应用场景

【1】如下图所示，这里有一个 11 × 11 的棋盘，如果现在要让你通过编码的方式，让你将这盘棋局保存起来，你会怎么做呢？

image.png 三、普通数组实现

比如，我们可以将棋盘进行抽象化，用一个 11 × 11 的二维数组来表示，然后用 0 表示空点，用 1 表示白子，用 2 表示黑子，于是就可以抽象为如下模样。

image.png

代码实现

/** * 将棋盘数据保存为二维数组 */ public static void main(String[] args) { int[][] array=new int[11][11]; //保存黑子 array[1][2]=2; // 保存白子 array[2][3]=1; // 遍历二维数组 for (int[] ints : array) { System.out.println(); for (int anInt : ints) { System.out.print("\t"+anInt); } } } 四、稀疏数组实现

所谓稀疏数组，从字面上我们也可以得知，它仍然是一个数组，他的作用就是将一个对应的数组数据进行优化，比如，我们将上面的二维数组进行优化。稀疏数组处理数据的方法： 1）记录数组一共有几行几列、有多少个不同的数值 2）把不同值元素的行列存储在一个小规模的数组里面，从而缩小程序的规模。

image.png

二位数组转稀疏数组，代码实现

//二维数组转稀疏数组 public static int[][] getSparseArray(int[][] array) { // 统计二位数组中有效值有几个 int count = 0; for (int[] ints : array) { for (int anInt : ints) { if (anInt != 0) { count++; } } } System.out.println("\n有效值为：" + count); //创建稀疏数组，count+1是因为稀疏数组需要单独占用一行 int[][] sparseArray = new int[count + 1][3]; //列头的初始化需要自己赋值 sparseArray[0][0] = 11; sparseArray[0][1] = 11; sparseArray[0][2] = count; // 统计 int sum=0; for (int i = 0; i < array.length; i++) { for (int j = 0; j < array[i].length; j++) { if (array[i][j] != 0) { // 每个有效值在稀疏数组中都是占一行，所以需要在外部声明一个数去统计有效值， sum++; sparseArray[sum][0] = i; sparseArray[sum][1] = j; sparseArray[sum][2] = array[i][j]; } } } return sparseArray; }

稀疏数组转二维数组，代码实现

//稀疏数组转二维数组 public static int[][] getArray(int[][] sparseArray) { // 因为稀疏数组的低1列就保存着数组的结构，所以直接取出来 int row = sparseArray[0][0]; int column = sparseArray[0][1]; //初始化二维数组 int[][] array = new int[row][column]; for (int i = 1; i < sparseArray.length; i++) { // 取出稀疏数组中第1行的行值 int tempRow = sparseArray[i][0]; // 取出稀疏数组中第1行的列值 int tempColumn = sparseArray[i][1]; // 对二维数组进行值装填 array[tempRow][tempColumn] = sparseArray[i][2]; } return array; } 六、总结

我们通过了一个最普通的方法，将棋盘数据保存在了一个二维数组中，整个数组我们用了 11 × 11（共 121）个点来保存数据，其中有 119 个点都是空的。实际来说，我们只需要将有价值的黑白子保存起来即可，因为只要我们知道黑白子数据，以及棋盘的大小，那么这 119个空点是可以不用进行保存的。

把这样没有价值的数据起来，不但会浪费存储空间的大小，如果写入到磁盘中，还会增大 IO 的读写量，影响性能，这就是用普通二维数组来表示棋盘数据的不足之处。

在存储数组数据的时候，我们如果存在许多默认值的数据，不妨用稀疏数组来进行存储。

【本文地址】

公司简介

联系我们