《王道数据结构》

第一章：绪论

1.1 数据结构的基本概念

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

2. 数据元素：数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。例如，学生记录就是一个数据元素，它由学号、姓名、性别等数据项组成。

3. 数据对象: 数据对象是具有相同性值的数据元素的集合，是数据的一个子集。

4. 数据类型: 数据类型是一个值的集合和定义再此集合上的一组操作的总称。

  • 原子类型。其值不可再分的数据类型。如 bool 和 int 类型。
  • 结构类型。其值可以再分解为若干成分（分量）的数据类型。
  • 抽象数据类型。抽象数据组织及与之相关的操作。（定义一个 ADT 就是定义了数据的逻辑结构，数据的运算，也就是定义了一个完整的数据结构）

5. 数据结构: 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

1.2 数据结构的三要素

逻辑结构

逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。与数据的存储无关，独立于计算机。
Pasted image 20230831095914
逻辑结构包括：
Pasted image 20230831100004|450

  1. 线性结构：结构中的数据元素之间只存在一对一的关系，除了第一个元素，所有元素都有唯一前驱；除了最后一个元素，所有元素都有唯一后继。
  2. 集合：结构中的数据元素之间除 “同属一个集合” 外，别无其它关系。
  3. 树形结构：结构中数据元素之间存在一对多的关系。
  4. 图状结构：数据元素之间是多对多的关系。

存储结构（物理结构）

存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构。它包括数据元素的表示和关系的表示。数据的存储结构是用计算机语言实现的逻辑结构，依赖于计算机语言。

存储结构包括：

  1. 顺序存储：把逻辑上相邻的元素存储在物理位置也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
    • 优点：实现随机存取，每个元素占用最少的存储空间
    • 缺点：只能使用相邻的一整块存储单元，可能产生较多外部碎片
  2. 链式存储：逻辑上相邻的元素在物理位置上可以不相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。
    • 优点：不会产生碎片，充分利用所有存储单元
    • 去欸但：每个元素因存储指针占用额外存储空间，且只能顺序读取
  3. 索引存储：在存储元素信息的同时，还建立附加的索引表，索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）
    • 优点：检索速度快
    • 缺点：索引表占用存储空间，增删数据要修改索引表，时间开销大。
  4. 散列存储（哈希存储）：根据元素的关键字直接计算出该元素的存储地址，又称哈希（Hash）存储。
    • 优点：检索，增删节点快速
    • 缺点：若哈希函数不好，可能出现存储单元的冲突，解决冲突会增加时间空间的开销

随机存取、顺序存取、随机存储、顺序存储

这四个概念是完全不一样的，切不可将之混淆

存取：

  1. 随机存取就是直接存取，可以通过下标直接访问的那种数据结构，与存储位置无关，例如数组。
  2. 非随机存取就是顺序存取了，不能通过下标访问了，只能按照存储顺序存取，与存储位置有关，例如链表。
  3. 顺序存取就是存取第 N 个数据时，必须先访问前（N-1）个数据 （list），随机存取就是存取第 N 个数据时，不需要访问前（N-1）个数据，直接就可以对第 N 个数据操作 （array）。

存储结构：

  1. 顺序存储结构：在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，称作线性表的顺序存储结构。
    • 顺序存储结构是存储结构类型中的一种，该结构是把逻辑上相邻的节点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的储结构为顺序存储结构。通常用高级程序设计语言中的数组来表述线性表的顺序存储结构。（注意，线性表中的元素位序从 1 开始，数组元素的下标从 0 开始）
  2. 随机存储结构：在计算机中用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。
    • 它不要求逻辑上相邻的元素在物理位置上也相邻。因此它没有顺序存储结构所具有的弱点，但也同时失去了顺序表可随机存取的优点。随机存储最典型的代表为链式存储：

3. 数据的运算

施加在数据上的运算包括运算的定义何实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。

1.3 算法的基本概念

程序 = 数据结构 + 算法

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

  1. 有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。
  2. 确定性：算法中每条指令必须有确定的含义，对于相同的输入只能得到相同的输出。
  3. 可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
  4. 输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
  5. 输出：一个算法有一个多个输出，这些输出是与输入有着某种特定关系的量。

第二章：线性表

Pasted image 20230831100324

线性表是逻辑结构，顺序表和链表为存储结构

2.1 线性表的定义

线性表是具有相同数据类型的 n(n>0) 个数据元素的有限序列。

  • 第一个元素称为表头元素，最后一个元素称为表尾元素
  • 除第一个元素外，每个元素有且仅有一个直接前驱。
  • 除最后一个元素外，每个元素有且仅有一个直接后继。
  • 每个数据元素的存储位置都和线性表的起始位置相差一个该数据元素的位序成正比的常数，因此线性表中任一数据元素都可以随机存取

2.2 顺序存储

2.2 顺序表的定义

顺序表的特点：

  • 用一组地址连续的存储单元存储数据元素，使得逻辑上相邻的元素在物理位置上也相邻
  • 表中元素的逻辑顺序与其物理顺序相同
  • 可以随机访问，即通过首地址和元素序号就可以在 $O(1)$ 时间内找到指定的元素
  • 插入和删除需要移动大量元素

Pasted image 20230831100739

2.3 链式存储

  • 链式存储线性表时，不要求逻辑上相邻的元素在物理位置上也相邻。
  • 插入和删除不需要移动操作，只需要修改指针
  • 不能随机存取（查找某个特定节点，需要从头遍历）

单链表

Pasted image 20230905094314

定义： 线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。
对于每个链表节点，除了存放自身自信外，还要存放一个指向后继的指针。

1
2
3
4
typedef struct LNode{//定义单链表结点类型
    ElemType data; //数据域
    struct LNode *next;//指针域
}LNode, *LinkList;

头指针指向第一个节点，为 NULL 时表示空表

单链表的两种实现方式：

  1. 不带头结点的单链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

//初始化一个空的单链表
bool InitList(LinkList &L){  //注意用引用 &
    L = NULL; //空表，暂时还没有任何结点；
    return true;
}

void test(){
    LinkList L;  //声明一个指向单链表的指针: 头指针
    //初始化一个空表
    InitList(L);
    //...
}

//判断单链表是否为空
bool Empty(LinkList L){
    if (L == NULL)
        return true;
    else
        return false;
}

头结点：代表链表上头指针指向的第一个结点，不带有任何数据。

  1. 带头结点的单链表
    Pasted image 20230905094517
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    typedef struct LNode{
        ElemType data;
        struct LNode *next;
    }LNode, *LinkList;

    //初始化一个单链表（带头结点）
    bool InitList(LinkList &L){  
        L = (LNode*) malloc(sizeof(LNode));  //头指针指向的结点——分配一个头结点（不存储数据）
        if (L == NULL)          //内存不足，分配失败
            return false;
        L -> next = NULL;       //头结点之后暂时还没有结点
        return true;
    }

    void test(){
        LinkList L;  //声明一个指向单链表的指针: 头指针
        //初始化一个空表
        InitList(L);
        //...
    }

    //判断单链表是否为空（带头结点）
    bool Empty(LinkList L){
        if (L->next == NULL)
            return true;
        else
            return false;
    }

带头结点和不带头结点的比较：
不带头结点：写代码麻烦！对第一个数据节点和后续数据节点的处理需要用不同的代码逻辑，对空表和非空表的处理也需要用不同的代码逻辑; 头指针指向的结点用于存放实际数据;
带头结点：头指针指向的头结点不存放实际数据, 头结点指向的下一个结点才存放实际数据;

双链表

Pasted image 20230905095018

双链表节点有两个指针，指向其前驱和后继

1
2
3
4
typedef struct DNode{            //定义双链表结点类型
    ElemType data;               //数据域
    struct DNode *prior, *next;  //前驱和后继指针
}DNode, *DLinklist;

循环链表

循环单链表

Pasted image 20230905095241
最后一个结点的指针不是 NULL, 而是指向头结点
判空条件不是头结点的指针是否为空，而是他是否等于头指针。

循环双链表

Pasted image 20230905095408
表头结点的 prior 指向表尾结点，表尾结点的 next 指向头结点

双向循环链表

和单链的循环表类似，双向链表也可以有循环表，让头结点的前驱指针指向链表的最后一个结点，让最后一个结点的后继指针指向头结点。

静态链表

Pasted image 20230905095525

用数组的方式来描述线性表的链式存储结构: 分配一整片连续的内存空间，各个结点集中安置，包括了——数据元素 and 下一个结点的数组下标 (游标)

  • 其中数组下标为 0 的结点充当 “头结点”
  • 游标为 - 1 表示已经到达表尾

顺序表和链表的比较

  1. 存取（读写）方式
    顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序存取元素。例如在第 i 个位置上执行存或取的操作，顺序表仅需一次访问，而链表则需从表头开始依次访问 i 次。
  2. 逻辑结构与物理结构
    采用顺序存储时，逻辑上相邻的元素，对应的物理存储位置也相邻。而采用链式存储时，逻辑上相邻的元素，物理存储位置不一定相邻，对应的逻辑关系是通过指针链接来表示的。
  3. 查找、插入和删除操作
    对于按值查找，顺序表无序时，两者的时间复杂度均为 O (n); 顺序表有序时，可采用折半查找，此时的时间复杂度为 O (logn)。
    对于按序号查找，顺序表支持随机访问，时间复杂度仅为 O (1)，而链表的平均时间复杂度为 O (n)。顺序表的插入、删除操作，平均需要移动半个表长的元素。链表的插入、删除操作，只需修改相关结点的指针域即可。由于链表的每个结点都带有指针域，故而存储密度不够大。
  4. 空间分配
    顺序存储在静态存储分配情形下，一旦存储空间装满就不能扩充，若再加入新元素，则会出现内存溢出，因此需要预先分配足够大的存储空间。预先分配过大，可能会导致顺序表后部大量闲置; 预先分配过小，又会造成溢出。动态存储分配虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且若内存中没有更大块的连续存储空间，则会导致分配失败。
    链式存储的结点空间只在需要时申请分配，只要内存有空间就可以分配，操作灵活、高效。

顺序、链式、静态、动态四种存储方式的比较

  1. 顺序存储的固有特点：
    逻辑顺序与物理顺序一直，本质上是用数组存储线性表的各个元素（即随机存取）；存储密度大，存储空间利用率高。
  2. 链式存储的固有特点：
    元素之间的关系采用这些元素所在的节点的 “指针” 信息表示（插、删不需要移动节点）。
  3. 静态存储的固有特点：
    在程序运行的过程中不要考虑追加内存的分配问题。
  4. 动态存储的固有特点：
    可动态分配内存；有效的利用内存资源，使程序具有可扩展性。

第三章：栈和队列

3.1 栈（stack）

Pasted image 20230905100318
顺序栈：采用顺序存储的栈，存储单元地址连续，附设一个 top 指针指向当前栈顶元素的位置。
共享栈：利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。Pasted image 20230905100327

**栈的链式存储 (链栈)**：便于多个栈共享存储空间和提高效率，不存在栈满的清空。通常采用单链表实现，并规定所有操作都在表头进行。
Pasted image 20230905100447

3.2 队列（Queue）

Pasted image 20230905100601
队头（Front）：出队
队尾（Rear）：入队

队列的顺序存储结构

分配一块连续的存储单元存放队列中的元素，并附设两个指针：

  • 队头指针front：指向队头元素
  • 队尾指针 rear：指向队尾元素的下一个位置
    （不同地方定义可能不同）
    队空条件：front==rear==0

入队：先送值到队尾元素，再将队尾指针+1
出队：先取队头元素，再将队头指针+1
Pasted image 20230905100913

循环队列

定义：将循环队列臆造为一个环状的空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。
基本操作：

当队首指针 front=MaxSize-1 时，再前进一个位置就自动到 0，这可以利用除法取余%运算来实现。

1
2
3
4
5
6
a%b == a除以b的余数

初始时：Q.front = Q.rear = 0;
队首指针进1：Q.front = (Q.front + 1) % MaxSize
队尾指针进1：Q.rear = (Q.rear + 1) % MaxSize —— 队尾指针后移，当移到最后一个后，下次移动会到第一个位置
队列长度：(Q.rear + MaxSize - Q.front) % MaxSize

区分队空还是队满的情况：
方案一: 牺牲一个单元来区分队空和队满
约定队头指针在队尾指针的下一个位置作为队满的标志，即 

1
2
3
队满条件:(Q.rear+1) % MaxSize==Q.front
队空条件仍: Q.front==Q.rear
队列中元素的个数:(Q.rear-Q.front+MaxSize)% MaxSize

Pasted image 20230905101546

方案二: 不牺牲存储空间，设置 size
定义一个变量 size用于记录队列此时记录了几个数据元素，初始化 size = 0，进队成功 size++，出队成功size--，根据 size 的值判断队满与队空

队满条件：size == MaxSize
队空条件：size == 0

