考研875数据结构

一、数据结构基本概念

建议另外过一遍严蔚敏课笔记
注意：代码缩进本该为4个空格，这里为了美观和方便，缩进是2个空格。

数据

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

数据元素

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

数据项

一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。
例如，学生记录就是一个数据元素，它由学号、姓名、性别等数据项组成。

数据对象

数据对象是具有相同性质的数据元素的集合，是数据的一个子集。
例如，整数数据对象是集合 N={0,±1,±2,…}。

数据、数据元素、数据项之间的关系

数据->数据对象->数据元素->数据项
两张表->数据；其中一张表->数据对象；表中每一行（记录）->数据元素；每条记录的每个属性->数据项

数据结构的定义

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素都不是孤立存在的，它们之间存在某种关系，这种数据元素相互之间的关系称为结构（Structure）。

数据结构的三要素

数据结构包括三方面的内容：逻辑结构、存储结构和数据的运算。
数据的逻辑结构和存储结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。

数据的逻辑结构

逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机的。
数据的逻辑结构分为线性结构和非线性结构，线性表是典型的线性结构，集合、树和图是典型的非线性结构。
1) 集合。结构中的元素之间除“同属一个集合”外，别无其它关系。
2) 线性结构。结构中的数据元素之间只存在一对一的关系。
3) 树形结构。结构中的数据元素之间存在一对多的关系。
4) 图状结构或网状结构。结构中的数据元素之间存在多对多的关系。

数据的物理结构

存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构。它包括数据元素的表示和关系的表示。数据的存储结构是计算机语言实现的逻辑结构，它依赖于计算机语言。数据的存储结构主要有顺序存储、链式存储、索引存储和散列存储。
1) 顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
其优点是可以实现随机存取，每个元素占用最少的存储空间；缺点是只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。
2) 链式存储。不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。
其优点是不会出现碎片现象，能充分利用所有存储单元；缺点是每个元素因存储指针而占用额外的存储空间，且只能实现顺序存取。
3) 索引存储。在存储元素信息的同时，还建立附加的索引表。索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）。
其优点是检索速度快；缺点是附加的索引表额外占用存储空间。另外，增加和删除数据时也要修改索引表，因而会花费较多的时间。
4) 散列存储。根据元素的关键字直接计算出该元素的存储地址，又称哈希（Hash）存储。
其优点时检索、增加和删除结点的操作都很快；缺点是若散列函数不好，则可能出现元素存储单元的冲突，而解决冲突会增加时间和空间开销。

数据的运算的定义

（王道）施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。
（博客）数据的运算是指对数据实施的操作，数据的运算最终需要在对应的存储结构上用算法实现，所以数据运算分为运算的定义和运算的实现两个层面。
运算的定义是对运算功能的描述，是抽象的，是基于逻辑的。
运算的实现是程序员完成运算的实现算法，是具体的，是基于存储结构的。

数据类型

数据类型是一个值的集合和定义在集合上的一组操作的总称。
1) 原子类型。其值不可再分的数据类型。
2) 结构类型。其值可以再分解为若干成分（分量）的数据类型。
3) 抽象数据类型。一个数学模型及定义在该数学模型上的一组操作。它通常是对数据的某种抽象，定义了数据的取值范围及其结构形式，以及对数据操作的集合。
抽象数据类型的三个组成部分：数据对象、数据关系和基本操作。
（蓝皮书，定义）抽象数据类型是一种构造数据类型，它具有三大特征，信息隐蔽、数据封装、使用与实现相分离。

数据类型、抽象数据类型和数据结构之间的关系

数据类型是一个值的集合和定义在此集合上的一组操作的总称。（值+操作）
抽象数据类型（ADT）是一个数学模型及定义在该数学模型上的一组操作。（数学模型+操作）它通常是对数据的某种抽象，定义了数据的取值范围及其结构形式，以及对数据操作的集合。（数据对象+数据关系+基本操作）
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。（数据元素+数据关系）

二、算法和算法分析

算法的定义

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每一条指令表示一个或多个操作。
算法和程序的区别：
1. 算法是描述一个问题求解的步骤序列，而程序是算法在特定计算机上的实现。
2. 算法不依赖于计算机，而程序依赖于特定的计算机和特定的编程语言。
3. 算法必须满足五个特性，即有穷性、确定性、可行性、有输入、有输出，而程序可能不满足有穷性。

算法的特性（五个）

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

算法设计的要求

正确性。算法应能够正确地解决求解问题。
- 首先，算法应当满足以特定的“规格说明”方式给出的需求。
- 其次，对算法是否“正确”的理解可以有以下四个层次：
  a. 程序中不含语法错误；
  b. 程序对于几组输入数据能够得出满足规格说明要求的结果；
  c. 程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果；
  d. 程序对于一切合法的输入数据都能产生满足规格说明要求的结果。
  （通常以第c层意义的正确性作为衡量一个程序是否合格的标准。）
可读性。算法应具有良好的可读性，以帮助人们理解。
- 算法主要是为了人的阅读与交流，其次才是机器执行。可读性好有助于人对算法的理解；
- 另一方面，晦涩难懂的程序易于隐藏较多错误，难以调试和修改。
健壮性。算法能对输入的非法数据做出反应或处理，而不会产生莫名其妙的输出。
- 当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。
- 并且，处理出错的方法应是返回一个表示错误或错误性质的值，而不是打印错误信息或异常，并中止程序的执行，以便在更高的抽象层次上进行处理。
效率与低存储量需求。效率是指算法执行的时间，存储量需求是指算法执行过程中所需要的最大存储空间，这两者都与问题的规模有关。
- （因为：求100个人的平均分与求1000个人的平均分所花的执行时间或运行空间显然有一定的差别。）

算法的时间、空间复杂度的定义及计算

（归纳下应该这么说）算法的时间复杂度是一个关于问题规模n的函数，表示算法中基本运算的执行次数的数量级，定性地描述该算法的运行时间。
（归纳下应该这么说）算法的空间复杂度是问题规模n的函数，定性地描述该算法或程序运行所需要的存储空间大小。
（wiki）算法的时间复杂度（time complexity）是一个函数，它定性描述该算法的运行时间。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，也就是考察输入值大小趋近无穷时的情况。例如，如果一个算法对于任何大小为 n （必须比 $n_0$ 大）的输入，它至多需要 $5n^3 + 3n$ 的时间运行完毕，那么它的渐近时间复杂度是 $O(n^3)$ 。
（wiki）在计算机科学中，一个算法或程序的空间复杂度定性地描述该算法或程序运行所需要的存储空间大小。空间复杂度是相应计算问题的输入值的长度的函数，它表示一个算法完全执行所需要的存储空间大小。
就像时间复杂度的计算不考虑算法所使用的空间大小一样，空间复杂度也不考虑算法运行需要的时间长短。

衡量算法在资源上的两个方面

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外内存空间。根据算法编写出的程序，运行时间更短，运行期间占用的内存更少，该算法的运行效率就更高，算法也就更好。
度量一个程序的执行时间通常有两种方法：

事后统计的方法（让算法变成一个程序，在机器上执行并计时）
缺点：
(1) 必须执行程序
(2) 其他因素掩盖算法本质
事前分析估算的方法（通常使用的）
和算法执行时间相关的因素：
(1) 算法选用的策略
(2) 问题的规模
(3) 编写程序的语言
(4) 编译程序产生的机器代码的质量
(5) 机器执行指令的速度
（后三条和计算机的软件和硬件有关，和设计算法无关，所以设计算法时只考虑前两条）

算法的存储量包括：
(1) 输入数据所占空间
(2) 程序本身所占空间
(3) 辅助变量所占空间
- 若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。
- 若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。
- 若所需存储量依赖于特定的输入，则通常按最坏情况考虑。

算法的渐进性分析方法，会用该方法对算法进行评估

渐进分析

渐进分析（asymptotic analysis、asymptotics），在数学分析中是一种描述函数在极限附近的行为的方法。有多个科学领域应用此方法。例子如下：
- 在计算机科学中，算法分析考虑给定算法在输入非常大的数据集时候的性能。
- 当实体系统的规模变得非常大的时候，分析它的行为。
最简单的例子如下：考虑一个函数f(n)，我们需要了解当n变得非常大的时候f(n)的性质。
令 $f(n)=n^2+3n$ ，在n特别大的时候，第二项3n比起第一项 $n^2$ 要小很多。
于是对于这个函数，有如下断言：“f(n)在n→∞的情况下与 $n^2$ 渐近等价”，记作 $f(n)∼n^2$ 。
算法分析
在计算机科学中，算法分析（Analysis of algorithm）是分析执行一个给定算法需要消耗的计算资源数量（例如计算时间，存储器使用等）的过程。算法的效率或复杂度在理论上表示为一个函数。其定义域是输入数据的长度（通常考虑任意大的输入，没有上界），值域通常是执行步骤数量（时间复杂度）或者存储器位置数量（空间复杂度）。算法分析是计算复杂度理论的重要组成部分。
理论分析常常利用渐近分析估计一个算法的复杂度，并使用大O符号、大Ω符号和大Θ符号作为标记。举例，二分查找所需的执行步骤数量与查找列表的长度之对数成正比，记为O(log n)，简称为“对数时间”。通常使用渐近分析的原因是，同一算法的不同具体实现的效率可能有差别。但是，对于任何给定的算法，所有符合其设计者意图的实现，它们之间的性能差异应当仅仅是一个系数。
精确分析算法的效率有时也是可行的，但这样的分析通常需要一些与具体实现相关的假设，称为计算模型。计算模型可以用抽象机器来定义，比如图灵机。或者可以假设某些基本操作在单位时间内可完成。
假设二分查找的目标列表总共有 n 个元素。如果我们假设单次查找可以在一个时间单位内完成，那么至多只需要 logn + 1 单位的时间就可以得到结果。这样的分析在有些场合非常重要。
算法分析在实际工作中是非常重要的，因为使用低效率的算法会显著降低系统性能。在对运行时间要求极高的场合，耗时太长的算法得到的结果可能是过期或者无用的。低效率算法也会大量消耗计算资源。
渐进最优
在计算机科学中，渐进最优一词用以评价算法的效率。如果已经证实一个问题需要使用Ω(f(n))的资源来解决，而某个算法用O(f(n))的资源来解决这个问题，则该算法就是渐进最优的。
渐进最优的例子包括数据结构动态数组，能够在常数时间内索引，但性能在多数机器上不如普通数组的索引。另外，在所有基于比较的排序算法中，归并排序和堆排序是渐进最优的。

三个标记法

$O$ $O$ 标记法
- 大O符号（上界）表示函数在增长到一定程度时总小于一个特定函数的常数倍。
$\Omega$ $Ω$ 标记法
- 大Ω符号表示函数在增长到一定程度时总大于一个特定函数的常数倍。
$\Theta$ $Θ$ 标记法
- 大Θ符号表示函数在某个区间上的渐近关系。如果两个函数在某个区间上的上界和下界都分别为另一个函数，那么这两个函数在该区间上是渐近相等的，可以用大Θ符号表示为：f(n) = Θ(g(n))

时空权衡原则

计算机科学中的时空权衡（英语：space–time trade off，又叫空间换时间）是指一个算法或程序用增加空间使用量来换取时间减少的情况。这里，空间指的是执行一个给定任务所消耗的数据存储（内存、硬盘等），而时间指的是执行一个给定任务所消耗的时间（计算时间或反应时间）。
一个给定的时空权衡的效用受到相关的固定和可变成本（如CPU速度、存储空间）的影响，并受到收益递减的影响。

三、线性表

线性表的定义

线性表是具有相同数据类型的n个数据元素的有限序列，n为表长，当n=0时，该线性表是空表。

线性表的逻辑结构

线性表是一种逻辑结构，表示元素之间一对一的相邻关系；顺序表和链表是存储结构。
线性表的逻辑特性：若用L命名线性表，则其一般表示为 $L=(a_1,a_2,\cdots,a_i,a_{i+1},\cdots,a_n)$ 。式中， $a_1$ 是唯一的“第一个”数据元素，又称表头元素； $a_n$ 是唯一的“最后一个”数据元素，又称表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继（“直接前驱”和“前驱”、“直接后继”和“后继”通常被视为同义词）。这种线性有序的逻辑结构正是线性表名字的又来。
线性表的特点：
1. 表中元素的个数有限。
2. 表中元素具有逻辑上的顺序性，表中元素有其先后次序。
3. 表中元素都是数据元素，每个元素都是单个元素。
4. 表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间。
5. 表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。

线性表的基本操作

InitList(&L): 初始化表。构造一个空的线性表。
Length(L): 求表长。返回线性表L的长度，即L中数据元素的个数。
LocateElem(L,e): 按值查找操作。在表L中查找具有给定关键字值的元素。
GetElem(L,i): 按位查找操作。获取表L中第i个位置的元素的值。
ListInsert(&L,i,e): 插入操作。在表L中的第i个位置上插入指定的元素e。
ListDelete(&L,i,&e): 删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
PrintList(L): 输出操作。按前后顺序输出线性表L的所有元素值。
Empty(L): 判空操作。若L为空表，则返回true，否则返回false。
DestroyList(&L): 销毁操作。销毁线性表，并释放线性表L所占用的内存空间。

顺序表的定义

线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。
（称i为元素 $a_i$ 在顺序表中的位序。）

顺序表的特点

表中元素的逻辑顺序与其存储的物理顺序相同，因此可以随机存取表中的任一元素，它的存储位置可用一个简单、直观的公式表示。

用顺序存储结构对线性表基本操作的实现

注意不可以用int替代数据元素的数据类型，因为数据类型未给定，得用ElemType代替。

线性表的动态分配顺序存储结构

数组指针elem指示线性表的基地址，listsize指示顺序表当前分配的存储空间大小，一旦因插入元素而导致空间不足时，可进行再分配，即为顺序表增加一个大小为存储LISTINCREMENT个数据元素的空间。

#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
#define LISTINCREMENT 10 //线性表存储空间的分配增量
typedef struct {
  ElemType *elem; //存储空间基址
  int length; //当前长度
  int listsize; //当前分配的存储容量（以sizeof(Elemtype)为单位）
}Sqlist;

顺序表的初始化

Status InitList_Sq(SqList &L) {
  //构造一个空的线性表L
  L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
  if (! L.elem) exit(OVERFLOW); //存储分配失败
  L.length = 0;
  L.listsize = LIST_INIT_SIZE; //初始存储容量
  return OK;
}

插入操作

在第i（1≤i≤n）个元素之前插入一个元素，需将第n至第i（共n-i+1个）个元素向后移动一个位置。
C语言中数组的下标从“0”开始，因此表中第i个数据元素是L.elem[i-1]。

Status ListInsert_Sq(SqList &L, int i, ElemType e) {
  //在顺序线性表L中第i个位置之前插入新的元素e
  //i的合法值为 1≤i≤ListLength_Sq(L)+1
  if (i < 1 || i > L.length+1) return ERROR; //i值不合法
  if (L.length >= L.listsize) { //当前存储空间已满，增加分配
    newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT) * sizeof(ElemType));
    if (!newbase) exit(OVERFLOW); //存储分配失败
    L.elem = newbase;
    L.listsize += LISTINCREMENT; //增加存储容量
  }
  q = &(L.elem[i-1]); //q为插入位置
  for (p = &(L.elem[L.length-1]); p >= q; --p)
    *(p+1) = *p; //插入位置及之后的元素右移
  *q = e; //插入e
  ++ L.length; //表长增1
  return OK;
}

删除操作

删除第i（1≤i≤n）个元素时，需将从第i+1至n（共n-i）个元素依次向前移动一个位置。
C语言中数组的下标从“0”开始，因此表中第i个数据元素是L.elem[i-1]。

Status ListDelete_Sq(SqList &L, int i, ElemType &e) {
  //在顺序线性表L中删除第i个元素，并用e返回其值
  //i的合法值为 1≤i≤ListLength_Sq(L)
  if (i < 1 || i > L.length) return ERROR; //i值不合法
  p = &(L.elem[i-1]); //p为被删除元素的位置
  e = *p; //被删除元素的值赋给e
  q = L.elem + L.length - 1; //表尾元素的位置（elem表示线性表的基址）
  for (++p; p <= q; ++p)
    *(p-1) = *p; //被删除元素之后的元素左移
  --L.length; //表长减1
  return OK;
}

移动元素次数的期望值

当在顺序存储结构的线性表中某个位置上插入或删除一个数据元素时，其时间主要耗费在移动元素上（换句话说，移动元素的操作为预估算法时间复杂度的基本操作），而移动元素的个数取决于插入或删除元素的位置。
- 假设等概率，
  - 插入（在i前插入）： $E_{is} = \sum\limits_{i=1}^{n+1}p_i(n-i+1) = \frac{1}{n+1}\sum\limits_{i=1}^{n+1}(n-i+1) = \frac{n}{2}$
  - 删除（第i个）： $E_{dl} = \sum\limits_{i=1}^{n}q_i(n-i) = \frac{1}{n}\sum\limits_{i=1}^{n}(n-i) = \frac{n-1}{2}$
- 若表长为n，则算法 ListInsert_Sq 和 ListDelete_Sq 的时间复杂度为 O(n) 。
- “求表长”（ListLength_Sq）和“取第i个数据元素”（GetElem_Sq）的时间复杂度为 O(1) 。
- LocateElem_Sq 的时间复杂度为 O(L.length) ， union_Sq（A=A∪B）的时间复杂度为 O ( La.length × Lb.length ) ， MergeList_Sq（C=A∪B）的时间复杂度为 O ( La.ListLength + Lb.ListLength ) 。

按值查找（顺序查找）

int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType)) {
  //在顺序线性表L中查找第1个值与e满足compare()的元素的位序
  //若找到，则返回其在L中的位序，否则返回0
  i = 1; //i的初值为第1个元素的位序
  p = L.elem; //p的初值为第1个元素的存储位置
  while(i <= L.length && !(*compare)(*p ++, e))
    ++i;
  if(i <= L.length)
    return i;
  else
    return 0;
}

线性表的合并（A=A∪B）

将存在于线性表LB中，而不存在于线性表LA中的数据元素插入到线性表LA中去。

void union(List &La, List &Lb) {
  //将所有在线性表Lb中但不在La中的数据元素插入到La中
  La.len = ListLength(La); Lb.len = ListLength(Lb); //求线性表的长度
  for (i = 1; i <= Lb.len; i++) {
    GetElem(Lb, i, e); //取Lb中第i个数据元素赋给e
    if (!LocateElem(La, e, equal)) ListInsert(La, ++ La_len, e); //La中不存在和e相同的数据元素，则插入之
  }
}

顺序表的合并（C=A∪B）

void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) {
  //已知顺序线性表La和Lb的元素按值非递减排列
  //归并La和Lb得到新的顺序线性表Lc，Lc的元素也按值非递减排列
  pa = La.elem; pb = Lb.elem;
  Lc.listsize = Lc.length = La.length + Lb.length;
  pc = Lc.elem = (ElemType *)malloc(Lc.listsize*sizeof(ElemType));
  if (!Lc.elem) exit(OVERFLOW); //存储分配失败
  pa_last = La.elem + La.length - 1;
  pb_last = Lb.elem + Lb.length - 1;
  while (pa <= pa_last && pb <= pb_last) { //归并
    if (*pa <= *pb) *pc ++ = *pa ++;
    else *pc ++ = *pb ++;
  }
  while (pa <= pa_last) *pc ++ = *pa ++; //插入La的剩余元素
  while (pb <= pb_last) *pc ++ = *pb ++; //插入Lb的剩余元素
}

链式表的定义

链式表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链式表的特点

用一组任意（可连续，也可不连续）的存储单元存储数据元素，对于每个数据元素都需要一个存储其本身信息的数据域和存储直接后继存储位置的指针域。

用链式存储结构对线性表基本操作的实现（见下）

链式存储结构的实现技术（比如）

单向链表

线性表的链式存储又称单链表。它是通过一组任意的存储单元来存储线性表中的数据元素。
为了建立数据元素之间的线性关系，对每个链表结点，除存放元素自身的信息之外，还需要存放一个指向其后继的指针。

结点类型描述：

typedef struct LNode {
  ElemType data;
  struct LNode *next;
}LNode, *LinkList;

利用单链表可以解决顺序表需要大量连续存储单元的缺点，但附加的指针域，也存在浪费存储空间的缺点。
由于单链表的元素离散地分布在存储空间中，因此是非随机存取的存储结构，即不能直接找到表中某个特定结点。查找特定结点时，需要从表头开始遍历，依次查找。
通常用头指针L（或head等）来标识一个单链表，指出链表的起始地址，头指针为NULL时表示一个空表。
此外，为了操作上的方便，在单链表第一个数据结点之前附加一个结点，称为头结点。
头结点的数据域可以不设任何信息，但也可以记录表长等信息。单链表带头结点时，头指针L指向头结点；单链表不带头结点时，头指针指向第一个数据结点。
表尾结点的指针域为NULL（用“^”表示）。
头结点和头指针的关系：不管带不带头结点，头指针都始终指向链表的第一个结点，而头结点是带头结点的链表中的第一个结点，结点内通常不存储信息。
引入头结点后，可以带来两个优点：
1. 由于第一个数据结点的位置被存放在头结点的指针域中，因此在链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理。
2. 无论链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就得到了统一。

初始化（王道）：

//带头结点
bool InitList(LinkList &L) {
  L=(LNode*)malloc(sizeof(LNode));
  L->next=NULL;
  return true;
}

//不带头结点
bool InitList(LinkList &L) {
  L=NULL;
  return true;
}

求表长（王道）：

int Length(LinkList L) {
  int len=0;
  LNode *p=L;
  while(p->next!=NULL) {
    p=p->next;
    len++;
  }
  return len;
}

按序号查找结点（王道+书）：

//王道
LNode *GetElem(LinkList L, int i) {
  LNode *p = L;
  int j = 0;
  while(p != NUll && j < i) {
    p = p -> next;
    j ++;
  }
  return p;
}

//书
Status GetElem_L(LinkList L, int i, ElemType &e) {
  p = L -> next; j = 1;
  while (p && j < i) {
    p = p -> next; ++ j;
  }
  if (!p) return ERROR; //表长小于i，没有第i个元素
  e = p -> data;
  return OK;
}

按值查找表结点（王道）：

LNode *LocateElem(LinkList L, ElemType e) {
  LNode *p = L -> next;
  while (p != NULL && p -> data != e) {
    p = p -> next;
  }
  return p;
}

插入结点（王道，书上与王道一致不写了）：

注意，当链表不带头结点时，需要判断插入位置i是否为1，若是，则要做特殊处理，将头指针L指向新的首结点。

//王道，将值为x的新结点插入到第i个位置
bool ListInsert(LinkList &L, int i, ElemType e) {
  LNode *p = L;
  int j = 0;
  while (p != NULL && j < i - 1 ) {
    p = p -> next;
    j ++;
  }
  if (p == NULL) return false; //i值不合法
  LNode *s=(LNode*)malloc(sizeof(LNode));
  s -> data = e;
  s -> next = p -> next;
  p -> next = s;
  return true;
}

可以将前插操作写成后插操作+data互换

在单链表插入算法中，通常都采用后插操作。

//需要将*s插入到*p前，用*s插入到*p后+互换data
s -> next = p -> next;
p -> next = s;
temp = p -> data;
p -> data = s -> data;
s -> data = temp;

删除结点（王道，书上与王道一致不写了）：

注意，当链表不带头结点时，需要判断插入位置i是否为1，若是，则要做特殊处理，将头指针L指向新的首结点。

