資料結構與演演算法（一）： 稀疏陣列
2023-07-04 06:00:31
問題引入
在五子棋遊戲或類似的遊戲中，我們可以把整個棋盤想象成是一個有規律的二維陣列，其值由0、1、2三個數位組成，0代表空白區域，1代表白子，2代表黑子。這種情況：即當一個陣列中大部分元素為0或者為同一值時，儲存該陣列資料可以使用稀疏陣列來對原始陣列進行精簡，以減少原始陣列中無用資料所佔的空間。
普通二維陣列與稀疏陣列
下圖表示的是一個12×12大小的二維陣列與之對應的稀疏陣列表示，其中普通二維陣列中有11個有效值，其餘的全為無用資料0填充。稀疏陣列的第一行表示有一個12行12列且11個有效數值的二維陣列。第二行表示，二維陣列中的第2行（從0開始）、第4列的數值為1。從第二行開始，每一行表示的都是二維陣列中數值的行列位置和真實值。
程式碼實現
生成二維陣列
private int[][] generatorArray() {
// 初始化二維陣列
int[][] arr = new int[12][12];
// 二維陣列賦值
arr[2][4] = 1;
arr[2][5] = 1;
arr[3][4] = 1;
arr[3][5] = 1;
arr[3][6] = 2;
arr[3][7] = 2;
arr[4][5] = 2;
arr[4][6] = 1;
arr[5][5] = 1;
arr[5][6] = 2;
arr[5][7] = 2;
System.out.println("原始二維陣列為：");
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++) {
System.out.print(arr[i][j] + "\t");
}
System.out.println();
}
System.out.println();
return arr;
}
執行結果：
原始二維陣列為：
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0 0 0
0 0 0 0 1 1 2 2 0 0 0 0
0 0 0 0 0 2 1 0 0 0 0 0
0 0 0 0 0 1 2 2 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
二維陣列轉換成稀疏陣列
private int[][] toSparseArray(int[][] originalArray) {
// 獲得原始陣列行列、有效值初始化稀疏陣列
int sum = 0;
for (int i = 0; i < originalArray.length; i++) {
for (int j = 0; j < originalArray[i].length; j++) {
if (originalArray[i][j] != 0) {
sum += 1;
}
}
}
// 稀疏陣列length為有效值個數+1
int[][] sparseArray = new int[sum+1][3];
// 行
sparseArray[0][0] = originalArray.length;
// 列
sparseArray[0][1] = originalArray[0].length;
// 有效值個數
sparseArray[0][2] = sum;
// 賦值
int count = 0;
for (int i = 0; i < originalArray.length; i++) {
for (int j = 0; j < originalArray[i].length; j++) {
if (originalArray[i][j] != 0) {
count++;
sparseArray[count][0] = i;
sparseArray[count][1] = j;
sparseArray[count][2] = originalArray[i][j];
}
}
}
// 輸出稀疏陣列
System.out.println("轉換後的稀疏陣列為：");
for (int i = 0; i < sparseArray.length; i++) {
for (int j = 0; j < sparseArray[i].length; j++) {
System.out.print(sparseArray[i][j] + "\t");
}
System.out.println();
}
System.out.println();
return sparseArray;
}
執行結果：
轉換後的稀疏陣列為：
12 12 11
2 4 1
2 5 1
3 4 1
3 5 1
3 6 2
3 7 2
4 5 2
4 6 1
5 5 1
5 6 2
5 7 2
稀疏陣列轉換為二維陣列
private int[][] toOriginalArray(int[][] sparseArray) {
// 初始化原始陣列
int[][] originalArray = new int[sparseArray[0][0]][sparseArray[0][1]];
// 從第二個值開始，因為第一個值存的是原始陣列的行列、有效值個數等資訊
for (int i = 1; i < sparseArray.length; i++) {
// 由稀疏陣列給原始陣列賦值
originalArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
}
System.out.println("轉換後的二維陣列為：");
for (int i = 0; i < originalArray.length; i++) {
for (int j = 0; j < originalArray[i].length; j++) {
System.out.print(originalArray[i][j] + "\t");
}
System.out.println();
}
return originalArray;
}
實踐運用
在真實開發中，一般是將稀疏陣列資料在資料庫或者檔案中進行儲存，這裡我使用 fastjson2 將稀疏陣列轉換成 JSON 字串之後儲存到電腦本地（二維陣列轉稀疏陣列），再從本地讀取檔案內容進行解析（稀疏陣列轉二維陣列）。儲存到資料庫也是同理的操作。
儲存到檔案
/**
* 將JSON字串儲存為檔案
* @param jsonString 轉換後的稀疏陣列JSON字串
* @param fileName 電腦本地檔案
*/
private void toFile(String jsonString, String fileName) {
File file = new File(fileName);
FileWriter fileWriter = null;
if (!file.exists()) {
try {
file.createNewFile();
fileWriter = new FileWriter(file);
char[] chars = jsonString.toCharArray();
fileWriter.write(chars);
fileWriter.flush();
} catch (IOException ioException) {
ioException.printStackTrace();
} finally {
try {
fileWriter.close();
} catch (IOException e) {
throw new RuntimeException(e);
}
}
}
}
從檔案讀取並解析
/**
* 從檔案讀取內容
* @param fileName
* @return
* @throws IOException
*/
private String readFile(String fileName) throws IOException {
File file = new File(fileName);
FileReader reader = new FileReader(file);
BufferedReader bufferedReader = new BufferedReader(reader);
String line = null;
System.out.println("檔案讀取內容為：");
while ((line = bufferedReader.readLine()) != null) {
System.out.println(line);
System.out.println();
return line;
}
reader.close();
bufferedReader.close();
return line;
}
/**
* 由JSON字串轉換成原始二維陣列
* @param jsonString
* @return
*/
private int[][] stringToOriginArray(String jsonString) {
JSONArray objects = JSON.parseArray(jsonString);
JSONArray s = (JSONArray) objects.get(0);
// 初始化原始陣列
int[][] originalArray = new int[(int)s.get(0)][(int)s.get(1)];
// 從第二個值開始，因為第一個值存的是原始陣列的行列、有效值個數等資訊
for (int i = 1; i < objects.size(); i++) {
JSONArray se = (JSONArray) objects.get(i);
originalArray[(int)se.get(0)][(int)se.get(1)] = (int)se.get(2);
}
System.out.println("JSON字串轉換為二維陣列：");
for (int i = 0; i < originalArray.length; i++) {
for (int j = 0; j < originalArray[i].length; j++) {
System.out.print(originalArray[i][j] + "\t");
}
System.out.println();
}
return originalArray;
}