数据结构与算法笔记

此份笔记是本人学习过程中自己总结记录的，其内容受到课堂教学内容、采用教材、个人认知水平的影响。虽然笔者力图保证内容准确以及易于理解（起码自己能看懂），但难免存在谬误或者渲染问题。非常欢迎您通过邮件等方式联系我修改，让我们一起让这份笔记变得更好！

第一章绪论

1、基本概念与术语

数据：对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称

数据元素：数据的基本单位。一个数据元素可以有若干个数据项组成

数据对象：性质相同的数据元素的集合，是数据的一个子集（如整数数据对象等）

数据结构：相互之间存在一种或多种特定关系的数据元素的集合。通常有以下的几种基本结构

集合
线性结构（一对一）
树形结构（一对多）
图状结构（多对多）

数据结构形式定义为一个二元组(D, S)，其中 D 为数据元素的有限集，S 是 D 上关系的有限集。

逻辑结构：数据元素之间的逻辑关系

物理结构：又称存储结构，是数据结构在计算机中的表示

数据元素之间的关系在计算机中有两种不同的表示方法：

顺序映像：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系（例如数组）

非顺序映像：借助指示元素存储地址的指针来表示数据元素之间的逻辑关系（例如链表）

对应得到两种不同的存储结构：顺式存储结构和链式存储结构

数据类型：一个值的集合和定义在这个值集上的一组操作的总称。按照“值”的特性可分为

原子类型（整型，字符型等）
结构类型（数组等）

抽象数据类型：一个数学模型以及定义在该模型上的一组操作。其定义仅取决于它的一组逻辑特性，而与在计算机内部的表示和实现无关。只要数学特性不变，使用方式就不会改变。按照“值”的特性可分为

原子类型
固定聚合类型（如复数类型）
可变聚合类型

后两者均是结构类型

数据类型是已经实现了的抽象数据类型

抽象数据类型形式定义为三元组(D, S, P)

其中 D 是数据对象，S 是 D 上的关系集，P 是对 D 的基本操作集。基本操作的描述要包括：输入、输出、初始条件（前件）、操作结果（后件）

2、算法

算法：对特定问题求解步骤的一种描述，是指令的有限序列，包含五个重要特性

有穷性
确定性
可行性
输入
输出

好算法的要求：

正确性
可读性
健壮性
效率与低存储量需求（时间和空间复杂度满足要求）

算法的选择：

问题规模大，选择符合时间复杂度要求的算法
问题规模小，选择实现起来简单，代码量小的算法

第二章线性表

1、线性表的定义

线性结构的特点：

存在唯一的被称为“第一个”的数据元素
存在唯一的被称为“最后一个”的数据元素
除第一个之外，集合中的每个数据元素均只有一个前驱
除最后一个之外，集合中的每个数据元素均只有一个后驱

2、顺序表示

线性表的顺序表示：用一组地址连续的存储单元依次存储线性表的数据元素

线性表中数据元素的存储位置之间的关系

$\text{LOC}(a_{i+1})=\text{LOC}(a_i)+l$

下标代表了数据元素在数组中的位置

数据元素在物理上的相邻就代表了在逻辑关系上的相邻

存储密度的计算公式

$\text{存储密度}=\frac{\text{存储数据元素占用空间}}{\text{存储数据元素占用空间+存储逻辑关系占用空间}}$

线性表的顺序存储时

优点

结构简单，实现容易
存储效率高
是随机存储结构

缺点

插入和删除元素时效率低（因为线性表采用连续存储设计时，要保证逻辑上相邻的元素在物理上也相邻）
长度固定，需要预先分配较大的空间，要经常扩充线性表

3、链式表示

链式存储的特点：用一组任意的存储单元存储线性表的数据元素。

单链表：除了存储其本身的信息之外，还需存储一个指示其直接后继的信息。两部分信息组成数据元素的存储映像，包含两个域：存储元素信息的域称为数据域，存储直接后继位置的域称为指针域。 $n$ 个节点链结成一个链表，即线性表的链式存储结构。

单链表是非随机存取的存储结构

双向链表：节点中有两个指针域，其一指向直接后继，另一指向直接前驱

循环链表：表中最后一个节点的指针域指向头节点

判断是否为空链表：if(head->next==head)

静态链表：用静态数组来实现链表

数组的一个单元包括数据 Data 和游标 Next 两部分，分别对应着数据域和指针域

游标就指向该链表下一个节点的序号

实际上在这个数组上，建立起了两个链表。一个是有数据的占用表，另一个是尚未存放数据的空闲表。用变量维护两个表的表头。

一开始占用表是空的，对空闲表进行初始化

Next[i]=i+1;
Next[N-1]=-1;

Available=0; //空闲表的头节点

插入节点时，从空闲表上取得第一个节点；删除时，把删除下来的节点连接到空闲表上

链式设计的优点：

占用空间就是实际空间
灵活

链式设计的缺点：

不是随机访问，查找元素效率低
实现比较复杂

第三章栈和队列

1、栈

栈是限定在表尾进行插入或者删除的线性表。表尾称之为栈顶，表头称之为栈底。

基本操作，构造空栈，销毁栈，判断空栈，栈长，插入，删除

栈的两种实现

顺序栈，用一维数组实现
- 结构简单
- 存储密度高
- 空间使用不灵活，要事先分配；空间不足时还要扩容
链栈，用链表实现，一般将链表首作为栈顶
- 空间利用比较灵活
- 实现起来比较复杂

2、表达式处理

表达式可分为：

前缀表达式（波兰式）
中缀表达式（即我们一般看到的表达式的样子）
后缀表达式（逆波兰式，计算机一般使用这种）

举个例子：

$*+ab-ab,\ (a+b)*(a-b),\ ab+ab-*$

以上是同一个式子的前缀，中缀，后缀表达式（很像树的前中后序遍历）

对于中缀表达式求值时，先有一个算符优先表，然后构造一个运算符栈和运算数栈

每读入一个运算符，与栈顶的运算符比较
- 若栈顶运算符的优先级比较大，先不管新来的运算符，运算符栈和运算数栈弹栈，进行一次运算，再将结果入栈
- 若新来的运算符优先级比较大，新来的运算符直接入栈，不用运算；若相等，运算符栈弹一次栈（即构成一对括号或者表达式运算结束的情况）
每读入一个运算数，直接入运算数栈

引入#作为表达式的结束符，同时在运算符最左边也加一个#，这样两个#相当于构成了一对括号。运算符栈初始状态里面应该有一个#。构造算符优先表时，应该把#也考虑进去。

对于后缀表达式求值，只需要一个操作数栈，一直读入，遇到操作符时，就弹出两个操作数进行运算，再把结果压回去。

将中缀表达式转化为后缀表达式，创建一个运算符栈，不断读入中缀表达式

遇到运算数，直接输出（注意运算数之间要输出适当的分隔符）
遇到运算符，与栈顶的运算符的优先级比较
- 如果栈顶的元素优先级低，则新运算符入栈
- 如果相等，弹运算符栈
- 如果栈顶元素的优先级高，弹运算符栈并输出，然后继续与新的栈顶比较。

3、递归

递归调用：子程序（或子函数）直接调用自己或者通过一系列调用语句间接调用自己。

递归定义的算法有两个部分：

递归基：直接定义最简单情况下的函数值
递归步：通过较为简单情况下的函数值定义一般情况下的函数值

递归算法适用的条件：

问题具有某种可借用的类同自身的子问题描述的性质
某一有限步子问题（也称为本原问题）有直接解的存在

递归算法的分类

单路递归（一个递归过程只有一个递归入口）
多路递归（有多个递归入口）
间接递归（函数可以通过其他函数间接调用自己）
迭代递归（每次递归调用都包含一次循环递归）

递归时，系统会设立一个递归工作栈，每一层递归所需的信息构成一个工作记录（包括所有实参，所有局部变量以及上一层的返回地址）。

每进入一层递归，就产生一个新的工作记录压入栈顶；每退出一层递归，就从栈顶弹出一个工作记录。

将递归程序改成非递归程序，就是自己来模拟这种过程，而不是由计算机来完成。（所以两者的时间复杂度不会差很多，本质上是一样的）

4、队列

队列是限定在表头删除，表尾插入（FIFO，先进先出）的线性表，也分为两种：

顺序队列：利用一组连续的存储单元依次存放队首到队尾的各个元素。设头指针和尾指针，约定头指针总是指向队首元素的前一个位置；头指针和尾指针相同时，说明队空。

循环队列，将队列分配的地址空间看成一个首尾相接的圆环。可以解决假溢出现象。头指针和尾指针相同的时候，可能是队空，也可能是队满。
链队列：用链表表示的队列

第四章串

1、串的概念

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

零个字符的串成为空串。空白字符构成的串称为空白串，不是空串。

子串是串中任意个连续字符组成的子序列，包含子串的串称为主串。子串的第一个字符在主串中的位置被称为子串在主串中的位置。

2、串的存储

压缩存储和非压缩存储

假设一个内存单元是 32 位，一个字符（ASCII 码形式）只要 8 位，所以一个单元可以存储四个字符，这就是所谓的压缩存储

可以用顺序存储，也可以用链式存储

链式存储时，如果每一个节点只存放一个字符，则节点的指针域就很多，浪费存储空间。所以一个节点通常要放两三个字符。

这种情况下，如果要插入串，就可能要把原来的某个节点拆开，然后再插入。这样的话，一些节点就不会占满，造成存储密度的进一步下降。所以每个节点存储的字符也不能过多。

3、串的模式匹配算法

子串的定位操作通常称为串的模式匹配算法，形式为Index(S, T, pos)

也即在寻找子串 T 在主串 S 中第 pos 个字符之后的位置，其中 S 称为目标串，T 称为模式串

以下默认字符串下标从 1 开始

3.1、朴素模式匹配算法

用分别指向目标串和模式串的两个指针，一开始两个指针都指向各自串的第一个字符。比较当前两个指针指向的字符，如果相等，则两个指针同时向后移动一位，继续比较，直到碰到模式串的末尾或某两个字符不相等。若碰到模式串末尾，则说明匹配成功；若某两个字符不等，说明匹配失败，目标串指针要回溯到开始比较的位置的后一个位置，模式串指针也要回到初始位置，重新开始匹配。

