目录

写在前面

一、为什么要进行数据仓库建模？

二、四种常见模型

2.1 维度模型

2.1.1 星型模型

2.1.2 雪花模型

2.1.3 星座模型

2.2 范式模型

2.3 Data Vault模型

2.4 Anchor模型

三 数据模型的评价标准

小编有话

---

写在前面

大数据时代，维度建模已成为各大厂的主流方式。

维度建模从分析决策的需求出发构建模型，为分析需求服务。重点关注用户如何快速的完成数据分析，可以直观的反应业务模型中的业务问题，需要大量的数据预处理、数据冗余，有较好的大规模复杂查询的响应性能。

系列文章详见「数仓系列文章- 传送门」

一、为什么要进行数据仓库建模？

• 性能：良好的模型能帮我们快速查询需要的数据，减少数据的IO吞吐
• 成本：减少数据冗余、计算结果复用、从而降低存储和计算成本
• 效率：改善用户使用数据的体验，提高使用数据的效率
• 改善统计口径的不一致性，减少数据计算错误的可能性

二、四种常见模型

2.1 维度模型

维度建模按数据组织类型划分可分为星型模型、雪花模型、星座模型。

Kimball老爷爷维度建模四个步骤：

选择业务处理过程 > 定义粒度 > 选择维度 > 确定事实

2.1.1 星型模型

星型模型主要是维表和事实表，以事实表为中心，所有维度直接关联在事实表上，呈星型分布。

2.1.2 雪花模型

雪花模型，在星型模型的基础上，维度表上又关联了其他维度表。这种模型维护成本高，性能方面也较差，所以一般不建议使用。尤其是基于hadoop体系构建数仓，减少join就是减少shuffle，性能差距会很大。

星型模型可以理解为，一个事实表关联多个维度表，雪花模型可以理解为一个事实表关联多个维度表，维度表再关联维度表。

2.1.3 星座模型

星座模型，是对星型模型的扩展延伸，多张事实表共享维度表。

星座模型是很多数据仓库的常态，因为很多数据仓库都是多个事实表的。所以星座模型只反映是否有多个事实表，他们之间是否共享一些维度表。

2.2 范式模型

即实体关系（ER）模型，数据仓库之父Immon提出的，从全企业的高度设计一个3NF模型，用实体加关系描述的数据模型描述企业业务架构，在范式理论上符合3NF。此建模方法，对建模人员的能力要求非常高。

特点：设计思路自上而下，适合上游基础数据存储，同一份数据只存储一份，没有数据冗余，方便解耦，易维护，缺点是开发周期一般比较长，维护成本高。

详见：一篇文章搞懂数据仓库：三范式与反范式_不吃西红柿-CSDN博客_数据仓库三范式

2.3 Data Vault模型

DataVault由Hub（关键核心业务实体）、Link（关系）、Satellite（实体属性） 三部分组成 ，是Dan Linstedt发起创建的一种模型方法论，它是在ER关系模型上的衍生，同时设计的出发点也是为了实现数据的整合，并非为数据决策分析直接使用。

2.4 Anchor模型

高度可扩展的模型，所有的扩展只是添加而不是修改，因此它将模型规范到6NF，基本变成了K-V结构模型。企业很少使用。

三 数据模型的评价标准

数据模型建设的怎么样，极度依赖规范设计，如果代码风格是“千人千面”，那么恐怕半年下来，业务系统就没法看了。没有什么比“数据系统”更看重“法制”了，规范体系不仅能保障数据建设的一致性，也能够应对业务交接的情况，更能够为自动化奠定基础。

1. 业务过程清晰：ODS就是原始信息，不修改；DWD面向基础业务过程；DIM描述维度信息；DWS针对最小场景做指标计算；ADS也要分层，面向跨域的建设，和面向应用的建设；
2. 指标可理解：按照一定业务事务过程进行业务划分，明细层粒度明确、历史数据可获取，汇总层维度和指标同名同义，能客观反映业务不同角度下的量化程度；
3. 核心模型相对稳定：如果业务过程运行的比较久，过程相对固定，就要尽快下沉到公共层，形成可复用的核心模型；
4. 高内聚低耦合：各主题内数据模型要业务高内聚，避免在一个模型耦合其他业务的指标，造成该模型主题不清晰和性价比低。

小编有话

• 在传统企业数仓中，业务相对稳定，以范式建模为主。 如电信、金融行业等
• 在互联网公司，业务变化快，需求来来回回的改，计算和存储也不是问题，我们更关心快速便捷的响应业务需求，所以以维度建模为主流。

数仓系列传送门：https://blog.csdn.net/weixin_39032019/category_8871528.html

友情链接：数据结构专栏

图

【知识框架】

图的基本概念

在线性表中，数据元素之间是被串起来的，仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继。在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关。图是一种较线性表和树更加复杂的数据结构。在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。

一、图的定义

图(Graph)是由顶点的有穷非空集合$V(G)$和顶点之间边的集合$E(G)$组成，通常表示为: $G=(V,E)$，其中，$G$表示个图，$V$是图$G$中顶点的集合，$E$是图$G$中边的集合。若 V = { v 1 , v 2 , . . . , v n } V= \{v_1, v_2,...,v_n\} V={v1​,v2​,...,vn​}，则用$|V|$表示图$G$中顶点的个数，也称图$G$的阶， E = { ( u , v ) ∣ u ∈ V , v ∈ V } E= \{(u, v) |u∈V, v∈V\} E={(u,v)∣u∈V,v∈V}，用$|E|$表示图$G$中边的条数。

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

二、图的基本概念和术语

1、有向图

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

图(a)所示的有向图$G_1$可表示为$$G_1=(V_1,E_1)$$ V 1 = { 1 , 2 , 3 } V_1=\{1,2,3\} V1​={1,2,3} E 1 = { < 1 , 2 > , < 2 , 1 > , < 2 , 3 > } E_1=\{<1,2>,<2,1>,<2,3>\} E1​={<1,2>,<2,1>,<2,3>}

2、无向图

若E是无向边(简称边)的有限集合时，则图G为无向图。边是顶点的无序对，记为(v, w)或(w,v),因为(v,w)=(w,v), 其中v,w是顶点。可以说顶点w和顶点v互为邻接点。边(v, w)依附于顶点w和v，或者说边(v, w)和顶点v, w相关联。

图(b)所示的无向图G2可表示为$$G_2=(V_2,E_2)$$ V 2 = { 1 , 2 , 3 , 4 } V_2=\{1,2,3,4\} V2​={1,2,3,4} E 2 = { ( 1 , 2 ) , ( 1 , 3 ) , ( 1 , 4 ) , ( 2 , 3 ) , ( 2 , 4 ) , ( 3 , 4 ) } E_2=\{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)\} E2​={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}

3、简单图

一个图$G$若满足:①不存在重复边;②不存在顶点到自身的边，则称图$G$为简单图。上图中$G_1$和$G_2$均为简单图。数据结构中仅讨论简单图。

4、多重图

若图$G$中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则$G$为多重图。多重图的定义和简单图是相对的。

5、完全图（也称简单完全图）

对于无向图，$|E|$的取值范围是$0$到$n(n-1)/2$，有$n(n-1)/2$条边的无向图称为完全图，在完全图中任意两个顶点之间都存在边。对于有向图，$|E|$的取值范围是$0$到$n(n-1)$，有$n(n-1)$条弧的有向图称为有向完全图，在有向完全图中任意两个顶点之间都存在方向相反的两条弧。上图中$G_2$为无向完全图，而$G_3$为有向完全图。

6、子图

设有两个图$G=(V,E)$和$G^{\prime }=(V^{\prime },E^{\prime })$， 若$V^{\prime }$是$V$的子集，且$E^{\prime }$是$E$的子集，则称$G^{\prime }$是$G$的子图。若有满足$V(G^{\prime })=V(G)$的子图$G^{\prime }$，则称其为$G$的生成子图。上图中$G_3$为$G_1$的子图。

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

7、连通、连通图和连通分量

在无向图中，若从顶点$v$到顶点$w$有路径存在，则称$v$和$w$是连通的。若图$G$中任意两个顶点都是连通的，则称图$G$为连通图，否则称为非连通图。无向图中的极大连通子图称为连通分量。若一个图有$n$个顶点，并且边数小于$n-1$，则此图必是非连通图。如下图(a)所示， 图$G_4$有3个连通分量，如图（b）所示。

注意:弄清连通、连通图、连通分量的概念非常重要。首先要区分极大连通子图和极小连通子图，极大连通子图是无向图的连通分量，极大即要求该连通子图包含其所有的边;极小连通子图是既要保持图连通又要使得边数最少的子图。

8、强连通图、强连通分量

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

注意:强连通图、强连通分量只是针对有向图而言的。一般在无向图中讨论连通性，在有向图中考虑强连通性。

9、生成树、生成森林

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

注意:包含无向图中全部顶点的极小连通子图，只有生成树满足条件，因为砍去生成树的任一条边，图将不再连通。

10、顶点的度、入度和出度

图中每个顶点的度定义为以该项点为一个端点的边的数目。
对于无向图，顶点v的度是指依附于该顶点的边的条数，记为$TD(v)$。
在具有$n$个顶点、$e$条边的无向图中，$\sum _{i=1}^{n}TD(v_i)=2e$，即无向图的全部顶点的度的和等于边数的2倍，因为每条边和两个顶点相关联。
对于有向图,顶点$v$的度分为入度和出度,入度是以顶点$v$为终点的有向边的数目，记为$ID(v)$; 而出度是以顶点$v$为起点的有向边的数目，记为$OD(v)$。顶点$v$的度等于其入度和出度之和，即$TD(v)=ID(v)+OD(v)。$
在具有$n$个顶点、$e$条边的有向图中，$\sum _{i=1}^{n}ID(v_i)=\sum _{i=1}^{n}OD(v_i)=e$，即有向图的全部顶点的入度之和与出度之和相等，并且等于边数。这是因为每条有向边都有一个起点和终点。

11、边的权和网

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

12、稠密图、稀疏图

边数很少的图称为稀疏图，反之称为稠密图。稀疏和稠密本身是模糊的概念，稀疏图和稠密图常常是相对而言的。一般当图G满足$|E|<|V|log|V|$时，可以将$G$视为稀疏图。

13、路径、路径长度和回路

顶点$v_p$到顶点$v_q$之间的一条路径是指顶点序列$v_p,v_{i_1},v_{i_2},...,v_{i_m},v_q$，当然关联的边也可以理解为路径的构成要素。路径上边的数目称为路径长度。第一个顶点和最后一个顶点相同的路径称为回路或环。若一个图有$n$个顶点，并且有大于$n-1$条边，则此图一定有环。

14、 简单路径、简单回路

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

15、距离

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

16、有向树

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

图的存储结构

由于图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在内存中的物理位置来表示元素之间的关系，也就是说，图不可能用简单的顺序存储结构来表示。而多重链表的方式，要么会造成很多存储单元的浪费，要么又带来操作的不便。因此，对于图来说，如何对它实现物理存储是个难题，接下来我们介绍五种不同的存储结构。

一、邻接矩阵

图的邻接矩阵(Adjacency Matrix) 存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。
设图$G$有$n$个顶点，则邻接矩阵$A$是一个$n\ast n$的方阵，定义为:

下图是一个无向图和它的邻接矩阵：

可以看出:

1. 无向图的邻接矩阵一定是一个对称矩阵(即从矩阵的左上角到右下角的主对角线为轴，右上角的元与左下角相对应的元全都是相等的)。 因此，在实际存储邻接矩阵时只需存储上(或下)三角矩阵的元素。
2. 对于无向图，邻接矩阵的第$i$行(或第$i$列)非零元素(或非$\infty$元素)的个数正好是第$i$个顶点的度$TD(v_i)$。比如顶点$v_1$的度就是$1+0+1+0=2$。
3. 求顶点$v_i$的所有邻接点就是将矩阵中第i行元素扫描一遍， $A[i][j]$为 1就是邻接点。

---

下图是有向图和它的邻接矩阵：

可以看出:

1. 主对角线上数值依然为0。但因为是有向图，所以此矩阵并不对称。
2. 有向图讲究入度与出度，顶点$v_1$的入度为1,正好是第$v_1$列各数之和。顶点$v_1$的出度为2，即第$v_1$行的各数之和。
3. 与无向图同样的办法，判断顶点$v_i$到$v_j$是否存在弧，只需要查找矩阵中$A[i][j]$ 是否为1即可。

---

对于带权图而言,若顶点$v_i$和$v_j$之间有边相连，则邻接矩阵中对应项存放着该边对应的权值

下图是有向网图和它的邻接矩阵：

---

通过以上对无向图、有向图和网的描述，可定义出邻接矩阵的存储结构：

#define MaxVertexNum 100	//顶点数目的最大值
typedef char VertexType;	//顶点的数据类型
typedef int EdgeType;	//带权图中边上权值的数据类型
typedef struct{
	VertexType Vex[MaxVertexNum];	//顶点表
	EdgeType Edge[MaxVertexNum][MaxVertexNum];	//邻接矩阵，边表
	int vexnum, arcnum;	//图的当前顶点数和弧树
}MGraph;

---

注意:
①在简单应用中，可直接用二维数组作为图的邻接矩阵(顶点信息等均可省略)。
②当邻接矩阵中的元素仅表示相应的边是否存在时，EdgeType可定义为值为0和1的枚举类型。
③无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可采用压缩存储。
④邻接矩阵表示法的空间复杂度为$O(n^2)$， 其中n为图的顶点数$|V|$。
⑤ 用邻接矩阵法存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。
⑥ 稠密图适合使用邻接矩阵的存储表示。

二、邻接表

当一个图为稀疏图时（边数相对顶点较少），使用邻接矩阵法显然要浪费大量的存储空间，如下图所示：

而图的邻接表法结合了顺序存储和链式存储方法，大大减少了这种不必要的浪费。
所谓邻接表，是指对图$G$中的每个顶点$v_i$建立一个单链表，第$i$个单链表中的结点表示依附于顶点$v_i$ 的边(对于有向图则是以顶点$v_i$为尾的弧)，这个单链表就称为顶点$v_i$的边表(对于有向图则称为出边表)。边表的头指针和顶点的数据信息采用顺序存储(称为顶点表)，所以在邻接表中存在两种结点:顶点表结点和边表结点，如下图所示。

顶点表结点由顶点域(data)和指向第一条邻接边的指针(firstarc) 构成，边表(邻接表)结点由邻接点域(adjvex)和指向下一条邻接边的指针域(nextarc) 构成。
无向图的邻接表的实例如下图所示。

有向图的邻接表的实例如下图所示。

此时我们很容易就可以算出某个顶点的入度或出度是多少，判断两顶点是否存在弧也很容易实现。
对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可。

图的邻接表存储结构定义如下：

#define MAXVEX 100	//图中顶点数目的最大值
type char VertexType;	//顶点类型应由用户定义
typedef int EdgeType;	//边上的权值类型应由用户定义
/*边表结点*/
typedef struct EdgeNode{
	int adjvex;	//该弧所指向的顶点的下标或者位置
	EdgeType weight;	//权值，对于非网图可以不需要
	struct EdgeNode *next;	//指向下一个邻接点
}EdgeNode;

/*顶点表结点*/
typedef struct VertexNode{
	Vertex data;	//顶点域，存储顶点信息
	EdgeNode *firstedge	//边表头指针
}VertexNode, AdjList[MAXVEX];

/*邻接表*/
typedef struct{
	AdjList adjList;
	int numVertexes, numEdges;	//图中当前顶点数和边数
}

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

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

三、十字链表

十字链表是有向图的一种链式存储结构。
对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才能知道，反之，逆邻接表解决了入度却不了解出度的情况。有没有可能把邻接表与逆邻接表结合起来呢?答案是肯定的，就是把它们整合在一起。这就是我们现在要介绍的有向图的一种存储方法：十字链表(Orthogonal List)。
我们重新定义顶点表结点结构如下表所示。

其中firstin表示入边表头指针，指向该顶点的入边表中第一个结点，firstout 表示出边表头指针，指向该顶点的出边表中的第一个结点。
重新定义的边表结点结构如下表所示。

其中tailvex 是指弧起点在顶点表的下标，headvex 是指弧终点在顶点表中的下标，headlink是指入边表指针域，指向终点相同的下一条边，taillink是指边表指针域，指向起点相同的下一条边。如果是网，还可以再增加一个weight域来存储权值。

接下来通过一个例子详细介绍十字链表的结构。
如下图所示，顶点依然是存入一个一维数组 { V 0 , V 1 , V 2 , V 3 } \{V_0,V_1,V_2,V_3\} {V0​,V1​,V2​,V3​}，实线箭头指针的图示完全与的邻接表的结构相同。就以顶点$V_0$来说，firstout 指向的是出边表中的第一个结点$V_3$。所以$V_0$边表结点的$headvex=3$，而tailvex就是当前顶点$V_0$的下标0，由于$V_0$只有一个出边顶点，所以headlink和taillink都是空。

我们重点需要来解释虚线箭头的含义，它其实就是此图的逆邻接表的表示。对于$V_0$来说，它有两个顶点$V_1$和$V_2$的入边。因此$V_0$的firstin指向顶点$V_1$的边表结点中headvex为0的结点，如上图右图中的①。接着由入边结点的headlink指向下一个入边顶点$V_2$，如图中的②。对于顶点$V_1$,它有一个入边顶点$V_2$，所以它的firstin指向顶点$V_2$的边表结点中headvex为1的结点，如图中的③。顶点$V_2$和$V_3$也是同样有一个入边顶点，如图中④和⑤。

十字链表的好处就是因为把邻接表和逆邻接表整合在了一起， 这样既容易找到以$V_1$为尾的弧，也容易找到以$V_1$为头的弧，因而容易求得顶点的出度和入度。而且它除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同的，因此，在有向图的应用中，十字链表是非常好的数据结构模型。

四、邻接多重表

邻接多重表是无向图的另一种链式存储结构。
在邻接表中，容易求得顶点和边的各种信息，但在邻接表中求两个顶点之间是否存在边而对边执行删除等操作时，需要分别在两个顶点的边表中遍历，效率较低。比如下图中，若要删除左图的$(V_0,V_2)$ 这条边，需要对邻接表结构中右边表的阴影两个结点进行删除操作，显然这是比较烦琐的。

重新定义的边表结点结构如下表所示。

其中ivex和jvex是与某条边依附的两个顶点在顶点表中下标。ilink 指向依附顶点ivex的下一条边，jlink 指向依附顶点jvex的下一条边。这就是邻接多重表结构。

每个顶点也用一一个结点表示，它由如下所示的两个域组成。

其中，data 域存储该顶点的相关信息，firstedge 域指示第一条依附于该顶点的边。

我们来看结构示意图的绘制过程，理解了它是如何连线的，也就理解邻接多重表构造原理了。如下图7所示，左图告诉我们它有4个顶点和5条边，显然，我们就应该先将4个顶点和5条边的边表结点画出来。

