王道数据结构

• 绪论

1. 1. 数据结构的基本概念

知识点1 基本概念和术语

1. 数据

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

1. 数据元素

数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。

1. 数据对象

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

1. 数据类型

数据类型是一个值的集合和定义在此集合上的一组操作的总称

1. 原子类型：其值不可再分的数据类型
2. 结构类型：其值可以再分解为若干成分（分量）的数据类型
3. 抽象数据类型：抽象数据组织及与之相关的操作。

1. 数据结构

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素都不是孤立存在的，它们之间存在某种关系，这种数据元素相互之间的关系称为结构。数据结构包括三方面的内容：逻辑结构，存储结构和数据的运算。

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

知识点2 数据结构三要素

1. 数据的逻辑结构

逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机的。数据的逻辑结构分为线性结构和非线性结构，线性表是典型的线性结构；集合，树和图是典型的非线性结构。

1. 集合。结构中的数据元素之间除“同属一个集合”外，别无其他关系
2. 线性结构。结构中的数据元素之间只存在一对一的关系
3. 树形结构。结构中的数据元素之间存在一对多的关系
4. 图状结构或网状结构。结构中的数据元素之间存在多对多的关系。

1. 数据的存储结构

存储结构是指数据结构在计算机中的表示，也称物理结构。它包括数据元素的表示和关系的表示。数据的存储结构是用计算机语言实现的逻辑结构，它依赖于计算机语言。数据的存储结构主要有顺序存储，链式存储，索引存储和散列存储。

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

1. 数据的运算

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

习题：

1. 抽象数据类型描述了数据的逻辑结构和抽象运算，通常用（数据对象，数据关系，基本操作集）这样的三元组来表示，从而构成一个完整的数据结构定义。
2. 顺序表，哈希表和单链表是三种不同的数据结构，既描述逻辑结构，又描述存储结构和数据运算。而有序表是指关键字有序的线性表，仅描述元素之间的逻辑关系，它既可以链式存储，又可以顺序存储，故属于逻辑结构。
3. 循环队列（易错点）是用顺序表表示的队列，是一种数据结构。栈是一种抽象数据类型，可采用顺序存储或链式存储，只表示逻辑结构。
4. 链式存储设计时，各个不同结点的存储空间可以不连续，但结点内的存储单元地址必须连续。

数据的运算也是数据结构的一个重要方面。

对于两种不同的数据结构，它们的逻辑结构和物理结构完全有可能相同。比如二叉树和二叉排序树，二叉排序树可以采用二叉树的逻辑表示和存储方式，前者通常用于表示层次关系，而后者通常用于排序和查找。虽然它们的运算都有建立树，插入结点，删除结点和查找结点等功能，但对于二叉树和二叉排序树，这些运算的定义是不同的。

举例对同样的逻辑结构，同一种运算在不同的存储方式下实现时，其运算效率不同。

线性表既可以用顺序存储方式实现，又可以用链式存储方式实现。但是两种存储方式下。插入和删除元素的时间复杂度不同。

1. 1. 算法和算法评价

知识点1 算法的基本概念

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

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

1. 算法的目标

1. 正确性
2. 可读性
3. 健壮性：输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。
4. 高效率与低存储量需求

知识点2 算法效率的度量

1. 时间复杂度

一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为T(n)，它是该算法问题规模n的函数，时间复杂度主要分析T(n)的数量级。算法中基本运算（最深层循环内的语句）的频度与T(n)同数量级，因此通常采用算法中基本运算的频度来分析算法的时间复杂度

算法的时间复杂度不仅依赖于问题的规模n，也取决于待输入数据的性质（如输入数据元素的初始状态）

1）最坏时间复杂度是指在最坏情况下，算法的时间复杂度

2）平均时间复杂度是指所有可能输入实例在等概率出现的情况下，算法的期望运行时间

3）最好时间复杂度是指在最好情况下，算法的时间复杂度

2，分析时间复杂度的两条规则：

1. 加法规则

   

2. 乘法规则

   

3，常见的渐进时间复杂度

1. 空间复杂度

定义为该算法所耗费的存储空间，它是问题规模n的函数

一个程序在执行时除需要存储空间来存放本身所用的指令，常数，变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助单元。若输入数据所占空间只取决于问题本身，和算法无关，则只需分析输入和程序之外的额外空间。

算法原地工作是指算法所需的辅助空间为常量，即O(1)

习题

1. 算法代表对问题求解步骤的描述，而程序则是算法在计算机上的特定实现

2. 

1. 

归纳总结

1. 循环主体中的变量参与循环条件的判断

此类题目应该找出主题语句中与T(n)成正比的循环条件，将之代入条件中进行计算

1. 循环主体中的变量与循环条件无关

此类题可采用数学归纳法或直接累计循环次数。多层循环时从内到外分析，忽略单步语句，条件判断语句，只关注主体语句的执行次数。此类问题又可分为递归程序和非递归程序：

·递归程序一般使用公式进行递推

·非递归程序比较简单，可以直接累计次数

• 线性表

2.1 线性表的定义和基本操作

知识点1 线性表的定义

1，线性表是具有相同数据类型的n个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表

2，逻辑特性：a1是唯一的“第一个”数据元素，又称表头元素；an是唯一的“最后一个”数据元素，又称表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。

3，线性表的特点

1）表中元素的个数有限

2）表中元素具有逻辑上的顺序性，表中元素有其先后次序

3）表中元素都是数据元素，每个元素都是单个元素

4）表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间

5）表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容

注意：线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层面的概念，因此不要将其混淆

知识点2 线性表的基本操作

1. 一个数据结构的基本操作是指其最核心，最基本的操作。其他较复杂的操作可通过调用其基本操作来实现。
2. 线性表的主要操作如下

1. 初始化表
2. 求表长
3. 按值查找操作
4. 按位查找操作
5. 插入操作
6. 删除操作
7. 输出操作
8. 判空操作
9. 销毁操作

1. 基本操作的实现取决于采用哪种存储结构，存储结构不同，算法的实现也不同。

2.2 线性表的顺序表示

知识点1 顺序表的定义

1. 线性表的顺序存储又称为顺序表。它是用一组地址连续的存储单元一次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻
2. 顺序表的特点是表中元素的逻辑顺序和物理顺序相同
3. 每个数据元素的存储位置都和线性表的起始位置相差一个和该数据元素的位序成正比的常数，因此，顺序表中的任意一个数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。通常用高级程序设计语言中的数组来描述线性表的顺序存储结构。

注意：线性表中的位序是从1开始的，而数组中的元素的下标是从0开始的

1. 一维数组可以是静态分配的，也可以是动态分配的。在静态分配时，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据就会溢出，进而导致程序崩溃。而在动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，就另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储数组空间的目的，而不需要为线性表一次性地划分所有空间。

注意：动态分配并不是链式存储，它同样属于顺序存储结构，物理结构没有变化，依然是随机存取方式，只是分配的空间大小可以在运行时动态决定

1. 顺序表最主要的特点是随机访问，顺序表的存储密度高，每个结点只存储数据元素，顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。

知识点2 顺序表上基本操作的实现

1. 插入操作

在顺序表L的第i个位置插入新元素e。若i的输入不合法，则返回false，表示插入失败；否则，将第i个元素及其后的所有元素一次往后移动一个位置，腾空出一个空位置插入新元素e，顺序表长度增加1，插入成功，返回true。

顺序表插入算法的平均时间复杂度为O(n)

1. 删除操作

删除顺序表L中第i个位置的元素，用引用变量e返回。若i的输入不合法，则返回false；否则，将被删元素赋给引用变量e，并将第i+1个元素及其后的所有元素依次往前移动一个位置，返回true

顺序表删除算法的平均时间复杂度为O(n)

1. 按值查找

在顺序表L中查找第一个元素值等于e的元素，并返回其位序

顺序表按值查找算法的平均时间复杂度为O(n)

习题

1. 

D是错误的，比如对于树形结构，顺序表显然不如链表表示起来方便

1. 线性表元素的序号是从1开始，而在n+1个位置插入相当于在表尾追加

2.3 线性表的链式表示

知识点1 单链表的定义

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

1. 利用单链表可以解决顺序表需要大量连续存储单元的缺点，但单链表附加指针域，也存在浪费存储空间的缺点。由于单链表的元素离散地分布在存储空间中，所以单链表是非随机存取的存储结构，即不能直接找到表中某个特定的结点。查找某个特定的结点时，需要从表头开始遍历，依次查找。
2. 通常用头指针来标识一个单链表，如单链表L，头指针为NULL时表示一个空表。此外，为了操作上的方便，在单链表第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点