bool ListDelete(LinkList &L, int i, ElemType &e) {
  LNode *p = L;
  int j = 0;
  while (p != NULL && j < i - 1) {
    p = p -> next;
    j ++;
  }
  if (p == NULL || p -> next == NULL) return false; //i值不合法
  LNode *q = p -> next;
  e = q -> data;
  p -> next = q -> next;
  free(q);
  return true;
}

可以将删除p写成删除p的后继+交换data

删除结点的通常做法是找到p前驱，然后执行删除操作。
1
2
3
4
q = p -> next;
p -> data = p -> next -> data;
p -> next = q -> next;
free(q);

采用头插法建立单链表（插入头结点之后），可以用来实现链表的逆置。

LinkList List_HeadInsert(LinkList &L) {
  LNode *s; int x; //定义新结点
  L = (LNode*)malloc(sizeof(LNode)); //创建头结点
  L -> next = NULL; //初始为空链表
  scanf("%d", &x); //输入结点的值
  while(x!=9999) { //输入9999表示结束
    s = (LNode*)malloc(sizeof(LNode)); //创建新结点
    s -> data = x;
    s -> next = L -> next;
    L -> next = s; //L为头指针
    scanf("%d", &x);
  }
  return L;
}

采用尾插法建立单链表。为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。

LinkList List_TailInsert(LinkList &L) {
  int x;
  L = (LNode*)malloc(sizeof(LNode)); //创建头结点
  LNode *s, *r = L; //r为表尾指针
  scanf("%d", &x);
  while(x != 9999) { //输入9999表示结束
    s = (LNode*)malloc(sizeof(LNode));
    s -> data = x;
    r -> next = s;
    r = s; //r指向新的表尾结点
    scanf("%d", &x);
  }
  r -> next = NULL; //尾结点指针置空
  return L;
}

归并两个链表（书）

void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) {
  //已知单链线性表La和Lb的元素按值非递减排列
  //归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列
  pa = La -> next; pb = Lb -> next;
  Lc = pc = La; //用La的头结点作为Lc的头结点
  while(pa && pb) {
    if (pa -> data <= pb -> data) {
      pc -> next = pa; pc = pa; pa = pa -> next; //将pa所指结点链接到pc所指结点之后
    }
    else {
      pc -> next = pb; pc = pb; pb = pb -> next; //将pb所指结点链接到pc所指结点之后
    }
  }
  pc -> next = pa ? pa : pb; //插入剩余段（pa存在连pa，否则连pb）
  free(Lb); //释放Lb的头结点
}

静态链表

静态链表是用数组来描述线性表的链式存储结构（其他链表为指针型描述），结点也有数据域data和指针域next。
与其他链表中的指针不同的是，这里的指针是结点在数组中的相对地址（书：相对位置）（数组下标），又称游标。
和顺序表一样，静态链表也要预先分配一块连续的内存空间。
静态链表的插入、删除操作与动态链表的相同，只需要修改指针，而不需要移动元素，故仍具有链式存储结构的主要优点。
这种描述方法便于在不支持指针的高级程序设计语言（如Basic）中使用链表结构。
数组的一个分量表示一个结点，数组的第零分量可看成头结点，其指针域只是链表的第一个结点。

线性表的静态单链表存储结构：

#define MAXSIZE 1000 //链表的最大长度
typedef struct {
  ElemType data;
  int cur;
}component, SLinkList[MAXSIZE];

定位函数（书）

int LocateElem_SL(SLinkList S, ElemType e) {
  //在静态单链线性表L中查找第1个值为e的元素
  //若找到，则返回它在L中的位序，否则返回0
  i = S[0].cur; //i表中第一个结点
  while(i && S[i].data != e) i = S[i].cur; //在表中顺链查找
  return i;
}

求(A-B)∪(B-A)（书P33，挺复杂的，有时间可看）

双向链表

单链表只能从前往后依次遍历；要访问某个结点的前驱（插入、删除操作时），只能从头开始遍历，访问前驱的时间复杂度为O(n)。
为了克服单链表的这个缺点，引入了双链表，双链表结点中有两个指针prior和next，分别指向其直接前驱和直接后继。
表头结点的prior域和尾结点的next域都是NULL。

线性表的双向链表存储结构（书）：

typedef struct DuLNode {
  ElemType data;
  struct DuLNode *prior;
  struct DuLNode *next;
}DuLNode, *DuLinkList;

单循环链表

循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL，而改为指向头结点，从而整个链表形成一个环。
在循环单链表中，表尾结点*r的next域指向L，故表中没有指针域为NULL的结点，因此，循环单链表的判空条件不是头结点的指针是否为空，而是它（头结点的指针）是否等于头指针L。
循环单链表的插入、删除算法与单链表的几乎一样，所不同的是若操作是在表尾进行，则执行的操作不同，以让单链表继续保持循环的性质。
当然，正是因为循环单链表是一个“环”，所有在任何位置上的插入和删除操作都是等价的，而无须判断是否是表尾。
在单链表中只能从表头结点开始往后顺序遍历整个链表，而循环单链表可以从表中的任意一个结点开始遍历整个链表。
有时对循环单链表不设头指针，而仅设尾指针，以使得操作效率更高。其原因是，若设的是头指针，对在表尾插入元素需要O(n)的时间复杂度，而若设的是尾指针r，r->next即为头指针，对在表头或插入元素都只需要O(1)的时间复杂度。

双向循环链表

与循环单链表不同的是，在循环双链表中，头结点的prior指针还要指向表尾结点。
表尾结点*p的next域也指向L；当循环双链表为空表时，其头结点的prior域和next域都等于L。

带头结点的链表

（对于单链表：）

头结点的数据域可以不设任何信息，但也可以记录表长等信息。单链表带头结点时，头指针L指向头结点；单链表不带头结点时，头指针指向第一个数据结点。
头结点和头指针的关系：不管带不带头结点，头指针都始终指向链表的第一个结点，而头结点是带头结点的链表中的第一个结点，结点内通常不存储信息。
引入头结点后，可以带来两个优点：
1. 由于第一个数据结点的位置被存放在头结点的指针域中，因此在链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理。
2. 无论链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就得到了统一。

初始化（王道）：

//带头结点
bool InitList(LinkList &L) {
  L=(LNode*)malloc(sizeof(LNode));
  L->next=NULL;
  return true;
}

//不带头结点
bool InitList(LinkList &L) {
  L=NULL;
  return true;
}

对于插入操作，当链表不带头结点时，需要判断插入位置i是否为1，若是，则要做特殊处理，将头指针L指向新的首结点。
对于删除操作，当链表不带头结点时，需要判断插入位置i是否为1，若是，则要做特殊处理，将头指针L指向新的首结点。

（单循环链表，关于头结点的部分）

循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL，而改为指向头结点，从而整个链表形成一个环。
在循环单链表中，表尾结点*r的next域指向L，故表中没有指针域为NULL的结点，因此，循环单链表的判空条件不是头结点的指针是否为空，而是它（头结点的指针）是否等于头指针L。
（双向循环链表，关于头结点的部分）
双向循环链表
与循环单链表不同的是，在循环双链表中，头结点的prior指针还要指向表尾结点。
表尾结点*p的next域也指向L；当循环双链表为空表时，其头结点的prior域和next域都等于L。

线性表的应用

一元多项式的表示和相加

这个应该是线性表的应用吧，书P39

代码很复杂，大致思路：

先将一个一元n次多项式按照升幂写成 $P_n(x) = p_1 x^{e_1} + p_2 x^{x_2} + \cdots + p_m x^{e_m}$ ，
其中 $p_i$ 是指数为 $e_i$ 的项的非零系数，且满足 $0 \leq e_1 < e_2 < \cdots < e_m = n$
用线性链表表示一元多项式，每个结点表示多项式中的一项，每个结点存储系数和指数。
实现两个多项式（用两个线性链表表示）的相加：类似于归并，因为指数升序排列，对于指数相同的把系数相加即可。
实现多项式相乘： $M(x)=A(x)×B(x) =A(x)×[b_1x^{e_1}+b_2x^{e_2}+\cdots +b_nx^{e_n}] =\sum\limits_{i=1}^n b_i A(x)x^{e_i}$

具有在实际中选取不同存储结构的判断能力

顺序表和链表的比较

（出自蓝皮书）

顺序表
- 优点：
1. 时间上，它可以顺序存储，还可以随机存取，访问速度快；
2. 空间上，它的存储利用率高，不需要指针。
- 缺点：
1. 时间上，顺序表在插入删除时，如果需要保持原来的顺序，必须平均移动一半的元素，更新速度慢；
2. 空间上，如果采用静态分配的存储结构，一旦存储数组的空间已满，不能扩充，再插入元素将导致溢出。
链表
- 优点：
1. 时间上，插入删除不需要大量移动元素，只需修改指针，更新速度快；
2. 空间上，链表基本没有满和溢出的问题，只要内存可以分配节点，就可以扩充。
- 缺点：
1. 时间上，链表只能顺序访问，所以查找一个元素平均要搜索半个表，访问速度慢；
2. 空间上，每个元素需要附加一个指针，存储利用率较低。
3. 此外，由于链表的单线联系的特性，如果操作不慎，导致断链，将会丢失后面的所有元素。

（出自王道）

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

在实际中怎样选取存储结构

（出自王道）

基于存储的考虑
- 难以估计线性表的长度或存储规模时，不宜采用顺序表；
- 但链表的存储密度较低，显然链式存储结构的存储密度是小于1的。
基于运算的考虑
- 若经常做的运算是按序号访问数据元素，顺序表优于链表。
  - 在顺序表中按序号访问 $a_i$ 的时间复杂度为O(1)；
  - 链表中按序号访问的时间复杂度为O(n)。
- 关于插入、删除操作。
  - 在顺序表中进行插入、删除操作时，平均移动表中一半的元素，当数据元素的信息量较大且表较长时，这一点是不应忽视的；
  - 在链表中进行插入、删除操作时，虽然也要找插入位置，但操作主要是比较操作，从这个角度考虑显然链表优于顺序表。
基于环境的考虑
- 顺序表容易实现，任何高级语言中都有数组类型；
- 链表的操作是基于指针的，相对来讲，前者实现较为简单，这也是用户考虑的一个因素。

总之，两种存储结构各有长短，选择哪一种由实际问题的主要因素决定。
通常较稳定的线性表选择顺序存储，而频繁进行插入、删除操作的线性表（即动态性较强）宜选择链式存储。

广义表

不记得在哪的知识点了，先写在这儿了。
内容来自博客。

广义表的定义

线性表 线性表指的是n≥0个元素a1, a2, a3…的有序数列，并且线性表的元素具有原子性，即结构上是不可分割的一个整体。
广义表(Generalized list) 而广义表则是线性表的一种扩展延伸。相对于线性表，广义表最大的特点在于其元素既可以是一个确定的类型，同时也可以是另一个有不定数量的元素组成的表（广义表）。
不难看出从广义表的定义是递归的。广义表是线性表的递归数据结构。

广义表的基本概念

广义表的表示
我们通常可以用 GL = (a1, a2, a3… an)来表示一个广义表，其中n为表的长度，n≥0，当n==0时，我们称广义表为空表，GL为广义表的名字。
为了能更好的区分广义表中的元素我们有以下定义：
原子如果ai是单个元素，我们称之为GL的原子
子表如果ai是一个广义表，我们陈之为GL的子表
我们通常把广义表中的原子用小写字母表示，而子表用大写字母表示。例如

A=() //空表
B=(e) //只含有一个原子的广义表
C=(a,(b,c,d)) //含有一个原子和一个子表的广义表
D=(A,B,C)=((),(e),(a,(b,c,d))) //含有三个子表的广义表，且第一个表为空表
E=(a,E) //广义表 E 中有两个元素，原子 a 和它本身。这是一个递归广义表，等同于：E = (a,(a,(a,…)))。

广义表的深度和长度
广义表的长度：广义表中元素的个数（包括原子和子表）
广义表的深度：广义表中括号的最大层数叫广义表的深度

广义表的表头和表尾
表头：当广义表不为空表时，第一个元素（可能为子表和原子）称为表头
表尾：除去表头，剩余元素组成的新广义表称为表尾
例如：

1 2	LS=(1,(1,2,3),5), 其中表头Head(LS)为原子1，表尾为Tail(LS)=((1,2,3),5) LS=(1), 其中表头Head(LS)为原子1，表尾为空表

广义表的存储结构

广义表是一种递归的数据结构，它的元素有两种类型，因此很难为广义表分配固定的存储空间，所以其存储结构适合用链式存储结构。
为了能使原子和子表在结构上保持一致，又容易区分我们通常采用如下结构：
广义表的第一种存储结构

typedef enum {ATOM,LIST } ElemTag; //ATOM==0:表示原子,LIST==1:表示子表
typedef struct GLNode {
  ElemTag tag; //公共部分，用以区分原子部分和表结点
  union { //原子部分和表结点的联合部分
    AtomType atom; //atom是原子结点的值域,  AtomType由用户定义
    struct { struct GLNode *hp, *tp;} ptr;
    // ptr是表结点的指针域,ptr.hp和ptr.tp分别指向表头和表尾
  };
} *Glist; //广义表类型

e.g. 表示（a,(b,c,d)）

广义表的第二种存储结构

第二种表示形式实际上就只是在原子中添加了tp指针指向下一个原子或子表

Typedef enum { ATOM,LIST} ElemTag;
//ATOM==0:表示原子,LIST==1:表示子表
Typedef struct GLNode {
  ElemTag tag; //公共部分，用以区分原子部分和表结点
  union { //原子部分和表结点的联合部分
    AtomType atom; //原子结点的值域
    struct GLNode *hp; //表结点的表头指针
  };
  struct GLNode *tp;
  //相当于线性链表的next，指向下一个元素结点
} *Glist; //广义表类型Glist 是一种扩展的线性链表

e.g. 表示（a,(b,c,d)）

广义表的计算（以第二种存储结构为例）

（wiki）D=(( ),(e),(a,(b,c,d)))是多层次的广义表，长度为3，深度为3。
广义表长度的计算（类似于链表的长度，直接统计tp）

int GLLength(GLNode *g) { //g为一个广义表头节点的指针
  int n=0;
  g=g->hp; //g指向广义表的第一个元素
  while (g!=NULL) {
    n++;
    g=g->tp;
  }
  return n;
}

广义表的深度（括号的最大层数）
对于带头节点的广义表g,广义表深度的递归定义是它等于所有子表中表的最大深度加1。若g为原子,其深度为0。

求广义表深度的递归模型f()如下：

int GLDepth(GLNode *g) { //求带头节点的广义表g的深度
  int max=0,dep;
  if (g->tag==0) return 0; //为原子时返回0
  g=g->hp; //g指向第一个元素
  if (g==NULL) return 1; //为空表时返回1
  while (g!=NULL) { //遍历表中的每一个元素
    if (g->tag==1) {　//元素为子表的情况
      dep=GLDepth(g); //递归调用求出子表的深度
      if (dep>max) max=dep;
      //max为同一层所求过的子表中深度的最大值
    }
    g=g->tp; //使g指向下一个元素
  }
  return(max+1); //返回表的深度
}

四、栈和队列

博客：
栈的深度解析：顺序栈与链栈的实现
 队列的深度解析：链式队列的实现

栈的定义

栈是一种后进先出（LIFO）的线性表，只允许在表尾进行插入和删除操作。
栈顶——表尾端（线性表允许进行插入和删除操作的那一端）。
栈底——表头端（线性表不允许进行插入和删除操作的那一端）。
空栈——不含任何元素的空表。

栈的逻辑结构

栈是操作受限的线性表，可被称为限定性的数据结构，其操作特性是后进先出（Last In First Out，LIFO）。
栈是只允许在一端进行插入和删除操作的线性表，允许进行插入和删除操作的那一端称为栈顶，不允许进行插入和删除操作的另一端称为栈底。

栈的特点（考点没写）

操作限制：只能在栈顶进行元素的添加（入栈）和移除（出栈）。
栈顶元素：当前可以访问和操作的元素。
空栈：栈为空时，无法进行出栈操作。

栈的操作特性（考点没写）

后进先出（Last In First Out，LIFO）

栈的基本操作

入栈（Push）：将新元素添加到栈顶。
出栈（Pop）：移除并返回栈顶元素。
查看栈顶元素（GetTop）：返回栈顶元素，但不删除它。
判断是否为空（IsEmpty）：检查栈是否没有元素。
统计栈的大小（Size）：获取栈中有效元素个数。

栈的数学性质（考点没写）

当n个不同元素进栈时，出栈元素不同排列的个数为
$\frac{1}{n+1}\mathrm{C}_{2n}^{n}$ 。这个公式称为卡特兰数（Catalan）公式。
证明：

画个n*n条路（边）的方格，从一个顶点走到另一个斜对角的端点总共要走2n条边，从中选择n条边为竖着走或横着走（类比为进栈或出栈），剩下n条为横着走或竖着走，得到 $\mathrm{C}_{2n}^{n}$ 种方式。
过了斜对角线的路径是有问题的，就是在某个前缀操作里边出栈次数多于入栈了（拿鬼出栈啊），求出这些非法路径的数目。
设不能越过的对角线为y=x，从(0,0)→(n,n)。画出y=x+1，作为对称轴。若越过y=x，与y=x+1就会有交点，把第一次碰到y=x+1以后的部分关于y=x+1对称，路径变为(0,0)→(n-1,n+1)。显然每一条非法路径都可以这么变为(0,0)→(n-1,n+1)，而任何合法方案由于不接触直线y=x+1，无论从哪个点对称都不是一条连续的路径。
非法路径条数为(0,0)→(n-1,n+1)的方案数，为 $\mathrm{C}_{2n}^{n-1}$ 。
合法路径数= $\mathrm{C}_ {2n}^{n}-\mathrm{C}_{2n}^{n-1} =\frac{(2n)!}{n!n!}-\frac{(2n)!}{(n+1)!(n-1)!} =\frac{(2n)!(n+1)}{n!n!(n+1)}-\frac{(2n)!n}{(n+1)n!n!} =\frac{1}{n+1}[\frac{(2n)!(n+1)-(2n)!n}{n!n!}] =\frac{1}{n+1} \mathrm{C}_{2n}^{n}$

顺序栈的定义

顺序栈：采用顺序存储的栈，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设一个指针top指示栈顶元素在顺序栈中的位置。

链式栈的定义

链栈：采用链式存储的栈。优点是便于多个栈共享存储空间和提高其效率，且不易发生栈溢出。
通常用单链表实现，并规定所有操作都是在单链表的表头进行的。

顺序栈和链式栈的特点

特点	顺序栈 (Sequential Stack)	链式栈 (Linked Stack)
存储结构	基于数组实现	基于链表实现
内存布局	内存连续	内存不连续，元素间通过指针连接
内存管理	静态分配（可动态扩容）	动态分配
空间效率	容量固定（可动态扩容，若超出初始容量则可能浪费空间）	动态扩展，使用的空间与元素个数相匹配
访问速度	O(1) 时间复杂度	O(1) 时间复杂度
空间复杂度	O(n)	O(n)
栈溢出	容易发生，尤其在固定容量情况下	不易发生，除非系统内存耗尽
实现简单性	实现较为简单，适用于容量已知的情况	实现复杂，需处理节点的动态分配与释放
元素访问	只能访问栈顶元素	只能访问栈顶元素
适用场景	适合对栈容量有明确限制的场景	适合不确定栈容量，且需频繁变化元素的场景

顺序栈的基本操作

定义

#define STACK_INIT_SIZE 100 //存储空间初始分配量
#define STACKINCREMENT 10 //存储空间分配增量
typedef struct {
  SELemType *base;
  SElemType *top;
  int stacksize; //栈的当前可使用的最大容量
}SqStack;

初始化

Status InitStack(SqStack &S) {
  S.base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
  if(!S.base) exit(OVERFLOW);
  S.top = S.base;
  S.stacksize = STACK_INIT_SIZE;
  return OK;
}

查看栈顶元素

Status GetTop(SqStack S, ElemType &e) {
  if(S.top == S.base) return ERROR; //栈空
  e = *(S.top-1);
  return OK;
}

入栈

// 插入元素e为新的栈顶元素
Status Push(SqStack &S, SElemType e) {
  if(S.top - S.base >= S.stacksize) { //栈满，追加存储空间
    S.base = (SElemType *)realloc((S.stacksize+STACKINCREMENT)*sizeof(ElemType));
    if(!S.base) exit(OVERFLOW);
    S.top = S.base + S.stacksize;
    S.stacksize +=STACKINCREMENT;
  }
  *S.top ++ = e;
  return OK;
}

出栈

Status Pop(SqStack &S, ElemType &e) {
  if(S.top == S.base) return ERROR; //栈空
  e = *--S.top;
  return OK;
}

注：验证过*S.top++ = e和e = *--S.top，代码如下，输入结果为1。

#include <bits/stdc++.h>
using namespace std;
typedef struct {
    int *top;
    int *base;
    int stacksize;
} SqStack;
int main(void){
    SqStack S;
    S.base = (int *)malloc(100*sizeof(int));
    S.top = S.base;
    *S.top ++ = 1;
    cout<<*--S.top<<endl;
    return 0;
}

情况分析：S.top = -1 和 S.top = 0。注意：声明struct的时候，用的是ElemType data[Maxsize]，所以不要出现top==Maxsize时S.data[top]，先把top降掉。

属性	当 `S.top = -1` 时	当 `S.top = 0` 时
初始时	`S.top = -1`	`S.top = 0`
栈的第一个元素	`S.data[0]`	`S.data[0]`
栈顶指针指向	指向栈顶元素	指向栈顶元素的后一个元素
栈满条件	`top == MAX_SIZE - 1`	`top == MAX_SIZE`
栈空条件	`top == -1`	`top == 0`
进栈操作	`判栈满，S.data[++top] = x;`	`判栈满，S.data[top++] = x;`
出栈操作	`判栈空，x = S.data[top--];`	`判栈空，x = S.data[--top];`

链栈的基本操作

声明（王道）

typedef struct Linknode {
  ElemType data;
  struct Linknode *next;
}ListStack;

链栈通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。
这里规定链栈没有头结点，Lhead指向栈顶元素。

共享栈（考点没写）

利用栈底位置相对不变的特性，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。
共享栈时为了更有效地利用存储空间，两个栈的空间相互调节，只有再整个存储空间被占满时才发生上溢。
其存取数据的时间复杂度均为O(1)，所以对存取效率没什么影响。

共享栈	0号栈	1号栈
初始时	top0 = -1	top1 = Maxsize
栈的第一个元素	S.data[0]	S.data[Maxsize]
栈顶指针指向	指向栈顶元素	指向栈顶元素
栈满条件	top1 - top0 == 1
栈空条件	top0 == -1，0号栈空	top1 == Maxsize，1号栈空
进栈操作	判栈满，S.data[++top0] = x;	判栈满，S.data[--top1] = x;
出栈操作	判栈空，x = S.data[top0--];	判栈空，x = S.data[top1++];

队列的定义

队列（Queue）简称队，是一种先进先出（First In First Out, FIFO）的线性表，它只允许在表的一端进行插入，而在另一端删除元素。
这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。
队尾（Front）——允许插入的一端。
队头（Rear）——允许删除的一端。
空队列——不含任何元素的空表。

队列的逻辑结构

队列是一种操作受限的线性表，只允许在表的一端进行插入，而在另一端删除元素，服从先进先出原则。允许插入的一端叫做队尾，允许删除的一端称为队头，队列为空时无法进行出队操作。

队列的操作特性（考点没写）

先进先出（FIFO）

队列的特点

先进先出（FIFO）：最先进入的元素最先被移除。
操作限制：只能在队列的尾部入队，头部出队。
队首元素：队首是当前可以访问和移除的元素。
空队列：队列为空时无法进行出队操作。
动态大小：可以根据需要扩展或收缩。