我们开始连线，如图，首先连线的①②③④就是将顶点的firstedge指向一条边，顶点下标要与ivex的值相同,这很好理解。接着，由于顶点$V_0$的$(V_0,V_1)$ 边的邻边有$(V_0,V_3)$ 和$(V_0,V_2)$。 因此⑤⑥的连线就是满足指向下一条依附于顶点$V_0$的边的目标，注意ilink指向的结点的jvex一定要和它本身的ivex的值相同。同样的道理，连线⑦就是指$(V_1,V_0)$ 这条边，它是相当于顶点$V_1$指向$(V_1,V_2)$ 边后的下一条。$V_2$有三条边依附，所以在③之后就有了⑧⑨。连线④的就是顶点$V_3$在连线④之后的下一条边。 左图一共有5条边，所以右图有10条连线，完全符合预期。

---

到这里，可以明显的看出，邻接多重表与邻接表的差别，仅仅是在于同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。 这样对边的操作就方便多了，若要删除左图的$(V_0,V_2)$ 这条边，只需要将右图的⑥⑨的链接指向改为NULL即可。

五、边集数组

边集数组是由两个一维数组构成。一个是存储顶点的信息;另一个是存储边的信息，这个边数组每个数据元素由一条边的起点下标(begin)、 终点下标(end)和权(weight)组成，如下图所示。显然边集数组关注的是边的集合，在边集数组中要查找一个顶点的度需要扫描整个边数组，效率并不高。因此它更适合对边依次进行处理的操作，而不适合对顶点相关的操作。

图的遍历

图的遍历是和树的遍历类似，我们希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次， 这一过程就叫做图的遍历(Traversing Graph)。
对于图的遍历来，通常有两种遍历次序方案:它们是深度优先遍历和广度优先遍历。

一、深度优先遍历

深度优先遍历(Depth First Search)，也有称为深度优先搜索，简称为DFS。

1、DFS算法

深度优先搜索类似于树的先序遍历。如其名称中所暗含的意思一样，这种搜索算法所遵循的搜索策略是尽可能“深”地搜索一个图。它的基本思想如下:首先访问图中某一起始顶点v，然后由v出发，访问与v邻接且未被访问的任一顶点$w_1$，再访问与$w_1$邻接且未被访问的任一顶点…重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。
般情况下，其递归形式的算法十分简洁，算法过程如下:

bool visited[MAX_VERTEX_NUM];	//访问标记数组
/*从顶点出发，深度优先遍历图G*/
void DFS(Graph G, int v){
	int w;
	visit(v);	//访问顶点
	visited[v] = TRUE;	//设已访问标记
	//FirstNeighbor(G,v):求图G中顶点v的第一个邻接点，若有则返回顶点号，否则返回-1。
	//NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点，返回除w外顶点v
	for(w = FirstNeighbor(G, v); w>=0; w=NextNeighor(G, v, w)){
		if(!visited[w]){	//w为u的尚未访问的邻接顶点
			DFS(G, w);
		}
	}
}
/*对图进行深度优先遍历*/
void DFSTraverse(MGraph G){
	int v; 
	for(v=0; v<G.vexnum; ++v){
		visited[v] = FALSE;	//初始化已访问标记数据
	}
	for(v=0; v<G.vexnum; ++v){	//从v=0开始遍历
		if(!visited[v]){
			DFS(G, v);
		}
	}
}

以下面这个无向图为例

其深度优先遍历的结果为$abdehcfg$

2、DFS算法的性能分析

DFS算法是一个递归算法，需要借助一个递归工作栈，故其空间复杂度为$O(V)$。
对于n个顶点e条边的图来说，邻接矩阵由于是二维数组，要查找每个顶点的邻接点需要访问矩阵中的所有元素，因此都需要$O(V^2)$的时间。而邻接表做存储结构时，找邻接点所需的时间取决于顶点和边的数量，所以是$O(V+E)$。 显然对于点多边少的稀疏图来说，邻接表结构使得算法在时间效率上大大提高。
对于有向图而言，由于它只是对通道存在可行或不可行，算法上没有变化，是完全可以通用的。

3、深度优先的生成树和生成森林

深度优先搜索会产生一棵深度优先生成树。 当然，这是有条件的，即对连通图调用DFS才能产生深度优先生成树，否则产生的将是深度优先生成森林，如下图所示。基于邻接表存储的深度优先生成树是不唯一的 。

二、广度优先遍历

广度优先遍历(Breadth First Search)，又称为广度优先搜索，简称BFS。

1、BFS算法

如果说图的深度优先遍历类似树的前序遍历，那么图的广度优先遍历就类似于树的层序遍历了。
广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况，因此它不是一个递归的算法。为了实现逐层的访问，算法必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点。
以下是广度优先遍历的代码：

/*邻接矩阵的广度遍历算法*/
void BFSTraverse(MGraph G){
	int i, j;
	Queue Q;
	for(i = 0; i<G,numVertexes; i++){
		visited[i] = FALSE;
	}
	InitQueue(&Q);	//初始化一辅助用的队列
	for(i=0; i<G.numVertexes; i++){
		//若是未访问过就处理
		if(!visited[i]){
			vivited[i] = TRUE;	//设置当前访问过
			visit(i);	//访问顶点
			EnQueue(&Q, i);	//将此顶点入队列
			//若当前队列不为空
			while(!QueueEmpty(Q)){
				DeQueue(&Q, &i);	//顶点i出队列
				//FirstNeighbor(G,v):求图G中顶点v的第一个邻接点，若有则返回顶点号，否则返回-1。
				//NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点，返回除w外顶点v
				for(j=FirstNeighbor(G, i); j>=0; j=NextNeighbor(G, i, j)){
					//检验i的所有邻接点
					if(!visited[j]){
						visit(j);	//访问顶点j
						visited[j] = TRUE;	//访问标记
						EnQueue(Q, j);	//顶点j入队列
					}
				}
			}
		}
	}
}

以下面这个无向图为例

其广度优先遍历的结果为$abcdefgh$。

2、BFS算法性能分析

无论是邻接表还是邻接矩阵的存储方式，BFS 算法都需要借助一个辅助队列Q, n个顶点均需入队一次，在最坏的情况下，空间复杂度为$O(V)$。
采用邻接表存储方式时，每个顶点均需搜索一次(或入队一次)， 在搜索任一顶点的邻接点时，每条边至少访问一次，算法总的时间复杂度为$O(V+E)$。采用邻接矩阵存储方式时，查找每个顶点的邻接点所需的时间为$O(V)$，故算法总的时间复杂度为$O(V^2)$。

注意：图的邻接矩阵表示是唯一的，但对于邻接表来说，若边的输入次序不同，生成的邻接表也不同。因此，对于同样一个图，基于邻接矩阵的遍历所得到的DFS序列和BFS序列是唯一的，基于邻接表的遍历所得到的DFS序列和BFS序列是不唯一的。

三、图的遍历与图的连通性

图的遍历算法可以用来判断图的连通性。
对于无向图来说，若无向图是连通的，则从任一结点出发， 仅需一次遍历就能够访问图中的所有顶点；若无向图是非连通的，则从某一个顶点出发，一次遍历只能访问到该顶点所在连通分量的所有顶点，而对于图中其他连通分量的顶点，则无法通过这次遍历访问。对于有向图来说，若从初始点到图中的每个顶点都有路径，则能够访问到图中的所有顶点，否则不能访问到所有顶点。
故在BFSTraverse ()或DFSTraverse ()中添加了第二个for循环，再选取初始点，继续进行遍历，以防止一次无法遍历图的所有顶点。对于无向图，上述两个函数调用BFS (G,i)或DFS(G,i)的次数等于该图的连通分量数；而对于有向图则不是这样，因为一个连通的有向图分为强连通的和非强连通的，它的连通子图也分为强连通分量和非强连通分量，非强连通分量一次调用BFS (G, i)或DFS (G, i)无法访问到该连通分量的所有顶点。
如下图所示为有向图的非强连通分量。

最小生成树

一个连通图的生成树是一个极小的连通子图，它含有图中全部的顶点，但只有足以构成一棵树的$n-1$条边，若砍去它的一条边，则会使生成树变成非连通图；若给它增加一条边，则会形成图中的一条回路。对于一个带权连通无向图$G=(V,E)$，生成树不同，其中边的权值之和最小的那棵生成树（构造连通网的最小代价生成树），称为G的最小生成树(Minimum-Spanning-Tree, MST)。

构造最小生成树有多种算法，但大多数算法都利用了最小生成树的下列性质：假设$G=(V,E)$是一个带权连通无向图，$U$是顶点集$V$的一个非空子集。若$(u,v)$是一条具有最小权值的边，其中$u\in U,v\in V-U$，则必存在一棵包含边$(u,v)$的最小生成树。
基于该性质的最小生成树算法主要有Prim算法和Kruskal算法，它们都基于贪心算法的策略。
下面介绍一个通用的最小生成树算法：

GENERIC_MST(G){
	T=NULL;
	while T 未形成一棵生成树;
		do 找到一条最小代价边(u, v)并且加入T后不会产生回路;
			T=T U (u, v);
}

通用算法每次加入一条边以逐渐形成一棵生成树，下面介绍两种实现上述通用算法的途径。

一、普里姆（Prim）算法

