2022年数据结构教案第七章 .pdf

《2022年数据结构教案第七章 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构教案第七章 .pdf（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、名师精编优秀教案安徽新华电脑专修学院课堂教学教案（软工专业课使用）课程名称数据结构教学对象新华软工专业教材数据结构（ C语言）授课内容第七章图课 时3 教学目的与要求1、了解图的各种存储结构及其构造算法，了解实际问题的求解效率和采用何种存储结构和算法有密切联系2. 了 解 图 的 两 种 遍 历 ： 深 度 优 先 遍 历 和 广 度 优 先 遍 历 的 算 法 ，在学习中应注意图的遍历算法和树的遍历算法之间的类似和差异，树的先根遍历是一种深度优先搜索策略，树的层次遍历是一种广度优先搜索策略3. 了解课件中讨论的各种图的算法重点、难点重点：图的概念，存储，遍历，拓朴排序，最小生成树难点： 算法

2、实现、遍历有生成树和拓朴排序课型电脑应用课教学方法讲授、投影、板书教学过程设计（包括讲授知识、演示内容及案例、提问及学生演示内容）课程导入 ：前面所学的数据结构中有线性结构和非线性结构，其中线性表，栈和队列及串、数组均为线性结构，而上章所讲的树是非线性结构。树的结构特点是任一结点除根有且仅有一个直接前驱含有一个或多个直接后继。本章将学习另一种非常重要的非线性结构图，它的特点是：任意两个结点都有可能相关联，即任一结点可能有多个直接前驱和多个直接后继，结点间的邻接关系可以是任意的。（10 分钟）任务一、图的基本概念1图的定义精选学习资料 - - - - - - - - - 名师归纳总结 - - -

3、 - - - -第 1 页，共 12 页名师精编优秀教案教学过程设计(续表) 图 G 是集合 V 和集合 E 组成，记 G=（V，E） ，其中 V 是 G 中顶点的非空有限集，E 是 G 中边的集合， 面边是 V 中顶点的偶对。 若顶点的偶是有序的，刚称为有向图，用尖括号括起，若为无序的，则称为无向图。有向边又称为弧。图中 E（G）可以为空。任务二、图的基本述语1无向图边是无向的2有向图每条边是有向的3端点和邻接点4起点和邻接点5度、入度、出度6子图G=（V，E）和 G=（V，E） ，若 V是 V 的子集且 E是 E 的子集，并使得 E中的边仅与 V中顶点相关联，则 G是 G 的子图。7无向完

4、全图和在向完全图设一无向图有 N 个顶点，且有 n(n-1)/2 条边，即任何两顶点都有边相关联，这样的无向图称为无向完全图。有向图中基有n(n-1)条边，即任何两顶点都有一对反向弧，则此有向图称为有向完全图。8路径和路径长度及简单路径路径是顶点的序列。路径长度是路径所含的边。若一条路径的顶点序列中不出现重复顶点，称为简单路径9回路或环10 连通、连通图和连通分图11 强连通图和强连通分图12 赋权图精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 12 页名师精编优秀教案任务三、图的存储结构1.图的邻接矩阵存储它是用二维数组来表示图中顶

5、点之间的邻接关系，可将G 的邻接矩阵定义为一个 n 阶方阵。#define MAVX 50 Void creatadjmatrix(int costMAXVMAXV,int vexnum,int enum) int I,j,k,v1,v2; For(i=1;i=vexnum;i+) For(j=1;j=vexnum;j+) Costij=0; For(k=1;k=enum;k+) scanf(“%d%d ”,&v1,&v2);Costv1v2=1; Costv2v1=1; 2、邻接链表一个图的邻接链表存储结构的类型定义：#define maxvertex 50 Typedef struct a

6、rcnode int adjvex; Struct arnode *nextarc; arcnodetyp; Type struct vexnode int vertex; Arcnodetp *firstarc; adjlistmaxvertex; Typedef struct graph adjlist adjlist; Int vexnum,arcnum; graphtp; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 12 页名师精编优秀教案复习思考题作业上机任务1. 搞清图的基本概念的含义2. 描述图的存储的实现参考文献晋良

7、颖数据结构人民邮电大学出版社课后记（或归纳小结）本次课程就介绍这里结束，总结本次的内容；精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 12 页名师精编优秀教案安徽新华电脑专修学院课堂教学教案（软工专业课使用）课程名称数据结构教学对象新华软工专业教材数据结构（ C语言）授课内容第七章图课 时3 教学目的与要求1、了解图的各种存储结构及其构造算法，了解实际问题的求解效率和采用何种存储结构和算法有密切联系2. 了 解 图 的 两 种 遍 历 ： 深 度 优 先 遍 历 和 广 度 优 先 遍 历 的 算 法 ，在学习中应注意图的遍历算法和树

