极简Java数据结构-稀疏数组SparseArray｜CSDN创作打卡

极简Java数据结构-稀疏数组SparseArray｜CSDN创作打卡 经典算法面试题

字符串匹配问题:

暴力匹配[简单，效率低下]KMP算法《部分匹配表》 汉罗塔游戏

分治算法 八皇后问题

回溯算法 马踏棋盘

深度优化遍历算法（DFS）+贪心算法 数据结构和算法的关系

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

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

数据结构分为线性结构和非线性结构线性结构

数据元素之间一对一的的线性关系有两种不同的存储结构：
顺序结构—>顺序表（元素连续）（数组）链式存储结构—>链表（元素不一定是连续的，元素节点存放数据元素及相邻元素的地址信息）（链表）

常见的结构有:数组、队列、链表和栈 非线性结构

二维数组、多维数组、广义表、树结构、图结构 稀疏表

适用场景

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

稀疏数组的处理方法：

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

例子：

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

代码复现：

package icu.lookyousmileface.sparsearray;

import java.io.*;


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("rn");
        }
        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();
        }

    }
}

执行结果：