庖丁解牛--数据结构(一)之稀数组
一,稀疏数组
1.定义
稀疏数组可以看做是普通数组的压缩,简单点 稀疏数组中都是有用数据且,结构int sparseArray[][] = new int[sum+1][3]
说明:sum为二维数组中有用数据个数。
2.举例个例子
棋盘(标准的二维数组 11 * 11) 0代表无子 1 代表黑子 2 代表 白子
将上述二维数组转为稀疏数组如下展示
说明:
第一行 存储 原二维数组的行、列、有效数据个数
第二至sum+1行 存储 原二维数组中 有效数据 所在 行、列、有效数据值(sum为有效数据个数)
理论到此为止上码~~
3.实践
public static void main(String[] args) { //1.创建二维数组11*11 //0 标示没有子,1 标示黑子 2标示 白子 int chessArr1[][] = new int[11][11]; chessArr1[1][2] = 1; chessArr1[2][3] = 2; for (int[] ints : chessArr1) { for (int anInt : ints) { System.out.printf("%d\t", anInt); } System.out.println(); } System.out.println("二维数组~~~~"); //2二维数组转稀疏数组 int sum = 0; for (int[] ints : chessArr1) { for (int anInt : ints) { if (anInt > 0) { sum ++ ; } } } int chessArr2[][] = new int[sum + 1][3]; chessArr2[0][0] = chessArr1.length; chessArr2[0][1] = chessArr1[0].length; chessArr2[0][2] = sum; int row = 1; for (int i = 0; i < chessArr1.length; i++) { for (int y = 0 ; y <chessArr1[i].length; y++) { if (chessArr1[i][y] > 0) { chessArr2[row][0] = i; chessArr2[row][1] = y; chessArr2[row][2] = chessArr1[i][y]; row ++; } } } for (int[] ints : chessArr2) { System.out.printf("%d\t%d\t%d\t", ints[0],ints[1],ints[2]); System.out.println(); } System.out.println("稀疏数组~~"); //3.稀疏数组转二维数组 int chessArr3[][] = new int[chessArr2[0][0]][chessArr2[0][1]]; for (int i = 1 ; i < chessArr2.length ; i++) { chessArr3[chessArr2[i][0]][chessArr2[i][1]] = chessArr2[i][2]; } for (int[] ints : chessArr3) { for (int anInt : ints) { System.out.printf("%d\t", anInt); } System.out.println(); } }