Prim算法构造最小生成树的过程如下图所示。初始时从图中任取一顶点(如顶点加入树T，此时树中只含有一个顶点，之后选择一个与当前T中顶点集合距离最近的顶点，并将该顶点和相应的边加入T，每次操作后T中的顶点数和边数都增1。以此类推，直至图中所有的顶点都并入T，得到的T就是最小生成树。此时T中必然有n-1条边。
通俗点说就是：从一个顶点出发，在保证不形成回路的前提下，每找到并添加一条最短的边，就把当前形成的连通分量当做一个整体或者一个点看待，然后重复“找最短的边并添加”的操作。

Prim算法的步骤如下：
假设 G = { V , E } G= \{V, E\} G={V,E}是连通图，其最小生成树$T=(U,E_T)$，$E_T$是最小生成树中边的集合。
初始化：向空树$T=(U,E_T)$中添加图$G=(V,E)$的任一顶点$u_0$，使 U = { u 0 } U=\{u_0\} U={u0​}，$E_T=NULL$。
循环(重复下列操作直至$U=V$)：从图$G$中选择满足 { ( u , v ) ∣ u ∈ U , v ∈ V − U } \{(u, v)|u∈U, v∈V-U\} {(u,v)∣u∈U,v∈V−U}且具有最小权值的边$(u,v)$,加入树$T$，置 U = U ∪ { v } U=U∪\{v\} U=U∪{v}， E T = E T U { ( u , v ) } E_T= E_TU\{(u, v)\} ET​=ET​U{(u,v)}。

额，不得不说这样理解起来有点抽象，为了能描述这个算法，我们先构造一个邻接矩阵，如下图的右图所示。

于是普里姆(Prim) 算法代码如下，左侧数字为行号。其中INFINITY为权值极大值，不妨设65535，MAXVEX 为顶点个数最大值，此处大于等于9即可。

/*Prim算法生成最小生成树*/
void MiniSpanTree_Prim(G){
	int min, i, j, k;
	int adjvex[MAXVEX];	//保存相关顶点下标
	int lowcost[MAXVEX];	//保存相关顶点间边的权值
	lowcost[0] = 0;	//初始化第一个权值为0，即v0加入生成树
	//lowcost的值为0，在这里就是此下标的顶点已经加入生成树
	adjvex[0] = 0;	//初始化第一个顶点下标为0
	for(i=1; i<G.numVertexes; i++){
		lowcost[i] = G.arc[0][i];	//将v0顶点与之组成边的权值存入数组
		adjvex[i] = 0;	//初始化都为v0的下标
	}
	for(i=1; i<G.numVertexes; i++){
		min = INFINITY;	//初始化最下权值为∞，通常设置一个不可能的很大的数字
		j = 1; k = 0;
		//循环全部顶点
		while(j < G.numVertexes){
			//如果权值不为0且权值小于min
			if(lowcost[j] != 0 && lowcost[j] < min){
				min = lowcost[j];	//则让当前权值成为最小值
				k = j;	//将当前最小值的下标存入k
			}
			j++;
		}
		print("(%d, %d)", adjvex[k], k);	//打印当前顶点边中权值的最小边
		for(j=1; j<G.numvertexes; j++){
			//若下标为k顶点各边权值小于此前这些顶点未被加入生成树权值
			if(lowcost[j] != 0 && G.arc[k][j] < lowcost[j]){
				lowcost[j] = G.arc[k][j];	//将较小权值存入lowcost
				adjvex[j] = k;	//将下标为k的顶点存入adjvex
			}
		}
	}
}

由算法代码中的循环嵌套可得知此算法的时间复杂度为$O(n^2)$。

二、克鲁斯卡尔（Kruskal）算法

与Prim算法从顶点开始扩展最小生成树不同，Kruskal 算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。

Kruskal算法构造最小生成树的过程如下图所示。初始时为只有n个顶点而无边的非连通图$T=V,$，每个顶点自成一个连通分量，然后按照边的权值由小到大的顺序，不断选取当前未被选取过且权值最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入$T$，否则舍弃此边而选择下一条权值最小的边。以此类推，直至$T$中所有顶点都在一个连通分量上。

算法思路：
我们可以直接就以边为目标去构建，因为权值是在边上，直接去找最小权值的边来构建生成树也是很自然的想法，只不过构建时要考虑是否会形成环路而已。此时我们就用到了图的存储结构中的边集数组结构。以下是edge边集数组结构的定义代码：

/*对边集数组Edge结构的定义*/
typedef struct{
	int begin;
	int end;
	int weight;
}Edge;

我们将下面左图的邻接矩阵通过程序转化为右图的边集数组，并且对它们按权值从小到大排序。

于是Kruskal算法代码如下，左侧数字为行号。其中MAXEDGE为边数量的极大值，此处大于等于15即可，MAXVEX为顶点个数最大值，此处大于等于9即可。

/*Kruskar算法生成最小生成树*/
void MiniSpanTree_Kruskal(MGraph G){
	int i, n, m;
	Edge edges[MAXEDGE];	//定义边集数组
	int parent[MAXVEX];	//定义一数组用来判断边与边是否形成环路
	/*此处省略将邻接矩阵G转化为边集数组edges并按照权由小到大排序的代码*/
	for(i=0; i<G.numVertexes; i++){
		parent[i] = 0;	//初始化数组为0
	}
	for(i=0; i<G.numVertexes; i++){
		n = Find(parent, edges[i].begin);
		m = Find(parent, edge[i],end);
		/*假如n与m不等，说明此边没有与现有生成树形成环路*/
		if(n != m){
		/*将此边的结尾顶点放入下标为起点的parent中
		表示此顶点已经在生成树集合中*/
		parent[n] = m;
		printf("(%d, %d, %d)", edges[i].begin, 
						edges[i].end, edges[i].weight);
		}
	}
}

/*查找连线顶点的尾部下标*/
int Find(int *parent, int f){
	while(parent[f] > 0){
		f = parent[f];
	}
	return f;
}

此算法的Find函数由边数e决定，时间复杂度为$O(loge)$，而外面有一个for循环e次。所以克鲁斯卡尔算法的时间复杂度为$O(eloge)$。
对比两个算法，克鲁斯卡尔算法主要是针对边来展开，边数少时效率会非常高，所以对于稀疏图有很大的优势；而普里姆算法对于稠密图，即边数非常多的情况会更好一些。

最短路径

在网图和非网图中，最短路径的含义是不同的。由于非网图它没有边上的权值，所谓的最短路径，其实就是指两顶点之间经过的边数最少的路径；而对于网图来说，最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点。

一、迪杰斯特拉( Dijkstra )算法

Dijkstra算法用于构建单源点的最短路径—，即图中某个点到任何其他点的距离都是最短的。例如，构建地图应用时查找自己的坐标离某个地标的最短距离。可以用于有向图，但是不能存在负权值。

我们以上图为例，通俗点说，这个迪杰斯特拉(Dijkstra) 算法，它并不是一下子求出了$v_0$到$v_8$的最短路径，而是一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到你要的结果。

Dijkstra算法设置一个集合S记录已求得的最短路径的顶点。
在构造的过程中还设置了个辅助数组:
dist[]：记录从源点$v_0$到其他各顶点当前的最短路径长度，它的初态为：若从$v_0$到$v_i$;有弧，则dist[i]为弧上的权值；否则置dist[i]为$\infty$。

例如，对图6.17中的图应用 Dijkstra算法求从顶点1出发至其余顶点的最短路径的过程，如表6.1所示。算法执行过程的说明如下。

• 初始化：集合S初始为$v_1$，$v_1$可达$v_2$和$v_5$，$v_1$不可达$v_3$和$v_4$，因此dist[]数组各元素的初值依次设置为dist[2]=10，dist[3]=$\infty$，dist[4]=$\infty$，dist[5]=5。
• 第一轮：选出最小值dist[5]，将顶点$v_5$并入集合$S$,即此时已找到$v_1$到${\nu }_5$的最短路径。当$v_5$加入$S$后，从$v_1$到集合$S$中可达顶点的最短路径长度可能会产生变化。因此需要更新dist[]数组。$v_5$可达$v_2$，因$v_1\to v_5\to v_2$的距离8比dist[2]=10小，更新dist[2]=8；$v_5$可达$v_3$，$v_1\to v_5\to v_3$的距离14，更新dist[3]=14；$v_5$可达$v_4$，$v_1\to v_5\to v_4$的距离7，更新dist[4]=7。
• 第二轮：选出最小值dist[4]，将顶点${\nu }_4$并入集合$S$。继续更新dist[]数组。${\nu }_4$不可达$v_2$，dist[2]不变；$v_4$可达$v_3$，$v_1\to v_5\to v_4\to v_3$的距离13比dist[3]小，故更新dist[3]=13。
• 笫三轮：选出最小值dist[2]，将顶点${\nu }_2$并入集合$S$。继续更新dist[]数组。$v_2$可达${\nu }_3$，$v_1\to v_5\to v_2\to v_3$的距离9比dist[3]小，更新dist[3]=9。
• 第四轮：选出唯一最小值dist[3]，将顶点$v_3$并入集合$S$，此时全部顶点都已包含在$S$中。

显然，Dijkstra 算法也是基于贪心策略的。使用邻接矩阵或者带权的邻接表表示时，时间复杂度为$O(V^2)$。
人们可能只希望找到从源点到某个特定顶点的最短路径，但这个问题和求解源点到其他所有顶点的最短路径一样复杂，时间复杂度也为$O(V^2)$。

二、弗洛伊德( Floyd )算法

定义一个n阶方阵序列$A^{(-1)},A^{(0)},...,A^{(n-1)}$，其中，$$A^{(-1)}[i][j]=arcs[i][j]$$ A ( k ) [ i ] [ j ] = M i n { A ( k − 1 ) [ i ] [ j ] , A ( k − 1 ) [ i ] [ k ] + A ( k − 1 ) [ k ] [ j ] , k = 0 , 1 , . . . , n − 1 } A^{(k)}[i][j] = Min\{A^{(k-1)}[i][j],A^{(k-1)}[i][k]+A^{(k-1)}[k][j],k=0,1,...,n-1\} A(k)[i][j]=Min{A(k−1)[i][j],A(k−1)[i][k]+A(k−1)[k][j],k=0,1,...,n−1}式中，$A^{(0)}[i][j]$是从顶点$v_i$到$v_j$、中间顶点的序号不大于k的最短路径的长度。Floyd算法是一个迭代的过程，每迭代一次，在从$v_i$到$v_j$的最短路径上就多考虑了一个顶点；经过$n$次迭代后，所得到的$A^{(n-1)}[i][j]$就是$v_i$到$v_j$的最短路径长度，即方阵$A^{(n-1)}$中就保存了任意一对顶点之间的最短路径长度。

上图所示为带权有向图$G$及其邻接矩阵。算法执行过程的说明如下。

• 初始化：方阵$A^{(-1)}[i][j]=arcs[i][j]$。
• 第一轮：将$v_0$作为中间顶点，对于所有顶点 { i , j } \{i, j\} {i,j}，如果有$A^{-1}[i][j]>A^{-1}[i][0]+A^{-1}[0][j]$，则将$A^{-1}[i][j]$更新为$A^{-1}[i][0]+A^{-1}[0][j]$。有$A^{-1}[2][1]>A^{-1}[2][0]+A^{-1}[0][1]=11$，更新$A^{-1}[2][1]=11$，更新后的方阵标记为$A^0$。
• 第二轮：将$v_1$作为中间顶点，继续监测全部顶点对 { i , j } \{i, j\} {i,j}。有$A^0[0][2]>A^0[0][1]+A^0[1][2]=10$，更新后的方阵标记为$A^1$。
• 第三轮：将$v_2$作为中间顶点，继续监测全部顶点对 { i , j } \{i, j\} {i,j}。有$A^1[1][0]>A^1[1][2]+A^1[2][0]=9$，更新后的方阵标记为$A^2$。此时$A^2$中保存的就是任意顶点对的最短路径长度。

应用Floyd算法求所有顶点之间的最短路径长度的过程如下表所示。

从这个表中，可以发下一些规律：

可以看出，矩阵中，每一步中红线划掉的部分都不用考虑计算，只需要计算红线外的部分，节省了计算量。

Floyd算法的时间复杂度为$O(V^3)$。不过由于其代码很紧凑，且并不包含 其他复杂的数据结构，因此隐含的常数系数是很小的，即使对于中等规模的输入来说，它仍然是相当有效的。
Floyd算法允许图中有带负权值的边，但不允许有包含带负权值的边组成的回路。Floyd 算法同样适用于带权无向图，因为带权无向图可视为权值相同往返二重边的有向图。
也可以用单源最短路径算法来解决每对顶点之间的最短路径问题。轮流将每个顶点作为源点，并且在所有边权值均非负时，运行一次 Dijkstra算法，其时间复杂度为$O(V^3)\ast V=O(V^3)$。

---

拓扑排序

一、定义

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网( Activity On VertexNetwork)。
若用DAG图（有向无环图）表示一个工程，其顶点表示活动，用有向边$<V_i,V_j>$表示活动$V_i$必须先于活动$V_j$进行的这样一种关系。在AOV网中，活动$V_i$是活动$V_j$的直接前驱，活动$V_j$是活动$V_i$的直接后继，这种前驱和后继关系具有传递性，且任何活动$V_i$不能以它自己作为自己的前驱或后继。
设$G=(V,E)$是一个具有n个顶点的有向图，$V$中的顶点序列$V_1,V_2,...V_n$，满足若从顶点$V_i$到$V_j$有一条路径，则在顶点序列中顶点$V_i$必在顶点$V_j$之前。则我们称这样的顶点序列为一个拓扑序列。

所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程。每个AOV网都有一个或多个拓扑排序序列。

二、算法

对一个AOV网进行拓扑排序的算法有很多，下面介绍比较常用的一种方法的步骤:

• ①从AOV网中选择一个没有前驱的顶点并输出。
• ②从网中删除该顶点和所有以它为起点的有向边。
• ③重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。如果输出顶点数少了，哪怕是少了一个，也说明这个网存在环(回路)，不是AOV网。

上图所示为拓扑排序过程的示例。每一轮选择一个入度为0的顶点并输出，然后删除该顶点和所有以它为起点的有向边，最后得到拓扑排序的结果为 { 1 , 2 , 4 , 3 , 5 } \{1,2, 4, 3,5\} {1,2,4,3,5}。
拓扑排序算法的实现如下：

bool TopologicalSort(Graph G){
	InitStack(S);	//初始化栈，存储入度为0的顶点
	for(int i=0; i<G.vexnum; i++){
		if(indegree[i] == 0){
			Push(S, i);	//将所有入度为0的顶点进栈
		}
	}
	int count = 0;	//计数，记录当前已经输出的顶点数
	while(!IsEmpty(S)){	//栈不空，则存在入度为0的顶点
		Pop(S, i);	//顶点元素出栈
		printf("%d ", i);	//输出顶点i
		count++;
		for(p=G.vertices[i].finstarc; p; p=p->nextarc){
			//将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈S
			v = p->adjvex;
			if(!--indegree[v]){
				Push(S, v);	//入度为0，则入栈
			}
		}
	}
	if(count < G.vexnum){
		return false;	//输出顶点少了，有向图中有回路，排序失败
	}else{
		return true;	//拓扑排序成功
	}
}

由于输出每个顶点的同时还要删除以它为起点的边，故拓扑排序的时间复杂度为$O(V+E)$。
此外，利用深度优先遍历也可实现拓扑排序。

用拓扑排序算法处理AOV网时，应注意以下问题:
①入度为零的顶点，即没有前驱活动的或前驱活动都已经完成的顶点，工程可以从这个顶点所代表的活动开始或继续。
②若一个顶点有多个直接后继，则拓扑排序的结果通常不唯一；但若各个顶点已经排在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，则拓扑排序的结果是唯一的。
③由于AOV网中各顶点的地位平等，每个顶点编号是人为的，因此可以按拓扑排序的结果重新编号，生成AOV网的新的邻接存储矩阵，这种邻接矩阵可以是三角矩阵；但对于一般的图来说，若其邻接矩阵是三角矩阵，则存在拓扑序列；反之则不一定成立。

---

关键路径

一、定义

拓扑排序主要是为解决一个工程能否顺序进行的问题，但有时我们还需要解决工程完成需要的最短时间问题。
在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销(如完成活动所需的时间)，称之为用边表示活动的网络，简称AOE网。AOE网和AOV网都是有向无环图，不同之处在于它们的边和顶点所代表的含义是不同的，AOE网中的边有权值；而AOV网中的边无权值，仅表示顶点之间的前后关系。
AOE网具有以下两个性质：

• ①只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；
• ②只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。

如上图的AOE网，在AOE网中仅有一个入度为0的顶点，称为开始顶点(源点)，它表示整个工程的开始；网中也仅存在一个出度为0的顶点，称为结束顶点(汇点)，它表示整个工程的结束。我们把路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫关键路径，在关键路径上的活动叫关键活动。
完成整个工程的最短时间就是关键路径的长度，即关键路径上各活动花费开销的总和。这是因为关键活动影响了整个工程的时间，即若关键活动不能按时完成，则整个工程的完成时间就会延长。因此，只要找到了关键活动，就找到了关键路径，也就可以得出最短完成时间。

二、算法

在分析算法之前，需要了解几个重要的参数：

1.事件的最早发生时间$ve$：即顶点$V_k$的最早发生时期。
2.事件的最晚发生时间$vl$：即顶点$V_k$的最晚发生时间，也就是每个顶点对应的事件最晚需要开始的时间，超出此时间将会延误整个工期。
3.活动的最早开始时间$e$：即弧$a_i$的最早发生时间。
4.活动的最晚开始时间$l$：即弧$a_i$的最晚发生时间，也就是不推迟工期的最晚开工时间。
5.一个活动$a_i$的最迟开始时间$l(i)$和其最早开始时间$e(i)$的差额$d(i)=l(i)-e(i)$：它是指该活动完成的时间余量，即在不增加完成整个工程所需总时间的情况下，活动$a_i$可以拖延的时间。若一个活动的时间余量为零，则说明该活动必须要如期完成，否则就会拖延整个工程的进度，所以称$l(i)-e(i)=0$即$l(i)=e(i)$的活动$a_i$是关键活动。

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

1. 从源点出发，令$ve(源点)=0$， 按拓扑排序求其余顶点的最早发生时间$ve()$。
2. 从汇点出发，令$vl(汇点)=ve(汇点)$，按逆拓扑排序求其余顶点的最迟发生时间$vl()$。
3. 根据各顶点的$ve()$值求所有弧的最早开始时间$e()$。
4. 根据各顶点的$vl()$值求所有弧的最迟开始时间$l()$。
5. 求AOE网中所有活动的差额$d()$， 找出所有$d()=0$的活动构成关键路径。

上图所示为求解关键路径的过程，简单说明如下:

1. 求$ve()$：初始$ve(1)=0$，在拓扑排序输出顶点的过程中，求得$ve(2)=3$，$ve(3)=2$， v e ( 4 ) = m a x { v e ( 2 ) + 2 , v e ( 3 ) + 4 } = m a x { 5 , 6 } = 6 ve(4)=max\{ve(2)+2, ve(3)+4\} = max\{5, 6\} = 6 ve(4)=max{ve(2)+2,ve(3)+4}=max{5,6}=6，$ve(5)=6$， v e ( 6 ) = m a x { v e ( 5 ) + 1 , v e ( 4 ) + 0 , v e ( 3 ) + 3 } = m a x { 7 , 8 , 5 } = 8 ve(6) = max\{ve(5)+1, ve(4)+0, ve(3)+3\} = max\{7, 8, 5\} = 8 ve(6)=max{ve(5)+1,ve(4)+0,ve(3)+3}=max{7,8,5}=8。
2. 求$vl()$：初始$vl(6)=8$，在逆拓扑排序出栈过程之中，求得$vl(5)=7$，$vl(4)=6$， v l ( 3 ) = m i n { v l ( 4 ) − 4 , v l ( 6 ) − 3 } = m i n { 2 , 5 } = 2 vl(3)=min\{vl(4)-4, vl(6)-3\} = min\{2, 5\}=2 vl(3)=min{vl(4)−4,vl(6)−3}=min{2,5}=2， v l ( 2 ) = m i n { v l ( 5 ) − 3 , v l ( 4 ) − 2 } = m i n { 4 , 4 } = 4 vl(2)=min\{vl(5)-3,vl(4)-2\}=min\{4,4\}=4 vl(2)=min{vl(5)−3,vl(4)−2}=min{4,4}=4，$vl(1)$必然为$0$而无需再求。
3. 弧的最早开始时间$e()$等于该弧的起点的顶点的$ve()$，求得结果如上表所示。
4. 弧的最迟开始时间$l(i)$等于该弧的终点的顶点的$vl()$减去该弧持续的时间，求得结果如上表所示。
5. 根据$l(i)-e(i)=0$的关键活动，得到的关键路径为$(v_1,v_3,v_4,v_6)$。

对于关键路径，需要注意以下几点:
①关键路径上的所有活动都是关键活动，它是决定整个工程的关键因素，因此可通过加快关键活动来缩短整个工程的工期。但也不能任意缩短关键活动，因为一旦缩短到一定的程度，该关键活动就可能会变成非关键活动。
②网中的关键路径并不唯一，
且对于有几条关键路径的网，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。

总结

图是计算机科学中非常常用的一类数据结构，同时也是最复杂的数据结构了，对它的学习，涉及到顺序表、链表、栈、队列、树等之前学的几乎所有数据结构，所以学习图之前要对这几种数据结构都要有所了解才行。

---

附录

上文链接

数据结构：树

下文链接

数据结构：查找

专栏

数据结构专栏

参考资料

1、严蔚敏、吴伟民：《数据结构（C语言版）》
2、程杰：《大话数据结构》
3、王道论坛：《数据结构考研复习指导》
4、托马斯·科尔曼等人：《算法导论》

上次发操作系统笔记，很快浏览上万，这次数据结构比上次硬核的多哦，同样的会发超硬核代码，关注吧。

超硬核！操作系统学霸笔记，考试复习面试全靠它

 

---

 

---

 

第一次笔记（复习c，课程概述）

第一节课复习了c语言的一些知识，并简单介绍了数据结构这门课程。

 

1、引用和函数调用：

1.1引用：对一个数据建立一个“引用”，他的作用是为一个变量起一个别名。这是C++对C语言的一个重要补充。

用法很简单：

int a = 5;

int &b = a;

b是a别名，b与a代表的是同一个变量，占内存中同一个存储单元，具有同一地址。

注意事项：

1. 声明一个引用，同时必须初始化，及声明它代表哪一个变量。（作为函数参数时不需要初始化）
    
2. 在声明一个引用后，不能再作为另一变量的引用。

     3。不能建立引用数组。

1.2函数调用：

其实还是通过函数来理解了一下引用

void Myswap1(int a,int b)
{
	int c = a;
	a = b;
	b = c;
}

void Myswap2(int &a,int &b)
{
	int c = a;
	a = b;
	b = c;
}

void Myswap3(int *pa,int *pb)
{
	int c = *pa;
	*pa = *pb;
	*pb = c;
}

这三个函数很简单，第一个只传了值进来，不改变全局变量；而第三个也很熟悉，就是传递了地址，方便操作。依旧是“值传递”的方式，只不过传递的是变量的地址而已；那二就彻底改变了这些东西，引用作为函数参数，传入的实参就是变量，而不是数值，真正意义上的“变量传递”。

 

2、数组和指针：

这一块讲得比较简单，就是基本知识。

主要内容：

1、函数传数组就是传了个指针，这个大家都知道，所以传的时候你写arr[],里面写多少，或者不写，都是没关系的，那你后面一定要放一个变量来把数组长度传进来。

2、还有就是，定义：int arr[5]，你访问越界是不会报错的，但是逻辑上肯定就没有道理了。那用typedef int INTARR[3];访问越界，在vs上会报错，要注意。

3、再说一下指针和数组名字到底有什么区别？这本来就是两个东西，可能大家没注意罢了。

第一：指针可以自增，数组名不行，因为是常量啊。

第二：地址不同，虽然名字[n]，都可以这样用，但是数组名地址就是第一个元素地址。指针地址就是那个指针的地址，指针里存的才是第一个元素地址。

第三：sizeof（），空间不一样，数组是占数组那么大空间。指针是四个字节。

本来就是俩东西，这么多不同都是本质不同的体现。

3、结构体：

也是讲的基本操作，基本就是这个东西：

typedef struct Date
{
	int Year;
	int Month;
	int Day;
	struct Date *pDate;
}Date, *pDate;

1、内部无指向自己的指针才可以第一行先不起名字。

2、内部不能定义自己的，如果能的话那空间不就无限了么。很简单的逻辑

 

指针我不习惯，还是写Date *比较顺眼

3、有同学没注意：访问结构体里的东西怎么访问？

Date.这种形式，或者有指向这个节点的指针p可以p->这种形式，别写错了。

 

4、还有就是结构体能直接这么赋值：

   Date d1 = {2018,9,11};

我竟然不知道，以前还傻乎乎的一个一个赋值呢。

 

5、还有，想写一下结构体有什么优点。。

这一块可能写的就不好了，因为不是老师讲的。。

比如学生成绩，如果不用结构体，我们一个学生可能有十几个信息，那定义变量和操作就很烦琐了，数据结构有一种松散的感觉。用一个结构体来表示更好，无论是程序的可读性还是可移植性还是可维护性，都得到提升。还有就是函数调用的时候，传入相当多的参数，又想操作或者返回，那是很麻烦的事。现在只传入一个结构体就好了，操作极其简单。总结一下就是好操作，中看中用，有机地组织了对象的属性。以修改结构体成员变量的方法代替了函数(入口参数)的重新定义。

基本就这样吧。

6、还有就是它了：typedef int INTARR[3];这样直接定义了一个数据类型，长度为3的数组，然后直接这样用就可以了：

INTARR arr1;

 

回忆完C语言储备知识，然后讲了数据结构的基本概念

 

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

数据：是对客观事物的符号表示，在计算机中指能输入到计算机中并被处理的符号总称。

数据元素：数据的基本单位

数据项：数据的不可分割的最小单位

数据对象：性质相同的数据元素的集合。

举例：动物是数据，某只动物是数据元素，猫狗是数据对象，颜色可以是数据项。

 

数据元素之间存在某种关系，这种关系成为结构。

四种基本结构：

集合：除了同属一个集合无其他关系。

线性结构：一对一的关系

树形结构：一对多的关系

图状结构：多对多的关系

 

第二次笔记（基本概念，时间空间复杂度）

今天继续说明了一些基本概念，讲解了时间空间复杂度。

（对于概念的掌握也很重要）

 

元素之间的关系在计算机中有两种表示方法：顺序映像和非顺序映像，由此得到两种不同的储存结构：

顺序存储结构和链式存储结构。

 

顺序：根据元素在存储器中的相对位置表示关系

链式：借助指针表示关系

 

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

抽象数据类型：是指一个数学模型以及定义在该模型上的一组操作。（仅仅取决于逻辑特性，与其在计算机内部如何表示和实现无关）

 

定义抽象数据类型的一种格式：

ADT name{

数据对象：<>

数据关系：<>

基本操作：<>

}ADT name

 

算法：是对特定问题求解步骤的一种描述。

算法五个特性：

1. 有穷性：有穷的时间内完成，或者可以说是可接受的时间完成
2. 确定性：对于相同的输入只能得到相同的输出
3. 可行性：描述的操作都可以执行基本操作有限次来实现
4. 输入：零个或多个输入。取自于某个特定对象的集合
5. 输出：一个或多个输出

 

设计要求：正确性、可读性、健壮性、效率与低存储量需求。

执行频度概念：是指通过统计算法的每一条指令的执行次数得到的。

执行频度=算法中每一条语句执行次数的和

一般认定每条语句执行一次所需时间为单位时间（常数时间）O(1)

 

几个小知识和小问题：

1）循环执行次数n+1次，不是n次。第一次执行i=1和判断i<=n以后执行n次判断和i++。所以该语句执行了n+1次。在他的控制下，循环体执行了n次。

2）四个并列程序段：分别为O(N),O(N^2),O(N^3),O(N*logN),整个程序时间复杂度为O(N^3)，因为随着N的增长，其它项都会忽略

3）算法分析的目的是分析算法的效率以求改进

4）对算法分析的前提是算法必须正确

5）原地工作指的不是不需要空间，而是空间复杂度O(1)，可能会需要有限几个变量。

实现统一功能两种算法：时间O(2^N),O(N^10)，假设计算机可以运行10^7秒，每秒可执行基本操作10^5次，问可解问题规模各为多少？选哪个更为合适？

计算机一共可执行10^7*10^5=10^12次

第一种：n=log2,(10^12)=12log(2,10)

第二种：n=（10^12）^0.1

显然1更适用。

虽然一般情况多项式算法比指数阶更优

 

时间空间复杂度概述

 

找个时间写一写时间复杂度和一些问题分类，也普及一下这方面知识。

如何衡量一个算法好坏

很显然，最重要的两个指标：需要多久可以解决问题、解决问题耗费了多少资源

那我们首先说第一个问题，要多长时间来解决某个问题。那我们可以在电脑上真实的测试一下嘛，多种方法比一比，用时最少的就是最优的啦。

但是没必要，我们可以通过分析计算来确定一个方法的好坏，用O()表示，括号内填入N、1，等式子。

这到底是什么意思呢？

简单来说，就是这个方法，时间随着数据规模变化而增加的快慢。时间可以当成Y，数据规模是X，y=f(x)，就这样而已。但是f(x)不是准确的，只是一个大致关系，y=10x,我们也视作x，因为他的增长速度还是n级别的。现在就可以理解了：一般O(N)就是对每个对象访问优先次数而已。请注意：O(1)它不是每个元素访问一次，而是Y=1的感觉，y不随x变化而变化，数据多大它的时间是不变的，有限的常数操作即可完成。

那我们就引入正规概念：

时间复杂度是同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。

计算机科学中，算法的时间复杂度是一个函数，它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况。

注意：文中提到：不包括这个函数的低阶项和首项系数。什么意思呢？就是说10n,100n,哪怕1000000000n,还是算做O(N)，而低阶项是什么意思？不知大家有没有学高等数学1，里面有最高阶无穷大，就是这个意思。举个例子。比如y=n*n*n+n*n+n+1000

就算做o(n*n*n),因为增长速率最大，N*N及其它项增长速率慢，是低阶无穷大，n无限大时，忽略不计。

 

那接着写：o(n*n*n)的算法一定不如o(n)的算法吗？也不一定，因为之前说了，时间复杂度忽略了系数，什么意思？o(n)可以是10000000n，当n很小的时候，前者明显占优。

所以算法要视实际情况而定。

算法的时间 复杂度常见的有：
常数阶 O(1)，对数阶 O(log n)，线性阶 O(n)，
线性对数阶 O(nlog n)，平方阶 O(n^2)，立方阶 O(n^3)，…，
k 次方阶O(n^k)，指数阶 O(2^n)，阶乘阶 O(n!)。

常见的算法的时间 复杂度之间的关系为：
       O(1)<O(log n)<O(n)<O(nlog n)<O(n^2)<O(2^n)<O(n!)<O(n^n) 

 

我们在竞赛当中，看见一道题，第一件事就应该是根据数据量估计时间复杂度。

计算机计算速度可以视作10^9,如果数据量是10000，你的算法是O(N*N)，那就很玄，10000*10000=10000 0000，别忘了还有常数项，这种算法只有操作比较简单才可能通过。你可以想一想O(nlog n)的算法一般就比较稳了。那数据量1000，一般O(N*N)就差不多了，数据量更小就可以用复杂度更高的算法。大概就这样估算。

 

当 n 很大时，指数阶算法和多项式阶算法在所需时间上非常
悬殊。因此，只要有人能将现有指数阶算法中的任何一个算法化
简为多项式阶算法，那就取得了一个伟大的成就。

体会一下：

 

空间复杂度也是一样，用来描述占空间的多少。

注意时间空间都不能炸。

所以才发明了那么多算法。

符上排序算法的时间空间表，体会一下：

 

排序博客：加深对时间空间复杂度理解

https://blog.csdn.net/hebtu666/article/details/81434236

 

 

 

引入：算法优化

 

想写一系列文章，总结一些题目，看看解决问题、优化方法的过程到底是什么样子的。

 

系列问题一：斐波那契数列问题

在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）根据定义，前十项为1, 1, 2, 3, 5, 8, 13, 21, 34, 55

问题一：

给定一个正整数n，求出斐波那契数列第n项（这时n较小）

解法一：最笨，效率最低，暴力递归，完全是抄定义。请看代码

def f0(n):
    if n==1 or n==2:
        return 1
    return f(n-1)+f(n-2)

 

分析一下，为什么说递归效率很低呢？咱们来试着运行一下就知道了：

 

比如想求f(10)，计算机里怎么运行的？

 

每次要计算的函数量都是指数型增长，时间复杂度O(2^(N/2))<=T(N)<=O(2^N),效率很低。效率低的原因是，进行了大量重复计算，比如图中的f(8),f(7).....等等，你会发现f(8)其实早就算过了，但是你后来又要算一遍。

如果我们把计算的结果全都保存下来，按照一定的顺序推出n项，就可以提升效率， 斐波那契（所有的一维）的顺序已经很明显了，就是依次往下求。。

优化1

def f1(n):
    if n==1 or n==2:
        return 1
    l=[0]*n
    l[0],l[1]=1,1
    for i in range(2,n):
        l[i]=l[i-1]+l[i-2]
    return l[-1]

 

时间复杂度o(n)，依次往下打表就行，空间o(n).

继续优化：既然只求第n项，而斐波那契又严格依赖前两项，那我们何必记录那么多值呢？记录前两项就行了

 

优化2

def f2(n):
    a,b=1,1
    for i in range(n-1):
        a,b=b,a+b
    return a

此次优化做到了时间o(n),空间o(1)

附：这道题掌握到这里就可以了，但是其实有时间o(log2n)的方法

 

优化三：

学习过线性代数的同学们能够理解：

 

结合快速幂算法，我们可以在o(log2n)内求出某个对象的n次幂。(在其它专题详细讲解)

注意：只有递归式不变，才可以用矩阵+快速幂的方法。

注：优化三可能只有在面试上或竞赛中用，当然，快速幂还是要掌握的。

 

经过这个最简单的斐波那契，大家有没有一点感觉了？

好，我们继续往下走

(补充：pat、蓝桥杯原题，让求到一万多位，结果模一个数。

可以每个结果都对这个数取模，否则爆内存，另：对于有多组输入并且所求结果类似的题，可以先求出所有结果存起来，然后直接接受每一个元素，在表中查找相应答案)

 

问题二：

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

依旧是找递推关系，分析：跳一阶，就一种方法，跳两阶，它可以一次跳两个，也可以一个一个跳，所以有两种，三个及三个以上，假设为n阶，青蛙可以是跳一阶来到这里，或者跳两阶来到这里，只有这两种方法。它跳一阶来到这里，说明它上一次跳到n-1阶，同理，它也可以从n-2跳过来，f（n）为跳到n的方法数，所以，f(n)=f(n-1)+f(n-2)

和上题的优化二类似。

因为递推式没变过，所以可以用优化三

 

问题三：

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？提示，大矩形看做是长度吧

请读者自己先思考一下吧。。。仔细看题。。仔细思考

如果n是1，只有一种，竖着放呗；n是2，两种：

，

n等于3，三种：

 

题意应该理解了吧？

读到这里，你们应该能很快想到，依旧是斐波那契式递归啊。

对于n>=3:怎么能覆盖到三？只有两种办法，从n-1的地方竖着放了一块，或者从n-2的位置横着放了两块呗。

和问题二的代码都不用变。

 

问题四：

给定一个由0-9组成的字符串，1可以转化成A，2可以转化成B。依此类推。。25可以转化成Y，26可以转化成z，给一个字符串，返回能转化的字母串的有几种？

比如：123，可以转化成

1 2 3变成ABC，

12 3变成LC，

1 23变成AW，三种，返回三，

99999，就一种：iiiii，返回一。

分析：求i位置及之前字符能转化多少种。

两种转化方法，一，字符i自己转换成自己对应的字母，二，和前面那个数组成两位数，然后转换成对应的字母

假设遍历到i位置，判断i-1位置和i位置组成的两位数是否大于26，大于就没有第二种方法，f(i)=f(i-1),想反，等于f(i-1)+f(i-2)

注意：递归式不确定，不能用矩阵快速幂

 

(这几个题放到这里就是为了锻炼找递归关系的能力，不要只会那个烂大街的斐波那契)

 

'''
斐波那契问题：
斐波纳契数列以如下被以递归的方法定义：
F(1)=1
F(2)=1
F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）
'''
#暴力抄定义,过多重复计算
def f0(n):
    if n==1 or n==2:
        return 1
    return f(n-1)+f(n-2)
#记录结果后依次递推的优化，时间O(N)
def f1(n):
    if n==1 or n==2:
        return 1
    l=[0]*n
    l[0],l[1]=1,1
    for i in range(2,n):
        l[i]=l[i-1]+l[i-2]
    return l[-1]
#既然严格依赖前两项，不必记录每一个结果，优化空间到O(1)
def f2(n):
    a,b=1,1
    for i in range(n-1):
        a,b=b,a+b
    return a

第三次笔记（线性表结构和顺序表示）

 

这节课介绍了线性表结构和顺序表示的一部分内容。

操作太多，而且书上有，就不一一介绍分析了。

线性表定义：n个数据元素的有限序列。

特点：

1. 存在唯一一个称作“第一个”的元素。
2. 存在唯一一个称作“最后一个”的元素
3. 除最后一个元素外，集合中每一个元素都只有一个直接前趋
4. 除最后一个元素外，集合中每一个元素都只有一个直接后继

注意1、2条：证明循环的序列不是线性表

 

注意：

1)线性表从1开始,线性表第一个元素对应到数组中下标是0.