方案三: 不牺牲存储空间，设置 tag
定义一个变量 tag，tag = 0 – 最近进行的是删除操作；tag = 1 – 最近进行的是插入操作；

每次删除操作成功时，都令tag = 0；只有删除操作，才可能导致队空；
每次插入操作成功时，都令tag = 1；只有插入操作，才可能导致队满；
队满条件：Q.front == Q.rear && tag == 1
队空条件：Q.front == Q.rear && tag == 0

队列的链式存储结构

队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表。
Pasted image 20230905101640
Pasted image 20230905101716

双端队列

Pasted image 20230905101727

  1. 定义：双端队列是指允许两端都可以进行入队和出队操作的队列
  • 双端队列允许从两端插入、两端删除的线性表；
  • 如果只使用其中一端的插入、删除操作，则等同于栈；
  • 输入受限的双端队列：允许一端插入，两端删除的线性表；
  • 输出受限的双端队列：允许两端插入，一端删除的线性表；

3.3 栈的应用

3.3.1 栈在括号匹配中的应用

用栈实现括号匹配

  • ([()]) 最后出现的左括号最先被匹配 (栈的特性—先进后出);

  • 遇到左括号就入栈;

  • 遇到右括号，就 “消耗” 一个左括号 (出栈);

  • 还有一些技巧，在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多了！

  • 匹配失败情况：

    • 扫描到右括号且栈空，说明栈中没有与该右括号匹配的的左括号。
    • 扫描完所有括号后，栈非空，说明栈中的左括号没有与之匹配的右括号。
    • 左右括号不匹配;
  • 成功的情况：遍历完字符串，栈是空的，就说明全都匹配了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    bool isValid(string s) 
    {
        stack<char> ST;
        for(int i = 0; i<s.size(); i++)
        {
            //遇到左括号就入栈;
            if(s[i] == '(' || s[i] == '{' || s[i] == '[')
            {
                ST.push(s[i]);
            }
            else
            {
                //扫描到右括号且栈空，说明栈中没有与该右括号匹配的的左括号。
                if(ST.empty()) 
                    return false;

                //左右括号不匹配
                char TopElem = ST.top();
                if(s[i] == ')' && TopElem != '(' )
                    return false;
                if(s[i] == '}' && TopElem != '{' )
                    return false;
                if(s[i] == ']' && TopElem != '[' )
                    return false;

                //到右括号，就 “消耗” 一个左括号 (出栈); 
                ST.pop();
            }
        }

        //扫描完字符串
        //栈空，则匹配成功
        //栈非空，说明栈中的左括号没有与之匹配的右括号,则匹配失败
        return ST.empty();
    }
};

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

1. 中缀表达式 (需要界限符)
运算符在两个操作数中间:

1
2
3
4
5
① a + b
② a + b - c
③ a + b - c*d
④ ((15 ÷ (7-(1+1)))×3)-(2+(1+1))
⑤ A + B × (C - D) - E ÷ F

2. 后缀表达式 (逆波兰表达式)
运算符在两个操作数后面:

1
2
3
4
5
6
① a b +
② ab+ c - / a bc- +
③ ab+ cd* -
④ 15 7 1 1 + - ÷ 3 × 2 1 1 + + -
⑤ A B C D - × + E F ÷ - (机算结果)
  A B C D - × E F ÷ - + (不选择)

中缀表达式转后缀表达式 - 手算
步骤 1： 确定中缀表达式中各个运算符的运算顺序

步骤 2： 选择下一个运算符，按照 [左操作数 右操作数 运算符] 的方式组合成一个新的操作数

步骤 3： 如果还有运算符没被处理，继续步骤 2

“左优先” 原则: 只要左边的运算符能先计算，就优先算左边的 (保证运算顺序唯一)；

1
2
3
中缀：A + B - C * D / E + F
       ①   ④   ②   ③   ⑤     
后缀：A B + C D * E / - F +

重点：中缀表达式转后缀表达式 - 机算
初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。从左到右处理各个元素，直到末尾。可能遇到三种情况:

遇到操作数: 直接加入后缀表达式。
遇到界限符: 遇到 ‘(’ 直接入栈; 遇到 ‘)’ 则依次弹出栈内运算符并加入后缀表达式，直到弹出 ‘(’ 为止。注意: '(' 不加入后缀表达式。
遇到运算符: 依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到 ‘(’ 或栈空则停止。之后再把当前运算符入栈。
按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

后缀表达式的计算—手算:
从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应的运算，合体为一个操作数；

1
注意： 两个操作数的左右顺序

重点：后缀表达式的计算—机算
用栈实现后缀表达式的计算（栈用来存放当前暂时不能确定运算次序的操作数）

步骤 1: 从左往后扫描下一个元素，直到处理完所有元素;

步骤 2: 若扫描到操作数，则压入栈，并回到步骤 1; 否则执行步骤 3;

步骤 3: 若扫描到运算符，则弹出两个栈顶元素，执行相应的运算，运算结果压回栈顶，回到步骤 1;

注意: 先出栈的是 “右操作数”

3. 前缀表达式 (波兰表达式)
运算符在两个操作数前面:

1
2
3
① + a b
② - +ab  c
③ - +ab *cd

中缀表达式转前缀表达式—手算
步骤 1： 确定中缀表达式中各个运算符的运算顺序

步骤 2： 选择下一个运算符，按照 [运算符 左操作数 右操作数] 的方式组合成一个新的操作数

步骤 3： 如果还有运算符没被处理，就继续执行步骤 2

“右优先” 原则: 只要右边的运算符能先计算，就优先算右边的;

1
2
3
中缀：A + B * (C - D) - E / F
       ⑤   ③    ②    ④   ①
前缀：+ A - * B - C D / E F

前缀表达式的计算—机算
用栈实现前缀表达式的计算

步骤 1: 从右往左扫描下一个元素，直到处理完所有元素；

步骤 2: 若扫描到操作数则压入栈，并回到步骤 1，否则执行步骤 3

步骤 3: 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到步骤 1；

注意: 先出栈的是 “左操作数”

4. 中缀表达式的计算 (用栈实现)
两个算法的结合： 中缀转后缀 + 后缀表达式的求值

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

若扫描到操作数，压人操作数栈

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

3.3.3 栈在递归中的应用

函数调用的特点：最后被调用的函数最先执行结束 (LIFO)

函数调用时，需要用一个栈存储：

  • 调用返回地址
  • 实参
  • 局部变量

递归调用时，函数调用栈称为 “递归工作栈”:

  • 每进入一层递归，就将递归调用所需信息压入栈顶；
  • 每退出一层递归，就从栈顶弹出相应信息；

** 缺点：** 太多层递归可能回导致栈溢出；

适合用 “递归” 算法解决：可以把原始问题转换为属性相同，但规模较小的问题；

第四章：字符串

字符串简称串

4.1 串的定义和实现

4.1.1 串的定义

串: 零个或多个字符组成的有限序列，如 S = 'iPhone 11 Pro Max?'；

串是特殊的线性表，数据元素之间呈线性关系（逻辑结构相似）； 串的数据对象限定为字符集：中文字符、英文字符、数字字符、标点字符…
串的基本操作，如增删改除通常以子串为操作对象

4.1.3 串的存储结构

定长顺序存储：类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串。
堆分配存储表示：仍以一组空间足够大的、地址连续的存储单元依次存放字符序列，但它们的存储空间实在程序执行过程种动态分配的 (new 或malloc)
串的链式存储（块链）：每一个链表的结点存储多个字符——每个结点称为块——块链结构
Pasted image 20230905102630

4.2 串的模式匹配

模式匹配：子串的定位操作称为串的模式匹配，它求的是子串（常称模式串）在主串中的位置。

4.2.1 朴素模式匹配算法——暴力匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int Index(SString S, SString T){
    int i=1;                //扫描主串S
    int j=1;                //扫描模式串T
    while(i<=S.length && j<=T.length){
        if(S.ch[i] == T.ch[j]){
            ++i;
            ++j;             //继续比较后继字符
        }
        else{
            i = i-j+2;
            j=1;             //指针后退重新开始匹配
        }
    }
    if(j>T.length)
        return i-T.length;
    else
        return 0;
}

在上述算法中，分别用计数指针 i 和 j 指示主串 s 和模式串 T 中当前正待比较的字符位置。算法思想为: 从主串 s 的第一个字符起，与模式 T 的第一个字符比较，若相等，则继续逐个比较后续字符; 否则从主串的下一个字符起，重新和模式的字符比较;
以此类推，直至模式 T 中的每个字符依次和主串 s 中的一个连续的字符序列相等，则称匹配成功，函数值为与模式 T 中第一个字符相等的字符在主串 s 中的序号，否则称匹配不成功，函数值为零。
Pasted image 20231217140440
时间复杂度分析：

  • 主串长度为 n，模式串长度为 m
    最多比较n-m+1个子串
    最坏时间复杂度 = O(nm)
    每个子串都要对比 m 个字符 (对比到最后一个字符才匹配不上)，共要对比 n-m+1 个子串，复杂度 = O((n-m+1)m) = O(nm - m^2 + m) = O(nm)
    PS: 大多数时候，n>>m
    最好时间复杂度 = O(n)
    每个子串的第一个字符就匹配失败，共要对比 n-m+1 个子串，复杂度 = O(n-m+1) = O(n)

4.2.2 【需要重新整理】改进的模式匹配算法——KMP 算法

  • 前缀：指除最后一个字符以外，字符串的所有头部子串;
  • 后缀：指除第一个字符外，字符串的所有尾部子串;
  • 部分匹配值：为空符出的前缀和后缀的最长相等前后缀长度。
计算部分匹配值的方法

以’ ababa’为例进行说明:
Pasted image 20231217141715

部分匹配值的作用

Pasted image 20231218100948
Pasted image 20231218101000

KMP 算法原理

移动位数 = 已匹配的字符数 - 对应的部分匹配值

在暴力匹配中，每趟匹配失败都是模式后移一位再从头开始比较。而某趟已匹配相等的字符序列是模式的某个前缀，这种频繁的重复比较相当于模式串在不断地进行自我比较，这就是其低效率的根源。
因此，可以从分析模式本身的结构着手，如果已匹配相等的前缀序列中有某个后缀正好是模式的前缀，那么就可以将模式向后滑动到与这些相等字符对齐的位置，主串 i 指针无须回溯，并从该位置开始继续比较。

算法改进-引入 Next 数组

移动位数 = 已匹配的字符数 - 对应的部分匹配值
改成
Move = (j-1) - PM[j-1]

使用部分匹配值时，每当匹配失败，就去找它前一个元素的部分匹配值，这样使用起来有些不方便，所以将 PM 表右移一位，这样哪个元素匹配失败，直接看它自己的部分匹配值即可。

Pasted image 20231218112718

我们注意到:

  1. 第一个元素右移以后空缺的用-1 来填充，因为若是第一个元素匹配失败，则需要将子串向右移动一位，而不需要计算子串移动的位数。
  2. 最后一个元素在右移的过程中溢出，因为原来的子串中，最后一个元素的部分匹配值是其下一个元素使用的，但显然已没有下一个元素，故可以舍去。

这样，上式就改写为
Move = (j-1) - PM[j]
相当于将子串的比较指针 j 回退到
j=j - Move = j -((j-1)-next[j]) = next[j] + 1
有时为了使公式更加简洁、计算简单，将 next 数组整体+1。因此，上述子串的 next 数组也可以写成
Pasted image 20231218113121
最终得到子串指针变化公式 j=next[j]

⭐ next[j] 的含义是： 在子串的第 j 个字符与主串发生失配时，则跳到子串的 next[j] 位置重新与主串当前位置进行比较。

  • 不匹配的字符之前，一定是和模式串一致的；
  • 根据模式串 T，求出 next 数组（只与模式串有关，与主串无关），利用 next 数组进行匹配，当匹配失败时，主串的指针 i 不再回溯！
  • next 数组是根据子串求出来的，当前面的字符串已知时如果有重复的，从当前的字符匹配即可。
  1. 求 next 数组
  • 作用：当模式串的第 j 个字符失配时，从模式串的第 next[j] 继续往后匹配;
  • 对于任何模式串，当第 1 个字符不匹配时，只能匹配下一个子串，因此，next[1] = 0——表示模式串应右移一位，主串当前指针后移一位，再和模式串的第一字符进行比较；
  • 对于任何模式串，当第 2 个字符不匹配时，应尝试匹配模式串的第一个字符，因此，next[2] = 0;
    例：对于串 T = 'abaabc'
  1. 利用next数组进行模式匹配
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int Index_KMP(SString S, SString T, int next[])
{
    int i=1;     //主串
    int j=1;     //模式串
    while（i<S.length && j<=T.length)
    {
        if(j==0 || S.ch[i]==T.ch[j])
        {      //第一个元素匹配失败时
            ++j;
            ++i;         //继续比较后继字符
        }
        else
            j=next[j]   //模式串向右移动
    }
    if(j>T.length)
        return i-T.length; //匹配成功
    else
        return 0;
}
  1. 时间复杂度分析
  • 求 next 数组时间复杂度 = O(m)
  • 模式匹配过程最坏时间复杂度 = O(n)
  • KMP 算法的最坏时间复杂度 = O(m+n)

next 数组的求法：
我们能确定 next 数组第一二位一定分别为 0，1，后面求解每一位的 next 值时，根据前一位进行比较。
从第三位开始，将前一位与其 next 值对应的内容进行比较，
如果相等，则该位的 next 值就是前一位的 next 值加上 1；
如果不等，向前继续寻找 next 值对应的内容来与前一位进行比较，
直到找到某个位上内容的 next 值对应的内容与前一位相等为止，
则这个位对应的值加上 1 即为需求的 next 值；
如果找到第一位都没有找到与前一位相等的内容，那么求解的位上的 next 值为 1。

注意下标都是从 1 开始的
传送门：https://blog.csdn.net/m0_37482190/article/details/86667059

第五章：树

Pasted image 20230905103027

5.1 树的基本概念

5.1.1 树的定义

树是 n 个结点的有限集。

  • 空树：n=0
  • 根节点没有前驱，其他节点有且只有一个前驱
  • 所有节点可以有 0 个或多个后继

树的定义是递归的，即树的定义中又用到了其自身。数是一种递归的数据结构
树作为一种逻辑结构，同时也是一种分层结构。

5.1.2 基本术语

Pasted image 20230905103227

祖先：AB 是 K 的祖先，K 是他们的子孙
双亲：E 是 K 的双亲
兄弟：KL拥有相同双亲 E
堂兄弟：双亲在同一层

结点的度：孩子数量
树的度：树中结点的最大度数
分支节点：度大于 0
叶子节点：度等于 0
结点的层次：从树根开始定义，根节点为第一层，从上到下依次类推。
结点深度：从根结点开始自顶向下
结点高度：从叶子节点开始自底向上
树的高度（深度）：树中结点最大层数

有序树：树中结点各子树从左到右是由次序的，不能互换，称为有序树，否则为无序数。
路径：两节点之间的路径由所经过的结点序列构成
路径长度：经过的边数

森林：m 棵互不相交的树的集合。

5.1.3 树的性质

  1. 树中的结点数等于所有结点的度数之和加 1。
  2. 度为 $m$ 的树第 $i$ 层上至多有 $m^i-1$ 个结点
  3. 度为 $m$ 的数、$m$ 叉数的区别

5.2 二叉树的概念

5.2.1 二叉树的定义与特性

二叉树是另一种树形结构，其特点是每个结点至多只有两棵子树（即二叉树中不存在度大于 2 的结点)，并且二叉树的子树有左右之分，其次序不能任意颠倒（二叉树是有序树，若将其左、右子树颠倒，则成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。）。
Pasted image 20230905104508

