第1章绪论

1. 编写解决实际问题程序的流程 (重)

用计算机解决一个具体的问题大致需要经过以下几个步骤：

分析问题，确定数据模型。
设计相应的算法。
编写程序，运行并调试程序，直至得到正确的结果。
寻求数据模型的实质是分析问题，并找出这些操作对象之间的关系，然后用数学语言加以描述。

2. 数据结构的定义、基本原理和基本方法

基本定义：数据元素：是数据（集合）中的一个“个体”，它是数据的基本单位。数据项：数据项是用来描述数据元素的，它是数据的最小单位。数据对象：具有相同性质的若干个数据元素的集合。数据结构是指所有数据元素以及数据元素之间的关系，可以看作相互之间存在着某种特定关系的数据元素的集合。 数据结构 = 数据对象 + 结构
基本原理：数据结构通常包括数据的逻辑结构、数据的存储结构以及数据的运算三个方面。
数据的逻辑结构：由数据元素之间的逻辑关系构成
数据的存储结构：数据元素及其关系在计算机存储器中的存储表示，也成为数据的物理结构。
数据的运算：施加在该数据上的操作。
基本方法：1. 同一逻辑结构可以对应多种存储结构。2. 同样的运算，在不同的存储结构中，其实现过程是不同的

3. 逻辑结构类型

数据的逻辑结构是从数据元素的逻辑关系上描述数据的，独立于计算机。归纳起来分为以下四类：

集合：数据元素之间除了“同属于一个集合”的关系外，别无其他关系。特点：是最松散的，不受任何制约的关系。
线性结构：数据元素之间存在一对一的关系。特点：开始元素和终端元素都是唯一的，除此之外，其余元素都有且仅有一个前驱元素和一个后继元素。
树形结构：数据元素之间存在一对多的关系。
特点：开始元素唯一，终端元素不唯一。除终端元素以外，每个元素有一个或多个后继元素；除开始元素外，每个元素有且仅有一个前驱元素。
图形结构：数据元素之间存在多对多的关系。 树形结构和图形结构统称为非线性结构。
特点：所有元素都可能有多个前驱元素和多个后继元素。

4. 存储结构类型

存储结构是逻辑结构在计算机存储器中的存储表示，常用类型有 4 种：

顺序存储结构：采用一组连续的存储单元存放所有的数据元素，逻辑上相邻的元素在存储位置上也相邻。
链式存储结构：每个逻辑元素用一个内存结点存储，结点地址不一定连续，通过指针域表示逻辑关系。
索引存储结构：在存储数据元素信息的同时，还建立附加的索引表。
哈希（或散列）存储结构：根据元素的关键字通过哈希函数直接计算出一个值，并将其作为该元素的存储地址。

5. 抽象数据类型 (ADT)

定义：抽象数据类型（abstract data type, ADT）指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算，而不考虑计算机的具体存储结构和运算的具体实现算法。
描述格式：通常采用 (D, R, P) 三元组表示，其中 D 是数据对象，R 是 D 上的关系，P 是 D 中数据操作的基本运算集。
核心特征：具有数据抽象和数据封装两个重要特征。

6. 算法及其特征、要求、效率度量与时间复杂度 (重)

算法定义：算法是对特定问题求解步骤的一种描述，它是指令的有限序列。
五个特征：
1. 有穷性：在执行有穷步之后结束，且每一步都在有穷时间内完成。
2. 确定性：每条指令都有确切含义，无二义性。
3. 可行性：算法中的所有操作都足够基本，可以通过有限次基本运算完成。
4. 有输入：有零个或多个输入。
5. 有输出：有一个或多个输出。
设计目标（要求）：正确性、可使用性、可读性、健壮性、高效率与低存储量需求。
效率度量方法：包括事后统计法和事前估算法。
事后统计法：编写算法对应程序，统计其执行时间
事前估算法：撇开这些与计算机硬件、软件有关的因素，认为算法的执行时间是问题规模n的函数
时间复杂度：指算法运行所需时间，通过算法中基本操作的频度 来衡量，记作。它表示随问题规模增大时算法执行时间的增长率。
空间复杂度：是对一个算法在运行过程中临时占用存储空间大小的量度，记作。

7. 数据结构、算法和程序的区别

核心公式：数据结构 + 算法 = 程序。
主要区别：
- 算法是程序的“灵魂”，解决“做什么”和“如何做”的问题。算法是解题的方法和步骤。
  没有算法，程序就成了“无本之木，无源之水”。
  算法在计算机科学中处于极其重要的核心地位
