# 稀疏矩陣(Sparse Matrix)

五子棋程序如何存取盤的下棋情況？

A：可以使用二維陣列，將黑棋白棋記錄下來。

**思考**
Q：該二維陣列很多值默認為0，因此記錄了很多沒意義的數據，該如何去解決？
A：可以使用稀疏矩陣來保存該陣列。

## 稀疏矩陣的處理方法
1. 記錄陣列一共有幾行幾列，有多少個不同的值。
2. 把具有不同值的元素的行列及值記錄在一個小規模的陣列中，從而縮小程式的規模。

以下圖為例，我們可以將原先 6\*7 = 42 的陣列縮減為 9\*3 = 27 的陣列：

**【小結】**

使用稀疏矩陣的情況：
- 當一個陣列有很多沒意義數據(0)或相同數據。

處理方法：
- 第一行記錄陣列共幾列幾行並且有幾個非0的值。
- 第二行開始用於紀錄每個非0值在陣列第幾列第幾行、值為多少。

## 二維陣列 轉 稀疏矩陣
**思路**
1. 遍歷原始的二維陣列，得到有效數據的個數(sum)。
2. 根據sum 就可以創建稀疏矩陣`parseMatrix int[sum+1][3]`
3. 將二維陣列的有效數據存入到稀疏矩陣。

## 稀疏矩陣 轉 二維陣列
**思路**
1. 先讀取稀疏矩陣第一行，根據第一行的數據創建原始的二維陣列，比如上方圖示`chessArr = int[11][11]`
2. 再讀取稀疏矩陣後幾行的數據，並賦給原始的二維陣列。

## 代碼實現
現在，我們用JAVA來將下方這個二維陣列轉維稀疏矩陣。


### 創建原始的二維陣列 11*11

0: 沒有旗子, 1:黑子, 2:藍子

//創建原始的二維陣列 11*11
//0: 沒有旗子, 1:黑子, 2:藍子
  int chessArr1[][] = new int[11][11];
  chessArr1[1][2] = 1;
  chessArr1[2][3] = 2;
//輸出原始二維陣列
  for(int[] row: chessArr1){
    for(int data:row){
       System.out.printf("%d ",data);
     }
        System.out.println();
   }


### 獲取非0數據個數
先遍歷二維陣列,獲取非0數據個數

//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]; //列:sum為非0值的個數+1列存放原始二維陣列資訊 行:列,行,非0值

//給稀疏矩陣賦值
sparseArr[0][0] = 11;
sparseArr[0][1] = 11;
sparseArr[0][2] = sum;

//遍歷二維陣列,將非0值存放到稀疏矩陣中
int count=0; //用於紀錄是第幾個非0數據
for(int i=0;i<11;i++){
    for(int j=0;j<11;j++){
        if(chessArr1[i][j] !=0){
            count++;
            sparseArr[count][0] = i;
            sparseArr[count][1] = j;
            sparseArr[count][2] = chessArr1[i][j];
        };
    }
}

//輸出稀疏矩陣
for(int[] row: sparseArr){
    for(int data:row){
        System.out.printf("%d\t",data);
    }
    System.out.println();
}


### 恢復原始二維陣列

//恢復原始二維陣列
int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];

//從稀疏矩陣第二行開始讀取數據,並賦給原始二維陣列
for(int i=1;i<sparseArr.length;i++){
    chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
}

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


現在，我們來實作將稀疏矩陣寫入txt檔和從txt檔中讀取出來

### 寫入稀疏矩陣到txt檔

import java.io.*;

File file = new File("./data.txt");
FileWriter out = new FileWriter(file); 

//寫入稀疏矩陣內容
for(int i=0;i<sum+1;i++){
    for(int j=0;j<3;j++){
        out.write(sparseArr[i][j]+"\t");
    }
    out.write("\r\n");
}
out.close();

### 讀取稀疏矩陣到txt檔

//讀取稀疏矩陣內容
BufferedReader in = new BufferedReader(new FileReader(file));  
String line;  //一行資料
int row=0;
int[][] arr2 = new int[sum+1][3]; //讀取後存放在此二維陣列

//逐行讀取,並將每個陣列放入到陣列中
while((line = in.readLine()) != null){
    String[] temp = line.split("\t"); 
    for(int j=0;j<temp.length;j++){
        arr2[row][j] = Integer.parseInt(temp[j]);
    }
    row++;
}
in.close();

//顯示讀取出的陣列
for(int i=0;i<sum+1;i++){
    for(int j=0;j<3;j++){
        System.out.print(arr2[i][j]+"\t");
    }
    System.out.println();
}
}