什么時(shí)候使用稀疏數(shù)組

當(dāng)一個(gè)數(shù)組中大部分元素為零，或者為用一個(gè)數(shù)值的時(shí)候，可以使用稀疏數(shù)組來(lái)保存該數(shù)組；

稀疏數(shù)組的數(shù)據(jù)存儲(chǔ)方式：

1. 稀疏數(shù)組是：行不確定，列為三列的動(dòng)態(tài)數(shù)組；
2. 第一行記錄數(shù)組中一共有幾列幾行，有多少個(gè)不同的數(shù)值；
3. 其他行記錄有效數(shù)據(jù)的行列及值，從而縮小數(shù)組程序的規(guī)模；

應(yīng)用實(shí)例（五子棋程序）

編寫(xiě)的五子棋程序中，有存盤(pán)退出和續(xù)上盤(pán)的功能。

分析問(wèn)題:
因?yàn)樵摱S數(shù)組的很多值是默認(rèn)值0,因此記錄了很多沒(méi)有意義的數(shù)據(jù)->稀疏數(shù)組。
分析思路：

1. 使用稀疏數(shù)組來(lái)保存前面的二維數(shù)組；
2. 把稀疏數(shù)組存盤(pán)，并且可以從新恢復(fù)到原來(lái)的二維數(shù)組中；

3. 整體思路：

   
   

• 二維數(shù)組 轉(zhuǎn)稀疏數(shù)組的思路

1. 遍歷原來(lái)的二維數(shù)組，得到有效數(shù)據(jù)的總數(shù)（sum）；
2. 根據(jù)sum就可以創(chuàng)建 稀疏數(shù)組 new sparseArr Int[sum+1][3]；
3. 將二維數(shù)組中的有效數(shù)據(jù)存儲(chǔ)到稀疏數(shù)組；

• 稀疏數(shù)組轉(zhuǎn)原始的二維數(shù)組的思路

1. 先讀取稀疏數(shù)組的第一行，根據(jù)第一行的數(shù)據(jù)創(chuàng)建原始的二維數(shù)組，比如：new chessArr = int[11][11]
2. 在讀取稀疏數(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： 表示 沒(méi)有棋子，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();
        }
    }
}