与树相似，二叉树也以递归的形式定义。二叉树是 n (n≥0）个结点的有限集合:

  1. 或者为空二叉树，即 n=0。
  2. 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

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

  1. 度为 2 的树至少有 3 个结点，而二叉树可以为空。
  2. 度为 2 的有序树的孩子的左右次序是相对于另一孩子而言的，若某个结点只有一个孩子，则这个孩子就无须区分其左右次序，而二叉树无论其孩子数是否为 2，均需确定其左右次序，即二叉树的结点次序不是相对于另一结点而言，而是确定的。

5.2.2 几种特殊的二叉树

Pasted image 20230905104719

  1. 满二叉树：一颗深度为 $h$ 且有 $2^h-1$ 个结点的二叉树称为满二叉树。每一层上的结点数都达到最大。叶子全部在最低层。
  2. 完全二叉树：深度为 $h$ 的具有 $n$ 个结点的二叉树，当且仅当其每一个结点都与深度为 $h$ 的满二叉树中编号为 $1-n$ 的结点一一对应时，称之为完全二叉树。
  3. 二叉排序树。左子树上所有结点的关键字均小于根结点的关键字; 右子树上的所有结点的关键字均大干根结点的关键字: 左子树和右子树又各是一棵二叉排序树。
  4. 平衡二叉树: 树上任一结点的左子树和右子树的深度之差不超过 1。

5.2.3 二叉树的存储结构

顺序存储

Pasted image 20230905105008
二叉树的顺序存储是指用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为 $i$ 的结点元素存储在一维数组下标为 $i-1$ 的分量中
依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映结点之间的逻辑关系，这样既能最大可能地节省存储空间，又能利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。

用数组来存储二叉树如何遍历的呢？
如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。
但是用链式表示的二叉树，更有利于我们理解，所以一般我们都是用链式存储二叉树。所以大家要了解，用数组依然可以表示二叉树。

链式存储

Pasted image 20231220144047|500
由于顺序存储的空间利用率较低，因此二叉树一般都采用链式存储结构，用链表结点来存储二叉树中的每个结点。
在二叉树中，结点结构通常包括若干数据域和若干指针域，二叉链表至少包含 3 个域: 数据域 data、左指针域 lchild 和右指针域 rchild.

实际上在不同的应用中，还可以增加某些指针域，如增加指向父结点的指针后，变为三叉链表的存储结构。

链式存储的二叉树节点的定义方式如下：

1
2
3
4
5
6
7
8
9
10
struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  };

5.3 二叉树的遍历和线索二叉树

二叉树的遍历是指按某条搜索路径访问树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。由于二叉树是一种非线性结构，每个结点都可能有两棵子树，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，进而便于遍历。
由二叉树的递归定义可知，遍历一棵二叉树便要决定对根结点 N、左子树 L 和右子树 R 的访问顺序。按照先遍历左子树再遍历右子树的原则，常见的遍历次序有先序 (NLR)、中序（LNR)和后序 (LRN） 三种遍历算法，序指的是根结点在何时被访问。

5.3.1 二叉树的遍历

二叉树的层次遍历

Pasted image 20230905105548

要进行层次遍历，需要借助一个队列。先将二叉树根结点入队，然后出队，访问出队结点，若它有左子树，则将左子树根结点入队; 若它有右子树，则将右子树根结点入队。然后出队，访问出队结点……如此反复，直至队列为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//二叉树的结点(链式存储)
typedef struct BiTnode{
   ElemType data;          
   struct BiTNode *lchild, *rchild; 
}BiTNode, *BiTree;

//链式队列结点
typedef struct LinkNode{
   BiTNode * data;
   typedef LinkNode *next;
}LinkNode;

typedef struct{
   LinkNode *front, *rear;  
}LinkQueue;

//层序遍历
void LevelOrder(BiTree T){
   LinkQueue Q;
   InitQueue (Q);          //初始化辅助队列
   BiTree p;
   EnQueue(Q,T);           //将根节点入队
   while(!isEmpty(Q)){     //队列不空则循环
      DeQueue(Q,p);        //队头结点出队
      visit(p);            //访问出队结点
      if(p->lchild != NULL)
         EnQueue(Q,p->lchild);   //左孩子入队
      if(p->rchild != NULL)
         EnQueue(Q,p->rchild);   //右孩子入队
   }
}
由遍历序列构造二叉树

由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树。

  • 先序序列 + 中序序列
  • 后序序列 + 中序序列
  • 层序序列 + 中序序列
    key: 找到树的根节点，并根据中序序列划分左右子树，再找到左右子树根节点、

先序+后序无法唯一确定一颗二叉树，但可以确定二叉树中结点的关系。

为什么不能确定？因为没有中序遍历无法确定左右部分
Pasted image 20230905105748

5.3.2 线索二叉树

  1. 线索二叉树的概念与作用
    在二叉树的结点上加上线索的二叉树称为线索二叉树，对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，使其变为线索二叉树的过程称为对二叉树进行线索化。
  2. 线索二叉树的存储结构
  • 中序线索二叉树——线索指向中序前驱、中序后继
1
2
3
4
5
6
//线索二叉树结点
typedef struct ThreadNode{
   ElemType data;
   struct ThreadNode *lchild, *rchild;
   int ltag, rtag;                // 左、右线索标志
}ThreadNode, *ThreadTree;

tag == 0: 指针指向孩子

tag == 1: 指针是 “线索”

  • 先序线索二叉树——线索指向先序前驱、先序后继

  • 后序线索二叉树——线索指向后序前驱、后序后继

  1. 二叉树的线索话
  • 中序线索化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
typedef struct ThreadNode{
   int data;
   struct ThreadNode *lchild, *rchild;
   int ltag, rtag;                // 左、右线索标志
}ThreadNode, *ThreadTree;

//全局变量pre, 指向当前访问的结点的前驱
TreadNode *pre=NULL;

void InThread(ThreadTree T){
    if(T!=NULL){
        InThread(T->lchild);    //中序遍历左子树
        visit(T);               //访问根节点
        InThread(T->rchild);    //中序遍历右子树
    }
}

void visit(ThreadNode *q){
   if(q->lchid = NULL){                 //左子树为空，建立前驱线索 
      q->lchild = pre;
      q->ltag = 1;
   }

   if(pre!=NULL && pre->rchild = NULL){ 
      pre->rchild = q;           //建立前驱结点的后继线索
      pre->rtag = 1;
   }
   pre = q;
}

//中序线索化二叉树T
void CreateInThread(ThreadTree T){
   pre = NULL;                //pre初始为NULL
   if(T!=NULL);{              //非空二叉树才能进行线索化
      InThread(T);            //中序线索化二叉树
      if(pre->rchild == NULL)
         pre->rtag=1;         //处理遍历的最后一个结点
   }
}
  • 先序线索化
    注意【转圈】问题，当 ltag==0 时，才能对左子树先序线索化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
typedef struct ThreadNode{
   int data;
   struct ThreadNode *lchild, *rchild;
   int ltag, rtag;                // 左、右线索标志
}ThreadNode, *ThreadTree;

//全局变量pre, 指向当前访问的结点的前驱
TreadNode *pre=NULL;

//先序遍历二叉树，一边遍历一边线索化
void PreThread(ThreadTree T){
   if(T!=NULL){
      visit(T);
      if(T->ltag == 0)         //lchild不是前驱线索
         PreThread(T->lchild);
      PreThread(T->rchild);
   }
}

void visit(ThreadNode *q){
   if(q->lchid = NULL){                 //左子树为空，建立前驱线索 
      q->lchild = pre;
      q->ltag = 1;
   }

   if(pre!=NULL && pre->rchild = NULL){ 
      pre->rchild = q;           //建立前驱结点的后继线索
      pre->rtag = 1;
   }
   pre = q;
}

//先序线索化二叉树T
void CreateInThread(ThreadTree T){
   pre = NULL;                //pre初始为NULL
   if(T!=NULL);{              //非空二叉树才能进行线索化
      PreThread(T);            //先序线索化二叉树
      if(pre->rchild == NULL)
         pre->rtag=1;         //处理遍历的最后一个结点
   }
}
  • 后序线索化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
typedef struct ThreadNode{
   int data;
   struct ThreadNode *lchild, *rchild;
   int ltag, rtag;                // 左、右线索标志
}ThreadNode, *ThreadTree;

//全局变量pre, 指向当前访问的结点的前驱
TreadNode *pre=NULL;

//先序遍历二叉树，一边遍历一边线索化
void PostThread(ThreadTree T){
   if(T!=NULL){
      PostThread(T->lchild);
      PostThread(T->rchild);
      visit(T);                  //访问根节点
   }
}

void visit(ThreadNode *q){
   if(q->lchid = NULL){                 //左子树为空，建立前驱线索 
      q->lchild = pre;
      q->ltag = 1;
   }

   if(pre!=NULL && pre->rchild = NULL){ 
      pre->rchild = q;           //建立前驱结点的后继线索
      pre->rtag = 1;
   }
   pre = q;
}

//先序线索化二叉树T
void CreateInThread(ThreadTree T){
   pre = NULL;                //pre初始为NULL
   if(T!=NULL);{              //非空二叉树才能进行线索化
      PostThread(T);            //后序线索化二叉树
      if(pre->rchild == NULL)
         pre->rtag=1;         //处理遍历的最后一个结点
   }
}
  1. 线索二叉树中找前驱、后继
  • 中序线索二叉树找中序后继：在中序线索二叉树中找到指定节点 *p 的中序后继 next
1
2
3
若 p->rtag == 1, 则 next = p->rchild;

若 p->rtag == 0, 则 p 必有右孩子, 则 next = p的右子树中最左下结点;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//1. 找到以P为根的子树中，第一个被中序遍历的结点
ThreadNode *Firstnode(ThreadNode *p){
   //循环找到最左下的结点（不一定是叶结点）
   while(p->ltag == 0)
      p=p->lchild;
   return p;
}

//2. 在中序线索二叉树中找到结点p的后继结点
ThreadNode *Nextnode(ThreadNode *p){
   //右子树最左下结点
   if(p->rtag==0)
      return Firstnode(p->rchild);
   else 
      return p->rchild; //rtag==1，直接返回后继线索
}

//3. 对中序线索二叉树进行中序遍历
void Inorder(ThreadNode *T){            //T为根节点指针
   for(ThreadNode *p = Firstnode(T); p!=NULL; p = Nextnode(p))
      visit(p);
}
  • 先序线索二叉树找先序后继：在先序线索二叉树中找到指定节点 *p 的先序后继 next

若 p->rtag == 1, 则 next = p->rchild; 若 p->rtag == 0, 则 p 必有右孩子（左孩子不知道）

case1: 若 p 有左孩子 ——— 根 左 右 / 根 (根 左 右) 右

case2: 若 p 没有左孩子 ——— 根 右 / 根 (* 根 * 左 右)

  • 先序线索二叉树找先序前驱：在先序线索二叉树中找到指定节点 *p 的先序前驱 pre

若 p->ltag == 1, 则 next = p->lchild;

若 p->ltag == 0, 则 p
必有左孩子，但是先序遍历中，左右子树的结点只可能是根的后继，不可能是前驱，所以不能从左右孩子里寻找 p 的先序前驱，（除非从头开始遍历 / 三叉链表

case1: 如果能够找到 p 的父节点，且 p 是左孩子 —— p 的父节点就是 p 的前驱；

case2: 如果能够找到 p 的父节点，且 p 是右孩子，且其左兄弟为空 —— p 的父节点就是 p 的前驱；

case3: 如果能够找到 p 的父节点，且 p 是右孩子，且其左兄弟非空 ——
p 的前驱为左兄弟子树中最后一个被先序遍历到的结点（根节点出发，先往右，右没有往左，找到最下一层的结点）；

case4: p 没有父节点，即 p 为根节点，则 p 没有先序前驱

  • 后序线索二叉树找后序前驱：在后序线索二叉树中找到指定节点 *p 的后序前驱 pre

若 p->ltag == 1, 则 next = p->lchild;

若 p->ltag == 0, 则 p 必有左孩子（不知道有没有右孩子）

case1: 若 p 有右孩子 ——— 左 右 根 / 左 (左 右 根) 根

case2: 若 p 没有右孩子 ——— 左 根 （左子树按后序遍历，最后一个结点，p 的左孩子）

  • 后序线索二叉树找后序后继：在后序线索二叉树中找到指定节点 *p 的后序后继 next

若 p->rtag == 1, 则 next = p->rchild;

若 p->rtag == 0, 则 p 必有右孩子, 左孩子不知道, 但是在后序遍历中，左右子树中的结点只有可能是根的前驱，而不可能是根的后继，所以找不到后继，（除非从头开始遍历 / 三叉链表

case1: 如果能找到 p 的父节点，且 p 是右孩子 —— p 的父节点即为其后继

case2: 如果能找到 p 的父节点，且 p 是左孩子，其右兄弟为空 —— p 的父节点即为其后继

case3: 如果能找到 p 的父节点，且 p 是左孩子，其右兄弟非空 —— p 的后继为其右兄弟子树中第一个被后序遍历的结点；

case4: p 没有父节点，即 p 为根节点，则 p 没有后序后继；

5.4 树、森林

5.4.1 树的存储结构

  1. **双亲表示法 (顺序存储)**：采用一组连续空间存储每个节点，每个结点中保存指向双亲的指针（在数组中的位置）
  • 数据域：存放结点本身信息。
  • 双亲域：指示本结点的双亲结点在数组中的位置。

优点：利用了每个结点 (根结点除外)只有唯一双亲的性质，可以很快得到双亲结点
缺点：求结点的孩子时需要遍历整个结构
Pasted image 20230905110036

1
2
3
4
5
6
7
8
9
10
11
#define MAX_TREE_SIZE 100  //树中最多结点数

typedef struct{      //树的结点定义
   ElemType data; 
   int parent;      //双亲位置域
}PTNode;

typedef struct{                   //树的类型定义
   PTNode nodes[MAX_TREE_SIZE];   //双亲表示
   int n;                         //结点数
}PTree;
  1. 孩子表示法 (顺序 + 链式)
    孩子表示法是将每个结点的孩子结点都用单链表链接起来形成一个线性结构，此时 n 个结点就有 n 个孩子链表（叶子结点的孩子链表为空表)
    Pasted image 20230905110348
    这种存储方式寻找子女的操作非常直接，而寻找双亲的操作需要遍历 n 个结点中孩子链表指针域所指向的 n 个孩子链表。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct CTNode{
   int child;    //孩子结点在数组中的位置
   struct CTNode *next;    // 下一个孩子
};

