二維數組與稀疏數組的互轉

• 2022 年 4 月 6 日
• 筆記
• 數據結構與演算法

二維數組與稀疏數組的互轉

• 轉換思路

二維數組轉稀疏數組的思路：

1. 遍歷原始的二維數組，得到有效數據的個數sum，根據sum就可以創建稀疏數組sparseArr int[sum+1][3]
2. 將二維數組的有效數據存入到稀疏數組

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

1. 先讀取稀疏數組的第一行，根據第一行的數據，創建原始的二維數組，比如上面的chessArr2=int[11][11]
2. 再讀取稀疏數組後幾行的數據，並賦給原始的二維數組即可

1. 寫一個二維數組：

//1.創建一個二維數組
int chessArr1[][]=new int[11][11];
//2.給二維數組賦值
chessArr1[1][2]=1;
chessArr1[2][3]=2;
//3.雙重for循環輸出二維數組
System.out.println("原始的二維數組：");
for (int[] row : chessArr1) {
    for (int data : row) {
        System.out.printf("%d\t",data);
    }
    //每輸出完一個一重數組換一行
    System.out.println();
}

2. 將二維數組換換位稀疏數組

//將二維數組轉稀疏數組
//1.先遍歷二維數組，得到非0數據的個數，知道數據個數，就可以創建稀疏數組（知道了稀疏數組的行）
int sum=0;
for (int i = 0; i < 11; i++) {
    for (int j = 0; j < 11; j++) {
        if (chessArr1[i][j]!=0){
            sum++;
        }
    }
}
System.out.println("有效值的個數為："+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 (chessArr1[i][j]!=0){
            sparseArr[count+1][0]=i;
            sparseArr[count+1][1]=j;
            sparseArr[count+1][2]=chessArr1[i][j];
            count++;
        }
    }
}
//5.輸出稀疏數組
//以下是兩種遍歷方式：
/*for (int[] ints : sparseArr) {
    for (int anInt : ints) {
        System.out.printf("%d\t",anInt);
    }
    //把一個數組遍歷完之後換一行
    System.out.println();
}*/
System.out.println("得到稀疏數組為~~~~~");
for (int i = 0; i < sparseArr.length; i++) {
    System.out.printf("%d\t%d\t%d\t\n",sparseArr[i][0],sparseArr[i][1],sparseArr[i][2]);
}

3. 將稀疏數組還原為二維數組

//把稀疏數組還原為二維數組
//1.創建二維數組
int chessArr2[][]=new int[sparseArr[0][0]][sparseArr[0][1]];
//2.給二維數組賦值
for (int i = 1; i < sparseArr.length; i++) {
    chessArr2[sparseArr[i][0]][sparseArr[i][1]]=sparseArr[i][2];
}
//3.輸出二維數組
for (int[] row : chessArr2) {
    for (int data : row) {
        System.out.printf("%d\t",data);
    }
    System.out.println();
}