int Index(string S, string T, int pos)
{
    int i=pos, j=1;
    while(i<=S.length() && j<=T.length())
    {
        if(S[i]==T[j])
            i++, j++;
        else
        {
            i=i-j+2;
            j=1;
        }
    }

    if(j>=T.length())
        return i-j;
    else
        return -1;
}

时间复杂度是 $O(nm)$ ，效率低的主要原因是，匹配时进行了大量冗余匹配和指针回溯。

3.2、KMP 算法

利用了已经得到的“部分匹配”的结果，不进行回溯。不再是逐个遍历，每次匹配失败后，向右滑动尽可能远的一段距离再比较。

KMP 算法的基本模式与朴素算法一样，只是在匹配失败时，假设此时

$\begin{align} ...,&S_{i-j+1}&S_{i-j+2}&S_{i-j+3}&...&S_{j-1}&S_j\\ &T_1&T_2&T_3&...&T_{i-1}&T_i \end{align}$

已经匹配了串 $T$ 的前 $i-1$ 个字符，但是 $S_j\neq T_i$ 。下一步，不再是将 $T_1$ 与 $S_{i-j+2}$ 比较（即仅将模式串向右滑动 1 位），而是要尽量向右滑动，忽略到中间必定匹配不上的一些情况。

假设模式串可以向右滑动的距离为 $(i-1)-x$ ，也即让 $T_x$ 与 $S_{j-1}$ 对齐，则模式串向右滑动到：

$\begin{align} ...,&S_{j-x}&S_{j-x+1}&S_{j-x+2}&...&S_{j-1}&S_j\\ &T_1&T_2&T_3&...&T_{x}&T_{x+1} \end{align}$

首先要保证前 $x$ 个字符是匹配上的，再由滑动前的匹配情况，一定有：

$T_1T_2T_3...T_x=T_{i-x}T_{i-x+1}T_{i-x+2}...T_{i-1}=S_{j-x}S_{j-x+1}S_{j-x+2}...S_{j-1}$

其次，由于要找第一次出现的位置，所以不能向右滑过头了，滑到最近的满足要求的地方就好了。易知 $x$ 越大，向右滑动的距离越小，所以我们要让 $x$ 尽量大。

又可以发现， $x$ 是串 $T_1T_2\dots T_{i-1}$ 的一个公共前缀和后缀的长度。

所以，我们需要的 $x$ 值就是串 $T_1T_2\dots T_{i-1}$ 的前缀和后缀的最长公共元素的长度（注意，串的前后缀是不包括本身的）。

实际代码实现时，我们不用真的使模式串向右滑动，只需要修改在模式串上的指针即可，易知指针应该从 $i$ 修改到 $x+1$ 处。

记 $Next[i]=x+1$ ，则可知失配的时候，模式串上原来指向 $i$ 的指针要回到 $Next[i]$ 处，在目标串上的指针不变。

int KMP(string S, string T, int pos){
    int i=pos, j=1;
    while(i<S.length() && j<T.length()){
        if(j==0 || S[i]==T[j])
            i++, j++;
        else
            j=next[j];
    }
    if(j>=T.length())
        return i-j+1;
    else
        return -1;
}

3.3、 $Next$ 数组的计算

假设模式串为 $T_1T_2T_3...T_n$

则

$Next[j]=\begin{cases} 0&, j=1\\ max\{x|T_1T_2...T_{x}=T_{j-x}T_{j-x+1}...T_{j-1}\}+1&, \text{这样的x存在时}\\ 1&, \text{其他情况} \end{cases}$

具体而言，如果有 $Next[j]=k$ ，也就是说 $T_1T_2...T_{k-1}=T_{j-k+1}T_{j-k}...T_{j-1}$ 。

若有 $T_k=T_j$ ，则显然 $Next[j+1]=k+1$
若 $T_k\neq T_j$ ，则将其视作一个模式匹配问题，此时的目标串和模式串均是串 T。现在从目标串第 $j-k-1$ 位开始已经连续匹配上了 $k-1$ 个，第 $k$ 位没匹配上。按照 KMP 算法，将模式串向右滑动，令 $T_{Next[k]}$ 与 $T_j$ 比较。
- 如果相同，说明有长度为 $Next[k]$ 的公共前缀和后缀，也即 $Next[j+1]=Next[k]$ 。
- 如果不同，说明仍然失配，继续右滑，令 $T_{Next[Next[k]]}$ 与 $T_j$ 比较，依次类推。

void Cal_Next(string T, vector<int>& next)
{
    next[1]=0;

    int j=1, k=next[j];
    while(j<T.length())
    {
        if(k==0 || T[j]==T[k])
        {
          next[j+1]=k+1;
          j++, k++;
        }
        else
          k=next[k];
    }
}

3.4、KMP 算法的改进

在目标串aaabaaaab与模式串aaaab比较时，当失配时，每次只能向右滑动一位。但实际上模式串前四位都相同，不可能与目标串的 b 匹配上。所以这些比较都是“浪费的”，应该直接向右滑动四位。

也就是说，按照 3.3 中的流程，如果已经有 $Next[j]=k$ （ $k<j$ ），且模式串中接下来有 $T_j=T_k$ ，

我们知道主串中如果 $S_i\neq T_j$ ，则显然也会有 $S_i\neq T_k$ ，一次修改指针到不了位。

所以我们加以改进，在计算 $Next$ 数组时，如果碰上 $T_j=T_k$ ，那就直接让 $Next[j]=Next[k]$ ，从而实现一步滚到位

记修正后的数组为 $Nextval$

void Cal_Nextval(string T, vector<int>& nextval){
    nextval[1]=0;
    int j=1, k=nextval[j];
    while(j<T.length()){
        if(k==0 || T[j]==T[k]){
            if(T[j+1]==T[k+1])
                nextval[j+1]=nextval[k+1];
            else
                nextval[j+1]=k+1;
            j++, k++;
        }
        else
            k=nextval[k];
    }
}

第五章数组和广义表

1、数组

数组是一组偶对（下标值，数据元素值）的集合。在数组中，对于一组有意义的下标，都存在一个与其对应的值。

数组是由 $n$ 个具有相同数据类型的数据元素组成的有限序列，且该序列必须存储在一组连续的存储单元中，元素数目不许改变，所以只有查，存，改的结构

与线性表的差异：数组是在数据元素个数上受限

由于数组天然没有增删操作，所以一般用顺序存储来表示数组

两种顺序存储方式：

行优先存储：同一行的紧邻存放，行与行之间再依次存放（Pascal，C 语言）
列优先存储：同一列的紧邻存放，列与列之间再依次存放（Fortran）

假设一个 $n$ 维数组Array[b_1][b_2]...[b_n]，则任意一个数组元素的地址可以写成：

$LOC(j_1, j_2, j_3, ..., j_n)=LOC(0, 0, 0, ..., 0)+\sum_{i=1}^{n}c_ij_i,\ c_n=L,\ c_{i-1}=c_i\times b_i$

其中 L 为一个数据元素所占的存储单元数量

2、矩阵的压缩存储

2.1、对称矩阵

只需要存一半的元素即可，只需要在二维坐标和一维顺序里建立一个映射

若要存储下半三角形，为方便实现，按照”行优先“的思想，可以建立如下映射：

$k=\begin{cases} i*(i-1)/2+j-1, i\geqslant j\\ j*(j-1)/2+i-1,i<j \end{cases}, b_k=a_{i, j}$

注意，b 数组的下标从 0 开始

2.2、三角矩阵

以上三角矩阵为例，其下三角（不包括对角线）都是一个相同的常数，只需要用一个空间来存储即可。

与对称矩阵类似，若要存储一个下三角矩阵，可以建立如下映射：

$k=\begin{cases} i*(i-1)/2+j-1, i\geqslant j\\ n*(n-1)/2,i<j \end{cases}, b_k=a_{i, j}$

2.3、对角矩阵

元素分布在以对角线为中心的带状区域中，其余元素都是 0

也可以按照行优先的思想或者对角线的顺序进行存储，一般都是有一定规律的

2.4、稀疏矩阵

假设在 $m\times n$ 的矩阵中，有 $t$ 个元素不为 0，令 $\displaystyle\delta=\frac{t}{m\times n}$ ，则 $\delta$ 就被称为矩阵的稀疏因子，当 $\delta \leqslant0.05$ 时，认为该矩阵是稀疏矩阵

对于稀疏矩阵中的每一个非零元素，我们用三元组的形式来表示 $(i, j, value)$ ，然后存放在一维数组中。

由三元组表的不同表示方法可以引出稀疏矩阵不同的压缩存储方法：

2.4.1 三元组顺序表

将三元组以行序为第一关键字，列序为第二关键字来排序形成的表

压缩结构下的转置算法：为了保持顺序，除了对每个三元组的 $i, j$ 交换之外，还要改变一下顺序。

快速转置算法：核心思想是借助两个辅助向量，一步到位，把转置后的三元组直接放到相应位置上。

维护数组 $num, pos$ ，记 $num[i]$ 为第 $i$ 列非零元素的个数， $pos[i]$ 为第 $i$ 列的第一个非零元素在三元组顺序表中的位置。

易有：

$\begin{cases} pos[0]=&1 \\ pos[i]=&pos[i-1]+num[i-1], 2\leqslant i\leqslant n \end{cases}$

由于原顺序表是以行序为主序的，（以下认为遍历时，已经交换好了坐标）遍历时，列坐标是递增的。所以每次遍历到一个横坐标为 $i$ 的三元组，将其放在 $pos[i]$ 的位置上，然后 $pos[i]++$ 即可。

时间复杂度为 $O(m+n)$

2.4.2 十字链表

虽然矩阵的数据元素的个数是固定的，但是非零元素的个数是不固定的。矩阵的非零元个数和位置操作过程中变化比较大时（如矩阵加法），就不适合再用顺序结构来存储。此时，应该用链式结构来存储。

核心思想就是将三元组扩充为五元组：

struct Node{
  int i, j, val;
  Node* right; //同一行中下一个非零元节点的指针
  Node* down; //同一列中下一个非零元节点的指针
};