- 数据结构是程序的“原料”，是对问题处理对象的组织和描述。程序总是以数据为处理对象。将无组织的数据按要求组成数据结构，是设计高效程序的基础
- 程序是用某种程序设计语言对算法的具体实现。由程序设计语言描述的算法就是计算机程序
相互联系：算法的设计取决于数据的逻辑结构，算法的实现取决于数据的存储结构。

第2章线性表

1. 线性结构的特点

一对一关系：线性结构中数据元素之间存在一对一的关系。
唯一首尾：在非空线性结构中，有且仅有一个开始结点和终端结点。
前驱与后继：除开始结点外，每个结点有且仅有一个直接前驱；除终端结点外，每个结点有且仅有一个直接后继。
序列性：所有元素在线性表中都有唯一的序号。

2. 线性表定义 (重)

基本概念：线性表是由 ()个具有相同特性的数据元素组成的有限序列。
数学表示：通常记为，其中是表头元素，是表尾元素。
基本特性：
- 有限性：表中元素的个数是有限的。
- 一致性：所有元素具有相同的性质，属于同一数据类型。
- 有序性：元素之间的相对位置是线性的，存在唯一的先后次序。
抽象数据类型 (ADT)：线性表的操作通常包括初始化、求长度、求某个位置元素、按值查找、插入和删除等。

3. 线性表的插入与删除

3.1 顺序存储结构（顺序表）

插入逻辑：在第个位置插入新元素，需要将原第个及之后的元素（物理下标为到）依次向后移动一个位置，腾出空间后再存入新值，最后表长加 1。
删除逻辑：删除第个元素，需要将第个至最后一个元素依次向前移动一个位置，覆盖被删除的元素，最后表长减 1。
移动规律：插入时需从后往前移动；删除时需从前往后移动。

3.2 链式存储结构（单链表）

插入逻辑：要在结点之后插入结点，需修改指针：先让的后继指向原本的后继，再让的后继指向。
删除逻辑：要删除结点的后继结点，需让的指针域直接跳过，指向的后继结点，然后释放的存储空间。
特点：插入和删除操作不需要移动元素，只需修改相关结点的指针域。

4. 顺序表和单链表的优缺点 (重)

4.1 顺序表

优点：
- 存储密度大：无须为表示线性表中元素之间的逻辑关系而增加额外的存储空间。
- 具有随机存取特性
缺点：
- 修改效率低：插入和删除操作平均需要移动约一半的元素，时间复杂度为。
- 空间分配不灵活：需要预先分配连续的整块空间，可能导致空间浪费或溢出。

4.2 单链表

优点：
- 修改效率高：插入和删除只需改变指针指向，不需要移动元素。
- 空间利用灵活：由于采用结点的动态分配方式，具有良好的适应性。
缺点：
- 非随机访问：不具有随机存储特性。
- 存储密度低：为表示线性表中元素之间的逻辑关系而需要增加额外的存储空间。

第3章栈和队列

1. 栈的定义与操作规则 (重)

基本概念：栈是一种只能在表的一端（称为栈顶）进行插入或删除操作的线性表。
物理结构：另一端固定不动，称为栈底。
操作规则：遵循“后进先出”的原则，最先进入栈的元素最后被删除，最后进入的则最先被弹出。
状态判定：
- 顺序栈：栈空的条件为 top == -1；栈满的条件为 top == MaxSize - 1。
- 链栈：通常采用带头结点的单链表实现，栈空的条件为头结点的指针域为 NULL（s->next == NULL），且由于动态分配空间，一般不考虑栈满情况。

2. 栈的入栈和出栈 (重)

进栈：
- 在顺序栈中，先将栈顶指针 top 加 1，然后将新元素存入指针指向的位置。
- 在链栈中，创建一个新结点，将其插入到头结点之后（作为新的首结点）。
出栈：
- 在顺序栈中，先取出当前指针指向的元素值，再将 top 减 1。
- 在链栈中，提取首结点的元素值，然后将其从链表中删除并释放存储空间。
时间复杂度：无论是进栈还是出栈，其基本操作的时间复杂度均为。

3. 队列的定义与操作规则

