JAVA描述算法和数据结构(01)：稀疏数组和二维数组转换

本文源码：[GitHub·点这里] || [GitEE·点这里] # 一、基本简介 ## 1、基础概念 在矩阵中，若数值为0的元素数目远远多于非0元素的数目，并且非0元素分布没有规律时，则称该矩阵为稀疏矩阵；与之相反，若非0元素数目占大多数时，则称该矩阵为稠密矩阵。定义非零元素的总数比上矩阵所有元素的总数为矩阵的稠密度。 ## 2、处理方式 ``` 1)、记录数组一共有几行几列，有多少个不同的值 2)、把具有不同值的元素的行列及值记录在稀疏数组中，可以缩小程序代码的复杂度。 ``` ## 3、图解描述 ``` 稀疏数组表示 3 4 4 二维数组，3行，4列，4个非0的值； 1 2 2 一行，2列的值是2； 1 3 3 一行，3列的值是3； …以此类推 ``` ## 4、五子棋场景 ``` 使用稀疏数组描述 行 列 值 11 11 2 1 2 1 2 3 2 ``` # 二、代码实现 ## 1、转换流程 二维数组转稀疏数组 ``` 1)、遍历二维数组，得到非零元素的个数 2)、创建稀疏数组 3)、二维数组的非零元素写入稀疏数组 ``` 稀疏数组转二维数组 ``` 1)、读取稀疏数组的首行，创建二维数组 2)、根据稀疏数组描述的有效元素，给二维数组赋值 ``` ## 2、代码实现 1)、核心流程 ``` 1、棋盘：基于二维数组 2、二维数组转稀疏数组 3、稀疏数组转二维数组 ``` 2)、方法一：生成二维数组 ``` public static int[][] printChess (){ // 二维数组表示 11 * 11 的棋盘，0表示没有棋,1表示 黑, 2 表示蓝 int chessArray[][] = new int; chessArray = 1; chessArray = 2; for (int[] row : chessArray) { for (int data : row) { System.out.printf("%d\t", data); } System.out.println(); } return chessArray ; } ``` 3)、方法二：转为稀疏数组 ``` public static int[][] convertTwoArray (int chessArray[][]){ // 有效元素：先遍历二维数组 得到非0数据的个数 int unZeroSum = 0; for (int i = 0; i < 11; i++) { for (int j = 0; j < 11; j++) { if (chessArray != 0) { unZeroSum++; } } } // 行：有效元素+1，列：3列 int sparseArray[][] = new int[unZeroSum+1] ; sparseArray = 11 ;// 0行0列值：11 sparseArray = 11 ;// 0行1列值：11 sparseArray = unZeroSum ;// 0行2列值：unZeroSum // 遍历二维数组，将非0的值存放到稀疏数组中 // unZeroCount 用于记录是第几个非0数据,也就是稀疏数组的行 int unZeroCount = 0; // for (int i = 0; i < 11; i++) { for (int j = 0; j < 11; j++) { if (chessArray != 0) { unZeroCount++; sparseArray = i; sparseArray = j; sparseArray = chessArray; } } } // 输出稀疏数组的形式 for (int i = 0; i < sparseArray.length; i++) { System.out.printf("%d\t%d\t%d\t\n", sparseArray, sparseArray, sparseArray); } return sparseArray ; } ``` 4)、方法三：转为二维数组 ``` public static void convertSparseArray (int sparseArray[][]){ // 读取稀疏数组首行创建二维数组==>> int chessArray[][] = new int; int chessArray[][] = new int[sparseArray][sparseArray] ; // 非零元素赋值给二维数组 for(int i = 1; i < sparseArray.length; i++) { // 几行、几列、是什么值 chessArray[sparseArray][sparseArray] = sparseArray; } // 打印二维数组 for (int[] row : chessArray) { for (int data : row) { System.out.printf("%d\t", data); } System.out.println(); } } ``` 5)、主程序调用 ``` public static void main(String[] args) { // 棋盘：基于二维数组 int chessArray[][] = printChess () ; System.out.println("=========================="); // 二维数组转稀疏数组 int sparseArray[][] = convertTwoArray(chessArray) ; System.out.println("=========================="); // 稀疏数组转二维数组 convertSparseArray(sparseArray); } ``` 三、源代码地址 ``` GitHub·地址 https://github.com/cicadasmile/model-arithmetic-parent GitEE·地址 https://gitee.com/cicadasmile/model-arithmetic-parent ```