3、广义表

广义表是线性表的推广和扩充。

原来的线性表中的所有元素具有相同的数据类型，且只能是原子项（结构上不可分）。如果容许元素有自身结构，就形成了广义表。

广义表（列表）：是由 $n$ 个元素组成的有穷序列 $LS=(a_1, a_2, ..., a_n)$ ，其中 $a_i$ 可以是原子项或广义表。若 $a_i$ 是广义表，则称其为 $LS$ 的子表。

广义表是一个多层次的结构（层次性）
广义表可以是本身的子表（递归性）
广义表可以被其他广义表共享（共享性）

广义表的表头：非空广义表的第一个元素

广义表的表尾：除表头元素外的其余元素构成的表（记得外面都要再加一层括号）

第六章树和二叉树

前面介绍的都是线性的结构，这一章开始要介绍非线性数据结构。树形结构就是一类非常重要的非线性结构。

1、基本概念

树形结构以分支关系定义的层次结构

树是 $n(n\geqslant0)$ 个节点的有限集，如果 $n=0$ ，则称之为空树；否则：

有且只有一个特殊的称为树的根的节点
$n>1$ 时，根节点之外的节点被分为 $m(m>0)$ 个互不相交的子集 $T_1, T_2, ..., T_m$ ，其中每个集合本身又是一棵树，称为根的子树

显然可以看出，树是递归定义的。且树是一对多的关系，反映了节点之间的层次关系。

树的其他表示形式：嵌套集合形式；广义表形式；凹入表示法（用线的长短来表示）

节点拥有的子树数称为节点的度

树的度是树中节点度的最大值

度不为 0 的节点是分支节点；度为 0 的节点是叶子节点

某节点的子树的根称为该节点的孩子（子节点），该节点称为孩子的双亲（父节点）

同一个双亲的孩子之间互称为兄弟（节点）

树中节点的最大层次为树的深度或高度。只有一个节点的树的高度为 0。

树中节点的各子树不能交换次序，则称该树为有序树；否则为无序树

森林是 $m(m\geqslant0)$ 棵互不相交的树的集合

2、树的存储设计

2.1、双亲表示法

对每个节点编号，用数组存储下每个节点的双亲是什么。

优点：实现简单；查找双亲的时间复杂度 $O(1)$

缺点：查找兄弟或者孩子时是 $O(n)$ ；要预先分配空间，空间使用不灵活。

2.2、孩子表示法

同样对每个节点编号，用链表存储下每个节点的孩子（用链表是因为孩子的数量不定，若用数组，给每个节点分配相同的空间用于存储孩子，则会造成空间的浪费）

2.3、孩子兄弟表示法

对每个节点，有两个指针，一个指向第一个孩子，另一个指向第一个兄弟。

3、二叉树

二叉树是另一种树形结构，特点是每个节点至多只有两颗子树。但二叉树不是树，具体的说，不能简单的认为二叉树就是度不大于 2 的树。

这是因为二叉树的子树有着严格的左右次序，不能任意交换，且把空节点也看做子树。而在树的定义中，这些都是没有的。

满二叉树：高度为 $K$ 且有 $2^K-1$ 个节点的二叉树

完全二叉树：树的高度为 $K$ ，且所有的叶子节点都只出现在第 $K$ 层或第 $K-1$ 层，且第 $K$ 层的叶子都是集中在该层的左边

二叉树的性质：

若二叉树的层次从 1 开始，则二叉树第 $i$ 层最多有 $2^{i-1}$ 个节点
高度为 $K$ 的二叉树最多有 $2^K-1$ 个节点
对于任意一颗二叉树，如果其叶子节点的个数为 $n_0$ ，度为 2 的非叶节点的个数为 $n_2$ ，则有 $n_0=n_2+1$
有 $n$ 个节点的完全二叉树的高度为 $\log_2n+1$
将一颗有 $n$ $n$ 个节点的完全二叉树，自顶向下，从左到右给节点依次编号为 $1, 2, ..., n$ $1, 2, ..., n$ ，可以存到一维数组中，则：
- 节点 $i$ 的双亲为节点 $\lfloor \frac i 2\rfloor$ ，0 表示没有双亲
- 节点 $i$ 的左右孩子是节点 $2*i, 2*i+1$ ，超出范围则说明原节点是叶子节点，没有孩子
- 节点 $i$ ，若 $i$ 为奇数，则其有左兄弟 $i-1$ ；若 $i$ 为偶数，则有右兄弟 $i+1$ 。超出范围说明没有兄弟。

4、二叉树的存储设计

4.1、连续设计存储

就是上面提到的，只用于完全二叉树，用数组实现

4.2、链接设计存储

分为二叉链表和三叉链表。其中二叉链表即有两个分别指向左孩子和右孩子的指针，三叉链表在二叉链表的基础上还有一个指向双亲的指针。

5、二叉树的遍历

遍历二叉树就是按一定规则将二叉树的节点排列在一个线性序列上

按照子树和根的访问顺序分为前、中、后序遍历，这里前中后的意思是什么时候访问根节点。

前序遍历：先访问根节点，然后左子树，最后右子树
中序遍历：先访问左子树，然后根节点，最后右子树
前序遍历：先访问左子树，然后右子树，最后根节点

三种遍历的递归实现是很简单的，不再赘述

假设根节点均非空

前序遍历的非递归实现，利用栈实现：

一开始，根节点压栈
当栈非空的时候，弹栈，如果该节点不是空节点，遍历该节点，该节点的右孩子入栈，该节点的左孩子入栈。重复第二步。
栈空时，结束

vector<int>  preorder(Node* root)
{
    vector<int> res;
    stack<Node*> st;

    st.push(root);
    while(!st.empty())
    {
        Node* tem=st.top();
        st.pop();

        if(tem!=nullptr)
        {
            res.push_back(tem->val);
            st.push(tem->right);
            st.push(tem->left);
        }
    }

    return res;
}

中序遍历的非递归实现，利用栈加上一个辅助指针实现：

一开始，指针指向根节点
若指针指向的不是空节点，该节点入栈，指针指向该节点的左孩子。回到第二步
若指针指向的是空节点，指针回退指向栈顶元素，遍历当前指向节点，弹栈，指针指向该节点的右孩子。回到第二步
栈空，结束

vector<int>  inorder(Node* root)
{
    vector<int> res;
    stack<Node*> st;
    Node* p=root;

    while(p!=nullptr || !st.empty())
    {
        if(p!=nullptr)
        {
            st.push(p);
            p=p->left;
        }
        else
        {
            p=st.top();
            st.pop();
            res.push_back(p->val);
            p=p->right;
        }
    }

    return res;
}

后序遍历的非递归实现，利用两个栈和一个辅助指针实现。栈 1 保存节点，栈 2 表示栈 1 的栈顶节点能否被遍历：

一开始，指针指向根节点
若指针指向的不是空节点，该节点入栈 1，状态 0 入栈 2，指针指向该节点左孩子。回到第二步。
若指针指向的是空节点，指针回退指向栈 1 栈顶元素，同时访问栈 2 栈顶对应的状态值。如果是 0，则指针指向该元素的右孩子，栈 2 栈顶修改为 1；如果是 1，则遍历该元素，弹栈，指针置空。
栈空，结束

vector<int>  postorder(Node* root)
{
    vector<int> res;
    stack<Node*> st1;
    stack<Node*> st2;
    Node* p=root;

    while(p!=nullptr || !st.empty())
    {
        if(p!=nullptr)
        {
            st1.push_back(p);
            st1.push_back(0);
            p=p->left;
        }
        else
        {
            p=st1.top();
            if(st2.top()==0)
            {
                p=st1.right;
                st2.pop();
                st2.push(1);
            }
            else
            {
                res.push_back(p->val);
                st1.pop();
                st2.pop();
                p=nullptr;
            }
        }
    }

    return res;
}

后序遍历的另一种非递归方法是，稍加修改前序序列的算法，按“根右左”的顺序遍历，最后对结果反向，就得到“左右根”的后序序列了。

层序遍历用队列实现，很简单

6、二叉树遍历的运用

6.1、建树

给出某二叉树先序遍历（空节点也包括在序列中），用链式结构建立这颗二叉树，并返回这颗二叉树的根节点。用递归的方法做。

若序列中值为非空值，新建一个节点，将该非空值放进去，递归建立该节点的左子树，右子树
若序列中值为空值，置空指针，返回

6.2、求二叉树的叶子节点数

用任意一种遍历方式，在遇到左右孩子均为空的节点时，计数加一即可

6.3、求二叉树的高度

利用公式

$H(root)=max(H(root->left), H(root->eight))+1$

递归地求二叉树高度

要先知道左子树和右子树的高度，所以只能用后序遍历

6.4、由前序序列和中序序列唯一地确定二叉树

前序序列的第一个节点就是根节点。

然后在中序序列中找到根节点，根节点左边就是左子树的中序序列，右边就是右子树的中序序列。

得知了左子树和右子树的遍历序列长度，在前序序列中，可以依次得到左子树的前序序列和右子树的前序序列。

这样子树的前序和中序序列都确定了，可以递归地求解。

7、线索树

7.1、基本概念

遍历二叉树将二叉树的节点排成了线性序列，每个节点也就有了直接前驱和直接后继。

一颗二叉树有 $n$ 个节点，有 $n-1$ 条边，但是有 $2n$ 个指针域，所以有 $n+1$ 个指针域是空闲的，我们就用这些指针域来存放直接前驱和直接后继。

规定：

若该节点有左孩子，左指针指向左孩子；否则，指向直接前驱
若该节点有右孩子，有指针指向右孩子，否则，指向直接后继

自然，要加上两个标志变量，表示目前指针指向的是谁。标志变量为 1，表示指向的是前驱或后继；标志变量为 0，表示指向的是孩子。

用这种结构的节点构成的二叉树的存储结构叫做线索链表；指向前驱或者后继的指针叫做线索；按照某种次序遍历下加上了相应线索的二叉树称为线索二叉树。

线索化二叉树就是按照某种遍历次序，将二叉树转化为线索二叉树的过程。