1）头结点和头指针的区分：不管带不带头结点，头指针都始终指向链表的第一个结点，而头结点是带头结点的链表中的第一个结点，结点内通常不存储信息

2）引入头结点后，可以带来两个优点

1. 由于第一个数据结点的位置被存放在头结点的指针域中，因此在链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理
2. 无论链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就得到了统一。

知识点2 单链表上基本操作的实现

1. 采用头插法建立单链表

该方法从一个空表开始，生成新结点，并将读取到的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头。

采用头插法建立单链表时，读入数据的顺序域生成的链表中的元素的顺序是相反的。每个结点插入的时间为O(1)，设单链表长为n，则总时间复杂度为O(n)

1. 利用尾插法建立单链表

为此必须增加一个尾指针r，使其始终指向当前链表的尾结点

因为附设了一个指向表尾结点的指针，故时间复杂度和头插法的相同

1. 按序号查找结点

在单链表中从第一个结点出发，顺时针next域逐个往下搜索，直到找到第i个结点为止，否则返回最后一个结点指针域NULL

按序号查找操作的时间复杂度O(n)

1. 按值查找表结点

从单链表达到第一个结点开始，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值e，则返回该结点的指针；若整个单链表中没有这样的结点，则返回NULL

按值查找操作的时间复杂度为O(n)

1. 插入结点操作

插入结点操作将值为x的新结点插入到单链表的第i个位置上。先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第i-1个结点，再在其后插入新结点

本算法主要的时间开销在于查找第i-1个元素，时间复杂度为O(n)。若在给定的结点后面插入新结点，则时间复杂度仅为O(1)

扩展：对某一结点进行前插操作

对结点的前插操作均可转化为后插操作，前提是从单链表的头结点开始顺序查找到前驱结点，时间复杂度为O(n)。此外，可采用另一种方式将其转化为后插操作来实现，设待插入结点为*s，将*s插入到*p的前面。我们仍然将*s插入到*p的后面，然后将p->data与s->data交换，这样既满足了逻辑关系，又能使得时间复杂度为O(1)。

1. 删除结点操作

删除结点操作是将单链表的第i个结点删除。先检查删除位置的合法性，后查找表中第i-1个结点，即被删结点的前驱结点，再将其删除。仅需修改*p的指针域，即将*p的指针域next指向*q的下一结点。

和插入算法一样，该算法的主要时间也耗费在查找操作上，时间复杂度为O(n)

扩展：删除结点*p

要删除某个给定结点*p，通常的做法是先从链表的头结点开始顺序找到其前驱结点，然后执行删除操作，算法的时间复杂度为O(n)。其实，删除结点*p的操作可用删除*p的后继结点操作来实现，实质就是将其后继结点的值赋予其自身，然后删除后继结点，也能使得时间复杂度为O(1)

1. 求表长操作

求表长操作就是计算单链表中数据结点（不含头结点）的个数，需要从第一个结点开始顺序依次访问表中的每个结点，为此需要设置一个计数器变量，每访问一个结点，计数器加1，直到访问到空结点为止。算法的时间复杂度为O(n)。

需要注意的是，因为单链表的长度是不包含头结点的，因此不带头结点和带头结点的单链表在求表长操作上会略有不同。对不带头结点的单链表，当表为空时，要单独处理。

知识点3 双链表

1. 双链表结点中有两个指针prior和next，分别指向其前驱结点和后驱结点。
2. 双链表在单链表的结点中增加了一个指向其前驱的prior指针，因此双链表中的按值查找和按位查找的操作与单链表的相同。但双链表在插入和删除操作的实现上，与单链表有着较大的不同。这是因为”链”变化时也需要对prior指针做出修改，其关键是保证在修改的过程中不断链。此外，双链表可以很方便地找到其前驱结点，因此，插入，删除操作的时间复杂度仅为O(1)
3. 在建立双链表的操作中，也可采用如同单链表的头插法和尾插法，但在操作上需要注意指针的变化和单链表有所不同。

知识点4 循环链表

1. 循环单链表

循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL，而改为指向头结点，从而整个链表形成一个环。

1）循环单链表的判空条件不是头结点的指针是否为空，而是它是否等于头指针

2）有时对循环单链表不设头指针而仅设尾指针，以使得操作效率更高。其原因是，若设的是头指针，对在表尾插入元素需要O(n)的时间复杂度，而若设的是尾指针r，r->next即为头指针，对在表头或表尾插入元素都只需要O(1)的时间复杂度。

1. 循环双链表

1. 在循环双链表中，头结点的prior指针还要指向表尾结点
2. 在循环双链表L中，某结点*p为尾结点时，p->next==L；当循环双链表为空表时，其头结点的prior域和next域都等于L。

知识点5 静态链表

1. 静态链表借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域next，与前面所讲的链表中的指针不同的是，这里的指针是结点的相对地址（数组下标），又称游标。和顺序表一样，静态链表也要预先分配一块连续的内存空间。

1. 静态链表以next==-1作为其结束的标志。静态链表的插入，删除操作与动态链表的相同，只需要修改指针，而不需要移动元素。

知识点6 顺序表和链表的比较

1. 存取方式

顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序存取元素

1. 逻辑结构与物理结构

采用顺序存储时，逻辑上相邻的元素，对应的物理存储位置也相邻。而采用链式存储时，逻辑上相邻的元素，物理存储位置不一定相邻，对应的逻辑关系是通过指针链接来表示的。

1. 查找，插入和删除操作

对于按值查找，顺序表无序时，两者的时间复杂度均为O(n)；顺序表有序时，可采用折半查找，此时的时间复杂度为O(log2n)

对于按序号查找，顺序表支持随机访问，时间复杂度仅为O(1)，而链表的平均时间复杂度为O(n)。顺序表的插入，删除操作，平均需要移动半个表长的元素，链表的插入，删除操作，只需修改相关结点的指针域即可。由于链表的每个结点都带有指针域，故而存储密度不够大。

4，空间分配

顺序存储在静态存储分配情形下，一旦存储空间装满就不能扩充，若再加入新元素，则会出现内存溢出，因此需要预先分配足够大的存储空间。预先分配过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。动态存储分配虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且若内存中没有更大块的连续存储空间，则会导致分配失败。链式存储的结点空间只在需要时申请分配，只要内存有空间就可以分配，操作灵活，高效。

知识点7 如何选取存储结构

1. 基于存储的考虑

难以估计线性表的长度或存储规模时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低，显然链式存储结构的存储密度是小于1的

2，基于运算的考虑

3，基于环境的考虑

顺序表容易实现，任何高级语言中都有数组类型；链表的操作是基于指针的，相对来讲，前者实现较为简单。

• 栈，队列和数组

1. 1. 栈

知识点1 栈的基本概念

1. 栈的定义：栈是只允许在一端进行插入或删除操作的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。

1. 栈顶：线性表允许进行插入删除的那一端
2. 栈底：固定的，不允许进行插入和删除的另一端
3. 空栈：不含任何元素的空表

栈的操作特性可以明显地概括为后进后出

栈的数学性质：n个不同元素进栈，出栈元素不同排列的个数为

1. 栈的基本操作

1. 初始化一个空栈
2. 判断一个栈是否为空
3. 进栈
4. 出栈
5. 读栈顶元素
6. 销毁栈

在解答算法题中，若题干未做出限制，则可直接使用这些基本的操作函数

知识点2 栈的顺序存储结构

1. 顺序栈的实现

采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶元素的位置

1. 栈顶指针：S.top，初始时设置S.top=-1；栈顶元素:S.Data[S.top]
2. 进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶元素
3. 出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减1
4. 栈空条件：S.top==-1；栈满条件：S.top==Maxsize-1；栈长:S.Top+1

由于顺序栈的入栈操作受数组上界的约束，当对栈的最大使用空间估计不足时，有可能发生栈上溢，此时应及时向用户报告消息，以便及时处理，避免出错。

注意：栈和队列的判空，判满条件，会因实际给的条件不同而变化

1. 顺序栈的基本运算

注意：这里top指向的是栈顶元素，所以进栈操作为S.data[++S.top]=x，出栈操作为x=S.data[S.top--]。若栈顶指针初始化为S.top=0，即top指向栈顶元素的下一位置，则入栈操作变为S.data[S.top++]=x；出栈操作变为x=S.data[--S.top]。相应的栈空，栈满条件也会发生变化

1. 共享栈