2)函数通过引用对线性表的元素进行修改即可

3)数组比较特别，它即可视为逻辑结构，又可视为存储结构。

4)每一个表元素都是不可再分的原子数据。一维数组可以视为线性表，二维数组不可以，在逻辑上它最多可以有两个直接前趋和直接后继。

5)线性表具有逻辑上的顺序性，在序列中各元素有其先后次序，各个数据元素在线性表中的逻辑位置只取决于序号。

 

顺序表：是线性表的循序储存结构，以物理位置表示逻辑关系，任意元素可以随机存取。用一组地址连续的存储单元依次存储线性表中的元素。逻辑顺序和物理顺序是一致的。可以顺序访问，也可随机访问。

顺序表存储：

这些定式还是很重要的，比如define typedef等，真正实现时最好就这样写，不要自己规定个长度和数据类型，这样以后好维护、修改。

静态存储分配：

#define maxSize 100//显式定义表长

Typedef int DataType;//定义数据类型

Typedef struct{

DataType data[maxSize];//静态分配存储表元素向量

Int n;//实际表中个数

}SeqList;

 

动态存储分配：

#define maxSize 100//长度初始定义

Typedef int DataType;//定义数据类型

Typedef struct{

DataType *data;//动态分配数组指针

Int maxSize,n;//最大容量和当前个数

}SeqList;

 

初始动态分配：

Data=(DataType *)malloc(sizeof(DataType)* initSize);

C++:data=new DataType[initSize];

maxSize=initSize;n=0;

动态分配存储，向量的存储空间是在程序执行过程中通过动态存储分配来获取的。空间满了就另外分配一块新的更大的空间，用来代替原来的存储空间，从而达到扩充的目的。

 

插入：需要查找，移动元素，概率上1，2，3....n，平均O(N)

删除：同样需要移动元素。填充被空出来的存储单元。

在等概率下平均移动次数分别为n/2,(n-1)/2

 插入注意事项：

1. 需要判断是否已满
2. 要从后向前移动，否则会冲掉元素

删除注意事项：

1. 需要先判断是否已空
2. 需要把后方元素前移，要从前向后。

 

注意：线性表的顺序存储借用了一维数组，但是二者不同：

1. 一维数组各非空结点可以不相继存放，但顺序表是相继存放的
2. 顺序表长度是可变的，一维数组长度是确定的，一旦分配就不可变
3. 一维数组只能按下标存取元素，顺序表可以有线性表的所有操作。

 

 

第四次笔记（链表概述）

 

介绍了链表和基本操作

用一组物理位置任意的存储单元来存放线性表的数据元素。 这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中元素的逻辑次序和 物理次序不一定相同。

 

定义：

typedef  struct  Lnode{  
        //声明结点的类型和指向结点的指针类型  
        ElemType         data;    //数据元素的类型 
        struct   Lnode  *next;   //指示结点地址的指针  
}Lnode, *LinkList;  

struct Student
{ char num[8];   //数据域
  char name[8];  //数据域
  int score;          //数据域
  struct Student *next;  // next 既是 struct Student 
                                       // 类型中的一个成员，又指 
                                       // 向 struct Student 类型的数据。 
}Stu_1, Stu_2, Stu_3, *LL;  

头结点：在单链表的第一个结点之前人为地附设的一个结点。

带头结点操作会方便很多。

带和不带的我都写过了

下面列出我见过的一些好题

1、

线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

• 正确

• 错误

 

错，线性表是逻辑结构概念，可以顺序存储或链式储，与元素数据类型无关。链表就是线性表的一种  前后矛盾

 

2、

若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用(    )存储方式最节省运算时间。

• 单链表

• 仅有头指针的单循环链表

• 双链表

• 仅有尾指针的单循环链表

  对于A,B，C要想在尾端插入结点，需要遍历整个链表。

  对于D，要插入结点，只要改变一下指针即可，要删除头结点，只要删除指针.next的元素即可。

 

3、注意：线性表是具有n个数据元素的有限序列，而不是数据项

 

4、

以下关于单向链表说法正确的是

• 如果两个单向链表相交，那他们的尾结点一定相同

• 快慢指针是判断一个单向链表有没有环的一种方法

• 有环的单向链表跟无环的单向链表不可能相交

• 如果两个单向链表相交，那这两个链表都一定不存在环

自己多画画想想就明白了，关于快慢指针我以后会写总结。

 

5、

链接线性表是顺序存取的线性表 。 ( )

• 正确

• 错误

链接线性表可以理解为链表
线性表分为顺序表和链表
顺序表是顺序存储结构、随机存取结构
链表是随机存储结构、顺序存取结构

 

6、

typedef struct node_s{
    int item;
    struct node_s* next;
}node_t;
node_t* reverse_list(node_t* head)
{
    node_t* n=head;
    head=NULL;
    while(n){
    _________               
    }
    return head;
 }

空白处填入以下哪项能实现该函数的功能？

• node_t* m=head; head=n; head->next=m; n=n->next;

• node_t* m=n; n=n->next; m->next=head; head=m;

• node_t* m=n->next; n->next=head; n=m; head=n;

• head=n->next; head->next=n; n=n->next;

 

代码的功能是要实现链表的反转。为了方便阐述，每个结点用①②③④⑤⑥等来标示。

在执行while（n）循环之前，有两句代码：

node_t* n=head; head=NULL;

这两行代码的中：第一句的作用是用一个临时变量n来保存结点①，第二句是把head修改为NULL。

然后就开始遍历了，我们看到while循环里的那四句代码：

node_t* m=n; 
n=n->next; 
m->next=head; 
head=m；

先看前两句，用m来保存n，然后让n指向n的下一个结点，之所以复制 n 给 m ，是因为 n 的作用其实是  控制while循环次数  的作用，每循环一次它就要被修改为指向下一个结点。

再看后两句，变量head在这里像是一个临时变量，后两句让 m 指向了 head，然后 head 等于 m。

 

7、

若某表最常用的操作是在最后一个结点之后插入一个节点或删除最后一二个结点，则采用（）省运算时间。

• 单链表

• 双链表

• 单循环链表

• 带头结点的双循环链表

D

带头结点的双向循环链表，头结点的前驱即可找到最后一个结点，可以快速插入，再向前可以找到最后一二个结点快速删除

单链表找到链表尾部需要扫描整个链表

双链表找到链表尾部也需要扫描整个链表

单循环链表只有单向指针，找到链表尾部也需要扫描整个链表

 

8、

单链表的存储密度（  ）

• 大于1

• 等于1

• 小于1

• 不能确定

全麦白

存储密度 = 数据项所占空间 / 结点所占空间

 

9、完成在双循环链表结点p之后插入s的操作是

• s->prior=p; s->next=p->next; p->next->prior=s ; p->next=s;

 

10、用不带头结点的单链表存储队列,其队头指针指向队头结点,队尾指针指向队尾结点,则在进行出队操作时()

• 仅修改队头指针

• 仅修改队尾指针

• 队头、队尾指针都可能要修改

• 队头、队尾指针都要修改

 

当只有一个元素，出队列时，要将队头和队尾，指向-1.所以说队头和队尾都需要修改

 

 

链表刷了几百道吧，好题还有很多，以后接着更新

 

 

第六次笔记（链表选讲/静态链表）

 

本节课介绍了单链表的操作实现细节，介绍了静态链表。

 

链表带头的作用：对链表进行操作时，可以对空表、非空表的情况以及 对首元结点进行统一处理，编程更方便。

下面给出带头的单链表实现思路：

 

按下标查找：

判断非法输入，当 1 < =i <= n 时，i 的值是合法的。

p = L -> next; j = 1;

while ( p && j < i ) {  p = p ->next; ++j; }

return 

 

按值查找：

 p = L1 -> next;

 while ( p && p ->data!=key)          p = p -> next;

return;

 

插入：

判断

查找

创建

插入

 

删除：

查找

删除

释放内存

 

静态链表

对于线性链表，也可用一维数组来进行描述。这种描述方法便于在没有指针类型的高级程序设计语言中使用链表结构。

这种存储结构，仍需要预先分配一个较大的空间，但在作为线性表的插入和删除操作时不需移动元素，仅需修改指针，故仍具有链式存储结构的主要优点。

 

表示：

#define MAXSIZE 1000      / /链表的最大长度

typedef  struct{      

    ElemType data；        

    int cur；

}component,  SLinkList[MAXSIZE]；

 

过程：

 

 

顺序存储线性表实现

 

在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构。

 

顺序存储结构的主要优点是节省存储空间，因为分配给数据的存储单元全用存放结点的数据（不考虑c/c++语言中数组需指定大小的情况），结点之间的逻辑关系没有占用额外的存储空间。采用这种方法时，可实现对结点的随机存取，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。但顺序存储方法的主要缺点是不便于修改，对结点的插入、删除运算时，可能要移动一系列的结点。

优点：随机存取表中元素。缺点：插入和删除操作需要移动元素。

 

线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储），但是把最后一个数据元素的尾指针指向了首位结点）。

给出两种基本实现：

