Java資料結構與算法(二、稀疏數組的介紹)

1. 稀疏數組是什麼？

當一個數組中打大部分元素為 0， 或者為 同一個值 時，可以使用 稀疏數組 來儲存該數組。

2. 可以解決什麼問題？

五子棋 程式中，有存盤退出和徐上盤的功能。因為儲存棋盤的二維數組中存在很多隻都是預設值0，是以記錄了很多 沒有意義的資料。 在這裡就可以使用稀疏數組來解決該問題，在儲存資料中起到 壓縮空間 的作用。

3. 是如何壓縮空間的？

思路分析：   1）記錄數組一共有幾行幾列，有多少個不同的值。

  2）把具有不同值的元素的行列及值記錄在一個小規模的數組中，進而縮小程式的規模。

4. 代碼實作：

public static void main(String[] args) {
		System.out.println("普通的二維數組：");
		// 假設這是個 8x8 的棋盤
		int[][] array = new int[6][7];
		// 給棋盤上放棋子
		array[0][3] = 2;
		array[0][6] = 5;
		array[1][1] = 1;
		array[1][5] = 7;
		array[2][3] = 6;
		array[3][5] = 9;
		array[4][0] = 1;
		array[5][2] = 8;
		// 列印看一下
		for (int i = 0; i < array.length; i++) {
			int[] js = array[i];
			for (int j = 0; j < js.length; j++) {
				System.out.print(array[i][j] + " ");
			}
			System.out.println();
		}
		
		// 轉換思路分析：
		// 1）記錄數組一共有幾行幾列，有多少個不同的值。
		// 2）把具有不同值的元素的行列及值記錄在一個小規模的數組中，進而縮小程式的規模。		
		System.out.println("\n轉為稀疏數組：");
		int sum = 0;// 記錄值總數的變量
		for (int i = 0; i < array.length; i++) {
			int[] js = array[i];
			for (int j = 0; j < js.length; j++) {
				if(array[i][j] != 0) {
					sum++;// 值總數++
				}
			}
		}
		// 按照求出的值總數 建立稀疏數組的行大小，列為3是分别儲存 行列值 三種屬性的
		int[][] sparseArray = new int[sum+1][3];
		// 數組中第0行，頭空間，用來儲存棋盤 行高的總大小 和 值總數
		sparseArray[0][0] = array.length;
		sparseArray[0][1] = array[1].length;
		sparseArray[0][2] = sum;
		// 把棋盤中不同在值存進稀疏數組中
		int num = 1;
		for (int i = 0; i < array.length; i++) {
			int[] js = array[i];
			for (int j = 0; j < js.length; j++) {
				if(array[i][j] != 0) {
					sparseArray[num][0] = i;
					sparseArray[num][1] = j;
					sparseArray[num][2] = array[i][j];
					num++;
				}
			}
		}
		
		// 列印看一下
		for (int i = 0; i < sparseArray.length; i++) {
			int[] js = sparseArray[i];
			for (int j = 0; j < js.length; j++) {
				System.out.print(sparseArray[i][j] + " ");
			}
			System.out.println();
		}
		
		// 總結語錄
		String summarize = "可以看出二維數組一共需要6*7=42個空間，\n"
				+ "而稀疏數組轉換後隻占用了3x9=27個空間，\n"
				+ "當然這隻适用于一個數組要儲存有很多相同值的時候";
		System.out.println("\n"+summarize);
	}
}
           

5. 列印結果：