02-稀疏數(shù)組和隊(duì)列

介紹

當(dāng)一個(gè)數(shù)組中的大部分元素為0，或者為一個(gè)值得數(shù)組時(shí)，可以使用稀疏數(shù)組來保存該數(shù)組。

?稀疏數(shù)組的處理方法是：

1）記錄數(shù)組一共有幾行幾列，有多少個(gè)不同的值

2）把具有不同值的元素的行列及值記錄在一個(gè)小規(guī)模的數(shù)組中，從而縮小程序的規(guī)模

稀疏數(shù)組應(yīng)用實(shí)例

1）使用稀疏數(shù)組，來保留類似前面的二維數(shù)組（棋盤、地圖等）

2）把稀疏數(shù)組存盤，并且可以重新恢復(fù)原來的二維數(shù)組數(shù)

3）整體思路分析

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

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

2，根據(jù)sum就可以創(chuàng)建稀疏數(shù)組int[sum+1][3]

3，將二維數(shù)組的有效數(shù)據(jù)存入到稀疏數(shù)組

稀疏數(shù)組轉(zhuǎn)原始二維數(shù)組的思路

1，先讀取稀疏數(shù)組的第一行，創(chuàng)建原始二維數(shù)組int[11][11]

2，讀取稀疏數(shù)組后幾行的數(shù)據(jù)，并賦給原始二維數(shù)組

?稀疏數(shù)組代碼實(shí)現(xiàn)

package?com.datastack.datastack.sparsearr;
/**
?*?稀疏數(shù)組
?*?@author?ahpan
?*
?*/
public?class?SparseArr?{
	public?static?void?main(String[]?args)?{
		//創(chuàng)建一個(gè)二維數(shù)組，并打印
		int?arr[][]?=?new?int[11][11];
		arr[1][2]?=?1;
		arr[2][3]?=?2;
		System.out.println("二維數(shù)組");
		for(int[]?row?:?arr){
			for(int?data?:?row){
				System.out.printf("%d\t",data);
			}
			System.out.println();
		}
		
		//二維數(shù)組轉(zhuǎn)稀疏數(shù)組
		//1,遍歷二維數(shù)組，獲取非0的個(gè)數(shù)，定義稀疏數(shù)組
		int?sum?=?0;
		for(int?i=0;i<11;i++){
			for(int?j=0;j<11;j++){
				if(arr[i][j]?!=?0){
					sum++;
				}
			}
		}
		//2,創(chuàng)建稀疏數(shù)組
		int[][]?sparseArr?=?new?int[sum+1][3];
		//3,給稀疏數(shù)組第一行賦值
		sparseArr[0][0]?=?11;
		sparseArr[0][1]?=?11;
		sparseArr[0][2]?=?sum;
		//4,給稀疏數(shù)組其他行賦值
		int?count?=?0;//定義非零的數(shù)量
		for(int?i=0;i<11;i++){
			for(int?j=0;j<11;j++){
				if(arr[i][j]?!=?0){
					count++;
					sparseArr[count][0]?=?i;
					sparseArr[count][1]?=?j;
					sparseArr[count][2]?=?arr[i][j];
				}
			}
		}
		//打印稀疏數(shù)組
		System.out.println("稀疏數(shù)組");
		for(int[]?row?:?sparseArr){
			for(int?data?:?row){
				System.out.printf("%d\t",data);
			}
			System.out.println();
		}
		
		//稀疏數(shù)組轉(zhuǎn)二維數(shù)組，定義二維數(shù)組
		int?arr2[][]?=?new?int[sparseArr[0][0]][sparseArr[0][0]];
		//賦值，從第二行開始遍歷稀疏數(shù)組
		for(int?i=1;i<sparseArr.length;i++){
			arr2[sparseArr[i][0]][sparseArr[i][1]]?=?sparseArr[i][2];
		}
		System.out.println("二維數(shù)組");
		for(int[]?row?:?arr2){
			for(int?data?:?row){
				System.out.printf("%d\t",data);
			}
			System.out.println();
		}
	}
}