数据结构复习

数据结构复习（JAVA实现）

本文是我复习数据结构整理的资料，使用的语言主要为：Java。

绪论

什么是数据结构

数据结构是相互之间存在一种或多种特定关系的数据元素集合，这种数据元素之间的关系称为结构。数据结构包括：逻辑结构、存储结构、数据运算。

逻辑结构

逻辑结构指的是数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的存储方式没有关系，独立于计算机。（例如，线性表既可以用顺序存储方式的数组实现，也可以用链式存储方式的单链表实现，没有必然关系）

数据的逻辑结构主要有：

• 线性结构（数据元素一对一）：
  • 一般线性表：
    • 顺序表（数组实现）
    • 单链表（链式实现，利用指针）
  • 受限线性表：
    • 栈（后进先出）
    • 队列（先进先出）
    • 串（字符串匹配，BF算法和KMP算法）
  • 线性表推广：
    • 数组
    • 广义表
• 非线性结构：
  • 集合（数据元素除了同属一个集合外，没有任何联系）
  • 树形结构：（数据元素一对多，所有节点入度为0）
    • 二叉树（一个节点只有两个孩子节点）
    • 一般树（一个节点有任意多个孩子节点）
  • 图状结构：（数据元素多对多）
    • 邻接表（链式表示图）
    • 邻接矩阵（数组表示图）

存储结构

• 顺序存储：
  • 把逻辑上相邻的元素存放在物理上相邻的存储单元中，最典型的例子是数组。数据元素之间的关系通过存储单元的邻接关系体现（比如要求当前元素的下一个元素，只需要访问当前存储单元的下一个存储单元即可）
  • 优点：
    • 可以随机存取（例如，OS的逻辑文件中的直接文件，一旦知道存储开始位置，直接通过所求元素的脚标即可访问对应的元素），数据读取和修改较快，时间复杂度为$O(1)$
    • 每个元素只占用最少的存储空间（不需要存放指针，只用占用一个存储单元即可）
  • 缺点：
    • 所需的存储单元必须是连续的（类似于OS中的连续内存分配机制），因此会产生大量的外部碎片（比如，一个数组 int[] arr = new int[100]，需要100个连续的int型，即4个字节的空间，虽然目前的内存中有400字节的空闲空间，但是它们被分割开来了，所以无法使用，这些被割裂开来的小孔即为外部碎片，如果是链式存储的话，可以非连续地存放在这些小孔中）
    • 数据的插入和删除需要挪动之后所有的元素，较慢，时间复杂度为$O(n)$
  • 实例：数组
• 链式存储：
  • 不要求逻辑上相邻的数据元素在物理位置上也相邻。数据元素之间的逻辑关系采用指示元素物理位置的指针来表示。
  • 优点：
    • 非连续存储，因此可以充分利用碎片空间，不会产生碎片现象，空间利用率高
    • 不考虑定位问题，数据的插入和删除直接修改指针即可，较快，时间复杂度为$O(1)$
  • 缺点：
    • 需要在每个元素中额外占用空间存放指针
    • 只能顺序存取，访问和修改数据较慢，时间复杂度为$O(n)$
  • 实例：单链表
• 索引存储：
  • 在存储元素信息时，建立附加的索引表，索引表中的每一项都是索引项，格式为（关键字，地址）。既可以让数据元素以非连续的方式存储，也可以直接存取数据元素。
  • 优点：
    • 检索速度快（直接链式存储，一个100GB的文件要读完100GB才能获取到最后的元素，而100GB的文件，其索引表可能只有100MB，大大减少了需要遍历的数据量）
    • 不会出现碎片现象（非连续存储）
  • 缺点：
    • 附加的索引表需要占用额外的空间（其实就相当于把链式存储每一个元素的指针提出来到一张大表中了）
    • 插入删除数据也要修改索引表，花费时间较长
  • 实例：Mysql数据库索引
• 散列存储：
  • 使用哈希（hash）函数，根据元素的关键字直接计算出该元素的存储地址。
  • 优点：
    • 检索、增加、删除结点的操作都很快。因为可以在$O(1)$的时间复杂度内通过函数计算的方式直接定位到对应元素的物理位置。
  • 缺点：
    • 如果散列函数（哈希函数）不好，可能出现存储元素的冲突（哈希碰撞现象），需要花费时间和空间解决冲突（拉链法、二次探测法等）
  • 实例：hashmap、hashset、hashtable

数据运算

数据运算的定义是针对逻辑结构的，表示运算的功能。

数据运算的实现是针对存储结构的，表示运算的具体步骤。

易错点

• 如何区分逻辑结构和存储结构：
  • 如果一个数据结构，只能被一种存储结构所实现，例如：单链表（链式存储）、顺序表（顺序存储）、哈希表（散列存储）、循环队列（顺序存储），那么必然和存储结构有关。
  • 如果一个数据结构，可以被多种存储结构实现，例如：队列、栈、二叉树，那么就是逻辑结构。
• 逻辑结构独立于存储结构，它是抽象表达的，在设计逻辑结构时不需要考虑存储结构的实现。但设计存储结构时，需要考虑数据的逻辑结构，因为存储结构是逻辑结构在计算机上的映射。
• 链式存储设计中，结点内的存储单元地址（逻辑地址）一定连续。
• 针对两种不同的数据结构，其逻辑结构或物理结构不一定相同：例如，二叉树和二叉排序树，逻辑结构和物理结构可以相同。

算法的概念

定义：算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。

特性：

• 有穷性：算法必须在有穷步之后结束，每一步都必须在有穷时间完成。（死循环的程序不是算法）
• 确定性：算法中每条指令必须有确切的含义，对于相同的输入只能得到相同的输出。
• 可行性：算法中描述的操作可以通过已经实现的基本运算执行有限次实现。
• 输入：一个算法有零个或多个输入。
• 输出：一个算法有一个或多个输出。

目标：

• 正确性。算法能正确地求解目标问题。
• 可读性。算法能够被人们理解。
• 健壮性。针对非法输入，能够有效处理。
• 效率与低存储量需求。良好的时间和空间复杂度。

时间复杂度

• 算法中最深层循环内的语句被重复执行次数的数量级，即为算法的时间复杂度。
• 包括：
  • 最好时间复杂度
  • 最坏时间复杂度
  • 平均时间复杂度
• 一般考虑的时间复杂度都是最坏时间复杂度。

空间复杂度

• 算法需要耗费的存储空间的数量级。
• 算法原地工作的含义是所需要的额外的辅助空间是常数级别的。

时间复杂度和空间复杂度往往不可兼得，需要平衡。

• 以时间换空间：
  • 虚拟内存技术
  • 交换技术
  • 覆盖技术
• 以空间换时间：
  • 动态规划技术
  • Cache技术

时间复杂度和空间复杂度只考虑最大的数量级，且不考虑常数项。

复杂度如何计算

• 时间复杂度计算（单个循环体）
  • 直接关注循环体的执行次数，设为k
• 时间复杂度计算（多个循环体）
  • 两个运算规则：乘法规则，加法规则。

易错点

• 时间复杂度不等于执行次数，它描述的是一个数量级
• 计算时间、空间复杂度时需要在脑子中模拟清楚。
• 时间复杂度指的是：渐进时间复杂度，所以$O(n)$总是优于$O(nlogn)$，不应找特殊值。
• 递归程序的时间复杂度要进行数学推导。

线性表

线性表的定义

线性表示具有相同数据类型的n个数据元素的有限序列（按照这个定义，python中的列表不属于线性表），其中n为表长。当n = 0时，线性表为空表。是一个逻辑结构

线性表的逻辑特性为：

• 唯一的第一个元素称为表头元素
• 唯一的最后一个元素称为表尾元素
• 除最后一个元素外，每个元素只有唯一一个直接后继；除第一个元素外，每个元素只有唯一一个直接前驱

线性表的特点为：

• 表中的元素个数有限（实际上，单链表不受这个限制，可以无限增长，只要内存足够）
• 表中元素具有逻辑上的顺序性，表中元素有其先后次序
• 表中元素都是数据元素，每个元素都是单个元素
• 表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间

常见的线性表实现（存储结构）：

• 顺序表：基于数组
• 单链表：基于指针

线性表的操作

• 初始化：
  • 最大长度
  • 当前长度
  • 存储结构（数组or链表结点）
• 求表长：
  • 返回当前长度
• 按值查找：
  • 根据值返回元素的下标
• 按位查找：
  • 根据下标返回元素的值
• 插入操作：
  • 在指定位置插入元素
• 删除操作：
  • 指定位置删除元素
• 输出操作：
  • 顺序输出所有元素的值
• 判空操作：
  • 线性表是否为空
• 销毁操作：
  • 销毁线性表，释放内存（Java中不需要，JVM会自动GC）
• 清空操作：
  • 让线性表置空，保留其数据结构

我们尝试定义一个接口（Interface）IList，规定一下，线性表（List）的操作。

/*
线性表的接口定义
 */
public interface IList {
    public void clear();    //清空操作
    public boolean isEmpty();    //判空操作
    public int length();    //获取长度操作
    public Object get(int i) throws Exception;    //按位查找
    public void insert(int i,Object x) throws Exception;    //插入操作
    public void remove(int i) throws Exception;    //删除操作
    public int indexOf(Object x);    //按值查找
    public void display();    //输出操作
}

顺序表的实现

顺序表，顾名思义，就是顺序存储结构实现的线性表。按照顺序存储的定义，它的所有数据元素物理存放顺序和逻辑顺序一致。

顺序表的好处也就是顺序存储的好处：

• 随机存取，读取和修改元素方便，$O(1)$
• 存储密度高，每个结点只存放数据元素（单链表还需要存放指针）

顺序表的缺点：

• 存在外部碎片，空间利用率低
• 插入和删除元素需要移动大量元素（但是，实际上进行表尾的插入删除操作，顺序表优于链表）

所以，我们可以知道：顺序表适用于存取频繁而修改较少的场景，也就是数据静态的场景

初始化操作

首先，我们定义一个SqList类，表示SequenceList，顺序表。

由于Java不支持动态数组，只能使用JDK提供的ArrayList类进行实现（实际上，ArrayList也是通过扩容因子，在需要扩容时将原有的数据复制到一个更大的静态数组实现的），所以，我们就不使用C语言的动态声明数组方式了。也就是说，我们需要显式地定义一下顺序表的最大长度。

public class SqList implements IList {    //实现Ilist接口
    private Object[] listElem;    //静态数组，在内存中开辟一块连续的存储空间，用来存放顺序表
    private int curLen;    //顺序表当前长度
    private int maxSize;    //顺序表最大长度

    public SqList(int maxSize) {    //顺序表的构造函数
        curLen=0;    //初始化当前长度为0
        listElem=new Object[maxSize];    //创建指定最大长度maxSize的静态数组，用于存放数据元素
        this.maxSize=maxSize;    //指定顺序表最大长度
    }

插入操作

插入操作需要注意的点：

• 我们的插入位置与顺序表中的数组下标一致，从0开始
• 可以插入的位置从0到curlen，而可以删除的位置只能从0到curlen-1，因为在curlen处插入相当于追加一个新元素
• 后移元素必须从后向前操作，否则还没有访问的元素会被当前元素后移所覆盖

    public void insert(int i,Object x) throws Exception{    //在第i个位置插入元素
        if ((i<0)||(i>curLen)) {    //判断插入位置是否合法，这里需要注意，第curlen个位置插入即为尾插，不需要后移元素
            throw new Exception("插入位置不合法");
        }
        else if(curLen==maxSize) {    //判断是否表满
            throw new Exception("表满");
        }
        else {
            for (int j=curLen;j>i;j--) {    //将最后一个元素到第i个元素全部向后移动一个位置，必须是倒序后移，否则后面的元素会被前面元素后移操作所覆盖
                listElem[j]=listElem[j-1];
            }
            listElem[i]=x;    //在第i个位置插入元素
            curLen+=1;    //当前长度+1
        }
    }

删除操作

删除操作需要注意的点：

• 可以插入的位置从0到curlen，而可以删除的位置只能从0到curlen-1，因为在curlen处插入相当于追加一个新元素，而curlen处不存在元素
• 前移元素必须从前向后操作，否则还没有访问的元素会被当前元素前移所覆盖

    public void remove(int i) throws Exception{    //删除第i个位置的元素
        if ((i<0)||(i>curLen-1)) {    //判断删除位置是否合法，需要注意与插入操作的区别
            throw new Exception("删除位置不合法");
        }
        else {
            for (int j=i;j<curLen-1;j++) {    //将第i+1个元素到最后一个元素前移一个位置，必须是正序前移，防止未访问的元素被覆盖
                listElem[j]=listElem[j+1];
            }
            curLen-=1;    //当前长度减1
        }
    }

按值查找操作

顺序查找即可，线性时间复杂度，时间复杂度为$O(n)$。

    public int indexOf(Object x) {    //查找顺序表对应元素的位置，从value获取key
        for (int i=0;i<curLen;i++) {
            if (listElem[i]==x) {
                return i;
            }
        }
        return -1;
    }

按下标查找操作

直接获取对应下标的数组元素，时间复杂度为$O(1)$。

    public Object get(int i) throws Exception{    //按下标返回对应的元素，从key获取value
        if ((i<0)||(i>curLen-1)) {
            throw new Exception("第"+i+"个元素不存在");
        }
        else {
            return listElem[i];
        }
    }

完整实现代码

/*
顺序表的实现
 */

public class SqList implements IList {    //实现Ilist接口
    private Object[] listElem;    //静态数组，在内存中开辟一块连续的存储空间，用来存放顺序表
    private int curLen;    //当前长度
    private int maxSize;    //最大长度

    public SqList(int maxSize) {    //顺序表的构造函数
        curLen=0;    //初始化当前长度为0
        listElem=new Object[maxSize];    //创建指定最大长度maxSize的静态数组，用于存放数据元素
        this.maxSize=maxSize;    //指定顺序表最大长度
    }

    public void clear() {    //顺序表的清空，直接让当前长度等于0即可
        curLen=0;
    }

    public boolean isEmpty() {    //顺序表是否为空，即当前长度是否为0
        return curLen == 0;
    }

    public int length() {    //返回当前长度
        return curLen;
    }

    public Object get(int i) throws Exception{    //按下标返回对应的元素，从key获取value
        if ((i<0)||(i>curLen-1)) {
            throw new Exception("第"+i+"个元素不存在");
        }
        else {
            return listElem[i];
        }
    }

    public void insert(int i,Object x) throws Exception{    //在第i个位置插入元素
        if ((i<0)||(i>curLen)) {    //判断插入位置是否合法，这里需要注意，第curlen个位置插入即为尾插，不需要后移元素
            throw new Exception("插入位置不合法");
        }
        else if(curLen==maxSize) {    //判断是否表满
            throw new Exception("表满");
        }
        else {
            for (int j=curLen;j>i;j--) {    //将最后一个元素到第i个元素全部向后移动一个位置，必须是倒序后移，否则后面的元素会被前面元素后移操作所覆盖
                listElem[j]=listElem[j-1];
            }
            listElem[i]=x;    //在第i个位置插入元素
            curLen+=1;    //当前长度+1
        }
    }

    public void remove(int i) throws Exception{    //删除第i个位置的元素
        if ((i<0)||(i>curLen-1)) {    //判断删除位置是否合法，需要注意与插入操作的区别
            throw new Exception("删除位置不合法");
        }
        else {
            for (int j=i;j<curLen-1;j++) {    //将第i+1个元素到最后一个元素前移一个位置，必须是正序前移，防止未访问的元素被覆盖
                listElem[j]=listElem[j+1];
            }
            curLen-=1;
        }
    }

