《大话数据结构》学习笔记

最近开始学习数据结构，在图书馆借到了《大话数据结构》这本书，作者是程杰。

数据结构绪论

数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科。
**程序设计 = 数据结构 + 算法**

基本概念和术语

数据

数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。

数据元素

数据元素：是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。也被称作*记录*。

数据项

数据项：一个数据元素可以有若干个数据项组成。数据项是数据不可分割的最小单位。

数据对象

数据对象：是性质相同的数据元素的集合，是数据的子集。

数据结构

数据结构：是相互之间存在一种或者多种特定关系的数据元素的集合。
数据结构分为逻辑结构和物理结构。

逻辑结构

逻辑结构：是指数据对象中数据元素之间的相互关系。主要包括：
集合结构：集合结构中的数据元素除了同属于一个集合外，他们之间没有其他关系。
线性结构：线性结构中的数据元素之间是一对一的关系。
树形结构：树形结构中的数据元素之间存在一种一对多的层次关系。
图形结构：图形结构的数据元素是多对多的关系。

物理结构

物理结构：是指数据的逻辑结构在计算机中的存储形式。主要包括：
顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。
链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。

抽象数据类型

数据类型

数据类型：是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。

抽象数据类型

抽象数据类型(ADT)：是指一个数学模型及定义在该模型上的一组操作。抽象的意义在于数据类型的数学抽象特性。

算法

算法是解决特定问题求解步骤的描述，在计算机中体现为指令的有限序列，并且每条指令表示一个或多个操作。

算法的特性

输入输出

算法具有零个或多个输入；算法至少有一个输出。

有穷性

有穷性：指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。

确定性

确定性：算法的每一步骤都具有确定的含义，不会出现二义性。

可行性

可行性：算法的每一步都必须是可行的，也就是说，每一步都能通过执行有限次数完成。

算法设计的要求

正确性

正确性：算法的正确性指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。

可读性

可读性：算法设计的另一个目的是为了便于阅读、理解和交流。

健壮性

健壮性：当输入数据不合法时，算法也能做出相关处理，而不是产生异常或者莫名其妙的结果。

时间效率高和存储量低

设计算法应该尽量满足时间效率高和存储量低的需求。

算法效率的度量方法

事后统计方法

事后统计方法：这种方法主要是通过设计好的测试程序和数据，
             利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。

事前分析估算方法

事前分析估算方法：在计算机程序编制前，依据统计方法对算法进行估算。
                一个程序的运行时间，依赖于算法的好坏和问题的输入规模。

函数的渐进增长

函数的渐进增长：给定两个函数 f(n) 和 g(n) ，如果存在一个整数N，使得对于所有的 n>N ，
              f(n) 总是比 g(n) 大，那么我们说 f(n) 的增长渐进快于 g(n)。
判断一个算法的效率时，函数中的常数和其他次项要常常可以忽略，而更应该关注主项（最高阶项）的阶数。

算法时间复杂度

算法时间复杂度：在进行算法分析时，语句总的执行次数 T(n) 是关于问题规模 n 的函数，
              进而分析 T(n) 随 n 的变化情况并确定 T(n) 的数量级。算法的时间复杂度，也就是算法的时间量度，
              记作： T(n) = O(f(n))。它表示随问题规模 n 的增大，算法执行时间的增长率和 f(n) 的增长率相同，
              称作算法的渐进时间复杂度，简称为时间复杂度。其中 f(n) 是问题规模 n 的某个函数。

常见的时间复杂度

执行次数函数	阶	非正式术语
12	O(1)	常数阶
2n+3	O(n)	线性阶
3n^2+2n+1	O(n^2)	平方阶
5log2(n)+20	O(log(n))	对数阶
2n+3nlog2(n)+19	O(nlog(n))	nlog(n)阶
6n^3+2n^2+3n+4	O(n^3)	立方阶
2^n	O(2^n)	指数阶

常用的时间复杂度所耗费的时间从小到大依次是：
O(1) < O(log(n)) < O(n) < O(nlog(n)) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

最坏情况与平均情况

最坏情况运行时间是一种保证，那就是运行时间将不会再坏了。
在应用中，这是一种最重要的需求，通常，除非特别指定，我们提到的运行时间都是最坏情况的运行时间。
平均时间是所有情况中最有意义的，因为它是期望的运行时间。

算法空间复杂度

算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：
S(n) = O(f(n))，其中，n 为问题的规模，f(n) 为语句关于 n 所占存储空间的函数。

线性表

零个或多个数据元素的有限序列。

线性表的定义

零个或多个数据元素的有限序列。
线性表元素的个数 n(n >= 0)定义为线性表的长度，当 n = 0 时，称为空表。
在较复杂的线性表中，一个数据元素可以有若干个数据项组成。

线性表的抽象数据类型

ADT 线性表(List)
Data
    线性表的数据对象集合为 {a₁, a₂, ... ,a(n)}，每个元素的类型均为DataType。
    其中，除第一个元素 a₁ 外，每一个元素有且只有一个直接前驱元素，除了最后一个元素 a(n) 外，
    每一个元素有且仅有一个直接后继元素。数据元素之间的关系是一对一的关系。
Operation
    InitList(*L)：       初始化操作，建立一个空的线性表L。
    ListEmpty(L)：       若线性表为空，返回true，否则返回false。
    ClearList(*L)：      将线性表清空。
    GetElem(L,i,*e)：    将线性表L中的第i个位置元素返回给e。
    LocateElem(L,e)：    在线性表L中查找与给定值e相等的元素，如果查找成功，
                         返回该元素在表中序号表示成功；否则，返回0表示失败。
    ListInsert(*L,i,e)： 在线性表L的第i个位置插入新元素e。
    ListDelete(*L,i,*e)：删除线性表L中第i个位置元素，并用e返回其值。
    ListLenth(L)：       返回线性表L的元素个数