8、的遍历算法之间的类似和差异，树的先根遍历是一种深度优先搜索策略，树的层次遍历是一种广度优先搜索策略3. 了解课件中讨论的各种图的算法重点、难点重点：图的概念，存储，遍历，拓朴排序，最小生成树难点： 算法实现、遍历有生成树和拓朴排序课型电脑应用课教学方法讲授、投影、板书教学过程设计（包括讲授知识、演示内容及案例、提问及学生演示内容）复习内容：上讲介绍了图的基本概念，图在计算机中的存储结构，具体讲的图的邻接矩阵和邻接表的存储。这两种存储结构的算法需要重点掌握。课程导入：树一章中介绍了树的先根、 中根和后根遍历， 即按照某种顺序对树中的所有结点访问一次且只访问一次的顺序，那么对图来说又怎么来访问它的

9、每一个结点呢，我们称为图的遍历。任务一、图的遍历1、深度优先搜索基本思想：从图G 中某个顶点出发，访问V1，然后选择一下与V1 相邻且未被访问过的顶点Vi 访问，再从 Vi 出发选择一个与Vi 相邻接且未被访问过的顶点 Vj 访问，依次继续。若当前被访问过的顶点的所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后一个仍未被访问的相邻接顶点 Vw，从 Vw 出以按同样方法向前遍历，直到图中所有的顶点被访问。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 12 页名师精编优秀教案教学过程设计(续表) 2广度优先搜索基本思想：首先访问初

10、始点Vi,并将其标记为已访问过，接着访问Vi 的所有未被访问过的邻接顶点Vi1,vi2vit, 并均标记为已访问地过，然后再按照vi1,vi2vit 的次序，访问每一个顶点的所有未被访问过的邻接顶点，并均标记为已访问，依次类推，直到图 G 中所有和初始点 Vi 有路径相通的顶点都有被访问过为止。void BFSTraverse(Graph G , Status (* visit)(int v) for(v=0; vG.vexnum; +v) visitedv = FALSE; IntiQueque(Q); for(v=0; vG.vexnum; +v) if(!visitedv) EnQueu

11、e(Q,v); while(!QueueEmpty(Q) DeQueue(u); visitedu = TRUE; Visit (u); for(w=FirstAdjVex(G , u); w; w = NextAdjVex(G,u,w) if(!visitedw) visitedw=TRUE; visited(w); EnQueue(G ,w); 任务二、图的生成树1、生成树i.定义：所有顶点均由边连接在一起，但不存在回路的图叫 ii.深度优先生成树与广度优先生成树iii.生成森林：非连通图每个连通分量的生成树一起组成非连通图的 iv.说明1.一个图可以有许多棵不同的生成树2.所有生成树具有

12、以下共同特点：a)生成树的顶点个数与图的顶点个数相同b)生成树是图的极小连通子图c)一个有 n 个顶点的连通图的生成树有n-1 条边d)生成树中任意两个顶点间的路径是唯一的e)在生成树中再加一条边必然形成回路3.含 n 个顶点 n-1 条边的图不一定是生成树2、最小生成树（1） 网络及其邻接矩阵（2） 最小生成树3、求最小生成树的常用算法（1） 普里姆算法精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 12 页名师精编优秀教案算法思想：设 N=(V,E) 是连通网， TE 是 N 上最小生成树中边的集合初始令 U=u0,(u0V), T

13、E=在所有 u U,vV-U 的边(u,v) E 中，找一条代价最小的边(u0,v0) 将(u0,v0)并入集合 TE，同时 v0 并入 U 重复上述操作直至U=V 为止，则 T=(V,TE) 为 N 的最小生成树算法实现：图用邻接矩阵表示算法描述算法评价： T(n)=O(n2) （2） 克鲁斯卡尔算法算法思想：设连通网N=(V,E) ，令最小生成树初始状态为只有 n 个顶点而无边的非连通图T=(V,) ， 每个顶点自成一个连通分量在 E 中选取代价最小的边，若该边依附的顶点落在T 中不同的连通分量上，则将此边加入到 T 中；否则，舍去此边，选取下一条代价最小的边依此类推，直至 T 中所有顶点