利用栈底位置相对不变的特性，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延申

两个栈的栈顶指针都指向栈顶元素，top0=-1时0号栈为空，top1=Maxsize时1号栈为空；仅当两个栈顶指针相邻（top1-top0=1）时，判断为栈满。当0号栈进栈时top0先加1再赋值，1号栈进栈时top1先减1再赋值；出栈时则刚好相反。

共享栈是为了更有效地利用存储空间，两个栈的空间相互调节，只有在整个存储空间被占满时才发生上溢。其存取数据的时间复杂度均为O(1)，所以对存取效率没有什么影响。

知识点3 栈的链式存储结构

1. 采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。这里规定链栈没有头结点，Lhead指向栈顶元素
2. 采用链式存储，便于结点的插入与删除。链栈的操作与链表类似，入栈和出栈的操作都在链表的表头进行。需要注意的是，对于带头结点和不带头结点的链栈，具体的实现会有所不同。

1. 1. 队列

知识点1 队列的基本概念

1. 队列的定义

队列简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。向队列中插入元素称为入队或进队；删除元素称为出队或离队。其特点是先进先出。

1. 队列常见的基本操作

1. 初始化队列
2. 判队列空
3. 入队
4. 出队
5. 读队头元素

需要注意的是，栈和队列是操作受限的线性表，因此不是任何队线性表的操作都可以作为栈和队列的操作。比如，不可以随便读取栈或队列中间的某个数据。

知识点2 队列的顺序存储结构

1. 队列的顺序存储

队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置（不同教材对front和rear的定义可能不同，例如可以让rear指向队尾元素，front指向队头元素。对于不同的定义，出对入队的操作是不同的）

1. 假溢出

1. 循环队列

将顺序队列臆造为一个环状的空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。

1. 初始时：Q.front=Q.rear=0
2. 队首指针进1：Q.front=(Q.front+1)%maxsize
3. 队尾指针进1：Q.rear=(Q.rear+1)%maxsize
4. 队列长度:（Q.rear+maxsize-Q.front)%maxsize

为了区分是队空还是队满的情况，有三种处理方式

1. 牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是一种较为普遍的做法，

队满条件：（Q.rear+1)%maxsize==Q.front

队空条件：Q.front==Q.rear

队列中元素的个数：（Q.Rear-Q.front+maxsize)%maxsize

1. 类型中增设表示元素个数的数据成员。这样，队空的条件为Q.size==0；队满的条件为Q.size==maxsize。这两种情况都有Q.front==Q.rear
2. 类型中增设tag数据成员，以区分是队满还是队空。Tag等于0时，若因删除导致Q.front==Q.rear，则为队空；tag等于1时，若因插入导致Q.front==Q.rear，则为队满。

知识点3 队列的链式存储结构

1. 队列的链式存储

队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点（注意与顺序存储的不同）

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

知识点4 双端队列

1. 双端队列是指允许两端都可以进行入队和出队操作的队列。其元素的逻辑结构仍然是线性结构。将队列的两端分别称为前端和后端，两端都可以入队和出队。
2. 在双端队列出队时，无论是前端还是后端出队，先出的元素排列在后出的元素的前面
3. 输出受限的双端队列：允许在一端进行插入和删除，但在另一端只允许插入的双端队列称为输出受限的双端队列。
4. 输入受限的双端队列：允许在一端进行插入和删除，但在另一端只允许删除的双端队列称为输入受限的双端队列。

1. 1. 栈和队列的应用

知识点1 栈在括号匹配中的应用

知识点2 栈在表达式求值中的应用

知识点3 栈在递归中的应用

知识点4 队列在层次遍历中的应用

知识点5 队列在计算机系统中的应用

1. 1. 数组和特殊矩阵

知识点1 数组的定义

1. 数组是由n个相同类型的数据元素构成的有限序列。每个数据元素称为一个数组元素，每个元素在n个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界。
2. 数组与线性表的关系：数组是线性表的推广。一维数组可视为一个线性表；二维数据可视为其元素也是定长线性表的线性表，以此类推。数组一旦被定义，其维数和维界就不再改变。因此，除结构的初始化和销毁外，数组只会有存取元素和修改元素的操作。

知识点2 数组的存储结构

1. 大多数计算机语言都提供了数组数据类型，逻辑上的数组可采用计算机语言中的数组数据类型进行存储，一个数组的所有元素在内存中占用一段连续的存储空间。
2. 对于多维数组，有两种映射方法：按行优先和按列优先。以二维数组为例，按行优先存储的基本思想是，先行后列，先存储行号较小的元素，行号相等先存储列号较小的元素。
3. 行下标和列下标的范围分别是[0,h1]与[0,h2]

知识点3 特殊矩阵的压缩存储

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

其中的元素可以划分为3个部分，即上三角区，主对角线和下三角区

1. 三角矩阵

1）下三角矩阵中，上三角区的所有元素均为同一变量。其存储思想与对称矩阵类似，不同之处在于存储完下三角区和主对角线上的元素之后，紧接着存储对角线上方的常量一次。

1. 上三角矩阵中，下三角区的所有元素均为同一常量。只需存储主对角线，上三角区上的元素和下三角区的常量一次。

1. 三对角矩阵

1）对角矩阵也称带状矩阵。在三对角矩阵中，所有非零元素都集中在以主对角线为中心的3条对角线的区域，其他区域的元素都为零。

2）三对角矩阵也可以采用压缩存储，将3条对角线上的元素按行优先方式存放在一维数组中

知识点4 稀疏矩阵

1. 矩阵中非零元素的个数t，相对矩阵元素的个数s来说非常少的矩阵称为稀疏矩阵。
2. 若采用常规的方法存储稀疏矩阵，则相当浪费存储空间，因此仅存储非零元素。但通常非零元素的分布没有规律，所以仅存储非零元素的值是不够的，还要存储它所在的行和列。因此，将非零元素及其相应的行和列构成一个三元组（行标，列标，值）。然后，按照某种规律存储这些三元组。稀疏矩阵压缩存储后便失去了随机存取特性。
3. 稀疏矩阵的三元组既可以采用数组存储，也可以采用十字链表法存储。

• 串

4.1 串的定义和实现

知识点1 串的定义

1. 串是由零个或多个字符组成的有限序列
2. 串中任意多个连续的字符组成的子序列称为该串的子串，包含子串的串称为主串。某个字符在串中的序号称为该字符在串中的位置。子串在主串中的位置以子串的第一个字符在主串中的位置来表示。当两个串的长度的相等且每个对应位置的字符都相等时，称这两个串是相等的。
3. 由一个或多个空格组成的串称为空格串
4. 串的逻辑结构和线性表极为相似，区别仅在于串的数据对象限定为字符集。在基本操作上，串和线性表有很大差别。线性表的基本操作主要以单个元素作为操作对象，如查找，插入或删除某个元素等；而串的基本操作通常以子串作为操作对象，如查找，插入或删除一个子串等。

知识点2 串的存储结构

1. 定长顺序存储表示

1）类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。在串的定长顺序存储结构中，为每个串分量分配一个固定长度的存储区，即定长数组。

2）串长有两种表示方法：一是如上述定义描述的那样，用一个额外的变量len来存放串的长度；二是在串值后面加一个不计入串长的结束标记字符“\0”，此时的串长为隐含值。

3）在一些串的操作（如插入，联接等）中，若串值序列的长度超过上界maxlen，约定用“截断法”处理，要克服这种弊端，只能不限定串长的最大长度，即采用动态分配的方式。

1. 堆分配存储表示

堆分配存储表示仍然以一组地址连续的存储单元存放串值的字符序列，但它们的存储空间是在程序执行过程中动态分配得到的。

1. 块链存储表示

类似于线性表的链式存储结构，也可采用链表方式存储串值。由于串的特殊性（每个元素只有一个字符），在具体实现中，每个结点既可以存放一个字符，也可以存放多个字符。每个结点称为块，整个链表称为块链结构。

• 树与二叉树

5.1 树的基本概念

知识点1 树的定义

1. 树是n个结点的有限集。当n=0时，称为空树。在任意一棵非空树中应满足：

1. 有且仅有一个特定的称为根的结点
2. 当n>1时，其与结点可分为m个互不相交的有限集，其中每个集合本身又是一棵树，并且称为根的子树。

2，显然，树的定义是递归的，即在树的定义中又用到了其自身，树是一种递归的数据结构。树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点

1. 树的根节点没有前驱，除根结点外的所有结点有且只有一个前驱
2. 树中所有结点都可以有零个或多个后继。