endADT

线性表的顺序存储结构

顺序存储定义

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

顺序存储方式

用一维数组来实现顺序存储结构。
描述顺序存储结构需要三个属性：存储空间的起始位置，线性表的最大存储容量，线性表的当前长度。

数组长度与线性表长度区别

在任意时刻，线性表的长度应该小于等于数组的长度。

地址计算方法

存储器中的每个存储单元都有自己的编号，这个编号称为地址。
线性表的起始为1，即：a1, a2, ...
数组的下标起始为0.

顺序存储结构的插入和删除

插入操作

思路：（时间复杂度 O(n)）
1. 如果插入位置不合理，抛出异常；
2. 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量；
3. 从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置；
4. 将要插入元素填入位置i处；
5. 表长加1.

删除操作

思路：（时间复杂度 O(n)）
1. 如果删除位置不合理，抛出异常；
2. 取出删除元素
3. 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置；
4. 表长减1.

线性表顺序存储结构的优缺点

优点：
- 无须为表示表中元素之间的逻辑关系而增加额外的存储空间；
- 可以快速地存取表中任一位置的元素。
缺点：
- 插入和删除操作需要移动大量元素；
- 当线性表长度变化较大时，难以确定存储空间的容量；
- 造成存储空间的“碎片”。

线性表的链式存储结构

线性表链式存储结构定义

为了表示每个数据元素 a(i) 与其直接后继数据元素 a(i+1) 之间的逻辑关系，对数据元素 a(i) 来说，
除了存储本身的信息外，还需存出一个指示其直接后继的信息（即直接后继的存储位置）。
指针域：把存储数据元素信息的域称为数据域，把存储直接后继的域称为指针域。
指针：指针域中存储的信息称作指针或链。
结点：这两部分信息组成数据元素 a(i) 的存储映像，称为结点（Node）。
头指针：把链表中的第一个结点的存储位置叫做头指针。
头结点：在单链表的第一个结点前附设一个结点，称为头结点。

头指针与头结点的异同

头指针：
- 头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针。
- 头指针具有标识作用，所以常用头指针冠以链表的名字。
- 无论链表是否为空，头指针均不为空。头指针式链表的必要条件。
头结点：
- 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据与一般无意义（也可存放链表的长度）。
- 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一了。
- 头结点不一定是链表必须要素

线性表链式存储结构代码描述

结点由存放数据元素的数据域（p->data）和存放后继结点地址的指针域（p->next）组成。

单链表的读取

核心思想：工作指针后移。获得链表第 i 个元素
1. 声明一个结点 p 指向链表第一个结点，初始化 j 从 1 开始；
2. 当 j<i 时，就遍历链表，让 p 的指针向后移动，不断指向下一个结点，j 累加 1；
3. 若到链表末尾 p 为空，则说明第 i 个元素不存在；
4. 否则查找成功，返回结点 p 的数据。

单链表的插入与删除

单链表的插入

单链表第 i 个数据插入结点的算法思路：（时间复杂度 O(n)）
1. 声明一个结点 p 指向链表第一个结点，初始化 j 从 1 开始；
2. 当 j<i 时，就遍历链表，让 p 的指针向后移动，不断指向下一个结点，j 累加 1；
3. 若到链表末尾 p 为空，则说明第 i 个元素不存在；
4. 否则查找成功，在系统中生成一个空结点 s；
5. 将数据元素 e 赋值给 s->data;
6. 单链表的插入标准语句 s->next = p->next;  p->next = s;
7. 返回成功。

单链表的删除

单链表第 i 个数据删除结点的算法思路：（时间复杂度 O(n)）
1. 声明一个结点 p 指向链表第一个结点，初始化 j 从 1 开始；
2. 当 j<i 时，就遍历链表，让 p 的指针向后移动，不断指向下一个结点，j 累加 1；
3. 若到链表末尾 p 为空，则说明第 i 个元素不存在；
4. 否则查找成功，将欲删除的结点 p->next 赋值给 q；
5. 单链表的删除标准语句 p->next = q->next;
6. 将 q 结点的数据赋值给 e，作为返回；
7. 释放 q 结点；
8. 返回成功。
**对于插入或删除数据越频繁的操作，单链表的效率优势就越是明显。**

单链表的整表创建

头插法：
1. 声明一结点 p 和计数器变量 i；
2. 初始化一空链表；
3. 让 L 的头结点的指针指向 NULL，即建立一个带头结点的空链表；
4. 循环：
    - 生成一新结点赋值给 p；
    - 随机生成一数字赋值给 p 的数据域 p->data;
    - 将 p 插入到头结点与前一新结点之间 p->next = (*L)->next, (*L)->next = p。
尾插法：
1. 声明两结点 p、r 和计数器变量 i；
2. 初始化一空链表；
3. r 为指向尾部的结点；
4. 循环：
    - 生成一新结点赋值给 p；
    - 随机生成一数字赋值给 p 的数据域 p->data;
    - 将 p 插入到尾结点之后 r->next = p。
    - 将当前的新结点定义为表尾终端结点 r = p。

单链表的整表删除

思路：
1. 声明一结点 p 和 q；
2. 将第一个结点赋值给 q；
3. 循环：
    - 将下一个结点赋值给 q；
    - 释放 p；
    - 将 q 赋值给 p。

单链表结构与顺序存储结构优缺点

存储分配方式

- 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素；
- 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素。

时间性能

- 查找
  - 顺序存储结构 O(1)；
  - 单链表 O(n)。
- 插入和删除
  - 顺序存储结构需要平均移动表长一半的元素，时间为 O(n)；
  - 单链表在找出某位置的指针后，插入和删除时间仅为 O(1)。

空间性能

- 顺序存储结构需要与分配存储空间，分大了，浪费，分小了易发生上溢；
- 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。

静态链表

用二维数组[data, cur]描述的链表叫做静态链表。