队列的基本操作

入队（Push）：将一个元素添加到队列的尾部。
出队（Pop）：从队列的头部移除并返回一个元素。
取队首元素（Front）：返回队首的元素，但不删除它。
取队尾元素（Back）：返回队尾的元素，但不删除它。
队列判空（isEmpty）：判断队列中是否有元素。
获取队列长度（Size）：获取队列中有效元素个数。

顺序队列的定义

顺序队列：采用顺序存储的队列，利用一块连续的存储单元存放队列中的元素，并附设两个指针front和rear分别指示队头和队尾元素在顺序队列中的位置。

链式队列的定义

链队列是队列的链式表示，它实际上是一个同时有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点。

顺序队列和链式队列的特点

特点	顺序队列	链式队列
存储结构	使用数组实现，连续存储元素	使用链表实现，非连续存储元素
固定大小	队列的大小在创建时固定	可以根据需要动态扩展
入队和出队效率	O(1)	O(1)
空间浪费	可能存在未使用的数组空间	无空间浪费
队满判断	需要判定是否队满	不需要判定队满
额外开销	无额外开销	每个元素需存储指针，空间开销较大

顺序队列的基本操作

（例如，还有其他变换，比如=1）这四个变换是用来锻炼思维和熟练度的，理清楚就可以举一反三了。

队头指针front

队尾指针rear

① 指向队尾元素

② 指向队尾元素的后一个位置

① 指向队头元素

初始时	Q.front=0; Q.rear=-1;
判空	Q.front==Q.rear+1
判满（若有限制长度为len）	Q.rear-Q.front==len-1
判再入队一个值，是否会“上溢出”	Q.rear+1>=Maxsize
进队	判“上溢出”和“满（若有）”，Q.rear++，赋值
出队	判空，取值，Q.front++

初始时	Q.front=Q.rear=0
判空	Q.front==Q.rear
判满（若有限制长度为len）	Q.rear-Q.front==len
判再入队一个值，是否会“上溢出”	Q.rear>=Maxsize
进队	判“上溢出”和“满（若有）”，赋值，Q.rear++
出队	判空，取值，Q.front++

② 指向队头元素的前一个位置

初始时	Q.front=-1; Q.rear=-1;
判空	Q.front==Q.rear
判满（若有限制长度为len）	Q.rear-Q.front==len
判再入队一个值，是否会“上溢出”	Q.rear+1>=Maxsize
进队	判“上溢出”和“满（若有）”，Q.rear++，赋值
出队	判空，Q.front++，取值

初始时	Q.front=-1; Q.rear=0;
判空	Q.front+1==Q.rear
判满（若有限制长度为len）	Q.rear-Q.front-1==len
判再入队一个值，是否会“上溢出”	Q.rear>=Maxsize
进队	判“上溢出”和“满（若有）”，赋值，Q.rear++
出队	判空，Q.front++，取值

链队列的基本操作

头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点。
不带头结点时，当Q.front==NULL && Q.rear==NULL时，链式队列为空。
入队时，建立一个新结点，将新结点插入到链表的尾部，并让Q.rear指向这个新插入的结点（若原队列为空队，则令Q.front也指向该结点 （带头结点时不用操作Q.front，因为它指向头结点））。
出队时，首先判断队是否为空，若不空，则取出队头元素，将其从链表中摘除，并让Q.front指向下一个结点（若该结点为最后一个结点，则置Q.front和Q.rear都为NULL （带头结点时只需修改Q.front->next为下一个结点，Q.front不用动，Q.rear置为指向头结点））。
不难看出，不带头结点的链式队列在操作上往往比较麻烦，因此通常将链式队列设计成一个带头结点的单链表，这样插入和删除操作就统一了。
用单链表表示的链式队列特别适合于数据元素变动比较大的情形，而且不存在队列满且产生溢出的问题。
另外，假如程序中要使用多个队列，与多个栈的情形一样，最好使用链式队列，这样就不会出现存储分配不合理和“溢出”的问题。
带头结点和不带头结点的操作是不一样的，要注意。

单链队列——队列的链式存储结构

typedef struct QNode {
  QElemType data;
  struct QNode *next;
}QNode, *QueuePtr;
typedef struct {
  QueuePtr front; //队头指针
  QueuePtr rear;
}LinkQueue;

初始化

Status InitQueue (LinkQueue &Q) {
  //构造一个空队列
  Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
  if(!Q.front) exit(OVERFLOW);
  Q.front -> next = NULL;
  return OK;
}

销毁队列Q

Stauts DestroyQueue (LinkQueue &Q) {
  while(Q.front) {
    Q.rear = Q.front -> next;
    free(Q.front);
    Q.front = Q.rear;
  }
  return OK;
}

入队——插入元素e为Q的新的队尾元素

Status EnQueue (LinkQueue &Q, ElemType e) {
  p = (QueuePtr)malloc(sizeof(QNode));
  if(!p) exit(OVERFLOW);
  p -> data = e;
  p -> next = NULL;
  Q.rear -> next = p;
  Q.rear = p; //别忘记这句！！！
  return OK;
}

出队——若队列不空，则删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR

Status DeQueue(LinkQueue &Q, QElemType &e) {
  if(Q.front == Q.rear) return ERROR;
  p = Q.front -> next;
  e = p -> data;
  Q.front -> next = p -> next;
  if(Q.rear == p) Q.rear = Q.front;
  free(p);
  return OK;
}

顺序存储结构中实现循环队列的具体要求

在顺序队列中，Q.rear==Maxsize并不能作为判断队列满的条件，但在此时如果再插入新的队尾元素，会发生数组越界问题；
但此时又不宜像顺序栈那样通过再分配来扩大数组空间，因为队列的实际可用空间可能并未占满。这便是一种“假溢出”。
为解决这种“假溢出”问题，引出了循环队列的概念。将顺序队列臆造为一个环状的空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。
当队首指针或队尾指针到达Maxsize-1后，若要再前进一个位置就自动到0，这里可以通过取模(%)的方式实现。
初始时：Q.front=Q.rear=0
队首指针进1：Q.front=(Q.front+1)%Maxszie
队尾指针进1：Q.rear=(Q.rear+1)%Maxsize
队列长度：(Q.rear+Maxsize-Q.front)%Maxsize
出队入队时：指针都按顺时针方向进1
为了区分是队空还是堆满的情况，有3种处理方式：
1. 牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是一种较为普遍的做法，约定以“队头指针在队尾指针的下一个位置作为队满的标志”。
  队满条件：(Q.rear+1)%Maxsize==Q.front；
  队空条件：Q.front == Q.rear；
  队列中元素的个数：(Q.rear-Q.front+Maxsize)%Maxsize。
2. 类型中增设size数据成员，表示元素个数。删除成功size—，插入成功size++。
  队空条件：Q.size==0；
  队满条件：Q.size==Maxsize。
  两种情况都有Q.front==Q.rear。
3. 类型中增设tag数据成员，以区分是队满还是队空。
  删除成功置tag=0，若导致Q.front==Q.rear，则为队空；
  插入成功置tag=1，若导致Q.front==Q.rear，则为队满。
在C语言中不能用动态分配的一维数组来实现循环队列。如果用户的应用程序中设有循环队列，则必须为它设定一个最大队列长度；若用户无法预估所用的队列的最大长度，则宜采用链队列。
这里会有很多变式，考试的时候随机应变，用手模特殊值，然后换成未知量的形式来做题即可。主要是记住队尾rear是入队，队头front是出队。

循环队列——队列的顺序存储结构

类型声明

#define MAXQSIZE 100 //最大队列长度
typedef struct {
  QElemType *base;
  int front;
  int rear;
}SqQueue;

初始化

Status InitQueue(SqQueue &Q) {
  Q.base = (QElemType *)alloc(MAXQSIZE*sizeof(QElemType));
  if(!Q.base) exit(OVERFLOW);
  Q.front = Q.rear = 0; //合法操作，在C语言中，赋值操作不仅会将值赋给变量，还会返回这个值本身
  return OK;
}

返回Q的元素个数，即队列的长度

1
2
3

int QueueLength(SqQueue Q) {
  return (Q.rear-Q.front+MAXQSIZE)%MAXSIZE;
}

入队

Status EnQueue(SqQueue &Q, QElemType e) {
  if((Q.rear+1) % MAXQSIZE == Q.front) return ERROR; //队满
  Q.base[Q.rear] = e;
  Q.rear = (Q.rear + 1) % MAXQSIZE;
  return OK;
}

出队

Status DeQueue(SqQueue &Q, QElemType &e) {
  if(Q.front == Q.rear) return ERROR;
  e = Q.base[Q.front];
  Q.front = (Q.front + 1) % MAXQSIZE;
  return OK;
}

理解递归调用和栈之间的关系

什么是递归？
在数学及程序设计方法学中，若一个对象部分包含它自己，或者用它自己定义自己，则称这个对象是递归的；若一个过程直接或间接地调用自己，则称这个过程是递归的过程。
递归是一种重要的程序设计方法。简单地说，若在一个函数、过程或数据结构的定义中又应用了它自身，则这个函数、过程、数据结构被称为是递归定义的，简称递归。
它通常把一个大型的复杂问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的代码就可以描述出解题过程所需要的多次重复计算，大大减少了程序的代码量。但在通常情况下，它的效率并不是太高。
一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数。
栈还有一个重要作用是在程序设计语言中实现递归。（可见栈可以用来实现递归）
阶乘函数
$\text{Fact}(n) = \begin{cases} 1 & \text{if } n = 0 \\ n \times \text{Fact}(n - 1) & \text{if } n > 0 \end{cases}$

int factorial(int n) {
    if (n == 0) {
        return 1; // 0 的阶乘为 1
    } else {
        return n * factorial(n - 1); // 递归调用
    }
}

Fibonacci数列

\text{Fibo}(n) = \begin{cases} 0 & \text{if } n = 0 \\ 1 & \text{if } n = 1 \\ \text{Fibo}(n - 1) + \text{Fibo}(n - 2) & \text{if } n > 1 \end{cases}

int fibonacci(int n) {
    if (n == 0) {
        return 0; // F(0) = 0
    } else if (n == 1) {
        return 1; // F(1) = 1
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2); // 递归调用
    }
}

Ackerman函数
Ackermann 函数的定义通常限制 m 和 n 为非负整数。
$\text{Ack}(m, n) = \begin{cases} n + 1 & \text{if } m = 0 \\ \text{Ack}(m - 1, 1) & \text{if } m > 0 \text{ and } n = 0 \\ \text{Ack}(m - 1, \text{Ack}(m, n - 1)) & \text{if } m > 0 \text{ and } n > 0 \end{cases}$

int ackermann(int m, int n) {
    while (m != 0) {
        if (n == 0) {
            n = 1; // 当 n 为 0 时，设置 n 为 1
        } else {
            // 递归调用，使用一个栈来存储 m 和 n 的值
            n = ackermann(m, n - 1);
        }
        m--; // 减小 m 的值
    }
    return n + 1; // 返回 n + 1
}

递归是程序设计中一个强有力的工具
1. 很多数学函数是递归定义的，比如以上三种；
2. 有的数据结构，如二叉树、广义表等，由于结构本身固有的递归特性，则它们的操作可递归地描述；
3. 还有一类问题，虽然问题本身没有明显的递归结构，但用递归求解比迭代求解更简单，如八皇后问题、Hanoi塔问题等。

八皇后问题
八皇后问题是一个经典的回溯算法问题，其目标是在 8×8 的国际象棋棋盘上放置 8 个皇后，使得它们彼此之间不能互相攻击。皇后可以在同一行、同一列或对角线上攻击其他皇后。因此，解决八皇后问题的关键在于找到一种摆放方式，使得任意两个皇后不在同一行、同一列或同一对角线上。

问题描述：

将 8 个皇后放置在 8×8 的棋盘上。
每一行放置一个皇后，最终找到一种摆放方案满足互不攻击的条件。

算法思路：

从第 1 行开始，每一行尝试放置一个皇后。
对于当前行的每一列，检查该位置是否安全（即，不与前面的皇后冲突）。
如果安全，则将皇后放置在该位置，递归地求解下一行。
如果不安全或无法为下一行找到合法位置，则回溯到上一步，尝试在该行的下一个位置放置皇后。

判定位置安全性：

检查该列是否已有皇后。
检查主对角线和副对角线上是否已有皇后（即，使用两条对角线数组记录状态）。

C语言实现

#include <stdio.h>
#include <math.h>

#define N 8

int board[N]; // board[i] 表示第 i 行皇后所在的列索引
int solution_count = 0; // 解的计数

// 判断当前位置是否安全
int isSafe(int row, int col) {
    for (int i = 0; i < row; i++) {
        // 检查列冲突和对角线冲突
        if (board[i] == col || abs(board[i] - col) == abs(i - row)) {
            return 0;
        }
    }
    return 1;
}

// 递归回溯求解八皇后问题
void solve(int row) {
    if (row == N) {
        solution_count++;
        printf("Solution %d:\n", solution_count);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                printf(board[i] == j ? " Q " : " . ");
            }
            printf("\n");
        }
        printf("\n");
        return;
    }

    for (int col = 0; col < N; col++) {
        if (isSafe(row, col)) {
            board[row] = col; // 放置皇后
            solve(row + 1); // 递归放置下一行的皇后
        }
    }
}

int main() {
    solve(0); // 从第 0 行开始
    printf("Total solutions: %d\n", solution_count);
    return 0;
}

运行结果
每种解法都会在棋盘上打印出 Q 表示皇后的位置，. 表示空位。最后输出总共找到的解的数量。

Hanoi塔问题
汉诺塔问题（Tower of Hanoi）是一个经典的递归问题，起源于一个古老的传说。假设有三根柱子和一组大小不同（最小圆盘编号为1，最大圆盘编号为n）的圆盘，圆盘一开始按从大到小的顺序（下面大，上面小）堆叠在第一根柱子上。目标是将所有圆盘移动到第三根柱子上，并满足以下规则：

每次只能移动一个圆盘。
圆盘只能放在柱子上，并且必须保持小圆盘在大圆盘之上。

问题描述
给定 n 个圆盘，设柱子分别为 A、B 和 C，将圆盘从 A 移动到 C，并使用 B 作为辅助柱子。
递归思路
汉诺塔问题可以用递归解决，通过将问题分解为子问题逐步求解：

基本情况：当只有一个圆盘时，直接将圆盘从 A 移动到 C。
递归情况：
(1) 先将 n-1 个圆盘从 A 移动到 B（使用 C 作为辅助柱）。
(2) 将第 n 个圆盘从 A 移动到 C。
(3) 将 n-1 个圆盘从 B 移动到 C（使用 A 作为辅助柱）。
每次递归地解决 n-1 个圆盘的子问题，直到所有圆盘都被移动到目标柱上。
C语言实现

#include <stdio.h>

void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", from, to);
        return;
    }
    hanoi(n - 1, from, aux, to);  // 将 n-1 个盘子从 from 移到 aux
    printf("Move disk %d from %c to %c\n", n, from, to); // 将第 n 个盘子移到目标柱
    hanoi(n - 1, aux, to, from);  // 将 n-1 个盘子从 aux 移到 to
}

int main() {
    int n;
    printf("Enter the number of disks: ");
    scanf("%d", &n);
    hanoi(n, 'A', 'C', 'B');
    return 0;
}

输出示例
若n=3

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

时间复杂度
汉诺塔问题的时间复杂度为 $O(2^n-1)$ ，因为每次增加一个盘子，操作数会翻倍。因此，汉诺塔问题适合用递归解法，但当 n 很大时计算量会非常大。

利用栈实现递归调用
（gpt给出的）
递归调用的定义：
递归是一种编程技术，其中一个函数直接或间接地调用自身。递归通常由两个部分组成：基例（终止条件）和递归步骤（即函数如何调用自身）。
栈的作用：
在计算机中，递归调用会使用调用栈（Call Stack）来管理函数调用。每当一个函数被调用时，系统会将该函数的状态（包括参数、局部变量、返回地址等）压入栈中。当函数执行完毕后，状态会从栈中弹出，并返回到调用该函数的位置。
栈的增长：
当递归调用发生时，每次调用都会在栈上增加一个新的帧（Frame）（调用栈中的每一层，它包含了特定函数调用的所有信息，如参数、局部变量、返回地址等）。如果递归深度较大，栈的空间可能会被耗尽，导致栈溢出（Stack Overflow）错误。
基例的重要性：
基例是防止无限递归的重要机制。如果没有适当的基例，递归会不断调用自身，直到耗尽栈空间。
步骤：
1. 初始化栈：创建一个栈，用于存储待处理的函数状态（如参数和局部变量）。
2. 入栈操作：将初始参数（或状态）压入栈中。
3. 循环处理：使用循环来处理栈中的元素：
  (1) 从栈中弹出一个状态。
  (2) 检查是否满足基例（一个或多个不需要再次递归的情况），如果满足，则处理结果（例如返回值）。
  (3) 如果不满足基例，计算递归步骤，并将新的状态（参数）压入栈中。
4. 返回结果：继续处理直到栈为空，最终返回结果。
  （书上的说法↓）
  为了保证递归函数正确执行，系统需设立一个“递归工作栈”作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个“工作记录”，其中包括所有的实在参数、所有的局部变量以及上一层的返回地址。每进入一层递归，就从栈顶弹出一个工作记录，则当前执行层的工作记录必是递归工作栈栈顶的工作记录，称这个记录为“活动记录”，并称指示活动记录的栈顶指针为“当前环境指针”。

掌握栈和队列的经典应用

栈的应用

递归调用↑
数制转换
十进制→八进制：从低位到高位产生八进制数的各个数位，从高位到地位顺序输出。

void conversion() {
  InitStack(S);
  scanf("%d", &N);
  while(N) {
    Push(S, N % 8);
    N = N / 8;
  }
  while(!StackEmpty(S)) {
    Pop(S, e);
    printf("%d", e);
  }
}

括号匹配的检验

在算法中设置一个栈，每读入一个括号，若是右括号，则要么使置于栈顶的最急迫的期待得以消解，要么是不合法的情况；
若是左括号，则作为一个新的更急迫的期待压入栈中，自然使原有的在栈中的所有未消解的期待的急迫性都降了一级。
另外，在算法的开始和结束时，栈都应该是空的。

行编辑程序
一个简单的行编辑程序的功能是：接受用户的从终端输入的程序或数据，并存入用户的数据区。由于用户在终端上进行输入时，不能保证不出差错，因此，若在编辑程序中，“每接受一个字符即存入用户数据区”的做法显然不是最恰当的。
较好的做法是，设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入出差错，并在发现有误时可以及时更正。
例如，当用户发现刚刚键入的一个字符是错的时，可补进一个退格符“#”，以表示前一个字符无效；如果发现当前键入的行内差错较多或难以补救，则可以键入一个退行符“@”，以表示当前行中的字符均无效。
例如，假设从终端接受了这样的两行字符：

1 2	whli##ilr#e(s#s) outcha@putchar(s++);

则实际有效的是下列两行：

1 2	while(s) putchar(s++);

为此，可设这个输入缓冲区为一个栈结构，每当从终端接受了一个字符之后先作如下判别：

如果它既不是退格符也不是退行符，则将该字符压入栈顶；
如果是一个退格符，则从栈顶删去一个字符；
如果它是一个退行符，则将字符栈清为空栈。

void LineEdit() {
  InitStack(S);
  ch = getchar(); //从终端接收第一个字符
  while(ch!=EOF) { //EOF为全文结束符
    while(ch!=EOF&&ch!='\n') {
      switch(ch) {
        case '#': Pop(S, c); break; //仅当栈非空时退栈
        case '@': ClearStack(S); break; //重置S为空栈
        default: Push(S,ch); break; //有效字符进栈，未考虑栈满情形
      }
      ch = getchar(); //从终端接收下一个字符
    }
    将从栈底到栈顶的栈内字符传送至调用过程的数据区;
    ClearStack(S); //重置S为空栈
    if(ch != EOF) ch = getchar();
  }
  DestroyStack(S);
}

迷宫求解
BFS用队列，DFS用栈。

//BFS
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int directions[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

bool isValid(int x, int y, int n, int m, vector<vector<int>>& maze, vector<vector<bool>>& visited) {
    return x >= 0 && x < n && y >= 0 && y < m && maze[x][y] == 0 && !visited[x][y];
}

int bfs(vector<vector<int>>& maze) {
    int n = maze.size();
    int m = maze[0].size();
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    queue<pair<int, int>> q;

    // Starting point
    q.push({0, 0});
    visited[0][0] = true;

    int steps = 0;
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; ++i) {
            auto [x, y] = q.front();
            q.pop();

            // Check if we reached the end
            if (x == n - 1 && y == m - 1) return steps;

            for (auto& dir : directions) {
                int nx = x + dir[0];
                int ny = y + dir[1];

                if (isValid(nx, ny, n, m, maze, visited)) {
                    q.push({nx, ny});
                    visited[nx][ny] = true;
                }
            }
        }
        steps++;
    }
    return -1; // If there's no path to the destination
}

//DFS
#include <iostream>
#include <vector>

using namespace std;

const int directions[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

bool dfs(vector<vector<int>>& maze, vector<vector<bool>>& visited, int x, int y, int n, int m) {
    // If out of bounds or not a path, return false
    if (x < 0 || x >= n || y < 0 || y >= m || maze[x][y] == 1 || visited[x][y]) return false;

    // Check if reached destination
    if (x == n - 1 && y == m - 1) return true;

    visited[x][y] = true;

    for (auto& dir : directions) {
        int nx = x + dir[0];
        int ny = y + dir[1];

        if (dfs(maze, visited, nx, ny, n, m)) {
            return true; // Path found
        }
    }

    return false; // No path found from this cell
}

bool hasPathDFS(vector<vector<int>>& maze) {
    int n = maze.size();
    int m = maze[0].size();
    vector<vector<bool>> visited(n, vector<bool>(m, false));

    return dfs(maze, visited, 0, 0, n, m);
}

1 2	//书上写的（用栈） //看不下去，太乱了

表达式求值
#是表达式的结束符，为了算法简洁，在表达式的最左边也虚设一个#构成整个表达式的一对括号。
(和)相遇时，表示括号内的运算已经完成，#和#相遇时表示整个表达式求值完毕。
两个工作栈，OPTR寄存运算符，OPND寄存操作数或运算结果。
对算术表达式3*(7-2)求值

步骤	`OPTR` 栈	`OPND` 栈	输入字符	主要操作
1	`#`		3*(7-2)#	`PUSH(OPND, '3')`
2	`#`	3	*(7-2)#	`PUSH(OPTR, '*')`
3	`#*`	3	(7-2)#	`PUSH(OPTR, '(')`
4	`#*(`	3	7-2)#	`PUSH(OPND, '7')`
5	`#*(`	3 7	-2)#	`PUSH(OPTR, '-')`
6	`#*(-`	3 7	2)#	`PUSH(OPND, '2')`
7	`#*(-`	3 7 2	)#	`OPERATE('7', '-', '2')`
8	`#*(`	3 5	)#	`POP(OPTR){消去一对括号}`
9	`#*`	3 5	#	`OPERATE('3', '*', '5')`
10	`#`	15	#	`RETURN(GETTOP(OPND))`

前缀、中缀、后缀表达式（书p129）
前缀表达式：- + A B - C D / E F
中缀表达式：A + B (C - D) - E / F
后缀表达式：A B C D - * + E F / -
前缀、中缀、后缀表达式分别对应表达式树的先序、中序、后序遍历。中缀表达式的括号是必须的。