/*
静态顺序存储线性表的基本实现
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LIST_INITSIZE 100
#define ElemType int
#define Status int
#define OK     1
#define ERROR  0

typedef struct
{
	ElemType elem[LIST_INITSIZE];
	int length;
}SqList;

//函数介绍
Status InitList(SqList *L); //初始化
Status ListInsert(SqList *L, int i,ElemType e);//插入
Status ListDelete(SqList *L,int i,ElemType *e);//删除
void ListPrint(SqList L);//输出打印
void DisCreat(SqList A,SqList *B,SqList *C);//拆分(按正负)，也可以根据需求改
//虽然思想略简单，但是要写的没有错误，还是需要锻炼coding能力的

Status InitList(SqList *L)
{
    L->length = 0;//长度为0
    return OK;
}

Status ListInsert(SqList *L, int i,ElemType e)
{
    int j;
    if(i<1 || i>L->length+1)
        return ERROR;//判断非法输入
    if(L->length == LIST_INITSIZE)//判满
    {
        printf("表已满");//提示
        return ERROR;//返回失败
    }
    for(j = L->length;j > i-1;j--)//从后往前覆盖，注意i是从1开始
        L->elem[j] = L->elem[j-1];
    L->elem[i-1] = e;//在留出的位置赋值
    (L->length)++;//表长加1
    return OK;//反回成功
}

Status ListDelete(SqList *L,int i,ElemType *e)
{
    int j;
    if(i<1 || i>L->length)//非法输入/表空
        return ERROR;
    *e = L->elem[i-1];//为了返回值
    for(j = i-1;j <= L->length;j++)//从前往后覆盖
        L->elem[j] = L->elem[j+1];
    (L->length)--;//长度减1
    return OK;//返回删除值
}

void ListPrint(SqList L)
{
    int i;
    for(i = 0;i < L.length;i++)
        printf("%d ",L.elem[i]);
    printf("\n");//为了美观
}

void DisCreat(SqList A,SqList *B,SqList *C)
{
    int i;
    for(i = 0;i < A.length;i++)//依次遍历A中元素
    {
        if(A.elem[i]<0)//判断
            ListInsert(B,B->length+1,A.elem[i]);//直接调用插入函数实现尾插
        else
            ListInsert(C,C->length+1,A.elem[i]);
    }
}

int main(void)
{
    //复制的
	SqList L;
	SqList B, C;
	int i;
	ElemType e;
	ElemType data[9] = {11,-22,33,-3,-88,21,77,0,-9};
	InitList(&L);
	InitList(&B);
	InitList(&C);
	for (i = 1; i <= 9; i++)
		ListInsert(&L,i,data[i-1]);
    printf("插入完成后L = : ");
	ListPrint(L);
    ListDelete(&L,1,&e);
	printf("删除第1个后L = : ");
	ListPrint(L);
    DisCreat(L , &B, &C);
	printf("拆分L后B = : ");
	ListPrint(B);
	printf("拆分L后C = : ");
	ListPrint(C);
	printf("拆分L后L = : ");
	ListPrint(L);
}

静态：长度固定

动态：不够存放可以加空间（搬家）

 

/*
子任务名任务:1_2 动态顺序存储线性表的基本实现
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define Status int
#define OVERFLOW -1
#define OK 1
#define ERROR 0
#define ElemType int

typedef struct
{
	ElemType * elem;
	int length;
	int listsize;
}SqList;
//函数介绍
Status InitList(SqList *L); //初始化
Status ListInsert(SqList *L, int i,ElemType e);//插入
Status ListDelete(SqList *L,int i,ElemType *e);//删除
void ListPrint(SqList L);//输出打印
void DeleteMin(SqList *L);//删除最小

Status InitList(SqList *L)
{
    L->elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));//申请100空间
	if(!L->elem)//申请失败
		return ERROR;
	L->length = 0;//长度0
	L->listsize = LIST_INIT_SIZE;//容量100
	return OK;//申请成功
}

Status ListInsert(SqList *L,int i,ElemType e)
{
    int j;
    ElemType *newbase;
    if(i<1 || i>L->length+1)
        return ERROR;//非法输入
        
    if(L->length >= L->listsize)//存满了，需要更大空间
    {
        newbase = (ElemType*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType));//大10的空间
        if(!newbase)//申请失败
            return ERROR;
        L->elem = newbase;//调指针
        L->listsize+= LISTINCREMENT;//新容量
    }
    
    for(j=L->length;j>i-1;j--)//从后往前覆盖
        L->elem[j] = L->elem[j-1];
    L->elem[i-1] = e;//在留出的位置赋值
    L->length++;//长度+1
    return OK;
}

Status ListDelete(SqList *L,int i,ElemType *e)
{
    int j;
    if(i<1 || i>L->length)//非法输入/表空
        return ERROR;
    *e = L->elem[i-1];//为了返回值
    for(j = i-1;j <= L->length;j++)//从前往后覆盖
        L->elem[j] = L->elem[j+1];
    (L->length)--;//长度减1
    return OK;//返回删除值
}

void ListPrint(SqList L)
{
    int i;
    for(i=0;i<L.length;i++)
        printf("%d ",L.elem[i]);
    printf("\n");//为了美观
}

void DeleteMin(SqList *L)
{
    //表空在Listdelete函数里判断
    int i;
    int j=0;//最小值下标
    ElemType *e;
    for(i=0;i<L->length;i++)//寻找最小
    {
        if(L->elem[i] < L->elem[j])
            j=i;
    }
    ListDelete(L,j+1,&e);//调用删除，注意j要+1
}

int main(void)
{
	SqList L;
	int i;
	ElemType e;
	ElemType data[9] = {11,-22,-33,3,-88,21,77,0,-9};
	InitList(&L);
	for (i = 1; i <= 9; i++)
	{
		ListInsert(&L,i,data[i-1]);
	}
	printf("插入完成后 L = : ");
	ListPrint(L);
    ListDelete(&L, 2, &e);
	printf("删除第 2 个后L = : ");
	ListPrint(L);
    DeleteMin(&L);
	printf("删除L中最小值后L = : ");
	ListPrint(L);
	DeleteMin(&L);
	printf("删除L中最小值后L = : ");
	ListPrint(L);
	DeleteMin(&L);
	printf("删除L中最小值后L = : ");
	ListPrint(L);
}

单链表，不带头实现

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。

 

下面给出不带头的单链表标准实现：

定义节点：

typedef struct node 
{ 
    int data;
    struct node * next;
}Node;

尾插：

void pushBackList(Node ** list, int data) 
{ 
    Node * head = *list;
    Node * newNode = (Node *)malloc(sizeof(Node));//申请空间
    newNode->data = data; newNode->next = NULL;
    if(*list == NULL)//为空
        *list = newNode;
    else//非空
    {
        while(head ->next != NULL)
            head = head->next;
        head->next = newNode;
    }
}

插入：

int insertList(Node ** list, int index, int data) 
{
    int n;
    int size = sizeList(*list); 
    Node * head = *list; 
    Node * newNode, * temp;
    if(index<0 || index>size) return 0;//非法
    newNode = (Node *)malloc(sizeof(Node)); //创建新节点
    newNode->data = data; 
    newNode->next = NULL;
    if(index == 0) //头插
    {
        newNode->next = head; 
        *list = newNode; 
        return 1; 
    }
    for(n=1; n<index; n++) //非头插
        head = head->next;
    if(index != size) 
        newNode->next = head->next; 
    //链表尾部next不需指定
    head->next = newNode; 
    return 1;
}

按值删除：

void deleteList(Node ** list, int data) 
{ 
    Node * head = *list; Node * temp; 
    while(head->next!=NULL) 
    { 
        if(head->next->data != data) 
        { 
            head=head->next; 
            continue; 
        } 
        temp = head->next;
        if(head->next->next == NULL) //尾节点删除
            head->next = NULL; 
        else 
            head->next = temp->next; 
        free(temp);
    }    
    head = *list; 
    if(head->data == data) //头结点删除
    { 
        temp = head; 
        *list = head->next; 
        head = head->next; 
        free(temp); 
    }
}

打印：

void printList(Node * head) 
{ 
    Node * temp = head; 
    for(; temp != NULL; temp=temp->next) 
        printf("%d ", temp->data); 
    printf("\n"); 
}

清空：

void freeList(Node ** list) 
{ 
    Node * head = *list; 
    Node * temp = NULL; 
    while(head != NULL) //依次释放
    { 
        temp = head; 
        head = head->next; 
        free(temp); 
    } 
    *list = NULL; //置空
}

别的也没啥了，都是基本操作

有些代码要分情况，很麻烦，可读性较强吧

看我压缩代码：https://blog.csdn.net/hebtu666/article/details/81261043

 

双链表带头实现

以前写的不带头的单链表实现，当时也啥也没学，好多东西不知道，加上一心想压缩代码，减少情况，所以写得不太好。

请教了老师，首先是命名问题和代码紧凑性等的改进。还有可读性方面的改进，多写了一些注释。并且因为带头的比较好写，好操作，所以标准写法也不是很长，繁琐。

 

 

下面贴代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node{
    int key;//数据
    struct node * prev;//前驱
    struct node * next;//后继
}Node;

初始化（带头） 

Node * list;
//初始化，这里·我们list不再是NULL，而是指向了一个节点
//这个改进方便了很多操作，也不用借助二重指针把list和next统一表示了

void init(Node * list)//初始化
{
    list = (Node *)malloc(sizeof(Node));
    list->next = NULL;
    list->prev = NULL;
}

查找（不用再判断一下空不空）

Node * find(int key,Node * list)
{
    Node * head = list->next;//从头节点后面开始找
    while(head != NULL && head->key != key)//找到或空跳出
        head = head->next;
    return head;
}

打印

void printList(Node * list)//打印
{
    Node * temp = list->next;头节点下一个开始
    while(temp != NULL)
    {
        printf("%d ",temp->key);
        temp = temp->next;
    }
    printf("\n");
}

删除指定结点

void delete(Node * list)//删除指定结点
{
    list->prev->next = list->next;前面后面指针改了，再free自己即可
    list->next->prev = list->prev;
    free(list);
}

配合一下删除：

void deleteKey(int key,Node * list)
{
    delete(find(key,list));
}

头插：

void insertHead(int key,Node * list)//头插
{
    Node * newNode = (Node *)malloc(sizeof(Node));//初始化
    newNode->key = key;
    newNode->next = list->next;//赋值后继
    if(list->next != NULL)//如果有后继，赋值后继的前指针为新结点
        list->next->prev = newNode;
    list->next = newNode;//改头
    newNode->prev = list;//赋值新结点前指针
}

按下标插入

单链表都写了，我就不写长度函数和判断非法了，用的时候注意吧。

void insert(int key,Node * list,int index)
{
    Node * head=list;//最后指到要插位置的前一个即可
    Node * newNode = (Node *)malloc(sizeof(Node));//初始化
    newNode->key = key;
    while(index--)
        head = head->next;
    newNode->next = head->next;//修改指针
    newNode->prev = head;
    head->next = newNode;
}

指定某值后插入不写了，和这个修改指针逻辑一样，再传一个find配合一下就行了。

 

然后简单测试

int main()
{
    Node * list = NULL;
    init(list);
    insertHead(1,list);
    insertHead(2,list);
    insertHead(3,list);
    printList(list);
    deleteKey(2,list);
    printList(list);
    insert(10,list,0);
    printList(list);
}

 

第七次笔记（栈/队列）

 

介绍栈和队列基本概念和用法。

 

设输入序列1、2、3、4，则下述序列中（ ）不可能是出栈序列。【中科院中国科技大学2005】

A. 1、2、3、4                      B. 4、 3、2、1

C. 1、3、4、2                      D.４、1、2、3

选D

我是一个个模拟来做的。

 

描述栈的基本型性质：

1、集合性：栈是由若干个元素集合而成，没有元素（空集）成为空栈。

2、线性：除栈顶和栈底之外，任意元素均有唯一前趋和后继。

3、运算受限：只在一端插入删除的线性表即为栈

 

顺序存储和顺序存取：顺序存取是只能逐个存或取结构中的元素，例如栈。顺序存储是利用一个连续的空间相继存放，例如栈可基于一维数组存放元素。

 

一个较早入栈的元素能否在后面元素之前出栈？如果后面元素压在它上面，就不可以了。如果后面元素未压入，它可以弹出。在其他元素前面。

 

 

栈与递归：

  当在一个函数的运行期间调用另一个函数时，在运行 该被调用函数之前，需先完成三件事：  将实参等传递给被调用函数，保存返回地址（入栈）；  为被调用函数的局部变量分配存储区；    将控制转移到被调用函数的入口。  

从被调用函数返回调用函数之前，应该完成：  保存被调函数的计算结果；  释放被调函数的数据区；  按被调函数保存的返回地址（出栈）将控制转移到调        用函数。

多个函数嵌套调用的规则是：后调用先返回。

 此时的内存管理实行“栈式管理”

 

队列：

        在多用户计算机系统中，各个用户需要使用 CPU 运行自己的程序，它们分别向操作系统提出使用 CPU 的请求，操作系统按照每个请求在时间上的先后顺序， 将其排成一个队列，每次把CPU分配给队头用户使用， 当相应的程序运行结束，则令其出队，再把CPU分配 给新的队头用户，直到所有用户任务处理完毕。

 

以主机和打印机为例来说明，主机输出数据给打印 机打印，主机输出数据的速度比打印机打印的速度要快 得多，若直接把输出的数据送给打印机打印，由于速度 不匹配，显然不行。解决的方法是设置一个打印数据缓 冲区，主机把要打印的数据依此写到这个缓冲区中，写 满后就暂停输出，继而去做其它的事情，打印机就从缓 冲区中按照先进先出的原则依次取出数据并打印，打印 完后再向主机发出请求，主机接到请求后再向缓冲区写 入打印数据，这样利用队列既保证了打印数据的正确， 又使主机提高了效率。

 

双端队列：

某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，若元素a,b,c,d,e依次入队列后，再进行出队操作，则不可能得到的顺序是（ ）。 

A. bacde                B. dbace              C. dbcae                D. ecbad

解析：出队只能一端，所以abcde一定是这个顺序。

反模拟入队，每次只能在两边出元素。

 

栈/队列 互相模拟实现

 

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

思路：大概这么想：用一个辅助栈把进第一个栈的元素倒一下就好了。

比如进栈1，2，3，4，5

第一个栈：

5

4

3

2

1

然后倒到第二个栈里

1

2

3

4

5

再倒出来，顺序为1，2，3，4，5

实现队列

然后要注意的事情：

1）栈2非空不能往里面倒数，顺序就错了。栈2没数再从栈1倒。

2）栈1要倒就一次倒完，不倒完的话，进新数也会循序不对。

import java.util.Stack;
 
public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
     
    public void push(int node) {
        stack1.push(node);
    }
     
    public int pop() {
        if(stack1.empty()&&stack2.empty()){
            throw new RuntimeException("Queue is empty!");
        }
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

 

用两个队列实现栈，要求同上：

这其实意义不是很大，有些数据结构书上甚至说两个队列不能实现栈。

其实是可以的，只是时间复杂度较高，一个弹出操作时间为O(N)。

思路：两个队列，编号为1和2.

进栈操作：进1号队列

出栈操作：把1号队列全弄到2号队列里，剩最后一个别压入，而是返回。

最后还得把1和2号换一下，因为现在是2号有数，1号空。

 

仅仅有思考价值，不实用。

比如压入1，2，3

队列1：1，2，3

队列2：空

依次弹出1，2，3：

队列1里的23进入2号，3弹出

队列1：空

队列2：2，3

 

队列2中3压入1号，2弹出

队列1：3

队列2：空

 

队列1中只有一个元素，弹出。

 

上代码：

public class TwoQueueImplStack {
	Queue<Integer> queue1 = new ArrayDeque<Integer>();
	Queue<Integer> queue2 = new ArrayDeque<Integer>();
//压入
	public void push(Integer element){
		//都为空，优先1
		if(queue1.isEmpty() && queue2.isEmpty()){
			queue1.add(element);
			return;
		}
		//1为空，2有数据，放入2
		if(queue1.isEmpty()){
			queue2.add(element);
			return;
		}
		//2为空，1有数据，放入1
		if(queue2.isEmpty()){
			queue1.add(element);
			return;
		}
	}
//弹出
	public Integer pop(){
		//两个都空，异常
		if(queue1.isEmpty() && queue2.isEmpty()){
			try{
				throw new Exception("satck is empty!");
			}catch(Exception e){
				e.printStackTrace();
			}
		}	
		//1空，2有数据，将2中的数据依次放入1，最后一个元素弹出
		if(queue1.isEmpty()){
			while(queue2.size() > 1){
				queue1.add(queue2.poll());
			}
			return queue2.poll();
		}
		
		//2空，1有数据，将1中的数据依次放入2，最后一个元素弹出
		if(queue2.isEmpty()){
			while(queue1.size() > 1){
				queue2.add(queue1.poll());
			}
			return queue1.poll();
		}
		
		return (Integer)null;
	}
//测试
	public static void main(String[] args) {
		TwoQueueImplStack qs = new TwoQueueImplStack();
		qs.push(2);
		qs.push(4);
		qs.push(7);
		qs.push(5);
		System.out.println(qs.pop());
		System.out.println(qs.pop());
		
		qs.push(1);
		System.out.println(qs.pop());
	}
}

 

第八次笔记 （串）

串的概念：串（字符串）：是由 0 个或多个字符组成的有限序列。 通常记为：s =‘ a1 a2 a3 … ai …an  ’ ( n≥0 )。

串的逻辑结构和线性表极为相似。

 

一些串的类型：

 

空串：不含任何字符的串，长度 = 0。

空格串：仅由一个或多个空格组成的串。

子串：由串中任意个连续的字符组成的子序列。

主串：包含子串的串。

位置：字符在序列中的序号。

子串在主串中的位置：子串的首字符在主串中的位置。

 

空串是任意串的子串，任意串是其自身的子串。

串相等的条件：当两个串的长度相等且各个对应位置的字符都相等时才相等。

 

实现：

 

因为串是特殊的线性表，故其存储结构与线性表的 存储结构类似，只不过组成串的结点是单个字符。

 

定长顺序存储表示

也称为静态存储分配的顺序串。 即用一组地址连续的存储单元依次存放串中的字符序列。

 

串长：可能首字符记录（显式）或\0结尾（隐式）

 

定长顺序存储表示时串操作的缺点 ：串的某些操作受限（截尾），如串的联接、插入、置换

 

堆分配存储表示  

 

存储空间在程序执行过程中动态分配，malloc() 分配一块实际串长所需要的存储空间（“堆”）

堆存储结构的优点：堆存储结构既有顺序存储 结构的特点，处理（随机取子串）方便，操作中对 串长又没有任何限制，更显灵活，因此在串处理的 应用程序中常被采用。

 

串的块链存储表示

为了提高空间利用率，可使每个结点存放多个字符 （这是顺序串和链串的综合 (折衷) ），称为块链结构。

 优点：便于插入和删除    缺点：空间利用率低 

 

串的定长表示

思想和代码都不难，和线性表也差不多，串本来就是数据受限的线性表。

串连接：

 

#include <stdio.h>
#include <string.h>
//串的定长顺序存储表示
#define MAXSTRLEN 255							//用户可在255以内定义最大串长
typedef unsigned char SString[MAXSTRLEN + 1];	//0号单元存放串的长度

int Concat(SString *T,SString S1,SString S2)
	//用T返回S1和S2联接而成的新串。若未截断返回1，若截断返回0
{
	int i = 1,j,uncut = 0;
	if(S1[0] + S2[0] <= MAXSTRLEN)	//未截断
	{
		for (i = 1; i <= S1[0]; i++)//赋值时等号不可丢
			(*T)[i] = S1[i];
		for (j = 1; j <= S2[0]; j++)
			(*T)[S1[0]+j] = S2[j];	//(*T)[i+j] = S2[j]
		(*T)[0] = S1[0] + S2[0];
		uncut = 1;
	}
	else if(S1[0] < MAXSTRLEN)		//截断
	{
		for (i = 1; i <= S1[0]; i++)//赋值时等号不可丢
			(*T)[i] = S1[i];

		for (j = S1[0] + 1; j <= MAXSTRLEN; j++)
		{
			(*T)[j] = S2[j - S1[0] ];
			(*T)[0] = MAXSTRLEN;
			uncut = 0;
		}
	}
	else
	{
		for (i = 0; i <= MAXSTRLEN; i++)
			(*T)[i] = S1[i];
		/*或者分开赋值，先赋值内容，再赋值长度
		for (i = 1; i <= MAXSTRLEN; i++)
			(*T)[i] = S1[i];
		(*T)[0] = MAXSTRLEN;
		*/
		uncut = 0;
	}

	return uncut;
}