静态链表定义

对数组第一个和最后一个元素作为特殊元素处理，不存数据。通常把未被使用的数组元素成为备用链表。
数组第一个元素，即下标为 0 的元素的 cur 就存放备用链表的第一个结点的下标；
数组的最后一个元素的 cur 则存放第一个有数值的元素的下标，相当于单链表的头结点作用。
当整个链表为空时，则为 0^2。

静态链表的插入操作

静态链表插入

静态链表的删除操作

静态链表删除

静态链表优缺点

优点：
- 在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点。
缺点：
- 没有解决连续存储分配带来的表长难以确定的问题；
- 失去了顺序存储结构随机存取的特性。

循环链表

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，
这种头尾相接的单链表称为单循环链表，简称循环链表（circular linked list）。

双向链表

双向链表（double linked list）是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。

双向链表的插入

将结点 s 插入到结点 p 和 p->next 之间：
1. s->prior = p；
2. s->next = p->next；
3. p->next-prior = s；
4. p->next = s。

栈与队列

栈（stack）是限定仅在表尾进行查如何删除操作的线性表；
队列（queue）是只允许在一端进行插入操作、而在另一端进行删除操作的线性表。

栈的定义

栈的定义

栈（stack）是限定仅在表尾进行查如何删除操作的线性表。
栈顶（top）：允许插入和删除的一端（表尾）；
栈底（bottom）：不允许插入和删除的一端；
空栈：不含任何数据元素的栈；
栈又称为后进先出（Last In First Out）的线性表，简称 LIFO 结构。
进栈（push）：栈的插入操作，叫做进栈，也称压栈、入栈；
出栈（pop）：栈的删除操作，也叫弹栈。

栈的抽象数据类型

ADT 栈（stack）
Data
    同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。
Operation
    InitStack(*S)：初始化操作，建立一个空栈S。
    DestroyStack(*S)：若栈存在，则销毁它。
    ClearStack(*S)：将栈清空。
    StackEmpty(S)：若栈为空，返回 true，否则返回 false。
    GetTop(S,*e)：若栈存在且非空，用 e 返回 S 的栈顶元素。
    Push(*S,e)：若栈S存在，插入新元素 e 到栈 S 中并成为栈顶元素。
    Pop(*S,*e)：删除栈 S 中栈顶元素，并用 e 返回其值。
    StackLength(S)：返回栈 S 的元素个数。
endADT

栈的顺序存储结构及实现

栈的顺序存储结构

top = 1：栈有两个元素；
top = -1：栈空；
top = MAXSIZE-1：栈满。

栈的顺序存储结构——进栈操作push

栈的顺序存储结构-进栈操作

1. 栈顶指针加一：S->top++;
2. 将新元素赋值给栈顶空间：S->data[S->top]=e;
时间复杂度为 O(1)。

栈的顺序存储结构——出栈操作pop

1. 将要删除的栈顶元素赋值给 e ：*e=S->data[S->top];
2. 栈顶指针减一：S->top--;
时间复杂度为 O(1)。

两栈共享空间

两栈共享空间

用一个数组存储两个栈，数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，
即下标为 0 处；另一个栈的栈底为数组的末端，即小标为数组的长度 n-1 处。
top1 + 1 == top2 为栈满。

栈的链式存储结构及实现

把栈顶放在单链表的头部。

栈的链式存储结构——进栈操作

栈的链式存储结构-进栈操作

1. 创建一个空指针 s，并赋值 e：s->data = e;
2. 把当前栈顶元素赋值给新结点的直接后继：s->next = S->top;
3. 将新结点 s 赋值给栈顶指针：S->top = s;
4. 栈计数加1：S->count++;
时间复杂度为 O(1)。

栈的链式存储结构——出栈操作

栈的链式存储结构-出栈操作

1. 将栈顶元素值赋值给 e：*e = S->top->data;
2. 将栈顶结点赋值给 p：p = s->top;
3. 栈顶指针下移一位，指向后一结点：S->top = S->top->next;
4. 释放结点 p：free(p);
5. 栈计数减1：S->count--;
时间复杂度为 O(1)。

栈的作用

栈的引入简化了程序设计的问题，划分了不同关注层次，使得思考范围缩小。更加聚焦于我们要解决的问题核心。

栈的应用——递归

递归定义

例子：菲波那切数列（生兔子问题）。
把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称作递归函数。
每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出。
迭代和递归的区别：迭代使用的是循环结构，递归使用的是选择结构。

栈的应用——四则运算表达式求值

例子：逆波兰表示法
中缀表达式：9+(3-1)*3+10/2
后缀表达式：9 3 1 - 3 * + 10 2 / +
1. 将中缀表达式转化为后缀表达式（栈用来进出运算的符号）；
2. 将后缀表达式进行运算得出结果（栈用来进出运算的数字）。

队列的定义

队列的定义