3，树适合于表示具有层次结构的数据。

树中的某个结点（除根节点外）最多只和上一层的一个结点（即其父结点）有直接关系，根结点没有直接上层结点，因此在n个结点的树中有n-1条边。而树中每个结点与其下一层的零个或多个结点都有直接关系。

知识点2 基本术语

1. 考虑结点K。根A到结点K的唯一路径上的任意结点，称为结点K的祖先。如结点B是结点K的祖先，而结点K是结点B的子孙。路径上最接近结点K的结点E称为K的双亲，而K为结点E的孩子。根A是树中唯一没有双亲的结点。有相同双亲的结点称为兄弟
2. 树中一个结点的孩子个数称为该结点的度，树中结点的最大度数称为树的度。
3. 度大于0的结点称为分支结点（又称非终端结点）；度为0（没有子女结点）的结点称为叶结点（又称终端结点）。在分支结点中，每个结点的分支数就是该结点的度。
4. 结点的深度，高度和层次

1. 结点的层次从树根开始定义，根结点为第1层，它的子结点为第2层，以此类推。双亲在同一层的结点互为堂兄弟。
2. 结点的深度是从根结点开始自顶向下逐层累加的
3. 结点的高度是从叶结点开始自底向上逐层累加的
4. 树的高度（或深度）是树中结点的最大层数。

5，有序树和无序树。树中结点的各子树从左到右是有次序的，不能互换，称该树为有序树

6，路径和路径长度。树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数。

注意：由于树中的分支是有向的，即从双亲指向孩子，所以树中的路径是从上向下的，同一双亲的两个孩子之间不存在路径。

1. 森林

森林是m棵互不相交的树的集合。森林的概念与树的概念十分相近，因为只要把树的根节点删去就成了森林。反之，只要给m棵独立的树加上一个结点，并把这m棵树作为该结点的子树，则森林就变成了树。

知识点3 树的性质

1. 树中的结点数等于所有结点的度数之和加1
2. 度为m的树中第i层上至多有

   

   个结点
3. 高度为h的m叉树至多有

   

   个结点
4. 具有n个结点的m叉树的最小高度为

   

注意：常用于求解树结点与度之间关系的有：

5.2 二叉树的概念

知识点1 二叉树的定义及其主要特性

1. 二叉树的定义

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

1. 与树相似，二叉树也以递归的形式定义。二叉树是n个结点的有限集合：

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

1. 二叉树是有序树，若将其左，右子树颠倒，则称为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。
2. 二叉树与度为2的有序树的区别：

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

1. 几个特殊的二叉树

1. 满二叉树。树中的每层都含有最多的结点。满二叉树的叶结点都集中在二叉树的最下一层，并且除叶结点之外的每个结点度数均为2.

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

1. 二叉排序树。左子树上所有结点的关键字均小于根结点的关键字；右子树上的所有结点的关键字均大于根结点的关键字；左子树和右子树又各是一棵二叉排序树。
2. 平衡二叉树。树上任意一个结点的左子树和右子树的深度之差不超过1。

1. 二叉树的性质

1. 非空二叉树上的叶结点数等于度为2的结点数加1
2. 非空二叉树上第k层上至多有

   

   个结点
3. 高度为h的二叉树至多有

   

   个结点
4. 对完全二叉树按从上到下，从左到右得到顺序依次编号

1. 具有n个结点的完全二叉树的高度为

   

知识点2 二叉树的存储结构

1. 顺序存储结构

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

注意：这种存储结构建议从数组下标为1开始存储树中的结点

1. 但对于一般的二叉树1，为了让数组下标能反映二叉树中结点之间的逻辑关系，只能添加一些并不存在的空结点，让其每个结点与完全二叉树上的结点相对照，再存储到一维数组的相应分量中。

1. 链式存储结构

1. 由于顺序存储的空间利用率较低，因此二叉树一般都采用链式存储结构，用链表结点来存储二叉树中的每个结点。在二叉树中，结点结构通常包括若干数据域和若干指针域，二叉链表至少包含三个域：数据域，左指针域和右指针域
2. 实际上在不同的应用中，还可以增加某些指针域，如增加指向父结点的指针后，变为三叉链表的存储结构。
3. 使用不同的存储结构时，实现二叉树操作的算法也会不同，因此要根据实际应用场合（二叉树的形态和需要进行的运算）来选择合适的存储结构。
4. 容易验证，在含有n个结点的二叉链表中，含有n+1个空链域

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

知识点1 二叉树的遍历

二叉树的遍历是指按照某条搜索路径访问树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。由于二叉树是一种非线性结构，每个结点都可能有两棵子树，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，进而便于遍历。

由二叉树的递归定义可知，遍历一棵二叉树便要决定对根结点N，左子树L和右子树R的访问顺序。按照先遍历左子树再遍历右子树的原则，常见的遍历次序有先序，中序和后序三种遍历算法，其中序指的是根结点在何时被访问。

1. 先序遍历

若二叉树为空，则什么也不做；否则

1. 访问根结点
2. 先序遍历左子树
3. 先序遍历右子树

1. 中序遍历

若二叉树为空，则什么也不做；否则

1. 中序遍历左子树
2. 访问根结点
3. 中序遍历右子树

1. 后序遍历

若二叉树为空，则什么也不做；否则

1. 后序遍历左子树
2. 后序遍历右子树
3. 访问根结点

三种遍历算法中，递归遍历左，右子树的顺序都是固定的，只是访问根结点的顺序不同。不管采用哪种遍历算法，每个结点都访问一次且仅访问一次，故时间复杂度都是O(n)。在递归遍历中，递归工作栈深恰好为树的深度，所以在最坏情况下，二叉树是有n个结点且深度为n的单支树，遍历算法的空间复杂度为0(n)

1. 递归算法和非递归算法的转换

1. 中序遍历的非递归算法

1. 先序遍历和中序遍历的基本思想是类似的，只需把访问结点操作放在入栈操作的前面
2. 后序非递归遍历算法的思路分析：从根结点开始，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，但是此时还不能出栈并访问，因为如果其有右子树，还需按相同的规则对其右子树进行处理。直至上述操作进行不下去，若栈顶元素想要出栈被访问，要么右子树为空，要么右子树刚被访问完。

1. 层次遍历

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

注意：遍历是二叉树各种操作的基础，可以在遍历的过程中对结点进行各种操作。

1. 由遍历序列构造二叉树

1. 若只知道二叉树的先序序列和后序序列，则无法唯一确定一棵二叉树。
2. 先序和中序，中序和后序可以
3. 由二叉树的层序序列和中序序列也可以唯一地确定一棵二叉树。

知识点2 线索二叉树

1. 线索二叉树的基本概念

1. 遍历二叉树使得序列中每个结点（第一个和最后一个结点除外）都有一个直接前驱和直接后继
2. 在含n个结点的二叉树中，有n+1个空指针。这是因为每个叶结点都有2个空指针，每个度为1的结点都有1个空指针，空指针总数为2n0+n1，又n0=n2+1，所以空指针总数为n0+n1+n2+1=n+1。由此设想能否利用这些空指针来存放指向其前驱或后继的指针？这样就可以像遍历单链表那样方便地遍历二叉树。引入线索二叉树正是为了加快查找结点前驱和后继的速度。
3. 线性二叉树的结点结构

1. 中序线索二叉树的构造

1. 二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历时才能得到。因此线索化的实质就是遍历一次二叉树。
2. 以中序线索二叉树的建立为例。附设指针pre指向刚刚访问过的结点，指针p指向正在访问的结点，即pre指向p的前驱。在中序遍历的过程中，检查p的左指针是否为空，若为空就将它指向pre；检查pre的右指针是否为空，若为空就将它指向p。

为了方便，可以在二叉树的线索链表上也添加一个头结点，令其lchild域的指针指向二叉树的根结点，其rchild域的指针指向中序遍历时访问的最后一个结点；令二叉树中序序列中的第一个结点的lchild域指针和最后一个结点的rchild域指针均指向头结点。这好比为二叉树建立了一个双向线索链表，方便从前往后或从后往前对线索二叉树进行遍历。

1. 中序线索二叉树的遍历

在中序线索二叉树中找结点后继的规律是：若其右标志为1，则右链为线索，指示其后继，否则遍历右子树中第一个访问的结点（右子树中最左下的结点）为其后继。不含头结点的线索二叉树的遍历算法如下：

1. 先序线索二叉树和后序线索二叉树

