数据结构与算法（Java）

一、稀疏数组

/**
 * 稀疏数组（三列多行【第一行：表示共几行几列】）
 *
 * <br>CreateDate 2022/3/1 0:08
 */
public class SparseArr {
    public static void main(String[] args) {
        // 1.定义一个数组
        int[][] arr = new int[11][11];
        // 2.存放数值(1.为白子;2为黑子;0为空;)
        arr[1][1] = 1;
        arr[2][2] = 1;
        arr[3][3] = 2;
        arr[4][4] = 2;
        arr[6][6] = 2;
        getSparseArr(arr);
    }

    /***
     *给一个二维数组，将压缩成一个稀疏数组
     *
     * @param arr 二维数组
     * @author xusj
     * <br>CreateDate 2022/3/1 0:13
     */
    public static void getSparseArr(int[][] arr) {
        // 行
        int row = arr.length;
        // 列
        int col = arr[0].length;
        // 记录有效数值
        int sum = 0;

        // 1,循环得到二维数组的一共有几个不为零的值（或者最多的值以外的值）【初学者注意数组越界问题】
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (arr[i][j] != 0) {
                    // 有效数字加一
                    sum++;
                }
            }
        }
        System.out.println("有效数据一共有：" + sum);
        // 定义一个稀疏数组
        int[][] sparseArr = new int[sum + 1][3];
        // 二维数组的行
        sparseArr[0][0] = row;
        // 二维数组的列
        sparseArr[0][1] = col;
        // 二维数组的有效值数量
        sparseArr[0][2] = sum;
        // 从稀疏数组的第二行开始存放数据,定义一个开始的行号
        int count = 1;
        // 循环数组将有效值存放到稀疏数组中
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (arr[i][j] != 0) {
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = arr[i][j];
                    count++;
                }
            }
        }
        System.out.println("稀疏数组如下：");
        for (int i = 0; i < sum + 1; i++) {
            for (int j = 0; j < 3; j++) {
                // 不换行
                System.out.print(sparseArr[i][j] + "\t");
            }
            // 换行
            System.out.println();
        }


        // 二：将稀疏数组逆向回二维数组
        // 1.原数组的行列,构建原数组
        int a = sparseArr[0][0];
        int b = sparseArr[0][1];

        int[][] ints = new int[a][b];
        // 循环稀疏数组
        for (int i = 1; i < sparseArr.length; i++) {
            ints[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
        System.out.println("原有数组为：");
        for (int[] anInt : ints) {
            for (int i : anInt) {
                System.out.print(i + "\t");
            }
            System.out.println();
        }

    }
}

二、队列

1、普通队列

/**
 * 完成普通队列
 *
 * @author xusj
 * <br>CreateDate 2022/3/5 17:19
 */
public class QueueNormal {
    /**
     * 测试代码
     */
    public static void main(String[] args) {
        MyQueue myQueue = new MyQueue(5);
        myQueue.push(3);
        myQueue.push(4);
        myQueue.push(5);
        myQueue.push(6);
        myQueue.push(7);
//        myQueue.push(7);
//        myQueue.push(7);
        myQueue.printOut();
        System.out.println();
        for (int i = 0; i < 1000; i++) {
            myQueue.pull();
        }
    }

    // 总：先入后出
    // 1.构建一个队列容器
    // 2.入队列
    // 2.1判断队列是否满？不能入：入队列
    // 3.出队列
    // 3.1判断队列是否为空？无：出
    static class MyQueue {
        // 1.队列最大长度
        private int maxSize;
        // 2.头指针
        private int front;
        // 3.尾指针
        private int rear;
        // 4.容器
        private int[] queue;

        /***
         * 构造一个队列
         *
         * @param maxSize 队列最大长度
         * @author xusj
         * <br>CreateDate 2022/3/5 17:47
         */
        public MyQueue(int maxSize) {
            this.maxSize = maxSize;
            this.queue = new int[maxSize];
            this.front = -1;
            this.rear = -1;
        }

        /**
         * 队列尾指针==队列的最大长度
         */
        public boolean isFull() {
            return rear == maxSize - 1;
        }

        /**
         * 队列尾指针==头指针
         */
        public boolean isEmpty() {
            return front == rear;
        }