int SubString(SString *Sub,SString S,int pos,int len)
	//用Sub返回串S的第pos个字符起长度为len的子串
	//其中，1 ≤ pos ≤ StrLength(S)且0 ≤ len ≤ StrLength(S) - pos + 1(从pos开始到最后有多少字符)
	//第1个字符的下标为1,因为第0个字符存放字符长度
{
	int i;
	if(pos < 1 || pos > S[0] || len < 0 || len > S[0] - pos + 1)
		return 0;
	for (i = 1; i <= len; i++)
	{
		//S中的[pos,len]的元素 -> *Sub中的[1,len]
		(*Sub)[i] = S[pos + i - 1];//下标运算符 > 寻址运算符的优先级
	}
	(*Sub)[0] = len;
	return 1;
}
void PrintStr(SString S)
{
	int i;
	for (i = 1; i <= S[0]; i++)
		printf("%c",S[i]);
	printf("\n");
}


int main(void)
{
	/*定长顺序存储初始化和打印的方法
	SString s = {4,'a','b','c','d'};
	int i;
	//s = "abc";	//不可直接赋值
	for (i = 1; i <= s[0]; i++)
		printf("%c",s[i]);
	*/
	SString s1 = {4,'a','b','c','d'};
	SString s2 = {4,'e','f','g','h'},s3;
	SString T,Sub;
	int i;
	
	for (i = 1; i <= 255; i++)
	{
		s3[i] = 'a';
		if(i >= 248)
			s3[i] = 'K';
	}
	s3[0] = 255;
	SubString(&Sub,s3,247,8);
	PrintStr(Sub);
	



	return 0;
}

第九次笔记（数组，广义表）

数组：按一定格式排列起来的具有相同类型的数据元素的集合。

 

二维数组：若一维数组中的数据元素又是一维数组结构，则称为二维数组。 

同理，推广到多维数组。若 n -1 维数组中的元素又是一个一维数组结构，则称作 n 维数组。 

声明格式：数据类型   变量名称[行数] [列数] ；

 

实现：一般都是采用顺序存储结构来表示数组。

 

二维数组两种顺序存储方式：以行序为主序 (低下标优先) 、以列序为主序 (高下标优先)

一个二维数组 A，行下标的范围是 1 到 6，列下标的范围是 0 到 7，每个数组元素用相邻的6 个字节存储，存储器按字节编址。那么，这个数组的体积是288个字节。

 

 广义表（又称列表 Lists）是n≥0个元素 a1, a2, …, an 的有限序列，其中每一个ai 或者是原子，或者是一个子表。

 

表头：若 LS 非空 (n≥1 )，则其第一个元素 a1 就是表头。

 表尾：除表头之外的其它元素组成的表。记作  tail(LS) = (a2, ..., an)。 

 

(( )) 长度为 1，表头、表尾均为 ( )

(a, (b, c))长度为 2，由原子 a 和子表 (b, c) 构成。表头为 a ；表尾为 ((b, c))。

 

广义表的长度定义为最外层所包含元素的个数

广义表的深度定义为该广义表展开后所含括号的重数。

“原子”的深度为 0 ;  “空表”的深度为 1 。

 

取表头运算 GetHead  和取表尾运算 GetTail

GetHead(LS) = a1        GetTail(LS) = (a2, …, an)。

 

广义表可看成是线性表的推广，线性表是广义表的特例。

 

广义表的结构相当灵活，在某种前提下，它可以兼容线 性表、数组、树和有向图等各种常用的数据结构。

由于广义表不仅集中了线性表、数组、树和有向图等常 见数据结构的特点，而且可有效地利用存储空间，因此在计算机的许多应用领域都有成功使用广义表的实例。 

 

 

第十次笔记（树和二叉树）

树

 

树的定义：树(Tree)是 n(n≥0)个结点的有限集。若 n=0，称为空树；若 n > 0，则它满足如下两个条件：  

(1)  有且仅有一个特定的称为根 (Root) 的结点；  

(2)  其余结点可分为 m (m≥0) 个互不相交的有限集 T1, T2, T3, …, Tm， 其中每一个集合本身又是一棵树，并称为根的子树 (SubTree)。

显然，树的定义是一个递归的定义。

树的一些术语：

• 结点的度（Degree）：结点的子树个数；
• 树的度：树的所有结点中最大的度数；
• 叶结点（Leaf）：度为0的结点；
• 父结点（Parent）：有子树的结点是其子树的根节点的父结点；
• 子结点/孩子结点（Child）：若A结点是B结点的父结点，则称B结点是A结点的子结点；
• 兄弟结点（Sibling）：具有同一个父结点的各结点彼此是兄弟结点；
• 路径和路径长度：从结点n1到nk的路径为一个结点序列n1，n2，...，nk。ni是ni+1的父结点。路径所包含边的个数为路径的长度；
• 祖先结点（Ancestor）：沿树根到某一结点路径上的所有结点都是这个结点的祖先结点；
• 子孙结点（Descendant）：某一结点的子树中的所有结点是这个结点的子孙；
• 结点的层次（Level）：规定根结点在1层，其他任一结点的层数是其父结点的层数加1；
• 树的深度（Depth）：树中所有结点中的最大层次是这棵树的深度；

将树中节点的各子树看成从左至右是有次序的（即不能互换），则称为该树是有序树，否则称为无序树。

森林(forest)是 m (m≥0) 棵互不相交的树的集合。

 

二叉树

 

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

 

虽然二叉树与树概念不同，但有关树的基本术语对二叉树都适用。

 

二叉树结点的子树要区分左子树和右子树，即使只有一 棵子树也要进行区分，说明它是左子树，还是右子树。树当 结点只有一个孩子时，就无须区分它是左还是右。

 

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

一些性质：

在二叉树的第 i 层上至多有  个结点 (i ≥1)。

证明：每个节点至多两个孩子，每一层至多比上一层多一倍的结点，根为1.

 

深度为 k 的二叉树至多有 个结点（k ≥1)。

证明：把每一层最大节点加起来即可

 

对任何一棵二叉树 T，如果其叶子数为 n0，度为 2的结点数为 n2，则 n0 = n2 + 1。

证明：对于一个只有根的树，n0 = n2 + 1成立。1=0+1

我们把一个叶子节点换成度为2的结点：

黑色节点原来为叶子节点

我们发现，度为2的结点数加1（黑色节点）；叶子节点数加1（原来的去掉，新增两个）；对于式子n0 = n2 + 1没影响，还是成立。

 

我们把叶子节点换成度为1的结点，比如没有右孩子。

我们发现，度为2的结点数没变。叶子节点数没变（减了一个加了一个）

所以，不管你怎么换，公式都成立。（佛系证明）

 

 

二叉树概述

 

各种实现和应用以后放链接

一、二叉树的基本概念

二叉树：二叉树是每个节点最多有两个子树的树结构。

根节点：一棵树最上面的节点称为根节点。

父节点、子节点：如果一个节点下面连接多个节点，那么该节点称为父节点，它下面的节点称为子 节点。

叶子节点：没有任何子节点的节点称为叶子节点。

兄弟节点：具有相同父节点的节点互称为兄弟节点。

节点度：节点拥有的子树数。上图中，13的度为2，46的度为1，28的度为0。

树的深度：从根节点开始（其深度为0）自顶向下逐层累加的。上图中，13的深度是1，30的深度是2，28的深度是3。

树的高度：从叶子节点开始（其高度为0）自底向上逐层累加的。54的高度是2，根节点23的高度是3。

对于树中相同深度的每个节点来说，它们的高度不一定相同，这取决于每个节点下面的叶子节点的深度。上图中，13和54的深度都是1，但是13的高度是1，54的高度是2。

二、二叉树的类型

类型	定义	图示
满二叉树 Full Binary Tree	除最后一层无任何子节点外，每一层上的所有节点都有两个子节点，最后一层都是叶子节点。满足下列性质： 1）一颗树深度为h，最大层数为k，深度与最大层数相同，k=h； 2）叶子节点数（最后一层）为2k−1； 3）第 i 层的节点数是：2i−1； 4）总节点数是：2k−1，且总节点数一定是奇数。
完全二叉树 Complete Binary Tree	若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。满足下列性质： 1）只允许最后一层有空缺结点且空缺在右边，即叶子节点只能在层次最大的两层上出现； 2）对任一节点，如果其右子树的深度为j，则其左子树的深度必为j或j+1。 即度为1的点只有1个或0个； 3）除最后一层，第 i 层的节点数是：2i−1； 4）有n个节点的完全二叉树，其深度为：log2n+1或为log2n+1； 5）满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。
平衡二叉树 Balanced Binary Tree	又被称为AVL树，它是一颗空树或左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。
二叉搜索树 Binary Search Tree	又称二叉查找树、二叉排序树（Binary Sort Tree）。它是一颗空树或是满足下列性质的二叉树： 1）若左子树不空，则左子树上所有节点的值均小于或等于它的根节点的值； 2）若右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值； 3）左、右子树也分别为二叉排序树。
红黑树 Red Black Tree	是每个节点都带有颜色属性（颜色为红色或黑色）的自平衡二叉查找树，满足下列性质： 1）节点是红色或黑色； 2）根节点是黑色； 3）所有叶子节点都是黑色； 4）每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。) 5）从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

 

 

 

 

 

 

 

 

 

啦啦啦

 

 

第十一次笔记（满二叉树，完全二叉树）

因为图片丢失，内容不全，我尽量找一下图

满二叉树 (Full binary tree)

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。

国内教程定义：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

国外(国际)定义:a binary tree T is full if each node is either a leaf or possesses exactly two childnodes.

大意为：如果一棵二叉树的结点要么是叶子结点，要么它有两个子结点，这样的树就是满二叉树。(一棵满二叉树的每一个结点要么是叶子结点，要么它有两个子结点，但是反过来不成立，因为完全二叉树也满足这个要求，但不是满二叉树)

从图形形态上看，满二叉树外观上是一个三角形。

这里缺失公式

完全二叉树

 

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，则 ：

①n= n0+n1+n2 （其中n为完全二叉树的结点总数）；又因为一个度为2的结点会有2个子结点，一个度为1的结点会有1个子结点，除根结点外其他结点都有父结点，

②n= 1+n1+2*n2 ；由①、②两式把n2消去得：n= 2*n0+n1-1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0=n/2 或 n0=(n+1)/2。

简便来算，就是 n0=n/2，其中n为奇数时（n1=0）向上取整；n为偶数时（n1=1）。可根据完全二叉树的结点总数计算出叶子结点数。

 

重点：出于简便起见,完全二叉树通常采用数组而不是链表存储

 

对于tree[i]，有如下特点：

（1）若i为奇数且i>1，那么tree的左兄弟为tree[i-1]；

（2）若i为偶数且i<n，那么tree的右兄弟为tree[i+1]；

（3）若i>1，tree的父亲节点为tree[i div 2]；

（4）若2*i<=n，那么tree的左孩子为tree[2*i]；若2*i+1<=n，那么tree的右孩子为tree[2*i+1]；

（5）若i>n div 2,那么tree[i]为叶子结点（对应于（3））；

（6）若i<(n-1) div 2.那么tree[i]必有两个孩子（对应于（4））。

（7）满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

完全二叉树第i层至多有2^（i-1）个节点，共i层的完全二叉树最多有2^i-1个节点。

特点：

1）只允许最后一层有空缺结点且空缺在右边，即叶子结点只能在层次最大的两层上出现；

2）对任一结点，如果其右子树的深度为j，则其左子树的深度必为j或j+1。 即度为1的点只有1个或0个

 

第十二次笔记（二叉树的存储和遍历）

 

顺序存储结构

 

完全二叉树：用一组地址连续的 存储单元依次自上而下、自左至右存 储结点元素，即将编号为 i  的结点元 素存储在一维数组中下标为 i –1 的分量中。

一般二叉树：将其每个结点与完 全二叉树上的结点相对照，存储在一 维数组的相应分量中。

 

最坏情况：树退化为线性后：

我们要把它“变”成这个大家伙来存了：

深度为 k 的且只 有 k 个结点的右单支树需要 长度为2^k-1 的一维数组。 

 

链式存储结构

lchild和rchild都是指向相同结构的指针

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

typedef struct BiTNode { // 结点结构
    TElemType data;
    struct BiTNode *lchild,*rchild;// 左右孩子指针
} BiTNode, *BiTree;

可以多一条指向父的指针。

 

遍历二叉树

 

顺着某一条搜索路径巡访二叉树中的结点，使   得每个结点均被访问一次，而且仅被访问一次

 “访问”的含义很广，可以是对结点作各种处理， 如：输出结点的信息、修改结点的数据值等，但要求这种访问不破坏原来的数据结构。

（所以有些题目比如morris遍历、链表后半段反转判断回文等等必须进行完，解题时就算已经得出答案也要遍历完，因为我们不能改变原来的数据结构。）

 

具体遍历的介绍

https://blog.csdn.net/hebtu666/article/details/82853988

 

深入理解二叉树遍历

二叉树：二叉树是每个节点最多有两个子树的树结构。

 

本文介绍二叉树的遍历相关知识。

我们学过的基本遍历方法，无非那么几个：前序，中序，后序，还有按层遍历等等。

设L、D、R分别表示遍历左子树、访问根结点和遍历右子树， 则对一棵二叉树的遍历有三种情况：DLR（称为先根次序遍历），LDR（称为中根次序遍历），LRD （称为后根次序遍历）。

首先我们定义一颗二叉树

typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

前序

首先访问根，再先序遍历左（右）子树，最后先序遍历右（左）子树

思路：

就是利用函数，先打印本个节点，然后对左右子树重复此过程即可。

void PreorderTraversal( BinTree BT )
{
    if(BT==NULL)return ;
    printf(" %c", BT->Data);
    PreorderTraversal(BT->Left);
    PreorderTraversal(BT->Right);
}

 

中序

首先中序遍历左（右）子树，再访问根，最后中序遍历右（左）子树

思路：

还是利用函数，先对左边重复此过程，然后打印根，然后对右子树重复。

void InorderTraversal( BinTree BT )
{
    if(BT==NULL)return ;
    InorderTraversal(BT->Left);
    printf(" %c", BT->Data);
    InorderTraversal(BT->Right);
}

后序

首先后序遍历左（右）子树，再后序遍历右（左）子树，最后访问根

思路：

先分别对左右子树重复此过程，然后打印根

void PostorderTraversal(BinTree BT)
{
    if(BT==NULL)return ;
    PostorderTraversal(BT->Left);
    PostorderTraversal(BT->Right);
    printf(" %c", BT->Data);
}

进一步思考

看似好像很容易地写出了三种遍历。。。。。

 

但是你真的理解为什么这么写吗？

比如前序遍历，我们真的是按照定义里所讲的，首先访问根，再先序遍历左（右）子树，最后先序遍历右（左）子树。这种过程来遍历了一遍二叉树吗？

仔细想想，其实有一丝不对劲的。。。

再看代码：

void Traversal(BinTree BT)//遍历
{
//1111111111111
    Traversal(BT->Left);
//22222222222222
    Traversal(BT->Right);
//33333333333333
}

为了叙述清楚，我给三个位置编了号 1，2，3

我们凭什么能前序遍历，或者中序遍历，后序遍历？

我们看，前序中序后序遍历，实现的代码其实是类似的，都是上面这种格式，只是我们分别在位置1，2，3打印出了当前节点而已啊。我们凭什么认为，在1打印，就是前序，在2打印，就是中序，在3打印，就是后序呢？不管在位置1，2，3哪里操作，做什么操作，我们利用函数遍历树的顺序变过吗？当然没有啊。。。

都是三次返回到当前节点的过程：先到本个节点，也就是位置1，然后调用了其他函数，最后调用完了，我们开到了位置2。然后又调用别的函数，调用完了，我们来到了位置3.。然后，最后操作完了，这个函数才结束。代码里的三个位置，每个节点都被访问了三次。

而且不管位置1，2，3打印了没有，操作了没有，这个顺序是永远存在的，不会因为你在位置1打印了，顺序就改为前序，你在位置2打印了，顺序就成了中序。

 

为了有更直观的印象，我们做个试验：在位置1，2，3全都放入打印操作；

我们会发现，每个节点都被打印了三次。而把每个数第一次出现拿出来，就组成了前序遍历的序列；所有数字第二次出现拿出来，就组成了中序遍历的序列。。。。

 

其实，遍历是利用了一种数据结构：栈

而我们这种写法，只是通过函数，来让系统帮我们压了栈而已。为什么能实现遍历？为什么我们访问完了左子树，能返回到当前节点？这都是栈的功劳啊。我们把当前节点（对于函数就是当时的现场信息）存到了栈里，记录下来，后来才能把它拿了出来，能回到以前的节点。

 

想到这里，可能就有更深刻的理解了。

我们能否不用函数，不用系统帮我们压栈，而是自己做一个栈，来实现遍历呢？

先序实现思路：拿到一个节点的指针，先判断是否为空，不为空就先访问（打印）该结点，然后直接进栈，接着遍历左子树；为空则要从栈中弹出一个节点来，这个时候弹出的结点就是其父亲，然后访问其父亲的右子树，直到当前节点为空且栈为空时，结束。

核心思路代码实现：

*p=root;
while(p || !st.empty())
{
    if(p)//非空
    {
        //visit(p);进行操作
        st.push(p);//入栈
        p = p->lchild;左
    } 
    else//空
    {
        p = st.top();//取出
        st.pop();
        p = p->rchild;//右
    }
}

