教案(数据结构)

1、江门职业技术学院教案 XX职业技术学院学年第二学期教案学科：数据结构/嵌入式应用算法基础系部：电子与信息技术系教研室：计算机教研室授课班级：11软件工程/11嵌入式应用；任课教师：授课时间第1周授课地点实训B208课程类型理论课授课题目概述授课班级教学目的与教学要求1什么是数据结构2基本概念和术语3算法和算法分析重点与难占八、算法分析教学方法手段（教具）讲授法主要内容基本概念和术语参考资料精品课程网站： HYPERLINK /other/sjjg/jiaoan/jiaoan.html /other/sjjg/jiaoan/jiaoan.html HYPERLINK /sjjg/ /sjjg/h

2、ttp:/wsjiaoxue/kejian/fanshixi/DataStructure/index.asp课后作业与思考题P121.1;1.2教学后记教学过程时间分配1.1什么是数据结构举例说明数据结构课程要解决的问题数据结构课程的创建数据结构课程所处的地位1.2基本概念和术语基本概念和术语：数据、数据元素、数据对象、数据结构等数据结构的分类数据结构的二元组表示抽象数据类型的概念和三元组表示1.3算法和算法分析算法的概念和5个重要特性算法设计的4个要求算法效率的度量：时间复杂度授课时间第2周；第3周授课地点课程类型理论课授课题目线性表授课班级教学目的与教学要求熟练线性表的基本特征和基本运算重

3、点与难占八、线性表的插入与删除教学方法手段（教具）讲授法主要内容数组的基本特点及寻址方式线性数据结构的基本特征和基本运算参考资料精品课程网站： HYPERLINK /other/sjjg/jiaoan/jiaoan.html /other/sjjg/jiaoan/jiaoan.html HYPERLINK /sjjg/ /sjjg/http:/wsjiaoxue/kejian/fanshixi/DataStructure/index.asp课后作业与思考题P372.4;2.5;2.6;2.7教学后记教学过程时间分配1线性表的类型定义线性表的定义和相关术语线性表的抽象数据类型定义举例2线性表的顺

4、序表示和实现线性表的顺序表示方式线性表的动态分配顺序存储结构线性表顺序表示方式下的操作：InitList_SqListInsert_SqListDelete_SqLocateElem_SqMergeList_Sq结合第一章内容，分析上述算法的时间复杂度授课时间第3周授课地点课程类型理论课授课题目线性表授课班级教学目的与教学要求熟练掌握以下内容：单链表的结构特点、基本运算并能设计简单算法循环链表的结构特点、基本运算并能设计简单算法重点与难占八、双链表插入、删除运算的算法利用链接结构的特点设计有效算法，解决与链表结构相关的应用问题教学方法手段（教具）讲授法主要内容单链表的结点形式、组织方法和特点单

5、链表的基本运算和相应的算法循环链表的组织方法和基本运算算法顺序表与链表比较，各自的优、缺点链表的应用参考资料精品课程网站： HYPERLINK /other/sjjg/jiaoan/jiaoan.html /other/sjjg/jiaoan/jiaoan.html HYPERLINK /sjjg/ /sjjg/http:/wsjiaoxue/kejian/fanshixi/DataStructure/index.asp课后作业与思考题P372.4;2.5;2.6;2.7教学后记教学过程时间分配链表基本结构结构讨论静态链表：定义及示意图动态链表：详细介绍链表的相关知识，链表的类型说明及示意图。

6、带头结点的链表结构示意图单链表上运算的实现：初始化链表（思考题）链表不带头结点时的初始化算法。求链表长度按序号取元素结点（算法流程图）按值查询元素（算法流程图）插入（示意图）删除（示意图）链表的构造（算法的基本框架，.尾插法建立链表的算法，.头插法建立链表的算法）链表结构的应用：列举若干求解实例5.4其它链表结构：单循环、带尾指针的单循环链表，双链表、双循环链表结构讨论，运算实现的变化讨论。授课时间第4周授课地点课程类型理论课授课题目堆栈和队列授课班级教学目的与教学要求掌握堆栈的有关操作；理解队列的定义、特性和运算；理解队列的顺序存储实现及其性能分析；理解循环队列的背景和实现方法。重点与难占八

