稀疏陣列(sparse array)：
定義：如果一個陣列(包括多維陣列)中的大部分元素為0（或者為同一個值的陣列時），為了節約空間，可以使用稀疏陣列來保存該陣列，
功能：
（1）記錄原始陣列總共有幾行幾列，以及有多少個有效值（下圖中右邊稀疏陣列第0行），
（2）通過一個小規模的陣列記錄原始陣列中有效值的行，列和該值（下圖中右邊稀疏陣列第0行之后），從而縮小原始陣列的規模，
稀疏陣列實體：
應用場景：
需求：簡單模擬一個五子棋盤，并將稀疏陣列存盤以及恢復原來的二維陣列
思路分析：
原始二維陣列 ---> 稀疏陣列：
1.遍歷原始二維陣列，得到陣列中有效值 sum；
2.根據sum創建稀疏陣列sparse array；
3.將二維陣列中的有效值存到稀疏陣列，
稀疏陣列 --> 恢復二維陣列：
1.讀取稀疏陣列第一行，根據稀第一行陣列創建二維陣列；
2.讀取稀疏陣列第一行之后的資料，并賦給二維陣列，
Java代碼實作
1 package Work.DataStructure; 2 3 import java.io.*; 4 5 /** 6 * 稀疏陣列案例：棋盤案例 7 */ 8 public class SparseArray { 9 private int[][] arr1; 10 private int[][] arr2; 11 private int[][] sparseArr; 12 private static int sum; 13 public static void main(String[] args) { 14 SparseArray sa = new SparseArray(); 15 sa.arr1(); 16 sa.sparseArr(); 17 sa.arr2(); 18 try { 19 sa.sparseArrFromIo(sum); 20 }catch(Exception e){e.printStackTrace();} 21 } 22 /** 23 * 創建初始二維陣列arr1 24 */ 25 public void arr1(){ 26 arr1 = new int[11][11]; 27 arr1[0][0] = 1; 28 arr1[2][3] = 2; 29 arr1[3][5] = 1; 30 arr1[10][10] = 2; 31 for(int i = 0; i<arr1.length;i++){ 32 for(int j =0;j<arr1[i].length;j++){ 33 if(arr1[i][j] != 0){ 34 sum++; 35 } 36 } 37 } 38 System.out.println("========這里是原始二維陣列========"); 39 for(int[] row : arr1){ 40 for(int data : row){ 41 System.out.printf("%d\t",data); 42 } 43 System.out.println(); 44 } 45 System.out.println("sum: "+sum); 46 } 47 48 /** 49 * 二維陣列 --> 稀疏陣列 50 */ 51 public void sparseArr(){ 52 int count =0 ; 53 //根據二維陣列中的有效值創建稀疏陣列 54 sparseArr = new int[sum+1][3]; 55 sparseArr[0][0] = 11; 56 sparseArr[0][1] = 11; 57 sparseArr[0][2] = sum; 58 //將原始二維陣列的有效值添存入稀疏陣列中 59 System.out.println("=======這里是稀疏陣列========"); 60 for(int i = 0;i<arr1.length;i++){ 61 for(int j =0;j<arr1[i].length;j++){ 62 if( arr1[i][j] != 0) { 63 count++; 64 sparseArr[count][0] = i; 65 sparseArr[count][1] = j; 66 sparseArr[count][2] = arr1[i][j]; 67 } 68 } 69 } 70 for(int i = 0; i<sparseArr.length;i++){ 71 System.out.printf("%d\t%d\t%d\t\n",sparseArr[i][0],sparseArr[i][1],sparseArr[i][2]); 72 } 73 try{ 74 sparseArrToIo(sparseArr); 75 } 76 catch(Exception e){e.printStackTrace();} 77 } 78 79 /** 80 * 稀疏陣列 --> 二維陣列 81 */ 82 public void arr2(){ 83 //根據稀疏陣列的第一行資料創建二維陣列 84 arr2 = new int[sparseArr[0][0]][sparseArr[0][1]]; 85 //根據稀疏陣列第一行之后的資料將二維陣列有效值還原 86 for(int i =1 ;i <sparseArr.length;i++){ 87 arr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2]; 88 } 89 System.out.println("========這里是還原后的二維陣列========"); 90 for( int[] row :arr2){ 91 for(int data: row){ 92 System.out.printf("%d\t",data); 93 } 94 System.out.println(); 95 } 96 } 97 98 /** 99 *將稀疏陣列存入磁盤 100 */ 101 public void sparseArrToIo(int[][] sparseArr) throws Exception{ 102 File file = new File("D:\\4-Code\\sparseArr.txt"); 103 if(! file.exists()){ 104 file.createNewFile(); 105 } 106 FileOutputStream fos = new FileOutputStream(file); 107 StringBuilder sb = new StringBuilder(); 108 for(int i = 0; i < sparseArr.length;i++){ 109 sb.append(sparseArr[i][0]+" "+sparseArr[i][1]+" "+sparseArr[i][2]+"\n"); 110 } 111 fos.write(sb.toString().getBytes()); 112 fos.flush(); 113 fos.close(); 114 } 115 /** 116 * 讀取磁盤中的稀疏陣列 117 */ 118 public static void sparseArrFromIo(int row) throws Exception{ 119 System.out.println("========這里是從磁盤中讀取的稀疏陣列========"); 120 int[][] sarr = new int[row+1][3]; 121 FileReader fr = new FileReader("D:\\4-Code\\sparseArr.txt"); 122 BufferedReader br = new BufferedReader(fr); 123 String temp = ""; 124 String[] tarr = null; 125 int count =0; 126 while((temp = br.readLine())!=null){ 127 tarr = temp.split(" "); 128 sarr[count][0] = Integer.valueOf(tarr[0]); 129 sarr[count][1] = Integer.valueOf(tarr[1]); 130 sarr[count][2] = Integer.valueOf(tarr[2]); 131 count++; 132 } 133 for(int i =0;i<sarr.length;i++){ 134 System.out.printf("%d\t%d\t%d\t\n",sarr[i][0],sarr[i][1],sarr[i][2]); 135 } 136 } 137 }
運行結果：
1 ========這里是原始二維陣列======== 2 1 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 2 0 0 0 0 0 0 0 5 0 0 0 0 0 1 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 11 0 0 0 0 0 0 0 0 0 0 0 12 0 0 0 0 0 0 0 0 0 0 2 13 sum: 4 14 =======這里是稀疏陣列======== 15 11 11 4 16 0 0 1 17 2 3 2 18 3 5 1 19 10 10 2 20 ========這里是還原后的二維陣列======== 21 1 0 0 0 0 0 0 0 0 0 0 22 0 0 0 0 0 0 0 0 0 0 0 23 0 0 0 2 0 0 0 0 0 0 0 24 0 0 0 0 0 1 0 0 0 0 0 25 0 0 0 0 0 0 0 0 0 0 0 26 0 0 0 0 0 0 0 0 0 0 0 27 0 0 0 0 0 0 0 0 0 0 0 28 0 0 0 0 0 0 0 0 0 0 0 29 0 0 0 0 0 0 0 0 0 0 0 30 0 0 0 0 0 0 0 0 0 0 0 31 0 0 0 0 0 0 0 0 0 0 2 32 ========這里是從磁盤中讀取的稀疏陣列======== 33 11 11 4 34 0 0 1 35 2 3 2 36 3 5 1 37 10 10 2
小結：
通過該實體可得知，稀疏陣列直觀的功能實作思路主要是通過一個小規模的（固定列）二維陣列儲存另一個含有很多無效資料的規模大（重復資料）的陣列，對于陣列的操作更多的是通過回圈來實作兩個陣列之間的轉換，類似壓縮檔案和解壓檔案的程序；對于資料存入磁盤和從磁盤中讀取資料則是用到基本的IO流知識，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/33621.html
標籤：Java
上一篇：LeetCode–斐波那契數列
下一篇：PHP獲取多維資料的交集與差集