教案数据结构.docx

1、教案数据结构XX职业技术学院 学年第 二 学期教 案学 科： 数 据 结 构/嵌入式应用算法基础 系 部： 电子与信 息 技 术 系 教 研 室： 计算机 教研室 授课班级： 11软件工程/11嵌入式应用； 任课教师： 江门职业技术学院教案授课时间第1周授课地点实训B208课程类型理论课授课题目概述授课班级教学目的与教学要求1什么是数据结构2基本概念和术语3算法和算法分析重点与难点算法分析教学方法手段（教具）讲授法主要内容基本概念和术语参考资料精品课程网站:课后作业与思考题P12 1.1;1.2教学后记教学过程时间分配1.1什么是数据结构举例说明数据结构课程要解决的问题数据结构课程的创建数据结

2、构课程所处的地位1.2基本概念和术语基本概念和术语：数据、数据元素、数据对象、数据结构等数据结构的分类数据结构的二元组表示抽象数据类型的概念和三元组表示1.3算法和算法分析算法的概念和5个重要特性算法设计的4个要求算法效率的度量：时间复杂度江门职业技术学院教案授课时间第2周；第3周授课地点课程类型理论课授课题目线性表授课班级教学目的与教学要求熟练线性表的基本特征和基本运算重点与难点线性表的插入与删除教学方法手段（教具）讲授法主要内容数组的基本特点及寻址方式线性数据结构的基本特征和基本运算参考资料精品课程网站:课后作业与思考题P37 2.4;2.5;2.6;2.7教学后记教学过程时间分配2.1线

3、性表的类型定义线性表的定义和相关术语线性表的抽象数据类型定义举例2.2线性表的顺序表示和实现线性表的顺序表示方式线性表的动态分配顺序存储结构线性表顺序表示方式下的操作：InitList_SqListInsert_SqListDelete_SqLocateElem_SqMergeList_Sq结合第一章内容，分析上述算法的时间复杂度江门职业技术学院教案授课时间第3周授课地点课程类型理论课授课题目线性表授课班级教学目的与教学要求熟练掌握以下内容: 单链表的结构特点、基本运算并能设计简单算法循环链表的结构特点、基本运算并能设计简单算法重点与难点双链表插入、删除运算的算法利用链接结构的特点设计有效算法

4、，解决与链表结构相关的应用问题 教学方法手段（教具）讲授法主要内容单链表的结点形式、组织方法和特点 单链表的基本运算和相应的算法 循环链表的组织方法和基本运算算法 顺序表与链表比较，各自的优、缺点 链表的应用 参考资料精品课程网站:课后作业与思考题P37 2.4;2.5;2.6;2.7教学后记教学过程时间分配链表基本结构结构讨论 静态链表：定义及示意图 动态链表：详细介绍链表的相关知识，链表的类型说明及示意图。 带头结点的链表结构示意图 单链表上运算的实现： 初始化链表 （思考题）链表不带头结点时的初始化算法。 求链表长度 按序号取元素结点（算法流程图） 按值查询元素（算法流程图） 插入（示意

5、图） 删除（示意图） 链表的构造（算法的基本框架， . 尾插法建立链表的算法， . 头插法建立链表的算法） 链表结构的应用：列举若干求解实例 5.4 其它链表结构： 单循环、带尾指针的单循环链表，双链表、双循环链表结构讨论，运算实现的变化讨论。 江门职业技术学院教案授课时间第4周授课地点课程类型理论课授课题目堆栈和队列授课班级教学目的与教学要求掌握堆栈的有关操作;理解队列的定义、特性和运算；理解队列的顺序存储实现及其性能分析；理解循环队列的背景和实现方法。重点与难点堆栈的应用教学方法手段（教具）讲授法主要内容栈的定义和运算；栈的 C 描述、顺序存储结构及运算实现；栈在表达式求解中的作用。队列的

6、定义和运算；队列的 C 描述、顺序存储结构以及运算实现参考资料精品课程网站:课后作业与思考题P583.1;3.2;3.3教学后记教学过程时间分配3.1.1 栈的定义和运算 栈的定义及相关概念，栈的示意图 栈的特征 栈的基本运算 和 C 描述（注意几个关键问题的细节讨论） ： (1) 初始化栈 (2) 判断栈是否为空 (3) 取栈顶元素值 (4) 入栈 (5) 出栈 (6) 判断栈是否为满 初始化的讨论，函数返回值的方法，错误信息类型的引入，私有和公用属性的讨论。3.1.2 顺序栈 栈的顺序存储结构 顺序栈，示意图 顺序栈上运算的实现（结合示意图分析算法思想，然后写出算法）3.1.3 栈的应用