7、、堆栈的应用教学方法手段（教具）讲授法主要内容栈的定义和运算；栈的C描述、顺序存储结构及运算实现；栈在表达式求解中的作用。队列的定义和运算；队列的C描述、顺序存储结构以及运算实现参考资料精品课程网站： HYPERLINK /other/sjjg/jiaoan/jiaoan.html /other/sjjg/jiaoan/jiaoan.html课后作业与思考题P583.1;3.2;3.3教学后记教学过程栈的定义和运算栈的定义及相关概念，栈的示意图栈的特征栈的基本运算和C描述(注意几个关键问题的细节讨论)：(1)初始化栈(2)判断栈是否为空(3)取栈顶元素值(4)入栈(5)出栈(6)判断栈是否为满

8、初始化的讨论，函数返回值的方法，错误信息类型的引入，私有和公用属性的讨论。顺序栈时间分配栈的顺序存储结构顺序栈，示意图顺序栈上运算的实现(结合示意图分析算法思想，然后写出算法)栈的应用举出若干应用实例，说明栈在软件设计中的广泛应用。栈的基本应用实例：表达式的计算，从软件技术的发展到表达式的计算的介绍，表达式计算方法的讨论(以示意图表现计算过程)。队列的定义和运算队列队列的特性队列示意图队尾，队头，入队和出队队列的基本运算和C+描述：(1)初始化队列(2)判队列是否为空(3)取队头元素(4)入队(5)出队(6)判队列是否为满基本讨论与栈类似。3.2顺序队列和循环队列队列的顺序存储结构顺序队列，示

9、意图由顺序队列中运算的实现可能出现假溢出，引入循环队列(示意图)。提出问题：对循环队列，如何判断队列的满和空的状态？解决方法：设置一个入队(出队)标志；或者少用一个元素空间。循环队列中运算的实现(结合示意图讲解)。授课时间第5周授课地点教C504教D502课程类型理论课授课题目串授课班级07软件工程；07信息管理教学目的与教学要求理理解串的相关概念，串的基本和常用运算的定义，理解串的两种顺序存储方式，能实现有关运算。重点与难占八、串的两种顺序存储方式，实现有关运算。教学方法手段（教具）讲授法主要内容串的概念、运算、存储结构及运算的实现。参考资料精品课程网站： HYPERLINK /other/

10、sjjg/jiaoan/jiaoan.html /other/sjjg/jiaoan/jiaoan.html HYPERLINK /sjjg/ /sjjg/http:/wsjiaoxue/kejian/fanshixi/DataStructure/index.asp课后作业与思考题P764.1;4.2;4.3;4.4教学后记教学过程时间分配串的定义串名，串值，串的长度，空串，子串（举例说明）串的基本运算：（1）赋值（2）求长度（3）连接（4）求子串（5）串比较（比较是否相等，比较大小）串的常用运算：（6）插入（7）删除串的存储：顺序串，链串（结点大小的概念，示意图）举例说明链串运算的实现。授课

11、时间第6,7,8周授课地点教C504教D502课程类型理论课授课题目树和二叉树授课班级07软件工程；07信息管理教学目的与教学要求理解树和二叉树的定义及相关术语；理解二叉树的五个性质及相关概念；理解二叉树的两种存储结构的形式、描述及特点，理解二叉树的遍历运算，并能综合应用理解树和森林的存储结构及其描述，树（森林）与二叉树的相互转换，树（森林）的遍历算法；理解树模型在软件设计中的作用；理解哈夫曼树的有关概念、应用及构造。重点与难占八、有关树和二叉树的算法。教学方法手段（教具）讲授法主要内容树和二叉树的概念，二叉树的性质和存储方法，二叉树的三种遍历算法和线索化概念及算法，树的存储，二叉树与树（森林

12、）的相互转换，哈夫曼树。参考资料精品课程网站： HYPERLINK /other/sjjg/jiaoan/jiaoan.html /other/sjjg/jiaoan/jiaoan.html HYPERLINK /sjjg/ /sjjg/http:/wsjiaoxue/kejian/fanshixi/DataStructure/index.asp课后作业与思考题P1466.1;6.2;6.3;6.4;6.5;6.7;6.8;6.18;6.22教学后记时间教学过程分配7.1树的定义和运算举出若干现实生活和软件设计中的树形结构的实例，引入树的概念。树，根，子树几种常见的表示树结构的形式：（1）图形

