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

精选学习资料 - - - - - - - - - 名师精编 优秀教案安徽新华电脑专修学院课堂教学教案（软工专业课使用）课程名称数据结构教学对象新华软工专业课 时3 教材数据结构（ C语言）授课内容第七章图1、明白图的各种储备结构及其构造算法,种储备结构和算法有亲密联系明白实际问题的求解效率和采纳何教学目的 与要求重点、难点2. 了 解 图 的 两 种 遍 历 ： 深 度 优 先 遍 历 和 广 度 优 先 遍 历 的 算 法 ,在学习中应留意图的遍历算法和树的遍历算法之间的类似和差异,树的先根遍历是一种深度优先搜寻策略,树的层次遍历是一种广度优先搜寻策略3. 明白课件中争论的各种图的算法重点：图的概念,储备,遍历,拓朴排序,最小生成树难点： 算法实现、遍历有生成树和拓朴排序课型电脑应用课教学方法讲授、投影、板书名师归纳总结 教学过程课程导入 ：前面所学的数据结构中有线性结构和非线性结构,其第 1 页,共 12 页中线性表,栈和队列及串、数组均为线性结构,而上章所讲的树设计是非线性结构；树的结构特点是任一结点除根有且仅有一个直接（包括讲授前驱含有一个或多个直接后继；本章将学习另一种特别重要的非学问、演示线性结构图,它的特点是：任意两个结点都有可能相关联,即任内容及案一结点可能有多个直接前驱和多个直接后继,结点间的邻接关系例、提问及可以是任意的；（10 分钟）同学演示内容）任务一、图的基本概念1图的定义- - - - - - -精选学习资料 - - - - - - - - - 名师精编 优秀教案图 G 是集合 V 和集合 E 组成,记 G=（V,E）,其中 V 是 G 中顶点的非空有限集,E 是 G 中边的集合, 面边是 V 中顶点的偶对； 如顶点的偶是有序的,刚称为有向图,用尖括号括起,如为无序的,就称为无向图；有向边又称为弧；图中 E（G）可以为空；任务二、图的基本述语1无向图边是无向的2有向图每条边是有向的教3端点和邻接点起点和邻接点4度、入度、出度5学过6子图程设7G=（V,E）和 G=（V,E）,如 V是 V 的子集且 E是 E 的子集,计并使得 E中的边仅与 V 中顶点相关联,就 G是 G 的子图；续表 无向完全图和在向完全图设一无向图有 N 个顶点,且有 nn-1/2 条边,即任何两顶点都有边相关联,这样的无向图称为无向完全图；有向图中基有 nn-1条边,即任何两顶点都有一对反向弧,就此有向图称为有向完全图；8路径和路径长度及简洁路径路径是顶点的序列；路径长度是路径所含的边；如一条路径的顶点序列中不显现重复顶点,称为简洁路径9回路或环10 连通、连通图和连通分图11 强连通图和强连通分图12 赋权图名师归纳总结 - - - - - - -第 2 页,共 12 页精选学习资料 - - - - - - - - - 名师精编 优秀教案任务三、图的储备结构1.图的邻接矩阵储备它是用二维数组来表示图中顶点之间的邻接关系,可将 义为一个 n 阶方阵；G 的邻接矩阵定#define MAVX 50 Void creatadjmatrixint int I,j,k,v1,v2; costMAXVMAXV,int vexnum,int enum Fori=1;i<=vexnum;i+ Forj=1;j<=vexnum;j+ Costij=0; Fork=1;k<=enum;k+ scanf“ %d%d” ,&v1,&v2; Costv1v2=1; Costv2v1=1; 2、邻接链表一个图的邻接链表储备结构的类型定义：#define maxvertex 50 Typedef struct arcnode 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. 描述图的储备的实现作业上机任务参考文献晋良颖数据结构人民邮电高校出版社课后记（或归纳小本次课程就介绍这里终止,总结本次的内容；结）名师归纳总结 - - - - - - -第 4 页,共 12 页精选学习资料 - - - - - - - - - 名师精编 优秀教案安徽新华电脑专修学院课堂教学教案（软工专业课使用）课程名称数据结构教学对象新华软工专业课 时3 教材数据结构（ C语言）授课内容第七章图1、明白图的各种储备结构及其构造算法,种储备结构和算法有亲密联系明白实际问题的求解效率和采纳何教学目的 与要求重点、难点2. 了 解 图 的 两 种 遍 历 ： 深 度 优 先 遍 历 和 广 度 优 先 遍 历 的 算 法 ,在学习中应留意图的遍历算法和树的遍历算法之间的类似和差异,树的先根遍历是一种深度优先搜寻策略,树的层次遍历是一种广度优先搜寻策略3. 明白课件中争论的各种图的算法重点：图的概念,储备,遍历,拓朴排序,最小生成树难点： 算法实现、遍历有生成树和拓朴排序课型电脑应用课教学方法讲授、投影、板书名师归纳总结 教学过程复习内容：上讲介绍了图的基本概念,图在运算机中的储备结构,详细讲的图的邻设计接矩阵和邻接表的储备；这两种储备结构的算法需要重点把握；课程导入：（包括讲授树一章中介绍了树的先根、 中根和后根遍历, 即根据某种次序对树中的学问、演示全部结点拜访一次且只拜访一次的次序,那么对图来说又怎么来拜访它的每一个结点呢,我们称为图的遍历；内容及案任务一、图的遍历例、提问及1、深度优先搜寻基本思想：从图G 中某个顶点动身,拜访V1,然后挑选一下与V1 相邻同学演示内且未被拜访过的顶点Vi 拜访,再从 Vi 动身挑选一个与Vi 相邻接且未被拜访过的顶点 Vj 拜访,依次连续；如当前被拜访过的顶点的全部邻接顶容）点都已被拜访, 就回退到已被拜访的顶点序列中最终一个仍未被拜访的相邻接顶点 Vw,从 Vw 出以按同样方法向前遍历,直到图中全部的顶点被拜访；第 5 页,共 12 页- - - - - - -精选学习资料 - - - - - - - - - 名师精编 优秀教案2广度优先搜寻基本思想：第一拜访初始点 Vi,并将其标记为已拜访过,接着拜访 Vi 的所 有未被拜访过的邻接顶点 Vi1,vi2 vit,并均标记为已拜访地过,然后再根据 vi1,vi2 vit的次序,拜访每一个顶点的全部未被拜访过的邻接顶点,并均标 记为已拜访,依次类推, 直到图 G 中全部和初始点 Vi 有路径相通的顶点都有被拜访过为止；void BFSTraverseGraph G, Status * visitint v forv=0; v<G.vexnum; +v visitedv = FALSE; IntiQuequeQ; forv=0; v<G.vexnum; +v if.visitedv EnQueueQ,v; while.QueueEmptyQ DeQueueu; visitedu = TRUE; Visit u; forw=FirstAdjVexG , u; w; w = NextAdjVexG,u,w 教 if.visitedw visitedw=TRUE; visitedw; EnQueueG,w; 学 过程 任务二、图的生成树设计续表 1、生成树定义：全部顶点均由边连接在一起,但不存在回路的图叫 i.ii.深度优先生成树与广度优先生成树iii.生成森林：非连通图每个连通重量的生成树一起组成非连通图的 iv.说明1.一个图可以有很多棵不同的生成树2.全部生成树具有以下共同特点：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,u0 V, TE= 在全部 u U,v V-U 的边 u,v E 中,找一条代价最小的边 u0,v0 将u0,v0并入集合 TE,同时 v0 并入 U 重复上述操作直至 U=V 为止,就 T=V,TE 为 N 的最小生成树 算法实现：图用邻接矩阵表示算法描述 算法评判： Tn=On2 （2） 克鲁斯卡尔算法算法思想：设连通网N=V,E ,令最小生成树初始状态为只有 n 个顶点而无边的非连通图T=V, ,每个顶点自成一个连通重量 在 E 中选取代价最小的边,如该边依附的顶点落在 T 中不同的连通重量上,就将此边加入到 T 中；否就,舍去此边,选取下一条代价最小的边 依此类推,直至 T 中全部顶点都在同一连通重量上为止（3）统观法名师归纳总结 - - - - - - -第 7 页,共 12 页精选学习资料 - - - - - - - - - 复习摸索题1、名师精编优秀教案课后习题 2 题作业2、P138 第三题人民邮电高校出版社上机任务3、P138 4、5、6 题参考文献晋良颖数据结构课后记 本次课程的内容为图的遍历和最小生成树,相对较难,课余时（或归纳小 间要多看,多做题；结）名师归纳总结 - - - - - - -第 8 页,共 12 页精选学习资料 - - - - - - - - - 名师精编 优秀教案安徽新华电脑专修学院课堂教学教案（软工专业课使用）课程名称数据结构教学对象新华软工专业课 时3 教材数据结构（ C语言）授课内容第七章图1、明白图的各种储备结构及其构造算法,种储备结构和算法有亲密联系明白实际问题的求解效率和采纳何教学目的 与要求重点、难点2. 了 解 图 的 两 种 遍 历 ： 深 度 优 先 遍 历 和 广 度 优 先 遍 历 的 算 法 ,在学习中应留意图的遍历算法和树的遍历算法之间的类似和差异,树的先根遍历是一种深度优先搜寻策略,树的层次遍历是一种广度优先搜寻策略3. 明白课件中争论的各种图的算法重点：图的概念,储备,遍历,拓朴排序,最小生成树难点： 算法实现、遍历有生成树和拓朴排序课型电脑应用课教学方法讲授、投影、板书教学过程 设计（包括讲授 学问、演示 内容及案 例、提问及复习内容： 上一讲主要讲解的是图的深度优先和广度优先遍历及其算法的实现,以及生成树和最小生成树及求解最小生成树的各种算法,如普里姆算 法、克鲁期斯卡尔算法等；课程导入 :用带权的有向图表示一个交通运输网,图中：顶点 表示城市 边 表示城市间的交通联系 权 表示此线路的长度或沿此线路运输所花的时间或费用等 问题：从某顶点动身,沿图的边到达另一顶点所经过的路径中,各边上权值之和最小的一条路径 最短路径同学演示内容）名师归纳总结 - - - - - - -第 9 页,共 12 页精选学习资料 - - - - - - - - - 名师精编 优秀教案任务一、最短路径迪杰斯特拉 Dijkstra 算法1设置两个顶点的集合 T 和 S; 集合 S 存放已找到最短路径的顶点 集 合 T 存放当前仍未找到最短路径的顶点2初始状态时 ,S 只包含源点 v0 ; 3从 T 中选取某个顶点 vi 要求 vi 到 v0的路径长度最短 加入到 S中,; 4S 中每加入一个顶点 vi,都要修改顶点 v0 到 T 中剩余顶点的最短路径长度值 ; 它们的值为原先值与 新值的较小者 新值是 vi 的最短路径长度值加上vi 到该顶点的路径长度5不断重复 3和4,直到 S 包含全部顶点 ; 任务二、拓朴排序 1、问题提出：同学选修课程问题顶点 表示课程有向弧 表示先决条件,如课程i 是课程 j 的先决条件,就图中有弧 <i,j> 教 学 过 程 设 计 续表 同学应按怎样的次序学习这些课程,才能无冲突、顺当地完成学业 拓扑排序 2、定义 AOV 网 用顶点表示活动, 用弧表示活动间优先关系的有向图称为顶点表示活动的网 Activity On Vertex network,简称 AOV 网如<vi,vj> 是图中有向边,就vi 是 vj 的直接前驱；vj 是 vi 的直接后继AOV 网中不答应有回路, 这意味着某项活动以自 己拓扑排序 把 AOV 网络中各顶点根据它们 相互之间的优先关系排列成一个线性序列的过程 叫 检测 AOV 网中是否存在环方法：对有向图构造 其顶点的拓扑有序序列,如网中全部顶点都在它 的拓扑有序序列中,就该 AOV 网必定不存在环 拓扑排序的方法在有向图中选一个没有前驱的顶点且输出之 从图中删除该顶点和全部以它为尾的弧重复上述两步,直至全部顶点均已输出；或者当 图中不存在无前驱的顶点为止为先决条件名师归纳总结 - - - - - - -第 10 页,共 12 页精选学习资料 - - - - - - - - - 名师精编 优秀教案拓扑排序 把 AOV 网络中各顶点根据它们相互之间的优先关系排列成一个线性序列的过程叫 检测 AOV 网中是否存在环方法：对有向图构造其顶点的拓扑有序序列,如网中全部顶点都在它的拓扑有序序列中,就该 AOV 网必定不存在环拓扑排序的方法在有向图中选一个没有前驱的顶点且输出之从图中删除该顶点和全部以它为尾的弧重复上述两步,直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止算法实现以邻接表作储备结构把邻接表中全部入度为 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 页（或归纳小同学们需要要搞清概念的同时多看看各个算法,通过做题来把握结）各学问点；- - - - - - -