数据结构知识点-3

第一课绪论

覆盖的知识点最小集：我们的地址是，重庆市九龙坡区白市驿镇金桥2号重庆市农业学校

1.数据结构、数据元素、数据项、数据对象、数据的概念

2.数据的逻辑结构和存储结构的概念

3.算法设计时的注意事项

4.时间复杂度的概念及度量方法

5.空间复杂度的概念及度量方法

知识点细化：

1-001数据结构的基本概念

数据结构是研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学

科。数据结构由数据的逻辑结构、存储结构和对数据的操作三部分组成。

数据元素是数据的基本单位。数据项是数据的不可分割的最小单位。数据对象是性质相同的数据元素

的集合，是数据的子集。数据是所有需输入计算机并为程序所处理的对象的总称。

1-002数据的逻辑结构和存储结构，对后面的名词要能区分哪些是属于逻辑结构哪些属于物理结构

数据的逻辑结构指的是数据元素间的逻辑关系，分为集合、线性结构、树形结构和图形结构，或分为

线性结构和非线性结构。

数据的物理结构指的是数据元素及其间逻辑关系在计算机中的表示，也称存储结构。其中数据元素间

关系的表示有顺序映象(顺序存储结构)和非顺序映象(链式存储结构)两种方式，前者以存储地址上的

联系来体现数据元素之间的逻辑关系，后者则通过指针的指向来体现数据元素之间的逻辑关系。

1-003算法设计时的注意事项

算法是对特定问题求解步骤的一种描述，是指令的有限序列。算法的特性：有穷性、确定性、可行性、

零或多个输入、一或多个输出。算法设计的要求：正确性、可读性、健壮性、高效性。

1-004时间复杂度的概念及度量方法

算法的时间复杂度是算法执行效率的量度，记作：T(n)=O(f(n)),其中n为问题的规模。

衡量算法效率时，通常在算法中选择一种不可再分解的基本操作(该操作的重复执行次数应与算法的

执行时间成正比)，若该操作的执行次数为f(n),则记该算法的时间复杂度为O(f(n))。

若基本操作的执行次数与输入数据有关，则可求算法的平均时间复杂度或最坏时间复杂度。一般，当

所有可能的输入数据集及其出现概率均可知时，可求算法的平均时间复杂度，否则求最坏情况下的时间复

杂度。

1-005空间复杂度的概念及度量方法

算法的空间复杂度是算法执行时所需存储空间的量度，记作：S(n)=O(f(n)),其中n为问题的规模。

分析算法空间复杂度时，一般只考虑执行算法所需辅助空间，但若输入数据所占空间与算法本身有关,

则也应计算在内。若执行算法所需辅助空间与输入数据有关，则可求最坏情况下的空间复杂度。

第二课线性表

覆盖的知识点最小集：

1.线性表的定义和基本操作

2.线性表的实现

(1)顺序存储

⑵链式存储

(3)线性表的应用

知识点细化：

2-010线性表基本概念

线性表是n个数据元素构成的有限序列。表长指线性表中数据元素的个数，表长20。空表指表长为

0的线性表。若线性表非空，则表中第一个元素没有直接前趋，有且仅有一个直接后继；表中最后一个元

素没有直接后继，有且仅有一个直接前趋；其余每个数据元素有且仅有一个直接前趋，有且仅有一个直接

后继。

2-011线性表的基本操作

(1)取元素

GetElem(L,i,&e)

初始条件：线性表L已存在，iWiWListLength(L)

操作结果：用e返回L中第i个数据元素的值

(2)插入

Li>tInsert(&L,i,e)

初始条件：线性表L已存在，1WiWListLength(L)+l

操作结果：在L中第i个位置之前插入数据元素e,L的长度加1

(3)删除

LiitDelete(&L,i,&e)

初始条件：线性表L已存在且非空，iWiWLislLength(L)

操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1

2-012线性表的顺序存储方式

用一组地址连续的存储单元依次存储线性表中数据元素，以数据元素物理地址上的相邻关系表示其逻

辑上的先后关系。以顺序存储方式保存的线性表也称顺序表。

在顺序表中访问结点时，由丁第一个元素就存储在相对地址为i-1的位置上(随机存取)，算法时间复:

杂度为。⑴。

设顺序表长为n,则在第i(lWiWn+1)个元素前插入时，需移动n-i+1个元素。设在各位置上插入元

素的概率相等，则需移动元素的平均个数为n/2,算法时间复杂度为O(n)。

设顺序表长为n,则删除第i(iWiWn)个数据元素时，需移动n-i个元素。设删除任一元素的概率相

等，则需移动元素的平均个数为：(n-l)/2,算法时间复杂度为O(n)。

2-013以静态分配方法实现顺序表

由于线性表的长度是可变的，采用静态分配，则需定义最大可能长度，并需设变量记录线性表长。

#defineMAXSIZE1000〃最大可能长度