    public int indexOf(Object x) {    //查找顺序表对应元素的位置，从value获取key
        for (int i=0;i<curLen;i++) {
            if (listElem[i]==x) {
                return i;
            }
        }
        return -1;
    }

    public void display() {    //打印当前顺序表中的所有元素
        for (int i=0;i<curLen;i++) {
            System.out.print(listElem[i]+" ");
        }
        System.out.println();
    }
}

单链表的实现

顺序表虽然可以随机存取，访问较快，但在中间插入和删除元素需要移动大量的数据元素。为此，我们使用链式存储结构的单链表实现线性表，它不要求逻辑上相邻的元素在物理位置上相邻，通过指针指示元素的逻辑关系，插入和删除操作只需要移动指针即可。

顺序表对于内存的要求较高，需要连续的内存空间，存在外部碎片的现象。而链表虽然不存在外部碎片，但也会浪费存储空间来存放指针域。

单链表结点的定义

首先，我们尝试定义一个单链表结点。一个单链表结点由数据域和指针域两部分构成：

/*
单链表结点
 */
public class Node {
    public Object data;    //数据域
    public Node next;    //指针域，指向下一个数据元素
    public Node() {
        this(null,null);
    }
    public Node(Object x) {
        this(x,null);
    }
    public Node(Object x,Node p) {
        data=x;
        next=p;
    }
}

单链表的头结点

单链表通常以两种形式来标识：

• 直接使用头指针指向第一个数据元素的链表结点
• 创建一个没有数据域的（伪）头结点，让头指针指向该头结点，该头结点的后继指针指向第一个数据元素的链表结点。

使用头结点的好处有：

• 不用区分链表首部的操作和表中其他位置的操作。
• 对于空表和非空表一样处理。

初始化单链表

我们使用带有头结点的方式表示单链表。

/*
单链表类
 */
import java.util.Scanner;
public class LinkList implements IList{
    public Node head;    //头结点

    public LinkList() {    //构造函数，创建空表
        head=new Node();
    }

    public LinkList(int n) throws Exception{    //构造函数，以尾插法建立单链表
        this();
        create(n);
    }

尾插法创建单链表

我们可以用头插法或者尾插法的方式输入元素并初始化单链表，但是头插法所得链表中的数据顺序与输入顺序相反，所以我们这里是用尾插法。

尾插法创建

    public void create(int n) throws Exception{    //尾插法创建单链表
        Scanner in=new Scanner(System.in);
        String x;
        Node p=head;    //表尾指针
        for (int i=1;i<=n;i++) {
            x=in.next();    //读取用户输入的数据元素（假设是字符串）
            p.next=new Node(x);    //插入到链表末尾
            p=p.next;    //移动表尾指针指向新的表尾
        }
    }

单链表按序号查找结点

从第一个结点出发，顺序搜索，时间复杂度$O(n)$。

    public Object get(int i) throws Exception{    //按序号查找结点
        Node p=head.next;
        int j=0;    //序号从0开始
        while ((j<i)&&(p!=null)) {    //一旦找到第i个元素，或者移动到链表之外，跳出循环
            p=p.next;
            j++;
        }
        if(i<0||p==null) {    //序号非法，抛出异常
            throw new Exception("第"+i+"个元素不存在");
        }
        return p.data;
    }

单链表按结点值查找序号

从第一个结点出发，如果当前结点值与目标值相等，则返回当前结点序号。如果不存在目标值的结点，返回-1。

    public int indexOf(Object x) {    //按结点值返回序号
        Node p=head.next;
        int j=0;    //记录当前序号，用于返回
        while (p!=null&&p.data!=x) {    //寻找第一个值等于x的结点
            j+=1;
            p=p.next;
        }
        if (p==null) {    //如果整个链表都找不到对应值的结点，返回-1
            return -1;
        }
        return j;
    }

单链表插入

单链表的插入结点到第 i 个位置需要分为两步：

• 先顺序遍历，定位到第 i - 1个结点（$O(n)$）
• 再在第 i - 1 个结点处进行后插操作（$O(1)$）

    public void insert(int i,Object x) throws Exception{    //第i个位置插入值x
        Node p=head;
        int j=-1;
        while (p!=null&&j<i-1) {    //找到第i-1个结点
            p=p.next;
            j++;
        }
        if (p==null||i<0) {
            throw new Exception("插入位置不合法");
        }
        Node s=new Node(x);    //进行插入
        s.next=p.next;
        p.next=s;
    }

拓展：如果只给定单链表的某个结点p，要求对其进行前插s结点操作，我们依然可以先后插，再将插入结点s的值与结点p的值交换。（这里是逻辑上的插入，只保证了单链表的元素值顺序符合要求，但实际上没有真正插入到前面）

单链表删除

与单链表的插入类似，单链表的删除也是先定位到前驱结点，再执行删除操作。

    public void remove(int i) throws Exception{    //第i个位置删除结点
        Node p=head;
        int j=-1;
        while (p!=null&&j<i-1) {    //找到第i-1个结点
            p=p.next;
            j++;
        }
        if (p==null||i<0) {
            throw new Exception("删除位置不合法");
        }
        p.next=p.next.next;    //进行删除
    }

拓展：如果只给定单链表的某个结点p，要求删除该结点，我们可以先将 p.val 与 p.next.val 交换，再使用常规方法删除下一个结点。

完整单链表实现

/*
单链表类
 */
import java.util.Scanner;
public class LinkList implements IList{
    public Node head;    //头结点

    public LinkList() {    //构造函数，创建空表
        head=new Node();
    }

    public LinkList(int n) throws Exception{    //构造函数，以尾插法建立单链表
        this();
        create(n);
    }

    public void create(int n) throws Exception{    //尾插法创建单链表
        Scanner in=new Scanner(System.in);
        String x;
        Node p=head;
        while (p.next!=null){    //寻找尾结点
            p=p.next;
        }
        for (int i=1;i<=n;i++) {
            x=in.next();    //读取用户输入的数据元素（假设是字符串）
            p.next=new Node(x);    //插入到链表末尾
            p=p.next;
        }
    }
    public void clear() {    //清空链表直接让头结点的后继指针指向空即可，JVM自动回收不再使用的结点
        head.next=null;
    }

    public boolean isEmpty() {    //是否为空表只要看头结点是否有后继结点
        return head.next==null;
    }

    public int length() {    //遍历整个单链表，返回总长度
        Node p=head.next;
        int length=0;
        while (p!=null) {
            length+=1;
            p=p.next;
        }
        return length;
    }

    public Object get(int i) throws Exception{    //按序号查找结点值
        Node p=head.next;
        int j=0;    //序号从0开始
        while ((j<i)&&(p!=null)) {    //一旦找到第i个元素，或者移动到链表之外，跳出循环
            p=p.next;
            j++;
        }
        if(i<0||p==null) {    //序号非法，抛出异常
            throw new Exception("第"+i+"个元素不存在");
        }
        return p.data;
    }

    public void insert(int i,Object x) throws Exception{    //第i个位置插入值x
        Node p=head;
        int j=-1;
        while (p!=null&&j<i-1) {    //找到第i-1个结点
            p=p.next;
            j++;
        }
        if (p==null||i<0) {
            throw new Exception("插入位置不合法");
        }
        Node s=new Node(x);    //进行插入
        s.next=p.next;
        p.next=s;
    }
    public void remove(int i) throws Exception{    //第i个位置删除结点
        Node p=head;
        int j=-1;
        while (p!=null&&j<i-1) {    //找到第i-1个结点
            p=p.next;
            j++;
        }
        if (p==null||i<0) {
            throw new Exception("删除位置不合法");
        }
        p.next=p.next.next;    //进行删除
    }
    public int indexOf(Object x) {    //按结点值返回序号
        Node p=head.next;
        int j=0;    //记录当前序号，用于返回
        while (p!=null&&p.data!=x) {    //寻找第一个值等于x的结点
            j+=1;
            p=p.next;
        }
        if (p==null) {    //如果整个链表都找不到对应值的结点，返回-1
            return -1;
        }
        return j;
    }
    public void display() {
        Node p=head.next;
        while (p!=null) {
            System.out.print(p.data+" ");
            p=p.next;
        }
        System.out.println();
    }
}

双链表的实现

单链表结点的指针域指向后继，导致单链表只能从头结点开始向后访问，如果要访问某个结点的前驱，需要从头开始查找。

为了克服该缺陷，我们引入了双链表，双链表结点的指针域中有两个指针，prior指向双链表结点的前驱结点，而next指针指向后继结点。

/*
双链表结点
 */

public class DuLNode {
    public Object data;
    public DuLNode prior;    //与单链表结点的区别：新增了一个前驱指针
    public DuLNode next;
    public DuLNode() {
        prior=null;
        next=null;
    }
    public DuLNode(Object data) {
        prior=null;
        next=null;
        this.data=data;
    }
}

双链表的插入删除操作

双链表与单链表实现几乎一致，最大的区别在于插入删除操作的不同。双链表需要额外修改prior指针。

    public void insert(int i,Object x) throws Exception{
        DuLNode p=head;
        int j=-1;
        while (p!=null&&j<i-1) {    //我们可以选择在第i-1个结点处尾插，也可以选择在第i个结点处前插，因为是双向链表，所以两种方法没有区别
            p=p.next;
            j++;
        }
        if (p==null||i<0) {
            throw new Exception("插入位置不合法");
        }
        DuLNode s=new DuLNode(x);
        if (i==this.length()) {    //需要分类讨论尾部的情况，因为假如在尾部插入，则不需要修改p.next的prior指针，因为p.next为null
            s.next=p.next;
            s.prior=p;
            p.next=s;
        }
        else {
            s.prior=p;
            s.next=p.next;
            p.next.prior=s;
            p.next=s;
        }
    }

同理，双向链表的删除操作如下：

    public void remove(int i) throws Exception{
        DuLNode p=head;
        int j=-1;
        while (p!=null&&j<i-1) {
            p=p.next;
            j++;
        }
        if (p==null||i<0) {
            throw new Exception("删除位置不合法");
        }
        if (i==this.length()) {
            p.next=p.next.next;
        }
        else {
            p.next=p.next.next;
            p.next.prior=p;
        }
    }

循环单链表

循环单链表与单链表的区别在于：尾结点的后继指针不为空，而是指向头结点。

这样做的好处是：循环单链表可以从任意一个结点开始遍历整个链表，而普通单链表只能从头结点开始。

循环单链表的判空操作

由于循环单链表的尾结点next指针不为空，所以无法通过头结点的next指针为空判断是空表。取而代之的方法是判断头结点的后继是否为自身。

    public boolean isEmpty() {
        return head.next==head;
    }

循环单链表的求长度操作

我们知道，循环单链表可以从任意结点遍历整个链表，遍历的终点为当前结点的前一个结点。

    public int length() {
        Node p=head.next;
        int length=0;
        while (p!=head) {    //原先的null相当于现在的head，因为尾结点的next指向head了
            length+=1;
            p=p.next;
        }
        return length;
    }

循环单链表的优化

为了进一步优化循环单链表，我们发现，如果设置head指针，那么对于尾结点的操作需要$O(n)$的时间复杂度，如果设置tail指针，那么对头结点的操作仅需$O(1)$的时间复杂度，因为单链表只存在后继指针而不存在前驱指针。

所以，如果对循环单链表的表首、表尾操作频繁，则设置尾指针比头指针更好。

循环双链表

循环双链表与循环单链表几乎类似，区别在于它的头结点的prior指针需要指向尾结点。

静态链表

静态链表是使用数组（顺序存储）来模拟链式存储结构的一种数据结构。它本质上属于顺序表，但它的元素之间逻辑关系是使用指针域体现的，所以插入和删除不需要移动元素。需要提前分配较大的连续空间。主要用于在不支持指针的语言中模拟链式存储。

顺序表和链表的比较

• 存取方式：
  • 顺序表可以顺序存取，也可以随机存取
  • 链表只能顺序存取
• 逻辑结构和物理结构：
  • 顺序表逻辑上相邻的元素物理上一定相邻，元素之间的逻辑关系通过位置关系体现。
  • 链表逻辑上相邻的元素物理上不一定相邻，元素之间的逻辑关系通过指针链接体现。
• 查找、插入和删除元素：
  • 查找：二者都无序，均需要$O(n)$的查找时间，如果有序，顺序表可以进行二分查找，仅需要$O(log_2n)$的查找时间。
  • 插入、删除：顺序表插入和删除需要移动大量元素，平均$O(n)$。而链表不考虑定位，只需要修改指针即可，$O(1)$，考虑定位虽然也需要$O(n)$，但大都是比较操作而非赋值操作，更快。
• 空间分配：
  • 顺序表必须分配连续的存储空间，存在外部碎片现象。如果预先分配存储空间，当分配空间过小时，会出现内存溢出现象，分配空间过大，会导致浪费。如果使用malloc动态分配空间，扩充时需要移动大量元素，效率很低。并且当内存空间不足时，会导致扩充失败。
  • 链表不需要分配连续的空间，不存在外部碎片现象，只要内存有空间就可以分配，灵活高效。但需要存储指针，造成了空间的浪费，数据存储密度较低。

顺序表和链表的选择

• 基于存储的考虑：
  • 如果线性表的长度和规模难以估计，优先使用链表。但链表的存储密度比较低，必然小于1，因为需要存放指针。
• 基于运算的考虑：
  • 如果经常需要按序号对元素进行存取，优先使用顺序表。（静态的数据）
  • 如果经常需要对元素进行插入和删除，优先使用链表。（动态的数据）
• 基于环境的考虑：
  • 大多数语言都有数组，但一些语言没有指针，所以无法实现链表。

栈和队列

栈

栈本质上就是一个线性表，但它是受限的。它受到的限制为：只允许在线性表的一端插入和删除元素。

常见的名词：

• 栈顶：允许进行插入和删除操作的一端。
• 栈尾：不允许进行插入和删除操作的一端。
• 空栈：不含元素的栈。

一个栈最大的特性为后进先出（LIFO）。

卡特兰数：n个不同的元素进栈，出栈元素的不同排列有$\frac{1}{n+1}C_{2n}^n$种。

栈的基本操作

我们定义一个栈的接口，并且规定一个栈具有的操作：

• 初始化
• 判空
• 出栈
• 入栈
• 获取栈顶元素（不出栈）
• 求栈长度
• 清空栈（JVM自动释放内存）

/*
栈的接口
 */
public interface IStack {
    public void clear();    //清空
    public boolean isEmpty();    //判空
    public int length();    //长度
    public Object peek();    //求栈顶元素
    public void push(Object x)throws Exception;    //入栈
    public Object pop();    //出栈
}

顺序栈

顺序栈的类型描述为：

public class SqStack implements IStack {
    private Object[] StackElem;    //栈元素数组
    private int top;    //栈顶元素的指针
}

新建栈的构造函数为：

    public SqStack(int maxSize) {
        StackElem= new Object[maxSize];
        top=0;    //我们让栈顶元素指针指向栈顶元素的下一个位置
    }

入栈操作

    public void push(Object x)throws Exception{
        if (top>=StackElem.length) {    //栈顶指针出界
            System.out.println("栈已满");
        }
        else {
            StackElem[top++]=x;    //如果栈顶指针指向的是栈顶元素，这里修改为++top，先后移栈顶指针
        }
    }

出栈操作