中序实现思路：和前序遍历一样，只不过在访问节点的时候顺序不一样，访问节点的时机是从栈中弹出元素时访问，如果从栈中弹出元素，就意味着当前节点父亲的左子树已经遍历完成，这时候访问父亲，就是中序遍历.

（对应递归是第二次遇到）

核心代码实现：

*p=root;
while(p || !st.empty())
{
    if(p)//非空
    {
        st.push(p);//压入
        p = p->lchild;
    }
    else//空
    {
        p = st.top();//取出
        //visit(p);操作
        st.pop();
        p = p->rchild;
    }
}

后序遍历是最难的。因为要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，这就为流程的控制带来了难点。

因为我们原来说了，后序是第三次遇到才进行操作的，所以我们很容易有这种和递归函数类似的思路：对于任一结点，将其入栈，然后沿其左子树一直往下走，一直走到没有左孩子的结点，此时该结点在栈顶，但是不能出栈访问， 因此右孩子还没访问。所以接下来按照相同的规则对其右子树进行相同的处理。访问完右孩子，该结点又出现在栈顶，此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶。

第二种思路：对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，或者左孩子和右孩子都已被访问过了，就可以直接访问该结点。如果有孩子未访问，将P的右孩子和左孩子依次入栈。

网上的思路大多是第一种，所以我在这里给出第二种的大概实现吧

首先初始化cur，pre两个指针，代表访问的当前节点和之前访问的节点。把根放入，开始执行。

s.push(root);
while(!s.empty())
{
    cur=s.top();
    if((cur->lchild==NULL && cur->rchild==NULL)||(pre!=NULL && (pre==cur->lchild||pre==cur->rchild)))
    {
        //visit(cur);  如果当前结点没有孩子结点或者孩子节点都已被访问过 
        s.pop();//弹出
        pre=cur; //记录
    }
    else//分别放入右左孩子
    {
        if(cur->rchild!=NULL)
            s.push(cur->rchild);
        if(cur->lchild!=NULL)    
            s.push(cur->lchild);
    }
}

这两种方法，都是利用栈结构来实现的遍历，需要一定的栈空间，而其实存在一种时间O(N),空间O(1)的遍历方式，下次写了我再放链接。

 

斗个小机灵：后序是LRD，我们其实已经知道先序是DLR，那其实我们可以用先序来实现后序啊，我们只要先序的时候把左右子树换一下：DRL（这一步很好做到），然后倒过来不就是DRL了嘛。。。。。就把先序代码改的左右反过来，然后放栈里倒过来就好了，不需要上面介绍的那些复杂的方法。。。。

第十四次笔记（树的存储）

 

 

父节点表示法

 

数据域：存放结点本身信息。

双亲域：指示本结点的双亲结点在数组中的位置。

对应的树：

/* 树节点的定义 */
#define MAX_TREE_SIZE 100
 
typedef struct{
    TElemType data;
    int parent; /* 父节点位置域 */
} PTNode;
 
typedef struct{
    PTNode nodes[MAX_TREE_SIZE];
    int n; /* 节点数 */
} PTree;

特点：找双亲容易，找孩子难。

孩子表示法（树的链式存储结构）

 

childi指向一个结点

可以加上parent。

在有 n 个结点、度为  d 的树的 d 叉链表中，有  n×(d－1)＋1 个空链域

 

我们可以用degree记录有几个孩子，省掉空间，但是结点的指针个数不相等，为该结点的度 degree。

 

孩子链表：

 

把每个结点的孩子结点排列起来，看成是一个线性表，用单链表存储，则 n 个结点有 n 个孩子链表（叶子的孩子链表为空表）。而 n 个头指针又组成一个线性表，用顺序表（含 n 个元素的结构数组）存储。

孩子兄弟表示法（二叉树表示法）

用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点

typedef struct CSNode{
     ElemType data;
     struct CSNode *firstchild, *nextsibling;  
} CSNode, *CSTree;

第十五次笔记（图基础）

 

图是一种：   数据元素间存在多对多关系的数据结构   加上一组基本操作构成的抽象数据类型。

图 (Graph) 是一种复杂的非线性数据结构，由顶点集合及顶点间的关系（也称弧或边）集合组成。可以表示为： G＝(V, VR)  

其中 V 是顶点的有穷非空集合；

VR 是顶点之间   关系的有穷集合，也叫做弧或边集合。

弧是顶点的有序对，边是顶点的无序对。

 

特点：（相对于线性结构）

顶点之间的关系是任意的 

图中任意两个顶点之间都可能相关

顶点的前驱和后继个数无限制

 

相关概念：

 

顶点(Vertex)：图中的数据元素。线性表中我们把数据元素叫元素，树中将数据元素叫结点。

边：顶点之间的逻辑关系用边来表示，边集可以是空的。

 

无向边(Edge)：若顶点V1到V2之间的边没有方向，则称这条边为无向边。

无向图(Undirected graphs)：图中任意两个顶点之间的边都是无向边。（A,D）=（D,A）

无向图中边的取值范围：0≤e≤n(n-1)/2

有向边：若从顶点V1到V2的边有方向，则称这条边为有向边，也称弧(Arc)。用<V1,V2>表示，V1为狐尾(Tail)，V2为弧头(Head)。（V1，V2）≠（V2，V1）。

有向图(Directed graphs)：图中任意两个顶点之间的边都是有向边。

有向图中弧的取值范围：0≤e≤n(n-1)

   注意：无向边用“（）”，而有向边用“< >”表示。

 

简单图：图中不存在顶点到其自身的边，且同一条边不重复出现。

无向完全图：无向图中，任意两个顶点之间都存在边。

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

稀疏图：有很少条边。

稠密图：有很多条边。

 

邻接点：若 (v, v´) 是一条边，则称顶点 v 和 v´互为 邻接点，或称 v 和 v´相邻接；称边 (v, v´) 依附于顶点 v 和 v´，或称 (v, v´) 与顶点 v 和 v´ 相关联。

 

权（Weight）：与图的边或弧相关的数。

网（Network）：带权的图。

子图（Subgraph）：假设G=（V,{E}）和G‘=（V',{E'}），如果V'包含于V且E'包含于E，则称G'为G的子图。

 

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

出度：有向图中以顶点 v 为尾的弧的数目称为 v 的出度，记为：OD(v)。

度（Degree）：无向图中，与顶点V相关联的边的数目。有向图中，入度表示指向自己的边的数目，出度表示指向其他边的数目，该顶点的度等于入度与出度的和。

 

回路（环）：第一个顶点和最后一个顶点相同的路径。

简单路径：序列中顶点（两端点除外）不重复出现的路径。 

简单回路（简单环）：前后两端点相同的简单路径。

路径的长度：一条路径上边或弧的数量。

 

连通：从顶点 v 到 v´ 有路径，则说 v  和 v´ 是连通的。

连通图：图中任意两个顶点都是连通的。

连通分量：无向图的极大连通子图（不存在包含它的 更大的连通子图）；

任何连通图的连通分量只有一个，即其本身；非连通图有多个连通分量（非连通图的每一个连通部分）。

强连通图： 任意两个顶点都连通的有向图。 

强连通分量：有向图的极大强连通子图；任何强连通 图的强连通分量只有一个，即其本身；非强连通图有多个 强连通分量。

 

生成树：所有顶点均由边连接在一起但不存在回路的图。（n个顶点n-1条边）

 

 

 

 

图的存储

 

多重链表：完全模拟图的样子，每个节点内的指针都指向该指向的节点。

节点结构内指针数为度

缺点：浪费空间、不容易操作

 

数组表示法（邻接矩阵表示法）

可用两个数组存储。其中一个 一维数组存储数据元素（顶点）的信息，另一个二维数组 （邻接矩阵）存储数据元素之间的关系（边或弧）的信息

有向图：

有向网：

缺点：用于稀疏图时空间浪费严重

优点：操作较容易

 

邻接表

指针数组存放每个结点，每个结点后接所有能到达的节点。

 

图的遍历

 

从图的任意指定顶点出发，依照某种规则去访问图中所有顶 点，且每个顶点仅被访问一次，这一过程叫做图的遍历。

图的遍历按照深度优先和广度优先规则去实施，通常有深度 优先遍历法（Depth_First Search——DFS ）和  广度优先遍历法 （ Breadth_Frist Search——BFS）两种。

简单棋盘搜索https://blog.csdn.net/hebtu666/article/details/81483407

别的实现以后再贴

如何判别V的邻接点是否被访问？

为每个顶点设立一个“访问标志”。

 

最小生成树

问题提出：
    要在n个城市间建立通信联络网。顶点：表示城市，权：城市间通信线路的花费代价。希望此通信网花费代价最小。
问题分析：
    答案只能从生成树中找，因为要做到任何两个城市之间有线路可达，通信网必须是连通的；但对长度最小的要求可以知道网中显然不能有圈，如果有圈，去掉一条边后，并不破坏连通性，但总代价显然减少了，这与总代价最小的假设是矛盾的。
结论：
    希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小 —— 最小代价生成树。
    构造最小生成树的算法很多，其中多数算法都利用了一种称之为 MST 的性质。
    MST 性质：设 N = (V, E)  是一个连通网，U是顶点集 V的一个非空子集。若边 (u, v) 是一条具有最小权值的边，其中u∈U，v∈V-U，则必存在一棵包含边 (u, v) 的最小生成树。

（1）普里姆 (Prim) 算法

算法思想： 
    ①设 N=(V, E)是连通网，TE是N上最小生成树中边的集合。
    ②初始令 U={u_0}, (u_0∈V), TE={ }。
    ③在所有u∈U，u∈U-V的边(u,v)∈E中，找一条代价最小的边(u_0,v_0 )。
    ④将(u_0,v_0 )并入集合TE，同时v_0并入U。
    ⑤重复上述操作直至U = V为止，则 T=(V,TE)为N的最小生成树。

 
代码实现：

void MiniSpanTree_PRIM(MGraph G,VertexType u)
    //用普里姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边。
    //记录从顶点集U到V-U的代价最小的边的辅助数组定义；
    //closedge[j].lowcost表示在集合U中顶点与第j个顶点对应最小权值
{
    int k, j, i;
    k = LocateVex(G,u);
    for (j = 0; j < G.vexnum; ++j)    //辅助数组的初始化
        if(j != k)
        {
            closedge[j].adjvex = u;
            closedge[j].lowcost = G.arcs[k][j].adj;    
//获取邻接矩阵第k行所有元素赋给closedge[j!= k].lowcost
        }
    closedge[k].lowcost = 0;        
//初始，U = {u};  
    PrintClosedge(closedge,G.vexnum);
    for (i = 1; i < G.vexnum; ++i)    \
//选择其余G.vexnum-1个顶点，因此i从1开始循环
    {
        k = minimum(G.vexnum,closedge);        
//求出最小生成树的下一个结点：第k顶点
        PrintMiniTree_PRIM(G, closedge, k);     //输出生成树的边
        closedge[k].lowcost = 0;                //第k顶点并入U集
        PrintClosedge(closedge,G.vexnum);
        for(j = 0;j < G.vexnum; ++j)
        {                                           
            if(G.arcs[k][j].adj < closedge[j].lowcost)    
//比较第k个顶点和第j个顶点权值是否小于closedge[j].lowcost
            {
                closedge[j].adjvex = G.vexs[k];//替换closedge[j]
                closedge[j].lowcost = G.arcs[k][j].adj;
                PrintClosedge(closedge,G.vexnum);
            }
        }
    }
}

（2）克鲁斯卡尔 (Kruskal) 算法

算法思想： 
    ①设连通网  N = (V, E )，令最小生成树初始状态为只有n个顶点而无边的非连通图，T=(V, { })，每个顶点自成一个连通分量。
    ②在 E 中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上（即：不能形成环），则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边。
③依此类推，直至 T 中所有顶点都在同一连通分量上为止。
      
    最小生成树可能不惟一！

 

拓扑排序

（1）有向无环图

    无环的有向图，简称 DAG (Directed Acycline Graph) 图。
 
有向无环图在工程计划和管理方面的应用：除最简单的情况之外，几乎所有的工程都可分为若干个称作“活动”的子工程，并且这些子工程之间通常受着一定条件的约束，例如：其中某些子工程必须在另一些子工程完成之后才能开始。
对整个工程和系统，人们关心的是两方面的问题： 
①工程能否顺利进行； 
②完成整个工程所必须的最短时间。
对应到有向图即为进行拓扑排序和求关键路径。 
AOV网： 
    用一个有向图表示一个工程的各子工程及其相互制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为顶点表示活动的网，简称AOV网(Activity On Vertex network)。
例如：排课表
      
AOV网的特点：
①若从i到j有一条有向路径，则i是j的前驱；j是i的后继。
②若< i , j >是网中有向边，则i是j的直接前驱；j是i的直接后继。
③AOV网中不允许有回路，因为如果有回路存在，则表明某项活动以自己为先决条件，显然这是荒谬的。

问题：    
    问题：如何判别 AOV 网中是否存在回路？
    检测 AOV 网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环。

拓扑排序的方法：
    ①在有向图中选一个没有前驱的顶点且输出之。
    ②从图中删除该顶点和所有以它为尾的弧。
    ③重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止。
        
    一个AOV网的拓扑序列不是唯一的！
代码实现：

Status TopologicalSort(ALGraph G)
    //有向图G采用邻接表存储结构。
    //若G无回路，则输出G的顶点的一个拓扑序列并返回OK，否则返回ERROR.
    //输出次序按照栈的后进先出原则，删除顶点，输出遍历
{
    SqStack S;
    int i, count;
    int *indegree1 = (int *)malloc(sizeof(int) * G.vexnum);
    int indegree[12] = {0};
    FindInDegree(G, indegree);    //求个顶点的入度下标从0开始
    InitStack(&S);
    PrintStack(S);
    for(i = 0; i < G.vexnum; ++i)
        if(!indegree[i])        //建0入度顶点栈S
            push(&S,i);        //入度为0者进栈
    count = 0;                //对输出顶点计数
    while (S.base != S.top)
    {
        ArcNode* p;
        pop(&S,&i);
        VisitFunc(G,i);//第i个输出栈顶元素对应的顶点，也就是最后进来的顶点    
        ++count;          //输出i号顶点并计数
        for(p = G.vertices[i].firstarc; p; p = p->nextarc)
        {    //通过循环遍历第i个顶点的表结点，将表结点中入度都减1
            int k = p->adjvex;    //对i号顶点的每个邻接点的入度减1
            if(!(--indegree[k]))
                push(&S,k);        //若入度减为0，则入栈
        }//for
    }//while
    if(count < G.vexnum)
    {
        printf("\n该有向图有回路!\n");
        return ERROR;    //该有向图有回路
    }
    else
    {
        printf("\n该有向图没有回路!\n");
        return OK;
    }
}

关键路径

    把工程计划表示为有向图，用顶点表示事件，弧表示活动，弧的权表示活动持续时间。每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。称这种有向图为边表示活动的网，简称为 AOE网 (Activity On Edge)。
例如：
设一个工程有11项活动，9个事件。
事件v_1——表示整个工程开始（源点） 
事件v_9——表示整个工程结束（汇点）

 
对AOE网，我们关心两个问题：  
①完成整项工程至少需要多少时间？ 
②哪些活动是影响工程进度的关键？
关键路径——路径长度最长的路径。
路径长度——路径上各活动持续时间之和。
v_i——表示事件v_i的最早发生时间。假设开始点是v_1，从v_1到〖v�i〗的最长路径长度。ⅇ(ⅈ)——表示活动a_i的最早发生时间。
l(ⅈ)——表示活动a_i最迟发生时间。在不推迟整个工程完成的前提下，活动a_i最迟必须开始进行的时间。
l(ⅈ)-ⅇ(ⅈ)意味着完成活动a_i的时间余量。
我们把l(ⅈ)=ⅇ(ⅈ)的活动叫做关键活动。显然，关键路径上的所有活动都是关键活动，因此提前完成非关键活动并不能加快工程进度。
    例如上图中网，从从v_1到v_9的最长路径是(v_1,v_2,v_5,v_8,ν_9 )，路径长度是18，即ν_9的最迟发生时间是18。而活动a_6的最早开始时间是5，最迟开始时间是8，这意味着：如果a_6推迟3天或者延迟3天完成，都不会影响整个工程的完成。因此，分析关键路径的目的是辨别哪些是关键活动，以便争取提高关键活动的工效，缩短整个工期。
    由上面介绍可知：辨别关键活动是要找l(ⅈ)=ⅇ(ⅈ)的活动。为了求ⅇ(ⅈ)和l(ⅈ)，首先应求得事件的最早发生时间vⅇ(j)和最迟发生时间vl(j)。如果活动a_i由弧〈j,k〉表示，其持续时间记为dut(〈j,k〉),则有如下关系：
ⅇ(ⅈ)= vⅇ(j)
l(ⅈ)=vl(k)-dut(〈j,k〉)
    求vⅇ(j)和vl(j)需分两步进行：
第一步：从vⅇ(0)=0开始向前递推
vⅇ(j)=Max{vⅇ(i)+dut(〈j,k〉)}   〈i,j〉∈T,j=1,2,…,n-1
其中，T是所有以第j个顶点为头的弧的集合。
第二步：从vl(n-1)=vⅇ(n-1)起向后递推
vl(i)=Min{vl(j)-dut(〈i,j〉)}  〈i,j〉∈S,i=n-2,…,0
其中，S是所有以第i个顶点为尾的弧的集合。
下面我们以上图AOE网为例，先求每个事件v_i的最早发生时间，再逆向求每个事件对应的最晚发生时间。再求每个活动的最早发生时间和最晚发生时间，如下面表格：
          
在活动的统计表中，活动的最早发生时间和最晚发生时间相等的，就是关键活动

关键路径的讨论：

①若网中有几条关键路径，则需加快同时在几条关键路径上的关键活动。      如：a11、a10、a8、a7。 
②如果一个活动处于所有的关键路径上，则提高这个活动的速度，就能缩短整个工程的完成时间。如：a1、a4。
③处于所有关键路径上的活动完成时间不能缩短太多，否则会使原关键路径变成非关键路径。这时必须重新寻找关键路径。如：a1由6天变成3天，就会改变关键路径。

关键路径算法实现：