7、举出若干应用实例，说明栈在软件设计中的广泛应用。 栈的基本应用实例： 表达式的计算， 从软件技术的发展到表达式的计算的介绍，表达式计算方法的讨论 （以示意图表现计算过程） 。3.1.2 队列的定义和运算 队列 队列的特性 队列示意图 队尾，队头，入队和出队 队列的基本运算 和 C+ 描述 ： (1) 初始化队列 (2) 判队列是否为空 (3) 取队头元素 (4) 入队 (5) 出队 (6) 判队列是否为满 基本讨论与栈类似。3.2 顺序队列和循环队列 队列的顺序存储结构 顺序队列，示意图 由顺序队列中运算的实现可能出现“假溢出”，引入循环队列（示意图）。 提出问题：对循环队列，如何判断队列的满

8、和空的状态？解决方法：设置一个入队（出队）标志；或者少用一个元素空间。 循环队列中运算的实现（结合示意图讲解）。江门职业技术学院教案授课时间第5周授课地点教C504教D502课程类型理论课授课题目串授课班级07软件工程；07信息管理教学目的与教学要求理理解串的相关概念，串的基本和常用运算的定义，理解串的两种顺序存储方式，能实现有关运算。重点与难点串的两种顺序存储方式，实现有关运算。教学方法手段（教具）讲授法主要内容串的概念、运算、存储结构及运算的实现。参考资料精品课程网站:课后作业与思考题P76 4.1;4.2;4.3;4.4教学后记教学过程时间分配串的定义 串名，串值，串的长度，空串，子串（

9、举例说明） 串的基本运算： （ 1 ）赋值 （ 2 ）求长度 （ 3 ）连接 （ 4 ）求子串 （ 5 ）串比较（比较是否相等，比较大小） 串的常用运算： （ 6 ）插入 （ 7 ）删除 串的存储：顺序串，链串（结点大小的概念，示意图） 举例说明链串运算的实现。江门职业技术学院教案授课时间第6，7，8周授课地点教C504教D502课程类型理论课授课题目树和二叉树授课班级07软件工程；07信息管理教学目的与教学要求理解树和二叉树的定义及相关术语；理解二叉树的五个性质及相关概念；理解二叉树的两种存储结构的形式、描述及特点，理解二叉树的遍历运算，并能综合应用理解树和森林的存储结构及其描述，树（森林）

10、与二叉树的相互转换，树（森林）的遍历算法；理解树模型在软件设计中的作用；理解哈夫曼树的有关概念、应用及构造。重点与难点有关树和二叉树的算法。教学方法手段（教具）讲授法主要内容树和二叉树的概念，二叉树的性质和存储方法，二叉树的三种遍历算法和线索化概念及算法，树的存储，二叉树与树（森林）的相互转换，哈夫曼树。参考资料精品课程网站:课后作业与思考题P1466.1;6.2;6.3;6.4;6.5;6.7;6.8;6.18;6.22教学后记教学过程时间分配7.1 树的定义和运算 举出若干现实生活和软件设计中的树形结构的实例，引入树的概念。 树，根，子树 几种常见的表示树结构的形式： （ 1 ）图形表示法

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

12、本形态 二叉树的性质： （较简单直观的性质，可以不给出证明。） 性质 1 ：在二叉树的第 i 层上的结点数 2 i-1 （ i0 ）。 性质 2 ：深度为 k 的二叉树的结点数 2 k -1 （ k0 ）。 性质 3 ：对任一棵非空的二叉树 T ，如果其叶子数为 n 0 ，度为 2 的结点数为 n 2 ，则有下面的关系式成立： n 0 =n 2 +1 。（证明） 满二叉树，完全二叉树的定义 性质 4 ：有 n 个结点的完全二叉树 (n0) 的深度为 +1 。 性质 5 ：在编号的完全二叉树中，各结点的编号之间的关系为： 编号为 i 的结点如果存在左孩子，则其编号为 2i ，如果存在右孩子，则其

