欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java數(shù)據(jù)結(jié)構(gòu)之稀疏數(shù)組的實(shí)現(xiàn)與應(yīng)用

 更新時(shí)間:2022年10月21日 09:57:25   作者:興趣使然黃小黃  
這篇文章主要為大家詳細(xì)介紹了Java數(shù)據(jù)結(jié)構(gòu)中稀疏數(shù)組的實(shí)現(xiàn)與應(yīng)用,文中的示例代碼講解詳細(xì),具有一定的借鑒價(jià)值,感興趣的可以了解一下

1.稀疏數(shù)組引入

1.1 使用場(chǎng)景

筆者在課程設(shè)計(jì)中曾寫過一個(gè)掃雷小游戲,為了便于講解,我們來做個(gè)簡化(實(shí)際比這個(gè)復(fù)雜),只考慮當(dāng)前位置有雷與無雷兩種狀況:雷用1表示,非雷用0表示。則將當(dāng)前狀態(tài)用二維數(shù)組表示如下:

在右側(cè)的二維數(shù)組中,很多都是0,即記錄了很多沒有意義的數(shù)據(jù),因此,我們考慮使用稀疏數(shù)組進(jìn)行存儲(chǔ)結(jié)構(gòu)的優(yōu)化。

1.2 稀疏數(shù)組簡介

當(dāng)一個(gè)數(shù)組中的大部分元素都是0(或者為相同的某一值),可以考慮使用稀疏數(shù)組來優(yōu)化保存。

而稀疏數(shù)組的基本處理方式為:

記錄數(shù)組有幾行幾列,有幾個(gè)有效值;

把有效值的元素的行、列及值記錄在一個(gè)小規(guī)模的數(shù)組中,從而縮小程序的規(guī)模。

例如上述的二維數(shù)組用稀疏數(shù)組表示,可以創(chuàng)建一個(gè)n*3列的稀疏數(shù)組。其中,n為有效值個(gè)數(shù)加1,第一行用于存儲(chǔ)二維數(shù)組的行數(shù)、列數(shù)及有效值的個(gè)數(shù),便于恢復(fù)二維數(shù)組時(shí)使用。

而從第二行開始后的每一行,都記錄某個(gè)有效值的所在行、列索引與值。

上述二維數(shù)組用稀疏數(shù)組表示如下:

稀疏數(shù)組的第n行rowcolval
010108
1041
2081
3151
4171
5481
6551
7721
8871

以索引0那行,10 10 8為例:表示原二維數(shù)組有10行10列,共有8個(gè)有效值。

以索引1那行,0 4 1為例:即第一個(gè)有效值在原數(shù)組的第0行第4列(索引為0和4),值為1,以此類推…

2.稀疏數(shù)組的實(shí)現(xiàn)

2.1 案例概述

1.使用稀疏數(shù)組來保存前面1.1樣例中的二維數(shù)組(見下圖);

2.可以由稀疏數(shù)組恢復(fù)成二維數(shù)組。

2.2 思路分析

二維數(shù)組轉(zhuǎn)稀疏數(shù)組:

遍歷原始的二維數(shù)組,得到有效數(shù)據(jù)的個(gè)數(shù) amount;

根據(jù) amount 可以創(chuàng)建稀疏數(shù)組 sparseArray[amount+1][3];

將二維數(shù)組中的有效值存入稀疏數(shù)組中。

稀疏數(shù)組恢復(fù)二維數(shù)組:

先讀取稀疏數(shù)組的第一行,根據(jù)第一行的數(shù)據(jù),創(chuàng)建原始二維數(shù)組;

讀取第二行及以后行的數(shù)據(jù),按照每行的行、列、值恢復(fù)有效值,錄入二維數(shù)組中。

2.3 代碼實(shí)現(xiàn)

根據(jù)如上思路,逐步實(shí)現(xiàn)稀疏數(shù)組,詳情可見代碼注釋

參考代碼:

/**
 * @author 興趣使然黃小黃
 * @version 1.0
 * 二維數(shù)組轉(zhuǎn)稀疏數(shù)組、稀疏數(shù)組還原二維數(shù)組的實(shí)現(xiàn)
 */
public class SparseArray {