转换中缀表达式为前缀表达式的步骤

首先构造一个运算符栈（也可放置括号），栈中的运算符（以括号为分界点）按照越往栈顶优先级不降低的原则进行排列。
从右至左扫描中缀表达式，从右边第一个字符开始判断：
- 如果当前字符是数字，则分析到数字串的结尾并将数字串直接输出。
- 如果是运算符，则比较优先级：
  - 如果当前运算符的优先级大于等于栈顶运算符的优先级（当栈顶是括号时，直接入栈），则将运算符直接入栈。
  - 否则，将栈顶运算符出栈并输出，直到当前运算符的优先级大于等于栈顶运算符的优先级（当栈顶是括号时，直接入栈），再将当前运算符入栈。
- 如果是括号，则根据括号的方向进行处理：
  - 如果是右括号，则直接入栈；
  - 否则，在遇到左括号之前，将所有的运算符全部出栈并输出；遇到右括号后将左右括号一起出栈（但不输出）。
重复步骤 2，直到扫描结束，将栈内剩余运算符全部出栈并输出。最后逆序输出字符串，中缀表达式就转换为前缀表达式了。

转换示例表格
将中缀表达式“1+((2+3)*4)-5”转换为前缀表达式。

中缀表达式	前缀表达式	运算符栈（栈顶）	说明
5	5	空	`5` 是数字串，直接输出
-	5	-	`-` 栈内无运算符，直接入栈
)	5	- )	`)` 直接入栈
4	5 4	- )	`4` 是数字串，直接输出
*	5 4	- ) *	`*` 栈顶是括号，直接入栈
)	5 4	- ) * )	`)` 直接入栈
3	5 4 3	- ) * )	`3` 是数字串，直接输出
+	5 4 3	- ) * ) +	`+` 栈顶是括号，直接入栈
2	5 4 3 2	- ) * ) +	`2` 是数字串，直接输出
(	5 4 3 2 +	- ) *	`(` 抵消栈中最后一个 `)` 并释放它们之间的 `+`
(	5 4 3 2 + *	-	`(` 抵消方法同上
+	5 4 3 2 + *	- +	`+` 优先级大于等于栈顶运算符，直接入栈
1	5 4 3 2 + * 1	- +	`1` 是数字串，直接输出
空	5 4 3 2 + * 1 + -	空	扫描结束，将栈内剩余运算符全部出栈并输出
空	- + 1 * + 2 3 4 5	空	逆序输出字符串

中缀表达式转后缀表达式的步骤

设定一个运算符栈。
假设表达式的结束符为 #，并预设运算符栈底元素也为 #。
扫描表达式，按以下规则处理每个字符：
- 如果当前字符是操作数，则直接添加到后缀表达式中。
- 如果当前字符是运算符且优先级高于栈顶运算符，则将其入栈；否则，将从栈顶开始，依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，然后将当前运算符入栈。
- 如果当前字符是结束符 #，则依次将栈中剩余的运算符出栈并添加到后缀表达式。
- 如果当前字符是左括号 (，则直接入栈。
- 如果当前字符是右括号 )，则从栈顶开始，依次将运算符出栈并添加到后缀表达式，直到遇到左括号 (。将 ( 出栈，但不添加到后缀表达式中，然后继续扫描表达式。

（详见gpt和王道p93，书上没看到有写,2018真题有考小题目）

队列的应用

离散事件模拟
书p65。讲的是模拟银行业务，不同的客户在随机时间到达，如果前边有其他客户还在办理业务则需要等待。计算客户的平均逗留时间。
每个窗口都被设置成一个队列，客户到达银行时排队排在人数最少的那个队伍后边。总之就是用到了队列。
队列在层次遍历（BFS）中需要用到。
数据缓冲区
CPU（即中央处理器，它包括运算器和控制器）资源的竞争。在一个带有多终端的计算机系统上，有多个用户需要CPU各自运行自己的程序，它们分别通过各自的终端向操作系统提出占用CPU的请求。操作系统通常按照每个请求在时间上的先后顺序，把它们排成一个队列，每次把CPU分配给队首请求的用户使用。当相应的程序运行结束或用完规定的时间间隔后，令其出队，再把CPU分配给新的队首请求的用户使用。这样既满足每个用户的请求，又使CPU能够正常运行。
（看一下书p49、p65，王道里也有内容别忘记）

五、二叉树、树和森林

二叉树、树、森林的定义以及它们之间的异同点

二叉树的定义

二叉树是一种树型结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒。

二叉树可以为空，或由一个根节点和两个互不相交的分别被称为左子树和右子树的二叉树组成。
二叉树是有序树。
(1) 若将其左、右子树颠倒，则成为另一棵不同的二叉树。
(2) 即使树中结点只有一棵子树，也要区分它是左子树还是右子树。
二叉树与度为2的有序树的区别：
(1) 度为2的树至少有3个结点（因为至少要有一个结点的度为2）。
(2) 度为2的有序树，若某个结点只有一个孩子，则这个孩子就无须区分其左右次序；而二叉树不管孩子是否是2个，都区分次序。
非空二叉树上的叶结点数等于度为2的结点数加1，即n0=n2+1。

证明： ①结点总数n=n0+n1+n2 ②除根节点外，其余结点都有一个分支进入，n=B（分支总数）+1 ③这些分支是由度为1或2的结点射出的，B=n1+2n2 ④n0+n1+n2=n1+2n2+1，则n0=n2+1。

度为m的树和m叉树的区别
度为m的树：至少有一个节点的度为m。
m叉树：允许所有节点的度<m，可以是空树。

	度为 m	m 叉树
结点数与度数	结点数 = 度数 + 1
第 i 层上结点数	第 i 层上最多有 $m^{i-1}$ 个结点（ $i \geq 1$ ）
高度为 h，总结点数	至多有 $\frac{m^h - 1}{m - 1}$ 个结点
高度为 h，总结点数	至少有 $h + m - 1$ 个结点	至少有 h 个结点
有 n 个结点，	最小高度 $\lceil \log_m(n(m - 1) + 1) \rceil$ ，根据 $n \leq \frac{m^h - 1}{m - 1}$ 得出
有 n 个结点，	最大高度 $n - m + 1$	最大高度 $n$

满二叉树
一棵高度为h，且有 $2^h-1$ 个结点的二叉树称为满二叉树，即二叉树中的每层都含有最多的结点。
（与树相似，二叉树也以递归的形式定义）

叶结点都集中在二叉树的最下一层
除叶结点外的每个结点度数均为2。
可以按照层次对满二叉树进行编号，自上而下，自左向右。对于编号为i的结点，
- 若有双亲（i>1），则其双亲为⌊i/2⌋
- 若有左孩子，则其左孩子为2i
- 若有有孩子，则其右孩子为2i+1

完全二叉树
高度为h，有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号为1～n的结点一一对应时，称为完全二叉树。

若i≤⌊n/2⌋，则结点i为分支节点，否则为叶结点。
叶结点只可能在层次最大的两层上出现。对于最大层次中的叶结点，都依次排列在该层最左边的位置上。
若有度为1的结点，则最多只可能有一个，且该结点只有左孩子而无右孩子。
按层次编号后，一旦出现某结点（编号为i）为叶结点或只有左孩子，则编号大于i的结点均为叶结点。
若n为奇数，则每个分支节点都有左孩子和右孩子；若n为偶数，则编号最大的分支节点（编号为n/2）只有左孩子，没有右孩子，其余分支节点左、右孩子都有。
（和满二叉树一样）对于编号为i的结点，
- 若有双亲（i>1），则其双亲为⌊i/2⌋
- 若有左孩子，则其左孩子为2i
- 若有有孩子，则其右孩子为2i+1
结点i所在层次（深度）为 $\lceil log_2(i+1) \rceil$ 或 $\lfloor log_2 i \rfloor + 1$ （情况与8一致，证明见下）
有n(n>0)个结点的完全二叉树的高度为 $\lceil log_2(n+1) \rceil$ 或 $\lfloor log_2 n \rfloor + 1$ 。

证明：① $2^{h-1}-1 < n \leq 2^h-1 或者 2^{h-1} \leq n < 2^h$ ②得 $2^{h-1} < n+1 \leq 2^h, \; h-1 < log_2 (n+1) \leq h \; 或者得 \; h-1 \leq log_2 n < h$ ③∴ $h=\lceil log_2(n+1) \rceil 或者 h=\lfloor log_2 n \rfloor +1$

二叉排序树
左子树上所有结点的关键字均小于根节点的关键字；右子树上所有结点的关键字均大于根节点的关键字；左子树和右子树又各是一棵二叉排序树。
平衡二叉树
树中任意一个结点的左子树和右子树的高度之差的绝对值不超过1。
正则二叉树
树中每个分支结点都有2个孩子，即树中只有度为0或2的结点。

树的定义

树是n(n≥0)个结点的有限集。当n=0时，称为空树。
在任意一个非空树中应满足：
1. 有且仅有一个特定的称为根的结点。
2. 当n>1时，其余结点可分为m(m>0)个互不相交的有限集 $T_1,T_2,\cdots,T_m$ ，其中每个集合本身又是一棵树，并且称为根的子树。
显然，树的定义是递归的（二叉树也是），即在树的定义中又用到了其自身，树是一种递归的数据结构。树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：
1. 树的根节点没有前驱，除根节点外的所有结点有且只有一个前驱。
2. 树中所有结点都可以有零个或多个后继。
树适用于表示具有层次结构的数据。树中的某个结点（除根节点外）最多只和上一层的一个结点（即其父结点）有直接关系，根节点没有直接上层结点，因此在n个结点的树中有n-1条边。而树中每个结点与其下一层的0个或多个结点（即其孩子结点）都有直接关系。
基本术语

        A
      / | \
    B   C   D
   / \  |  /|\
  E   F G H I J
 / \      |
K   L     M

祖先：考虑结点K，从根A到结点K的唯一路径上的所有其他结点，称为结点K的祖先。

注：双亲也算祖先！！！
子孙：如果结点B是结点K的祖先，则K是B的子孙。

注：孩子也算子孙！！！
双亲结点：路径上最接近K的结点E称为K的双亲。根A是树中唯一没有双亲的结点。
孩子结点：而K为E的孩子。
兄弟结点：有相同双亲的结点称为兄弟，K和L为兄弟。
堂兄弟结点：双亲在同一层的结点互为堂兄弟。

注意：G与E，F，H，I，J互为堂兄弟！！！！！
结点的度：树中一个结点的孩子个数称为该结点的度。
树的度：树中结点的最大度数（要存在以这个数为度的结点）称为树的度。
分支结点：度大于0的结点称为分支结点（又称非终端结点）。每个结点的分支数就是该结点的度。
叶结点：度为0（没有孩子结点）的结点称为叶结点（又称终端结点）。
结点的层次：从树根开始定义，根节点为第1层，它的孩子为第2层，以此类推。（↓）
结点的深度：就是结点所在的层次。（↓）
结点的高度：是以该结点为根的子树的高度。（↑）

结点的层次＝深度≠高度；树的最大层次＝深度＝高度。王道P129，书P120
有序树和无序树：树中结点的各子树从左到右是有次序的，不能互换，称该树为有序树，否则称为无序树。若将有序树的子结点位置互换，则变成一棵不同的树。
路径：树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的。
路径长度：是路径上所经过的边的个数。

树的性质

树的结点数n等于所有结点的度数之和加1。树中所有结点的度数之和等于树中的边数之和。
（其他在二叉树的“度为m的树和m叉树的区别”表格里有）

森林的定义

森林是m(m≥0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。由此，也可以森林和树相互递归的定义来描述树。

二叉树、树、森林的异同点

特性	树	二叉树	森林
根节点	有且仅有一个根节点	有且仅有一个根节点	每棵树有一个根节点
子节点数	不限	每个节点最多两个子节点	每棵树的节点数不限
节点顺序	没有严格顺序	子节点有左右之分	各棵树和节点无顺序
连通性	必须连通	必须连通	每棵树是连通的
结构关系	是一种特殊的无向无环图	是树的一种特殊类型	是多个树的集合
应用	文件系统、家谱等	表达式树、二叉搜索树等	多棵树的集合作为林

二叉树的实现（包括）

理解二叉树采用顺序存储结构和链式存储结构的差异性

顺序存储结构

二叉树的顺序存储是指用一组连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在一维数组下标为i-1的分量中。（书上讲的就是i-1哦）

     1
   /   \
  2     3
   \     \
    4     5
   /
  6

1 2 3 0 4 0 5 0 0 6

会导致很多空间被浪费。在最坏的情况下，一个深度为k且只有k个结点的单支树（树中不存在度为2的结点）需要长度为 $2^k-1$ 的一维数组。因此顺序存储结构仅适用于完全二叉树。

链式存储结构

由于顺序存储的空间利用率低，因此二叉树一般都采用链式存储结构，用链表结点来存储二叉树中的每个结点。
链表的头指针指向二叉树的根节点。
二叉链表
由二叉树的定义得知，二叉树的结点由一个数据元素和分别指向其左、右子树的两个分支构成，则表示二叉树的链表中的结点至少包含3个域：数据域和左、右指针域。

lchild data rchild

注意：容易证得，在含有n个结点的二叉链表中有n+1个空链域。
三叉链表
有时，为了便于找到结点的双亲，则还可以在结点结构中增加一个指向其双亲结点的指针域。

lchild data parent rchild
如果要找结点x的双亲结点，在三叉链表很容易实现，而在二叉链表中则需从根指针出发巡查。

二叉树的遍历（四种）

掌握二叉树的四种遍历，并具有能够依赖遍历完成对二叉树进行操作的能力
书p128
二叉树—层序、前序中序后序(递归、非递归)遍历详解这篇博客光是先序遍历的非递归算法就包含了两种，不错，可以看一下

遍历二叉树是以一定规则将二叉树中结点排列成一个线性序列，得到二叉树中结点的先序序列或中序序列或后序序列。这实质上是对一个非线性结构进行线性化操作，使每个结点（除第一个结点和最后一个外）在这些线性序列中有且仅有一个直接前驱和直接后继。

L->遍历左子树；D->访问根节点；R->遍历右子树。
则可有DLR、LDR、LRD、DRL、RDL、RLD这6种方案。
若限定先左后右，则只有前3种情况。
基于二叉树的递归定义，可得下述遍历二叉树的递归定义。

先序遍历

先序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则

访问根节点；
先序遍历左子树；
先序遍历右子树。

递归算法

void preorder(BiTree T) {
    if (T!=NULL) {
    visit(T);                  // 访问根节点
    preorder(T->lchild);      // 递归遍历左子树
    preorder(T->rchild);     // 递归遍历右子树
}

非递归算法
第一种，这个节点，再右节点进栈，左节点进栈

void preorderIterative(TreeNode* root) {
    if (root == nullptr) return;
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        cout << node->val << " ";      // 访问根节点
        if (node->right) s.push(node->right);   // 先将右子节点压栈
        if (node->left) s.push(node->left);     // 再将左子节点压栈
    }
}

第二种，传统（王道p148）。遍历左子结点的链，直到没有左子结点，然后回溯处理右子结点。

void preorderIterativeAlt(TreeNode* root) {
    if (root == nullptr) return;
    stack<TreeNode*> s;
    TreeNode* current = root;
    while (current != nullptr || !s.empty()) {
        while (current != nullptr) {
            cout << current->val << " ";   // 访问当前节点
            s.push(current);               // 当前节点入栈
            current = current->left;       // 向左子树移动
        }
        current = s.top();
        s.pop();
        current = current->right;          // 处理右子树
    }
}

中序遍历

中序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则

中序遍历左子树；
访问根节点；
中序遍历右子树。

递归算法

void inorderRecursive(TreeNode* root) {
    if (root == nullptr) return;
    inorderRecursive(root->left);       // 递归遍历左子树
    cout << root->val << " ";           // 访问根节点
    inorderRecursive(root->right);      // 递归遍历右子树
}

非递归算法
第一种，类似于先序遍历的第一种，只不过引入了标记。（已经用很多特殊的二叉树例子运行完整代码来验证过了，且手模了一下，没发现什么问题）
每次取出栈顶结点：

如果节点未被标记，意味着我们还没有访问它。因此：
- 按照中序遍历的顺序，需要先遍历左子树，再访问根节点，最后遍历右子树。
- 为此，我们首先将右子结点入栈（如果存在），然后将当前结点重新入栈并标记为已访问，最后将左子结点入栈（如果存在）。
如果节点已被标记，意味着这是第二次从栈中取出它。此时，我们可以访问该节点，因为它的左子树已经处理过了。、
这样处理的效果就是，在中序遍历的顺序上保证了左子树→根节点→右子树的顺序。

struct StackNode {
    TreeNode* node;
    bool visited;  // true 表示该节点的左子树已访问
    StackNode(TreeNode* n, bool v) : node(n), visited(v) {}
};

void inorderIterativeWithMark(TreeNode* root) {
    if (root == nullptr) return;

    stack<StackNode> s;
    s.push(StackNode(root, false));  // 初始根节点未访问

    while (!s.empty()) {
        StackNode current = s.top();
        s.pop();

        if (current.visited) {
            cout << current.node->val << " "; // 访问已标记的当前节点
        } else {
            // 将节点标记为已访问并重新压入栈中
            if (current.node->right) s.push(StackNode(current.node->right, false)); // 右子节点
            s.push(StackNode(current.node, true));  // 标记当前节点为已访问（表示左子树已访问）
            if (current.node->left) s.push(StackNode(current.node->left, false));   // 左子节点
        }
    }
}

第二种，（传统，王道p148），类似于先序遍历的第二种

void inorderIterative(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* current = root;
    while (current != nullptr || !s.empty()) {
        while (current != nullptr) {
            s.push(current);
            current = current->left;
        }
        current = s.top();
        s.pop();
        cout << current->val << " ";    // 访问根节点
        current = current->right;
    }
}

后序遍历

后序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则

后序遍历左子树；
后序遍历右子树；
访问根节点。

递归算法

void postorderRecursive(TreeNode* root) {
    if (root == nullptr) return;
    postorderRecursive(root->left);     // 递归遍历左子树
    postorderRecursive(root->right);    // 递归遍历右子树
    cout << root->val << " ";           // 访问根节点
}

非递归算法
第一种（双栈）

void postorderIterative(TreeNode* root) {
    if (root == nullptr) return;
    stack<TreeNode*> s1, s2;
    s1.push(root);
    while (!s1.empty()) {
        TreeNode* node = s1.top();
        s1.pop();
        s2.push(node);
        if (node->left) s1.push(node->left);
        if (node->right) s1.push(node->right);
    }
    while (!s2.empty()) {
        cout << s2.top()->val << " ";
        s2.pop();
    }
}

第二种，（传统，王道p167-168，03题）

void postorderIterative(TreeNode* root) {
    if (root == nullptr) return;
    
    stack<TreeNode*> s;
    TreeNode* prev = nullptr;  // 记录上一个访问的节点
    
    while (!s.empty() || root != nullptr) {
        if (root != nullptr) {
            s.push(root);  // 将当前节点压入栈中
            root = root->left;  // 继续向左子树深入
        } else {
            TreeNode* node = s.top();  // 获取栈顶节点
            // 如果当前节点的右子树未被访问过，先访问右子树
            if (node->right != nullptr && node->right != prev) {
                root = node->right;
            } else {
                cout << node->val << " ";  // 后序遍历的访问节点
                prev = node;  // 标记当前节点为已访问
                s.pop();  // 弹出栈顶节点
            }
        }
    }
}

为什么需要标记？
答：如果栈顶节点的右子树已经访问过，说明当前节点已经是后序遍历顺序中的最后一个步骤（即根节点），我们可以访问这个节点并将其从栈中弹出。

层次遍历

利用队列，BFS

void levelOrder(TreeNode* root) {
    if (root == nullptr) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        cout << node->val << " ";       // 访问节点
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

二叉树的遍历和表达式的关系

书p129
前缀表达式（波兰式）对应先序遍历
中缀表达式对应中序遍历
后缀表达式（逆波兰式）对应后序遍历

线索二叉树

lchild

LTag

data

RTag

rchild

LTag = \begin{cases} 0 & lchild \text{ 指示结点的左孩子} \\ 1 & lchild \text{ 指示结点的前驱} \end{cases} \quad RTag = \begin{cases} 0 & rchild \text{ 指示结点的右孩子} \\ 1 & rchild \text{ 指示结点的后继} \end{cases}

以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针，叫做线索。
加上线索的二叉树称之为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。
在后序线索树上招后继时需知道结点的双亲，即需带标志域的三叉链表作存储结构。
若在某程序中所用二叉树需经常遍历或查找结点在遍历所得线性序列中的前驱和后继，应采用线索链表作存储结构。
为方便起见，仿照线性表的存储结构，在二叉树的线索链表上也添加一个头结点，并令其lchild域的指针指向二叉树的根结点，其rchild域的指针指向中序遍历时访问的最后一个结点；令二叉树中序序列中的第一个结点的lchild域指针和最后一个结点rchild域的指针均指向头结点。这好比为二叉树建立了一个双向线索链表，既可以从第一个结点其顺后继进行遍历，也可从最后一个结点起顺前驱进行遍历。

中序线索化

// 中序线索化二叉树
void inThread(ThreadedTreeNode* root, ThreadedTreeNode*& pre) {
    if (!root) return;
    // 先线索化左子树
    inThread(root->left, pre);
    
    // 线索化当前节点
    if (!root->left) {
        root->lTag = true;  // 左子树为空，指向前驱
        root->left = pre;
    }
    if (pre && !pre->right) {
        pre->rTag = true;  // 右子树为空，指向后继
        pre->right = root;
    }

    pre = root;  // 更新前驱节点

    // 线索化右子树
    inThread(root->right, pre);
}

中序线索化后，找结点a的后继

若其右标志为“1”，则右链为线索，指示其后继；
否则遍历右子树中第一个访问的结点（右子树中最左下的结点）。找到其右子树的根节点b，然后顺其左指针往下至其左标志为1（无左孩子，且线索指向b）的结点，即为a的后继。

中序线索化后，找结点a的前驱

若其左标志为“1”，则左链为线索，指示其前驱；
否则遍历左子树时最后访问的一个结点（左子树中最右下的结点）为其前驱。

先序线索化

// 先序线索化二叉树
void preThread(ThreadedTreeNode* root, ThreadedTreeNode*& pre) {
    if (!root) return;
    
    // 线索化当前节点
    if (!root->left) {
        root->lTag = true;
        root->left = pre;
    }
    if (pre && !pre->right) {
        pre->rTag = true;
        pre->right = root;
    }
    pre = root;

    // 先线索化左子树
    if (!root->lTag) preThread(root->left, pre);

    // 后线索化右子树
    if (!root->rTag) preThread(root->right, pre);
}

先序线索化后，找结点a的后继

若有左孩子，则左孩子就是其后继；
若无左孩子，但有右孩子，则右孩子就是其后继；
若为叶结点，则右链域直接指示了结点的后继。

先序线索化后，找结点a的前驱（书上没有，自己写的）

若无左孩子，则左链域直接指示了结点的前驱；
若有左孩子，
①若a无双亲结点，即其为整棵树的根节点，则无前驱；
②若a有双亲结点，且a为双亲结点的左孩子，则其前驱为双亲结点；
③若a有双亲结点，且a为双亲结点的右孩子，则其前驱为双亲结点的左子树按照先序遍历下的最后一个结点，不一定是左子树的最右侧结点，因为可以是最右侧结点b的左孩子c（b没有右孩子的情况下）

注：这个应该也需要三叉链表，因为需要知道其双亲结点。

后序线索化

// 后序线索化二叉树
void postThread(ThreadedTreeNode* root, ThreadedTreeNode*& pre) {
    if (!root) return;
    
    // 先线索化左子树
    if (!root->lTag) postThread(root->left, pre);
    
    // 再线索化右子树
    if (!root->rTag) postThread(root->right, pre);
    
    // 线索化当前节点
    if (!root->left) {
        root->lTag = true;
        root->left = pre;
    }
    if (pre && !pre->right) {
        pre->rTag = true;
        pre->right = root;
    }

    pre = root;  // 更新前驱节点
}

后序线索化后，找结点a的后继

若结点a是二叉树的根，则其后继为空；
若结点a是①其双亲结点的右孩子或是②其双亲的左孩子且其双亲没有右子树，则其后继即为双亲结点；
若结点a是其双亲的左孩子，且其双亲有右子树，则其后继为双亲的右子树上按照后序遍历列出的第一个结点。

注：可见，在后序线索化树上找后继时需知道结点双亲，即需带标志域的三叉链表作存储结构。

后序线索化后，找结点a的前驱（书上没有，自己写的）

若结点a无左孩子，则其前驱为左链域所指示的结点。
若结点a有左孩子，若其有右孩子则前驱为右孩子，若其无右孩子则前驱为左孩子。

二叉树结构下的应用及扩展（例如）

掌握利用二叉树及其扩展下的检索技术；掌握Huffman编码、堆的实现及应用

二叉检索树

二叉排序树(BST)、二叉查找树、二叉搜索树

二叉排序树或者是一棵空树；或者是具有下列性质的二叉树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树。

通常可取二叉链表作为二叉排序树的存储结构。
和次优二叉树相对，二叉排序树是一种动态树表。其特点是，树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字（所以结点不能重复）等于给定值的结点时再进行插入。
新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。

查找的关键字序列：{45, 24, 53, 45, 12, 24, 90}
生成的二叉排序树：
        45
      /    \
     24     53
    /         \
   12         90

二叉排序树既拥有类似于折半查找的特性，又采用了链表作为存储结构，因此是动态查找表的一种适宜表示。
同样，在二叉排序树上删去一个结点也很方便。
对于一般的二叉树来说，删去树中一个结点是没有意义的。因为它将使以被删结点为根的子树成为森林，破坏了整棵树的结构。
然而，对于二叉排序树，删去树上一个结点相当于删去有序序列中的一个记录，只要在删除某个结点之后依旧保持二叉排序树的特性即可。
设被删结点为*p，其双亲结点为*f，且不失一般性，可设*p是*f的左孩子。

若*p结点为叶子结点，即P_L（*p的左子树）和P_R（右子树）均为空树。由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可。
若*p结点只有左子树P_L或者只有右子树P_R，此时只要令P_L或P_R直接成为其双亲结点*f的左子树即可。显然，作此修改也不破坏二叉排序树的特性。
若*p结点的左子树和右子树均不空。

ASL(书P231)
查找成功的平均查找长度ASL=(Σ每层结点数*深度)/结点总数
二叉排序树的查找效率，主要取决于树的高度。

（和折半查找的判定树相同，最好情况，和 $log_2n$ 成正比）若二叉排序树的左、右子树的高度之差的绝对值不超过1（平衡二叉树），它的平均查找长度为 $O(log_2n)$ 。
（先后插入的关键字有序，单支树，和顺序查找相同，最坏情况，= $\frac{n+1}{2}$ ）若二叉排序树是一个只有右（左）孩子的单支树（类似于有序的单链表），则其平均查找长度为O(n)。
随机情况下，二叉排序树的平均查找长度和logn是等数量级的。

二分（折半）查找的判定树唯一，而二叉排序树的查找不唯一，相同的关键字其插入的顺序不同可能生成不同的二叉排序树（如有序，则生成单支树）。
当有序表是静态查找表时，宜用顺序表作为其存储结构，而采用二分查找实现其查找操作；若有序表是动态查找表，则应选择二叉排序树作为其逻辑结构。

2-3-4树

oiwiki 2-3树
 oiwiki 2-3-4树

B树(B-)

oiwiki B树

B 树是一种平衡的多路搜索树，广泛用于数据库和文件系统中，以支持高效的数据插入、删除和查找操作。B 树的设计目标是最大限度减少磁盘 I/O 操作，因此特别适合处理大量数据的场景。

B 树的结构与特性
B 树的关键特性如下：

多路搜索树：
- B 树的每个结点可以包含多个数据项和多个子结点。
- 对于一个 m 阶的 B 树，每个结点最多可以有 m 个子结点，至少有 ⌈m/2⌉ 个子结点（除了根结点可以少于此数目）。
数据项的有序性：
- 每个结点中的数据项按从小到大的顺序排列。
- 每个子树对应的值范围在当前结点的数据项之间。
  - 比如，如果结点包含数据项 [A, B, C]，则其子树的数据项满足：
    - 第一个子树的数据项小于 A；
    - 第二个子树的数据项在 A 和 B 之间；
    - 第三个子树的数据项在 B 和 C 之间；
    - 第四个子树的数据项大于 C。
平衡性：
- B 树是平衡树，所有叶子结点的深度相同，从根到任一叶子结点的路径长度一致。这使得查找的时间复杂度在 O(log n) 范围内。
高度控制：
- B 树的高度相对较低，通常通过较大的分支因子（m 的值较大）来控制树的高度，使得每个结点包含更多数据，从而减少查找路径长度。
- 对于磁盘存储，树的高度越低，磁盘 I/O 次数越少，因此性能越高。

B 树的基本操作
B 树的基本操作主要包括查找、插入和删除：

查找：
查找操作与二叉搜索树类似，通过与每个结点的数据项逐一比较，进入对应范围的子树。由于 B 树是平衡的，所以查找的时间复杂度为 O(log n)。
插入：
插入操作包括以下几个步骤：
- 定位叶结点：先从根结点查找，找到适合插入新数据项的叶结点。
- 插入数据项：将新数据项插入到叶结点中，并保持结点中的数据项顺序。
- 分裂结点：如果插入后结点的数据项数量超过 m-1，则该结点需要分裂。分裂时，选择中间的数据项上移到父结点，分裂后的两个新结点分别成为父结点的子结点。
- 上溢处理：如果父结点也满了，则父结点同样需要分裂，这可能导致分裂操作逐层向上传播，甚至需要分裂根结点，从而使树的高度增加。
删除：
删除操作分为以下几种情况：
- 删除叶结点的数据项：直接删除数据项即可，但要检查该结点是否满足最小数据项数要求（即至少含有 ⌈m/2⌉ 个数据项）。
- 删除内部结点的数据项：可以通过以下策略进行替换：
  - 找到左子树的最大值或右子树的最小值来替换该数据项。
  - 然后在对应子树中递归删除这个替换的数据项。
- 借用和合并：如果删除后某结点数据项不足，可从相邻的兄弟结点中“借”一个数据项，或将该结点与兄弟结点合并。如果合并导致父结点数据项不足，则继续向上递归调整，直到树重新平衡。

B 树的应用场景
B 树广泛应用于数据库系统、文件系统、键-值存储等，因为它能够有效地支持大量数据的动态存储与管理，并优化磁盘 I/O 操作。在实际应用中，通常会用 B+ 树或 B* 树，因为它们对顺序访问进行了进一步优化。

B 树的优点

平衡性：自动保持平衡，避免了二叉搜索树退化为链表的情况。
高效的磁盘访问：B 树的高度较低，结点中包含多个数据项，因此每次磁盘读取获取更多数据，有效减少磁盘 I/O 次数。
支持范围查找：B 树中的数据项有序排列，因此支持按范围查找（例如查找所有小于某个值的项）。

B 树的缺点

实现复杂性：插入、删除需要多种特殊情况处理，尤其是分裂和合并操作。
内存利用率：B 树的内存利用率不如二叉树，因为每个结点中可能存在未使用的指针。

通过这些特性，B 树能够很好地管理大量有序数据，使得查找、插入和删除都在 O(log n) 时间内完成，非常适合高效管理大规模数据。

B树和2-3-4树有什么区别？

2-3-4 树是 B 树的一个特例，阶数为 4 的 B 树。

2-3-4 树和 B 树的主要区别在于 B 树的阶数 m 更为灵活，而 2-3-4 树的阶数固定为 4。

在结构上，2-3-4 树的结点数目（子结点和数据项数目）正好符合 B 树的一个具体实现。

B+树

oiwiki B+树

Huffman编码

路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。
路径长度：路径上的分支数目。
权：树中结点常常被赋予一个表示某种意义的数值，称为该结点的权。
带权路径长度：从树的根到一个结点的路径长度与该结点上权值的乘积，称为该结点的权。
树中所有叶结点的带权路径长度之和称为该树的带权路径长度，记为 $WPL=\sum\limits_{i=1}^{n}w_i l_i$ 。
哈夫曼树：在含有n各带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树。
哈夫曼树的构造：给定n各权值分别为 $w_1, w_2, \cdots, w_n$ 的结点，构造哈夫曼树的算法描述如下：
1. 将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F。
2. 构造一个新结点，从F中选取两棵根节点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。
3. 从F中删除刚才选出的两棵树，同时将新得到的树加入F中。
4. 重复步骤2和3，直至F中只剩下一棵树为止。
哈夫曼树的性质：从上述构造过程中可以看出哈夫曼树具有如下特点：
1. 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大。
2. 构造过程中共新建了n-1个结点（双分支结点），因此哈夫曼树的结点总数为2n-1。
3. 每次构造都选择2棵树作为新结点的孩子，因此哈夫曼树中不存在度为1的结点。
哈夫曼编码：
- 固定长度编码：在数据通信中，若对每个字符用相等长度的二进制表示，称这种编码方式为固定长度编码。
- 可变长度编码：若允许对不同字符用不等长的二进制位表示，则这种编码方式称为可变长度编码。
- 可变长度编码比固定长度编码要好得多，其特点是对频率高的字符赋以短编码，而对频率较低的字符则赋以较长一些的编码，从而可以使字符的平均编码长度减短，起到压缩数据的效果。
- 前缀编码：若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。
  - e.g. 0, 10, 110
- 可以利用二叉树来设计二进制前缀编码。
- 哈夫曼编码是一种非常有效的数据压缩编码。
  
  这棵哈夫曼树的WPL=1×45+3×(12+13+16)+4×(5+9)=224
  此处的WPL可视为最终编码得到二进制编码的长度，共224位。若采用3位固定长度编码，则得到的二进制编码长度为300位(45+12+13+16+5+9=100)，因此哈夫曼树可以设计出总长度最短的二进制前缀编码。
- 左分支和右分支究竟是表示0还是表示1没有明确规定，因此构造出的哈夫曼树并不唯一，但各哈夫曼树的带权路径长度WPL相同且为最优。此外，如有若干权值相同的结点，则构造出的哈夫曼树更可能不同，但WPL必然相同且为最优。

堆

n个关键字序列L[1…n]称为堆，当且仅当该序列满足：
1. L(i)≥L(2i)且L(i)≥L(2i+1) （大根堆）或
2. L(i)≤L(2i)且L(i)≤L(2i+1) (1≤i≤⌊n/2⌋) （小根堆）
堆一定是完全二叉树。
堆的插入
先将新结点放在堆的末端，再对这个新结点向上执行调整操作。

平衡二叉树的定义和意义(AVL)

为了避免树的高度增长过快，降低二叉排序树的性能，规定在插入和删除结点时，要保证任意结点的左、右子树高度差的绝对值不超过1，将这样的二叉树称为平衡二叉树，也称AVL树。
平衡二叉树可以是空树，或是：左右子树都是平衡二叉树且左右子树的高度差的绝对值不超过1。

平衡因子的定义

定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是-1、0或1。

平衡二叉树的旋转操作

插入

每次调整的对象都是最小不平衡树，即以插入路径上离插入结点最近的平衡因子绝对值大于1的结点作为根的子树。
LL平衡旋转（右单旋转）
由于在结点A的左孩子（L）的左子树（L）上插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右的旋转操作。
将A的左孩子B向右上旋转代替A成为根结点，将A向右下旋转成为B的右孩子，而B的原右子树则作为A的左子树。
RR平衡旋转（左单旋转）
由于在结点A的右孩子（R）的右子树（R）上插入了新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要一次向左的旋转操作。
将A的右孩子B向左上旋转代替A成为根结点，将A向左下旋转成为B的左孩子，而B的原左子树则作为A的右子树。
LR平衡旋转（先左后右双旋转）
由于在结点A的左孩子（L）的右子树（R）上插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。
先将A的左孩子B的右子树的根结点C向左上旋转提升到B的位置，然后把C向右上旋转提升到A的位置。
RL平衡旋转（先右后左双旋转）
由于在结点A的右孩子（R）的左子树（L）上插入了新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。
先将A的右孩子B的左子树的根结点C向右上旋转提升到B的位置，然后把C向左上旋转提升到A的位置。

LR和RL旋转时，新结点究竟是插入C的左子树还是插入C的右子树不影响旋转操作过程。

平衡二叉树的删除

若删除w导致了不平衡，则从结点w开始向上回溯，找到第一个不平衡的结点z（即最小不平衡树）；
接下来对z的操作与插入操作的调整方式一样。
若调整后的子树的高度减1，则可能需要对z的祖先结点进行平衡调整，甚至回溯到根结点（导致树高减1）。

平衡二叉树的查找

在平衡二叉树上进行查找的过程与二叉排序树的相同。因此，在查找过程中，进行关键字的比较次数不超过树的深度。
假设以 $n_k$ 表示深度为h的平衡二叉树中含有的最少结点数。（最多结点数显然是满二叉树的情况）
显然，有 $n_0=0, n_1=1, n_2=2$ ，并且有 $n_h=n_{h-2}+n_{h-1}+1$ 。依次推出 $n_3=4,n_4=7,n_5=12,\cdots$ 。
含有n个结点的平衡二叉树的最大深度为 $O(log_2n)$ ，因此平均查找效率为 $O(log_2n)$ 。
该结论可用于求解给定结点数的平衡二叉树的查找所需的最多比较次数（或树的最大高度）。

树和森林的存储结构

掌握树、森林能够采用的各种存储方式的差异性

树和森林在计算机中有多种不同的存储方式，每种方式各有优缺点，适合不同的应用场景。下面介绍几种常见的树和森林的存储方法及它们的差异性。

1. 链式存储方式

链式存储方式使用指针来表示树结点之间的父子关系，常见的有双亲表示法、孩子表示法和孩子兄弟表示法。链式存储适合不定度的树（即每个结点的子结点数不确定的树），例如文件目录结构、HTML DOM 树等。

a. 双亲表示法
每个结点使用一个结构体表示，并包含一个指向其父结点的指针或索引。适合查找父结点，但查找子结点效率较低。

结构：每个结点存储自己的值和父结点的指针或索引。
优点：利用了每个结点（根结点除外）只有唯一双亲地性质，查找父结点很方便。
缺点：查找子结点不方便，需要遍历整个数组来找到该结点的所有子结点。

b. 孩子表示法
为每个结点分配一个孩子链表，链表中的每个结点包含指向一个子结点的指针。

结构：每个结点存储自己的值，以及一个链表指针指向其所有的子结点。
优点：方便查找子结点，适合不定度的树。
缺点：存储结构较为复杂，查找父结点不方便，需要从根结点遍历。

c. 孩子兄弟表示法（又称二叉树表示法）
将树转化为二叉树来存储。每个结点使用两个指针：一个指向其第一个孩子，另一个指向其下一个兄弟。这种方法特别适合存储森林结构。

结构：每个结点存储自己的值，一个孩子指针和一个兄弟指针。
优点：适合任意度的树，且能够高效地存储森林结构。
缺点：编程逻辑复杂，查找特定的孩子结点或兄弟结点需要遍历。

2. 其他存储方式

a. 数组表示法（用于完全二叉树）
对完全二叉树的结点按层次从左到右编号，可以使用数组存储。对于父结点在数组中的索引（从0开始）为i：

左子结点在位置2*i + 1
右子结点在位置2*i + 2

这种方法适合完全二叉树或近似完全二叉树。

优点：占用空间小，定位子结点和父结点的效率高。
缺点：如果是一般的树或不规则的二叉树，会浪费大量空间，且不适合查找任意度的树。

b. 邻接矩阵或邻接表（用于森林）
可以用邻接矩阵或邻接表来表示森林，将每棵树的结点当作一个图的顶点，将父子关系当作图的边。

优点：适合表示复杂的关系，特别是用于图结构的算法。
缺点：邻接矩阵会占用大量空间；邻接表适合稀疏图结构，不适合高密度的父子关系。

存储方式的对比总结

存储方式	适用场景	优点	缺点
双亲表示法	查找父节点频繁的场景	查找父节点方便	查找子节点效率低
孩子表示法	查找子节点频繁、不定度的树结构	查找子节点方便	查找父节点困难，数据结构复杂
孩子兄弟表示法	不定度的树、森林	适合任意度的树，能存储森林	逻辑复杂，查找指定孩子或兄弟节点时不便
数组表示法	完全二叉树、近似完全二叉树	占用空间小，定位节点快	不适合非完全二叉树，存储一般树浪费空间
邻接矩阵/表	复杂的森林结构、图结构	表示关系灵活，特别适合图算法	邻接矩阵空间大；邻接表不适合高密度父子关系的树

根据树的结构和操作需求选择合适的存储方式，可以有效提高数据操作的效率并节省空间。

树和森林的遍历

掌握树、森林在遍历方面和二叉树的不同以及相关性

树和森林的遍历是理解数据结构中结点访问顺序的关键部分。树的遍历有不同的策略，包括深度优先遍历（如先序、中序、后序遍历）和广度优先遍历（层次遍历）。对于森林，遍历也遵循类似的策略。与二叉树的遍历相比，树和森林的遍历在实现上有一些独特的地方，尤其是当树的度（每个结点的子结点数）不固定时。

1. 树的遍历

树的遍历与二叉树的遍历类似，但树的每个结点可能有多个子结点，因此其遍历方式会有所调整。树的遍历方法一般包括先根遍历、后根遍历和层次遍历，但在每个结点的子结点的访问顺序上有所不同。

a. 树的先根遍历
对于一般树（多子树的树），前根遍历访问顺序为：
（若树非空）

访问根结点。
遍历根结点的每一个子结点，按从左到右的顺序递归遍历每个子结点。

其遍历序列与这棵树相应的二叉树的先序序列相同。

b. 树的后根遍历
对于一般树的后根遍历，访问顺序为：
（若树非空）

递归遍历每个子结点（从左到右）。
访问根结点。

其遍历序列与这棵树相应的二叉树的中序序列相同。

c. 树的层次遍历
树的层次遍历类似于二叉树的层次遍历，按层次逐层从上到下、从左到右访问每个结点。这通常通过队列来实现：

将根结点加入队列。
取出队列中的结点并访问它。
如果该结点有子结点，将子结点按顺序加入队列。

3. 森林的遍历

森林是多个树的集合，因此森林的遍历可以看作是对每一棵树进行遍历。在遍历森林时，通常会对森林中的每一棵树单独进行遍历，遍历的方法与树的遍历方法相同。

先序遍历森林
（若森林非空）

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

其遍历序列与这个森林对应的二叉树的先序序列相同。

中序遍历森林（类似于树的后根遍历，先子树后根）
（若森林非空）

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

其遍历序列与这个森林相应的二叉树的中序序列相同。

森林与二叉树的转换

二叉树和树都可以用二叉链表作为存储结构。从物理结构上看，树的孩子兄弟表示法与二叉树的二叉链表表示法是相同的，因此可以用同一存储结构的不同解释将一棵树转换为二叉树。

1. 树转换为二叉树

树转换为二叉树的画法：

在兄弟结点之间加一条线；
对每个结点，只保留它与第一个孩子的连线，而与其他孩子的连线全部抹掉；
以树根为轴心，顺时针旋转45°。

2. 森林转换为二叉树
将森林转换为二叉树的规则与树类似。先将森林中的每棵树转换为二叉树，由于任意一棵树对应的二叉树的右子树必空，若把森林中第二棵树根视为第一棵树根的右兄弟，即将第二棵树对应的二叉树当作第一棵二叉树根的右子树，将第三棵树对应的二叉树当作第二课二叉树根的右子树，以此类推，就可以将森林转换为二叉树。
森林转换为二叉树的画法：

将森林中的每棵树转换成相应的二叉树；
每棵树的根也可视为兄弟关系，在每棵树的根之间加一根连线；
以第一棵树的根为轴心，顺时针旋转45°。

3. 二叉树转换为森林

森林结构的应用（例如）

并查集

理解并查集的意义，以及掌握并查集的基本操作的实现

并查集的概念
并查集是一种简单的集合表示，它支持以下3种操作：

Initia(S): 将集合S中的每个元素都初始化为只有一个单元素的子集合。
Union(S, Root1, Root2): 把集合S中的子集合Root2并入子集合Root1。要求Root1和Root2互不相交，否则不执行合并。
Find(S, x): 查找集合S中单元素x所在的子集合，并返回该子集合的根结点。

并查集的存储结构
通常用树的双亲表示作为并查集的存储结构，每个子集合以一棵树表示。所有表示子集合的树，构成表示全集合的森林，存放在双亲表示数组内。
通常用数组元素的下标代表元素名，用根结点的下标代表子集合名，根结点的双亲域为负数（可设置为该子集合元素数量的相反数）。

//并查集的结构定义
#define SIZE 100
int UFSets[SIZE];

//并查集的初始化操作
void Initial(int S[]) { //S即为并查集
  for (int i = 0; i < SIZE; i++) {
    s[i] = -1;
  }
}

//查找操作
//判断两个元素是否属于同一个集合，只需分别找到它们的根，再比较根是否相同即可。
int Find(int S[], int x) {
  while(S[x] > 0) {
    x = S[x];
  }
  return x;
}

//合并操作
void Union(int S[], int Root1, int Root2) {
  if(Root1 == Root2) return;
  S[Root2] = S[Root1];
}

//并查集实现的优化
/*
在极端情况下，n个元素构成的集合树的深度为n，则Find操作的最坏时间复杂度为O(n)
改进：令根结点的绝对值＝集合树的成员数量，将小树合并到大树
*/
void Union(int S[], int Root1, int Root2) {
  if(Root1 == Root2) return;
  if(abs(S[Root2]) < abs(S[Root1])) { //Root2结点数更少
    S[Root1] += S[Root2];
    S[Root2] = Root1;
  }
  else {
    S[Root2] += S[Root1];
    S[Root1] = Root2;
  }
}
/*
采用这种方法构造得到的集合树，其深度不超过⌊log_2 n⌋+1
随着子集逐对合并，集合树的深度越来越大，
为了进一步减少确定元素所在集合的时间，还可优化Find操作，
即将从根到元素x路径上的所有元素都变成根的孩子
*/
int Find(int S[], int x) {
  int root = x;
  while(S[root] >= 0) {
    root = S[root];
  }
  while(x != root) {
    int t = S[x];
    S[x] = root;
    x = t;
  }
  return root;
}
/*
通过Find操作的“压缩路径”优化后，可使集合树的深度不超过O(α(n))，
其中α(n)是一个增长极其缓慢的函数，对于常见的正整数n，通常α(n)≤4。
*/

//或递归
int Find(int S[], int x) {
  if (S[x] < 0) return;
  return S[x] = Find(S, S[x]);
}

什么是并查集？并查集主要用在什么地方？
答：并查集又称为不相交集合，是表示集合的不相交子集合的一种集合表示，它主要有三种操作：初始化，查找和合并。并查集主要用于判断和构造等价类。

为什么并查集的实现采用树或森林的双亲数组？
答：一般集合的实现采用位数组或有序链表，但这两种存储表示对于描述子集合的集合、查找某个集合元素在哪个子集合有一定的困难。
采用树或森林的双亲表示数组，同一子集合的元素位于同一棵树中，子集合的集合用森林表示，可以方便地实现查找和合并操作。

为什么在并查集的双亲数组中树（子集合）的根的双亲指针为负数？
答：子集合用树的根来标识，根的双亲指针为负数，可区别树的根结点和树中的其他结点。该负数的绝对值可能表示的是树中结点的个数，也可能表示的是树的高度。

在合并操作Merge(S, R1, R2)中，为什么规定R1和R2是两棵树的根？
答：若允许R1和R2是两棵树的任意结点，如让R2的双亲指针指向R1，可能会把以R2为根的子树从原来R2所在的树中脱离出去，造成运算错误。

六、图

图的定义（包括）

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

完全图（又称简单完全图）

用n表示图中顶点数目，不考虑顶点到其自身的弧或边的情况下，
（无向图的边数目的取值范围：0到 $\frac{1}{2}n(n-1)$ ，有向图的弧数目的取值范围：0到n(n-1)。）
有 $\frac{1}{2}n(n-1)$ 条边的无向图称为完全图；
有n(n-1)条弧的有向图称为有向完全图。
有很少条边或弧（如 e < nlogn）的图称为稀疏图，反之称为稠密图。

连通图

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

在有向图中，若有一对顶点v和w，从v到w和从w到v之间都有路径，则称这两个顶点是强连通的。
若图中任意一对顶点都是强连通的，则称此图为强连通图。
强连通分量：有向图中的极大强连通子图。
若一张有向图的节点两两互相可达，则称这张图是强连通的 (strongly connected)。
若一张有向图的边替换为无向边后可以得到一张连通图，则称原来这张有向图是弱连通的 (weakly connected)。
弱连通分量(weakly connected component)（极大弱连通子图）
强连通分量(strongly connected component)（极大强连通子图）。

简单路径

路径：一个顶点到另一个顶点之间的顶点序列。
路径长度：路径上的边（无向图）或弧（有向图）的数目。
距离：从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径，则记该距离为无穷（∞）。
回路或环：第一个顶点和最后一个顶点相同的路径（说明是顶点序列）称为回路或环。
简单路径：序列中顶点不重复出现的路径。
简单回路或环：除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。
简单图：①不存在重复边；②不存在顶点到自身的边；的图。
多重图：存在某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联的图。

有向图

有向图（Digraph）是由一组顶点和一组有向边组成的图。在有向图中，边有方向，即一条边从一个顶点指向另一个顶点。若存在一条边从顶点 A 指向顶点 B，则只能从 A 到 B，不能从 B 到 A。
弧是顶点地有序对，记为，v称为弧尾，w称为弧头。

称为从v到w的弧，也称v邻接到w。

无向图

无向图（Undigraph）是由一组顶点和一组无向边组成的图。在无向图中，边没有方向，即如果存在一条边连接顶点 A 和顶点 B，则可以从 A 到 B，也可以从 B 到 A。
边是顶点的无序对，记为(v, w)或(w,v)。
可以说w和v互为邻接点。
边(v,w)依附于w和v，或称边(v,w)和v，w相关联。

无环图

在无环图中，从任何一个顶点出发，沿着图中的边所走的路径都不能回到该顶点。
无环图有两种常见的类型：有向无环图（DAG）和无向无环图（UAG，又称森林）。
注：①无向、无环、连通图：树#)； ②无向、无环图：森林#%E6%A3%AE%E6%9E%97)。

等

子图的定义

子图 $G' = (V', E')$ 是图 $G = (V, E)$ 的一个子集，其中：

$V' \subseteq V$ 是 $G$ 的顶点集合的子集。
$E' \subseteq E$ 是 $G$ 的边集合的子集，且 $E'$ 中的每一条边都连接 $V'$ 中的顶点。

真子图的定义

真子图 $G' = (V', E')$ 是图 $G = (V, E)$ 的一个真子集，即：

$V' \subset V$ 且 $E' \subset E$ ，并且至少有一个顶点或边不在 $G'$ 中。

注：真子图必须少于原图的顶点或边，不能与原图完全相同。

导出子图的定义

导出子图 $G' = (V', E')$ 是由原图 $G = (V, E)$ 中的一个顶点子集 $V' \subseteq V$ 生成的，且包含 $V'$ 中顶点之间在原图中的所有边：

$E' = \{(u, v) \in E \mid u, v \in V'\}$

导出子图是由顶点子集及其间所有连接边构成的子图。

生成子图（或支撑子图）的定义

对一张图 $G = (V, E)$ ，若存在另一张图 $G' = (V', E')$ 满足 $V' = V$ 且 $E' \subseteq E$ ，则称 $G'$ 是 $G$ 的生成子图/支撑子图 (spanning subgraph)。

子图、真子图、导出子图和生成子图的区别

图类型	定义	说明
子图	从原图中选取部分顶点和与之连接的部分边构成的图。	可以是原图的任意部分，包括可能包含整个图。
真子图	是一个子图，但必须少于原图，即不等于原图。	真子图不能包含原图的所有顶点和边。
导出子图	从原图中选取一个顶点集合，生成包含这些顶点和它们之间的所有边的子图。	导出子图必须保留选定顶点之间的原始边，通常导出子图是从子集顶点产生的最小图。
生成子图	从原图中选取全部顶点和与之连接的部分边构成的图。	生成子图G’中顶点个数V’必须和原图G中V的数量相同，而E’∈E即可。

显然，原图 G 是自身的子图，支撑子图，导出子图；无边图是 G 的支撑子图。

生成树：一个连通图（无向）的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。

如果在一棵生成树上添加一条边，必定构成一个环，因为这条边使得它依附的那两个顶点之间有了第二条路径。
一棵有n个顶点的生成树有且仅有n-1条边。
1. 如果一个图有n个顶点和小于n-1条边，则是非连通图。
2. 如果它多于n-1条边，则一定有环。
3. 但是，有n-1条边的图不一定是生成树。

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

生成森林：在非连通图中，连通分量的生成树构成了非连通图的生成森林。
一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。

顶点的度、入度、出度
在无向图中，顶点v的度是指依附于顶点v的边的条数，记为TD(v)。
无向图全部顶点的度之和等于边数的2倍，因为每条边和两个顶点相关联。
在有向图中，顶点v的度分为入度和出度，入度是以顶点v为终点的有向边的数目，记为ID(v)；而出度是以顶点v为起点的有向边的数目，记为OD(v)。顶点v的度TD(v)=ID(v)+OD(v)。
有向图的全部顶点的入度之和与出度之和相等，这是因为每条有向边都有一个起点和终点。

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

图和二叉树、树和森林这种结构之间的异同点（明确理解）

无向、无环、连通图：树#)
森林是指互相不交并树的集合。
无向、无环图：森林#%E6%A3%AE%E6%9E%97)

结构	连通性	环的存在	边的数量	子节点数量
图	可以连通，也可以不连通	可以有环	没有固定要求	没有限制
树	连通	无环	( n-1 )（( n ) 为顶点数）	每个结点有且仅有一个父节点
二叉树	连通	无环	( n-1 )（( n ) 为顶点数）	每个结点最多两个子节点
森林	不一定连通	无环	( n - k )（( k ) 为树的数量）	每棵树都是一棵独立的无环连通树

图的存储（包括）

邻接矩阵法

所谓邻接矩阵存储，是指用一个一维矩阵存储图中顶点的信息，用一个二维矩阵存储图中边的信息（即各顶点之间的邻接关系），存储顶点之间邻接关系的二维数组称为邻接矩阵。
顶点数为n的图的邻接矩阵A是n×n的。通常用0或∞来代表两个顶点之间不存在边。
无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可采用压缩存储。
空间复杂度为O(n)，其中n为图的顶点数|V|。
对于无向图，邻接矩阵的第i行（或列）非零（或∞）元素的个数正好是顶点i的度TD(i)。
对于有向图，i行->出度 $OD(v_i)$ ，i列->入度 $ID(v_i)$
设图G的邻接矩阵为 $A \text{，} A^n$ 的元素 $A^n[i][j]$ 等于由顶点i到顶点j的长度为n的路径的数目。

邻接表法

所谓邻接表，是指对图G中的每个顶点 $v_i$ 建立一个单链表，第i个单链表中的结点表示依附于顶点 $v_i$ 的边（对于有向图则是以顶点 $v_i$ 为尾的弧），这个单链表就称为顶点 $v_i$ 的边表（对于有向图则称为出边表）。边表的头指针和顶点的数据信息采用顺序存储，称为顶点表，所以在邻接表中存在两种结点：顶点表和边表结点。
顶点表结点由两个域组成：顶点域（data）存储顶点 $v_i$ 的相关信息，边表头指针域（firstarc）指向第一条边的边表结点。
边表结点至少由两个域组成：邻接点域（adjvex）存储与头结点顶点 $v_i$ 邻接的顶点编号，指针域（nextarc）指向下一条边的边表结点。
空间复杂度：无向图->O(|V|+2|E|)，有向图->O(|V|+|E|)。
找有向图的入度必须遍历整个邻接表。
图的邻接表表示法并不唯一，因为在每个顶点对应的边表中，各边结点的链接次序可以是任意的，它取决于建立邻接表的算法及边的输入次序。

差异性

掌握图采用邻接矩阵和邻接表进行存储的差异性

特性	邻接矩阵	邻接表
空间复杂度	$O(V^2)$	无向图：O(V + 2E)，有向图：O(V + E)
找相邻边	需要遍历整行或列，O(V)	找有向图的入度必须遍历整个邻接表
删除边或顶点	删除边很方便，删除顶点需要大量移动数据	无向图中删除边或顶点都不方便
适用图类型	稠密图（图中的边较多）	稀疏图（图中的边较少）
表示方式	唯一	不唯一
实现难度	简单	稍复杂

十字链表（大纲这里没写）

十字链表是有向图的一种链式存储结构。在十字链表中，有向图的每条弧用一个结点（弧结点）来表示，每个结点（顶点结点）来表示。
弧结点有5个域：

tailvex和headvex两个域分别指示狐尾和弧头这两个顶点的编号；
头链域hlink指向弧头相同的下一个弧结点；
尾链域tlink指向弧尾相同的下一个弧结点；
info域存放该弧的相关信息。

顶点结点中有3个域：

data域存放该顶点的数据信息，如顶点名称；
firstin域指向以该顶点为弧头的第一个弧结点；
firstout域指向以该顶点为弧尾的第一个弧结点。

弧结点

tailvex

headvex

hlink

tlink

(info)

顶点结点

data

firstin

firstout

注意，顶点结点之间是顺序存储的，弧结点省略了info域。
在十字链表中，既容易找到 $V_i$ 为尾的弧，也容易找到 $V_i$ 为头的弧，因而容易求得顶点的出度和入度。图的十字链表表示是不唯一的，但一个十字链表表示唯一确定的图。

邻接多重表（大纲这里没写）

邻接多重表是无向图的一种链式存储结构。在邻接表中，容易求得顶点和边得各种信息，但在邻接表中求两个顶点之间是否存在边而对边执行删除等操作时，需要分别在两个顶点得边表中遍历，效率极低。
与十字链表类似，在邻接多重表中，每条边用一个结点表示，每个顶点也用一个结点表示。
边结点

ivex

ilink

jvex

jlink

(info)

ivex和jvex这两个域指示该边依附的两个顶点的编号；
ilink域指向下一条依附于顶点ivex的边；
jlink域指向下一条依附于顶点jvex的边；
info域存放该边的相关信息。

顶点结点

data

firstedge

data域存放该顶点的相关信息；
firstedge域指向第一条依附于该顶点的边。

在邻接多重表中，所有依附于同一顶点的边串联在同一链表中；因为每条边依附于两个顶点，所以每个边结点同时链接在两个链表中。
对无向图而言，其邻接多重表和邻接表的差别仅在于，同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。

图的基本操作

略

图的两种遍历

图的遍历是指从图中的某一顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次，且仅访问一次。
注意树是一种特殊的图，所以树的遍历实际上也可视为一种特殊的遍历。

广度优先遍历

Breadth-First-Search, BFS
Dijkstra单源最短路径算法和Prim最小生成树算法也应用了类似的思想。
逐层访问，不回溯。

//标准写法
void BFS(int start, const vector<vector<int>>& graph, vector<bool>& visited) {
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        // 遍历当前结点的邻接结点
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                q.push(neighbor);
                visited[neighbor] = true;
            }
        }
    }
}

//邻接表法
void BFS(AlGraph G, int i) {
  visit(i);
  visited[i] = TRUE;
  EnQueue(Q, i);
  while(!IsEmpty(Q)) {
    DeQueue(Q, v); //队首顶点v出队
    for (p = G.vertices[v].firstarc; p; p = p -> nextarc) {
      w = p -> adjvex;
      if(visited[w] == FALSE) {
        visit(w);
        visited[w] = TRUE;
        EnQueue(Q, w);
      }
    }
  }
}

//邻接矩阵法
void BFS(MGraph G, int i) {
  visit(i);
  visited[i] = TRUE;
  EnQueue(Q, i);
  while(!IsEmpty(Q)) {
    DeQueue(Q, v);
    for (w = 0; w < G.vexnum; w ++) {
      if(visited[w] == FALSE && G.edge[v][w] == 1) {
        visit(w);
        visited[w] = TRUE;
        EnQueue(Q, w);
      }
    }
  }
}

图的广度优先遍历是二叉树的层次遍历算法的扩展。
最坏时间复杂度为O(|V|)。
邻接表时间复杂度为O(|V|+|E|)，因为每个顶点均需搜索（或入队）一次（O(|V|)），在搜索每个顶点的邻接点时，每条边至少访问一次（O(|E|)）。
邻接矩阵时间复杂度为 $O(|V|^2)$ 。

// 求非带权图的单源最短路径
vector<int> shortestPath(int start, const vector<vector<int>>& graph) {
    int n = graph.size();
    vector<int> distance(n, -1); // 距离数组，初始化为-1表示未访问
    queue<int> q;
    
    q.push(start);
    distance[start] = 0; // 起始结点到自身的距离为0

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        for (int neighbor : graph[node]) {
            if (distance[neighbor] == -1) { // 如果未访问
                distance[neighbor] = distance[node] + 1; // 更新最短距离
                q.push(neighbor);
            }
        }
    }

    return distance;
}

