【墨尘の笔记】数据结构与算法

前言

仙人指路

[第一章]为入门，讲解数据结构是干什么的

[第二章]到第四章是数据结构基础，主要讲解链表，栈，队列，串等

[第五章]是二叉树

[第六章]是图,此章偏难，非考研或算法从业可粗略看

[第七章]到第八章是查找以及各种排序

[第九章]为补充，教材中没有的部分概念我随机补充上去

墨尘の话

本文内容主要参考王道考研，其中21版本咸鱼学长的课尚可，20版本比较枯燥,可选择性学习

浙大陈越姥姥的课比较精简且侧重于练习，能看懂且时间多的蛋疼可以看这个

因时间关系,后期比较匆促，本人也就是学着玩玩╮(╯▽╰)╭，可多参考链接自主学习

参考视频

2020 王道考研 数据结构 - B站

数据结构-浙江大学 - B站

第一章

1.1.1 数据机构的基本概念

1. 什么是数据结构

数据：信息的载体，是描述客观事务属性的数，字符，以及所有能输入到计算机种并被计算机程序识别和处理的符号集合

数据对象： 具有相通性质的数据元素的集合，是数据的一个子集

数据元素： 数据的基本单位，通常作为一个整体进行考虑和处理

数据项： 构成数据元素的不可分割的最小单位

举例：一群人，就是一个数据对象，每个人就是一个数据元素，他们的手，头等就是数据项

结构：数据中存在某种关联关系，称为结构

举例：小明是八年级一班中的学生，成绩为100

上例中小明和成绩是数据项，一班是数据元素，八年级是数据对象

2. 数据结构三要素

1. 逻辑结构

线性结构

线性结构： 数据元素是一对一的关系，除了第一个元素，所有都有唯一前驱（前面有一个节点）；除了最后一个元素，所有元素都有唯一后继（后面有一个节点）

非线性结构

集合： 一组元素属于同一个集合，除此外别无关系

树形结构： 数据元素之间是一对多的关系

图状结构： 数据元素之间是多对多的关系

2. 存储结构

顺序存储

顺序存储： 把逻辑上相邻的元素存储在物理位置也相邻的存储单元中，元素之间的关系靠存储单元的邻接关系体现

非顺序存储

链式存储： 逻辑上相邻的元素在物理位置上可以不相邻，借助元素存储地址的指针来表示元素之间的逻辑关系

索引存储： 在存储元素信息的同时，还建立附加的索引表。索引表中每项称为索引项，索引项一般为（关键字，地址）

散列存储： 根据元素的关键字直接计算出该元素的存储地址，又称哈希（Hash）存储

顺序存储便于查找，非顺序查找便于增删

3. 数据的运算

3. 概念

1.2.1 算法的基本概念

1. 什么是算法

程序 = 数据结构 + 算法

数据结构负责将现实世界的问题转化为信息，然后将信息存入计算机

算法是处理信息的步骤，负责将信息进行处理得到我们想要的结果

2. 算法的特性

1. 有穷性： 有限时间里可以执行完
2. 可行性： 可以用现有的操作实现算法

好算法的特性

1. 正确性：正确解决问题
2. 可读性：别人也能很清晰的看明白
3. 健壮性（鲁棒性）： 可以处理异常情况，比如非法数据等
4. 高效率： 省时间，省内存

3. 概念

1.2.2 时间复杂度

1. 如何评价算法的时间开销

1.和机器性能相关，诸如超级计算机 vs 单片机

2.和编程语言相关，越高级的语言效率越低

3.和编译程序产生的机器指令相关

4.有些算法是不能事后统计的

通常情况机器性能和编程语言无法改变，因此考虑如何优化程序性能即可

时间开销与问题规模n之间的关系

2. 如何计算

一般指代循环/迭代，循环的次数越多时间复杂度越高（参考下图）

3. 三种复杂度

1.最坏时间复杂度： 考虑最坏的情况

2.平均时间复杂度： 考虑所有输入情况都处于同等概率

3.最好时间复杂度： 考虑最好的情况

评定一个算法的时间复杂度好坏通常要拿最坏情况去考虑

4. 概念

1.2.3 空间复杂度

通俗理解：每个变量都会在内存中开辟一个新的空间，因此基于空间复杂度优化变量越少越好，递归尤甚

内存开销与问题规模n之间的关系

基于现在计算机内存来讲，通常我们只需要考虑时间复杂度，空间复杂度无需作为首选考虑

1. 概念

第二章

2.1 线性表的定义的基本操作

1. 线性表的定义

线性表是具有相同数据类型的n（n >= 0）个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表

2. 线性表的基本操作

// 初始化表。构造一个空的线性表L，分配内存空间
InitList(L); 
// 销毁操作。销毁线性表，并释放线性表L所占用的内存空间
DestroyList(L); 

// 插入操作。在表L中第i个位置上插入指定元素e
ListInsert(L, i ,e);
// 删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值
ListDelete(L, i ,e);

// 按值查找操作。在表L中查找具有给定关键字值的元素。
LocateElem(L, e);
// 按位查找操作。获取表L中第i个位置的元素的值。
GetElem(L, i);

// 其他常用操作

// 求表长。返回线性表L的所有元素值。
Length(L);
// 输出操作。按前后顺序输出线性表L的所有元素值。
PrintList(L);
// 判空操作。若L为空表，则返回true，否则返回false
Empty(L);

Tips:

1.对数据的操作（分析思路） —— 创销，增删改查（适用于所有数据结构）

2.java函数的定义 —— <返回值类型> 函数名（<参数1类型> 参数1，<参数2类型> 参数2，…）

3.实际开发中，可根据实际需求定义其他的基本操作（输出，判空等）

4.函数名和参数的形式，命名都可改变（Reference: 严蔚敏版《数据结构与算法》）

概念

2.2.1 顺序表的定义

1. 顺序表的定义

用顺序存储的方式实现线性表

顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现

2. 顺序表的特点

​ 优点

1. 随机访问，既可以在O(1)时间内找到第一个元素

2. 存储密度高，每个节点只存储数据元素

   缺点

3. 拓展容量不方便（采用动态分配时间复杂度较高）

4. 插入，删除不方便，需要移动大量元素

3. 概念

注：图上所示函数均为c语言中动态分配相关函数，可根据自身情况选择性学习

代码在2.2.2.2 顺序表的查找一节

2.2.2.1 顺序表的插入删除

概念

2.2.2.2 顺序表的查找

/**
 * @Description: 顺序表
 * @author: HouBo
 * @Date: 2020/11/26 17:52
 */
public class SqList {

    static final int MAXSIZE = 10; // 最大长度
    int data[] = new int[MAXSIZE]; // 使用静态数组存放数据
    int length;  // 顺序表的当前长度

    // 初始化一个顺序表
    void initList(SqList L){
        L.length = 8; // 初始长度为0
    }

    // 添加一个数据
    boolean listInsert(SqList L, int i, int e){
        if(i < 1 || i > L.length + 1){ // 当前i的值是否有效
            return false;
        }
        if(L.length == MAXSIZE){ // 当前存储空间是否充盈
            return false;
        }
        for(int j = L.length; j >= i; j--){ // 将第i个元素之后的元素后移
            L.data[j] = L.data[j - 1];
            L.data[j - 1] = e; // 在位置i处放入e
        }
        L.length++; // 长度+1
        return true;
    }

    // 删除一个数据
    boolean listDelete(SqList L, int i, int e){
        if(i < 1 || i > L.length + 1){ // 当前i的值是否有效
            return false;
        }
        e = L.data[i - 1];
        for(int j = i; j <= L.length; j++){ // 将第i个元素之后的元素后移
            L.data[j - 1] = L.data[j]; // 在位置i处放入e
        }
        L.length--; // 长度-1
        return true;
    }
    
    // 按位查找
    int getElem(SqList L, int i){
        if(i < 1 || i > L.length + 1){
            return 0;
        }
        return L.data[i - 1];
    }

    // 按值查找
    int locateElem(SqList L, int e){
        for(int i = 0; i < L.length; i++){
            if(L.data[i] == e){
                return i + 1;
            }
        }
        return 0;
    }
}

此段代码非最优解，仅作练习使用

概念

2.3.1 单链表的定义

1. 什么是单链表

相对于顺序表，单链表除了存储数据元素外，还需要存储指向下一个节点的指针

2. 单链表和顺序表的不同

	顺序表	单链表
优点	随机存取，存储密度高	不要求大片连续空间，改变容量方便
缺点	要求大片连续空间，改变容量不方便	不可随机存取，要耗费一定空间存放指针

带头结点和不带头结点的区别

创立第一个结点，既为带头结点，反之则为不带

不带头结点，对第一个数据结点和后续数据结点的处理需要用不用的代码逻辑，空表和非空表的处理同理

带头结点通常情况下优于不带

概念

代码放在2.3.2.3 单链表的建立一节中

2.3.2.1 单链表的插入删除

此章中，p通过代指当前结点，s指新插入的结点, a1指下一个结点, e指新值

1.1 按位序插入(带头结点)

思路：插入结点打断链表，上一个结点挂到它身上（指向它），它挂到下一个结点身上。

链表插入删除操作和顺序表相比相对复杂，需多多思考。

1.2 按位序插入（不带头结点）

不带头结点第一个结点需要做特殊处理，创建一个s，将第a1挂到它身上。

2. 指定结点的后插操作

a1挂到s身上，s挂到p身上。

3. 指定结点的前插操作

由于无法直接获取p的上一个结点，因此可采用如下方法实现:

思路：将p变更为s, s变更为p

实现：p的值赋给s，新值e赋给p

4. 按位序删除

思路：找到要删除的结点，断开它并释放空间

5. 指定结点的删除

思路：同上

实现：将p的值和下一个引用都指向下一个，实现删除p的效果

此处如果p是最后一个结点，将会出现异常

单链表的局限性：无法逆向检索，不方便

6. 概念

2.3.2.2 单链表的查找

概念

2.3.2.3 单链表的建立

思路：遍历所有结点，通过头插或者尾插的方式实现循环建立一个单链表。

头插法可以实现反转链表，注意这是个重点

代码

/**
 * @Description: 结点
 * @Author: MoChen
 */
public class HNode {

    public HNode(){

    }

    public HNode(int data){
        this.data = data;
    }

    // 数据
    int data;
    // 下一个结点
    HNode next;
}

/**
 * @Description: 单链表
 * @Author: MoChen
 */
public class HLinkerList {

    // 链表的头结点
    HNode head = null;

    // 初始化一个空链表
    boolean InitList(HLinkerList L){
        L.head = new HNode(); // 分配一个头结点,如果不带头结点此处直接赋空
        L.head.next = null; // 头结点之后暂时没有结点
        return true;
    }

    // 在第i个位置插入元素e
    boolean ListInsert(HLinkerList L, int i, int e) {
        if(i < 1) {
            return false;
        }
        // 以下代码段为不带头结点的操作
//        if(i == 1) { // 插入第一个结点的操作与其他结点操作不同
//            HNode s = new HNode();
//            s.data = e;
//            s.next = L.head.next;
//            L.head = s; // 头指针指向新结点
//        }
//        HNode p; // 指针p向前扫描到的结点
//        int j = 0; // 当前p指向的是第几个结点，不带的话此处赋1
//        p = L.head; // L指向头结点，头结点是第0个结点
//        while (p != null && j < i - 1) { // 循环找到 i - 1 个结点
//            p = p.next;
//            j++;
//        }
        HNode p = GetElem(L, i - 1);

//        if(p == null){ // i值不合法
//            return false;
//        }
//        HNode s = new HNode();
//        s.data = e;
//        s.next = p.next;
//        p.next = s; // 将结点s连到p之后
//        return true; // 插入成功

        return InsertNextNode(p, e);
    }

    // 后插操作：在p结点之后插入元素e
    boolean InsertNextNode(HNode p, int e){
        if(p == null){
            return false;
        }
        HNode s = new HNode();
        s.data = e; // 新结点s存储数据e
        s.next = p.next;
        p.next = s; // 新结点s挂到p身上
        return true;
    }

    // 前插操作：在p结点之前插入元素e
    boolean InsertPriorNode(HNode p, int e){
        if(p == null){
            return false;
        }
        HNode s = new HNode();
        s.next = p.next;
        p.next = s; // 新结点s挂到p身上
        s.data = p.data; // 将p里面的元素复制到s中
        p.data = e; // p中的元素覆盖为e
        return true;
    }

    // 按位序删除
    boolean ListDelete(HLinkerList L, int i, int e){
        if(i < 1){
            return false;
        }
//        HNode p; // 指针p向前扫描到的结点
//        int j = 0; // 当前p指向的是第几个结点，不带的话此处赋1
//        p = L.head; // L指向头结点，头结点是第0个结点
//        while (p != null && j < i - 1) { // 循环找到 i - 1 个结点
//            p = p.next;
//            j++;
//        }
        HNode p = GetElem(L, i - 1);

        if(p == null){ // i值不合法
            return false;
        }
        if(p.next == null){ // 第i - 1个结点后面已无其他结点
            return false;
        }
//        HNode q = p.next; // 令q指向被删除的结点
//        e = q.data; // 用e返回元素的值
//        p.next = q.next; // 将q结点从链中断开
//        return true; // 删除成功

        return DeleteNode(p);
    }

    // 删除指定结点p
    boolean DeleteNode(HNode p){
        if(p == null){
            return false;
        }
        HNode q = p.next; // 令q指向p的后继结点
        p.data = p.next.data; // 和后继结点交换数据域
        p.next = q.next; // 将q结点从链中断开
        return true;
    }

    // 按位查找，返回第i个元素
    HNode GetElem(HLinkerList L, int i){
        if(i < 0){
            return null;
        }
        HNode p; // 指针p向前扫描到的结点
        int j = 0; // 当前p指向的是第几个结点，不带的话此处赋1
        p = L.head; // L指向头结点，头结点是第0个结点
        while (p != null && j < i) { // 循环找到 i 个结点
            p = p.next;
            j++;
        }
        return p;
    }

    // 按值查找
    HNode LocateElem(HLinkerList L, int e){
        HNode p = L.head.next;
        // 从第一个结点开始查找数据域为e的结点
        while(p != null && p.data != e){
            p = p.next;
        }
        return p; // 找到后返回该结点，否则返回null
    }

    // 求表的长度
    int Length(HLinkerList L){
        int len = 0;
        HNode p = L.head;
        while(p.next != null){
            p = p.next;
            System.out.println("链表第" + len + "个数据:" + p.data);
            len++;
        }
        return len;
    }
}

此段代码非最优解，仅作练习使用

2.3.3 双链表

下文中，s指代新结点，p指代当前结点，q指代下一个结点

1. 双链表和单链表的概念

单链表：无法逆向检索，有时候不太方便

双链表：可进可退，存储密度更低

双链表整体和单链表差距不大，额外新增了一个指向上一个结点的处理

2. 双链表的插入

思路：和单链表同理，额外增加了prior的处理

① q挂到s身上

② q的prior指向s

③ s的prior指向p

④ s挂到p身上

如果q不存在，第二步需省略

3. 双链表的删除

① q的下一个结点挂到p身上

② q的下一个结点的prior指向p

代码

/**
 * @Description: 结点（双链表）
 * @Author: MoChen
 */
public class HDNode {
    public HDNode(){

    }

    public HDNode(int data){
        this.data = data;
    }

    // 数据
    int data;
    // 下一个结点
    HDNode next;
    // 上一个结点
    HDNode prior;
}

/**
 * @Description: 双链表
 * @Author: MoChen
 */
public class HDLinkedList {

    // 链表的头结点
    HDNode head = null;

    // 初始化一个空链表
    boolean InitList(HDLinkedList L){
        L.head = new HDNode(); // 分配一个头结点,如果不带头结点此处直接赋空
        L.head.prior = null; // 头结点的prior永远指向空
        L.head.next = null; // 头结点之后暂时没有结点
        return true;
    }

    // 在p结点之后插入s结点
    boolean InsertNextHDNode(HDNode p, HDNode s){
        if(p == null || s == null){ // 非法参数
            return false;
        }
        s.next = p.next;
        if(p.next != null){ // 如果p后面有结点
            p.next.prior = s;
        }
        s.prior = p;
        p.next = s;
        return true;
    }

    // 删除p结点的后继结点
    boolean DeleteNextNode(HDNode p){
        if(p == null){
            return false;
        }
        HDNode q = p.next; // 找到p的后继结点q
        if(q == null){
            return false; // p没有后继
        }
        p.next = q.next;
        if(q.next != null){ // q结点不是最后一个结点
            q.next.prior = p;
        }
        return true;
    }

    // 求表的长度
    int Length(HDLinkedList L){
        int len = 0;
        HDNode p = L.head;
        while(p.next != null){
            p = p.next;
            System.out.println("链表第" + len + "个数据:" + p.data);
            len++;
        }
        return len;
    }
}

概念

2.3.4 循环链表

1. 循环链表与普通链表的不同

循环链表的尾结点的指针指向头结点，而普通链表的尾结点指向空。

通常我们无法获取之前的结点，除非拿到头结点，循环单链表可以通过遍历结点的方式从而拿到自己想要的结点。

以前在增加/删除操作时，需要给最后一个结点判空，现在则不需要。

2. 循环双链表

表头的prior指向表尾，表尾的next指向表头。

概念

2.3.5 静态链表

1. 什么是静态链表

单链表：各个结点在内存中随意散落。

静态链表：分配一整片连续的内存空间，各个结点集中安置。

2. 静态链表的概念

静态链表就是用数组的方式实现的链表。

容量固定不可变

本章内容不是很重要，了解其概念即可。

2.3.6 顺序表和链表的比较

1. 线性结构

都属于线性结构

2. 存储结构

	顺序表	单链表
优点	随机存取，存储密度高	不要求大片连续空间，改变容量方便
缺点	要求大片连续空间，改变容量不方便	不可随机存取，要耗费一定空间存放指针

3. 基本操作

操作	顺序表	链表
创	需要分配大片连续空间。若分配空间过小，则之后不方便扩展；若分配空间过大，则浪费内存资源	只需分配一个头结点（也可不分配），方便扩展
销	长度赋0即可，本笔记采用java实现，因此无需考虑内存问题，如果使用c实现则需要通过free函数释放内存	依次删除每个结点
增，删	插入/删除元素都要将后续元素全部后移/前移 时间复杂度O(n),时间开销主要来自移动元素	插入/删除元素只需修改指针即可 时间复杂度O(n),时间开销主要来自查找元素
查	按位查找：O(1)	按值查找：O(n)

4. 概念

表长无法预估，需要经常进行增/删操作，可使用链表

表长可预估，需要经常进行查询操作，可使用顺序表

第三章

3.1.1 栈的基本概念

1. 栈（Stack）的概念

栈是只允许在一端进行插入或删除的线性表

重要术语：栈顶，栈底，空栈

特点：后进先出（Last In First Out）LIFO

2. 栈的基本操作

InitStack(S); // 初始化栈。构造一个空栈，分配内存空间。
DestroyStack(L); // 销毁栈。销毁并释放栈s所占用的内存空间。

Push(S, x); // 进栈，若栈S未满，则将x加入使之成为新栈顶。
Pop(S, x); // 出栈，若栈S非空，则弹出栈顶元素，并用x返回。

GetTop(S, x); // 读栈顶元素。若栈S非空，则用x返回栈顶元素。

// 其他常用操作
StackEmpty(S); // 判断一个栈是否为空

概念

3.1.2 栈的顺序存储实现

思路

给定一个静态数组，每次操作头或者尾即可

指针用于操纵当前数据

代码

/**
 * @Description: 顺序存储实现栈
 * @Author: MoChen
 */
public class HSqStack {

    final int MAXSIZE = 10; // 定义栈中元素的最大个数

    int[] data; // 静态数组中放栈中元素

    int top; // 栈顶指针

    HSqStack(){
        data = new int[MAXSIZE];
    }

    // 初始化栈
    void InitStack(){
        top = -1; // 此处如果指向0，则预示已经有一个参数了，所以初始化指向-1
    }

    // 判断栈空
    boolean StackEmpty(){
        return top == -1;
    }

    // 入栈
    boolean Push(int x){
        if(top == MAXSIZE - 1){ // 栈满
            return false;
        }
        top++; // 指针上移一位
        data[top] = x; // 新元素入栈
        return true;
    }

    // 出栈
    boolean Pop(int x){
        if(top ==  - 1){ // 空栈
            return false;
        }
        x = data[top]; // 栈顶元素先出栈
        top--; // 指针下移
        return true;
    }

    // 读取栈顶元素
    int GetTop(int x){
        if(top ==  - 1){ // 空栈
            return -1;
        }
        x = data[top]; // 读取栈顶元素
        return x;
    }
}

概念

3.1.3 栈的链式存储实现

用链表的方式实现栈几乎等同于单链表，此处直接套用单链表即可

3.2.1 队列的基本概念

1. 什么是队列

栈（Stack）是只允许在一端进行插入或删除的线性表

队列（Queue）是只允许在一端插入,在另一端删除的线性表

队列的特点：先进先出 First In First Out (FIFO)

2. 队列的基本操作

InitQueue(Q); // 初始化队列，构造一个空队列Q
DestroyQueue(Q); // 销毁队列，销毁并释放队列Q所占用的空间

EnQueue(Q, x); // 入队，若队列Q未满，将x加入，使之成为新的队尾
DeQueue(Q, x); // 出队，若队列Q非空，删除队头元素，并用x返回

