數據結構(一)-稀疏矩陣

• 2020 年 9 月 13 日
• 筆記
• 數據結構和算法

圖示原始數組和稀疏數組的轉換過程

代碼實現

public class SparseArray {

	public static void main(String[] args) throws Exception {
		// 1. 創建原始數組
		int[][] chessArr1 = new int[11][11];
		chessArr1[1][2] = 1;
		chessArr1[2][3] = 2;
		chessArr1[4][5] = 2;

		// 1.1 遍歷輸出原始數組
		System.out.println("原始數組：");
		travarseArrayPrint(chessArr1);

		// 2. 將原始數組轉換為稀疏數組
		// 2.1 定義變量記錄原始數組中非0元素的個數
		int sum = 0;
		for (int i = 0; i < chessArr1.length; i++) {
			for (int j = 0; j < chessArr1[0].length; j++) {
				if (chessArr1[i][j] != 0) {
					sum++;
				}
			}
		}
		// 2.2 創建稀疏數組並給稀疏數組賦值
		int[][] sparseArr = new int[sum + 1][3];
		// 2.3 給稀疏數組的第一行賦值
		sparseArr[0][0] = chessArr1.length;
		sparseArr[0][1] = chessArr1[0].length;
		sparseArr[0][2] = sum;
		// 2.4 定義變量記錄稀疏數組的行數
		int count = 0;
		// 2.5 給稀疏數組第一行之後的行賦值
		for (int i = 0; i < chessArr1.length; i++) {
			for (int j = 0; j < chessArr1[0].length; j++) {
				if (chessArr1[i][j] != 0) {
					count++;
					sparseArr[count][0] = i;
					sparseArr[count][1] = j;
					sparseArr[count][2] = chessArr1[i][j];

				}
			}
		}
		// 2.6 遍歷輸出稀疏數組
		System.out.println("稀疏數組：");
		travarseArrayPrint(sparseArr);
		// 2.7 將稀疏數組存入到磁盤文件
		File file = new File("data.txt");
		FileWriter fw = new FileWriter(file);
		for (int[] row : sparseArr) {
			for (int i : row) {
				fw.write(i + "\t");
			}
			fw.write("\r\n");
		}
		fw.close();

		// 3. 恢復原始數組
		// 3.1 從磁盤文件中讀取稀疏數組
		BufferedReader br = new BufferedReader(new FileReader("data.txt"));
		// 記錄讀取的單行字符串
		String line;
		// 記錄讀取的當前的行數
		int row = 0;
		while((line = br.readLine()) != null) {
			row++;
		}
		br.close();
		
		// 3.2 創建稀疏數組
		BufferedReader br1 = new BufferedReader(new FileReader("data.txt"));
		int[][] sparseArr1 = new int[row][3];
		row = 0;
		while((line = br1.readLine()) != null) {
			String[] temp = line.split("\t");
			for(int i = 0; i < temp.length; i++) {
				sparseArr1[row][i] = Integer.parseInt(temp[i]);
			}
			row++;
		}
		br1.close();
		System.out.println("從磁盤讀進來的稀疏數組：");
		travarseArrayPrint(sparseArr1);
		// 3.3創建原始數組並根據從磁盤讀取的稀疏數組恢復原始數組
		int[][] chessArr2 = new int[sparseArr1[0][0]][sparseArr1[0][1]];
		for (int i = 1; i < sparseArr1.length; i++) {
			for (int j = 0; j < sparseArr1[0].length; j++) {
				chessArr2[sparseArr1[i][0]][sparseArr1[i][1]] = sparseArr1[i][2];
			}
		}

		// 3.4 遍歷輸出恢復之後的原始數組
		System.out.println("恢復之後的原始數組：");
		travarseArrayPrint(chessArr2);
	}
	
	
	private static void travarseArrayPrint(int[] ...array) {
		for (int[] row : array) {
			for (int i : row) {
				System.out.printf("%d\t", i);
			}
			System.out.println();
		}
	}
}