1. 建立先序线索二叉树和建立后序线索二叉树的代码与建立中序线索二叉树的代码类似，只需变动线索化改造的代码段与调用线索化左右子树递归函数的位置。
2. 如何在先序线索二叉树中找结点的后继？如果有左孩子，则左孩子就是其后继；如果无左孩子但有右孩子，则右孩子就是其后继；如果为叶结点，则右链域直接指示了结点的后继。
3. 在后序线索二叉树中找结点的后继较为复杂

1. 若结点x是二叉树的根，则其后继为空
2. 若结点x是其双亲的右孩子，或是其双亲的左孩子且其双亲没有右孩子，则其后继即为双亲
3. 若结点x是其双亲的左孩子，且其双亲有右子树，则其后继为双亲的右子树上按后序遍历列出的第一个结点。

5.4 树，森林

知识点1 树的存储结构

树的存储方式有多种，即可采用顺序存储结构，又可采用链式存储结构，但无论采用何种存储方式，都要求能唯一地反映树中各结点之间的逻辑关系。

1. 双亲表示法

这种存储结构采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置。该存储结构利用了每个结点（根结点除外）只有唯一双亲的性质，可以很快地得到每个结点的双亲结点，但求结点的孩子时则需要遍历整个结构。

注意：区别树的顺序存储结构与二叉树的顺序存储结构。在树的顺序存储结构中，数组下标代表结点的编号，下标中所存的内容指示了结点之间的关系。而在二叉树的顺序存储结构中，数组下标既代表了结点的编号，又指示了二叉树中各结点之间的关系。当然，二叉树属于树，因此二叉树都可以用树的存储结构来存储，但树却不都能用二叉树的存储结构来存储。

1. 孩子表示法

孩子表示法是将每个结点的孩子结点都用单链表链接起来形成一个线性结构，此时n个结点就有n个孩子链表。这种存储结构寻找子女的操作非常直接，而寻找双亲的操作需要遍历n个结点中孩子链表指针域所指向的n个孩子链表。

1. 孩子兄弟表示法

孩子兄弟表示法又称二叉树表示法，即以二叉链表作为树的存储结构。孩子兄弟表示法使每个结点包括三部分内容：结点值，指向结点第一个孩子结点的指针，以及指向结点下一个兄弟结点的指针

知识点2 树，森林与二叉树的转换

1. 由于二叉树和树都可以用二叉链表作为存储结构，因此以二叉链表为媒介可以导出树与二叉树的一个对应关系，即给定一棵树，可以找到唯一的一棵二叉树与之对应。从物理结构上看，它们的二叉链表是相同的，只是解释不同而已。

1. 树转换为二叉树的画法：1）在兄弟结点之间加一连线2）对每个结点，只保留它与第一个孩子的连线，而与其他孩子的连线全部抹掉 3）以树根为轴心，顺时针旋转45度
2. 将森林转换为二叉树的规则与树类型。先将森林中的每棵树转换为二叉树，由于任意一棵和树对应的二叉树的右子树必空，若把森林中第二棵树根视为第一棵树根的右兄弟，即将第二棵树对应的二叉树当作第一棵二叉树根的右子树···以此类推，就可以将森林转换为二叉树。
3. 二叉树转换为森林的规则：若二叉树非空，则二叉树的根及其1左子树为第一棵树的二叉树形式，故将根的右链断开。二叉树根的右子树又可视为一个由除第一棵树外的森林转换后的二叉树应用同样的方法，直到最后只剩一棵没有右子树的二叉树位置，最后再将每棵二叉树依次转换成树，就得到了森林。

知识点3 树和森林的遍历

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

1. 先根遍历。若树非空，先访问根结点，再依次遍历根结点的每棵子树，遍历子树时仍遵循先根后子树的规则。其遍历序列与这棵树相应二叉树的先序序列相同。
2. 后根遍历。若树非空，先依次遍历根结点的每棵子树，再访问根结点，遍历子树时仍遵循先子树后根的规则。其遍历序列与这棵树相应二叉树的中序序列相同。

1. 另外，树也有层次遍历，与二叉树的层次遍历思路基本相同，即按层序依次访问各结点。3，按照森林和树相互递归的定义，可得到森林的两种遍历方法

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

4，

注意：部分教材也将森林的中序遍历称为后序遍历，称中序遍历是相对其二叉树而言的，称后序遍历是因为根确实是最后才访问的，如遇到这两种称谓，那么都可以理解为同一种遍历方法。

5.5 树与二叉树的应用

知识点1 哈夫曼树和哈夫曼编码

1. 哈夫曼树的定义

在许多应用中，树中结点常常被赋予一个表示某种意义的数值，称为该结点的权。从树的根到任意结点的路径长度（经过的边数）与该结点上权值的乘积，称为该结点的带权路径长度。树中所有叶结点的带权路径长度之和称为该树的带权路径长度。在含有n个带权叶结点的二叉树中，其中带权路径长度最小的二叉树称为哈夫曼树，也称为最优二叉树。

1. 哈夫曼树的构造

1. 将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F
2. 构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左，右子树，并且将新结点的权值置为左，右子树上根结点的权值之和。
3. 从F中删除刚才选出的两棵树，同时将新得到的树加入F中
4. 重复步骤2)和3）直至F中只剩下一棵树为止

从上述构造过程中可以看出哈夫曼树具有如下特点

1. 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大
2. 构造过程中共新建了n-1个结点（双分支结点），因此哈夫曼树的结点总数为2n-2
3. 每次构造都选择2棵树作为新结点的孩子，因此哈夫曼树中不存在度为1的结点

1. 哈夫曼编码

1. 在数据通信中，若对每个字符用相等长度的二进制位表示，称这种编码方式为固定长度编码。若允许对不同字符用不等长的二进制位表示，则这种编码方式为可变长编码。可变长度编码比固定长度编码要好得多，其特点是对频率高的字符赋以短编码，而对频率低的字符则赋以长一些的编码，从而可以使字符的平均编码长度缩短，起到压缩数据的效果。哈夫曼编码是一种被广泛应用而且非常有效的数据压缩编码。
2. 若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。对前缀编码的解码很简单，因为没有一个编码是其他编码的前缀。所以识别出第一个编码，将它翻译为原码，再对余下的编码文件重复同样的解码操作。
3. 由哈夫曼树得到哈夫曼编码是很自然的过程。首先，将每个出现的字符当作一个独立的结点，其权值为它出现的频度（或次数），构造出对应的哈夫曼树。显然，所有字符结点都出现在叶结点中。我们可将字符的编码解释为从根至该字符的路径上边标记的序列，其中边标记为0表示转向左孩子，标记为1表示转向右孩子。利用哈夫曼树可以设计出总长度最短的二进制前缀编码。

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

知识点2 并查集

1，并查集是一种简单的集合表示，它支持以下三种操作

1. initial（s）：将集合S中的每个元素都初始化为只有一个单元素的子集合
2. Union(s,root1,root2):把集合s中的子集合root2并入子集合root1，要求root1和root2并不相交
3. Find(s,x):查找集合s中单元素x所在的子集合，并返回该子集合的根结点

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

为了得到两个子集合的并，只需将其中一个子集合根结点的双亲指针指向另一个集合的根结点。

2，在采用树的双亲指针数组表示作为并查集的存储表示时，集合元素的编号从0到size-1

3，判断两个元素是否属于同一集合，只需分别找到它们的根结点，比较根结点是否相同即可。如果将两个元素所在的集合合并为一个集合，那么就需要先找到两个元素的根结点。

1. 图

6.1 图的基本概念

知识点1 图的定义

图G由顶点集V和边集E组成，记为G=(V,E)，其中V(G)表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系集合。|V|表示图G中顶点的个数，|E|表示图G中边的条数。

注意：线性表可以是空表，树可以是空表，但图不可以是空图。就是说，图中不能一个顶点也没有，图的顶点集V一定非空，但边集E可以为空，此时图中只有顶点而没有边。

1. 有向图

若E是有向边（也称弧）的有限集合时，则图G为有向图。弧是顶点的有序对，记为<v,w>，v称为弧尾，w称为弧头，<v,w>称为从v到w的弧，也称v邻接到w

1. 无向图

若E是无向边的有限集合时，则图G为无向图。边是顶点的无序对。

1. 简单图，多重图

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

1. 完全图

在完全图中任意两个顶点之间都存在边。在有向完全图中任意两个顶点之间都存在方向相反的两条弧。

1. 子图

注意：并非V和E的任何子集都能构成G的子图，因为这样的子集可能不是图，即E的子集中的某些边关联的顶点可能不在这个V的子集中。