typedef struct{
   ElemType data;
   struct CTNode *firstChild;    // 第一个孩子
}CTBox;

typedef struct{
   CTBox nodes[MAX_TREE_SIZE];
   int n, r;   // 结点数和根的位置
}CTree;
  1. 孩子兄弟表示法 （二叉树表示法）（链式）
    以二叉链表作为树的存储结构。孩子兄弟表示法使每个结点包括三部分内容: 结点值、指向结点第一个孩子结点的指针，及指向结点下一个兄弟结点的指针（沿此域可以找到结点的所有兄弟结点)
    优点：这种存储表示法比较灵活，可以方便地实现树转换为二叉树的操作，易于查找结点的孩子。
    缺点是从当前结点查找其双亲结点比较麻烦。若为每个结点增设一个 parent 域指向其父结点，则查找结点的父结点也很方便。

Pasted image 20230905110408

1
2
3
4
typedef struct CSNode{
   ElemType data;                               //数据域
   struct CSNode *firstchild, *nextsibling;     //第一个孩子和右兄弟指针, *firstchild 看作左指针，*nextsibling看作右指针
}CSNode. *CSTree;

5.4.3 树、森林的遍历

Pasted image 20230905110832

树的遍历是指用某种方式访问树中的每个结点，且仅访问一次。主要有两种方式:

  1. 先根遍历：若树非空，先访问根结点，再依次对每棵子树进行先根遍历；（与对应二叉树的先序遍历序列相同）

    1
    2
    3
    4
    5
    6
    7
    void PreOrder(TreeNode *R){
       if(R!=NULL){
          visit(R);    //访问根节点
          while(R还有下一个子树T)
             PreOrder(T);      //先跟遍历下一个子树
       }
    }

  2. 后根遍历：若树非空，先依次对每棵子树进行后根遍历，最后再返回根节点；（与对应二叉树的中序遍历序列相同）

1
2
3
4
5
6
7
void PostOrder(TreeNode *R){
   if(R!=NULL){
      while(R还有下一个子树T)
         PostOrder(T);      //后跟遍历下一个子树
      visit(R);    //访问根节点
   }
}
  • 层序遍历（队列实现）：
    若树非空，则根结点入队；
    若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队；
    重复以上操作直至队尾为空；
  1. 森林的遍历
  • 先序遍历：等同于依次对各个树进行先根遍历；也可以先转换成与之对应的二叉树，对二叉树进行先序遍历；
  • 中序遍历：等同于依次对各个树进行后根遍历；也可以先转换成与之对应的二叉树，对二叉树进行中序遍历；

5.5.1 二叉排序树（BST）

定义

Binary Search Tree
二叉排序树（也称二叉查找树、二叉搜索树）或者是一棵空树，或者是具有下列特性的二叉树:

  1. 若左子树非空，则左子树上所有结点的值均小于根结点的值。
  2. 若右子树非空，则右子树上所有结点的值均大于根结点的值。
  3. 左、右子树也分别是一棵二叉排序树。

根据二叉排序树的定义，左子树结点值<根结点值<右子树结点值，所以对二叉排序树进行中序遍历，可以得到一个递增的有序序列。例如，图 5.21 所示二叉排序树的中序遍历序列为 123468。
Pasted image 20230908092527

查找 (搜索)

[!NOTE]

  • 当有序表是静态查找表时，适合用顺序表作为存储结构，使用二分查找。
  • 当有序表时是动态查找表时，则应选择二叉排序树作为其逻辑结构

二叉排序树的查找是从根结点开始，沿某个分支逐层向下比较的过先将给定值与根结点的关键字比较，若相等，则查找成功; 若不等，如则在根结点的左子树上查找，否则在根结点的右子树上查找。是一个递归的过程。

例如，在图 5.21 中查找值为 4 的结点。首先 4 与根结点 6 比较。由于 4 小于 6，所以在根结点 6 的左子树中继续查找。由于 4 大于 2，所以在结点 2 的右子树中查找，查找成功。

同样，二叉排序树的查找也可用递归算法实现，递归算法比较简单，但执行效率较低。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
typedef struct BSTNode{
   int key;
   struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;

//在二叉排序树中查找值为key的结点（非递归）
//最坏空间复杂度：O(1)
BSTNode *BST_Search(BSTree T, int key){
   while(T!=NULL && key!=T->key){        //若树空或等于跟结点值，则结束循环
      if(key<T->key)       //值小于根结点值，在左子树上查找
         T = T->lchild;
      else                  //值大于根结点值，在右子树上查找
         T = T->rchild;
   }
   return T;
}

//在二叉排序树中查找值为key的结点（递归）
//最坏空间复杂度：O(h)
BSTNode *BSTSearch(BSTree T, int key){
   if(T == NULL)
      return NULL;
   if(Kry == T->key)
      return T;
   else if(key < T->key)
      return BSTSearch(T->lchild, key);
   else 
      return BSTSearch(T->rchild, key);
}

插入

二叉排序树作为一种动态树表，其特点是树的结构通常不是一次生成的，而是在查找过程中当树中不存在关键字值等于给定值的结点时再进行插入的。
插入结点的过程如下: 若原二叉排序树为空，则直接插入结点; 否则，若关键字 k 小于根结点值，则插入到左子树，若关键字 k 大于根结点值，则插入到右子树。
插入的结点一定是一个新添加的叶结点，且是查找失败时的查找路径上访问的最后一个结点的左孩子或右孩子。如图 5.22 所示在一个二叉排序树中依次插入结点 28 和结点 58，虚线表示的边是其查找的路径。
Pasted image 20230908092959

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        //原树为空，新插入的结点为根结点
        if(root == nullptr)
        {
            root = new TreeNode(val);
            return root;
        }
        //树中存在相同关键字的结点，插入失败
        else if(val == root->val)
        {
            //不进行操作
        }
        else if(val < root->val)
        {
            root->left = insertIntoBST(root->left, val);
        }
        else if(val > root->val)
        {
            root->right = insertIntoBST(root->right, val);
        }

        return root;
    }
};

构造

从一棵空树出发，依次输入元素，将它们插入二叉排序树中的合适位置。设查找的关键字序列为{45,24,53,45,12,24}，则生成的二叉排序树如图 5.23 所示。
Pasted image 20230908093025

1
2
3
4
5
6
7
8
9
//按照str[]中的关键字序列建立二叉排序树
void Crear_BST(BSTree &T, int str[], int n){
   T = NULL;                     //初始时T为空树
   int i=0;
   while(i<n){
      BST_Insert(T,str[i]);     //依次将每个关键字插入到二叉排序树中
      i++;
   }
}

删除

在二叉排序树中删除一个结点时，不能把以该结点为根的子树上的结点都删除，必须先把被删除结点从存储二叉排序树的链表上摘下，将因删除结点而断开的二叉链表重新链接起来，同时确保二叉排序树的性质不会丢失。删除操作的实现过程按 3 种情况来处理:

  1. 若被删除结点 z 是叶结点，则直接删除，不会破坏二叉排序树的性质。
  2. 若结点 z 只有一棵左子树或右子树，则让 z 的子树成为 z 父结点的子树，替代 z 的位置
  3. 若结点 z 有左、右两棵子树，则令 z 的直接后继（或直接前驱）替代 z，然后从二叉排序树中删去这个直接后继（或直接前驱)，这样就转换成了第一或第二种情况。
    Pasted image 20230908093150

查找效率分析

二叉排序树的查找效率，主要取决于树的高度。

  • 若二叉排序树的左、右子树的高度之差的绝对值不超过 1，则这样的二叉排序树称为平衡二叉树，它的平均查找长度为 O (logzn)。
  • 若二叉排序树是一个只有右（左）孩子的单支树（类似于有序的单链表)，则其平均查找长度为 O (n)。
    在最坏情况下，即构造二叉排序树的输入序列是有序的，则会形成一个倾斜的单支树，此时二叉排序树的性能显著变坏，树的高度也增加为元素个数 n，如图 5.25 (b)所示。
    Pasted image 20230908093915
    ASL 计算方法：
    图 5.25(a) 查找成功的平均查找长度：
    $$
    \mathrm{ASL_{a}=(1+2{\times}2+3{\times}4+4{\times}3)/10=2.9}
    $$
    而图 5.25 (b)查找成功的平均查找长度为
    $$
    \mathrm{ASL}_{b}=(1+2+3+4+5+6+7+8+9+10)/10=5.5
    $$
    从查找过程看，二叉排序树与二分查找相似。就平均时间性能而言，二叉排序树上的查找和二分查找差不多。但二分查找的判定树唯一，而二叉排序树的查找不唯一，相同的关键字其插入顺序不同可能生成不同的二叉排序树，如图 5.25 所示。

