稀疏數(shù)組

1. 基本介紹

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

稀疏數(shù)組的處理方法是:

1. 記錄數(shù)組一共有幾行幾列，有多少個(gè)不同的值

2. 把具有不同值的元素的行列及值記錄在一個(gè)小規(guī)模的數(shù)組中值漫，從而縮小程序的規(guī)模

2. 應(yīng)用實(shí)例

1. 使用稀疏數(shù)組，來(lái)保留類似前面的二維數(shù)組(棋盤、地圖等等)
2. 把稀疏數(shù)組存盤替蛉，并且可以從新恢復(fù)原來(lái)的二維數(shù)組數(shù)
3. 整體思路分析

3.轉(zhuǎn)換思路

轉(zhuǎn)化過(guò)程

1. 二維數(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ù)據(jù)存入到稀疏數(shù)組

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

   1. 先讀取稀疏數(shù)組的第一行拄氯，根據(jù)第一行的數(shù)據(jù)躲查，創(chuàng)建原始的二維數(shù)組，比如上面的 chessArr = int[11][11]

   2. 在讀取稀疏數(shù)組后幾行的數(shù)據(jù)译柏，并賦給原始的二維數(shù)組即可.

4. 代碼實(shí)現(xiàn)

public class SparseArray {
    public static void main(String[] args){
        //創(chuàng)建一個(gè)原始的二維數(shù)組
        //0 表示沒(méi)有棋子镣煮，1表示黑子，2表示白子
        int[][] chessArr = new int[11][11];
        chessArr[1][2] = 1;
        chessArr[2][3] = 2;
        //輸出原始的二維數(shù)組
        System.out.println("這是原始的二維矩陣");
        for (int[] row:chessArr) {
            for (int data:row) {
                System.out.printf("%d\t",data);
            }
            System.out.println();
        }
        //轉(zhuǎn)化成稀疏矩陣
        //1.先遍歷二維數(shù)組得到非0數(shù)據(jù)的值
        int sum = 0;//記錄非零值
        for(int i = 0; i < 11; i++)//11即chessArr.lenth
            for(int j = 0; j < 11; j++)//11即chessArr[0].length
            {
                if(chessArr[i][j] != 0){
                    sum++;
                }
            }
//        System.out.println(sum);
        int sparseArr[][] = new int[sum+1][3];
        //給稀疏數(shù)組賦值
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        sparseArr[0][2] = sum;
        //遍歷二維數(shù)組將非零值存入稀疏數(shù)組
        int count = 0;//用于記錄是第幾個(gè)非0數(shù)據(jù)
        for(int i = 0; i < 11; i++)
            for(int j = 0; j < 11; j++){
                if(chessArr[i][j] != 0){
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessArr[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", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]);
            //System.out.println(sparseArr[i][0]+"\t"+sparseArr[i][1]+"\t"+sparseArr[i][2]);
            System.out.println();//在printf后加\n也可
        }
        //將稀疏數(shù)組恢復(fù)成二維數(shù)組
        //1.先讀取稀疏數(shù)組的第一行鄙麦，創(chuàng)建原始二維數(shù)組
        int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
        //2典唇、再讀取稀疏數(shù)組后幾行的數(shù)據(jù)邮弹，并賦值
        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();
        }

    }