数据结构（稀疏数组）

简介

稀疏数组是一种数据结构，用于有效地存储和处理那些大多数元素都是零或者重复值的数组。在稀疏数组中，只有非零或非重复的元素会被存储，从而节省内存空间。

案例引入

假如想把下面这张表存入文件，我们会怎么做？

如果我们不做优化其实是浪费了很大一部分空间去存储空值，有没有办法既能实现效果又能节省空间呢？其实有的，稀疏数组就可以做到。

假如我们只存储右边的数据，相对左边做了相对大的数据压缩，会把空数据也就是无效的数据过滤，只存储有效的数据。
稀疏数组结构解释：

[0][0] - 记录原二维数组有几行
[0][1] - 记录原二维数组有几列
[0][2] - 记录原二维数组有多少个有效的数据

后面的一次记录有效数据所在行和列及有效数据的具体值

1，我们先将上图中的第一个数据结构转成程序中的二维数组

//1，将棋盘中的1，2用二维数组保存起来int[][] chessArray = new int[11][11];chessArray[1][2] = 1;chessArray[2][3] = 2;System.out.println("将棋盘转换为原始的二维数组");for (int i = 0; i < 11; i++) {for (int j = 0; j < 11; j++) {System.out.printf("%d\t", chessArray[i][j]);}System.out.println();}

        //2，将棋盘chessArray转出稀疏数组//稀疏数组一共有 row 3 col sum+1  第一行第一列未i行，第一行第二列为j列，第三个为num有效数据//第一步先要找出上述棋盘一共有多少个有效数据，计为sumint sum = 0;//默认0个有效数据for (int[] row : chessArray) {for (int data : row) {if (data != 0) {sum++;}}}//转换的稀疏数组int[][] sparseArray = new int[sum + 1][3];//将有效数据保存到稀疏数组中sparseArray[0][0] = chessArray.length;sparseArray[0][1] = chessArray.length;sparseArray[0][2] = sum;int count = 0;for(int i = 0;i<chessArray.length;i++){for(int j = 0 ;j<chessArray.length;j++){if(chessArray[i][j]!=0){count++;sparseArray[count][0] = i;sparseArray[count][1] = j;sparseArray[count][2] = chessArray[i][j];}}}System.out.println("转换的稀疏数组为");for(int []rows : sparseArray){for(int data:rows){System.out.printf("%d\t",data);}System.out.println();}

 //将稀疏数组转出原始数组//1，读取第一行创建原始数组的大小int [][] chessArray2 = new int[sparseArray[0][0]][sparseArray[0][1]];System.out.println();System.out.println("原始数组"+sparseArray[0][0]+" "+sparseArray[0][1]);for(int i = 1;i<sparseArray.length;i++){chessArray2[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];}System.out.println("转换的原始数组");for(int []rows : chessArray2){for(int data:rows){System.out.printf("%d\t",data);}System.out.println();}

总结

从上面的案例中，我们能感受到稀疏数组的一些特点：
存储效率：由于只存储非零或非重复的元素，稀疏数组在处理大量零值或重复值的数据时非常高效。

空间优化：相比于传统的数组，稀疏数组可以显著减少所需的存储空间。

稀疏性：稀疏数组中的元素大部分是零或重复值，这些值不需要存储。

实现方式：稀疏数组可以通过多种方式实现，例如使用哈希表、链表、位图或压缩存储等。

适用场景：稀疏数组适用于那些元素值重复或为零的情况，例如图的邻接矩阵、大规模数据集、科学计算中的矩阵等。

访问速度：虽然稀疏数组在存储上很高效，但访问速度可能会比传统数组慢，因为需要额外的查找步骤来定位非零元素。

更新和删除：在稀疏数组中更新或删除元素可能比在传统数组中更复杂，因为需要维护非零元素的索引或映射。

稀疏度：稀疏数组的效率很大程度上取决于其稀疏度，即非零或非重复元素占总元素的比例。稀疏度越高，稀疏数组的优势越明显。

总的来说，稀疏数组是一种针对特定数据特性优化的数据结构，可以在特定场景下提供存储和处理上的优势。