数据结构（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("--------------------------------------------------------恢复完成");
	}
		
}