广度优先生成树

同一个图的邻接矩阵存储表示是唯一的，所以广度优先生成树也是唯一的。
但因为邻接表存储表示不唯一，所以广度优先生成树也是不唯一的。

深度优先遍历

Depth-First-Search, DFS
类似于树的先序遍历。

// 递归实现
void DFS_recursive(int node, const vector<vector<int>>& graph, vector<bool>& visited) {
    visited[node] = true; // 标记当前结点为已访问
    cout << node << " ";  // 输出当前访问的结点

    for (int neighbor : graph[node]) { // 遍历相邻结点
        if (!visited[neighbor]) {
            DFS_recursive(neighbor, graph, visited); // 递归访问未访问的结点
        }
    }
}
//非递归
void DFS_iterative(int start, const vector<vector<int>>& graph) {
    vector<bool> visited(graph.size(), false);
    stack<int> s;
    s.push(start);
    visited[start] = true;

    while (!s.empty()) {
        int node = s.top();
        s.pop();
        cout << node << " "; // 输出当前访问的结点

        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                s.push(neighbor);
                visited[neighbor] = true; // 标记为已访问，防止重复入栈
            }
        }
    }
}
//邻接表
void DFS(ALGraph G, int i) {
  visit(i);
  visited[i] == TRUE;
  for (p = G.vertices[i]; p; p = p -> nextarc) {
    j = p -> adjvex;
    if(visited[j] == FALSE) {
      DFS(G, j);
    }
  }
}
//邻接矩阵
void DFS(MGraph G, int i) {
  visit(i);
  visited[i] = TRUE;
  for (j = 0; j < G.vexnum; j ++) {
    if(visited[j] == FALSE && G.edge[i][j] == 1) {
      DFS(G, j);
    }
  }
}

