开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> Java数据结构与算法笔记 -> 正文阅读

[数据结构与算法]Java数据结构与算法笔记

????????2021年8月2日16:41:25，天气晴，今天开始复习数据结构与算法，其实就是从头开始，大二没好好学QAQ，此笔记是在学习B站尚硅谷Java数据结构与java算法视频时所做记录。

一、稀疏数组

作用

? ? ? ? 当一个二维数组中的大多数数据默认值为0，或者为同一个数值时，记录了很多无用数据，可以转化为稀疏数组用以保存，

例如：?

左侧为初始数组（8*8的二维数组），右侧为稀疏数组。稀疏数组行数为初始数组有效值的数量+1，列数固定为3，即是个7*3的二维数组。稀疏数组记录初始数组的行列数，有效值，用以缩小数组规模

第一行保存的是初始数组的行数、列数、有效值的个数
第二行开始保存的是有效值的行数、列数、有效值

转换思路

初始二维数组转换为稀疏数组：

定义一个sum，遍历初始数组，得到有效值个数
创建稀疏数组：行数为sum+1，列数为固定值3
将初始数组有效值及其行数列数存入稀疏数组

稀疏数组转化为二维数组：

定义一个二维数组，行数为稀疏数组第一行第一列，列数为第一行第二列
从第二列开始遍历稀疏数组，将有效值还原至二维数组对应位置

?下面是转换demo：

package SparseArrayAndQueues;

import java.io.*;

public class SparseArray {
    public static void main(String[] args) {
        //定义数组
        int arr1[][] = new int[10][10];
        //给数组赋值
        arr1[0][0] = 1;
        arr1[0][8] = 3;
        arr1[2][3] = 2;
        arr1[4][6] = 4;
        arr1[5][5] = 5;
        arr1[8][8] = 6;
        arr1[9][7] = 7;
        arr1[6][0] = 9;

        //遍历初始数组、  定义sum：有意义数据的个数
        int sum = 0;
        System.out.println("初始数组：");
        for(int i = 0; i < arr1.length; i++){
            for (int j = 0 ; j < arr1[i].length; j++){
                System.out.printf("%d\t",arr1[i][j]);
                if (arr1[i][j] != 0){
                    sum++;
                }
            }
            System.out.println();
        }

        //定义稀疏数组sparsearray,共有sum+1行，固定3列
        int sparsearray[][] = new int[sum+1][3];
        //第一行第一列：二维数组总行数、第二列：二维数组总列数、第三列：初始数组有效值个数
        sparsearray[0][0] = arr1.length;
        sparsearray[0][1] = arr1[0].length;
        sparsearray[0][2] = sum;
        //为稀疏数组赋值,定义count为稀疏数组的行数，赋值后count+1换行
        int count = 1;
        for(int i = 0; i < arr1.length; i++){
            for (int j = 0 ; j < arr1[i].length; j++){
                if (arr1[i][j] != 0){
                    sparsearray[count][0] = i;
                    sparsearray[count][1] = j;
                    sparsearray[count][2] = arr1[i][j];
                    count++;
                }
            }
        }

        //遍历稀疏数组
        System.out.println("稀疏数组：");
        for (int i = 0; i < sparsearray.length; i++){
            for (int j = 0; j < sparsearray[i].length; j++){
                System.out.printf("%d\t",sparsearray[i][j]);
            }
            System.out.println();
        }

        //将稀疏数组还原，定义一个新的二维数组，行数为稀疏数组第一行第一列，列数为第一行第二列
        int arr2[][] = new  int[sparsearray[0][0]][sparsearray[0][1]];
        //从第二行开始遍历稀疏数组为二维数组赋值
        for (int i = 1; i < sparsearray.length; i++){
            for (int j = 0; j < sparsearray[i].length; j++){
                //arr2[稀疏数组有效值所在行][稀疏数组有效值所在列] = 稀疏数组有效值
                arr2[sparsearray[i][0]][sparsearray[i][1]] = sparsearray[i][2];
            }
        }


        //遍历还原后的稀疏数组
        System.out.println("稀疏数组还原为二维数组");
        for(int i = 0; i < arr2.length; i++){
            for (int j = 0 ; j < arr2[i].length; j++){
                System.out.printf("%d\t",arr2[i][j]);
            }
            System.out.println();
        }


        System.out.println("以下扩展，将稀疏数组通过IO流存取——————————————————————————————————————————————————————————————————————————");
        //将稀疏数组存入磁盘
        writeArray(sparsearray);

        //读取磁盘中的稀疏数组
        System.out.println("读取磁盘稀疏数组");
        int[][] sarr2 = readsparsearray();


        for(int i = 0; i < sarr2.length; i++){
            for (int j = 0 ; j < sarr2[i].length; j++){
                System.out.printf("%d\t",sarr2[i][j]);
            }
            System.out.println();
        }
    }

