《《数据结构(Python语言描述)》教学教案.docx》由会员分享，可在线阅读，更多相关《《数据结构(Python语言描述)》教学教案.docx（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、教学单元：数据结构（本科）课程概述（2学时）授课班级:教学内容提要:1课程简介：地位（考研、软件开发岗位必考），在专业知识体系中的位置，就 业岗位等；2课程主要内容及学时分配；3课程考核方式；4课程学习方法；5算法的基本概念和术语；6 Java语言编程回顾。教学目的：1 了解该课程所研究的内容、作用和发展状况，就业岗位，可以考取的证书等；了解算法基本概念和术语；3在Eclipse环境下编辑一个简单的求最大公约数的程序。教学重点、难点：1数据结构、算法、算法复杂度的基本概念；2如何把现实的问题抽象出来，建立模型，设计算法，再分析算法的复杂度，并 选取合适的语言编码实现。教学方法：通过动画演示，提
2、问，采用讲授、启发引导、学生自己动手做相结合。教学过程设计：1、利用CC网，介绍课程的资源：老师搭建的hustoj在线评测网站、几本教材的 PPT、Java软件等供他们下载，自学，要求他们主动学习，提供参考资料给他们； 2、介绍学习方法，课堂及作业要求、纪律要求、考核方式等；3、了解学生：有多少人数准备继续深造（出国，考研等），多少人准备从事软件 开发，自己创业等；4、介绍课程的作用，在专业课程中的地位，对个人提升的重要性等，特别强调所4）二叉树的层次遍历层次遍历的定义、层次遍历的算法实现和层次遍历的应用教学目的：1 了解树和二叉树的定义；2 了解二叉树的性质和存储结构；3掌握二叉树的几种遍历
3、；4掌握利用前序和中序遍历构建二叉树的递归算法教学重点、难点：1二叉树二叉链式存储实现2二叉树遍历的应用3利用前序和中序遍历构建二叉树教学方法：通过动画演示，提问，采用讲授、启发引导、学生自己动手做相结合。教学过程设计：1、介绍树和二叉树的基本概念；2、介绍树和二叉树的顺序存储和链式存储的实现，并画出示意图（黑板）；3、讲解完全二叉树的存储原理和实现细节（为后面堆的知识做铺垫）；4、介绍二叉树常用的三种遍历讨论二叉树的遍历能否确定一棵二叉树？举出前序和后序遍历不能确定二叉树的反例给出利用前序和中序遍历构建二叉树的递归算法，作业题95、讲解二叉树的层次遍历；讨论二叉树的层次遍历，要怎么存储层次和
4、父子信息课堂提问：提问1:如何判定完全二叉树？提问2：能不能给出前序和后序遍历不能确定二叉树的反例？提问3：老师给出的利用前序和中序遍历构建二叉树的算法，为什么要用递 归？使用递归有什么优点？小结：14) 介绍二叉树基本概念和术语；介绍二叉树常用的三种遍历和层次遍历;3)掌握利用前序和中序遍历构建二叉树的算法。作业：预习：常用二叉树复习：队列教学单元：数据结构哈夫曼树（2时）授课班级：教学内容提要：5哈夫曼树1哈夫曼树构造方法5. 1. 1最优二叉树概念1 .路径和路径长度2 .结点的权和带权路径长度3 .树的带权路径长度WPL = W1=1哈夫曼树构造的步骤如下：（1）用给定的n个权值wl,
5、 w2,，wn对应的n个结点构成n棵二叉树的森 林F=T1, T2,，Tn,其中每一棵二叉树Ti （1 Wi Wn）都只有一个权值为wi的 根结点，其左、右子树为空。（2）在森林F中选择两棵根结点权值最小的二叉树，作为一棵新二叉树的左、 右子树，标记新二叉树的根结点权值为其左右子树的根结点权值之和。（3）从F中删除被选中的那两棵二叉树，同时把新构成的二叉树加入到森林F中。（4）重复（2）、（3）操作，直到森林中只含有一棵二叉树为止，此时得 到的这棵二叉树就是赫夫曼树。5. 2哈夫曼编码前缀编码：任一个字符的编码都不是另一个字符编码的前缀，可利用二叉树 设计前缀编码。6. 3哈夫曼编码的编码方法
6、二叉树指向左孩子的边编码为1,指向右孩子的边编码为0。每个叶子节点代 表字符（单词）的编码，为从根节点到该节点所经边的编码串。教学目的：1 了解哈夫曼树和哈夫曼编码的定义；了解哈夫曼树的性质和构造方法；3掌握哈夫曼树的编码方法；教学重点、难点：1哈夫曼树存储实现2哈夫曼树构造方法的编码实现3哈夫曼树编码的编码实现教学方法：通过动画演示，提问，采用讲授、启发引导、学生自己动手做相结合。教学过程设计：1、介绍哈夫曼树和哈夫曼编码的基本概念；2、介绍哈夫曼树构造方法，并画出示意图(黑板)；3、讲解哈夫曼树构造方法的代码实现(为后面哈夫曼编码做铺垫)；4、讲解哈夫曼编码的代码实现；讨论：采用链式存储好
7、还是顺序存储好？课堂提问:有一电文共使用五种字符a, b, c, d, e,其出现频率依次为4, 7, 5, 2, 9。(1)试画出对应的编码赫夫曼树(要求左子树根结点的权小于等于右子树根结 点的权)。(2)求出每个字符的赫夫曼编码。小结：16) 介绍哈夫曼树和哈夫曼编码的基本概念；掌握哈夫曼树构造方法和哈夫曼编码方法作业：预习：堆复习：二叉树教学单元：数据结构堆和堆排序（4时）授课班级:教学内容提要：5哈夫曼树1哈夫曼树构造方法5. 1. 1最优二叉树概念1 .路径和路径长度2 .结点的权和带权路径长度3 .树的带权路径长度WPL = W1=1哈夫曼树构造的步骤如下：（1）用给定的n个权值w
8、l, w2,，wn对应的n个结点构成n棵二叉树的森 林F=T1, T2,，Tn,其中每一棵二叉树Ti （1 Wi Wn）都只有一个权值为wi的 根结点，其左、右子树为空。（2）在森林F中选择两棵根结点权值最小的二叉树，作为一棵新二叉树的左、 右子树，标记新二叉树的根结点权值为其左右子树的根结点权值之和。（3）从F中删除被选中的那两棵二叉树，同时把新构成的二叉树加入到森林F中。（4）重复（2）、（3）操作，直到森林中只含有一棵二叉树为止，此时得 到的这棵二叉树就是赫夫曼树。5. 2哈夫曼编码前缀编码：任一个字符的编码都不是另一个字符编码的前缀，可利用二叉树 设计前缀编码。6. 3哈夫曼编码的编码
9、方法二叉树指向左孩子的边编码为1,指向右孩子的边编码为0。每个叶子节点代 表字符（单词）的编码，为从根节点到该节点所经边的编码串。教学目的：1 了解哈夫曼树和哈夫曼编码的定义；了解哈夫曼树的性质和构造方法；3掌握哈夫曼树的编码方法；教学重点、难点：1哈夫曼树存储实现2哈夫曼树构造方法的编码实现3哈夫曼树编码的编码实现教学方法：通过动画演示，提问，采用讲授、启发引导、学生自己动手做相结合。教学过程设计：1、介绍哈夫曼树和哈夫曼编码的基本概念；2、介绍哈夫曼树构造方法，并画出示意图(黑板)；3、讲解哈夫曼树构造方法的代码实现(为后面哈夫曼编码做铺垫)；4、讲解哈夫曼编码的代码实现；讨论：采用链式存
10、储好还是顺序存储好？课堂提问:有一电文共使用五种字符a, b, c, d, e,其出现频率依次为4, 7, 5, 2, 9。(1)试画出对应的编码赫夫曼树(要求左子树根结点的权小于等于右子树根结 点的权)。(2)求出每个字符的赫夫曼编码。小结：18) 介绍哈夫曼树和哈夫曼编码的基本概念；掌握哈夫曼树构造方法和哈夫曼编码方法作业：预习：堆复习：二叉树教学单元：数据结构图的基本概念和存储(2学时)授课班级:教学内容提要：1 .图的概念首先介绍“七桥问题”，说明数学模型的重要性图的概念：有向图、无向图、完全图、度、出度、入度、邻接、邻接点、连通分 量、强连通分量、生成树、第一邻接点、下一邻接点 抽象
11、数据类型定义图的操作中最重要的4个操作：GraphLocateVertex(G, v)；GraphGetVertex(G, v)；GraphFirstAdj(G, v)；GraphNextAdj(G, v, w)；2 .图的顺序存储结构一一邻接矩阵表示法图的邻接矩阵表示法的特点：对于无向图，邻接矩阵一定是一个对称矩阵 行(列)非零元素个数，表示度。对于有向图，矩阵不一定是一个对称矩阵 行非零元素个数，表示出度列非零元素个数，表示入度邻接矩阵的存储空间只和 顶点个数有关，和边数无关。3 .图的邻接表存储结构图的邻接矩阵表示法(Adjacency Matrix)也称作数组表示法。它采用两个 数组来
12、表示图：一个是用于存储顶点信息的一维数组；另一个是用于存储图中顶 点之间关联关系的二维数组，这个关联关系数组被称为邻接矩阵。4 .图的存储结构间的相互转换（邻接矩阵转为邻接表的算法、邻接表转为邻接矩 阵的算法）教学目的：1 .掌握图的基本概念.掌握图的存储结构，重点是邻接矩阵和邻接表2 .掌握图的算法，特别是图的生成算法.掌握邻接矩阵和邻接表存储结构间的相互转换教学重点、难点：1 .重点是图的基本概念，存储结构.难点是图的存储结构间相互转换的算法教学方法：通过动画演示，提问，采用讲授、启发引导、学生自己动手做相结合。教学过程设计：1、介绍图的基本概念；2、介绍图的两种存储方法，并画出示意图（黑
13、板）；3、讲解图的基本操作；4、讲解两种存储方法的转换课堂提问:1、一个n个顶点的连通无向图，其边的个数至少为多少？2、n个顶点的无向图的邻接矩阵至少有多少非零元素？3、n个顶点的完全有向图含有弧的数目是多少？4、要连通具有n个顶点的有向图，至少需要多少条弧？小结：20） 介绍图的基本概念和存储；掌握两种存储方法的转换方法作业：课本课后练习题预习：图的连通性教学单元：数据结构图的遍历、连通性和最小生成树(10 时)教学内容提要：1.图的遍历图的遍历(Travelling Graph):从图中某一个顶点出发，访问图中的其余顶 点，使每个顶点被访问一次且仅被访问一次。方法：深度优先遍历广度优先遍历
14、(1)深度优先遍历1)从任一个顶点v出发，访问该顶点；2)然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和 v有路径相通的顶点都被访问到；3)此时若图中尚有顶点未被访问，则另选中下一个未被访问的顶点作起始 点，访问该顶点，继续过程2),直到所有顶点都被访问完。(2)广度优先遍历1)从图中某顶点v出发，访问v,之后：2)依次访问v的各个未曾被访问过的邻接点，然后分别从这些邻接点出发依 次访问它们的未被访问的邻接点，并使“先被访问的顶点的邻接点先于 后被访问的顶点的邻接点”被访问，直至图中所有已经被访问的顶点的邻接 点都被访问到；3)若图中尚有顶点未曾被访问，则另选图中一个未曾被访
15、问的顶点作起点, 访问该顶点，继续过程2),直至所有顶点被访问完毕。2 .图的连通分量进入DFS或BFS一次可以求得一个连通分量.深度优先生成树和广度优先生成树采用DFS遍历图所得到的生成树称为深度优先生成树，采用BFS遍历图所得到 的生成树称为广度优先生成树.最小生成树n个顶点网络的生成树有n个结点，n-1条分枝。假设网络中有m条边(m2nT), 用MST表示许多可能的生成树的集合，每棵树中n-l条分枝上的权之和用WG(T)表 示，则使得WG(Tmin)=MinWG(T) | TeMST)的生成树Tmin便是网络的最小生成树。MST性质假设N= (V, E)是一个连通无向网，U是顶点集V的一
16、个非空子集。若(u, v) 是一条具有最小权值的边，其中uU, veV-U,则必存在一棵包含边(u, v)的 最小生成树。3 . Prim算法算法思想：假设N=(V, |E|)是连通图，TE是N上最小生成树中边的集合。算 法从U=uO (uOgV) , TE=开始,重复执行下述操作：在所有ueU, veVU的边 (u, v)中找一条代价最小的边(uO, vO)并入集合TE,同时vO并入U,直至U=V为止。 此时，TE中必有n-1条边，则T=(V, TE)为N的最小生成树。教学目的：1 .掌握图的遍历算法：深度优先遍历，宽度优先遍历。2 . 了解图的连通性，掌握连通分量的求法.掌握生成树的构造方
17、法3 .理解构造生成树的算法教学重点、难点：1 .重点：图的遍历算法和生成树.难点：图的遍历算法的应用有的相关计算机专业的考研以及高级程序员、系统分析师的考试、另外招聘程序 员的面试笔试等都会考相关的算法等；5、介绍课程的主要内容和学时分配；6、鼓励他们考取高级证书，提前到招聘会或者招聘网站上了解最新的岗位需求, 提前学些前沿的技术，为就业作准备，介绍一些学生就业情况7、通过最大公约数、一列数中第k大数等例子，介绍计算机算法可以解决的实际 问题，引出算法、算法评价指标和算法复杂度等基本概念，并要同学举例说明： 现实世界中的有哪些运用计算机算法的地方？课堂提问：1、最小公倍数怎么计算？2、n个数
18、中第k大数，当数字的个数n非常巨大，而k比较小时，采用什么样的算法, 当k的阶和数字个数n相当时，又该如何计算？小结：1）初步认识算法基本概念和术语，一定要分清程序和算法是完全不同的两个概念；2） 了解课程章节的安排规律；3）基本熟悉Java环境的使用，知道如何在Java中进行算法编程。作业：习题1 （简答3,7, 8）预习：算法复杂度分析复习：Java与算法相关的类库和这些类的使用教学方法：通过动画演示，提问，采用讲授、启发引导、学生自己动手做相结合。教学过程设计：1、介绍图的遍历、连通性和最小生成树的基本概念；2、介绍图的两种遍历方法，并画出示意图（黑板）；3、讲解求图的连通性和最小生成树
19、方法（黑板）；4、求图的遍历、连通性和最小生成树的代码实现；课堂提问:图的BFS生成树的树高要小于等于同图DFS生成树的树高，对吗？如果图有多个连通分量，深度优先遍历如何找出？Prim算法的时间复杂度是多少？ 小结：22） 介绍图的遍历、连通性和最小生成树;掌握图的两种遍历方法；23） 掌握求图的连通性和最小生成树方法作业：课本课后练习题一带权无向图的邻接矩阵如下图，试画出它的一棵最小生成树。110000120010030020010 00 03 01 10 11 0如图所示是一带权有向图的邻接表法存储表示。其中出边表中的每个结点均含有 三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权
20、值和指向下一个 边结点的指针。试求：（1）该带权有向图的图形；（2）从顶点VI为起点的广度优先遍历的顶点序列及对应的生成树；（3）以顶点VI为起点的深度优先遍历生成树;（顶点边）（顶点边）（出边表）336A3 V3 A230110230110338618A6 V6 A预习：堆 复习：二叉树教学单元：数据结构图的最短路径(6时)授课班级：教学内容提要：1 .从某源点到其它各顶点的最短路径。(1) Dijkstra 算法按路径长度递增的次序来产生最短路径算法(2)方法：把V分成两组S：已求出最短路径的顶点的集合V-S：尚未确定最短路径的顶点集合,将V-S中顶点按最短路径递增的次序加入到S(3)步骤
21、：(1)邻接矩阵arcs来表示带权的有向图,arcsi j表示 vi, vj上的权值。若 vi, vjeE,则置arcsiS为已找到从v出发的最短路径的终点集合，初态为空。(2)选择vj,使Dj=min Di | vieV-Sj vj就是当前求得的一条从v出发的最短 路径，并令S=SUj(3)从v出发到集合V-S上任一顶点vk可达的最短路径，有Dk=min Dk, Dj+arcsi k(4)重复(2)、(3)直到 S二V。2 .每一对顶点之间的最短路径方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次一T(n)二0(n3)方法二：弗洛伊德(Floyd)算法(1) Floyd算法思想
22、逐个顶点试探法求最短路径步骤初始时设置一个n阶方阵，令其对角线元素为0,若存在弧则对应元 素为权值；否则为8逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之; 否则，维持原值所有顶点试探完毕，算法结束(2) Floyd 算法 void ShortestPath_Floyed(Graph G, PathMatrix P , DistanceMatrix D)用Floyed算法求有向图G中各对顶点v和w之间最短路径Pv w,及其带权路/径长度Dvw。若Pv w u为真，则u是从v到当前求得最短路径上的顶点for(v=0； vG.vexnum； v+)for(w=0； wG.ve
23、xnum； w+) Dvw=G.arcsvw；for(u=0； uG.vexnum； u+)Pvwu=0；if (Dv wINTMAX)/ 从 v 到 w 有直接通路 Pv w v=l; Pv w w=l;/ if/ forfor(u=0； uG.vexnum； u+)for(v=0； vG.vexnum； v+)for(w=0； wG.vexnum； w+)if(Dv u+Du wDv w )/ 从 v 经 u 到 w 一条路径更短 Dv w=Dv u+Du w；for(i=0； iG.vexnum； i+)Pv w i=Pv u i I I Pu w i； / if / Shor test
24、 Pa th_Floyed66(3)举例0 4 116 0 23 od 0教学目的：1 .掌握单源点到其它各顶点的最短路径。2 .掌握任意两顶点间的最短路径。教学重点、难点：1 .重点是单源点和任意两顶点间的最短路径.难点是算法的理解和应用教学方法：通过动画演示，提问，采用讲授、启发引导、学生自己动手做相结合。教学过程设计：1、介绍单源最短路径和多点间最短路径的基本概念;2、介绍Dijkstra方法，并画出示意图（黑板）；3、讲解Dijkstra方法的代码实现；4、介绍Floyd方法，并画出示意图（黑板）；5、讲解Floyd方法的代码实现；课堂提问：比较Dijkstra方法和Prim算法的异同
25、。Di jkstra方法中寻找最小的Dv w有什么好算法?小结：25） 介绍单源最短路径和多点间最短路径的基本概念；掌握求解单源最短路径和多点间最短路径的基本概念方法作业：课本课后练习题1）已知n个顶点的有向图，用邻接表表示，编写函数，计算每对顶点之间的最短路径。预习：排序复习：图的遍历和连通性教学单元：查找（6学时） 授课班级: 教学内容提要1 杏胡其木并不今2：莪性奏的查萩及其时间复杂度的分析顺序查找、顺序表的折半查找、顺序表的分块查找.基于树的结点查找（二叉检索树/二叉排序树、平衡二叉树、*B-树）3 .基于散列表的Hash查找 教学目的：1理解查找的基本概念2掌握线性表的几种查找方法3
26、二叉排序树的查找4散列查找 教学重点、难点：1顺,查找、二分查找、散列查找的方法及算法2二叉排序树的创建及检索 教学方法：通过动画演示，项目，采用讲授、演示、启发引导、学生自己动手 做相结合。教学过程设计: 1检查上节课布置的作业2讲解查找的基本概念和基本思想，引出数据的索引存储和散列存储3讲解查找的3种方法：线性表、二叉排序树、散列表的查找 动画演示A.顺序查找、二分查找（折半查找）、分块查找B.二叉排序树，平衡二叉树的概念，动画演示B-树的生成与删除C.散列表（创建与查找）4讲解查找算法演示李春葆的代码动画演示顺序查找、二分查找二叉排序树的创建和查找算法散列表的创建及查找5实践项目修改优化
27、二分查找代码，添加查找次数二叉排序树的创建散列表的创建及查找次数计算 小结：各种查找方法使用的条件，学会散列存储和散列查找 作业：书后所有习题实验9 准备项目答辩教学单元：排序（4学时） 授课班级：17软件1、17软件2 教学内容提要1 .排序基本概念.内部排序插入排序（直接插入排序、希尔排序）选择排序（直接选择排序、*堆排序）交换排序（冒泡排序、快速排序）*归并排序*基数排序（桶排序）教学目的：1理解排序的基本概念2掌握线性表的几种排序方法，并知道之间排序结果 教学重点、难点：1直接编入排最 直接选择排序、冒泡排序2希尔排序、快速排序教学方法：通过动画演示，项目，采用讲授、演示、启发引导、学
28、生自己动手 做相结合。教学过程设计：复习：1检查上节课布置的问题提问：学生知道有哪些排序方法？说出算法主要思想新课：1检查上节课布置的问题2讲解排序的基本概念和基本思想3、看舞蹈视频，跳出排序的效果，推出排序的思路4讲解排序的儿种方式（算法）动画演示,，A.插入排序（直接插入排序、希尔排序）B.选择排序（直接选择排序、*堆排序）C.交换排序（冒泡排序、快速排序）D. *归并排序E. *基数排序（桶排序）5学生实践：调试各种排序算法，要求写出中间排序的每趟结果 第二次课：调试代码，书上例题，检查项目1）各种排序方法特点2）学会选择合适的排序排序方法作业： 书后所有习题、实验8 准备项目答辩教学单
29、元：数据结构A一一线性表基础(3学时)授课班级：教学内容提要：2线性表的定义、分类和实现2.1线性表的顺序表示和实现1)线性表的顺序表示：指的是用一组地址连续的存储单元依次存储线性表的数据 元素。用物理位置来表示逻辑结构。LOC(ai+i)=LOC(ai)+/LOC(ai)=LOC(ai)+(i-l)*/2)顺序表的特点：随机存取3)顺序表的运算顺序表容易实现访问操作，可随机存取元素。但是插入、删除操作是需要移动 大量的元素。2. 2线性表的链式表示和实现2. 1单链表：1)单链表概念2)单链表的存储结构定义3)单链表的操作：算法思想：单链表是非随机存取结构。每个元素的位置信息都包含在前驱结
30、点的信息中，所以取得第i个元素必须从头指针出发寻找。设置一个指针变量指向 第一个结点，然后，让该指针变量逐一向后指向，直到第i个元素。插入操作：要在数据元素a和b之间插入元素x。3. 2. 2掌握循环链表、双链表及静态链表存储结构及其运算实现教学目的：1 了解线性表和链表、单链表、双向链表的定义；了解单链表的存储和操作；3掌握循环链表、双链表及静态链表存储结构及其运算实现。教学重点、难点：1线性表的基本概念；2单链表的实现，插入、删除和查询操作。教学方法：通过动画演示，提问，采用讲授、启发引导、学生自己动手做相结合。教学过程设计：1、介绍线性表的基本概念；2、介绍线性表的顺序存储和链式存储结构
31、对比顺序存储和链式存储的内存组织方式，让学生了解要根据实际场景选择 合适的存储结构；介绍单链表、双向链表的逻辑结构，并画出示意图（黑板）；3、提问单链表的插入、删除和查询操作如何实现；4、让学生完成一个简单的链表插入节点和删除节点的程序；提示学生一定要注意要判断引用不为空。否则引发空指针异常。5、介绍双向链表的节点定义以及插入、删除和查询操作课堂提问：1、能开整数数组大小最大多少？为什么可用内存还有很多？2、数组（顺序存储结构）插入、删除和查找节点的时间复杂度3、单链表（链式存储结构）插入、删除和查找节点如何实现？这些操作的时间复 杂度是多少？小结：3）初步认识线性表基本概念和术语，一定要分清
32、线性表的线性存储和链式存储 是完全不同的逻辑结构；4）介绍多种链表的逻辑结构；3）教会如何实现单链表和双向链表。作业：预习：有序线性表复习：常见数据结构教学单元：数据结构（本科）有序线性表广义（6学时）授课班级：教学内容提要：1.4 有序线性表. 4. 1有序线性表的顺序存储4）有序线性表的顺序存储结构的特点相关概念：顺序存储、数组、二分查找5）顺序存储结构的优点：二分查找查找非常高效6）顺序存储结构的缺点：增加和删除操作，需要移动大量元素，效率低。3 .4.2有序线性表的链式表示和实现：4）链式存储结构定义（链表节点）5）有序链表的操作：算法思想：单链表是非随机存取结构，所以从头节点出发寻找
33、合适的位置插 入节点。找到第一个比待插入节点值大的节点（假设为节点N）,待插入节点就放 在节点N前面即可。6）有序链表的作业1多项式相加7）有序链表的作业2多项式相乘1.5 广义表5. 1广义表的定义3. 5.2广义表的创建的递归算法教学目的：1了解有序线性表的定义和分类；2掌握有序数组的存储和二分查找操作；3掌握有序链表的存储结构及其操作实现：插入、更新和删除；4掌握广义表的存储结构及其操作实现：插入、更新和删除；教学重点、难点：1有序数组的二分查找；2有序链表的实现，插入、删除和查询操作；3广义表创建的递归算法教学方法：通过动画演示，提问，采用讲授、启发引导、学生自己动手做相结合。教学过程
34、设计：1、介绍有序线性表的基本概念；2、介绍顺序存储和链式存储的逻辑结构，并画出示意图（黑板）；3、复习书上没有的有序链表的插入、删除和更新操作；4、提问如何保证插入节点后链表还是有序的；5、用课件中微软面试题，拓展学生视野，并引发学生的讨论；微软面试题：一共三道，难度为递进关系。而且环环相扣，对学生掌握链表的 设计和操作，有很大帮助课堂提问：提问L为什么是第一个比待插入节点值大的节点提问2：如果节点N为链表第一个节点，还要注意什么？提问3：节点N是否会找不到，找不到怎么办？提问4：广义表的创建为什么使用递归算法？可不可以不用？小结：5）介绍有序线性表基本概念和术语，一定要分清线性表的线性存储
35、和链式存储是完全不同的逻辑结构；6）介绍有序线性表的操作，并分析相关的复杂度；7）教会如何实现二分查找和有序链表；8）广义表的创建和基本操作作业：预习：栈复习：线性表的插入节点（代码）教学单元：数据结构A栈和队列（栈4学时）授课班级：教学内容提要：1 .什么是堆栈？2 .堆栈的存储方式.堆栈的操作4,堆栈的应用5.实践项目：进制的转换、括号匹配、后缀表达式的计算教学目的：1理解堆栈的工作原理2掌握堆栈的设计与实现3会使用堆栈进行编程教学重点、难点：1堆栈的工作原理2使用堆栈进行编程3中缀表达式变后缀表达式以及后缀表达式的计算教学方法：通过动画演示，提问，采用讲授、启发引导、学生自己动手做相结合
36、。教学过程设计：1、介绍栈的基本概念；2、介绍栈的顺序存储和链式存储，并画出示意图(黑板)；3、利用提问栈的顺序存储和链式存储，栈顶位于哪一端，让学生掌握自己创建栈;4、介绍括号匹配问题，并给出用栈的解决方法；5、讲解栈和递归的关系，并让学生测试机房的机器递归最大深度；6、讲解作业题“迷宫”，突出里面的递归思想；7、讲解练习题“全排列”和“组合”，进一步消化递归思想；课堂提问：提问1：栈的顺序存储和链式存储，栈顶位于哪一端？提问2：机房的机器，递归最大深度是多少，怎能知道？提问3：迷宫问题，走回头路怎么办？提问4：全排列问题的分解，是否能理解？提问5：组合问题的分解，是否能理解？小结：9)介绍
37、栈基本概念和术语，一定要分清栈的顺序存储和链式存储是完全不同的 逻辑结构；介绍栈的操作，并分析相关的复杂度；10) 教会如何用栈解决括号匹配问题；理解栈和递归的关系；11) 掌握常见递归问题的解法作业：预习：栈复习：有序链表教学单元：数据结构树和二叉树（6学时）授课班级：教学内容提要：5树5.1树的定义和基本术语结点的度、树的度、儿子结点、父亲结点、兄弟结点5. 2树的表示形式5. 3树形结构的逻辑结构树形结构的逻辑特征可用树中结点之间的父子关系来描述树形结构是非线性结构5. 4二叉树5.4. 1二叉树的定义二叉树的五种基本形态：5. 4. 2二叉树的重要性质性质1、在二叉树中的第i层上最多有
38、的结点数为2i-l个结点。（il）性质2、深度为k的二叉树至多有2k-l个结点（il）性质3、在任意二叉树中，若叶子结点（即度为零的结点）的个数为nO,度为1的结点个数为nl ，度为2的结点个数为n2 ,则有nO=n2+l性质4：具有n个结点的完全二叉树树深为log2n +1性质5、对于完全二叉树，对其结点采用“按层编号”比较方便，即从根结 点开始由上而下逐层给结点编号，同一层的结点由左向右编号。二叉树的存储结构顺序存储、二叉链表存储和三叉链表存储5. 4. 4二叉树的遍历1）遍历二叉树三种遍历次序以递归的形式定义：中序（Inorder）遍历先序（Preorder）遍历后序（Proorder）遍历2）遍历算法的实现3）遍历算法的应用