    public static void main(String[] args) {
        //先創(chuàng)建原始二維數(shù)組
        int[][] originalArray = new int[10][10];
        originalArray[0][4] = 1;
        originalArray[0][8] = 1;
        originalArray[1][5] = 1;
        originalArray[1][7] = 1;
        originalArray[4][8] = 1;
        originalArray[5][5] = 1;
        originalArray[7][2] = 1;
        originalArray[8][7] = 1;
        //輸出原始的二維數(shù)組
        System.out.println("原始的二維數(shù)組:");
        for (int[] row: originalArray) {
            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 amount = 0;
        for (int i = 0; i < originalArray.length; i++) {
            for (int j = 0; j < originalArray[i].length; j++) {
                if (originalArray[i][j] != 0){
                    amount++;
                }
            }
        }
        System.out.println("amount = " + amount);
        //2.創(chuàng)建對(duì)應(yīng)的稀疏數(shù)組 sparseArray[amount+1][3], 并初始化稀疏數(shù)組第一行的數(shù)據(jù)
        //第一行第一列: 原數(shù)組的行數(shù)   第一行第二列: 原數(shù)組的列數(shù)  第一行第三列: 原數(shù)組的有效數(shù)據(jù)個(gè)數(shù)
        int[][] sparseArray = new int[amount + 1][3];
        sparseArray[0][0] = 10;
        sparseArray[0][1] = 10;
        sparseArray[0][2] = amount;
        //3.遍歷二維數(shù)組,將非0值存儲(chǔ)進(jìn)稀疏數(shù)組
        int count = 0; //用于記錄是第幾個(gè)非零數(shù)據(jù)
        for (int i = 0; i < originalArray.length; i++) {
            for (int j = 0; j < originalArray[i].length; j++) {
                if (originalArray[i][j] != 0){
                    count++;
                    sparseArray[count][0] = i; //記錄所在行
                    sparseArray[count][1] = j; //記錄所在列
                    sparseArray[count][2] = originalArray[i][j]; //記錄值
                }
            }
        }
        //輸出稀疏數(shù)組
        System.out.println("稀疏數(shù)組:");
        for (int i = 0; i < sparseArray.length; i++) {
                System.out.printf("%d\t%d\t%d\n", sparseArray[i][0], sparseArray[i][1], sparseArray[i][2]);
        }

        //將稀疏數(shù)組恢復(fù)成為二維數(shù)組
        //1.根據(jù)稀疏數(shù)組的第一行初始化二維數(shù)組
        int[][] recoveredArray = new int[sparseArray[0][0]][sparseArray[0][1]];
        //2.讀取稀疏數(shù)組的后面行數(shù)據(jù),賦值給原始二維數(shù)組
        for (int i = 1; i < sparseArray.length; i++) {
            recoveredArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }
        //輸出二維數(shù)組
        System.out.println("恢復(fù)后的二維數(shù)組:");
        for (int[] row: recoveredArray) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }
    }
}

運(yùn)行結(jié)果:

原始的二維數(shù)組:
0    0    0    0    1    0    0    0    1    0    
0    0    0    0    0    1    0    1    0    0    
0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    1    0    
0    0    0    0    0    1    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    1    0    0    
0    0    0    0    0    0    0    0    0    0    
amount = 8
稀疏數(shù)組:
10    10    8
0    4    1
0    8    1
1    5    1
1    7    1
4    8    1
5    5    1
7    2    1
8    7    1
恢復(fù)后的二維數(shù)組:
0    0    0    0    1    0    0    0    1    0    
0    0    0    0    0    1    0    1    0    0    
0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    0    0    
0    0    0    0    0    0    0    0    1    0    
0    0    0    0    0    1    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    1    0    0    
0    0    0    0    0    0    0    0    0    0    

比對(duì)結(jié)果如下:

經(jīng)過比較,恢復(fù)后的二維數(shù)組與原二維數(shù)組保持一致!

分析可知:原二維數(shù)組需要的空間為:10 * 10 *(int),而稀疏數(shù)組只需要 9 * 3 * (int),相對(duì)節(jié)省了73(int)的空間!

以上就是Java數(shù)據(jù)結(jié)構(gòu)之稀疏數(shù)組的實(shí)現(xiàn)與應(yīng)用的詳細(xì)內(nèi)容,更多關(guān)于Java稀疏數(shù)組的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

最新評(píng)論