需求
編寫一個五子棋程序, 要有存盤退出和續(xù)上盤的功能，怎么保存棋盤數(shù)據(jù)?
棋盤
編程思路:
創(chuàng)建一個二維數(shù)組, 數(shù)字0代表沒有棋子, 1表示黑子, 2表示藍子, 來保存棋盤數(shù)據(jù)
但是這樣會有一個問題些己？
二維數(shù)組中會存在很多值是默認值0, 因此記錄了很多沒有意義的數(shù)據(jù)
怎么解決赤炒？
我們可以嘗試使用稀疏數(shù)組來解決這個問題, 使用稀疏數(shù)組的解決方法就是記錄數(shù)組有多少行多少列褒傅，有多少個值蛾默，把不同的值的元素的行列和值記錄在一個小規(guī)模的數(shù)組中, 看下圖
解決方案
我們可以使用稀疏數(shù)組來保存棋盤數(shù)據(jù)捷绒，把稀疏數(shù)組存盤瑰排，使用的時候再把稀疏數(shù)組轉(zhuǎn)為二維數(shù)組。
原始數(shù)組和對應(yīng)的稀疏數(shù)組
二維數(shù)組和稀疏數(shù)組互轉(zhuǎn)
- 二維數(shù)組轉(zhuǎn)稀疏數(shù)組思路
- 遍歷原始數(shù)組, 得到有效數(shù)據(jù)的個數(shù)num
- 根據(jù)行數(shù)暖侨、列數(shù)和元素個數(shù)num創(chuàng)建稀疏數(shù)組
- 將二位數(shù)組的有效數(shù)據(jù)存入到稀疏數(shù)組
- 稀疏數(shù)組轉(zhuǎn)二位數(shù)組思路
- 先根據(jù)稀疏數(shù)組的第一行數(shù)據(jù)創(chuàng)建原始的二維數(shù)組
- 再讀取稀疏數(shù)組后幾行的數(shù)據(jù), 并賦值給原始二維數(shù)組即可
代碼實現(xiàn)
- Java
public class Sparse {
/**
* 原始數(shù)組轉(zhuǎn)稀疏數(shù)組
* @param arr 原始數(shù)組
* @return 稀疏數(shù)組
*/
static int[][] Array2Sparse(int[][] arr){
//1. 原始二維數(shù)組幾行幾列
int row = arr.length;
int column = arr[0].length;
//2. 一共幾個有效元素
int num = 0;
for (int i=0; i<arr.length; i++){
for(int j=0; j<arr[i].length; j++){
if(arr[i][j] != 0){
num ++;
}
}
}
//3. 創(chuàng)建稀疏數(shù)組
int[][] sparseArr = new int[num+1][3];
//4. 二維數(shù)組轉(zhuǎn)稀疏數(shù)組
sparseArr[0][0] = row;
sparseArr[0][1] = column;
sparseArr[0][2] = num;
int count = 0;
for (int i=0; i<arr.length; i++){
for(int j=0; j<arr[i].length; j++){
if(arr[i][j] != 0){
count ++;
sparseArr[count][0] = i;
sparseArr[count][1] = j;
sparseArr[count][2] = arr[i][j];
}
}
}
return sparseArr;
}
/**
* 稀疏數(shù)組轉(zhuǎn)二維數(shù)組
* @param sparseArr 稀疏數(shù)組
* @return 原始數(shù)組
*/
static int[][] Sparse2Arr(int[][] sparseArr){
//1. 創(chuàng)建二維數(shù)組
int[][] arr = new int[sparseArr[0][0]][sparseArr[0][1]];
//2. 稀疏數(shù)組轉(zhuǎn)二維數(shù)組
for(int i=1; i<sparseArr.length; i++){
arr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
}
return arr;
}
/**
* 控制臺輸出二維數(shù)組
* @param arr
*/
static void printArr(int[][] arr){
for (int i=0; i<arr.length; i++){
for(int j=0; j<arr[i].length; j++){
System.out.printf("%d\t", arr[i][j]);
}
System.out.println();
}
}
public static void main(String[] args) {
//1. 初始化一個二維數(shù)組
int[][] arr = new int[11][11];
arr[1][2] = 1;
arr[2][5] = 3;
arr[4][6] = 5;
//2. 二維數(shù)組轉(zhuǎn)稀疏數(shù)組
int[][] sparseArr = Array2Sparse(arr);
System.out.println("原始數(shù)組:");
printArr(arr);
System.out.println("稀疏數(shù)組:");
printArr(sparseArr);
//3. 稀疏數(shù)組轉(zhuǎn)二維數(shù)組
int[][] arr1 = Sparse2Arr(sparseArr);
System.out.println("原始數(shù)組:");
printArr(arr1);
}
}
輸出:
原始數(shù)組:
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 3 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 5 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ù)組:
11 11 3
1 2 1
2 5 3
4 6 5
原始數(shù)組:
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 3 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 5 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
