《数据结构第七章》PPT课件

Data Structure
完整版P21P.T0课4.2件021
Page 3
已知以二维数组表示的图的邻接矩阵如图所示。试分别画 出自顶点出发进行遍历所得的深度优先生成树和广度优先 生成树。
Data Structure
完整版0课4.2件021
Page 4
请对下边的无向带权图，
❖ 写出它的邻接矩阵，并按普里姆算法求其最小生成树； ❖ 写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。
Data Structure
完整版P21P.T0课4.2件021
Page 9
Data Structure
完整版P21P.T0课4.2件021
Page 7
试利用 Dijkstra 算法求下图中从顶点 a 到其它各顶点 间的最短路径，写出执行算法过程中各步的状态。
Data Structure
完整版P21P.T0课4.2件021
Page 8
试利用 Floyd 算法求下图所示有向图中各对顶点之间的 最短路径。
Data Structure
完整版P21P.T0课4.2件021
Page 5
试列出下图中全部可能的拓扑有序序列。
Data Structure
完整版P21P.T0课4.2件021
Page 6
对于下图所示的 AOE 网络，计算各活动弧的 e(ai) 和 l(aj) 函数值，各时间(顶点)的 ve(vi) 和 vl(vj) 函数 值；列出各条关键路径。
数据结构
计算机科学与技术学院
基础知识题
已知有向图，请给出该图的 (1) 每个顶点的入/出度； (2) 邻接矩阵； (3) 邻接表； (4) 逆邻接表； (5) 强连通分量。

7.5 树的应用
➢判定树
在实际应用中，树可用于判定问题的描述和解决。
•设有八枚硬币，分别表示为a，b，c，d，e，f，g，h，其中有一枚且 仅有一枚硬币是伪造的，假硬币的重量与真硬币的重量不同，可能轻， 也可能重。现要求以天平为工具，用最少的比较次数挑选出假硬币， 并同时确定这枚硬币的重量比其它真硬币是轻还是重。
的第i棵子树。 ⑺Delete（t，x，i）在树t中删除结点x的第i棵子树。 ⑻Tranverse（t）是树的遍历操作，即按某种方式访问树t中的每个
结点，且使每个结点只被访问一次。
7.2.2 树的存储结构
顺序存储结构 链式存储结构 不管哪一种存储方式，都要求不但能存储结点本身的数据 信息，还要能够唯一的反映树中各结点之间的逻辑关系。 1.双亲表示法 2.孩子表示法 3.双亲孩子表示法 4.孩子兄弟表示法
21
将二叉树还原为树示意图
A BCD
EF
A
B
C
E
D
F
A
B
C
E
D
F
22
练习：将下图所示二叉树转化为树
1 2
4
5
3
6
2 4
1 53
6
23
7.3.2 森林转换为二叉树
由森林的概念可知，森林是若干棵树的集合，只要将森林中各棵树 的根视为兄弟，森林同样可以用二叉树表示。 森林转换为二叉树的方法如下：
⑴将森林中的每棵树转换成相应的二叉树。 ⑵第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树 的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来 后，此时所得到的二叉树就是由森林转换得到的二叉树。
相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤i≤m）本身又是 一棵树。树T1，T2，…，Tm称为这个根结点的子树。 • 可以看出，在树的定义中用了递归概念，即用树来定义树。因此， 树结构的算法类同于二叉树结构的算法，也可以使用递归方法。

含有 e=n(n-1) 条弧的有向图称作 有 向完全图；
若边或弧的个数 e<nlogn，则称作
稀疏图，
13
1
1
4
2
3
4
2
3
无向完全图 有向完全图
15 A 9
11
B 7 21
E
3
C2 F
权：与图的边或 弧相关的数。
网:带权的图。
有两个图G=(V,{E}) 和
图 G=(V,{E}),
245
无向完全图 5
3
6
1
3
6
图与子图 例
例
245
1 57
1
3
6
32
46
G2
顶点5的度：3 顶点2的度：4
G1
顶点2入度：1 出度：3 顶点4入度：1 出度：0
例
路径：1，2，3，5，6，3 路径长度：5
245
简单路径：1，2，3，5
回路：1，2，3，5，6，3，1
1
3
6
简单回路：3，5，6，3
G1
31.12.2020
h
6
7.1 图的定义和术语
主
7.2 图的存储结构（***）
要
7.3 图的遍历（***）
内 容
7.4 图的连通性问题 最小生成树（***）
7.5 有向无环图及其应用
拓扑排序 关键路径
7.6 最短路径
图的结构定义:
图是由一个顶点集 V 和一个弧集 R构成的 数据结构。
Graph = (V , R ) 其中，VR＝{<v,w>| v,w∈V 且 P(v,w)}
C D
E
A F

比较次数： C min C max

n2 i0
( n i 1) n ( n 1) 2