5.5.2 平衡二叉树（AVL）

[!NOTE] Title

  • 平衡二叉树（AVL） 和红黑树是自平衡二叉搜索树（Self-balancing BST ）的子集
  • 而自平衡二叉搜索树是二叉搜索树（BST）的子集
  • 综上可以说 AVL 是一种 BST 树

定义

为避免树的高度增长过快，降低二叉排序树的性能，规定在插入和删除二叉树结点时，要保证任意结点的左、右子树高度差的绝对值不超过 1，将这样的二叉树称为平衡二叉树 (Balanced Binary Tree)，简称平衡树。
定义结点左子树与右子树的高度差为该结点的平衡因子, 则平衡二叉树结点的平衡因子的值只可能是-1、0 或 1。
因此，平衡二叉树可定义为或者是一棵空树，或者是具有下列性质的二叉树: 它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度差的绝对值不超过 1。
图 5.26 (a)所示是平衡二叉树，图 5.26 (b)所示是不平衡的二叉树。结点中的值为该结点的平衡因子。
Pasted image 20230908094234

1
2
3
4
5
6
//平衡二叉树结点
typedef struct AVLNode{
   int key;         //数据域
   int balance;     //平衡因子
   struct AVLNode *lchild; *rchild; 
}AVLNode, *AVLTree;

插入

二叉排序树保证平衡的基本思想如下: 每当在二叉排序树中插入（或删除）一个结点时，首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。若导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子的绝对值大于 1 的结点 A，再对以 A 为根的子树，在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新达到平衡。

[!NOTE]
注意: 每次调整的对象都是最小不平衡子树，即以插入路径上离插入结点最近的平衡因子的绝对值大于 1 的结点作为根的子树。图 5.27 中的虚线框内为最小不平衡子树。（只要将最小不平衡子树调整平衡，则其他祖先节点都会恢复平衡）

Pasted image 20230908095018

调整最小不平衡子树：

  1. LL 平衡旋转: 在 A 结点的左孩子的左子树中插入导致不平衡
    调整： A 的左孩子结点右上旋
    Pasted image 20230908095353
  2. RR 平衡旋转: 在 A 结点的右孩子的右子树中插入导致不平衡
    调整： A 的右孩子结点左上旋
    Pasted image 20230908095400
  3. LR 平衡旋转: 在 A 结点的左孩子的右子树中插入导致不平衡
    调整： A 的左孩子的右孩子，**先左上旋再右上旋 **
    Pasted image 20230908095410
  4. RL 平衡旋转: 在 A 结点的右孩子的左子树中插入导致不平衡
    调整： A 的右孩子的左孩子，先右上旋再左上旋
    Pasted image 20230908095415

查找与效率分析

在平衡二叉树上进行查找的过程与二叉排序树的相同。
含有 $n$ 个结点的平衡二叉树的最大深度为 $O (log2_n)$，因此平衡二叉树的平均查找长度为 $O (log_2n)$，如图 5.33所示。

5.5.3 哈夫曼树（最优二叉树）

定义

在许多应用中，树中结点常常被赋予一个表示某种意义的数值，称为该结点的权。

  1. 结点的带权路径长度：从根节点到该结点之间的路径长度（经过的边数）与该节点的权的乘积。
  2. 树的带权路径长度：树中所有叶结点的带权路径长度之和称为该树的带权路径长度。记为$$
    \mathrm{WPL}=\sum_{i=1}^{n}w_{i}l_{i}
    $$ 式中，$w_i$ 是第 $i$ 个叶结点所带的权值，$l_i$是该叶结点到根结点的路径长度。
  3. 哈夫曼树的定义：多个二叉树中带权路径WPL最小的树。
  4. 多叉哈夫曼树：如果叶结点的数量不能刚好凑成一颗严格多叉哈夫曼树（只包含度为 0 或 3 的结点），需要补充权值为 0 的虚叶节点。
  5. 哈夫曼树的构造（重点）：构造森林全是根, 选用两小造新树，删除两小添新人，重复 2、3 剩单根。Pasted image 20230908100404

哈杜曼编码（重点）：

由哈夫曼树得到的二进制前缀编码称为哈夫曼编码。

在数据通信中, 若对每个字符用相等长度的二进制位表示，称这种编码方式为固定长度编码。若允许对不同字符用不等长的二进制位表示，则这种编码方式称为可变长度编码。
可变长度编码比固定长度编码要好得多，其特点是对频率高的字符赋以短编码，而对频率较低的字符则赋以较长一些的编码，从而可以使字符的平均编码长度减短，起到压缩数据的效果。哈夫曼编码是一种被广泛应用而且非常有效的数据压缩编码。
若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。举例: 设计字符 A，B 和 C 对应的编码 0,101 和 100 是前缀编码。对前缀编码的解码很简单，因为没有一个编码是其他编码的前缀。所以识别出第一个编码，将它翻译为原码，再对余下的编码文件重复同样的解码操作。例如，码串 00101100 可被唯一地翻译为 0,0,101 和 100。另举反例: 如果再将字符 D 的编码设计为 00，此时 0 是 00 的前缀，那么这样的码串的前两位就无法唯一翻译。
由哈夫曼树得到哈夫曼编码是很自然的过程。

  1. 首先, 将每个出现的字符当作一个独立的结点，其权值为它出现的频度（或次数)，构造出对应的哈夫曼树。显然，所有字符结点都出现在叶结点中
  2. 我们可将字符的编码解释为从根至该字符的路径上边标记的序列, 其中边标记为 0 表示“转向左孩子”，标记为 1 表示“转向右孩子”。图 5.36 所示为一个由哈夫曼树构造哈夫曼编码的示例，矩形方块表示字符及其出现的次数。
    Pasted image 20230908100845

[!NOTE]
注意: 0 和 1 究竟是表示左子树还是右子树没有明确规定。左、右孩子结点的顺序是任意的，所以构造出的哈夫曼树并不唯一，但各哈夫曼树的带权路径长度 WPL 相同且为最优。此外如有若干权值相同的结点，则构造出的哈夫曼树更可能不同，但 WPL 必然相同且是最优的。

红黑树

【数据结构】史上最好理解的红黑树讲解，让你彻底搞懂红黑树-CSDN博客
红黑树（图解+秒懂+史上最全） - 疯狂创客圈 - 博客园 (cnblogs.com)

红黑树也是一种平衡二叉查找树，它与AVL树类似，都在添加和删除的时候通过旋转操作保持二叉树的平衡，以求更高效的查询性能。

与AVL树相比，红黑树牺牲了部分平衡性，以换取插入/删除操作时较少的旋转操作，整体来说性能要优于AVL树。

虽然红黑树是复杂的, 但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的：它可以在O(log n) 时间内做查找,插入和删除,这里的**n 是树中元素的数目

Pasted image 20240312132314

在红黑树中，节点被标记为红色和黑色两种颜色。

红黑树的特性：

  1. 节点非黑即红
  2. 根节点一定是黑色
  3. 叶子节点（NIL）一定是黑色
  4. 每个红色节点的两个子节点都为黑色。
  5. 从任一节点到其每个叶子的所有路径，都包含相同数目的黑色节点。

注意，根据原则 5，红黑树的平衡条件，不是以整体的高度来约束的，而是以黑色节点的高度，来约束的。

第六章 图

6.1 图的基本概念

定义：图 G 由顶点集 $V$ 和边集 $E$ 组成，记为 $G=(V, E)$，其中 $V (G)$ 表示图 G 中顶点的有限非空集; $E (G)$ 表示图 G 中顶点之间的关系 (边)集合。若 $V={v_1, v_2,…, n}$，则用 $|V|$ 表示图 $G$ 中顶点的个数，$E= {(u, v)| u∈V, v∈V}$，用$|E|$ 表示图 $G$ 中边的条数。

图不能为空，顶点集 V 一定非空，边集 E 可以为空，此时图中只有顶点。

有向图/无向图：边有没有箭头指向 <v1,v2>/(v1, v2)

简单图/多重图：

  • 图 G ①不存在重复边;②不存在顶点到自身的边，那么称图 G 为简单图。
  • 若图 G 中某两个顶点之间的边数大于 1 条，又允许顶点通过一条边和自身关联，则称图 G 为多重图。
  • 多重图和简单图的定义是相对的。数据结构中仅讨论简单图。

完全图（简单完全图）：无向图中任意两个顶点之间都有边或者有向图中任意两个顶点之间都存在方向相反的两条弧。
Pasted image 20230908102812

连通：在无向图中，若从顶点 v 到顶点 w 有路径存在，则称 v 和 w 是连通的。若图 G 中任意两个顶点都是连通的，则称图 G 为连通图，否则称为非连通图。无向图中的极大连通子图称为连通分量
Pasted image 20230908103017

强连通：在有向图中，如果有一对顶点 v 和 w，从 v 到 w 和从 w 到 v 之间都有路径，则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的，则称此图为强连通图。有向图中的极大强连通子图称为有向图的强连通分量
Pasted image 20230908103121
生成树/生成森林：连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为 n，则它的生成树含有 n-1 条边。包含图中全部顶点的极小连通子图，只有生成树满足这个极小条件，对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。在非连通图中，连通分量的生成树构成了非连通图的生成森林。
Pasted image 20230908103241
顶点的度/入度和出度：

  • 在无向图中，顶点 v 的度是指依附于顶点 v 的边的条数
  • 在有向图中，顶点 v 的度分为入度和出度, 入度是以顶点 v 为终点的有向边的数目。而出度是以顶点 v 为起点的有向边的数目。顶点 v 的度等于其入度与出度之和,

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

稠密图、稀疏图：边数很少的图称为稀疏图，反之称为稠密图。稀疏和稠密本身是模糊的概念，稀疏图和稠密图常常是相对而言的。一般当图 G 满足 $|E|<|V|log|V|$ 时，可以将 G 视为稀疏图。

路径、路径长度和回路
顶点之间的一条路径是指顶点序列，当然关联的边也可理解为路径的构成要素。路径上边的数目称为路径长度。第一个顶点和最后一个顶点相同的路径称为回路或环。若一个图有 n 个顶点，并且有大于 n-1 条边，则此图一定有环。

简单路径、简单回路
在路径序列中，顶点不重复出现的路径称为简单路径。除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。

距离
从顶点 u 出发到顶点 v 的最短路径若存在，则此路径的长度称为从 u 到 v 的距离。若从 u 到 v 根本不存在路径，则记该距离为无穷( oo )。

有向树
一个顶点的入度为 0、其余顶点的入度均为 1 的有向图，称为有向树。

6.2 图的存储结构

6.2.1 邻接矩阵表示法

[!NOTE]
时间复杂度大，适用于稠密图，能快速确定两个顶点之间是否存在边。

所谓邻接矩阵存储，是指用一个一维数组存储图中顶点的信息，用一个二维数组 (即邻接矩阵) 存储图中边的信息（即各顶点之间的邻接关系)。
结点数为 $n$ 的图 $G=(V, E)$ 的邻接矩阵 $A$ 是 $n\times n$ 的

1
2
3
4
5
6
7
8
9
10
#define MaxVertexNum 100//顶点数目的最大值
typedef char VertexType;//顶点的数据类型
typedef int EdgeType;   //带权图中边上权值的数据类型
typedef struct
{
    VertexType Vex [MaxVertexNum]; //顶点表
    EdgeType Edge [MaxVertexNum] [MaxVertexNum] ; //邻接矩阵，边表
    int vexnum, arcnum; //图的当前顶点数和弧数
}MGraph;

Pasted image 20230908104252

行对应出度，列对应入度

6.2.2 邻接表法

[!NOTE] Title
找入度入边不方便，适用于稀疏图，能快速找到所有临边。

当一个图为稀疏图时，使用邻接矩阵法显然要浪费大量的存储空间，而图的邻接表法结合了顺序存储和链式存储方法，大大减少了这种不必要的浪费。

