資料結構與演算法之稀疏陣列

1.簡單理解稀疏陣列

可以把稀疏陣列理解為只保存有效資料的一種陣列，其針對的自然是有大量無用資料的陣列，直接上圖

原陣列

稀疏陣列

稀疏陣列第一行類似于表格的表頭，依次代表原陣列的行數、列數、非零數個數（用零代表無用資料），第一行之下的每一行都代表有一個非零數，第一列的數字代表非零數的行下標（陣列下標從0開始），第二列數字代表非零數的列下標，第三列數就是非零數的實際值，

2.用Java代碼實作普通二維陣列到稀疏陣列的轉換及其逆程序

 1 public class SparseArray {
 2     public static void main(String[] args) throws IOException, ClassNotFoundException {
 3         //創建一個二維陣列
 4         int arr1[][] = new int[11][11];
 5         arr1[1][2] = 1;
 6         arr1[2][3] = 2;
 7         arr1[2][4] = 1;
 8 
 9         //輸出列印
10         System.out.println("新的二維陣列：");
11         for (int[] rows : arr1) {
12             for (int i : rows) {
13                 System.out.print(i+"\t");
14             }
15             System.out.println();
16         }
17         System.out.println();
18 
19         //獲取二維陣列的行數、列數
20         int rowNum = arr1.length;
21         int colNum = arr1[0].length;
22         //獲取非零數個數
23         int valNum = 0;
24         for (int[] rows : arr1) {
25             for (int i : rows) {
26                 if (i != 0){
27                     valNum++;
28                 }
29             }
30         }
31 
32         //依斬訓取的資料創建一個稀疏陣列
33         int sparseArr[][] = new int[valNum+1][3];
34 
35         //設定第一行資料
36         sparseArr[0][0] = rowNum;
37         sparseArr[0][1] = colNum;
38         sparseArr[0][2] = valNum;
39 
40         //計數器
41         int count = 0;
42         for (int i = 0; i < arr1.length; i++) {
43             for (int j = 0; j < arr1[i].length; j++) {
44                 if (arr1[i][j] != 0){
45                     count++;
46                     //第n個非零數在稀疏陣列中的行下標為n+1
47                     sparseArr[count][0] = i;
48                     sparseArr[count][1] = j;
49                     sparseArr[count][2] = arr1[i][j];
50                 }
51             }
52         }
53 
54         //列印稀疏陣列
55         for (int[] rows : sparseArr) {
56             for (int i : rows) {
57                 System.out.print(i+"\t");
58             }
59             System.out.println();
60         }
61         System.out.println();
62 
63         //用物件輸出流寫入檔案中
64         ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("G:\\Files\\test\\sparseArr.txt"));
65         oos.writeObject(sparseArr);
66         oos.close();
67 
68         //用物件輸入流讀入檔案中的物件
69         ObjectInputStream ois = new ObjectInputStream(new FileInputStream("G:\\Files\\test\\sparseArr.txt"));
70         int[][] sparseArr2 = (int[][]) ois.readObject();
71         ois.close();
72 
73         //列印驗證資料還原
74         System.out.println("還原的稀疏陣列：");
75         for (int[] rows : sparseArr2) {
76             for (int i : rows) {
77                 System.out.print(i+"\t");
78             }
79             System.out.println();
80         }
81         System.out.println();
82 
83 
84         //將稀疏陣列還原為原來的二維陣列
85         int arr2[][] = new int[sparseArr2[0][0]][sparseArr2[0][1]];
86         for (int i = 1; i < sparseArr2.length; i++) {
87             arr2[sparseArr2[i][0]][sparseArr2[i][1]] = sparseArr2[i][2];
88         }
89 
90         //再次列印驗證
91         for (int[] rows : arr2) {
92             for (int i : rows) {
93                 System.out.print(i+"\t");
94             }
95             System.out.println();
96         }
97 
98     }
99 }

標籤：Java

上一篇：作為一個Java程式員連簡單的分頁功能都會寫，你好意思嘛！

下一篇：Spring 的Controller 是單例or多例