JAVA描述算法和數(shù)據(jù)結(jié)構(gòu)(01)：稀疏數(shù)組和二維數(shù)組轉(zhuǎn)換

本文源碼：[GitHub·點(diǎn)這里] || [GitEE·點(diǎn)這里] # 一、基本簡介 ## 1、基礎(chǔ)概念 在矩陣中，若數(shù)值為0的元素?cái)?shù)目遠(yuǎn)遠(yuǎn)多于非0元素的數(shù)目，并且非0元素分布沒有規(guī)律時(shí)，則稱該矩陣為稀疏矩陣；與之相反，若非0元素?cái)?shù)目占大多數(shù)時(shí)，則稱該矩陣為稠密矩陣。定義非零元素的總數(shù)比上矩陣所有元素的總數(shù)為矩陣的稠密度。 ## 2、處理方式 ``` 1)、記錄數(shù)組一共有幾行幾列，有多少個(gè)不同的值 2)、把具有不同值的元素的行列及值記錄在稀疏數(shù)組中，可以縮小程序代碼的復(fù)雜度。 ``` ## 3、圖解描述 ``` 稀疏數(shù)組表示 3 4 4 二維數(shù)組，3行，4列，4個(gè)非0的值； 1 2 2 一行，2列的值是2； 1 3 3 一行，3列的值是3； …以此類推 ``` ## 4、五子棋場景 ``` 使用稀疏數(shù)組描述 行 列 值 11 11 2 1 2 1 2 3 2 ``` # 二、代碼實(shí)現(xiàn) ## 1、轉(zhuǎn)換流程 二維數(shù)組轉(zhuǎn)稀疏數(shù)組 ``` 1)、遍歷二維數(shù)組，得到非零元素的個(gè)數(shù) 2)、創(chuàng)建稀疏數(shù)組 3)、二維數(shù)組的非零元素寫入稀疏數(shù)組 ``` 稀疏數(shù)組轉(zhuǎn)二維數(shù)組 ``` 1)、讀取稀疏數(shù)組的首行，創(chuàng)建二維數(shù)組 2)、根據(jù)稀疏數(shù)組描述的有效元素，給二維數(shù)組賦值 ``` ## 2、代碼實(shí)現(xiàn) 1)、核心流程 ``` 1、棋盤：基于二維數(shù)組 2、二維數(shù)組轉(zhuǎn)稀疏數(shù)組 3、稀疏數(shù)組轉(zhuǎn)二維數(shù)組 ``` 2)、方法一：生成二維數(shù)組 ``` public static int[][] printChess (){ // 二維數(shù)組表示 11 * 11 的棋盤，0表示沒有棋,1表示 黑, 2 表示藍(lán) 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)、方法二：轉(zhuǎn)為稀疏數(shù)組 ``` public static int[][] convertTwoArray (int chessArray[][]){ // 有效元素：先遍歷二維數(shù)組 得到非0數(shù)據(jù)的個(gè)數(shù) 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 // 遍歷二維數(shù)組，將非0的值存放到稀疏數(shù)組中 // unZeroCount 用于記錄是第幾個(gè)非0數(shù)據(jù),也就是稀疏數(shù)組的行 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; } } } // 輸出稀疏數(shù)組的形式 for (int i = 0; i < sparseArray.length; i++) { System.out.printf("%d\t%d\t%d\t\n", sparseArray, sparseArray, sparseArray); } return sparseArray ; } ``` 4)、方法三：轉(zhuǎn)為二維數(shù)組 ``` public static void convertSparseArray (int sparseArray[][]){ // 讀取稀疏數(shù)組首行創(chuàng)建二維數(shù)組==>> int chessArray[][] = new int; int chessArray[][] = new int[sparseArray][sparseArray] ; // 非零元素賦值給二維數(shù)組 for(int i = 1; i < sparseArray.length; i++) { // 幾行、幾列、是什么值 chessArray[sparseArray][sparseArray] = sparseArray; } // 打印二維數(shù)組 for (int[] row : chessArray) { for (int data : row) { System.out.printf("%d\t", data); } System.out.println(); } } ``` 5)、主程序調(diào)用 ``` public static void main(String[] args) { // 棋盤：基于二維數(shù)組 int chessArray[][] = printChess () ; System.out.println("=========================="); // 二維數(shù)組轉(zhuǎn)稀疏數(shù)組 int sparseArray[][] = convertTwoArray(chessArray) ; System.out.println("=========================="); // 稀疏數(shù)組轉(zhuǎn)二維數(shù)組 convertSparseArray(sparseArray); } ``` 三、源代碼地址 ``` GitHub·地址 https://github.com/cicadasmile/model-arithmetic-parent GitEE·地址 https://gitee.com/cicadasmile/model-arithmetic-parent ```