    public Object pop() {
        if (this.isEmpty()) {
            System.out.println("是空栈");
            return null;
        }    
        return StackElem[--top]; //如果栈顶指针指向的是栈顶元素，这里修改为top--，先取元素
    }

取栈顶元素

    public Object peek() {
        if (this.isEmpty()) {
            System.out.println("是空栈");
            return null;
        }
        return StackElem[top-1];
    }

完整实现

/*
顺序栈
 */
public class SqStack implements IStack {
    private Object[] StackElem;
    private int top;
    public SqStack(int maxSize) {
        StackElem= new Object[maxSize];
        top=0;    //我们让栈顶元素指针指向栈顶元素的下一个位置
    }
    public void clear() {
        top=0;
    }
    public boolean isEmpty() {
        return (top==0);
    }
    public int length() {
        return top;
    }
    public Object peek() {
        if (this.isEmpty()) {
            System.out.println("是空栈");
            return null;
        }
        return StackElem[top-1];
    }
    public void push(Object x)throws Exception{
        if (top>=StackElem.length) {    //栈顶指针出界
            System.out.println("栈已满");
        }
        else {
            StackElem[top]=x;    //如果栈顶指针指向的是栈顶元素，这里的两个操作要调换位置
            top+=1;
        }
    }
    public Object pop() {
        if (this.isEmpty()) {
            System.out.println("是空栈");
            return null;
        }
        top--;    //如果栈顶指针指向的是栈顶元素，这里的两个操作要调换位置
        return StackElem[top];
    }
    public void display() {
        if (!this.isEmpty()) {
            for (int i=0;i<this.length();i++) {
                System.out.print(StackElem[i]+" ");
            }
        }
        else {
            System.out.print("栈为空");
        }
    }
    public int search(Object x) {
        for (int i=top-1;i>=0;i--) {
            if (StackElem[i]==x) {
                return i;
            }
        }
        return -1;
    }
}

链栈

链栈的实现过程与单链表基本类似，唯一的限制在于只能在单链表首部进行插入删除操作。

链栈的好处就是单链表的好处，即不存在栈满溢出的情况，便于多个栈共享存储空间和提高效率。

链栈一般不设置头结点，因为插入和删除都是在首部，头结点能够统一不同操作的优势不存在了，也就没有必要设置了。

完整实现

/*
链栈
 */

public class LinkStack implements IStack {
    public Node top;    //栈顶指针（即头指针）
    public void clear() {
        top=null;    
    }
    public boolean isEmpty() {
        return (top==null); 
    }
    public int length() {
        int l=0;
        Node p=top;
        while(p!=null) {
            l+=1;
            p=p.next;
        }
        return l;
    }
    public Object peek() {
        if (top==null) {
            System.out.println("是空栈");
            return null;
        }
        return top.data;
    }
    public void push(Object x)throws Exception{
        Node p=new Node(x);
        p.next=top;
        top=p;
    }
    public Object pop() {
        if (this.top==null) {
            System.out.println("是空栈");
            return null;
        }
        Object x=top.data;
        top=top.next;
        return x;
    }
    public void display() {
        Node p=top;
        while (p!=null) {
            System.out.print(p.data+" ");
            p=p.next;
        }
    }
}

共享栈

共享栈技术主要利用了栈底位置的相对不变特性，可让两个顺序栈共享一个一维数组空间，让二者共同向中间延伸。

目的：更有效地利用存储空间。降低发生上溢的可能。

队列

队列本质上也是一个操作受限的线性表，但它的限制与栈不同：它只能在一端进行插入，另一端进行删除。

队列的特点是：先进先出（FIFO）。

常见概念为：

• 队首：允许删除的一端。
• 队尾：允许插入的一端。

队列的常见操作

我们定义一个队列接口来描述队列应该具有的操作：

/*
队列接口
 */

public interface IQueue {
    public void clear();
    public boolean isEmpty();
    public int length();
    public Object peek();    //取队首元素
    public void offer(Object x)throws Exception;    //入队
    public Object poll();    //出队
}

顺序队列

顺序队列是指用顺序存储的队列，需要使用front指针指向队首元素，rear指针指向队尾元素的下一个位置。

有元素入队时，我们将其放在数组的rear位置，再将rear指针加1，有元素出队时，我们将front指针加1即可。

但是，这样实现的顺序队列存在“假溢出”的问题，因为当入队操作出现上溢出时，数组前端可能会有因为出队操作空闲的存储区域，这样就把它们白白浪费了。

循环队列

为了解决顺序队列存在的“假溢出”问题，我们使用循环队列。

循环队列可以被想象为一个环状结构，当front指针或者rear指针越过数组末尾时，我们通过取余数的方法让它们回到数组的开头。

但是，我们会发现，如果使用循环队列以及上述的两个指针定义，存在这样的一个问题：队空和队满的判断条件都是rear == front，这将难以判断到底是哪一种情况。

解决该问题的方法主要有以下三种：

• 牺牲一个单元来区分队空和队满。如果rear == front ，则为队空，如果 （rear + 1）%maxsize == front，则为队满。
• 记录当前队列长度，判断是否达到数组容量上限。我们可以使用一个size变量存放队列总长度，size == 0，则为队空，size == maxSize，则为队满。其中，size = （rear + maxSize - front）%maxSize。
• 使用tag变量记录当前操作。插入操作时，我们将tag置为true，删除操作时，我们将tag置为false，tag默认为false，当rear == front 且 tag == false时，队空，当rear == front 且 tag == true时，队满。

循环队列完整实现

/*
循环队列
 */
public class CircularSqQueue implements IQueue{
    private Object[] queueElem;
    private int front;
    private int rear;
    private int maxSize;
    public CircularSqQueue(int maxSize) {
        front=rear=0;
        this.maxSize=maxSize;
        queueElem=new Object[maxSize];
    }
    public void clear() {
        front=rear=0;
    }
    public boolean isEmpty() {
        return (front==rear);
    }
    public int length() {
        return (rear+maxSize-front)%maxSize;
    }
    public Object peek() {
        if (!this.isEmpty()) {
            return queueElem[front];
        }
        else {
            System.out.println("队列空");
            return null;
        }
    }
    public void offer(Object x)throws Exception{
        if(front==(rear+1)%maxSize) {
            throw new Exception("队列已满");
        }
        else {
            queueElem[rear]=x;
            rear=(rear+1)%maxSize;
        }
    }
    public Object poll() {
        if (!this.isEmpty()) {
            Object t=queueElem[front];
            front=(front+1)%maxSize;
            return t;
        }
        else {
            System.out.println("队列空");
            return null;
        }
    }
}

链式队列

链式队列通常采用一个带有头结点的单链表实现，队首指针front指向头结点，队尾指针rear指向队尾结点。

链式队列的好处是不存在容量上限和溢出问题，适用于数据元素变动较大的场景，并且不会存在外部碎片，不要求分配连续的较大空间。

链式队列的实现

这里，我们使用不带头结点的单链表实现队列。

（实际上，带头结点的单链表实现队列更好，因为能够减少额外的判断，比如当队空时的入队操作）

/*
链式队列
 */
public class LinkQueue implements IQueue{
    public Node front;
    public Node rear;
    public LinkQueue() {
        front=rear=null;
    }
    public void clear() {
        front=rear=null;
    }
    public boolean isEmpty() {
        return front==null;
    }
    public int length() {
        Node p=front;
        int length=0;
        while (p!=null) {
            p=p.next;
            length++;
        }
        return length;
    }
    public Object peek() {
        if(!this.isEmpty()) {
            return front.data;
        }
        else {
            System.out.println("队列为空");
            return null;
        }
    }
    public void offer(Object x)throws Exception{
        Node p=new Node(x);
        if (!this.isEmpty()) {
            rear.next=p;
            rear=p;
        }
        else {
            front=rear=p;
        }
    }
    public Object poll() {
        if(!this.isEmpty()) {
            Object t=front.data;
            front=front.next;
            if (front==null) {
                rear=null;
            }
            return t;
        }
        else {
            System.out.println("队列为空");
            return null;
        }
    }
    public void display() {
        if(!this.isEmpty()) {
            Node p=front;
            while (p!=rear.next) {
                System.out.print(p.data+" ");
                p=p.next;
            }
        }
        else {
            System.out.println("队列为空");
        }
    }
}

双端队列指的是：允许在两端进行入队和出队操作的队列。

其中，只允许在一端入队，两端出队的队列叫作输入受限的双端队列；只允许在一端出队，两端入队的队列叫作输出受限的双端队列。

了解即可，有一些题目可能会用到双端队列，比如LeetCode上的滑动窗口的最大值这道题。

栈和队列的应用

栈在括号匹配的应用

括号的匹配可以使用一个括号栈来进行匹配。

• 遍历括号串，如果当前括号是左括号，那么将其压入括号栈。
• 如果当前括号是右括号，尝试将其与栈顶的左括号匹配，如果不匹配，则说明括号串失配，如果匹配，则将栈顶左括号出栈。
• 如果遍历完括号串，括号栈中仍有左括号，说明失配。

栈在表达式求值中的应用

我们人类使用的大都是中缀表达式，即运算符在操作数的中间，但实际上这种表示方法不利于计算机理解。计算机通常使用的是后缀表达式，即操作符在两个操作数之后，这样只用一个栈就可以完成计算。（前缀表达式需要两个栈辅助计算，一般不用）

遍历后缀表达式，如果遇到符号，则将栈顶两个元素出栈计算（如果是减法或者除法要注意计算顺序），并将计算得到的结果入栈。如果是数字，则将其入栈。

将中缀表达式转化为后缀表达式的算法思想如下：

• 从左到右扫描中缀表达式
• 遇到数字，加入后缀表达式
• 遇到运算符
  • 如果是“（”，直接入栈
  • 如果是“）”，依次将当前栈内的运算符弹出，直到遇到“（”，由于后缀表达式不需要括号表示运算优先级，所以直接将“（”删除即可。
  • 如果是其它运算符，则当其优先级大于栈顶运算符优先级时，直接入栈。否则，将栈顶运算符出栈并加入到后缀表达式中，重复操作直到遇到了小于它的优先级的栈顶元素或者左括号。
• 操作符优先级：
  • 乘号和除号优先级为2,
  • 加号和减号优先级为1，
  • 括号优先级为0

import java.util.*;
public class Calculate {
    public boolean isOperator(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/';
    }
    public int priority(char c) {
        if (c=='+'||c=='-') {
            return 1;
        }
        if (c=='*'||c=='/') {
            return 2;
        }
        return 0;
    }
    public String convertToPostfix(String expression) throws Exception{    //转化为后缀表达式
        LinkStack st=new LinkStack();
        String Postfix= "";
        char c=expression.charAt(0);
        int i=0;
        while (c!='#') {
            if (c!=' ') {
                if(c=='(') {
                    st.push(c);
                }
                else if (isOperator(c)) {
                    if (!st.isEmpty()) {
                        char ac=(Character)st.pop();
                        while (ac!=')'&&priority(ac) >= priority(c)) {
                            Postfix=Postfix.concat(String.valueOf(ac));
                            ac=(Character)st.pop();
                        }
                        if (ac==')'){
                            st.pop();
                        }
                        st.push(ac);
                    }
                    st.push(c);
                }
                else if (c==')') {
                    char ac=(Character)st.pop();
                    while (ac!='(') {
                        Postfix=Postfix.concat(String.valueOf(ac));
                        ac=(Character)st.pop();
                    }
                }
                else {
                    Postfix=Postfix.concat(String.valueOf(c));
                }
            }
            c=expression.charAt(++i);
        }
        while (!st.isEmpty()) {
            Postfix=Postfix.concat(String.valueOf(st.pop()));
        }
        return Postfix;
    }
    public double numberCalculate(String Postfix) throws Exception{    //计算后缀表达式
        LinkStack st=new LinkStack();
        for (int i=0;Postfix!=null&&i<Postfix.length();i++) {
            char c=Postfix.charAt(i);
            if (isOperator(c)) {
                double d2=Double.parseDouble(st.pop().toString());
                double d1=Double.parseDouble(st.pop().toString());
                double d3=0.0;
                if (c=='+') {
                    d3=d1+d2;
                }
                else if (c=='-') {
                    d3=d1-d2;
                }
                else if (c=='*') {
                    d3=d1*d2;
                }
                else if (c=='/') {
                    d3=d1/d2;
                }
                st.push(d3);
            }
            else {
                st.push(c);
            }
        }
        return (double)st.pop();
    }
    public static void main(String[] args) throws Exception {
        Calculate cal=new Calculate();
        String s1;
        Scanner in=new Scanner(System.in);
        s1=in.nextLine();
        String s2=cal.convertToPostfix(s1);
        System.out.println(cal.numberCalculate(s2));
    }
}

栈在递归中的应用

系统借助递归工作栈来存放每一层递归函数的返回点、局部变量、传入实参等。

我们可以通过手工设置栈来模拟递归，从而将递归算法转变为非递归算法。例如，树的遍历问题可以同时存在递归和非递归两种方法。

由于栈可以模拟递归，所以它可以应用与如下递归算法解决的问题，如：

• 迷宫求解

此外，它可以轻松完成倒序操作，所以也被用在：

• 进制转换（需要倒序输出）

队列在层次遍历中的应用

树的层次遍历是通过队列实现的，开始时，只有根结点位于队列中，然后将队首结点出队，访问该结点，将它的所有非空孩子加入队列，继续重复直到队列为空。

队列在计算机系统的应用

队列在计算机系统的应用有很多，主要有：

• 各种类型的先进先出算法（CPU调度FCFS、页面置换算法FIFO），都是使用FIFO队列实现的。
• 进程调度的就绪队列、阻塞队列等。
• 缓冲队列，解决主机和外部设备之间速度不匹配的问题。

特殊矩阵的压缩存储

矩阵即为数组，由于矩阵可能存在着许多重复的元素或者零元素，所以可以对多个值相同的元素只分配一个存储空间，并且对零元素不分配空间，从而节约了存储空间。

需要注意题目中的矩阵是哪一种矩阵：

• 上三角矩阵
• 对称矩阵
• 下三角矩阵
• 三对角矩阵（带状矩阵）

同时，还要注意存储的顺序按照的是：

• 按行优先
• 按列优先

上述几类矩阵的压缩存储，通常是将其压缩到一维数组中去，对应的下标关系不需要死记，必要时拿几个对应关系列方程求出系数即可。

此外，存在着一些没有规律的稀疏矩阵，即矩阵中0的个数很多。对于这一类矩阵，我们的压缩方式为：

• 三元组表（行标、列标、元素值）
• 十字链表法

串

串即字符串，指的是由零个或者多个字符组成的有限序列。

串的主要操作用Java接口表示为：

/*
字符串接口
 */
public interface IString {
    public void clear();    //清空字符串
    public boolean isEmpty();    //字符串判空
    public int length();    //    字符串求长度
    public char charAt(int index);    //求字符串中第index个字符
    public IString subString(int begin,int end);    //求子串
    public IString insert(int offset,IString str);    //插入子串
    public IString concat(IString str);    //拼接字符串
    public IString delete(int begin,int end);    //删除子串
    public int compareTo(IString str);    //比较字符串（ASCII码按位比较）
    public int IndexOf(IString str,int begin);    //串的模式匹配
}

字符串的存储结构通常分为顺序存储和链式存储。

一个字符串类的简单实现：

/*
字符串类实现
 */
public class SeqString implements IString{
    private char[] strvalue;
    private int curlen;
    public SeqString() {
        this.curlen=0;
        this.strvalue=new char[0];
    }
    public SeqString(String str) {
        this.strvalue=str.toCharArray();
        this.curlen=this.strvalue.length;
    }
    public SeqString(char[] value) {
        this.strvalue=new char[value.length];
        System.arraycopy(value, 0, this.strvalue, 0, value.length);
        this.curlen=value.length;
    }
    public int length() {
        return this.curlen;
    }
    public void clear() {
        this.curlen=0;
    }
    public boolean isEmpty() {
        return this.curlen==0;
    }
    public char charAt(int index) {
        if(index<0||index>=this.curlen) {
            throw new StringIndexOutOfBoundsException(index);
        }
        return this.strvalue[index];
    }
    public void allocate(int newCapacity) {
        char[] temp=new char[newCapacity];
        if (newCapacity>this.strvalue.length) {
            System.arraycopy(this.strvalue, 0, temp, 0, this.strvalue.length);
            this.strvalue=temp;
        }
        else {
            System.out.println("扩充错误");
        }
    }
    public IString subString(int begin,int end) {
        if (begin<0) {
            throw new StringIndexOutOfBoundsException("起始位置不能小于0");
        }
        else if (end>this.curlen) {
            throw new StringIndexOutOfBoundsException("结束位置不能大于字符串的长度");
        }
        else if (begin>end) {
            throw new StringIndexOutOfBoundsException("开始位置不能大于结束位置");
        }
        else if (begin==0&&end==this.curlen) {
             return this;
        }
        else {
            char[] newString=new char[end-begin];
            if (newString.length >= 0) System.arraycopy(this.strvalue, begin, newString, 0, newString.length);
            return new SeqString(newString);
        }
    }
    public IString insert(int offset,IString str) {
        if (offset<0||offset>this.curlen) {
            throw new StringIndexOutOfBoundsException("插入位置不合法");
        }
        int len=str.length();
        int newCount=len+this.curlen;
        if (newCount>this.strvalue.length) {
            this.allocate(newCount);
        }
        if (this.curlen - offset >= 0)
            System.arraycopy(this.strvalue, offset, this.strvalue, offset + len, this.curlen - offset);
        for (int i=offset;i<offset+len;i++) {
            this.strvalue[i]=str.charAt(i-offset);
        }
        this.curlen=newCount;
        return this;
    }
    public IString delete(int begin,int end) {
        if (begin<0||end>this.curlen||begin>end) {
            throw new StringIndexOutOfBoundsException("删除位置非法");
        }
        if (end - begin >= 0) System.arraycopy(this.strvalue, end, this.strvalue, begin, end - begin);
        this.curlen-=end-begin;
        return this;
    }
    public IString concat(IString str) {
        return insert(curlen, str);
    }
    public int compareTo(IString str) {
        int len1=this.length();
        int len2=str.length();
        int n=Math.min(len1, len2);
        int k=0;
        while (k<n) {
            if (this.charAt(k)!=str.charAt(k)) {
                return k;
            }
            k++;
        }
        return len1-len2;
    }
    public int IndexOf(IString str,int begin) {
        if (str != null && this.length() > str.length() && str.length() > 0) {
            int slen=this.length();
            int tlen=str.length();
            for (int i=begin;i<=slen-tlen;i++) {
                int b=0;
                for (int j=0;j<tlen;j++) {
                    if (this.charAt(i+j)!=str.charAt(j)) {
                        b=1;
                        break;
                    }
                }
                if (b==0) {
                    return i;
                }
            }
        }
        return -1;
    }
}

串的模式匹配

串的模式匹配通常采用两种方法：（1）BF暴力算法（2）KMP算法。上述实现中我仅仅实现了暴力算法。

KMP算法的核心是采用部分匹配表（PMT），来跳过必然不可能匹配成功的情况。因为假设模式串和待匹配串已经成功匹配了K个字符，而在第K+1个字符处失配，按照暴力算法，将回退到第1个字符处重新匹配。而实际上，成功匹配的K个字符其实就是模式串的前缀，这种频繁的重复比较相当于模式串不断地和自己比较。

采用KMP算法，可以跳过这些重复比较，具体的过程我已经写了一篇详细的博客，在https://hillzhang1999.gitee.io/2020/03/17/kmp-suan-fa/。

树与二叉树

树的基本概念

树的定义

树属于逻辑结构中的树形结构，它表示的是数据的一对多关系。

树是n（n>=0）个结点的有限集，当 n=0时，我们称其为“空树”。任意一个非空树中应该满足：

• 有且仅有一个称为“根”的结点。
• 当 n > 1 时，其余结点可以分为 m （m>0）个互不相交的有限集，其中每个集合本身也是一颗树，称作根的子树。

可以看出，树是一种分层结构，也是一种递归定义的数据结构。

树的特点为：

• 树的根节点没有前驱，除根结点外的所有结点有且仅有一个前驱。
• 树中的结点可以有零个（叶子结点）或多个后继。

树适合存放具有层次结构的数据。

基本术语

结点类型：

• 祖先结点：树中的某个结点A，从结点A到根结点Root上的唯一路径上的任意一个结点都是A的祖先结点（不包含自身）。
• 子孙结点：结点A是它的所有祖先结点的子孙结点。
• 双亲结点（父亲结点）：与结点A最接近的祖先结点即为双亲结点，即结点A的前驱。只有根结点没有祖先结点和双亲结点。
• 孩子结点：结点A的所有后继结点，即为它的孩子结点。
• 兄弟结点：具有相同双亲结点的结点。
• 堂兄弟结点：位于树中的同一层结点，称作堂兄弟结点。

常用术语：

• 度：与离散数学中的定义不同，数据结构中树的某个结点的度就是它的孩子结点的个数，也就是“出度”的个数。树的度即为树中结点的最大度数。
• 分支结点：度大于0的结点。
• 叶子结点：度等于0的结点。
• 深度（高度）：树的层次从根结点开始定义，根结点为第1层（有时从0开始），它的孩子结点为第二层，以此类推。树的高度（深度）为树中结点的最大层数。
• 有序树和无序树：如果树中结点的各子树从左到右有固定的顺序，交换后将变为不同的树，那么称其为有序树，否则为无序树。
• 路径和路径长度：树中任意两个结点的路径为二者之间经过的结点序列，路径长度为路径上边的个数。
• 森林：n棵（n>0）互不相交的树组成一个森林。

树的几个性质

• 树中结点个数等于树中结点度数加1（为什么要加1，是因为根结点没有前驱）
• 度为 m 的树中第 i 层上最多有 $m^{i-1}$个结点
• 高度为 h 的 m 叉树中最多有 $(m^h-1)/(m-1)$ 个结点
• **具有 n 个结点的 m 叉树最小高度为 $log_m(n(m-1)+1)$**（由上一条性质逆推即可）

二叉树

二叉树的定义

二叉树是一种受限的树，它受到的限制为：树的度为2，即每个结点最多有两个孩子结点。并且它的子树有左右之分，即为有序树。

虽然二叉树是度为2的有序树，但是反之并不成立，这是因为：

• 度为2的有序树至少有3个结点，而二叉树可以为空。
• 度为2的有序树，如果某个结点只有一个孩子结点，那么该孩子无需确定左右次序，可二叉树需要。

二叉树的5种形态分别为：

• 空二叉树
• 只有根结点
• 只有左子树
• 左右子树都有
• 只有右子树

几种特殊的二叉树

• 满二叉树：一颗高度为 h 且含有$2^h-1$个结点的二叉树称为满二叉树，即二叉树中每一层都含有最多结点。
• 完全二叉树：只有最后一层没有被填满的二叉树。叶子结点只可能存在于最后一层和倒数第二层。如果存在度为1的结点，那么它只可能有1个，且只有左孩子没有右孩子。
• 二叉排序树：左子树的所有结点的关键字值小于根结点，右子树上所有结点的关键字值均大于根结点。
• 平衡二叉树：左右子树高度差小于等于1。

二叉树的性质

• 非空二叉树上的叶子结点数等于度为2的结点数加1。（很重要，可以推导出来）
• 非空二叉树的第k层上只多有$2^{k-1}$个结点。
• 高度为h的二叉树至多有$2^k-1$个结点。（等比数列求和）
• 对完全二叉树的结点按从上到下，从左到右的顺序编号1,2,3,4…n，有以下关系：
  • 当 i>1 时，结点 i 的双亲结点为第 i//2 号结点。
  • 当 2i<=n 时，结点 i 的左孩子为第 2i 号结点。
  • 当 2i+1<=n时，结点 i 的左孩子为第 2i+1 号结点。
  • 结点 i 所在层数为 $log_2i+1$

二叉树的存储结构

顺序存储

二叉树的顺序存储指的是利用一组连续的存储单元按照从上到下、从左到右的顺序存储完全二叉树的结点。结点中间的关系通过数组下标的关系来标识（见上述完全二叉树的结点下标关系）。

一般来说，数组是从0下标开始的，但上述完全二叉树的下标性质的编号是从1开始的。所以我们通常舍弃数组中0号位置，从1号位置开始存放结点。

二叉树顺序存储适用于满二叉树和完全二叉树，因为无需额外存放指针，仅通过下标运算即可得到结点的关系，并且可以方便地进行二叉树的遍历，还可以方便地访问某个结点的双亲结点。

而对于非完全二叉树，我们只能通过填充空结点的方式，让它的每个结点与完全二叉树中的结点对应。对于一个只有k个结点的二叉树，最坏情况下需要$2^k-1$个空间，十分浪费。

链式存储

由于非完全二叉树的顺序存储空间利用率可能非常低，因此二叉树一般采用链式存储结构。用链表结点来存储二叉树中的每个结点，用左右指针来指向当前结点的左右孩子。

常用的二叉链表的存储结构为：（lchild左孩子指针域，data数据域，rchild右孩子指针域）

此外，我们也可以在二叉链表中加入指向父结点的指针域，变为三叉链表。

/*
二叉树结点类
 */
public class BiTreeNode {
    public Object data;
    public BiTreeNode lchild,rchild;
    public BiTreeNode() {
        this(null);
    }
    public BiTreeNode(Object data) {
        this(data,null,null);
    }
    public BiTreeNode(Object data,BiTreeNode lchild,BiTreeNode rchild) {
        this.lchild=lchild;
        this.rchild=rchild;
        this.data=data;
    }
}

一个具有n个结点的二叉链表中，含有n+1个空链域（总指针域数目为2n个，除根结点外有n-1个结点，二者相减）。我们可以利用这些空指针域，来实现另一种链表结构——线索链表。

二叉树的遍历

二叉树的遍历指的是按照某条搜索路径遍历二叉树中的每个结点，从而使得树中每个结点被访问一次。

二叉树的遍历顺序主要分为：

• 先序遍历：访问根结点——先序遍历左子树——先序遍历右子树（
• 中序遍历：中序遍历左子树——访问根结点——中序遍历右子树
• 后序遍历：后序遍历左子树——后序遍历右子树——访问根结点
• 层次遍历：按照从左到右，从上到下的顺序，对每一层的结点依次访问。

先序遍历、中序遍历、后序遍历的实现可以采用递归来实现，实现起来很简单。

**递归算法的时间复杂度为：$O(n)$**。n为二叉树结点个数。因为需要访问每个结点一次。

递归算法的空间复杂度为：$O(h)$**。h为二叉树高度。因为递归需要利用系统栈压栈保存需要返回的函数，而最深需要从叶子结点的递归函数返回到根结点的递归函数。最坏情况下，二叉树退化为单链表，递归空间复杂度为$O(n)$**。