队列(queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出（First In First Out）的线性表，简称 FIFO。
允许插入的一端称为队尾，允许删除的一端称为队头。

队列的抽象数据类型

ADT 队列（Queue）
Data
    同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。
Operation
    InitQueue(*Q)：初始化操作，建立一个空队列 Q。
    DestroyQueue(*Q)：若队列 Q 存在，则销毁它。
    ClearQueue(*Q)：将队列 Q 清空。
    QueueEmpty(Q)：若队列 Q 为空，返回 true，否则返回 false。
    GetHead(Q,*e)：若队列 Q 存在且非空，用 e 返回 Q 的队头元素。
    EnQueue(*Q,e)：若队列 Q 存在，插入新元素 e 到队列 Q 中并成为队尾元素。
    DEQueue(*Q,*e)：删除队列 Q 中队头元素，并用 e 返回其值。
    QueueLength(S)：返回队列 Q 的元素个数。
endADT

循环队列

队列顺序存储的不足

队列的顺序存储结构-入队

入队：在队尾追加一个元素，时间复杂度 O(1)。

队列的顺序存储结构-出队

出队：队列中所有元素向前移动一个位置，时间复杂度 O(n)。

front：指向队头元素；
rear：指向队尾元素的下一个位置。
空队列：当 front 等于 rear 时。

循环队列的定义

把队列的头尾相接的顺序存储结构称为循环队列。
循环队列满的条件：(rear+1) % QueueSize == front。
循环队列长度计算公式：(rear-front+Queuesize) % QueueSize。

循环队列入队：

1. 将元素 e 赋值给队尾：Q->data[Q->rear] = e;
2. rear 指针向后移动一位置，若到最后转到数组头部：Q->rear = (Q->rear+1)%MAXSIZE;
时间复杂度为 O(1)。

循环队列出队：

1. 将队头元素赋值给 e：*e = Q->data[Q->front];
2. front 指针向后移动一位置，若到最后转到数组头部：Q->front = (Q->front+1)%MAXSIZE;
时间复杂度为 O(1)。

队列的链式存储结构及其实现

队列的链式存储结构

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，简称为链队列。
队头指针指向链队列的头结点，队尾指针指向终端结点。
空队列：front 和 rear 都指向头结点。

队列的链式存储结构——入队操作

1. 新建队列结点 s：s->data = e; s->next = NULL;
2. 将新结点赋值给原队尾的后继：Q->rear->next = s;
3. 将当前的 s 结点设置为队尾结点：Q->rear = s;
时间复杂度为 O(1)。

队列的链式存储结构——出队操作

1. 将欲删除的队头结点暂存给 p：p = Q->front->next;
2. 将欲删除的队头结点赋值给 e：*e = p->data;
3. 将原队头结点后继赋值给头结点后继：Q->front->next = p->next；
4. 若队头是队尾，则删除后将 rear 指向头结点：if(Q->rear == p) Q->rear = Q->front；
5. 释放 p：free(p)。
时间复杂度为 O(1)。

串

串（string）是由零个或多个字符组成的有限序列，又名叫字符串。

串的定义

串（string）是由零个或多个字符组成的有限序列，又名叫字符串。
一般记为 s = "a₁a₂...a(n)" (n>=0)。
串中的字符数目 n 称为串的长度。
零个字符的串称为空串（null string）：""。
空格串：只包含空格的串，" "。

串的比较

计算机中的常用字符是使用标准的 ASCII 编码，更确切一点，有 7 位二进制数表示一个字符，共可表示 128 个字符。
后来发现一些特殊符号，扩展 ASCII 由 8 位二进制数表示一个字符，共可表示 256 个字符。
Unicode 编码由 16 位的二进制数表示一个字符，共可表示 2^16 个字符。Unicode 的前 256 个字符与 ASCII 码完全相同。
给定两个串：s = "a₁a₂...a(n)"，t = "b₁b₂...b(m)",当满足以下条件之一时，s < t。
1. n < m，且 a(i) = b(i) (i = 1,2,...,n)。
2. 存在某个 k ≤ min(m,n)，使得 a(i) = b(i) (i = 1,2,...,k-1)，a(k) < b(k)。

串的抽象数据类型

ADT 串（String）
Data
    串中元素仅有一个字符组成，相邻元素具有具有前驱和后继关系。
Operation
    StrAssign(T,*chars)：生成一个其值等于字符串常量 chars 的串 T。
    StrCopy(T,S)：串 S 存在，由串 S 复制得到串 T。
    ClearString(S)：串 S 存在，将串清空。
    StringEmpty(S)：若串 S 为空，返回 true，否则返回 false。
    StrLength(S)：返回串 S 的元素个数，即串的长度。
    StrCompare(S,T)：若 S > T，返回值 > 0;若 S = T，返回值 = 0;若 S < T，返回值 < 0;
    Concat(T,S1,S2)：用 T 返回由 S1 和 S2 联接而成的新串。
    SubString(Sub,S,pos,len)：串 S 存在，1 ≤ pos ≤ StrLength(S)，
                              且 0 ≤ len ≤ StrLength(S)-pos+1，用 Sub 返回
                              串 S 的第 pos 个字符串起长度为 len 的子串。
    Index(S,T,pos)：串 S 和 T 存在，T 是非空串，1 ≤ pos ≤ StrLength(S)，
                    若主串 S 中存在和串 T 值相同的子串，则返回它在主串 S 中
                    第 pos 个字符之后第一次出现的位置，否则返回 0。
    Replace(S,T,V)：串 S、T 和 V 存在，T 是非空串。用 V 替换主串 S 中出现的所有
                    与 T 相等的不重叠的子串。
    StrInsert(S,pos,T)：串 S 和 T 存在，1 ≤ pos ≤ StrLength(S)+1，
                        在串 S 的第 pos 个字符之前插入串 T。
    StrDelete(S,pos,len)：串 S 和 T 存在，1 ≤ pos ≤ StrLength(S)-len+1，
                        从串 S 中删除第 pos 个字符起长度为 len 的子串。
endADT

串的存储结构

串的顺序存储结构

串的顺序存储结构

串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。一般用定长数组来定义。

串的链式存储结构

串的链式存储结构

一个结点可以存放一个字符，也可以存放多个字符。

朴素的模式匹配算法

子串的定位操作通常称做串的模式匹配 。
简单地说，就是对主串的每一个字符串作为子串开头，与要匹配的字符串进行匹配。
对主串进行大循环，每个字符开头做 T 的长度的小循环，直到匹配成功或全部遍历完成为止。

KMP模式匹配算法

由来：D.E.Knuth、J.H.Morris和V.R.Pratt发表一个模式匹配算法，可以大大避免重复遍历的情况。
     我们称之为克努特-莫里斯-普拉特算法，简称 KMP 算法。
我们把子串 T 各个位置的 j 值得变化定义为一个数组 next，那么 next 的长度就是 T 串的长度。
我们可以根据经验得到如果前后缀一个字符相等，k 值是 2，两个字符 k 值是 3，n 个相等 k 值就是 n+1。

树

树的定义

树(Tree)是 n（n ≥ 0）个结点的有限集。n = 0 称为空树。
在任意一棵非空树中：
1. 有且仅有一个特定的称为根（Root）的结点；
2. 当 n > 1 时，其余结点可分为 m（m > 0）个互不相交的有限集 T₁、T₂、...、T(m)，
   其中每一个集合本身又是一棵树，并且称为根的子树。
强调两点：
1. n > 0 时，根结点是唯一的，不可能存在多个根结点。
2. m > 0 时，子树的个数没有限制，但它们一定是互不相交的。

结点分类

度（Degree）：结点拥有的子树称为结点的度。
叶结点（Leaf）：度为 0 的结点称为叶结点或终端结点;
分支结点：度不为 0 的结点称为非终端结点或分支结点。
内部结点：除根结点外，分支结点也称为内部结点。
树的度：是树内各结点的度的最大值。

结点间关系

孩子（Child）：结点的子树的根称为该结点的孩子；
双亲（Parent）：该结点称为孩子的双亲。
兄弟（Sibling）：同一个双亲的孩子之间互称兄弟。
结点的祖先：是从根到该结点所经历分支上的所有结点。
结点的子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。

树的其他相关概念

层次（Level）：结点的层次从根开始定义起，根称为第一层，根的孩子称为第二层。
堂兄弟：双亲在同一层的结点互为堂兄弟。
树的深度（Depth）：树中结点的最大层次称为树的深度或高度。
有序树：如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。
森林（Forest）：是 m（m ≥ 0）棵互不相交的树的集合。

线性表与树的不同

线性结构：
1. 第一个数据元素：无前驱；
2. 最后一个元素：无后继；
3. 中间元素：一个前驱一个后继。
树结构：
1. 根结点：无双亲，唯一
2. 叶结点：无孩子，可以多个；
3. 中间结点：一个双亲，多个孩子。

树的抽象数据类型

ADT 树（Tree）
Data
    树是由一个根结点和若干棵子树构成。树中结点具有相同数据类型和层次关系。
Operation
    InitTree(*T)：构造空树 T。
    DestroyTree(*T)：销毁树 T。
    CreateTree(*T,definition)：按 definition 中给出树的定义来构造树。
    ClearTree(*T)：若树 T 存在，将树 T 清为空树。
    TreeEmpty(T)：若 T 为空树，返回 true，否则返回 false。
    TreeDepth(T)：返回 T 的深度。
    Root(T)：返回 T 的根结点。
    Value(T,cur_e)：cur_e 是树 T 中一个结点，返回此结点的值。
    Assign(T,cur_e,value)：给树 T 的结点 cur_e 赋值为 value。
    Parent(T,cur_e)：若 cur_e 是树 T 的非根结点，则返回它的双亲，否则返回空。
    LeftChild(T,cur_e)：若 cur_e 是树 T 的非叶结点，则返回它的最左孩子，否则返回空。
    RightSibling(T,cur_e)：若 cur_e 有右兄弟，则返回它的右兄弟，否则返回空。
    InsertChild(*T,*p,i,c)：其中 p 指向树的某个结点，i 为所指向结点 p 的度加上1，
              非空树 c 与 T 不想交，操作结果为插入 c 为树 T 中 p 指结点的第 i 棵子树。
    DeleteChild(*T,*p,i)：其中 p 指向树的某个结点，i 为所指向结点 p 的度，操作结果为
                          删除 T 中 p 所指结点的第 i 棵子树。
endADT

树的存储结构

双亲表示法

以一组连续的空间存储树的节点，在每个结点中，附设一个指示器指示其双亲结点在数组中的位置。
data 表示数据域，存储结点的数据信息；
parent 是指针域，存储该结点的双亲在数组中的下标。
约定根结点的指针域设置为 -1。

树的双亲表示法

孩子表示法

每个结点有多个指针域，其中每个指针指向一棵子树的根结点，叫做多重链表表示法。
把每个结点的孩子结点排列起来，以单链表作存储结构，则 n 个结点有 n 个孩子链表，
如果是叶子结点则此单链表为空。然后 n 个头指针又组成一个线性表，采用顺序存储结构，
存放进一个一维数组中。

孩子兄弟表示法

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。
因此，我们设置两个指针，分别指向该结点的第一个孩子和此节点的右兄弟。

二叉树的定义

二叉树（Binary Tree）是 n（n ≥ 0）个结点的有限集合，该集合或者为空集（空二叉树），
或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

二叉树特点

- 每个结点最多有两个子树，所以二叉树中不存在度大于 2 的结点。
- 左子树和右子树是有顺序的，次序不能任意颠倒。
- 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。
二叉树具有五种基本形态：
1. 空二叉树。
2. 只有一个根结点。
3. 根结点只有左子树。
4. 根结点只有右子树。
5. 根结点既有左子树又有有字数。

特殊二叉树

1. 斜树
      - 左斜树：所有结点都只有左子树的二叉树；
      - 右斜树：所有结点都只有右子树的二叉树；
2. 满二叉树
      在一棵二叉树中，所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。
      - 叶子只能出现在最下一层。
      - 非叶子结点的度一定是 2。
      - 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。
3. 完全二叉树
      对一棵具有 n 个结点的二叉树按层序编号，如果编号为 i（1 ≤ i ≤ n）的结点
      与同样深度的满二叉树编号为 i 的结点在二叉树中位置完全相同，称为完全二叉树。
      - 叶子结点只能出现在最下两层。
      - 最下层的叶子一定集中在左部连续位置。
      - 倒数二层，若有叶子结点，一定都在右部连续位置。
      - 如果结点度为 1，则该结点只有左子树。
      - 同样结点数的二叉树，完全二叉树的深度最小。

二叉树的性质

1. 在二叉树的第 i 层上至多有 2^(i-1) 个结点（i ≥ 1）。
2. 深度为 k 的二叉树至多有 2^(k-1) 个结点（k ≥ 1）。
3. 对任何一棵二叉树 T，如果其终端结点数为 n(0)，度为 2 的结点数为 n₂，则n(0) = n₂+1。
4. 具有 n 个结点的完全二叉树的深度为 𠃊㏒₂n𠃎+1。
5. 如果对一颗有 n 个结点的完全二叉树的结点按层序编号，对任一结点 i （1 ≤ i ≤ n）有：
      - 如果 i = 1，则结点 i 是二叉树的根，无双亲；如果 i > 1，则双亲是结点 𠃊i/2𠃎。
      - 如果 2i > n，则结点 i 无左孩子（结点 i 为叶子结点）；否则其左孩子是结点 2i。
      - 如果 2i+1 > n，则结点 i 无右孩子；否则其右孩子是结点 2i+1。

二叉树的存储结构

二叉树顺序存储结构

用一维数组存储二叉树中的结点，并且结点的存储位置也就是数组的下标要能体现结点之间的逻辑关系。

二叉树顺序存储结构

二叉链表

二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域的链表，叫做二叉链表。

二叉链表

遍历二叉树

二叉树遍历原理

二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问
            二叉树的所有结点，使得每个结点被访问一次且只被访问一次。

二叉树遍历方法

1. 前序遍历：规则是若二叉树为空，则空操作返回，否则先访问根结点，
            然后前序遍历左子树，再前序遍历右子树。

二叉树前序遍历

2. 中序遍历：规则是若二叉树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），
            中序遍历根结点的左子树，然后访问根结点，最后中序遍历右子树。

二叉树中序遍历

3. 后序遍历：规则是若二叉树为空，则空操作返回，否则从左到右先叶子后结点的方式
            遍历访问左右子树，最后访问根结点。

二叉树后序遍历

4. 层序遍历：规则是若二叉树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，
            从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。

二叉树层序遍历

推导遍历结果

- 已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
- 已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
- *已知前序遍历序列和后序遍历序列，不能确定一棵二叉树。*

线索二叉树

指向前驱和后继的指针称为线索，加上线索的二链表称为二叉链表，相应的二叉树称为线索二叉树。
对二叉树以某种次序遍历使其变为线索二叉树的过程称作是线索化。
如果需要经常遍历或查找结点时，需要某种遍历的前驱或后继。宜采用线索二叉树。

线索二叉树

树、森林与二叉树的转换

树转化为二叉树

1. 加线。在所有兄弟结点之间加一条连线。
2. 去线。对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线。
3. 层次调整。以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。
            注意第一个孩子是二叉树结点的做孩子，兄弟结点转换过来的孩子是结点的右孩子。

树转化为二叉树

森林转换为二叉树

1. 把每个树转换为二叉树。
2. 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的
   根结点的右孩子，用线连接起来。当所有的二叉树连接起来后就得到了由森林转换来的二叉树。

森林转换为二叉树

二叉树转化为树

1. 加线。若某结点的左孩子结点存在，则将这个左孩子结点的右孩子结点、右孩子的右孩子结点、
        ...，即左孩子的 n 个右孩子结点都作为此结点的孩子，将该结点与这些右孩子结点连接起来。
2. 去线。删除原二叉树中所有结点与其右孩子结点的连线。
3. 层次调整。使之结构层次分明。

二叉树转化为树

二叉树转换为森林

1. 从根结点开时。若右孩子存在，则把与右孩子结点的连线删除，再查看分离后的二叉树，
   若右孩子存在，则连线删除...，直到所有右孩子连线都删除为止，得到分离的二叉树。
2. 再将每棵分离后的二叉树转换为树即可。

二叉树转换为森林

树与森林的遍历

树的遍历：
1. 先根遍历。先访问树的根结点，然后依次先根遍历根的每棵子树。
2. 后根遍历。先依次后根遍历每棵子树，然后再访问根结点。
森林的遍历：
1. 前序遍历。先访问森林中第一棵树的根结点，然后再依次先根遍历根的每棵子树，
            再依次用同样方式遍历除去第一棵树的剩余树构成的森林。
2. 后序遍历。先访问森林中的第一棵树，后根遍历的方式遍历每棵子树，然后再访问根结点，
            再依次用同样方式遍历除去第一棵树的剩余树构成的森林。

赫夫曼树及其应用

赫夫曼树定义与原理

路径长度：从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的
         分支数目称作路径长度。树的路径长度就是树根到每一个节点的路径长度之和。
赫夫曼树：带权路径长度 WPL 最小的二叉树称作赫夫曼树。
赫夫曼树的赫夫曼算法描述：
1. 根据给定的 n 个权值{w₁,w₂,...,w(n)}构成 n 棵二叉树的集合 F =  {T₁,T₂,...,T(n)}，
   其中每棵二叉树 T(i) 中只有一个带权为 w(i) 根结点，其左右子树均为空。
2. 在 F 中选取两棵树根结点的权值最小的树作为左右子树构造一棵新的二叉树，
   且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
3. 在 F 中删除这两棵树，同时将新得到的二叉树加入到 F 中。
4. 重复 2 和 3 步骤，直到 F 只含一棵树为止.这棵树便是赫夫曼树。

赫夫曼编码

一般地，设需要编码的字符集为 {d₁,d₂,...,d(n)}，各个字符在电文中出现的次数或频率
    集合为 {w₁,w₂,...,w(n)}，以 d₁,d₂,...,d(n) 作为叶子结点，以 w₁,w₂,...,w(n)
    作为相应叶子结点的权值来构造一棵赫夫曼树。规定赫夫曼树的左分支代表 0，右分支代
    表 1，则从根结点到叶子结点所经过的路径分支组成的 0 和 1 的序列便为该结点对应字
    符的编码，这就是赫夫曼编码。

图

图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，
   其中，G 表示一个图， V 是图 G 中顶点的集合，E 是图 G 中边的集合。

图的定义

- 顶点：在图中数据元素称为顶点。
- 在图结构中，不允许没有顶点。
- 图中任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边表示，边集可以是空的。

各种图定义

- 无向边：若顶点 v(i) 到 v(j) 之间的边没有方向，则称这条边为无向边，
         用无序偶对 (v(i),v(j)) 来表示。
- 有向边：若顶点 v(i) 到 v(j) 之间的边有方向，则称这条边为有向边，也称为弧（Arc）
         用有序偶对 <v(i),v(j)> 来表示。v(i) 叫弧尾（Tail），v(j) 叫弧头（Head）。
- 有向图：如果图中任意两个顶点之间的边都是有向边，则称该图为有向图（Directed graphs）。
- 简单图：在图中，若不存在顶点到其自身的边，且同一条边不重复出现，称为简单图。
- 无向完全图：在无向图中，如果任意两个顶点之间都存在边，称为无向完全图。
             含有 n 个结点的无向完全图有 n*(n-1)/2 条边。
- 有向完全图：如果如果任意两个顶点之间都存在方向互为相反的两条弧，称该图为有向完全图。
             含有 n 个结点的有向完全图有 n*(n-1) 条边。
- 稀疏图：有很少条边或弧的图称为稀疏图，反之称为稠密图。
- 权：与图的边或弧相关的数叫做权（Weight）。
- 网：带权的图统称为网（Network）。
- 子图：假设有两个图 G = (V,{E}) 和  G' = (V',{E'})，如果 V' ⊆ V，且 E' ⊆ E，
       则称 G' 为 G 的子图（Subgraph）。

图的顶点与边间关系

- 对于无向图 G = (V,{E})，如果边 (v,v') ∈ E，则称顶点 v 和 v' 互为邻接点（Adjacent），
   即 v 和 v' 相邻接。边 (v,v') 依附（incident）于顶点 v 和 v'，或者说 (v,v') 与
   顶点 v 和 v' 相关联。顶点 v 的度（Degree）是和 v 相关联的边的数目，记为 TD(v)。
   边数是各顶点度数和的一半。
- 对于有向图G = (V,{E})，如果弧 <v,v'> ∈ E，则称顶点 v 邻接到顶点 v'，顶点 v' 邻接自顶点 v。
   弧 <v,v'> 和顶点 v 和 v' 相关联。以顶点 v 为头的弧的数目称为 v 的入度（InDegree），记为 ID(v)；
   以 v 为尾的弧的数目称为 v 的出度（OutDegree），记为 OD(v)；顶点 v 的度为 TD(v) = ID(v) + OD(v)。
   弧数 = 各顶点入度之和 = 各顶点出度之和。
- 无向图 G = (V,{E}) 中从顶点 v 到顶点 v' 的路径（Path）是一个顶点序列 (v = v(i,0),v(i,1),...,v(i,m) = v' )，
   其中(v(i,j-1),v(i,j)) ∈ E， 1 ≤ j ≤ m。
