Java數(shù)據(jù)結(jié)構(gòu)之稀疏數(shù)組的實(shí)現(xiàn)與應(yīng)用
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行 | row | col | val |
---|---|---|---|
0 | 10 | 10 | 8 |
1 | 0 | 4 | 1 |
2 | 0 | 8 | 1 |
3 | 1 | 5 | 1 |
4 | 1 | 7 | 1 |
5 | 4 | 8 | 1 |
6 | 5 | 5 | 1 |
7 | 7 | 2 | 1 |
8 | 8 | 7 | 1 |
以索引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)文章!
- Java二維數(shù)組與稀疏數(shù)組相互轉(zhuǎn)換實(shí)現(xiàn)詳解
- java稀疏數(shù)組的示例代碼
- java數(shù)據(jù)結(jié)構(gòu)算法稀疏數(shù)組示例詳解
- Java 輕松實(shí)現(xiàn)二維數(shù)組與稀疏數(shù)組互轉(zhuǎn)
- Java數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)二維數(shù)組與稀疏數(shù)組轉(zhuǎn)換詳解
- java數(shù)據(jù)結(jié)構(gòu)基礎(chǔ):稀疏數(shù)組
- Java實(shí)現(xiàn)二維數(shù)組和稀疏數(shù)組之間的轉(zhuǎn)換
- 淺談Java數(shù)據(jù)結(jié)構(gòu)之稀疏數(shù)組知識(shí)總結(jié)
- Java稀疏數(shù)組的應(yīng)用實(shí)踐
相關(guān)文章
Java項(xiàng)目開發(fā)中實(shí)現(xiàn)分頁的三種方式總結(jié)
這篇文章主要給大家介紹了關(guān)于Java項(xiàng)目開發(fā)中實(shí)現(xiàn)分頁的三種方式,通過這一篇文章可以很快的學(xué)會(huì)java分頁功能,文中通過示例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-02-02Spring內(nèi)置任務(wù)調(diào)度如何實(shí)現(xiàn)添加、取消與重置詳解
任務(wù)調(diào)度是我們?nèi)粘i_發(fā)中經(jīng)常會(huì)碰到的,下面這篇文章主要給大家介紹了關(guān)于Spring內(nèi)置任務(wù)調(diào)度如何實(shí)現(xiàn)添加、取消與重置的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),需要的朋友可以參考借鑒,下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧。2017-10-10SpringBoot2使用JTA組件實(shí)現(xiàn)基于JdbcTemplate多數(shù)據(jù)源事務(wù)管理(親測(cè)好用)
這篇文章主要介紹了SpringBoot2使用JTA組件實(shí)現(xiàn)基于JdbcTemplate多數(shù)據(jù)源事務(wù)管理(親測(cè)好用),在Spring?Boot?2.x中,整合了這兩個(gè)JTA的實(shí)現(xiàn)分別是Atomikos和Bitronix,本文通過實(shí)例代碼給大家介紹的非常詳細(xì),需要的朋友可以參考下2022-07-07解決springboot錯(cuò)誤:找不到或無法加載主類(配置編碼或者M(jìn)aven)
這篇文章主要介紹了解決springboot錯(cuò)誤:找不到或無法加載主類(配置編碼或者M(jìn)aven)問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-06-06java 全角半角字符轉(zhuǎn)換的方法實(shí)例
這篇文章主要介紹了java 全角半角字符轉(zhuǎn)換的方法,大家參考使用吧2013-11-11Java實(shí)現(xiàn)AC自動(dòng)機(jī)全文檢索示例
本篇文章主要介紹了Java實(shí)現(xiàn)AC自動(dòng)機(jī)全文檢索示例,小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-02-02springboot hazelcast緩存中間件的實(shí)例代碼
這篇文章主要介紹了springboot hazelcast緩存中間件的實(shí)例代碼,非常不錯(cuò),具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2018-08-08