        /**
         * 入队：首先判断队列是否已满
         * 因为尾指针定义为当前队列所在的位置，所以可以判断
         */
        public boolean push(int num) {
            if (isFull()) {
                throw new RuntimeException("队列已满");
            }
            queue[++rear] = num;
            return true;
        }

        /**
         * 出队列：
         * 1.首先判断队列是否为空，
         * 2.尾指针--，指向最后一个元素
         */
        public int pull() {
            if (isEmpty()) {
                throw new RuntimeException("队列是空的");
            }
            int num = queue[rear];
            rear--;
            System.out.println(num);
            return num;
        }

        public void printOut() {
            for (int i = 0; i < queue.length; i++) {
                System.out.println(queue[i]);
            }
        }
    }
}

—–更新2022.03.06

2、循环队列

package com.xusj;

/**
 * 环形队列
 * 1、普通队列中：内存空间没有复用性
 * 2、优化成环形队列=》空间可以循环利用
 * 3、主要使用的一个小算法：后移=》rear=（rear+1）%maxSize
 *
 * @author xusj
 * <br>CreateDate 2022/3/20 22:03
 */
public class CircleQueue {
    public static void main(String[] args) {
        // test
        Circle circle = new Circle(4);
        circle.add(1);
        circle.add(2);
        circle.add(3);
//        circle.add(4); 约定指向最后元素的后一个，所以到这里容器已经满了
        circle.selectNum();

    }

}

/**
 * 定义一个环形列表
 * 一、属性：
 * 1、头指针（int front）
 * 2、尾指针（int rear）
 * 3、最大内存大小（int maxSize）
 * 4、使用数组分配空间（int[] arr）
 * <p>
 * 二、方法：
 * 1、判空=》front==rear
 * 2、判满=》（rear+1）%maxSize==front【可以画一个图去感受一下取余数的小魅力】
 * 3、add=》rear指针后移一位 rear=（rear+1）%maxSize【这就是队列成环的妙处】
 * 4、del=》front后移一位front=（front+1）%maxSize
 * 5、取值
 * <p>
 * 对取余操作的理解：
 * 1、首先：下标是从0开始的
 * 2、对总长度取余就是等于当前下标的位置
 * 3、画图自己跑两个帮助理解
 */
class Circle {
    /**
     * 头指针：指向第一个元素
     */
    private int front;
    /**
     * 尾指针：指向最后一个元素的后一个位置，留一个预留位置
     */
    private int rear;
    /**
     * 队列最大长度
     */
    private int maxSize;
    /**
     * 数组=》容器用来存放元素
     */
    private int[] arr;

    /**
     * 构造器：定义一个容器
     *
     * @param maxSize 最大长度
     */
    public Circle(int maxSize) {
        this.maxSize = maxSize;
        this.arr = new int[maxSize];
    }

    /**
     * 判断容器是否已满
     *
     * @return boolean
     */
    public boolean isFull() {
        // 如果后移一个就是头指针所在的位置，则满（取余需要体会一下）
        if (this.front == (this.rear + 1) % this.maxSize) {
            return true;
        }
        return false;
    }

    /**
     * 判断容器是否为空
     *
     * @return boolean
     */
    public boolean isEmpty() {
        if (this.front == this.rear) {
            return true;
        }
        return false;
    }

    /**
     * 向容器中添加元素
     *
     * @param num 元素
     */
    public void add(int num) {
        // 判断容器是否已满
        if (isFull()) {
            System.out.println("容器已满");
        } else {
            // 赋值(约定指向最后元素的后一个位置)
            arr[this.rear] = num;
            // 尾指针后移一位
            this.rear = (this.rear + 1) % this.maxSize;
        }
    }

    /**
     * 出队：遵循队列的先入后出原则
     */
    public void push() {
        // 判断是否空
        if (isEmpty()) {
            System.out.println("队列为空");
        } else {
            System.out.println(this.arr[this.front]);
            // 头指针后移
            this.front = (this.front + 1) % this.maxSize;
        }
    }

    /**
     * 循环，取值
     */
    public void selectNum() {
        for (int i : this.arr) {
            System.out.println(i);
        }
    }
}
/**
 * 总结：
 * 1、队列逻辑成环
 * 2、弄清指针的位置
 * 3、取余操作的在环形队列中的妙处
 */