所谓邻接表，是指对图 G 中的每个顶点 v 建立一个单链表，第 i 个单链表中的结点表示依附于顶点 v 的边（对于有向图则是以顶点 v 为尾的弧)，这个单链表就称为顶点 v 的边表 (对于有向图则称为出边表)。边表的头指针和顶点的数据信息采用顺序存储（称为顶点表)，所以在邻接表中存在两种结点: 顶点表结点和边表结点
Pasted image 20240212163019

  • 顶点表结点由顶点域 (data）和指向第一条邻接边的指针 (firstarc)构成，
  • 边表（邻接表）结点由邻接点域 (adjvex）和指向下一条邻接边的指针域 (nextarc）构成。
    无向图和有向Pasted image 20240212163155图的邻接表的实例分别如图所示。
    Pasted image 20240212163100
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    #define MaxVertexNum 100 //图中顶点数目的最大值

    //边表结点
    typedef struct ArcNode 
    { 
        int adjvex; //该弧所指向的顶点的位置
        struct ArcNode* next; //指向下一条弧的指针
        //InfoType info; //网的边权值
    }ArcNode;

    //顶点表结点
    typedef struct VNode 
    {
        VertexType data;
        //顶点信息
        ArcNode *first;
        //指向第一条依附该顶点的孤的指针
    }VNode , AdjList [MaxVertexNum];

    typedef struct
    {
        AdjList vertices; //邻接表
        int vexnum, arcnum; //图的顶点数和弧数
    }ALGraph;   //ALGraph 是以邻接表存储的图类型

6.2.3 十字链表

十字链表是有向图的一种链式存储结构。在十字链表中，对应于有向图中的每条弧有一个结点，对应于每个顶点也有一个结点。这些结点的结构如下图所示。
Pasted image 20240212164622
弧结点中有 5 个域:尾域 (tailvex)和头域 (headvex）分别指示弧尾和弧头这两个顶点在图中的位置; 链域 hlink 指向弧头相同的下一条弧; 链域 tlink 指向弧尾相同的下一条 info 域指向该弧的相关信息。这样，弧头相同的弧就在同一个链表上，弧尾相同的弧也在同个链表上。

顶点结点中有 3 个域: data 域存放顶点相关的数据信息，如顶点名称; firstin 和 firstout 两个域分别指向以该顶点为弧头或弧尾的第一个弧结点。

在十字链表中，既容易找到 V 为尾的弧，又容易找到 V 为头的弧，因而容易求得顶点的出度和入度。图的十字链表表示是不唯一的，但一个十字链表表示确定一个图。

6.3 图的遍历

定义：从图的任意指定顶点出发，依照某种规则去访问图中所有顶点，且每个顶点仅被访问一次，这一过程叫图的遍历。

方式：

  • 深度优先遍历方法（Depth_First Search——DFS）
  • 广度优先遍历法（Breadth_Frist Search——BFS）

6.4 最小生成树

普里姆（Prim）算法。

6.5 最短路径

迪杰斯特拉：

6.6AOV 网络与拓扑排序

6.7 AOE 网络与关键路径

第七章 查找

Pasted image 20230901093425

相关概念

  • 查找：在数据集合中找到满足条件的元素
  • 查找表：用于查找的由同一类型的数据元素（或记录）构成的集合。对查找表进行的经常操作为：查找、检索、增加、删除。
  • 静态查找表：对查找表只进行前两种操作。不会增删元素。适合静态查找表的方法有顺序查找，折半查找，散列查找
  • 动态查找表：不仅限于前两种操作。适合动态查找表的方法有二叉树的查找、散列查找。
  • 关键字：数据元素唯一标识该元素的某个中某个数据项的值，使用基于关键字的查找，查找结果应该唯一。
  • 平均查找长度（ASL）：一次查找的长度是需要比较的关键字次数，而平均查找长度是所有查找过程中进行关键字的比较次数的平均值。是衡量查找算法效率的主要指标。
    $$
    \mathrm{ASL}=\sum_{i=1}^{n}P_{i}C_{i}
    $$
  • $n$ ：查找表的长度
  • $P_i$ ：查找第 i 个数据元素的概率，一般认为每个数据元素的查找概率相等，即 $P_i= 1/n$;
  • $C_i$ ：找到第 $i$ 个数据元素所需进行的比较次数。

ad7552f66d61359ce065140396e1b51d_MD5

1 顺序查找

核心：从数据的第一个元素开始，依次比较，直到找到目标数据或查找失败。

优点：

  • 数据元素无要求
  • 顺序存储链式存储都可以，顺序表通过数组下标依次扫描，链表通过指针 next 依次扫描。对线性的链表只能顺序查找
  • 对有序性也没有要求。对于有序表的查找，查找失败时可以不用再继续比较，降低顺序查找失败的 ASL。

缺点：是时间复杂度较大，n 较大时，ASL 大，效率较低。

时间复杂度：$O (n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* 顺序查找，Array为数组，n为要查找的数组元素个数，key为要查找的关键字*/
int seqSearch(int Array[], int key, int n) 
{
    for (int index = 0; index < n; index++)
    {
        if (Array[index] == key)
            return index;
    }
    return -1;
}
 
/*有哨兵顺序查找-优化最简单的顺序查找*/
/*优化部分：Array[0]存放要查找的关键字key，引入它的目的是使得循环不必判断数组是否越界，因为满足i==0时，循环一定跳出。
ps：Array[0] = key的目的就是让上述的简单顺序查找的两次判断修正为一次Array[i]与Array[0]是否相等的一次判断。*/
 
int seqSearch1(int Array[], int key, int n) {
    int i;         //声明i
    Array[0] = key;//设置哨兵
    for (i = n; Array[0] != Array[i]; i--){ }//从表后往前找，直到Array[0] == Array[i]
    return i;//若i为0，表示查找失败，否则R[i]是要找的结点
}

2 二分查找（折半查找）

性能优异，仅适用于有序的顺序表

二分查找：每次将中间位置的数与 key 比较，若相等则查找成功，不等则选择前半部分或后半部分继续查找。（例如，在升序表中，若给定值 key 大于中间元素，则查找的元素只能在后半部分）

时间复杂度：$O (log_2n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/* 二分查找，Array为数组，n为要查找的数组元素个数，key为要查找的关键字*/
/*二分查找，非递归*/
int binarySearch(int Array[],int key,int n) 
{
    int left = 0;//记录范围左边界
    int right = n - 1;//记录范围右边界
    int mid;//范围是否不为空
 
    while (left<=right)
    {
        mid = (right + left) / 2; //取中间位置
        if (Array[mid]==key)
        {
            return mid;//查找成功返回
        }
        else if (Array[mid]>key)
        {
            right = mid - 1; //继续在左半边中查找
        }
        else
        {
            left = mid + 1;//继续在右半边中查找
        }
    }
 
    return -1; // 当left>right时表示查找区间为空，查找失败
 
}
 
/* 二分查找，Array为数组，n为要查找的数组元素个数，key为要查找的关键字,left为范围左边界，right为范围右边界*/
 
/*二分查找，递归*/
 
int binarySearch1(int Array[],int left,int right,int key) 
{
 
    int mid = (right + left) / 2;
    if (Array[mid]==key)
        return mid;//查找成功返回
    else if (Array[mid]>key)
        binarySearch1(Array,left, mid - 1,key);//递归调用，在左半边查询
    else
        binarySearch1(Array, mid + 1,right,key);//递归调用，在右半边查询
}

3 插值查找

在介绍插值查找之前，首先考虑一个新问题，为什么上述算法一定要是折半，而不是折四分之一或者折更多呢？

打个比方，在英文字典里面查“apple”，你下意识翻开字典是翻前面的书页还是后面的书页呢？如果再让你查“zoo”，你又怎么查？很显然，这里你绝对不会是从中间开始查起，而是有一定目的的往前或往后翻。
同样的，比如要在取值范围1 ~ 10000 之间100 个元素从小到大均匀分布的数组中查找 5，我们自然会考虑从数组下标较小的开始查找。

经过以上分析，折半查找这种查找方式，不是自适应的（也就是说是傻瓜式的）。二分查找中查找点计算如下：

1
mid=(low+high)/2, 即 mid=low+1/2*(high-low);

　　通过类比，我们可以将查找的点改进为如下：

1
mid=low+(key-a[low])/(a[high]-a[low])*(high-low)

也就是将上述的比例参数 1/2 改进为自适应的，根据关键字在整个有序表中所处的位置，让mid值的变化更靠近关键字key，这样也就间接地减少了比较次数。

　　基本思想： 基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，插值查找也仅适用于有序的顺序表
　　
注：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。

时间复杂度： **$O (log_2(log_2n))$****。

1
2
3
4
5
6
7
8
9
10
11
//插值查找
int InsertionSearch(int Array[],int left,int right,int key) 
{
    int mid = left + (key - Array[left]) / (Array[right] - Array[left])*(right - left);//插值公式
    if (Array[mid] == key)
        return mid;
    if (Array[mid]>key)
        return InsertionSearch(Array, key, left, mid - 1);
    if (Array[mid]<key)
        return InsertionSearch(Array, key, mid + 1, right);
}

4 分块查找（索引顺序查找）

吸取了顺序查找和折半查找各自的优点，既有动态结构，有适合快速查找。

算法思想：
将查找表分为若个子块。子块内元素可以无序，块之间必须有序；即第 1 块中任一元素的关键字都必须小于第 2 块中任一元素的关键字；而第 2 块中任一元素又都必须小于第 3 块中的任一元素。以此类推。

算法流程：
　　1. 建立一个索引表（按关键字有序排列），索引表中每个元素含有各块的最大关键字和各块中的第一个元素的地址。
　　2. 查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；然后，在已确定的块中顺序查找。

时间复杂度：$O(log_2n)~O(n)$

例如, 关键码集合为{88,24,72,61,21,6,32,11,8,31, 22,83,78,54}, 按照关键码值 24,54,78,88，分为 4 个块和索引表，如图 7.3 所示。

Pasted image 20230901103623

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
typedef int KeyType;
typedef char InfoType[10];
typedef struct
{
    KeyType key;                //KeyType为关键字的数据类型 
    InfoType data;              //其他数据 
} NodeType;

typedef NodeType SeqList[MAXL]; //顺序表类型 
 
typedef struct
{
    KeyType key;            //KeyType为关键字的类型 
    int link;               //指向对应块的起始下标 
} IdxType;
 
typedef IdxType IDX[MAXI];  //索引表类型 
 
//I表示索引表如：IDX I = { { 14,0 },{ 34,5 },{ 66,10 },{ 85,15 },{ 100,20 } };
 
//m表示分块的数量如：m=5;
 
//R表示需要查找的数据表 如：KeyType a[] = { 8,14,6,9,10, 22,34,18,19,31, 40,38,54,66,46, 71,78,68,80,85, 100,94,88,96,87 };
 
//n表示a[]中的个数 n=25;
 
//K表示需要查找的数值 K=85;
 
int IdxSearch(IDX I, int m, SeqList R, int n, KeyType k) {   //二分查找法查找索引表
    int low = 0, high = m - 1, mid, i;
    int b = n / m;              //b为每块的记录个数 
    while (low <= high)       //在索引表中进行二分查找,找到的位置存放在low中 
    {
        mid = (low + high) / 2;
        if (I[mid].key >= k)
            high = mid - 1;
        else
            low = mid + 1;
    }
 
    //应在索引表的high+1块中,再在线性表中进行顺序查找 
    i = I[high + 1].link;
    
    while (i <= I[high + 1].link + b - 1 && R[i].key != k) //在顺序表中固定的块中查找
        i++;
    if (i <= I[high + 1].link + b - 1)
        return i + 1; //返回查找成功后该数值在顺序表中的序号
    else
        return 0;
}

B 树和 B+树

P270

定义

B 树，又称多路平衡查找树，B 树中所有结点的孩子个数的最大值称为 B 树的阶，通常用 m 表示。
一棵 m 阶 B 树或为空树，或为满足如下特性的 m 叉树:

[!NOTE] m 阶 B 树和核心特性

  1. 根结点的子树数 $[2, m]$，关键字数量 $[1, m-1]$
  2. 其他结点的子树数 $[\ulcorner{m/2}\urcorner,m]$，关键字数 $[\ulcorner{m/2}\urcorner-1,m-1]$
  3. 对任一结点，其所有子树高度都相同
  4. 关键字的值：类比二叉查找树，左<中<右
  5. 所有叶节点都在同一层，并且不带信息（可以视为外部结点，类似于折半查找失败结点。查找失败的结点。实际上这些结点不存在，指向这些结点的指针为空）

Pasted image 20230909095539

哈希表

构造方法：

  1. 直接定址法：直接去关键字的某个线性函数值作为散列地址
  2. 除留余数法：去一个接近或等于散列表表长的质数，用 key 除以该质数取余作为散列地址。
  3. 数字分析法
  4. 平方取中法

处理哈希冲突

  1. 开放定址法
  2. 拉链法

第八章 排序

1 排序的基本概念

  1. 排序：重新排列表中的元素，使表中元素满足按关键字有序的过程（关键字可以相同）
  2. 排序算法的评价指标：时间复杂度、空间复杂度；
  3. 排序算法的稳定性：关键字相同的元素在排序之后相对位置不变，称为稳定的；
  4. 排序算法的分类：
    内部排序： 数据都在内存——关注如何使时间、空间复杂度更低；
    外部排序： 数据太多，无法全部放入内存——关注如何使时间、空间复杂度更低，如何使读 / 写磁盘次数更少；

2 插入排序

基本思想：每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列，直到全部记录插入完成。

直接插入排序

[!NOTE] Title
稳定，使用于顺序、链式存储

假设在排序过程中，待排序表 $L[ 1… n]$在某次排序过程中的某一时刻状态如下:
Pasted image 20240221094351
要将元素 $L(i)$ 插入已有序的子序列 $L[ l… i-1]$，需要执行以下操作（为避免混淆，下面用 L[ ] 表示一个表，而用 L() 表示一个元素):

  1. 查找出 L(i) 在 $L[ l… i-1]$ 中的插入位置 k。
  2. 将 $L[ k… i-1]$中的所有元素依次后移一个位置。
  3. 将 L(i) 复制到 L(k)。

为了实现对 $L[l… n]$ 的排序, 可以将 L (2)~L (n) 依次插入前面已排好序的子序列, 初始 L[1]可以视为是一个已排好序的子序列。上述操作执行 n - 1 次就能得到一个有序的表。

Pasted image 20240221095134

  • 不带 “哨兵”（记这种，比较直观）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    void InsertSort(int A[], int n)
    {    //A中共n个数据元素
        int i,j,temp;
        for(i=1; i<n; i++)
        {
            if(A[i]<A[i-1])
            {    //A[i]关键字小于前驱
                temp = A[i];  
                
                for(j=i-1; j>=0 && A[j]>temp; --j)
                    A[j+1] = A[j];     //所有大于temp的元素都向后挪
                    
                //最后A[j]<temp,插入到j+1即可
                A[j+1] = temp;         //复制到插入位置
            }
        }
    }

  • 带 “哨兵” ，优点：不用每轮循环都判断 j>=0

1
2
3
4
5
6
7
8
9
10
11
12
13
void InsertSort(int A[], int n){    //A中从1开始存储，0放哨兵
    int i,j;
    for(i=2; i<n; i++) //依次将A[2]~A[n]插入前面已排序序列
    {
        if(A[i]<A[i-1])
        {    
            A[0] = A[i];     //复制为哨兵
            for(j=i-1; A[0] < A[j]; --j)  //从后往前查找待插入位置
                A[j+1] = A[j];     //向后挪动
            A[j+1] = A[0];          //复制到插入位置
        }
    }
}
  1. 算法效率分析

空间复杂度：O(1)
时间复杂度：主要来自于对比关键字、移动关键字，若有 n 个元素，则需要 n-1 躺处理
最好情况： 原本为有序，共 n-1 趟处理，每一趟都只需要对比 1 次关键字，不需要移动元素，共对比 n-1 次 —— O(n)
最差情况： 原本为逆序 —— O(n²)
平均情况： O(n²)
算法稳定性：稳定

  1. 对链表进行插入排序
    移动元素的次数变少了，因为只需要修改指针，不需要依次右移；
    但是关键字对比的次数依然是 O(n²) 数量级，因此整体看来时间复杂度仍然是 O(n²)

二分插入排序

[!NOTE] Title
稳定，仅适用于顺序表

  1. 思路： 先用二分查找找到应该插入的位置，再移动元素；

  2. 为了保证稳定性，当查找到和插入元素关键字一样的元素时，应该继续在这个元素的右半部分继续查找以确认位置; 即当 A[mid] == A[0] 时，应继续在 mid 所指位置右边寻找插入位置

  3. 当 low>high 时，折半查找停止，应将 [low,i-1] （或 [high+1,i-1]） 内的元素全部右移，并将 A[0]复制到 low 所指的位置；

  4. 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void InsertSort(int A[], int n){ 
    int i,j,low,high,mid;
    for(i=2;i<=n;i++){                  //A中从1开始存储，0放哨兵
        A[0] = A[i];                    //将A[i]暂存到A[0]
        low = 1; high = i-1;            //折半查找的范围

        while(low<=high){               //折半查找
            mid = (low + high)/2;       //取中间点
            if(A[mid]>A[0])             //查找左半子表
                high = mid - 1;
            else                        //查找右半子表
                low = mid + 1;
        }
        //此时low>high,low=high+1
        for(j=i-1; j>low;--j)       //统一后移元素，空出插入位置
            A[j+1] = A[j];
        A[low] = A[0];
    }
}
  1. 与直接插入排序相比，比较关键字的次数减少了，但是移动元素的次数没有变，时间复杂度仍然是 O(n²)

希尔排序

[!NOTE] Title
不稳定，仅适用于顺序表

基本思想是: 先将待排序表分割成若干形如 L[i, i+d, i+ 2d,…, i+ kd] 的特殊子表，即把相隔某个“增量”的记录组成一个子表，对各个子表分别进行直接插入排序，当整个表由的元素已旱“基本有序”时，再对全体记录进行一次直接插入排序。
希尔排序的过程如下: 先取一个小于 $n$ 的步长 $d_1$，把表中的全部记录分成 $d_1$ 组，所有距离为 $d_1$ 的倍数的记录放在同一-组，在各组内进行直接插入排序; 然后取第二个步长 $d_2<d_1$，重复上述过程，直到所取到的 $d_t= 1$，即所有记录已放在同一组中，再进行直接插入排序

希尔提出的方法是 $d_1 =n/2，d_{i+1}=d_i/2(向上取整)$，并且最后一个增量等于 1 ($d_i$ 时全部为一组进行排序)。

例如：第一躺增量取 $d_i=5$，分成了 5 个子序列，分别直接插入排序。第二趟取 $d_i=3$。
Pasted image 20230908111241

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void ShellSort(ElemType A[], int n){
    //A[0]为暂存单元
    for(dk=n/2; dk>=1; dk=dk/2)   //步长递减（看题目要求，一般是1/2
    {
        for(i=dk+1; i<=n; ++i)
        {
            if(A[i]<A[i-dk])
            {
                A[0]=A[i];
                for(j=i-dk; j>0&&A[0]<A[j];j-=dk)
                    A[j+dk]=A[j];         //记录后移，查找插入的位置
                A[j+dk]=A[0;]             //插入
            }
        }
    }
}

3 交换排序

基于 “交换” 的排序：根据序列中两个元素关键字的比较结果来对换这两个记录再序列中的位置；

[!NOTE]
交换排序每一趟确定至少一个元素的最终位置，其中快排是将枢轴元素记录在序列中的位置。

冒泡排序

[!NOTE] Title
稳定（为保证稳定性，关键字相同的元素不交换），适用于顺序、链式存储

基本思想：从后往前两两比较相邻元素的值，若为逆序（即 $A[i-1]>A[i]$)，则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置，关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”。
下一趟冒泡时，前一趟确定的最小元素不再参与比较,每趟冒泡的结果是把序列中的最小元素 (或最大元素）放到了序列的最终位置……这样最多做 n-1 趟冒泡就能把所有元素排好序。
图 8.3 所示为冒泡排序的过程，第一趟冒泡时:27<49，不交换;13<27，不交换;76>13，交换; 97>13，交换; 65>13，交换; 38>13，交换; 49>13，交换。通过第一趟冒泡后，最小元素已交换到第一个位置，也是它的最终位置。第二趟冒泡时对剩余子序列采用同样方法进行排序，以此类推，到第五趟结束后没有发生交换，说明表已有序，冒泡排序结束。
Pasted image 20230909100325

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//冒泡排序
void BubbleSort(int A[], int n)
{   //从0开始存放
    for(int i=0; i<n; i++)
    {
        bool flag = false; // 表示本趟冒泡是否发生交换的标志
        for(int j = n-1; j > i; j--) //一趟冒泡过程
        {
            if(A[j-1]>A[j])
            {      //若为逆序
                swap(A[j-1],A[j]);  //交换
                flag=true;
            }
        }
        if(flag==false)
            return;       //本趟遍历后没有发生交换，说明表已经有序，可以结束算法
    }
}
  1. 算法效率分析

空间复杂度：O(1)
时间复杂度
最好情况 (有序) ：只需要一趟排序，比较次数 = n-1，交换次数 = 0，最好时间复杂度 = O(n)
最坏情况 (逆序) ：比较次数 = (n-1)+(n-2)+…+1 = n(n-1)/2 = 交换次数，最坏时间复杂度 = O(n²)，平均时间复杂度 = O(n²)

快速排序

[!NOTE]

  • 不稳定
  • 快排是所有内部排序算法中平均性能最优的排序算法
  • 不产生有序子序列，每趟排序后会将枢轴元素放在最终位置

快速排序的基本思想是基于分治法的：在待排序表 $L[ 1… n ]$ 中任取一个元素 pivot 作为枢轴（或基准，通常取首元素)，通过一趟排序将待排序表划分为独立的两部分 $L[ 1\dots k-1]$ 和 $L[k+1\dots n ]$，使得 $[ 1\dots k-1]$ 中的所有元素小于 pivot，$L[ k+1\dots n]$ 中的所有元素大于等于 pivot，则 pivot 放在了其最终位置 $L(k)$ 上，这个过程称为一趟快速排序（或一次划分)。然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。

  1. 选枢轴（取第一个元素），右往左找小换，左往右找大换
  2. 每一趟要对所有子序列排序
    Pasted image 20230909101333

快速排序算法的关键在于划分操作，同时快速排序算法的性能也主要取决于划分操作的好坏。
快排的划分操作有多种版本，这里使用的严蔚敏数据结构版本。假设每次总以当前表中第一个元素作为枢轴来对表进行划分，则将表中比枢轴大的元素向右移动, 将比枢轴小的元素向左移动，使得一趟 Partition() 操作后，表中的元素被枢轴值一分为二。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//用第一个元素将待排序序列划分为左右两个部分
int Partition(int A[], int low, int high){
    int pivot = A[low];          //用第一个元素作为枢轴
    while(low<high) //循环跳出条件
    {
        while(low<high && A[high]>=pivot) --high; //high所指元素大于枢轴，high左移
        A[low] = A[high];   //high所指元素小于枢轴，移动到左侧

        while(low<high && A[low]<=pivot)  ++low; //low所指元素小于枢轴，low右移
        A[high] = A[low];   //low所指元素大于枢轴，移动到右侧
    }
    A[low] = pivot   //枢轴元素存放到最终位置
    return low；     //返回存放枢轴的最终位置
} 

//快速排序
void QuickSort(int A[], int low, int high)
{
    if(low>=high)  return;  //递归跳出条件
    
    int pivotpos = Partition(A, low, high);   //划分
    QuickSort（A, low, pivotpos - 1);    //划分左子表
    QuickSort（A, pivotpos + 1, high);   //划分右子表
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int Partition(int A[], int low, int high){
    int pivot = A[low];         
    while(low<high)
    {
        while(low<high && A[high]>=pivot) --high; 
        A[low] = A[high];   

        while(low<high && A[low]<=pivot)  ++low; 
        A[high] = A[low];   
    }
    A[low] = pivot   
    return low；     
} 


void QuickSort(int A[], int low, int high)
{
    if(low>=high)  return;  //递归跳出条件
      
    int pivotpos = Partition(A, low, high);   
    QuickSort（A, low, pivotpos - 1);   
    QuickSort（A, pivotpos + 1, high);  
}