线索二叉树中，不一定每一个节点都有空闲的指针域来存储线索，可能所有指针域都被正常的左右孩子占用了

7.2、线索化二叉树

实际上就是往原二叉树节点的空闲指针域放入指向前驱或者后继的指针。用一个辅助指针记录上一个访问的节点，然后在遍历过程中修改即可。

要注意，不仅要考虑当前节点的左指针域能不能放前驱，还要考虑上一个访问的节点右指针域能不能放后继。

7.2、中序线索二叉树上查找

在中序线索二叉树上，要查找某一个节点的前驱：

ltag=1，左指针域是线索，可以直接取到前驱
ltag=0，左指针域是左孩子，不可以直接取前驱。此时，该节点左子树的最右下的节点就是前驱。左子树最右下的节点肯定没有右孩子了，也就是说右指针域放的一定是线索，也就是说 rtag=1。所以只需要从当前节点的左孩子开始，一直往右边访问，直到访问到 rtag=1 的节点，就找到了前驱。

要查找某一个节点的后继：

rtag=1，右指针域是线索，可以直接取到后继
rtag=0，右指针域是右孩子，不可以直接取后继。此时，该节点右子树的最左下的节点就是后继。右子树最左下的节点肯定没有左孩子了，也就是说左指针域放的一定是线索，也就是说 ltag=1。所以只需要从当前节点的右孩子开始，一直往左边访问，直到访问到 ltag=1 的节点，就找到了后继。

8、树和森林

8.1、树和二叉树之间的转化

树转化为二叉树

每一棵树都可以方便地转化为一颗唯一的二叉树。步骤如下：

兄弟节点之间用线相连
双亲节点除了与左边第一个孩子的连线之外，与其他孩子节点的连线都去掉
稍加旋转变形，变成二叉树的模样

由于我们只保留了左边第一个孩子的连线，实际上这样得到的二叉树是没有右子树的

二叉树转化为树

对转化后得到的二叉树，将其还原成原来的树，步骤如下：

如果某节点是其父节点的左孩子，则从该节点的右孩子开始，每次都继续访问右孩子，将所有访问到的节点都与父节点连线。
如果某节点是其父节点的右孩子，则去掉该节点与父节点之间的连线（第一步中连的线不算）。
整理变形

8.3、森林和二叉树之间的转化

森林转化为二叉树

设 $F=\{T_1, T_2, ..., T_n\}$ 是森林，按以下步骤转化为树：

首先将所有的树都转化为二叉树
刚才已经说到，这样子转化出的二叉树没有右子树。为方便理解和叙述，从最后一棵树开始。首先将 $T_n$ 作为右子树拼到 $T_{n-1}$ 上。再将拼接后的 $T_{n-1}$ 作为右子树，拼到 $T_{n-2}$ 上，以此类推，直到最后拼成一整颗二叉树。

二叉树转化为森林

就是反过来操作。把二叉树的右子树摘出去，剩下的部分就是森林的第一棵树；然后将这个右子树的右子树摘下来，剩下的部分就是森林的第二棵树，以此类推，直到没有右子树可摘，说明到了最后一棵树。

8.5、树和森林的遍历

树的遍历：

先根遍历：先访问根节点，然后依次先根遍历所有子树（与把树转化为二叉树后，再先序遍历相同）
后根遍历：先依次后根遍历完所有子树，再访问根（与把树转化为二叉树后，再中序遍历相同）

之前说的先“序”遍历，都是针对二叉树而言的。所谓的“序”是指左子树、右子树、根这三者的顺序。树可能有不止一棵子树，所以不再用“序”来描述，而用“根”在遍历中的顺序来描述。

森林的遍历：

先序遍历：依次先根遍历森林中的所有树
中序遍历：依次后根遍历森林中的所有树

森林是有多棵树的，可以转化为二叉树。这里用转化为二叉树后的遍历结果来命名。

9、哈夫曼树

9.1、哈夫曼树的概念与构造

给树的每个节点赋一个权值，记某节点的路径长度为根节点到该节点要经过的节点数（不包括根节点，但是包括目标节点），记树的带权路径长度（WPL）为树中所有叶子节点的权值乘以路径长度的和

哈夫曼树：具有 n 个叶子节点的二叉树中，WPL 最小的一颗

哈夫曼树的构造（贪心）：

一开始，手上有 n 个孤立的节点，权值就是 n 个叶子节点的权值。将其看作是有 n 棵树的森林
从森林中取出两颗根节点权值最小的树，作为左右子树，与一个新的根节点构成一棵树。这个新的根节点的权值是原来两棵树的根节点的权值之和。
将新树放回森林，重复二、三步
森林中只剩下一颗二叉树时，这就是构造出的哈夫曼树

由构造过程可以发现：

哈夫曼树中的节点，要么没有孩子，要么有两个孩子
权值越大的节点离根越近，权值越小的树离根越远
哈夫曼树的形态不是唯一的

9.2、哈夫曼树的应用

在数据传输中，首先要对文字用二进制数编码，然后组成 01 字符串发送出去。这个字符串越短，需要的发送时间越短，越不容易因为收到干扰而出错。

使用等长编码方式（每一个字符用相同位数的二进制数编码）编码时，容易发现，一些使用频次很低的字符会占用较多的空间。

我们加以改进，对不同使用频次的字符，用不同位数的二进制数编码，这就是变长编码方式。

在这其中，

首先要考虑到每个字符的编码长度不同了可能引起歧义。

编码的前缀性：如果一组编码中，任意一个编码都不是其他任何一个编码的前缀，则称这种编码有前缀性，或者将这种编码称作前缀码。显然前缀码是不会有歧义的。

等长编码天然是有前缀性的，变长编码不一定有前缀性。
另一个问题是，根据不同的字符频次，如何才能选出最优的编码，使得平均编码长度最小。

这就用到了哈夫曼树，将频次作为叶子节点的权值，编码长度认为是路径长度。由于哈夫曼树的 WPL 是最小的，所以平均编码长度也是最小的。

以 n 个字符的出现频次，作为 n 个叶子节点的权值，构造出哈夫曼树。父节点到左孩子的边是 0，到右孩子的边是 1。

则从根节点走到某叶子节点即可得出该叶子节点对应的字符的编码。

解码的时候也是这样子从根节点，碰到 0 走左边，碰到 1 走右边，直到走到叶子节点，这就解出了一个字符。然后再从根节点重新开始。

10、二叉查找树（BST 树）

二叉查找树是一棵空树或者是具有以下性质的二叉树：

每个节点都有一个关键字，所有的关键字互不相同
左子树上所有节点的关键字都小于根节点的
右子树上所有节点的关键字都大于根节点的

中序遍历二叉查找树，可以得到一个按照关键字递增的有序序列

二叉查找树上查找某节点，与二分查找的思想类似，比较简单，不赘述
二叉查找树上插入新节点
- 空树，直接把新节点作为根节点
- 非空树，与查找时类似，找到第一个合适的空节点直接塞进去就可以
二叉查找树上删除某节点（假设该节点确实存在）
- 如果该节点是叶子节点，直接删除就可以
- 如果该节点只有左子树或者只有右子树，直接拿子树顶上来就可以
- 如果该节点同时有左子树和右子树，为了保证二叉查找树的结构，可以让该节点左子树的最大节点或者右子树的最小节点顶上来。
  
  以后者为例，也就是以该节点为起点做中序遍历，遍历到的第一个节点就是右子树的最小节点。然后删除这个最小节点（由于是中序遍历，这个最小节点一定是没有左子树的，这就退化到了前两种情况），再把原节点替换成最小节点。

11、AVL 树

名字来源于两位发明者的名字（lol）

二叉查找树的查找效率会受到树形态的影响，当树明显偏向某个方向时，时间复杂度会退化到 $O(n)$ 。

AVL 树是一种高度平衡的二叉查找树。AVL 树的每个节点附加一个数字，称之为平衡因子，表示该节点左右子树的高度之差的绝对值。AVL 树上所有节点的平衡因子不超过 1.

11.1、AVL 树上的插入操作

在 AVL 树上寻找插入节点位置的过程与在 BST 树上类似，将新节点作为叶子节点，从根节点向下查找到一个合适的位置，然后插入进去。但是，插入新节点可能会导致树不再平衡，这时候要对树进行平衡化旋转，使树重新保持平衡。

旋转操作一共有四种情况（以下图中的根节点是从新插入的节点沿来时路径回溯到的第一个平衡因子大于 1 的节点）

左单旋转

left-single-rotate

当回溯路径是’\'的形状时，做左单旋转。想象捏着节点 C 拎起来

Node* L_Rotate(Node* root)
{
    Node* tem=root->right;
    root->right=tem->left;
    tem->left=root;

    return tem;
}

当然，节点 A 不一定是整棵树的根节点，还要修改其双亲的指针。

右单旋转

right-sigle-rotate

当回溯路径是’/'的形状时，要进行右单旋转，与左单旋转是类似的

先左后右旋转

left-right-rotate

当回溯路径是’<'的形状时，先进行一次左单旋转，再进行一次右单旋转

先右后左旋转

right-left-rotate

当回溯路径是’>'的形状时，先右单旋转，再左单旋转

实现的时候，我们不定义平衡因子，而定义高度。且令叶子节点的高度为 1，从底往上依次递增。这样也可以在 $O(1)$ 内直接算出平衡因子。

插入时，也采用递归的写法。这样可以自然的回到第一个不平衡的节点，而不用再用多余的指针指向上一个节点或者存储路径。

旋转或者插入函数的返回值是新的根节点，这样又可以方便地完成父节点与子节点关系的调整

11.2、AVL 树上的删除操作

AVL 树本身也是二叉查找树，前置流程与 BST 树上的操作一样。同样要注意删除后的可能导致失衡。

实际上，如果删除右子树上的某个节点导致失衡，与在左子树上添加一个节点导致失衡是一样的。同理，如果删除左子树上的某个节点导致失衡，与在右子树上添加一个节点导致失衡是一样的。

所以可以直接借用添加节点时的处理办法。

在删除节点时，如果该节点既有左子树，也有右子树，则我们选择在高度较高的子树上挑选最大（或最小）的节点来替换，这样删除后，就不会出现失衡，简化操作。