    public void preRootTraverse(BiTreeNode T){
        if (T!=null){
            System.out.print(T.data);
            preRootTraverse(T.lchild);
            preRootTraverse(T.rchild);
        }
    }
    public void inRootTraverse(BiTreeNode T){
        if (T!=null){
            inRootTraverse(T.lchild);
            System.out.print(T.data);
            inRootTraverse(T.rchild);
        }
    }
    public void postRootTraverse(BiTreeNode T){
        if (T!=null){
            postRootTraverse(T.lchild);
            postRootTraverse(T.rchild);
            System.out.print(T.data);            
        }
    }

正如我们在之前所说，递归算法可以使用栈来进行模拟。

先序遍历的非递归算法流程为：

1. 指针指向根结点
2. 从当前指针指向的结点开始，先访问当前结点，然后将当前结点的右孩子入栈保存（模拟递归系统栈的功能，使得递归返回时可以继续进入右子树，当然也可以让当前结点入栈，返回时让指针指向它的右孩子即可），接着让指针指向当前结点的左孩子。重复上述访问和入栈过程，直到指针指向空结点。
3. 从栈中弹出一个结点，让指针指向该结点，重复第2步。
4. 如果栈为空，或者指针为空，那么就说明访问已经结束。

    public void preRootTraverse() throws Exception {
        BiTreeNode T=this.root;
        if (T!=null) {
            LinkStack S=new LinkStack();
            while (T!=null || !S.isEmpty()) {
                if (T!=null){
                    if(T.rchild!=null) 
                        S.push(T.rchild);
                    System.out.print(T.data);
                    T=T.lchild;
                }
                else{
                    T = (BiTreeNode) S.pop();
                }
            }
        }

中序遍历的非递归算法流程为：

1. 指针指向根结点
2. 从当前指针指向的结点开始，先将当前结点入栈保存，接着让指针指向当前结点的左孩子。重复上述访问和入栈过程，直到指针指向空结点。
3. 此时说明找到了可以访问的点，我们让栈顶结点出栈并访问，然后让指针指向它的右孩子，重复第2步。
4. 如果栈为空，或者指针为空，那么就说明访问已经结束。

    public void inRootTraverse() throws Exception {
        BiTreeNode T=this.root;
        if(T!=null) {
            LinkStack S=new LinkStack();
            while (T!=null||!S.isEmpty()){
                if (T!=null){
                    S.push(T);
                    T = T.lchild;
                }
                else{
                    T = (BiTreeNode)S.pop();
                    System.out.println(T.data);
                    T = T.rchild;
                }
            }
        }
    }

后序遍历的非递归实现最为复杂，有一种取巧的方法是进行翻转的先序遍历，即“根-右-左”，然后将得到的序列再次翻转，得到后序序列“左-右-根”。

常规的做法是：

1. 沿着根的左孩子，依次入栈，直到左孩子为空。
2. 读栈顶元素（不出栈），如果其右孩子不为空且没有被访问过，那么就将指针指向右孩子，重复第1步。否则，访问栈顶元素并出栈。
3. 为了判断右孩子有没有被访问过，我们设置一个指针r指向最近一个被访问的结点。如果它指向的是右孩子，说明右子树全部被访问完，可以访问当前根结点了。为了判断右子树是否被访问过，需要设置一个指针r指向最后一个被访问的结点。访问完结点后，需要让指针 r 指向它。

事实上，访问某个结点P时，栈中所有结点都是P的祖先结点，这一性质可用于求解根到某结点的路径，求两个结点的公共祖先等。

    public void postRootTraverse() throws Exception{
        BiTreeNode T=this.root;
        BiTreeNode r=null;
        if(T!=null) {
            LinkStack S=new LinkStack();
            while (T!=null||!S.isEmpty()){
                if (T!=null){
                    S.push(T);
                    T=T.lchild;
                }
                else{
                    T=(BiTreeNode)S.peek();
                    if (T.rchild!=null&&T.rchild!=r){
                        T = T.rchild;
                    }
                    else{
                        T = (BiTreeNode)S.pop();
                        System.out.println(T.data);
                        r = T;
                        T = null;
                    }
                }
            }
        }
    }

层次遍历只能通过非递归的方式实现，一般采用队列进行辅助。

流程为：

1. 先将根结点入队。
2. 从队首出队一个结点，访问该结点，然后将其非空左右孩子结点入队。
3. 重复第2步，直到队列为空。

    public void levelTraverse() throws Exception {
        BiTreeNode T=this.root;
        if(T!=null) {
            LinkQueue L=new LinkQueue();
            L.offer(T);
            while(!L.isEmpty()) {
                T=(BiTreeNode)L.poll();
                System.out.print(T.data);
                if(T.lchild!=null) {
                    L.offer(T.lchild);
                }
                if(T.rchild!=null) {
                    L.offer(T.rchild);
                }
            }
        }
    }

特别地，如果我们需要按层对结点进行访问，可以嵌套一个次数为当前层结点数（也就是当前队列长度）的循环，在这个循环内对当前层的结点进行遍历。

二叉树的构造（Python语言实现）

二叉树的构造通常有两种方法：

• 由先序、中序序列或者中序、后序序列唯一的确定一个二叉树。以先序、中序序列为例。我们根据先序序列确定根结点，然后通过中序序列分别确定左、右子树的结点个数。然后，我们依据左右结点的数目，对原序列进行划分，获得左、右子树的先序、中序序列，递归构造左、右子树即可。该方法至少需要两个序列，且必需中序序列。（PS：只有先序和后序序列虽然无法唯一地确定一个二叉树，但是可以得到二叉树中的祖先关系。如果X结点在先序序列中位于Y结点之前，而在后序序列中位于Y结点之后，则X结点是Y节点的祖先）

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def build(preL,preR,inL,inR):
            if preL>preR or inL>inR:
                return None
            root=TreeNode(preorder[preL])
            in_pos=inorder[inL:inR+1].index(preorder[preL])
            root.left=build(preL+1,preL+in_pos,inL,inL+in_pos-1)
            root.right=build(preL+in_pos+1,preR,inL+in_pos+1,inR)
            return root
        return build(0,len(preorder)-1,0,len(inorder)-1)

• 利用填充了空结点的先序或中序或后序或层次序列或确定二叉树。该方法可以递归地进行二叉树的序列化和反序列化，也可以非递归地进行。只需要一个序列即可。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

"""
层次遍历实现二叉树的序列化和反序列化
"""
class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        data=[]
        queue=[root]
        while queue!=[]:
            node=queue.pop(0)
            if node==None:
                data.append("*")
            else:
                data.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
        return ",".join(data)


    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        data=data.split(",")
        queue=[]
        index=1
        if data[0]=="*":
            return None
        else:
            root=TreeNode(int(data[0]))
        queue.append(root)
        while queue!=[] and index<len(data):
            node=queue.pop(0)
            if data[index]!="*":
                node.left=TreeNode(int(data[index]))
                queue.append(node.left)
            index+=1
            if data[index]!="*":
                node.right=TreeNode(int(data[index]))
                queue.append(node.right)
            index+=1
        return root

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

"""
先序遍历实现
"""
class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        data=[]
        def preorder(root):
            if root==None:
                data.append("*")
            else:
                data.append(str(root.val))
                preorder(root.left)
                preorder(root.right)
        preorder(root)
        return ",".join(data)     

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        data=data.split(",")
        self.index=0
        def build():
            if data[self.index]=="*":
                self.index+=1
                return None
            root=TreeNode(int(data[self.index]))
            self.index+=1
            root.left=build()
            root.right=build()
            return root
        return build()



# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

线索二叉树

我们在之前说过，一个有着 n 个结点的二叉链表，必然存在着 n+1 个空指针。这些指针可以用来存放当前结点的前驱或者后继，从而可以方便地像遍历单链表一样遍历二叉树的结点。

线索二叉树是二叉树的一种改进后的特殊存储结构。

我们对于线索二叉树的规定是：

• 如果当前结点没有左孩子，那么让其lchild指针指向前驱结点。
• 如果当前结点没有右孩子，那么让其rchild指针指向后继结点。
• 为了区分指针指向的是孩子结点还是前驱或者后继，我们使用两个标志位ltag和rtag，如果为0表示对应的指针指向的是孩子结点，否则表示指向的是前驱/后继。

二叉树的线索化就是将二叉树中的空指针改为前驱线索指针或者后继线索指针的过程。

我们以中序线索二叉树的构造为例：

• 我们设置一个指针pre指向刚刚访问过的访问的结点。pre初始化为null。
• 如果当前结点的lchild指针为空，那么让它指向pre。如果pre指针的rchild为空，那么让它指向当前结点。记得修改对应的ltag和rtag。
• 最后，记得设置中序序列首尾结点的线索和对应的标志位。

中序线索二叉树的遍历过程为：

• 先找到序列中的首个结点，即当前树中最左的结点。我们不断访问左孩子，直到左孩子的lchild指针为空。但在线索二叉树中，不存在空指针，所以这里判断的条件改为ltag为1。
• 如果它的rtag为1，表示rchild指针指向它的后继结点，进入访问即可。否则，它的右子树的最左结点即为后继结点。

先序和后序线索二叉树的构建同理。手工构建的过程中，可以先将序列写出来，然后根据序列中的前驱和后继修改对应结点的空指针。

后序线索树的遍历较为麻烦，需要栈的支持。

树的存储结构

双亲表示法

该方法通常使用顺序存储（链式存储也可以），使用一组连续的空间存放树中的每个结点，然后在每个结点中增设一个伪指针指向其双亲结点的位置（数组下标）。

该存储结构利用了每个结点（除根结点）只有一个双亲结点的性质，可以很快得到某个结点的双亲结点。但要访问孩子结点的话，需要遍历整个结构。

孩子表示法

将树中每个结点的孩子结点组成一个单链表，然后让当前结点指向该单链表。

此方法获取孩子结点非常方便，但寻找双亲结点最坏情况下需要遍历所有结点的孩子链表。

孩子兄弟表示法

孩子兄弟法，又称二叉树表示法，是利用二叉链表作为树的存储结构。

通常来说，一个孩子兄弟结点，拥有三部分内容：（1）数据域（2）指向它的首个孩子结点的指针域（3）指向它的右兄弟的指针域。

也就是说，每个结点只能直接访问到它的第一个孩子，对于其余孩子的遍历需要通过首个孩子的右兄弟指针进行。

该方法比较灵活，最大的优点是可以方便地进行树和二叉树的转化，易于查找孩子结点，但如果想要方便地查找双亲结点，还需要给每个结点新增一个指向双亲的指针域。

树、二叉树、森林的转化

树、森林转化为二叉树

树转化为二叉树，需要遵循“左孩子右兄弟”的规则，即利用二叉树结点的左孩子指针存放树节点的首个孩子，而利用二叉树结点的右孩子指针存放树结点的右兄弟。

需要注意，由于根结点没有兄弟，所以它的右孩子指针必然为空。

树转化为二叉树的步骤：

1. 在兄弟结点之间加一根线，方向为从左到右
2. 对于每个结点，只保留它和它的首个孩子的连线，其余连线全部抹掉
3. 以根结点为轴，将二叉树顺时针旋转45度

森林转化为二叉树的步骤类似。先将森林中的每棵树转为二叉树，然后利用二叉树根结点右孩子指针指向下一棵树。

二叉树转化为森林

二叉树转化为树的步骤只需要将上一节的方法逆推即可。

如果二叉树要转化为森林，需要先将右子树断开，然后将当前二叉树转化为树，即为森林中的第一棵树。然后进入右子树，继续转化，直到根结点没有右子树。

二叉树转化为的森林是唯一的。

树、二叉树、森林相互转化后遍历的对应关系

树和转化而成的二叉树，二者的先序遍历一致，而树的后序遍历等于它转化而成的二叉树的中序遍历。（PS：树无法中序遍历）

森林和转化而成的二叉树，二者的先序和中序遍历都一致。

树的应用——并查集

一种顺序存储的双亲表示法的树的结构。顾名思义只有并操作和查操作。

具体可以看我在LeetCode题解中写的岛屿数量题解。

二叉排序树BST

二叉排序树，也叫二叉查找树，是一棵空树，或者是具有如下特性的二叉树：

• 若左子树非空，则左子树上所有结点的值均小于根结点的值。
• 若右子树非空，则右子树上所有结点的值均大于根结点的值。
• 左右子树本身也是一棵二叉排序树。

根据二叉排序树的定义，如果我们按照中序遍历访问它，将得到一个递增序列。

同一组数据生成的二叉排序树不唯一，这和插入顺序有关。

二叉排序树的查找

二叉排序树的查找可以递归实现也可以非递归实现，总体思路非常简单。

• 首先将目标值与根结点的值比较，如果相等或者根节点为空，那么返回根结点。
• 如果目标值小于根结点，那么进入左子树继续查询。
• 如果目标值大于根结点，那么进入右子树继续查询。

整体思路和二分查找非常相近。

二叉排序树的插入

二叉排序树作为一种动态树表，其结构是可以动态插入的。

插入的过程如下：

• 如果当前树为空，那么直接将新插入的数据元素作为根结点。
• 如果新结点的关键字小于根结点的关键字，那么：
  • 如果根结点没有左孩子，那么就将新结点作为它的左孩子插入
  • 如果根结点有左孩子，那么递归进入左子树继续比较
• 如果新结点的关键字值大于根结点的关键字，那么：
  • 如果根结点没有右孩子，那么就将新结点作为它的右孩子插入
  • 如果根结点有右孩子，那么递归进入右子树继续比较

（C或者C++等有指针的语言不需要那么复杂，直接将双亲结点的孩子指针传进函数，如果它为空直接将其指向要插入的结点即可，而Java、Python等只有引用，无法通过修改引用改变实际的值）

我们可以发现，插入的结点一定是一个叶子结点，且是查找失败时的路径上的最后一个结点的左孩子或者右孩子。

二叉排序树的删除

二叉排序树结点的删除流程如下：

• 如果要删除的结点是叶结点，那么直接删除即可。
• 如果要删除的结点只有左子树或者右子树，那么将其删除，并让它的左或者右子树代替它的位置。
• 如果要删除的结点既有左子树也有右子树，那么需要让它直接前驱（直接后继）替换它的值，并且删除它的直接前驱或者直接后继。（因为它的直接前驱必然是它的左子树的最右结点，必然没有右子树，所以转化为第1或者第2种情况，直接后继同理）

二叉排序树的效率

二叉排序树的查找效率取决于其高度，最差时的比较次数等于它的高度。

当插入的序列有序时，二叉排序树退化为单链表，此时查找的平均时间复杂度为$O(n)$。

当二叉排序树的任意一个结点的左右子树高度差绝对值小于等于1时，二叉排序树称为平衡二叉树，此时查找的平均时间复杂度为$O(log_2n)$。

二分查找除了利用二叉排序树实现，还可以直接通过有序顺序表实现。就维护有序性而言，二叉排序树无需移动结点，只需要修改指针即可完成插入删除操作，平均时间复杂度为$O(log_2n)$（主要用于定位结点）。而有序顺序表需要$O(n)$的平均时间复杂度。

所以，如果有序表是动态查找表，适合使用二叉排序树，如果是静态表，则可以使用有序顺序表（不需要额外存放指针）

平衡二叉树AVL

上一节中我们提到了如果树高度增长太快，那么将大大降低二叉排序树的查找性能。为此，我们规定，在插入和删除结点时，要保证任意一个结点的左右子树高度差绝对值小于等于1，这样的二叉树叫作：平衡二叉树。

其中，任意一个结点的左子树与右子树的高度差为该结点的平衡因子，平衡二叉树的平衡因子只能取：0，-1，1。

平衡二叉树的插入

平衡二叉树的插入前半部分与普通二叉排序树类似，但是如果插入后导致了某个结点的不平衡，则需要先找到查找路径上距离插入结点最近的平衡因子绝对值大于1的结点A，称以A为根结点的子树为“最小不平衡子树”，然后调整该子树，使之重新平衡。

调整的方法主要有：

• LL平衡旋转（右单旋转）：如果因为在A的左孩子的左子树上插入结点，导致了A子树的不平衡，那么需要进行一次A子树的右旋。
  • 我们先让A结点的左孩子B代替A结点的位置
  • 然后让A结点成为B的右孩子
  • 最后让B结点的原右子树成为A结点的左孩子
• RR平衡旋转（左单旋转）：如果因为在A的右孩子的右子树上插入结点，导致了A子树的不平衡，那么需要进行一次A子树的左旋。
  • 我们先让A结点的右孩子B代替A结点的位置
  • 然后让A结点成为B的左孩子
  • 最后让B结点的原左子树成为A结点的右孩子
• LR平衡旋转（先左后右旋转）：如果因为在A的左孩子的右子树上插入结点，导致了A子树的不平衡，那么需要进行两次旋转。
  • 先让A结点的右子树进行一次左旋
  • 再让A子树进行一次右旋
• RL平衡旋转（先右后左旋转）：如果因为在A的右孩子的左子树上插入结点，导致了A子树的不平衡，那么需要进行两次旋转。
  • 先让A结点的左子树进行一次右旋
  • 再让A子树进行一次左旋

AVL树的查找效率

可以证明，n个结点的平衡二叉树，其高度为&O(log_2n)&，所以，在它上面查找的平均时间复杂度为&O(log_2n)&。

哈夫曼树

在许多实际应用中，树中的结点常常被赋予一个表示某种意义的值，叫作该结点的权。从根结点到某个结点的路径长度（路径上的边数）与该结点的权值的乘积，叫作该结点的带权路径长度。

树的带权路径长度是其所有叶子结点带权路径长度的总和。

在含有n个带权叶子结点的二叉树中，其中带权路径长度（WPL）最小的二叉树即为哈夫曼树，也叫最优二叉树。

哈夫曼树的构造

哈夫曼树的构造也比较简单，给定n个带权结点，算法流程如下：

1. 将这n个结点看做是n棵只包含一个根结点的二叉树，构造森林F。
2. 从F中选取两个根结点权值最小的树作为新结点的左右子树，新结点的权值为左右子树根结点权值之和。
3. 将得到的树加入到F中，并将刚才选出的两棵树删除。
4. 重复2-3步，直到森林只包含一棵树。

上述构造过程可以看出哈夫曼树的性质有：

• 每个初始结点最终都成为哈夫曼树的叶子结点，权值越小的结点，根结点到它的路径长度越长。
• 哈夫曼树的总结点数目为2n-1，其中包含n-1个伪结点。
• 哈夫曼树不存在度为1的结点。

public class HuffmanTree {
    public int[][] huffmanCoding(int[] W){
        int n=W.length;
        int m=2*n-1;
        HuffmanNode[] HN=new HuffmanNode[m];
        int i;
        for (i=0;i<n;i++) {
            HN[i]=new HuffmanNode(W[i]);
        }
        for (i=n;i<m;i++) {
            HuffmanNode min1=selectMin(HN,i-1);
            min1.flag=1;
            HuffmanNode min2=selectMin(HN,i-1);
            min2.flag=1;
            HN[i]=new HuffmanNode();
            min1.parent=HN[i];
            min2.parent=HN[i];
            HN[i].lchild=min1;
            HN[i].rchild=min2;
            HN[i].weight=min1.weight+min2.weight;
        }
        int[][] HuffCode=new int[n][n];
        for (i=0;i<n;i++) {
            int start=n-1;
            HuffmanNode c=HN[i];
            HuffmanNode p=c.parent;
            while (p!=null) {
                if (p.lchild.equals(c)) {
                    HuffCode[i][start--]=0;
                }
                else {
                    HuffCode[i][start--]=1;
                }
                c=p;
                p=p.parent;
            }
            HuffCode[i][start]=-1;
        }
        return HuffCode;
    }
    public HuffmanNode selectMin(HuffmanNode[] HN, int end) {
        HuffmanNode min=HN[end];
        for (int i=0;i<=end;i++) {
            if (HN[i].weight<min.weight&&HN[i].flag==0) {
                min=HN[i];
            }
        }
        if(min.flag==1) {
            return null;
        }
        return min;
    }
}

哈夫曼编码

数据通信中，如果对每个字符用等长的二进制位表示，则称为固定长度编码方式。如果对每个字符用不等长的二进制位表示，则称为可变长度编码方式。

可变长度编码方式可以起到压缩数据的效果。通常，我们对出现频率较低的字符使用较长的编码，而对出现频率较高的字符使用较短的编码。具体实现方式是将每个字符看作是一个带权的结点，权值为出现次数，然后构造哈夫曼树。

图

图的概念

图G由顶点集V和边集E组成，记为G=（V,E）。其中，V（G）表示图G中顶点的有限非空集，E（G）表示图G中顶点之间的关系（边）集合。我们用|V|表示图中顶点的个数，也称为图G的阶。用|E|表示图中边的个数。

需要注意的是，线性表可以是空表，树可以是空树，但图不可以是空图。图G的顶点集V（G）一定非空，而边集E（G）可以为空。

有向图

若图中的边是有向边，则称图G为有向图。有向边也称为弧，它是顶点的有序对，记为**<v,w>，其中，顶点v是有向边的起点，也叫作弧尾。顶点W是有向边的终点，也叫作弧头**。

无向图

若图中的边是无向边，则称图G为无向图。它是顶点的有序对，记为（v,w）或（w，v）。我们可以称v和w互为邻接点，也可以称（v,w）与v和w相关联。

简单图

简单图指的是图G满足（1）不存在重复的边（2）不存在顶点到自身的边。数据结构中的图通常都是简单图。不符合上述条件的图叫作多重图。

完全图（简单完全图）

完全图指的是图中任意两个顶点间都有边直接相连。

对于|V|=n的无向图，它为完全图的条件是拥有n（n-1）/2条边。如果它是有向图，那么它为完全图的条件是拥有n（n-1）条边。

子图

如果一个图G2的顶点集和边集都是另一个图G1的顶点集和边集的子集，那么称G2为G1的子图。如果G2的顶点集和G1相等，那么称G2是G1的生成子图（G1删去某些边可以生成G2）。

但是，图G1的顶点集和边集的任意子集不一定是它的子图，因为不一定是一个图（边集的顶点可能不在顶点集中）。

连通、连通图和连通分量（无向图）

在无向图中，如果从顶点v到顶点w存在一条路径，那么可以称v和w是连通的。如果图中任意两个结点都是连通的，则称此图为连通图（连通图不等于完全图，完全图要求直接相连）。无向图中的极大连通子图称为连通分量。

需要注意的是，极大连通子图和极小连通子图的区别。一个无向图的极大连通子图，不仅要连通，还要包含原图中的所有边。而极小连通子图在保证连通的前提下，要使边数最小。

强连通图和强连通分量（有向图）

强连通的概念只存在于有向图中。如果有向图中的两个结点v和w之间，既存在v到w的路径，也存在w到v的路径（双向路径），那么称v和w是强连通的。如果图中任意两个结点都是强连通的，则称此图为强连通图。有向图中极大强连通子图称为有向图的强连通分量。

生成树和生成森林

包含图中所有结点的一个极小连通子图叫作该图的生成树，如果一个图的顶点数为n，那么它的生成树必然有n-1条边。在非连通图中，所有连通分量的生成树构成了该图的连通森林。

度、入度、出度

顶点的度指的是以此顶点为一个端点的边的个数。

对于无向图，所有顶点的度数之和等于图上边数的两倍（一条边和两个顶点相关联）

入度指的是以此顶点为终点的有向边个数，出度指的是以此顶点为起点的有向边个数。

对于有向图，所有顶点的入度之和等于出度之和等于边数（每条边都有一个起点和一个终点）

边的权和网

一个图中，每条边都可以标上具有某种含义的值，该值为边的权值。这种边上带有权值的图称为带权图，也叫网。

稠密图和稀疏图

边数较少的图为稀疏图，反之则为稠密图。一般图G满足|E|<|V|log|V|时，称之为稀疏图。

路径和路径长度、回路

路径上边的长度称为路径长度，如果是网，那么就是路径上边的权值总和，这叫做带权路径长度。

起点与终点相同的路径叫作环，也称为回路。

如果一个图有n个顶点，但有超过n-1条边，则它是必然有环路存在。

简单路径和简单回路

如果路径上不存在重复的顶点，那么它是一个简单路径。

如果一个回路除了起点和终点外不存在重复的顶点，那么它是一个简单回路。

图的存储方法

邻接矩阵法

邻接矩阵法用一个一位数组存放图中的顶点信息，一个二维数组存放图中的边信息，这个二维数组即为邻接矩阵，因为它存放的是顶点之间的邻接关系。

它的特点有：

• 无向图的邻接矩阵必然是一个对称矩阵，可以压缩存储。
• 对于无向图，第 i 行的非零元素个数即为第 i 个顶点的度。
• 对于有向图，第 i 行的非零元素个数即为第 i 个顶点的出度。
• 邻接矩阵法存储，可以方便地知道两个顶点之间是否有边（直接通过数组下标查看），但如果要确定图中的边数，需要访问邻接矩阵的每个元素，时间耗费较大（$O(n^2)$）。
• 稠密图适合使用邻接矩阵，如果是稀疏图，将存放大量零元素，浪费空间。
• 图G的邻接矩阵为A，则$A^n$为图G中的顶点之间的路径长度为n的路径数目的矩阵。

一个邻接矩阵的实现：

import java.util.*;
public class MGraph implements IGraph {
    private final static int INFINITY= Integer.MAX_VALUE;
    private GraphKind kind;
    private int vexNum,arcNum;
    private Object[] vexs;
    private int[][] arcs;
    Scanner in=new Scanner(System.in);
    public MGraph() {
        this(null,0,0,null,null);
    }
    public MGraph(GraphKind kind,int vexNum,int arcNum,Object[] vexs,int[][]arcs) {
        this.kind=kind;
        this.vexNum=vexNum;
        this.arcNum=arcNum;
        this.vexs=vexs;
        this.arcs=arcs; 
    }
    public void createGraph() {
        System.out.println("请输入图的类型");
        GraphKind kind=GraphKind.valueOf(in.next());
        switch(kind){
        case UDG:
            createUDG();
            return;
        case DG:
            createDG();
            return;
        case UDN:
            createUDN();
            return;
        case DN:
            createDN();
            return;
        }
    }
    private void createUDG() {
        System.out.println("请输入无向图的顶点数和边数：");
        vexNum=in.nextInt();
        arcNum=in.nextInt();
        vexs=new Object[vexNum];
        System.out.println("请依次输入各顶点的值：");
        for(int i=0;i<vexNum;i++) {
            vexs[i]=in.next();
        }
        arcs=new int[vexNum][vexNum];
        for (int i=0;i<vexNum;i++) {
            for (int j=0;j<vexNum;j++) {
                arcs[i][j]=0;
            }
        }
        System.out.println("请输入各无向边的两个顶点值：");
        for(int i=0;i<arcNum;i++) {
            int n=locateVex(in.next());
            int m=locateVex(in.next());
            while(true) {
                if(n>=0&&m>=0) {
                    arcs[n][m]=arcs[m][n]=1;
                    break;
                }
                System.out.println("顶点值不存在，请重新输入各无向边的两个顶点值：");
                n=locateVex(in.next());
                m=locateVex(in.next());
            }
        }
    }
    private void createDG() {
        System.out.println("请输入有向图的顶点数和边数：");
        vexNum=in.nextInt();
        arcNum=in.nextInt();
        vexs=new Object[vexNum];
        System.out.println("请依次输入各顶点的值：");
        for(int i=0;i<vexNum;i++) {
            vexs[i]=in.next();
        }
        arcs=new int[vexNum][vexNum];
        for (int i=0;i<vexNum;i++) {
            for (int j=0;j<vexNum;j++) {
                arcs[i][j]=0;
            }
        }
        System.out.println("请输入各有向边的两个顶点的值：");
        for(int i=0;i<arcNum;i++) {
            int n=locateVex(in.next());
            int m=locateVex(in.next());
            while(true) {
                if(n>=0&&m>=0) {
                    arcs[n][m]=1;
                    break;
                }
                System.out.println("顶点值不存在，请重新输入各有向边的两个顶点值：");
                n=locateVex(in.next());
                m=locateVex(in.next());
            }
        }
    }
    private void createUDN() {
        System.out.println("请输入无向网的顶点数和边数：");
        vexNum=in.nextInt();
        arcNum=in.nextInt();
        vexs=new Object[vexNum];
        System.out.println("请依次输入各顶点的值：");
        for(int i=0;i<vexNum;i++) {
            vexs[i]=in.next();
        }
        arcs=new int[vexNum][vexNum];
        for (int i=0;i<vexNum;i++) {
            for (int j=0;j<vexNum;j++) {
                if (i==j) {
                    arcs[i][j]=0;
                }
                else{
                    arcs[i][j]=INFINITY;
                }
            }
        }
        System.out.println("请输入各无向边的两个顶点值和边的权值：");
        for(int i=0;i<arcNum;i++) {
            int n=locateVex(in.next());
            int m=locateVex(in.next());
            while(true) {
                if(n>=0&&m>=0) {
                    arcs[n][m]=arcs[m][n]=in.nextInt();
                    break;
                }
                System.out.println("顶点值不存在，请重新输入各无向边的两个顶点值和边的权值：");
                n=locateVex(in.next());
                m=locateVex(in.next());
            }
        }
    }
    private void createDN() {
        System.out.println("请输入有向网的顶点数和边数：");
        vexNum=in.nextInt();
        arcNum=in.nextInt();
        vexs=new Object[vexNum];
        System.out.println("请依次输入各顶点的值：");
        for(int i=0;i<vexNum;i++) {
            vexs[i]=in.next();
        }
        arcs=new int[vexNum][vexNum];
        for (int i=0;i<vexNum;i++) {
            for (int j=0;j<vexNum;j++) {
                if (i==j) {
                    arcs[i][j]=0;
                }
                else{
                    arcs[i][j]=INFINITY;
                }
            }
        }
        System.out.println("请输入各有向边的两个顶点值和边的权值：");
        for(int i=0;i<arcNum;i++) {
            int n=locateVex(in.next());
            int m=locateVex(in.next());
            while(true) {
                if(n>=0&&m>=0) {
                    arcs[n][m]=in.nextInt();
                    break;
                }
                System.out.println("顶点值不存在，请重新输入各有向边的两个顶点值和边的权值：");
                n=locateVex(in.next());
                m=locateVex(in.next());
            }
        }
    }
    public int getVexNum() {
        return vexNum;
    }
    public int getArcNum() {
        return arcNum;
    }
    public int locateVex(Object Vex) {
        for(int i=0;i<vexNum;i++) {
            if(vexs[i].equals(Vex)) {
                return i;
            }
        }
        return -1;
    }
    public Object getVex(int v)throws Exception{
        if (v<0||v>=vexNum) {
            throw new Exception("第"+v+"个顶点不存在");
        }
        return vexs[v];
    }
    public int getArc(int v,int w)throws Exception{
        if (v<0||v>=vexNum||w<0||w>=vexNum) {
            throw new Exception("坐标非法");
        }
        return arcs[v][w];
    }
    public int firstAdjVex(int v)throws Exception{
        if (v<0||v>=vexNum) {
            throw new Exception("第"+v+"个顶点不存在");
        }
        for (int j=0;j<vexNum;j++) {
            if (arcs[v][j]!=0&&arcs[v][j]<INFINITY) {
                return j;
            }
        }
        return -1;
    }
    public int nextAdjVex(int v,int w)throws Exception{
        if (v<0||v>vexNum) {
            throw new Exception("第"+v+"个顶点不存在");
        }
        for (int j=w+1;j<vexNum;j++) {
            if (arcs[v][j]!=0&&arcs[v][j]<INFINITY) {
                return j;
            }
        }
        return -1;
    }
    public GraphKind getKind() {
        return kind;
    }
    public int[][] getArcs(){
        return arcs;
    }
    public Object[] getVexs() {
        return vexs;
    }
    public void addArc(int v,int u,int value) {
        arcs[v][u]=value;
    }
    public void BFSTraverse(int v) throws Exception{
        boolean[] visited=new boolean[vexNum];
        for (int i=0;i<vexNum;i++) {
            visited[i]=false;
        }
        visited[v]=true;
        System.out.print(getVex(v).toString()+" ");
        LinkQueue Q=new LinkQueue();
        Q.offer(v);
        while(!Q.isEmpty()) {
            v=(Integer)Q.poll();
            for (int i=firstAdjVex(v);i>=0;i=nextAdjVex(v,i)) {
                if(!visited[i]) {
                    visited[i]=true;
                    System.out.print(getVex(i).toString()+" ");
                    Q.offer(i);
                }
            }
        }
    }
}

邻接表法

邻接表法结合了顺序存储和链式存储的方式，使用了一个顶点表和一个边表。

顶点表结点具有两个域：（1）存放顶点信息的顶点域（2）存放边表头指针的指针域。顶点表结点可以按顺序放在一个数组中，即为顶点表，数组的下标即为对应顶点的关键字。

边表结点具有两个域：（1）存放这条边的邻接点信息（一般是顶点表中的邻接点的下标）的邻接点域（2）存放顶点的下一条邻接边的指针域。

邻接表的优点是：

• 节约了存储空间。如果图G是有向图，那么邻接表的空间复杂度为$O(|E|+|V|)$，如果无向图，邻接表的空间复杂度为$O(2|E|+|V|)$。而使用邻接矩阵，无论如何都需要$O(|V|*|V|)$的空间。所以如果是稀疏图，适合用邻接表。
• 给定一个顶点，使用邻接表可以很方便地确定它的出度和邻边。但要查询两个顶点之间是否有边，那么邻接表需要顺序查找边表，不如邻接矩阵的直接查找。
• 图的邻接矩阵唯一，而邻接表不唯一，邻接表的边表链接次序可以是任意的。

一个邻接表的实现：

import java.util.*;
public class ALGraph {
    private GraphKind kind;
    private int vexNum,arcNum;
    private VNode[] vexs;
    Scanner in=new Scanner(System.in);
    public ALGraph() {
        this(null,0,0,null);
    }
    public ALGraph(GraphKind kind,int vexNum,int arcNum,VNode[] vexs) {
        this.kind=kind;
        this.vexNum=vexNum;
        this.arcNum=arcNum;
        this.vexs=vexs;
    }
    public void createGraph() {
        System.out.println("请输入图的类型");
        GraphKind kind=GraphKind.valueOf(in.next());
        switch(kind){
        case UDG:
            createUDG();
            return;
        case DG:
            createDG();
            return;
        case UDN:
            createUDN();
            return;
        case DN:
            createDN();
            return;
        }
    }
    private void createUDG() {
        System.out.println("请输入无向图的顶点数和边数：");
        vexNum=in.nextInt();
        arcNum=in.nextInt();
        vexs=new VNode[vexNum];
        System.out.println("请依次输入各顶点的值：");
        for(int i=0;i<vexNum;i++) {
            vexs[i]=new VNode(in.next());
        }
        System.out.println("请输入各无向图的两个顶点值：");
        for(int i=0;i<arcNum;i++) {
            int n=locateVex(in.next());
            int m=locateVex(in.next());
            addArc(n,m,0);
            addArc(m,n,0);
        }
    }
    private void createDG() {
        System.out.println("请输入有向图的顶点数和边数：");
        vexNum=in.nextInt();
        arcNum=in.nextInt();
        vexs=new VNode[vexNum];
        System.out.println("请依次输入各顶点的值：");
        for(int i=0;i<vexNum;i++) {
            vexs[i]=new VNode(in.next());
        }
        System.out.println("请输入各有向图的两个顶点值：");
        for(int i=0;i<arcNum;i++) {
            int n=locateVex(in.next());
            int m=locateVex(in.next());
            addArc(n,m,0);
        }
    }
    private void createUDN() {
        System.out.println("请输入无向网的顶点数和边数：");
        vexNum=in.nextInt();
        arcNum=in.nextInt();
        vexs=new VNode[vexNum];
        System.out.println("请依次输入各顶点的值：");
        for(int i=0;i<vexNum;i++) {
            vexs[i]=new VNode(in.next());
        }
        System.out.println("请输入各无向边的两个顶点值和边的权值：");
        for(int i=0;i<arcNum;i++) {
            int n=locateVex(in.next());
            int m=locateVex(in.next());
            int value=in.nextInt();
            addArc(n,m,value);
            addArc(m,n,value);
        }
    }
    private void createDN() {
        System.out.println("请输入有向网的顶点数和边数：");
        vexNum=in.nextInt();
        arcNum=in.nextInt();
        vexs=new VNode[vexNum];
        System.out.println("请依次输入各顶点的值：");
        for(int i=0;i<vexNum;i++) {
            vexs[i]=new VNode(in.next());
        }
        System.out.println("请输入各有向边的两个顶点值和边的权值：");
        for(int i=0;i<arcNum;i++) {
            int n=locateVex(in.next());
            int m=locateVex(in.next());
            int value=in.nextInt();
            addArc(n,m,value);
        }
    }
    public int getVexNum() {
        return vexNum;
    }
    public int getArcNum() {
        return arcNum;
    }
    public int locateVex(Object v) {
        for (int i=0;i<vexNum;i++) {
            if(vexs[i].data.equals(v)) {
                return i;
            }
        }
        return -1;
    }
    public VNode[] getVexs() {
        return vexs;
    }
    public GraphKind getKind() {
        return kind;
    }
    public Object getVex(int v)throws Exception{
        if(v<0||v>=vexNum) {
            throw new Exception("第"+v+"个顶点不存在");
        }
        return vexs[v].getData();
    }
    public int firstAdjVex(int v)throws Exception{
        if(v<0||v>=vexNum) {
            throw new Exception("第"+v+"个顶点不存在");
        }
        VNode vex=vexs[v];
        if(vex.firstArc!=null) {
            return vex.firstArc.adjVex;
        }
        return -1;
    }
    public void addArc(int v,int u,int value) {
        ArcNode arc=new ArcNode(u,value);
        arc.nextArc=vexs[v].firstArc;
        vexs[v].firstArc=arc;
    }
    public int nextAdjVex(int v,int w)throws Exception{
        if(v<0||v>=vexNum) {
            throw new Exception("第"+v+"个顶点不存在");
        }
        VNode vex=vexs[v];
        ArcNode arcvw=null;
        ArcNode arc=vex.firstArc;
        while (arc!=null) {
            if(arc.adjVex==w) {
                arcvw=arc;
                break;
            }
            arc=arc.nextArc;
        }
        if(arcvw!=null&&arcvw.nextArc!=null) {
            return arcvw.nextArc.adjVex;
        }
        return -1;
    }
    public int getArc(int v,int w)throws Exception{
        if (v<0||v>=vexNum||w<0||w>=vexNum) {
            throw new Exception("坐标非法");
        }
        int a=vexs[v].firstArc.adjVex;
        ArcNode AN=vexs[v].firstArc;
        while (a!=w) {
            a=nextAdjVex(v,a);
            AN=AN.nextArc;
        }
        return AN.value;
    }
}

十字链表法（有向图）

十字链表法是用于有向图的一种链式存储结构。它对每一条弧和每一个顶点都有一个结点。

弧结点的数据结构为：

• 尾域：存放弧尾（有向边起点）在顶点表中的位置
• 头域：存放弧头（有向边终点）在顶点表中的位置
• 尾链域：指向弧尾相同（有向边起点）的下一条弧
• 头链域：指向弧头相同（有向边终点）的下一条弧
• 信息域：存放弧的信息，如权值

顶点结点的数据结构为：

• 数据域
• firstin：指向首个以该顶点为弧头的弧
• firstout：指向首个以该顶点为弧尾的弧

应用十字链表，我们可以方便地求出每个顶点的入度和出度。（邻接表只能求出出度）

邻接多重表（无向图）

类似于十字链表在无向图中的应用。

与邻接表的区别在于，每条边只需要用一个结点表示，而邻接表中需要两个。

图的遍历

图的遍历主要分为BFS和DFS。通常，需要设置一个辅助数组visited来标记已被访问的顶点，防止重复访问。

BFS，即广度优先搜索，是按层进行访问的方式，是树的层次遍历的推广。一般应用在求解最短路径的问题，例如最少找零次数，Dijkstra单源最短路径算法、prim最小生成树算法。需要使用到辅助队列。

public class BTraverser {
   private static boolean[] visited;
   public static void BFSTraverse(IGraph G) throws Exception{
      visited=new boolean[G.getVexNum()];
      for (int i=0;i<G.getVexNum();i++) {
         visited[i]=false;
      }
      for (int i=0;i<G.getVexNum();i++) {
         if(!visited[i]) {
            BFS(G,i);
         }
      }
   }
   public static void BFS(IGraph G,int v) throws Exception {
      visited[v]=true;
      System.out.print(G.getVex(v).toString()+" ");
      LinkQueue Q=new LinkQueue();
      Q.offer(v);
      while(!Q.isEmpty()) {
         v=(Integer)Q.poll();
         for (int i=G.firstAdjVex(v);i>=0;i=G.nextAdjVex(v,i)) {
            if(!visited[i]) {
               visited[i]=true;
               System.out.print(G.getVex(i).toString()+" ");
               Q.offer(i);
            }
         }
      }
   }
   public static void Re(IGraph G) {
      visited=new boolean[G.getVexNum()];
      for (int i=0;i<G.getVexNum();i++) {
         visited[i]=false;
      }
   }
}

DFS，即深度优先搜索，类似于二叉树的先序遍历，是递归访问的方式。一般用于求解所有路径的问题，还可以应用回溯算法，进行模拟。

public class DTraverser {
    private static boolean[] visited;
    public static void DFSTraverse(IGraph G) throws Exception{
        visited=new boolean[G.getVexNum()];
        for (int i=0;i<G.getVexNum();i++) {
            visited[i]=false;
        }
        for (int i=0;i<G.getVexNum();i++) {    //防止非连通图    
            if(!visited[i]) {
                DFS(G,i);
            }
        }
    }
    public static void DFS(IGraph G,int v) throws Exception{
        visited[v]=true;
        System.out.print(G.getVex(v).toString()+" ");
        for (int i=G.firstAdjVex(v);i>=0;i=G.nextAdjVex(v,i)) {
            if(!visited[i]) {
                DFS(G,i);
            }
        }
    }
    public static void Re(IGraph G) {
        visited=new boolean[G.getVexNum()];
        for (int i=0;i<G.getVexNum();i++) {
            visited[i]=false;
        }
    }
}

对于访问所有顶点的问题，DFS和BFS的时空复杂度一致。

广度优先遍历生成的遍历树叫作广度优先生成树，深度优先遍历生成的遍历树叫作深度优先生成树。邻接矩阵的两个生成树唯一，邻接表不唯一。

最小生成树MST

一个带权连通无向图的生成树是它的极小连通子图，其中包括图的所有顶点，并且只包含尽可能少的边。

最小生成树的性质有：

• 当图中边的权值不唯一时，最小生成树的树形可能不唯一，但MST的边的权值总和总是唯一。
• 当图中边的权值唯一时，最小生成树唯一。
• 最小生成树首先是一棵树，所以它的边数总是比顶点数小1。

构造最小生成树的算法主要有：普利姆算法（Prim）和克鲁斯卡尔算法（Kruskal），它们都是基于贪心策略的。

Prim算法

普利姆算法非常简单，它是从顶点开始扩展最小生成树。其思想有些类似于求解单源最短路径的Dijkstra算法。

它的算法流程为：

1. 初始化一棵空树T。
2. 从图G中任选一个顶点加入该树中。
3. 在图G剩余的顶点中选取一个与树T中的顶点距离最小（贪心思想，眼前的最优解）的顶点，并将该顶点与对应的边加入树中。
4. 重复第3步，直到图中所有顶点都加入到树T中。此时，树T为图G的最小生成树。

该算法的时间复杂度：$O(|V|^2)$，与边数无关，所以适合使用在稠密图上。

（求解最小距离的过程与Dijkstra算法非常类似，也是使用一个dist距离数组来实现，每次选取到一个新顶点，就尝试更新它的邻接点的最小距离，唯一的区别是：Dijkstra算法的距离数组指的是从源点到对应顶点的距离，使用dist[j]+arcs[j] [k]更新；而Prim算法的距离数组是从树上任意一个顶点到对应顶点的距离，直接用arcs[j] [k]更新即可）

public class MiniSpanTree_PRIM {
    private static class CloseEdge{
        Object adjvex;
        int lowcost;
        public CloseEdge(Object adjvex,int lowcost) {
            this.adjvex=adjvex;
            this.lowcost=lowcost;
        }
    }
    public Object[][]PRIM(MGraph G,Object u)throws Exception {
        Object[][]tree=new Object[G.getVexNum()-1][2];
        int count=0;
        CloseEdge[]closeEdge=new CloseEdge[G.getVexNum()];
        int k=G.locateVex(u);
        for (int j=0;j<G.getVexNum();j++) {
            if(j!=k) {
                closeEdge[j]= new CloseEdge(u, G.getArcs()[k][j]);
            }
        }
        closeEdge[k]= new CloseEdge(u, 0);
        for (int i=1;i<G.getVexNum();i++) {
            k=getMinMun(closeEdge);
            tree[count][0]=closeEdge[k].adjvex;
            tree[count][1]=G.getVex(k);
            count++;
            closeEdge[k].lowcost=0;
            for (int j=0;j<G.getArcNum();j++) {
                if(G.getArcs()[k][j]<closeEdge[j].lowcost) {
                    closeEdge[j]= new CloseEdge(G.getVex(k), G.getArcs()[k][j]);
                }
            }
        }
        return tree;
    }
    private int getMinMun(CloseEdge[] closeEdge) {
        int min=Integer.MAX_VALUE;
        int v=-1;
        for (CloseEdge edge : closeEdge) {
            if (edge.lowcost < min) {
                min = edge.lowcost;
                v = 0;
            }
        }
        return v;
    }
}

Kruskal算法

克鲁斯卡尔算法基于边的权值递增次序来选择合适的边构造最小生成树。

其算法的核心思想是：每次选取当前权值最小且不会使最小生成树产生回路的边加入到最小生成树中。

克鲁斯卡尔算法选择权值最小的边的操作，通常使用堆（数据结构的堆，不是系统的堆）来完成，时间复杂度为$O(log|E|)$（主要用于调整堆），最小生成树可以使用并查集来描述（因为只有选取的边的两个顶点不在同一棵树中，才不会产生回路，可以通过并查集的Find操作实现判断），总的时间复杂度为$O(|E|log|E|)$，所以它适合用于稀疏图。

最短路径

之前我们提到了BFS求解最短路径的算法，但是该算法只适用于无权图。

对于有权图，求解最短带权路径通常使用两种方法：

• 针对单源最短路径（起点唯一）的Dijkstra算法。
• 针对所有顶点之间的最短路径的Floyd算法。

它们都基于这样一个性质：两点之间的最短路径必然包含路径上其他顶点之间的最短路径。

最短路径必须是一条简单路径（不存在环路）。

Dijkstra算法

Dijkstra算法的主要流程为：

1. 确定起点Start
2. 定义dist[i]为起点Start到其余每个顶点的最短路径长度，初始时，dist[i] = arcs[start] [i]（如果不相邻，则为无穷）。定义path[j]为从起点到顶点i的最短路径上的前驱结点，通过它可以追溯出最短路径。初始时，path[i] = start （if arcs[start] [i] != 无穷）
3. 每次选取未访问过的顶点中的dist最小值dist[i]，则源点到该顶点i的最短路径长度即为当前dist。同时，遍历该顶点的邻接点j，尝试更新dist数组和path数组：dist[j] = dist[i] + arcs[i] [j]，path[j] = i（if dist[j] < dist[i] + arcs[i] [j]）（这一操作又叫做松弛操作）
4. 重复第3步，直到到达图中所有顶点的最短路径被确定。

Dijkstra算法基于贪心策略，时间复杂度为$O(|V|^2)$，如果仅要求图上两点之间的最短路径，时间复杂度也最少是$O(|V|^2)$。

Dijkstra算法不适用于存在负边的带权图，可以使用Bellman-ford算法或者SPFA算法等代替。

public class ShortestPath_DIJ {
    private boolean[][] p;
    private int[]D;
    public final static int INFINITY=Integer.MAX_VALUE;

    public void DIJ(IGraph G,int v0) throws Exception {
        int vexNum=G.getVexNum();
        p=new boolean[vexNum][vexNum];
        D=new int[vexNum];
        boolean[] finish=new boolean[vexNum];
        for (int v=0;v<vexNum;v++) {
            finish[v]=false;
            D[v]=G.getArc(v0, v);
            for (int w=0;w<vexNum;w++) {
                p[v][w]=false;
                }
            if (D[v]<INFINITY) {
                p[v][v0]=true;
                p[v][v]=true;
            }
        }
        finish[v0]=true;
        int v=-1;
        for (int i=1;i<vexNum;i++) {
            int min=INFINITY;
            for (int w=0;w<vexNum;w++) {
                if(!finish[w]) {
                    if(D[w]<min) {
                        min=D[w];
                        v=w;
                    }
                }
            }
            finish[v]=true;
            for (int w=0;w<vexNum;w++) {
                if(!finish[w]&&G.getArc(v, w)<INFINITY&&((min+G.getArc(v, w))<D[w])) {
                    D[w]=min+G.getArc(v, w);
                    System.arraycopy(p[v], 0, p[w], 0, p[v].length);
                    p[w][w]=true;
                }
            }
        }
    }
    public int[] getD() {
        return D;
    }
    public boolean[][] getP(){
        return p;
    }
    public void DijKstra(IGraph G,int v0,int u) throws Exception {
        int vexNum=G.getVexNum();
        p=new boolean[vexNum][vexNum];
        D=new int[vexNum];
        boolean[] finish=new boolean[vexNum];
        for (int v=0;v<vexNum;v++) {
            finish[v]=false;
            D[v]=G.getArc(v0, v);
            for (int w=0;w<vexNum;w++) {
                p[v][w]=false;
                }
            if (D[v]<INFINITY) {
                p[v][v0]=true;
                p[v][v]=true;
            }
        }
        finish[v0]=true;
        int v=-1;
        for (int i=1;i<vexNum;i++) {
            int min=INFINITY;
            for (int w=0;w<vexNum;w++) {
                if(!finish[w]) {
                    if(D[w]<min) {
                        min=D[w];
                        v=w;
                    }
                }
            }
            finish[v]=true;
            for (int w=0;w<vexNum;w++) {
                if(!finish[w]&&G.getArc(v, w)<INFINITY&&((min+G.getArc(v, w))<D[w])) {
                    D[w]=min+G.getArc(v, w);
                    System.arraycopy(p[v], 0, p[w], 0, p[v].length);
                    p[w][w]=true;
                }
            }
        }
        System.out.println("从第"+v0+"个顶点到第"+u+"个顶点的最短路线的距离为："+D[u]);
        System.out.println("从第"+v0+"个顶点到第"+u+"个顶点的最短路线经过的顶点为：");
        for (int i=0;i<vexNum;i++) {
            if(p[u][i]==true) {
                System.out.println(G.getVex(i).toString()+" ");
            }
        }
    }
}

Floyd算法

Floyd算法可以用于求出图上所有顶点之间的最短路径。

其思想主要是：

• 首先，初始化图的邻接矩阵A[i] [j]。
• 以第0个顶点作为中间顶点，如果其他顶点i能够通过第0个顶点到达另一个顶点j比当前到达该顶点的路径更短，就更新（松弛）A[i] [j]为更短的路径长度。
• 选取第1个、第2个….顶点，直到所有顶点都被作为过中间顶点。
• 此时的A[i] [j] 为 i 顶点到 j 顶点的最短路径。

时间复杂度：$O(|V|^3)$，这与调用|V|次Dijkstra算法是一样的。

Floyd算法允许图中存在负权边，但是不允许存在负权边组成的回路。

public class Shortest_FLOYD {
    private boolean[][][]P;
    private int[][]D;
    public static final int INFINITY=Integer.MAX_VALUE;
    public void FLOYD(MGraph G) {
        int vexNum=G.getVexNum();
        P=new boolean[vexNum][vexNum][vexNum];
        D=new int[vexNum][vexNum];
        for (int v=0;v<vexNum;v++) {
            for (int w=0;w<vexNum;w++) {
                D[v][w]=G.getArcs()[v][w];
                for (int u=0;u<vexNum;u++) {
                    P[v][w][u]=false;
                }
                if(D[v][w]<INFINITY) {
                    P[v][w][v]=true;
                    P[v][w][w]=true;
                }
            }
        }
        for (int u=0;u<vexNum;u++) {
            for (int v=0;v<vexNum;v++) {
                for(int w=0;w<vexNum;w++) {
                    if(D[v][u]<INFINITY&&D[u][w]<INFINITY&&D[v][u]+D[u][w]<D[v][w]) {
                        D[v][w]=D[v][u]+D[u][w];
                        for (int i=0;i<vexNum;i++) {
                            P[v][w][i]=P[v][u][i]||P[u][w][i];
                        }
                    }
                }
            }
        }
    }
    public int[][] getD() {
        return D;
    }
    public boolean[][][] getP(){
        return P;
    }
}

拓扑排序

如果用DAG有向无环图表示一个工程，顶点V表示一个活动，边E表示两个活动的前后关系，那么这样的图叫作AOV网（Activities On Vertex）

为了防止图中出现环路，我们可以进行拓扑排序：

1. 从图中选择一个入度为0的顶点，将它和与之相关的边删除。
2. 重复上述过程，直到无法删除。
3. 此时，如果图为空，则不存在环路，否则存在环路。

也可以选取出度为0的定点删除，这叫做逆拓扑排序。

该算法可以应用在死锁检测等问题上。

如果一个图的邻接矩阵是三角矩阵，通常不存在环路，即存在拓扑序列。反之，如果一个图存在着有序的拓扑序列（前提是有序），则它的邻接矩阵必然是三角矩阵。

如果一个图中存在着顶点数目大于1的强连通分量（必然出现环路），则它必然不是有向无环图，也不存在拓扑序列。

一个唯一的拓扑序列，无法唯一地确定一个有向无环图。

public class TopoSort {
    public static int[] findInDegree(ALGraph G) throws Exception{
        int[] indegree=new int[G.getVexNum()];
        for (int i=0;i<G.getVexNum();i++) {
            for (ArcNode arc=G.getVexs()[i].firstArc;arc!=null;arc=arc.nextArc) {
                indegree[arc.adjVex]++;
            }
        }
        return indegree;
    }
    public static boolean topologicalSort(ALGraph G)throws Exception{
        int count=0;
        int[] indegree=findInDegree(G);
        LinkStack S=new LinkStack();
        for (int i=0;i<G.getVexNum();i++) {
            if (indegree[i]==0) {
                S.push(i);
            }
        }
        while(!S.isEmpty()) {
            int i=(Integer)S.pop();
            System.out.println(G.getVex(i).toString()+" ");
            count++;
            for (ArcNode arc=G.getVexs()[i].firstArc;arc!=null;arc=arc.nextArc) {
                indegree[arc.adjVex]--;
                if(indegree[arc.adjVex]==0) {
                    S.push(arc.adjVex);
                }
            }
        }
        if (count<indegree.length) {
            return false;
        }
        return true;
    }
}

关键路径

AOE网：用边表示活动。

关键路径：图上的源点到终点（某个汇点）的最大长度路径。一张有向无环图的关键路径可能有多条。

关键活动：所有关键路径上的活动。如果想要缩短工期，必须缩短所有关键路径共同的关键活动才行。

查找

基本概念

在数据集合中查找满足某种条件的数据元素的过程叫做查找。

用于查找的数据集合一般称为查找表。如果查找表不涉及插入和删除操作，那么我们一般称之为静态查找表，如果查找表涉及插入和删除操作，我们一般称之为动态查找表。

适用于静态查找表的一般是：顺序查找、折半查找，散列查找。

适用于动态查找表的一般是：二叉排序树、散列查找。（链式结构方便插入和删除数据）

关键字指的是数据元素中唯一标识该元素的数据项。

平均查找长度（ASL）指的是所有查找过程进行关键字比较的次数的平均值，它还和数据元素的查找频率有关。

顺序查找

一般线性表的顺序查找

对于一般的线性表的顺序查找，基本思想是从线性表的一端开始查找，逐个检查关键字是否满足给定的要求，如果遍历到线性表的另一端仍没有找到符合条件的数据元素，则说明查找失败。

通常情况下，我们还可以设置数组的第0号元素为哨兵元素，这样不必判断是否越界。

在各数据元素查找频率相等的条件下，ASL为$\frac{n+1}{2}$，时间复杂度为$O(n)$。

• 优点：对数据元素的存储方式无要求，顺序结构和链式结构均可。对数据元素的有序性也没有要求。
• 缺点：当n较大时，ASL较大，查找效率低。

有序线性表的顺序查找

有序顺序表的线性查找，可以让我们在查找失败时提前跳出，不用比较到表的另一端。

如果我们在升序的有序表arr中查找k，那么假如我们发现arr[i-1]小于k而arr[i]大于k，那么k一定不存在于该有序表中。

这样一来，查找不成功的ASL在数据元素查找概率相等的条件下，变为：
$$
ASL=\frac{n}{2}+\frac{n}{n+1}
$$
有序线性表的顺序查找，使用顺序存储或者链式存储均可。

二分查找

二分查找（折半查找），一般对数据结构的要求为：

• 有序
• 顺序表

二叉排序树本质上也是使用了二分查找的思想，但它属于链式结构，需要耗费一定的时间用于建立BST。

二分查找的基本思想：

• 将给定关键字与当前区间中间元素比较，如果相等，那么返回中间元素。
• 如果给定关键字大于中间元素，那么进入左半区间（升序，如果是降序是右半区间）继续查找。
• 如果给定关键字小于中间元素，那么进入右半区间（升序，如果是降序是左半区间）继续查找。
• 如此往复，直到找到为止。当区间长度小于0时（left>=right），说明查找失败。

二分查找的平均时间复杂度为$O(log_2n)$，求解ASL时，可以画出二分查找的判定树（平衡二叉树）用于判断。

二分查找也不是一定优于顺序查找的，假设给定的数据无序，那么二分查找还需要先耗费$O(nlog_2n)$的时间用于排序，当查找的次数较少时，这并不划算。

分块查找

分块查找又称索引顺序查找，它吸取了顺序查找和二分查找的优点，既有动态结构，也可以快速查找。

它的基本思想是：将数据元素分为若干个子块，块内元素可以无序，但块间是有序的。每一块的最大关键字小于下一块中的所有关键字。然后，建立一个索引表，索引表中存储每一块的最大关键字和对应块的首个元素起始位置。

分块查找时，先在索引表中进行二分或者顺序查找，再在块内进行顺序查找，总的ASL为二者之和。

B树和B+树

参考我的数据库博客https://hillzhang1999.gitee.io/2020/05/29/shu-ju-ku-fu-xi-ji-yu-mysql/，其中的Mysql索引一章介绍了B树和B+树在数据库中的应用。这两种数据结构主要都是为了进行外部查找（即数据存放在硬盘上），由于磁盘IO都是整块读入，所以要求查找树尽量“矮胖”，从而减少磁盘IO次数。

散列表HashTable

散列表（哈希表）是一种根据关键字直接访问的数据结构，它需要借助于散列函数，它建立了数据元素的关键字和存储地址之间的一一直接映射关系。

理想情况下，散列表的查找时间复杂度为$O(1)$，仅需一次哈希函数的计算即可。

散列函数（哈希函数）：一种把查找表中数据元素的的关键字映射为对应的地址的函数。即为Hash（key）=Addr

哈希表无法进行范围查找，因为数据元素之间没有逻辑关系。

散列函数的一个问题是：可能会把多个不同关键字映射到同一个存储地址，这种情况称为冲突（哈希碰撞）。这些发生碰撞的关键字称为同义词。一方面，我们要设计好的散列函数尽量减少冲突，另一方面，由于冲突难以完全避免，我们还要设计好处理冲突的方法。

常用散列函数

散列函数的设计原则：

• 散列函数的定义域依赖于所有需要存储的关键字，散列函数的值域依赖于存储地址的范围。
• 散列函数得到的地址应该等概率、均匀分布在存储地址空间上，以尽可能地避免冲突。
• 散列函数尽可能简单，以减少计算量，加快查找速度。

常用的散列函数有：

• 直接定址法：设计一个关键字的某个线性函数值作为散列地址，即H（key）= k * key + b。
  • 优点：计算简单，不会产生冲突。
  • 缺点：如果关键字不均匀分布，会浪费存储空间。
• 除留余数法：取一个不大于散列表长度m的最大质数p，H（key）= key % p。
  • 优点：计算简单，最常用
  • 缺点：需要选好除数p，尽可能让关键字均匀分布在地址空间上
• 数字分析法：如果关键字是r进制数，那么对r个数码进行分析，选取数码分布均匀的若干位作为散列地址。此方法适合于已知关键字集合的情况下，如果关键字集合改变，需要重新构造。
• 平方取中法：取关键字平方的中间几位作为散列地址。使散列地址取值与关键字的每一位均有关，适用于关键字每次取值都不均匀或者均小于散列地址所需要的位数。

散列函数的取法不是固定的，要结合具体的关键集合进行选择。

处理冲突的方法

开放定址法

开放定址法指的是可以存放新表项的空闲地址，即向能映射到该地址的同义词关键字开放，又向它的非同义词开放。也就是说，一个关键字最后的存储位置可能不位于它通过散列函数计算出的散列地址上。

主要类型有：

• 线性探测法：当发生冲突后，顺序查看表中下一个单元，直到找到一个空闲单元或者遍历全表。
  • 聚集（堆积）现象：此问题存在于线性探测法中，因为线性探测法很可能导致大量的数据元素在相邻的地址空间内争夺空闲空间，从而大大降低查找效率。（第i个占第i+1个，第i+1个再去占i+2个……）
• 平方探测法：当冲突发生后，每次递增$0^2,1^2,-1^2,2^2,-2^2…k^2,-k^2$，它要求表长必须是可以表示为4k+3的素数。这样做可以较好地减少堆积，但最多只能探测一半的单元。
• 再散列法（双散列法）：出现冲突后，通过提前设计的再散列函数进行二次散列，重新获得一个新的散列地址。
• 伪随机序列法：随机递增，进行二次查找。

使用开放地址法的哈希表中不能随便物理删除表中的数据元素，因为可能会切断其他具有相同散列元素的查找地址。除非每次删除都移动所有具有相同散列地址的元素。可以先做标记，将其逻辑删除，然后定期物理删除。

拉链法

拉链法又称链地址法，是目前比较常用的一种冲突处理方法，他的处理方式是将同义词存放在一个线性链表中，同义词链的头指针存放在散列表的单元中。

该方法适用于经常插入和删除的情况。（Java的hashmap）

散列表的性能

散列表虽然理性情况下是O（1）的查找时间复杂度，但实际情况下，由于冲突现象的存在，散列表的查找依然需要进行关键字和给定值的比较，所以，我们仍使用ASL平均查找长度衡量散列表的性能。

散列表的性能三大影响因素：

• 散列函数
• 处理冲突的方法
• 装填因子
  • 装填因子等于表中元素数除以表长。所以，哈希表的性能不直接依赖于表中的元素个数或者是表的长度，而依赖于装填因子。

排序

排序的稳定性：即关键字相同的元素的相对位置在排序前后不变。

内部排序：排序期间数据元素全部存放在内存中。

外部排序：排序期间，数据元素要在内存和外存中不断移动（往往是因为要排序的文件很大）

内部排序算法的基本操作主要为：比较和移动。但也有不基于比较的排序算法，例如基数排序等。

排序算法的总结可以看我的另一篇博文：https://hillzhang1999.gitee.io/2020/02/16/sort-algorithms/

选择排序算法需要考虑的因素：

• 待排序元素的数目
• 元素本身信息量大小（和移动次数有关）
• 元素关键字结构及其分布情况
• 稳定性要求
• 语言工具条件，存储结构和辅助空间大小。

排序算法小结：

• 若n较小，可以直接采用直接插入排序或者简单选择排序。如果记录本身信息量较大，那么适合使用简单选择排序，因为它的移动次数更少。
• 如果排序表基本有序，那么可以使用直接插入排序或者冒泡排序（$O(n)$的时间复杂度）
• 如果n较大，那么应该使用$O(nlog_2n)$时间复杂度的算法：
  • 快速排序：当关键字随机分布时，平均时间复杂度最低，目前是基于比较的内排序算法中最好的算法。如果关键字基本有序，则会退化为$O(n^2)$的时间复杂度。
  • 堆排序：快速排序需要借助$O(log_2n)$的辅助空间，而堆排序不需要辅助空间，且不存在快排的最坏情况。
  • 二路归并排序：快排和堆排序均不稳定，如果要稳定的话需要使用二路归并排序。
• 基于比较的排序算法，通过判定树的证明，最优情况下仍需$O(nlog_2n)$的时间复杂度。
• 当n很大，且关键字位数比较少，并且可以分解，可以采用基数排序，时间复杂度为$O(d(n+r))$，其中d是趟数，即关键字位数，r是基数。
• 当记录本身信息量很大，可以采用链表结构，以减少移动记录的消耗。