数据结构

Publish Date: 2022-04-21

Update Date: 2022-04-21

Word Count: 15.7k

Read Times: 70 Min

Read Count:

数据结构

包括线性结构和非线性结构

根据B站视频学习

线性结构

最常用的数据结构，其特点就是数据元素存在一对一的线性关系
线性结构有两存储结构，即顺序存储结构和链式存储结构
- 顺序存储的线性表成为顺序表，顺序表的存储元素是连续的
- 链式存储的线性表称为链表，链表存储元素顺序不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息
线性结构：数组、队列、链表和栈

非线性结构

包括：二维数组，多维数组，广义表，树结构，图结构

稀疏数组

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

稀疏数组的存储方式

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

原本是6 * 7，用稀疏数组表示9 * 3

表示方法

稀疏数组的第一个元素表示原数组的几行，几列和不为0的元素个数

剩下的元素表示不为0的元素的位置

二维数组转稀疏数组的思路

遍历原始的二维数组，得到不为0的有效数据个数sum
根据sum就可以创建稀疏数组sparseArr int [sum+1] [3]
将二维数组的有效数据存入到稀疏数组中

代码实现

public class SparseArray {
    public static void main(String[] args) {
        //创建一个原始的二维数组11*11
        //0:表示没有棋子  1：表示黑子  2：表示白子
        int[][] chessArr = new int[11][11];
        chessArr[1][2] = 1;
        chessArr[2][3] = 2;
        //原始二维数组
        for (int[] row : chessArr) {
            for(int data : row){
                System.out.printf("%d\t",data);
            }
            System.out.println();
        }
        System.out.println("----------------------------------------------");

        int sum = 0;
        for (int i = 0; i < 11; i++) {
            for (int j = 0;j < 11; j++) {
                if(chessArr[i][j]!=0){
                    sum++;
                }
            }
        }

        int[][] sparseArr = new int[sum+1][3];

        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        sparseArr[0][2] = sum;

        int count = 1;
        for (int i = 0;i < 11; i++){
            for (int j = 0;j < 11; j++){
                if(chessArr[i][j]!=0){
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessArr[i][j];
                    count++;
                }
            }
        }
        for (int[] row : sparseArr) {
            for(int data : row){
                System.out.printf("%d\t",data);
            }
            System.out.println();
        }
        System.out.println("------------------------------");

        System.out.println(sum);
        int[][] chessArr1 = new int[sparseArr[0][0]][sparseArr[0][1]];
        for (int i = 0;i < sparseArr[0][0]; i++){
            for (int j = 0;j < sparseArr[0][1]; j++){
                chessArr1[i][j] = 0;
            }
        }
        for(;sum>0;sum--){
            chessArr1[sparseArr[sum][0]][sparseArr[sum][1]] = sparseArr[sum][2];
        }
        for (int[] row : chessArr1) {
            for(int data : row){
                System.out.printf("%d\t",data);
            }
            System.out.println();
        }
    }
}

队列（Queue）

队列是一个有序列表，可以用数组和链表来实现
遵循先入先出的原则

数组模拟队列

使用数组的结构来存储队列的数据，队列的输入和输出分别是从前端和后端来的处理，需要两个变量front和rear来分别标记队列前后端的下标，front的下标会随着数据的输出而改变，rear的下标会随着数据的输入而改变

addQueue
- 而当front==rear，则队列为空
- 将尾指针往后移：rear+1
- 若指针 rear小于队列的最大容量maxSize-1，则将数据存入rear所指数据元素中，否则无法存入数据
- 当rear==maxSize-1时队列满，数据是存储在数组里面的，最大容量为maxSize，则相当于n（数组的长度），所以当rear的下标等于maxSize-1时，队列则满

代码实现

public class ArrayQueue {
    public static void main(String[] args) {
        queue queue = new queue(3);
        char key = ' ';//接收用户输入
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        while(loop){
            System.out.println("s(show):显示数据");
            System.out.println("e(exit):退出程序");
            System.out.println("a(add):添加数据到队列");
            System.out.println("g(get):从队列取出数据");
            System.out.println("h(head):查看头数据");
            key = scanner.next().charAt(0);//接收一个字符
            switch (key){
                case 's':
                    queue.showQueue();
                    break;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
                case 'a':
                    System.out.println("输入一个数");
                    int value = scanner.nextInt();
                    queue.addQueue(value);
                    break;
                case 'g':
                    try {
                        int res = queue.getQueue();
                        System.out.printf("取出数据是%d\n",res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int res = queue.headQueue();
                        System.out.printf("队列头数据是%d\n",res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                default:
                    break;

            }
        }
        System.out.println("程序退出~~~");
    }
}
class queue{
    private int maxSize;//数组的最大容量
    private int front;//队列的头
    private int rear;//队列尾
    private int[] arr;//存放数组

    //创建队列的构造器
    public queue(int arrMaxSize){
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        front = -1;//指向队列头部，指向队列头的前一个位置
        rear = -1;//指向队列尾部，指向队列尾最后一个的数据

    }

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

    //添加数据到队列
    public void addQueue(int n) {
        //先判断是否为空
        if(isFull()){
            return;
        }
        rear++;
        arr[rear] = n;
    }
    //获取队列的数据
    public int getQueue() {
        //判断队列是否为空
        if(isEmpty()){
            //通过抛出异常，进行回弹
            throw new RuntimeException("队列为空，不能取数据！");
        }
        front++;
        return arr[front];
    }

    //显示所有数据
    public void showQueue() {
        if(isEmpty()){
            //通过抛出异常，进行回弹
            System.out.println("队列为空，没有数据");
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("arr[%d]=%d\n",i,arr[i]);
        }

    }
    //显示队列头数据
    public int headQueue() {
        if(isEmpty()){throw new RuntimeException("队列为空，没有数据");}
        front++;
        return arr[front];
    }
}

出现的问题并优化

数组只能使用一次，没有达到复用的效果
将这个数组使用算法，改进成一个环形的队列

数组模拟环形队列

front变量的含义做一个调整：front指向数组的第一个元素，front的初始值为0
rear变量的含义坐一个调整：rear指向数组最后一个元素的后一位置，空出一个空间做约定，rear的初始值为0
当队列满时，**(rear+1)%maxSize = front**
队列为空时，rear==front
队列中有效数据的个数：(rear+maxSize-front)%maxSize

代码实现

public class CircleArrayQueue {
    public static void main(String[] args) {
        CircleArray queue = new CircleArray(3);//但是队列的有效数据个数为2
        char key = ' ';//接收用户输入
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        while(loop){
            System.out.println("s(show):显示数据");
            System.out.println("e(exit):退出程序");
            System.out.println("a(add):添加数据到队列");
            System.out.println("g(get):从队列取出数据");
            System.out.println("h(head):查看头数据");
            key = scanner.next().charAt(0);//接收一个字符
            switch (key){
                case 's':
                    queue.showQueue();
                    break;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
                case 'a':
                    System.out.println("输入一个数");
                    int value = scanner.nextInt();
                    queue.addQueue(value);
                    break;
                case 'g':
                    try {
                        int res = queue.getQueue();
                        System.out.printf("取出数据是%d\n",res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int res = queue.headQueue();
                        System.out.printf("队列头数据是%d\n",res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                default:
                    break;

            }
        }
        System.out.println("程序退出~~~");


    }
}
class CircleArray{
    private int maxSize;//最大容量
    private int front;//队列头
    private int rear;//队列尾
    private int[] arr;//存放数据

    public CircleArray(int CircleMaxSize){
        maxSize = CircleMaxSize;
        front = 0;
        rear = 0;
        arr = new int[maxSize];
    }

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

    //添加数据到队列
    public void addQueue(int n){
        if(isFull()){
            System.out.println("队列已满，不能加入数据");
            return;
        }
        arr[rear] = n;
        //rear后移，必须考虑取模
        rear = (rear+1)%maxSize;

    }

    //取出数据
    public int getQueue(){
        if(isEmpty()){
            throw new RuntimeException("队列为空，不能取数据");
        }
        int value = arr[front];
        front = (front+1)%maxSize;
        return value;
    }

    //显示所有数据
    public void showQueue() {
        if(isEmpty()){
            //通过抛出异常，进行回弹
            System.out.println("队列为空，没有数据");
            return;
        }
        for (int i = front; i < front+getQueueNum(); i++) {
            System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);
        }

    }

    //求出当前队列有多少个数据
    public int getQueueNum(){
        return (rear-front+maxSize)%maxSize;
    }
    //显示队列头数据
    public int headQueue() {
        if(isEmpty()){throw new RuntimeException("队列为空，没有数据");}
        return arr[front];
    }
}

链表（Linked List）

链表是有序的列表，但是存储的方式不一样

链表是以节点的方式来存储的
每一个节点包含data域，next域指向下一个节点的地址
每一个节点不一定是连续存放的

链表分为带头节点的链表和不带头结点的链表，根据实际需求确定

单链表

逻辑结构

实例

public class SingleLinkedListDemo {
    public static void main(String[] args) {

        //创建节点
        HeroNode hero1 = new HeroNode(1,"宋江","及时雨");
        HeroNode hero2 = new HeroNode(2,"吴用","智多星");
        HeroNode hero3 = new HeroNode(3,"林冲","豹子头");
        HeroNode hero4 = new HeroNode(4,"卢俊义","玉麒麟");

        SingleLinkedList singleLinkedList = new SingleLinkedList();
//        singleLinkedList.add(hero1);
//        singleLinkedList.add(hero2);
//        singleLinkedList.add(hero3);
//        singleLinkedList.add(hero4);

        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.list();
        System.out.println("--------修改节点信息--------");
        HeroNode newHeroNode = new HeroNode(2,"无用","zhiduoxin");
        singleLinkedList.update(newHeroNode);
        singleLinkedList.list();
        System.out.println("---------删除节点信息----------------");
        singleLinkedList.delete(1);
        singleLinkedList.list();
    }
}
class SingleLinkedList {
    //先初始化一个节点，头结点不动，不存放具体数据
    private HeroNode head = new HeroNode(0,"","");

    //添加节点到链表中
    public void add(HeroNode heroNode){

        HeroNode temp = head;
        while (true) {
            //找到链表的最后
            if (temp.next==null) {
                break;
            }
            //没有找到，就将temp指向的位置后移一位
            temp = temp.next;
        }
        //当temp退出while后，temp指向最后一个节点
        temp.next = heroNode;
    }

    //显示链表
    public void list() {
        //判断链表是否为空
        if(head.next==null){
            System.out.println("链表为空");
            return;
        }
        //头结点不能动，需要一个辅助节点来遍历
        HeroNode temp = head.next;
        while (true) {
            if(temp==null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }

    }
    public void addByOrder(HeroNode heroNode){
        //头结点不能动
        HeroNode temp = head;
        boolean flag = false;//标记是否重复
        while (true){
            if(temp.next==null){//temp为最后一个位置
                break;
            }
            if(heroNode.no < temp.next.no){//找到位置
                break;
            }else if(heroNode.no == temp.next.no){//重复
                flag = true;
            }
            temp = temp.next;//后移，继续查找
        }
        //判断是否重复
        if(flag) {

            System.out.printf("待插入的英雄编号%d已经存在，不能加入\n",heroNode.no);
        }else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }
    public void update(HeroNode newHeroNode){
        //判断链表是否为空
        if(head.next==null){
            System.out.println("链表为空");
            return;
        }
        //定义一个变量，来遍历链表
        HeroNode temp = head;
        boolean flag = false;//表示是否可以找到节点
        while(true){
            if(temp == null){//链表的最后
                break;
            }
            if(temp.no == newHeroNode.no){
                flag = true;
                break;
            }
            temp = temp.next;//没有找到继续遍历
        }
        if(flag){
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        }else {
            System.out.printf("没有找到编号为%d的节点\n",newHeroNode.no);
        }
    }

    public void delete(int no){
        //定义一个变量，来遍历链表
        HeroNode temp = head;
        boolean flag = false;//表示是否可以找到节点
        while(true){
            if(temp.next == null){//链表的最后
                break;
            }
            if(temp.next.no == no){
                flag = true;
                break;
            }
            temp = temp.next;//没有找到继续遍历
        }
        if(flag){

            temp.next = temp.next.next;
        }else {
            System.out.printf("没有找到编号为%d的节点\n",no);
        }
    }
}

class HeroNode {
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;

    public HeroNode(int no, String name, String nickname){
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }
    //为了更好的显示，重写toString方法
    @Override
    public String toString(){
        return "HeroNode [no="+no+",name="+name+",nickname="+nickname+"]";
    }

}思路分析

思路分析

添加（创建）
- 创建一个head头结点，用来表示单链表的头
- 每天添加一个节点，直接添加到链表最后
遍历
- 通过一个辅助变量遍历整个链表
按照编号的顺序添加
- 首先找到新添加节点的位置，通过辅助变量temp遍历查找
- temp定位到添加位置的前一个位置
- 新节点的next域指向temp的下一个节点
- 然后改变temp下一个节点为新节点
通过编号修改节点信息
- 首先定义一个变量遍历数组
- 修改节点信息
删除节点
- 首先定义一个变量temp遍历数组
- 找到删除节点的前一个节点
- 前一个节点的next域直接指向删除节点的下一个节点

双向链表

单向链表的缺点分析

单向链表查找的方向只能是一个方向，而双向链表的方向可以向前也可以向后
单向链表不能自我删除，需要靠辅助节点，而双向链表，可以自我删除

思路分析

1、遍历

和单链表的方法一样，但是双向链表可以是向前遍历，也可以是向后遍历

2、添加到双向链表的最后

先找到双向链表的最后一个节点
temp.next = newHeroNode
newHeroNode.pre = temp

3、修改

和单链表的方法一样

4、删除

双向链表有pre和next，可以实现自我删除

用辅助变量temp找到要删除的节点
temp.pre.next = temp.next
如果temp不是最后一个节点：temp.next.pre = temp.pre

单向环形链表

Josephu问题

设编号为1,2，…..n的n个人围坐在一圈，，约定编号为k（1<=k<n）的人从1开始报数，数到m的那个人出列，他的下一位又从1开始报数，数到m的那个人又出列，以此类推，知道所有人出列为止，由此产生一个出队编号的序列

思路分析

构建一个单向环形链表
- 先创建第一个节点，让first指向第一个节点，并形成环形
- 当每创建一个新的节点，就把该节点加入到已有的环形链表中
遍历环形链表
- 先让一个辅助变量curBoy指向first节点
- 然后通过while循环遍历环形链表到curBoy.next == first结束

public class Josephu {
    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addBoy(5);
        circleSingleLinkedList.showBoy();
        System.out.println("--------------------");
        circleSingleLinkedList.countBoy(1,2,5);
    }
}
//创建一个单向环形链表
class CircleSingleLinkedList {
    //先创建一个first节点
    private Boy first = new Boy(-1);
    //添加小孩
    public void addBoy(int nums){
        if(nums<1){
            System.out.println("不能创建小于一个人的链表");
            return;
        }


        Boy curBoy = null;
        //
        for (int i = 1;i<=nums;i++){
            Boy boy = new Boy(i);
            if(i==1){
                first = boy;
                first.setNext(boy);//如果只有一个孩子，first的next指向自己
                curBoy = first;
            }else {
                curBoy.setNext(boy);
                boy.setNext(first);
                curBoy = boy;
            }
        }
    }

    //遍历当前的链表
    public void showBoy(){
        //判断链表是否为空
        if (first==null){
            System.out.println("链表为空，不能打印！");
            return;
        }
        //使用辅助指针
        Boy curBoy = first;
        while (true){
            System.out.printf("小孩的编号为%d\n",curBoy.getNo());
            if(curBoy.getNext()==first){//说明遍历到链表的最后
                break;
            }
            curBoy = curBoy.getNext();//curBoy后移一位，继续遍历
        }
    }

    /**
     * 根据用户输入的数据，计算小孩的出圈的顺序
     * @param startNo 表示从第几个孩子开始数数
     * @param countNum 表示数几下
     * @param nums  表示最初有几个孩子
     */
    public void countBoy(int startNo, int countNum ,int nums){
        //先对输入的数据进行校验
        if(startNo < 1 || startNo > nums || first == null){
            System.out.println("输入参数有误！");
            return;
        }
        //定义辅助指针
        Boy helper = first;
        while (true){
            if (helper.getNext() == first){//helper指向最后一个节点,first指向第一个节点
                break;
            }
            helper = helper.getNext();
        }
        //第几个孩子开始报数startNo,先让first和helper移动startNo-1
        for (int i = 0; i < startNo-1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        while (true){
            if (helper == first){//说明只剩一个孩子
                break;
            }
            //数几下，first和helper移动countNum-1次
            for (int i = 0; i < countNum-1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            //first就是要出圈的孩子，helper在要出圈孩子的前一个节点
            System.out.printf("小孩%d出圈\n",first.getNo());
            //first指向的孩子出圈，链表重新连接
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.printf("最后留在圈中的小孩编号为%d\n",helper.getNo());
    }
}
//boy类，一个节点
class Boy {
    private int no;
    private Boy next;
    public Boy(int no){
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "Boy{" +
                "no=" + no +
                ", next=" + next +
                '}';
    }
}

栈

栈是一个先入后出的有序列表，并且限制线性表中元素的插入和删除只能在线性表的同一端进行的一种数线性表。允许插入和删除的一端为变化的一端叫做栈顶，另一端为固定的一端为栈底

实现栈的思路分析

使用数组来模拟栈
定义一个top表示栈顶，初始化为-1
入栈的操作，当有数据加到栈时，top++；stack[top] = data
出栈的操作，int value = stack[top];top–; return value;

代码实现

public class ArrayStackDemo {
    public static void main(String[] args) {
        ArrayStack stack = new ArrayStack(4);
        String key = "";
        boolean loop = true;//判断是否退出程序;
        Scanner scanner = new Scanner(System.in);
        while (loop){
            System.out.println("show：显示栈的数据");
            System.out.println("push：添加数据到栈");
            System.out.println("pop：删除栈的数据");
            System.out.println("exit：退出程序");
            key = scanner.next();
            switch (key){
                case "show":stack.list();break;
                case "push":
                    System.out.println("请输入添加的数：");
                    int value = scanner.nextInt();
                    stack.push(value);
                    break;
                case "pop":
                    try {
                        int res = stack.pop();
                        System.out.printf("出栈的数据是%d\n",res);
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                case "exit":
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
    }
}
class ArrayStack {
    private int maxSize;//表示栈的大小
    private int [] stack;
    private int top = -1;//表示栈顶，初始化为-1
    public ArrayStack(int maxSize){
        this.maxSize = maxSize;
        stack = new int[maxSize];
    }

    //栈是否满
    public boolean isFull(){
        return top == maxSize-1;
    }
    //栈是否为空
    public boolean isEmpty(){
        return top == -1;
    }

    //入栈
    public void push(int value){
        //先判断栈是否满
        if (isFull()){
            System.out.println("数据已存满！");
            return;
        }
        top++;
        stack[top] = value;
    }

    //出栈
    public int pop(){
        if (isEmpty()){
            throw new RuntimeException("栈空，没有数据了！");
        }
        int value = stack[top];
        top--;
        return value;
    }

    //显示栈的情况
    public void list(){
        if (isEmpty()){
            System.out.println("栈空，没有数据了~~");
            return;
        }
        for (int i = top; i >=0 ; i--) {
            System.out.printf("stack[%d]==%d\n",i,stack[i]);
        }
    }
}

实现计算器

思路分析

用index遍历表达式
如果是一个数字直接入数栈
如果是符号，分情况
- 如果这时的符号栈为空，直接入栈
- 如果这时的符号栈已经有符号，就进行比较，如果当前的操作符的优先级小于等于栈内的操作符，就从数栈中出两个数，进行计算，得到结果入数栈，然后将当前的操作符入符号栈
- 如果当前的操作符优先级大于栈内的操作符，直接入符号栈
当表达式扫描完毕后，就顺序的从数栈和符号栈中pop出相应的书和符号，并运行
最后在数栈只留一个数字

前缀表达式（波兰表达式）

前缀表达式又称波兰表达式，前缀表达式的运算符位于操作符之前

举例说明

（3+4）* 5-6对应的前缀表达式 -、*、+3 4 5 6

从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对他们做出响应的计算，并将结果压入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果

从右至左扫描，将6、5、4、3压入堆栈
遇到+运算符，弹出3和4，计算出3+4的结果，再将7入栈
*运算符，弹出7和5，计算7 * 5结果，35入栈
-运算符，计算35-6的值，即最终结果

中缀表达式

中缀表达式就是常见的运算表达式

对于我们人是最熟悉的，但是对计算机确实不好操作，因此，在计算结果时，往往会将中缀表达式转成其他表达式来操作

中缀表达式转后缀表达式

具体步骤：

1、初始化两个栈：运算符栈stack1和存储中间结果的栈stack2

2、从左往右扫描中缀表达式

3、遇到操作数时，将数压入栈stack2

4、遇到运算符时，与stack1栈顶比较运算符的优先级

如果stack1为空，或者栈顶运算符为左括号 (，则直接将此运算符压入栈
否则，若优先级比栈顶运算符高，也将运算符压入s1
否则，将s1栈顶的运算符弹出并踏入s2中，再次转到上4步骤与s1中新的栈顶运算

5、遇到括号时

如果是左括号直接入栈
如果是右括号，则依次弹出s1栈顶的运算符，并压入s2中，直到遇到左括号为止，可以将s1中这一对括号去掉

6、重复步骤2-5，直到表达式的最右边

7、将s1中剩余的运算符依次弹出并压入s2

8、依次弹出s2中的元素并输出

代码演示

/**
     * 将中缀表达式对应的list转换成后缀表达式所对应的list
     * [1, +, (, (, 2, +, 3, ), *, 4, ), -, 5] --> [1,2,3,+,4,*,+,5,-]
     * @param list
     * @return
     */
    public static List<String> parseSuffixExpressionList(List<String> list){

        //定义两个栈
        Stack<String> stack1 = new Stack<String>();//符号栈
        //在操作Stack2时没有pop这个操作，并且最后输出结果还需逆序输出，所以使用list
        List<String> stack2 = new ArrayList<String>();//存放中间结果的栈，最后输出结果的栈

        //遍历list
        for(String item: list){
            //如果是一个数的话，直接入栈
            if (item.matches("\\d+")){
                stack2.add(item);
            } else if(item.equals("(")){
                stack1.push(item);
            } else if(item.equals(")")){
                while (!stack1.peek().equals("(")){
                    stack2.add(stack1.pop());
                }
                stack1.pop();//消除左括号
            } else {
                while (stack1.size()!=0 && Operation.getValue(item)<=Operation.getValue(stack1.peek())){
                    stack2.add(stack1.pop());
                }
                stack1.push(item);
            }
        }
        while (stack1.size()!=0){
            stack2.add(stack1.pop());
        }

        return stack2;
    }

    /**
     * 将中缀表达式存入list中
     * @return
     */
    public static List<String> toInfixExpressionList(String s){
        //定义一个list存放中缀表达式
        List<String> list = new ArrayList<String>();

        int i = 0;//用于遍历中缀表达式
        String str;//对多位数的拼接
        char c;//每遍历一个字符就放到c中
        do{
            if((c=s.charAt(i)) < 48 || (c=s.charAt(i)) > 57){//c是非数字的话，加入到c中
                list.add("" + c);
                i++;
            }else {
                str = "";//先将str制成 '0'[48]->'9'[57]
                while (i<s.length() && (c=s.charAt(i))>=48 && (c=s.charAt(i))<=57){
                    str += c;
                    i++;
                }
                list.add(str);
            }

        }while (i<s.length());
        return list;
    }
/**
* operation编写运算符的优先级
*
*/
class Operation{
    private static int ADD = 1;//+
    private static int SUB = 1;//-
    private static int MUL = 2;//*
    private static int DIV = 2;///

    public static int getValue(String operation){
        int result = 0;
        switch (operation){
            case "+":
                result = ADD;
                break;
            case "-":
                result = SUB;
                break;
            case "*":
                result = MUL;
                break;
            case "/":
                result = DIV;
                break;
            default:
                System.out.println("没有该运算符！");
                break;
        }
        return result;
    }
}

简单图解

后缀表达式（逆波兰表达式）

后缀表达式又称逆波兰表达式

举例说明：（3+4）*5-6对应的后缀表达式就是3 4 + 5 * 6 -

public class PolandNotion {
    public static void main(String[] args) {
        //先定义一个逆波兰表达式
//        String suffixExpression = "3 4 - 5 * 6 -";//(3+4)*5-6
        String suffixExpression = "5 - 4 +";//(3+4)*5-6

        List<String> rpmList = getListString(suffixExpression);
        System.out.println(rpmList);
        int result = calculation(rpmList);
        System.out.printf("计算结果=%d",result);
    }

    /**
     * 将suffixExpression用空格分隔存入Arraylist中
     * @param suffixExpression
     * @return
     */
    public static List<String> getListString(String suffixExpression){
        String[] split = suffixExpression.split(" ");
        List list = new ArrayList<String>();
        for(String ele : split){
            list.add(ele);
        }
        return list;
    }

    public static int calculation(List<String> rpmList){
        Stack<String> stack = new Stack<>();
        for(String item: rpmList){
            if(item.matches("\\d+")){//匹配的是多位数
                stack.push(item);
            }else {//不是数字直接取出两个数字进行运算
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                int result = 0;//计算结果
                if(item.equals("+")){
                    result = num1 + num2;
                }else if (item.equals("-")){
                    result = num2 - num1;
                }else if (item.equals("*")){
                    result = num1 * num2;
                }else if (item.equals("/")){
                    result = num2 / num1;
                }else {
                    throw new RuntimeException("运算符有误！");
                }
                //将结果入栈
                stack.push("" + result);
            }
        }
        //栈中留下的最后一个数就是表达式的结果
        return Integer.parseInt(stack.pop());
    }
}

时间复杂度

常见的时间复杂度

常数阶O(1)
```
int i = 0;
int j = 1;
int m = i + j;
```
无论代码执行了多少行，只要代码中没有循环等结构的，他的时间复杂度都是O(1)
对数阶O(log2n)
```
while(i<n){
    i = i * 2;
}
```
在while的循环中，每次i*2，直到i大于等于n时退出循环，所以设定x次退出循环，2^x = n,所以循环log2n次才能退出循环
线性阶O(n)
```
for(int i = 0; i < n;i++){
    
}
```

线性对数阶O(nlog2n)

for(int i = 0; i < n;i++){
    while(i<n){
    i = i * 2;
}
}

平方阶O(n^2)

for(int i = 0; i < n ; i++){
    for(int j =0; j < m; j++){
        
    }
}

立方阶O(n^3)
k次方阶O(n^k)
指数阶(2^n)

说明：

常见的算法复杂度由小到大排列：O(1)、O(log2n)、O(n)、O(nlog2n)、O(n^2)、O(n^3)、O(n^k)、(2^n)

递归

概念

递归就是方法自己调用自己，但是每次调用时传入不同的变量

调用规则

当程序执行到一个方法时，就会开辟一个独立的空间（栈）
每个空间的数据（局部变量）是独立的
递归必须向退出递归的田间逼近，否则就是无限递归
当一个方法执行完毕时，或者遇到return，返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕

迷宫回溯问题

代码实现

package com.bai.recursion;

public class MiGong {
    public static void main(String[] args) {
        //定义一个二维数组表示地图
        int [][] map = new int[8][7];
        //设置边框，为1
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        for (int j = 0; j < 8; j++) {
            map[j][0] = 1;
            map[j][6] = 1;
        }

        //设置挡板
        map[2][1] = 1;
        map[2][3] = 1;
        map[3][3] = 1;
        map[3][4] = 1;
        for (int i = 4; i < 7; i++) {
            for (int j = 2; j < 5; j++) {
                map[i][j] = 1;
            }
        }


        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.printf(" " + map[i][j]);
            }
            System.out.println();
        }
        setWay(map,1,1);
        System.out.println("--------------------");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.printf(" " + map[i][j]);
            }
            System.out.println();
        }
    }

    /**
     *  约定：当map[i][j]=0,表示没有走过，map[i][j]=1表示墙，map[i][j]=2表示已经走过，map[i][j]=3表示已经走过但是走不通
     *  策略：下-》右-》上-》左
     * @param map 表示地图
     * @param i 起始点的位置
     * @param j
     * @return 如果找到通路，就返回true，否则返回false
     */
    public static boolean setWay(int[][] map, int i, int j){
        if(map[6][5] == 2){//说明找到通路
            return true;
        }else {
            if(map[i][j] == 0){//表示没有走过
                map[i][j] = 2;
                //开始探索
                if(setWay(map,i+1,j)){//向下
                    return true;
                }else if(setWay(map,i,j+1)){//向右
                    return true;
                }else if(setWay(map,i-1,j)){//向上
                    return true;
                }else if (setWay(map,i,j-1)){//向上
                    return true;
                }else {//说明该点走不通
                    map[i][j] = 3;
                    return false;
                }
            }else {//可能是1(墙),2(走过的),3(死路)
                //不需要走
                return false;
            }
        }
    }
}

八皇后问题

在8*8的国际象棋上摆放八个皇后，使其不能互相攻击，任意两个皇后都不能处于同一行、同一列或者同一斜线上，问有几种解法

思路分析

1、一个皇后先放在第一行第一列

2、第二个皇后放在第二行第一列，然后判断是否可以放，如果不能放，继续放在第二列、第三列，依次把所有列都放完，找到一个合适的

3、继续第三个皇后，还是第一列、第二列。。。直到第八个皇后也能放在一个合适的地方

4、当得到一个合适的解时，在栈回退到上一个栈，就开始回溯，即将第一个皇后，放在第一列的所有解，全部得到

5、然后回头继续第一个皇后放在第二列，然后继续循环1，2,3,4的步骤

代码实现

public class Queue8 {
    int max = 8;
    int[] array = new int[max];
    static int count = 0;
    public static void main(String[] args) {
        Queue8 queue8 = new Queue8();
        queue8.check(0);
        System.out.printf("一共有%d解法",count);
    }

    /**
     * 放置第n个皇后
     * @param n
     */
    private void check(int n){
        if(n==max){//八个皇后已经放好了
            print();
            return;
        }
        //依次放入皇后，并判断是否冲突
        for (int i = 0; i < max; i++) {
            //先把这个皇后放在第一列
            array[n] = i;
            //判断这个皇后是否与之前的皇后冲突
            if(judge(n)){//不冲突
                //放下一行的皇后，即下一个皇后
                check(n+1);
            }
            //如果冲突把这个皇后放在本行的位置的下一列，即位置后移
            //array[n] = i+1,即下一循环的array[n] = i;
        }
    }
    /**
     * 查看第n个皇后，与之前的皇后是否冲突
     * @param n
     * @return
     */
    private boolean judge(int n){
        for (int i = 0; i < n; i++) {
            if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n]-array[i])){
                return false;
            }
        }
        return true;
    }
    //打印所有皇后的位置
    private void print(){
        count++;
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }
}

排序算法

1、内部排序：指将需要处理的的所有数据都需要加载到内部存储中进行排序

2、外部排序：数据量过大，无法将全部加载到内存中，需要借助外部存储进行排序

排序速度测试

int[] arr = new int[8000000];
for(int i = 0; i < 8000000; i++){
    arr[i] = (int) (Math.random() * 8000000);
}
System.out.println("排序前");
Date date1 = new Date();
SimpleDateFormat simpleDateFormat1 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str = simpleDateFormat1.fromat(date1);
System.out.println("排序前的时间是="+date1Str);

//方法

Date date2 = new Date();
SimpleDateFormat simpleDateFormat2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date2Str = simpleDateFormat1.fromat(date2);
System.out.println("排序前的时间是="+date2Str);

冒泡排序

介绍

通过从前往后遍历序列，依次比较相邻元素的值，将值较大的逐渐移动到最后

一共进行数组大小-1循环
每一趟排序的次数都在减少
优化，在某一次排序中没有发生一次交换，就可以提前结束循环

图解

代码实现

/**
 * 冒泡排序
 */
public class BobbleSort {
    public static void main(String[] args) {
        int arr[] = {3,9,-1,10,20};

        int temp = 0;//用于交换数据的辅助变量
        for(int i = 0; i < arr.length-1; i++){

            for(int j = 0; j < arr.length-1-i;j++){//每一趟排序最大都会排在最后一位
                //arr.length-1原因arr[j+1]已经指向最后一位元素，如果是arr.length则出界
                if(arr[j]>arr[j+1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

}

发现当进行到第三趟时，数据已经不进行交换，其实排序已经完成，所以为了优化程序，减少程序执行时间，可以定义一个boolean变量用来标记当一趟数据不发生交换时，直接跳出循环，输出排序后的结果，代码优化如下：

public class BobbleSort {
    public static void main(String[] args) {
//        int arr[] = {4,1,3,2};

        int [] arr = new int[80000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random()*800000);
        }
        Date data1 = new Date();
        SimpleDateFormat simpleDateFormat1 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String format1 = simpleDateFormat1.format(data1);
        System.out.println("排序前的时间："+format1);

        boolean flag = false;//标记是否发生交换
        int temp = 0;//用于交换数据的辅助变量
        for(int i = 0; i < arr.length-1; i++){

            for(int j = 0; j < arr.length-1-i;j++){//每一趟排序最大都会排在最后一位
                //arr.length-1原因arr[j+1]已经指向最后一位元素，如果是arr.length则出界
                if(arr[j]>arr[j+1]){
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
            if(!flag){//一趟排序没有发生数据交换，已经排序完成，不用继续排序
                break;
            }else {
                flag = false;//重置
            }
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
        Date data2 = new Date();
        SimpleDateFormat simpleDateFormat2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String format2 = simpleDateFormat2.format(data2);
        System.out.println("排序后的时间："+format2);
    }

}

选择排序

基本介绍

第一次从数组中选择出一个最小的数，然后与数组第一个位置交换数据；第二次从数组的第二个位置选出一个最小的数，与数组第二个位置交换数据，直到排序完成

代码实现

public class SelectSort {
    public static void main(String[] args) {
        int[] arr = {4,2,6,3,7,5};
        selectSort(arr);

    }
    public static void selectSort(int[] arr){

        for(int i= 0;i<arr.length-1;i++){
            int minIndex = i;//用来交换数据的辅助变量
            int min = arr[i];//每一趟遍历的最小值
            for (int j = i+1; j < arr.length; j++) {
                if(min>arr[j]){
                    min = arr[j];
                    minIndex = j;
                }
            }
            if(minIndex!=i){//当arr[minIndex]刚好是剩下的数中最小的，不需要做交换
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

插入排序

基本介绍

把n个待排序的元素看成一个有序表和一个无序表，开始有序表只有一个元素，无序表中有n-1个元素，排序过程中每次从无序表中取出第一个元素，把他的排序码一次与有序表元素的排序码进行比较，将他插入有序表中适当位置，使之成为新的有序表

图解

代码实现

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {56,23,11,45,87};
        insertSort(arr);
    }
    public static void insertSort(int[] arr){

        for (int i = 1; i < arr.length; i++) {
            int insertValue = arr[i];
            int insertIndex = i-1;

            while (insertIndex>=0 && insertValue<arr[insertIndex]){
                arr[insertIndex+1] = arr[insertIndex];//往后移位置，直到找到要插入的位置之后都要移位置
                insertIndex--;//在已经排好顺序的前边，寻找
            }

            //退出while循环时，已经找到insertValue要插入的位置，insertIndex+1

            //判断是否赋值，要插入的位置刚好是排序完部分的最后一个元素的位置后一个，说明不用赋值
            if(insertIndex+1!=i){

                arr[insertIndex+1] = insertValue;
            }
        }


        System.out.println(Arrays.toString(arr));
    }
}

希尔排序

基本介绍

希尔排序是希尔在1959年提出的一种排序算法，也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序

图解

交换法

public class ShellSort {
    public static void main(String[] args) {

        int[] arr = {8,3,5,9,4,6,7,2};
        int n = arr.length;
        shellSort(arr);
    }
    public static void shellSort(int[] arr){

        int temp = 0;
        for(int gap = arr.length/2; gap > 0; gap /=2){
            for (int i = gap; i < arr.length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
        }

        System.out.println(Arrays.toString(arr));
    }
}

效率不高，发现一个就去交换，速度不是很快

移位法

 public static void shellSort(int[] arr){

        int temp = 0;
        for(int gap = arr.length/2; gap > 0; gap /=2){
            for (int i = gap; i < arr.length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
        }

        System.out.println(Arrays.toString(arr));
    }

快速排序

基本介绍

快速排序是对冒泡排序的一种改进，基本思想是通过一趟排序将要排序的数据分隔成独立的两部分，其中一部分的所有数据都比另外一部分数据都要小，然后再按此方法对这两部分进行快速排序，整个过程可以递归进行，一次达到整个数据变成有序序列

图解

代码实现

public class QuickSort {
    public static void main(String[] args) {
        int [] arr = {2,1,0,-6,5,7};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));

    }
    public static void quickSort(int[] arr, int left, int right){
        int l = left;
        int r = right;
        int temp = 0;//辅助变量用于交换数据
        int pivot = arr[(left+right)/2];
        while(l<r){

            while(arr[l]<pivot){
                l += 1;
            }
            //找到比pivot大的数据下标

            while (arr[r]>pivot){
                r -= 1;
            }
            //找到比pivot小的数据下标

            if(l>=r){
                break;
            }
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            //发现交换完的数据和pivot相等，右指针左移
            if(arr[l]==pivot){
                r -= 1;
            }

            if(arr[r]==pivot){
                l += 1;
            }
        }
        //如果l==r，必须l++，r--,否则会溢出
        if(l==r){
            l += 1;
            r -= 1;
        }
        //向左递归
        if(left<r){
            quickSort(arr,left,r);
        }
        //向右递归
        if(right>l){
            quickSort(arr,l,right);
        }
    }
}

归并排序

基本介绍

归并排序是利用归并的思想实现的排序方法，该算法采用的分治策略，将问题分成一些小问题然后递归求解，而治的夹断就将分的阶段得到的个答案合并在一起

图解

代码实现

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {8,4,5,7,1,3,6,2};
        int temp[] = new int[arr.length];
        mergeSort(arr,0,arr.length-1,temp);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 分和合方法
     * @param arr
     * @param left
     * @param right
     * @param temp
     */
    public static void mergeSort(int[] arr, int left, int right, int[] temp){
        if (left<right){
            int mid = (left+right)/2;
            //向左递归排序
            mergeSort(arr,left,mid,temp);
            //向右递归排序
            mergeSort(arr,mid+1,right,temp);
            //合并
            mergeSort(arr,left,mid,right,temp);

        }
    }
    /**
     * 合并方法
     * @param arr   排序的数据
     * @param left  左边有序列的初始序列
     * @param mid   中间索引
     * @param right 右边索引
     * @param temp  做中转的数组
     */
    public static void mergeSort(int[] arr, int left, int mid, int right, int[] temp){
        int i = left;
        int j = mid + 1;//
        int t = 0;//指向temp数组的当前索引

        while (i<=mid && j<=right){
            if(arr[i] <= arr[j]){
                temp[t] = arr[i];
                t += 1;
                i += 1;
            }else {
                temp[t] = arr[j];
                t += 1;
                j += 1;
            }
        }
        //将一边序列的剩余数据全部填充到数组中
        while (i<=mid){//左边序列剩余数据
            temp[t] = arr[i];
            t += 1;
            i += 1;
        }
        while (j<=right){//右边序列会剩余数据
            temp[t] = arr[j];
            t += 1;
            j += 1;
        }

        //将所有数据拷贝到arr中，但是并不是每一次都要全部拷贝
        t = 0;
        int tempLeft = left;
        System.out.printf("tempLeft=%d right=%d\n",tempLeft,right);
        while(tempLeft<=right){//第一次合并tempLeft=0 right=1 第二次合并tempLeft=1 right=2 第三次合并tempLeft=0 right=3...
            // 直到最后一次才是tempLeft=0 right=7
            arr[tempLeft] = temp[t];
            t += 1;
            tempLeft +=1;
        }
    }
}

基数排序

基本介绍

基数排序属于“分配式排序”，又称“桶子法”，它是通过键值的各个位的值，将要排序的元素分配在某些桶中，达到排序的作用

思路分析

将每个元素的个位数取出，然后看这个数在哪个对应的桶中

代码实现

package com.bai.sort;

import java.util.Arrays;

public class RadixSort {
    public static void main(String[] args) {
        int arr[] = {53,3,542,748,14,214};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void radixSort(int[] arr){
        //定义一个二维数组，表示十个桶，每一个桶就是一个数组
        //为了防止溢出，将每一个数组的大小都设为arr.length
        //所以基数排序是以空间换时间的经典算法
        int[][] bucket = new int[10][arr.length];

        //记录每个桶中存入数据的个数,bucketElementsCounts[0]表示bucket[0]的数据个数
        int[] bucketElementsCounts = new int[10];

        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if(arr[i]>max){
                max = arr[i];
            }
        }
        int maxLength = (max+"").length();

        for (int s = 0, n = 1;s<maxLength;s++, n *= 10){
            for (int i = 0; i < arr.length; i++) {
                int digitOfElement = arr[i]/n%10;
                bucket[digitOfElement][bucketElementsCounts[digitOfElement]] = arr[i];
                bucketElementsCounts[digitOfElement]++;
            }
            int index = 0;
            //遍历每一个桶
            for (int j = 0; j < bucket.length; j++){
                if(bucketElementsCounts[j] != 0){
                    for (int k = 0;k<bucketElementsCounts[j];k++){
                        arr[index++] = bucket[j][k];
                    }
                }
                //每趟排序完都得至0，下一个存入
                bucketElementsCounts[j] = 0;
            }
            System.out.println(Arrays.toString(arr));
        }

    }
}

查找算法

顺序(线性)查找

基本介绍

可以是有序的，也可以是无序的

代码实现

/**
 * 线性查找
 */
public class LinearSearch {
    public static void main(String[] args) {
        int[] arr = {45,78,223,451,112,56};
        int index = linearSearch(arr,78);
        if(index>=0){
            System.out.printf("arr[%d]=target",index);
        }else {
            System.out.println("没有此数据！");
        }
    }
    public static int  linearSearch(int[] arr,int target){
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] == target){
                return i;
            }
        }
        return -1;
    }
}

二分查找

对数组进行二分查找时，这个数组必须是顺序的，所以如果数组是无序的，需先进行排序

思路分析

1、首先确定数组中间的下标

2、然后让需要查找的数与中间的值进行比较

如果target>arr[mid]，说明要查找的数在mid的右边，因此向右递归
如果target<arr[mid]，说明要查找的数在mid的左边，因此向左递归
如果target=arr[mid]，说明找到，退出

代码实现

package com.bai.search;

import java.util.ArrayList;
import java.util.List;

/**
 * 二分查找
 * 必须有序
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {23,23,45,78,89,5645};
        ArrayList<Integer> integers = binarySearch(arr, 0, arr.length - 1, 11);
        System.out.println(integers);
//        if(search>=0){
//            System.out.printf("找到，下标为%d",search);
//        }else {
//            System.out.println("没有这个数");
//        }
    }

    /**
     * 查找目标值
     * @param arr
     * @param left
     * @param right
     * @param target 目标值
     * @return 如果找到返回数组的下标值，没有找到就返回-1
     */
    public static ArrayList<Integer> binarySearch(int[] arr, int left, int right, int target){
        if(left>right){
            return new ArrayList<Integer>();
        }
        ArrayList<Integer> list = null;
        int mid = (left+right)/2;
        if(target>arr[mid]){//向右递归
            return binarySearch(arr,mid+1,right,target);
        }else if(target<arr[mid]){//向左递归
            return binarySearch(arr,left,mid-1,target);
        }else if (target==arr[mid]){
            list = new ArrayList<Integer>();
            int temp = mid-1;
            while (true){//向左扫描
                if(temp<0 || arr[temp] != target){//出界或者左边没有target目标值
                    break;
                }
                list.add(temp);
                temp -= 1;//temp左移，继续查找
            }
            list.add(mid);
            temp = mid+1;
            while (true){//向右递归
                if(temp >= arr.length || arr[temp] !=target){
                    break;
                }
                list.add(temp);
                temp += 1;
            }

        }
        return list;

    }
}

插值查找

基本介绍

插值查找算法类似于二分查找，但是插值查找每次从自适应mid处开始查

mid索引的公式发生了改变，mid = left +(findValue-arr[left])*(right-left)/(arr[right]-arr[left])

代码实现

package com.bai.search;

import java.util.logging.Level;

/**
 * 插值查找
 */
public class InsertValueSearch {
    public static void main(String[] args) {
        int[] arr = {0,12,45,56,78,89,100};
        int index = insertValueSearch(arr, 0,arr.length-1,56);
        System.out.printf("arr[%d]=findValue",index);
    }

    /**
     *
     * @param arr
     * @param left
     * @param right
     * @param findValue
     * @return
     */
    public static int insertValueSearch(int[] arr, int left, int right, int findValue) {
        if (findValue > arr[arr.length - 1] || findValue < arr[left] || left > right) {
            return -1;
        }

        int mid = left+(right-left)*(findValue-arr[left])/(arr[right]-arr[left]);
        int midVal = arr[mid];
        if(findValue>midVal){
            return insertValueSearch(arr,mid+1,right,findValue);
        }else if(findValue<midVal){
            return insertValueSearch(arr,left,mid-1,findValue);
        }else {
            return mid;
        }
    }
}

注意事项

对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找，速度较快

关键字分布不均匀的情况下，该方法不一定比二分查找要好

斐波那契查找

基本介绍

斐波那契数列{1,1,2,3,5,8,13,21,34,55},通过改变中间节点位置，不是中间或者数插值得到的，而是mid=low+f(k-1)-1

代码实现

public class FibonacciSearch {
    public static int maxSize = 20;
    public static void main(String[] args) {
        int[] arr = {1,3,5,8,13,19};
        int flag = fibonacciSearch(arr, 13);
        System.out.printf("arr[%d]="+arr[flag],flag);
    }

    /**
     * 获取一个斐波那契数列
     * @return
     */
    public static int[] fibonacci(){
        int[] fibonacci = new int[20];
        fibonacci[0] = 1;
        fibonacci[1] = 1;
        for (int i = 2; i < maxSize; i++){
            fibonacci[i] = fibonacci[i-1]+fibonacci[i-2];
        }
        return fibonacci;
    }

    /**
     *
     * @param a 数组
     * @param key   需要查询的数
     * @return 没有找到返回-1
     */
    public static int fibonacciSearch(int[] a,int key){
        int low = 0;
        int high = a.length-1;
        int k = 0;//斐波那契数列的下标
        int mid = 0;
        int f[] = fibonacci();//存放斐波那契数列的值
        //获取到斐波那契数列分隔数值的下标
        while (high > f[k]-1){
            k++;
        }
        //因为f[k]的数值可能大于a的长度，需要arrays类，构造一个新的数组，并指向a[]
        //不足的部分用0补充
        int[] temp = Arrays.copyOf(a,f[k]);
        //实际上使用a数组最后的数填充temp
        //{1,3,5,8,13,19,0,0} ==>{1,3,5,8,13,19,19,19}
        for (int i = high+1;i< temp.length;i++){
            temp[i] = a[high];
        }

        while (low<=high){
            mid = low + f[k-1]-1;
            if(key<temp[mid]){//继续向数组的前面查找
                high = mid-1;
                k--;
                //f[k] = f[k-1]+f[k-2]
                //f[k-1]是f[k]前面的部分,f[k-2]是f[k]后面的部分,f[k]是黄金分割点
            }else if (key>temp[mid]){
                low = mid+1;
                k -= 2;
                //f[k] = f[k-1]+f[k-2]
                //后面是f[k-2],继续拆分成f[k-2] = f[k-3]+f[k-4]
                //相当于在黄金分割点f[k-2]的前面进行查找key
            } else {
                if(mid<=high){
                    return mid;
                }else {
                    return high;
                }
            }
        }
        return -1;
    }
}

哈希表

散列表也叫哈希表，是根据关键码值而直接进行访问数据结构

哈希表相当于是一个数组，数组的每一个元素指向一条链表

基本结构

代码实现

package com.bai.hashMap;

import java.util.Scanner;

/**
 * 当一个公司有新员工来报到时，要求将该员工的信息加入（id，性别，名字，住址），当输入该员工的id时，查到该员工的所有信息
 */
public class hashMapDemo {
    public static void main(String[] args) {
        HashTab hashTab = new HashTab(7);
        String key = "";//输出指令
        Scanner scanner = new Scanner(System.in);
        while (true){
            System.out.println("add:添加员工");
            System.out.println("find:查找员工");
            System.out.println("list:显示全部员工");
            System.out.println("exit:退出");
            key = scanner.next();
            switch (key){
                case "add":
                    System.out.println("输入员工id");
                    int id = scanner.nextInt();
                    System.out.println("输入员工姓名");
                    String name = scanner.next();
                    Emp emp = new Emp(id, name);
                    hashTab.add(emp);
                    break;
                case "find":
                    System.out.println("输入要查找的员工id");
                    id = scanner.nextInt();
                    hashTab.findEmpById(id);
                    break;
                case "list":
                    hashTab.list();
                    break;
                case "exit":
                    scanner.close();
                    System.exit(0);
                    break;
                default:
                    break;
            }

        }

    }
}
//创建hashTab管理多条链表
class HashTab{
    private EmpLinkedList[] empLinkedListArray;

    private int size;//表示有多少条链表


    public HashTab(int size){
        this.size = size;
        //初始化empLinkedListArray这个链表
        empLinkedListArray = new EmpLinkedList[size];
        //empLinkedListArray为null，所以不能将员工的信息emp放在一个空的EmpLinkedList上去
        for (int i = 0; i < size; i++) {
            //里面的每一个数组链表都需要创建
            empLinkedListArray[i] = new EmpLinkedList();
        }
    }

    public void list(){
        for (int i = 0; i < size; i++) {
            empLinkedListArray[i].list(i);
        }
    }

    public void add(Emp emp){
        //根据id，取模后应该添加到哪条链表
        int empLinkedListNum = HashFun(emp.id);
        empLinkedListArray[empLinkedListNum].add(emp);
    }
    //取模
    public int HashFun(int id){
        return id%size;
    }

    public void findEmpById(int id){
        int empLinkedListNum = HashFun(id);
        Emp emp = empLinkedListArray[empLinkedListNum].findEmpById(id);
        if(emp!=null){
            System.out.printf("在第%d条链表中找到id=%d,name=%s\t",empLinkedListNum,emp.id,emp.name);
        }else {
            System.out.println("在哈希表中没有找到该员工");
        }
    }
}


/**
 * 表示一个员工
 */
class Emp{
    public int id;
    public String name;
    public Emp next;

    public Emp(int id, String name) {
        super();
        this.id = id;
        this.name = name;
    }
}
class EmpLinkedList{
    private Emp head;//头指针执行第一个emp，因此链表head直接指向第一个emp

    //添加员工到链表
    public void add(Emp emp){
        if(head == null){
            head = emp;
            return;
        }
        //如果不是第一个员工，使用一个辅助指针，帮助定位
        Emp curEmp = head;
        while (true){
            if(curEmp.next==null){//说明到链表最后
                break;
            }
            curEmp = curEmp.next;//后移
        }
        //退出时直接将emp加入栈
        curEmp.next = emp;
    }

    //遍历链表的员工信息
    public void list(int no){
        if(head == null){//说明链表为空
            System.out.println("第"+no+"条链表为空！");
            return;
        }
        System.out.print("第"+no+"条链表信息为");
        Emp curEmp = head;
        while (true){
            System.out.printf("id=%d,name=%s\n",curEmp.id,curEmp.name);
            if(curEmp.next == null){
                break;
            }
            curEmp = curEmp.next;
        }
    }
    public Emp findEmpById(int id){
        //判断链表是否为空
        if(head == null){
            System.out.println("链表为空");
            return null;
        }

        //辅助指针
        Emp curEmp = head;

        while (true){
            if (curEmp.id == id){//说明找到该员工
                //curEmp就是该员工，退出即可
                break;
            }
            if(curEmp.next == null){//到达链表的最后没有查到
                curEmp = null;
                break;//没有找到直接退出
            }
            curEmp = curEmp.next;
        }
        return curEmp;
    }
}

树结构

树的引入

数组存储数据的方式，通过下标直接访问数据，但是对于插入数值，或者检索具体某个值数组会整体移动，效率低；链式存储，只需要插入节点，链接到链表中，但是效率很低，比如检索时须比较很多次数据

二叉树

如果二叉树的所有叶子节点都在最后一层，并且节点总数=2^n-1,n为层数，则称为满二叉树

如果该二叉树的所有叶子节点都在最后一层或者在倒数第二层，而且最后一层的叶子节点在左边延续，倒数第二层的叶子结点在右边连续，称为完全二叉树

前序遍历

先输出父节点，再遍历左子树和右子树

中序遍历

先遍历左子树，再输出父节点，再遍历右子树

后序遍历

先遍历左子树，再遍历右子树最后输出父节点

遍历查找

前序遍历查找

1、先判断当前节点是否是要查找的节点

2、如果相等，则返回该节点

3、不相等，则判断当前节点的左子节点是否为空，如果不为空，则向左遍历

4、如果向左遍历查找没有找到，则判断当前节点的右子节点是否为空，如果不为空，则向右遍历

中序遍历查找

1、先判断当前节点的左子节点是否为空，如果不为空，则先向左遍历

2、如果向左遍历查找没有找到，则先判断当前节点是否是要查找的节点

3、如果相等，则返回该节点

4、不相等，则先判断当前节点的右子节点是否为空，如果不为空，，则向右遍历

后序遍历查找

1、先判断当前节点的左子节点是否为空，如果不为空，则先向左遍历

2、如果向左遍历查找没有找到，则判断当前节点的右子节点是否为空，如果不为空，则向右遍历

3、如果没有找到再判断当前节点是否是要查找的节点

4、如果相等，则返回该节点

package com.bai.tree;

/**
 * 二叉树
 */
public class BinaryTreeDemo {
    public static void main(String[] args) {
        //创建一颗二叉树
        BinaryTree binaryTree = new BinaryTree();
        //创建节点
        HeroNode root = new HeroNode(1,"宋江");//第一个节点
        HeroNode hero2 = new HeroNode(2,"无用");
        HeroNode hero3 = new HeroNode(3,"卢俊义");
        HeroNode hero4 = new HeroNode(4,"林冲");

        root.setLeft(hero2);
        root.setRight(hero3);
        hero3.setRight(hero4);

        binaryTree.setRoot(root);

        //测试
        binaryTree.preOrder();//1,2,3,4
        System.out.println("---------------------");
        binaryTree.infixOrder();//2,1,3,4
        System.out.println("---------------------");
        binaryTree.postOrder();//2,4,3,1
        //后序遍历首先遍历左子树，然后遍历右子树，首先遍历到3节点，但是3节点的右节点不为空，所以首先遍历4
        //遍历是以递归遍历的所以首先输出的是4节点，然后3节点的postOrder()执行

        System.out.println("---------------------");

        HeroNode heroNode1 = binaryTree.preOrderSearch(2);
        if(heroNode1 != null){
            System.out.printf("找到了，姓名为%s\n",heroNode1.getName());
        }else {
            System.out.println("没有找到");
        }
        System.out.println("------------------------");
        HeroNode heroNode2 = binaryTree.infixOrderSearch(1);
        if(heroNode2 != null){
            System.out.printf("找到了，姓名为%s\n",heroNode2.getName());
        }else {
            System.out.println("没有找到");
        }
        System.out.println("------------------------");
        HeroNode heroNode3 = binaryTree.postOrderSearch(3);
        if(heroNode3 != null){
            System.out.printf("找到了，姓名为%s\n",heroNode3.getName());
        }else {
            System.out.println("没有找到");
        }
    }
}
//二叉树
class BinaryTree{
    private HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    //前序遍历
    public void preOrder(){
        if(this.root != null){
            this.root.preOrder();
        }else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    //中序遍历
    public void infixOrder(){
        if (this.root != null){
            this.root.infixOrder();
        }else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    //后序遍历
    public void postOrder(){
        if (this.root !=null){
            this.root.postOrder();
        }else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    public HeroNode preOrderSearch(int no){
        if(root != null){
            return root.preOrderSearch(no);
        }else {
            return null;
        }
    }

    public HeroNode infixOrderSearch(int no){
        if(root != null){
            return root.infixOrderSearch(no);
        }else {
            return null;
        }
    }

    public HeroNode postOrderSearch(int no){
        if(root != null){
            return root.postOrderSearch(no);
        }else {
            return null;
        }
    }
}

//创建节点
class HeroNode{
    private int no;
    private String name;
    private HeroNode left;
    private HeroNode right;

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }


    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    /**
     * 前序遍历
     */
    public void preOrder(){
        System.out.println(this);
        //左子树遍历
        if(this.left != null){
            this.left.preOrder();
        }
        //右子树遍历
        if(this.right != null){
            this.right.preOrder();
        }
    }

    /**
     * 中序遍历
     */
    public void infixOrder(){
        if(this.left != null){
            this.left.infixOrder();
        }
        System.out.println(this);
        if(this.right !=null){
            this.right.infixOrder();
        }
    }

    /**
     * 后序遍历
     */
    public void postOrder(){
        if (this.left != null){
            this.left.postOrder();
        }
        if(this.right !=null){
            this.right.postOrder();
        }
        System.out.println(this);
    }

    /**
     * 前序遍历查找员工
     * @param no 查找id
     * @return 如果查找到了就返回hero,没有就返回null
     */
    public HeroNode preOrderSearch(int no){
        //判断当前节点是否相同
        if(this.no == no){
            return this;
        }

        //先向左遍历，首先判断是否左子树是否为空
        HeroNode resNode = null;
        if(this.left != null){//继续向左遍历
            resNode = this.left.preOrderSearch(no);
        }
        if(resNode != null){//说明已经找到
            return resNode;
        }

        if(this.right != null){
            resNode = this.right.preOrderSearch(no);
        }
        return resNode;
    }

    /**
     * 中序遍历查找
     * @param no
     * @return
     */
    public HeroNode infixOrderSearch(int no){
        HeroNode resNode = null;
        if(this.left != null){
            resNode = this.left.infixOrderSearch(no);
        }
        if(resNode != null){
            return resNode;
        }

        if(this.no == no){
            return this;
        }

        if(this.right != null){
            resNode = this.right.infixOrderSearch(no);
        }
        return resNode;
    }

    /**
     * 后序遍历查找
     * @param no
     * @return
     */
    public HeroNode postOrderSearch(int no){
        HeroNode resNode = null;
        if(this.left != null){
            resNode = this.left.postOrderSearch(no);
        }
        if(resNode != null){
            return resNode;
        }

        if(this.right != null){
            resNode = this.right.postOrderSearch(no);
        }
        if(resNode != null){
            return resNode;
        }

        if(this.no == no){
            return this;
        }
        return resNode;
    }
}

删除节点

删除规则

1、如果删除的节点是叶子结点，则删除该节点

2、如果删除的节点是非叶子节点，则删除该子树

分析思路

二叉树是单向的，所以是判断当前节点的子节点是否需要删除，而不是去判断当前这个节点是不是需要删除节点

如果当前节点的左子节点不为空，并且左节点

代码实现

/**
* HeroNode节点方法
*/
public void deleteNode(int no){


        if(this.left != null && this.left.no == no){
            this.left = null;
            return;
        }
        if(this.right != null && this.right.no == no){
            this.right = null;
            return;
        }

        if(this.left != null){
            this.left.deleteNode(no);
        }
        if(this.right != null){
            this.right.deleteNode(no);
        }
    }

/**
*     二叉树内方法
*/
    public void deleteNode(int no){
        if(root != null){
            if(root.getNo() == no){
                root = null;
            }else {
                root.deleteNode(no);
            }
        }else {
            System.out.println("空树不能删除");
        }
    }

先判断当前节点是否为空，然后再判断当前的root是否要查找的节点，如果不是则进入deleteNode函数中，判断节点的左子节点和右子节点

顺序存储二叉树

特点

顺序二叉树通常只考虑完全二叉树

第n个元素的左子节点为2*n+1

第n个元素的右子节点为2*n+2

第n个元素的父节点为(n-1)/2

代码实现

public class arrBinaryTreeDemo {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7};
        ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
        arrBinaryTree.preOrder();
    }
}

class ArrBinaryTree{
    private int[] arr;//存储数据节点的数组

    public ArrBinaryTree(int[] arr){
        this.arr = arr;
    }

    //为了方便简洁
    //重载
    public void preOrder(){
        this.preOrder(0);
    }
    /**
     * 完成顺序存储二叉树的前序遍历
     * @param index
     */
    public void preOrder(int index){
        if(arr.length == 0 || arr == null){
            System.out.println("数组为空，不能按照二叉树的前序遍历");
        }
        //前序遍历，先输出这个元素
        System.out.println(arr[index]);
        if((2*index+1)<arr.length){
            preOrder(2*index+1);
        }
        if((2*index+2)<arr.length){
            preOrder(2*index+2);
        }
    }
}

线索化二叉树

基本介绍

n个节点的二叉链表中含有n+1 公式2n-(n-1) = n+1个空指针域。利用二叉链表中的空指针域，存放指向节点在某种遍历次序下的前驱和后继节点的指针（线索），这种被加上线索的二叉链表被称为线索链表

图解

代码实现

package com.bai.tree;

public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        Node root = new Node(1, "tom");
        Node node2 = new Node(3, "jack");
        Node node3 = new Node(6, "john");
        Node node4 = new Node(8, "jon");
        Node node5 = new Node(10, "thu");
        Node node6 = new Node(14, "saas");
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);
        threadedBinaryTree.setRoot(root);
        threadedBinaryTree.threadedNodes();

        Node leftNode = node5.getLeft();
        Node rightNode = node5.getRight();
        System.out.println("10节点前驱结点为"+leftNode+"后继节点为"+rightNode);
        System.out.println("-------------------------");
        threadedBinaryTree.ThreadedBinaryList();
    }
}
class ThreadedBinaryTree {
    private Node root;
    //当前节点的前驱结点的指针
    private Node preNode = null;

    public void setRoot(Node root) {
        this.root = root;
    }

    public void threadedNodes(){
        this.threadedNodes(root);
    }
    /**
     * 对二叉树进行线索化的方法
     * @param node
     */
    public void threadedNodes(Node node) {
        //如果node为空，不能线索化
        if(node == null){
            return;
        }

        //先遍历线索化左子树
        threadedNodes(node.getLeft());
        //线索化当前节点

        if(node.getLeft() == null){//当前节点为8节点，设置前驱结点为空
            //当前节点指向前驱结点
            node.setLeft(preNode);
            //修改当前节点的指针类型，指向前驱结点
            node.setLeftType(1);
        }

        //处理后续节点,下一次循环执行，node节点是3，前驱结点是8节点
        if(preNode != null && preNode.getRight() == null){
            preNode.setRight(node);
            preNode.setRightType(1);
        }
        //每次线索化一个节点都要将前驱结点指向当前节点
        preNode = node;

        //后遍历线索化右子树
        threadedNodes(node.getRight());
    }

    public void ThreadedBinaryList(){

        //辅助变量，存储当前遍历的节点
        Node node = root;
        while (node != null){

            //先找到leftType为1的节点，就是8节点
            while (node.getLeftType() == 0){//8寻找节点
                node = node.getLeft();
            }
            //leftType = 1时退出循环，这时node就是8节点
            System.out.println(node);

            while(node.getRightType() == 1){//当前node节点的右子节点就是他的后继节点
                node = node.getRight();
                System.out.println(node);
            }

            //替换这个节点
            node = node.getRight();

        }
    }
    //前序遍历
    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    //中序遍历
    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    //后序遍历
    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    public Node preOrderSearch(int no) {
        if (root != null) {
            return root.preOrderSearch(no);
        } else {
            return null;
        }
    }

    public Node infixOrderSearch(int no) {
        if (root != null) {
            return root.infixOrderSearch(no);
        } else {
            return null;
        }
    }

    public Node postOrderSearch(int no) {
        if (root != null) {
            return root.postOrderSearch(no);
        } else {
            return null;
        }
    }

    public void deleteNode(int no) {
        if (root != null) {
            if (root.getNo() == no) {
                root = null;
            } else {
                root.deleteNode(no);
            }
        } else {
            System.out.println("空树不能删除");
        }
    }
}
class Node {
    private int no;
    private String name;
    private Node left;
    private Node right;

    /**
     * 1.如果；leftType = 0表示指向的是左子树，如果是1的话指向前驱结点
     * 2.如果：rightType = 0表示指向的是右子树，如果是1的话指向后继节点
     */
    private int leftType;
    private int rightType;

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    public Node(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }


    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    /**
     * 前序遍历
     */
    public void preOrder() {
        System.out.println(this);
        //左子树遍历
        if (this.left != null) {
            this.left.preOrder();
        }
        //右子树遍历
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    /**
     * 中序遍历
     */
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    /**
     * 后序遍历
     */
    public void postOrder() {
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }

    /**
     * 前序遍历查找员工
     *
     * @param no 查找id
     * @return 如果查找到了就返回hero, 没有就返回null
     */
    public Node preOrderSearch(int no) {
        //判断当前节点是否相同
        if (this.no == no) {
            return this;
        }

        //先向左遍历，首先判断是否左子树是否为空
        Node resNode = null;
        if (this.left != null) {//继续向左遍历
            resNode = this.left.preOrderSearch(no);
        }
        if (resNode != null) {//说明已经找到
            return resNode;
        }

        if (this.right != null) {
            resNode = this.right.preOrderSearch(no);
        }
        return resNode;
    }

    /**
     * 中序遍历查找
     *
     * @param no
     * @return
     */
    public Node infixOrderSearch(int no) {
        Node resNode = null;
        if (this.left != null) {
            resNode = this.left.infixOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }

        if (this.no == no) {
            return this;
        }

        if (this.right != null) {
            resNode = this.right.infixOrderSearch(no);
        }
        return resNode;
    }

    /**
     * 后序遍历查找
     *
     * @param no
     * @return
     */
    public Node postOrderSearch(int no) {
        Node resNode = null;
        if (this.left != null) {
            resNode = this.left.postOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }

        if (this.right != null) {
            resNode = this.right.postOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }

        if (this.no == no) {
            return this;
        }
        return resNode;
    }

    /**
     * 删除节点
     *
     * @param no
     */
    public void deleteNode(int no) {


        if (this.left != null && this.left.no == no) {
            this.left = null;
            return;
        }
        if (this.right != null && this.right.no == no) {
            this.right = null;
            return;
        }

        if (this.left != null) {
            this.left.deleteNode(no);
        }
        if (this.right != null) {
            this.right.deleteNode(no);
        }
    }
}

堆排序

基本介绍

1、堆排序是以堆这种数据结构（以树结构为基础）的一种排序算法，是一种选择排序，也是一种不稳定排序（[参考文章][https://blog.csdn.net/weixin_39996908/article/details/111108431]对于某一种排序算法，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序保持不变，那么就说这个排序算法是稳定的。对于某种需求，虽然元素相等，但是他的先后顺序不能排序完后改变，不稳定排序后得到的结果可能是不正确的）

2、堆是具有以下性质的完全二叉树：每个结点的值都大于或者等于其左右孩子结点的值称为大顶堆，没有要求结点的左孩子的值和右孩子的值的大小关系（特点：arr[i]>=arr[2 * i+1]&&arr[i]>=arr[2 * i+2]）

3、相反，每个结点的值都小于或者等于其左右孩子的值，称为小顶堆（特点：arr[i]<=arr[2 * i+1]&&arr[i]<=arr[2 * i+2]）

4、一般对数组进行升序采用大顶堆，降序采用小顶堆

堆排序的基本思路

1、将无序序列构成一个堆，根据升序降序需求选择大顶堆或小顶堆

2、将堆顶元素与末尾元素交换，将最大元素沉到数组末尾

3、重新调整结构，满足堆定义，再继续交换堆顶元素和当前末尾元素（除去上一步得到的最大元素），反复执行交换操作，直到整个序列有序

以数组（{4,6,8,5,9}）演示：

1、将一个数组（二叉树），调整为一个大顶堆

从第一个非叶子结点开始调整，arr.length/2-1=1，叶子结点不用调整，从左至右，从上至下进行调整
找到第二个非叶子结点4，[4,9,8]中9最大，4和9交换
- 交换完后子根[4,5,6]结构混乱，继续调整

代码演示

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {4,6,8,5,9};
        heapSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            System.out.print(" ");
        }
    }

    public static void heapSort(int[] arr) {
        for (int i = arr.length/2-1; i >= 0; i--) {
            adjustHeap(arr,i,arr.length);
        }

        int temp = 0;
        for (int j = arr.length-1; j >= 0 ; j--) {
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr,0,j);//每次大小-1，在此范围内最大值在arr[0]和最尾端进行交换
        }
    }

    /**
     * 将一个二叉树，调整成一个大顶堆
     * @param arr
     * @param i
     * @param length
     */
    public static void adjustHeap(int[] arr,int i, int length){
        int temp = arr[i];//取出当前元素的值，存入临时变量中

        for (int k = i*2+1; k < length; k=k*2+1) {
            if (k+1<length && arr[k]<arr[k+1]){//预防超界，左子结点的值小于右子结点的值
                k++;//k指向右子结点
            }
            if (arr[k]>temp){//如果子结点大于父结点，交换
                arr[i] = arr[k];
                i = k;//i指向了大于父结点的子结点位置
            }else {
                break;//从下往上的
            }
        }
        //当for循环结束后，以i为父结点的树的最大值，放在最顶端
        arr[i] = temp;//交换，i指向的就是子结点

    }
}

赫夫曼树

基本介绍

1、给定n个权值作为n个叶子结点，构造一棵二叉树，若该数的带权路径长度（wpl）达到最小，称这样的二叉树为最优二叉树，也成为哈夫曼树（HuffmanTree）

2、赫夫曼树是带权路径长度最短的树，权值最大的结点离根较近

概念

路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或者孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1
结点的权及带权路径长度：如将书中结点赋给一个带有某种意义的值，则这个数值称为该结点的权。而结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积
树的带权路径长度：树的带权路径长度规定为所有叶结点的带权路径长度之和，称为WPL，权值越大的结点离根结点越近的二叉树才是最优二叉树
WPL最小的就是赫夫曼树

baiwenhui

http://example.com/2022/04/21/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AC%94%E8%AE%B0/

All articles in this blog are used except for special statements CC BY 4.0 reprint policy. If reproduced, please indicate source baiwenhui !

数据结构

计算机网络

2022-05-03 计算机网络

计算机网络

java集合解析

2022-04-03 java基础

java

数据结构笔记

数据结构

线性结构

非线性结构

稀疏数组

队列（Queue）

数组模拟队列

数组模拟环形队列

链表（Linked List）

单链表

双向链表

单向环形链表

栈

实现计算器

前缀表达式（波兰表达式）

中缀表达式

后缀表达式（逆波兰表达式）

时间复杂度

递归

迷宫回溯问题

八皇后问题

排序算法

冒泡排序

选择排序

插入排序

希尔排序

快速排序

归并排序

基数排序

查找算法

顺序(线性)查找

二分查找

插值查找

斐波那契查找

哈希表

树结构

二叉树

前序遍历

中序遍历

后序遍历

遍历查找

删除节点

顺序存储二叉树

线索化二叉树

堆排序

赫夫曼树