- 路径的长度是路径上的边或弧的数目。
- 第一个顶点到最后一个顶点相同的路径称为回环（Cycle）。序列中顶点不重复出现的路径称为简单路径。
   除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路，称为简单回路或简单环。

连通图相关术语

- 在无向图 G 中，如果从顶点 v 到顶点 v' 有路径，则称 v 和 v' 是连通的。
- 连通图：如果对于图中任意两个顶点 v(i)、v(j) ∈ V，v(i) 和 v(j) 都是连通的，称 G 是连通图（Connected Graph）。
- 连通分量：无向图中的极大连通子图称为连通分量。
           1. 要是子图。
           2. 子图要是连通的。
           3. 连通子图含有极大顶点数。
           4. 具有极大顶点数的连通子图包含依附于这些顶点的所有边。
- 强连通图：在有向图 G 中，如果对于每一对 v(i)、v(j) ∈ V、v(i) ≠ v(j)，从v(i) 到 v(j)和
           从 v(j) 到 v(i) 都存在路径，则称 G 为强连通图。
- 有向图的强连通分量：有向图中的极大强连通子图称做有向图的强连通分量。
- 连通树的生成树：一个连通图的生成树是一个极小的连通子图，它含有图中全部的 n 个顶点，
                但只有足以构成一棵树的 n-1 条边。
                如果一个图中有 n 个顶点和 n-1 条边，则是非连通图；
                如果它多于 n-1 条边，必定构成一个环。
