稀疏sparsearray數(shù)組
先看一個(gè)實(shí)際的需求
- 編寫(xiě)的五子棋程序中,有存盤(pán)退出和
續(xù)上盤(pán)的功能。
使用二維數(shù)組記錄棋盤(pán)
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 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 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 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
- 分析問(wèn)題:
因?yàn)樵摱S數(shù)組的很多值都是默認(rèn)值0,因此記錄了很多沒(méi)有意義的數(shù)據(jù)--->稀疏數(shù)組辐烂。
基本介紹
當(dāng)一個(gè)數(shù)組中大部分元素為0,或者為同一個(gè)值的數(shù)組時(shí),可以使用稀疏數(shù)組來(lái)保存該數(shù)組蚂斤。
稀疏數(shù)組的處理方法是:
- 記錄數(shù)組一共
有幾行幾列,有多少個(gè)不同的值 - 把不同值的元素的行列及值記錄在一個(gè)小規(guī)模的數(shù)組中,從而
縮小程序的規(guī)模栓拜。
- 稀疏數(shù)組舉例說(shuō)明
0 0 0 22 0 0 15
0 11 0 0 0 17 0
0 0 0 -6 0 0 0
0 0 0 0 0 39 0
91 0 0 0 0 0 0
0 0 28 0 0 0 0
| 行(row) | 列(col) | 值(value) | 備注 | |
|---|---|---|---|---|
| [0] | 6 | 7 | 8 | 稀疏數(shù)組第一個(gè)下標(biāo)存的是整個(gè)二維數(shù)組的行,列,包括有幾個(gè)非0的值 |
| [1] | 0 | 3 | 22 | 稀疏數(shù)組第二個(gè)下標(biāo)存的是二維數(shù)組中的第0行第3列的值(記錄非0的值) |
| [2] | 0 | 6 | 15 | 以此類(lèi)推 |
| [3] | 1 | 1 | 11 | 以此類(lèi)推 |
| [4] | 1 | 5 | 17 | 以此類(lèi)推 |
| [5] | 2 | 3 | -6 | 以此類(lèi)推 |
| [6] | 3 | 5 | 39 | 以此類(lèi)推 |
| [7] | 4 | 0 | 91 | 以此類(lèi)推 |
| [8] | 5 | 2 | 28 | 以此類(lèi)推 |
應(yīng)用實(shí)例
二維數(shù)組轉(zhuǎn)稀疏數(shù)組的思路:
1.遍歷原始的二維數(shù)組,得到有效數(shù)據(jù)的個(gè)數(shù)(sum)
2.根據(jù)sum就可以創(chuàng)建稀疏數(shù)組sparseArr int[sum+1][3]
3.將二維數(shù)組的有效數(shù)據(jù)存入到稀疏數(shù)組中
稀疏數(shù)組轉(zhuǎn)原始二維數(shù)組的思路:
1.先讀取稀疏數(shù)組的第一行,根據(jù)第一行的數(shù)據(jù),創(chuàng)建原始的二維數(shù)組,比如上面的chessArr2=int[15][15]
2.在讀取稀疏數(shù)組后幾行的數(shù)據(jù),并賦給原始的二維數(shù)組即可
1)使用稀疏數(shù)組,來(lái)保留類(lèi)似前面的二維數(shù)組(棋盤(pán),地圖等等)
2)把稀疏數(shù)組存盤(pán),并且可以重新恢復(fù)原來(lái)的二維數(shù)組
3)代碼實(shí)現(xiàn)
package com.young.sparsearray;
public class SparseArray {
public static void main(String[] args) {
//創(chuàng)建一個(gè)原始的二維數(shù)組 15 * 15
//0: 表示沒(méi)有棋子,1: 表示黑子,2: 表示白子
int[][] chessArr1 = new int[15][15];
chessArr1[1][2] = 1;
chessArr1[2][3] = 2;
//輸出原始的二維數(shù)組
System.out.println("原始的二維數(shù)組");
for (int[] row : chessArr1) {
for (int data : row) {
System.out.printf("%d\t", data);
}
System.out.println();
}
//將二維數(shù)組轉(zhuǎn)稀疏數(shù)組
//1.先遍歷二維數(shù)組得到非0數(shù)據(jù)的個(gè)數(shù)
int sum = 0;
for (int i = 0; i < 15; i++) {
for (int j = 0; j < 15; j++) {
if (chessArr1[i][j] != 0) {
sum++;
}
}
}
//2.創(chuàng)建對(duì)應(yīng)的稀疏數(shù)組
int[][] sparseArr = new int[sum + 1][3];
//給稀疏數(shù)組賦值
//row col value
//15 15 2
sparseArr[0][0] = 15;
sparseArr[0][1] = 15;
sparseArr[0][2] = sum;
//遍歷二維數(shù)組,將非0的值存放到稀疏數(shù)組中
int count = 0;//count用于幾率是第幾個(gè)非0數(shù)據(jù)
for (int i = 0; i < 15; i++) {
for (int j = 0; j < 15; 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();
System.out.println("得到稀疏數(shù)組為~~~~");
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();
/**
* 將稀疏數(shù)組-->恢復(fù)成原始的二維數(shù)組步驟:
* 1.先讀取稀疏數(shù)組的第一行,根據(jù)第一行的數(shù)據(jù),創(chuàng)建原始的二維數(shù)組,比如上面的chessArr2=int[15][15]
* 2.在讀取稀疏數(shù)組后幾行的數(shù)據(jù),并賦給原始的二維數(shù)組即可
*/
//1.先讀取稀疏數(shù)組的第一行,根據(jù)第一行的數(shù)據(jù),創(chuàng)建原始的二維數(shù)組
int[][] chessArr2 = new int[sparseArr[0][0]][sparseArr[0][1]];
//2.在讀取稀疏數(shù)組后幾行的數(shù)據(jù)(從第二行開(kāi)始),并賦給原始的二維數(shù)組即可
for (int i = 1; i < sparseArr.length; i++) {
chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
}
//輸出恢復(fù)后的二維數(shù)組
System.out.println();
System.out.println("恢復(fù)后的二維數(shù)組");
for (int[] row : chessArr2) {
for (int data : row) {
System.out.printf("%d\t", data);
}
System.out.println();
}
}
}
