搜索
《数据结构》教案Createdbyarlene第1次课第一章绪论步骤内容重点难点要求课堂互动一20分钟1．1什么是数据结构通过书上的三个例子解说——例1－1线性结构例1－2树形结构例1－3图形结构数据结构的概念数据结构的概念完全领会提问：(1)你认为计算机是如何实现人机对弈的？(2)你会如何解决多叉路口交通灯的管理问题？二45分钟1．2基本概念和术语包括：数据、数据元素、数据对象、数据结构、结构、集合、线性结构、树形结构、图形结构、逻辑结构、物理结构、顺序存储结构、链式存储结构、数据类型、原子类型、结构类型、抽象数据类型、多形数据类型数据结构、线性结构、树形结构、图形结构、顺序存储结构、链式存储结构抽象数据类型完全领会、熟记反复提问：有哪四类基本结构？引导提问：你知道的数据类型有哪些？三25分钟1．4算法和算法分析包括：1个定义、5个特性、4个性能标准、2个效率的度量（时间复杂度和空间复杂度）算法的概念、时间复杂度、空间复杂度时间复杂度能判断简单算法的时间复杂度和空间复杂度幻灯片上的题目，要求学生一起做，引导他们作答《数据结构》教案Createdbyarlene2006-09-04《数据结构》教案Createdbyarlene第2次课第2章线性表步骤内容重点难点要求课堂互动一15分钟通过出题要学生做的形式复习上节课的内容：数据结构的定义和逻辑结构图、求时间复杂度数据结构的定义和逻辑结构图求时间复杂度前者熟练应用，后者领会前题叫学生上台做后题提问点名回答二15分钟线性表的类型定义例2－1线性表的长度、空表抽象数据类型线性表的定义重点要熟记，难点领会重点部分幻灯片出题，当场叫人回答三60分钟线性表的顺序表示和实现——顺序表包括：存储方式、类型定义、基本运算（插入、删除等）顺序表的存储方式、基本运算（插入和删除）顺序表的基本运算（插入和删除）综合运用《数据结构》教案Createdbyarlene2006-09-11《数据结构》教案Createdbyarlene第3次课2．3线性表的链式表示和实现2006-09-15步骤内容重点难点要求课堂互动一30分钟线性表的链式存储结构——单链表包括：1.单链表表示法的基本思想——用指针表示结点间逻辑关系。2.单链表的结点形式：由数据域和指针(链)域两部分组成；这两部分各自的作用。3.头指针和头结点的作用。单链表的结点形式单链表表示法的基本思想简单应用提问：空表的表示法二40分钟插入、删除和定位运算在单链表上的实现包括：实现上述三种运算的三个算法；插入、删除算法中所包含的指针操作插入、删除运算在单链表上的实现插入、删除运算在单链表上的实现综合应用三15分钟设计出实现线性表其它较简单运算的算法设计算法根据已有的算法编写出其他较简单运算的算法《数据结构》教案Createdbyarlene第4次课2．3线性表的链式表示和实现＋习题步骤内容重点难点要求课堂互动一45分钟循环链表和双链表包括：1.循环链表的组织方法；2.双链表的结点形式、双链表的组织方法和特点。循环链表的组织方法循环链表的组织方法领会二10分钟顺序表与链表的比较包括：1.顺序表的主要优点和主要缺点；2.链表的主要优点顺序表与链表的比较识记要求学生思考总结“顺序表与链表的比较”，并点名回答三35分钟第2章习题《数据结构》教案Createdbyarlene2006-09-18《数据结构》教案Createdbyarlene第5次课第3章栈和队列步骤内容重点难点要求课堂互动一15分钟栈的定义和队列的定义包括：1.栈的基本运算及由此而决定的栈的基本特点；2.队列的基本运算及由此决定的队列的特点。栈的基本运算、栈的基本特点、队列的特点栈的基本运算及由此而决定的栈的基本特点领会二45分钟栈的顺序实现和链接实现包括：1.顺序栈的组织方法；2.进栈和退栈运算在顺序栈上的实现算法，弄清栈满和栈空的条件；3.链栈的结点形式及其描述，链栈的组织方法；4.链栈上实现进栈和退栈的算法。链栈链栈上实现进栈和退栈的算法简单应用三30分钟队列的顺序实现和链接实现包括：1.顺序队的组织方法，顺序队上的“假溢出”及其原因；2.链队的结点形式及其语言描述，熟悉链队的组织方法；3.在链队上实现入队、出队的算法。在链队上实现入队、出队的算法在链队上实现入队、出队的算法简单应用《数据结构》教案Createdbyarlene2006-09-18《数据结构》教案Createdbyarlene第6次课实验一：线性表的基本操作步骤内容重点难点要求课堂互动一15分钟二15分钟三60分钟《数据结构》教案Createdbyarlene2006-09-29《数据结构》教案Createdbyarlene第7次课循环队列＋串定义＋第3章习题步骤内容重点难点要求课堂互动一15分钟循环队的组织方法；以及在其上进行人队、出队运算的方法和队满、队空的条件。循环队的组织方法、队满、队空的条件人队、出队运算的方法识记二15分钟串的定义领会三60分钟第3章习题每一题都要求一位学生作答《数据结构》教案Createdbyarlene2006-10-09《数据结构》教案Createdbyarlene第8次课实验二：栈和队列的应用步骤内容重点难点要求课堂互动一15分钟二15分钟三60分钟《数据结构》教案Createdbyarlene2006-10-13《数据结构》教案Createdbyarlene第9次课第5章数组和广义表步骤内容重点难点要求课堂互动一15分钟数组元素地址的计算二元数组元素地址的计算多元数组元素地址的计算识记出题，黑板作答二15分钟特殊矩阵的压缩存储特殊矩阵的压缩存储领会三60分钟广义表1．定义2．特点3．存储结构（两种）定义和存储结构存储结构识记，能画出任一种存储结构出题，黑板作答《数据结构》教案Createdbyarlene2006-10-16《数据结构》教案Createdbyarlene第10次课第6章树和二叉树步骤内容重点难点要求课堂互动一15分钟树形结构的基本概念和术语抽象数据类型树的定义领会二15分钟二叉树的定义包括：1．二叉树的逻辑结构、特点和五种基本形态2．二叉树的基本运算和性质二叉树的基本运算和性质二叉树的5个性质领会，熟练运用二叉树的5个性质提问，课堂点名回答三60分钟二叉树的链式存储结构和顺序存储结构1．二叉链表的结点形式及其描述，二叉链表中各结点的联系方法及根指针的作用2．满二叉树和完全二叉树的概念3．二叉树的顺序存储的基本思想(按层编号)链式存储结构链式存储结构链式要求简单应用，顺序要求领会提问出题，黑板求解《数据结构》教案Createdbyarlene2006-10-23《数据结构》教案Createdbyarlene第11次课实验三：二叉树的建立和遍历（1）步骤内容重点难点要求课堂互动一15分钟二15分钟三60分钟《数据结构》教案Createdbyarlene2006-10-27《数据结构》教案Createdbyarlene第12次课二叉树的遍历步骤内容重点难点要求课堂互动一20分钟二叉树的先序、中序和后序遍历方法，三种遍历所得的结点访问序列三种遍历方法的应用综合应用二30分钟1．设计二叉树上基于三种遍历的简单算法2．根据先序和中序序列画出二叉树根据先序和中序求后序设计算法综合应用引导学生设计算法出题，黑板作答三40分钟先序遍历的非递归算法先序遍历的非递归算法领会出题：根据先序的非递归算法写出中序的非递归算法《数据结构》教案Createdbyarlene2006-10-30《数据结构》教案Createdbyarlene第13次课线索二叉树步骤内容重点难点要求课堂互动一15分钟二15分钟三60分钟《数据结构》教案Createdbyarlene2006-11-06《数据结构》教案Createdbyarlene第14次课实验四：二叉树的建立和遍历（2）步骤内容重点难点要求课堂互动一15分钟二15分钟三60分钟《数据结构》教案Createdbyarlene2006-11-10《数据结构》教案Createdbyarlene第15次课树和森林＋赫夫曼树2006-11-13步骤内容重点难点要求课堂互动一45分钟树和森林包括：1．树的逻辑结构、基本运算和三种主要存储结构2．树、森林与二叉树的关系3．森林与二叉树的转换4．树和森林的遍历树、森林与二叉树的关系树和森林的遍历识记出题，黑板作答二45分钟树的应用包括：1．哈夫曼树的概念2．构造哈夫曼树的方法构造哈夫曼树的方法简单运用出题，黑板作答《数据结构》教案Createdbyarlene第16次课第6章习题课＋7.1图的定义和术语步骤内容重点难点要求课堂互动一55分钟第6章习题每一题都要求学生回答二35分钟图状结构的定义并熟悉有关术语包括：顶点、弧、弧尾、弧头、有向图、无向图、边、完全图、权、有向完全图、稀疏图、稠密图、邻接点、度、出度、入度、路径、简单路径、连通、连通图、连通分量、强连通图、强连通分量、生成树、生成森林所有概念领会并识记《数据结构》教案Createdbyarlene2006-11-20《数据结构》教案Createdbyarlene第17次课实验五：图的存储和遍历步骤内容重点难点要求课堂互动一15分钟二15分钟三60分钟《数据结构》教案Createdbyarlene2006-11-24《数据结构》教案Createdbyarlene第18次课图的存储结构和遍历2006-11-25步骤内容重点难点要求课堂互动一45分钟图的存储结构包括：1．有向图、无向图和网的邻接矩阵表示法和邻接表表示法2．网的邻接矩阵和无向图的邻接表的建立方法和算法领会给出一个无向图，要两名学生分别画出该图的邻接矩阵和邻接表（逆邻接表）二45分钟图的遍历包括：1．连通图的深度优先搜索和广度优先搜索的基本思想、基本步骤，并给出相应搜索的顶点序列2．非连通图的遍历方法以及图的连通分量的求法简单应用出题，要两个学生黑板作答，分别用不同的搜索算法，比较速度《数据结构》教案Createdbyarlene第19次课7．4图的连通性问题步骤内容重点难点要求课堂互动一15分钟相关概念：连通图、强连通图、连通分量、强连通分量、生成树连通分量、生成树生成树完全领会、熟记二15分钟1．连通图的生成树2．非连通图的生成森林连通图的生成树的特点生成森林完全领会，能判断出正确的生成树三60分钟1．最小生成树MST的概念2．两个生成MST的算法：普里姆．．．(Prim)．．．．．．算法和克鲁．．．．．斯卡尔（．．．．Kruskal．．．．．．．）．算法．．使用两个算法生成最小生成树两个算法的比较，及时间复杂度能熟练运用任一个算法生成图的最小生成树出题，要两个学生黑板作答，分别用不同的算法，比较速度《数据结构》教案Createdbyarlene2006-11-27第20次课7．5有向无环图及其应用步骤内容重点难点要求课堂互动一10分钟有向无环图的概念识记二30分钟拓扑排序的基本概念和算法思想拓扑排序的基本概念拓扑排序的算法思想领会《数据结构》教案Createdbyarlene2006-12-08第21次课7．6最短路径＋习题课三50分钟关键路径的算法思想关键路径的算法思想关键路径的算法思想领会和简单运用步骤内容重点难点要求课堂互动一40分钟从某个源点到其余各顶点的最短路径——迪杰斯特拉（Dijkstra）算法Dijkstra算法Dijkstra算法熟练运用该算法求得源点到各个顶点的最短路径《数据结构》教案Createdbyarlene2006-12-11二40分钟第7章的习题练习，见幻灯片，包括选择题、填空题、求解题（出\入度、邻接矩阵、邻接表、逆邻接表、强连通分量、DFS、BFS、最小生成树、拓扑序列、最短路径、关键路径）选择题和求解题求解题能熟练求解每道题都要求一位学生回答或用黑板解题三10分钟强调本章需掌握的知识点：理解：图的基本概念图的顶点集合是非空有限集合|图的边集合可以是空集合|图的顶点序号不是固有的掌握：1.图的存储表示图的邻接矩阵元素个数与顶点有关，非零元素个数与边有关