极简Java数据结构-稀疏数组SparseArray

👨🏻‍🎓博主介绍：大家好，我是芝士味的椒盐，一名在校大学生，热爱分享知识，很高兴在这里认识大家🌟
🌈擅长领域：Java、大数据、运维、电子
🙏🏻如果本文章各位小伙伴们有帮助的话，🍭关注+👍🏻点赞+🗣评论+📦收藏，相应的有空了我也会回访，互助！！！
🤝另本人水平有限，旨在创作简单易懂的文章，在文章描述时如有错，恳请各位大佬指正，在此感谢！！！

@[TOC]

经典算法面试题

• 字符串匹配问题:
  • 暴力匹配[简单，效率低下]
  • KMP算法《部分匹配表》
• 汉罗塔游戏
  • 分治算法
• 八皇后问题
  • 回溯算法
• 马踏棋盘
  • 深度优化遍历算法（DFS）+贪心算法

数据结构和算法的关系

• 数据结构是一门研究组织数据方式的学科，有了编程语言也就有了数据结构.学好数据结构可以编写出更加漂亮,更加有效率的代码。
• 程序 = 数据结构 + 算法

常见算法

• 修路问题 => 最小生成树(加权值)【数据结构】+ 普利姆算法
• 最短路径问题 => 图+弗洛伊德算法
• 汉诺塔 => 分支算法
• 八皇后问题 => 回溯法

线性结构和非线性结构

• 数据结构分为线性结构和非线性结构
• 线性结构
  1. 数据元素之间一对一的的线性关系
  2. 有两种不同的存储结构：
     1. 顺序结构—>顺序表（元素连续）（数组）
     2. 链式存储结构—>链表（元素不一定是连续的，元素节点存放数据元素及相邻元素的地址信息）（链表）
  • 常见的结构有:数组、队列、链表和栈
• 非线性结构
  • 二维数组、多维数组、广义表、树结构、图结构

稀疏表

• 适用场景

  • 当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组

• 稀疏数组的处理方法：

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

• 例子：
  

• 原始二维数组和稀疏数组之间的转换原理：
  

• 代码复现：

  package icu.lookyousmileface.sparsearray;
  
  import java.io.*;
  
  /**
   * @author 芝士味的椒盐
   * @title: SparseArray
   * @projectName DataStructure_Algorithm
   * @date 2020/12/14 10:17
   * 模拟棋盘
   */
  public class SparseArray {
  
      private static final int originalRow = 11;
      private static final int originalCol = 11;
      private static int itWorksNum;
      private static final File filePath = new File("map.data");
  
      public static void main(String[] args) throws IOException {
          //定义原始数组
          int[][] originalArray = new int[originalRow][originalCol];
          originalArray[1][2] = 1;
          originalArray[2][3] = 2;
          originalArray[3][4] = 2;
          System.out.println("原始数组状态：");
          for (int[] row : originalArray) {
              for (int data : row) {
                  itWorksNum = data != 0 ? ++itWorksNum : itWorksNum;
                  System.out.print(data+"\t");
              }
              System.out.println();
          }
  
  
          //定义稀疏数组 originalArray.length表示行，originalArray[0].length表示列
  
          int[][] sparseArray = new int[itWorksNum + 1][3];
          sparseArray[0][0] = 11;
          sparseArray[0][1] = 11;
          sparseArray[0][2] = itWorksNum;
          int count = 0;
          for (int i = 0; i < originalArray.length; i++) {
              for (int i1 = 0; i1 < originalArray[0].length; i1++) {
                  if (originalArray[i][i1] != 0) {
                      count++;
                      sparseArray[count][0] = i;
                      sparseArray[count][1] = i1;
                      sparseArray[count][2] = originalArray[i][i1];
                  }
              }
          }
          System.out.println("稀疏数组状态：");
          for (int[] row : sparseArray) {
              for (int data : row) {
                  itWorksNum = data != 0 ? ++itWorksNum : itWorksNum;
                  System.out.print(data+"\t");
              }
              System.out.println();
          }
  
          //稀疏数组写入到map.data
          FileWriter fileWriter = new FileWriter(filePath);
          for (int i = 0; i < sparseArray.length; i++) {
              for (int i1 = 0; i1 < sparseArray[0].length; i1++) {
                  fileWriter.write(sparseArray[i][i1] + "\t");
              }
              fileWriter.write("\r\n");
          }
          fileWriter.close();
  
  //        ----------复原-------
          //将map.data中的数据读取到稀疏数组中,先读取row确定row，col是确定的
          int row = 0;
          String line;
          BufferedReader bufferedReader = null;
          bufferedReader = new BufferedReader(new FileReader(filePath));
          while ((line = bufferedReader.readLine()) != null) {
              ++row;
          }
          bufferedReader.close();
          //根据获得的row确定稀疏数组，切片
          int rowtmp = 0;
          int[][] originalArrayed = new int[row][3];
          bufferedReader = new BufferedReader(new FileReader(filePath));
          while ((line = bufferedReader.readLine()) != null) {
              String[] splited = line.split("\t");
              for (int i = 0; i < splited.length; i++) {
                  originalArrayed[rowtmp][i] = Integer.parseInt(splited[i]);
              }
              ++rowtmp;
          }
  //        原始数组
          int[][] oArrays = new  int[originalArrayed[0][0]][originalArrayed[0][1]];
  
          for (int i = 1; i < originalArrayed.length; i++) {
              for (int i1 = 0; i1 < originalArrayed[0].length; i1++) {
                  if (true){
                      oArrays[originalArrayed[i][1]-1][originalArrayed[i][1]] = originalArrayed[i][2];
                      continue;
                  }
              }
          }
          System.out.println("稀疏数组复原状态：");
          for (int[] rowss : oArrays) {
              for (int data : rowss) {
                  System.out.print(data+"\t");
              }
              System.out.println();
          }
  
      }
  }
  
  

  执行结果：