稀疏数组和队列
应用场景
编写五子棋
基本介绍
当一个数组的大部分元素为0、或者为同一个值时，可以使用稀疏数组来保存该数组
处理方法：
1）、记录数组一共有几行几列，有多少个不同的值
2）、把具有不同值得元素得行列及值记录在一个小规模的数组。
应用实例
编写五子棋的棋盘
二维数组转稀疏数组的思路：
- 遍历原始的二维数组，得到有效的个数sum - 根据sum创建稀疏数组的大小 - 将二维数组的有效数据存入稀疏数组稀疏数组转原始的二维数组的思路：
- 先读取第一行第一列，根据所得到得的第一行数据，创建原始的二维数组 - 在读取后面几行的数据，并赋值给原始的二维数组即可代码
public class SpraseArray {
public static void main(String[] args) {
// TODO Auto-generated method stub
//创建原始的二维数组，0：没有，1：黑色，2：蓝色
int chassArr1[][] = new int[11][11];
chassArr1[1][2] = 1;
chassArr1[2][3] = 2;
//输出原始的二维数组
for(int[] row:chassArr1) {
for(int data:row) {
System.out.printf( "%d\t",data);
}
System.out.println();
}
//将二维数组转稀疏数组的思想
//1先遍历二维数组，得到非0数据的个数
int sum=0;
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
if(chassArr1[i][j]!=0) {
sum++;
}
}
}
//2
int spraseArr[][] = new int[sum+1][3];
spraseArr[0][0] = 11;
spraseArr[0][1] = 11;
spraseArr[0][2] = sum;
//将非零的数组放入在稀疏数组中
int count=0;
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
if(chassArr1[i][j]!=0) {
count++;
spraseArr[count][0] = i;
spraseArr[count][1] = j;
spraseArr[count][2] = chassArr1[i][j];
}
}
}
System.out.println("得到的稀疏数组");
for (int i = 0; i < spraseArr.length; i++) {
System.out.printf("%d\t%d\t%d\t",spraseArr[i][0],spraseArr[i][1],spraseArr[i][2]);
System.out.println();
}
//将稀疏数组转化成二维数组
//读取第一行
System.out.println("恢复后的二维数组");
int chassArr2[][] = new int[spraseArr[0][0]][spraseArr[0][1]];
for(int i=1;i<spraseArr.length;i++) {
chassArr2[spraseArr[i][0]][spraseArr[i][1]] = spraseArr[i][2];
}
for(int[] row:chassArr2) {
for(int data:row) {
System.out.printf( "%d\t",data);
}
System.out.println();
}
//
}
}
- 课后练习
在前面的基础上，将稀疏数组保存到磁盘上，在恢复原来的数组，读取map.data进行恢复
import java.io.*;
/**
* 稀疏数组
*/
public class Sparsearray {
//棋盘的行数
public static final int row = 11;
//棋盘的列数
public static final int col = 11;
//创建保存稀疏数组的文件（当前项目跟路径下）
File file = new File( "/map.data");
public static void main(String[] args) throws Exception{
Sparsearray spa = new Sparsearray();
//获取稀疏数组
spa.getSparseArr();
//把稀疏数组还原成二维数组
spa.restore();
}
//获取稀疏数组
public void getSparseArr() {
//创建初始二维数组 11 * 11
int chessArr[][] = new int[row][col];
// 0表示没有棋子，1 表示白棋，2表示黑棋
chessArr[2][5] = 2;
chessArr[5][4] = 1;
chessArr[5][3] = 1;
chessArr[6][5] = 2;
System.out.println("初始数组");
// 获取非0个数
int sum = 0;
for (int[] row : chessArr) {
for (int data : row) {
System.out.printf("%d\t", data);
if (data != 0)
sum++;
}
System.out.println();
}
//创建稀疏数组
int sparseArr1[][] = new int[sum + 1][3];
//给稀疏数组赋初始值
sparseArr1[0][0] = chessArr.length;//行数
sparseArr1[0][1] = chessArr[1].length;//列数
sparseArr1[0][2] = sum;//有几个非0的值
//创建行计数器
int count = 0;
for (int i = 0; i < chessArr.length; i++) {
for (int j = 0; j < chessArr[0].length; j++) {
if (chessArr[i][j] != 0) {
count++;
sparseArr1[count][0] = i;
sparseArr1[count][1] = j;
sparseArr1[count][2] = chessArr[i][j];
}
}
}
System.out.println("稀疏数组");
for (int[] row : sparseArr1 ) {
for (int col : row ) {
System.out.printf("%d\t", col);
}
System.out.println();
}
//把棋盘存档，保存在本地磁盘
download(sparseArr1);
}
//把稀疏数组还原成二维数组
public int[][] restore() throws Exception{
//读档，获取保存在本地磁盘的稀疏数组
int[][] sparseArr2 = read();
//创建还原稀疏数组的二维数组对象
int[][] chessArr2 = new int[row][col];
System.out.println("===================从磁盘还原成稀疏数组===================");
//把稀疏数组还原成二维数组
for (int i=0;i<sparseArr2.length;i++){
System.out.printf("%d\t%d\t%d\t\n",sparseArr2[i][0],sparseArr2[i][1],sparseArr2[i][2]);
if (i!=0)
chessArr2[sparseArr2[i][0]] [sparseArr2[i][1]]= sparseArr2[i][2];
}
System.out.println("===================稀疏数组还原成二位数组===================");
for (int [] row :chessArr2){
for (int data:row){
System.out.printf("%d\t",data);
}
System.out.println();
}
return chessArr2;
}
//把棋盘存档，保存在本地磁盘
public void download(int[][]sparseArr1){
try {
FileOutputStream fileOutputStream = new FileOutputStream(file.getPath());
OutputStreamWriter outputStreamWriter = new OutputStreamWriter(fileOutputStream, "UTF-8");
for (int i = 0; i < sparseArr1.length; i++) {
//把稀疏数组保存到磁盘中
outputStreamWriter.write(sparseArr1[i][0] + "," + sparseArr1[i][1] + "," + sparseArr1[i][2] + ",");
}
//关闭输出流
outputStreamWriter.close();
fileOutputStream.close();
System.out.println("===================把稀疏数组保存到磁盘成功===================");
} catch (Exception e) {
e.printStackTrace();
System.out.println("===================把稀疏数组保存到磁盘失败===================");
}
}
//读档，从本地磁盘中读取
public int[][] read() throws Exception {
if (!file.exists()){
System.out.println("===================磁盘中不存在map.data文件===================");
return null;
}
System.out.println("===================从磁盘中读取map.data文件===================");
FileInputStream fileInputStream = new FileInputStream(file);
InputStreamReader inputStreamReader = new InputStreamReader(fileInputStream,"UTF-8");
StringBuffer stringBuffer = new StringBuffer();
while (inputStreamReader.ready()){
stringBuffer.append((char)inputStreamReader.read());
}
System.out.println("===================读取成功===================");
//关闭输入流
inputStreamReader.close();
fileInputStream.close();
//创建一个数组，用来接收稀疏数组保存在磁盘中的值
String[] sparse = stringBuffer.toString().split(",");
//创建一个稀疏数组，用来接收之前保存在磁盘中的值
int[][] sparseArr2 = new int[sparse.length/3][3];
for (int i =0;i<sparse.length;i++){
sparseArr2[i/3][i%3] =Integer.valueOf(sparse[i]);
}
return sparseArr2;
}
}
- 总结
对与数组就有多个相同的元素时，可以将其压缩为稀疏数组。掌握了如何将稀疏数组转换成二维数组，二维数组转换成稀疏数组。猜想可以应用于多维数组。
版权声明：本文为MGfanfan原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。