02-稀疏數組和隊列

介紹

當一個數組中的大部分元素為0，或者為一個值得數組時，可以使用稀疏數組來保存該數組。

?稀疏數組的處理方法是：

1）記錄數組一共有幾行幾列，有多少個不同的值

2）把具有不同值的元素的行列及值記錄在一個小規模的數組中，從而縮小程序的規模

稀疏數組應用實例

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

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

3）整體思路分析

二維數組轉稀疏數組思路

1，遍歷二維數組，得到有效數據的個數 sum

2，根據sum就可以創建稀疏數組int[sum+1][3]

3，將二維數組的有效數據存入到稀疏數組

稀疏數組轉原始二維數組的思路

1，先讀取稀疏數組的第一行，創建原始二維數組int[11][11]

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

?稀疏數組代碼實現

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