Java數(shù)據(jù)結構之稀疏數(shù)組的實現(xiàn)與應用
1.稀疏數(shù)組引入
1.1 使用場景
筆者在課程設計中曾寫過一個掃雷小游戲,為了便于講解,我們來做個簡化(實際比這個復雜),只考慮當前位置有雷與無雷兩種狀況:雷用1表示,非雷用0表示。則將當前狀態(tài)用二維數(shù)組表示如下:
在右側的二維數(shù)組中,很多都是0,即記錄了很多沒有意義的數(shù)據(jù),因此,我們考慮使用稀疏數(shù)組進行存儲結構的優(yōu)化。
1.2 稀疏數(shù)組簡介
當一個數(shù)組中的大部分元素都是0(或者為相同的某一值),可以考慮使用稀疏數(shù)組來優(yōu)化保存。
而稀疏數(shù)組的基本處理方式為:
記錄數(shù)組有幾行幾列,有幾個有效值;
把有效值的元素的行、列及值記錄在一個小規(guī)模的數(shù)組中,從而縮小程序的規(guī)模。
例如上述的二維數(shù)組用稀疏數(shù)組表示,可以創(chuàng)建一個n*3列的稀疏數(shù)組。其中,n為有效值個數(shù)加1,第一行用于存儲二維數(shù)組的行數(shù)、列數(shù)及有效值的個數(shù),便于恢復二維數(shù)組時使用。
而從第二行開始后的每一行,都記錄某個有效值的所在行、列索引與值。
上述二維數(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個有效值。
以索引1那行,0 4 1為例:即第一個有效值在原數(shù)組的第0行第4列(索引為0和4),值為1,以此類推…
2.稀疏數(shù)組的實現(xiàn)
2.1 案例概述
1.使用稀疏數(shù)組來保存前面1.1樣例中的二維數(shù)組(見下圖);
2.可以由稀疏數(shù)組恢復成二維數(shù)組。
2.2 思路分析
二維數(shù)組轉稀疏數(shù)組:
遍歷原始的二維數(shù)組,得到有效數(shù)據(jù)的個數(shù) amount;
根據(jù) amount 可以創(chuàng)建稀疏數(shù)組 sparseArray[amount+1][3];
將二維數(shù)組中的有效值存入稀疏數(shù)組中。
稀疏數(shù)組恢復二維數(shù)組:
先讀取稀疏數(shù)組的第一行,根據(jù)第一行的數(shù)據(jù),創(chuàng)建原始二維數(shù)組;
讀取第二行及以后行的數(shù)據(jù),按照每行的行、列、值恢復有效值,錄入二維數(shù)組中。
2.3 代碼實現(xiàn)
根據(jù)如上思路,逐步實現(xiàn)稀疏數(shù)組,詳情可見代碼注釋
參考代碼:
/** * @author 興趣使然黃小黃 * @version 1.0 * 二維數(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ù)組轉成稀疏數(shù)組 //1.遍歷二維數(shù)組,得到非0的有效數(shù)據(jù)的個數(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)建對應的稀疏數(shù)組 sparseArray[amount+1][3], 并初始化稀疏數(shù)組第一行的數(shù)據(jù) //第一行第一列: 原數(shù)組的行數(shù) 第一行第二列: 原數(shù)組的列數(shù) 第一行第三列: 原數(shù)組的有效數(shù)據(jù)個數(shù) int[][] sparseArray = new int[amount + 1][3]; sparseArray[0][0] = 10; sparseArray[0][1] = 10; sparseArray[0][2] = amount; //3.遍歷二維數(shù)組,將非0值存儲進稀疏數(shù)組 int count = 0; //用于記錄是第幾個非零數(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ù)組恢復成為二維數(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("恢復后的二維數(shù)組:"); for (int[] row: recoveredArray) { for (int data : row) { System.out.printf("%d\t", data); } System.out.println(); } } }
運行結果:
原始的二維數(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
恢復后的二維數(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
比對結果如下:
經(jīng)過比較,恢復后的二維數(shù)組與原二維數(shù)組保持一致!
分析可知:原二維數(shù)組需要的空間為:10 * 10 *(int),而稀疏數(shù)組只需要 9 * 3 * (int),相對節(jié)省了73(int)的空間!
以上就是Java數(shù)據(jù)結構之稀疏數(shù)組的實現(xiàn)與應用的詳細內容,更多關于Java稀疏數(shù)組的資料請關注腳本之家其它相關文章!
相關文章
Java項目開發(fā)中實現(xiàn)分頁的三種方式總結
這篇文章主要給大家介紹了關于Java項目開發(fā)中實現(xiàn)分頁的三種方式,通過這一篇文章可以很快的學會java分頁功能,文中通過示例代碼介紹的非常詳細,需要的朋友可以參考下2022-02-02Spring內置任務調度如何實現(xiàn)添加、取消與重置詳解
任務調度是我們日常開發(fā)中經(jīng)常會碰到的,下面這篇文章主要給大家介紹了關于Spring內置任務調度如何實現(xiàn)添加、取消與重置的相關資料,文中通過示例代碼介紹的非常詳細,需要的朋友可以參考借鑒,下面隨著小編來一起學習學習吧。2017-10-10SpringBoot2使用JTA組件實現(xiàn)基于JdbcTemplate多數(shù)據(jù)源事務管理(親測好用)
這篇文章主要介紹了SpringBoot2使用JTA組件實現(xiàn)基于JdbcTemplate多數(shù)據(jù)源事務管理(親測好用),在Spring?Boot?2.x中,整合了這兩個JTA的實現(xiàn)分別是Atomikos和Bitronix,本文通過實例代碼給大家介紹的非常詳細,需要的朋友可以參考下2022-07-07解決springboot錯誤:找不到或無法加載主類(配置編碼或者Maven)
這篇文章主要介紹了解決springboot錯誤:找不到或無法加載主類(配置編碼或者Maven)問題,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2023-06-06springboot hazelcast緩存中間件的實例代碼
這篇文章主要介紹了springboot hazelcast緩存中間件的實例代碼,非常不錯,具有一定的參考借鑒價值,需要的朋友可以參考下2018-08-08