严蔚敏数据结构复习整理完整版

1.复杂性分析

对各种操作的时间复杂性的分析。

主要是链表，树，排序等简单一些的分析。

分析的时候，从简单的入手，学会方法。

后续的各种豆可能让你分析时间复杂度。

线性链表（顺序表和单链表）

链表循环链表

双向链表

2.线性结构队列（循环队列）

栈

链表主要操作：找某一个元素，插入一个（在哪个位置增加），删除一个（在哪个位置删除）。栈：查找，插入（位置固定），删除（位置固定）

队列：查找，插入（位置固定），删除（位置固定）

顺序表（可以视为一个数组）

单链表：

（删除）

（插入）

倒置：

（查找）

循环链表

双向链表

栈：

（插入删除查找）

队列

（插入删除查找）

循环队列的实现，并不是像上面的图那样，实现了一个循环的样子。

3.二叉树

基本概念

二叉树是每个节点最多有两个子树的有序树。二叉树常被用于实现二叉查找树和二叉堆。值得注意的是，二叉树不是树的特殊情形。

二叉树是每个结点最多有两个子树的有序树。通常根的子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在出度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。

二叉树不是树的一种特殊情形，尽管其与树有许多相似之处，但树和二叉树有两个主要差别：

1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2；

2. 树的结点无左、右之分，而二叉树的结点有左、右之分。

二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：

(1)空二叉树——如图(a)；

(2)只有一个根结点的二叉树——如图(b)；

(3)只有左子树——如图(c)；

(4)只有右子树——如图(d)；

(5)完全二叉树——如图(e)

注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形

性质

(1) 在非空二叉树中，第i层的结点总数不超过

, i>=1；

(2) 深度为h的二叉树最多有2^h-1个结点(h>=1)，最少有h个结点；

(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；

(4) 具有n个结点的完全二叉树的深度为

(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：

若I为结点编号则如果I>1，则其父结点的编号为I/2；

如果2*I<=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*I>N，则无左儿子；

如果2*I+1<=N，则其右儿子的结点编号为2*I+1；若2*I+1>N，则无右儿子。

(6)给定N个节点，能构成h(N)种不同的二叉树。h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)。

（7）设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i

存储结构

顺序存储表示

二叉树可以用数组或线性表来存储，而且如果这是满二叉树，这种方法不会浪费空间。用这种紧凑排列，如果一个结点的索引为i，它的子结点能在索引2i+1和2i+2找到，并且它的父节点（如果有）能在索引floor((i-1)/2)找到（假设根节点的索引为0）。这种方法更有利于紧凑存储和更好的访问的局部性，特别是在前序遍历中。然而，它需要连续的存储空间，这样在存储高度为h的n个结点组成的一般普通树时将会浪费很多空间。一种最极坏的情况下如果深度为h的二叉树每个节点只有右孩子需要占用2的h次幂减1，而实际却只有h个结点，空间的浪费太大，这是顺序存储结构的一大缺点。

/* 二叉树的顺序存储表示 */

#define MAX_TREE_SIZE 100 /* 二叉树的最大节点数 */

typedef TElemType SqBiTree[MAX_TREE_SIZE]; /* 0号单元存储根节点 */

typedef struct

{

int level,order; /* 节点的层，本层序号(按满二叉树计算) */

}position;

二叉链表存储表示

/* 二叉樹的二叉鏈表存儲表示 */

typedef struct BiTNode

{

TElemType data;

struct BiTNode *lchild,*rchild; /* 左右孩子指針 */

}BiTNode,*BiTree;

遍历算法

二叉树的遍历三种方式，如下：

（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树。简记根-左-右。

（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树。简记左-根-右。

（3）后序遍历（LRD），首先遍历左子树，然后遍历右子树，最后访问根结点。简记左-右-根。

例1：如上图所示的二叉树，若按前序遍历，则其输出序列为。若按中序遍历，则其输出序列为。若按后序遍历，则其输出序列为。

前序：根A，A的左子树B，B的左子树没有，看右子树，为D，所以A-B-D。再来看A的右子树，根C，左子树E，E的左子树F，E的右子树G，G的左子树为H，没有了结束。连起来为C-E-F-G-H,最后结果为ABDCEFGH

中序：先访问根的左子树,B没有左子树，其有右子树D，D无左子树，下面访问树的根A，连起来是BDA。

再访问根的右子树，C的左子树的左子树是F，F的根E，E的右子树有左子树是H，再从H出发找到G，到此C的左子树结束，找到根C，无右子树，结束。连起来是FEHGC, 中序结果连起来是BDAFEHGC

后序：B无左子树，有右子树D，再到根B。再看右子树，最下面的左子树是F，其根的右子树的左子树是H，再到H的根G，再到G的根E，E的根C

无右子树了，直接到C，这时再和B找它们其有的根A，所以连起来是DBFHGECA

深度优先遍历

在深度优先中，我们希望从根结点访问最远的结点。和图的深度优先搜索不同的是，不需记住访问过的每一个结点，因为树中不会有环。

广度优先遍历

和深度优先遍历不同，广度优先遍历会先访问离根节点最近的节点。

完全二叉树，满二叉树

1.满二叉树：一棵深度为k，且有个节

点称之为满二叉树

2.完全二叉树：深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k

的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树

4.树

基本概念

树（tree）是包含n（n>0）个结点的有穷集，其中：

（1）每个元素称为结点（node）；

（2）有一个特定的结点被称为根结点或树根（root）。

（3）除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。

树也可以这样定义：树是由根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或称为树根。

我们可以形式地给出树的递归定义如下:

单个结点是一棵树，树根就是该结点本身。

设T1,T2,..,Tk是树，它们的根结点分别为n1,n2,..,nk。用一个新结点n作为n1,n2,..,nk的父亲，则得到一棵新树，结点n就是新树的根。我们称n1,n2,..,nk为一组兄弟结点，它们都是结点n的子结点。我们还称T1,T2,..,Tk为结点n的子树。

空集合也是树，称为空树。空树中没有结点。

术语

1.节点的度：一个节点含有的子树的个数称为该节点的度；

2.树的度：一棵树中，最大的节点的度称为树的度；

3.叶节点或终端节点：度为零的节点；

4.非终端节点或分支节点：度不为零的节点；

5.父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；

6.孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；

7.兄弟节点：具有相同父节点的节点互称为兄弟节点；

8.节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

9.树的高度或深度：树中节点的最大层次；

10.堂兄弟节点：父节点在同一层的节点互为堂兄弟；

11.节点的祖先：从根到该节点所经分支上的所有节点；

12.子孙：以某节点为根的子树中任一节点都称为该节点的子孙。

13.森林：由m（m>=0）棵互不相交的树的集合称为森林；

存储

父节点表示法

/* 树节点的定义 */#define MAX_TREE_SIZE 100typedef struct{

TElemType data;

int parent; /* 父节点位置域 */} PTNode;typedef struct{

PTNode nodes[MAX_TREE_SIZE];

int n; /* 节点数 */} PTree;