- 有向树：如果一个有向图恰有一个顶点的入度为 0，其余顶点的入度均为 1，则是一棵有向树。
         一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。

图的抽象数据类型

ADT 图（Graph）
Data
    顶点的有穷非空集合和边的集合。
Operation
    CreateGraph(*G,V,VR)：按照顶点集 V 和边弧集 VR 的定义来构造图。
    DestroyGraph(*G)：图 G 存在则销毁。
    LocateVex(G,u)：若图 G 中存在顶点 u，将返回图中的位置。
    GetVex(G,v)：返回图 G 中顶点 v 的值。
    PutVex(G,v,value)：将图 G 中顶点 v 赋值 value。
    FirstAdjVex(G,*v)：返回顶点 v 的一个邻接顶点，若顶点在 G 中无邻接则返回空。
    NextAdjVex(G,v,*w)：返回顶点 v 相对于顶点 w 的下一个邻接顶点，若 w 是 v 的最后一个邻接点则返回空。
    InsertVex(*G,v)：在图 G 中增添新顶点 v。
    DeleteVex(*G,v)：删除图 G 中顶点 v 及其相关的弧。
    InsertArc(*G,v,w)：在图 G 中增添弧 <v,w>，若 G 是无向图，还需要增添对称弧 <w,v>。
    DeleteArc(*G,v,w)：在图 G 中删除弧 <v,w>，若 G 是无向图，还需要删除对称弧 <w,v>。
    DFSTraverse(G)：对图 G 中进行深度优先遍历，在遍历过程对每个顶点调用。
    HFSTraverse(G)：对图 G 中进行广度优先遍历，在遍历过程对每个顶点调用。