12、B 树

也写作 B-树，B 是 Balance 的意思

大型数据库中，所有数据和索引都存储在外存，内外存数据的交换次数和交换快慢成为限制查找效率的瓶颈。为了提高效率，必须要尽量减少内外存数据的交换次数。

如果以二叉树的节点作为内外存数据交换单位，则平均要进行 $\log_2n$ 次访问，这对于大型数据库而言，效率仍然太低了，是不可容忍的。

B 树是一种多路平衡查找树，是多叉树。

m 阶 B 树是一颗 m 路查找树，它或者是空树，或者是满足下列性质的树：

树中每个节点最多有 $m$ 棵子树（就有 $m-1$ 个关键字）
若根节点不是终端节点，则至少要有两棵子树
除根节点之外的所有非终端节点至少要有 $\displaystyle\lceil \frac m 2 \rceil$ 棵子树
所有的非终端节点包含以下数据：关键字个数 $k$ ，关键字向量 $K_i$ （ $i=1, 2, \dots , n$ ，且 $K_1<K_2<\dots<K_n$ ），子节点指针向量 $A_i$ （ $i=0, 1, \dots, n$ 。满足 $A_i$ 指向的子树中的关键字均小于 $K_{i+1}$ ，大于 $K_i$ ），信息指针向量（ $k$ 个指针，每个关键字与这里的一个指针对应，指针指向与这个关键字相关联的信息）
所有的叶子节点都位于同一层，而且不带信息（可以看作查找到最后，到达的那个空节点）

B 树中，终端节点就是通常意义上的叶子节点，终端节点在叶子节点的上一层。

在 B 树中查找失败最终就会到叶子节点，所以叶子节点也称为失败节点。

B-tree

12.1、B 树上的查找

在 B 树上查找，每次从硬盘中读入一个节点的内容到内存中。

提高 B 树的阶数 m 虽然可以减少树的高度，从而减少读入节点的次数，但是不能无限地提升阶数。这是因为内存的大小是有限的，m 越大，一个节点占用的空间也就越大。如果内存不能一次写入一个节点的内容，反而会使效率降低，问题更复杂。

在 B 树上查找某关键字 $b$ ，从根节点开始，查找每个节点的关键字表（可以二分）

具体而言，假设某节点的 k 个关键字是 $a_1, a_2, a_3, ..., a_k$ ，且 $a_1<a_2<a_3<...<a_k$ 。

如果恰好有 $b=a_i$ ，则直接从关键字关联指针表里面，就可以找到关键字 $b$ 关联的指针；

否则，一定会存在 $a_i<b<a_{i+1}$ （记 $a_0=0, a_{k+1}=\infin$ ），则读入第 i 个子节点，往下继续查找。

m 阶 B 树的高度 h 满足 $\displaystyle \log_m(n+1)\leqslant h\leqslant \log_{\lceil \frac m 2 \rceil}(\frac {n+1} 2)+1$

访问硬盘的复杂度为 $O(\log_mn)$

在 B 树上查找的时间复杂度为 $h*\log_2m$ ，或者写成 $O(\log_2m*\log_mn)$

12.2、B 树上的插入

插入新节点也就是插入新关键字以及关联的指针和子树指针等，下面用关键字代表所有要插入的东西。

与二叉查找树类似，也是先按照查找节点的思路，拿着新关键字往下找，然后插入到某个非叶子节点中。

如果插入后，该节点的关键字个数超过了 m-1，则要进行分裂。

具体而言，如果插入新关键字后，关键字向量变成 $a_1, a_2, ..., a_m$ ，则从中间分裂成关键字向量为 $a_1, a_2, ..., a_{\lceil \frac m 2 \rceil-1}$ 和 $a_{\lceil \frac m 2 \rceil}, a_{\lceil \frac m 2 \rceil+1}, ..., a_m$ 的两个节点。并要向父节点插入新关键字 $a_{\lceil \frac m 2 \rceil}$ 以及相应指针。

如果父节点的关键字数量超过 m-1，要继续分裂，一直向上。这是一个递归的过程。

12.3、B 树上的删除

假设要删除的关键字确实存在

这个关键字所在的节点是终端节点
- 如果这个节点中的关键字个数大于 ${\lceil \frac m 2 \rceil}-1$ ，直接删除即可
- 如果小于，删除这个关键字之后，这个节点中的关键字个数就不够了。要从有富余关键字的兄弟节点中上浮一个关键字到父节点，然后父节点下移一个关键字到本节点。

delete-node

这个关键字所在的节点不是终端节点

从关键字的左子树或者右子树里选一个上来代替，然后删除那个节点。思想与 AVL 树类似

13、B+树

B+树是 B 树的变体，主要不同是信息全部放在叶子节点中（而不像 B 树中的叶子节点是没有信息的）

m 阶 B+树是空树或者满足下列性质的树：

树中每个非叶节点至多有 m 棵子树
根节点至少有两颗子树
除根节点和叶子节点以外的节点至少有 $\lceil \frac m 2 \rceil$ 棵子树
所有叶子节点在同一层上，包含了所有关键字以及指向数据的指针，且叶子节点本身按照关键字从小到大顺序链接

可见 B 树与 B+树的主要区别就在最后一点上。

B+tree

其他操作与 B 树都是类似的，不再赘述。

第七章图

1、基本概念

线性表中数据元素之间仅有线性关系；树形结构中，数据元素之间有着明显的层次关系；图形结构中，节点之间的关系是任意的，任意两个数据元素之间都可能相关。

所以图是一种较线性表和树更为复杂的非线性结构

图中的数据元素通常称为顶点，顶点与顶点之间的连线称为边。

有向边记为 $\langle u, v\rangle$ ，其中 $u$ 称为弧尾（箭头尾巴所在的顶点）， $v$ 称为弧头（箭头指向的顶点）

无向边记为 $(u, v)$ ，与 $(v, u)$ 等价

图 $G$ 是由顶点的有穷非空集合 $V$ 和顶点之间的边的集合 $E$ 组成的数据结构，记为 $G=(V, E)$ 。

如果图中所有的边都是无向边，则这个图是无向图；否则是有向图

本章中均不考虑自环和重边

对于有 $n$ 个顶点的无向图，如果它有 $\displaystyle\frac 1 2n(n-1)$ 条边，则称其为完全图；对于有 $n$ 个顶点的有向图，如果它有 $n(n-1)$ 条边，则称其为有向完全图

有时图的边有与它相关的树，称之为权，可以代表两个顶点之间的花费或者距离等，带权图通常称之为网

如果有图 $G=(V, E), G'=(V', E')$ ，如果 $V'\subseteq V, E'\subseteq E$ ，则 $G'$ 称为 $G$ 的子图

