数据结构与算法基础笔记

第一章 绪论

P2 数据结构研究

利用计算机求解问题涉及到两大核心方法：

l 如何表达定义要处理的对象（数据结构）

l 处理这些对象的步骤（算法）

数据结构的种类：

l 线性结构（就是集合，每个数据首尾相连，线性表、栈、队列、串、数组、广义表）

l 树状结构（一对多，一个子数据只能有一个父数据）

l 图状结构（网状结构  ）

描述非树脂计算问题的数学模型不是数学方程，而是数据结构

P3-P4 基本概念和术语

数据的分类：数值型（可运算）、非数值型：文字、图像等

数据对象：性质相同的数据元素的集合，是数据的子集

数据元素/记录/结点/顶点：数据的基本单位，常常作为一个整体处理，是数据对象的子集

数据项：构成数据元素的不可分割的最小单位

数据结构：一种或多种带结构的数据元素的集合

数据结构 = 逻辑结构（抽象） + 存储结构（实现，物理上如何存储）

逻辑结构分类（一）：

l 线性结构：收尾相连，只有一个开始节点和一个终端节点

l 非线性结构：树、图

逻辑结构分类（二）：

l 集合：数据元素均独立

l 线性结构

l 树状结构

l 图状/网状结构

存储结构：

l 顺序存储结构：依次存储，数据之间的逻辑由储存位置决定。如数组。

l 链接存储结构：数据元素之间的逻辑关系用指针表示。

l 索引存储结构：通过索引表（index，就是目录）找数据；一般形式是（关键字，地址）；每个节点只有一个标识；

l 散列存储结构：根据节点的关键字计算出节点的储存地址？？？

数据类型：一组性质相同的值的集合

抽象数据类型（ADT）：数学模型及其操作，不考虑具体存储结构即具体实现算法

抽象数据类型的表示：（D数据对象，S关系集，P基本操作集）

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

ADT 抽象数据类型名{

DATA

数据对象：<数据对象的定义>

数据关系：<数据关系的定义>

Operation

基本操作名1

基本操作：<基本操作的定义>

基本操作名2

初始条件：<初始条件描述>

操作结果：<操作结果描述>

} ADT 抽象数据类型名

其中：数据对象、数据关系用伪代码描述；

基本操作定义格式为：基本操作名（参数表）            ：为操作提供输入值，赋值参数、引用参数

初始条件：<初始条件描述>      ：执行之前要满足的条件

操作结果：<操作结果描述>      ：成功操作完成后，返回的结果

抽象数据类型的一个实例：

ADT Circle{

数据对象:D = {t,x,y|r,x,y均为实数}

数据关系：R = {<r,x,y>|r是半径,<x,y>为圆心坐标}

基本操作：

Circle（&C,r,x,y）

操作结果：构造一个圆

double Area(C)

初始条件：圆已经存在

操作结果：计算面积

} ADT 抽象数据类型名

P5 抽象数据类型的表示与实现

使用c语言实现一个抽象数据的定义：

P6-P9 算法和算法分析

算法的描述：

l 自然语言

l 流程图：传统流程图、NS流程图

l 伪代码/类语言：类C语言等

l 程序代码：C语言、Python等

程序是对算法的具体实现。

算法的特性：

l 有穷性：每一步都要有穷

l 确定性：相同输入、相同输出

l 可行性：

l 输入：有零个或多个输入

l 输出：一个或多个输出

算法设计的要求：

l 正确性：无语法错误、满足要求、典型/刁难的数据输入后也能得出满足要求的结果

l 可读性：易于找到错误

l 稳健性：输入非法数据时，可以返回错误信息

l 高效性：时间和占用资源低

算法的时间效率：

1)    事后统计：实现算法，测算时间和空间开销（与软硬件性能有关）

2)    事前分析：对消耗资源的估算

算法运行时间 = ∑（简单操作次数X简单操作所需时间）

算法运行时间 = ∑（   语句频度  X 简单操作所需时间）

如果假设简单操作所需时间为单位施加

例：

有算法如下：

【如果不知道一个循环作为整体执行多少次，那么就无法知道该循环内的语句执行多少次】

【一个循环A里的语句a的执行次数 = 循环A的执行次数 X 循环A执行一次语句a执行的次数】

为方便比较，只比较数量级。例如一个算法消耗时间为T1（n）=10n2

若有一个辅助函数f（n），使得 为一个不等于零的常数，则有渐进时间复杂自由度

例如，求解矩阵相乘算法消耗时间为 。因为

所以该算法时间复杂度为

某些情况下，算法基本操作执行的次数因输入的数据集不同而不同。因而有最坏时间复杂度/平均时间负责度/最好时间复杂度。

时间复杂自由度的运算：

l 加法（顺序执行）：

l 乘法（程序嵌套）：

渐进空间复杂度：