最少移动次数： 最多移动次数：

n 1 i 1
i
M
min
0
3 ( n 1)
M
max
一个交换包含三次移动
稳定算法
Data Structure
16
交换指针，减少交换记录的开销
{ A[0]=A[i];j=i-1;
while (Comp::lt(x, A[j])) { A[j+1]=A[j];j--;}
A[j+1]=A[0];
} }
Data Structure
8
插入排序算法分析
最小比较次数：
C min n 1
最多比较次数： C max 最少移动次数： 最多移动次数：
Data Structure
12
起泡排序算法分析
最小比较次数： 最多比较次数： 最少移动次数： 最多移动次数：
C min n 1
C max

n 1 i 1
i
n ( n 1) 2
M
M
min
0
3
n 1 i 1
max
i 2
3 n ( n 1)
稳定算法
template <class Elem, class Comp>
void bubsort(Elem A[], int n) {
for (int i=0; i<n-1; i++) for (int j=n-1; j>i; j--) if (Comp::lt(A[j], A[j-1])) swap(A, j, j-1);

if (!visited[w]) DFS(G, w);
/*对v的尚未访问的邻接顶点w递归调用DFS*/
}
第5页/共99页
6
在邻接表存储结构上实现深度优先搜索: void DFSTraverseAL(ALGraph G) /*深度优先遍历以邻接表存储的图G*/ {int i; for (i=0;i<G.vexnum; ++ i)
数据结构 第七章-图2
会计学
1
【重点掌握】： 1. 图的两种遍历方法：遍历的定义、深度优先搜索遍历和
广度优先搜索遍历的算法； 2. 应用图的遍历算法判断图的连通性及求图的生成树； 3. 用Prim、Kruskal算法求图的最小生成树； 4. 用Dijkstra算法求解单源最短路径问题；用Floyd算法求
aovaov网和网和aoeaoe网用都能表示工程各子工程的流程网用都能表示工程各子工程的流程一个用顶点表示活动一个用边表示活动但一个用顶点表示活动一个用边表示活动但aovaov网侧重网侧重表示活动的前后次序表示活动的前后次序aoeaoe网除表示活动先后次序还表网除表示活动先后次序还表示了活动的持续时间等因此可利用示了活动的持续时间等因此可利用aoeaoe网解决工程所需网解决工程所需最短时间及哪些子工程拖延会影响整个工程按时完成等问最短时间及哪些子工程拖延会影响整个工程按时完成等问题
(2)用顶点v到集合T中顶点的边权“更新”原集合U中顶点 到集合T中顶点的最小边权；
(3)从一个顶点在U中，而另一个顶点在T中的各条边中选择 权值最小的边(u,v),把顶点v加入到集合U 中。
(4)重复(2) 、(3)，直到网络中的所有顶点都加入到生成树顶 点集合U中为止。
第21页/共99页

5
(最坏情况)
可编辑ppt
11
7.2 顺序查找
成功查找的平均查找长度为（n+1）/2。显然不成功 查找次数为n+1，其时间复杂度均为 O(n)。
顺序查找的优点是：算法简单且适用面广，它对表的 结构无任何要求。无论记录是否按关键字的大小有序，其 算法均可应用，而且上述讨论对线性链表也同样适用。
顺序查找的缺点是：查找效率低，当 n 较大时，不宜 采用顺序查找。
中
5 13 19 21 37 56 64 75 80 88 92
low>high 查找失败
123456
low high
mid 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
可编辑ppt
16
high low
7.3 二分法查找
从二分法查找的执行情况分析，每做一次比较，查找的 范围都缩小一半。因此二分法查找的平均查找长度为
【答案】
查找成功时，最少比较1次，最多比较5次。
2、已知如下11个数据元素的有序表（6，14，19， 21，36，57，63，76，81，89，93），请画出 查找键值为21和85的查找过程。
可编辑ppt
18
7.4 分块查找
可编辑ppt
10
01 64 5
23456 13 19 21 37 56
找64 7 8 9 10 11 64 75 80 88 92
监视哨
比较次数：
查找第n个元素： 1
查找第n-1个元素：2
……….
查找第1个元素： n
查找第i个元素： n+1-i
查找失败：
n+1
iiiii

二、归并排序 1.思想：（2-路归并排序）
① n个记录的表看成n个，长度为1的有序表 ② 两两归并成 n/2 个，长度为2的有序表（n为奇数，则 还有1个长为1的表） ③再两两归并为 n/2 /2 个，长度为4的有序表 . . . 再两两归并直至只剩1个，长度为n的有序表；
共log2n 趟
2. 例：
二、快速排序★
1.基本思想：通过分部排序完成整个表的排 序；
首先取第一个记录，将之与表中其余记录比较并交换，从而将 它放到记录的正确的最终位置，使记录表分成两部分{其一（左边的） 诸记录的关键字均小于它；其二（右边的）诸记录的关键字均大于 它}；然后对这两部分重新执行上述过程，依此类推，直至排序完毕。
7.5 归并排序
一、有序序列的合并(两个有序表归并成一个有 序表) 1. 思想：比较各个子序列的第一个记录的 键值，最小的一个就是排序后序列的第一个 记录。取出这个记录，继续比较各子序列现 有的第一个记录的键值，便可找出排序后的 第二个记录。如此继续下去，最终可以得到 排序结果。 2. 两个有序表归并算法 （见P199）
▲排序类型——
内部排序：全部数据存于内存；
排序过程
外部排序:需要对外村进行访问的
内部排序
按方法分
插入排序 交换排序 选择排序 归并排序
▲排序文件的物理表示：数组表示 #define n 100 /*序列中待排序记录的总数*/ typedef struct { int key; /*关键字项*/ anytype otheritem ; /*其他数据项*/ }records; typedef records list[n+1]; list r; r[0] r[1] r[2]….r[n] r[i].key——第i个记录的关键字 ▲排序指标（排序算法分析）： 存储空间-空间复杂度 比较次数-时间复杂度

非简单图
2020/9/30
3
7.1 图的逻辑结构
7.1.1 图的定义
● 相关概念 无向图和有向图
● 无向图：如果图中顶点 vi 和 vj 之间的边无方向，则称这条边为无向边， 用无序偶对 (vi, vj) 表示，称该图为无向图。
● 有向图：如果图中顶点 vi 和 vj 之间的边有方向，则称这条边为有向边， 用有序偶对 <vi, vj> 表示，称该图为有向图。
无论有向图还是无向图，顶点数 n、边 数 e 和度数之间满足：
2020/9/30
8
7.1 图的逻辑结构
7.1.1 图的定义
● 相关概念 权和网
● 权：权通常是指对图中边赋予的有意义的数值量。在实际应用中，权 可以有具体的含义。
● 网：如果将图中的每条边上都赋上一个权值，则称这种图为网，或称 为有权图 。
2020/9/30
6
7.1 图的逻辑结构
7.1.1 图的定义
● 相关概念 稀疏图和稠密图
● 稀疏图：边数很少的图称为稀疏图，如果 e 表示图中的边数，n 表示 图中的顶点数，则 e＜nlogn。
● 稠密图：边数很多的图称为稠密图，如果 e 表示图中的边数，n 表示 图中的顶点数，则 e≥nlogn。
2020/9/30
无向完全图
有向完全图
5
7.1 图的逻辑结构
7.1.1 图的定义
● 相关概念 邻接和依附
● 邻接：对图 G=(V, VR)，如果边 (vi, vj)∈VR，则称顶点 vi 和 vj 互为邻 接点；如果弧<vi, vj>∈VR，则称顶点 vi 邻接到 vj，vj 邻接自 vi。
● 依附：对图 G=(V, VR)，如果边 (vi, vj)∈VR 或弧 <vi, vj>∈VR，则称 边 (vi, vj) 或弧 <vi, vj> 依附于顶点 vi 和 vj。

while (!StackEmpty(S)) { Pop(S，i); printf(i，G.vertices[i].data); ++count; //输出i号顶点并计数
for(p=G.vertices[i].firstarc; p; p=p->nextarc){ k=p—>adivex；//对i号顶点的每个邻接点入度减1 if(！(--indegree[k])) Push(S，k); //若入度减为0，则入栈
§7.5 有向无环图及其应用
❖有向无环图
在工程实践中，一个工程项目往往由若干个子项 目组成，这些子项目间往往有多种关系：
①先后关系，即必须在一子项目完成后，才能开 始实施另一个子项目；
②子项目之间无次序要求，即两个子项目可以同 时进行，互不影响。
§7.5 有向无环图及其应用
❖两种常用的活动网络(Activity Network)
3
4 4^
4
2 1^ 3^
1^
s
0 V1 3 V4
5 V6
4
V2 1 V3 2 V5 4
indegree[0..5] 0 0 0 0 0 0 012345
最后输出的拓扑序列为：v6v1v3v2v4v5
§7.5 有向无环图及其应用
G.vertices[0] v1
3
2
G.vertices[1] v打2 印^G.vertices[4].data
1. 输入AOV网络。令 n 为顶点个数。 2. 在AOV网络中选一个没有直接前驱的顶点, 并输出之; 3. 从图中删去该顶点, 同时删去所有它发出的有向边; 4. 重复以上 2、3 步, 直到：
全部顶点均已输出，拓扑有序序列形成，拓扑排序完成 或者，图中还有未输出的顶点，但已跳出处理循环。这说 明图中还剩下一些顶点，它们都有直接前驱，再也找不到 没有前驱的顶点了。这时AOV网络中必定存在有向环。