13、表示法（2）嵌套集合表示法（3）凹入表表示法（4）广义表表示法与树有关的概念：结点的度，叶子结点（终结点），分支结点（非终结点，内部结点），树的度；孩子结点，双亲结点（父结点），兄弟结点，祖先结点和后代结点；层次，树的高度（深度）；有序树，无序树，森林。树（森林）的基本运算：（1）初始化树（2）插入子树（3）插入兄弟结点（4）查询根结点（5）查询父结点（6）查询孩子结点（7）查询兄弟结点由树和森林的存储结构引入二叉树。7.2二叉树的定义、性质和存储二叉树的定义，左、右子树，示意图举例说明树和二叉树的区别二叉树的五种基本形态二叉树的性质：（较简单直观的性质，可以不给出证明。）性质1：在二叉树的第

14、i层上的结点数2i-1（i0）。性质2:深度为k的二叉树的结点数2k-1（k0）。性质3:对任一棵非空的二叉树T，如果其叶子数为n0，度为2的结点数为n2，则有下面的关系式成立：n0=n2+1。（证明）满二叉树，完全二叉树的定义性质4：有n个结点的完全二叉树（n0）的深度为卜？1+1。性质5:在编号的完全二叉树中，各结点的编号之间的关系为：编号为i的结点如果存在左孩子，则其编号为2i，如果存在右孩子，则其编号为2i+1，如果存在父结点，则其编号为（提出并讲解一个与二叉树的性质）相关的例题。二叉树的存储结构：江门职业技术学院教案 顺序存储结构按完全二叉树的编号次序进行，示意图，缺点：空间的浪费，

15、引入动态链表结构。二叉链表存储结构二叉链表，相关描述，示意图。7.3二叉树的遍历基本遍历方法讨论：先序遍历，中序遍历，后序遍历。详细讲解几种算法的思想。遍历算法的求解过程，举出实例：对给定二叉树，分别写出它的先序、中序和后序序列。（结合示意图分步讲解）已知二叉树的先（后）序和中序序列，试构造出相应的二叉树。（求解过程示意图）遍历算法的实现：先序遍历算法中序遍历算法后序遍历算法为加深学生对递归形式的遍历算法的理解，举例说明遍历算法的执行过程（遍历过程示意图）。二叉树遍历算法的应用：二叉树遍历算法的简单应用：对二叉树遍历算法适当修改，便可得到许多问题的求解算法。二叉树遍历算法思想的应用：法形式较繁

16、杂的递归算法的编写、阅读及证明。授课时间第9,10周授课地点教C504教D502课程类型理论课授课题目图授课班级07软件工程；07信息管理教学目的与教学要求理解图的相关概念、图的存储结构；熟练掌握图的两种遍历算法（深度优先搜索遍历和广度优先搜索遍历），并能灵活应用；熟练掌握两种求解最小生成树的算法（Prim算法和Kruskal算法）；熟练掌握拓扑排序算法和关键路径算法，并能灵活应用；熟练掌握两种最短路径算法（Dijkstra算法和Floyd算法），并能灵活应用。重点与难占八、图的两种遍历算法以及各应用问题的求解算法。教学方法手段（教具）讲授法主要内容图的相关概念、存储结构、图的遍历、最小生成树

17、、拓扑排序和关键路径、最短路径。参考资料精品课程网站： HYPERLINK /other/sjjg/jiaoan/jiaoan.html /other/sjjg/jiaoan/jiaoan.html HYPERLINK /sjjg/ /sjjg/http:/wsjiaoxue/kejian/fanshixi/DataStructure/index.asp课后作业与思考题P1917.1;7.3;7.4;7.5;7.6;7.7;7.9;7.10教学后记教学过程时间分配图结构的定义、相关术语和运算结合示意图讲解：图顶点，弧/边无向图，有向图，带权图（网络）无向完全图，有向完全图，子图邻接，邻接点，度

18、，入度，出度路径，简单路径，回路（环），简单回路（无向）连通图，连通分量，强连通图（无向）树，有向树。图的基本运算图的存储结构邻接矩阵：无向图、有向图及带权图的邻接矩阵，示意图简单介绍采用邻接矩阵时基本运算的算法思想。由邻接矩阵存在的不足引入邻接表。邻接表：无向图、有向图及带权图的邻接表，有向图的逆邻接表，示意图简单介绍采用邻接表时基本运算的算法思想。图的遍历.深度优先搜索遍历基本遍历算法的描述深度优先搜索遍历（dfs）算法描述，示意图执行过程，顶点访问序列，深度遍历生成树深度优先搜索遍历算法：详细讲述算法思想，给出算法的实现。深度遍历算法的应用：举例讨论。.广度优先搜索遍历广度优先搜索遍历算