算法占据的空间：算法本身占据的空间（输入输出、指令、常量变量）、使用的辅助空间

第六章 图

P108-P109 图的基本概念与术语

定义： ，其中V：数据元素（顶点）的有穷非空集合；E：边的有穷集合。

l 完全图：任意亮点都有一条边相连。其中，无向完全图有 ，有向完全图有 条边。

l 稠密图：边很少，

l 稠密图：边较多

l 网：边有权重的图

l 邻接：有边相连的两个顶点间的关系。

，两个顶点互为邻接点；

， 邻接到 ， 邻接于

l 关联（依附）：存在 或 ，册称该边关联与 和

l 顶点的度：一个顶点关联的边的数量。度： ；入度： ；出度：

l 路径：连续的边构成的顶点序列

l 路径长度：路径上边的数目或权重之和

l 回路/环：第一个顶点和最后一个顶点相同的路径

l 简单路径：除路径起点和终点相同外，其余顶点均不相同

l （强）连通图：任意两个顶点v，u都存在v到u的路径

判断无向图是否为连通图，只要没顶点孤立即可

判断有向图是否连接，除了看有无顶点孤立，还要看不相邻的顶点之间能否顺着有向边连接。

l 子图：有两图 、 ，若存在 、 ，则称 为 的子图

l （强）连通分量：一个图的极大连通子图的数量

l 极小连通子图：是子图，而且删除任意边，就不再连通

l 生成树：包含连通图G所有顶点的极小连通子图。不能再删关系的图就是数结构嘛

l 生成森林：对于非连通图，各个连通分量（极大连通子图）的生成树的集合

P111 图的类型定义

图的抽象数据类型定义：？？？

ADT Graph{

数据对象：V，顶点集，具有相同特性的数据元素的集合，

数据关系：R，R = {VR}

<V,W>表示从V到W的边， 定义了边的信息}

CreateGraph(&G,V,VR)

初始条件:V是图的顶点集，VR是图中弧的集合。操作结果:按V和VR的定义构造图G。

DFSTraverse(G)

初始条件:图G存在。

操作结果:对图进行深度优先遍历。

BFSTraverse(G)

初始条件:图G存在。

操作结果:对图进行广度优先遍历。

}ADT Graph

P112 图的存储结构-无向图邻接矩阵

数组表示法（邻接矩阵）

链接表示法（邻接表）

链式存储结构：邻接表、邻接多重表、十字链表

数组表示法/邻接矩阵表示：

有图 有n个顶点（这里的顶点就是图谱里的实体）

建立顶点表（记录顶点信息）：Vexs[n]

建立邻接矩阵（记录顶点间关系）：A.arcs[n][n]

P113 图的存储结构-有向图和网邻接矩阵

有向图的邻接矩阵表示：

网（加权图）的邻接矩阵：

P114 图的存储结构-邻接矩阵创建无向网

▼定义顶点表、邻接矩阵等

▼输入顶点信息、初始化邻接矩阵

▼构造邻接矩阵/输入关系信息

P115 图的存储结构-邻接矩阵的优缺点

优点：

l 直观、简单

l 方便检查任意一对顶点间是否存在边

l 方便查找任意顶点的所有邻接点

缺点：

l 不便添加和删除顶点

l 浪费存储空间，尤其是稀疏图的时候

l 统计边的时候浪费时间，尤其是稀疏图的时候

P116 图的存储结构-邻接表表示无向图

▼邻接表表示无向图

特点：

l 邻接表中的边表不唯一

l 无向图中，有n个顶点、e条边，则需要n个头结点，2e个表结点，故空间复杂度为S（n）=O（n+2e）。适合存储稀疏图。

P117 图的存储结构-邻接表表示有向图

▼邻接表表示有向图

特点：

l 顶点 的出度为第i个单链表中的节点个数

l 顶点 的入度为整个单链表邻接点域值为i-1的节点个数

l 有向图中，有n个顶点、e条边，则需要n个头结点，e个表结点，故空间复杂度为S（n）=O（n+e）

P118 图的存储结构-建立邻接表算法

▼定义顶点表

▼定义边表

▼定义图

▼某邻接表表示的图结构的实例：

P119 图的存储结构-邻接表特点、与邻接矩阵关系

邻接表优点：

l 适合稀疏图，需要空间：无向图N+2E，有向图N+2E

l 方便计算无向图的度

邻接表缺点：

l 有向图需要使用邻接表计算出度，逆邻接表计算入度

l 不方便判断任意两节点是否存在边

区别：

l 邻接矩阵唯一，邻接表不唯一

l 邻接矩阵空间复杂度为O(n2), 邻接表空间复杂度为O(n+e)或O(n+2e)

l 邻接矩阵多用于稠密图, 邻接表多用于稀疏图

P120 图的存储结构-十字链表

P121 图的存储结构-邻接多重表