1. 连通，连通图和连通分量

在无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。无向图中的极大连通子图称为连通分量。假设一个图有n个顶点，如果边数小于n-1，那么此图必是非连通图。

1. 强连通图，强连通分量

在有向图中，如果一对顶点v和w，从v到w和从w到v之间都有路径，则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的，则称此图为强连通图。有向图中的极大强连通子图称为有向图的强连通分量。

1. 生成树，生成森林

连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点树为n，则它的生成树含有n-1条边。包含图中全部顶点的极小连通子图，只有生成树满足这个极小条件，对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。在非连通图中，连通分量的生成树构成了非连通图的生成森林。

注意：区分极大连通子图和极小连通子图。极大连通子图是无向图的连通分量，极大即要求该连通子图包含所有的边；极小连通子图是既要保持图连通又要使得边数最少的子图。

1. 顶点的度，入度和出度

1. 在无向图中，顶点v的度是指依附于顶点v的边的条数。无向图的全部顶点的度的和等于边数的2倍，因为每条边和两个顶点相关联。
2. 在有向图中，顶点v的度分为入度和出度，入度是以顶点v为终点的有向边的数目，而出度是以顶点v为起点的有向边的数目。有向图的全部顶点的入度之和与出度之和相等，并且等于边数。

1. 边的权和网

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

1. 稠密图，稀疏图

边数很少的图称为稀疏图，反之称为稠密图。稀疏和稠密本身是模糊的概念，稀疏图和稠密图常常是相对而言的。

1. 路径，路径长度和回路

路径上边的数目称为路径长度。第一个顶点和最后一个顶点相同的路径称为回路或环。若一个图有n个顶点，并且有大于n-1条边，则此图一定有环。

1. 简单路径，简单回路

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

1. 距离

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

1. 有向树

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

6.2 图的存储及基本操作

知识点1 邻接矩阵法

1. 所谓邻接矩阵存储，是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息，存储顶点之间邻接关系的二维数组称为邻接矩阵。对于带权图而言，若顶点vi和vj之间有边相连，则邻接矩阵中对应项存放着该边对应的权值。若不相连，则通常用无穷来代替这两个顶点之间不存在边。

注意：

1. 在简单应用中，可直接用二维数组作为图的邻接矩阵（顶点信息等均可省略）
2. 当邻接矩阵的元素仅表示相应边是否存在时，edgetype可采用值为0和1的枚举类型
3. 无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可采用压缩存储
4. 邻接矩阵表示法的空间复杂度是

   

1. 图的邻接矩阵存储表示法具有以下特点

1. 无向图的邻接矩阵一定是一个对称矩阵（并且唯一）。因此，在实际存储邻接矩阵时只需存储上（或下）三角矩阵的元素。
2. 对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是顶点i的度
3. 对于有向图，邻接矩阵的第i行非零元素（或非∞元素）的个数正好是顶点i的出度；第i列非零元素（或非∞元素）的个数正好是顶点i的入度。
4. 用邻接矩阵存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少边，则必须按行，按列对每个元素进行检测，所花费的时间代价很大。
5. 稠密图适合使用邻接矩阵的存储表示
6. 设图G的邻接矩阵为A，

   

   目

知识点2 邻接表法

1. 当一个图为稀疏图时，使用邻接矩阵法显然要浪费大量的存储空间，而图的邻接表法结合了顺序存储和链式存储方法，大大减少了这种不必要的浪费。
2. 所谓邻接表，是指对图G中的每个顶点vi建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对于有向图则是以顶点vi为尾的弧），这个单链表就称为顶点vi的边表（对于有向图则称为出边表）。边表的头指针和顶点的数据信息采用顺序存储（称为顶点表），所以在邻接表中存在两种结点：顶点表结点和边表结点

1. 图的邻接表存储方法具有以下特点

1. 若G为无向图，则所需的存储空间为O(|V|+2|E|)；若G为有向图，则所需的存储空间为O(|V|+|E|)。
2. 对于稀疏图，采用邻接表表示将极大地节省存储空间
3. 在邻接表中，给定一顶点，能很容易地找出它的所有邻边，因为只需要读取它的邻接表。在邻接矩阵中，相同的操作则需要扫描一行，花费的时间为O(n)。但是，若要确定给定的两个顶点间是否存在边，则在邻接矩阵中可以立刻查到，而在邻接表中则需要在相应结点对应的边表中查找另一结点，效率较低。
4. 在有向图的邻接表表示中，求一个给定顶点的出度只需计算其邻接表中的结点个数；但求其顶点的入度则需要遍历全部的邻接表。因此，也有人采用逆邻接表的存储方式来加速求解给定顶点的入度。当然，这实际上与邻接表存储方式是类似的。
5. 图的邻接表表示并不唯一，因为在每个顶点对应的单链表中，各边结点的链接次序可以是任意的，它取决于建立邻接表的算法及边的输入次序。

知识点3 十字链表

1. 十字链表是有向图的一种链式存储结构。在十字链表中，对应于有向图中的每条弧有一个结点，对应于每个顶点也有一个结点。
2. 弧结点中有5个域：tailvex和headvex两个域分别指示弧尾和弧头这两个顶点的编号；hlink域指向弧头相同的下一弧结点；tlink域指向弧尾相同的下一个弧结点；info域存放该弧的相关信息。这样，弧头相同的弧就在同一个链表上，弧尾相同的弧也在同一个链表上。
3. 顶点结点中有3个域：data域存放该顶点的数据信息，如顶点名称；firstin域指向以该顶点为弧头的第一个弧结点；firstout域指向以该顶点为弧尾的第一个弧结点。

注意：顶点结点之间是顺序存储的

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

知识点4 邻接多重表

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

每个顶点也用一个结点表示

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

知识点5 图的基本操作

1. 图的基本操作是独立于图的存储结构的。而对于不同的存储结构，操作算法的具体实现会有着不同的性能。在设计具体算法的实现时，应考虑采用何种存储方式的算法效率会更高。

6.3 图的遍历

图的遍历比树的遍历要复杂得多，因为图的任意一个顶点都可能和其余的顶点相邻接，所以在访问某个顶点后，可能沿着某条路径搜索又回到了该顶点上。为避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点，为此可以设一个辅助数组来标记顶点是否被访问过。图的遍历算法主要有两种：广度优先搜索和深度有限搜索。

知识点1 广度优先搜索