19、法描述广度优先搜索遍历（bfs）算法描述，示意图执行过程，顶点访问序列，广度遍历生成树广度遍历算法：详细讲述算法思想，给出算法的实现。广度遍历算法应用实例.4最小生成树从现实中的问题引入最小生成树。最小生成树的定义，如何构造最小生成树？分别介绍两种算法。1.Prim算法Prim算法的求解思想求解实例，示意图江门职业技术学院教案 算法的实现.Kruskal算法Kruskal算法的求解思想求解实例，示意图算法的实现。拓扑排序有向无环图的应用：两个问题：拓扑排序、关键路径。工程，子工程（活动），活动之间的制约关系工程问题：工程能否顺利进行？用图（AOV网）来表示工程，判断工程能否顺利进行等价于判断A

20、OV网中是否存在有向回路。如何判断AOV网中是否存在有向回路？环环拓扑排序。拓扑排序、拓扑序列的概念拓扑排序的方法步骤，举实例说明，示意图。拓扑排序算法及实现。最短路径.从单个顶点到其余各顶点之间的最短路径：Dijkstra算法用Dijkstra算法求解从单个顶点到其余各顶点之间的最短路径的求解方法，举实例说明求解过程，结合示意图讲解。讨论Dijkstra算法的实现，给出算法描述。.各顶点之间的最短路径：FLOYD算法算法思想，求解实例分析，算法描述，算法分析授课时间第11周授课地点课程类型理论课授课题目查找授课班级教学目的与教学要求理解查找的相关概念，理解简单顺序查找、二分查找、分块有序表的

21、查找算法的算法及性能分析；理解二叉排序树的定义、特性和查找算法，二叉排序树的构造、插入结点的算法和删除结点的实现方法；重点与难占八、二分查找，二叉排序树的构造，教学方法手段（教具）讲授法主要内容查找的相关概念，顺序表中的顺序查找、有序表上的二分查找、分块有序表上的查找；二叉排序树构造、及查找运算；参考资料精品课程网站： HYPERLINK /other/sjjg/jiaoan/jiaoan.htm /other/sjjg/jiaoan/jiaoan.html HYPERLINK /sjjg/ /sjjg/http:/wsjiaoxue/kejian/fanshixi/DataStructure

22、/index.asp课后作业与思考题P2218.2;8.3;8.4;8.5教学后记教学过程时间分酉己.1查找运算的定义和相关概念查找，查找表关键字（键），主关键字，次关键字查找算法的时间性能，查找长度9.2顺序表的查找顺序表查找的问题描述.简单顺序查找简单顺序查找的算法思想，算法的实现（算法中设置监视哨的技巧）算法在查找成功时的平均查找长度、失败时的查找长度。由简单顺序查找的查找长度引入更快的查找方法字字二分查找。.有序表的二分查找有序表，二分查找（折半查找）二分查找的算法思想，以示意图举实例说明查找过程。二分查找算法的实现：二分查找的递归算法，算法分析二分查找的判定树及其构造.索引顺序表的查

23、找分块有序表，索引表在索引顺序表中进行查找分两步：首先要通过在索引表中查找以确定元素所在的块，然后在所确定的块中进行查找。每一步可以采用的查找方法。简述索引顺序表的查找的时间性能。.3二叉排序树二树表的查找通过分析顺序类表查找的静态特性对维护表的制约，引入树表的查找。二叉排序树的定义、特性二叉排序树的查找方法、算法描述。二叉排序树的运算：插入结点与构造二叉排序树授课时间第12,13周授课地点课程类型理论课授课题目排序授课班级教学目的与教学要求直接插入排序、Shell排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序和基数排序等。重点与难占八、快速排序、堆排序、归并排序教学方法手段（教具）讲授法、启发法主要内容理解排序的相关概念；理解直接插入排序、Shell排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序和基数排序等算法的基本思想、算法、时间复杂度和空间占用情况，并能根据具体问题选择合适的算法。参考资料精品课程网站：http:/other/sjjg/jiaoan/jiaoan.html HYPERLINK /sjjg/ /sjjg/http:/wsjiaoxue/kejian/fanshixi/DataStructure/index.asp课后作业与思考题P2479.3;9.7;9.8教学后