GetHead(Q, x); // 读队头元素，对队列Q非空，则将队头元素赋值给x
QueueEmpty(Q); // 判断队列是否为空

概念

3.2.2 队列的顺序实现

要点

求队列一共有多少个元素的算法如下：

// 尾指针 + 长度 - 头指针 % 长度
(rear + MAX_SIZE - front) % MAX_SIZE

头尾指针均为长度以内任意一个数字，因此想要求差必须先加上最大长度

尾指针和头指针位置可调换

概念上不会大于长度，保证代码健全性加上模运算

代码

/**
 * @Description: 顺序队列
 * @Author: MoChen
 */
public class HSqQueue{

    private static class SqQueue{
        private final int MAX_SIZE = 10;
        int[] data; // 静态数组存放元素
        int front, rear; // 队头指针和队尾指针

        public SqQueue(){
            data = new int[MAX_SIZE];
        }
    }

    private SqQueue Q;

    // 初始化队列
    void initQueue(){
        Q = new SqQueue();
        Q.front = Q.rear = 0; // 初始时，队头队尾全部指向空
    }

    // 判断队列是否为空
    boolean queueEmpty(){
        return Q.front == Q.rear; // 当队头队尾指向一样时，则意味队列为空
    }

    // 入队
    boolean enQueue(int x){
        if((Q.rear + 1) % Q.MAX_SIZE == Q.front){ // 如果队头的指针的下一位指向队尾，则表示队满
            return false;
        }
        Q.data[Q.rear] = x;
        Q.rear = (Q.rear + 1) % Q.MAX_SIZE; // 队尾指针+1取模，保证指针不会超过长度
        return true;
    }

    // 出队
    boolean deQueue(){
        if(Q.front == Q.rear){ // 队列为空
            return false;
        }
        Q.data[Q.front] = -1;
        Q.front = (Q.rear + 1) % Q.MAX_SIZE; // 队尾指针+1取模，保证指针不会超过长度
        return true;
    }

    // 获取队头元素
    int getHead(){
        if(Q.front == Q.rear){ // 队列为空
            return -1;
        }
        int x = Q.data[Q.front];
        return x;
    }

    // 获取队列长度
    int queueLength(){
        return (Q.rear + Q.MAX_SIZE - Q.front) % Q.MAX_SIZE;
    }
}

代码不完善，仅作练习使用

概念

3.2.3 队列的链式实现

概念

链式无需考虑内存

代码

/**
 * @Description: 链式队列
 * @Author: MoChen
 */
public class HLinkQueue {

    private class LinkNode{
        int data;
        LinkNode next;

        public LinkNode(){}

        public LinkNode(int data) {
            this.data = data;
        }
    }

    private class LinkQueue{
        LinkNode front, rear;
    }

    private LinkQueue Q;

    // 初始化队列
    void initQueue(){
        // 初始时，front,rear都指向头结点
        Q.front = Q.rear = new LinkNode();
        // 不带头结点的话front和rear都要指向空
        Q.front.next = null;
    }

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

    // 入队
    boolean enQueue(int x){
        LinkNode s = new LinkNode(x);
        s.next = null;
        // 如果不带头结点则front需要进行非空判断，为空则修改表头指针
        Q.rear.next = s; // 新结点挂到rear身上
        Q.rear = s; // 修改表尾指针
        return true;
    }

    // 出队
    boolean deQueue(){
        if(Q.rear == Q.front){ // 空队列
            return false;
        }
        LinkNode p = Q.front.next;
        Q.front.next = p.next; // 修改头结点的next指针
        if(Q.rear == p){ // 如果是最后一个结点
            Q.rear = Q.front;
        }
        return true;
    }
}

概念

3.2.4 双端队列

概念

栈：单端插入和删除的线性表

队列：一端插入，另一端删除的线性表

双端队列：两端插入，两端删除的线性表

双端队列包含输入受限和输出受限两种情况，不同情况具有不同局限性，需根据情况选择

概念

3.3.1 栈在括号匹配中的应用

示例：

一组括号，求出它们能不能完成匹配

思路：

使用栈，将左括号压入，如果遇到右括号就压出，遇到无法匹配的括号或者匹配结束栈里还有值则匹配失败

代码

/**
 * @Description: 给定一组括号，判断这组括号能否完成匹配
 * @Author: MoChen
 */
public class Brancket {

    static String bracketStr = "({}{})";

    public static void main(String[] args) {
        System.out.println(bracketCheck(bracketStr));
    }

    static boolean bracketCheck(String bracketStr){
        char[] data = new char[bracketStr.length()]; // 栈元素
        int top = 0; // 栈顶指针
        char[] strs = bracketStr.toCharArray();
        for(int i = 0; i < strs.length; i++){
            if(strs[i] == '[' || strs[i] == '{' || strs[i] == '('){ // 扫描到左括号，入栈
                data[++top] = strs[i];
            }else{
                if(top == 0){ // 扫描到右括号且当前栈空,匹配失败
                    return false;
                }
                char topElem = data[top--]; // 栈顶元素出栈
                // 进行匹配，如果匹配失败则返回false
                if(strs[i] == ')' && topElem != '('){
                    return false;
                }
                if(strs[i] == ']' && topElem != '['){
                    return false;
                }
                if(strs[i] == '}' && topElem != '{'){
                    return false;
                }
            }
        }
        return top == 0; // 括号校验完成且栈空则匹配成功
    }
}

3.3.2 栈在表达式求值中的应用（上）