14、都在同一连通分量上为止（3）统观法精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 12 页名师精编优秀教案复习思考题作业上机任务1、课后习题 2 题2、P138 第三题3、P138 4、5、6 题参考文献晋良颖数据结构人民邮电大学出版社课后记（或归纳小结）本次课程的内容为图的遍历和最小生成树，相对较难，课余时间要多看，多做题。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 12 页名师精编优秀教案安徽新华电脑专修学院课堂教学教案（软工专业课使用）课程名称数据结构教学对象新华软工专

15、业教材数据结构（ C语言）授课内容第七章图课 时3 教学目的与要求1、了解图的各种存储结构及其构造算法，了解实际问题的求解效率和采用何种存储结构和算法有密切联系2. 了 解 图 的 两 种 遍 历 ： 深 度 优 先 遍 历 和 广 度 优 先 遍 历 的 算 法 ，在学习中应注意图的遍历算法和树的遍历算法之间的类似和差异，树的先根遍历是一种深度优先搜索策略，树的层次遍历是一种广度优先搜索策略3. 了解课件中讨论的各种图的算法重点、难点重点：图的概念，存储，遍历，拓朴排序，最小生成树难点： 算法实现、遍历有生成树和拓朴排序课型电脑应用课教学方法讲授、投影、板书教学过程设计（包括讲授知识、演示内

16、容及案例、提问及学生演示内容）复习内容：上一讲主要讲解的是图的深度优先和广度优先遍历及其算法的实现，以及生成树和最小生成树及求解最小生成树的各种算法，如普里姆算法、克鲁期斯卡尔算法等。课程导入 :用带权的有向图表示一个交通运输网，图中：顶点表示城市边表示城市间的交通联系权表示此线路的长度或沿此线路运输所花的时间或费用等问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径最短路径精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 12 页名师精编优秀教案教学过程设计(续表) 任务一、最短路径迪杰斯特拉 (Dij

17、kstra) 算法(1)设置两个顶点的集合T 和 S; 集合 S存放已找到最短路径的顶点集合 T 存放当前还未找到最短路径的顶点(2)初始状态时 ,S只包含源点 v0 ; (3)从 T 中选取某个顶点 vi(要求 vi 到 v0的路径长度最短 ) 加入到 S中,; (4)S 中每加入一个顶点vi,都要修改顶点 v0 到 T 中剩余顶点的最短路径长度值 ; 它们的值为原来值与 新值的较小者新值是 vi 的最短路径长度值加上vi 到该顶点的路径长度(5)不断重复 (3)和(4),直到 S包含全部顶点 ; 任务二、拓朴排序1、问题提出：学生选修课程问题顶点表示课程有向弧 表示先决条件，若课程i 是课

18、程 j 的先决条件，则图中有弧 学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业拓扑排序2、定义AOV 网用顶点表示活动， 用弧表示活动间优先关系的有向图称为顶点表示活动的网 (Activity On Vertex network)，简称 AOV 网若 是图中有向边，则vi 是 vj 的直接前驱；vj 是 vi 的直接后继AOV 网中不允许有回路， 这意味着某项活动以自己拓扑排序 把 AOV 网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫 检测 AOV 网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV 网必定不存

19、在环拓扑排序的方法在有向图中选一个没有前驱的顶点且输出之从图中删除该顶点和所有以它为尾的弧重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止为先决条件精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 12 页名师精编优秀教案拓扑排序 把 AOV 网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫 检测 AOV 网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV 网必定不存在环拓扑排序的方法在有向图中选一个没有前驱的顶点且输出之从图中删除该顶点和所有以它为

20、尾的弧重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止算法实现以邻接表作存储结构把邻接表中所有入度为0 的顶点进栈栈非空时，输出栈顶元素Vj 并退栈；在邻接表中查找Vj 的直接后继 Vk，把 Vk 的入度减 1；若 Vk 的入度为0 则进栈重复上述操作直至栈空为止。若栈空时输出的顶点个数不是 n，则有向图有环；否则，拓扑排序完毕邻接表结点：typedef struct node int vex; /顶点域struct node *next; /链域JD; 表头结点：typedef struct tnode int in; /入度域struct node *link; /链域TD; TD gM; /g0不用精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 12 页名师精编优秀教案复习思考题作业上机任务3. 最后习题第 7 题4. P139 第 12，13 题参考文献晋良颖数据结构人民邮电大学出版社课后记（或归纳小结）本次课程主要讲解的是拓朴排序和最短路径，至此本章已全部结束，图在现实生活中有着广泛的应用，并且本章较有难度，故同学们需要要搞清概念的同时多看看各个算法，通过做题来掌握各知识点。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 12 页