孩子链表表示法

/*树的孩子链表存储表示*/typedef struct CTNode { // 孩子节点

int child;

struct CTNode *next;} *ChildPtr;typedef struct {

ElemType data； // 节点的数据元素

ChildPtr firstchild； // 孩子链表头指针} CTBox;typedef struct { CTBox nodes[MAX_TREE_SIZE]；

int n, r； // 节点数和根节点的位置} CTree;

5.森林

6.森林、树与二叉树的转换

将树转换为二叉树

树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树：

①在所有兄弟结点之间加一连线；

②对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。

注意：

由于树根没有兄弟，故树转化为二叉树后，二叉树的根结点的右子树必为空。

2）将一个森林转换为二叉树

具体方法是：

①将森林中的每棵树变为二叉树

②因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视

为兄弟从左至右连在一起，就形成了一棵二叉树。

二叉树到树、森林的转换

把二叉树转换到树和森林自然的方式是：若结点x是双亲y的左孩子，则把x的右孩子，右孩子的右孩子，…，都与y用连线连起来，最后去掉所有双亲到右孩子的连线。

图

二元组的定义

图G是一个有序二元组(V,E)，其中V称为顶集(Vertices Set)，E称为边集(Edges set)，E与V不相交。它们亦可写成V(G)和E(G)。

E的元素都是二元组，用(x,y)表示，其中x,y∈V。

三元组的定义

图G是指一个三元组(V,E,I)，其中V称为顶集，E称为边集，E与V不相交；I 称为关联函数，I将E中的每一个元素映射到

。如果e被映射到(u,v)，那么称边e连接顶点u,v，而u,v则称作e的端点，u,v此时关于e相邻。同时，若两条边i,j有一个公共顶点u，则称i,j关于u 相邻。

有/无向图

如果给图的每条边规定一个方向，那么得到的图称为有向图。在有向图中，与一个节点相关联的边有出边和入边之分。相反，边没有方向的图称为无向图。

简单图

一个图如果

1.没有两条边，它们所关联的两个点都相同（在有向图中，没有两条边的起点终点都

分别相同）；

2.每条边所关联的是两个不同的顶点

则称为简单图（Simple graph）。简单的有向图和无向图都可以使用以上

的“二元组的定义”，但形如的序对不能属于E。而无向图的边集必须是对称的，即如果

，那么

。

基本术语

阶（Order）：图G中顶集V的大小称作图G的阶。

子图（Sub-Graph）：当图G'=(V',E')其中V‘包含于V，E’包含于E，则G'称作图G=(V,E)的子图。每个图都是本身的子图。

生成子图（Spanning Sub-Graph）：指满足条件V(G') = V(G)的G的子图G。导出子图（Induced Subgraph）：以图G的顶点集V的非空子集V1为顶点集，以两端点均在V1中的全体边为边集的G的子图，称为V1导出的导出子图；以图G的边集E的非空子集E1为边集，以E1中边关联的顶点的全体为顶点集的G 的子图，称为E1导出的导出子图。

度（Degree）：一个顶点的度是指与该顶点相关联的边的条数，顶点v的度记作d(v)。

入度（In-degree）和出度（Out-degree）：对于有向图来说，一个顶点的度可细分为入度和出度。一个顶点的入度是指与其关联的各边之中，以其为终点的边数；出度则是相对的概念，指以该顶点为起点的边数。

自环（Loop）：若一条边的两个顶点为同一顶点，则此边称作自环。

路径（Path）：从u到v的一条路径是指一个序列v0,e1,v1,e2,v2,...ek,vk，其中ei的顶点为vi及vi - 1，k称作路径的长度。如果它的起止顶点相同，该路径是“闭”的，反之，则称为“开”的。一条路径称为一简单路径(simple path)，如果路径中除起始与终止顶点可以重合外，所有顶点两两不等。

行迹（Trace）：如果路径P(u,v)中的边各不相同，则该路径称为u到v的一条行迹。

轨道（Track）：如果路径P(u,v)中的顶点各不相同，则该路径称为u到v的一条轨道。

闭的行迹称作回路（Circuit），闭的轨称作圈（Cycle）。

（另一种定义是：walk对应上述的path，path对应上述的track。Trail对应trace。）

桥（Bridge）：若去掉一条边，便会使得整个图不连通，该边称为桥。

图的存储表示

1.数组（邻接矩阵）存储表示（有向或无向）

2.邻接表存储表示

邻接表是图的一种链式存储结构。

邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点V i的边（对有向图是以顶点V i为尾的弧）。

邻接表中的表结点和头结点结构：

有向图的邻接表和逆邻接表

（一）在有向图的邻接表中，第i个单链表链接的边都是顶点i发出的边。（二）为了求第i个顶点的入度，需要遍历整个邻接表。因此可以建立逆邻接表。（三）在有向图的逆邻接表中，第i个单链表链接的边都是进入顶点i的边。

邻接表小结

◆设图中有n个顶点，e条边，则用邻接表表示无向图时，需要n个顶点结点，2e个表结点；用邻接表表示有向图时，若不考虑逆邻接表，只需n个顶点结点，e个边结点。

◆在无向图的邻接表中，顶点v i的度恰为第i个链表中的结点数。

◆在有向图中，第i个链表中的结点个数只是顶点v i的出度。在逆邻接表中的第i个链表中的结点个数为v i的入度。

◆建立邻接表的时间复杂度为O(n+e)。

3.有向图的十字链表存储表示

十字链表表示特点

1.针对弧结点，增加入弧链表结构和出弧链表结构；

2.容易求得任意顶点的出度和入度，专用于有向图的操作；

3.结构实现比较复杂。

4.无向图的邻接多重表存储表示

邻接多重表(Adjacency Multilist)主要用于存储无向图。因为，如果用邻接表存储无向图，每条边的两个边结点分别在以该边所依附的两个顶点为头结点的链表中，这给图的某些操作带来不便。例如，对已访问过的边做标记，或者要删除图中某一条边等，都需要找到表示同一条边的两个结点。因此，在进行这一类操作的无向图的问题中采用邻接多重表作存储结构更为适宜。

邻接多重表的存储结构和十字链表类似，也是由顶点表和边表组成，每一条边用一个结点表示，其顶点表结点结构和边表结点结构如图

其中，顶点表由两个域组成，vertex 域存储和该顶点相关的信息firstedge 域指示第一条依附于该顶点的边；边表结点由六个域组成，mark 为标记域，可用以标记该条边是否被搜索过；ivex 和jvex 为该边依附的两个顶点在图中的位置；ilink 指向下一条依附于顶点ivex的边;jlink 指向下一条依附于顶点jvex 的边，info 为指向和边相关的各种信息的指针域。

一个不带权图中若两点不相邻，邻接矩阵相应位置为0，对带权图(网)，相应位置为∞。一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一。在邻接表中，对图中每个顶点建立一个单链表（并按建立的次序编号），第i个单链表中的结点表示依附于顶点vi的边（对于有向图是以顶点vi为尾的弧）。每个结点由两个域组成：邻接点域(adjvex)，用以指示与vi邻接的点在图中的位置，链域(nextarc)用以指向依附于顶点vi的下一条边所对应的结点。如果用邻接表存放网（带权图）的信息，则还需要在结点中增加一个存放权值的域（info）。每个顶点的单链表中结点的个数即为该顶点的出度(与该顶点连接的边的总数)。无论是存储图或网，都需要在每个单链表前设一表头结点，这些表头结点的第一个域data用于存放结点vi的编号i，第二个域firstarc用于指向链表中第一个结点。

在上面两个图结构中，一个是有向图，即每条边都有方向，另一个是无向图，即每条边都没有方向。

本文来源：https://www.bwwdw.com/article/3z4e.html