基本概念：队列是一种操作受限的线性表，仅允许在表的一端（队尾）进行插入，在另一端（队头）进行删除。向队列中插入新元素称为进队或入队，新元素进队后就成为新的队尾元素。队列中删除元素称为出队或离队，元素出队后，其后继元素就成为队首元素。
操作规则：遵循“先进先出”的原则，即先入队的元素必须先出队。
环形队列（循环队列）：为了解决顺序队列在删除元素后出现的“假溢出”问题（即队尾指针已达上限但队头仍有空位），逻辑上将数组头尾相连形成环形。
- 关键公式：队头/队尾指针加 1 操作通过取余运算实现：rear = (rear + 1) % MaxSize。
- 队满判定：为区分队空和队满，通常牺牲一个存储单元，判定条件为 (rear + 1) % MaxSize == front。

4. 队列的入队与出队

**进队：
- 在环形队列中，先检查队是否已满，若未满则将 rear 指针循环进 1，并将新元素插入到该位置。
- 在链队中，创建一个新结点并将其链接到队尾指针 rear 之后，随后更新 rear 指向该新结点。
出队：
- 在环形队列中，先检查队是否为空，若不为空则将 front 指针循环进 1，并取出该位置的元素。
- 在链队中，取出队头指针 front 所指向结点的后继结点值，并将其从链表中移除；若队中仅剩一个元素，删除后需将 rear 指回 front。

5. 逆波兰表达式（后缀表达式）（看）