typedefstruct(

ElemTypeelem[MAXSIZE];〃保存数据元素

intlen;〃线性表长度

JSqList;〃顺序表类型名(静态线性表就是用数组来存储的那种形式)

2-014以一次性动态分配方法实现顺序表

采用一次性的动态分配方法时，需定义最大可能长度，并需设变量记录线性表长。

#defineMAXSIZE1000〃最大可能长度

typedcfstruct{

ElemType*elem;//保存首地址

intlen;〃线性表长度

ISqList;〃顺序表类型名（动态的就是需要用指针来实现的）

2-015以带增量的动态分配方法实现顺序表

采用带增量的动态分配方法时，需定义初始分配量和增量，并需分别设变量以记录线性表长及当前分

配总量。

#defineLISTJNIT_SIZE100//初始分配量，以数据元素个数为单位

#defineLISTINCREMENT10〃增量

typedefstruct）

ElemType*elem;//保存首地址

intlen;〃线性表长度

intlistsize;〃当前分配量，以数据元素个数为单位

JSqList;〃顺序表类型名

在该结构上实现三个基本操作。

2・016线性表的链式存储方式

用一组任意的（可连续可不连续）存储单元存储线性表中数据元素，用指针来表示数据元素间的逻辑

关系。根据所用指针的类型、个数、方法等的不同，又可分为：、循环链表、双向线性链表（单链表）链

表、双向循环链表、静态链表等。

2・017线性链表（单链表）及其特点

每个结点由两个域组成，其中数据域用以保存数据元素的值，指针域用以保存其直接后继结点的绝对

地址。表中最后一个结点的指针域值为空指针NULL。在首元结点前还可附设头结点，以方便运算的实现

（无论表空与否，头指针值不变；插入时不必特别判断是否在第一个元素之前插入：删除时不必特别判断

是否删除第一个元素）。头结点的数据域一般不使用。头结点（若表中不含头结点则为首元结点）的地址

保存在头指针中。

typedefstructLNode!

ElemTypedata;〃数据域

slruclLNodc*ncxl;〃指针域

）LNode,*LinkList;

在该结构上实现三个基本操作。

在单链表中访问结点时，必须从头指针开始顺序查找该结点，指针的移动是其中的基本操作，查找第

i个结点时需移动i-1次。设查找任一元素的概率相等，则需移动指针的平均次数为（n-l）/2,算法时间复杂

度为0（n）。

在单链表中插入结点时，时间主要用于查找插入位置，即查找第i-1个结点上。算法的时间复杂度为

O（n）o

在单链表中删除结点时，时间主要用于查找待删结点。算法的时间复杂度为O（n）。

2.018循环链表及其特点

循环链表的结点结构同单链表，但表中最后一个结点的指针域保存头结点（若表中不含头结点则为首

元结点）的绝对地址。在循环链表中，从任一结点出发均可访问到表中其余结点。

循环链表上基本操作的实现与单链表基本相同，主要区别在于算法中的循环条件。

2.019双向链表及其特点

2-024线性表的应用

基于线性表的各种存储方式实现指定的操作，尤其是各种链表（带头结点、不带头结点）（仅设头指

针、仅设尾指针、分设头尾指针）上插入（当前结点之前，当前结点之后，头结点之后，尾结点之后，其

它位置），删除（当前结点、前趋结点、后继结点、首元结点、具它结点），分解（一表到多表），归并（多

表合一表），查找（顺序表上的顺序和折半查找，链表上的顺序查找）、排序（各种排序方法的实现）等。

第三课栈、队列和数组

覆盖的知识点最小集：

1.栈和队列的基本概念

2.栈和队列的顺序存储结构

3.栈和队列的链式存储结构

4.栈和队列的应用

5.特殊矩阵的压缩存储

知识点细化：

3-001栈的基本概念

栈是限定仅在表尾端进行插入、删除的线性表；表尾端称栈顶，而称栈顶元素；表头端称栈底，ai称

栈底元素。栈的长度即栈中元素个数。长度为0的栈称空栈。向栈中插入元素称入栈，从栈中删除元素称

出栈,栈的修改是按后进先出的原则进行的。

3-002栈的顺序存储方式

与线性表的顺序存储方式类似：三种分配方法；线性表长度分量一栈顶指针分量（指向栈顶元素的下

一个位置）。以顺序存储方式保存的栈称顺序栈。

设采用静态分配。实现入栈和出栈操作。

#defineMAXSIZE1000〃栈的最人容量

typedefstruct（

ElemTypeelem[MAXSIZE];〃保存数据元素，以低地址为栈底

inttop;〃栈顶指针

JSqStack;

3・003栈的链式存储方式

与单链表类似：带/不带头结点；插入、删除操作点（即栈顶端）放在靠近头指针的一端。以链式存储

方式保存的栈称链栈。

实现入栈和出栈操作

typedefstructSNode（

ElemTypedata;

structSNodc*next;

}SNode,*LinkStack;

3-101队列的基本概念

队列是限定仅在表尾端进行插入，而在表头端进行删除的线性表。表头端称队头，a1称队头元素；表

尾端称队尾，“称队尾元素。队列的长度即队列中元素个数。长度为。的队列称空队。向队列中插入元素

称入队，从队列中删除元素称出队。队列的修改是按先进先出的原则进行的。

双端队列是限定仅在表的两端进行插入删除操作的线性表（如果规定从哪端入的只能从哪端出，则退

化为两个栈底相邻的栈）。输入受限的双端队列是插入操作仅在一端进行而删除操作可在两端进行的线性

表。输出受限的双端队列是删除操作仅在--端进行而插入操作可在两端进行的线性表。

3-102队列的顺序存储方式

线性表的顺序存储方式f去除线性表长度分量，添加指向队头元素所在位置的队头指针以及指向队尾

元素的下一个位置的队尾指针一产生假溢出问题f三个解决方案：（1）每删一个元素，其余元素向前移；（2）

发生假溢出时才移动剩余元素；（3）采用循环队列，不移动元素，但不能采用带增量的动态分配，且需解决

队空、队满判定条件相同的问题，解决方法可为：①添加长度分量（添加标志分量）②浪费一个元素的存

储空间。

循环队列另一设计方案：以数组存储元素，以队尾指针指示队尾元素所在位置，并记录队列长度。

循环队列只能采用静态分配或一次性动态分配，不能采用带增量的动态分配，因而队列最大长度应能

预估。

3-103循环队列的入队和出队

设采用一次性动态分配，设置队头队尾指针，以浪费一个元素存储空间的方式解决队空、队满判定条

件相同的问题。

实现入队、出队和求队列长度操作。

#defineMAXSIZE1000

typedefstruct{

ElemType*base;

intfront;

intrear;

JCirQueue;

3-104队列的链式存储方式

与单链表类似：带/不带头结点；删除操作点（即队头端）放在靠近头指针的一端，另设尾指针，指向

队尾元素结点，以方便插入操作的执行。以链式存储方式保存的队列称链队列。

链队列在执行出队操作时要考虑空队列和队列中只有一个结点这两种特殊情况。

3405链队列的入队和出队

实现入队和出队操作。

typedefstructQNode{

ElemTypedata;

structQNode*next;

}QNode;

typedefstruct（

QNode*front;

QNode*rear;

JLinkQueue;

3-106栈和队列的应用

栈在表达式求值、括号匹配、进制转换、递归问题等中都有应用。队列在共享打印机缓冲池、消息队

列、二叉树的层序遍历、图的广度优先遍历等中都有应用。

3-107从递归到非递归

一个函数直接或间接调用自己即为递归。

函数递归是因为：（1）有很多数学函数是递归定义的；（2）有些数据结构本身就有递归性（广义表、树、

二叉树），其上操作常用递归描述；（3）有些问题本身虽无明显递归结构，但用递归求解较简单（汉诺塔）。

递归算法可转换为用栈来实现的半递归算法。

3-201对称阵的定义及压缩存储

若n阶方阵A有a产却，ijG[l,n]/[0,n-l],则称A为n阶对称阵。

压缩存储时用一组地址连续的存储单元按行或列优先的顺序保存对称阵上或下三角（含对角线）中的

数据元素，共n（n+l）/2个。

对矩阵进行压缩存储是为了节省空间，仍属随机存取，但计算地址的运算会复杂。

3-202上三角阵的定义及压缩存储

若n阶方阵A有a产C,7£[1,亚[0.1]且间，C为常量，则称A为n阶上三角阵。上三角阵中下三

角部分元素（不含对角线）的值为常量。

压缩存储时用一组地址连续的存储单元按行或列优先的顺序保存上三角（含对角线）中的数据元素，

再加一个下三角常量，共n（n+l）/2+l个。

3-203下二角阵的定义及压缩存储

若n阶方阵A有a产C,且i<j,C为常量，则称A为n阶下三角阵。下三角阵中上三

角部分元素（不含对角线）的值为常量。

压缩存储时用一组地址连续的存储单元按行或列优先的顺序保存下三角（含对角线）中的数据元素，

再加一个上三角常量，共n（n+l）/2+l个。

3-204对角阵的定义及压缩存储

若n阶方阵A中除主对角线及其上下若干条对角线上的元素之外，其余元素均为0,则称对角阵。

将矩阵中的非零元按某种次序（行优先、列优先、对角线顺序等）存储于一组地址连续的存储单元。

对n阶x对角阵A进行压缩存储，采用行优先/列优先/指定的对角线顺序-第一元素为aoo/a”，保存在

足够大的一维数组e中。若a.保存在e[k]中，要求由ij值求k值。

3-205稀疏阵的定义及压缩存储

设在mXn矩阵中，有t个数据元素不为零，则通常认为当B=」一<0.05时，称该矩阵为稀疏矩阵,

mxn

其中6称稀疏因子。

对稀疏矩阵进行压缩存储时，可只保存其中非零元，同时还需指明非零元所处的行列位置及总的行数、

列数（可再加非零元个数），此即稀疏矩阵的三元组表示法。此时不能再随机存取。

第四课树与二叉树

覆盖的知识点最小集：

I.树的基本概念

2.二叉树

(1)二叉树的定义及具主要特征

(2)二叉树的顺序存储结构和链式存储结构

(3)二叉树的遍历

(4)线索二叉树的基本概念和构造

3.树、森林

(1)树的存储结构

(2)森林与二叉树的转换

(3)树和森林的遍历

4.树与二叉树的应用

(1)二叉排序树

⑵平衡二叉树

(3)哈夫曼(Huffman)树和哈夫曼编码

知识点细化：

4-001树和结点

树是n520)个结点的有限集。若n=0则为空树，记为中。若nWO,贝的⑴有且仅有一个根结点；

⑵若n>l,则其余结点可分为m(m>0)个互不相交的有限集TI,T2,…,Tm，其中每一集合又是一棵树，

并称根的子树.若将树中结点的各子树看成从左至右是有次序的，即不能互换的，则称该树为有序树，否

则称无序树，结点可分为分支结点(根结点+内部结点)和叶子结点°结点的度即结点拥有的子树数。树

的度是树内各结点的度的最大值。结点的层次从根开始定义起，根为第一层，根的孩子为第二层，余则类

推。树的深度(高度)即树内结点的层次的最大值。

4-002二叉树

二叉树是具有如下特点的树型结构：⑴每个结点至多只有两棵子树；⑵二叉树的子树有左右之分。

二叉树有五种基本形态：⑴空二叉树⑵只有根结点⑶根结点只有左子树⑷根结点只有右子树⑸根结点

左右子树都有。

二叉树和度为2的有序树的本质区别在于有序树上结点若只有一个孩子，则孩子无次序之分。

4-003满二叉树和完全二叉树

满二叉树是深度为k且有2k-l个结点的二叉树。若含n个结点的二叉树中各结点位置与同深度的满二

叉树按层序的前n个结点位置相对，则称完全二叉树,满二叉树一定是完全二叉树，反之未必。若完全二

叉树上有n个结点按层序从1开始编号，则第|_〃2」个结点是最后一个有孩子的结点；若n是偶数，则该

完全二叉树上有一个度为1的结点，若n是奇数，则该完全二叉树上没有度为1的结点。

4-004森林

森林为m(m2。)棵互不相交的树的集合。

4-101二叉树性质一

在二叉树的第i层上最多有2皿个结点(i21)。

【证明】

⑴当i=l时，只有一个根结点。2皿=2°=1,结论成立。

⑵假设第k层上最多有2kd个结点

•・•二叉树中每个结点最多有2个孩子

，第k层结点的孩子总数最多为2卜|><2=2卜个

•・,第k+1层上的结点均为第k层结点的孩子

工第k+1层上最多有2k=2（k+.个结点

⑶由⑴⑵可得结论成立。

4-102二叉树性质二

深度为k的二叉树最多有2k.i个结点。（k-l）

【证明】由二叉树性质1可知在二叉树的第i层上最多有2评个结点（i2l）,因此深度为k的二叉树最多结

2°（T）=2J。

点数为：Z2'T=2°+2i+...+2J

1-2

深度为k的m叉树最多有.（用上-l）/（/w-l）个结点。

4-103二叉树性质三

对任意二叉树T,若其叶子结点数为no,度为2的结点数为m，则n产血+1。

【证明】设二叉树中度为1的结点数为川

・・•二叉树中结点的度只能为0、1、2

结点总数n=no+n1+图;....⑴

又.••含n个结点的二叉树必有n-l条分支，这些分支是有孩子的结点提供的

工分支数b=n-l=2*n2+l*ni

•二结点总数n=2*n2+l*ni+l；..⑵

由⑴和⑵,可得no=n2+l,结论成立。

4・104二叉树性质四

具有n个结点的完全二叉树的深度为［log?〃」+1。

【证明】设完全二叉树深度为k

・・,前k・l层元素个数为2k

又•・•第k层元素个数至少为1,最多为2k.i

・•・深度为k的完全二叉树最多2<1个结点，最少2kd个结点

（另：深度为k的二叉树最多2卜-1个结点，最少k个结点）

即（211）十1WnWQll）十即2k-YnW2k-lv2k

/.k-Klog2n<k

Iog2n<k<log2n+1

Vk是整数

.\k=|_log2/zj+l

4-105二叉树性质五

若对一棵含n个结点的完全二叉树中的结点按层序进行编号，则其中编号为i的结点有:

①若i=l,则结点i为二叉树的根，无双亲，若IviWn,则其双亲为结点匕/2」；

②若2i>n,则结点i无左孩子，否则其左孩子为结点2i；

③若2i+l>n,则结点i无右孩子，否则其右孩子为结点2i+l°

4-106二叉树的顺序存储结构

用一段地址连续的存储空间，从下标为1的存储单元开始按层序依次保存完全（满）二叉树中的数据

元素，以结点间存储地址上的联系(按层序编号为i的结点保存在下标为i的存储单元，其双亲若存在则

保存在下标为i/2的存储单元，其左孩子若存在则保存在下标为2*i的存储单元，其右孩子若存在则保存在

下标为2巧+1的存储单元)，体现结点间双亲与孩子的关系。

二叉树顺序存储结构的优点包括：(1)便于由一个结点找其双亲结点、孩子结点；(2)存储密度大。缺点

包括：(1)需预测二叉树上可能的最多结点数。适用：完全二叉树、满二叉树，若用于保存一般二叉树，则

最坏情况下，深度为k的二叉树只含k个结点却需使用长度为2k-l的一维数组保存。

4-107二叉树的二叉链表存储结构

每个结点含三个域，即数据域、指向左孩子的指针域和指向右孩子的指针域。设置头指针，指向根结

点。含n个结点的二叉链表中有n+1个空链域。

typedefstructBiTreeNode{

TElcmTypcdata;

structBiTreeNode*lchild;

structBiTreeNode*rchild;

}BiTreeNode,*BiTree;

4-108二叉树的三叉链表存储结构

在二叉链表的基础上，每个结点再增加一个指向双亲的指针域。

typcdcfstructBiTreeNode{

TElemTypedata;

structBiTreeNode*lchild;

structBiTreeNode*rchild;

structBiTreeNode"parent;

)BiTreeNode,*BiTree;

4-109二叉树的中序遍历

【方法】(D中序遍历左子树；⑵访问根结点；(初中序遍历右子树。

【递归算法】

intInOrderTraverse(BiTreeT,int(*visit)(TElemTypee)){

〃若遍历成功则返回1,否则返回0

if(!T){

if(!IiiOrderTraverse(T->luhild,visit))return0;〃中序遍历左子树

if(!visit(T->data))return0;〃访问根结点

if(!lnOrdcrTraversc(T->rchild,visit))return0;〃中序遍历右子树

}

return1;

)//InOrderTraverse

【非递归算法】

intInOrderTraverse(BiTreeT,int(*visit)(TElemTypee)){

〃若遍历成功则返回1,否则返回0

InitStack(S);

P=T；

while(p||!StackEmpty(S)){

if(P)(

Push(S,p);

p=p->lchild;

else{

Pop(S,p);

if(!visit(p->data))return0;

p=p->rchild;

)//else

(//while

return1;

}//InOrderTraverse

辅助栈的最大容量等于二叉树的深度，最坏情况下为n。

二叉树遍历算法中的基本操作是访问结点，无论按何种次序，对含n个结点的二叉树，时间复杂度均

为O(n)。

4410二叉树的先序遍历

【方法】⑴访问根结点；⑵先序遍历左子树；⑶先序遍历右子树。

【递归算法】

intPreOrderTraverse(BiTreeT,int(*visit)(TElemTypee)){

〃若遍历成功则返回1,否则返回0

if(!T){

if(!visit(T->data))return0;〃访问根结点

if(!PreOrderTraverse(T->lchild,visit))return0;〃先序遍历左子树

if(!PreOrderTraverse(T->rchild,visit))return0;〃先序遍历右子树

)

return1;

}//PreOrderTraverse

【非递归算法】

intPreOrderTraverse(BiTreeT,int(*visit)(TElemTypee)){

〃若遍历成功则返回1,否则返回0

InitStack(S);

P=T；

while(p||!SlackEniply(S)){

if(!visit(p->data))return0;

if(p->rchild)Push(S,p->rchild);

p=p->lchild;

)

else{

Pop(S,p);

}//else

}//while

return1;

(//PreOrderTraverse

4-111二叉树的后序遍历

【方法】⑴后序遍历左了树；⑵后序遍历右了树；⑶访问根结点。

【递归算法】

intPostOrderTraverse(BiTreeT,int(*visit)(TElemTypee)){

〃若遍历成功则返回1,否则返回0

if(!T){

if(!PostOrderTraverse(T->lchild,visit))return0;〃后序遍历左子树

if(!PoslOrderTraverse(T->rchild,visit))return0;〃后序遍历右子树

if(!visit(T->data))return0;〃访问根结点

)

return1;

}//PostOrderTraverse

【非递归算法】

typedefstruct{

BiTreeNodenode;

intflag;//0表示结点node的右子树尚未被访问，I表示结点node的右子树已被访问

(SElemType;

iniPostOrderTraverse(BiTreeT,int(*vi$it)(TElemTypee)){

//若遍历成功则返回1,否则返回0

InitStack(S);

P=T；

while(p||!StackEmpty(S)){

if(P){

temp.node=p;

temp.flag=0;

Push(S,temp);

p=p->lchild;

)

else{

Pop(S,temp);

if(temp.flag){〃出栈结点的左、右子树均已被访问

if(!visit(temp.node->data))return0;

)

else{〃出栈结点的右子树尚未被访问

temp.flag=l;

Push(S,temp);//修改标志位后重新入栈

p=temp.node->rchild;〃处理右子树

)

}//if

(//while

(//PostOrderTraverse

4-112二叉树的层序遍历

【方法】⑴按结点所在层次，由低层向高层依次遍历；⑵同层中按自左向右次序遍历。

【算法】

intLeveIOrderTraverse(BiTreeT.int(*visit)(TEIemTypee)){

〃若遍历成功则返回1，否则返回0

if(IT)return1;〃空二叉树

InitQueue(Q);//初始化辅助队列

if(!visit(T->data))return0;〃访问根结点

EnQueue(Q,T);〃指向根结点的指针入队

while(!QueueEmpty(Q)){〃若队列非空

DeQueue(Q,p);〃队头指针出队

if(p->Ichild){〃先访问p所指结点的左孩子，再访问其右孩子

if(!visit(p->lchild->data))return0;

EnQueue(Q,p->lchild);

)//if

if(p->rchild){

if(!visit(p->rchild->data))return0;

EnQucuc(Q,p->rchild);

}//if

(//while

return1;

)//LevelOrderTraverse

4-201线索二叉树

二叉树的任何一种遍历，其实质均为对非线性结构的线性化。若将遍历序列中所体现的结点间的线性

关系保存在二叉树的存储结构中，这样的二叉树称线索二叉树，存储结构称线索链表。线索链表中指向结

点的前驱、后继的指针称线索。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。

一棵二叉树在中序线索化后，其中空的链域的个数是2。一棵左子树为空的二叉树在先序线索化后，

其中空的链域的个数是2；一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是lo一

棵右子树为空的二叉树在后序线索化后，其中空的链域的个数是2；一棵左右子树均不空的二叉树在后序

线索化后，其中空的链域的个数是1。

4-202线索链表

【方法一】在二叉链表中每个结点上增加两个指针域，分别用以指向该结点在遍历序列中的直接前驱

和直接后继。

【方法二】利用二叉链表中的空链域保存结点间的线性关系。规定：若结点的Ichild域为空，则在其

中保存指向其直接前驱的指针；若结点的「child域为空，则在其中保存指向其宜接后继的指针；每个结点

再设两个标志域Itag和rtag,当指针域指向孩子时标志域取值为0,否则取值为1。

在线索链表中还可添加头结点：头结点的data域不使用，其Ichiki域指向根，llag域为0,rchild域指

向遍历序列中的尾结点，rtag域为1。同时，令遍历序列中首结点的Ichild域和尾结点的rchild域均指向头

结点。

typedefenum{Link,Thread}PointerTag,//Link值为0,Thread值为1

typedefstructBiThrNode{

TElemTypedata;

structBiThrNode*lchild;

structBiThrNode*rchild;

PointcrTagItag;

PointerTagrtag;

(BiThrNode,*BiThrTree;

4-203中序线索化

【方法】

对二叉链表T进行中序线索化，生成二叉中序线索链表Thr1。

⑴生成头结点，其data域不用，ltag=Link,rtag=Thread；

⑵若二叉树为空，则头结点的Ichild和rchild均指向自己；

⑶若二叉树非空，则头结点的Ichild指向根，rchild需指向遍历序列中的尾结点，应在遍历完成后处理；

⑷对二叉链表进行中序遍历，对于在遍历过程中遇到的每个结点：

若Ichild域非空

则令Ilag=Link

否则令lchild=指向其直接前驱的指针且令Mg=Thread(在遍历中设指针pre指向刚访问过的结点)

若rchild域非空

则令rtag=Link

否则令rchild=指向其直接后继的指针且令rtag=Thread(此操作需在访问到下一结点时处理，即访问当

前结点时，处理其直接前驱的rchild、rtag域)。

【递归算法】

voidInOrderThreading(BiThrTree&Thrt,BiThrTreeT){

〃由二叉链表T生成二叉中序线索链表Thrt

Thrt=(BiThrTree)malloc(sizeof(BiThrNode));〃生成头结点

if(!Thrt)exit(-2);

if(!T){〃二叉树为空树

Thrt->lchild=Thrt;

Thrt->ltag=Link;

Thrt->rchild=Thrt;

Thrt->rtag=Thread;

)//if

else{

Thrt->lchild=T;

Thrt->ltag=Link;〃头结点的Ichiki指向二叉链表根结点

pre=Thrt;//pre为指向前驱的指针，在InThreading中需使用，此处用全局变量实现，也可设置为参数

InThreading(T);〃调用中序线索化函数处理二叉链表T

pre->rchild=Thrt;

pre->rtag=Thread;〃中序遍历完成，pre指向遍历序列中的尾结点，该结点一定无右子树

Thrt->rchild=pre;

Thrt->rtag=Thread;〃头结点的rchild指向遍历序列中的尾结点

}//else

}//InOrderThreading

voidInThreading(BiThrTrccp){

if(P){

InThreading(p->lchild);〃左子树线索化

if(!p->lchild){p->lchild=pre;p->ltag=Thread;}

elsep->ltag=Link;

if(!pre->rchild){pre->rchild=p;pre->rtag=Thread;}

elsepre->rtag=Link;

InThrcading(p->rchild);〃右子树线索化

)//if

(InThreading

【非递归算法】

voidInOrdcrThrcading(BiThiTrcc&Thrt,BiThrTreeT){

〃由二叉链表T生成二叉中序线索链表Thrt

Thrt=(BiThrTree)malloc(sizeof(BiThrNode));〃生成头结点

if(!Thrt)exit(-2);

if(!T)(〃二叉树为空树

Thrt->lchild=Thrt;

Thrt->ltag=Link;

Thrt->rchiId=Thrl;

Thrt->rtag=Thread;

(//if

else{

Thrt->lchild=T;

Thrt->ltag=Link;〃头结点的Ichiki指向二叉链表根结点

pre=Thrt;//pre为指向前驱的指针

InitSlack(S);

P=T；

while(p||!StackEmpty(S)){

if(P){

Push(S,p);

p=p->lchild;

)

else{

Pop(S,p);

if(!p->lchild){p->lchild=pre;p->ltag=Thread;(

elsep->ltag=Link;

if(!pre->rchild){pre->rchild=p;pre->rtag=Thread;}

elsepre->rtag=Link;

p=p->rchild;

}//e!se

}//while

pre->rchild=Thrt;

pre->rtag=Thread;〃遍历序列中的尾结点的rchild域指向头结点

Thrt->rchild=pre;

Thrt->rtag=Thread;〃头结点的rchild域指向遍历序列中的尾结点

}//IriOrderThreading

4-204中序线索二叉树的遍历

【方法】

对中序线索二叉树进行遍历，可从头结点开始，沿前驱或后继进行遍历。

若对中序线索二叉树从首结点起沿后继进行遍历，则遍历序列中首结点是二叉树中最左下的结点。若

结点无右子树，则其直接后继由其右指针指向，否则其直接后继为其右子树中最左下的结点。

若对中序线索二叉树从尾结点起沿前驱进行遍历，则遍历序列中尾结点由头结点的右指针指向(二叉

树中最右下的结点)。若结点无左子树，则其直接前驱由其左指针指向，否则其直接前驱为其左子树中最

右下的结点。

【算法】

StatusIOT_Thr(BiThrTreeT,Status(*visit)(TElemTypee)){

〃对中序线索链表T从首结点起，沿后继进行遍历，遍历成功则返回1,否则返回0

p=T->lchiid;〃p指向根结点

while(p!=T){

〃第一次判定时若p等于T,则二叉树为空，以后判定时若p等于T,则遍历完成

while（p->ltag==Link）p=p->lchild;

〃找p的最左下孩子，第一次p指向根，所找结点即遍历序列首结点，

//以后p指向刚访问过的结点的右孩子，此时刚访问过的结点，其rtag应为Link

if（!visit（p->data））return0;

while（p->rtag==Thread&&p->rchild!=T）{

〃若p所指结点的rchild指向其直接后继，且该直接后继不是头结点，即p所指结点不是遍历序列尾

结点

p=p->rchild;

if（!visit（p->data））return0;

}//while

}while

}//IOT_Thr

4-205先序线索化及其遍历

若对先序线索二叉树从首结点起沿后继进行遍历，则遍历序列中首结点是二叉树的根结点。若结点无

右子树，则其直接后继由其右指针指向，否则其直接后继为其左孩子（即左子树的根结点），若左孩子不

存在，则为其右孩子。

若对先序线索二叉树从尾结点起沿前驱进行遍历，则遍历序列中尾结点是二叉树中最右下的结点。若

结点无左子树，则其直接前驱由其左指针指向，否则其直接前驱为其双亲（当该结点是其双亲的左孩子或

该结点虽是其双亲的右孩子但其双亲并无左孩子时）或为其双亲的左子树中最右下的结点（当该结点是其

双亲的右孩子且其双亲有左孩子时），若该结点无双亲（即根结点）则无直接前驱。

4-206后序线索化及其遍历

若对后序线索二叉树从首结点起沿后继进行遍历，则遍历序列中首结点是二叉树中最左下的结点。若

结点无右子树，则其直接后继由其右指针指向，否则其直接后继为其双亲（当该结点是其双亲的右孩子或

该结点虽是其双亲的左孩子但其双亲并无右孩子时）或为其双亲的右子树中第一个被访问的结点（所以仍

需栈的支持）（当该结点是其双亲的左孩子且其双亲有右孩子时）。

若对后序线索二叉树从尾结点起沿前驱进行遍历，则遍历序列中尾结点是二叉树的根结点,若结点无

左子树，则其直接前驱由其左指针指向，否则其直接前驱为其右子树的根，若该结点无右子树，则其直接

前驱为其左子树的根。

4-301哈夫曼二叉树（最优二叉树）

哈夫曼（二叉）树是带权路径长度最短的（二叉）树，又称最优（二叉）树’树的带权路径长度指树

中所有叶子结点的带权路径长度之和；结点的带权路径长度指从根到结点的路径长度与结点上权的乘积；

结点间的路径长度指从一个结点到另一结点的路径上的分支数。

完全二叉树是路径长度最短的二叉树。树的路径长度指根到每个结点的路径长度之和。

4・302哈夫曼二叉树（最优二叉树）

由给定的n个权值构造哈夫曼二叉树的方法（哈夫曼算法）如下：

⑴根据给定的n个权值{wi,W2,…,wj构成n棵二叉树的集合F={TI,T2,…,T”,其中每棵二叉树只含一

个带权的根结点，其左右子树均空；

⑵在F中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且置新的二叉树的根

结点的权值为其左、右子树上根结点的权值之和；

⑶在F中删除这两棵二叉树，同时将新得到的二叉树加入F；

⑷重复⑵和（3）,直到F只含一棵二叉树，此即哈夫曼二叉树。

4-303哈夫曼编码

【方法】⑴以字符出现频率为权值，构造哈夫曼二叉树；⑵约定以左分支表示0,右分支表示1,把从根

到叶子的路径上所有分支构成的01串作为叶子的二进制编码，即为哈夫曼编码。

4-401树的双亲表示法存储结构

用一组地址连续的存储单元，按一定次序保存树中数据元素，每个结点中设置指针，指示具双亲位置。

此法易查找结点的双亲，而找结点的孩子则需扫描整张表。

#defineMAXSIZE1000

typedefstructPTNode{

ElemTypedata;

intparent;

JPTNode;

typedefstruct{

PTNodenodes[MAXSIZE];

intn;

（ParentTree;

4-402树的孩子表示法存储结构

用一组地址连续的存储单元，按一定次序保存树中数据元索，每个结点中设置指针，指向其孩子链表。

此法易查找结点的孩子，而查找结点的双亲则需扫描整张表。

#defineMAXSIZE1000

typedefstructChildNode{

intchild;

structChildNode*next;

JChildNodc,*ChildPtr;〃孩子链表中的结点

typedefstruct{

ElemTypedata;

ChildPtrfirstchild;

}CTNode;

typedefstruct{

CTNodenodes[MAXSIZEl;

intii;〃树中结点数

intr;〃根的位置

JChildTrcc;

4-403树的双亲一孩子表示法存储结构

双亲表示法与孩子表示法的组合。结点间逻辑关系的存储冗余。

4-404树的孩子.兄弟表示法存储结构

用二叉链表保存与树对应的二叉树。

4-405树与二叉树的相互转化

树与二叉树可相互转化。由树转化而来的二叉树中，结点的左指针指向它在树中的第一个孩子结点，

右指针指向它在树中的右兄弟结点。

由一棵非空树转化而得的二叉树，其根结点无右子树（若树中只有一个结点，则转化而得的二叉树也

没有左了树）。

若二叉树的根结点无右子树，则可将它转化为树。

对树的操作也可转化为对相应二叉树的操作。树的先序遍历相当于对相应二叉树的先序遍历。树的后

序遍历相当于对相应二叉树的中序遍历。

4-406树的遍历

⑴先序遍历：①访问树的根结点；②从左至右，依次先序遍历根的每棵子树。

⑵后序遍历：①从左至右，依次后序遍历根的每棵子树；②访问树的根结点。

4-407森林与二叉树的相互转化

将森林中各棵树的树根看作互为兄弟。

若森林中有多棵树，则转化而得的二叉树，其根结点有右子树。若二叉树的根结点有右子树，则转化

而得的必为森林。

森林的先序遍历相当于对相应二叉树的先序遍历。森林的中（后）序遍历相当于对相应二叉树的中序

遍历。

4-408森林的遍历

⑴森林的先序遍历

若森林非空，则：

①访问森林中第一棵树的根结点；

②先序遍历第一棵树中根结点的子树森林；

③先序遍历除去第一棵树之后剩余的树构成的森林。

⑵森林的中（后）序遍历

若森林非空，则：

①中序遍历森林中第一棵树的根结点的子树森林；

②访问第一棵树的根结点；

③中序遍历除去第一棵树之后剩余的树构成的森林。

第五课图

覆盖的知识点最小集：

I.图的基本概念

2.图的存储及基本操作

(1)邻接矩阵法

⑵邻接表法

3.图的遍历

(1)深度优先搜索

⑵广度优先搜索

4.图的基本应用

(1)最小(代价)生成树

(2)最短路径

(3)拓扑排序

(4)关键路径

知识点细化：

5-001图

图G=(V,{VR}),其中V为顶点的非空有限集合，VR为顶点间关系的集合，即图中边的集合(注意：

离散数学中将树定义为一个连通且无回路的无向图)。

图中的边若为顶点的无序序偶，则称无向边(简称边)，若为顶点的有序序偶，则称有向边(简称弧)。

若图中的边均为无向边，则称无向图；含n个顶点n(n-l)/2条边的无向图称无向完全图;若图中的边均为

有向边，则称有向图；含n个结点n(n-l)条弧的有向图称有向完全图。网是边/弧上带权的图。权是与图

的边/弧相关的数。

5-002顶点的度

无向图中依附于顶点v的边的数目，称顶点v的度，记TD(v).

有向图中以顶点v为弧头顶点的弧的数目称顶点v的入度，记ID(v)；以顶点v为弧尾顶点的弧的数

目称顶点v的出度，记OD(v)；入度与出度之和称顶点v的度.记TD(v),

若图G中有n个顶点，e条边/弧，必有€之

5-003顶点间路径

无向图G=(V,{E})中顶点V和顶点W间的路径为顶点序列Vo,Vl/-,Vn»其中Vo=V为起点，Vn=W为终点，

voJ:VnWV,ei=(Vj.i,Vj)£E,i=l,,,no

有向图G=(V,{A})中从顶点V到顶点W的路径为顶点序列Vo,Vi,…,Vn，其中Vo=V为起点，Vn=W为终点，

V。,…,Vn^V，ai=<Vj.|,Vj>^A,

路径上边/弧的数目称路径长度，，没有重复顶点的路径称简单路径.，起点与终点相同的路径称回路,,

除起点和终点相同外，别无重复顶点的路径称简单回路。

5・004子图

设图G=<V,{VR}>,若有图G=vV：{VR}>,满足▽包含于V,VR包含于VR,则称G为G的子图。

5・005无向图的连通性

无向图中，若两顶点间存在路径，则称两顶点连通。若图中任意两顶点都是连通的，则称该图为连通

图，否则称非连通图，

无向图的极大连通了图称其连通分量，连通图只有•个连通分量，就是它本身，非连通图则有多个连

通分量。

连通图的极小连通子图（含原图中全部顶点）称其生成树。若连通图有n个顶点，则其生成树有n个

顶点，并有且仅有n-1条边，但该图的含n个顶点及n-1条边的子图不一定是其生成树。生成树上任意两

顶点间有且仅有一条路径。

非连通图的各连通分量的生成树构成该图的生成森林。

5-006有向图的连通性

有向图中，任意一对结点间，若两者相互可达，则称该图为强连通图；若至少有一个结点到另一个结

点是可达的，则称该图为单侧连通图，若略去弧的方向（即把该图看作无向图），该图为一连通图，则称

该图为弱连通图，以上三者均不符，则为非连通图。有向图若强连通，则必单侧连通；若单侧连通，则必

弱连通；反之不然。

有向图的极大强连通子图称其强连通分量

只有一个顶点的入度为0,其余顶点的入度均为1的有向图称有向树。一个有向图的生成森林由若干

棵有向树组成，该森林含有图中全部顶点以及足以构成若干棵不相交的有向树的弧。

含n个顶点的有向强连通图至少含n条弧，至多含n（n・l）条弧。

5-101图的邻接矩阵存储结构

设图G含n个顶点，则G的邻接矩阵是记录这些顶点间逻辑关系的n阶方阵，不妨记为A=（aRxn，

1<v.,v.>eVRw<V,,V>eVR

则对（有向/无向）图有：八对（有向/无向）网有：Ujj7

J

[（）<vPvy>^VRoo<>^VR

其中W为权值。

无向图（网）的邻接矩阵是对称阵；有向图（网）的邻接矩阵可以对称，也可以不对称（后者更为常见）。

邻接矩阵存储结构的空间复杂度为0（1?）。

在邻接矩阵存储结构中，添加新顶点V：若顶点数未满，贝1J（1）将顶点V保存在vexs[vexnum]中；（2）

必要时将adjmaxlrix[vexnum][O..vexnum]及adjmaxtrix[O..vexnum][vexnum]清为0或8；（3）vexnum力口1。

在邻接矩阵存储结构中，设顶点V保存在vexs国中，删除顶点V（注意：删除顶点时，依附于该顶点

的边/弧也一并删除）：（1）求依附于该顶点的边数，依此修改arcnum的值；（2）若V不是顶点向量中最后一

个结点，即i!=vexnum-l,贝令vexs[i]=vexs[vexnum-l],并令

adjmaxtrix[i][O..vexnum]=adjmaxtrix[vexnum][O..vexnum],令

adjmaxtrix[O..vexnuml[i]=adjmaxtrix[O..vexnum][vexnumb令adjmaxtrix[i][i]=OB£°°；（3）vexnum减1。

在邻接矩阵存储结构中，设顶点V保存在vexs国中，顶点W保存在vexslj]中，添加边（V,W）/弧

vV,W>（注意：添加边/弧时，要求相关顶点已存储）：（1）对于无向图，则令adjmaxtrix[il[jl=adjmaxtrix[jl[il=l,

并使arcnuni加1；（2）对丁有向图，令adjiiiaxtrix[i]（j]=l,并使arcnuni加1；（3）对丁网,则令相应位置的值

为输入的权值，并使arcnum加1。

在邻接矩阵存储结构中，设顶点V保存在vexs[i]中，顶点W保存在vexsfj]中，删除边（V,W）/弧

<V,W>（注意:删除边/弧时，不删除相关顶点）:⑴对于无向图，则令adjmaxtrix[i][j]=adjmaxtrix皿"=0,

并使arcnum减1；（2）对于有向图,令adjmaxtrix[i][j]=O,并使arcnum减1；（3）对于网，则令相应位置的值

为8,并使arcnum减1。

在邻接矩阵存储结构中，设顶点V保存在vexs[i]中，顶点W保存在vexs[j]中，判断边（V,W）/弧

<V,W>是否存在：（1）对于无向图，若adjmaxtrix[i][j]=l或adjmaxtrix[j][i]=l,则边（V,W）存在，时间

复杂度0（1）;（2）对于有向图，若adjmaxtrix[i皿=1,则弧（V,W）存在，时间复杂度0（1）