图的邻接矩阵表示是唯一的，但对邻接表来说，若边的输入次序不同，则生成的邻接表也不同。
因此，对于同一张图，基于邻接矩阵的遍历得到的DFS序列和BFS序列是唯一的，基于邻接表的遍历得到的DFS序列和BFS序列是不唯一的。
空间复杂度为O(|V|)。
邻接表O(|V|+|E|)，邻接矩阵 $O(|V|^2)$
连通图-深度优先生成树，非连通图-深度优先生成森林。
与BFS类似，基于邻接表存储的深度优先生成树是不唯一的。

图的遍历与图的连通性

图的遍历算法可以用来判断图的连通性。
对于有向图来说，若从初始顶点到图中的每个顶点都有路径，则能够访问到图中的所有顶点，否则不能访问到所有顶点。

图的基本应用（包括）

最小支撑树（最小生成树）

一个连通图的生成树包含图的所有顶点，并且只含尽可能少的边。
对于生成树来说，若砍去它的一条边，则会使生成树变成非连通图；若给它增加一条边，则会形成图中的一条回路。
对于带权连通无向图G，生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。权值之和最小的那棵生成树称为G的最小生成树。
①若图G存在权值相同的边，则G的最小生成树可能不唯一；②当G中的各边权值互不相等时，G的最小生成树是唯一的；③若无向连通图G的边数比顶点数少一，即G本身是一棵树时，则G的最小生成树就是它本身。
虽然最小生成树（树形）不唯一，但其对应的边的权值之和总是唯一的，而且是最小的。
最小生成树的边数为顶点数-1。
注意：最小生成树中所有边的权值之和最小，但不能保证任意两个顶点之间的路径是最短路径。

Prim和Kruskal都基于贪心算法。

Prim算法

（记忆：PV (Prim vertices)，经常写博客会注重page view）
假设 $G=(V,T)$ 是连通图，其最小生成树 $T=(U,E_T)，E_T$ 是最小生成树中边的集合。
初始化：向空树 $T=(U,E_T)$ 中添加图 $G=(V,E)$ 的任意一个顶点 $u_0$ ，使 $U={u_0}，E_T=Ø$ 。
循环（重复下列操作直至 $U=V$ ：从图G中选择满足 ${(u,v)|u∈U, v∈V-U}$ 且具有最小权值的边(u,v)，加入树T，置 $U=U∪{v}，E_T=E_T∪{(u,v)}$ 。
Prim算法的时间复杂度为 $O(|V|^2)$ ，不依赖于|E|，因此它适用于求解边稠密的图的最小生成树。
Kruskal算法
假设 $G=(V,E)$ 是连通图，其最小生成树 $T=(U, E_T)$ 。
初始化： $U=V, E_T=Ø$ 。即每个顶点构成一棵独立的树，T此时是一个仅含|V|个顶点的森林。
循环（重复直至T是一棵树）：按G的边的权值递增顺序依次从 $E-E_T$ 中选择一条边，若这条边加入T后不构成回路，则将其加入T后不构成回路，则将其加入 $E_T$ ，否则舍弃，直到 $E_T$ 中含有n-1条边。
在Kruskal算法中，最坏情况需要对|E|条边各扫描一次。通常采用堆来存放边的集合，每次选择最小权值的边需要 $O(log_2|E|)$ 的时间；每次使用并查集来快速判断两个顶点是否属于一个集合所需的时间为O(α(|V|))，α(|V|)的增长极其缓慢，可视为常数。
算法的总时间复杂度为 $O(|E|log_2|E|)$ ，不依赖于|V|，因此Kruskal算法适合于边稀疏而顶点较多的图。

最短路径

Dijkstra算法
求单源最短路径问题


vector<int> dijkstra(int start, int n, const vector<vector<Edge>>& graph) {
    vector<int> dist(n, INT_MAX); // 初始化所有节点的距离为无穷大
    dist[start] = 0; // 起点到自己的距离为0

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start}); // 将起点加入优先队列

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u]) continue; // 已有更短路径，跳过

        for (const auto& edge : graph[u]) {
            int v = edge.to;
            int weight = edge.weight;

            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }

    return dist;
}

使用邻接矩阵表示时，时间复杂度为 $O(|V|^2)$ 。使用带权的邻接表表示时，虽然修改dist[]的时间可以减少，但由于在dist[]中选择最小分量的时间不变，所以时间复杂度仍为 $O(|V|^2)$ 。
人们可能只希望找到从源点到某个特定顶点的最短路径，但这个问题和求解源点到其他所有顶点的最短路径一样复杂，时间复杂度为 $O(|V|^2)$ 。
不适合负权。

BellmanFord算法

算法步骤
假设图中有 𝑉 个节点和 𝐸 条边，起点为 start，算法的主要步骤如下：
① 初始化：将起点到自身的距离设为0，其他节点的初始距离设为无穷大（表示不可达）。
② 松弛边：重复 𝑉−1 次，对所有边进行松弛操作。
- 对于每一条边 (u, v, weight)，如果 dist[u] + weight < dist[v]，则更新 dist[v] = dist[u] + weight。
- 之所以重复 𝑉−1 次，是因为最短路径最多包含 𝑉−1 条边，多余的边不会影响路径长度。
  ③ 检测负环：在执行完𝑉−1 轮松弛操作后，再对所有边执行一次松弛操作。如果此时还能找到更短路径（即 dist[u] + weight < dist[v] 依然成立），则说明图中存在负权回路（负环）。

bool bellmanFord(int n, int start, const vector<Edge>& edges, vector<int>& dist) {
    dist.assign(n, INT_MAX);
    dist[start] = 0;

    // 进行 n-1 次松弛操作
    for (int i = 0; i < n - 1; ++i) {
        for (const auto& edge : edges) {
            if (dist[edge.from] != INT_MAX && dist[edge.from] + edge.weight < dist[edge.to]) {
                dist[edge.to] = dist[edge.from] + edge.weight;
            }
        }
    }

    // 检测负环
    for (const auto& edge : edges) {
        if (dist[edge.from] != INT_MAX && dist[edge.from] + edge.weight < dist[edge.to]) {
            return false; // 存在负环
        }
    }

    return true; // 没有负环
}

用于求单源最短路径，支持带负权边的图。Bellman-Ford的时间复杂度为O(V×E)，可以检测负权回路（负环）。
适合稀疏图：在稀疏图中（边数较少的图），Bellman-Ford的效率较高，但在稠密图中效率不如Floyd-Warshall。

Floyd算法

const int INF = INT_MAX;
void floydWarshall(int n, vector<vector<int>>& dist) {
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}

用于求解任意两点之间的最短路径。该算法的时间复杂度为 $O(|V|^3)$ ，适用于较小规模的稠密图。
Floyd算法允许出现带负权值的边，但是不允许有包含带负权值的边组成的回路。

总结

Dijkstra：快速且适合无负权边的单源最短路径。
Floyd-Warshall：适合小规模图的任意两点最短路径，但无法处理负环。
Bellman-Ford：支持负权边且能检测负环，适合较低效率需求的单源最短路径。

Bellman-Ford算法
回路检测能力：Bellman-Ford可以检测负权回路（负环）。在执行完 𝑉−1 轮松弛操作后，如果还能进一步松弛，说明图中存在负权回路。
适用场景：当我们需要检测负权回路，或者在存在负权边的图中寻找单源最短路径时，Bellman-Ford非常适用。

