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

第Java數(shù)據(jù)結(jié)構(gòu)之稀疏數(shù)組的實(shí)現(xiàn)與應(yīng)用目錄1.稀疏數(shù)組引入1.1使用場(chǎng)景1.2稀疏數(shù)組簡(jiǎn)介2.稀疏數(shù)組的實(shí)現(xiàn)2.1案例概述2.2思路分析2.3代碼實(shí)現(xiàn)

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

1.1使用場(chǎng)景

筆者在課程設(shè)計(jì)中曾寫過一個(gè)掃雷小游戲，為了便于講解，我們來做個(gè)簡(jiǎn)化（實(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ù)組簡(jiǎn)介

當(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行rowcolval01010810412081315141715481655177218871

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

以索引1那行，041為例：即第一個(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興趣使然黃小黃

*@version1.0

*二維數(shù)組轉(zhuǎn)稀疏數(shù)組、稀疏數(shù)組還原二維數(shù)組的實(shí)現(xiàn)

publicclassSparseArray{

publicstaticvoidmain(String[]args){

//先創(chuàng)建原始二維數(shù)組

int[][]originalArray=newint[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(intdata:row){

System.out.printf("%d\t",data);

System.out.println();

//將二維數(shù)組轉(zhuǎn)成稀疏數(shù)組

//1.遍歷二維數(shù)組，得到非0的有效數(shù)據(jù)的個(gè)數(shù)

intamount=0;

for(inti=0;ioriginalArray.length;i++){

for(intj=0;joriginalArray[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=newint[amount+1][3];

sparseArray[0][0]=10;

sparseArray[0][1]=10;

sparseArray[0][2]=amount;

//3.遍歷二維數(shù)組,將非0值存儲(chǔ)進(jìn)稀疏數(shù)組

intcount=0;//用于記錄是第幾個(gè)非零數(shù)據(jù)

for(inti=0;ioriginalArray.length;i++){

for(intj=0;joriginalArray[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(inti=0;isparseArray.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=newint[sparseArray[0][0]][sparseArray[0][1]];

//2.讀取稀疏數(shù)組的后面行數(shù)據(jù)，賦值給原始二維數(shù)組

for(inti=1;isparseArray.length;i++){

recoveredArray[sparseArray[i][0]][sparseArray[i][1]]=sparseArray[i][2];

//輸出二維數(shù)組

System.out.println("恢復(fù)后的二維數(shù)組:");

for(int[]row:recoveredArray){

for(intdata:row){

System.out.printf("%d\t",data);

System.out.println();

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

原始的二維數(shù)組:

0000100010

0000010100

0000000000

0000000000

0000000010

0000010000

0000000000

0010000000

0000000100

0000000000

amount=8

稀疏數(shù)組:

10108

041

081

151

171

481

551

721

871

恢復(fù)后的二維數(shù)組:

0000100010

0000010100

0000000000

0000000000

0000000010

0000010000

0000000000

0010000000

0000000100

00