問題引入
在五子棋游戲或類似的游戲中，我們可以把整個(gè)棋盤想象成是一個(gè)有規(guī)律的二維數(shù)組，其值由0、1、2三個(gè)數(shù)字組成，0代表空白區(qū)域，1代表白子，2代表黑子。這種情況：即當(dāng)一個(gè)數(shù)組中大部分元素為0或者為同一值時(shí)，存儲(chǔ)該數(shù)組數(shù)據(jù)可以使用稀疏數(shù)組來對(duì)原始數(shù)組進(jìn)行精簡(jiǎn)，以減少原始數(shù)組中無用數(shù)據(jù)所占的空間。
普通二維數(shù)組與稀疏數(shù)組
下圖表示的是一個(gè)12×12大小的二維數(shù)組與之對(duì)應(yīng)的稀疏數(shù)組表示，其中普通二維數(shù)組中有11個(gè)有效值，其余的全為無用數(shù)據(jù)0填充。稀疏數(shù)組的第一行表示有一個(gè)12行12列且11個(gè)有效數(shù)值的二維數(shù)組。第二行表示，二維數(shù)組中的第2行（從0開始）、第4列的數(shù)值為1。從第二行開始，每一行表示的都是二維數(shù)組中數(shù)值的行列位置和真實(shí)值。
代碼實(shí)現(xiàn)
生成二維數(shù)組
private int[][] generatorArray() {
// 初始化二維數(shù)組
int[][] arr = new int[12][12];
// 二維數(shù)組賦值
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("原始二維數(shù)組為：");
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;
}
運(yùn)行結(jié)果：
原始二維數(shù)組為：
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
二維數(shù)組轉(zhuǎn)換成稀疏數(shù)組
private int[][] toSparseArray(int[][] originalArray) {
// 獲得原始數(shù)組行列、有效值初始化稀疏數(shù)組
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;
}
}
}
// 稀疏數(shù)組length為有效值個(gè)數(shù)+1
int[][] sparseArray = new int[sum+1][3];
// 行
sparseArray[0][0] = originalArray.length;
// 列
sparseArray[0][1] = originalArray[0].length;
// 有效值個(gè)數(shù)
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];
}
}
}
// 輸出稀疏數(shù)組
System.out.println("轉(zhuǎn)換后的稀疏數(shù)組為：");
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;
}
運(yùn)行結(jié)果：文章來源：http://www.zghlxwxcb.cn/news/detail-516236.html
轉(zhuǎn)換后的稀疏數(shù)組為：
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
稀疏數(shù)組轉(zhuǎn)換為二維數(shù)組
private int[][] toOriginalArray(int[][] sparseArray) {
// 初始化原始數(shù)組
int[][] originalArray = new int[sparseArray[0][0]][sparseArray[0][1]];
// 從第二個(gè)值開始，因?yàn)榈谝粋€(gè)值存的是原始數(shù)組的行列、有效值個(gè)數(shù)等信息
for (int i = 1; i < sparseArray.length; i++) {
// 由稀疏數(shù)組給原始數(shù)組賦值
originalArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
}
System.out.println("轉(zhuǎn)換后的二維數(shù)組為：");
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;
}
實(shí)踐運(yùn)用
在真實(shí)開發(fā)中，一般是將稀疏數(shù)組數(shù)據(jù)在數(shù)據(jù)庫(kù)或者文件中進(jìn)行保存，這里我使用 fastjson2 將稀疏數(shù)組轉(zhuǎn)換成 JSON 字符串之后保存到電腦本地（二維數(shù)組轉(zhuǎn)稀疏數(shù)組），再?gòu)谋镜刈x取文件內(nèi)容進(jìn)行解析（稀疏數(shù)組轉(zhuǎn)二維數(shù)組）。保存到數(shù)據(jù)庫(kù)也是同理的操作。文章來源地址http://www.zghlxwxcb.cn/news/detail-516236.html
保存到文件
/**
* 將JSON字符串保存為文件
* @param jsonString 轉(zhuǎn)換后的稀疏數(shù)組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);
}
}
}
}
從文件讀取并解析
/**
* 從文件讀取內(nèi)容
* @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("文件讀取內(nèi)容為：");
while ((line = bufferedReader.readLine()) != null) {
System.out.println(line);
System.out.println();
return line;
}
reader.close();
bufferedReader.close();
return line;
}
/**
* 由JSON字符串轉(zhuǎn)換成原始二維數(shù)組
* @param jsonString
* @return
*/
private int[][] stringToOriginArray(String jsonString) {
JSONArray objects = JSON.parseArray(jsonString);
JSONArray s = (JSONArray) objects.get(0);
// 初始化原始數(shù)組
int[][] originalArray = new int[(int)s.get(0)][(int)s.get(1)];
// 從第二個(gè)值開始，因?yàn)榈谝粋€(gè)值存的是原始數(shù)組的行列、有效值個(gè)數(shù)等信息
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字符串轉(zhuǎn)換為二維數(shù)組：");
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;
}
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法（一）： 稀疏數(shù)組的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