1. 广度优先搜索类似于二叉树的层序遍历算法。基本思想是：首先访问起始顶点v，接着由v出发，依次访问v的各个未访问过的邻接顶点w1,w2,```wi，然后依次访问w1, ``的所有未被访问过的邻接顶点；再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，直至图中所有顶点都被访问过为止。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为始点，重复上述过程，直至图中所有顶点都被访问到为止。
2. BFS算法的性能分析

1. 无论是邻接表还是邻接矩阵的存储方式，BFS算法都需要借助一个辅助队列Q

2. 

1. BFS算法求解单源最短路径问题

若图G=(V,E)为非带权图，定义从顶点u到顶点v的最短路径d(u,v)为从u到v的任何路径中最少的边数；若从u到v没有道路，则距离为∞。利用BFS，我们可以求解一个满足上述定义的非带权图的单源最短路径问题，这是由广度优先搜索总是按照距离由近到远来遍历图中每个顶点的性质决定的

知识点2 连通图的深度优先搜索遍历

1. 深度优先搜索遍历类似于树的前序遍历。假设给定图G的初态是所有顶点均未曾访问过，在G中任选一顶点vi为初始出发点，则深度优先搜索可定义如下：首先，访问出发点vi，并将其标记为已访问过，然后，依次从vi出发搜索vi的每一个邻接点vj，若vj未曾访问过，则以vj为新的出发点继续进行深度优先搜索。
2. 对图进行深度优先搜索遍历时，按访问顶点的先后次序所得到的顶点序列，称为该图的深度优先搜索遍历序列，简称DFS序列。一个图的DFS序列不一定唯一，它与算法，图的存储结构以及初始出发点有关。在DFS算法中，当从vi出发搜索时，是在邻接矩阵的第i行中从左至右选择下一个未曾访问过的邻接点作为新的出发点，若这种邻接点多于一个，则选中的是序号较小的那一个。因为图的邻接矩阵表示是唯一的，故对于指定的初始出发点，由DFS算法所得的DFS序列是唯一的。因为图的邻接表表示不唯一，故对于指定的初始出发点，由算法DFSL所得到的DFS序列也不唯一，它取决于邻接表表示中边表结点的链接次序。
3. 对于具有n个顶点e条边的连通图，算法DFS和DFSL均递归调用n次。在每次递归调用时，除访问顶点及做标记外，主要时间耗费在从该顶点出发搜索它的所有邻接点。用邻接矩阵表示图时，搜索一个顶点的所有邻接点需花费O(n)时间来检查矩阵相应行中所有的n个元素，故从n个顶点出发搜索所需的时间是O(n2)。用邻接表表示图时，搜索n个顶点的所有邻接点即是对各边表结点扫描一遍，故算法DFSL的时间复杂度为O(n+e)

知识点3 连通图的广度优先搜索遍历

1. 广度优先搜索遍历类似于树的按层次遍历。假设给定图G的初态是所有顶点均未曾访问过，在G中任选一顶点vi为初始出发点，则广度优先搜索的基本思想是：首先访问出发点vi，接着依次访问vi的所有邻接点w1,w2,```wi，然后，再依次访问与w1,w2,```wi邻接的所有未曾访问过的顶点，依此类推，直至图中所有和初始出发点vi有路径相通的顶点都已经访问到为止。
2. 我们可将广度优先搜索遍历图所得的顶点序列，定义为图的广度优先搜索遍历序列，简称BFS序列。一个图的BFS序列也不是唯一的，它与算法，图的存储结构及初始出发点有关。
3. 对于具有n个顶点和e条边的连通图，因为每个顶点均入队一次，所以算法BFS和BFSL的外循环次数为n。算法BFS的内循环是n次，故算法BFS的时间复杂度是O(n2)。算法BFSL的内循环次数取决于各顶点的边表结点个数，内循环执行的总次数是边表结点的总个数2e.故算法BFSL的时间复杂度是O（n+e）。

知识点3 非连通图的遍历

1. 若一个无向图是非连通图，则从图中任意一个顶点出发进行深度优先搜索或广度优先搜索都不能访问到图中所有顶点，而只能访问到初始出发点所在的连通分量中的所有顶点。若从每个连通分量中都选一个顶点作为出发点进行搜索，便可访问到整个非连通图中所有的顶点。因此非连通图的遍历必须多次调用深度优先搜索或广度优先搜索算法。
2. 以上讨论的各种遍历算法虽然是以无向图为例，但算法本身对有向图也是适用的。

7.4 生成树和最小生成树

知识点1 生成树与最小生成树

1. 连通图G的一个子图如果是一棵包含G的所有顶点的树，则该子图称为G的生成树。由于n个顶点的连通图至少有n-1条边，而所包含n-1条边及n个顶点的连通图都是无回路的树，所以生成树是连通图的极小连通子图。所谓极小是指边数最少，若在生成树中去掉任何一条边，都会使之变为非连通图，若在生成树上任意添加一条边，就必定出现回路
2. 通常，由深度优先搜索得到的生成树称为深度优先生成树，简称为DFS生成树；由广度优先搜索得到的生成树称为广度优先生成树，简称为BFS生成树。
3. 上面给出的生成树定义，是从连通图的观点出发，针对无向图而言的。由于从图的遍历可求得生成树，我们也可以将生成树定义为：若从图的某顶点出发，可以系统地访问到图中所有顶点，则遍历时经过的边和图的所有顶点所构成的子图，称作该图的生成树。此定义不仅仅适用于无向图，对有向图同样适用。
4. 生成森林
5. 图的生成树不是唯一的，从不同的顶点出发进行遍历，可以得到不同的生成树。对于连通网络G=（V,E），边是带权的，因而G的生成树的各边也是带权的。我们把生成树各边的权值总和称为生成树的权，并把权最小的生成树称为G的最小生成树。
6. MST性质：设G=(V,E)是一个连通网络，U是顶点集V的一个真子集。若(u,v)是G中所有的一个端点在U里，另一个端点不在U里的边中，具有最小权值的一条边，则一定存在G的一棵最小生成树包括此边。

知识点2 普里姆（prim）算法

1. 假设G=(V,E)是连通网络，为简单起见，我们用序号1至n来表示顶点集合，即V。设所求的最小生成树为T=(U,TE），其中U是T的顶点集，TE是T的边集。
2. Prim算法的基本思想是：首先从V中任选一个顶点u0，将生成树T置为仅有一个结点u0的树，即置U={u0}。然后只要U是V的真子集，就在所有那些其一个端点u已在T，另一个端点v还未在T的边中，找一条最短的边，并把该条边（u,v）和其不在T中的顶点v，分别并入T的边集TE和顶点集U。如此进行下去，每次往生成树里并入一个顶点和一条边，直到把所有顶点都包括进生成树T为止。此时必有U==V，TE中有n-1条边。MST性质保证上述过程求得的T是G的一棵最小生成树。
3. 关键在于如何找到连接U和V-U的最短边来扩充生成树T。构造一个较小的候选紫边集，且保证最短紫边属于该候选集。事实上，对于每一个蓝点，从该蓝点到各红点的紫边中，必存在一条最短的紫边，我们只要将所有n-k个蓝点所关联的最短紫边作为候选集，就必定能保证所有紫边中最短的紫边属于该候选集。
4. Prim算法的梗概描述如下

1. 置T为任意一个顶点，置初始候选紫边集
2. While（T中顶点数目<n）
3. {从候选紫边集中选取最短紫边(u,v);
4. 将（u,v）及蓝点v涂成红色，扩充到T中；
5. 调整候选紫边集；
6. }

1. 若候选紫边集中最短紫边不止一条时，可任选其中一条扩充到T中，因此，连通网络的最小生成树不一定是唯一的，但它们的权是相等的。
2. 在带权邻接矩阵dist中，用一个大于任何边上权值的较大值max来表示不存在的边的长度∞

知识点3 克鲁斯卡尔算法

1. 设G=（V,E)是连通网络，令最小生成树的初始状态为只有n个顶点而无边的非连通图T，T中每个顶点自成一个连通分量。我们按照长度递增的顺序依次选择E中的边(u,v)，若该边端点u,v分别是当前T的两个连通分量的顶点，则将该边加入到T中，两个连通分量也由此边连接成一个连通分量；若u,v是当前同一个连通分量中的顶点，则舍去此边。依次类推，直到T中所有顶点都在同一连通分量上为止，T便是G的一棵最小生成树。

7.5 最短路径

1，带权图中求最短路径的问题，即求两个顶点间长度最短的路径，这里路径长度不是指路径上边数的总和，而是指路径上各边的权值总和，它的具体含义取决于边上权值所代表的意义。

2，本节将只讨论有向网络的最短路径问题。习惯上称路径的开始顶点为源点，路径的最后一个顶点为终点。

知识点1 单源最短路径

1. 单源最短路径问题是：对于给定的有向网络G=(V,E）及单个源点v，求从v到G的其余各顶点的最短路径。
2. 迪杰斯特拉算法首次提出按路径长度递增序产生诸顶点的最短路径算法。算法的基本思想是，设置并逐步扩充一个集合S，存放已求出其最短路径的顶点，则尚未确定最短路径的顶点集合是V-S。为了直观起见，我们设想S中顶点均被涂成红色，V-S中的顶点均被涂成蓝色。算法初始化时，红点集仅有一个源点，以后的每一步都是按最短路径长度递增的顺序，逐个地把蓝点集中的顶点涂成红色后，加入到红点集中。

扩充红点集的方法，即每一步只要在当前蓝点集中选择一个具有最小距离值的蓝点k扩充到红点集合中，k被涂成红色之后，剩余的蓝点的距离值可能由于增加了新红点k而发生变化（即减少）。因此，我们必须调整当前蓝点集中各蓝点的距离值。调整距离值的方法：对蓝点集扫描检查，若某蓝点j的原距离值D[J-1]大于新路径的长度D[k-1]+边<k,j>上的权，则将D[j-1]修改为此长度值。

记下路径：为此，设置一个路径向量P[n]，其中p[i-1]表示从源点到达i点的最短路径上该点的前驱顶点。算法结束前，可根据P找到源点到顶点i的最短路径上每个顶点的前驱顶点，从而得到从源点到i的最短路径。

优化：一旦当前蓝点集中所有蓝点的距离值均为max，则表示这些蓝点得到最短路径均不存在，因此，也无需再将它们扩充到红点集。这样，可以在把k加入到红点集之前，判断D[k-1]或min是否等于max？若是的话，则退出扩充红点集的循环，打印结果。

知识点2 所有顶点对之间的最短路径

1. 所有顶点队之间的最短路径问题是：对于给定的有向网络G=(V,E)，要对G中任意两个顶点v,w找出v到w的最短路径。
2. 我们可以依次把有向网络的每个顶点作为源点，重复执行DIJKSTRA算法n次，即求得每对顶点之间的最短路径。另一个更为直接的方式是FLOYD算法，A0等于G的邻接矩阵，表示从i到j不经过任何中间顶点的最短路径长度，An就是从i到j的最短路径长度。FLOYD算法的基本思想是：从A0开始，递推的生成矩阵序列A1,A2,···An
3. 递推公式

知识点3 拓扑排序

1. 一般情况下，我们将顶点表示活动，边表示活动间的先后关系的有向图，称为顶点活动图，或简称为AOV图。
2. 对于一个AOV图，常常要将它的所有顶点排成一个满足下述关系的线性序列，若在AOV网中，从顶点vi到顶点vj有一条路径，则在该线性序列中顶点vi必在顶点vj之前。我们把满足这种关系的线性序列称为拓扑序列，并把AOV网构造拓扑序列的操作称为拓扑排序。
3. 任何无回路的AOV网，其顶点都可以排成一个拓扑序列，并且其拓扑序列不一定是唯一的。
4. 拓扑排序算法的基本步骤

1. 从网中选择一个入度为0的顶点且输出之
2. 从网中删掉此顶点及其所有出边

反复执行这两步，直至所有顶点都已经输出，此时整个拓扑排序已完成；或者直到余留在网中的顶点入度都不为0时终止，此时说明网中存在回路，拓扑排序不能再进行下去。

1. 邻接表作AOV网的存储结构，讨论拓扑排序算法的实现。为了便于考察每个顶点的入度，我们在顶点表中增加一个入度域id，以指示各个顶点当前的入度值，每个顶点的入度域的值随邻接表动态生成过程中累计得到。在算法中，找入度为零的顶点只要对顶点表的入度域扫描即可。但为了避免在每一步选入度为零的顶点时进行重复扫描，我们可以设置一个链栈来存储所有入度为零的顶点，在进行拓扑排序之前，只要对顶点表扫描一遍，将所有入度为零的顶点都推入栈中，以后每次选入度为零的顶点，就可直接从栈顶取出。一旦排序过程中出现新的入度为零的顶点，也同样将其推入栈中。
2. 邻接表作存储结构的拓扑排序算法梗概

1. 扫描顶点表，将入度为零的顶点入栈
2. While（栈非空）

{将栈顶顶点vi弹出并输出之；

检查vi出边表，将每条出边(vi,vj)终点的vj的入度减1，若vj的入度变为零，则把vj推入栈；

}

1. 若输出的顶点数小于n，则输出有回路；否则拓扑排序正常结束

值得注意的是，在算法具体实现时，上述链栈无须占用额外的空间，而是利用顶点表中值为零的入度域来存放链栈的指针（用下标值模拟），利用顶点表中的顶点域vertext来作为链栈的顶点域。由此可知，这里的链栈是用静态链表实现的。因为顶点域中已经存入有相应的顶点，故入栈时只需修改指针。

7.7 关键路径

1，与AOV网相对的是AOE网，即边表示活动的网络。AOE网是一个带权的有向图，其中：顶点表示事件，边表示活动，权表示活动持续的时间。顶点所表示的事件实际上是它的入边所表示的活动均已完成，它的出边所表示的活动可以开始这样一种状态。

2，通常可用AOE网来估算工程计划的完成时间。与AOV网不同，对AOE网有待研究的问题是：完成整项工程至少需要多少时间？哪些活动是影响工程进度的关键？

3，由于在AOE网中有些活动可以并行地进行，所以完成整个工程的最短时间是从源点到汇点的最长路径的长度，这里，路径长度是路径上各边的权值之和。我们把从源点到汇点的最长路径称为关键路径。

4，若把所有活动ai的最早开始时间e(i)和最迟开始时间l(i)都计算出来，就可以找到所有的关键活动。为了求得AOE网的e(i)和l(i)，应该先求网中所有事件vj的最早发生时间ve(j)和最迟发生时间vl(j)。

若活动ai由边<vj,vk>表示，其持续时间记为dut(<j,k>)

1. 值得指出，并不是加快任何一个关键活动都可以缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到这个目的。求出网中所有关键活动后，只要删去网中所有的非关键活动就可得到网的关键路径。
2. 求关键活动算法的基本步骤

1. 对AOE网进行拓扑排序，同时按拓扑序列的次序求出各顶点事件的最早发生时间ve，若网中有回路，则算法终止，否则执行步骤2）
2. 按拓扑序列的逆序求出各顶点事件的最迟发生时间vl
3. 根据各顶点时间的ve值和vl值，求出各活动ai的最早开始时间e(i)和最迟开始时间l(i)。若e(i)=l(i)，则ai为关键活动。

• 排序

8.1 基本概念

1，假定被排序的对象是由一组记录组成的文件，而记录则由若干个数据项（或域）组成，其中有一项可用来标识一个记录，称为关键字项，该数据项的值称为关键字。关键字可用来作为排序运算的依据，它可以是数字类型，也可以是字符类型，选取记录中的哪一项作为关键字，根据问题的要求而定。

2，所谓排序，就是要整理文件中的记录，使得它按关键字递增（或递减）的次序排列起来。显然，当待排序记录的关键字均不相同时，则排序的结果是唯一的，否则排序的结果不一定唯一。如果待排序的文件中，存在有多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是稳定的；反之，若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的

3，各种排序方法可以按照不同的原则加以分类。在排序过程中，若整个文件都是放在内存中处理，排序时不涉及数据的内，外存交换，则称之为内部排序（简称内排序）；反之，若排序过程中要进行数据的内，外存交换，则称之为外部排序。内排序适用于记录个数不很多的小文件，外排序则适用于记录个数太多，不能一次将其全部记录放入内存的大文件。按所用的策略不同，内部排序方法可以分为五类：插入排序，选择排序，交换排序，归并排序和分配排序。

4，每一种内部排序方法均可在不同的存储结构上实现。通常，文件可有下列三种存储结构

1）以一维数组作为存储结构，排序过程是对记录本身进行物理重排，即通过比较和判定，把记录移到合适的位置；

2）以链表（动态链表或静态链表）作为存储结构，排序过程中无须移动记录，仅需修改指针即可，通常把这类排序称为表排序

3）有的排序方法难于在链表上实现，此时，若仍需要避免排序过程中记录的移动，可以为文件建立一个辅助表，这样，排序过程中只需对这个辅助表目进行物理重排，只移动辅助表的表目，而不移动记录本身

5，评价排序算法好坏的标准主要是两条：第一条是算法执行时所需要的时间；第二条是执行算法所需要的附加空间。另外，算法本身的复杂程度也是考虑的一个因素。排序的时间开销时算法好坏的最重要的标志。排序的时间开销主要是指执行算法中关键字的比较次数和记录移动的次数。

若无特定声明，一下均按递增序讨论排序，并且以记录数组作为文件的存储结构。

8.2 插入排序

1，插入排序的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的文件中的适当位置，直到全部记录插入完成为止。

知识点1 直接插入排序

具体做法是将待插入记录R[i]的关键字依次与有序区中记录R[j](j=i-1,i-2````1)的关键字进行比较，若R[j]的关键字大于R[i]的关键字，即将R[j]后移一个位置；若R[j]的关键字小于或等于R[i]的关键字，则查找过程结束，j+1即为R[i]的插入位置。因为关键字比R[i]的关键字大的记录均已后移，所以j+1的位置已经腾空。

知识点2 希尔排序

希尔排序又称缩小增量排序，它的作法是：先取丁一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组，所有距离为d1倍数的记录放在同一个组中，在各组内进行直接插入排序，然后，取第二个增量d2<d1，重复上述分组和排序，直至所取的增量dt=1，即所有记录放在同一组中进行直接插入排序为止。

8.3 交换排序

交换排序的基本思想是：两两比较排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。

知识点1 起泡排序

根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违法本原则的轻气泡，就使其向上漂浮，如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。

知识点2 快速排序

快速排序又称划分交换排序。其基本思想是：在当前无序区中任取一个记录作为比较的基准，用此基准将当前无序区划分为左右两个较小的无序子区，且左边的无序子区中记录的关键字均小于或等于基准的关键字

8.4 选择排序

选择排序的基本方法是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直至全部记录排序完成。

知识点1 直接选择排序

知识点2 堆排序

8.5 归并排序