无向图 $G=(V, E)$ 中，如果 $(v, v')\in E$ ，则 $v, v'$ 互称为邻接点，边 $(v, v')$ 与顶点 $v, v'$ 相关联

顶点的度是与顶点相关联的边的数目。

有向图中，以该顶点为弧头的边的数目称为该顶点的入度，以该顶点为弧尾的边的数目称为该顶点的出度。所以有向图中某顶点的度等于该顶点的出度和入度之和。

显然所有顶点的度的和是边数的两倍

无向图 $G=(V, E)$ 中从顶点 $v$ 到顶点 $v'$ 的路径是一个顶点序列 $v=v_1, v_2, ..., v_n=v'$ ，且 $(v_i, v_{i+1})\in E$ ；有向图中路径的定义也是类似的

路径的长度就是路径上边的数目

若 $v=v'$ ，则这个路径也称为环或回路

若序列中没有重复的顶点，则该路径为简单路径；除第一个顶点和最后一个顶点外，序列中没有其他重复的顶点了，则该路径称为简单回路或者简单环

无向图 $G=(V, E)$ 中，如果顶点 $v$ 和顶点 $v'$ 之间有路径，则称 $v, v'$ 是连通的。如果 $\forall v_i, v_j\in V$ ， $v_i, v_j$ 是连通的，则称 $G$ 是连通图

无向图中的极大连通子图称之为连通分量或连通块

（极大是指，包含尽可能多的边和顶点，以至于再多加一个顶点或一条边，这个子图就不连通了。极大子图是可以有多个的，可以联想数学中的极大值）

有向图 $G=(V, E)$ 中，如果顶点 $v$ 和顶点 $v'$ 之间有路径，顶点 $v'$ 和顶点 $v$ 之间也有路径，则称 $v, v'$ 是强连通的。

如果 $\forall v_i, v_j\in V$ ， $v_i, v_j$ 是强连通的，则称 $G$ 是强连通图

有向图中的极大强连通子图称之为强连通分量或强连通块

一个连通图的生成树是一个极小连通子图，包含图中的所有 $n$ 个顶点，但是只有 $n-1$ 条边

一个有向图恰有一个顶点的入度为 0，其余顶点的入度为 1，则其是一棵有向树

2、图的存储

2.1、邻接矩阵

对于一个有 $n$ 个顶点的图，创建一个 $n\times n$ 的矩阵 $A$

$A[i][j]$ 的值表示顶点 $i$ 和顶点 $j$ 之间的关系。

2.2、邻接表

适用于有向图和无向图

（无向边可以看成互逆的两条有向边）

邻接表中，对每一个顶点建立一个单链表，第 $i$ 个单链表中的结点表示依附于顶点 $i$ 的边，我们将这种结点称之为边结点（因为存储的是一条“边”的信息，虽然实际上只存储了一个“点”的信息（后面会提到））

边结点包括与顶点 $i$ 邻接的点在图中的位置（或者说邻接点的标号），以及一个指向下一个与顶点 $i$ 邻接的边（边结点）（可见实际上只存储了一个点的标号，但是这个边结点在哪个单链表，这条边的另一个顶点就是这个单链表对应的顶点）

我们还要对每一个单链表加上一个头节点，这个节点对应称之为顶点节点，第 $i$ 个单链表的头结点存储了顶点 $i$ 的标号，以及指向第一个结点的指针。

头节点通常以顺序结构的方式存储，这样可以随机访问任一顶点对应的链表。

假设有一条有向边 $\langle u, v\rangle$

（正）邻接表：在结点 $u$ 对应的单链表中存储 $v$

逆邻接表：在结点 $v$ 对应的单链表中存储 $u$

2.3、十字链表

适用于有向图

有向图的十字链表法可以看作是正邻接表和逆邻接表的结合（也可以联想一下稀疏矩阵的十字链表法）

这种方法中边结点存储的是真正的边了，包括两个数据域，即弧头和弧尾所在结点的标号；以及两个指针域，分别指向下一条弧头相同的边和下一条弧尾相同的边。

顶点结点除了存储本节点的标号，也有两个指针域，分别指向第一个以该结点为弧头和弧尾的边。

适用于有向图的原因：

对于有向图，如果采用邻接表存储，则只能比较方便的知道节点的出度，而对于入度，只有遍历了整个图才知道。

采用十字链表存储后，就可以同时比较方便的知道出度和入度了

2.4、邻接多重表

无向图的邻接多重表法可以看成邻接矩阵的压缩表示（稀疏矩阵的十字链表表示法）

和十字链表法很类似

适用于无向图的原因：

对于无向图，如果采用邻接表存储，同一条边实际上是对应到两个单链表中的两个节点，十分麻烦。

采用邻接多重表存储，一条边只对应一个结点，这样对边的操作会简单很多。

2.5、边表

采用顺序结构存储每一条边，每一个单元包括这一条边弧头和弧尾的标号以及权值

3、图的遍历

从图的某一顶点出发遍访图中的其余顶点，且使每个顶点仅仅被访问一次，就叫做图的遍历

图结构中，任何两个顶点之间都可能存在边，顶点之间是没有确定的先后的次序的，所以遍历的顺序不唯一

一般设置一个辅助数组 $visit$ ，来防止一个结点被多次访问

遍历图的两种方法：深度优先搜索（DFS）和广度优先搜索（BFS）

假设 $G=(V, E)$ 是无向连通图。从 $G$ 中任意点出发遍历时，边集 $E$ 被分为两个互不相交的集合 $T, B$ 。其中 $T$ 表示整个遍历过程中已经经过的边的集合， $B$ 表示整个遍历过程中未经过的边的集合。

显然有 $E=T\cup B, T\cap B=\emptyset$ ，而且图 $G'=(V, T)$ 是 G 的极小连通子图，且 $G'$ 是一棵树，称之为 $G$ 的一棵生成树。

用 DFS 方法遍历得到的生成树称为深度优先生成树；用 BFS 方法遍历得到的生成树称为广度优先生成树

若是非连通图，则可以得到多个连通分量的顶点集和相应边集，相应得到优先生成森林

若给定了存储情况，则能得到的遍历序列和生成树应该是唯一的。

假设一个图有 $n$ 个顶点， $e$ 条边

遍历邻接表存储的图，时间复杂度是 $O(n+e)$

遍历邻接表存储的图，时间复杂度是 $O(n^2)$

4、图的连通性问题

4.1、关节点与重连通图

对于无向图而言

如果是连通图，则从任一顶点出发，就能访问图中的所有顶点；

如果是非连通图，需要从多个顶点出发。每次从一个未被访问过的顶点出发所访问到的顶点序列就是该图中一个连通分量的顶点集。

在一个无向连通图 $G$ 中，当且仅当删去 $G$ 中某个顶点 $v$ 以及其关联的所有边后，可将图分割为两个或两个以上的连通分量，则把 $v$ 称为关节点

没有关节点的连通图，称为重连通图。也就是说任何一对顶点之间有至少两条路径，删去某个顶点及其关联的边之后，并不会破坏整个图的连通性。

4.2、求无向连通图的关节点

对一个无向连通图，选取任一一个顶点开始进行深度优先搜索，得到一颗深度优先生成树。

图中除去生成树中也有的边后，剩下的边称为回边

若某个顶点 $u$ 是关节点的充要条件是：

$u$ 是深度优先生成树的根，且 $u$ 至少有两个子女（删除 $u$ 的话，各子树就脱离下来构成新的连通分量）
$u$ 不是深度优先生成树的根，但 $u$ 至少有一个子女 $w$ ，且从 $w$ 出发，只经过 $w$ 、 $w$ 的子孙、一条回边组成的路径，不能到达 $u$ 的祖先（删除 $u$ 的话，以 $w$ 为根的子树就脱离下来称为新的连通分量）（如果能到达，就是说有另一条路径可以回去，并不会与图的其他部分断开）

4.3、求有向图的强连通分量

从有向图的某个顶点 $v$ 出发，能到达的顶点集合记为 $V_1$ ；能到达 $v$ 的所有顶点的集合记为 $V_2$ 。则该有向图中包含 $v$ 的强连通分量的顶点集 $V=V_1\cap V_2$

按照上面的想法，可以得出以下求有向图 $G$ 强连通分量的步骤：

对 $G$ 进行深度优先遍历，生成 $G$ 的深度优先生成森林 $T$
对 $T$ 进行中序遍历，并按遍历顺序给顶点编号
将 $G$ 中所有的边反向，得到一个新的图 $G'$
按照刚才的编号，从最大的开始，进行深度优先搜索，得到的一颗生成树中的顶点就是 $G$ 的一个强连通分量的顶点；如果没有遍历完所有的顶点，就从剩下的顶点里面，选一个编号最大的顶点，继续遍历，直到所有的顶点都被遍历完。

5、最小生成树

设有一个无相连通带权图 $G=(V, E)$

$G$ 的生成树上各边的权值之和称为该生成树的代价。 $G$ 的所有生成树中，代价最小的称之为最小生成树

由最小生成树的定义，我们可以得出以下构造准则：

尽可能用权值最小的边
只需要 $n-1$ 条边
不能有环（有环说明有一条边多余，可以去掉）

构造最小生成树一般有两种算法

5.1、Kruskal 算法

设有一个无相连通带权图 $G=(V, E)$ 有 $n$ 个顶点

用这 $n$ 个顶点，构造出一个没有边的图 $T=(V, \emptyset)$ ，则图中每一个顶点自成一个连通分量
在 $E$ 中选出一条权值最小的边，如果这条边对应的两个顶点在两个不同的连通分量中，把这条边加入 $T$ 中；否则舍去这条边，重新选一条权值最小的边，直到所有顶点都在一个连通分量上

用并查集的思想可以比较简单的实现

时间复杂度是 $O(e\log e+n)$

5.2、Prim 算法

设有一个无相连通带权图 $G=(V, E)$ 有 $n$ 个顶点

定义生成树的顶点集 $U$ ，边集 $T$ ，一开始 $U$ 为空，随意的选择一个顶点 $u$ 放到 $U$ 中
选择满足 $(u, v)\in E, u\in U, v\in V$ 的边中，权值最小的那条，然后把 $v$ 加入 $U$ ， $(u, v)$ 加入 $T$ 中。依次类推，直到把所有的顶点都加入 $U$ 中

用优先队列优化后的时间复杂度是 $O(n\log e)$

6、有向无环图及其应用

6.1、AOV 网络以及拓扑排序

有向无环图 $(DAG)$ 是没有环的有向图

一个工程可以分为若干个称为活动的子工程（工序），某个子工程必须等另一些子工程完成之后，才能开始。

如果用顶点表示活动，用有向边 $\langle u, v\rangle$ 表示活动 $u$ 必须先于 $v$ 进行。这样构成的有向图叫做AOV 网络(Activity On Vertices)

我们实际遇到的问题是：是否按照某种顺序，在满足 AOV 网络给出的限制的情况下，完成整个工程

抽象出来就是：能否将各个顶点排列成一个线性有序的序列，使得所有的弧尾结点都在弧头结点的前面。我们把这个序列称之为拓扑序列

构造 AOV 网络全部顶点的拓扑序列的方法就叫做拓扑排序：

选出一个入度为 0 的顶点
删去该顶点以及从该顶点出发的所有边，将该顶点放到序列中
重复第 1、2 步直到所有顶点都放到了序列中，此时得到的序列就是一个拓扑有序序列；如果还剩下一些顶点放不进去，说明这些顶点入度都不为 0，则一定构成了环，不存在拓扑序列。

利用一个数组来记录顶点的入度，栈来保存入度为 0 的顶点，时间复杂度可以优化到 $O(n+e)$

6.2、AOE 网络以及关键路径

在带权有向无环图中，用有向边表示一个工程的活动，用边的权值活动的持续时间，用顶点表示事件。则这样的有向图叫做用边表示活动的网络，简称AOE 网络（ $Activity\ On\ Edges$ ）

我们称 AOE 网络中，入度为 0 的点叫做源点，出度为 0 的点叫做汇点。

完成整个工程所需要的时间就是从源点到汇点的最长的路径长度。这条路径叫做关键路径。（注意某个事件要开始，则之前所有的事件都要完成才行）

定义某事件 $v_i$ 的最早可能开始时间 $ve[i]$ （在这个时间之前，该事件不可能开始做），则有：

$ve[j]=\begin{cases} 0, &v_j\text{是源点}\\ \max\{ve[i]+dur(\langle i, j\rangle)\},&\forall\langle i, j\rangle\in E \end{cases}$

定义某事件 $v_i$ 的可容许的最迟开始时间 $vl[i]$ （在这个时间之后再开始，就会延误后面的事件），则有：

$vl[j]=\begin{cases} ve[j],&v_j\text{是汇点}\\ \min\{vl[k]-dur(\langle j, k\rangle)\},&\forall\langle j, k\rangle\in E \end{cases}$

按照定义，易知前者可以按照拓扑排序的顺序求，后者可以按照逆拓扑排序的顺序求。

设活动 $a_{i,j}$ 就是边 $\langle i, j\rangle$ 表示的活动

定义活动 $a_{i, j}$ 的最早开始时间 $e[\langle i, j\rangle]=ve[i]$

定义活动 $a_{i, j}$ 的可容许的最迟开始时间 $l[\langle i, j\rangle]=vl[j]-dur(\langle i, j\rangle)$

时间余量定义为 $l[i]-e[i]$ ，理论上，活动在 $e[i]$ ~ $l[i]$ 时间段内开始都可以

时间余量为 0 的活动，我们称之为关键活动。关键活动没有余量，必须在那个时间点开始。只有使关键活动的持续时间缩短，才能使整个活动提前完成。

所有关键活动（也可以看成边）一起，就构成了关键路径。当然关键路径可以有多条。

只有加快同时在所有关键路径上的关键活动才能缩短整个活动的时间。

6.3、最短路径问题

即寻找一条从某一顶点到另一顶点的最短的路径。

6.3.1、Dijkstra 算法

适用于权值非负的单源最短路问题

具体算法如下：

从起点 $v_0$ 开始，记 $dis[i]$ 为 $v_0$ 到 $v_i$ 的最短路径长度，已经找到最短路径的顶点集为 $S$ ，尚未确定最短路径的顶点集为 $T$ 。初始化 $dis[0]=0,dis[i]=\infin,i>0$ ， $v_0\in S$
从 $T$ 中选一个 $dis$ 最小的顶点 $v_i$ 且未被访问过的，对 $v_i$ 的所有出边进行松弛操作，即令 $dis[j]=\min\{dis[i]+weight[\langle i, j\rangle]\}$ ，其中 $\langle i, j\rangle \in E$
将 $v_j$ 放入 $S$ 中
重复第 2、3 步直至 $T$ 为空

时间复杂度为 $O(n^2)$ ，利用优先队列可以优化到 $O(n\log n)$

6.3.2、Floyd 算法

适用于求任意两点之间的最短路问题

具体算法如下：

定义 $dis[i][j]$ 表示顶点 $i, j$ 之间最短路径的长度。初始化，令：

$dis[i][j]=\left\{ \begin{align} 0,\ &i=j\\ weight[i][j],\ &\langle i, j\rangle\in E\\ \infin,\ &\langle i, j\rangle\not\in E\\ \end{align} \right.$
做 $n$ 次循环，每 $k$ 轮循环对所有顶点对之间考虑中间顶点全在集合 $\{v_1, v_2, \dots, v_k\}$ 中的最短路径，也即 $dis[i][j]=\min\{dis[i][j], dis[i][k]+dis[k][j]\}$

代码实现即是一个三重循环：

for(int k=0; k<n; k++)
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            dis[i][j]=min(dis[i][j], dis[i][k]+dis[k][j]);

时间复杂度为 $O(n^3)$ 。用 Dijkstra 算法求任意两点之间的最短路，只需用 $n$ 次即可，时间复杂度也是 $O(n^3)$

第八章查找

8.1、基本概念

之前研究的数据结构中，数据元素之间或者有前驱后继的关系，或者有父节点子节点的约束。本章研究的“集合”中的数据元素之间是完全松散的关系，没有什么约束。

查找表就是由同一类型的数据元素（或记录）构成的集合

查找就是在查找表中寻找特定的数据元素

关键字是数据元素中的某个数据项的值，它可以标识一个数据元素。如果该关键字可以唯一标识某一个数据元素，则该关键字是称为主关键字；否则称为次关键字。

所以查找也可以定义为，给定一个值，在查找表中确定一个其关键字等于给定值的数据元素。

查找表是一个松散的集合，为了便于查找，我们通常会对查找表中的数据元素之间人为地加上一些关系，以便能够按照某种规则进行查找。也即用另一种数据结构来表示查找表。

查找表可以分为静态查找表和动态查找表，后者可以进行删改。

衡量一个查找算法时间效率的标准是，确定某数据元素在查找表中的位置时，所需的关键字比较次数的期望，也称为查找成功时的平均查找长度（ASL）。

查找成功时的平均查找长度为：

$ASL_{success}=\displaystyle \sum\limits^n_{i=1}p_ic_i$

其中 $p_i$ 是要查找查找表中第 $i$ 个元素的概率， $c_i$ 是成功查找到元素 $i$ 所需的比较次数。（注意，此处假设要查找的记录都在查找表中，也即 $\displaystyle \sum p_i=1$ ，也即查找总是成功的。注意与查找失败的平均查找长度）

8.2、顺序查找

适用于以顺序表或者线性链表表示的静态查找表。就是一个一个比过去。

$\displaystyle ASL_{success}=\frac{n+1}{2}$

查找时间复杂度为 $O(n)$ ，插入删除的时间复杂度为 $O(1)$

8.3、折半查找（二分）

适用于以有序表表示的静态查找表，也即按照关键字升序或者降序排列的顺序表。

计算平均查找长度的时候可以构建一个二叉查找树， $mid$ 对应的值就是根节点，如果要向左半段查找，就相当于前往左子树；向右半段查找同理。要比较的次数即为节点在二叉树上的深度。

$ASL_{success}=\displaystyle \frac{n+1}{n}\log_2(n+1)-1\approx \log_2(n+1)-1$

查找时间复杂度 $O(\log n)$ ，插入删除的时间复杂度是 $O(n)$ （为了保持有序）

8.4、分块查找

适用于以索引顺序表表示的静态查找表

将原查找表分成若干个子表，第 $i+1$ 个子表上的所有关键字都大于（或者小于）第 $i$ 个子表上的关键字，我们称其为分块有序。

对每个子表建立一个索引项，包括该子表中最大关键字以及指向该子表第一个记录的指针。所有的索引项构成一个索引表，且按照关键字有序。

假设共 $n$ 记录，每个块中有 $s$ 个元素，则一共分成了 $b=\displaystyle \lceil \frac n s \rceil$ 块

$ASL_{success}=\displaystyle \frac{b+1}{2}+\frac{s+1}{2}=\frac 1 2(\frac n s+s)+1$ ，显然当 $s=\sqrt n$ 时，取得最小值（这就是莫队算法分块时的依据）

8.5、斐波那契查找

适用于以有序表表示的静态查找表。

是二分查找的一种改进、具体而言用上下界和中间点改用斐波那契数列的值。

设 $F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)$

假设查找表的有 $n$ 个关键字，且 $F(j-1)<n\leqslant F(j)$

令 $left=1, right=F(j),mid=F(j-1)$ ，接下来的过程类似二分

8.6、树形查找

适用于以树形结构表示的动态查找表

例如之前笔记中的二叉查找树以及平衡二叉查找树

平均插入、删除、查找的时间复杂度均为 $O(\log n)$

还有 B 树，B+树等

8.7、哈希表

之前讨论的各种用于表示查找表的结构中，记录在结构中的相对位置都是随机的，记录的存储位置与关键字之间并没有什么确定的关系。因此，在这些结构上的查找方法都是基于比较的，用决策树可以证明查找的时间复杂度的下界是 $O(\log n)$ 。

要想要得到更快的查找方法，就要“不比较”。则需要建立一个记录的关键字 $k$ 和记录的存储位置 $f(k)$ 之间的映射 $f:k\rightarrow f(k)$ 。关键字在这种映射关系下的像就是相应记录的存储位置。

这样只要知道了关键字，就能知道对应记录的存储位置，就不再需要比较了。这个映射或者说函数就被称为哈希函数。按这个思想建立起来的表就是哈希表。

为了避免两个不同的关键字，映射到同一个存储位置上，也即哈希冲突。我们需要选择一个合适的哈希函数，同时在发生哈希冲突时，也要有解决办法。

8.7.1、选择一个好的哈希函数

为了减少冲突，我们会希望不同的关键字通过哈希函数映射出的哈希地址是均匀分布的。如果对于关键字集合中任意一个关键字，经过哈希函数映射到地址集合中任何一个地址的概率是相等的，则称此类哈希函数是均匀的哈希函数。

常用的确定哈希函数的方法有：

直接定址法：直接取关键字或者关键字的某个线性函数值作为哈希地址。这样的哈希函数下，关键字集合与地址集合大小相同，不同的关键字不会产生冲突。
数字分析法：假设关键字是数字，分析关键字分布，直接挑选关键字的某些分布随机的位经过处理后作为哈希地址。
平方取中法：将关键字平方后，取中间几位作为哈希地址。
折叠法：将关键字分成均匀几段后，相加，作为哈希地址。一般关键字分布均匀的时候效果比较好。
除留余数法：将关键字模某个数的结果作为哈希地址。一般选用不超过哈希表长的质数，或者不含有 20 以内质因子的合数。

8.7.2、解决哈希冲突

冲突发生的时候，我们需要另找一个空的地方来存放

开放定址法

基本思想就是冲突发生的时候，按照某个探测序列去查找有空的地方：

假如此时关键字为 $key$ ，发现 $Hash(key)$ 这个位置已经被用了，接下来依此找 $H_i=(Hash(key)+d_i \mod m), i=1, 2, \dots$

其中 $d_i$ 就是探测序列的项， $m$ 是哈希表长

探测序列具体有以下三种：
- 线性探测序列： $d_i=1, 2, 3, \dots$
- 二次探测序列： $d_i=1^2,-1^2,2^2,-2^2,3^2,\dots$
伪随机探测序列： $d_i$ 是一系列随机数

其中线性探测序列保证只要哈希表未满，一定可以找到一个不冲突的地址。但是它只是简单的把新记录放在冲突位置的紧邻的不冲突的位置，这样相当于将记录”聚集“分布，而不是均匀分布，增加了哈希冲突的可能。这种现象称为二次聚集。

二次探测序列则不易产生“二次聚集”现象，可以发现其探测的位置是均匀跳跃式地向两侧分布的。但是它不一定能探测到所有的位置。（不一定是平方剩余）

伪随机探测序列理论上有可能永远也找不到不冲突的位置。所以一般都会设置一个探测次数上限，超过这个次数还没找到，就用线性探测。
再哈希法

利用一组哈希函数，如果 $Hash_1(key)$ 被使用过了，就计算 $Hash_2(key)$ ，依此类推

这种方法不易产生聚集现象，但是计算时间会增加
链地址法

将映射到同一个哈希地址的记录用一个链表存储起来，形成类似邻接表的形式。
公共溢出区

冲突的记录统一放到一个公共的溢出区

8.7.3、利用哈希表查找、删除、修改

根据关键字算出哈希地址
如果哈希地址对应的存储单元是空的，则查找失败
如果哈希地址对应的存储单元非空，查看该记录的关键字是否等于原关键字，如果是，就说明找到了，然后进行相应操作；否则，说明存储该关键字对应的记录时发生了冲突，按照设定好的解决冲突的办法计算下一个可能位置，知道找到了对应的记录或者查找失败。

如果要删除哈希表中某个记录，由于处理哈希冲突时，会依赖冲突位置的记录。所以不能简单的直接删去此处的记录，要用“有效位”标记。

8.7.4、哈希表的效率分析

由于冲突的存在，最终仍然需要通过比较来确定查找结果。我们仍然用平均查找长度来衡量效率。

哈希表越满，越容易产生冲突，需要的比较次数越多，查找效率越低。

定义哈希表的装填因子 $\alpha=\displaystyle\frac{\text{表中填入的记录数}}{\text{哈希表的长度}}$

	$ASL_{success}$	$ASL_{unsuccess}$
线性探测序列	$\displaystyle \frac 1 2\left(1+\frac {1}{1-\alpha}\right)$	$\displaystyle \frac 1 2\left(1+\frac {1}{(1-\alpha)^2}\right)$
链地址	$1+\displaystyle \frac \alpha 2$	$\alpha+e^{-\alpha}$
随机探测序列、二次探测序列、再哈希	$-\displaystyle \frac 1 \alpha \ln(1-\alpha)$	$\displaystyle \frac{1}{1-\alpha}$

第十章排序

10.1、基本概念

排序就是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列（从而便于查找等）

假设含 $n$ 个记录的序列是 $\{R_1, R_2,\dots,R_n\}$ ，其对应的关键字序列是 $\{K_1, K_1, \dots, K_n\}$ 。排序就是找到一个 $1, 2, \dots, n$ 的序列 $p_1, p_2, \dots, p_n$ ，使得 $K_{p_1}\leqslant K_{p_2}\leqslant \dots \leqslant K_{p_n}$

由主关键字的定义，如果按照主关键字排序，则排序后的结果是唯一的；否则不唯一。

假如按次关键字排序，有 $K_i=K_j, i<j$ 。在排序后的序列中， $R_i$ 仍然在 $R_j$ 的前面，则称这种排序方法是稳定的；如果排序后， $R_i$ 可能在 $R_j$ 的后面，则称这种排序方法是不稳定的。

如果记录数量过多，以至于在内存中无法存放下所有的记录，在排序过程中必须访问外存，则称这种排序为外部排序；如果排序完全在内存中完成，则称为内部排序，接下来只讨论内部排序。

排序方法的敏感性是指原序列的有序程度对排序所需时间的影响程度。

排序方法大致可以分为五种：

插入排序
交换排序
选择排序
归并排序
基数排序

10.2、插入排序

10.2.1、直接插入排序

即将记录逐个有序插入。

平均时间复杂度为 $O(n^2)$ ，这是稳定的排序方法。

10.2.2、希尔排序

对整个序列的一些子序列分别进行直接插入排序，然后逐渐缩小子序列的长度，重复若干趟，使得整个序列“基本有序”，最后再对全体记录进行一次直接插入排序。

核心思想是利用直接插入排序在 $n$ 较小或者原序列有序度高的时候效率比较高，从而实现优化。

这若干趟中的子序列的长度称之为增量序列 ${d_1, d_2, \dots, d_n}$ ，其中 $d_n=1$ ，对应着最后对整个序列进行直接插入排序

第 $i$ 趟，就是分别对子序列 $\{R_1, R_{d_i+1}, R_{2d_i+1}, \dots\}$ ， $\{R_2, R_{d_i+2}, R_{2d_i+2}, \dots\}$ ， $\dots$ ， $\{R_d, R_{2d},R_{3d},\dots\}$ 等，进行直接插入排序

增量序列的选取就决定了希尔排序的效率，但是现在还没有研究出最好的取法。但是通过大量实验数据可以得出， $n$ 很大的时候，平均时间复杂度大概在 $n^{1.25}$ 到 $1.6n^{1.25}$ 的量级左右。这是不稳定的排序方法。

10.3、交换排序

10.3.1、冒泡排序

非常简单，不赘述。

其平均时间复杂度为 $O(n^2)$ 。这是稳定的排序方法。

10.3.2、快速排序

基本思想是，一趟排序将序列分为两个部分，其中一部分的关键字都比另一个部分的关键字小。中间那个分割点就称为枢轴。之后再递归地对两个部分同样进行快速排序，直到需要快排的序列只有一个元素，则其显然是有序的，整个排序过程结束。

其平均时间复杂度为 $O(n\log n)$ 。如果枢轴选第一个元素，在原序列有序度高时的情况下会退化到 $O(n^2)$ ，由于是递归的，还容易爆栈。这是不稳定的排序方法。

为了防止退化，可以调整取枢轴的方法，取序列的第一个，中间，最后一个这三个记录关键字大小居中的那个作为枢轴。这样可以改善在最坏情况下的性能。

10.4、选择排序

10.4.1、简单选择排序

进行 $n-1$ 趟，第 $i$ 趟，从第 $i+1$ 个到第 $n$ 个中选出最小的（或最大的），然后与第 $i$ 位的元素交换。

其平均时间复杂度为 $O(n^2)$ 。这是不稳定的排序方法。

10.4.2、堆排序

一个关键字序列 $k_1<k_2<\dots<k_n$ ，且满足 $k_i<k_{2i},k_i<k_{2i+1}$ ，则该序列就称为堆（将定义中所有的小于号换成大于号也成立）

很容易可以与二叉树联系起来，如果按照标号从上到下，从左到右建立起一棵二叉树，会发现堆满足任意一棵子树的根节点总是该子树的最大（或者最小）的元素，分别称为大顶堆和小顶堆。

以大顶堆为例，如果每次调整都能保证大顶堆的结构，则序列的第一个元素始终是目前堆中最大的元素。我们每次取出第一个元素，然后依次排好，就得到了一个有序的序列，这就是堆排序。

为了实现堆排序，首先要能调整原来无序的序列变成堆，然后在输出堆顶元素后，要能调整剩余的元素，维持堆的结构。

以用大根堆排序为例

建堆：

一开始的序列不一定是堆，要进行调整。当成一棵二叉树来考虑，为了把最大的元素放到顶上，要从底部开始，依次往上考虑
从 $k_{\lfloor \frac n 2\rfloor}$ 考虑一直到 $k_1$ 。考虑 $k_i$ 时，从 $k_i, k_{2i}, k_{2i+1}$ 中选出最大的，然后与 $k_i$ 交换；递归地往下，直到替换完成（可能需要连续调整）。从二叉树的角度看，就是从根节点和两个子节点中挑出最小的，与根节点交换。

输出堆顶后，调整：

先将堆顶元素与最后一个元素交换（序列中即是交换第一个和最后一个元素）
对序列的前 $i-1$ 个元素调整，使其重新变为堆

其最坏情况下的时间复杂度也为 $O(n\log n)$ 。这是不稳定的排序方法。堆排序的另一个优点是仅需要一个用于交换的辅助空间，占用的空间较小。

10.5、归并排序

将原表分为两个表，对两个表进行归并排序后，都变成有序的，最后再合并起来，整个表排序完成。这是一个递归的过程。

最坏、平均时间复杂度是 $O(n\log n)$ 。是一种稳定的排序方法。一个缺点是需要的辅助内存较多，需要另一个与原数组大小相同的辅助数组。一般不用于内部排序。

10.6、基数排序

如果关键字是数字，每个关键字最多有 $d$ 位，每一位有 $r$ 种取值（关键字是 $r$ 进制的）。

基数排序的第 $i$ 趟：

分配：有 $r$ 个桶（链表）。从右到左一个一个看关键字序列，如果某关键字的第 $i$ 位是 $k$ ，就插入到第 $k$ 个链表的尾部
收集：从左往右看每一个链表，从每一个链表的尾部开始依次取下关键字，排成一列

第一章 绪论

1、基本概念与术语

2、算法

第二章 线性表

1、线性表的定义

2、顺序表示

3、链式表示

第三章 栈和队列

1、栈

2、表达式处理

3、递归

4、队列

第四章 串

1、串的概念

2、串的存储

3、串的模式匹配算法

3.1、朴素模式匹配算法

3.2、KMP 算法

3.3、NextNextNext数组的计算

3.4、KMP 算法的改进

第五章 数组和广义表

1、数组

2、矩阵的压缩存储

2.1、对称矩阵

2.2、三角矩阵

2.3、对角矩阵

2.4、稀疏矩阵

2.4.1 三元组顺序表

2.4.2 十字链表

3、广义表

第六章 树和二叉树

1、基本概念

2、树的存储设计

2.1、双亲表示法

2.2、孩子表示法

2.3、孩子兄弟表示法

3、二叉树

4、二叉树的存储设计

4.1、连续设计存储

4.2、链接设计存储

5、二叉树的遍历

6、二叉树遍历的运用

6.1、建树

6.2、求二叉树的叶子节点数

6.3、求二叉树的高度

6.4、由前序序列和中序序列唯一地确定二叉树

7、线索树

7.1、基本概念

7.2、线索化二叉树

7.2、中序线索二叉树上查找

8、树和森林

8.1、树和二叉树之间的转化

8.3、森林和二叉树之间的转化

8.5、树和森林的遍历

9、哈夫曼树

9.1、哈夫曼树的概念与构造

9.2、哈夫曼树的应用

10、二叉查找树（BST 树）

11、AVL 树

11.1、AVL 树上的插入操作

11.2、AVL 树上的删除操作

12、B 树

12.1、B 树上的查找

12.2、B 树上的插入

12.3、B 树上的删除

13、B+树

第七章 图

1、基本概念

2、图的存储

2.1、邻接矩阵

2.2、邻接表

2.3、十字链表

2.4、邻接多重表

2.5、边表

3、图的遍历

4、图的连通性问题

4.1、关节点与重连通图

4.2、求无向连通图的关节点

4.3、求有向图的强连通分量

5、最小生成树

第一章绪论

第二章线性表

第三章栈和队列

第四章串

3.3、 $Next$ 数组的计算

第五章数组和广义表

第六章树和二叉树

第七章图

第八章查找

第十章排序