①Bellman-Ford算法能算出负权回路的最小路径吗？
不能算出负权回路的最小路径：Bellman-Ford算法确实只能检测到负权回路的存在，但无法求出包含负权回路的最小路径。
为什么无法求出最小路径：因为负权回路的性质是可以让路径不断缩短——随着每次通过负权回路，路径权重会持续降低。因此，如果图中存在负权回路，任意包含该回路的路径长度可以趋近负无穷大。
结论：一旦图中有负权回路，Bellman-Ford就无法得到正确的最短路径，只能返回一个错误标志，提示“图中存在负权回路”。
②带负权回路的图是否能求最小路径？
带负权回路的图整体上不能求最小路径：如果图中有负权回路，且这个回路能够从起点达到（即负权回路在从起点到某个节点的路径中），则不存在“最短路径”，因为我们可以沿着负权回路无限循环，让路径长度趋向负无穷。
局部求解：如果负权回路在图中的某个孤立部分，并不影响起点到其他节点的路径，则在受影响的节点之外，我们仍然可以使用Bellman-Ford求出正确的最短路径。但一般情况下，一旦存在负权回路就难以求得全局最短路径。
Dijkstra算法
回路检测能力：Dijkstra不能检测回路，也无法正确处理负权边。
适用场景：主要用于无负权边的图的单源最短路径问题。

①Dijkstra是不是连普通的回路都不能检测？
Dijkstra无法检测回路：Dijkstra算法的设计初衷是用于求解无负权边的单源最短路径，因此它不具备回路检测能力。
为什么无法检测回路：Dijkstra假设路径是单调递增的，因此一旦确定某个节点的最短路径后，它不会再访问该节点，也不会追踪是否形成回路。这种设计避免了多次访问同一节点，但也因此放弃了回路检测的能力。
结论：Dijkstra既不能检测负权回路，也不能检测普通回路。
②为什么Dijkstra不能正确处理负权边？
Dijkstra的贪心策略依赖非负权边，一旦节点的最短路径确定，它不会再更改。如果存在负权边，后续路径可能提供更短的路径，贪心策略就被破坏。
负权边破坏了路径长度递增的假设，Dijkstra没有更新已确定最短路径的机制，因此最终结果可能不正确。
Floyd-Warshall算法
回路检测能力：Floyd-Warshall不直接检测回路，但可以在结果矩阵中检测到负权回路。
方法：如果在计算过程中发现 dist[i][i] < 0（即一个节点到自身的最短路径为负值），则说明存在负权回路。
适用场景：适用于较小规模的图，可以同时解决任意两点的最短路径问题。

注：利用dist[i][i] < 0条件不一定能判出存在“带有负权值的边组成的回路”（但负环的定义是跑一圈是负数），因为比如某个负环走一圈仍是正的，如图所示。

BFS算法
回路检测能力：在无向图和有向图中，BFS都可以检测到回路。
无向图：如果在遍历过程中遇到一个已经访问过的邻居节点，且该邻居节点不是当前节点的父节点，则存在回路。
有向图：如果在遍历过程中遇到一个已经在当前访问路径中的节点（即一个祖先节点），则存在回路。
适用场景：主要用于无权图中的最短路径和环检测，尤其在广度优先搜索遍历时很适用。

BFS算法可以算边权相同情况下的最短路径。

使用BFS检测无向图中的回路

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

bool bfsCycle(int start, vector<vector<int>>& graph, vector<int>& visited) {
    queue<pair<int, int>> q;
    visited[start] = 1;
    q.push({start, -1}); // 存储节点和父节点

    while (!q.empty()) {
        int node = q.front().first;
        int parent = q.front().second;
        q.pop();

        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = 1;
                q.push({neighbor, node});
            } else if (neighbor != parent) {
                return true; // 找到回路
            }
        }
    }

    return false;
}

bool hasCycle(vector<vector<int>>& graph, int n) {
    vector<int> visited(n, 0);
    for (int i = 0; i < n; ++i) {
        if (!visited[i] && bfsCycle(i, graph, visited)) {
            return true;
        }
    }
    return false;
}

int main() {
    int n = 4;
    vector<vector<int>> graph = {
        {1, 2},  // 节点 0 -> 节点 1 和 节点 2
        {0, 2},  // 节点 1 -> 节点 0 和 节点 2
        {0, 1, 3},  // 节点 2 -> 节点 0, 节点 1 和 节点 3
        {2}     // 节点 3 -> 节点 2
    };

    if (hasCycle(graph, n)) {
        cout << "图中存在回路" << endl;
    } else {
        cout << "图中不存在回路" << endl;
    }

    return 0;
}

DFS算法
回路检测能力：DFS同样可以检测回路，是一种常用的回路检测方法。
无向图：如果在遍历过程中遇到一个已经访问过的邻居节点，且该邻居节点不是当前节点的父节点，则存在回路。
有向图：DFS通过维护一个访问状态数组来检测环。在遍历过程中，如果遇到一个正在访问的节点（即当前路径中的祖先节点），则存在回路。
适用场景：DFS广泛用于图遍历和回路检测，包括拓扑排序、检测强连通分量等。

DFS算法不能求最短路径。

使用DFS检测有向图中的回路

#include <iostream>
#include <vector>

using namespace std;

bool dfs(int node, vector<vector<int>>& graph, vector<int>& visited) {
    visited[node] = 1; // 标记当前节点正在访问

    for (int neighbor : graph[node]) {
        if (visited[neighbor] == 0) { // 未访问过
            if (dfs(neighbor, graph, visited)) {
                return true; // 找到环
            }
        } else if (visited[neighbor] == 1) {
            return true; // 遇到正在访问的节点，说明存在回路
        }
    }

    visited[node] = 2; // 标记当前节点已访问完毕
    return false;
}

bool hasCycle(vector<vector<int>>& graph, int n) {
    vector<int> visited(n, 0); // 0-未访问, 1-正在访问, 2-已访问完毕
    for (int i = 0; i < n; ++i) {
        if (visited[i] == 0) {
            if (dfs(i, graph, visited)) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    int n = 4; // 节点数
    vector<vector<int>> graph = {
        {1},      // 节点 0 -> 节点 1
        {2},      // 节点 1 -> 节点 2
        {0, 3},   // 节点 2 -> 节点 0 和 节点 3
        {}        // 节点 3 没有相邻节点
    };

    if (hasCycle(graph, n)) {
        cout << "图中存在回路" << endl;
    } else {
        cout << "图中不存在回路" << endl;
    }

    return 0;
}

有向无环图描述表达式（考点无）

王道p246
在二叉树描述表达式的基础上，实现对相同子式的共享，从而节省存储空间。

拓扑排序

AOV网：若用有向无环图（DAG）表示一个工程，其顶点表示活动，用有向边 $<V_i,V_j>$ 表示活动 $V_i$ 必须先于活动 $V_j$ 进行的这样一种关系，则将这种有向图称为顶点表示活动的网络，简称AOV网。
任何活动 $V_i$ 不能以它自己作为自己的前驱或后继。
拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：
1. 每个顶点出现且仅出现一次。
2. 若顶点A在序列中排在顶点B的前面，则在图中不存在从B到A的路径。
  或定义为：拓扑排序是对有向无环图的顶点的一种排序，它使得若存在一条从顶点A到顶点B的路径，则在排序中B出现在A的后面。每个AOV网都有一个或多个拓扑排序序列。
对一个AOV网进行拓扑排序的算法有很多，下面介绍比较常见的一种方法的步骤：
1. 从AOV网中选择一个没有前驱（入度为0）的顶点并输出。
2. 从网中删除该顶点和所有以它为起点的有向边。
3. 重复1和2直到当前的AOV网为空或当前网中不存在无前驱的顶点为止，后一种情况说明有向图中必然存在环。

vector<int> topologicalSort(int n, const vector<vector<int>>& edges) {
    vector<int> inDegree(n, 0);  // 入度数组
    vector<vector<int>> adj(n);  // 邻接表

    // 构建邻接表并计算每个结点的入度
    for (const auto& edge : edges) {
        int u = edge[0], v = edge[1];
        adj[u].push_back(v);
        inDegree[v]++;
    }

    queue<int> q;
    // 将入度为 0 的结点入队
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    vector<int> topoOrder;  // 存储拓扑排序结果
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topoOrder.push_back(u);

        // 遍历当前结点的邻接结点
        for (int v : adj[u]) {
            inDegree[v]--;  // 将相邻结点的入度减 1
            if (inDegree[v] == 0) {
                q.push(v);
            }
        }
    }

    // 如果拓扑排序结果中的结点数不等于总结点数，说明图中有环
    if (topoOrder.size() != n) {
        cout << "图中存在环，无法进行拓扑排序" << endl;
        return {};
    }

    return topoOrder;
}

时间复杂度：邻接矩阵 $O(|V|^2)$ ，邻接表 $O(|V|+|E|)$ 。
DFS的方式：
1. 若u是v的祖先，则在调用DFS访问u之前，必然已对v进行了DFS访问，即v的DFS结束时间先于u的DFS结束时间。从而可以考虑在DFS函数中设置一个时间标记，在DFS调用结束时，对各顶点计时。因此，祖先的结束时间必然大于子孙的结束时间。
2. 若u是v的子孙，则v为u的祖先，按上述思路，v的结束时间大于u的结束时间。
3. 若u和v没有路径关系，则u和v在拓扑序列的关系任意。
4. 最后按照结束时间从大到小排列，就可以得到一个拓扑排序序列。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void dfs(int node, vector<vector<int>>& adj, vector<bool>& visited, vector<int>& finishTime, int& time) {
    visited[node] = true;

    // 递归访问所有未访问的邻接结点
    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, adj, visited, finishTime, time);
        }
    }

    // 当前结点的所有邻接结点访问完成后，记录完成时间
    finishTime[node] = time++;
}

vector<int> topologicalSort(int n, const vector<vector<int>>& edges) {
    vector<vector<int>> adj(n);      // 邻接表
    vector<bool> visited(n, false);  // 访问标记
    vector<int> finishTime(n);       // 记录每个结点的完成时间
    int time = 0;                    // 时间计数器

    // 构建邻接表
    for (const auto& edge : edges) {
        int u = edge[0], v = edge[1];
        adj[u].push_back(v);
    }

    // 对所有未访问的结点进行 DFS，并记录完成时间
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i, adj, visited, finishTime, time);
        }
    }

    // 根据完成时间对结点进行排序，完成时间大的在前
    vector<int> topoOrder(n);
    for (int i = 0; i < n; i++) {
        topoOrder[i] = i;
    }
    sort(topoOrder.begin(), topoOrder.end(), [&](int a, int b) {
        return finishTime[a] > finishTime[b];
    });

    return topoOrder;
}

int main() {
    int n = 6;  // 结点数
    vector<vector<int>> edges = {{5, 2}, {5, 0}, {4, 0}, {4, 1}, {2, 3}, {3, 1}};  // 边

    vector<int> result = topologicalSort(n, edges);

    cout << "拓扑排序结果: ";
    for (int node : result) {
        cout << node << " ";
    }
    cout << endl;

    return 0;
}

对一个AOV网，若采用下列步骤进行排序，则称之为逆拓扑排序：
1. 从AOV网中选择一个没有后继（出度为0）的顶点并输出/
2. 从网中删除该顶点和所有以它为终点的有向边。
3. 重复1和2直到当前的AOV网为空。
用拓扑排序算法处理AOV网时，应注意以下问题：
1. 入度为0的顶点，即没有前驱活动的或前驱活动都已经完成的顶点，工程可以从这个顶点所代表的活动开始或继续。
2. 若一个顶点有多个直接后继，则拓扑排序的结果通常不唯一；但若各个顶点已经排在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，则拓扑排序的结果是唯一的。
3. 由于AOV网中各顶点的地位平等，每个顶点编号是人为的，因此可以按拓扑排序的结果重新编号，生成AOV网的新的邻接存储矩阵，这种邻接矩阵可以是三角矩阵；但对一般的图来说，若其邻接矩阵是三角矩阵，则存在拓扑序列；反之不一定成立。

什么条件下会存在多条拓扑路径？
大致可以归纳为：

存在多个入度为零的结点。

图中的结点之间没有完全的依赖关系。

关键路径

AOE网：在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为用边表示活动的网络，简称AOE网。
AOE网和AOV网都是有向无环图，不同之处在于它们的边和顶点所代表的的含义是不同的，AOE网中的边有权值，而AOV网中的边无权值，仅表示顶点之间的前后关系。
AOE网具有以下两个性质：
1. 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；
2. 只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。
  在AOE网中仅有一个入度为0的顶点，称为开始顶点（源点），它表示整个工程的开始；也仅有一个出度为0的顶点，称为结束顶点（汇点），它表示整个工程的结束。
在AOE网中，有些活动时可以并行进行的。从源点到汇点的有向路径可能有多条，并且这些路径长度可能不同。完成不同路径上的活动所需的时间虽然不同，但是只有所有路径上的活动都已完成，整个工程才能算结束。因此，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。
完成整个工程的最短时间就是关键路径的长度，即关键路径上各活动花费开销的总和。这是因为关键活动影响了整个工程的时间，即若关键活动不能按时完成，则整个工程的完成时间就会延长。因此，只要找到了关键活动，就找到了关键路径，也就可以得出最短完成时间。

事件 $v_k$ 的最早发生时间 $v_e(k)$

它是指从源点 $v_1$ 到顶点 $v_k$ 的最长路径长度。
事件 $v_k$ 的最早发生时间决定了所有从 $v_k$ 开始的活动能够开工的最早时间。
可用下面的递推公式来计算（用拓扑排序）：
1. $v_e(\text{源点})=0$
2. $v_e(k)=Max\{v_e(j)+Weight(v_j,v_k)\},v_k\text{为}v_j\text{的任意后继，}Weight(v_j,v_k)\text{表示}<v_j,v_k>\text{上的权值}$

事件 $v_k$ 的最迟发生时间 $v_l(k)$

它是指在不推迟整个工程完成的前提下，即保证它的后继事件 $v_j$ 在其最迟发生事件 $v_l(j)$ 能够发生时，该事件最迟必须发生的时间。
可用下面的递推公式来计算（用逆拓扑排序）：
1. $v_l(\text{汇点})=v_e(\text{汇点})$
2. $v_l(k)=Min\{v_l(j)-Weight(v_k,v_j)\},v_k\text{为}v_j\text{的任意前驱}$

活动 $a_i$ 的最早开始时间 $e(i)$

它是指该活动弧的起点所表示的事件的最早发生时间。若边 $<v_k,v_j>$ 表示活动 $a_i$ ，则有 $e(i)=v_e(k)$ 。

活动 $a_i$ 的最迟开始时间 $l(i)$

它是指该活动弧的终点所表示时间的最迟发生时间与该活动所需时间之差。若边 $<v_k,v_j>$ 表示活动 $a_i$ ，则有 $l(i)=v_l(j)-Weight(v_k,v_j)$ 。

一个活动 $a_i$ 的最迟开始时间l(i)和其最早开始时间e(i)的差额d(i)=l(i)-e(i)

它是指该活动完成的时间余量，即在不增加完成整个工程所需总时间的情况下，活动 $a_i$ 可以拖延的时间。若一个活动的时间余量为0，则说明该活动必须要如期完成，否则会拖延整个工程的进度。
所以称l(i)=e(i)的活动 $a_i$ 是关键活动。

求关键路径的算法步骤如下：

从源点出发，令 $v_e(\text{源点})=0$ ，按拓扑有序求其余顶点的最早发生时间 $v_e()$ 。

最早发生时间即为前面的任务要全部完成了才能做这个任务
如果是选择题，在这一步就可以得出关键路径。（具有最大路径长度的路径）
从汇点出发，令 $v_l(汇点)=v_e(汇点)$ ，按逆拓扑有序求其余顶点的最迟发生时间 $v_l()$ 。

最迟发生时间即为该事件再不发生，后续任务就得推迟进行了。
根据各顶点的 $v_e()$ 值求所有弧的最早开始时间 $e()$ 。

弧的起点的最早开始时间
记住，早找前面，因为要前面全部完成任务。
根据各顶点的 $v_l()$ 值求所有弧的最迟开始时间 $l()$ 。

弧的终点的最迟开始时间-弧的权值
记住，迟找后面，因为要后面不被这边拖进度。
求AOE网中所有活动的差额d()，找出所有d()=0的活动构成关键路径。

对于关键路径，需要注意以下几点：

关键路径上的所有活动都是关键活动，它是决定整个工程的关键因素，因此可以通过加快关键活动来缩短整个工程的工期。但也不能任意缩短关键活动，因为一旦缩短到一定的程度，该关键活动就可能变成非关键活动。

网中的关键路径并不一定唯一，且对于有几条路径的网，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。

不同存储结构时各种图算法的时间复杂度

七、查找

查找的定义和与查找有关的算法：顺序查找法、折半查找法、散列（Hash）技术。

理解查找的定义

查找。在数据集合中寻找满足某种条件的数据元素的过程称为查找。
在数据集合中找了满足条件的数据元素为查找成功，否则为查找失败。
用于查找的数据集合为查找表，它是由同一类型的数据元素（或记录）组成的。对查找表的常见操作有：① 查询符合条件的数据元素；② 插入、删除数据元素。
静态查找表。若一个查找表的操作只涉及查找操作，则无须动态地修改查找表，此类查找表称为静态查找表。与此对应，需要动态地插入或删除的查找表称为动态查找表。适合静态查找表的查找方法有顺序查找、折半查找、散列查找等；适合动态查找表的查找方法有二叉排序树的查找、散列查找等。
关键字。数据元素中的唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。例如，在有一个学生元素构成的数据集合中，学生元素中“学号”这一数据项的值唯一地标识一名学生。
平均查找长度。在查找过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值，其数学定义为 $ASL=\sum\limits_{i=1}^{n}P_i C_i$ . 式中，n是查找表的长度（因为每一个元素都要查找，所有都得考虑进去），Pi是查找第i个数据元素的概率，一般认为每个数据元素的查找概率相等，即Pi=1/n；Ci是找到第i个数据元素所需进行的比较次数。平均查找长度是衡量算法效率的最主要指标。
有序线性表的顺序查找中的线性表可以是链式存储结构，而折半查找中的线性表只能是顺序存储结构。

衡量查找算法的一些指标：三个查找长度

顺序查找法

一般无序线性表

从后往前找，a[0]=x作为哨兵，若查找不成功，说明是从n比较到0都没找到，即比较了n+1次。

平均查找长度（成功不成功都计入，每个概率为1/2n） $ASL=\frac{1}{2n}\sum\limits_{i=1}^{n}(n-1+1)+\frac{1}{2}(n+1)=\frac{3}{4}(n+1)$
成功查找的（平均）查找长度 $ASL=\sum\limits_{i=1}^{n}P_i C_i= \frac{1}{n} \sum\limits_{i=1}^{n} (n-i+1)=\frac{n+1}{2}$
不成功查找的（平均）查找长度 ASL=n+1

有序线性表

平均查找长度
成功查找的（平均）查找长度
有序的结果和一般线性表的顺序查找一样，但是！！！要注意！！！这里的查找顺序若是从前往后，就不是和上面一样的结果！！！
不成功查找的（平均）查找长度

表L是按关键字从小到大排列的，查找的顺序是从前往后。假设有n个结点（这些是查找成功的结点），虚构n+1个查找失败结点。Pi为1/(n+1)，1,2,…,n,n为查找失败时的比较次数。
$ASL=\frac{1+2+\cdots+n+n}{n+1}=\frac{n}{2}+\frac{n}{n+1}$

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

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

在索引表中确定待查记录所在的块，可以顺序查找或折半查找索引表；
在块内顺序查找。

ASL=L_I(\text{索引查找})+L_S(\text{块内查找})=\frac{b+1}{2}+\frac{s+1}{2}=\frac{s^2+2s+n}{2s}

（在块内和索引均采用顺序查找）

\text{若}s=\sqrt{n}\text{，则平均查找长度取最小值}\sqrt{n}+1

折半查找法（二分查找）

平均查找长度
成功查找的（平均）查找长度

等概率，Pi为1/n。树上的每个结点都要考虑进去，每个结点的比较次数为它的层数。第一层次数为1（层高），有 $2^0（2^{j-1}）$ 个结点要计算；第二层次数为2（层高），有 $2^1（2^{j-1}）$ 个结点要计算……直到最后一层，这里不一定是满二叉树，但就按照满二叉树近似计算了。
$ASL=\frac{1}{n}(1×1+2×2+\cdots+h×2^{h-1})=\frac{n+1}{n}log_2(n+1)-1≈log_2(n+1)-1$
这里记一下最终结果！（因为不知道咋算出来的）
另外，h为 $\lceil log_2(n+1) \rceil$ .
所以折半查找的时间复杂度为 $O(log_2n)$ ，平均情况下比顺序查找的效率高。
不成功查找的（平均）查找长度

虚构出方形结点，挂到圆形结点的下方。如果查找失败，即为方形结点，但是次数是上面那个圆形结点的层数。比如二叉树第3层下面总共挂了4个方形结点，第4层挂了8个方形节点：
ASL=(3×4+4×8)/12=11/3

散列（Hash）查找法

平均查找长度
成功查找的（平均）查找长度
不成功查找的（平均）查找长度
（见王道，直接看解析p341-03，p343-07）

执行步骤：
初始化：Addr=Hash(key);

检测查找表中地址为Addr的位置上是否有记录，若无记录，返回查找失败；若有记录（可能同义词放在这了），比较它与key的值，若相等，则返回查找成功标志，否则执行步骤2.
用给定的处理冲突方法计算“下一个散列地址”，并把Addr置为此地址，转入步骤1.

对同一组关键字，设定相同的散列函数，则不同的处理冲突的方法得到的散列表不同，它们的平均查找长度也不同，本例与采用拉链法的平均查找长度不同。
从散列表的查找过程可见：
1. 虽然散列表在关键字与记录的存储位置之间建立了直接映像，但由于“冲突”的产生，使得散列表的查找过程仍然是一个给定值和关键字进行比较的过程。因此，仍然需要以平均查找长度作为衡量散列表的查找效率的度量。
2. 散列表的查找效率取决于三个因素：散列函数、处理冲突的方法和装填因子（见下）。

掌握顺序查找法和折半查找法，并理解二者之间的异同点

顺序查找适用于任何情况，但效率较低，特别是对于大量数据时。
折半查找效率较高，但前提是数据必须有序。

掌握散列技术（包括）

散列函数（哈希函数）

一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash(key)=Addr（这里的地址可以是数组下标、索引或内存地址等）。
散列函数可能会把两个或两个以上的关键字映射到同一地址，称这种情况为冲突，这些发成冲突的不同关键字称为同义词。
1. 一方面，设计得好的散列函数应尽量减少这样的冲突；
2. 另一方面，由于这样的冲突总是不可避免的，所以还要设计好处理冲突的方法。
在构造散列函数时，必须注意以下几点：

散列函数的定义域必须包含全部关键字，而值域的范围则依赖于散列表的大小。
散列函数计算出的地址应尽可能均匀地分布在整个地址空间，尽可能地减少冲突。
散列函数应尽量简单，能在较短的时间内计算出一个关键字对应的散列地址。

常见的散列函数
1. 直接定址法
  - 直接取关键字的某个线性函数值（线性函数：f(x)=ax+b）为散列地址，散列函数为H(key)=key或H(key)=a×key+b.（a和b是常数）
  - 这种方法计算很简单，且不会产生冲突。它适合关键字的分布基本连续的情况；若关键字分布不连续，空位较多，则会造成存储空间的浪费。
2. 除留余数法
  - 这是一种最简单、最常用的方法，假定散列列表表长为m，取一个不大于m但最接近或等于m的质数p。散列函数为H(key)=key%p.
  - 除留余数法的关键是选好p，使得每个关键字通过该函数转换后等概率地映射到散列空间上的任意一个地址，从而尽可能减少冲突的可能性。
