資料結構（Java實作）- 稀疏sparsearray數組

1、先看一個實際的需求

2、基本介紹

3、實作

3.1二維數組轉稀疏數組

3.2稀疏數組轉二維數組

4、代碼實作：

1、先看一個實際的需求

  在編寫的五子棋程式中，有存盤退出和續上盤的功能。

這時候就要求我們要使用二維數組來記錄棋盤，如下圖所示：

在上圖的二維數組中用1表示黑棋，用2表示藍棋

分析問題：我們可以發現該二維數組的很多值是預設值0，是以記錄了很多沒有意義的資料。這時候就需要用稀疏數組對這個二維數組進行壓縮。

2、基本介紹

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

稀疏數組的處理方法是:

1. 記錄數組一共有幾行幾列，有多少個不同的值
2. 把具有不同值的元素的行列及值記錄在一個小規模的數組中，進而縮小程式的規模

而得到的這個小規模的數組就是稀疏數組

舉例如下：

一個原始二維數組：                                     轉換為稀疏數組後：

分析一下稀疏數組的資料特征：

  首先這個稀疏數組是  ： 9x3 （9行3列）的二維數組 （稀疏數組都是3列，也就是l裡面資料的列序号下标的最大值為3-1=2）

第一行資料 6   7   8 ：表示原二維數組一共6行 、7列、8個不同數值

第二行資料 0   3   22：0和3分别表示，數值22在原二維數組中的行序号下标和列序号下标（表示在原二維數組的0+1行 3+1列）

（後面各行的資料特征和第二行的一樣）

原始二維數組：6x7=42  轉換    稀疏數組：9x3=27

可以看出稀疏數組起到了一個把原始二維數組規模變小的作用

3、實作

3.1二維數組轉稀疏數組

思路：

1. 周遊原始二維數組，得到有效資料的個數sum
2. 根據sum就可以建立稀疏數組 sparseArr int[sum+1][3]
3. 将二維數組的有效資料存入到稀疏數組中

3.2稀疏數組轉二維數組

思路：

1. 先讀取稀疏數組的第一行，根據第一行的資料，建立原始二維數組，比如上面棋盤中的 chessArr = int[11][11]
2. 然後讀取稀疏數組的後幾行的資料，并指派給建立好的原始二維數組即可

4、代碼實作：

package com.zhukun.SparseArray;

import java.awt.Desktop;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class SparseArray {
	public static void main(String[] args) throws Exception {
		//先建立一個二維數組 11*11
		//0:表示沒有棋子，1表示黑子  2表示藍子
		int chessArr1[][] = new int[11][11];
		chessArr1[1][2] = 1;
		chessArr1[2][3] = 2;
		//輸出原始二維數組
		System.out.println("輸出原始二維數組");
		for(int[] row: chessArr1)
		{
			for(int data: row)
			{
				System.out.print(data+" ");
			}
			System.out.println();
		}
		//原始二維數組轉稀疏數組
		//1、先周遊原始二維數組，得到有效資料的個數sum
		int sum=0;
		for(int[] row:chessArr1) {
			for(int data:row) {
				sum=data!=0?sum+1:sum;  //三元運算符判斷 如果不為0則sum+1
			}
		}
		System.out.println("有效資料個數："+sum);  //輸出不為零的個數
		//2、根據sum就可以建立稀疏數組 sparseArr int[sum+1][3]
		int sparseArr[][]=new int[sum+1][3];
		sparseArr[0][0]=chessArr1.length;   //原二維數組的行數
		sparseArr[0][1]=chessArr1[0].length;  //原二維數組的列數
		sparseArr[0][2]=sum;
		
		//周遊二維數組，将不為0的數放入稀疏數組中
		int count=0;     //用于記錄第幾個非零資料    
		for(int i=0;i<chessArr1.length;i++) {
			for(int j=0;j<chessArr1.length;j++) {
				if(chessArr1[i][j]!=0) {
					count++;
					sparseArr[count][0]=i;
					sparseArr[count][1]=j;
					sparseArr[count][2]=chessArr1[i][j];
				}
			}
		}
		
		//列印稀疏數組
		System.out.println("稀疏數組為:");
		for(int[] row:sparseArr) {
			for(int data:row) {
				System.out.print(data+"   ");
			}
			System.out.println();
		}
		
		//稀疏數組還原成原二維數組
		//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];
		}
		
		//列印還原後的二維數組
		System.out.println("還原後的二維數組為:");
		for(int[] row:chessArr2) {
			for(int data:row) {
				System.out.print(data+" ");
			}
			System.out.println();
		}
		
		//将稀疏數組儲存到硬碟上
		File file = new File("C:\\Users\\zhukun\\Desktop\\app\\map.txt");
		FileOutputStream fos = new FileOutputStream(file);
		OutputStreamWriter write = new OutputStreamWriter(fos, "UTF-8");
		// 輸出稀疏數組的形式
		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]);
			if (i == sparseArr.length - 1)
			{
				write.append(sparseArr[i][0] + "," + sparseArr[i][1] + "," + sparseArr[i][2]);
			} 
			else
			{
				write.append(sparseArr[i][0] + "," + sparseArr[i][1] + "," + sparseArr[i][2] + ",");
			}
		}
		System.out.println("寫入檔案中...");
		write.close();
		fos.close();
		System.out.println("打開檔案中...");
		Desktop.getDesktop().open(file);
		System.out.println("------------------------------先讀取_map.txt");
		// 建立 FileReader 對象
		FileInputStream fis = new FileInputStream(file);
		InputStreamReader reader = new InputStreamReader(fis, "UTF-8");
		StringBuffer sb = new StringBuffer();
		while (reader.ready())
		{
			sb.append((char) reader.read());// 轉成char加到StringBuffer對象中
		}
		System.out.println(sb.toString());
		reader.close();// 關閉讀取流
		fis.close();// 關閉輸入流,釋放系統資源
	
		
		System.out.println("------------------------------恢複成稀疏數組_sparseArrHf");
		// 1.建立對應的稀疏數組
		String[] str = sb.toString().split(",");
		int sparseArrHf[][] = new int[str.length / 3][3];
		// 2.給稀疏數組指派
		int i = 0;
		for (String s : str) {
			sparseArrHf[i/3][i % 3]=Integer.parseInt(s);
			i++;
		}

		System.out.println("------------------------------再恢複成二維數組_chessArr22");
		// 将稀疏數組 -->恢複成 原始的二維數組
		/*
		 * 1. 讀取稀疏數組的第一行,根據第一行的資料,建立原始的二維數組,比如上面的 chessArr2 = int[11][11];
		 * 
		 * 2. 在讀取稀疏數組後幾行的資料,并賦給 原始的二維數組 即可.
		 */

		// 1. 讀取稀疏數組的第一行,根據第一行的資料,建立原始的二維數組
		int chessArr22[][] = new int[sparseArrHf[0][0]][sparseArrHf[0][1]];

		// 2. 在讀取稀疏數組後幾行的資料,并賦給 原始的二維數組 即可.
		for (int i3 = 1; i3 < sparseArrHf.length; i3++) {
			chessArr22[sparseArrHf[i3][0]][sparseArrHf[i3][1]] = sparseArrHf[i3][2];
		}

		// 輸出恢複的二維數組
		System.out.println();
		for (int[] row : chessArr22) {
			for (int data : row) {
				System.out.printf("%d\t", data);
			}
			System.out.println();
		}
		System.out.println("--------------------------------------------------------恢複完成");
	}
		
}