三种表达式的不同

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fcNMwH0u-1618913822522)(https://i.loli.net/2021/02/01/2GOCL9hukZWgNse.png)]

中缀表达式

运算符在中间，既为我们常用的数学表达式

后缀表达式

运算符在后面，又叫逆波兰表达式（Reverse Polish notation）

前缀表达式

运算符在前面，因为是波兰人提出，所以又叫波兰表达式（Polish notation）

中缀表达式	后缀表达式	前缀表达式
a + b	ab +	+ ab
a + b - c	a b + c -	- + ab c
a + b - c * d	ab + cd * -	- + ab * cd

核心思想还是一个计算区间一块区域，诸如(a + b) - (c * d) = （ab+）(cd*) -

中缀转后缀

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UCf07h9Q-1618913822523)(https://i.loli.net/2021/02/01/t2GmHCKyBF59gvq.png)]

左优先原则：只要左边的运算符能先计算，就先计算左边的

后缀表达式的手算方法

从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应操作，合并为一个操作数

对于计算机而言，后缀表达式的效率往往要更高

中缀表达式转前缀表达式

右优先原则：只要右边的操作符能先计算，就优先计算右边的

中缀
A + B * (C - D) - E / F
常规计算
- + A * B - C D / E F
右优先
+ A - * B - C D / E F

后缀表达式的机算方法

① 从左到右扫描下一个元素，直到处理完所有元素

② 若扫描到操作数则入栈

③ 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果入栈

概念

3.3.2 栈在表达式求值中的应用（下）

中缀转后缀

① 遇到操作数，直接加入后缀表达式

② 遇到界限符。遇到 ( 直接入栈，遇到 ) 则依次弹出栈内运算符并加入后缀表达式，直到弹出 ( 为止。注意（ 不加后缀

③ 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到 ( 或栈空则停止。之后再将当前运算符入栈。

中缀的计算

中缀转后缀 + 后缀求值

① 初始化两个栈，操作数栈和运算符栈

② 若扫描到操作数，压入操作数栈

③ 若扫描到运算符或界限符，则按照‘中缀转后缀’相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要在弹出两个操作数栈的栈顶元素并执行相应运算，运算结果在压回操作数栈）

代码

因时间原因，此处仅列出中转后和后计算

import java.util.Stack;
import java.util.regex.Pattern;

/**
 * @Description: 后缀表达式
 * @Author: MoChen
 */
public class PolishNotation {

    // 中缀表达式
    private static String notation = "((15 / (7 - (1 + 1))) * 3) - (2 + (1 + 1))";
    // 后缀表达式
    private static String poNotation = "15 7 1 1 + - / 3 * 2 1 1 + + -";
    // 前缀表达式
    private static String rpoNotation = "- * / 15 - 7 + 1 1 3 + 2 + 1 1";
    // 10的倍数
    private static int[] exactNums = {10, 100, 1000, 10000, 100000};

    public static void main(String[] args) {
        System.out.println("中计算：" + countNum(notation));
        System.out.println("中转后：" + commTransRpo(notation));
        System.out.println("后计算：" + poCount(poNotation));
    }

    /**
     * 中缀转后缀
     */
    static String commTransRpo(String notation){
        StringBuilder str = new StringBuilder();
        Stack<Character> stack = new Stack<>();
        char[] chars = notation.toCharArray();

        for(int i = 0; i < chars.length; i++){
            if(isInteger(chars[i] + "")){
                int j = 1;
                int num = Integer.parseInt(chars[i] + "");
                while(isInteger(chars[i + j] + "")){
                    num = Integer.parseInt(num + "" + chars[i + j] + "");
                    j++;
                }
                i += j - 1;
                str.append(num).append(" ");
            }else if(chars[i] != ' '){
                if(chars[i] == '('){
                    stack.push(chars[i]);
                }else if(chars[i] == ')' && !stack.empty()){
                    char pop = stack.pop();
                    while(pop != '('){
                        str.append(pop + " ");
                        pop = stack.pop();
                    }
                }else{
                    switch (chars[i]){
                        case '+':
                        case '-':
                            if(!stack.empty() && stack.peek() != '('){
                                while(!stack.empty()){
                                    char pop = stack.pop();
                                    if(pop != '(' && pop != ')'){
                                        str.append(pop + " ");
                                    }
                                }
                            }else{
                                stack.push(chars[i]);
                            }
                            break;
                        case '*':
                        case '/':
                            if(!stack.empty() && stack.peek() != '(' && stack.peek() != '-' && stack.peek() != '+'){
                                while(!stack.empty()){
                                    char pop = stack.pop();
                                    if(pop != '(' && pop != ')'){
                                        str.append(pop + " ");
                                    }
                                }
                            }else{
                                stack.push(chars[i]);
                            }
                            break;
                    }
                }
            }
        }
        while(!stack.empty()){
            str.append(stack.pop());
        }
        return str.toString();
    }

    /**
     * 后缀计算
     */
    static Integer poCount(String notation){
        int res = 0;
        Stack<Integer> stack = new Stack<>();
        char[] chars = notation.toCharArray();
        boolean count = false;

        for(int i = 0; i < chars.length; i++){
            if(isInteger(chars[i] + "")){
                int j = 1;
                int num = Integer.parseInt(chars[i] + "");
                while(isInteger(chars[i + j] + "")){
                    num = Integer.parseInt(num + "" + chars[i + j] + "");
                    j++;
                }
                i += j - 1;
                stack.push(num);
            }else if(chars[i] != ' '){
                int temp = stack.pop();
                switch (chars[i]){
                    case '+':
                        stack.push(stack.pop() + temp);
                        break;
                    case '-':
                        stack.push(stack.pop() - temp);
                        break;
                    case '*':
                        stack.push(stack.pop() * temp);
                        break;
                    case '/':
                        stack.push(stack.pop() / temp);
                        break;
                }
            }
        }
        res = stack.pop();
        return res;
    }

    /**
     * 求和（中缀）
     */
    static Integer countNum(String notation){
        return poCount(commTransRpo(notation));
    }

    /**
     * 判断一个字符是否为Integer
     */
    public static boolean isInteger(String str) {
        Pattern pattern = Pattern.compile("[0-9]*");
        return pattern.matcher(str).matches();
    }
}

3.3.3 栈在递归中的应用

什么问题适合用递归算法解决

可以把原始问题转换为属性相同，但规模较小的问题

概念

3.3.4 队列的应用

队列在操作系统中的应用

多个进程争抢着使用有限的系统资源时，FCFS(First Come First Service, 先来先服务)是一种常用策略

3.4 特殊矩阵的压缩存储

一维数组存储结构

各数组元素大小相同，且物理上连续存放

LOC + i * sizeof(ElemType)

除特殊说明，否则数组下标默认从0开始

二维数组存储结构

M行N列的二位数组b[M][N]中，若按行优先存储，则b[i][j]的存储地址
LOC + (i * N + j) * sizeof(elemeType)

M行N列的二位数组b[M][N]中，若按列优先存储，则b[i][j]的存储地址
LOC + (j * M + i) * sizeof(elemeType)

思路：无论行列优先，从起始地址遍历到当前元素即可得到存储地址

对称矩阵

若n阶方阵中任意一个元素a i,j 都有 a i, j = a j, ,则该矩阵称为对称矩阵

策略：只存储主对角线+下三角区

使用一维数组存储，则取值为:
行优先：先根据i值求出上面有几行，在根据j值求出在当前行的位置

列优先：同上，将位置调换即可

三角矩阵

下三角矩阵：除了主对角线和下三角区，其余都相同

上三角矩阵：除了主对角线和上三角区，其余都相同

存储策略：将中线和三角区按照行优先存入，最后一个位置存放常量c

三对角矩阵

又称带状矩阵，既中线周围一圈都有值，其余皆为0

首行和尾行是两个，其余都是三个

稀疏矩阵

非零元素远远少于矩阵元素的个数，且无规则分布

存储策略一：顺序存储

三元组 <行，列，值>

此处行列从1开始

存储策略二：十字链表法

概念

第四章

4.2.1 串的定义和基本操作

串的定义

串，既字符串(String)是由零个或多个字符组成的有限序列。

举例：

S = “Hello World!”
T = ‘iPhone 1 Pro Max?’

子串：串中任意个连续的字符组成的子序列 Eg : ‘iPhone’,'Pro M’是串的子串

主串：包含子串的串。 Eg : T是子串’iPhone’的主串

字符在主串中的位置:字符在串中的序号。 Eg:'1’在T中的位置是8

子串在主串中的位置:子串的第一个字符在主串中的位置 Eg:'11 Pro’在T中的位置是8

操作

StrAssign(T, chars); // 赋值操作。将chars的值赋给T
StrCopy(T, S); // 赋值操作。将串S复制给串T
StrEmpty(S); // 判空操作。若S为空串，则返回true，否则返回false
StrLength(S); // 求串长。返回串S的元素个数.
ClearString(S); // 清空操作。将S清为空串
DestoryString(S); // 销毁串。将串S销毁
Concat(T, S1, S2); // 串链接。由T返回由S1和S2连接而成的新串
SubString(Sub, S, pos, len); // 求子串。用Sub返回S中从pos开始到len的子串
Index(S, T); // 定位操作。若主串S中存在与T相同的子串，则返回一个字符的位置，否则返回0
StrCompare(S, T); // 比较操作。若S>T，则返回值>0，S<T则返回值<0,S=T则返回0

概念

4.1.2 串的存储结构

概念

4.2.1 串的朴素模式匹配

思路

在主串中找到模式串相同的子串

因该算法思路简单了然，故叫朴素模式匹配

最好时间复杂度	O（m）
常规时间复杂度	O（n）
最坏时间复杂度	O (nm)

概念

4.2.2 KMP算法（上）

什么是KMP算法

朴素模式匹配的优化

由三个人提出，各取名字中一个字母，因此叫KMP算法

朴素模式匹配的缺点

当某些子串与模式串能部分匹配时，主串的扫描指针i经常回溯，导致时间开销增加

4.2.3 KMP算法（下）

学不会，等我学会了再来补充

4.2.4 KMP算法的进一步

同上

第五章

5.1 树的基本概念

什么是树

树是 n (n >= 0) 个结点的有限集合，n = 0 时，称为空树。

而任意非空树应该满足:

1.有且仅有一个特定的称为根的结点。

2.当 n > 1时，其余结点可分为 m (m > 0) 个互不相交的有限集合，其中每一个集合本身又是一棵树，称为根节点的子树。

基本术语

1. 节点的度：一个节点含有的子树的个数称为该节点的度；
2. 树的度：一棵树中，最大的节点度称为树的度；
3. 叶节点或终端节点：度为零的节点；
4. 非终端节点或分支节点：度不为零的节点；
5. 父亲节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
6. 孩子节点：一个节点含有的子树的根节点称为该节点的子节点；
7. 兄弟节点：具有相同父节点的节点互称为兄弟节点；
8. 层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
9. 深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0；
10. 高度：对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0；
11. 堂兄弟节点：父节点在同一层的节点互为堂兄弟；
12. 节点的祖先：从根到该节点所经分支上的所有节点；
13. 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
14. 森林：由m（m>=0）棵互不相交的树的集合称为森林。

树的种类

• 无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树；
• 有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；
• 二叉树：每个节点最多含有两个子树的树称为二叉树；
• 完全二叉树：对于一颗二叉树，假设其深度为d（d>1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树；
• 满二叉树：所有叶节点都在最底层的完全二叉树；
• 平衡二叉树（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；
• 排序二叉树(二叉查找树（英语：Binary Search Tree))：也称二叉搜索树、有序二叉树；
• 霍夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树；
• B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多于两个子树。

5.2.1 二叉树的概念

什么是二叉树

二叉树是n（n>=0）个结点的有限集合。

1. n = 0 时，二叉树为空；
2. n > 0 时，由根节点和两个互不相交的左右子树组成。左右子树也分别是一颗二叉树。

二叉树与度为2的有序树的区别

二叉树	度为2的有序树
可以为空	至少有三个结点
子结点始终有左右之分	子结点次序相对

满二叉树

一颗高度为h，且含有2h - 1个结点的二叉树称为满二叉树

完全二叉树

相对于满二叉树，完全二叉树最后一层可以缺少结点或叶子

二叉排序树

对任意结点而言，左子树关键字均小于该结点，右子树关键字均大于该结点

平衡二叉树

树上任意结点的左右子树的深度之差不超过1

二叉树的性质

1. 非空二叉树的叶子结点数等于度为2的结点数 + 1

2. 非空二叉树第k层至多有2的k - 1 次幂个结点（K >= 1）

   第一层 1 个结点，二层 2 * 1 = 2个结点，三层 2 * 2 = 4个结点，以此类推

3. 高度为h的二叉树至多有2的h次方 - 1 个结点（K >= 1）

   由上一条可得此条结论

5.2.2 二叉树的存储结构

顺序存储

用一组连续的存储单元依次自上而下，自左至右存储完全二叉树的结点元素

链式存储

用链表来存放二叉树，二叉树中每个结点用链表的一个链结点来存储。

链式存储需要一个数据域和一个指针域，指针域存放两个指针，一个指向左几点，一个指向右节点

5.3.1 二叉树的遍历

并查集

一种简单的集合表示。

前言

仙人指路

[第一章](# 第一章)为入门，讲解数据结构是干什么的

[第二章](# 第二章)到第四章是数据结构基础，主要讲解链表，栈，队列，串等

[第五章](# 第五章)是二叉树

[第六章](# 第六章)是图,此章偏难，非考研或算法从业可粗略看

[第七章](# 第七章)到第八章是查找以及各种排序

[第九章](# 第九章)为补充，教材中没有的部分概念我随机补充上去

墨尘の话

本文内容主要参考王道考研，其中21版本咸鱼学长的课尚可，20版本比较枯燥,可选择性学习

浙大陈越姥姥的课比较精简且侧重于练习，能看懂且时间多的蛋疼可以看这个

因时间关系,后期比较匆促，本人也就是学着玩玩╮(╯▽╰)╭，可多参考链接自主学习

参考视频

2020 王道考研 数据结构 - B站

数据结构-浙江大学 - B站

第一章

1.1.1 数据机构的基本概念

1. 什么是数据结构

数据：信息的载体，是描述客观事务属性的数，字符，以及所有能输入到计算机种并被计算机程序识别和处理的符号集合

数据对象： 具有相通性质的数据元素的集合，是数据的一个子集

数据元素： 数据的基本单位，通常作为一个整体进行考虑和处理

数据项： 构成数据元素的不可分割的最小单位

举例：一群人，就是一个数据对象，每个人就是一个数据元素，他们的手，头等就是数据项

结构：数据中存在某种关联关系，称为结构

举例：小明是八年级一班中的学生，成绩为100

上例中小明和成绩是数据项，一班是数据元素，八年级是数据对象

2. 数据结构三要素

1. 逻辑结构

线性结构

线性结构： 数据元素是一对一的关系，除了第一个元素，所有都有唯一前驱（前面有一个节点）；除了最后一个元素，所有元素都有唯一后继（后面有一个节点）

非线性结构

集合： 一组元素属于同一个集合，除此外别无关系

树形结构： 数据元素之间是一对多的关系

图状结构： 数据元素之间是多对多的关系

2. 存储结构

顺序存储

顺序存储： 把逻辑上相邻的元素存储在物理位置也相邻的存储单元中，元素之间的关系靠存储单元的邻接关系体现

非顺序存储

链式存储： 逻辑上相邻的元素在物理位置上可以不相邻，借助元素存储地址的指针来表示元素之间的逻辑关系

索引存储： 在存储元素信息的同时，还建立附加的索引表。索引表中每项称为索引项，索引项一般为（关键字，地址）

散列存储： 根据元素的关键字直接计算出该元素的存储地址，又称哈希（Hash）存储

顺序存储便于查找，非顺序查找便于增删

3. 数据的运算

3. 概念

1.2.1 算法的基本概念

1. 什么是算法

程序 = 数据结构 + 算法

数据结构负责将现实世界的问题转化为信息，然后将信息存入计算机

算法是处理信息的步骤，负责将信息进行处理得到我们想要的结果

2. 算法的特性

1. 有穷性： 有限时间里可以执行完
2. 可行性： 可以用现有的操作实现算法

好算法的特性

1. 正确性：正确解决问题
2. 可读性：别人也能很清晰的看明白
3. 健壮性（鲁棒性）： 可以处理异常情况，比如非法数据等
4. 高效率： 省时间，省内存

3. 概念

1.2.2 时间复杂度

1. 如何评价算法的时间开销

1.和机器性能相关，诸如超级计算机 vs 单片机

2.和编程语言相关，越高级的语言效率越低

3.和编译程序产生的机器指令相关

4.有些算法是不能事后统计的

通常情况机器性能和编程语言无法改变，因此考虑如何优化程序性能即可

时间开销与问题规模n之间的关系

2. 如何计算

一般指代循环/迭代，循环的次数越多时间复杂度越高（参考下图）

3. 三种复杂度

1.最坏时间复杂度： 考虑最坏的情况

2.平均时间复杂度： 考虑所有输入情况都处于同等概率

3.最好时间复杂度： 考虑最好的情况

评定一个算法的时间复杂度好坏通常要拿最坏情况去考虑

4. 概念

1.2.3 空间复杂度

通俗理解：每个变量都会在内存中开辟一个新的空间，因此基于空间复杂度优化变量越少越好，递归尤甚

内存开销与问题规模n之间的关系

基于现在计算机内存来讲，通常我们只需要考虑时间复杂度，空间复杂度无需作为首选考虑

1. 概念

第二章

2.1 线性表的定义的基本操作

1. 线性表的定义

线性表是具有相同数据类型的n（n >= 0）个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表

2. 线性表的基本操作

// 初始化表。构造一个空的线性表L，分配内存空间
InitList(L); 
// 销毁操作。销毁线性表，并释放线性表L所占用的内存空间
DestroyList(L); 

// 插入操作。在表L中第i个位置上插入指定元素e
ListInsert(L, i ,e);
// 删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值
ListDelete(L, i ,e);

// 按值查找操作。在表L中查找具有给定关键字值的元素。
LocateElem(L, e);
// 按位查找操作。获取表L中第i个位置的元素的值。
GetElem(L, i);

// 其他常用操作

// 求表长。返回线性表L的所有元素值。
Length(L);
// 输出操作。按前后顺序输出线性表L的所有元素值。
PrintList(L);
// 判空操作。若L为空表，则返回true，否则返回false
Empty(L);

Tips:

1.对数据的操作（分析思路） —— 创销，增删改查（适用于所有数据结构）

2.java函数的定义 —— <返回值类型> 函数名（<参数1类型> 参数1，<参数2类型> 参数2，…）

3.实际开发中，可根据实际需求定义其他的基本操作（输出，判空等）

4.函数名和参数的形式，命名都可改变（Reference: 严蔚敏版《数据结构与算法》）

概念

2.2.1 顺序表的定义

1. 顺序表的定义

用顺序存储的方式实现线性表

顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现

2. 顺序表的特点

​ 优点

1. 随机访问，既可以在O(1)时间内找到第一个元素

2. 存储密度高，每个节点只存储数据元素

   缺点

3. 拓展容量不方便（采用动态分配时间复杂度较高）

4. 插入，删除不方便，需要移动大量元素

3. 概念

注：图上所示函数均为c语言中动态分配相关函数，可根据自身情况选择性学习

代码在2.2.2.2 顺序表的查找一节

2.2.2.1 顺序表的插入删除

概念

2.2.2.2 顺序表的查找

/**
 * @Description: 顺序表
 * @author: HouBo
 * @Date: 2020/11/26 17:52
 */
public class SqList {

    static final int MAXSIZE = 10; // 最大长度
    int data[] = new int[MAXSIZE]; // 使用静态数组存放数据
    int length;  // 顺序表的当前长度

    // 初始化一个顺序表
    void initList(SqList L){
        L.length = 8; // 初始长度为0
    }

    // 添加一个数据
    boolean listInsert(SqList L, int i, int e){
        if(i < 1 || i > L.length + 1){ // 当前i的值是否有效
            return false;
        }
        if(L.length == MAXSIZE){ // 当前存储空间是否充盈
            return false;
        }
        for(int j = L.length; j >= i; j--){ // 将第i个元素之后的元素后移
            L.data[j] = L.data[j - 1];
            L.data[j - 1] = e; // 在位置i处放入e
        }
        L.length++; // 长度+1
        return true;
    }

    // 删除一个数据
    boolean listDelete(SqList L, int i, int e){
        if(i < 1 || i > L.length + 1){ // 当前i的值是否有效
            return false;
        }
        e = L.data[i - 1];
        for(int j = i; j <= L.length; j++){ // 将第i个元素之后的元素后移
            L.data[j - 1] = L.data[j]; // 在位置i处放入e
        }
        L.length--; // 长度-1
        return true;
    }
    
    // 按位查找
    int getElem(SqList L, int i){
        if(i < 1 || i > L.length + 1){
            return 0;
        }
        return L.data[i - 1];
    }

    // 按值查找
    int locateElem(SqList L, int e){
        for(int i = 0; i < L.length; i++){
            if(L.data[i] == e){
                return i + 1;
            }
        }
        return 0;
    }
}

此段代码非最优解，仅作练习使用

概念

2.3.1 单链表的定义

1. 什么是单链表

相对于顺序表，单链表除了存储数据元素外，还需要存储指向下一个节点的指针

2. 单链表和顺序表的不同

	顺序表	单链表
优点	随机存取，存储密度高	不要求大片连续空间，改变容量方便
缺点	要求大片连续空间，改变容量不方便	不可随机存取，要耗费一定空间存放指针

带头结点和不带头结点的区别

创立第一个结点，既为带头结点，反之则为不带

不带头结点，对第一个数据结点和后续数据结点的处理需要用不用的代码逻辑，空表和非空表的处理同理

带头结点通常情况下优于不带

概念

代码放在2.3.2.3 单链表的建立一节中

2.3.2.1 单链表的插入删除

此章中，p通过代指当前结点，s指新插入的结点, a1指下一个结点, e指新值

1.1 按位序插入(带头结点)

思路：插入结点打断链表，上一个结点挂到它身上（指向它），它挂到下一个结点身上。

链表插入删除操作和顺序表相比相对复杂，需多多思考。

1.2 按位序插入（不带头结点）

不带头结点第一个结点需要做特殊处理，创建一个s，将第a1挂到它身上。

2. 指定结点的后插操作

a1挂到s身上，s挂到p身上。

3. 指定结点的前插操作

由于无法直接获取p的上一个结点，因此可采用如下方法实现:

思路：将p变更为s, s变更为p

实现：p的值赋给s，新值e赋给p

4. 按位序删除

思路：找到要删除的结点，断开它并释放空间

5. 指定结点的删除

思路：同上

实现：将p的值和下一个引用都指向下一个，实现删除p的效果

此处如果p是最后一个结点，将会出现异常

单链表的局限性：无法逆向检索，不方便

6. 概念

2.3.2.2 单链表的查找

概念

2.3.2.3 单链表的建立

思路：遍历所有结点，通过头插或者尾插的方式实现循环建立一个单链表。

头插法可以实现反转链表，注意这是个重点

代码

/**
 * @Description: 结点
 * @Author: MoChen
 */
public class HNode {

    public HNode(){

    }

    public HNode(int data){
        this.data = data;
    }

    // 数据
    int data;
    // 下一个结点
    HNode next;
}

/**
 * @Description: 单链表
 * @Author: MoChen
 */
public class HLinkerList {

    // 链表的头结点
    HNode head = null;

    // 初始化一个空链表
    boolean InitList(HLinkerList L){
        L.head = new HNode(); // 分配一个头结点,如果不带头结点此处直接赋空
        L.head.next = null; // 头结点之后暂时没有结点
        return true;
    }

    // 在第i个位置插入元素e
    boolean ListInsert(HLinkerList L, int i, int e) {
        if(i < 1) {
            return false;
        }
        // 以下代码段为不带头结点的操作
//        if(i == 1) { // 插入第一个结点的操作与其他结点操作不同
//            HNode s = new HNode();
//            s.data = e;
//            s.next = L.head.next;
//            L.head = s; // 头指针指向新结点
//        }
//        HNode p; // 指针p向前扫描到的结点
//        int j = 0; // 当前p指向的是第几个结点，不带的话此处赋1
//        p = L.head; // L指向头结点，头结点是第0个结点
//        while (p != null && j < i - 1) { // 循环找到 i - 1 个结点
//            p = p.next;
//            j++;
//        }
        HNode p = GetElem(L, i - 1);

//        if(p == null){ // i值不合法
//            return false;
//        }
//        HNode s = new HNode();
//        s.data = e;
//        s.next = p.next;
//        p.next = s; // 将结点s连到p之后
//        return true; // 插入成功

        return InsertNextNode(p, e);
    }

    // 后插操作：在p结点之后插入元素e
    boolean InsertNextNode(HNode p, int e){
        if(p == null){
            return false;
        }
        HNode s = new HNode();
        s.data = e; // 新结点s存储数据e
        s.next = p.next;
        p.next = s; // 新结点s挂到p身上
        return true;
    }

    // 前插操作：在p结点之前插入元素e
    boolean InsertPriorNode(HNode p, int e){
        if(p == null){
            return false;
        }
        HNode s = new HNode();
        s.next = p.next;
        p.next = s; // 新结点s挂到p身上
        s.data = p.data; // 将p里面的元素复制到s中
        p.data = e; // p中的元素覆盖为e
        return true;
    }

    // 按位序删除
    boolean ListDelete(HLinkerList L, int i, int e){
        if(i < 1){
            return false;
        }
//        HNode p; // 指针p向前扫描到的结点
//        int j = 0; // 当前p指向的是第几个结点，不带的话此处赋1
//        p = L.head; // L指向头结点，头结点是第0个结点
//        while (p != null && j < i - 1) { // 循环找到 i - 1 个结点
//            p = p.next;
//            j++;
//        }
        HNode p = GetElem(L, i - 1);

        if(p == null){ // i值不合法
            return false;
        }
        if(p.next == null){ // 第i - 1个结点后面已无其他结点
            return false;
        }
//        HNode q = p.next; // 令q指向被删除的结点
//        e = q.data; // 用e返回元素的值
//        p.next = q.next; // 将q结点从链中断开
//        return true; // 删除成功

        return DeleteNode(p);
    }

    // 删除指定结点p
    boolean DeleteNode(HNode p){
        if(p == null){
            return false;
        }
        HNode q = p.next; // 令q指向p的后继结点
        p.data = p.next.data; // 和后继结点交换数据域
        p.next = q.next; // 将q结点从链中断开
        return true;
    }

    // 按位查找，返回第i个元素
    HNode GetElem(HLinkerList L, int i){
        if(i < 0){
            return null;
        }
        HNode p; // 指针p向前扫描到的结点
        int j = 0; // 当前p指向的是第几个结点，不带的话此处赋1
        p = L.head; // L指向头结点，头结点是第0个结点
        while (p != null && j < i) { // 循环找到 i 个结点
            p = p.next;
            j++;
        }
        return p;
    }

    // 按值查找
    HNode LocateElem(HLinkerList L, int e){
        HNode p = L.head.next;
        // 从第一个结点开始查找数据域为e的结点
        while(p != null && p.data != e){
            p = p.next;
        }
        return p; // 找到后返回该结点，否则返回null
    }

    // 求表的长度
    int Length(HLinkerList L){
        int len = 0;
        HNode p = L.head;
        while(p.next != null){
            p = p.next;
            System.out.println("链表第" + len + "个数据:" + p.data);
            len++;
        }
        return len;
    }
}

此段代码非最优解，仅作练习使用

2.3.3 双链表

下文中，s指代新结点，p指代当前结点，q指代下一个结点

1. 双链表和单链表的概念

单链表：无法逆向检索，有时候不太方便

双链表：可进可退，存储密度更低

双链表整体和单链表差距不大，额外新增了一个指向上一个结点的处理

2. 双链表的插入

思路：和单链表同理，额外增加了prior的处理

① q挂到s身上

② q的prior指向s

③ s的prior指向p

④ s挂到p身上

如果q不存在，第二步需省略

3. 双链表的删除

① q的下一个结点挂到p身上

② q的下一个结点的prior指向p

代码

/**
 * @Description: 结点（双链表）
 * @Author: MoChen
 */
public class HDNode {
    public HDNode(){

    }

    public HDNode(int data){
        this.data = data;
    }

    // 数据
    int data;
    // 下一个结点
    HDNode next;
    // 上一个结点
    HDNode prior;
}

/**
 * @Description: 双链表
 * @Author: MoChen
 */
public class HDLinkedList {

    // 链表的头结点
    HDNode head = null;

    // 初始化一个空链表
    boolean InitList(HDLinkedList L){
        L.head = new HDNode(); // 分配一个头结点,如果不带头结点此处直接赋空
        L.head.prior = null; // 头结点的prior永远指向空
        L.head.next = null; // 头结点之后暂时没有结点
        return true;
    }

    // 在p结点之后插入s结点
    boolean InsertNextHDNode(HDNode p, HDNode s){
        if(p == null || s == null){ // 非法参数
            return false;
        }
        s.next = p.next;
        if(p.next != null){ // 如果p后面有结点
            p.next.prior = s;
        }
        s.prior = p;
        p.next = s;
        return true;
    }

    // 删除p结点的后继结点
    boolean DeleteNextNode(HDNode p){
        if(p == null){
            return false;
        }
        HDNode q = p.next; // 找到p的后继结点q
        if(q == null){
            return false; // p没有后继
        }
        p.next = q.next;
        if(q.next != null){ // q结点不是最后一个结点
            q.next.prior = p;
        }
        return true;
    }

    // 求表的长度
    int Length(HDLinkedList L){
        int len = 0;
        HDNode p = L.head;
        while(p.next != null){
            p = p.next;
            System.out.println("链表第" + len + "个数据:" + p.data);
            len++;
        }
        return len;
    }
}

概念

2.3.4 循环链表

1. 循环链表与普通链表的不同

循环链表的尾结点的指针指向头结点，而普通链表的尾结点指向空。

通常我们无法获取之前的结点，除非拿到头结点，循环单链表可以通过遍历结点的方式从而拿到自己想要的结点。

以前在增加/删除操作时，需要给最后一个结点判空，现在则不需要。

2. 循环双链表

表头的prior指向表尾，表尾的next指向表头。

概念

2.3.5 静态链表

1. 什么是静态链表

单链表：各个结点在内存中随意散落。

静态链表：分配一整片连续的内存空间，各个结点集中安置。

2. 静态链表的概念

静态链表就是用数组的方式实现的链表。

容量固定不可变

本章内容不是很重要，了解其概念即可。

2.3.6 顺序表和链表的比较

1. 线性结构

都属于线性结构

2. 存储结构

	顺序表	单链表
优点	随机存取，存储密度高	不要求大片连续空间，改变容量方便
缺点	要求大片连续空间，改变容量不方便	不可随机存取，要耗费一定空间存放指针

3. 基本操作

操作	顺序表	链表
创	需要分配大片连续空间。若分配空间过小，则之后不方便扩展；若分配空间过大，则浪费内存资源	只需分配一个头结点（也可不分配），方便扩展
销	长度赋0即可，本笔记采用java实现，因此无需考虑内存问题，如果使用c实现则需要通过free函数释放内存	依次删除每个结点
增，删	插入/删除元素都要将后续元素全部后移/前移 时间复杂度O(n),时间开销主要来自移动元素	插入/删除元素只需修改指针即可 时间复杂度O(n),时间开销主要来自查找元素
查	按位查找：O(1)	按值查找：O(n)

4. 概念

表长无法预估，需要经常进行增/删操作，可使用链表

表长可预估，需要经常进行查询操作，可使用顺序表

第三章

3.1.1 栈的基本概念

1. 栈（Stack）的概念

栈是只允许在一端进行插入或删除的线性表

重要术语：栈顶，栈底，空栈

特点：后进先出（Last In First Out）LIFO

2. 栈的基本操作

InitStack(S); // 初始化栈。构造一个空栈，分配内存空间。
DestroyStack(L); // 销毁栈。销毁并释放栈s所占用的内存空间。

Push(S, x); // 进栈，若栈S未满，则将x加入使之成为新栈顶。
Pop(S, x); // 出栈，若栈S非空，则弹出栈顶元素，并用x返回。

GetTop(S, x); // 读栈顶元素。若栈S非空，则用x返回栈顶元素。

// 其他常用操作
StackEmpty(S); // 判断一个栈是否为空

概念

3.1.2 栈的顺序存储实现

思路

给定一个静态数组，每次操作头或者尾即可

指针用于操纵当前数据

代码

/**
 * @Description: 顺序存储实现栈
 * @Author: MoChen
 */
public class HSqStack {

    final int MAXSIZE = 10; // 定义栈中元素的最大个数

    int[] data; // 静态数组中放栈中元素

    int top; // 栈顶指针

    HSqStack(){
        data = new int[MAXSIZE];
    }

    // 初始化栈
    void InitStack(){
        top = -1; // 此处如果指向0，则预示已经有一个参数了，所以初始化指向-1
    }

    // 判断栈空
    boolean StackEmpty(){
        return top == -1;
    }

    // 入栈
    boolean Push(int x){
        if(top == MAXSIZE - 1){ // 栈满
            return false;
        }
        top++; // 指针上移一位
        data[top] = x; // 新元素入栈
        return true;
    }

    // 出栈
    boolean Pop(int x){
        if(top ==  - 1){ // 空栈
            return false;
        }
        x = data[top]; // 栈顶元素先出栈
        top--; // 指针下移
        return true;
    }

    // 读取栈顶元素
    int GetTop(int x){
        if(top ==  - 1){ // 空栈
            return -1;
        }
        x = data[top]; // 读取栈顶元素
        return x;
    }
}

概念

3.1.3 栈的链式存储实现

用链表的方式实现栈几乎等同于单链表，此处直接套用单链表即可

3.2.1 队列的基本概念

1. 什么是队列

栈（Stack）是只允许在一端进行插入或删除的线性表

队列（Queue）是只允许在一端插入,在另一端删除的线性表

队列的特点：先进先出 First In First Out (FIFO)

2. 队列的基本操作

InitQueue(Q); // 初始化队列，构造一个空队列Q
DestroyQueue(Q); // 销毁队列，销毁并释放队列Q所占用的空间

EnQueue(Q, x); // 入队，若队列Q未满，将x加入，使之成为新的队尾
DeQueue(Q, x); // 出队，若队列Q非空，删除队头元素，并用x返回

GetHead(Q, x); // 读队头元素，对队列Q非空，则将队头元素赋值给x
QueueEmpty(Q); // 判断队列是否为空

概念

3.2.2 队列的顺序实现

要点

求队列一共有多少个元素的算法如下：

// 尾指针 + 长度 - 头指针 % 长度
(rear + MAX_SIZE - front) % MAX_SIZE

头尾指针均为长度以内任意一个数字，因此想要求差必须先加上最大长度

尾指针和头指针位置可调换

概念上不会大于长度，保证代码健全性加上模运算

代码

/**
 * @Description: 顺序队列
 * @Author: MoChen
 */
public class HSqQueue{

    private static class SqQueue{
        private final int MAX_SIZE = 10;
        int[] data; // 静态数组存放元素
        int front, rear; // 队头指针和队尾指针

        public SqQueue(){
            data = new int[MAX_SIZE];
        }
    }

    private SqQueue Q;

    // 初始化队列
    void initQueue(){
        Q = new SqQueue();
        Q.front = Q.rear = 0; // 初始时，队头队尾全部指向空
    }

    // 判断队列是否为空
    boolean queueEmpty(){
        return Q.front == Q.rear; // 当队头队尾指向一样时，则意味队列为空
    }

    // 入队
    boolean enQueue(int x){
        if((Q.rear + 1) % Q.MAX_SIZE == Q.front){ // 如果队头的指针的下一位指向队尾，则表示队满
            return false;
        }
        Q.data[Q.rear] = x;
        Q.rear = (Q.rear + 1) % Q.MAX_SIZE; // 队尾指针+1取模，保证指针不会超过长度
        return true;
    }

    // 出队
    boolean deQueue(){
        if(Q.front == Q.rear){ // 队列为空
            return false;
        }
        Q.data[Q.front] = -1;
        Q.front = (Q.rear + 1) % Q.MAX_SIZE; // 队尾指针+1取模，保证指针不会超过长度
        return true;
    }

    // 获取队头元素
    int getHead(){
        if(Q.front == Q.rear){ // 队列为空
            return -1;
        }
        int x = Q.data[Q.front];
        return x;
    }

    // 获取队列长度
    int queueLength(){
        return (Q.rear + Q.MAX_SIZE - Q.front) % Q.MAX_SIZE;
    }
}

代码不完善，仅作练习使用

概念

3.2.3 队列的链式实现

概念

链式无需考虑内存

代码

/**
 * @Description: 链式队列
 * @Author: MoChen
 */
public class HLinkQueue {

    private class LinkNode{
        int data;
        LinkNode next;

        public LinkNode(){}

        public LinkNode(int data) {
            this.data = data;
        }
    }

    private class LinkQueue{
        LinkNode front, rear;
    }

    private LinkQueue Q;

    // 初始化队列
    void initQueue(){
        // 初始时，front,rear都指向头结点
        Q.front = Q.rear = new LinkNode();
        // 不带头结点的话front和rear都要指向空
        Q.front.next = null;
    }

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

    // 入队
    boolean enQueue(int x){
        LinkNode s = new LinkNode(x);
        s.next = null;
        // 如果不带头结点则front需要进行非空判断，为空则修改表头指针
        Q.rear.next = s; // 新结点挂到rear身上
        Q.rear = s; // 修改表尾指针
        return true;
    }

    // 出队
    boolean deQueue(){
        if(Q.rear == Q.front){ // 空队列
            return false;
        }
        LinkNode p = Q.front.next;
        Q.front.next = p.next; // 修改头结点的next指针
        if(Q.rear == p){ // 如果是最后一个结点
            Q.rear = Q.front;
        }
        return true;
    }
}

概念

3.2.4 双端队列

概念

栈：单端插入和删除的线性表

队列：一端插入，另一端删除的线性表

双端队列：两端插入，两端删除的线性表

双端队列包含输入受限和输出受限两种情况，不同情况具有不同局限性，需根据情况选择

概念

3.3.1 栈在括号匹配中的应用

示例：

一组括号，求出它们能不能完成匹配

思路：

使用栈，将左括号压入，如果遇到右括号就压出，遇到无法匹配的括号或者匹配结束栈里还有值则匹配失败

代码

/**
 * @Description: 给定一组括号，判断这组括号能否完成匹配
 * @Author: MoChen
 */
public class Brancket {

    static String bracketStr = "({}{})";

    public static void main(String[] args) {
        System.out.println(bracketCheck(bracketStr));
    }

    static boolean bracketCheck(String bracketStr){
        char[] data = new char[bracketStr.length()]; // 栈元素
        int top = 0; // 栈顶指针
        char[] strs = bracketStr.toCharArray();
        for(int i = 0; i < strs.length; i++){
            if(strs[i] == '[' || strs[i] == '{' || strs[i] == '('){ // 扫描到左括号，入栈
                data[++top] = strs[i];
            }else{
                if(top == 0){ // 扫描到右括号且当前栈空,匹配失败
                    return false;
                }
                char topElem = data[top--]; // 栈顶元素出栈
                // 进行匹配，如果匹配失败则返回false
                if(strs[i] == ')' && topElem != '('){
                    return false;
                }
                if(strs[i] == ']' && topElem != '['){
                    return false;
                }
                if(strs[i] == '}' && topElem != '{'){
                    return false;
                }
            }
        }
        return top == 0; // 括号校验完成且栈空则匹配成功
    }
}

3.3.2 栈在表达式求值中的应用（上）

三种表达式的不同

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-sKR5VxaQ-1618913823563)(https://i.loli.net/2021/02/01/2GOCL9hukZWgNse.png)]

中缀表达式

运算符在中间，既为我们常用的数学表达式

后缀表达式

运算符在后面，又叫逆波兰表达式（Reverse Polish notation）

前缀表达式

运算符在前面，因为是波兰人提出，所以又叫波兰表达式（Polish notation）

中缀表达式	后缀表达式	前缀表达式
a + b	ab +	+ ab
a + b - c	a b + c -	- + ab c
a + b - c * d	ab + cd * -	- + ab * cd

核心思想还是一个计算区间一块区域，诸如(a + b) - (c * d) = （ab+）(cd*) -

中缀转后缀

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RRhTgc8d-1618913823564)(https://i.loli.net/2021/02/01/t2GmHCKyBF59gvq.png)]

左优先原则：只要左边的运算符能先计算，就先计算左边的

后缀表达式的手算方法

从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应操作，合并为一个操作数

对于计算机而言，后缀表达式的效率往往要更高

中缀表达式转前缀表达式

右优先原则：只要右边的操作符能先计算，就优先计算右边的

中缀
A + B * (C - D) - E / F
常规计算
- + A * B - C D / E F
右优先
+ A - * B - C D / E F

后缀表达式的机算方法

① 从左到右扫描下一个元素，直到处理完所有元素

② 若扫描到操作数则入栈

③ 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果入栈

概念

3.3.2 栈在表达式求值中的应用（下）

中缀转后缀

① 遇到操作数，直接加入后缀表达式

② 遇到界限符。遇到 ( 直接入栈，遇到 ) 则依次弹出栈内运算符并加入后缀表达式，直到弹出 ( 为止。注意（ 不加后缀

③ 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到 ( 或栈空则停止。之后再将当前运算符入栈。

中缀的计算

中缀转后缀 + 后缀求值

① 初始化两个栈，操作数栈和运算符栈

② 若扫描到操作数，压入操作数栈

③ 若扫描到运算符或界限符，则按照‘中缀转后缀’相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要在弹出两个操作数栈的栈顶元素并执行相应运算，运算结果在压回操作数栈）

代码

因时间原因，此处仅列出中转后和后计算

import java.util.Stack;
import java.util.regex.Pattern;

/**
 * @Description: 后缀表达式
 * @Author: MoChen
 */
public class PolishNotation {

    // 中缀表达式
    private static String notation = "((15 / (7 - (1 + 1))) * 3) - (2 + (1 + 1))";
    // 后缀表达式
    private static String poNotation = "15 7 1 1 + - / 3 * 2 1 1 + + -";
    // 前缀表达式
    private static String rpoNotation = "- * / 15 - 7 + 1 1 3 + 2 + 1 1";
    // 10的倍数
    private static int[] exactNums = {10, 100, 1000, 10000, 100000};

    public static void main(String[] args) {
        System.out.println("中计算：" + countNum(notation));
        System.out.println("中转后：" + commTransRpo(notation));
        System.out.println("后计算：" + poCount(poNotation));
    }

    /**
     * 中缀转后缀
     */
    static String commTransRpo(String notation){
        StringBuilder str = new StringBuilder();
        Stack<Character> stack = new Stack<>();
        char[] chars = notation.toCharArray();

        for(int i = 0; i < chars.length; i++){
            if(isInteger(chars[i] + "")){
                int j = 1;
                int num = Integer.parseInt(chars[i] + "");
                while(isInteger(chars[i + j] + "")){
                    num = Integer.parseInt(num + "" + chars[i + j] + "");
                    j++;
                }
                i += j - 1;
                str.append(num).append(" ");
            }else if(chars[i] != ' '){
                if(chars[i] == '('){
                    stack.push(chars[i]);
                }else if(chars[i] == ')' && !stack.empty()){
                    char pop = stack.pop();
                    while(pop != '('){
                        str.append(pop + " ");
                        pop = stack.pop();
                    }
                }else{
                    switch (chars[i]){
                        case '+':
                        case '-':
                            if(!stack.empty() && stack.peek() != '('){
                                while(!stack.empty()){
                                    char pop = stack.pop();
                                    if(pop != '(' && pop != ')'){
                                        str.append(pop + " ");
                                    }
                                }
                            }else{
                                stack.push(chars[i]);
                            }
                            break;
                        case '*':
                        case '/':
                            if(!stack.empty() && stack.peek() != '(' && stack.peek() != '-' && stack.peek() != '+'){
                                while(!stack.empty()){
                                    char pop = stack.pop();
                                    if(pop != '(' && pop != ')'){
                                        str.append(pop + " ");
                                    }
                                }
                            }else{
                                stack.push(chars[i]);
                            }
                            break;
                    }
                }
            }
        }
        while(!stack.empty()){
            str.append(stack.pop());
        }
        return str.toString();
    }

    /**
     * 后缀计算
     */
    static Integer poCount(String notation){
        int res = 0;
        Stack<Integer> stack = new Stack<>();
        char[] chars = notation.toCharArray();
        boolean count = false;

        for(int i = 0; i < chars.length; i++){
            if(isInteger(chars[i] + "")){
                int j = 1;
                int num = Integer.parseInt(chars[i] + "");
                while(isInteger(chars[i + j] + "")){
                    num = Integer.parseInt(num + "" + chars[i + j] + "");
                    j++;
                }
                i += j - 1;
                stack.push(num);
            }else if(chars[i] != ' '){
                int temp = stack.pop();
                switch (chars[i]){
                    case '+':
                        stack.push(stack.pop() + temp);
                        break;
                    case '-':
                        stack.push(stack.pop() - temp);
                        break;
                    case '*':
                        stack.push(stack.pop() * temp);
                        break;
                    case '/':
                        stack.push(stack.pop() / temp);
                        break;
                }
            }
        }
        res = stack.pop();
        return res;
    }

    /**
     * 求和（中缀）
     */
    static Integer countNum(String notation){
        return poCount(commTransRpo(notation));
    }

    /**
     * 判断一个字符是否为Integer
     */
    public static boolean isInteger(String str) {
        Pattern pattern = Pattern.compile("[0-9]*");
        return pattern.matcher(str).matches();
    }
}

3.3.3 栈在递归中的应用

什么问题适合用递归算法解决

可以把原始问题转换为属性相同，但规模较小的问题

概念

3.3.4 队列的应用

队列在操作系统中的应用

多个进程争抢着使用有限的系统资源时，FCFS(First Come First Service, 先来先服务)是一种常用策略

3.4 特殊矩阵的压缩存储

一维数组存储结构

各数组元素大小相同，且物理上连续存放

LOC + i * sizeof(ElemType)

除特殊说明，否则数组下标默认从0开始

二维数组存储结构

M行N列的二位数组b[M][N]中，若按行优先存储，则b[i][j]的存储地址
LOC + (i * N + j) * sizeof(elemeType)

M行N列的二位数组b[M][N]中，若按列优先存储，则b[i][j]的存储地址
LOC + (j * M + i) * sizeof(elemeType)

思路：无论行列优先，从起始地址遍历到当前元素即可得到存储地址

对称矩阵

若n阶方阵中任意一个元素a i,j 都有 a i, j = a j, ,则该矩阵称为对称矩阵

策略：只存储主对角线+下三角区

使用一维数组存储，则取值为:
行优先：先根据i值求出上面有几行，在根据j值求出在当前行的位置

列优先：同上，将位置调换即可

三角矩阵

下三角矩阵：除了主对角线和下三角区，其余都相同

上三角矩阵：除了主对角线和上三角区，其余都相同

存储策略：将中线和三角区按照行优先存入，最后一个位置存放常量c

三对角矩阵

又称带状矩阵，既中线周围一圈都有值，其余皆为0

首行和尾行是两个，其余都是三个

稀疏矩阵

非零元素远远少于矩阵元素的个数，且无规则分布

存储策略一：顺序存储

三元组 <行，列，值>

此处行列从1开始

存储策略二：十字链表法

概念

第四章

4.2.1 串的定义和基本操作

串的定义

串，既字符串(String)是由零个或多个字符组成的有限序列。

举例：

S = “Hello World!”
T = ‘iPhone 1 Pro Max?’

子串：串中任意个连续的字符组成的子序列 Eg : ‘iPhone’,'Pro M’是串的子串

主串：包含子串的串。 Eg : T是子串’iPhone’的主串

字符在主串中的位置:字符在串中的序号。 Eg:'1’在T中的位置是8

子串在主串中的位置:子串的第一个字符在主串中的位置 Eg:'11 Pro’在T中的位置是8

操作

StrAssign(T, chars); // 赋值操作。将chars的值赋给T
StrCopy(T, S); // 赋值操作。将串S复制给串T
StrEmpty(S); // 判空操作。若S为空串，则返回true，否则返回false
StrLength(S); // 求串长。返回串S的元素个数.
ClearString(S); // 清空操作。将S清为空串
DestoryString(S); // 销毁串。将串S销毁
Concat(T, S1, S2); // 串链接。由T返回由S1和S2连接而成的新串
SubString(Sub, S, pos, len); // 求子串。用Sub返回S中从pos开始到len的子串
Index(S, T); // 定位操作。若主串S中存在与T相同的子串，则返回一个字符的位置，否则返回0
StrCompare(S, T); // 比较操作。若S>T，则返回值>0，S<T则返回值<0,S=T则返回0

概念

4.1.2 串的存储结构

概念

4.2.1 串的朴素模式匹配

思路

在主串中找到模式串相同的子串

因该算法思路简单了然，故叫朴素模式匹配

最好时间复杂度	O（m）
常规时间复杂度	O（n）
最坏时间复杂度	O (nm)

概念

4.2.2 KMP算法（上）

什么是KMP算法

朴素模式匹配的优化

由三个人提出，各取名字中一个字母，因此叫KMP算法

朴素模式匹配的缺点

当某些子串与模式串能部分匹配时，主串的扫描指针i经常回溯，导致时间开销增加

4.2.3 KMP算法（下）

学不会，等我学会了再来补充

4.2.4 KMP算法的进一步

同上

第五章

5.1 树的基本概念

什么是树

树是 n (n >= 0) 个结点的有限集合，n = 0 时，称为空树。

而任意非空树应该满足:

1.有且仅有一个特定的称为根的结点。

2.当 n > 1时，其余结点可分为 m (m > 0) 个互不相交的有限集合，其中每一个集合本身又是一棵树，称为根节点的子树。

基本术语

1. 节点的度：一个节点含有的子树的个数称为该节点的度；
2. 树的度：一棵树中，最大的节点度称为树的度；
3. 叶节点或终端节点：度为零的节点；
4. 非终端节点或分支节点：度不为零的节点；
5. 父亲节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
6. 孩子节点：一个节点含有的子树的根节点称为该节点的子节点；
7. 兄弟节点：具有相同父节点的节点互称为兄弟节点；
8. 层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
9. 深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0；
10. 高度：对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0；
11. 堂兄弟节点：父节点在同一层的节点互为堂兄弟；
12. 节点的祖先：从根到该节点所经分支上的所有节点；
13. 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
14. 森林：由m（m>=0）棵互不相交的树的集合称为森林。

树的种类

• 无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树；
• 有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；
• 二叉树：每个节点最多含有两个子树的树称为二叉树；
• 完全二叉树：对于一颗二叉树，假设其深度为d（d>1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树；
• 满二叉树：所有叶节点都在最底层的完全二叉树；
• 平衡二叉树（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；
• 排序二叉树(二叉查找树（英语：Binary Search Tree))：也称二叉搜索树、有序二叉树；
• 霍夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树；
• B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多于两个子树。

5.2.1 二叉树的概念

什么是二叉树

二叉树是n（n>=0）个结点的有限集合。

1. n = 0 时，二叉树为空；
2. n > 0 时，由根节点和两个互不相交的左右子树组成。左右子树也分别是一颗二叉树。

二叉树与度为2的有序树的区别

二叉树	度为2的有序树
可以为空	至少有三个结点
子结点始终有左右之分	子结点次序相对

满二叉树

一颗高度为h，且含有2h - 1个结点的二叉树称为满二叉树

完全二叉树

相对于满二叉树，完全二叉树最后一层可以缺少结点或叶子

二叉排序树

对任意结点而言，左子树关键字均小于该结点，右子树关键字均大于该结点

平衡二叉树

树上任意结点的左右子树的深度之差不超过1

二叉树的性质

1. 非空二叉树的叶子结点数等于度为2的结点数 + 1

2. 非空二叉树第k层至多有2的k - 1 次幂个结点（K >= 1）

   第一层 1 个结点，二层 2 * 1 = 2个结点，三层 2 * 2 = 4个结点，以此类推

3. 高度为h的二叉树至多有2的h次方 - 1 个结点（K >= 1）

   由上一条可得此条结论

5.2.2 二叉树的存储结构

顺序存储

用一组连续的存储单元依次自上而下，自左至右存储完全二叉树的结点元素

链式存储

用链表来存放二叉树，二叉树中每个结点用链表的一个链结点来存储。

链式存储需要一个数据域和一个指针域，指针域存放两个指针，一个指向左几点，一个指向右节点

5.3.1 二叉树的遍历

并查集

一种简单的集合表示。

通常用树的双亲表示法作为并查集的存储结构

通常用数组元素的下标代表元素名，用根节点的下标代表子集合名，根节点的双亲结点为负数。

Initial(S)	// 将集合S中的每个元素都初始化为只有一个单元素的子集合
Union(S, Root1, Root2) // 把集合S中的子集合（互不相交）Root2并入子集合Root1
Find(S, x) // 查找集合S中单元素x所在子集合，并返回该子集合的名字

概念

5.3.2 线索二叉树

线索二叉树的概念

线索化

若无左子树，则将左指针指向其前驱结点

若无右子树，则将右指针指向其后驱结点

优点

将原本的空指针都替换为前驱和后驱，可以加快结点的查询

5.4.1 树的存储结构

双亲表示法

采用一组连续的存储空间来存储每个结点，同时每个结点中增设一个伪指针，指向双亲结点在数组中的位置。根节点的下标为0，其伪指针域为-1。

多一个指针，指向父节点，没爹则给-1。

孩子表示法

将每个结点的孩子结点都用单链表连接起来形成一个线性结构，n个结点具有n个孩子链表。

每个结点的所有子结点就是一个单链表。

孩子兄弟表示法

以二叉链表作为树的存储结构，又称二叉树表示法。

左指针指向第一个孩子，右子针指向下一个兄弟。

优缺点对比

	优点	缺点
双亲表示法	寻找双亲效率高	寻找孩子效率低
孩子表示法	寻找孩子效率高	寻找双亲效率低
孩子兄弟表示法	寻找孩子效率高 方便树转换为二叉树	寻找双亲效率低

5.4.2~5.4.3 树和森林

树与二叉树的转换

可用上一章的左孩子右兄弟的办法进行转换。

森林与二叉树的转换

先转为二叉树，在将每棵二叉树的根依次作为上一棵二叉树的右子树。

树的遍历

按照某种方式访问树中的每个结点，且仅访问一次

先根遍历

先访问根结点，在按照从左到右的顺序遍历根节点的子树

树的先根遍历与这棵树对应二叉树的先序遍历相同

后根遍历

先按照从左到右的顺序遍历根节点的子树，在访问根结点

树的后根遍历与这棵树对应二叉树的中序遍历相同

举例

先根遍历：RADEBCFGHK

后根遍历：DEABGHKFCR

森林的遍历

先序遍历

1. 访问第一棵树的根结点
2. 先序遍历第一棵树的子树森林
3. 先序遍历除去第一棵树之后剩余的树构成的子树森林

中序遍历

1. 中序遍历第一棵树的根结点的子树森林
2. 访问第一棵树的根结点
3. 中序遍历除去第一棵树之后剩余的树构成的子树森林

5.4.4 树的应用并查集

什么是并查集

并查集主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：

• 合并（Union）：把两个不相交的集合合并为一个集合。
• 查询（Find）：查询两个元素是否在同一个集合中。

实现代码

/**
 * @Description: 并查集
 * @Author: MoChen
 */
public class UnionFind {

    static final int MAX_SIZE = 10;
    int fa[] = new int[MAX_SIZE];

    /**
     * 初始化
     */
    void initial(int n){
        for(int i = 1; i <= n; ++i){
            fa[i] = i;
        }
    }

    /**
     * 查询
     */
    int find(int x){
        return x == fa[x] ? x : (fa[x] = find(fa[x]));
    }

    /**
     * 合并
     */
    void merge(int i, int j){
        fa[find(i)] = find(j);
    }

}

按秩合并

合并时，优先将简单的树往复杂的树上面合，从而达到最小程度影响深度

实现思路

重新给定一个数组rank[]记录每个树的深度，开始所有rank设为1。合并时比较两个根节点，把rank较小者往较大者上合并。

注意：按秩合并会带来额外的空间复杂度

此概念为优化，此处暂不做深究

参考内容

算法学习笔记(1):并查集 - 知乎

5.5.1 二叉排序树

什么是二叉排序树

二叉排序树(Binary Sort Tree),也称二叉查找树

1. 左子树所有节点均小于根节点
2. 右子树所有节点均大于根节点
3. 左右子树也是二叉排序树

插入

若二叉排序树为空，则直接插入

若二叉排序树非空，当值小于根节点时插入左子树，当值大于根节点时插入右子树，当值等于根节点则不插入

构造二叉排序树

读入元素并建立节点，若二叉树为空则将其作为根节点

若二叉排序树非空，当值小于根节点时插入左子树，当值大于根节点时插入右子树，当值等于根节点则不插入

思路和插入一样

删除

1. 若被删除节点是叶节点，则直接删除
2. 若被删除节点z只有一棵子树，则让z的子树指向z的父节点，代替z节点
3. 若被删除节点z有两颗子树，则让z的右子树最小的节点替换z

5.5.2 平衡二叉树

什么是平衡二叉树

平衡二叉树(AVL)，每个节点的左子树和右子树的高度差最多为1

AVL是取自作者名

平衡二叉树的判断

1. 判断左子树是一颗平衡二叉树
2. 判断右子树是一颗平衡二叉树
3. 判断该节点为根的二叉树为平衡二叉树

平衡树的旋转

LL平衡旋转(右旋转)

在结点A的左孩子的左子树上插入新节点

将A的左孩子B代替A，将A节点称为B的右子树根节点，而B的原右子树则作为A的左子树

RR平衡旋转(左旋转)

在结点A的右孩子的右子树上插入新节点

将A的右孩子B代替A，将A节点称为B的左子树根节点，而B的原左子树则作为A的右子树

可以对比红黑树的旋转，此处逻辑基本相同

5.5.3 哈夫曼树

带权路径长度

路径长度 路径上所经历边的个数

结点的权 结点被赋予的数值

树的带权路径长度 WPL，树中所有叶结点的带权路径长度之和

什么是哈夫曼树

哈夫曼树也称最优二叉树，含有n个带权叶子结点带权路径长度最小的二叉树

哈夫曼树的构造算法

1. 将n个结点作为n棵仅含有一个根节点的二叉树，构成森林F
2. 生成一个新节点，从F中找出根节点权值最小的两棵树作为它的左右子树，新节点的权值为两颗子树的权值之和
3. 从F中删除这两个数，并将新生成的树加入F
4. 重复2，3步骤，直到F中只有一棵树为止

哈夫曼树的性质

1. 每个初始结点都会成为叶节点，双支结点都为新生成的结点
2. 权值越大离根结点越进，反之则越远
3. 哈夫曼树中没有结点为度的1（要么没有子结点，要么两个子结点）
4. n个叶子结点的哈夫曼树的结点总数为2n-1，其中度为2的结点数为n-1

参考内容

什么是哈夫曼树？ - CSDN

第六章

6.1.1 图的基本概念

大概念

线性表	一对一
树	一对多
图	多对多

什么是图

图(Graph)是一种复杂的非线性结构，每个数据之间可任意关联。正是因为任意关联性，导致了图的复杂性。

图的结构

顶点(Vertex): 图中的数据元素

边(Edge): 图中连接顶点的线

无向图

一个图所有的边都没有方向，称为无向图

无序边(v, w) = (w, v)

有向图

一个图边有方向性，称为有向图

有序对<v, w>

权：图的边往往需要表示成为某种数值，这个数值便是该边的权。

除去上面两种还有多种其他概念的图，此处不做深究

Graph Create(); // 建立并返回空图
Graph InsertVertex(Graph G, Vertex V); // 将V插入G
Graph InsertEdge(Graph G, Edge e); // 将e插入G
void DFS(Graph G, Vertex V); // 从V出发深度优先遍历G
void BFS(Graph G, Vertex V); // 从V出发广度优先遍历G
void ShortestPath(Graph G, Vertex V, int Dist[]); // 计算图G中顶点V到任意其他顶点的最短距离
void MST(Graph G); // 计算图G的最小生成树

参考内容

图的java实现 - CSDN

数据结构 – 图 - CSDN

6.2.1 邻接矩阵法

什么是邻接矩阵

给定两个数组，一个一维数组存储顶点信息，一个二维数组存储图中的边的信息

无相图的邻接矩阵是一个对称矩阵

邻接矩阵的优点

1. 直观，便于理解
2. 方面检查任意一对顶点间是否存在边
3. 方便找任一顶点的所有邻接点（有边直接相连的顶点）
4. 方便计算任一顶点的度（从该点出发的边数为出度，指向该点的边数为入度）

• 无向图：对应行列非0元素的个数
• 有向图：对应行非0元素的个数是出度，对应列非0元素的个数是入度

邻接矩阵的缺点

1. 浪费空间 存稀疏图（点多边少）含有大量无效元素

   但对于稠密特别是完全图很划算

2. 浪费时间 统计稀疏图一共又多少边

参考内容

图的存储结构之邻接矩阵 - CSDN

6.2.2 邻接表法

什么是邻接表

为了解决邻接矩阵的缺点，邻接表应运而生

为每一个顶点建立一个单链表存放与他相领的边

顶点表

采用顺序存储，存放顶点的数据和边表的头指针

边表（出边表）

采用链式存储，单链表中存放与一个顶点相邻的所有边，一个链表表示一条从该顶点到链表结点顶点的边

邻接表的特点

1. 更适用于稀疏图
2. 无向图：结点的度为该结点边表的长度
3. 有向图：结点的出度为结点边表的长度，入度要遍历整个邻接表
4. 邻接表不唯一，边表结点的顺序根据算法和输入的不同可能会不同

邻接矩阵和邻接表的比较

	邻接矩阵	邻接表
适用性	稠密图	稀疏图
存储方式	顺序	顺序+链式
判断两顶点间是否存在边	高效	低效
找到某顶点相邻的边	低效	高效

上表中最后一条存疑，邻接矩阵是找到该点然后遍历该行列，邻接表是遍历链表，此处效率应无异

6.2.3 十字链表

什么是十字链表

有向图的一种链式存储结构

十字链表等于邻接表加逆邻接表

6.2.4 邻接多重表

无向图的一种链式存储结构

• mark：标志域，用于标记此节点是否被操作过，例如在对图中顶点做遍历操作时，为了防止多次操作同一节点，mark 域为 0 表示还未被遍历；mark 为 1 表示该节点已被遍历；
• ivex 和 jvex：数据域，分别存储图中各边两端的顶点所在数组中的位置下标；
• ilink：指针域，指向下一个存储与 ivex 有直接关联顶点的节点；
• jlink：指针域，指向下一个存储与 jvex 有直接关联顶点的节点；
• info：指针域，用于存储与该顶点有关的其他信息，比如无向网中各边的权；

vex代表边的前后结点，link代表与其关联的另一条边

十字链表和邻接多重表概念较为复杂，需多多理解

十字链表和邻接多重表可通过一条边去查找任意另一条边，此处可见图的优点与复杂

6.2.5 图的基本操作

Adjacent(G, x, y); // 判断图是否存在边<x,y>或(x,y)
Neighbors(G, x); // 列出图G中与结点x邻接的边
InsertVertex(G, x); // 在图G中插入顶点x
DeleteVerex(G, x); // 在图G中删除顶点x
AddEdge(G, x, y); // 若边(x,y)或<x,y>不存在，则向图G中添加该边
RemoveEdge(G, x, y); // 若边(x,y)或<x,y>存在，则向图G中删除该边
FirstNeighbor(G, x); // 求图G中顶点x的第一个邻接点
NextNeighbor(G, x, y); // 若图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点，若y是x的最后一个邻接点则返回-1
Get_edge_value(G, x, y); // 获取图G中边(x,y)或<x,y>对应的权值v
Set_edge_value(G, x, y); // 设置图G中边(x,y)或<x,y>对应的权值v

6.3.1 广度优先搜索

广度优先搜索(Breadth First Search), BFS

如上图，入队出队顺序参考数组

伪码

void BFS(Vertex V){
    visited[V] = true;
    Enqueue(V, Q);
    while(!IsEmpty(Q)){
        V = Dequeue(Q);
        for(V 的每个邻接点 W){
            if( !visited[W] ){
                visited[W] = true;
                Enqueue(W, Q);
            }
        }
    }
}

若有N个顶点，E条边，时间复杂度是

• 用邻接表存储图，为O(N+E)
• 用邻接矩阵存储图，为[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HPpI7ZHF-1618913823582)(https://www.zhihu.com/equation?tex=O%28n%5E%7B2%7D%29)]

每走一步，都要把周围一圈看一下(队列)

6.3.2 深度优先搜索

深度优先搜索(depth First Search), DFS

void DFS(Vertex V){
    visited[V] = true;
    for(V 的每个邻接点 w){
        if( !visited[W] ){
            DFS(W);
        }
    }
}

若有N个顶点，E条边，时间复杂度是

• 用邻接表存储图，为O(N+E)
• 用邻接矩阵存储图，为[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Zxe2hQaI-1618913823583)(https://www.zhihu.com/equation?tex=O%28n%5E%7B2%7D%29)]

一直走到死胡同，然后回到上个路口换个方向接着走(递归+回溯)

BFS和DFS复杂度大体一致，BFS适合大范围查找，DFS适合目标明确

参考内容

搜索思想——DFS & BFS（基础篇）- 知乎

6.4.1 最小生成树

什么是最小生成树

对于带权无向连通图G = （V, E）,G的所有生成树当中边的权值之和最小的生成树为G的最小生成树(MST)。

边和权值同时最小

Prim算法

此算法可以称为“加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点s开始，逐渐长大覆盖所有顶点

1. 图的所有顶点集合为VV；初始令集合u={s},v=V−uu={s},v=V−u;
2. 在两个集合u,vu,v能够组成的边中，选择一条代价最小的边(u0,v0)(u0,v0)，加入到最小生成树中，并把v0v0并入到集合u中。
3. 重复上述步骤，直到最小生成树有n-1条边或者n个顶点为止。

时间复杂度为O(V平方），适合稠密图

Kruskal算法

此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里面

1. 把图中的所有边按代价从小到大排序；
2. 把图中的n个顶点看成独立的n棵树组成的森林；
3. 按权值从小到大选择边，所选的边连接的两个顶点ui,viui,vi,应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。
4. 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。

时间复杂度为O(ElogE)，适合稀疏图

参考内容

最小生成树的两种方法（Kruskal算法和Prim算法）- CSDN

6.4.2 最短路径

最短路径

两个顶点之间带权路径长度最短的路径为最短路径

迪杰斯特拉（Dijkstra）算法

迪杰斯特拉算法用于解决单源最短路径

什么是迪杰斯特拉算法

每次找到离源点最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径

核心思路还是贪心算法，仙人指路：[贪心算法](# 9.2 贪心算法)

实现思路

1. 通过Dijkstra计算图G中的最短路径时，需要指定起点s(即从顶点s开始计算)。
2. 此外，引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。
3. 初始时，S中只有起点s；U中是除s之外的顶点，并且U中顶点的路径是”起点s到该顶点的路径”。然后，从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 然后，再从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 … 重复该操作，直到遍历完所有顶点。

时间复杂度为O(V的平方)

当出现负权边会影响该算法的判断，比如上图1到2的权改为-3那么0到2的最短就会变更为0 -> 1 -> 2,因此迪杰斯特拉算法不适用含有负权边的图

---

弗洛伊德（Floyd）算法

佛洛依德算法用于解决多源路径

什么是弗洛伊德算法

最开始只允许经过1号顶点进行中转，接下来只允许经过1号和2号顶点进行中转…允许经过1~n号所有顶点进行中转，来不断动态更新任意两点之间的最短路程。即求从i号顶点到j号顶点只经过前k号点的最短路程。

实现思路

**1，**首先构建邻接矩阵Floyd[n+1] [n+1]，假如现在只允许经过1号结点，求任意两点间的最短路程，很显然Floyd[i] [j] = min{Floyd[i] [j], Floyd[i] [1]+Floyd[1] [j]}，代码如下：

**2，**接下来继续求在只允许经过1和2号两个顶点的情况下任意两点之间的最短距离，在已经实现了从i号顶点到j号顶点只经过前1号点的最短路程的前提下，现在再插入第2号结点，来看看能不能更新更短路径，故只需在步骤1求得的Floyd[n+1] [n+1]基础上，进行Floyd[i] [j] = min{Floyd[i] [j], Floyd[i] [2]+Floyd[2] [j]}；…
**3，**很显然，需要n次这样的更新，表示依次插入了1号，2号…n号结点，最后求得的Floyd[n+1] [n+1]是从i号顶点到j号顶点只经过前n号点的最短路程。

特点

Floyd算法适用于APSP(AllPairsShortestPaths)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。

优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单

缺点：时间复杂度高，不适合计算大量数据

参考内容

通俗易懂理解——dijkstra算法求最短路径 - 知乎

最短路径模板+解析——（FLoyd算法） - CSDN

图论（二）：图的四种最短路径算法 - CSDN

6.4.3 拓扑排序

什么是拓扑排序

有向无环图 不存在环的图，简称DAG图

AOV网 若用一个DAG图表示一个工程，其顶点表示活动，用有向边<v1, vj>表示活动vi先于活动vj进行的传递关系，则将这种DAG称为顶点表示活动网络，简称AOV网

拓扑排序 对DAG所有顶点的一种排序，使若存在一条从顶点A到顶点B的路径，在排序中B排在A的后面

举例

如图，我想学习boot，那么前面都要学，我想学jsp，那么java要学，无关联的可任意序列排序，有关联的按照顺序走

思路

1. 从DAG图中选择一个没有前驱的顶点并输出
2. 从图中删除该顶点和以它为起点的边
3. 重复1，2，直到DAG图为空或当前图中不存在无前驱的顶点为止。后者则说明图中有环。

参考内容

拓扑排序详解与实现 - 博客园

6.4.4 关键路径

AOE网

在有向带权图中，以顶点表示事件，以有向边表示活动，以边上权值表示完成该活动的开销，则称这种有向图为用边表示活动的网络，简称AOE网

关键路径

从原点到汇点最大路径长度的路径称为关键路径，关键路径的活动为关键活动

事件的最早发生时间 ve[k]

根据AOE网的性质，只有进入Vk的所有活动<Vj, Vk>都结束，Vk代表的事件才能发生，而活动<Vj, Vk>的最早结束时间为ve[j]+len<Vj, Vk>。所以，计算Vk的最早发生时间的方法为：

ve[0] = 0

ve[k] = max(ve[j] + len<Vj, Vk>)

举例：v2的最早发生时间 = a1 = 3,v5 = a4 + v2 = 6,如果是多条边则取较大值

事件的最早发生时间 vl[k]

vl[k]是指在不推迟整个工期的前提下，事件Vk允许的最迟发生时间。根据AOE网的性质，只有顶点Vk代表的事件发生，从Vk出发的活动<Vk, Vj>才能开始，而活动<Vk, Vj>的最晚开始时间为vl[j] - len<Vk, Vj>。

逆推最早发生时间即可，注意取最小值

活动的最早发生时间：ee[i]

ai由有向边<Vk, Vj>，根据AOE网的性质，只有顶点Vk代表的事件发生，活动ai才能开始，即活动ai的最早开始时间等于事件Vk的最早开始时间。

弧尾 = 最早发生时间

活动的最迟发生时间：el[i]

el[i]是指在不推迟真个工期的前提下，活动ai必须开始的最晚时间。若活动ai由有向边<Vk, Vj>表示，则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后。

弧头 - 开销(边的权重) = 最迟发生时间

活动ai的差额d(i) = l(i) - e(i)

关键路径：{a2, a5, a7}

缩短关键路径活动时间可以加快整个工程，但缩短到一定程度关键路径会改变

当关键活动不唯一时，只有加快的关键活动或者关键活动组合包括在所有的关键路径上才能缩短工期

参考内容

图——关键路径 - CSDN

第七章

7.1.1 查找的基本概念

大概念

什么是查找

在数据集合中寻找满足某种条件的数据元素的过程

查找表

用于查找的数据集合，由同一种数据类型(或记录)的组成，可以是一个数组或链表等数据类型

操作：

• 查询某个特定的数据元素是否在查找表中
• 检索满足条件的某个特定的数据元素的各种属性
• 插入一个数据元素
• 删除一个数据元素

关键字

数据元素中唯一标识该元素的某个数据项的值，使用基于关键字查找，查找结果应该是唯一的

平均查找长度

ASL（Average Search Length），即平均查找长度，在查找运算中，由于所费时间在关键字的比较上，所以把平均需要和待查找值比较的关键字次数称为平均查找长度。

概念如下图

其中n为查找表中元素个数，Pi为查找第i个元素的概率，通常假设每个元素查找概率相同，Pi=1/n，Ci是找到第i个元素的比较次数。

一个算法的ASL越大说明时间性能越差，反之亦然。

参考内容

关于ASL(平均查找长度)的简单总结 - 博客园

7.2.1 顺序查找

什么是顺序查找

主要用于在线性表中进行查找

当无须线性表进行线性查找失败时，需要遍历整个线性表

7.2.2 折半查找

什么是折半查找

也叫二分查找，仅适用于有序的顺序表

思想

首先将给定key与表中间的元素相比较，相等则返回该元素，若不等则如下：

• key小于中间元素，查找前半部分
• key大于中间元素，查找后半部分

重复以上过程，直到找到结果或查找失败

顺序查找和二分查找的区别

顺序查找适用于顺序存储和链式存储，有序无序皆可

二分查找只适用于顺序存储，且要求序列一定有序

7.2.3 分块查找

什么是分块查找

又称索引顺序查找，它吸取了顺序查找和折半查找各自的优点，既有动态结构，又适用于快速查找

如何分块

将查找表分为若干子块。块内的元素无序，但块间是有序的。

建立索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列。

7.3.1 B树

什么是B树

又称多路平衡查找树，B树中所有结点的孩子结点数的最大值称为B数的阶

概念

一颗m阶的B树定义如下：

• 每个结点最多有m-1个关键字。
• 根结点最少可以只有1个关键字。
• 非根结点至少有Math.ceil(m/2)-1个关键字。
• 每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
• 所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。

查找

1. 在B树中找结点（磁盘）
2. 在结点中找关键字（内存）

插入

1. 定位

   查找插入该关键字的位置，既最底层中的某个非叶子结点

2. 插入

   若插入后不会破坏B树的定义，则直接插入即可

   若会破坏B树的定义，则进行分裂操作：

   分裂：

   1. 插入后的结点中间位置关键字并入父结点
   2. 左侧结点留在原地，右侧结点放入新结点
   3. 如果父节点关键字数量超出范围，则继续向上分裂，直到符合要求为止、

常规插入

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lM27DJqU-1618913823590)(C:%5CUsers%5CMOCHEN%5CAppData%5CRoaming%5CTypora%5Ctypora-user-images%5Cimage-20210326224746455.png)]

分裂插入

插入前

插入后

删除

1. 直接删除

   若删除该结点不破坏B树定义，则直接删除

2. 兄弟借

   若删除后破坏B树定义，则向兄弟借：

   1. 将父结点左（右）侧结点拉过来
   2. 将左（右）兄弟拉到父结点

3. 兄弟不借

   若左右兄弟都只有一个关键字，那就合并父结点

   1. 父结点合为兄弟结点
   2. 若条件不满足，重复兄弟借与不借的操作

4. 终端结点（最后一层非叶子结点）

   如果删除的是非终端结点，则进行以下操作：

   1. 替换

      找到它对应的关键字的终端结点，替换删除即可

   2. 合并

      如果它下面只有两个结点，直接合并结点然后删除即可

兄弟借

借之前

借之后

兄弟不借

合并前

合并后

终端结点 - 替换

如下图，33 和 32 替换，然后删除33

终端结点 - 合并

如下图，合并21和24并指向30，删除23

B树的特点

优点：

Ｂ树出现是因为磁盘ＩＯ。ＩＯ操作的效率很低，那么，当在大量数据存储中，查询时我们不能一下子将所有数据加载到内存中，只能逐一加载磁盘页，每个磁盘页对应树的节点。造成大量磁盘ＩＯ操作（最坏情况下为树的高度）。平衡二叉树由于树深度过大而造成磁盘IO读写过于频繁，进而导致效率低下。

常规的二叉树磁盘IO效率很低，比如我找个数需要访问h次，为了减少IO的操作就需要最大程度降低树的高度，将一个瘦长的树变成矮胖的树，因此有了B树

缺点：

难

B树的应用

B树常应用于文件系统和部分数据库索引，以及MongoDB

参考内容

B树详解 - 简书

B树与B+树 - CSDN

漫画 B树 B-树 - CSDN

7.3.2 B+树

概念

1. 根结点至少有两个孩子。

2. 每个中间节点都至少包含ceil(m / 2)个孩子，最多有m个孩子。

3. 每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m。

4. 所有的叶子结点都位于同一层。

5. 每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

图示

B树与B+树的区别

1. B+树中，具有n个关键字的结点值含有n棵子树，既每个关键字对应一颗子树

   B树中，具有n个关键字的结点值含有n棵子树

2. B+树中，非叶结点只保存索引，所有信息存放在叶节点中

   B树中，每个结点保存一个信息

3. B+树中，叶结点包含全部关键字，非叶结点中出现的关键字也会出现在叶结点中

   B树中，叶结点包含的关键字和其他结点不重复

7.4.1 散列表的基本概念

散列函数

一个把从查找表中的关键字映射成该关键字对应的地址的函数

散列表

根据关键字而直接进行访问的数据结构。它建立了关键字与存储地址之间的一种直接映射关系

冲突

散列函数可能会把多个不同的关键字映射到同一地址下的情况

7.4.2~7.4.4 散列函数的构造方法和冲突处理

要求

1. 散列函数的定义域必须包含全部需要存储的关键字，而值域则依赖于散列表的大小和地址范围
2. 散列函数计算出来的地址应该能等概率，均匀的分布在整个地址空间中，最大程度减少冲突的发生
3. 散列函数应尽量简单，能在较短时间内计算出任一关键字对应的散列地址

方法

直接定址法

直接取关键字的某个线性函数值为散列地址

Hash(key) = a * key + b

其中a,b为常数

方法简单，不会产生冲突，若关键字分布不连续则会浪费空间

除留取余法

假定散列表表长为m，取一个不大于m但最接近或等于m的质数p

Hash(key) = key % p

选好p是关键，可以减少冲突

数字分析法

前八位相同，取后四位

适用于关键字已知的集合，若更换关键字则需要重新构造散列函数

平方取中法

取关键字的平方值的中间几位作为散列地址

适用于关键字的每位取值不均匀或小于散列地址所需要的位数

折叠法

将关键字分割成位数相同的几部分，然后将这几部分相加作为散列地址

适用于关键字的位数多，而且关键字中的每位上数字分布大致均与

开放定址法

是指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放

Hi = (H(key) + di) % m

i = 0,1,2,…,k(k <= m - 1);

m为散列表表长

di为增量序列

如何计算增量序列

线性探查法

既 di = 0,1,2,…,k

平方探测法

既 di = 0平方，1平方，-1平方，2平方，-2平方，…,k平方，-k平方，其中k <= m / 2

避免堆积问题，缺点是不能探测到散列表上的所有单元

再散列法

既 di = i * Hash2(key)

伪随机序列法

既 di = 伪随机序列

开放定址法不能随便删除某个元素

拉链法（重点）

把所有同义词存放在一个线性链表中，这个线性链表由地址唯一表示，既散列表中每个单元存放该链表头指针

数组每个成员包括一个指针，指向一个数组

拉链法适用于经常进行插入和删除的情况

查找效率

散列函数，处理冲突的方法和填装因子

填装因子

一般记为阿尔法，表示表的装满程度

散列表的平均查找长度依赖于散列表的填装因子

散列表的特点

和数组以及链表对比：

	查找	增删
数组	快	慢
链表	慢	快
散列表	快	快

优点

接近O(1)的时间复杂度，碾压一切渣渣

缺点

因为是基于数组的，所以填装因子越大性能越低，因此必须要清楚表中将要存储多少数据

概念

参考内容

哈希表（散列表）原理详解 - CSDN

第八章

8.1 排序的基本概念

大概念

排序

重新定义表中的元素，使表中的元素按照关键字递增或递减

排序算法的稳定性

排序后两个相同的元素不发生变动，则为稳定，反之则为不稳定

如下图，淡蓝色小朋友排序后仍在深蓝色小朋友之前，则这个算法就是稳定的

稳定性只是算法的性质，无法评定算法的优劣

内部排序与外部排序

内部排序

指在排序期间全部放在内存中排序

外部排序

指在排序期间无法全部放在内存中，在排序过程中根据要求不断的在内，外存中移动

此处仅探讨内部排序

时空复杂度决定内部排序算法的性能

8.2.1 直接插入排序

动图演示

实现思路

1. 从第二个参数开始往前比较，如果上个参数比当前参数大则交换位置
2. 继续对比，直到前面没有比自身更大的数
3. 重复第二步，直到全部数据排完

实现代码

import java.util.Arrays;

/**
 * @Description: 插入排序
 * @Author: MoChen
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arrs = {1, 2, 5, 2, 3, 6, 7, 4};
        InsertSort is = new InsertSort();
        System.out.println(Arrays.toString(is.insSort(arrs)));
    }

    /**
     * 每次将当前数字与前面所有位数比较，前面大则交换，否则看下一个数字
     */
    public int[] insSort(int[] arrs){
        for (int i = 1; i < arrs.length; i++) {
            int j = i;
            while (j > 0){
                if (arrs[j] < arrs[j - 1]){
                    int temp ;
                    temp = arrs[j];
                    arrs[j] = arrs[j - 1];
                    arrs[j-1] = temp;
                    j--;
                }else {
                    break;
                }
            }
        }
        return arrs;
    }
    
    /**
     * 1. 从第二个数字开始遍历，将当前数字放入数组第一位当作哨兵使用
     * 2. 从当前数字往前遍历，只要大于哨兵就往前移一位
     * 3. 将哨兵赋给下一位，完成交换操作
     * 4. 重复以上操作，直到数据完成排序
     */
    public int[] insSortSent(int[] arrs){
        int i = 0, j = 0;
        int[] newArrs = new int[arrs.length + 1];
        // 将当前数组扩容一位，保证第一位是哨兵
        System.arraycopy(arrs, 0, newArrs, 1, arrs.length);
        for(i = 2; i < newArrs.length; i++){
            newArrs[0] = newArrs[i];
            for(j = i - 1; newArrs[0] < newArrs[j]; j--){
                newArrs[j + 1] = newArrs[j];
            }
            newArrs[j + 1] = newArrs[0];
        }
        // 归还结果
        arrs = Arrays.copyOfRange(newArrs, 1, newArrs.length);
        return arrs;
    }
}

此处while可以改成for，for版本代码更简洁，用while更清晰故使用while

教材代码虽然简洁但是偏难，需多多理解

概念

时间复杂度为[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zyBxBs5G-1618913823601)(https://www.zhihu.com/equation?tex=O%28n%5E%7B2%7D%29)]，可采用顺序存储和链式存储

参考内容

插入排序 - 沐雨橙风~~ - 博客园

8.2.2 折半插入排序

概念

二分查找 + 插入排序

减少了比较次数，但是元素的移动次数不变。平均时间复杂度为O(n^2)；空间复杂度为O(1)；是稳定的排序算法。

实现代码

/**
     * 折半插入排序
     */
    public int[] bInsSort(int[] arrs){
        int i = 0,j = 0;
        int low = 0, high = 0, mid = 0;
        int[] newArrs = new int[arrs.length + 1];
        // 将当前数组扩容一位，保证第一位是哨兵
        System.arraycopy(arrs, 0, newArrs, 1, arrs.length);
        for(i = 2; i < newArrs.length; i++){
            newArrs[0] = newArrs[i];
            low = 1;
            high = i - 1;
            while(low <= high){
                mid = (low + high) / 2;
                if(newArrs[mid] > newArrs[0]){
                    high = mid - 1;
                }else{
                    low = mid + 1;
                }
            }
            for(j = i - 1; j >= high + 1; j--){
                newArrs[j + 1] = newArrs[j];
            }
            newArrs[high + 1] = newArrs[0];
        }
        // 归还结果
        arrs = Arrays.copyOfRange(newArrs, 1, newArrs.length);
        return arrs;
    }

同上，此处也可使用非哨兵模式，同步教材代码故使用哨兵模式

时间复杂度下界

对于下标i < j, 如果A[i] > A[j], 则称(i, j)是一对逆序对

只要后面的数字比当前位数小，就是逆序对，交换元素的排序算法本质就是消除逆序对

任何仅以交换相邻两元素来排序的算法，其平均时间复杂度为**[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BwUVO1aO-1618913823602)(https://www.zhihu.com/equation?tex=O%28n%5E%7B2%7D%29)]**

参考内容

排序----折半插入排序 - CSDN

经典排序算法（4）——折半插入排序算法详解 - CSDN

8.2.3 希尔排序

什么是希尔排序

希尔排序是一种改进后的插入排序，也称缩小增量排序。

按照增量序列进行插入排序，最后一步增量序列为1

如下图，第一个按照五个间隔排序，第二次按照三个间隔排序，最后一次按照一个间隔排序，这里的5，3，1就是增量序列

实现代码

    /**
     * 希尔排序
     */
    public int[] shellSort(int[] arrs){
        for(int dk = arrs.length / 2; dk >= 1; dk /= 2){
            for(int i = dk + 1; i < arrs.length; i++){
                int j = i;
                int temp = arrs[j];
                for(j = i; j >= dk && arrs[i - dk] > temp; i -= dk){
                    arrs[i] = arrs[i - dk];
                }
                arrs[i] = temp;
            }
        }
        return arrs;
    }

思路很简单，就是插入排序外面套一层增量序列的循环

概念

希尔排序的最坏时间复杂度依然是[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Rdwat4wa-1618913823603)(https://www.zhihu.com/equation?tex=O%28n%5E%7B2%7D%29)]，但是往往并达不到这种程度

采用优化的增量序列可以最大程度减少时间复杂度，比如Hibbard等等

参考内容

图解排序算法(二)之希尔排序 - 博客园

8.3.1 冒泡排序

什么是冒泡排序

类似于冒泡，大的数沉下去，小的数浮上来，所以叫冒泡排序

每次遍历将最大的数字移到末尾

动图演示

实现代码

    /**
     * 冒泡排序
     */
    public int[] bubbleSort(int[] arrs){
        for(int i = 0; i < arrs.length; i++){
            for(int j = 0; j < arrs.length - i - 1; j++){
                if(arrs[j] > arrs[j + 1]){
                    int temp = arrs[j];
                    arrs[j] = arrs[j + 1];
                    arrs[j + 1] = temp;
                }
            }
        }
        return arrs;
    }

概念

思路就是比较，交换，该算法过于经典不多描述

参考内容

排序-冒泡排序 - 简书

8.3.2 快速排序

什么是快速排序

快排的性能在所有排序算法里面是最好的，数据规模越大快速排序的性能越优。快排在极端情况下会退化成 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6SvSbbug-1618913823604)(https://www.zhihu.com/equation?tex=O%28n%5E%7B2%7D%29)] 的算法，因此假如在提前得知处理数据可能会出现极端情况的前提下，可以选择使用较为稳定的归并排序。

动图演示

实现思路

• 选择A中任意一个元素pivot,该元素作为基准
• 将小于基准的元素移到左边，大于基准的移到右边
• A被pivot分为两部分，继续对剩下的两部分做同样的处理
• 重复以上操作，直到数据排序完成

实现代码

    /**
     * 快速排序
     */
    public int[] quickSort(int[] arrs, int low, int high){
        int i = low, j = high;
        int temp = 0;
        if(i < j){
            temp = arrs[i];
            while(i != j){
                while(j > i && arrs[j] > temp){
                    --j;
                }
                arrs[i] = arrs[j];
                while(i < j && arrs[i] < temp){
                    ++i;
                }
                arrs[j] = arrs[i];
            }
            arrs[i] = temp;
            quickSort(arrs, low, i - 1);
            quickSort(arrs, i + 1, high);
        }
        return arrs;
    }

更标准的写法应该是两个方法，一个拿基准，一个递归排序，此处图简洁不做实现

参考内容

排序–快速排序 - 知乎

快速排序—(面试碰到过好几次) - CSDN

8.4.1 直接选择排序

什么是选择排序

每次从无序中选出最小元（最小关键字），将最小元放入有序的后面

和插入不同，插入是交换有序序列，选择是追加到有序后面

和冒泡大抵相同，不过冒泡是每次交换n-1次，选择是交换两次

实现代码

    /**
     * 选择排序
     */
    public int[] selectSort(int[] arrs){
        for(int i = 0; i < arrs.length; i++){
            int min = i;
            for(int j = i + 1; j < arrs.length; j++){
                if(arrs[j] < arrs[min]){
                    min = j;
                }
            }
            if(min != i){
                // 交换
                arrs[i] = arrs[i] + arrs[min];
                arrs[min] = arrs[i] - arrs[min];
                arrs[i] = arrs[i] - arrs[min];
            }
        }
        return arrs;
    }

一次排序将一个元素放置到最终的位置上

8.4.2 堆排序

什么是堆排序

堆排序是一种**选择排序，**它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。

堆

堆是具有以下性质的完全二叉树：

每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；

每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

如下图：

实现代码

import java.util.Arrays;

/**
 * @Description: 堆排序
 * @Author: MoChen
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] arrs = {1, 2, 5, 3, 6, 7, 4};
        heapSort(arrs);
        System.out.println(Arrays.toString(arrs));
    }

    /**
     * 堆排序
     */
    public static void heapSort(int[] arrs){
        // 1. 构建大顶堆
        for(int i = arrs.length / 2 - 1; i >= 0; i--){
            adjustHeap(arrs, i, arrs.length);
        }
        // 2. 调整堆结构 + 交换堆顶元素与末尾元素
        for(int j = arrs.length - 1; j > 0; j--){
            swap(arrs, 0, j);
            adjustHeap(arrs, 0, j);
        }
    }

    /**
     * 调整大顶堆
     */
    public static void adjustHeap(int[] arrs, int i, int length){
        int temp = arrs[i];
        for(int k = i * 2 + 1; k < length; k = k * 2 + 1){
            if(k + 1 < length && arrs[k] < arrs[k + 1]){
                k++;
            }
            if(arrs[k] > temp){
                arrs[i] = arrs[k];
                i = k;
            }else{
                break;
            }
        }
        arrs[i] = temp;
    }

    /**
     * 交换元素
     */
    public static void swap(int[] arrs, int a, int b){
        int temp = arrs[a];
        arrs[a] = arrs[b];
        arrs[b] = temp;
    }
}

概念

1. 将无序序列构建成一个大顶堆（小顶堆同理）

   1. 将每个子树的最大值调整为父节点
   2. 重复上一步，直到根节点为最大值，堆构建完成

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

3. 重新调整结构，使其满足堆定义，然后重复第二步，反复执行调整+交换步骤，直到整个序列有序

参考内容

图解排序算法(三)之堆排序 - 博客园

8.5.1 归并排序

什么是归并排序

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略

分治法将问题分(divide)成一些小的问题然后递归求解，而**治(conquer)**的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之

动图演示

代码实现

import java.util.Arrays;

/**
 * @Description: 归并排序
 * @Author: MoChen
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {1, 13, 24, 26, 2, 15, 27, 38};
        int[] temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        mergeSort(arr, 0, arr.length - 1, temp);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 归并排序
     */
    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid, temp);//左边归并排序，使得左子序列有序
            mergeSort(arr, mid + 1, right, temp);//右边归并排序，使得右子序列有序
            merge(arr, left, mid, right, temp);//将两个有序子数组合并操作
        }
    }

    /**
     * 合并有序子列
     */
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;//左序列指针
        int j = mid + 1;//右序列指针
        int t = 0;//临时数组指针
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[t++] = arr[i++];
            } else {
                temp[t++] = arr[j++];
            }
        }
        while (i <= mid) {//将左边剩余元素填充进temp中
            temp[t++] = arr[i++];
        }
        while (j <= right) {//将右序列剩余元素填充进temp中
            temp[t++] = arr[j++];
        }
        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while (left <= right) {
            arr[left++] = temp[t++];
        }
    }
}

思路

上面两个图示已经比较明显，此处不做思路总结

参考内容

图解排序算法(四)之归并排序 - 博客园

【算法】排序算法之归并排序 - 知乎

8.5.2 基数排序

什么是基数排序

不同于以往的排序，基数排序无需进行比较或者交换，他通过分配和收集进行排序

思路

依照位数进行排序，比如三位数先进行个分位分配，然后十分位，百分位

可以这么理解，先对最后一位进行排序，然后往前一位，直到第一位，第一位排序完成即可

此章非重点不多做解释，感兴趣可去参考内容了解

参考内容

排序算法系列：基数排序 - CSDN

基数排序 顺序实现与链式实现

8.6 内部排序算法的比较及应用

考虑因素

综合考虑：元素数量，元素大小，关键字结构及分布，稳定性，存储结构，辅助空间

1. 若n较小(n<=50)时，可采用直接插入排序或简单选择排序，若n较大时，则采用快排，堆排或归并排序
2. 若n很大，关键字位数较小且可分解，采用基数排序
3. 当文件的n个关键字随机分布，任何借助于比较的排序，至少需要O(nlog2n)的时间
4. 若初始基本有序，则采用直接插入或冒泡排序
5. 当记录元素较大，应避免大量的移动的排序算法，尽量次啊用链式存储

每种排序算法都有它存在的意义，实际应用中应根据实际情况选择使用那种排序

8.7.1~8.7.2 外部排序的算法

什么是外部排序

对内存中的数据进行排序叫内部排序，内存外的数据排序即为外部排序

外部排序通常采用归并排序

举例

内存中只能放三个数，现在有十二个数，如何实现排序？

利用归并排序的思想，先分成四分进行依次排序，然后进行合并

两两合并子串，得到两个长度为六的子串，然后进行最后一次合并：

时间复杂度

外部排序的时间 = 内部排序的时间 + 外存读写时间 + 内部排序归并的时间

8.7.3 失败树

什么是失败树

树形选择排序的一种变体，可视为一颗完全二叉树

每个叶结点存放各归段在归并过程中参加比较的记录，内部结点用来记忆左右子树中的失败者，胜利者则向上继续比较，直到根节点

8.7.4 置换-选择排序

思路

设初始待排序文件为FI，初始归并段位FO,内存为WA,可容纳w个记录

1. 从FI中输入w个记录到WA
2. 从WA中选出最小值，输出到FO
3. 从FI中重新读入一个值，重复第二步操作
4. 重复2~3,直到选不出最小值，此处得到第一个归并段
5. 重复2~4，直到WA为空，得到所有初始归并段

示例

如下图所示，先进入三个数，最小值05给出去同事下一个数44进来，然后挑选比05大的第一个数17进来，重复操作知道56，后面没有最小值，此时得到第一个归并段；然后重复上述操作即可

8.7.5 最佳归并树

在上一章的基础上，将归并树转化为哈夫曼树，即为最佳归并树

如上图，该归并树IO次数为2 * WPL = 484

该树IO次数位 2 * WPL = 446，所以称为最佳归并树

当叶子结点不够时，增加权值为0的结点用来构造哈夫曼树

总结

可使用多路归并，最优为置换选择

参考内容

【漫画】什么是外部排序？ - 搜狐

外部排序&多路归并排序 - 博客园

第九章 - 补充

9.1 红黑树

什么是红黑树

为了解决二叉查找树多次单侧插入新节点导致的不平衡，红黑树应运而生

红黑树基于二叉查找树实现，它具有以下特点：

1. 节点是红色或黑色
2. 根节点是黑色
3. 每个叶子节点都是黑色的空节点（NIL节点）
4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5. 任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

红黑树的优点

正是因为有了上述繁琐的规则限制，才保证了红黑树的自平衡。红黑树从根到叶子的最长路径不会超过最短路径的2倍。

红黑树的调整

当插入或删除节点的时候，有可能会打破规则，这个时候就需要根据情况做出调整，以此来维持规则

调整有两种方法，变色和旋转，而旋转又分为左旋转和右旋转

变色

变色就是字面意思变色

旋转

左旋转

逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子

Y变成爹，X变成儿子，代价是左腿给X

右旋转

顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子

举例

如上图所示，该情况打破了规则4，解决方案如下：

变色

1. 22变为黑色
2. 25变为红色
3. 27变为黑色

旋转

此时变色已经无法解决问题了，就需要用到旋转

4. 13和17进行左旋转
5. 13变为红色，17变为黑色

此时并没有结束，路径(17 -> 8 -> 6 -> NIL)的黑色节点个数是4，其他路径的黑色节点个数是3，不符合规则5，我们继续操作：

6. 13和8进行右旋转
7. 8，15变为红色，13变为黑色

结果

参考内容

面试常问：什么是红黑树？- CSDN

9.2 贪心算法

顾名思义，贪心算法总是做出当前看来最好的选择，也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。

思路

1. 把问题分解成若干个问题
2. 求出每个子问题的最优解
3. 将每个局部最优解合并，得到结果的最优解

贪心策略适用的前提是：局部最优策略能导致产生全局最优解。

我也不太会，看漫画吧，漫画比较详细

参考内容

漫画：五分钟学会贪心算法 - 知乎

五大常用算法之一：贪心算法 - 简书

总结

后言

数据结构更多是一种思想，非算法从业者或考研可不做重点学习

既然说了是思想，就要明白为什么学这个，期望掌握什么，多思考，多code，才是出路

墨尘 2021年2月1日
通常用树的双亲表示法作为并查集的存储结构

通常用数组元素的下标代表元素名，用根节点的下标代表子集合名，根节点的双亲结点为负数。

Initial(S)	// 将集合S中的每个元素都初始化为只有一个单元素的子集合
Union(S, Root1, Root2) // 把集合S中的子集合（互不相交）Root2并入子集合Root1
Find(S, x) // 查找集合S中单元素x所在子集合，并返回该子集合的名字

概念

5.3.2 线索二叉树

线索二叉树的概念

线索化

若无左子树，则将左指针指向其前驱结点

若无右子树，则将右指针指向其后驱结点

优点

将原本的空指针都替换为前驱和后驱，可以加快结点的查询

5.4.1 树的存储结构

双亲表示法

采用一组连续的存储空间来存储每个结点，同时每个结点中增设一个伪指针，指向双亲结点在数组中的位置。根节点的下标为0，其伪指针域为-1。

多一个指针，指向父节点，没爹则给-1。

孩子表示法

将每个结点的孩子结点都用单链表连接起来形成一个线性结构，n个结点具有n个孩子链表。

每个结点的所有子结点就是一个单链表。

孩子兄弟表示法

以二叉链表作为树的存储结构，又称二叉树表示法。

左指针指向第一个孩子，右子针指向下一个兄弟。

优缺点对比

	优点	缺点
双亲表示法	寻找双亲效率高	寻找孩子效率低
孩子表示法	寻找孩子效率高	寻找双亲效率低
孩子兄弟表示法	寻找孩子效率高 方便树转换为二叉树	寻找双亲效率低

5.4.2~5.4.3 树和森林

树与二叉树的转换

可用上一章的左孩子右兄弟的办法进行转换。

森林与二叉树的转换

先转为二叉树，在将每棵二叉树的根依次作为上一棵二叉树的右子树。

树的遍历

按照某种方式访问树中的每个结点，且仅访问一次

先根遍历

先访问根结点，在按照从左到右的顺序遍历根节点的子树

树的先根遍历与这棵树对应二叉树的先序遍历相同

后根遍历

先按照从左到右的顺序遍历根节点的子树，在访问根结点

树的后根遍历与这棵树对应二叉树的中序遍历相同

举例

先根遍历：RADEBCFGHK

后根遍历：DEABGHKFCR

森林的遍历

先序遍历

1. 访问第一棵树的根结点
2. 先序遍历第一棵树的子树森林
3. 先序遍历除去第一棵树之后剩余的树构成的子树森林

中序遍历

1. 中序遍历第一棵树的根结点的子树森林
2. 访问第一棵树的根结点
3. 中序遍历除去第一棵树之后剩余的树构成的子树森林

5.4.4 树的应用并查集

什么是并查集

并查集主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：

• 合并（Union）：把两个不相交的集合合并为一个集合。
• 查询（Find）：查询两个元素是否在同一个集合中。

实现代码

/**
 * @Description: 并查集
 * @Author: MoChen
 */
public class UnionFind {

    static final int MAX_SIZE = 10;
    int fa[] = new int[MAX_SIZE];

    /**
     * 初始化
     */
    void initial(int n){
        for(int i = 1; i <= n; ++i){
            fa[i] = i;
        }
    }

    /**
     * 查询
     */
    int find(int x){
        return x == fa[x] ? x : (fa[x] = find(fa[x]));
    }

    /**
     * 合并
     */
    void merge(int i, int j){
        fa[find(i)] = find(j);
    }

}

按秩合并

合并时，优先将简单的树往复杂的树上面合，从而达到最小程度影响深度

实现思路

重新给定一个数组rank[]记录每个树的深度，开始所有rank设为1。合并时比较两个根节点，把rank较小者往较大者上合并。

注意：按秩合并会带来额外的空间复杂度

此概念为优化，此处暂不做深究

参考内容

算法学习笔记(1):并查集 - 知乎

5.5.1 二叉排序树

什么是二叉排序树

二叉排序树(Binary Sort Tree),也称二叉查找树

1. 左子树所有节点均小于根节点
2. 右子树所有节点均大于根节点
3. 左右子树也是二叉排序树

插入

若二叉排序树为空，则直接插入

若二叉排序树非空，当值小于根节点时插入左子树，当值大于根节点时插入右子树，当值等于根节点则不插入

构造二叉排序树

读入元素并建立节点，若二叉树为空则将其作为根节点

若二叉排序树非空，当值小于根节点时插入左子树，当值大于根节点时插入右子树，当值等于根节点则不插入

思路和插入一样

删除

1. 若被删除节点是叶节点，则直接删除
2. 若被删除节点z只有一棵子树，则让z的子树指向z的父节点，代替z节点
3. 若被删除节点z有两颗子树，则让z的右子树最小的节点替换z

5.5.2 平衡二叉树

什么是平衡二叉树

平衡二叉树(AVL)，每个节点的左子树和右子树的高度差最多为1

AVL是取自作者名

平衡二叉树的判断

1. 判断左子树是一颗平衡二叉树
2. 判断右子树是一颗平衡二叉树
3. 判断该节点为根的二叉树为平衡二叉树

平衡树的旋转

LL平衡旋转(右旋转)

在结点A的左孩子的左子树上插入新节点

将A的左孩子B代替A，将A节点称为B的右子树根节点，而B的原右子树则作为A的左子树

RR平衡旋转(左旋转)

在结点A的右孩子的右子树上插入新节点

将A的右孩子B代替A，将A节点称为B的左子树根节点，而B的原左子树则作为A的右子树

可以对比红黑树的旋转，此处逻辑基本相同

5.5.3 哈夫曼树

带权路径长度

路径长度 路径上所经历边的个数

结点的权 结点被赋予的数值

树的带权路径长度 WPL，树中所有叶结点的带权路径长度之和

什么是哈夫曼树

哈夫曼树也称最优二叉树，含有n个带权叶子结点带权路径长度最小的二叉树

哈夫曼树的构造算法

1. 将n个结点作为n棵仅含有一个根节点的二叉树，构成森林F
2. 生成一个新节点，从F中找出根节点权值最小的两棵树作为它的左右子树，新节点的权值为两颗子树的权值之和
3. 从F中删除这两个数，并将新生成的树加入F
4. 重复2，3步骤，直到F中只有一棵树为止

哈夫曼树的性质

1. 每个初始结点都会成为叶节点，双支结点都为新生成的结点
2. 权值越大离根结点越进，反之则越远
3. 哈夫曼树中没有结点为度的1（要么没有子结点，要么两个子结点）
4. n个叶子结点的哈夫曼树的结点总数为2n-1，其中度为2的结点数为n-1

参考内容

什么是哈夫曼树？ - CSDN

第六章

6.1.1 图的基本概念

大概念

线性表	一对一
树	一对多
图	多对多

什么是图

图(Graph)是一种复杂的非线性结构，每个数据之间可任意关联。正是因为任意关联性，导致了图的复杂性。

图的结构

顶点(Vertex): 图中的数据元素

边(Edge): 图中连接顶点的线

无向图

一个图所有的边都没有方向，称为无向图

无序边(v, w) = (w, v)

有向图

一个图边有方向性，称为有向图

有序对<v, w>

权：图的边往往需要表示成为某种数值，这个数值便是该边的权。

除去上面两种还有多种其他概念的图，此处不做深究

Graph Create(); // 建立并返回空图
Graph InsertVertex(Graph G, Vertex V); // 将V插入G
Graph InsertEdge(Graph G, Edge e); // 将e插入G
void DFS(Graph G, Vertex V); // 从V出发深度优先遍历G
void BFS(Graph G, Vertex V); // 从V出发广度优先遍历G
void ShortestPath(Graph G, Vertex V, int Dist[]); // 计算图G中顶点V到任意其他顶点的最短距离
void MST(Graph G); // 计算图G的最小生成树

参考内容

图的java实现 - CSDN

数据结构 – 图 - CSDN

6.2.1 邻接矩阵法

什么是邻接矩阵

给定两个数组，一个一维数组存储顶点信息，一个二维数组存储图中的边的信息

无相图的邻接矩阵是一个对称矩阵

邻接矩阵的优点

1. 直观，便于理解
2. 方面检查任意一对顶点间是否存在边
3. 方便找任一顶点的所有邻接点（有边直接相连的顶点）
4. 方便计算任一顶点的度（从该点出发的边数为出度，指向该点的边数为入度）

• 无向图：对应行列非0元素的个数
• 有向图：对应行非0元素的个数是出度，对应列非0元素的个数是入度

邻接矩阵的缺点

1. 浪费空间 存稀疏图（点多边少）含有大量无效元素

   但对于稠密特别是完全图很划算

2. 浪费时间 统计稀疏图一共又多少边

参考内容

图的存储结构之邻接矩阵 - CSDN

6.2.2 邻接表法

什么是邻接表

为了解决邻接矩阵的缺点，邻接表应运而生

为每一个顶点建立一个单链表存放与他相领的边

顶点表

采用顺序存储，存放顶点的数据和边表的头指针

边表（出边表）

采用链式存储，单链表中存放与一个顶点相邻的所有边，一个链表表示一条从该顶点到链表结点顶点的边

邻接表的特点

1. 更适用于稀疏图
2. 无向图：结点的度为该结点边表的长度
3. 有向图：结点的出度为结点边表的长度，入度要遍历整个邻接表
4. 邻接表不唯一，边表结点的顺序根据算法和输入的不同可能会不同

邻接矩阵和邻接表的比较

	邻接矩阵	邻接表
适用性	稠密图	稀疏图
存储方式	顺序	顺序+链式
判断两顶点间是否存在边	高效	低效
找到某顶点相邻的边	低效	高效

上表中最后一条存疑，邻接矩阵是找到该点然后遍历该行列，邻接表是遍历链表，此处效率应无异

6.2.3 十字链表

什么是十字链表

有向图的一种链式存储结构

十字链表等于邻接表加逆邻接表

6.2.4 邻接多重表

无向图的一种链式存储结构

• mark：标志域，用于标记此节点是否被操作过，例如在对图中顶点做遍历操作时，为了防止多次操作同一节点，mark 域为 0 表示还未被遍历；mark 为 1 表示该节点已被遍历；
• ivex 和 jvex：数据域，分别存储图中各边两端的顶点所在数组中的位置下标；
• ilink：指针域，指向下一个存储与 ivex 有直接关联顶点的节点；
• jlink：指针域，指向下一个存储与 jvex 有直接关联顶点的节点；
• info：指针域，用于存储与该顶点有关的其他信息，比如无向网中各边的权；

vex代表边的前后结点，link代表与其关联的另一条边

十字链表和邻接多重表概念较为复杂，需多多理解

十字链表和邻接多重表可通过一条边去查找任意另一条边，此处可见图的优点与复杂

6.2.5 图的基本操作

Adjacent(G, x, y); // 判断图是否存在边<x,y>或(x,y)
Neighbors(G, x); // 列出图G中与结点x邻接的边
InsertVertex(G, x); // 在图G中插入顶点x
DeleteVerex(G, x); // 在图G中删除顶点x
AddEdge(G, x, y); // 若边(x,y)或<x,y>不存在，则向图G中添加该边
RemoveEdge(G, x, y); // 若边(x,y)或<x,y>存在，则向图G中删除该边
FirstNeighbor(G, x); // 求图G中顶点x的第一个邻接点
NextNeighbor(G, x, y); // 若图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点，若y是x的最后一个邻接点则返回-1
Get_edge_value(G, x, y); // 获取图G中边(x,y)或<x,y>对应的权值v
Set_edge_value(G, x, y); // 设置图G中边(x,y)或<x,y>对应的权值v

6.3.1 广度优先搜索

广度优先搜索(Breadth First Search), BFS

如上图，入队出队顺序参考数组

伪码

void BFS(Vertex V){
    visited[V] = true;
    Enqueue(V, Q);
    while(!IsEmpty(Q)){
        V = Dequeue(Q);
        for(V 的每个邻接点 W){
            if( !visited[W] ){
                visited[W] = true;
                Enqueue(W, Q);
            }
        }
    }
}

若有N个顶点，E条边，时间复杂度是

• 用邻接表存储图，为O(N+E)
• 用邻接矩阵存储图，为[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4gxfuS2z-1618913822548)(https://www.zhihu.com/equation?tex=O%28n%5E%7B2%7D%29)]

每走一步，都要把周围一圈看一下(队列)

6.3.2 深度优先搜索

深度优先搜索(depth First Search), DFS

void DFS(Vertex V){
    visited[V] = true;
    for(V 的每个邻接点 w){
        if( !visited[W] ){
            DFS(W);
        }
    }
}

若有N个顶点，E条边，时间复杂度是

• 用邻接表存储图，为O(N+E)
• 用邻接矩阵存储图，为[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-J2LiA7uw-1618913822549)(https://www.zhihu.com/equation?tex=O%28n%5E%7B2%7D%29)]

一直走到死胡同，然后回到上个路口换个方向接着走(递归+回溯)

BFS和DFS复杂度大体一致，BFS适合大范围查找，DFS适合目标明确

参考内容

搜索思想——DFS & BFS（基础篇）- 知乎

6.4.1 最小生成树

什么是最小生成树

对于带权无向连通图G = （V, E）,G的所有生成树当中边的权值之和最小的生成树为G的最小生成树(MST)。

边和权值同时最小

Prim算法

此算法可以称为“加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点s开始，逐渐长大覆盖所有顶点

1. 图的所有顶点集合为VV；初始令集合u={s},v=V−uu={s},v=V−u;
2. 在两个集合u,vu,v能够组成的边中，选择一条代价最小的边(u0,v0)(u0,v0)，加入到最小生成树中，并把v0v0并入到集合u中。
3. 重复上述步骤，直到最小生成树有n-1条边或者n个顶点为止。

时间复杂度为O(V平方），适合稠密图

Kruskal算法

此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里面

1. 把图中的所有边按代价从小到大排序；
2. 把图中的n个顶点看成独立的n棵树组成的森林；
3. 按权值从小到大选择边，所选的边连接的两个顶点ui,viui,vi,应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。
4. 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。

时间复杂度为O(ElogE)，适合稀疏图

参考内容

最小生成树的两种方法（Kruskal算法和Prim算法）- CSDN

6.4.2 最短路径

最短路径

两个顶点之间带权路径长度最短的路径为最短路径

迪杰斯特拉（Dijkstra）算法

迪杰斯特拉算法用于解决单源最短路径

什么是迪杰斯特拉算法

每次找到离源点最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径

核心思路还是贪心算法，仙人指路：[贪心算法](# 9.2 贪心算法)

实现思路

1. 通过Dijkstra计算图G中的最短路径时，需要指定起点s(即从顶点s开始计算)。
2. 此外，引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。
3. 初始时，S中只有起点s；U中是除s之外的顶点，并且U中顶点的路径是”起点s到该顶点的路径”。然后，从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 然后，再从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 … 重复该操作，直到遍历完所有顶点。

时间复杂度为O(V的平方)

当出现负权边会影响该算法的判断，比如上图1到2的权改为-3那么0到2的最短就会变更为0 -> 1 -> 2,因此迪杰斯特拉算法不适用含有负权边的图

---

弗洛伊德（Floyd）算法

佛洛依德算法用于解决多源路径

什么是弗洛伊德算法

最开始只允许经过1号顶点进行中转，接下来只允许经过1号和2号顶点进行中转…允许经过1~n号所有顶点进行中转，来不断动态更新任意两点之间的最短路程。即求从i号顶点到j号顶点只经过前k号点的最短路程。

实现思路

**1，**首先构建邻接矩阵Floyd[n+1] [n+1]，假如现在只允许经过1号结点，求任意两点间的最短路程，很显然Floyd[i] [j] = min{Floyd[i] [j], Floyd[i] [1]+Floyd[1] [j]}，代码如下：

**2，**接下来继续求在只允许经过1和2号两个顶点的情况下任意两点之间的最短距离，在已经实现了从i号顶点到j号顶点只经过前1号点的最短路程的前提下，现在再插入第2号结点，来看看能不能更新更短路径，故只需在步骤1求得的Floyd[n+1] [n+1]基础上，进行Floyd[i] [j] = min{Floyd[i] [j], Floyd[i] [2]+Floyd[2] [j]}；…
**3，**很显然，需要n次这样的更新，表示依次插入了1号，2号…n号结点，最后求得的Floyd[n+1] [n+1]是从i号顶点到j号顶点只经过前n号点的最短路程。

特点

Floyd算法适用于APSP(AllPairsShortestPaths)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。

优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单

缺点：时间复杂度高，不适合计算大量数据

参考内容

通俗易懂理解——dijkstra算法求最短路径 - 知乎

最短路径模板+解析——（FLoyd算法） - CSDN

图论（二）：图的四种最短路径算法 - CSDN

6.4.3 拓扑排序

什么是拓扑排序

有向无环图 不存在环的图，简称DAG图

AOV网 若用一个DAG图表示一个工程，其顶点表示活动，用有向边<v1, vj>表示活动vi先于活动vj进行的传递关系，则将这种DAG称为顶点表示活动网络，简称AOV网

拓扑排序 对DAG所有顶点的一种排序，使若存在一条从顶点A到顶点B的路径，在排序中B排在A的后面

举例

如图，我想学习boot，那么前面都要学，我想学jsp，那么java要学，无关联的可任意序列排序，有关联的按照顺序走

思路

1. 从DAG图中选择一个没有前驱的顶点并输出
2. 从图中删除该顶点和以它为起点的边
3. 重复1，2，直到DAG图为空或当前图中不存在无前驱的顶点为止。后者则说明图中有环。

参考内容

拓扑排序详解与实现 - 博客园

6.4.4 关键路径

AOE网

在有向带权图中，以顶点表示事件，以有向边表示活动，以边上权值表示完成该活动的开销，则称这种有向图为用边表示活动的网络，简称AOE网

关键路径

从原点到汇点最大路径长度的路径称为关键路径，关键路径的活动为关键活动

事件的最早发生时间 ve[k]

根据AOE网的性质，只有进入Vk的所有活动<Vj, Vk>都结束，Vk代表的事件才能发生，而活动<Vj, Vk>的最早结束时间为ve[j]+len<Vj, Vk>。所以，计算Vk的最早发生时间的方法为：

ve[0] = 0

ve[k] = max(ve[j] + len<Vj, Vk>)

举例：v2的最早发生时间 = a1 = 3,v5 = a4 + v2 = 6,如果是多条边则取较大值

事件的最早发生时间 vl[k]

vl[k]是指在不推迟整个工期的前提下，事件Vk允许的最迟发生时间。根据AOE网的性质，只有顶点Vk代表的事件发生，从Vk出发的活动<Vk, Vj>才能开始，而活动<Vk, Vj>的最晚开始时间为vl[j] - len<Vk, Vj>。

逆推最早发生时间即可，注意取最小值

活动的最早发生时间：ee[i]

ai由有向边<Vk, Vj>，根据AOE网的性质，只有顶点Vk代表的事件发生，活动ai才能开始，即活动ai的最早开始时间等于事件Vk的最早开始时间。

弧尾 = 最早发生时间

活动的最迟发生时间：el[i]

el[i]是指在不推迟真个工期的前提下，活动ai必须开始的最晚时间。若活动ai由有向边<Vk, Vj>表示，则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后。

弧头 - 开销(边的权重) = 最迟发生时间

活动ai的差额d(i) = l(i) - e(i)

关键路径：{a2, a5, a7}

缩短关键路径活动时间可以加快整个工程，但缩短到一定程度关键路径会改变

当关键活动不唯一时，只有加快的关键活动或者关键活动组合包括在所有的关键路径上才能缩短工期

参考内容

图——关键路径 - CSDN

第七章

7.1.1 查找的基本概念

大概念

什么是查找

在数据集合中寻找满足某种条件的数据元素的过程

查找表

用于查找的数据集合，由同一种数据类型(或记录)的组成，可以是一个数组或链表等数据类型

操作：

• 查询某个特定的数据元素是否在查找表中
• 检索满足条件的某个特定的数据元素的各种属性
• 插入一个数据元素
• 删除一个数据元素

关键字

数据元素中唯一标识该元素的某个数据项的值，使用基于关键字查找，查找结果应该是唯一的

平均查找长度

ASL（Average Search Length），即平均查找长度，在查找运算中，由于所费时间在关键字的比较上，所以把平均需要和待查找值比较的关键字次数称为平均查找长度。

概念如下图

其中n为查找表中元素个数，Pi为查找第i个元素的概率，通常假设每个元素查找概率相同，Pi=1/n，Ci是找到第i个元素的比较次数。

一个算法的ASL越大说明时间性能越差，反之亦然。

参考内容

关于ASL(平均查找长度)的简单总结 - 博客园

7.2.1 顺序查找

什么是顺序查找

主要用于在线性表中进行查找

当无须线性表进行线性查找失败时，需要遍历整个线性表

7.2.2 折半查找

什么是折半查找

也叫二分查找，仅适用于有序的顺序表

思想

首先将给定key与表中间的元素相比较，相等则返回该元素，若不等则如下：

• key小于中间元素，查找前半部分
• key大于中间元素，查找后半部分

重复以上过程，直到找到结果或查找失败

顺序查找和二分查找的区别

顺序查找适用于顺序存储和链式存储，有序无序皆可

二分查找只适用于顺序存储，且要求序列一定有序

7.2.3 分块查找

什么是分块查找

又称索引顺序查找，它吸取了顺序查找和折半查找各自的优点，既有动态结构，又适用于快速查找

如何分块

将查找表分为若干子块。块内的元素无序，但块间是有序的。

建立索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列。

7.3.1 B树

什么是B树

又称多路平衡查找树，B树中所有结点的孩子结点数的最大值称为B数的阶

概念

一颗m阶的B树定义如下：

• 每个结点最多有m-1个关键字。
• 根结点最少可以只有1个关键字。
• 非根结点至少有Math.ceil(m/2)-1个关键字。
• 每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
• 所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。

查找

1. 在B树中找结点（磁盘）
2. 在结点中找关键字（内存）

插入

1. 定位

   查找插入该关键字的位置，既最底层中的某个非叶子结点

2. 插入

   若插入后不会破坏B树的定义，则直接插入即可

   若会破坏B树的定义，则进行分裂操作：

   分裂：

   1. 插入后的结点中间位置关键字并入父结点
   2. 左侧结点留在原地，右侧结点放入新结点
   3. 如果父节点关键字数量超出范围，则继续向上分裂，直到符合要求为止、

常规插入

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ikqudFA2-1618913822559)(C:%5CUsers%5CMOCHEN%5CAppData%5CRoaming%5CTypora%5Ctypora-user-images%5Cimage-20210326224746455.png)]

分裂插入

插入前

插入后

删除

1. 直接删除

   若删除该结点不破坏B树定义，则直接删除

2. 兄弟借

   若删除后破坏B树定义，则向兄弟借：

   1. 将父结点左（右）侧结点拉过来
   2. 将左（右）兄弟拉到父结点

3. 兄弟不借

   若左右兄弟都只有一个关键字，那就合并父结点

   1. 父结点合为兄弟结点
   2. 若条件不满足，重复兄弟借与不借的操作

4. 终端结点（最后一层非叶子结点）

   如果删除的是非终端结点，则进行以下操作：

   1. 替换

      找到它对应的关键字的终端结点，替换删除即可

   2. 合并

      如果它下面只有两个结点，直接合并结点然后删除即可

兄弟借

借之前

借之后

兄弟不借

合并前

合并后

终端结点 - 替换

如下图，33 和 32 替换，然后删除33

终端结点 - 合并

如下图，合并21和24并指向30，删除23

B树的特点

优点：

Ｂ树出现是因为磁盘ＩＯ。ＩＯ操作的效率很低，那么，当在大量数据存储中，查询时我们不能一下子将所有数据加载到内存中，只能逐一加载磁盘页，每个磁盘页对应树的节点。造成大量磁盘ＩＯ操作（最坏情况下为树的高度）。平衡二叉树由于树深度过大而造成磁盘IO读写过于频繁，进而导致效率低下。

常规的二叉树磁盘IO效率很低，比如我找个数需要访问h次，为了减少IO的操作就需要最大程度降低树的高度，将一个瘦长的树变成矮胖的树，因此有了B树

缺点：

难

B树的应用

B树常应用于文件系统和部分数据库索引，以及MongoDB

参考内容

B树详解 - 简书

B树与B+树 - CSDN

漫画 B树 B-树 - CSDN

7.3.2 B+树

概念

1. 根结点至少有两个孩子。

2. 每个中间节点都至少包含ceil(m / 2)个孩子，最多有m个孩子。

3. 每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m。

4. 所有的叶子结点都位于同一层。

5. 每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

图示

B树与B+树的区别

1. B+树中，具有n个关键字的结点值含有n棵子树，既每个关键字对应一颗子树

   B树中，具有n个关键字的结点值含有n棵子树

2. B+树中，非叶结点只保存索引，所有信息存放在叶节点中

   B树中，每个结点保存一个信息

3. B+树中，叶结点包含全部关键字，非叶结点中出现的关键字也会出现在叶结点中

   B树中，叶结点包含的关键字和其他结点不重复

7.4.1 散列表的基本概念

散列函数

一个把从查找表中的关键字映射成该关键字对应的地址的函数

散列表

根据关键字而直接进行访问的数据结构。它建立了关键字与存储地址之间的一种直接映射关系

冲突

散列函数可能会把多个不同的关键字映射到同一地址下的情况

7.4.2~7.4.4 散列函数的构造方法和冲突处理

要求

1. 散列函数的定义域必须包含全部需要存储的关键字，而值域则依赖于散列表的大小和地址范围
2. 散列函数计算出来的地址应该能等概率，均匀的分布在整个地址空间中，最大程度减少冲突的发生
3. 散列函数应尽量简单，能在较短时间内计算出任一关键字对应的散列地址

方法

直接定址法

直接取关键字的某个线性函数值为散列地址

Hash(key) = a * key + b

其中a,b为常数

方法简单，不会产生冲突，若关键字分布不连续则会浪费空间

除留取余法

假定散列表表长为m，取一个不大于m但最接近或等于m的质数p

Hash(key) = key % p

选好p是关键，可以减少冲突

数字分析法

前八位相同，取后四位

适用于关键字已知的集合，若更换关键字则需要重新构造散列函数

平方取中法

取关键字的平方值的中间几位作为散列地址

适用于关键字的每位取值不均匀或小于散列地址所需要的位数

折叠法

将关键字分割成位数相同的几部分，然后将这几部分相加作为散列地址

适用于关键字的位数多，而且关键字中的每位上数字分布大致均与

开放定址法

是指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放

Hi = (H(key) + di) % m

i = 0,1,2,…,k(k <= m - 1);

m为散列表表长

di为增量序列

如何计算增量序列

线性探查法

既 di = 0,1,2,…,k

平方探测法

既 di = 0平方，1平方，-1平方，2平方，-2平方，…,k平方，-k平方，其中k <= m / 2

避免堆积问题，缺点是不能探测到散列表上的所有单元

再散列法

既 di = i * Hash2(key)

伪随机序列法

既 di = 伪随机序列

开放定址法不能随便删除某个元素

拉链法（重点）

把所有同义词存放在一个线性链表中，这个线性链表由地址唯一表示，既散列表中每个单元存放该链表头指针

数组每个成员包括一个指针，指向一个数组

拉链法适用于经常进行插入和删除的情况

查找效率

散列函数，处理冲突的方法和填装因子

填装因子

一般记为阿尔法，表示表的装满程度

散列表的平均查找长度依赖于散列表的填装因子

散列表的特点

和数组以及链表对比：

	查找	增删
数组	快	慢
链表	慢	快
散列表	快	快

优点

接近O(1)的时间复杂度，碾压一切渣渣

缺点

因为是基于数组的，所以填装因子越大性能越低，因此必须要清楚表中将要存储多少数据

概念

参考内容

哈希表（散列表）原理详解 - CSDN

第八章

8.1 排序的基本概念

大概念

排序

重新定义表中的元素，使表中的元素按照关键字递增或递减

排序算法的稳定性

排序后两个相同的元素不发生变动，则为稳定，反之则为不稳定

如下图，淡蓝色小朋友排序后仍在深蓝色小朋友之前，则这个算法就是稳定的

稳定性只是算法的性质，无法评定算法的优劣

内部排序与外部排序

内部排序

指在排序期间全部放在内存中排序

外部排序

指在排序期间无法全部放在内存中，在排序过程中根据要求不断的在内，外存中移动

此处仅探讨内部排序

时空复杂度决定内部排序算法的性能

8.2.1 直接插入排序

动图演示

实现思路

1. 从第二个参数开始往前比较，如果上个参数比当前参数大则交换位置
2. 继续对比，直到前面没有比自身更大的数
3. 重复第二步，直到全部数据排完

实现代码

import java.util.Arrays;

/**
 * @Description: 插入排序
 * @Author: MoChen
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arrs = {1, 2, 5, 2, 3, 6, 7, 4};
        InsertSort is = new InsertSort();
        System.out.println(Arrays.toString(is.insSort(arrs)));
    }

    /**
     * 每次将当前数字与前面所有位数比较，前面大则交换，否则看下一个数字
     */
    public int[] insSort(int[] arrs){
        for (int i = 1; i < arrs.length; i++) {
            int j = i;
            while (j > 0){
                if (arrs[j] < arrs[j - 1]){
                    int temp ;
                    temp = arrs[j];
                    arrs[j] = arrs[j - 1];
                    arrs[j-1] = temp;
                    j--;
                }else {
                    break;
                }
            }
        }
        return arrs;
    }
    
    /**
     * 1. 从第二个数字开始遍历，将当前数字放入数组第一位当作哨兵使用
     * 2. 从当前数字往前遍历，只要大于哨兵就往前移一位
     * 3. 将哨兵赋给下一位，完成交换操作
     * 4. 重复以上操作，直到数据完成排序
     */
    public int[] insSortSent(int[] arrs){
        int i = 0, j = 0;
        int[] newArrs = new int[arrs.length + 1];
        // 将当前数组扩容一位，保证第一位是哨兵
        System.arraycopy(arrs, 0, newArrs, 1, arrs.length);
        for(i = 2; i < newArrs.length; i++){
            newArrs[0] = newArrs[i];
            for(j = i - 1; newArrs[0] < newArrs[j]; j--){
                newArrs[j + 1] = newArrs[j];
            }
            newArrs[j + 1] = newArrs[0];
        }
        // 归还结果
        arrs = Arrays.copyOfRange(newArrs, 1, newArrs.length);
        return arrs;
    }
}

此处while可以改成for，for版本代码更简洁，用while更清晰故使用while

教材代码虽然简洁但是偏难，需多多理解

概念

时间复杂度为[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pSxbvolo-1618913822579)(https://www.zhihu.com/equation?tex=O%28n%5E%7B2%7D%29)]，可采用顺序存储和链式存储

参考内容

插入排序 - 沐雨橙风~~ - 博客园

8.2.2 折半插入排序

概念

二分查找 + 插入排序

减少了比较次数，但是元素的移动次数不变。平均时间复杂度为O(n^2)；空间复杂度为O(1)；是稳定的排序算法。

实现代码

/**
     * 折半插入排序
     */
    public int[] bInsSort(int[] arrs){
        int i = 0,j = 0;
        int low = 0, high = 0, mid = 0;
        int[] newArrs = new int[arrs.length + 1];
        // 将当前数组扩容一位，保证第一位是哨兵
        System.arraycopy(arrs, 0, newArrs, 1, arrs.length);
        for(i = 2; i < newArrs.length; i++){
            newArrs[0] = newArrs[i];
            low = 1;
            high = i - 1;
            while(low <= high){
                mid = (low + high) / 2;
                if(newArrs[mid] > newArrs[0]){
                    high = mid - 1;
                }else{
                    low = mid + 1;
                }
            }
            for(j = i - 1; j >= high + 1; j--){
                newArrs[j + 1] = newArrs[j];
            }
            newArrs[high + 1] = newArrs[0];
        }
        // 归还结果
        arrs = Arrays.copyOfRange(newArrs, 1, newArrs.length);
        return arrs;
    }

同上，此处也可使用非哨兵模式，同步教材代码故使用哨兵模式

时间复杂度下界

对于下标i < j, 如果A[i] > A[j], 则称(i, j)是一对逆序对

只要后面的数字比当前位数小，就是逆序对，交换元素的排序算法本质就是消除逆序对

任何仅以交换相邻两元素来排序的算法，其平均时间复杂度为**[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PaRXUe8e-1618913822579)(https://www.zhihu.com/equation?tex=O%28n%5E%7B2%7D%29)]**

参考内容

排序----折半插入排序 - CSDN

经典排序算法（4）——折半插入排序算法详解 - CSDN

8.2.3 希尔排序

什么是希尔排序

希尔排序是一种改进后的插入排序，也称缩小增量排序。

按照增量序列进行插入排序，最后一步增量序列为1

如下图，第一个按照五个间隔排序，第二次按照三个间隔排序，最后一次按照一个间隔排序，这里的5，3，1就是增量序列

实现代码

    /**
     * 希尔排序
     */
    public int[] shellSort(int[] arrs){
        for(int dk = arrs.length / 2; dk >= 1; dk /= 2){
            for(int i = dk + 1; i < arrs.length; i++){
                int j = i;
                int temp = arrs[j];
                for(j = i; j >= dk && arrs[i - dk] > temp; i -= dk){
                    arrs[i] = arrs[i - dk];
                }
                arrs[i] = temp;
            }
        }
        return arrs;
    }

思路很简单，就是插入排序外面套一层增量序列的循环

概念

希尔排序的最坏时间复杂度依然是[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3BH3e77n-1618913822581)(https://www.zhihu.com/equation?tex=O%28n%5E%7B2%7D%29)]，但是往往并达不到这种程度

采用优化的增量序列可以最大程度减少时间复杂度，比如Hibbard等等

参考内容

图解排序算法(二)之希尔排序 - 博客园

8.3.1 冒泡排序

什么是冒泡排序

类似于冒泡，大的数沉下去，小的数浮上来，所以叫冒泡排序

每次遍历将最大的数字移到末尾

动图演示

实现代码

    /**
     * 冒泡排序
     */
    public int[] bubbleSort(int[] arrs){
        for(int i = 0; i < arrs.length; i++){
            for(int j = 0; j < arrs.length - i - 1; j++){
                if(arrs[j] > arrs[j + 1]){
                    int temp = arrs[j];
                    arrs[j] = arrs[j + 1];
                    arrs[j + 1] = temp;
                }
            }
        }
        return arrs;
    }

概念

思路就是比较，交换，该算法过于经典不多描述

参考内容

排序-冒泡排序 - 简书

8.3.2 快速排序

什么是快速排序

快排的性能在所有排序算法里面是最好的，数据规模越大快速排序的性能越优。快排在极端情况下会退化成 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-l5TMZRWU-1618913822582)(https://www.zhihu.com/equation?tex=O%28n%5E%7B2%7D%29)] 的算法，因此假如在提前得知处理数据可能会出现极端情况的前提下，可以选择使用较为稳定的归并排序。

动图演示

实现思路

• 选择A中任意一个元素pivot,该元素作为基准
• 将小于基准的元素移到左边，大于基准的移到右边
• A被pivot分为两部分，继续对剩下的两部分做同样的处理
• 重复以上操作，直到数据排序完成

实现代码

    /**
     * 快速排序
     */
    public int[] quickSort(int[] arrs, int low, int high){
        int i = low, j = high;
        int temp = 0;
        if(i < j){
            temp = arrs[i];
            while(i != j){
                while(j > i && arrs[j] > temp){
                    --j;
                }
                arrs[i] = arrs[j];
                while(i < j && arrs[i] < temp){
                    ++i;
                }
                arrs[j] = arrs[i];
            }
            arrs[i] = temp;
            quickSort(arrs, low, i - 1);
            quickSort(arrs, i + 1, high);
        }
        return arrs;
    }

更标准的写法应该是两个方法，一个拿基准，一个递归排序，此处图简洁不做实现

参考内容

排序–快速排序 - 知乎

快速排序—(面试碰到过好几次) - CSDN

8.4.1 直接选择排序

什么是选择排序

每次从无序中选出最小元（最小关键字），将最小元放入有序的后面

和插入不同，插入是交换有序序列，选择是追加到有序后面

和冒泡大抵相同，不过冒泡是每次交换n-1次，选择是交换两次

实现代码

    /**
     * 选择排序
     */
    public int[] selectSort(int[] arrs){
        for(int i = 0; i < arrs.length; i++){
            int min = i;
            for(int j = i + 1; j < arrs.length; j++){
                if(arrs[j] < arrs[min]){
                    min = j;
                }
            }
            if(min != i){
                // 交换
                arrs[i] = arrs[i] + arrs[min];
                arrs[min] = arrs[i] - arrs[min];
                arrs[i] = arrs[i] - arrs[min];
            }
        }
        return arrs;
    }

一次排序将一个元素放置到最终的位置上

8.4.2 堆排序

什么是堆排序

堆排序是一种**选择排序，**它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。

堆

堆是具有以下性质的完全二叉树：

每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；

每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

如下图：

实现代码

import java.util.Arrays;

/**
 * @Description: 堆排序
 * @Author: MoChen
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] arrs = {1, 2, 5, 3, 6, 7, 4};
        heapSort(arrs);
        System.out.println(Arrays.toString(arrs));
    }

    /**
     * 堆排序
     */
    public static void heapSort(int[] arrs){
        // 1. 构建大顶堆
        for(int i = arrs.length / 2 - 1; i >= 0; i--){
            adjustHeap(arrs, i, arrs.length);
        }
        // 2. 调整堆结构 + 交换堆顶元素与末尾元素
        for(int j = arrs.length - 1; j > 0; j--){
            swap(arrs, 0, j);
            adjustHeap(arrs, 0, j);
        }
    }

    /**
     * 调整大顶堆
     */
    public static void adjustHeap(int[] arrs, int i, int length){
        int temp = arrs[i];
        for(int k = i * 2 + 1; k < length; k = k * 2 + 1){
            if(k + 1 < length && arrs[k] < arrs[k + 1]){
                k++;
            }
            if(arrs[k] > temp){
                arrs[i] = arrs[k];
                i = k;
            }else{
                break;
            }
        }
        arrs[i] = temp;
    }

    /**
     * 交换元素
     */
    public static void swap(int[] arrs, int a, int b){
        int temp = arrs[a];
        arrs[a] = arrs[b];
        arrs[b] = temp;
    }
}

概念

1. 将无序序列构建成一个大顶堆（小顶堆同理）

   1. 将每个子树的最大值调整为父节点
   2. 重复上一步，直到根节点为最大值，堆构建完成

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

3. 重新调整结构，使其满足堆定义，然后重复第二步，反复执行调整+交换步骤，直到整个序列有序

参考内容

图解排序算法(三)之堆排序 - 博客园

8.5.1 归并排序

什么是归并排序

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略

分治法将问题分(divide)成一些小的问题然后递归求解，而**治(conquer)**的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之

动图演示

代码实现

import java.util.Arrays;

/**
 * @Description: 归并排序
 * @Author: MoChen
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {1, 13, 24, 26, 2, 15, 27, 38};
        int[] temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        mergeSort(arr, 0, arr.length - 1, temp);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 归并排序
     */
    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid, temp);//左边归并排序，使得左子序列有序
            mergeSort(arr, mid + 1, right, temp);//右边归并排序，使得右子序列有序
            merge(arr, left, mid, right, temp);//将两个有序子数组合并操作
        }
    }

    /**
     * 合并有序子列
     */
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;//左序列指针
        int j = mid + 1;//右序列指针
        int t = 0;//临时数组指针
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[t++] = arr[i++];
            } else {
                temp[t++] = arr[j++];
            }
        }
        while (i <= mid) {//将左边剩余元素填充进temp中
            temp[t++] = arr[i++];
        }
        while (j <= right) {//将右序列剩余元素填充进temp中
            temp[t++] = arr[j++];
        }
        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while (left <= right) {
            arr[left++] = temp[t++];
        }
    }
}

思路

上面两个图示已经比较明显，此处不做思路总结

参考内容

图解排序算法(四)之归并排序 - 博客园

【算法】排序算法之归并排序 - 知乎

8.5.2 基数排序

什么是基数排序

不同于以往的排序，基数排序无需进行比较或者交换，他通过分配和收集进行排序

思路

依照位数进行排序，比如三位数先进行个分位分配，然后十分位，百分位

可以这么理解，先对最后一位进行排序，然后往前一位，直到第一位，第一位排序完成即可

此章非重点不多做解释，感兴趣可去参考内容了解

参考内容

排序算法系列：基数排序 - CSDN

基数排序 顺序实现与链式实现

8.6 内部排序算法的比较及应用

考虑因素

综合考虑：元素数量，元素大小，关键字结构及分布，稳定性，存储结构，辅助空间

1. 若n较小(n<=50)时，可采用直接插入排序或简单选择排序，若n较大时，则采用快排，堆排或归并排序
2. 若n很大，关键字位数较小且可分解，采用基数排序
3. 当文件的n个关键字随机分布，任何借助于比较的排序，至少需要O(nlog2n)的时间
4. 若初始基本有序，则采用直接插入或冒泡排序
5. 当记录元素较大，应避免大量的移动的排序算法，尽量次啊用链式存储

每种排序算法都有它存在的意义，实际应用中应根据实际情况选择使用那种排序

8.7.1~8.7.2 外部排序的算法

什么是外部排序

对内存中的数据进行排序叫内部排序，内存外的数据排序即为外部排序

外部排序通常采用归并排序

举例

内存中只能放三个数，现在有十二个数，如何实现排序？

利用归并排序的思想，先分成四分进行依次排序，然后进行合并

两两合并子串，得到两个长度为六的子串，然后进行最后一次合并：

时间复杂度

外部排序的时间 = 内部排序的时间 + 外存读写时间 + 内部排序归并的时间

8.7.3 失败树

什么是失败树

树形选择排序的一种变体，可视为一颗完全二叉树

每个叶结点存放各归段在归并过程中参加比较的记录，内部结点用来记忆左右子树中的失败者，胜利者则向上继续比较，直到根节点

8.7.4 置换-选择排序

思路

设初始待排序文件为FI，初始归并段位FO,内存为WA,可容纳w个记录

1. 从FI中输入w个记录到WA
2. 从WA中选出最小值，输出到FO
3. 从FI中重新读入一个值，重复第二步操作
4. 重复2~3,直到选不出最小值，此处得到第一个归并段
5. 重复2~4，直到WA为空，得到所有初始归并段

示例

如下图所示，先进入三个数，最小值05给出去同事下一个数44进来，然后挑选比05大的第一个数17进来，重复操作知道56，后面没有最小值，此时得到第一个归并段；然后重复上述操作即可

8.7.5 最佳归并树

在上一章的基础上，将归并树转化为哈夫曼树，即为最佳归并树

如上图，该归并树IO次数为2 * WPL = 484

该树IO次数位 2 * WPL = 446，所以称为最佳归并树

当叶子结点不够时，增加权值为0的结点用来构造哈夫曼树

总结

可使用多路归并，最优为置换选择

参考内容

【漫画】什么是外部排序？ - 搜狐

外部排序&多路归并排序 - 博客园

第九章 - 补充

9.1 红黑树

什么是红黑树

为了解决二叉查找树多次单侧插入新节点导致的不平衡，红黑树应运而生

红黑树基于二叉查找树实现，它具有以下特点：

1. 节点是红色或黑色
2. 根节点是黑色
3. 每个叶子节点都是黑色的空节点（NIL节点）
4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5. 任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

红黑树的优点

正是因为有了上述繁琐的规则限制，才保证了红黑树的自平衡。红黑树从根到叶子的最长路径不会超过最短路径的2倍。

红黑树的调整

当插入或删除节点的时候，有可能会打破规则，这个时候就需要根据情况做出调整，以此来维持规则

调整有两种方法，变色和旋转，而旋转又分为左旋转和右旋转

变色

变色就是字面意思变色

旋转

左旋转

逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子

Y变成爹，X变成儿子，代价是左腿给X

右旋转

顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子

举例

如上图所示，该情况打破了规则4，解决方案如下：

变色

1. 22变为黑色
2. 25变为红色
3. 27变为黑色

旋转

此时变色已经无法解决问题了，就需要用到旋转

4. 13和17进行左旋转
5. 13变为红色，17变为黑色

此时并没有结束，路径(17 -> 8 -> 6 -> NIL)的黑色节点个数是4，其他路径的黑色节点个数是3，不符合规则5，我们继续操作：

6. 13和8进行右旋转
7. 8，15变为红色，13变为黑色

结果

参考内容

面试常问：什么是红黑树？- CSDN

9.2 贪心算法

顾名思义，贪心算法总是做出当前看来最好的选择，也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。

思路

1. 把问题分解成若干个问题
2. 求出每个子问题的最优解
3. 将每个局部最优解合并，得到结果的最优解

贪心策略适用的前提是：局部最优策略能导致产生全局最优解。

我也不太会，看漫画吧，漫画比较详细

参考内容

漫画：五分钟学会贪心算法 - 知乎

五大常用算法之一：贪心算法 - 简书

总结

后言

数据结构更多是一种思想，非算法从业者或考研可不做重点学习

既然说了是思想，就要明白为什么学这个，期望掌握什么，多思考，多code，才是出路

墨尘 2021年2月1日