3. 数字分析法
  - 设关键字r是进制数（如十进制数），而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时应选取数码分布较为均匀的若干位作为散列地址。
  - 这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。
    为什么选择分布较为均匀的位？
    1. 均匀分布减少冲突：数码均匀分布意味着每个可能的散列地址都有相似的数字频率，这样每个地址的负载相对均匀，避免了某些地址被过多数字占用，减少了哈希冲突。
    2. 提高散列效率：通过选取均匀分布的位，可以使得散列算法对输入数据的敏感度更高，避免了一些特定位置的数字偏差影响整个散列过程。这使得数据能够更广泛地分布到散列表中，提高查询和插入效率。
4. 平方取中法
  - 取关键字的平方值的中间几位作为散列地址。具体取多少位要视实际情况而定。
  - 这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。

散列表（哈希表）

根据关键字而直接进行访问的数据结构。也就是说，散列表建立了关键字和存储地址之间的一种直接映射关系。
理想情况下，对散列表进行查找的时间复杂度为O(1)，即与表中元素的个数无关。

散列冲突的发生及其解决方法

开放定址法

所谓开放定址法，是指表中可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。
$H_i=(H(key)+d_i)%m$
式中，H(key)为散列函数；i=1,2,…,k(k≤m-1)；m表示散列表表长；di为增量序列。
取定某一增量序列后，对应的处理方法就是确定的。通常有以下4种取法：
①线性探测法，又称线性探测再散列法。
- $d_i=1, 2, …, m-1$ 。它的特点是：冲突发生时，顺序查看表中下一个单元（探测到表尾地址m-1时，下一个探测地址是表首地址0），直到找出一个空闲单元（当表未填满时一定能找到一个空闲单元）或查遍全表。
- 线性探测法可能使第i个散列地址的同义词存入第i+1个散列地址，这样本应存入第i+1个散列地址的元素就争夺第i+2个散列地址的元素的地址……从而造成大量元素在相邻的散列地址上聚集（或堆积）起来，大大降低了查找效率。
②平方探测法，又称二次探测法。
- $d_i=1^2, -1^2, 2^2, -2^2, \cdots, k^2, -k^2$ ，其中k≤m/2，散列表长度m必须是一个可以表示成4k+3的素数。
- 平方探测法是一种处理冲突的较好方法，可以避免出现“堆积”问题，它的缺点是不能探测到散列表上的所有单元，但至少能探测到一半单元。
③双散列法。
- $d_i=i×Hash_2(key)$ 。需要使用两个散列函数，当通过第一个散列函数H(key)得到的地址发生冲突时，则利用第二个散列函数 $Hash_2(key)$ 计算该关键字的地址增量。具体散列函数： $H_i=(H(key)+i×Hash_2(key))%m$ 。
- 初始探测位置 $H_0=H(key)%m$ 。i时冲突的次数，初始为0。
④伪随机序列法。 $d_i=\text{伪随机数序列}$ 。

采用开放定址法时，不能随便物理删除表中已有元素，否则会截断其他同义词元素的查找路径。因此，要删除一个元素时，可以做一个删除标记，进行逻辑删除。
但这样做的副作用是：执行多次删除后，表面上看起来散列表很满，实际上有许多位置未利用。

拉链法（链接法，chaining）

为了避免非同义词发生冲突，可以把所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识。
假设散列地址为i的同义词链表的头指针存放在散列表的第i个单元中，因而查找、插入和删除操作主要在同义词链中进行。拉链法适用于经常进行插入和删除的情况。

负载因子（装填因子）

散列表的装填因子一般记为α，定义为一个表的装满程度，即 $α=\frac{\text{表中记录数n}}{\text{散列表长度m}}$
散列表的平均查找长度依赖于散列表的装填因子α，而不直接依赖于n或m。
直观地看，α越大，表示装填的记录越“满”，发生冲突的可能性越大；反之，发生冲突的可能性越小。

理解不同查找技术的优缺点

查找技术	优点	缺点	适用场景
顺序查找	简单实现，适用于无序数据，空间需求少	时间复杂度高，效率低	数据量小，数据无序时
二分查找	查找效率高（O(log n)），适用于有序数据	数据需要事先排序，复杂度较高	数据已排序，查找效率要求较高
哈希查找	查找速度快（O(1)），适用于大规模数据	哈希冲突，额外空间需求，不支持有序查找	需要高效查找的场景，如缓存、字典等
平衡二叉树查找	查找、插入、删除效率高（O(log n)）	实现复杂，空间开销较大	动态数据集，需要有序数据
跳表查找	查找效率高，插入删除简单，支持有序查找	空间开销大，较为复杂的实现	动态数据集，支持范围查询和排序的场景
B树/B+树查找	高效磁盘查找，支持范围查询	实现复杂，空间开销大	数据库、文件系统等大数据量存储和查询场景

八、排序

排序的定义（包括）

排序：就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。
输入：n个记录 $R_1, R_2, \cdots, R_n$ ，对应的关键字为 $k_1, k_2, \cdots, k_n$ 。
输出：输入序列的一个重排 $R_1', R_2', \cdots, R_n'$ ，使得 $k_1' \leq k_2' \leq \cdots \leq k_n'$ （其中“≤”可以换成其他的比较大小的符号）。

内排序

是指在排序期间元素全部存放在内存中的排序。
一般情况下，内部排序算法在执行过程中都要进行两种操作：比较和移动。基数排序不基于比较操作。

外排序

是指在排序期间元素无法全部同时存放内存中，必须在排序的过程中根据要求不断地在内、外存之间移动的顺序。

内排序和外排序的区别

在排序过程中，数据元素是否完全存放在内存中；

排序的稳定性

若待排序表中有两个元素 $R_i\text{和}R_j$ ，其对应的关键字相同，即 $key_i=key_j$ ，且在排序前 $R_i\text{在}R_j$ 的前面，若使用某一排序算法排序后， $R_i$ 仍然在 $R_j$ 的前面，则称这个排序算法是稳定的，否则称这个排序算法是不稳定的。

直接插入排序

假设前L[1…i-1]有序，后L[i+1…n]无序。（初始L[1]可以视为一个已排好序的子序列）

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

空间复杂度：O(1)，时间复杂度：最好O(n)，最坏 $O(n^2)$ ，平均总比较次数和总移动次数均约为 $\frac{n^2}{4}$ ，因此平均 $O(n^2)$ 。
稳定性：稳定。
适用性：顺序存储和链式存储的线性表，采用链式存储时无须移动元素。

折半插入排序（考点没写）

在直接插入排序的基础上，将寻找插入位置k的方式改成折半查找，移动部分不变。
时间复杂度为 $n^2$ 。对于数据量不是很大的顺序表，折半排序往往表现出很好的性能。
稳定。
仅使用于顺序存储的线性表。

冒泡排序

空间：O(1)
时间：最好情况（第一遍flag判定有序，移动0，比较一轮）O(n)；最坏情况（逆序，n-1轮）比较次数=n(n-1)/2，移动次数=3n(n-1)/2， $O(n^2)$ ；平均 $O(n^2)$ 。
稳定。
适用于顺序存储和链式存储的线性表。

简单选择排序

空间：O(1)
时间：移动次数不会超过3(n-1)，最好情况0，比较次数始终是n(n-1)/2，时间复杂度始终是 $O(n^2)$ 。
不稳定。
适用于顺序存储和链式存储的线性表，以及关键字较少的情况。

Shell排序

是对直接插入排序的改进，又称缩小增量排序。
过程：
1. 先取一个小于n的增量d1，把表中的全部记录分成d1组，所有距离为d1的倍数的记录放在同一组，在各组内进行直接插入排序；
2. 取第二个增量d2 < d1，重复1；
3. 直到所取到的dt=1，再进行直接插入排序。由于此时已经具有较好的局部有序性，因此可以很快得到最终结果。（直接插入排序适用于基本有序和数据量不大的排序表）
到目前为止，尚未求得一个最好的增量序列。

空间O(1)
时间：因为希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题，所以其时间复杂度分析比较困难。当n在某个特定范围时，希尔排序的时间复杂度约为 $O(n^{1.3})$ 。在最坏情况下希尔排序的时间复杂度为 $O(n^2)$ 。
不稳定。（相同关键字的记录被划分到不同的子表时，可能会改变它们之间的相对次序）
适用于顺序存储的线性表。

快速排序

int Partition(ElemType A[], int low, int high) {
  ElemType pivot = A[low];
  while(low < high) {
    while(low < high && A[high] >= pivot) 
      --high;
    A[low] = A[high];
    while(low <highg && A[low] <= pivot)
      ++low;
    A[high] = A[low];
  }
  A[low] = pivot;
  return low;
}

void QuickSort(ElemType A[], int low, int high) {
  if(low < high) {
    int pivotpos = Partition(A, low, high);
    Quicksort(A, low, pivotpos-1);
    Quicksort(A, pivotpos+1, high);
  }
}

空间最好 $log_2n$ ，最坏O(n)，平均 $O(log_2n)$ ；
时间最坏 $O(n^2)$ ，最好 $O(nlog_2n)$ ，平均 $O(nlog_2n)$ 。
快排是所有内部排序算法中平均性能最优的排序算法。
不稳定。
仅适用于顺序存储的线性表。

堆排序

① 初始化

对以第⌊n/2⌋个结点（完全二叉树最后一个结点的双亲）为根的子树筛选，使该子树成为堆。
向前依次对各结点（⌊n/2⌋-1~1）为根的子树进行筛选，看该结点值是否大于其左右结点的值，若不大于，则将左右子结点的较大值与之交换，交换后可能会破坏下一级的堆，于是继续采用上述方法构造下一级的堆，直到以该结点为根的子树构成堆为止。
反复利用上述调整堆的方法建堆，直到根结点。

② 输出堆顶元素后调整堆

输出堆顶元素后，将堆的最后一个元素与堆顶元素交换，此时堆的性质备破坏，需要向下进行筛选。

③再输出堆顶元素，如此重复，直到堆中只剩一个元素为止。

堆排序适合关键字较多的情况。例如，在1亿个数中选出前100个最大值。首先适用一个大小为100的数组，读入前100个数，建立小顶堆，而后依次读入余下的数，若小于堆顶则舍弃，否则用该数取代堆顶并重新调整堆，待数据读取完毕，堆中100个数为所求。
空间O(1)
时间：建堆O(n)，每次调整O(h)，最好、最坏、平均都是 $O(nlog_2n)$ 。
不稳定。
仅适用于顺序存储的线性表。

归并排序（二路归并排序）

ElemType *B = (ElemType *)malloc((n+1)*sizeof(ElemType));
void Merge (ElemType A[], int low, int mid, int high) {
  int i,j,k;
  for (k = low; k <= high; k++) 
    B[k] = A[k];
  for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k ++) {
    if(B[i] <= B[j]) 
      A[k] = B[i++];
    else
      A[k] = B[j++];
  }
  while(i<=mid) A[k++]=B[i++];
  while(j<=high) A[k++]=B[j++];
}
void MergeSort(ElemType A[], int low, int high) {
  if(low < high) {
    int mid = (low+high)/2;
    MergeSort(A, low, mid);
    MergeSort(A, mid+1, high);
    Merge(A, low, mid, high);
  }
}

空间O(n)
时间 $O(nlog_2n)$
稳定。
适用于顺序存储和链式存储的线性表。

基数排序

基数r（数位里的进制，如10）
两种：最高位优先（MSD）法，最低位优先（LSD）法。
空间O(r)
时间O(d(n+r))
稳定。
适用于顺序存储和链式存储的线性表。

时空复杂度和稳定性

对直接插入排序、冒泡排序、简单选择排序、Shell排序、快速排序、堆排序、归并排序、基数排序这些算法，掌握其在时间复杂度、空间复杂度以及是否稳定等方面的特点

平均时间复杂度位 $O(nlog_2n)$ 的稳定排序算法只有归并排序。
希尔排序的时间复杂度依赖于增量函数，所以无法准确给出其时间复杂度。
| 排序算法 | 最好情况时间复杂度 | 平均情况时间复杂度 | 最坏情况时间复杂度 | 空间复杂度 | 是否稳定 |
|————————|——————————|——————————|——————————|—————————|—————-|
| 直接插入排序 | O(n) | O(n²) | O(n²) | O(1) | 是 |
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 是 |
| 简单选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 否 |
| 希尔排序 | O(n log n) | O(n^1.3) | O(n²) | O(1) | 否 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 否 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 否 |
| 二路归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 是 |
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(r) | 是 |

K路归并排序

k路归并排序的外排序算法

王道p394

外部排序：在许多应用中，经常需要对大文件进行排序，因为文件中的记录很多，无法将整个文件复制进内存中进行排序。因此，需要将待排序的记录存储在外存上，排序时再将数据一部分一部分地调入内存进行排序，在排序过程中需要多次进行内存和外存之间的交换。这种排序算法就称为外部排序。
文件通常是按块存储在磁盘上的，操作系统也是按块对磁盘上的信息进行读/写的。因为磁盘读/写的机械动作所需的时间远远超过在内存中进行运算的时间（相比而言可以忽略不计），因此在外部排序过程中的时间代价主要考虑访问磁盘的次数，即I/O次数。
外部排序通常采用归并排序算法。它包括两个阶段：
1. 根据内存缓冲区大小，将外存上的文件分成若干长度为l的子文件，依次读入内存并利用内部排序算法对它们进行排序，并将排序后得到的有序子文件重新写回外存，称这些有序子文件为归并段或顺串；
2. 对这些归并段进行逐趟归并，使归并段（有序子文件）逐渐由小到大，直至得到整个有序文件为止。
一般情况下：外部排序的时间=内部排序的时间+外村信息读/写的时间（远大于另俩）+内部归并的时间
一般地，对r个初始归并段，做k路平衡归并（即每趟将k个或k个以下的有序子文件归并成一个有序子文件），第一趟可使⌈r/k⌉个归并段，以后每趟归并将m个归并段归并成⌈m/k⌉个归并段，直至最后形成一个大的归并段为止。树的高度-1= $⌈log_kr⌉$ =归并趟数S。可见，只要增大归并路数k，或减少初始归并段个数r，都能减少归并趟数S，进而减少读/写磁盘的次数，达到提高外部排序速度的目的。
增加归并路数k能减少归并趟数S，进而减少I/O次数。然而，增加归并路数k时，内部归并的时间将增加。做内部归并时，在k个元素中选择关键字最小的元素需要k-1次比较。每趟归并n个元素需要做(n-1)(k-1)次比较，S趟归并总共需要比较次数为 $S(n-1)(k-1)=\lceil log_k r \rceil (n-1)(k-1) = \lceil log_2 r \rceil (n-1)(k-1)/\lceil log_2 k \rceil$ ，式中， $(k-1)/\lceil log_2 k \rceil$ 随k增长而增长，因此内部归并时间亦随k的增长而增长。这将抵消因增大k而减少外村访问次数所得到的效益。因此，不能使用普通的内部归并排序算法。
为了使内部归并不受k的增大的影响，引入了败者树。败者树使树形选择排序的一种变体，可视为一棵完全二叉树。k个叶结点分别存放k个归并段在归并过程中当前参加比较的元素，内部结点用来记忆左右子树中的“失败者”，而让胜利者往上继续进行比较，一直到根结点。若比较两个数，大的为失败者，小的为胜利者，则根结点指向的数位最小数。
因为k路归并的败者树深度为 $⌈log_2 k⌉+1$ ，所以从k个记录中选择最小关键字，仅需进行 $⌈log_2 k⌉$ 次比较。因此总的比较次数约为 $S(n-1)\lceil log_k r \rceil=\lceil log_k r \rceil (n-1)\lceil log_k r \rceil = (n-1)\lceil log_2 r \rceil$ 。
可见，使用败者树后，内部归并的比较次数与k无关了。因此，只要内存空间允许，增大的并路数k将有效地减少归并树的高度，从而减少I/O次数，提高外部排序的速度。
值得说明的是，归并路数k并不是越大越好。归并路数k增大时，相应地需要增加输入缓冲区的个数。若可供使用的内存空间不变，势必要减少每个输入缓冲区的容量，使得内存、外存交换数据的次数增大。当k值过大时，虽然归并趟数会减少，但读/写外存的次数仍会增加。
可知，减少归并段个数r也可以减少归并趟数S。若总的记录个数为n，每个归并段的长度为l，则归并段的个数r=⌈n/l⌉。采用内部排序算法得到的各个初始归并段长度都相同（除最后一段外），它依赖于内部排序时可用内存工作区的大小。因此，必须探索新的方法，用来产生更长的初始归并段，即置换-选择算法。
设初始待排文件为FI，初始归并段输出文件为FO，内存工作区为WA，FO和WA的初始状态为空，WA可容纳w个记录。置换-选择算法的步骤如下：
1. 从FI输入w个记录到工作区WA。
2. 从WA中选出其中关键字取最小值的记录，记为MINIMAX记录。
3. 将MINIMAX记录输出到FO中去。
4. 若FI不空，则从FI输入下一个记录到WA中。
5. 从WA中所有关键字比MINIMAX记录的关键字大的记录中选出最小关键字记录，作为新的MINIMAX记录。
6. 重复3~5，直至在WA中选不出新的MINIMAX记录为止，由此得到一个初始归并段，输出一个归并段的结束标志到FO中去。
7. 重复2~6，直至WA为空。由此得到全部初始归并段。
上述算法，在WA中选择MINIMAX记录的过程需利用败者树来实现。
文件经过置换-选择排序后，得到的是长度不等的初始归并段。下面讨论如何组织长度不等的初始归并段的归并顺序，使得I/O次数最少。
假设由置换-选择排序得到9个初始归并段，其长度（记录数）依次为9，30，12，18，3，17，2，6，24。现做3路平衡归并。
各叶结点表示一个初始归并段，上面的权值表示该归并段的长度，叶结点到根的路径长度表示其参加归并的趟数，各非叶结点代表归并成的新归并段，根结点表示最终生成的归并段。树的带权路径长度WPL为归并过程中的总读记录数，所以I/O次数=2×WPL。
显然，归并方案不同，所得归并树不同，树的带权路径长度亦不同。为了优化归并树的WPL，可以将哈夫曼树的思想推广到m叉树的情形，在归并树中，让记录数少的初始归并段最先归并，记录数多的初始归并段最晚归并，就可以建立总的I/O次数最少的最佳归并树。
若初始归并段不足以构成一棵严格k叉树（也称正则k叉树）时，需添加长度为0的“虚段”，按照哈夫曼树的原则，权为0的叶子应离树根最远。
如何判定添加虚设的数目？
设度为0的结点有 $n_0$ $n_{0}$ 个，度为k的结点有 $n_k$ $n_{k}$ 个，归并树的结点总数为n，则有：
- $n=n_k+n_0$ （总结点数=度为k的结点数+度为0的结点数）
- $n=kn_k+1$ （总结点数=所有结点数的度数之和+1）
  因此，对严格k叉树有 $n_0=(k-1)n_k+1$ ，由此可得 $n_k=(n_0-1)/(k-1)$ 。
- 若 $(n_0-1)%(k-1)=0$ （%为取余运算），则说明这 $n_0$ 个叶结点（初始归并段）正好可以构造k叉归并树。此时，内节点有 $n_k$ 个。
- 若 $(n_0-1)%(k-1)=u≠0$ ，需要加上k-1-u个虚段。

选择合适排序算法

具有在不同的应用需求下，能够依据各种排序算法的特点选择合适排序算法的能力

九、矩阵和串

矩阵和串的定义

数组定义-王道p104

矩阵：矩阵是一个由 m 行 n 列元素组成的二维数组，通常表示为 $A_{m×n}$ ，其中 m 是矩阵的行数，n 是矩阵的列数。

串：字符串简称串，串是由零个或多个字符组成的有限序列。一般记为 $S='a_1 a_2 \cdots a_n'(n≥0)$ 。其中，S是串名，单引号括起来的字符序列是串的值； $a_i$ 可以是字母、数字或其他字符；串中字符的个数n称为串的长度。n=0时的串称为空串（用∅表示）。

特殊矩阵的压缩存储

压缩存储：指为多个值相同的元素只分配一个存储空间，对零元素不分配空间。
特殊矩阵：指具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。常见的特殊矩阵有对称矩阵、上（下）三角矩阵、对角矩阵等。
特殊矩阵的压缩存储方法：找出特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律性分布的、值相同的多个矩阵元素压缩到一个存储空间中。

考场随机应变。
三对角矩阵也称带状矩阵。

稀疏矩阵的三元组表示法以及相应的操作

三元组：行标i，列标j，值 $a_{i,j}$ 。
要保存：三元组表，稀疏矩阵的行数、列数和非零元素的个数。

多维数组和一维数组的映射

串的模式匹配

子串的定位操作通常称为模式匹配，它求的是子串（常称模式串）在主串中的位置。
Brute-Force
匹配失败时，i=i-j+2;j=1;
时间O(mn)

KMP

时间O(m+n)
PM表、next表（next为PM右移一位并+1）
| 编号| 1 | 2 | 3 | 4 | 5 |
|——-|—-|—-|—-|—-|—-|
| S | a | b | c | a | c |
| PM | 0 | 0 | 0 | 1 | 0 |
|next| 0 | 1 | 1 | 1 | 2 |
nextval表(遇到 $p_j=p_{next[j]}$ ，则递归至不等于为止)
|主串| a | a | a | b | a | a | a | a | b |
|——|—-|—-|—-|——|—-|—-|—-|—-|—-|
|模式串|a | a | a | a| b | | | | |
| j | 1 | 2 | 3 | 4 | 5 | | | | |
|next[j]|0|1 | 2 | 3 | 4 | | | | |
|nextval[j]|0|0|0| 0 | 4 | | | | |

一、数据结构基本概念

数据

数据元素

数据项

数据对象

数据、数据元素、数据项之间的关系

数据结构的定义

数据结构的三要素

数据的逻辑结构

数据的物理结构

数据的运算的定义

数据类型

数据类型、抽象数据类型和数据结构之间的关系

二、算法和算法分析

算法的定义

算法的特性（五个）

算法设计的要求

算法的时间、空间复杂度的定义及计算

衡量算法在资源上的两个方面

算法的渐进性分析方法，会用该方法对算法进行评估

渐进分析

算法分析

渐进最优

三个标记法

时空权衡原则

三、线性表

线性表的定义

线性表的逻辑结构

线性表的基本操作

顺序表的定义

顺序表的特点

用顺序存储结构对线性表基本操作的实现

链式表的定义

链式表的特点

用链式存储结构对线性表基本操作的实现（见下）

链式存储结构的实现技术（比如）

单向链表

静态链表

双向链表

单循环链表

双向循环链表

带头结点的链表

双向循环链表

线性表的应用

一元多项式的表示和相加

具有在实际中选取不同存储结构的判断能力

顺序表和链表的比较

在实际中怎样选取存储结构

广义表

广义表的定义

广义表的基本概念

广义表的存储结构

广义表的计算（以第二种存储结构为例）

四、栈和队列

栈的定义

栈的逻辑结构

栈的特点（考点没写）

栈的操作特性（考点没写）

栈的基本操作

栈的数学性质（考点没写）

顺序栈的定义

链式栈的定义

顺序栈和链式栈的特点

顺序栈的基本操作

链栈的基本操作

共享栈（考点没写）

队列的定义

队列的逻辑结构

队列的操作特性（考点没写）

队列的特点

队列的基本操作

顺序队列的定义

链式队列的定义

顺序队列和链式队列的特点

顺序队列的基本操作

链队列的基本操作

顺序存储结构中实现循环队列的具体要求

循环队列——队列的顺序存储结构

理解递归调用和栈之间的关系

掌握栈和队列的经典应用