数据结构与算法-稀疏数组
这个是假设存在的二维数组
public static void methodA() {//假设存在以下5x5二维数组int[][] arr = new int[5][5];arr[2][3] = 1;arr[4][1] = 2;//遍历输出该数组for (int i = 0; i < arr.length; i++) {for (int j = 0; j < arr[i].length; j++)System.out.print(arr[i][j] + " ");System.out.println();}System.out.println("*****");//从输出结果可以看出里面有很多数据都是0//如果整体存储这个二维数组的话，中间会存在很多垃圾数据//如果将有效的数据分拣出来，就可以节省很多空间，例如使用稀疏数组//一、首先遍历出有效数据的个数//主要目的是确认稀疏数组的初始容量int sum = 0;for (int i = 0; i < arr.length; i++)for (int j = 0; j < arr[i].length; j++)if (arr[i][j] > 0)sum++;//二、创建稀疏数组，并确认首行值int[][] sparseArr = new int[sum + 1][3];//数组的1行n列存放分别存放sparseArr[0][0] = arr.length; //原数组的行数sparseArr[0][1] = arr[0].length; //原数组的列数sparseArr[0][2] = sum; //原数组中有效的元素个数//三、遍历原数组，将有效值存放至稀疏数组中//因为已经占用了稀疏数组第一行的位置，所以从第二行开始存放有效元素int pos = 1;int fill = 0;label:for (int i = 0; i < arr.length; i++)for (int j = 0; j < arr[i].length; j++)if (arr[i][j] > 0) {sparseArr[pos][0] = i;sparseArr[pos][1] = j;sparseArr[pos++][2] = arr[i][j];if (++fill >= sum)//这个sum的作用是可以及时停止for循环，提高效率break label;}//四、验证结果//结果就是将原本要存储的5x5的二维数组转化为存储3x3的二维数组，存储占用的空间大大减少for (int i = 0; i < sparseArr.length; i++) {for (int j = 0; j < sparseArr[i].length; j++)System.out.print(sparseArr[i][j] + " ");System.out.println();}}
这个是假设存在的稀疏数组
public static void methodB() {//假设存在以下4x3的稀疏数组int[][] sparseArr = new int[4][3];sparseArr[0][0] = 6;//二维数组的行数sparseArr[0][1] = 6;//二维数组的列数sparseArr[0][2] = 3;//二维数组中有效的元素个数sparseArr[1][0] = 3;//第一个有效元素的信息sparseArr[1][1] = 4;sparseArr[1][2] = 6;sparseArr[2][0] = 5;//第二个有效元素的信息sparseArr[2][1] = 1;sparseArr[2][2] = 2;sparseArr[3][0] = 2;//第三个有效元素的信息sparseArr[3][1] = 2;sparseArr[3][2] = 8;//遍历显示文件中有效的数据信息for (int i = 0; i < sparseArr.length; i++) {for (int j = 0; j < sparseArr[i].length; j++)System.out.print(sparseArr[i][j] + " ");System.out.println();}System.out.println("*****");//一、先创建元素的二维数组int[][] arr = new int[sparseArr[0][0]][sparseArr[0][1]];//二、从稀疏数组重取出有用数据，存入到二维数组中//因为稀疏数组的首行中存储的信息数二维数组的基本信息，不涉及二维数组中的有效信息，故从第二行开始遍历for (int i = 1; i < sparseArr.length; i++)arr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];//将有用的行列信息及值信息返回值二维数组中//三、验证结果for (int i = 0; i < arr.length; i++) {for (int j = 0; j < arr[i].length; j++)System.out.print(arr[i][j] + " ");System.out.println();}}