快速排序算法优化思路：

  1. 尽量选择可以把数据中分的枢轴元素，如选头、中、尾三个位置的元素，取三个元素的中间值作为枢轴元素；
  2. 随机选一个元素作为枢轴元素，这样可使得最坏情况（初始排序表基本有序或基本逆序）在实际排序中几乎不发生。

4 选择排序

[!NOTE]
元素间的比较次数与初始状态无关，每躺确定一个元素的最终位置

选择排序的基本思想是: 每一趟（如第 $i$ 趟）在后面 $n-i+1 (i= 1,2,…, n- 1)$个待排序元素中选取关键字最小的元素，作为有序子序列的第 $i$ 个元素，直到第 $n-1$ 趟做完，待排序元素只剩下 1 个，就不用再选了

简单选择排序

[!note]
不稳定，适用于顺序、链式存储

n 个元素的简单选择排序需要 n-1 趟处理；

假设排序表为 $L[ 1… n]$，第 $i$ 趟排序即从 $L[ i… n ]$ 中选择关键字最小的元素与 $L (i)$ 交换，每一趟排序可以确定一个元素的最终位置，这样经过 n-1 趟排序就可使得整个排序表有序。（每次从未排序序列中选取最小关键字加入已排序序列末尾）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void SelectSort(int A[], int n) //A从0开始
{       
    for(int i=0; i<n-1; i++) 
    {          
        int min = i;                   //记录最小元素位置
        for(int j=i+1; j<n; j++)       //在A[i...n-1]中选择最小的元素
        {
            if(A[j]<A[min]) 
            {
                min = j;   //更新最小元素位置
            }
        }
        if(min!=i)  
        {                   
            swap(A[i],A[min]);         //交换
        }
    }
}

