数据结构教案模板.doc

数据结构教案模板篇一：新版数据结构教案五邑大学信息学院数据结构教案20XX20XX年度 第二学期课 程 名 称数据结构课 程 主 讲 人白明、金旺春课程所属教研室 软件工程、计算机科学与技术课程类型及学时理论课（含实验）、72学时授课教材版本数据结构（C+版）清华大学出版社授 课 班 级计算机科学与技术20XX级1班、2班网络工程20XX级1班 软件工程20XX级1班授 课 日 期20XX年3月7月五邑大学信息学院 制二七年一月1234篇二：数据结构详细教案图数据结构教案第七章 图第7章 图【学习目标】1领会图的类型定义。2熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。3熟练掌握图的两种遍历算法。4理解各种图的应用问题的算法。【重点和难点】图的应用极为广泛，而且图的各种应用问题的算法都比较经典，因此本章重点在于理解各种图的算法及其应用场合。【知识点】图的类型定义、图的存储表示、图的深度优先搜索遍历和图的广度优先搜索遍历、无向网的最小生成树、最短路径、拓扑排序、关键路径【学习指南】离散数学中的图论是专门研究图性质的一个数学分支，但图论注重研究图的纯数学性质，而数据结构中对图的讨论则侧重于在计算机中如何表示图以及如何实现图的操作和应用等。图是较线性表和树更为复杂的数据结构，因此和线性表、树不同，虽然在遍历图的同时可以对顶点或弧进行各种操作，但更多图的应用问题如求最小生成树和最短路径等在图论的研究中都早已有了特定算法，在本章中主要是介绍它们在计算机中的具体实现。这些算法乍一看都比较难，应多对照具体图例的存储结构进行学习。而图遍历的两种搜索路径和树遍历的两种搜索路径极为相似，应将两者的算法对照学习以便提高学习的效益。【课前思考】1. 你有没有发现现在的十字路口的交通灯已从过去的一对改为三对，即每个方向的直行、左拐和右拐能否通行都有相应的交通灯指明。你能否对某个丁字路口的6条通路画出和第一章绪论中介绍的"五叉路口交通管理示意图"相类似的图？2. 如果每次让三条路同时通行，那么从图看出哪些路可以同时通行？同时可通行的路为：,目 录第7章 图 . 1 图的定义和基本术语 . 1 图的存储和创建 . 2 图的存储表示 . 2 图的创建 . 4 图的遍历 . 5 深度优先搜索 . 5 广度优先搜索 . 6 遍历算法的应用 . 7 应用问题概述 . 7 求一条包含图中所有顶点的简单路径. 8 求距v0的各顶点中最短路径长度最长的一个顶点 . 9 图的连通性问题 . 10 无向图的连通分量和生成树 . 10 最小生成树 . 12 有向无环图及其应用 . 12第7章 图 图的定义和基本术语1、图的特征任意两个数据元素之间都可能相关。结点之间的关系是多对多的。G =2、基本术语结点： 顶点结点间的关系：无向图：边，v与w互为邻接点，边依附于顶点v, w，边和顶点v, w相关联v的度：和v相关联的边的数目。有向图：弧，v弧尾，w弧头，顶点v邻接到顶点w，顶点w邻接自顶点v，弧和顶点v,w相关联。v的入度：以v为弧头的弧的数目；v的出度：以v为弧尾的弧的数目；v的度：v的入度与出度之和。路径、回路、简单路径、简单回路连通性：若从顶点v到顶点v有路径，则称v和v是连通的图的规模：顶点数n、边数e、顶点的度子图：G= , G = ，若V?V且E ?E，则称G是G的子图。图的分类：1）关系的方向性（无向/有向）、关系上是否有附加的数权有向图、无向图、有向网、无向网2）边数：完全图 / 2的无向图)、有向完全图的有向图)稀疏图、稠密图3）连通性：无向图：连通图、连通分量、生成树、生成森林有向图：强/弱连通图、强连通分量、生成树、生成森林3、抽象数据类型定义ADT Graph数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R = VRVR = |v, w?V且P，表示从v到w的弧，谓词P定义了弧的意义或信息基本操作：CreateGraph初始条件：V是图的顶点集，VR是图中弧的集合操作结果：按V和VR的定义构造图GDestroyGraph初始条件：图G存在操作结果：销毁图GLocateVex初始条件：图G已存在，u和G中顶点有相同特征操作结果：若G中存在顶点u，则返回该顶点在图中位置，否则返回其它信息GetVex初始条件：图G存在，v是G中某个顶点操作结果：返回v的值PutVex初始条件：图G存在，v是G中某个顶点操作结果：对v赋值valueFirstAdjVex初始条件：图G存在，v是G中某个顶点操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接顶点，则返回“空”NextAdjVex初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点操作结果：返回v的下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”InsertVex初始条件：图G存在，v和G中顶点有相同特征操作结果：在图中增添新顶点vDeleteVex初始条件：图G存在，v是G中某个顶点操作结果：删除G中顶点v及其相关的弧InsertArc初始条件：图G存在，v和w是G中两个顶点操作结果：在图G中增添弧，若G是无向的，则还应增添对称弧DeleteArc初始条件：图G存在，v和w是G中两个顶点操作结果：删除G中的弧，若G是无向的，则还应删除对称弧DFSTraverse)初始条件：图G存在，v是G中某个顶点，visit是对顶点的应用函数操作结果：从顶点v起深度优先遍历图G，并对每个顶点调用函数visit一次且至多一次。一旦visit失败，则操作失败BFSTraverse)初始条件：图G存在，v是G中某个顶点，visit是对顶点的应用函数操作结果：从顶点v起广度优先遍历图G，并对每个顶点调用函数visit一次且至多一次。一旦visit失败，则操作失败ADT Graph 图的存储和创建 图的存储表示1、图的存储表示分析顶点之间的关系是多对多的，由于m和n都是不定的，无法给出一个这种多对多的关系向线性关系的映射公式图中的关系不能通过顺序映像反映；必须另外引入存储空间反映顶点之间的邻接关系。图的存储结构：1）顶点信息；2）边信息；3）整体信息：顶点数、边数、图的种类顶点集的存储：图的应用中，顶点集动态变化的几率十分小篇三：数据结构教学设计教案教 案课 程 名 称： 数据结构课程教学设计 院（系、部）： 计算机与信息工程学院基础教研室 主 讲 教 师：刘 国 英 使 用 教 材：数据结构（C语言版）严蔚敏编著授 课 内 容：