Java多維數(shù)組及稀疏數(shù)組
如何理解多維數(shù)組
數(shù)組大家應(yīng)該都是了解一些的，這里先從二維數(shù)組開(kāi)始說(shuō)起：可以將它理解為一個(gè)存放著數(shù)組的數(shù)組，能夠表示一個(gè)二維平面的行列集合，和關(guān)系型數(shù)據(jù)庫(kù)中的一張表格非常相似枕稀。
再向后延伸捐名，三維數(shù)組就可以理解為一個(gè)存放二維數(shù)組的數(shù)組旦万。
看到二維，三維這樣的字眼镶蹋，難免會(huì)想到生活中也提到的維度成艘，比如一種普遍的說(shuō)法，人是生活在四維空間的三維生物梅忌。
這個(gè)話題再展開(kāi)就扯太遠(yuǎn)了狰腌，這里只想做一下類比，多維數(shù)組以及關(guān)系型數(shù)據(jù)庫(kù)牧氮，和生活中所說(shuō)的維度琼腔，點(diǎn)線面體非常相似。
零維的點(diǎn)踱葛，相當(dāng)于數(shù)組中的一個(gè)數(shù)據(jù)丹莲，或數(shù)據(jù)庫(kù)表中的一個(gè)單元格；
一維的線尸诽，相當(dāng)于一整個(gè)數(shù)組甥材，或數(shù)據(jù)庫(kù)表中的一行；
二維的面性含，相當(dāng)于一個(gè)二維數(shù)組洲赵，或者一張數(shù)據(jù)庫(kù)表；
三維的體商蕴，相當(dāng)于多個(gè)二維數(shù)組的集合叠萍，或多張表的集合；
再向后绪商，超過(guò)了四維苛谷，生活中的維度就很難想象了，但數(shù)組的維度向后推去并沒(méi)有什么阻力格郁，四維數(shù)組也不過(guò)就是三維數(shù)組的集合......
根據(jù)上面的說(shuō)法腹殿，再來(lái)拿二維數(shù)組舉例，就可以產(chǎn)生豐富的應(yīng)用場(chǎng)景例书。
首先可以當(dāng)做關(guān)系型數(shù)據(jù)庫(kù)表格來(lái)用锣尉，比如存放一張成績(jī)單
此外，也完全可以將二維數(shù)組用來(lái)表示一個(gè)平面决采，例如棋盤(pán)悟耘、迷宮、推箱子地圖等
Java中的數(shù)組
這里只介紹普通數(shù)組和二維數(shù)組织狐，高維數(shù)組語(yǔ)法也是相同的可自行類比
在Java中聲明一個(gè)數(shù)組整體來(lái)歸類可分為兩種方式
靜態(tài)初始化和動(dòng)態(tài)初始化
/*普通數(shù)組*/
//數(shù)據(jù)類型 [] 變量名稱 = new 數(shù)據(jù)類型[]{xxx,xxx,xxx};聲明加靜態(tài)初始化,xxx表示數(shù)組中的數(shù)據(jù)
int [] arr = new int[]{1,2,3};
//數(shù)據(jù)類型 [] 變量名稱 = new 數(shù)據(jù)類型[i];聲明加動(dòng)態(tài)初始化,i表示數(shù)組容量
int [] arr = new int[5];
/*二維數(shù)組*/
//數(shù)據(jù)類型 [][] 變量名稱 = new 數(shù)據(jù)類型[][]{{xx,xx},{xx,xx},{xx}};靜態(tài)初始化
//數(shù)據(jù)類型 [][] 變量名稱 = new 數(shù)據(jù)類型[i][j];動(dòng)態(tài)初始化暂幼，可以沒(méi)有j筏勒，但必須有i
//如果不指定列，就需要在使用時(shí)動(dòng)態(tài)再初始化列
int arr[][] = new int[2][];//此時(shí)如果直接想要調(diào)用arr[0][0]會(huì)報(bào)錯(cuò)空指針旺嬉，因?yàn)闆](méi)有給列開(kāi)辟空間
//還需要以這樣的方式再給列初始化
arr[0] = new int[2];
//注意管行，等號(hào)前的中括號(hào)可以隨意擺放，以下方式都是可以的邪媳，但等號(hào)后的括號(hào)不能亂動(dòng)
int []a[];
int a[][];
int [][]a;
int a[];
int []a;
//也要注意捐顷，等號(hào)前面的括號(hào)必須是空的
//動(dòng)態(tài)靜態(tài)兩種方式不能結(jié)合使用，比如下面這樣就是錯(cuò)誤的
int [] arr = new int[5]{1,2,3,4,5};
注意：
Java中的數(shù)組是不可擴(kuò)容的雨效，也就是聲明時(shí)就已經(jīng)確定了數(shù)組的容量
jvm給聲明的數(shù)組分配的內(nèi)存空間是連續(xù)的迅涮，聲明后就必須被固定了，不支持后續(xù)更改空間容量徽龟，因?yàn)楹筮呥B續(xù)的空間可能被其他內(nèi)容占用
所以無(wú)論哪種聲明方式叮姑，都會(huì)在聲明時(shí)就確定了數(shù)組的容量
靜態(tài)初始化和動(dòng)態(tài)初始化的區(qū)別：
靜態(tài)方式會(huì)自動(dòng)根據(jù)賦值的數(shù)據(jù)開(kāi)辟數(shù)組的空間，同時(shí)存放上相應(yīng)的數(shù)據(jù)
這里需要注意据悔，多維數(shù)組中不一定是四方的,不同行可能不一樣長(zhǎng)传透，要小心邊界超出范圍
//比如下面這樣會(huì)報(bào)錯(cuò) java.lang.ArrayIndexOutOfBoundsException
int [][] arr = new int[][]{{1,2,3},{4,5},{6}};
System.out.println(arr[1][3]);
動(dòng)態(tài)方式會(huì)根據(jù)指定長(zhǎng)度開(kāi)辟內(nèi)存空間，對(duì)數(shù)據(jù)進(jìn)行初始化
初始化的方式：
1.如果是整型，int long short：數(shù)據(jù)會(huì)被初始化為0
2.如果是浮點(diǎn)型，float double：數(shù)據(jù)會(huì)被初始化為0.0
3.如果是boolean型：數(shù)據(jù)會(huì)被初始化為false
4.如果是引用類型（除基本類型外都是引用類型）：數(shù)據(jù)會(huì)被初始化為null
5.如果是char型：數(shù)據(jù)會(huì)被初始化為0或'\u0000'蛀恩，注意不是'0'，這是一個(gè)空格符但還不是鍵盤(pán)上的空格......所以想要判斷char型數(shù)組是否是沒(méi)有數(shù)據(jù)的可以判斷的方式只能是{arr[0]==0或者arr[0]=='\u0000'}不可以是{arr[0]==' '}
二維數(shù)組與稀疏數(shù)組
先用二維數(shù)組來(lái)畫(huà)一個(gè)11*11的五子棋盤(pán)
采用int數(shù)組榄笙，因?yàn)槌跏蓟瘮?shù)據(jù)都是0，所以用0表示空，1表示黑棋，2表示白棋
int [][] chessArr = new int[11][11];
遍歷一下二維數(shù)組闰围，打印在控制臺(tái)看一下
//遍歷二維數(shù)組需要一個(gè)嵌套循環(huán)
for (int[] row : arr) {
for (int data : row) {
System.out.print(data+"\t");
}
System.out.println();
}
可以看到如下的效果
給它添加上幾個(gè)棋子再打印
//假設(shè)當(dāng)前棋盤(pán)第二行第三列一枚黑子，第三行第四列一枚白子既峡，第八行第十列有一枚黑子
chessArr[1][2] = 1;
chessArr[2][3] = 2;
chessArr[7][9] = 1;
看到如下打印
可以發(fā)現(xiàn)，當(dāng)二維數(shù)組中有效數(shù)據(jù)較少的時(shí)候碧查，被大量無(wú)意義的0占用了內(nèi)存空間
是不是有什么辦法可以簡(jiǎn)化一下二維數(shù)組呢运敢？
這時(shí)就有人想到了一種辦法并將其命名為稀疏數(shù)組：
稀疏數(shù)組中，只去記錄有效的數(shù)據(jù)
1.記錄二維數(shù)組的總行數(shù)忠售，總列數(shù)传惠，有效數(shù)據(jù)數(shù)量
2.記錄每一個(gè)有效數(shù)據(jù)所在行，所在列稻扬，數(shù)據(jù)值
根據(jù)上述兩條的數(shù)據(jù)就可以通過(guò)一定的計(jì)算完整還原出二維數(shù)組
那么對(duì)于上面這個(gè)11行11列的二維數(shù)組卦方，只需要一個(gè)4行3列的二維數(shù)組就可以取代
對(duì)于很多場(chǎng)景，可以做到對(duì)內(nèi)存或存儲(chǔ)空間的節(jié)省
下面演示一下用Java代碼實(shí)現(xiàn)二維數(shù)組到稀疏數(shù)組的轉(zhuǎn)換
編碼思路無(wú)非就是獲得下面這三個(gè)我們需要的關(guān)鍵數(shù)據(jù)泰佳，再保存到一個(gè)新的數(shù)組作為稀疏數(shù)組返回即可
1.原二維數(shù)組的總行數(shù)盼砍、總列數(shù)
2.數(shù)組中有效數(shù)據(jù)的個(gè)數(shù)（遍歷一遍尘吗，非0就是有效的）
3.每一個(gè)有效數(shù)據(jù)所在的位置和數(shù)值（再遍歷一遍，獲取到這些信息插入到稀疏數(shù)組）
注意：第一次遍歷得到的數(shù)據(jù)要用來(lái)重建稀疏數(shù)組的時(shí)候初始化行數(shù)浇坐，第二次遍歷就已經(jīng)在創(chuàng)建好稀疏數(shù)組后插入數(shù)據(jù)了睬捶，所以雖然兩次都是遍歷原數(shù)組，但不能合并成一次遍歷進(jìn)行
這里還可以對(duì)是否值得轉(zhuǎn)換進(jìn)行一個(gè)判斷：
二維數(shù)組占用的內(nèi)存空間為總行數(shù)*總列數(shù)
稀疏數(shù)組占用的內(nèi)存空間為有（有效數(shù)據(jù)個(gè)數(shù)+1）*3
如果（有效數(shù)據(jù)個(gè)數(shù)+1）* 3 >= 總行數(shù) * 總列數(shù)就會(huì)失去轉(zhuǎn)換意義
/**
* 二維數(shù)組轉(zhuǎn)換為稀疏數(shù)組
* @param chessArr 二維數(shù)組
* @return 返回稀疏數(shù)組
*/
private static int[][] getSparseArr(int[][] chessArr) {
//獲得二維數(shù)組中非0數(shù)據(jù)的個(gè)數(shù)
int sum = 0;
for (int[] row : chessArr) {
for (int data : row) {
if (data!=0){
sum++;
}
}
}
//判斷是否值得創(chuàng)建稀疏數(shù)組
if ((sum+1)*3 >= chessArr.length * chessArr[0].length){
System.out.println("該二維數(shù)組其實(shí)不值得轉(zhuǎn)換為稀疏數(shù)組");
}
//創(chuàng)建稀疏數(shù)組近刘，列數(shù)固定為3擒贸，行數(shù)為非0數(shù)據(jù)的個(gè)數(shù)加一
int[][] sparseArr = new int[sum+1][3];
//稀疏數(shù)組第一行直接進(jìn)行賦值
//行數(shù)
sparseArr[0][0] = chessArr.length;
//列數(shù)
sparseArr[0][1] = chessArr[0].length;
//非0數(shù)據(jù)個(gè)數(shù)
sparseArr[0][2] = sum;
//后續(xù)表示具體數(shù)據(jù)的行，遍歷賦值
//count記錄當(dāng)前是第幾個(gè)非0數(shù)據(jù)
int count = 0;
//遍歷出每一行觉渴，i表示第幾行的索引（第一行就是0）
for (int i = 0; i < chessArr.length; i++) {
//遍歷當(dāng)前行的每個(gè)數(shù)據(jù)介劫，j表示第幾列（第一列就是0）
for (int j = 0; j < chessArr[i].length; j++) {
//判斷是否為非0數(shù)據(jù)
if (chessArr[i][j]!=0){
//找到一個(gè)非0數(shù)據(jù)計(jì)數(shù)器+1
count++;
//給稀疏數(shù)組賦值，行案淋、列座韵、值
sparseArr[count][0] = i+1;
sparseArr[count][1] = j+1;
sparseArr[count][2] = chessArr[i][j];
}
}
}
return sparseArr;
}
稀疏數(shù)組轉(zhuǎn)換回二維數(shù)組
稀疏數(shù)組保存起來(lái)節(jié)省空間，但需要檢索或展示的時(shí)候哎迄，還是變回二維數(shù)組更加方便
所以再演示一個(gè)反轉(zhuǎn)的代碼實(shí)例
/**
* 稀疏數(shù)組轉(zhuǎn)二維數(shù)組
* @param sparseArr 稀疏數(shù)組
* @return 返回轉(zhuǎn)換后的二維數(shù)組
*/
private static int[][] getNewChessArr(int[][] sparseArr) {
//創(chuàng)建新的二維數(shù)組作為轉(zhuǎn)換回的二維數(shù)組——行列數(shù)為稀疏數(shù)組第一行前兩列存放的行列數(shù)
int[][] newChessArr = new int[sparseArr[0][0]][sparseArr[0][1]];
//遍歷把非0數(shù)據(jù)插入進(jìn)去
for (int i = 0; i < sparseArr.length; i++) {
if (i!=0){
newChessArr[sparseArr[i][0]-1][sparseArr[i][1]-1] = sparseArr[i][2];
}
}
return newChessArr;
}