P122-图的遍历-深度优先思想

深度优先Depth_First Search（DFS）

图遍历定义：从连通图中某一顶点出发，访问图中所有顶点，且每个顶点仅被访问一次

如何避免重复访问：

l 设置辅助数组visited[n]标记每个被访问过的顶点

l 初始状态visited[i] = 0

l 顶点i被访问后，visited[i] = 1

DFS方法：

l 在访问图中某一起始顶点v后，由v出发，访问它的任一邻接顶点w;再从w出发，访问与w邻接但还未被访问过的顶点w2;

l 然后再从w出发，进行类似的访问，...

l 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点u为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。

l 如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问;

l 如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。

注：退回的时候根据路径（路径数组/栈）退回

深度优先遍历算法实现-邻接矩阵

P123 图的遍历-深度优先-邻接矩阵实现

P124 图的遍历-深度优先算法效率

时间复杂度

适合

邻接矩阵

O(n2)

稠密图

邻接表

O(n+e)？？？

稀疏图

P125 图的遍历-广度优先遍历及实现

BFS（Breadth First Search）：广度优先遍历，可以理解为一层一层的搜索

BFS方法：从图的某一节点出发，首先依次访问该结点的所有邻接点，再按这些顶点被访问的先后次序依次访问与他们相邻接的为被访问的顶点。重复此过程，直至所有顶点均被访问为止。

时间复杂度

适合

邻接矩阵

O(n2)

稠密图

邻接表

O(n+e)？？？

稀疏图

时间复杂度

空间复杂度

DFS

邻接矩阵O(n2)

邻接表O(n+e)

O(n)

BFS

P126 图的应用-生成树及结构

生成树：包含所有顶点的极小连通子图。不能再删关系的图就是数结构嘛

特点：

l 一个图可有不同的生成树

l 生成树的顶点个数与图的顶点个数相同

l 若图/生成树有n个节点，则一定有n-1条边。反之，不成立。？？？

l 生成树中再加一条边（原有图中的边），必然形成回路

l 生成树中任意两个顶点间的路径唯一

无向图的生成树

l 深度优先遍历树

l 广度优先遍历树

设图G=(V,E)是连通图，当从图中任一项顶点出发遍历图G时，将边集E(G)分成两个集合

l T(G)，遍历图所经过的边的集合

l B(G)，遍历图未经过的边的集合

即E(G)=T(G)∪B(G)，显然，新的子图G(V,T)是图G=(V,E)的极小连通子图和生成树。

P127 图的应用-最小生成树及应用

最小（代价）生成树MST（Minimum Spanning Tree）：给定一个无向网络，各边权值之和最小的生成树

最小生成树不唯一，但是各个最小生成树的权值之和一定最小且相等。

典型应用：导航（最短路径规划）、建立通讯网络

P128 图的应用-最小生成树MST性质

MST性质：若边（u，v）是一条具有最小权值的边，则必然存在一个包含边（u，v）的最小生成树

MST性质的意义在于，在生成树的构造过程中，可将网的顶点分为

l 顶点集合U：落入生成树内的顶点

l 顶点集合V-U：未落入生成树内的顶点

则接下来应在连通U和V-U的边中选择权值最小的边。

P129 图的应用-最小生成树Prim算法

算法思想：

P130 图的应用-最小生成树Kruskal算法

如何判断加边的时候，是否形成环呢

算法

普里姆算法

克鲁斯卡尔算法

算法思想

选择点

选择边

时间复杂度

适用范围

稠密图

稀疏图

P131 图的应用-最短路径问题抽象

问题抽象：

描述

算法

单源最短路径

在有向网中，源点到达终点的多条路径中，寻找一条各边权值之和最小的路径

Djikstra（迪杰斯特拉）算法

所有顶点最短路径

在有向网中，所有顶点之间的最短路径

Floyd（弗洛伊德）算法

P132 图的应用-最短路径-Djikstra（迪杰斯特拉）算法

Djikstra（迪杰斯特拉）算法就是在最小生成树Prim算法的基础上，增加了操作。

Djikstra（迪杰斯特拉）算法就是在最小生成树Prim算法的过程中，考虑了各个节点的最短路径。

看不懂？？？

P133 图的应用-最短路径-Floyd（弗洛伊德）算法

方法一：每个顶点执行Djikstra（迪杰斯特拉）算法

方法二：？？？讲了个啥，看不懂

P134 图的应用-拓扑排序

DAG图：有向无环图，不是有向树

DAG网

顶点表示

边表示

应用

AOV网（Activity On Vertex network）

活动

活动之间的优先制约关系

拓扑排序

AOE网（Activity On Edge network）

活动的开始或结束

活动

关键路径

拓扑排序：AOV网五回路的情况下，将全部活动（顶点）排序为线性序列（拓扑有序序列）

P135 图的应用-关键路径

AOE网：