稀疏数组

2023-12-13 20:22:33

案例需求

编写的五子棋程序中，有存盘退出和续上盘的功能。

因为该二维数组的很多值是默认值0, 因此记录了很多没有意义的数据==》稀疏数组

基本介绍

当一个数组中大部分元素为０，或者无效数据数量远大于有效数据数量，可以使用稀疏数组来保存该数组，以减少存储空间。

处理方法

记录数组一共有几行几列，有多少个不同的值
把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

举例

原二维数组　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

稀疏数组

第一行：11（有11行数据）11（有11列数据）2（不同的值有两个）

第二行：1（有效值在第二行）2（有效值在第3列）1（值是1），以此类推

应用实例

使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等)
把稀疏数组存盘，并且可以从新恢复原来的二维数组数

大概流程

代码

public static void main(String[] args) throws Exception {
  //创建一个二维数组
  //0代表没有数据，1代表黑子，2代表白子
  int[][] chessArray1 = new int[11][11];
  chessArray1[1][2]=1;
  chessArray1[2][3]=2;
  //输出原始的二维数组
  for (int[] row : chessArray1){
    for(int item : row){
      System.out.printf("%d\t", item);
    }
    System.out.println();
  }
  //将二维数组转化为稀疏数组
  //1. 循环遍历二维数组，得到有效数据的个数
  int sum = 0;
 for (int i = 0; i < chessArray1.length; i++){
   for (int j = 0; j < chessArray1[i].length; j++){
     if(chessArray1[i][j] != 0){
       sum++;
     }
   }
 }
  System.out.println("sum = " + sum);
 //2. 创建稀疏数组
  //赋值
  int[][] sparseArray = new int[sum + 1][3];
  sparseArray[0][0] = 11;
  sparseArray[0][1] = 11;
  sparseArray[0][2] = sum;
  //遍历二维数组，将有效数组放到sparseArray中
  int count = 0;
  for (int i = 0; i < chessArray1.length; i++){
    for (int j = 0; j < chessArray1[i].length; j++){
      if(chessArray1[i][j] != 0){
        count++;
        sparseArray[count][0] = i;
        sparseArray[count][1] = j;
        sparseArray[count][2] = chessArray1[i][j];
      }
    }
  }
  //输出得到的稀疏数组
  for (int[] row : sparseArray){
    for(int item : row){
      System.out.printf("%d\t", item);
    }
    System.out.println();
  }
  //将二维数组存储到磁盘的文件上
  String path = "E:\\java\\idea\\place\\DataStructure/info.txt";
  FileWriter fileWriter=null;
  File file = new File(path);
  try {
    fileWriter= new FileWriter(file);
    for (int[] array : sparseArray) {
      fileWriter.write(array[0]+"\t"+array[1]+"\t"+array[2]);
      fileWriter.write("\r\n");
    }
  }catch (Exception e){
    e.printStackTrace();
  }finally {
    try {
      if(fileWriter != null){
        fileWriter.close();
      }
    }catch (Exception e){
      e.printStackTrace();
    }
  }


  int[][] sparseArray2=null;
  boolean isNotRead=false;
  BufferedReader bufferedReader;
  bufferedReader=new BufferedReader(new FileReader(file));
  String lineStr;
  int curCount=0;
  while ((lineStr=bufferedReader.readLine())!=null){
    String[] tempStr=lineStr.split("\t");
    if(!isNotRead){
      sparseArray2=new int[Integer.parseInt(tempStr[2])+1][3];
      sparseArray2[curCount][0]=Integer.parseInt(tempStr[0]);
      sparseArray2[curCount][1]=Integer.parseInt(tempStr[1]);
      sparseArray2[curCount][2]=Integer.parseInt(tempStr[2]);
      curCount++;
      isNotRead=true;
    }else {
      sparseArray2[curCount][0]=Integer.parseInt(tempStr[0]);
      sparseArray2[curCount][1]=Integer.parseInt(tempStr[1]);
      sparseArray2[curCount][2]=Integer.parseInt(tempStr[2]);
      curCount++;
    }
  }
  bufferedReader.close();
  System.out.println("==================");
  assert sparseArray2 != null;
  for (int[] row : sparseArray2){
    for(int item : row){
      System.out.printf("%d\t", item);
    }
    System.out.println();
  }
  System.out.println("==================");


  //将稀疏数组转化为二维数组
  int[][] chessArray2 = new int[sparseArray[0][0]][sparseArray[0][1]];
  for(int i = 1; i < sparseArray.length; i++){
    chessArray2[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
  }
  //输出二维数组
  for (int[] row : chessArray2){
    for(int item : row){
      System.out.printf("%d\t", item);
    }
    System.out.println();
  }
}

二维数组转稀疏数组思路

循环变量二维数组，得到有效数据的个数sum
根据sum创建稀疏数组new sparseArray[sum+1][3]
将二维数组中的有效数据存储到稀疏数组中

稀疏数组转二维数组思路

根据稀疏数组第一行的数据创建出二维数组
在读取稀疏数组后面的数据，赋值给二维数组

码农公寓