稀疏陣列(Sparse Array)
實際案例
五子棋小游戲中實作存盤功能，棋盤用二維陣串列示，以0作為空落棋點，1為白棋，2為黑棋，
因為該二維陣列很多值是默認值0，因此記錄了許多沒有意義的資料，保存棋盤時就使用稀疏陣列來壓縮存盤，
稀疏陣列介紹
當一個陣列中大部分元素為同一個值時，可以使用稀疏陣列來保存該陣列，
處理方法
-
記錄陣列一共有幾行幾列，有多少個不同的值，
-
把具有不同值的元素的行列及值記錄在一個小規模的陣列中，從而縮小程式規模，
代碼實作
package com.sparseArray;
/*稀疏陣列實體
* 1.創建一個11*11的五子棋棋盤
* 2.給[1][2]和[2][3]處分別賦值1，2
* 3.將棋盤轉化為稀疏陣列存盤
* */
public class SparseArray {
public static void main(String[] args) {
//棋盤默認值為0，用1來表示白棋，2表示黑棋
int chessArr1[][] = new int[11][11];
chessArr1[1][2] = 1;
chessArr1[2][3] = 2;
System.out.println("原始的二位陣列：");
for(int[] row : chessArr1) {
for(int data : row) {
System.out.printf("%d\t" , data);
}
System.out.println();
}
//遍歷原始陣列得到非零元素個數
int sum = 0;
for (int i = 0; i < chessArr1.length; i++) {
for (int j = 0; j < chessArr1.length; j++) {
if(chessArr1[i][j] != 0)
sum++;
}
}
//創建稀疏陣列
int sparseArr[][] = new int[sum+1][3];
//稀疏陣列第一行存盤原始陣列行數、列數、非零元素個數
sparseArr[0][0] = 11;
sparseArr[0][1] = 11;
sparseArr[0][2] = sum;
//遍歷原始陣列非零元素并填充到稀疏陣列中
int cnt = 0;
for (int i = 0; i < chessArr1.length; i++) {
for (int j = 0; j < chessArr1.length; j++) {
if(chessArr1[i][j] != 0) {
cnt++;
sparseArr[cnt][0] = i;
sparseArr[cnt][1] = j;
sparseArr[cnt][2] = chessArr1[i][j];
}
}
}
//輸出稀疏陣列
System.out.println();
System.out.println("稀疏陣列：");
for (int i = 0; i < sparseArr.length; i++) {
System.out.printf("%d\t%d\t%d\t\n", sparseArr[i][0],sparseArr[i][1],sparseArr[i][2]);
}
//恢復原始陣列
//1.讀取稀疏陣列的第一行第一列資料
int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
//2.讀取稀疏陣列中有效資料
for (int i = 1; i < sparseArr.length; i++) {
chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
}
//3.輸出恢復陣列
System.out.println();
System.out.println("恢復后的陣列：");
for (int i = 0; i < chessArr2.length; i++) {
for (int j = 0; j < chessArr2.length; j++) {
System.out.printf("%d\t",chessArr2[i][j]);
}
System.out.println();
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/69370.html
標籤：Java