什么時(shí)候使用稀疏數(shù)組
當(dāng)一個(gè)數(shù)組中大部分元素為零琉预，或者為用一個(gè)數(shù)值的時(shí)候董饰，可以使用稀疏數(shù)組來保存該數(shù)組；
稀疏數(shù)組的數(shù)據(jù)存儲(chǔ)方式：
- 稀疏數(shù)組是：行不確定圆米，列為三列的動(dòng)態(tài)數(shù)組卒暂；
- 第一行記錄數(shù)組中一共有幾列幾行，有多少個(gè)不同的數(shù)值娄帖；
- 其他行記錄有效數(shù)據(jù)的行列及值也祠，從而縮小數(shù)組程序的規(guī)模；
應(yīng)用實(shí)例（五子棋程序）
編寫的五子棋程序中近速，有存盤退出和續(xù)上盤的功能诈嘿。
分析問題:
因?yàn)樵摱S數(shù)組的很多值是默認(rèn)值0,因此記錄了很多沒有意義的數(shù)據(jù)->稀疏數(shù)組堪旧。
分析思路：
- 使用稀疏數(shù)組來保存前面的二維數(shù)組；
- 把稀疏數(shù)組存盤奖亚，并且可以從新恢復(fù)到原來的二維數(shù)組中淳梦；
-
整體思路：
- 二維數(shù)組 轉(zhuǎn)稀疏數(shù)組的思路
- 遍歷原來的二維數(shù)組，得到有效數(shù)據(jù)的總數(shù)（sum）昔字；
- 根據(jù)sum就可以創(chuàng)建 稀疏數(shù)組 new sparseArr Int[sum+1][3]爆袍；
- 將二維數(shù)組中的有效數(shù)據(jù)存儲(chǔ)到稀疏數(shù)組；
- 稀疏數(shù)組轉(zhuǎn)原始的二維數(shù)組的思路
- 先讀取稀疏數(shù)組的第一行李滴，根據(jù)第一行的數(shù)據(jù)創(chuàng)建原始的二維數(shù)組螃宙，比如：new chessArr = int[11][11]
- 在讀取稀疏數(shù)組中的后幾行數(shù)據(jù)，賦值給創(chuàng)建的二維數(shù)組即可所坯；
代碼實(shí)現(xiàn)(這里就不實(shí)現(xiàn)文件存儲(chǔ)了谆扎，主要使用數(shù)據(jù)結(jié)構(gòu))：
package com.daley.sparsearray;
import java.util.Arrays;
public class SparseArray {
public static void main(String[] args) {
// 創(chuàng)建一個(gè)原始的二維數(shù)組 11 * 11
// 0： 表示 沒有棋子，1：表示黑子 芹助，2：表示藍(lán)字
int[][] chessArr1 =new int[11][11];
chessArr1[1][2] = 1;
chessArr1[2][3] = 2;
// 輸出原始二維數(shù)組
for (int[] row : chessArr1){
for(int data :row){
System.out.printf("%d\t",data);
}
System.out.println();
}
// 二維數(shù)組 轉(zhuǎn) 稀疏數(shù)組
// 1.遍歷二維數(shù)組堂湖，得到非零數(shù)據(jù)的個(gè)數(shù)
int sum = 0;
for (int[] row : chessArr1){
for(int data :row){
if(data != 0 ){
sum ++ ;
}
}
}
// 2. 創(chuàng)建稀疏數(shù)組
int[][] sparseArr = new int[sum + 1][3];
// 給稀疏數(shù)組賦值
sparseArr[0][0] = chessArr1.length;
sparseArr[0][1] = chessArr1[0].length;
sparseArr[0][2] = sum;
// 3. 遍歷二維數(shù)組，將非零的數(shù)據(jù)存儲(chǔ)到稀疏數(shù)組中
int count = 0;
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];
}
}
}
// 輸出稀疏數(shù)組
System.out.println("\n得到的稀疏數(shù)組》》》》");
for (int i = 0; i < sparseArr.length; i++) {
System.out.printf("%d\t%d\t%d\n",sparseArr[i][0],sparseArr[i][1],sparseArr[i][2]);
}
// 稀疏數(shù)組 轉(zhuǎn) 二維數(shù)組
// 1. 創(chuàng)建二維數(shù)組
int[][] chessArr2 = new int[sparseArr[0][0]][sparseArr[0][1]];
for (int i = 1; i < sparseArr.length; i++) {
chessArr2[sparseArr[i][0]][sparseArr[i][1]] =sparseArr[i][2];
}
System.out.println("\n輸出恢復(fù)的二維數(shù)組》》》》");
// 輸出恢復(fù)的二維數(shù)組
for (int[] row : chessArr2){
for(int data :row){
System.out.printf("%d\t",data);
}
System.out.println();
}
}
}