定义：后缀表达式是将运算符写在操作数之后的表达式形式，不需要括号且不依赖运算符优先级来确定计算顺序。
转换逻辑（中缀转后缀）：
1. 从左到右扫描中缀表达式。
2. 遇到数字直接输出到后缀表达式序列中。
3. 遇到运算符，根据优先级与栈顶运算符比较：优先级更高则进栈；更低或相等则将栈顶运算符出队并输出，直到当前运算符可以进栈为止。
4. 遇到左括号 ( 直接进栈，遇到右括号 ) 则将栈内运算符逐个弹出并输出，直到遇到 ( 为止。
求值算法：
- 使用一个操作数栈。
- 从左往右扫描后缀表达式：遇到数字则压入栈；遇到运算符则从栈中弹出两个操作数（注意先弹出的为右操作数），进行计算后将结果重新压入栈。
- 最终栈顶留下的数值即为表达式结果。

第4章串

1. 串类型的定义、特点及其相关概念

定义：串是由零个或多个字符组成的有限序列，记为。
空串：长度为零的串，不包含任何字符，记为或双引号 ""。
空格串：由一个或多个空格组成的串，其长度为其中的空格个数，不同于空串。
串相等：只有当两个串的长度相等，且对应位置上的字符都相同时，才称两个串相等。
逻辑特征：串是一种特殊的线性表，其特殊性体现在数据元素仅由字符组成，且通常将串作为一个整体进行处理（如查找子串、替换等）。

2. 串长、子串

串长：串中包含的字符个数。
子串：串中任意连续字符组成的子序列。包含子串的串称为主串。
子串位置：子串在主串中的序号，通常以子串第一个字符在主串中的位置来表示。
前缀与后缀：
- 前缀：指从第一个字符开始，到某个位置（不含最后一个字符）结束的子串。
- 后缀：指从某个位置（不含第一个字符）开始，到最后一个字符结束的子串。

3. 串的模式匹配

模式匹配是指在主串（目标串）中寻找与模式串相等的子串的过程。

3.1 Brute-Force 算法（暴力匹配）

匹配原理：从目标串的第一个字符开始与模式串的第一个字符比较。若相等，则继续比较后续字符；若不等，则目标串回溯到上一次开始比较位置的下一个字符（），模式串退回到第一个字符（），重新开始匹配。
缺点：存在大量重复的回溯，效率较低。在最坏情况下，时间复杂度为，和分别为主串和模式串的长度。

3.2 KMP 算法 (重)

核心改进：消除了主串指针的回溯。当发生失配时，主串指针不动，利用已经匹配过的“部分匹配”信息，通过 next 数组将模式串向右滑动尽可能远的距离，使模式串指针跳到指定位置继续比较。
时间复杂度：，在主串长度很大时比 BF 算法效率显著提高。

3.3 Next 数组

定义：表示当模式串第个字符发生失配时，模式串应回退到的位置。
求值规则：
1. 。
2. 。
3. 其他位置：寻找模式串前个字符中，相等的前缀和后缀的最大长度 。
Nextval 数组：KMP 的改进版。如果模式串中与回退后的相等，则继续回退，以避免无效的重复比较。

第6章数组和广义表

1. 数组的定义、特征

从逻辑结构上看，一维数组是（）个相同类型数据元素构成的有限序列。在（）维数组中，每个元素的位置由个整数的维下标标识。
数组具有以下性质：
(1) 数组中的数据元素数目固定；
(2) 数组中的数据元素具有相同的数据类型；
(3) 数组中的每个数据元素都和一组唯一的下标对应；
(4) 数组具有随机存储特性。

2. 二维数组的存储结构 (重)

数组通常采用顺序存储结构，对于二维数组（下标从 1 开始），有两类存储方式：

按行优先存放：先存储第 1 行，紧接着存储第 2 行，以此类推；其地址公式为。
按列优先存放：先存储第 1 列，紧接着存储第 2 列，以此类推；其地址公式为。

3. 特殊矩阵的压缩存储 (重)

特殊矩阵主要指当矩阵中有很多值相同的元素且分布有一定规律时，为了节省空间而进行的压缩存储：

对称矩阵：满足。按行优先存储下三角（含对角线）部分，下标从 0 开始时，在压缩数组中的位置为：若，；若，。
三角矩阵：下（或上）三角部分元素均为常数。将非重复元素按行优先存入一维数组，最后位置存放。上三角矩阵（）的映射公式为。
对角矩阵：所有非零元素集中在以主对角线为中心的带状区域中。当半带宽时，映射公式为。

4. 稀疏矩阵的三元组表示

当一个矩阵中非零元素个数相对于元素总数非常小时（即），称为稀疏矩阵。三元组表示法是只存储非零元素的行号、列号和元素值，构成一个三元组线性表。这种顺序存储结构可以简化大多数稀疏矩阵运算，但在进行某些操作时会丢失随机存取特性。

5. 稀疏矩阵的十字链表表示

十字链表是一种链式存储结构，为矩阵的每行和每列各设一个带头结点的循环单链表。每个非零元素结点包含五个域：row（行号）、col（列号）、value（元素值）、right（指向同行后继）和 down（指向同列后继）。这种结构大大降低了稀疏矩阵运算的时间复杂度。

6. 广义表的定义及特性 (重)

广义表是线性表的推广，是有个元素的有限序列，逻辑结构采用括号表示法：。广义表具有以下 5 个重要特性：

数据元素是有相对次序的。
广义表的长度定义为最外层包含元素的个数，；若，称为空表。
广义表的深度定义为所含括号的重数，其中原子的深度为 0，空表的深度为 1。
广义表可以共享，一个广义表可以被其他广义表共享，这种广义表称为再入表。
广义表可以是一个递归的表，一个广义表可以是自己的子表，这种广义表称为递归表；理论上讲，递归表的深度是无穷大，而长度是有限的。此外，非空广义表第一个元素称为表头（head），其余元素组成的广义表称为表尾（tail）。

7. 广义表的存储结构

广义表通常采用链式存储结构，结点包含标志域 tag、原子值或子表指针域、指向后继结点的指针域：

tag 标志域：用于区分两类结点，由 tag 决定是使用 sublist 还是 data 域。
原子结点 ()：第 2 个域为 data，存放相应原子元素信息。
表结点 ()：第 2 个域为 sublist，存放指向子表中第一个元素对应结点的地址。
link 指针域：存放同一层中下一个元素对应结点的地址，当没有兄弟结点时，其 link 域为 NULL。

第7章树和二叉树

1. 树的定义和基本术语

定义：树（tree）是由 () 个结点组成的有限集合,。当时称为空树,。在任意一棵非空树中：(1) 有且仅有一个称为根（root）的结点；(2) 除根结点外的其余结点可分为 () 个互不相交的有限集，其中每一个集合本身又是一棵树，称为根的子树（subtree）,。
基本术语：
- 结点的度：结点所拥有的子树的个数。
- 树的度：树中各结点度的最大值。
- 叶子结点：度为 0 的结点，也称终端结点。
- 分支结点：度不为 0 的结点，也称非终端结点。
- 孩子/双亲/兄弟：结点的子树的根称为该结点的孩子；该结点称为孩子的双亲；同一双亲的孩子之间互为兄弟。
- 路径/路径长度：两个结点序列之间的连线序列称为路径，路径上经过的边数（结点数减 1）称为路径长度。
- 结点的层次/树的高度：根为第一层，其孩子为第二层，依此类推；树中结点的最大层次称为树的高度（或深度）。
- 森林： () 棵互不相交的树的集合。

2. 树的逻辑表示法

树的常用表示方法包括,：

树形表示法：用圆圈表示结点，用连线表示分支关系。
文氏图表示法：用集合的包含关系来表示，由大圆圈包含小圆圈形成,。
凹入表示法：通过条形长短和缩进反映结点的层次关系。
括号表示法：用括号表示子树关系，如。

3. 结点的度与树的度

• 结点的度：指该结点子树的个数。

• 树的度：树中各结点度的最大值。度为 m 的树通常称为 m 次树。

4. 树的性质 (重)

性质 1：树中的结点总数等于所有结点的度数之和加 1。
性质 2：度为的树中第层上最多有个结点 ()。
性质 3：高度为的次树最多有个结点。
性质 4：具有个结点的次树的最小高度为。

5. 数据的遍历（树的遍历） (重)

树的遍历主要有三类方式,：

先根遍历：先访问根结点，然后按从左到右的顺序先根遍历每一棵子树。
后根遍历：先按从左到右的顺序后根遍历每一棵子树，最后访问根结点。
层次遍历：从根结点开始，按从上到下、从左到右的次序访问每一个结点。

5. 二叉树的定义、特点与性质

定义：二叉树是 n 个结点的有限集合，或为空，或由根结点及两棵互不相交的、分别称为左子树和右子树的二叉树组成。
逻辑结构表示：与树相同，采用树形、括号等表示。
特点：二叉树严格区分左、右子树，且每个结点最多只有两棵子树（度）。
基本性质,：

非空二叉树上的叶子结点数等于双分支结点数加 1（即）。
非空二叉树的第层上最多有个结点 ()。
高度为的二叉树最多有个结点 ()。

7 . 满二叉树与完全二叉树

满二叉树：所有分支结点都有左右孩子，且叶子全在最后一层。高度为的满二叉树有个结点。
完全二叉树：结点的个位置与对应的满二叉树的前个位置完全一致。
- 特点：叶子结点只在最下两层出现；度为 1 的结点最多只有一个。
- 性质：编号为的结点，其双亲（若有）编号为；左孩子为，右孩子为。

8. 树/森林与二叉树的转换

树/森林转换为二叉树：遵循“左孩子右兄弟”原则。树的根结点转换为二叉树根结点，左孩子指向该结点的第一个孩子，右孩子指向该结点的下一个兄弟。
1. 树中所有相邻兄弟之间加一条连线
2. 对树中的每个结点只保留它与长子之间的连线，删除与其他孩子之间的连线
3. 以树的根节点为轴心，将整棵树顺时针转动45°，使之结构层次分明
二叉树还原为树/森林：是上述过程的逆过程。若二叉树根结点的右孩子为空，还原为树；若不为空，则还原为森林,。
1. 若某节点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子等都与该结点的双亲结点用连线连起来。
2. 删除原二叉树中所有双亲结点与右孩子节点之间的连线
3. 整理由前面两步得到的树，即以根结点为轴心，逆时针转动45°，使之结构层次分明

8. 二叉树的存储结构

顺序存储结构：用地址连续的存储单元存放。仅适用于完全二叉树；对于一般二叉树，需补成完全二叉树形式，会浪费空间,。
链式存储结构：常用二叉链表，每个结点包含 data、lchild 和 rchild 三个域,。

9. 构造二叉树

• 唯一性：已知先序+中序或后序+中序序列可唯一确定一棵二叉树。

• 局限性：仅已知先序和后序无法唯一确定二叉树形态。

10. 线索二叉树 (重)

二叉树的线索化过程：
以该方法遍历一棵二叉树
在遍历的过程中，检查当前访问结点的左右指针域是否为空如果左指针域为空，将它改为指向前驱结点的线索如果右指针域为空，将它改为指向后继结点的线索

11. 构造赫夫曼树

• 术语：路径长度是路径上的分支数；带权路径长度 (WPL) 是叶子权值与路径长度之积的和。

• 构造方法：每次选出权值最小的两棵树作为左右子树合并，新树权值为两者之和，直到只剩一棵树。

• 性质：对应 n0 个叶子，总结点数 n=2n0−1，且不存在度为 1 的结点。

第 8 章图 (Graphs)

图是由顶点集和边集组成的，记为。

8.1 图的定义和术语

1. 基本分类

有向图 ：边是有方向的，用尖括号表示，如表示从到的一条弧。
**无向图：边无方向，用圆括号表示，如。
**完全图：
- 无向完全图：每两个顶点之间都存在一条边，共有条边。
- 有向完全图：每两个顶点之间都存在方向相反的两条弧，共有条弧。

2. 顶点的度、入度和出度

度：关联于该顶点的边数。
入度：以该顶点为终点的弧的数目。
出度：以该顶点为始点的弧的数目。
性质：图中所有顶点的度之和等于边数的两倍。

3. 路径与连通性 (重)

1. 路径与路径长度

路径的定义：在一个图中，从顶点到顶点的一条路径是一个顶点序列。
路径存在条件：若此图是无向图，则序列中相邻顶点对均属于边集；若此图是有向图，则序列中相邻顶点对均属于弧集。
路径长度 (Path Length)：路径长度是指一条路径上经过的边的数目。
计算方式：若路径由个顶点组成，其路径长度为（即顶点数减 1）。

2. 简单路径与回路

简单路径：指一条路径上除开始顶点和结束顶点外，其余顶点均不相同的路径。
回路或环：若一条路径上的开始顶点与结束顶点为同一个顶点，则此路径被称为回路或环。
简单回路：开始顶点与结束顶点相同，且其余顶点均不相同的回路被称为简单回路或简单环。

3. 无向图的连通性

连通：在无向图中，若从顶点到顶点有路径，则称顶点和顶点是连通的。
连通图：若图中任意两个顶点都是连通的，则称该图为连通图。
非连通图：若图中至少存在一对顶点之间没有路径，则该图为非连通图。
连通分量：无向图中的极大连通子图称为的连通分量。
- 极大性：意味着连通分量包含该子图中所有顶点关联的所有边。
- 性质：连通图的连通分量只有一个，即其本身；而非连通图有多个连通分量。

4. 有向图的连通性

连通：在有向图中，若从顶点到顶点有路径，则称顶点到顶点是连通的。
强连通：在有向图中，若对于每一对顶点和，从顶点到顶点和从顶点到顶点都存在路径，则称该有向图是强连通的。
强连通分量：有向图中的极大强连通子图称为的强连通分量。
- 性质：强连通图只有一个强连通分量（即其本身），非强连通图则有多个强连通分量。
判定特征：在一个含有个顶点的强连通图内，至少要有条边且构成一个环形。

5. 连通性分析的方法（非强连通图）

在非强连通图中找强连通分量的方法包括：
1. 在图中寻找有向环。
2. 扩展该有向环：如果某个顶点到该环中的任一顶点有路径，并且该环中的任一顶点到该顶点也有路径，则将该顶点并入此强连通分量。

8.2 图的存储结构：邻接矩阵 (数组表示法)

邻接矩阵是采用二维数组表示顶点之间相邻关系的存储结构。

定义：
- 若，则（或权值）；否则（或）。
特点：
1. 唯一性：图的邻接矩阵表示是唯一的。
2. 空间复杂度：，与边数无关，适合存储稠密图。
3. 度计算：
  - 无向图：第行（或列）非零元素个数即为顶点的度。
  - 有向图：第行非零元素个数为出度，第列为入度。

8.3 图的遍历

图的遍历是从图中某个顶点出发，按照某种搜索方法沿着边访问图中所有顶点，且每个顶点仅被访问一次。

1. 深度优先遍历 (DFS) （重）

过程：类似于树的先序遍历。从初始点出发，访问初始顶点，然后选择一个与相邻且未被访问的顶点出发进行深度优先搜索，直到图中所有和有路径相通的顶点都被访问。
算法实现：通常使用递归或栈。

2. 广度优先遍历 (BFS) （重）

过程：类似于树的层次遍历。从初始点出发，然后依次访问的所有未被访问的邻接点，再按的次序访问每一个顶点的所有未被访问过的邻接点。以此类推直到图中所有和初始点有路径相遇的顶点都被访问过为止
算法实现：必须使用队列。

3. 性能分析

采用邻接矩阵存储时，时间复杂度均为。
采用邻接表存储时，时间复杂度均为。

8.4 最小生成树（重）

包含图中全部个顶点和条边。
其中条边权值之和最小的生成树就叫最小生成树

1. 普里姆算法（重）

思路：从某个顶点开始，每次从未加入最小生成树的顶点中选择一个距离当前最小生成树最近的顶点加入。
特点：加点法。时间。

2. 克鲁斯卡尔算法

思路：按权值从小到大选择边，若该边不与已选边构成回路，则加入最小生成树。

8.5 拓扑排序（重）

拓扑排序是对有向无环图顶点的一种线性排序。

AOV 网：用顶点表示活动，用有向边表示活动之间优先关系的网。
过程：
1. 从图中选择一个入度为 0 的顶点并输出。
2. 从图中删除该顶点及所有以它为起点的有向边。
3. 重复上述步骤，直到图中不再存在入度为 0 的顶点。
结论：若输出顶点数少于总顶点数，说明图中存在回路。

8.6 AOE 网与关键路径（重）

AOE 网：用有向边表示活动，边上的权值表示活动的持续时间，顶点表示“事件”。
关键路径：从源点到汇点具有最大路径长度的路径。路径上的活动称为关键活动。
四个核心参数：
1. 事件最早发生时间。
2. 事件最迟发生时间。
3. 活动最早开始时间。
4. 活动最迟开始时间。
判断准则：若，则该活动为关键活动。

8.7 Dijkstra 算法 (最短路径) （重）

用于求解带权有向图中单源最短路径问题。

基本思想：
- 将顶点分为两组：已求出最短路径的顶点集合和未确定的集合。
- 初始时。
- 不断从中选择距离源点最近的顶点加入，并更新中其他顶点经由到达源点的距离。
算法复杂度：。
注意：Dijkstra 算法不适用于含有负权值的图。

步骤	集合 (已确定)	集合 (待选)	最短路径数组	前驱路径数组
初始	{0}	{1, 2, 3, 4, 5, 6}	(0, 4, 6, 6, ∞, ∞, ∞)	(0, 0, 0, 0, -1, -1, -1)
1	{0, 1}	{2, 3, 4, 5, 6}	(0, 4, 5, 6, 11, ∞, ∞)	(0, 0, 1, 0, 1, -1, -1)
2	{0, 1, 2}	{3, 4, 5, 6}	(0, 4, 5, 6, 9, 11, ∞)	(0, 0, 1, 0, 2, 2, -1)
3	{0, 1, 2, 3}	{4, 5, 6}	(0, 4, 5, 6, 9, 8, ∞)	(0, 0, 1, 0, 2, 3, -1)
4	{0, 1, 2, 3, 5}	{4, 6}	(0, 4, 5, 6, 9, 8, 16)	(0, 0, 1, 0, 2, 3, 5)
5	{0, 1, 2, 3, 5, 4}	{6}	(0, 4, 5, 6, 9, 8, 11)	(0, 0, 1, 0, 2, 3, 4)
6	{0, 1, 2, 3, 5, 4, 6}	{}	(0, 4, 5, 6, 9, 8, 11)	(0, 0, 1, 0, 2, 3, 4)

算法执行结束后，从顶点 0 出发的最短路径长度如下：

0 1: 长度 4，路径 0,1
0 2: 长度 5，路径 0,1,2
0 3: 长度 6，路径 0,3
0 5: 长度 8，路径 0,3,5
0 4: 长度 9，路径 0,1,2,5,4 (注：课本修正后路径)
0 6: 长度 11，路径 0,1,2,5,4,6

第 9 章查找

9.1 查找的基本概念

查找表：由同一类型的数据元素（或记录）组成的集合。
关键字：记录中某个数据项的值，用以标识一个数据元素。能唯一标识一个记录的称为主关键字。
查找：在含有个元素的查找表中找出关键字等于给定值的记录。
静态与动态查找表：静态查找表不涉及对表的修改；动态查找表在查找过程中会进行插入或删除操作。
平均查找长度：衡量算法性能的核心指标，指确定记录在表中位置时关键字比较次数的平均值。
- 公式：，其中为查找第个记录的概率，为找到该记录所需的比较次数。

9.2 线性表的查找

1. 顺序查找

原理：从表的一端向另一端逐个将关键字与给定值进行比较。
ASL 计算（等概率）：
- 成功时： $成功$ 。
- 不成功时：引入“哨兵”后， $不成功$ 。
时间复杂度：。

2. 折半查找（重）

前提条件：线性表必须采用顺序存储结构，且表中元素按关键字有序排列。
执行逻辑：设定 low 和 high 指向区间首尾，取 mid = (low + high) / 2。若，则在左半区 [low, mid-1] 继续查找；若，则在右半区 [mid+1, high] 继续查找。
判定树 (Decision Tree)：描述折半查找过程的二叉树，其高度为。
ASL 计算：。
时间复杂度：。

3. 分块查找

存储结构：由索引表和主表组成。要求“块间有序”，即后一个块中最小关键字大于前一个块最大关键字，但块内可以无序。
查找过程：先在索引表中确定待查记录所在的块（可顺序或折半查找索引），再在块内进行顺序查找。
ASL 计算： $索引块内$ 。

9.3 树表的查找

1. 二叉排序树 (BST) （重）

定义性质：
1. 若左子树不空，则左子树上所有结点关键字均小于根。
2. 若右子树不空，则右子树上所有结点关键字均大于根。
3. 左右子树也各是一棵二叉排序树。
特点：按中序遍历二叉排序树可以得到一个按关键字递增的有序序列。
创建与插入：插入总是作为新的叶子结点进行，且保持 BST 的性质。
结点删除：
- 叶子结点：直接删除。
- 只有左（或右）子树：用子树替代被删结点。
- 既有左子树又有右子树：用该结点的中序前驱（左子树中最大点）或中序后继（右子树中最小点）的值替代它，然后删除原前驱或后继。

2. 平衡二叉树 (AVL 树)

定义：左、右子树高度差的绝对值不超过 1 的二叉排序树。
平衡调整 (旋转)：
- LL 型：在失衡点 A 的左孩子 B 的左子树插入。调整：A 右旋。
- RR 型：在失衡点 A 的右孩子 B 的右子树插入。调整：A 左旋。
- LR 型：在 A 的左孩子 B 的右子树插入。调整：B 左旋再 A 右旋。
- RL 型：在 A 的右孩子 B 的左子树插入。调整：B 右旋再 A 左旋。
查找复杂度：。

3. 平衡二叉树的调整（重）

基本概念

平衡因子：结点的左子树高度减去右子树高度的差值。
平衡标准：AVL 树中所有结点的平衡因子绝对值均不超过 1（即 -1, 0, 1）。
最小不平衡子树：指距离插入结点最近、且平衡因子绝对值大于 1 的结点作为根的子树。

四种失衡调整型

当向平衡二叉树插入新结点导致失衡时，需针对最小不平衡子树进行旋转调整：

(1) LL 型调整 (右单旋)

情况：在失衡结点 A 的左孩子 B 的左子树上插入新结点。
调整方法：将 B 结点向上提升替代 A，A 成为 B 的右孩子，B 原有的右子树变为 A 的左子树。

(2) RR 型调整 (左单旋)

情况：在失衡结点 A 的右孩子 B 的右子树上插入新结点。
调整方法：将 B 结点向上提升替代 A，A 成为 B 的左孩子，B 原有的左子树变为 A 的右子树。

(3) LR 型调整 (先左旋后右旋)

情况：在失衡结点 A 的左孩子 B 的右子树上插入新结点。
调整方法：先对 B 进行左旋，再对 A 进行右旋。调整后，原插入位置附近的结点 C 提升为根，B 为其左孩子，A 为其右孩子。

(4) RL 型调整 (先右旋后左旋)

情况：在失衡结点 A 的右孩子 B 的左子树上插入新结点。
调整方法：先对 B 进行右旋，再对 A 进行左旋。调整后，新结点附近的结点 C 提升为根，A 为其左孩子，B 为其右孩子。

4. B-树

定义：一种多路平衡搜索树。一棵阶 B-树满足：根结点若非叶子则至少有 2 棵子树；非根非叶结点至少有棵子树；所有叶子结点都在同一层且不带信息。
插入与分裂：若插入后结点关键字个数超过，需从中间位置分裂，将中间关键字上移到父结点。
删除与合并：若删除后关键字个数少于，需尝试向邻居借关键字或进行结点合并。

9.4 哈希表

基本概念：
- 哈希函数 ：关键字与存储地址的映射。
- 哈希冲突：不同关键字映射到同一地址（同义词）。
- 装填因子 ：（记录数 / 表长），越大冲突概率越高。
构造方法：
- 除留余数法：。通常取不大于的质数。
- 直接定址法：。
冲突处理：
- 开放地址法：
  1. 线性探测法：从发生冲突的地址开始，依次检查。易产生聚集（堆积）现象。
  2. 平方探测法：地址序列为。
- 拉链法 (Chaining)：将所有同义词存储在同一个单链表中。

数据结构

第1章 绪论