    //将稀疏数组存入磁盘
    public static void writeArray(int[][] sparsearray){
        FileWriter fos = null;
        try {
            fos = new FileWriter("data.txt");
                for (int[] arr : sparsearray){
                    fos.write(arr[0]+"\t"+arr[1]+"\t"+arr[2]);
                    fos.write("\r\n");
                }
            fos.flush();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }finally {
            if (fos!=null){
                try {
                    fos.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
    }

    //从磁盘读取文件
    public static int[][] readsparsearray(){

        int[][] sparse2 = null;
        boolean isnotread=false;
        BufferedReader fis = null;
        try {
            fis = new BufferedReader(new FileReader(new File("data.txt")));
            String lineStr = null;
            int curCount = 0;
            while (((lineStr=fis.readLine())!=null)) {
                String[] tempStr = lineStr.split("\t");
                    if(!isnotread){
                        sparse2 = new int[Integer.parseInt(tempStr[2])+1][3];
                        sparse2[curCount][0] = Integer.parseInt(tempStr[0]);
                        sparse2[curCount][1] = Integer.parseInt(tempStr[1]);
                        sparse2[curCount][2] = Integer.parseInt(tempStr[2]);
                        curCount++;
                        isnotread=true;
                    }else {
                        sparse2[curCount][0] = Integer.parseInt(tempStr[0]);
                        sparse2[curCount][1] = Integer.parseInt(tempStr[1]);
                        sparse2[curCount][2] = Integer.parseInt(tempStr[2]);
                        curCount++;
                    }

            }

        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            try {
                fis.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return sparse2;
    }


}

运行结果：

二、队列

2021年8月3日09:47:58? 暴雨，?今天下大雨了，差点落汤鸡QAQ

介绍：

????????队列是一个有序列表、可以用数组或是链表来实现
? ??????队列遵循先入先出规则：先存入队列的数据要先取出

????????队列本身是有序列表、若使用数组的结构来存储队列的数据，则声明如下图，其中maxSize是该队列的最大容量
????????因为队列的输入输出是分别从前后端来处理，因此需要两个变量front、rear分别记录队列前后端的下标，front会随着数据输出而改变，二rear则是随着数据输入而改变，如图所示

思路分析

入队：尾指针后移一位；rear+1，front==rear【空】

? ? ? ? ? ?若尾指针小于队列的最大下标maxSize-1（数组起始为0故此），则将数据存入rear所指的数组元素中，否则无法存入数据。rear==maxSize-1【队列满】

代码思路

首先编写一个ArrayQueue类，
定义属性：
最大容量：maxSize
队列头：front
队列尾：rear
数组：arr
定义构造器：传入最大容量
判断队列是否满：rear == maxSize-1
判断队列是否为空：rear ==?front
添加数据到队列：
先判断队列是否已满、满则返回
没满则队尾rear后移：rear++
给数组赋值arr【rear】 =?n? （n为添加的值）
出队列，取队列
判断队列是否为空、满则返回，或抛出队列空异常提示
不为空则队头front后移：front++
返回数组?arr【front】
显示队列的所有数据，遍历
判断队列是否为空，为空则不遍历
不为空则遍历
显示队列头数据
判断是否为空、为空返回
不为空返回数据：arr【front+1】

代码demo：

package SparseArrayAndQueues;

public class ArrayQueue {

    public static void main(String[] args) {
        //初始化
        QuereArray quereArray = new QuereArray(4);
        //添加数据，多添加一个，看看能不能继续添加，然后遍历
        quereArray.add(1);
        quereArray.add(2);
        quereArray.add(3);
        quereArray.add(4);
        quereArray.add(5);
        quereArray.show();
        System.out.println("队头");
        quereArray.head();
        //取出数据后遍历并看队头
        quereArray.get();
        System.out.println("取出一个数后的队列:");
        quereArray.show();
        System.out.println("队头");
        quereArray.head();
        //连续取出数据，再遍历
        quereArray.get();quereArray.get();quereArray.get();quereArray.get();
        quereArray.show();
    }

    static class QuereArray{
        //最大容量、队头、队尾、数组
        private int maxSize;
        private int front;
        private int rear;
        private int arr[];

        //构造器,给队列初始化
        public QuereArray(int maxValue){
            maxSize = maxValue;
            front = -1; //指向头部
            rear = -1;  //指向尾部，初始化头尾相等
            arr = new int[maxSize];
        }

        //判断队列是否为空
        public boolean isEmpty(){
            return rear == front;
        }

        //判断队列是否为满
        public boolean isFull(){
            return rear == maxSize-1;
        }

        //添加数据
        public void add(int n){
            //先判断队列是否已满，满则返回
            if (isFull()){
                System.out.println("队列已满，不可再添加");
                return;
            }
            arr[++rear] = n;
            return;
        }

        //取出数据
        public int get(){
            //判断队列是否为空、是则返回
            if(isEmpty()){
                System.out.println("队列已空，不去再取");
                return 0;
            }
            front++;
            return arr[front];
        }

        //遍历队列
        public void show(){
            if (isEmpty()){
                System.out.println("队列为空，无法遍历");
                return;
            }
            for(int i = front+1; i<=rear;i++){
                System.out.println(arr[i]);
            }
            return;
        }

        public void head(){
            if (isEmpty()){
                System.out.println("队列为空，无法取出头部");
                return;
            }
            System.out.println( arr[front+1]);
            return;
        }

    }

}

运行结果：

这种队列的问题就是数组用了一个后无法再用了，队列满了之后无法取出后无法再添加，原因是没有取模，下面用环形队列解决，取模防止数组越界。

三、环形队列

思路分析

队头front变量做调整：指向队列第一个元素，初始化为front=0
队尾rear变量做调整：指向队列最后一个元素的后一个位置，故此需要空出个空间作为约定，则创建数组时多加一位：想创建3则int[4]。初始化rear=0
当队列满时，条件改变为(rear+1)%maxSize == front
当队列空时，rear==front
队列的有效数据个数(rear+maxSize-front)%maxSize

代码思路基本不变，demo如下：

package SparseArrayAndQueues;

public class ArrayQueue2 {

    static class QuereArray{
        //最大容量、队头、队尾、数组
        private int maxSize;
        private int front;
        private int rear;
        private int[] arr;

        //构造器,给队列初始化
        public QuereArray(int maxValue){
            maxSize = maxValue;
            front = 0; //指向头部
            rear = 0;  //指向尾部，初始化头尾相等
            arr = new int[maxSize];
        }

        //判断队列是否为空
        public boolean isEmpty(){
            return front==rear;
        }

        //判断队列是否为满
        public boolean isFull(){
            return (rear+1)%maxSize==front;
        }

        //添加数据
        public void add(int n){
            //先判断队列是否已满，满则返回
            if (isFull()){
                System.out.println("队列已满，不可再添加");
                return;
            }
            arr[rear] = n;
            System.out.println("添加数据：arr["+rear+"]="+arr[rear] );
            rear = (rear+1)%maxSize;
            return;
        }

        //取出数据
        public void get(){
            //判断队列是否为空、是则返回
            if(isEmpty()){
                return ;
            }
            System.out.println("取出：arr["+front+"]="+arr[front]);
            front = (front+1)%maxSize;
            return;
        }

        //遍历队列
        public void show(){
            if (isEmpty()){
                System.out.println("队列为空，无法遍历");
                return;
            }
            //遍历有效个数
            for(int i = front; i<front+(rear+maxSize-front)%maxSize;i++){
                System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);
            }
            return;
        }

        public void head(){
            if (isEmpty()){
                System.out.println("队列为空，无法取出头部");
                return;
            }
            System.out.println("队头：arr["+front+"]="+arr[front]);
            return;
        }

    }

    public static void main(String[] args) {
        //初始化
        QuereArray quereArray = new QuereArray(4);
        //添加数据，多添加一个，看看能不能继续添加，然后遍历
        quereArray.add(1);
        quereArray.add(2);
        quereArray.add(3);
        quereArray.add(4);
        quereArray.show();
        quereArray.head();
        //取出数据后遍历并看队头
        quereArray.get();
        System.out.println("取出一个数后的队列:");
        quereArray.show();
        quereArray.head();
        //连续取出数据，再遍历
        quereArray.get();quereArray.get();quereArray.get();quereArray.get();
        quereArray.show();
        quereArray.head();
        quereArray.add(1);
        quereArray.add(2);
        quereArray.add(3);
        quereArray.add(4);
        quereArray.show();
        quereArray.head();
    }
}

代码截图：?