数据结构（稀疏数组）

简介

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

案例引入

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

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

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

[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();}