首先來舉個栗子,來說明一下稀疏數組是什麼。
玩五子棋的時候我們需要存檔,假如是11*11的五子棋布局。我們要對如下戰況進行存檔
我們先想一下如果用二維數組把它存起來是不是需要用到一個11行11列的數組呢。答案肯定是毫無疑問了。
想一下如果用我們用chessArr[11][11] 這樣的數組是不是很浪費資源呢,因為我們隻需要存黑子第二行第三列也就是chessArr[1][2]和藍子第三行第四列chessArr[3][2],隻需要記錄這兩個棋子。如果用11*11的二維數組就完全是大材小用了。
那接下來我們就可以使用稀疏數組來記錄相應的資料了。
稀疏數組
0:代表沒有棋子,1:代表黑子,2:代表藍子
如果一個數組(包括多元數組)中的大部分元素為0,或者為同一個值的數組時,可以使用稀疏數組來儲存該數組,節約空間。
一般來說,稀疏數組的處理方法是:
1.記錄數組一共有幾行幾列,有多少個不同的數值。
2.把具有不同值的元素的行列及記錄在一個小規模的數組中,進而縮小程式的規模。
稀疏數組的列是固定的3列(下面畫個圖展示一下)
右邊表示的是一個三行三列的二維數組用來記錄原始數組的行列和值
第一行是用來記錄原始數組有幾行幾列以及幾個不同的值,如圖:記錄的是該數組有11行11列以及2個不同的值(即藍子與黑子)
第二行則記錄的是黑子在原始數組的位置[1][2]以及其值1
第三行就是記錄的藍子在原始數組的位置[2][3]以及其值2
- 二維數組轉稀疏數組的思路
周遊二維數組,得到有效個數sum。
根據sum就可以建立稀疏數組sparseArr int[sum+1][3]
将二維數組的有效資料存入稀疏數組。
- 稀疏數組轉原始的二維數組思路:
先讀取稀疏數組的第一行,根據第一行資料,建立原始的二維數組。
在讀取稀疏數組後幾行的資料,并賦給原始的二維數組即可。
代碼:
package com.blh.sparseArrary;
public class SparseArrary {
public static void main(String[] args) {
//建立一個原始二維數組11*11
//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();
}
//将二維數組轉稀疏數組
//1、先周遊二維數組得到非零的資料的個數
int sum =0;
for(int i=0;i<11;i++) {
for(int j = 0; j<11;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;
//周遊二維數組,将非零的值存到sparseArr中
int count = 0;//用于記錄是第幾個非零資料
for(int i=0;i<11;i++) {
for(int j = 0; j<11;j++) {
if(chessArr1[i][j]!=0){
count++;
sparseArr[count][0] = i;
sparseArr[count][1] = j;
sparseArr[count][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]);
}
System.out.println();
//将稀疏數組恢複成原始的二維數組
int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
System.out.println("----------恢複後的數組---------------------------");
//将稀疏數組後幾行資料(從第二行開始),指派給原始的二維數組即可
for (int i = 1; i < sparseArr.length; i++) {
chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
}
for(int[] row : chessArr2) {
for (int data : row) {
System.out.printf("%d\t",data);
}
System.out.println();
}
}
}
結果: