数据结构和算法基础


线性结构和非线性结构

线性结构

  • 线性结构作为最常用的数据结构,其特点是数据元素之间存在一对一的线性关系。
  • 线性结构有两种不同的存储结构,即顺序存储结构以及链式存储结构。顺序存储结构的线性表被称之为顺序表,顺序表中存储的元素是连续的。链式存储结构的线性表被称之为链表,链表中存储的元素不一定是连续的,元素节点中存放数据元素以及相邻元素的地址信息。
  • 线性结构常见的有:数组、队列、链表和栈。

非线性结构

  • 非线性结构包括:二维数组,多维数组,广义表,树结构,图结构。

稀疏数组

首先思考一个实际的程序问题,现在有一个五子棋游戏,游戏需要一个存盘退出和续上盘的功能。这个功能就要求我们需要将棋局的信息存储下来,记录下哪一方在哪个位置下了棋。
如下图所示,为完成功能,可以采用二维数组来表示棋盘数据:

默认棋盘的每一个点都是用0来代表,黑色方下的棋用数字1代表,蓝色方用数字2。
如此,我们就可以通过二维数组来完成功能。但是这样也会有一个问题,就是我们将太多的默认的0记录了下来,产生了大量的冗余数据,这个问题就可以使用稀疏数组来解决。

稀疏数组和二维数组对比


由上图可以看出,原二维数组一共有六行七列42个数据,转换为稀疏数组之后为三行九列27个数据,避免了存储大量的冗余的默认数据。
稀疏数组第一行用来存储表示原二维数组一共是几行几列的二维数组以及数组中有多少个有用的数据,剩下的行分别用来横纵坐标和数据的值,达到表示各个值在原二维数组中位置的功能。

二维数组和稀疏数组转换实现

package com.xsh.demo.datastructure;

/**
 * 稀疏数组
 * @author xiashihua
 */
public class SparseArray {
    /**
     * 编码实现使用二维数组模拟棋盘数据,并使用稀疏数组优化数据结构,然后实现稀疏数组和二维数组之间的转换
     * @param args
     */
    public static void main(String[] args) {
        //创建一个二维数组,表示棋盘,默认无棋子的数据是0,黑子是1,蓝子是2
        int chessArray[][] =new int [11][11];
        //放置一个黑子和一个蓝子
        chessArray[1][2]=1;
        chessArray[2][3]=2;
        chessArray[5][5]=2;
        //遍历二维数组
        System.out.println("原二维数组为:");
        for (int[] ints : chessArray) {
            for (int anInt : ints) {
                System.out.print(anInt+"   ");
            }
            System.out.println();
        }

        //根据原二维数组创建稀疏数组
        int sum=0;
        for (int[] ints : chessArray) {
            for (int anInt : ints) {
                if(anInt != 0){
                    sum++;
                }
            }
        }
        int sparseArray[][]=new int[sum+1][3];
        sparseArray[0][0]=chessArray.length;
        sparseArray[0][1]=chessArray.length;
        sparseArray[0][2]=sum;
        //获取原二维数组中的非零元素,存储到稀疏数组中
        int count=0;
        for (int i = 0; i < chessArray.length; i++) {
            for (int j = 0; j < chessArray.length; j++) {
                if(chessArray[i][j] != 0){
                    count++;
                    sparseArray[count][0]=i;
                    sparseArray[count][1]=j;
                    sparseArray[count][2]=chessArray[i][j];
                }
            }
        }
        System.out.println("根据原二维数组创建的稀疏数组为:");
        for (int[] ints : sparseArray) {
            for (int anInt : ints) {
                System.out.print(anInt+"   ");
            }
            System.out.println();
        }
        //根据得到的稀疏数组还原二维数组
        int chhessArray2[][] =new int[sparseArray[0][0]][sparseArray[0][1]];
        //数据填充
        for (int i = 1; i <= sum; i++) {
            chhessArray2[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }
        System.out.println("还原之后的二维数组为:");
        for (int[] ints : chhessArray2) {
            for (int anInt : ints) {
                System.out.print(anInt+"   ");
            }
            System.out.println();
        }
    }
}

如上代码就实现了二维数组和稀疏数组之间的转换,完成了有大量冗余数据时进行数据压缩的功能。

队列

队列是一个有序列表,可以使用数组或者链表来实现。
队列必须遵循先入先出的原则。即:先存入队列的数据要先取出,后存入队列的数据后去除。

使用数组模拟队列

使用数组模拟队列的示意图:

队列本身是有序列表,若使用数组的结构来储存队列的数据,则队列的声明如上图所示,其中maxSize表示为队列的最大容量。
因为队列的输入和输出分别是从前后端来处理,因此需要两个变量指针frontrear分别指向队列的最前端和最后端,front会随队列数据的输出而改变,rear会随队列数据的输入而改变。

使用数组实现基本的队列功能

package com.xsh.demo.datastructure;

/**
 * 使用数组模拟队列
 * @author xiashihua
 */
public class ArrayQueue {
    /**
     * 数组的最大长度,即队列的最大容量
     */
    private int maxSize;
    /**
     * 指向队列头部的指针
     */
    private int front;
    /**
     * 指向队列尾部的指针
     */
    private int rear;
    /**
     * 模拟队列的数组本身
     */
    private int[] arr;

    public ArrayQueue(int maxSize){
        //初始化队列基本信息
        this.maxSize=maxSize;
        front = -1;
        rear = -1;
        arr = new int[this.maxSize];
    }

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

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

    /**
     * 添加数据到队列中
     * @param number
     */
    public void addQueue(int number){
        if(isFull()){
            System.out.println("队列已满,无法存储数据!");
            return;
        }
        rear++;
        arr[rear]=number;
    }

    /**
     * 从队列中取出数据
     * @return
     */
    public int getQueue(){
        if(isEmpty()){
            throw new RuntimeException("队列为空,无法取出数据!");
        }
        front++;
        return arr[front];
    }

    /**
     * 展示队列中的所有数据
     */
    public void showQueue(){
        if(isEmpty()){
            System.out.println("队列中数据为空,无法展示!");
            return;
        }
        for (int i = front+1      ; i < arr.length; i++) {
            System.out.println("arr["+i+"]:"+arr[i]);
        }
    }

    /**
     * 展示队列的头数据
     * @return
     */
    public int peekQueue(){
        if(isEmpty()){
            throw new RuntimeException("队列中数据为空,无法显示头数据!");
        }
        return arr[front++];
    }
}

测试队列的基本功能

 @Test
    public void queueTest() {
        //初始化队列
        ArrayQueue queue = new ArrayQueue(3);
        //接受用户输入
        char key = ' ';
        Scanner scanner = new Scanner(System.in);
        boolean flag = true;
        while (flag) {
            System.out.println("s(show):显示队列所有数据");
            System.out.println("a(add):添加数据到队列中");
            System.out.println("g(get):从队列中取出数据");
            System.out.println("p(peek):查看队列中的头部数据");
            System.out.println("e(exit):推出程序");
            key = scanner.next().charAt(0);
            switch (key) {
                case 's':
                    queue.showQueue();
                    break;
                case 'a':
                    System.out.println("请输入一个数:");
                    int value = scanner.nextInt();
                    queue.addQueue(value);
                    break;
                case 'g':
                    try {
                        int number = queue.getQueue();
                        System.out.println("取出的数据为:"+number);
                    }catch (RuntimeException e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'p':
                    try {
                        int number = queue.peekQueue();
                        System.out.println("队列头部的数据:"+number);
                    }catch (RuntimeException e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    scanner.close();
                    flag = false;
                    break;
                default:break;
            }
        }
    }

经过测试代码的功能测试发现,现有的数组实现队列已经拥有基本的功能和队列特征,但是无法实现重复使用的功能。
当队列的数据经过一次存取之后就无法再使用了,接下来会使用环形队列改造代码解决这个问题。

在代码学习中,发现junit和idea的问题,当使用junit的测试注解进行单元测试的时候,当测试方法中设计到scanner输入的时候控制台是无法输入数据的。
解决办法如下:

数组实现环形队列

由以上的代码可以看到,当队列中的数据被取出的时候并不是真正的被取出了,而是因为逻辑上我们是通过指针来获取数据的,当指针被修改之后,即使原来存放数据的位置数据还在,按照我们设置的取出数据的规则也无法获取到数据了,因为指针已经不再会指向原来的位置。
所以当数据存满又被取完之后,前后的指针frontrear就重合了,此时既符合队列为空,也符合队列已满的规则,则数组无法第二次进行数据存储使用。
所以,环形队列的实现思路就是通过控制指针,使指针在满足一个规律的情况下循环产生变化,rear指针和front指针不会因为达到数组的长度就卡死,而会自动的按照规律回到数组的开头进行新一轮的循环,由此可以看成一个环形的队列。

环形队列实现思路:

  • 更改front指针的含义:由指向数组第一个元素的前一个元素改为指向数组的第一个元素,初始值为0.
  • 更改rear指针的含义:由指向数组的最后一个元素改为指向数组的最后一个元素的后一个位置,因为希望会预留出一个空间来进行判断是否需要进行重置循环,初始值为0.
  • 判断队列满的条件为:(rear+1)%maxSize=front
  • 获取队列中元素个数的条件为:(rear+maxSize-front)%maxSize

环形队列实现代码如下:

package com.xsh.demo.datastructure;

/**
 * 数组实现环形队列
 *
 * @author xiashihua
 */
public class CircleArrayQueue {
    /**
     * 数组的最大长度,即队列的最大容量
     */
    private int maxSize;
    /**
     * 指向队列头部的指针
     */
    private int front;
    /**
     * 指向队列尾部的指针
     */
    private int rear;
    /**
     * 模拟队列的数组本身
     */
    private int[] arr;

    public CircleArrayQueue(int maxSize) {
        this.maxSize = maxSize+1;
        arr = new int[this.maxSize];
    }

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

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

    /**
     * 添加数据到队列中
     *
     * @param number
     */
    public void addQueue(int number) {
        if (isFull()) {
            System.out.println("队列已满,无法存储数据!");
            return;
        }
        arr[rear] = number;
        rear = (rear + 1) % maxSize;
    }

    /**
     * 从队列中取出数据
     *
     * @return
     */
    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 + size(); i++) {
            System.out.println("arr[" + i % maxSize + "]:" + arr[i % maxSize]);
        }
    }

    /**
     * 返回数组中有效数据的个数
     *
     * @return
     */
    public int size() {
        return (rear + maxSize - front) % maxSize;
    }

    /**
     * 展示队列的头数据
     *
     * @return
     */
    public int peekQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列中数据为空,无法显示头数据!");
        }
        return arr[front];
    }
}

以上代码就完成了一个环形队列,队列的可以进行重复的数据存储且保证队列先进先出的数据特性。

链表(Linked list)

  • 链表是一个有序列表,以节点的方式来进行存储。
  • 每个节点除了存储节点数据的data域还有一个next域,next存放的是指向下一个节点的地址内容。
  • 链表的各个节点不一定连续存储,是通过next域信息进行关联。
  • 链表有可能有头节点,有可能没有,视实际需求而定。

编码实现单链表

链表节点对象代码

package com.xsh.demo.pojo;

/**
 * 链表节点对象
 * @author xiashihua
 */
public class HeroNode {
    private int no;
    private String name;
    private String nickName;
    private HeroNode next;

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

    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 String getNickName() {
        return nickName;
    }

    public void setNickName(String nickName) {
        this.nickName = nickName;
    }

    public HeroNode getNext() {
        return next;
    }

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

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

单链表实现代码:实现基本的添加(不考虑添加顺序)和遍历

package com.xsh.demo.datastructure;

import com.xsh.demo.pojo.HeroNode;

/**
 * 单向链表实现
 * @author xiashihua
 */
public class SingleLinkedList {

    /**
     * 初始化头节点
     * 头节点不存储具体数据,只用来进行定位指针
     */
    private HeroNode head=new HeroNode(0,"","");

    public void add(HeroNode heroNode){
        //定义指针
        HeroNode temp=head;
        while (true){
            if(temp.getNext() == null){
                break;
            }
            temp = temp.getNext();
        }
        //while循环结束表示此时temp指针已经代表链表的最后一个节点
        temp.setNext(heroNode);
    }

    public void show(){
        //判断链表数据是否为空
        if(head.getNext() == null){
            System.out.println("链表数据为空!");
            return;
        }
        //定义指针
        HeroNode temp = head.getNext();
        while (true){
            if(temp == null){
                break;
            }
            System.out.println(temp);
            temp = temp.getNext();
        }
    }
}

如上代码,我们就通过一个简单的HeroNode节点对象完成了一个单链表。
但是现在链表的功能是很简单的,而且添加数据也不能按照数据的顺序进行添加,接下来一步步完善链表的功能性。

添加方法实现按照节点编号顺序添加数据

    /**
     * 按照节点id的顺序插入
     *
     * @param heroNode
     */
    public void addByOrder(HeroNode heroNode) {
        //创建指针
        HeroNode temp = head;
        //创建标识,标识为false的时候表示
        boolean flag = false;
        while (true) {
            if (temp.getNext() == null) {
                break;
            } else if (temp.getNext().getNo() > heroNode.getNo()) {
                break;
            } else if (temp.getNext().getNo() == heroNode.getNo()) {
                //表示该id的节点已存在,不允许重复插入
                flag = true;
                break;
            }
            temp = temp.getNext();
        }
        if (flag) {
            System.out.println("id为" + heroNode.getNo() + "的节点已存在,不允许重复插入");
        } else {
            heroNode.setNext(temp.getNext());
            temp.setNext(heroNode);
        }
    }

补充单链表的节点数据修改和删除功能

    /**
     * 修改
     */
    public void update(HeroNode heroNode){
        //创建指针
        HeroNode temp=head.getNext();
        //创建标识,标识是否找到目标节点
        boolean flag=false;
        if(temp == null){
            System.out.println("链表数据为空,无法修改!");
            return;
        }
        while (true){
            if(temp == null){
                break;
            }else if(temp.getNo() == heroNode.getNo()){
                flag = true;
                break;
            }
            temp=temp.getNext();
        }
        if(flag){
            temp.setName(heroNode.getName());
            temp.setNickName(heroNode.getNickName());
        }else{
            System.out.println("没有找到目标节点!");
        }
    }

    /**
     * 删除
     */
    public void delete(int no){
        //创建指针
        HeroNode temp=head;
        //创建标识:标识为true标识找到目标节点
        boolean flag = false;
        while (true){
            if(temp.getNext() == null){
                break;
            }
            if(temp.getNext().getNo() == no){
                flag = true;
                break;
            }
            temp=temp.getNext();
        }
        if(flag){
            temp.setNext(temp.getNext().getNext());
        }else{
            System.out.println("未找到id为"+no+"的节点数据!");
        }
    }

单链表相关面试题解析

获取单链表有效节点的个数

    /**
     * 获取有效节点的个数
     * @return
     */
    public int getLength(){
        if(head.getNext() == null){
            System.out.println("链表数据为空!");
            return 0;
        }
        //创建指针
        HeroNode temp = head.getNext();
        int length = 0;
        while (temp != null){
            length++;
            temp=temp.getNext();
        }
        return length;
    }

获取链表中倒数第k个节点

    /**
     * 获取链表中的倒数第index个节点
     * @param index
     * @return
     */
    public HeroNode getLastNode(int index){
        if(head.getNext() == null){
            System.out.println("链表数据为空!");
            return null;
        }
        //创建辅助指针
        HeroNode temp=head.getNext();
        //获取链表有效节点的个数
        int length = getLength();
        //校验参数有效性
        if(index <= 0 || index > length ){
            System.out.println("参数非法!");
            return null;
        }
        for (int i = 0; i < length - index; i++){
            temp=temp.getNext();
        }
        return temp;
    }

单链表的反转

    /**
     * 单链表的反转
     */
    public void reversal(){
        //当链表无有效节点或者说有效节点的个数为1的时候不进行反转
        if(head.getNext() == null || head.getNext().getNext() == null) {
            System.out.println("单链表的有效节点个数为空或者个数为一,不进行反转!");
            return;
        }
        //创建辅助指针以及辅助头节点
        HeroNode temp = head.getNext();
        HeroNode next = null;
        HeroNode newHead = new HeroNode(0,"","");
        while(temp != null){
            next = temp.getNext();
            temp.setNext(newHead.getNext());
            newHead.setNext(temp);
            temp = next;
        }
        head.setNext(newHead.getNext());
    }

编码实现双向链表

与双向链表相比,单向链表无法反向遍历数据内容。
在进行数据删除的时候不能实现自我删除,需要借助借助指针定位在目标节点的上一个来进行操作。
之所以称之为双向链表,因为组成链表的节点中不仅包含一个next域,还有一个pre域指向上一个节点。
双向链表代码实现

package com.xsh.demo.datastructure;

import com.xsh.demo.pojo.DoubleHeroNode;

/**
 * 双向链表实现
 * @author xiashihua
 */
public class DoubleLinkedList {

    /**
     * 定义头节点
     */
    private DoubleHeroNode head=new DoubleHeroNode(0,"","");

    /**
     * 遍历双向链表
     */
    public void show(){
        if(head.getNext() == null){
            System.out.println("链表数据为空!");
            return;
        }
        DoubleHeroNode temp = head.getNext();
        while (true){
            if(temp == null){
                break;
            }
            System.out.println(temp);
            temp=temp.getNext();
        }
    }

    /**
     * 有序添加节点
     * @param node
     */
    public void addByOrder(DoubleHeroNode node){
        DoubleHeroNode temp = head;
        boolean flag = false;
        while (true){
            if(temp.getNext() == null){
                break;
            }
            if(temp.getNext().getNo() > node.getNo()){
                break;
            }
            if(temp.getNo() == node.getNo()){
                flag = true;
                break;
            }
            temp=temp.getNext();
        }
        if(flag){
            System.out.println("编号为"+node.getNo()+"的节点已经存在,不能重复添加!");
        }else{
            node.setNext(temp.getNext());
            node.setPre(temp);
            if(temp.getNext() != null){
                temp.getNext().setPre(node);
            }
            temp.setNext(node);
        }
    }

    /**
     * 修改节点信息
     * @param node
     */
    public void update(DoubleHeroNode node){
        if(head.getNext() == null){
            System.out.println("链表数据为空!");
            return;
        }
        DoubleHeroNode temp = head.getNext();
        boolean flag = false;
        while (true){
            if(temp == null){
                break;
            }
            if(temp.getNo() == node.getNo()){
               flag =  true;
               break;
            }
            temp=temp.getNext();
        }
        if(flag){
            temp.setName(node.getName());
            temp.setNickName(node.getNickName());
        }else{
            System.out.println("未找到编号为"+node.getNo()+"的节点数据!");
        }
    }

    /**
     * 根据编号删除节点
     * @param no
     */
    public void delete(int no){
        if(head.getNext() == null){
            System.out.println("链表数据为空!");
            return;
        }
        DoubleHeroNode temp = head.getNext();
        boolean flag = false;
        while (true){
            if(temp == null){
                break;
            }
            if(temp.getNo() == no){
                flag = true;
                break;
            }
            temp=temp.getNext();
        }
        if(flag){
            if(temp.getNext() != null){
                temp.getNext().setPre(temp.getPre());
            }
            temp.getPre().setNext(temp.getNext());
        }else{
            System.out.println("未找到编号为"+no+"的数据节点!");
        }
    }
}

环形链表及约瑟夫问题

单项循环链表逻辑示意图

约瑟夫问题:
设编号为1,2,3...n的n个人围成一圈,约定编号为k(1 对于约瑟夫问题,可以使用一个不带头节点的环形链表来解决:先构成一个有n个节点的单向环形链表,然后由k节点起从1开始计数,计到m的时候对应的节点从链表中删除,然后从被删除节点的下一个节点开始计数,直到最后一个节点从链表中删除算法结束。

单向环形链表代码实现以及解决约瑟夫问题

单向环形链表node节点实体代码

package com.xsh.demo.pojo;

/**
 * 单向环形链表的pojo类
 * @author xiashihua
 */
public 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;
    }
}

单向环形链表实现

package com.xsh.demo.datastructure;

import com.xsh.demo.pojo.Boy;

/**
 * 单向环形链表实现
 * @author xiashihua
 */
public class CircleSingleLinkedList {

    private Boy first = null;

    /**
     * 创建环形链表,根据传递的数字创建节点为多少的环形链表
     * @param number
     */
    public void add(int number){
        if(number < 1){
            System.out.println("参数非法");
            return;
        }
        //创建指针
        Boy temp = null;
        for (int i = 1; i <= number; i++) {
            Boy boy = new Boy(i);
            if(i == 1){
                //第一个节点
                first = boy;
                temp = boy;
                boy.setNext(first);
            }else{
                temp.setNext(boy);
                boy.setNext(first);
                temp = boy;
            }
        }
    }

    /**
     * 遍历单向环形链表
     */
    public void show(){
        if(first == null){
            System.out.println("链表数据为空!");
            return;
        }
        //创建指针
        Boy temp = first;
        while (true){
            System.out.println(temp.getNo());
            if(temp.getNext() == first){
                //表明遍历到了链表的最后
                break;
            }
            temp = temp.getNext();
        }
    }
}

以上代码实现了一个简单的单向环形链表,实现了创建链表以及遍历链表输出的功能,接下来就利用这个链表完成约瑟夫问题的求解。
编码解决约瑟夫问题

    /**
     * 解决约瑟夫问题
     * @param startNo 开始数数的节点编号
     * @param count   数多少个数
     * @param number  环形链表的节点数
     */
    public void joseph(int startNo, int count, int number) {
        //创建环形链表
        add(number);
        //参数校验
        if (startNo < 1 || startNo > number) {
            System.out.println("参数非法");
            return;
        }
        /**
         * 将first指针移动到需要删除的节点,将temp指针移动到需要删除节点的上一个节点
         * 实现思路:若报数2,因为节点本身也要报数,其实指针只需要移动1步。
         * 因为是单向的链表,所以无法自我删除,所以需要temp指针在目标节点的上一个位置完成删除
         */
        for (int i = 0; i < startNo - 1; i++) {
            first = first.getNext();
        }
        //创建指针
        Boy temp = first;
        //将指针移动到first的前一个位置
        while (true) {
            if (temp.getNext() == first) {
                break;
            }
            temp = temp.getNext();
        }
        //循环数数
        while (true) {
            if (temp == first) {
                //说明链表内只剩下一个节点
                break;
            }
            //数数
            for (int i = 0; i < count - 1; i++) {
                first = first.getNext();
                temp = temp.getNext();
            }
            //打印并出圈
            System.out.println("小孩" + first.getNo() + "出圈");
            first = first.getNext();
            temp.setNext(first);
        }
        //循环结束说明圈内只剩下一个节点
        System.out.println("小孩" + first.getNo() + "出圈");
    }

栈(Stack)

栈是一个先入后出的有序列表。
栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端称为栈顶,另一端为固定的一端,称之为栈底。
根据栈的定义可知,最先放入栈中的元素在栈底,最后放入的元素在栈顶。而删除元素刚好相反,最后放入栈中的元素最先被删除,最先被放入的元素最后被删除。

利用数组编码实现栈

package com.xsh.demo.datastructure;

/**
 * 数组实现栈
 *
 * @author xiashihua
 */
public class ArrayStack {

    /**
     * 栈的最大长度
     */
    private int maxSize;
    /**
     * 栈
     */
    private int[] stack;
    /**
     * 栈顶指针,栈空则为-1
     */
    private int top;

    public ArrayStack(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[this.maxSize];
        this.top = -1;
    }

    /**
     * 判断栈满
     *
     * @return
     */
    public boolean isPull() {
        return top == maxSize - 1;
    }

    /**
     * 判断栈空
     *
     * @return
     */
    public boolean isEmpty() {
        return top == -1;
    }

    /**
     * 入栈操作
     *
     * @param number
     */
    public void push(int number) {
        if (isPull()) {
            System.out.println("栈满,无法插入数据!");
            return;
        }
        top++;
        stack[top] = number;
    }

    /**
     * 出栈操作
     *
     * @return
     */
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈空,无法取出数据!");
        }
        int value = stack[top];
        top--;
        return value;
    }

    /**
     * 遍历栈:从栈顶到栈底进行遍历
     */
    public void show() {
        if (isEmpty()) {
            System.out.println("栈空,无法遍历数据!");
        }
        for (int i = top; i >= 0; i--) {
            System.out.println(stack[i]);
        }
    }
}

利用双向链表编码实现栈

package com.xsh.demo.datastructure;


import com.xsh.demo.pojo.DoubleHeroNode;

/**
 * 双向链表实现栈
 * @author xiashihua
 */
public class LinkedListStack {
    /**
     * 初始化头节点
     */
    DoubleHeroNode head = new DoubleHeroNode(0,"","");

    /**
     * 判断链表是否为空
     * @return
     */
    public boolean isEmpty(){
        return head.getNext() == null;
    }

    /**
     * 入栈
     * @param node
     */
    public void push(DoubleHeroNode node){
        //创建指针
        DoubleHeroNode temp = head;
        while (true){
            if(temp.getNext() == null){
                break;
            }
            temp = temp.getNext();
        }
        temp.setNext(node);
        node.setPre(temp);
    }

    /**
     * 出栈:从链表尾部获取数据
     * @return
     */
    public DoubleHeroNode pop(){
        //创建指针
        DoubleHeroNode temp = head;
        while (true){
            if(temp.getNext() == null){
                break;
            }
            temp = temp.getNext();
        }
        temp.getPre().setNext(temp.getNext());
        return temp;
    }

    /**
     * 遍历栈:从链表尾部打印数据
     */
    public void show(){
        //创建指针
        DoubleHeroNode temp = head;
        //将指针移动到链表的最后
        while(true){
            if(temp.getNext() == null){
                break;
            }
            temp = temp.getNext();
        }
        //反向遍历输出
        while (true){
            System.out.println(temp);
            if(temp.getPre() == head){
                break;
            }
            temp = temp.getPre();
        }
    }

}

栈的应用实例:通过栈来完成综合计算器的实现

综合计算器的实现要求是对一个字符串表达式进行计算,例如直接计算出表达式1+2/5*4的值。

实现思路
首先我们需要一个indexs索引来帮助遍历字符串,index指向字符串的每一个字符。
然后我们使用两个栈,一个符号栈和一个数字栈。
如果index遍历到的字符是数字,则直接入数字栈。
如果遍历到的字符是运算符,则分三种情况入栈:

  • 如果符号栈为空,则直接入栈;
  • 如果当前符号的运算符优先级小于或等于栈顶的符号,则从数字栈中pop出两个数字,从符号栈中pop出一个符号进行计算,并将计算结果入数栈,运算完毕之后如果当前符号的优先级大于栈顶符号,则入栈;
  • 如果当前符号的优先级大于栈顶符号优先级,则直接入栈。
    按照如上规则,当字符串遍历完毕之后,则只需要按顺序取出数字栈和符号栈的符号进行挨个计算,最后数栈中剩下的一个结果则为计算结果。

利用栈编码实现综合计算器

package com.xsh.demo.datastructure;

/**
 * 利用栈实现综合计算器
 *
 * @author xiashihua
 */
public class Calculator {

    /**
     * 主方法,实现对表达式的解析并计算
     *
     * @param str
     * @return
     */
    public int master(String str) {
        //创建符号栈和数字栈
        ArrayStack numStack = new ArrayStack(50);
        ArrayStack symbolStack = new ArrayStack(50);
        int index = 0;
        /**
         * chr用来表示index对应的字符
         */
        char chr = ' ';
        int num1;
        int num2;
        int symbol;
        int result;
        String number="";
        while (true) {
            chr = str.substring(index, index + 1).charAt(0);
            //判断截取的字符是否是符号
            if (isSymbol(chr)) {
                //是符号
                //如果符号栈为空,则直接入栈
                if (symbolStack.isEmpty()) {
                    symbolStack.push(chr);
                }else{
                    //如果当前符号优先级小于或等于栈顶符号优先级,则先取出两个数字和栈顶符号进行计算,然后将计算结果和当前符号入栈
                    if (symbolPri(chr) <= symbolPri(symbolStack.peek())) {
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        symbol = symbolStack.pop();
                        result = calculate(num1, num2, symbol);
                        numStack.push(result);
                        symbolStack.push(chr);
                    }else{
                        //如果当前符号优先级大于栈顶符号优先级,则直接入栈
                        symbolStack.push(chr);
                    }
                }
            } else {
                //是数字
                number+=chr;
                //判断是否是字符串最后的数字
                if(index == str.length()-1){
                    numStack.push(Integer.parseInt(number));
                }else{
                    if(isSymbol(str.substring(index+1,index+2).charAt(0))){
                        numStack.push(Integer.parseInt(number));
                        number = "";
                    }
                }
            }
            index++;
            if(index >= str.length()){
                break;
            }
        }
        //循环遍历求和
        while (true){
            if(symbolStack.isEmpty()){
                break;
            }
            num1 = numStack.pop();
            num2 = numStack.pop();
            symbol = symbolStack.pop();
            result = calculate(num1, num2, symbol);
            numStack.push(result);
        }
        return numStack.pop();
    }

    /**
     * 判断扫描的字符是否是符号
     *
     * @param chr
     */
    public boolean isSymbol(int chr) {
        return chr == '+' || chr == '-' || chr == '*' || chr == '/';
    }

    /**
     * 获取运算符的优先级
     *
     * @param chr
     * @return
     */
    public int symbolPri(int chr) {
        if (chr == '*' || chr == '/') {
            return 1;
        } else if (chr == '-' || chr == '+') {
            return 0;
        }
        throw new RuntimeException("运算符非法!");
    }

    /**
     * 计算方法
     *
     * @param num1
     * @param num2
     * @param chr
     * @return
     */
    public int calculate(int num1, int num2, int chr) {
        int result = 0;
        switch (chr) {
            case '+':
                result = num1 + num2;
                break;
            case '-':
                result = num2 - num1;
                break;
            case '*':
                result = num1 * num2;
                break;
            case '/':
                result = num2 / num1;
                break;
            default:
                break;
        }
        return result;
    }

}

前缀、中缀、后缀表达式

  • 中缀表达式也就是正常的计算表达式,例如:(3+4)*5-6
  • 前缀表达式又称之为波兰表达式,即运算符在操作数之前。例如:(3+4)5-6的前缀表达式对应为-+3456
  • 后缀表达式又称之为逆波兰表达式,与前缀表达式相似,只是运算符位于操作数之后。例如:(3+4)5-6对应的后缀表达式为34+56-

中缀表达式是人最熟悉的形式,但是对于计算机来说是难以判断的计算表达式。
所以在一般情况下都会将中缀表达式转换为前缀表达式和后缀表达式来进行运算,其中后缀表达式的计算更为方便简单。

程序中对于前缀表达式求值的步骤
程序从右至左扫描中缀表达式,扫描到数字的时候将数字压入栈中。遇到运算符时,弹出栈中的栈顶元素和次顶元素,并用运算符进行相应的计算,并将结果入栈。重复以上步骤扫描至表达式的最左端,最后得到的值即为表达式的结果。
程序中对于后缀表达式求值的步骤
程序从左到右扫描表达式,遇到数字时将数字压入栈中。遇到运算符时将弹出栈中的栈顶元素和次顶元素并使用运算符进行计算,计算结束之后将结果压入栈中。重复以上步骤扫描至表达式的最右端,最后得到的值即为表达式的结果。

接下来我们就采用逆波兰表达式的形式来完成综合计算器的实现。

编码实现逆波兰表达式计算器

package com.xsh.demo.datastructure;

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

/**
 * 逆波兰计算器实现
 * @author xiashihua
 */
public class ReversePolishCalculator {

    /**
     * 将逆波兰表达式转换为一个List集合,方便遍历
     * 在此约定逆波兰表达式的元素之间都会使用空格隔开,有利于字符串的切割
     * @param str
     * @return
     */
    public List expressionToList(String str){
        List list=new ArrayList<>();
        String[] split = str.split(" ");
        for (String s : split) {
            list.add(s);
        }
        return list;
    }

    /**
     * 主计算方法
     * @param list
     * @return
     */
    public int calculate(List list){
        //创建数栈
        Stack stack=new Stack<>();
        int result = 0;
        //遍历list
        for (String str : list) {
            if(str.matches("\\d+")){
                //匹配为数字
                stack.push(str);
            }else{
                //匹配为符号
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                if(str.equals("+")){
                    result = num1 + num2;
                }else if(str.equals("-")){
                    result = num2 - num1;
                }else if(str.equals("*")){
                    result = num1 * num2;
                }else if(str.equals("/")){
                    result = num2 / num1;
                }
                stack.push(result + "");
            }
        }
        return Integer.parseInt(stack.pop());
    }
}

如上,就非常简单的实现了逆波兰表达式的综合计算器,但是问题是如何将中缀表达式转换为逆波兰表达式呢?

中缀表达式转后缀表达式

思路分析
1、初始化两个栈,存储运算符的栈s1以及储存中间结果的栈s2;
2、从左至右扫描中缀表达式;
3、遇到操作数的时候将操作数压入s2;
4、遇到运算符时,比较其与s1栈顶运算符的优先级:
4.1、如果s1为空,或者栈顶运算符为'(',则直接将此运算符入栈;
4.2、否则,若此运算符优先级比栈顶运算符优先级高,则直接入栈;
4.3、否则,则将s1栈顶的运算符弹出并压入s2中,然后再次转到4.1步骤与新的栈顶运算符相比较;
5、遇到括号时:
5.1、如果是左括号'(',则直接压入栈s1;
5.2、如果是右括号')',则依次弹出s1栈顶的运算符,并压入s2,直到遇到一个左括号为止,此时将这一对括号丢弃;
6、重复步骤2-5,直到表达式的最右边;
7、将s1中剩余的运算符依次弹出并压入s2;
8、依次弹出s2中的元素并输入,其结果的逆序就是中缀表达式转换而来的后缀表达式。

中缀表达式转后缀表达式编码实现

package com.xsh.demo.datastructure;

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

/**
 * 中缀表达式转后缀表达式
 * @author xiashihua
 */
public class InfixToSuffix {


    /**
     * 中缀表达式转后缀表达式
     * @param expList
     * @return
     */
    public List master(List expList){
        /**
         * 初始化符号栈和中间结果栈
         * 按照思路分析中使用中间结果栈来保存数据的话其实不妥,因为中间结果栈是没有出栈操作的,而且最后还需要将输出结果逆序
         * 在此使用一个list集合来替代中间结果栈
         */
        Stack s1=new Stack<>();
        List s2=new ArrayList<>();
        //遍历expList
        for (String item : expList) {
            if(item.matches("\\d+")){
                //如果为数字则直接入中间结果栈
                s2.add(item);
            }else if(item.equals("(")){
                //如果item为左括号则直接入符号栈
                s1.push(item);
            }else if(item.equals(")")){
                //如果item是右括号则将符号栈中符号挨个出战入s2,直到遇到左括号为止
                while (!s1.peek().equals("(")){
                    s2.add(s1.pop());
                }
                //弹出左括号
                s1.pop();
            }else{
                while (s1.size() != 0 && symbolPri(s1.peek()) >= symbolPri(item)){
                    s2.add(s1.pop());
                }
                s1.push(item);
            }
        }
        //循环结束之后需要将符号栈中的最后一个符号也入s2
        s2.add(s1.pop());
        return s2;
    }

    /**
     * 获取运算符的优先级
     *
     * @param chr
     * @return
     */
    public int symbolPri(String chr) {
        if (chr.equals("*") || chr.equals("/")) {
            return 1;
        } else if (chr.equals("-") || chr.equals("+")) {
            return 0;
        }else{
            return -1;
        }
    }

    /**
     * 将中缀表达式转换为中缀表达式的字符集合,方便遍历
     * @param str
     * @return
     */
    public List expressionToList(String str){
        String temp =  "";
        int index = 0;
        List list = new ArrayList<>();
        while (index < str.length()){
            if(str.charAt(index) <= 48 || str.charAt(index) >= 57){
                //表示截取的字符为符号
                list.add(str.charAt(index)+"");
                index ++;
            }else{
                //表示截取的字符为数字
                temp += str.charAt(index);
                if(index == str.length()-1){
                    list.add(temp);
                    index++;
                }else{
                    if(str.charAt(index+1) >=48 && str.charAt(index+1) <=57){
                        index ++;
                    }else{
                        list.add(temp);
                        temp = "";
                        index ++;
                    }
                }
            }
        }
        return list;
    }

}

递归

递归在代码层面来简单的说就是方法自己调用自己。

使用递归需要遵守的重要规则

  • 递归每执行一个方法的时候就会在栈中创建一个独立的受保护的空间;
  • 递归调用的方法的局部变量是独立的,不会互相影响;
  • 如果方法中操作或传递的是引用类型变量,则递归的方法会共享该引用类型变量的数据;
  • 递归必须向退出递归的条件逼近,否则就是无限递归,会导致栈空间溢出发生错误;
  • 当一个方法执行完毕,或者遇到return就会返回,遵守谁调用就将结果返回给谁。同时当方法执行完毕或者返回时,该方法也就执行完毕。

迷宫问题


如上图所示为一个7*8的迷宫,红色部分为围墙,绿色星星为目标位置。我们需要通过编码来实现找到圆球从起始位置到目标位置的路径。
问题抽象为代码,首先我们使用一个二维数组来模拟图中的迷宫,约定为数组值为1的就代表围墙。

迷宫初始化代码实现

package com.xsh.demo.arithmetic;

/**
 * 使用递归解决迷宫回溯问题
 * @author xiashihua
 */
public class Maze {

    /**
     * 定义公共二维数组表示地图
     */
    private int[][] map = new int[8][7];

    /**
     * 初始化地图:默认约定二维数组值为1则表示围墙
     */
    public void init (){
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        map[3][1] = 1;
        map[3][2] = 1;
        //遍历查看初始化之后的地图
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j]+"   ");
            }
            System.out.println();
        }
    }
}

初始化效果为:

接下来使用递归实现从[1][1]起点走到[6][5]的路线:

迷宫回溯寻路代码实现

    /**
     * 实现迷宫回溯的主方法
     * @param i 起点坐标x
     * @param j 起点坐标y
     * @return
     */
    public boolean master(int i,int j){
        /**
         * 功能约定:
         *      1、迷宫坐标有三个状态:0表示未走过未初始化,1表示围墙,2表示走过并且可以走通,3表示走过并且走不通
         *      2、圆球寻路的规则是下、右、上、左的策略
         */
        if(map[6][5] == 2){
            //目标被标记为2表示寻路完成
            return true;
        }else{
            if(map[i][j] == 0){
                //首先默认当前所在点为走过且可以走通
                map[i][j] = 2;
                //接下来按照策略往下寻路
                if(master(i+1,j)){
                    return true;
                }else if(master(i,j+1)){
                    return true;
                }else if(master(i-1,j)){
                    return true;
                }else if(master(i,j-1)){
                    return true;
                }else{
                    //说明上下左右都走不通,当前点为死路
                    map[i][j] = 3;
                    return false;
                }
            }else{
                return false;
            }
        }
    }

运行方法效果如图:

其中数字2的路线就是寻址得出的路线。

八皇后问题

八皇后问题编码求解

package com.xsh.demo.arithmetic;

/**
 * 八皇后问题求解
 * Eight queens是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出的问题,是回溯算法的典型案例。
 * 问题表述为:在8×8格的国际象棋上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。
 * 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。
 *
 * @author xiashihua
 */
public class EightQueues {

    /**
     * 计数解法
     */
    public int count = 0;

    /**
     * 皇后个数
     */
    private int max = 8;

    /**
     * arr用来装载一种八皇后算法的解
     * arr的下标+1表示棋盘的行,arr下标对应的数值+1表示该行之中皇后的列坐标
     * 所以:[下标+1,下表对应的数值+1] = 皇后在棋盘上的坐标
     * 由题干所知,皇后每一行有且仅有一个,所以当arr都装载了数据的时候则说明每一行都放置了一个符合规则的皇后,也就是一种解。
     */
    private int[] arr = new int[max];

    /**
     * 实现八皇后回溯的主方法
     *
     * @param n 开始放置的皇后序号 n=0则表示从第一个皇后开始放置
     */
    public void master(int n) {
        if (n == max) {
            //n==max表示八个皇后都符合规则的摆放完毕,所以打印并结束
            print();
            return;
        }
        //依次放置皇后,如果放置的位置产生冲突则回溯将皇后摆放到下一个点
        for (int i = 0; i < max; i++) {
            arr[n] = i;
            if (verify(n)) {
                //当前皇后与之前的皇后位置不冲突,递归回溯,摆放下一个皇后
                master(n + 1);
            }
            //走到这里表示当前皇后与之前的皇后位置发生冲突,则接着进行循环,将当前皇后的位置挪动到下一格
        }
    }

    /**
     * 验证皇后位置是否正确方法
     *
     * @param n 第几个皇后
     * @return
     */
    public boolean verify(int n) {
        /**
         * 判断第n个皇后和前面的几个皇后的位置是否满足规则:不处于同一列和同一斜线
         * 是否处于同一行不需要判断,因为一个n就代表每行的皇后,n不可能相同
         */
        for (int i = 0; i < n; i++) {
            /**
             * arr[i] == arr[n]:判断第n个皇后是否与之前的皇后处于同一列
             * Math.abs(n - i) == Math.abs(arr[n] - arr[i]):判断第n个皇后是否与之前的皇后处于同一斜线
             */
            if (arr[i] == arr[n] || Math.abs(n - i) == Math.abs(arr[n] - arr[i])) {
                return false;
            }
        }
        return true;
    }

    /**
     * 打印arr方法
     */
    public void print() {
        count++;
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

排序算法

排序也称排序算法,是将一组数据依指定的顺序排列的过程。

排序的分类
1、内部排序

  • 指将需要处理的数据全部加载到内存中进行排序
    2、外部排序
  • 若数据量过大,无法全部加载到内存中,需要借助外部存储进行排序

冒泡排序

冒泡排序的基本思想是:从前往后遍历需要排序的序列,依次比较相邻元素的值。若发现逆序则交换,使值较大的元素逐渐从前移向后方,就像水底的气泡一样逐渐向上冒。
因为在排序的过程中,各个元素不断接近自己的位置。如果一次遍历没有进行任何的位置交换,则说明序列有序,因此可以在排序过程中设置一个标志flag判断元素是否进行过交换,从而减少不必要的比较。

冒泡排序编码实现

package com.xsh.demo.arithmetic;

import java.util.Arrays;

/**
 * 冒泡排序实现
 *
 * @author xiashihua
 */
public class BubbleSort {
    /**
     * 将arr中的数据进行排序并打印
     *
     * @param arr
     */
    public void master(int[] arr) {
        int temp = 0;
        //标识变量,默认为false,表示在某次循环中没有发生任何的元素替换位置行为
        boolean flag = false;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if(arr[j] > arr[j+1]){
                    flag = true;
                    temp = arr[j];
                    arr[j] =arr[j+1];
                    arr[j+1] = temp;
                }
            }
            System.out.println("第"+(i+1)+"次排序!");
            System.out.println(Arrays.toString(arr));
            if(flag == false){
                //说明在某次循环中没有发生元素替换位置的行为,也就是说此时的arr已经排好顺序了
                break;
            }else{
                flag = false;
            }
        }
    }
}

选择排序

选择排序也属于内部排序法,是从欲排序的数据中,按照指定的规则选出某一种元素,再依规定交换位置之后达到排序的目的。
选择排序的基本思想是:第一次从数组的arr[0] - arr[n-1]中选取最小值,与arr[0]交换,第二次从arr[1] - arr[n-1]中选取最小值,与arr[1]交换,依次类推,最后得到从小到大的有序序列。

选择排序代码实现

package com.xsh.demo.arithmetic;

import java.util.Arrays;

/**
 * 选择排序实现
 *
 * @author xiashihua
 */
public class SelectSort {

    /**
     * @param arr
     */
    public void master(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]) {
                    minIndex = j;
                    min = arr[j];
                }
            }
            //循环结束表示此时的min已经为数组中最小的元素
            if(minIndex != i){
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
            System.out.println("第" + (i + 1) + "次循环!");
            System.out.println(Arrays.toString(arr));
        }
    }

}

插入排序

插入排序是对欲排序的元素以插入的方式寻找该元素的适当位置,以达到排序的目的。
插入排序的基本思想是:把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中包含有n+1个元素。排序过程中每次从无序表中取出第一个元素,把它的排序码依次与有序表中的排序码进行比较,把它插入到有序表的适当位置,使之成为新的有序表。

插入排序编码实现

package com.xsh.demo.arithmetic;

/**
 * 插入排序
 * @author xiashihua
 */
public class InsertSort {

    public void master(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            /**
             * insertValue表示即将要进行比较的数据,insertIndex表示要与insertValue进行比较的数据的下标
             * 在插入排序中,默认将下标为0的数字视作为有序列表的元素,将其后的元素视为无序列表中的待排序元素,所以循环时从1开始
             */
            int insertValue = arr[i];
            int insertIndex = i - 1;
            /**
             * insertIndex >= 0保证了循环与有序列表元素对比的过程不会出现索引越界
             * arr[i] < arr[insertIndex]表示当前的待比较元素比前方有序列表中的元素更小
             */
            while (insertIndex >= 0 && insertValue < arr[insertIndex]){
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex --;
            }
            //循环结束则表示找到insertValue的插入位置
            arr[insertIndex + 1] = insertValue;
        }
    }

}

由插入排序代码解析可知,插入排序在将元素进行大小比对的时候,如果符合要求例如当前元素小于比对的元素,则会将比对的元素后移。此时,如果一个很小的元素在数组的末尾,则会导致元素在每一次与前方比对元素比对的时候都会产生后移赋值的操作,这样会对效率产生影响。
因此,为了优化插入排序的效率,产生了希尔排序算法。

希尔排序

希尔排序是希尔于1959年提出的一种排序算法。希尔排序也是一种插入排序,它是简单插入排序经过改良之后的一个更高效的版本,也称之为缩小增量排序。
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减为1时,整个文件恰被分成一组,算法结束。

希尔排序图解

元素交换法编码实现

package com.xsh.demo.arithmetic;

import java.util.Arrays;

/**
 * 希尔排序实现(交换法)
 *
 * @author xiashihua
 */
public class ShellSort {

    public void master(int[] arr) {
        //创建临时变量
        int temp = 0;
        int count = 0;
        //最外层循环是按照步长进行分组
        for (int k = arr.length / 2; k > 0; k /= 2) {
            for (int i = k; i < arr.length; i++) {
                for (int j = i - k; j >= 0; j -= k) {
                    if (arr[j] > arr[j + k]) {
                        temp = arr[j];
                        arr[j] = arr[j + k];
                        arr[j + k] = temp;
                    }
                }
            }
            System.out.println("希尔排序第" + (++count) + "次排序:" + Arrays.toString(arr));
        }
    }

}

交换法在进行排序的时候是类似于冒泡排序的交换位置形式,效率较低,如下移位法采用插入排序的移位机制,效率较高:

移位法希尔排序实现

    /**
     * 移位法希尔排序实现
     *
     * @param arr
     */
    public void master2(int[] arr) {
        //k为步长,且逐渐缩短步长的分组
        for (int k = arr.length / 2; k > 0; k /= 2) {
            for (int i = k; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                if (arr[j] < arr[j - k]) {
                    while (j - k >= 0 && temp < arr[j - k]) {
                        arr[j] = arr [j - k];
                        j -= k;
                    }
                    arr[j] = temp;
                }
            }
        }
    }

快速排序

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

快速排序示意图

快速排序编码实现

package com.xsh.demo.arithmetic;

/**
 * 快速排序实现
 * @author xiashihua
 */
public class QuickSort {

    public void master(int[] arr,int left,int right){
        //左下标
        int l = left;
        //右下标
        int r = right;
        //中轴值
        int pivot = arr[(left + right) / 2];
        //临时变量
        int temp = 0;

        while (l < r){
            while (arr[l] < pivot){
                l += 1;
            }
            while (arr[r] > pivot){
                r -= 1;
            }
            if(l >= r){
                break;
            }
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            if(arr[l] == pivot){
                r -= 1;
            }
            if(arr[r] == pivot){
                l +=1;
            }
        }

        if(l == r){
            l +=1;
            r -=1;
        }
        if(left < r){
            master(arr,left,r);
        }
        if(right > l){
            master(arr,l,right);
        }
    }

}

归并排序

归并排序是利用归并的思想实现的排序方法,该算法利用经典的分治策略。
分治法的分就是将问题分成一些小的问题然后去递归求解,而治的阶段则将分的阶段得到的各个答案修补在一起,即分而治之。

归并排序示意图

由图可以看出,在分的过程中实际上是没有进行任何排序的操作的,只是为了给治这个操作提供递归的条件。

归并排序代码实现

package com.xsh.demo.arithmetic;

/**
 * 归并排序实现
 *
 * @author xiashihua
 */
public class MergeSort {

    /**
     * 使用递归实现归并排序的方法
     *
     * @param arr   需要排序的的原始数组
     * @param left  原始数组的最左索引
     * @param right 原始数组的最右索引
     * @param temp  临时数组
     */
    public void master(int[] arr, int left, int right, int[] temp) {
        //当左边索引小于右边索引的时候永远进行分
        if (left < right) {
            int mid = (left + right) / 2;
            master(arr, left, mid, temp);
            master(arr, mid + 1, right, temp);
            merge(arr, left, mid, right, temp);
        }
    }

    /**
     * 元素合并的方法
     *
     * @param arr   排序的原始数组
     * @param left  左边有序序列的初始索引
     * @param mid   中间索引
     * @param right 右边有序序列的结束索引
     * @param temp  用作数据中转的临时数组
     */
    public void merge(int[] arr, int left, int mid, int right, int[] temp) {
        //初始化索引
        //初始化i:左边有序列表的初始索引
        int i = left;
        //初始化j:右边有序列表的初始索引
        int j = mid + 1;
        //初始化t:指向当前临时数组的当前索引
        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;
            }
        }
        /**
         * 当某一边的元素处理完毕之后,另外一边有序列表必然有未处理的剩余数据
         * 所以接下来就将剩余数据一边的有序列表数据全部填充到temp中
         */
        while (i <= mid) {
            temp[t] = arr[i];
            t += 1;
            i += 1;
        }
        while (j <= right) {
            temp[t] = arr[j];
            t += 1;
            j += 1;
        }
        /**
         * 排序处理完毕之后将temp中的元素拷贝到arr中
         */
        t = 0;
        int tempLeft = left;
        while (tempLeft <= right) {
            arr[tempLeft] = temp[t];
            t += 1;
            tempLeft += 1;
        }
    }


}

基数排序(桶排序)

基数排序属于分配式排序,又称桶子法或者bin sort。顾名思义,它是通过键值的各个位的值,将要排序的元素分配至某些“桶”中,达到排序的作用。
基数排序是桶排序的拓展,是高效率的稳定性排序法。

基数排序的基本思想:将所有待比较数值统一为同样的数位长度,数位短的数值前面补零。然后从最低位开始,依次进行一次排序。这样从最低为到最高位排完之后,数列就变成一个有序数列。

基数排序代码实现:

package com.xsh.demo.arithmetic;

import java.util.Arrays;

/**
 * 基数排序实现
 *
 * @author xiashihua
 */
public class RadixSort {

    public void master(int[] arr) {
        //获取数组中最大的元素
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        //获取最大元素的位数
        int maxLength = (max + "").length();
        /**
         * 定义一个二维数组,表示10个桶,每个桶即为当个的一维数组
         * 为防止存放数据的时候桶溢出,所以单个桶的大小为arr.length
         * 基数排序是典型的使用空间换时间的算法
         */
        int[][] bucket = new int[10][arr.length];
        /**
         * 为记录每个桶中分别放入了多少个元素,我们定义一个长度为10的 一维数组进行记录
         * 例如:bucketElementCounts[0]即表示bucket[0][arr.length]这个桶所存放的元素个数
         */
        int[] bucketElementCounts = new int[10];

        /**
         * 使用循环来解决排序问题
         * 其中n代表的是每次循环所取的位数
         */
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            for (int j = 0; j < arr.length; j++) {
                //取出每个元素当次循环用来匹配桶的值:第一次是个位,第二次是十位,第三次是百位......
                int digitOfElement = arr[j] / n % 10;
                //将元素放到匹配的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }
            //所有数据都归桶之后,按照顺序将桶中的元素取出放回到arr中准备下次循环
            int index = 0;
            for (int k = 0; k < bucketElementCounts.length; k++) {
                //如果桶中有数据,才将数据放回arr
                if (bucketElementCounts[k] != 0) {
                    //当第k个桶数据不等于0就将第k个桶的数据循环到arr中
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        arr[index++] = bucket[k][l];
                    }
                }
                //当将某个桶的数据复制完毕之后,需要将这个桶的计数归零
                bucketElementCounts[k] = 0;
            }
            System.out.println("第" + (i + 1) + "次轮数据处理,处理的结果为" + Arrays.toString(arr));
        }
    }

}

排序算法之间时间/空间复杂度稳定性之间的比较

查找算法

二分查找法

二分查找思路分析
1、二分查找只能对有序的数组进行查找,如果想要对无序的数组进心查找,需要先对无序数组排序;
2、首先需要确定数组中间值的下标:(left+right)/2,然后用目标value和中轴值进行比较,如果value>arr[mid],则说明你需要查找的数在中轴值的右边,需要对右递归查找;如果value,则说明你需要查找的数在中轴值的左边,因此需要向左递归查找;
3、如果value恰好等于arr[mid],则直接返回;
4、结束递归的情况:①找到目标value,②递归完整个数组仍然没有找到目标value,也结束递归,也就是left > right的时候退出。

二分查找代码实现

package com.xsh.demo.arithmetic;

/**
 * 二分查找实现:二分查找所查找的对象arr必须是有序的
 * @author xiashihua
 */
public class BinarySearch {

    /**
     * @param arr 被查找的目标数组
     * @param left  左边索引
     * @param right 右边索引
     * @param value 需要查找的目标数据
     * @return 如果找到目标数据就返回数据所在的下标,没有找到则返回-1
     */
    public int master(int[] arr,int left,int right, int value){
        if(left > right){
            return -1;
        }
        //计算中间位置索引
        int mid = (left + right) / 2;
        if(value > arr[mid]){
            //向右递归
            return master(arr,mid + 1,right,value);
        }else if(value < arr[mid]){
            //向左递归
            return master(arr,left,mid - 1,value);
        }else {
            return mid;
        }
    }

}

拓展:当数组中有多个相同元素的时候,需要将所有相同元素的索引全部返回。

package com.xsh.demo.arithmetic;

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

/**
 * 二分查找实现:二分查找所查找的对象arr必须是有序的
 * @author xiashihua
 */
public class BinarySearch {

    /**
     * @param arr 被查找的目标数组
     * @param left  左边索引
     * @param right 右边索引
     * @param value 需要查找的目标数据
     * @return 找到arr中所有与value匹配的元素的索引,如果没有则返回空的list
     */
    public List master(int[] arr, int left, int right, int value){
        if(left > right){
            return new ArrayList<>();
        }
        //计算中间位置索引
        int mid = (left + right) / 2;
        if(value > arr[mid]){
            //向右递归
            return master(arr,mid + 1,right,value);
        }else if(value < arr[mid]){
            //向左递归
            return master(arr,left,mid - 1,value);
        }else {
            /**
             * 走到这里说明当前的元素符合了value
             * 接下来就是往当前元素的左边和右边不停的遍历,直到两端的尽头或者元素与当前元素不同为止
             */
            List list = new ArrayList<>();
            int temp = mid - 1;
            //往左遍历
            while (true){
                if(temp < 0 || arr[temp] != arr[mid] ){
                    break;
                }
                list.add(temp);
                temp --;
            }
            //将mid添加到list中
            list.add(mid);
            //往右遍历
            temp = mid;
            while (true){
                if(temp > arr.length - 1 || arr[temp] != arr[mid]){
                    break;
                }
                list.add(temp);
                temp ++;
            }
            return list;
        }
    }

}

插值查找法

插值查找算法类似于二分查找法,不同的是,二分查找法总是选择数组的正中间元素进行二分,而插值查找可以根据数组自适应找到合适的mid进行二分。
例如之前二分查找寻找mid的公式为:(left + right)/2;而插值查找寻找mid的公式为:left + (right - left) * (value - arr[left]) / (arr[right] - arr[left])
插值查找可以当作是二分查找法的一种优化,因为当目标的数组元素很多,并且查找的目标处于数组的首尾的时候,可能导致算法进行多次的二分才能找到结果,而插值查找就可以避免这种情况。当数据量较大,且关键字分布比较均匀的时候,采用插值查找速度较快,但是当数组元素关键字分布不均匀的情况,插值查找不一定比二分查找快。

插值查找实现

package com.xsh.demo.arithmetic;

/**
 * 插值查找算法
 *
 * @author xiashihua
 */
public class InsertValueSearch {

    /**
     * 插值查找算法也要求查找的目标数组是有序的
     *
     * @param arr   被查找的目标数组
     * @param left  数组的起始索引
     * @param right 数组的结束索引
     * @param value 需要查找的目标元素
     * @return 在数组中目标元素所在位置的下标,如果没有返回-1
     */
    public int master(int[] arr, int left, int right, int value) {
        if (left > right || value < arr[0] || value > arr[arr.length - 1]) {
            return -1;
        }
        //求出mid
        int mid = left + (right - left) * (value - arr[left]) / (arr[right] - arr[left]);
        int midValue = arr[mid];
        if(value > midValue){
            //往右遍历
            return master(arr,mid + 1,right,value);
        }else if(value < midValue){
            //往左遍历
            return master(arr,0,mid - 1,value);
        }else{
            return mid;
        }
    }

}

哈希表

哈希表也叫做散列表,是根据关键码值而进行访问的数据结构。也就是说,它通过把关键码值映射到表中的一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

哈希表内存结构示意图

如图所示,hash表就是一个数组,数组的元素是一条条的链表。当有元素存放的时候散列函数会通过对元素关键码值进行计算,得到散列值,散列值决定元素放在哪一条链表之上。查询的时候同样,散列函数可以直接将你指向目标元素所存在的链表,然后直接查询链表就可以,数组中有多少条链表,就相当于将查找速度减少了多少倍。

哈希表代码实现
首先是构成链表的节点元素:

package com.xsh.demo.pojo;

/**
 * 表示雇员信息,哈希表实现使用
 * @author xiashihua
 */
public class Emp {
    private Integer id;
    private String name;
    private Emp next;

    public Emp(Integer id, String name) {
        this.id = id;
        this.name = name;
    }

    public Emp getNext() {
        return next;
    }

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

    public Integer getId() {
        return id;
    }

    public void setId(Integer id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

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

然后是链表的主要代码:

package com.xsh.demo.datastructure;

import com.xsh.demo.pojo.Emp;

/**
 * 节点为Emp的链表,表示哈希表中的每一个元素
 *
 * @author xiashihua
 */
public class EmpLinkedList {
    /**
     * 头指针,直接指向第一个Emp
     */
    private Emp head;

    /**
     * 添加元素到链表上,根据元素的id进行添加,默认元素的id是按序自增的,直接添加到链表的尾部
     *
     * @param emp
     */
    public void add(Emp emp) {
        //如果head为空,则直接将head指向需要添加的元素
        if (head == null) {
            head = emp;
            return;
        }
        //创建临时变量
        Emp temp = head;
        while (true) {
            if (temp.getNext() == null) {
                temp.setNext(emp);
                break;
            }
            temp = temp.getNext();
        }
    }

    /**
     * 根据id删除链表数据
     *
     * @param id
     */
    public boolean delete(int id) {
        boolean flag = false;
        if (head == null) {
            return flag;
        }
        //创建临时变量
        Emp temp = head;
        while (true) {
            if (temp == null) {
                break;
            }

            if (temp.getId() == id) {
                Emp cur = temp.getNext();
                if (cur != null) {
                    temp.setNext(cur.getNext());
                    temp.setId(cur.getId());
                    temp.setName(cur.getName());
                } else {
                    Emp temp2 = head;
                    if (temp2.getNext() == null) {
                        head = null;
                        flag = true;
                        break;
                    }
                    while (true) {
                        if (temp2.getNext().getNext() == null) {
                            temp2.setNext(null);
                            break;
                        }
                        temp2 = temp2.getNext();
                    }
                }
                flag = true;
                break;
            }

            temp = temp.getNext();
        }
        return flag;
    }

    /**
     * 根据id修改name
     *
     * @param emp
     * @return
     */
    public boolean update(Emp emp) {
        boolean flag = false;
        if (head == null) {
            return flag;
        }
        //创建临时变量
        Emp temp = head;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.getId().equals(emp.getId())) {
                temp.setName(emp.getName());
                flag = true;
                break;
            }
            temp = temp.getNext();
        }
        return flag;
    }

    /**
     * 打印链表节点信息
     */
    public void show(int no) {
        if (head == null) {
            System.out.println("第" + (no + 1) + "条链表数据为空");
            return;
        }
        //创建临时变量
        Emp temp = head;
        while (true) {
            System.out.print(" => id:" + temp.getId() + ",name:" + temp.getName());
            if (temp.getNext() == null) {
                break;
            }
            temp = temp.getNext();
        }
        System.out.println();
    }
}

最后是hashTable的主要实现:

package com.xsh.demo.datastructure;

import com.xsh.demo.pojo.Emp;

/**
 * 哈希表实现
 * @author xiashihua
 */
public class HashTable {
    private EmpLinkedList[] empLinkedListArray;
    private int size;

    //构造器初始化数组
    public HashTable(int size) {
        this.size = size;
        empLinkedListArray = new EmpLinkedList[size];
        for (int i = 0; i < empLinkedListArray.length; i++) {
            empLinkedListArray[i] = new EmpLinkedList();
        }
    }

    //添加emp信息
    public void add(Emp emp){
        //通过散列算法获知该emp应该放在哪一条链表上
        int fun = hashFun(emp.getId());
        empLinkedListArray[fun].add(emp);
    }

    //删除emp信息
    public boolean delete(int id){
        int fun = hashFun(id);
        return empLinkedListArray[fun].delete(id);
    }

    //修改emp信息
    public boolean update(Emp emp){
        int fun = hashFun(emp.getId());
        return empLinkedListArray[fun].update(emp);
    }

    //展示hashTable信息
    public void show(){
        for (int i = 0; i < empLinkedListArray.length; i++) {
            empLinkedListArray[i].show(i);
        }
    }

    //简单的散列算法
    public int hashFun(int id){
        return id % size;
    }
}

上述代码实现了哈希表的基本crud,可以使用下方测试代码进行测试:

package com.xsh.demo.test;

import com.xsh.demo.datastructure.HashTable;
import com.xsh.demo.pojo.Emp;
import org.junit.Test;

import java.util.Scanner;

/**
 * HashTable测试
 *
 * @author xiashihua
 */
public class HashTableTest {

    @Test
    public void test() {
        System.out.println("===========欢迎测试自定义hashTable===========");
        HashTable hashTable = new HashTable(5);
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("add:   添加数据");
            System.out.println("delete:删除数据");
            System.out.println("update:修改数据");
            System.out.println("show:  展示数据");
            System.out.println("exit:  退出测试");
            String key = scanner.next();
            switch (key) {
                case ("add"):
                    System.out.println("请输入员工编号:");
                    int id = scanner.nextInt();
                    System.out.println("请输入员工名称:");
                    String name = scanner.next();
                    Emp emp = new Emp(id, name);
                    hashTable.add(emp);
                    break;
                case ("show"):
                    hashTable.show();
                    break;
                case ("delete"):
                    System.out.println("请输入要删除的员工编号:");
                    int deleteId = scanner.nextInt();
                    if(hashTable.delete(deleteId)){
                        System.out.println("删除成功!");
                    }else{
                        System.out.println("删除失败!");
                    }
                    break;
                case ("update"):
                    System.out.println("请输入要修改的员工编号:");
                    int updateId = scanner.nextInt();
                    System.out.println("请输入要修改的员工名称:");
                    String updateName = scanner.next();
                    Emp updateEmp = new Emp(updateId, updateName);
                    if(hashTable.update(updateEmp)){
                        System.out.println("修改成功!");
                    }else{
                        System.out.println("修改失败!");
                    }
                    break;
                case ("exit"):
                    System.exit(0);
                    break;
                default:
                    break;
            }
        }
    }
}

二叉树

为什么会需要二叉树这样的数据结构?
在了解二叉树之前,我们需要回顾之前的内容,比对一下关于数组和链表存储数据的优劣点:
1、数组存储方式的分析
优点:通过下标访问元素,速度快。对于有序数组,还可以使用二分查找来提高检索效率。
缺点:如果要检索某个确定的值或者插入删除数组的元素,会导致数组元素的整体移动甚至扩容等操作,效率较低。
2、链表存储方式的分析
优点:相比于数组,链表在对存储元素的增删上有很大提升。
缺点:在检索数据的时候效率较低,无论目标元素处于链表的哪个位置,都需要从链表的头部开始遍历。

而对于以上问题,树的存储方式就能够有效提升数据存储、读取的效率,比如利用二叉排序树,既可以保证数据的检索速度,同时也可以保证数据的插入、删除、修改的效率。

关于二叉树的遍历
二叉树的遍历分为前序、中序、后序遍历三种:
前序遍历:先输出父节点,再遍历左子树和右子树;
中序遍历:先遍历左子树,再输出父节点,再遍历右子树;
后序遍历:先遍历左子树,再遍历右子树,最后输出父节点。

看父节点的输出顺序,就可以确定是前序、中序还是后序遍历。

前序、中序、后序遍历实现

关于二叉树的遍历实现,首先是关于二叉树的节点,因为节点是够成二叉树本身的元素,所以其中包含真正的遍历的方法。

package com.xsh.demo.pojo;

/**
 * 二叉树节点
 * @author xiashihua
 */
public class TreeNode {
    private int id;
    private String name;
    /**
     * 左节点
     */
    private TreeNode left;
    /**
     * 右节点
     */
    private TreeNode right;

    /**
     * 前序遍历方法
     */
    public void preTraverse(){
        //先输出父节点
        System.out.println(this);
        //向左遍历输出左子树
        if(this.left != null){
            this.left.preTraverse();
        }
        //向右遍历输出右子树
        if(this.right != null){
            this.right.preTraverse();
        }
    }

    /**
     * 中序遍历方法
     */
    public void midTraverse(){
        //先遍历左子树
        if(this.left != null){
            this.left.midTraverse();
        }
        //输出父节点
        System.out.println(this);
        //遍历右子树
        if(this.right != null){
            this.right.midTraverse();
        }
    }

    /**
     * 后序遍历方法
     */
    public void alterTraverse(){
        //遍历左子树
        if(this.left != null){
            this.left.alterTraverse();
        }
        //遍历右子树
        if(this.right != null){
            this.right.alterTraverse();
        }
        //输出父节点
        System.out.println(this);
    }

    public TreeNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

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

    public TreeNode getLeft() {
        return left;
    }

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

    public TreeNode getRight() {
        return right;
    }

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

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

然后就是二叉树本身,想要使用节点够成二叉树,则最起码需要一个二叉树的根节点,然后根据根节点的遍历方法完成遍历。

package com.xsh.demo.datastructure;

import com.xsh.demo.pojo.TreeNode;

/**
 * 二叉树实现
 * @author xiashihua
 */
public class BinaryTree {
    /**
     * 根节点
     */
    private TreeNode root;

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

    /**
     * 前序遍历
     */
    public void preTraverse(){
        root.preTraverse();
    }

    /**
     * 中序遍历
     */
    public void midTraverse(){
        root.midTraverse();
    }

    /**
     * 后序遍历
     */
    public void alterTraverse(){
        root.alterTraverse();
    }
}

如此,我们就有了二叉树的遍历方法以及根节点,但是还没有学习如何将节点按照规则添加到根节点上,在次为了展示遍历的效果,先暂且在单元测试中使用手动绑定节点的方式够成二叉树。

package com.xsh.demo.test;

import com.xsh.demo.datastructure.BinaryTree;
import com.xsh.demo.pojo.TreeNode;
import org.junit.Test;

/**
 * 二叉树测试
 * @author xiashihua
 */
public class BinaryTreeTest {

    /**
     * 二叉树遍历测试
     */
    @Test
    public void test(){
        //创建节点
        TreeNode zhangsan = new TreeNode(1, "zhangsan");
        TreeNode lisi = new TreeNode(2, "lisi");
        TreeNode wangwu = new TreeNode(3, "wangwu");
        TreeNode zhaoliu = new TreeNode(4, "zhaoliu");

        BinaryTree binaryTree = new BinaryTree();
        binaryTree.setRoot(zhangsan);
        zhangsan.setLeft(lisi);
        zhangsan.setRight(wangwu);
        wangwu.setRight(zhaoliu);

        System.out.println("前序遍历");
        binaryTree.preTraverse();

        System.out.println("中序遍历");
        binaryTree.midTraverse();

        System.out.println("后序遍历");
        binaryTree.alterTraverse();
    }
}

前序、中序、后序查找实现

在之前代码的基础上实现前序、中序、后序查找,按照编号id查找二叉树上对应的节点信息。
首先和遍历算法一样,主要的核心代码是在TreeNode节点上完成,然后由二叉树BinaryTree调用实现。
TreeNode代码

    /**
     * 使用前序遍历根据id查找指定节点
     * @param id
     */
    public TreeNode preSearch(int id){
        if(this.id == id){
            return this;
        }
        //创建临时变量
        TreeNode temp = null;
        //遍历左树
        if(this.left != null){
            temp =  this.left.preSearch(id);
        }
        if(temp != null){
            return temp;
        }
        //temp为空,说明没有在左子树上找到目标,接下来遍历右子树
        if(this.right != null){
            temp = this.right.preSearch(id);
        }
        return temp;
    }

    /**
     * 使用中序遍历根据id查找指定节点
     * @param id
     * @return
     */
    public TreeNode midSearch(int id){
        //创建临时变量
        TreeNode temp = null;
        //遍历左子树
        if(this.left != null){
            temp = this.left.midSearch(id);
        }
        if(temp != null){
            return temp;
        }
        //遍历父节点
        if(this.id == id){
            return this;
        }
        //遍历右子树
        if(this.right != null){
            temp  = this.right.midSearch(id);
        }
        return temp;
    }

    /**
     * 使用后序遍历根据id查找指定节点
     * @param id
     * @return
     */
    public TreeNode alterSearch(int id){
        //创建临时变量
        TreeNode temp = null;
        //遍历左子树
        if(this.left != null){
            temp = this.left.alterSearch(id);
        }
        if(temp != null){
            return temp;
        }
        //遍历右子树
        if(this.right != null){
            temp = this.right.alterSearch(id);
        }
        if(temp != null){
            return  temp;
        }
        if(this.id == id){
            return this;
        }
        return temp;
    }

BinaryTree代码

    /**
     * 前序查找
     * @param id
     * @return
     */
    public TreeNode preSearch(int id){
        if(root != null){
            return root.preSearch(id);
        }else{
            return root;
        }
    }

    /**
     * 中序查找
     * @param id
     * @return
     */
    public TreeNode midSearch(int id){
        if(root != null){
            return root.midSearch(id);
        }else{
            return root;
        }
    }

    /**
     * 后序查找
     * @param id
     * @return
     */
    public TreeNode alterSearch(int id){
        if(root != null){
            return root.alterSearch(id);
        }else{
            return root;
        }
    }

删除二叉树节点

TreeNode代码

    /**
     * 根据id删除节点
     * 如果目标节点是叶子节点,则删除节点,如果目标节点是父节点,则删除父节点以及父节点下的所有子节点
     * @param id
     */
    public void delNode(int id){
        //判断当前节点的左子节点是否为空,并且是否为目标节点
        if(this.left != null && this.left.id == id){
            this.left = null;
            return;
        }
        //怕段当前节点的右子节点是否为空,并且是否为目标节点
        if(this.right != null && this.right.id == id){
            this.right = null;
            return;
        }
        //当前节点的左子节点和右子节点皆不符合目标或者为空,则往左或往右递归
        if(this.left != null){
            this.left.delNode(id);
        }
        if(this.right != null){
            this.right.delNode(id);
        }
    }

BinaryTree代码

    /**
     * 根据id删除节点
     * @param id
     */
    public void delNode(int id){
        if(root != null){
            if(root.getId() == id){
                root = null;
            }else{
                root.delNode(id);
            }
        }else{
            System.out.println("该二叉树为空树,无法执行删除操作!");
        }
    }

顺序存储二叉树

顺序存储二叉树的意思是将顺序存储的数据结构数组按照二叉树来操作,即对于一个顺序存储的数组,也可以同样前序中序后序遍历的方式进行遍历。
在顺序存储二叉树中,对于二叉树节点与索引之间的关系,会保持如下规则:
1、下标为index的节点对应的左子节点为:2*n+1
2、下标为index的节点对应的右子节点为:2*n+2
3、下标为index的节点对应的父节点为:(n-1)/2

顺序存储二叉树代码实现

package com.xsh.demo.datastructure;

/**
 * 顺序存储二叉树
 *
 * @author xiashihua
 */
public class ArrayBinaryTree {
    private int[] arr;

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

    /**
     * 前序遍历数组,index表示数组元素下标,可以使用公式来通过下标计算出二叉树左右子节点以及父节点所在的下标
     *
     * @param index
     */
    public void preTraverse(int index) {
        if (arr == null || arr.length == 0) {
            System.out.println("数组为空!");
            return;
        }
        System.out.print(arr[index] + "   ");
        if ((2 * index + 1) < arr.length) {
            preTraverse((2 * index + 1));
        }
        if ((2 * index + 2) < arr.length) {
            preTraverse(2 * index + 2);
        }
    }

    /**
     * 中序遍历
     *
     * @param index
     */
    public void midTraverse(int index) {
        if (arr == null || arr.length == 0) {
            System.out.println("数组为空!");
            return;
        }
        if ((2 * index + 1) < arr.length) {
            midTraverse((2 * index + 1));
        }
        System.out.print(arr[index] + "   ");
        if ((2 * index + 2) < arr.length) {
            midTraverse((2 * index + 2));
        }
    }

    /**
     * 后序遍历
     *
     * @param index
     */
    public void alterTraverse(int index) {
        if (arr == null || arr.length == 0) {
            System.out.println("数组为空!");
            return;
        }
        if ((2 * index + 1) < arr.length) {
            alterTraverse((2 * index + 1));
        }
        if ((2 * index + 2) < arr.length) {
            alterTraverse((2 * index + 2));
        }
        System.out.print(arr[index] + "   ");
    }
}

线索化二叉树


如上图所示,是一个完整的二叉树,由图可以看到二叉树节点的指针是未完全使用到的,例如节点数值为6、8、10、14的节点指针都没有完全使用。所谓线索化二叉树就是想通过某种规则,将一个二叉树中空置的指针使用起来。

线索化二叉树基本介绍
1、在一个有n个节点的二叉树中,通常含有n+1个闲置的空指针域。而线索化二叉树就是想将这些空指针域利用起来,利用闲置的空指针域,存放指向该节点在某种遍历次序下的前驱节点和后继节点的指针,这种附加的指向被称之为现索;
2、这种加上了线索的链表称之为现索链表,相应的二叉树称之为线索二叉树。根据线索性质的不同,线索二叉树可分为前序线索二叉树、中序线索二叉树和后序现索二叉树三种;
3、一个节点的前指针域指向的节点,称之为前驱节点;
4、一个节点的后指针域指向的节点,称之为后继节点。

关于线索化二叉树的思考
想要将一个二叉树变成线索化二叉树,需要经过不同的线索方法完成,添加线索的方式分为前中后序三种,由此也产生了三种线索二叉树。而产生线索二叉树之后原来通过递归来遍历二叉树的方式就行不通了,需要额外的通过线索来进行遍历,通过线索遍历以及将二叉树线索化的好处是遍历不再需要通过递归的形式,可以直接通过线索遍历二叉树,提高了效率。

编写程序实现中序线索二叉树

首先是关于二叉树节点类的改造,在此实现中在二叉树节点的基础上进行改造。
CueTreeNode代码展示

package com.xsh.demo.pojo;

/**
 * 线索化二叉树节点
 * @author xiashihua
 */
public class CueTreeNode {
    private int id;
    private String name;
    private CueTreeNode left;
    private CueTreeNode right;

    /**
     * 该节点指向当前节点的父节点,供后序线索化二叉树遍历使用
     */
    private CueTreeNode parent;

    /**
     * leftType和rightType的作用是用于区分是否创建了线索
     * 如果type取值为0,则表示连接的是子树或者未使用
     * 如果type取值为1,则表示连接的是前驱节点或后继节点
     */
    private int leftType;
    private int rightType;

    /**
     * 前序遍历方法
     */
    public void preTraverse(){
        //先输出父节点
        System.out.println(this);
        //向左遍历输出左子树
        if(this.left != null){
            this.left.preTraverse();
        }
        //向右遍历输出右子树
        if(this.right != null){
            this.right.preTraverse();
        }
    }

    /**
     * 中序遍历方法
     */
    public void midTraverse(){
        //先遍历左子树
        if(this.left != null){
            this.left.midTraverse();
        }
        //输出父节点
        System.out.println(this);
        //遍历右子树
        if(this.right != null){
            this.right.midTraverse();
        }
    }

    /**
     * 后序遍历方法
     */
    public void alterTraverse(){
        //遍历左子树
        if(this.left != null){
            this.left.alterTraverse();
        }
        //遍历右子树
        if(this.right != null){
            this.right.alterTraverse();
        }
        //输出父节点
        System.out.println(this);
    }

    /**
     * 使用前序遍历根据id查找指定节点
     * @param id
     */
    public CueTreeNode preSearch(int id){
        if(this.id == id){
            return this;
        }
        //创建临时变量
        CueTreeNode temp = null;
        //遍历左树
        if(this.left != null){
            temp =  this.left.preSearch(id);
        }
        if(temp != null){
            return temp;
        }
        //temp为空,说明没有在左子树上找到目标,接下来遍历右子树
        if(this.right != null){
            temp = this.right.preSearch(id);
        }
        return temp;
    }

    /**
     * 使用中序遍历根据id查找指定节点
     * @param id
     * @return
     */
    public CueTreeNode midSearch(int id){
        //创建临时变量
        CueTreeNode temp = null;
        //遍历左子树
        if(this.left != null){
            temp = this.left.midSearch(id);
        }
        if(temp != null){
            return temp;
        }
        //遍历父节点
        if(this.id == id){
            return this;
        }
        //遍历右子树
        if(this.right != null){
            temp  = this.right.midSearch(id);
        }
        return temp;
    }

    /**
     * 使用后序遍历根据id查找指定节点
     * @param id
     * @return
     */
    public CueTreeNode alterSearch(int id){
        //创建临时变量
        CueTreeNode temp = null;
        //遍历左子树
        if(this.left != null){
            temp = this.left.alterSearch(id);
        }
        if(temp != null){
            return temp;
        }
        //遍历右子树
        if(this.right != null){
            temp = this.right.alterSearch(id);
        }
        if(temp != null){
            return  temp;
        }
        if(this.id == id){
            return this;
        }
        return temp;
    }

    /**
     * 根据id删除节点
     * 如果目标节点是叶子节点,则删除节点,如果目标节点是父节点,则删除父节点以及父节点下的所有子节点
     * @param id
     */
    public void delNode(int id){
        //判断当前节点的左子节点是否为空,并且是否为目标节点
        if(this.left != null && this.left.id == id){
            this.left = null;
            return;
        }
        //怕段当前节点的右子节点是否为空,并且是否为目标节点
        if(this.right != null && this.right.id == id){
            this.right = null;
            return;
        }
        //当前节点的左子节点和右子节点皆不符合目标或者为空,则往左或往右递归
        if(this.left != null){
            this.left.delNode(id);
        }
        if(this.right != null){
            this.right.delNode(id);
        }
    }

    public CueTreeNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

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

    public CueTreeNode getLeft() {
        return left;
    }

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

    public CueTreeNode getRight() {
        return right;
    }

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

    public CueTreeNode getParent() {
        return parent;
    }

    public void setParent(CueTreeNode parent) {
        this.parent = parent;
    }

    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;
    }

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

CueBinaryTree代码展示
代码中一共实现了前中后序三种线索二叉树,其中后序线索二叉树遍历最为复杂。后序遍历的顺序是左->右->中,面临多层的树结构的时候,我们最开始输出最底层的左子节点以及右子节点,然后输出他们的父节点,此时需要判断该父节点是否属于根节点,因为当该父节点不属于根节点的时候,意味着它本身也属于左子树的一部分,不能直接输出当前父节点的父节点,还需要遍历右子树的内容。但是由于当前的父节点所有指针都已经被使用,所以无法通过线索直接找到下一个遍历目标。此时就需要增加Parent字段,通过记录该父节点的父节点,来找到该父节点的同级右子树内容来进行遍历输出。

package com.xsh.demo.datastructure;

import com.xsh.demo.pojo.CueTreeNode;

/**
 * 线索二叉树实现
 *
 * @author xiashihua
 */
public class CueBinaryTree {
    /**
     * 根节点
     */
    private CueTreeNode root;

    /**
     * pre节点用于记录线索化时当前节点的上一个节点
     */
    private CueTreeNode pre;

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

    /**
     * 遍历前序线索化二叉树
     */
    public void CuePreTraverse() {

        CueTreeNode node = root;

        while (node != null) {
            while (node.getLeftType() == 0) {
                System.out.println(node);
                node = node.getLeft();
            }
            System.out.println(node);
            node = node.getRight();
        }

    }

    /**
     * 遍历后序线索化二叉树
     */
    public void CueAlterTraverse(){
        CueTreeNode node = root;

        /**
         * 先找到根节点左子树的最左节点
         */
        while (node != null && node.getLeftType() == 0){
            node = node.getLeft();
        }

        while (node != null){

            if(node.getRightType() == 1){
                //当前节点的右指针是线索
                System.out.println(node);
                pre = node;
                node = node.getRight();
            }else{

                if(node.getRight() == pre){
                    //上一个处理的节点为当前节点的右节点
                    System.out.println(node);
                    if(node == root){
                        return;
                    }
                    pre = node;
                    node = node.getParent();
                }else{
                    //进入parent的右子树,找到右子树的最左节点
                    node = node.getRight();
                    while (node != null && node.getLeftType() == 0){
                        node = node.getLeft();
                    }
                }
            }
        }
    }

    /**
     * 遍历中序线索化二叉树
     */
    public void CueMidTraverse() {
        CueTreeNode node = root;

        while (node != null) {

            while (node.getLeftType() == 0) {
                node = node.getLeft();
            }
            System.out.println(node);
            while (node.getRightType() == 1) {
                node = node.getRight();
                System.out.println(node);
            }

            node = node.getRight();
        }
    }

    /**
     * 中序线索化二叉树
     *
     * @param node
     */
    public void midCueNodes(CueTreeNode node) {

        if (node == null) {
            return;
        }

        //线索化左子树
        midCueNodes(node.getLeft());
        //线索化当前节点
        //线索化左指针
        if (node.getLeft() == null) {
            node.setLeft(pre);
            node.setLeftType(1);
        }
        //线索化右指针
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre = node;
        //线索化右子树
        midCueNodes(node.getRight());
    }

    /**
     * 前序线索化二叉树
     *
     * @param node
     */
    public void preCueNodes(CueTreeNode node) {

        if (node == null) {
            return;
        }

        //线索化当前节点
        if (node.getLeft() == null) {
            node.setLeft(pre);
            node.setLeftType(1);
        }
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre = node;
        //线索化左子树
        if (node.getLeftType() == 0) {
            preCueNodes(node.getLeft());
        }
        //线索化右子树
        if (node.getRightType() == 0) {
            preCueNodes(node.getRight());
        }
    }

    /**
     * 后序线索化二叉树
     * @param node
     */
    public void alterCueNodes(CueTreeNode node){
        if(node == null){
            return;
        }

        //线索化左子树
        if(node.getLeftType() == 0){
            alterCueNodes(node.getLeft());
        }
        //线索化右子树
        if(node.getRightType() == 0){
            alterCueNodes(node.getRight());
        }
        //线索化当前节点
        if(node.getLeft() == null){
            node.setLeft(pre);
            node.setLeftType(1);
        }
        if(pre != null && pre.getRight() == null){
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre = node;
    }


    /**
     * 前序遍历
     */
    public void preTraverse() {
        root.preTraverse();
    }

    /**
     * 中序遍历
     */
    public void midTraverse() {
        root.midTraverse();
    }

    /**
     * 后序遍历
     */
    public void alterTraverse() {
        root.alterTraverse();
    }

    /**
     * 前序查找
     *
     * @param id
     * @return
     */
    public CueTreeNode preSearch(int id) {
        if (root != null) {
            return root.preSearch(id);
        } else {
            return root;
        }
    }

    /**
     * 中序查找
     *
     * @param id
     * @return
     */
    public CueTreeNode midSearch(int id) {
        if (root != null) {
            return root.midSearch(id);
        } else {
            return root;
        }
    }

    /**
     * 后序查找
     *
     * @param id
     * @return
     */
    public CueTreeNode alterSearch(int id) {
        if (root != null) {
            return root.alterSearch(id);
        } else {
            return root;
        }
    }


    /**
     * 根据id删除节点
     *
     * @param id
     */
    public void delNode(int id) {
        if (root != null) {
            if (root.getId() == id) {
                root = null;
            } else {
                root.delNode(id);
            }
        } else {
            System.out.println("该二叉树为空树,无法执行删除操作!");
        }
    }
}

堆排序

堆排序是一种利用二叉树这种数据结构完成排序的排序算法,所以在放在学习了基本的二叉树之后进行记录。

堆排序的基本介绍
1、堆排序是一种选择排序,他的最好、最坏及平均时间复杂度都为O(nlogn),是一种不稳定排序;
2、堆是具有以下性质的完全二叉树:当每个节点的值都大于或者等于左右子节点的值,称之为大顶堆。每个节点的值都小于或者等于左右子节点的值,称之为小顶堆。注意在此没有强调节点左右子节点的大小关系,只是强调父节点与左右子节点的关系。

如图所示,展示的是大顶堆转换为顺序存储二叉树之后的结构示意,我们可以发现,转换为数组之后,大顶堆的数据之间关系满足如下公式:arr[i]>=arr[2*i+1] && arr[i]>=arr[2*i+2]。同理,小顶堆数据转换为顺序存储二叉树之后也满足如下公式:arr[i]<=arr[2*i+1] && arr[i]<=arr[2*i+2]

堆排序的基本思路
1、将无序序列构建成一个堆,根据排序目标是升序还是降序来决定构建大顶堆还是小顶堆(一般升序构建大顶堆,降序构建小顶堆);
2、将堆顶元素与末尾元素交换,将最大的元素“沉”到数组末端(大顶堆结构堆顶元素即为最大元素);
3、重新调整结构,在除去沉到数组末端的最大元素之后的结构恢复为一个新的大顶堆,然后沉入新的堆顶元素,重复这个操作,直至整个序列有序。

堆排序代码实现

package com.xsh.demo.arithmetic;

/**
 * 堆排序实现
 *
 * @author xiashihua
 */
public class HeapSort {

    public void master(int[] arr) {
        //创建临时变量
        int temp = 0;

        //通过循环将arr休整为大顶堆结构
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        //下沉堆顶元素并重复操作
        for (int i = arr.length - 1; i >= 0; i--) {
            temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, i);
        }
    }

    /**
     * 将arr休整成为大顶堆的方法
     * i:表示父节点的坐标,方法负责将该父节点元素与下面的左右子节点元素做对比,替换出最大的数值
     * length:表示二叉树节点个数,因为当一次大顶堆构成之后,堆排序会将顶堆元素也就是最大元素进行下沉处理,所以下次修整大顶堆的二叉树节点肯定是-1的
     *
     * @param arr    目标arr
     * @param i      父节点坐标
     * @param length 二叉树节点个数
     */
    public void adjustHeap(int arr[], int i, int length) {

        //创建临时变量保存父节点数值
        int temp = arr[i];

        /**
         * 开始休整大顶堆,k表示i的左子节点下标
         */
        for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {
            /**
             * k+1表示与左子节点平级的右子节点,进入该分支表示父节点坐标为i的右子节点数值比左子节点大
             */
            if (k + 1 < length && arr[k] < arr[k + 1]) {
                //让k指向右子节点
                k++;
            }
            /**
             * 如果k所在的子节点比父节点数值还大,则将子节点数值赋值给父节点,并调整i=k继续循环往下寻找是否有更大的子节点
             */
            if (arr[k] > temp) {
                arr[i] = arr[k];
                i = k;
            } else {
                break;
            }
        }
        //循环结束之后,temp所在的子树最大值已经被找到,此时i指向的是temp应在的位置(注意i=k的操作)
        arr[i] = temp;

    }

}

赫夫曼树

给定n个权值作为n个叶子节点,构造一棵二叉树,若该树的带权路径长度(wpl)达到最小,称这样的二叉树为最优二叉树,即赫夫曼树(Huffman Tree)。
赫夫曼树是带权路径最短的树,权值较大的节点离根节点较近。

基本概念解析
1、路径和路径长度:在一棵树中,从一个节点往下可以到达的孩子或者孙子节点之间的通路,被称之为路径。通路中分支的数目被称之为路径长度。若规定根节点的层数为1,则从根节点到第L层节点的路径长度为L-1
2、节点的权及带权路径长度:若将树中节点赋予一个有着某种含义的数值,那么这个数值就称之为该节点的权。节点的带权路径长度为:从根节点到该节点的路径长度与该节点的权的乘机。
3、树的带权路径长度:树的带权路径长度即为所有叶子节点的带权路径长度长度之和,记为wpl(weighted path length),权值越大的节点离根节点越近的二叉树才是最优二叉树。
如下图所示,叶子节点构建的方式不同,树的带权路径长度也不同:

构建赫夫曼树的思路解析
1、将目标数组进行排序,排序之后的数组每个节点都可以看作是一棵最简单的二叉树;
2、取出根节点权值最小的两棵二叉树,组成一棵新的二叉树,新的二叉树的根节点的权值是前面两棵二叉树根节点权值的和;
3、再将这棵新的二叉树以根节点的权值再次排序,重复上述操作,直到数列中所有数值都被处理,则得到一棵赫夫曼树。

暂停进度......2020.10.16