endADT

图的存储结构

邻接矩阵

图的邻接矩阵（Adjacency Matrix）存储方式使用两个数组来表示图。
一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。

无向图的邻接矩阵

有向图的邻接矩阵

网图的邻接矩阵

邻接表

数组和链表相结合的存储方法称为邻接表（Adjacency List）。
1. 图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取
   顶点信息，更加方便。另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻结点的指针，
   以便于查找该顶点的边信息。
2. 图中每个顶点 v(i) 的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，
   无向图称为顶点 v(i) 的边表，有向图则称为顶点 v(i) 作为弧尾的出边表。

无向图的邻接表

有向图的邻接表

网图的邻接表

十字链表

对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才能知道，
   反之，逆邻接表解决了入度却不能解决出度的情况。于是，把邻接表和逆邻接表组合起来就是十字链表。

有向图的十字链表

邻接多重表

ivex 和 jvex 是与某条边依附的两个顶点在顶点表中的下标。
ilink 指向依附顶点 ivex 的下一条边，jlink 指向依附顶点 jvex 的下一条边。

无向图的邻接多重表

边集数组

边集数组是由两个一维数组组成。一个是存储顶点的信息；另一个是存储边的信息。
这个边数组每个数据元素由一条边的起点下标（begin）、终点下标（end）和权（weight）组成。