13、编号为 2i+1 ，如果存在父结点，则其编号为 。 （提出并讲解一个与二叉树的性质）相关的例题。 二叉树的存储结构： 顺序存储结构 按完全二叉树的编号次序进行，示意图，缺点：空间的浪费，引入动态链表结构。 二叉链表存储结构 二叉链表，相关描述，示意图。 7.3 二叉树的遍历 基本遍历方法讨论：先序遍历，中序遍历，后序遍历。详细讲解几种算法的思想。 遍历算法的求解过程，举出实例： 对给定二叉树，分别写出它的先序、中序和后序序列。（结合示意图分步讲解） 已知二叉树的先（后）序和中序序列，试构造出相应的二叉树。（求解过程示意图） 遍历算法的实现： 先序遍历算法 中序遍历算法 后序遍历算法 为加深学生

14、对递归形式的遍历算法的理解，举例说明遍历算法的执行过程（遍历过程示意图）。 二叉树遍历算法的应用： 二叉树遍历算法的简单应用：对二叉树遍历算法适当修改，便可得到许多问题的求解算法。 二叉树遍历算法思想的应用：法形式较繁杂的递归算法的编写、阅读及证明。江门职业技术学院教案授课时间第9，10周授课地点教C504教D502课程类型理论课授课题目图授课班级07软件工程；07信息管理教学目的与教学要求理解图的相关概念、图的存储结构；熟练掌握图的两种遍历算法（深度优先搜索遍历和广度优先搜索遍历），并能灵活应用；熟练掌握两种求解最小生成树的算法（ Prim 算法和 Kruskal 算法）；熟练掌握拓扑排序算

15、法和关键路径算法，并能灵活应用；熟练掌握两种最短路径算法（ Dijkstra 算法和 Floyd 算法），并能灵活应用。 重点与难点图的两种遍历算法以及各应用问题的求解算法。教学方法手段（教具）讲授法主要内容图的相关概念、存储结构、图的遍历、最小生成树、拓扑排序和关键路径、最短路径。参考资料精品课程网站:课后作业与思考题P1917.1;7.3;7.4;7.5;7.6;7.7;7.9;7.10教学后记教学过程时间分配8.1 图结构的定义、相关术语和运算 结合示意图讲解： 图 顶点，弧 / 边 无向图，有向图，带权图（网络） 无向完全图，有向完全图，子图 邻接，邻接点，度，入度，出度 路径，简单路

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

17、 2 广度优先搜索遍历 广度优先搜索遍历算法描述 广 度优先搜索遍历（ bfs ）算法描述，示意图 执行过程，顶点访问序列， 广 度遍历生成树 广度遍历算法： 详细讲述算法思想，给出算法的实现。 广度遍历算法应用实例 8.4 最小生成树 从现实中的问题引入最小生成树。 最小生成树的定义，如何构造最小生成树？分别介绍两种算法。 1 Prim 算法 Prim 算法的求解思想 求解实例，示意图 算法的实现 2 Kruskal 算法 Kruskal 算法的求解思想 求解实例，示意图 算法的实现。 8.5 拓扑排序 有向无环图的应用：两个问题：拓扑排序、关键路径。 工程，子工程（活动），活动之间的制约关

18、系 工程问题：工程能否顺利进行？ 用图（ AOV 网）来表示工程，判断工程能否顺利进行等价于判断 AOV 网中是否存在有向回路。 如何判断 AOV 网中是否存在有向回路？拓扑排序。 拓扑排序、拓扑序列的概念 拓扑排序的方法步骤，举实例说明，示意图。 拓扑排序算法及实现。 8.6 最短路径 1 从单个顶点到其余各顶点之间的最短路径： Dijkstra 算法 用 Dijkstra 算法求解从单个顶点到其余各顶点之间的最短路径的求解方法，举实例说明求解过程，结合示意图讲解。 讨论 Dijkstra 算法的实现，给出算法描述。 2 各顶点之间的最短路径： FLOYD 算法 算法思想，求解实例分析，算法