int CriticalPath(ALGraph G)
{    //因为G是有向网，输出G的各项关键活动
    SqStack T;
    int i, j;    ArcNode* p;
    int k , dut;
    if(!TopologicalOrder(G,T))
        return 0;
    int vl[VexNum];
    for (i = 0; i < VexNum; i++)
        vl[i] = ve[VexNum - 1];        //初始化顶点事件的最迟发生时间
    while (T.base != T.top)            //按拓扑逆序求各顶点的vl值
    {
 
        for(pop(&T, &j), p = G.vertices[j].firstarc; p; p = p->nextarc)
        {
            k = p->adjvex;    dut = *(p->info);    //dut<j, k>
            if(vl[k] - dut < vl[j])
                vl[j] = vl[k] - dut;
        }//for
    }//while
    for(j = 0; j < G.vexnum; ++j)    //求ee,el和关键活动
    {
        for (p = G.vertices[j].firstarc; p; p = p->nextarc)
        {
            int ee, el;        char tag;
            k = p->adjvex;    dut = *(p->info);
            ee = ve[j];    el = vl[k] - dut;
            tag = (ee == el) ? '*' : ' ';
            PrintCriticalActivity(G,j,k,dut,ee,el,tag);
        }
    }
    return 1;
}

 

最短路 

最短路

    典型用途：交通网络的问题——从甲地到乙地之间是否有公路连通？在有多条通路的情况下，哪一条路最短？
 
    交通网络用有向网来表示：顶点——表示城市，弧——表示两个城市有路连通，弧上的权值——表示两城市之间的距离、交通费或途中所花费的时间等。
    如何能够使一个城市到另一个城市的运输时间最短或运费最省？这就是一个求两座城市间的最短路径问题。
    问题抽象：在有向网中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。最短路径与最小生成树不同，路径上不一定包含n个顶点，也不一定包含n - 1条边。
   常见最短路径问题：单源点最短路径、所有顶点间的最短路径
（1）如何求得单源点最短路径？
    穷举法：将源点到终点的所有路径都列出来，然后在其中选最短的一条。但是，当路径特别多时，特别麻烦；没有规律可循。
    迪杰斯特拉（Dijkstra）算法：按路径长度递增次序产生各顶点的最短路径。
路径长度最短的最短路径的特点：
    在此路径上，必定只含一条弧 <v_0, v_1>，且其权值最小。由此，只要在所有从源点出发的弧中查找权值最小者。
下一条路径长度次短的最短路径的特点：
①、直接从源点到v_2<v_0, v_2>（只含一条弧）；
②、从源点经过顶点v_1，再到达v_2<v_0, v_1>,<v_1, v_2>（由两条弧组成）
再下一条路径长度次短的最短路径的特点：
    有以下四种情况：
    ①、直接从源点到v_3<v_0, v_3>（由一条弧组成）；
    ②、从源点经过顶点v_1，再到达v_3<v_0, v_1>,<v_1, v_3>（由两条弧组成）；
    ③、从源点经过顶点v_2，再到达v_3<v_0, v_2>,<v_2, v_3>（由两条弧组成）；
    ④、从源点经过顶点v_1  ,v_2，再到达v_3<v_0, v_1>,<v_1, v_2>,<v_2, v_3>（由三条弧组成）；
其余最短路径的特点:    
    ①、直接从源点到v_i<v_0, v_i>（只含一条弧）；
    ②、从源点经过已求得的最短路径上的顶点，再到达v_i（含有多条弧）。
Dijkstra算法步骤：
    初始时令S={v_0},  T={其余顶点}。T中顶点对应的距离值用辅助数组D存放。
    D[i]初值：若<v_0, v_i>存在，则为其权值；否则为∞。 
    从T中选取一个其距离值最小的顶点v_j，加入S。对T中顶点的距离值进行修改：若加进v_j作中间顶点，从v_0到v_i的距离值比不加 vj 的路径要短，则修改此距离值。
    重复上述步骤，直到 S = V 为止。

算法实现：

void ShortestPath_DIJ(MGraph G,int v0,PathMatrix &P,ShortPathTable &D)
{ // 用Dijkstra算法求有向网 G 的 v0 顶点到其余顶点v的最短路径P[v]及带权长度D[v]。
    // 若P[v][w]为TRUE,则 w 是从 v0 到 v 当前求得最短路径上的顶点。  P是存放最短路径的矩阵，经过顶点变成TRUE
    // final[v]为TRUE当且仅当 v∈S,即已经求得从v0到v的最短路径。
    int v,w,i,j,min;
    Status final[MAX_VERTEX_NUM];
    for(v = 0 ;v < G.vexnum ;++v)
    {
        final[v] = FALSE;
        D[v] = G.arcs[v0][v].adj;        //将顶点数组中下标对应是 v0 和 v的距离给了D[v]
        for(w = 0;w < G.vexnum; ++w)
            P[v][w] = FALSE;            //设空路径
        if(D[v] < INFINITY)
        {
            P[v][v0] = TRUE;
            P[v][v] = TRUE;
        }
    }
    D[v0]=0;
    final[v0]= TRUE; /* 初始化,v0顶点属于S集 */
    for(i = 1;i < G.vexnum; ++i) /* 其余G.vexnum-1个顶点 */
    { /* 开始主循环,每次求得v0到某个v顶点的最短路径,并加v到S集 */
        min = INFINITY; /* 当前所知离v0顶点的最近距离 */
        for(w = 0;w < G.vexnum; ++w)
            if(!final[w]) /* w顶点在V-S中 */
                if(D[w] < min)
                {
                    v = w;
                    min = D[w];
                } /* w顶点离v0顶点更近 */
                final[v] = TRUE; /* 离v0顶点最近的v加入S集 */
                for(w = 0;w < G.vexnum; ++w) /* 更新当前最短路径及距离 */
                {
                    if(!final[w] && min < INFINITY && G.arcs[v][w].adj < INFINITY && (min + G.arcs[v][w].adj < D[w]))
                    { /* 修改D[w]和P[w],w∈V-S */
                        D[w] = min + G.arcs[v][w].adj;
                        for(j = 0;j < G.vexnum;++j)
                            P[w][j] = P[v][j];
                        P[w][w] = TRUE;
                    }
                }
    }
}

 

经典二分问题

经典二分问题：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  。

写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9。输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2。输出: -1
解释: 2 不存在 nums 中因此返回 -1

思路1：我们当然可以一个数一个数的遍历，但是毫无疑问要被大妈鄙视，这可怎么办呢？

思路2：二分查找
二分查找是一种基于比较目标值和数组中间元素的教科书式算法。

如果目标值等于中间元素，则找到目标值。
如果目标值较小，证明目标值小于中间元素及右边的元素，继续在左侧搜索。
如果目标值较大，证明目标值大于中间元素及左边的元素，继续在右侧搜索。

算法代码描述：

初始化指针 left = 0, right = n - 1。
当 left <= right：
比较中间元素 nums[pivot] 和目标值 target 。
如果 target = nums[pivot]，返回 pivot。
如果 target < nums[pivot]，则在左侧继续搜索 right = pivot - 1。
如果 target > nums[pivot]，则在右侧继续搜索 left = pivot + 1。

算法实现：照例贴出三种语言的实现，在Java实现中给出了详细注释

class Solution {
  public int search(int[] nums, int target) {
	//分别准备好左右端点
    int left = 0, right = nums.length - 1;
	//循环二分
    while (left <= right) {
	//取中点
      int pivot = left + (right - left) / 2;
	  //找到答案并返回
      if (nums[pivot] == target) return pivot;
	  //向左继续找
      if (target < nums[pivot]) right = pivot - 1;
	  //向右继续找
      else left = pivot + 1;
    }
	//未找到，返回-1
    return -1;
  }
}

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            pivot = left + (right - left) // 2
            if nums[pivot] == target:
                return pivot
            if target < nums[pivot]:
                right = pivot - 1
            else:
                left = pivot + 1
        return -1

class Solution {
  public:
  int search(vector<int>& nums, int target) {
    int pivot, left = 0, right = nums.size() - 1;
    while (left <= right) {
      pivot = left + (right - left) / 2;
      if (nums[pivot] == target) return pivot;
      if (target < nums[pivot]) right = pivot - 1;
      else left = pivot + 1;
    }
    return -1;
  }
};

 

 

 

二叉搜索树实现

本文给出二叉搜索树介绍和实现

 

首先说它的性质：所有的节点都满足，左子树上所有的节点都比自己小，右边的都比自己大。

 

那这个结构有什么有用呢？

首先可以快速二分查找。还可以中序遍历得到升序序列，等等。。。

基本操作：

1、插入某个数值

2、查询是否包含某个数值

3、删除某个数值

 

根据实现不同，还可以实现其他很多种操作。

 

实现思路思路：

前两个操作很好想，就是不断比较，大了往左走，小了往右走。到空了插入，或者到空都没找到。

而删除稍微复杂一些，有下面这几种情况：

1、需要删除的节点没有左儿子，那就把右儿子提上去就好了。

2、需要删除的节点有左儿子，这个左儿子没有右儿子，那么就把左儿子提上去

3、以上都不满足，就把左儿子子孙中最大节点提上来。

 

当然，反过来也是成立的，比如右儿子子孙中最小的节点。

 

下面来叙述为什么可以这么做。

下图中A为待删除节点。

第一种情况：

 

1、去掉A，把c提上来，c也是小于x的没问题。

2、根据定义可知，x左边的所有点都小于它，把c提上来不影响规则。

 

第二种情况

 

3、B<A<C,所以B<C,根据刚才的叙述，B可以提上去，c可以放在b右边，不影响规则

4、同理

 

第三种情况

 

5、注意：是把黑色的提升上来，不是所谓的最右边的那个，因为当初向左拐了，他一定小。

因为黑色是最大，比B以及B所有的孩子都大，所以让B当左孩子没问题

而黑点小于A，也就小于c，所以可以让c当右孩子

大概证明就这样。。

下面我们用代码实现并通过注释理解

上次链表之类的用的c，循环来写的。这次就c++函数递归吧，不同方式练习。

定义

struct node
{
    int val;//数据
    node *lch,*rch;//左右孩子
};

插入

 node *insert(node *p,int x)
 {
     if(p==NULL)//直到空就创建节点
     {
         node *q=new node;
         q->val=x;
         q->lch=q->rch=NULL;
         return p;
     }
     if(x<p->val)p->lch=insert(p->lch,x);
     else p->lch=insert(p->rch,x);
     return p;//依次返回自己，让上一个函数执行。
 }

查找

 bool find(node *p,int x)
 {
     if(p==NULL)return false;
     else if(x==p->val)return true;
     else if(x<p->val)return find(p->lch,x);
     else return find(p->rch,x);
 }

删除

 node *remove(node *p,int x)
 {
      if(p==NULL)return NULL;
      else if(x<p->val)p->lch=remove(p->lch,x);
      else if(x>p->val)p->lch=remove(p->rch,x);
      //以下为找到了之后
      else if(p->lch==NULL)//情况1
      {
          node *q=p->rch;
          delete p;
          return q;
      }
      else if(p->lch->rch)//情况2
      {
          node *q=p->lch;
          q->rch=p->rch;
          delete p;
          return q;
      }
      else
      {
          node *q;
          for(q=p->lch;q->rch->rch!=NULL;q=q->rch);//找到最大节点的前一个
          node *r=q->rch;//最大节点
          q->rch=r->lch;//最大节点左孩子提到最大节点位置
          r->lch=p->lch;//调整黑点左孩子为B
          r->rch=p->rch;//调整黑点右孩子为c
          delete p;//删除
          return r;//返回给父
      }
      return p;
 }

 

对数组排序可以说是编程基础中的基础，本文对八种排序方法做简要介绍并用python实现。

代码中注释很全，适合复习和萌新学习。这是刚入学自己写的，可能难免比不上标准的写法，但是懒得改了。

文末会放和排序相关的基本拓展总结链接。

看不明白可以看群里视频

注意排序实现的具体方式，不要用局部变量，否则占空间太多，和空间复杂度不符。

好，我们开始。

• 选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在待排序序列的起始位置，直到全部待排序的数据元素排完。时间复杂度O(N^2)

for i in range(len(l)):#意义是第i个位置开始挑第i大（小）的元素
    for j in range(i,len(l)):#和其他待排序的元素比较
	if l[j]<l[i]:#更大就交换
	    l[j],l[i]=l[i],l[j]

• 冒泡排序

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

它重复地走访过要排序的元素列，一次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换(一般进行n次即可，第n次一定会把第n小的元素放到正确位置）。

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。时间复杂度O(N^2)

for i in range(len(l)-1):#下标和i无关，代表的只是第i次排序，最多需要len（l）-1次排序即可
    for j in range(len(l)-1):#遍历每一个元素
	if l[j]<l[j+1]:#本元素比下一个元素小，就交换
		l[j],l[j+1]=l[j+1],l[j]

 分析一下其实每次排序都会多一个元素已经确定了位置，不需要再次遍历。

所以j循环可以改成len(l)-i-1

时间复杂度没变。

 

• 插入排序

有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。

for i in range(1,len(l)):#意义是第i个元素开始插入i之前的序列（已经有序）
    for j in range(i,0,-1):#只要比它之前的元素小就交换
	if l[j]<l[j-1]:
	    l[j],l[j-1]=l[j-1],l[j]
	else:
            break#直到比前一个元素大

 

• 归并排序

速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列

试想：假设已经有两个有序数列，分别存放在两个数组s，r中，我们如何把他们有序的合并在一起？

归并排序就是在重复这样的过程，首先单个元素合并为含有两个元素的数组（有序），然后这种数组再和同类数组合并为四元素数组，以此类推，直到整个数组合并完毕。

def gg(l,ll):#合并函数
    a,b=0,0
    k=[]#用来合并的列表
    while a<len(l) and b<len(ll):#两边都非空
        if l[a]<ll[b]:
            k.append(l[a])
            a=a+1
        elif l[a]==ll[b]:a=a+1#实现去重
        else:
            k.append(ll[b])
            b=b+1
    k=k+l[a:]+ll[b:]#加上剩下的
    return k

def kk(p):#分到只剩一个元素就开始合并
    if len(p)<=1:
        return p
    a=kk(p[0:len(p)//2])#不止一个元素就切片
    b=kk(p[len(p)//2:])
    return gg(a,b)#返回排好序的一部分
l=list(map(int,input().split(" ")))
print(kk(l))

• 快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

• 随机化快排

快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下，每次划分将得到最坏的结果。比如1 2 3 4 5，每次取第一个元素，就退化为了O(N^2)。一种比较常见的优化方法是随机化算法，即随机选取一个元素作为主元。

这种情况下虽然最坏情况仍然是O(n^2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。

进一步提升可以分割为三部分，即小于区，等于区，大于区，减小了递归规模，并克服了多元素相同的退化。

def gg(a,b):
    global l
    if a>=b:#注意停止条件，我以前没加>卡了半小时
        return
    x,y=a,b
    import random#为了避免遇到基本有序序列退化，随机选点
    g=random.randint(a,b)
    l[g],l[y]=l[y],l[g]#交换选中元素和末尾元素
    while a<b:
        if l[a]>l[y]:#比目标元素大
            l[a],l[b-1]=l[b-1],l[a]#交换
            b=b-1#大于区扩大
            #注意：换过以后a不要加，因为新换过来的元素并没有判断过
        else:a=a+1#小于区扩大
    l[y],l[a]=l[a],l[y]#这时a=b
    #现在解释a和b：a的意义是小于区下一个元素
    #b是大于区的第一个元素
    gg(x,a-1)#左右分别递归
    gg(a+1,y)

l=list(map(int,input().split(" ")))
gg(0,len(l)-1)
print(l)

• 堆排序

堆排序（HeapSort）是一树形选择排序。堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）的记录。

由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。

堆排序是就地排序，辅助空间为O(1).

它是不稳定的排序方法。

主要思想：维持一个大根堆（根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为大根堆，又称最大堆。注意：①堆中任一子树亦是堆。②以上讨论的堆实际上是二叉堆（Binary Heap），类似地可定义k叉堆。）

第一步：通过调整原地建立大根堆

第二步：每次交换堆顶和边界元素，并减枝，然后调整堆顶下沉到正确位置。

def down(i,k):#在表l里的第i元素调整，k为边界

#优先队列也是通过这种方式实现的
    global l
    while 2*i+2<k:#右孩子不越界
        lift,right=2*i+1,2*i+2
        m=max(l[i],l[lift],l[right])
        if m==l[i]:#不需要调
            break
        if m==l[lift]:#把最大的换上来
            l[i],l[lift]=l[lift],l[i]
            i=lift#目的节点下标更新
        else:#把最大的换上来
            l[i],l[right]=l[right],l[i]
            i=right#目的节点下标更新
    if 2*i+1<k:#判断左孩子
        if l[2*i+1]>l[i]:
            l[i],l[2*i+1]=l[2*i+1],l[i]

def main():
    global l
    for j in range(1,len(l)+1):#调大根堆
        i=len(l)-j
        down(i,len(l))
    for i in range(len(l)-1,-1,-1):#排序
        l[i],l[0]=l[0],l[i]#最大和边界交换，剪枝
        down(0,i)
    print(l)
    
l=list(map(int,input().split(" ")))
main()

        
    

        

• 桶排序

桶排序不是基于比较的排序方法，只需对号入座。将相应的数字放进相应编号的桶即可。

当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间o（n）

对于海量有范围数据十分适合，比如全国高考成绩排序，公司年龄排序等等。

l=list(map(int,input().split(" ")))
n=max(l)-min(l)
p=[0]*(n+1)#为了省空间
for i in l:
    p[i-min(l)]=1#去重排序，做标记即可
for i in range(n):
    if p[i]==1:#判断是否出现过
        print(i+min(l),end=" ")

• 希尔排序

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

通过缩小有序步长来实现。

 

def shell(arr):
 n=len(arr)#初始化步长
 h=1
 while h<n/3:
  h=3*h+1
 while h>=1:#判断，退出后就有序了。
  for i in range(h,n):
   j=i
   while j>=h and arr[j]<arr[j-h]:#判断是否交换
    arr[j], arr[j-h] = arr[j-h], arr[j]
    j-=h
  h=h//3#逐渐缩小步长
 print arr

稳定性及时间复杂度

排序稳定性概念：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

时间复杂度：时间复杂度是同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。可以理解为和常数操作所成的一种关系（常数操作为O(1))

空间复杂度类似。

下面给出各类排序的对比图：

 

 

 

• 基数排序

因为桶排序是稳定的，基数排序就是很多次桶排序而已，按位进行桶排序即可。

（个人认为桶排序名字不恰当，因为桶是先进后出，和稳定的算法正好反了，）

 

 

 

 

总：

比较排序和非比较排序

      常见的排序算法都是比较排序，非比较排序包括计数排序、桶排序和基数排序，非比较排序对数据有要求，因为数据本身包含了定位特征，所有才能不通过比较来确定元素的位置。

      比较排序的时间复杂度通常为O(n2)或者O(nlogn)，比较排序的时间复杂度下界就是O(nlogn)，而非比较排序的时间复杂度可以达到O(n)，但是都需要额外的空间开销。

• 若n较小（数据规模较小），插入排序或选择排序较好
• 若数据初始状态基本有序（正序），插入、冒泡或随机快速排序为宜
• 若n较大，则采用时间复杂度为O(nlogn)的排序方法：快速排序或堆排序
• 快速排序是目前基于比较的排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
• 堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。