JAVA算法與資料結構——稀疏矩陣的壓縮與恢複

稀疏矩陣

稀疏矩陣定義

矩陣中非零元素的個數遠遠小于矩陣元素的總數，并且非零元素的分布沒有規律，通常認為矩陣中非零元素的總數比上矩陣所有元素總數的值小于等于0.05時，則稱該矩陣為稀疏矩陣(sparse matrix)，該比值稱為這個矩陣的稠密度

稀疏矩陣的應用

對于一個五子棋小遊戲，如果我們使用二維數組進行存儲，在儲存對局時，可能棋子相對占比很少。就形成了一個稀疏矩陣。

稀疏矩陣的壓縮是使用另一個二維數組來表示這個稀疏矩陣，二維數組的第一行的第一個值表示被壓縮數組的行數，第二個值儲存被壓縮數組的列數，第三個值儲存共有多少個值。

之後的每一行表示被壓縮的數組裡的值的位置。

我們用棋盤來舉例

可以看到，第二行第三列和第三行第四列是存在值的（這裡我們用1表示黑棋，2表示藍棋）

那麼我們先初始化數組

int[][] arr = new int[11][11];
        arr[1][2] = 1;
        arr[2][3] = 2;
           

數組初始化完了，我們可以先周遊看看結果

周遊使用for循環

for(int[] row:arr){
            for(int data:row){
                System.out.printf("%d ",data);
            }
            System.out.println();
        }
           

好，我們一個稀疏的數組就建立了

壓縮前，先統計下數組中有多少值，周遊，遇到非零數值就+1

int sum = 0;
        for(int[] row:arr){
            for(int data:row){
                if (data != 0){
                    sum++;
                }
            }
        }
           

初始化稀疏數組

第一行儲存行列數和值

int[][] Sparsearr = new int[sum+1][3];
        Sparsearr[0][0] = arr.length;
        Sparsearr[0][1] = arr[0].length;
        Sparsearr[0][2] = sum;
           

周遊矩陣，遇到值則儲存在稀疏數組中

for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                if(arr[i][j]!=0){
                    Sparsearr[flag][0] = i;
                    Sparsearr[flag][1] = j;
                    Sparsearr[flag][2] = arr[i][j];
                    flag++;
                }
            }
        }
           

此時，我們已經完成了壓縮，列印下稀疏數組試試看

for(int[] row:Sparsearr){
            for(int data:row){
                System.out.print(data+" ");
            }
            System.out.println();
        }
           

那麼接下來，我們對稀疏數組進行展開

展開就比較簡單了

先初始化一個二維數組，然後一個一個指派

int[][] arr2 = new int[Sparsearr[0][0]][Sparsearr[0][1]];
        for (int i =1; i <= Sparsearr[0][2]; i++) {
            arr2[Sparsearr[i][0]][Sparsearr[i][1]] = Sparsearr[i][2];
        }
           

周遊一下看看

for(int[] row:arr2){
            for(int data:row){
                System.out.printf("%d ",data);
            }
            System.out.println();
        }
           

好，那麼就操作完了