有向图的边集数组

图的遍历

图的遍历（Traversing Graph）：从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。

深度优先遍历

深度优先遍历（Depth_First_Search），也称深度优先搜索，简称 DFS。
1. 它从图中某个顶点 v 出发，访问此顶点，然后从 v 的未被访问的邻接点出发深度优先遍历图，
   直至图中所有和 v 有路径相通的顶点都被访问到。
2. 若图中尚有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，重复上述过程，
   直至图中所有顶点都被访问到为止。

深度优先遍历

广度优先遍历

广度优先遍历（Breadth_First_Search）。又称广度优先搜索，简称 BFS。

广度优先遍历

最小生成树

最小生成树（Minimum Cost Spanning Tree）：构造连通网的最小代价生成树。

普里姆（Prim）算法

循环查找邻接矩阵每行的最小值，若某顶点已被纳入最小生成树，将其权值设为0，也就是跳过循环。
假如 N = (P,{E}) 是连通网，TE 是 N 上的最小生成树中边的集合。算法从 U = {u(0)} （u(0) ∈ V），
    TE = {} 开始。重复以下操作：在所有 u ∈ U，v ∈ V-U的边 (u,v) ∈ E 中找一条代价最小的边
    ( u(0),v(0) )并入集合 TE，同时 v(0) 并入 U，直至 U = V 为止。此时 TE 中必有 n-1 条边，
    则 T = (V,{TE}) 为 N 的最小生成树。
时间复杂度：O(n^2)。

附：https://zh.wikipedia.org/wiki/%E6%99%AE%E6%9E%97%E5%A7%86%E7%AE%97%E6%B3%95

克鲁斯卡尔（Kruskal）算法

假如 N = (V,{E}) 是连通网，则令最小生成树的初始状态为只有 n 个顶点而无边的非连通图 T = {V,{}}，
    图中每个顶点自成一个连通分量。在 E 中选择代价最小的边，若该边依附的顶点落在 T 中不同的连通
    分量上，则将此边加入到 T 中，否则舍去此边而选择下一条代价最小的边。依次类推，直至 T 中所有
    顶点都在同一连通分量上为止。
时间复杂度：O(e㏒e)。

最短路径

对于网图来说，最短路径是指两顶点之间经过的边上的权值之和最少的路径，
    并且我们称路径上的第一个顶点是原点，最后一个顶点是终点。

迪杰斯塔拉（Dijkstra）算法

按路径长度递增的次序产生最短路径。主要用来求一个顶点到其他所有顶点的最小路径。
从一个顶点开始，依次计算到其他各个顶点的最短路径，记录下从起始顶点到某个顶点最短路径的前驱顶点，
    直至到达最终顶点。

弗洛伊德（Floyd）算法

主要用来求所有顶点到所有顶点的最小路径。

附：http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html

拓扑排序

AOV 网（Activity On Vertex Network）：在一个表示工程的有向图中，用顶点表示活动，
    用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，称为 AOV 网。
拓扑序列：设 G = (V,E) 是一个具有 n 个顶点的有向图， V 中的顶点序列 v₁，v₂，...，v(n)，
        满足若从顶点 v(i) 到 v(j) 有一条路径，则从顶点序列中顶点 v(i) 比在顶点 v(j) 之前。
        称这样的顶点序列为一个拓扑排序。
所谓拓扑排序，就是对一个有向图构造拓扑序列的过程。
对 AOV 网进行拓扑排序的基本思路是：从 AOV 网中选择一个入度为 0 的顶点输出，然后删去此顶点，
    并删除以此顶点为尾的弧，继续重复此步骤，直至输出全部顶点或者 AOV 网中不存在入度为 0 的顶点为止。

时间复杂度：O(n+e)。

关键路径

AOE 网（Activity On Edge Network）：在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，
    用边上的权值表示活动持续的时间，这种有向图的边表示活动的网称为 AOE 网。
路径长度：路径上各个活动持续的时间之和叫路径长度。
关键路径：从源点到汇点具有最大长度的路径叫关键路径。
关键活动：在关键路径上的活动叫关键活动。