19、描述，算法分析江门职业技术学院教案授课时间第11周授课地点课程类型理论课授课题目查找授课班级教学目的与教学要求理解查找的相关概念，理解简单顺序查找、二分查找、分块有序表的查找算法的算法及性能分析；理解二叉排序树的定义、特性和查找算法，二叉排序树的构造、插入结点的算法和删除结点的实现方法； 重点与难点二分查找，二叉排序树的构造，教学方法手段（教具）讲授法主要内容查找的相关概念，顺序表中的顺序查找、有序表上的二分查找、分块有序表上的查找；二叉排序树构造、及查找运算；参考资料精品课程网站:课后作业与思考题P2218.2;8.3;8.4;8.5教学后记教学过程时间分配.1 查找运算的定义和相关概念 查

20、找，查找表 关键字（键），主关键字，次关键字 查找算法的时间性能，查找长度 9.2 顺序表的查找 顺序表查找的问题描述 1 简单顺序查找 简单顺序查找的算法思想，算法的实现（算法中设置监视哨的技巧） 算法在查找成功时的平均查找长度、失败时的查找长度。 由简单顺序查找的查找长度引入更快的查找方法二分查找。 2 有序表的二分查找 有序表，二分查找 ( 折半查找 ) 二分查找的算法思想，以示意图举实例说明查找过程。 二分查找算法的实现： 二分查找的递归算法，算法分析 二分查找的判定树及其构造 3 索引顺序表的查找 分块有序表，索引表 在索引顺序表中进行查找分两步：首先要通过在索引表中查找以确定元素所

21、在的块，然后在所确定的块中进行查找。每一步可以采用的查找方法。 简述索引顺序表的查找的时间性能。 9.3 二叉排序树二树表的查找 通过分析顺序类表查找的静态特性对维护表的制约，引入树表的查找。 二叉排序树的定义、特性 二叉排序树的查找方法、算法描述。 二叉排序树的运算： 插入结点与构造二叉排序树 江门职业技术学院教案授课时间第12，13周授课地点课程类型理论课授课题目排序授课班级教学目的与教学要求直接插入排序、 Shell 排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序和基数排序等。重点与难点快速排序、堆排序、归并排序教学方法手段（教具）讲授法、启发法主要内容理解排序的相关概念；理解

22、直接插入排序、 Shell 排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序和基数排序等算法的基本思想、算法、时间复杂度和空间占用情况，并能根据具体问题选择合适的算法。参考资料精品课程网站:课后作业与思考题P2479.3;9.7;9.8教学后记教学过程时间分配10.1 排序运算的定义和相关概念 排序的定义 排序的分类： 增排序和减排序 内部排序和外部排序 稳定排序和不稳定排序 插入排序、交换排序、选择排序、归并排序和基数排序 排序算法的分析指标： 时间性能分析，比较元素、移动或交换元素的平均次数。 空间性能分析，排序过程中所占用的辅助空间。 10.2 插入排序 插入排序算法的基本思想

23、1 直接插入排序 直接插入排序的基本思想 举例说明直接插入排序算法的执行过程。 直接插入排序算法的实现。 算法分析：稳定性、空间性能、时间性能。 2 希尔排序 希尔排序的基本思想 举例说明希尔排序算法的执行过程。 希尔排序算法的实现。 算法分析：稳定性、空间性能、时间性能。 10.3 交换排序 交换排序的基本思想 1 冒泡排序 冒泡排序的基本思想 举例说明冒泡排序算法的执行过程。 冒泡排序算法的实现。 算法分析：稳定性、空间性能、时间性能。 冒泡排序算法的时间复杂度依赖于待排序序列的初始特性，改善的冒泡排序算法，双向冒泡排序。 2 快速排序 快速排序算法是对冒泡排序算法的改进。 快速排序的基本思想 举例说明快速排序算法的执行过程。 快速排序算法的实现。 算法分析：稳定性、空间性能、时间性能（理想情况、最坏情况、一般情况）。 划分算法及其应用。 10.4 选择排序 选择排序的基本思想 1 直接选择排序 直接选择排序的基本思想 举例说明直接选择排序算法的执行过程。 直接选择排序算法的实现。 算法分析：稳定性、空间性能、时间性能。 改进直接选择排序算法的时间性能，引入堆排序。 2堆排序 堆的定义，堆顶，大根堆，小根堆 堆的完全二叉树描述示意图 堆的筛选极其算法的实现 堆排序及建堆的方法， 举例说明堆排序算法的执行过程。 堆排序算法的实现。 算法分析：稳定性、空间性