堆排序

[!NOTE]

  • 不稳定。
  • 每趟确定一个最终位置
  • 每一趟将堆顶元素加入有序子序列（与待排序序列中的最后一个元素交换），并将待排序元素序列再次调整为大根柱（小元素不断下坠）

堆排序适合关键字较多的情况。例如，在 1 亿个数中选出前 100 个最大值? 首先使用一个大小为 100 的数组，读入前 100 个数，建立小顶堆，而后依次读入余下的数，若小于堆顶则舍弃，否则用该数取代堆顶并重新调整堆，待数据读取完毕，堆中 100 个数即为所求。

堆（Heap）是非线性数据结构，相当于一维数组，有两个直接后继。

  • 堆中某个结点的值总是不大于或不小于其父结点的值；

  • 堆可以视为一颗完全二叉树。

  • 大根堆：根 $≥$ 左、右

  • 小根堆：根 $≤$ 左、右
    Pasted image 20230909104822

堆排序的思路: 首先将存放在 $L[ 1… n ]$ 中的 $n$ 个元素构造初始堆，由于堆本身的特点 (以大顶堆为例)，堆顶元素就是最大值。输出堆顶元素后，通常将堆底元素送入堆顶，此时根结点已不满足大顶堆的性质，堆被破坏，将堆顶元素向下调整使其继续保持大顶堆的性质，再输出堆顶元素。如此重复，直到堆中仅剩一个元素为止。

堆排序的关键是构造初始堆。$n$ 个结点的完全二叉树，最后一个结点是第 $\left\lfloor{n/2}\right\rfloor$ 个结点的孩子。对第 $\left\lfloor{n/2}\right\rfloor$ 个结点为根的子树筛选（对于大根堆，若根结点的关键字小于左右孩子中关键字较大者，则交换)，使该子树成为堆。之后向前依次对各结点 $\lfloor n/2\rfloor-1{\sim}1$ 为根的子树进行筛选，看该结点值是否大于其左右子结点的值，若不大于，则将左右子结点中的较大值与之交换交换后可能会破坏下一级的堆，于是继续采用上述方法构造下一级的堆，直到以该结点为根的子树构成堆为止。反复利用上述调整堆的方法建堆，直到根结点。
大根堆构造示例：如图 8.5 所示

  1. 初始时 $\left\lfloor{n/2}\right\rfloor=4$ 所以调整 $L (4)$ 子树，$09< 32$，交换，交换后满足堆的定义;
  2. 向前继续调整 $L (3)$ 子树，$78<左右孩子的较大者 87$，交换（与较大者交换位置才能满足大根堆定义！）交换后满足堆的定义;
  3. 向前调整 $L(2)$ 子树，$17<左右孩子的较大者 45$，交换后满足堆的定义;
  4. 向前调整至根结点 $L (1)$，$53<左右孩子的较大者 87$，交换，交换后破坏了 $L (3)$ 子树的堆，采用上述方法对 $L(3)$ 进行调整，$53<左右孩子的较大者 78$，交换，至此该完全二叉树满足堆的定义。

Pasted image 20230909110255

输出堆顶元素后，将堆的最后一个元素与堆顶元素交换，此时堆的性质被破坏，需要向下进行筛选。将 $09$ 和左右孩子的较大者 $78$ 交换，交换后破坏了 $L (3)$子树的堆，继续对$L (3)$子树向下筛选，将 $09$ 和左右孩子的较大者 $65$ 交换，交换后得到了新堆，调整过程如图 8.6 所示。

插入：同时，堆也支持插入操作。对堆进行插入操作时，先将新结点放在堆的末端，再对这个新结点向上执行调整操作。大根堆的插入操作示例如图 8.7 所示。
Pasted image 20230909111108

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//对初始序列建立大根堆
void BuildMaxHeap(int A[], int len)
{
    for(int i=len/2; i>0; i--)   //从后往前调整所有非终端结点
    {
        HeadAdjust(A, i, len);
    }
}

/*将以k为根的子树调整为大根堆，从最底层的分支结点开始调整*/
void HeadAdjust(int A[], int k, int len){
    A[0] = A[k];                      //A[0]暂存子树的根结点
    
    //沿key较大的子结点向下筛选
    // i为当前所选根结点的左孩子
    //i*=2是为了判断调整后再下一层是否满足大根堆
    for(int i=2*k; i<=len; i*=2)
    {     
        if(i<len && A[i]<A[i+1])      //判断：当前所选根结点的左、右结点哪个更大
            i++;                      //取key较大的子结点的下标
        if(A[0] >= A[i]) 
            break;                    //筛选结束：i指向更大的子结点
        else{
            A[k] = A[i];              //将A[i]调整至双亲结点上
            k=i;                      //修改k值，以便继续向下筛选
        }
    }
    A[k] = A[0]                       //被筛选的结点的值放入最终位置
}

//基于大根堆进行排序
void HeapSort(int A[], int len)
{
    BuildMaxHeap(A, len);          //初始建堆
    for(int i=len; i>1; i--)
    {      //n-1趟的交换和建堆过程
        swap(A[i], A[1]);          //堆顶元素和堆底元素交换
        HeadAdjust(A,1,i-1);       //把剩余的待排序元素整理成堆
    }
}

5 归并排序和基数排序

归并排序

基本思想是把待排序的元素分解成两个规模大致相等的子序列。如果不易分解，将得到的子序列继续分解，直到子序列中包含的元素个数为 1。因为单个元素的序列本身就是有序的，此时便可以进行合并，从而得到一个完整的有序序列。

首先我们先给定一个无序的数列（42，15，20，6，8，38，50，12），我们进行合并排序数列，如下图流程图所示：

7d3c721ac709c7dec6b5ace07379d591_MD5

  1. 首先将待排序的元素分成大小大致相同的两个序列。
  2. 再把子序列分成大小大致相同的两个子序列。
  3. 如此下去，直到分解成一个元素停止，这时含有一个元素的子序列都是有序的。
  4. 进行合并操作，将两个有序的子序列合并为一个有序序列，如此下去，直到所有的元素都合并为一个有序序列。

 
举例，下面我将以序列（4，9，15，24，30，2，6，18，20）进行图解。

（1）初始化：i = left，j = mid+1，mid = (left+right)/2 ，申请一个辅助数组 b

49630c00e5ac716cfde43bec775b2a9b_MD5

1
2
vector<int> b(right-left+1,0); //辅助数组
int i = left, j = mid + 1, k = 0;    // k为 b 数组的小标

 （2）现在比较 a[i]  和 b[j]  ，将较小的元素放在 b 数组中，相应的指针向后移动，直到 i > mid 或者 j>right 时结束。

1
2
3
4
5
6
7
8
9
10
11
while (i <= mid && j <= right)  
 {
	if (a[i] <= a[j])
	{
		b[k++] = a[i++];  //按从小到大存放在 b 数组里面
	}
	else
	{
		b[k++] = a[j++];
	}
}

进行第一次比较 a[i]=4  和 a[j]=2，将较小的元素 2 放入数组  b  中，j++, k++，如下图：

d9e074978a304b3018ec53329599489a_MD5

 进行第二次比较 a[i]=4  和 a[j]=6，将较小的元素放 4 入数组  b  中，i++, k++，如下图：

c2f8684c7186d6b810485aebd90951c2_MD5

 进行第三次比较 a[i]=9  和 a[j]=6，将较小的元素放 6 入数组  b  中，j++, k++，如下图：

6b114267a60a8648fd97a3b1f77b8455_MD5

 进行第四次比较 a[i]=9  和 a[j]=18，将较小的元素放 9 入数组  b  中，i++, k++，如下图：

8b887cb976b5ad392289d8672ff81e35_MD5

 进行第五次比较 a[i]=15  和 a[j]=18，将较小的元素放 15 入数组  b  中，i++, k++，如下图：

1fc6c8520341c914152f46751095e50d_MD5

  进行第六次比较 a[i]=24  和 a[j]=18，将较小的元素放 18 入数组  b  中，j++, k++，如下图：

9cb730dd00f9d215e92edf2fddeadf82_MD5

 进行第七次比较 a[i]=24  和 a[j]=20，将较小的元素放 20 入数组  b  中，j++, k++，如下图：

6578a9ffce0f728494377aa379404d71_MD5

 此时，j>right 了，while 循环结束，但 a 数组还剩下元素（i<mid）可直接放入  b  数组就可以了。如下图所示：

66355570a1eae54e8573b6ff3f5e402a_MD5

1
2
3
4
5
6
7
8
while (i <= mid)  // j 序列结束，将剩余的 i 序列补充在 b 数组中 
{
    b[k++] = a[i++];
}
while (j <= right)// i 序列结束，将剩余的 j 序列补充在 b 数组中 
{
    b[k++] = a[j++];
}

**现在将  b  数组的元素赋值给 a 数组

1
2
3
4
5
// 将排序后的部分复制回原数组
for (i = 0; i < b.size(); i++)
{
    a[left + i] = b[i];
}

（3）递归的形式进行归并排序

1
2
3
4
5
6
7
8
9
void mergesort(int* a, int left, int right) //归并排序 {
	if (left < right)
	{
		int mid = (left + right) / 2;
		mergesort(a, left, mid);          //对 a[left,mid]进行排序
		mergesort(a, mid + 1, right);    //对 a[mid+1,right]进行排序
		merge(a, left, mid, right);       //进行合并操作
	}
}

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
using namespace std;

//将前后相邻的两个有序表归并为一个有序表
void merge(vector<int>& a, int left, int mid, int right)
{
    //优化点：在函数内部创建vector会频繁构造和析构，可以将数组提出来，传引用进去。
    vector<int> b(right - left + 1, 0); // 辅助数组
    
    int i = left, j = mid + 1, k = 0;  // k为 b 数组的小标

    while (i <= mid && j <= right)
    {
        if (a[i] <= a[j])
        {
            b[k++] = a[i++]; // 按从小到大存放在 b 数组里面
        }
        else
        {
            b[k++] = a[j++];
        }
    }
    
    //没有归并完的部分复制到尾部，while只会执行一个
    while (i <= mid) // j 序列结束，将剩余的 i 序列补充在 b 数组中
    {
        b[k++] = a[i++];
    }

    while (j <= right) // i 序列结束，将剩余的 j 序列补充在 b 数组中
    {
        b[k++] = a[j++];
    }

    // 将排序后的部分复制回原数组
    for (i = 0; i < b.size(); i++)
    {
        a[left + i] = b[i];
    }
}

// 归并排序
void mergesort(vector<int>& a, int left, int right) 
{
    if (left < right)
    {
        int mid = (left + right) / 2;
        mergesort(a, left, mid);      // 对 a[left,mid]进行排序
        mergesort(a, mid + 1, right); // 对 a[mid+1,right]进行排序
        merge(a, left, mid, right);    // 进行合并操作
    }
}

int main()
{
    int n;
    cout << "请输入数列中的元素个数 n 为：" << endl;
    cin >> n;
    vector<int> a(n,0); //初始化数组a
    
    cout << "请依次输入数列中的元素：" << endl;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    mergesort(a, 0, n - 1);

    cout << "归并排序结果" << endl;
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
    return 0;
}

02c0974c3f48db616f8e064348d2cdab_MD5

基数排序

[!NOTE]
稳定（基你太稳）

基数排序是一种很特别的排序方法，它不基于比较和移动进行排序，而基于关键字各位的大小进行排序。
为实现多关键字排序，通常有两种方法:

  1. 最高位优先 (MSD）法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。
  2. 最低位优先（LSD）法，按关键字权重递增依次进行排序，最后形成一个有序序列。
    Pasted image 20230909141501
    Pasted image 20230909141512
    Pasted image 20230909141518

基数排序擅长解决的问题
①数据元素的关键字可以方便地拆分为 d 组，且 d 较小；
②每组关键字的取值范围不大，即 r 较小；
③数据元素个数 n 较大；

时间复杂度 $O(d(n+r))$
d：分配手机的趟数
n：数据元素个数
r：有多少个队列

6 排序算法比较

Pasted image 20230909142233

平均时间复杂度：快以 $O(nlog_2n)$ 的速度归队 (堆)，其他都为 $O(n^2)$，特别基数 $O(d (m+n))$
最坏时间复杂度：快排为 $O(n^2)$，其他如平均
最好时间复杂度：直接插入插得好变 $O(n)$，起泡起的好变 $O(n)$，其他如平均。（插得好起的好意为初始序列有序）

空间复杂度：快排为 $O (log2_n)$，归并为 $O(n)$，基数为 $O(r)$，其他都为 $O(1)$

稳定性：情绪不稳定，快希选一堆好友来聊天吧
（选：简单选择排序）

一趟排序确定一个最终位置：交换（冒泡，快排），选择（简单选择，堆）
关键字比较次数与原始无关：选择排序、折半插入排序，归并
排序趟数和原始有关：交换（冒泡，快排）