2022年《数据结构》教案

1、安庆师范学院 教案 课时方案 课程名称 : 数据结构 授课班级 : 授课地点 : 主讲老师 : 程玉胜 2022-2022 学年第 2 学期 第 1 页,共 70 页目 录 01,数据结构得概念及相关术语 02,抽象数据类型得表示与实现,算法与算法分析 03,线性表得类型定义,线性表得次序表示与实现 04,线性表得链式表示与实现 线性链表 05,循环链表,双向链表,一元多项式得表示及相加 06,栈,栈应用举例 数制转换,括号匹配,行编辑 07,迷宫求解,表达式求值,栈与递归得实现 08,队列 09,机动 10,习题课 11,串类型得定义,串得表示与实现 12,串得模式匹配算法,串操作应用举例

2、13,数组得定义,次序表示与实现,矩阵得压缩储备 14,稀疏矩阵得储备结构,广义表 15,树得定义与基本术语,二叉树得定义 16,二叉树得性质,二叉树得储备结构 17,遍历二叉树与线索二叉树 18,树与森林 19,赫夫曼树及其应用 20,习题课 21,图得定义与术语,图得储备结构 22,十字链表,邻接多重表,图得遍历 23,图得连通性问题 24,有向无环图及其应用 25,最短路径 26,静态查找表 27,二叉排序树与平稳二叉树 28, B- 树与 B+ 树 29,哈希表 30,排序概述,插入排序 31,快速排序,选择排序 32,归并排序,基数排序 33,外部排序,各种排序方法得比较 34,文件

3、 编号 1第 2 页,共 70 页周次 1日期 9, 3 课时支配 2课题 数据结构得概念及相关术语 教材 重点 :1 数据结构得规律结构 得 重 2 数据结构得储备结构 点 , 难 点 3 抽象数据类型得概念 分析 把握数据,数据元素,数据对象得概念 娴熟把握数据结构得概念及其规律结构与物理结构得分类 教 学 把握抽象数据类型得定义方法 目 标 教学 讲授法 方法 与 教学 多媒体 手段 教 教学内容支配与板书设计 : 第一章 绪论 1.1 什么就是数据结构 学 非数值运算问题举例 过 程 数据结构产生得背景 数据结构在运算机科学中得位置与作用 教 1.2 基本概念与术语 第 3 页,共 7

4、0 页学 数据 过 程 数据元素 数据对象 数据结构 数据结构得形式定义 Data-Structure = D, S 数据得规律结构及分类 :集合,线性,树形,图形结构 数据得物理结构 :次序储备结构与链式储备结构 数据类型 抽象数据类型 抽象数据类型得形式定义 ADT = D, S, P 抽象数据类型定义举例 Triplet 师生双边活动 : 提问 : 什么就是数据类型？ 举例 : 演示试验 : 教具预备 : 课后 1, 2,1, 19 作业 教材 : 1 严蔚敏 吴伟民编著 :数据结构 C 语言版 ,清华高校出版社 ,1997 年 教学 参考书目 : , ,1976 后记 1Wirth N

5、:Algorithms+Data Structures=Programs,Prentice-Hall Inc 2 美 S 巴斯 :运算机算法 :设计与分析引论 ,复旦高校出版社 ,1985 编号 2第 4 页,共 70 页周次 1日期 9, 6 课时支配 2课题 抽象数据类型得表示与实现,算法与算法分析 教材 重点 :1 算法复杂度得分析方法 得 重 点 , 难 点 分析 难点 :1 算法复杂度得分析方法 1 懂得数据抽象中意义 教 学 目 标 2 熟识类 C 语言 3 把握抽象数据类型得表示与实现方法 4 把握算法描述与算法分析得方法 教学 方法 与 教学 手段 教学内容安与排板书设计 :

6、1.3 抽象数据类型得表示与实现 教 学 过 程 教 数据抽象中意义 类 C 语言 抽象数据类型得表示与实现举例 1.4 算法与算法分析 第 5 页,共 70 页学 算法 过 程 算法得定义 算法得特性 :有穷性,确定性,可行性,输入,输出 算法设计得要求 正确性,可读性,健壮性,效率与低储备量需求 算法效率得度量 时间度量得方法分析 时间复杂度 Tn = Ofn 时间复杂度得运算 算法得储备空间需求 Sn = Ofn 师生双边活动 : 提问 : 举例 : 演示试验 : 教具预备 : 课后 1, 4,1, 20 作业 教学 后记 编号 3第 6 页,共 70 页周次 2日期 9, 10 课时支

7、配 2课题 线性表得类型定义,线性表得次序表示与实现 教材 重点 :1 次序表得基本运算 得 重 2 次序表上实现得各种算法得时间性能分析 点 , 难 点 分析 1 懂得线性表得规律结构特点 教 学 2 娴熟把握次序表得描述方法,特点及有关概念 3 娴熟把握次序表得基本运算 目 标 教学 方法 与 教学 手段 教 教学内容支配与板书设计 : 其次章 线性表 线性结构得特点 学 2.1 线性表得类型定义 过 程 线性表得定义及其表示 线性表得类型定义 线性表操作举例 :用线性表表示集合,线性表得合并 教 2.2 线性表得次序表示与实现 第 7 页,共 70 页学 线干脆表得次序表示 过 程 线性

8、表得次序储备结构得定义及其特点 次序表得基本运算 次序表得初始化 次序表得插入操作 次序表得删除操作 次序表得合并 次序表基本操作得时间复杂度运算 师生双边活动 : 提问 : 举例 : 演示试验 : 教具预备 : 课后 2, 12 作业 教学 后记 编号 4第 8 页,共 70 页周次 2日期 9, 13 课时支配 2课题 线性表得链式表示与实现 线性链表 教材 重点 :1 链表得基本运算 得 重 2 链表上实现得各种算法得时间性能分析 点 , 难 点 分析 1 娴熟把握链表得描述方法,特点及有关概念 教 学 2 把握链表得基本运算 3 把握静态链表得构造方法 目 标 教学 方法 与 教学 手

9、段 教学内容支配与板书设计 : 2.3 线性表得链式表示与实现 教 学 过 程 2.3.1 线性链表 单链表得定义 单链表得储备结构特点 单链表得基本操作 : 插入 教 删除 第 9 页,共 70 页学 有序链表得合并 过 程 静态链表 静态链表得定义 静态链表得操作举例 师生双边活动 : 提问 : malloc free 举例 : 演示试验 : 教具预备 : 课后 2, 17,2, 25 作业 教学 后记 编号 5第 10 页,共 70 页周次 3日期 9, 17 课时支配 2课题 循环链表,双向链表,一元多项式得表示及相加 教材 得 重 点 , 难 点 分析 难点 :1 循环链表 1 把握

10、循环链表得特点 教 学 目 标 2 把握双向链表得特点 3 从时空角度综合比较次序表与链表得不同特点及使用场合 4 能应用线性表解决一些实际问题 教学 方法 与 教学 手段 教学内容支配与板书设计 : 2.3.2 循环链表 教 学 过 循环链表得定义 循环链表得操作 程 教 2.3.3 双向链表 第 11 页,共 70 页学 双向链表得定义 过 程 双向链表得操作特点 线性链表得类型定义 2.4 一元多项式得表示及相加 一元多项式得表示 一元多项式得相加 一元多项式得类型定义 多项式得相加算法 师生双边活动 : 提问 : 举例 : 演示试验 : 教具预备 : 课后 2, 32 作业 教学 后记

11、 编号 6第 12 页,共 70 页周次 3日期 9, 20 课时支配 2课题 栈,栈应用举例 数制转换,括号匹配,行编辑 教材 重点 :1 栈在两种储备结构上实现得基本运算； 得 重 点 , 难 点 分析 难点 :栈满栈空得条件及它们得描述 1 把握栈这种数据结构得特点 教 学 目 标 2 熟识栈与线性表得关系 3 重点把握次序栈与链式栈得五种基本运算 4 把握栈得应用方法 教学 方法 与 教学 手段 教 学 过 程 教学内容支配与板书设计 : 第三章 栈与队列 3.1 栈 3.1.1 抽象数据类型栈得定义 栈及其与线性表得关系 栈得类型定义 教 3.1.2 栈得表示与实现 第 13 页,共

12、 70 页学 次序栈得定义 过 程 链栈得定义 3.2 栈得应用举例 3.2.1 数制转换 3.2.2 括号匹配得检验 3.2.3 行编辑程序 师生双边活动 : 提问 : 举例 : 演示试验 : 教具预备 : 课后 3, 15 作业 教学 后记 编号 7第 14 页,共 70 页周次 4日期 9, 24 课时支配 2课题 迷宫求解,表达式求值,栈与递归得实现 教材 得 重 点 , 难 点 分析 1 能应用栈解决一些实际问题 教 2 明白递归算法执行过程中栈得变化过程 学 目 标 教学 方法 与 教学 手段 教学内容支配与板书设计 : 3.2.4 迷宫求解 教 学 过 3.2.5 表达式求值 程

13、 3.3 栈与递归得实现 教 第 15 页,共 70 页学 过 程 师生双边活动 : 提问 : 举例 : 演示试验 : 教具预备 : 课后 3, 19,3, 25 作业 教学 后记 编号 8第 16 页,共 70 页周次 4日期 9, 27 课时支配 2课题 队列 教材 重点 :1 队列在两种储备结构上实现得基本运算； 得 重 点 , 难 点 分析 难点 :1 循环队列 留意队满队空得条件及它们得描述 1 把握队列这种数据结构得特点 教 学 目 标 2 熟识队列与线性表得关系 3 把握循环队列与链式队列得五种基本运算 4 能应用队列解决一些实际问题 教学 方法 与 教学 手段 教学内容支配与板

14、书设计 : 3.4 队列 教 学 过 程 教 3.4.1 抽象数据类型队列得定义 队列得定义 FIFO 队列得类型定义 3.4.2 链队列队列得链式表示与实现 第 17 页,共 70 页学 单链队列得定义 过 程 单链队列得操作 3.4.3 循环队列队列得次序表示与实现 队列得次序储备结构 循环队列得基本操作 师生双边活动 : 提问 : 举例 : 演示试验 : 教具预备 : 课后 3, 29 作业 教学 后记 编号 9第 18 页,共 70 页周次 5日期 10,1 课时支配 2课题 机动 教材 得 重 点 , 难 点 分析 教 学 目 标 教学 方法 与 教学 手段 教学内容支配与板书设计

15、: 教 学 过 程 教 第 19 页,共 70 页学 过 程 师生双边活动 : 提问 : 举例 : 演示试验 : 教具预备 : 课后 作业 教学 后记 编号 10 第 20 页,共 70 页周次 5日期 10,4 课时支配 2课题 习题课 教材 得 重 点 , 难 点 分析 教 学 目 标 教学 讲授法 方法 与 教学 手段 教学内容支配与板书设计 : 教 学 过 程 教 第 21 页,共 70 页学 过 程 师生双边活动 : 提问 : 举例 : 演示试验 : 教具预备 : 课后 作业 教学 后记 编号 11 第 22 页,共 70 页周次 6日期 10,8 课时支配 2课题 串类型得定义,串

16、得表示与实现 教材 重点 :1 串得基本运算 得 重 点 , 难 点 分析 难点 :1 串得动态储备结构 1 熟识串得有关概念 ,串与线性表得关系 教 学 2 把握串得静态储备结构与动态储备结构与它们得优缺点 3 娴熟把握串得基本运算 目 标 教学 方法 与 教学 手段 教 教学内容支配与板书设计 : 第四章 串 4.1 串类型得定义 学 串得概念 过 程 串类型得定义 教 4.2 串得表示与实现 第 23 页,共 70 页学 过 程 4.2.1 定长次序储备表示 串得定长次序储备表示 串联接 求子串 4.2.2 堆支配储备表示 串得堆支配储备表示 堆得基本操作 4.2.3 串得块链储备表示

17、师生双边活动 : 提问 : 举例 : 演示试验 : 教具预备 : 课后 4, 17,4, 22/4, 24 作业 教学 后记 编号 12 第 24 页,共 70 页周次 6日期 10,11 课时支配 2课题 串得模式匹配算法,串操作应用举例 教材 得 重 点 , 难 点 分析 1 懂得串得模式匹配算法 教 2 明白串得应用 学 目 标 教学 方法 与 教学 手段 教学内容支配与板书设计 : 4.3 串得模式匹配算法 教 学 过 程 教 4.3.1 求子串位置得定位函数 4.3.2 模式匹配得一种改进算法 KMP 算法 4.4 串操作应用举例 第 25 页,共 70 页学 过 4.4.1 文本编

18、辑 程 师生双边活动 : 提问 : 举例 : 演示试验 : 教具预备 : 课后 4, 8 作业 教学 后记 编号 13 第 26 页,共 70 页周次 7日期 10,15 课时支配 2课题 数组得定义,次序表示与实现,矩阵得压缩储备 教材 重点 :1 多维数组得储备方式 得 重 2 矩阵得压缩储备方式 点 , 难 点 分析 难点 :1 稀疏矩阵得压缩储备表示下实现得算法 1 熟识数组得按行 列 优先次序得储备结构中得地址运算方法 教 学 2 熟识特殊矩阵在压缩储备时得下标变换 3 懂得稀疏矩阵得三元组与十字链表两种压缩储备表示 目 标 教学 方法 与 教学 手段 教 学 过 程 教 教学内容支

19、配与板书设计 : 第五章 数组与广义表 5.1 数组得定义 数组得类型定义 二维数组 5.2 数组得次序表示与实现 第 27 页,共 70 页学 二维数组得储备方式 过 程 数组得次序储备表示与实现 5.3 矩阵得压缩储备 5.3.1 特殊矩阵 对称矩阵 对角矩阵 5.3.2 稀疏矩阵 稀疏矩阵得类型定义 1,三元组次序表 师生双边活动 : 提问 : 举例 : 演示试验 : 教具预备 : 课后 5, 21 作业 教学 后记 编号 14 第 28 页,共 70 页周次 7日期 10,18 课时支配 2课题 稀疏矩阵得储备结构,广义表得定义与储备结构 教材 重点 :1 广义表得定义及其运算 得 重

20、 点 , 难 点 分析 1 把握稀疏矩阵得储备结构 教 学 2 熟识广义表得有关概念与运算 3 把握广义表得两种储备结构 目 标 教学 方法 与 教学 手段 教学内容支配与板书设计 : 2,行规律链接得次序表 教 学 过 3,十字链表 程 5.4 广义表得定义 教 广义表得类型定义 第 29 页,共 70 页学 广义表举例 过 程 广义表得特点 5.5 广义表得储备结构 争辩 : M 元多项式得表示 广义表得递归算法 师生双边活动 : 提问 : 举例 : 演示试验 : 教具预备 : 课后 5, 26,5, 12 作业 教学 后记 编号 15 第 30 页,共 70 页周次 8日期 10,22

21、课时支配 2课题 树得定义与基本术语,二叉树得定义 教材 重点 :1 树得基本术语 得 重 2 二叉树得定义 点 , 难 点 分析 1 把握树得定义与有关术语 教 2 熟识二叉树得递归定义 ,有关术语及基本概念 学 目 标 教学 方法 与 教学 手段 教 教学内容支配与板书设计 : 第六章 树与二叉树 6.1 树得定义与基本术语 学 树得类型定义 过 程 基本术语 教 6.2 二叉树 第 31 页,共 70 页学 过 程 6.2.1 二叉树得定义 二叉树得类型定义 二叉树得基本外形 师生双边活动 : 提问 : 举例 : 演示试验 : 教具预备 : 课后 6, 2 作业 教学 后记 编号 16

22、第 32 页,共 70 页周次 8日期 10,25 课时支配 2课题 二叉树得性质与与储备结构 教材 重点 :1 二叉树得储备结构 得 重 点 , 难 点 分析 难点 :1 二叉树得性质 1 娴熟把握二叉树得性质及证明方法 教 2 娴熟把握二叉树得次序与链式储备结构及特点 学 目 标 教学 讲授法 方法 与 教学 手段 教学内容支配与板书设计 : 6.2.2 二叉树得性质 教 学 过 程 性质 1 性质 2 性质 3性质 4性质 5教 6.2.3 二叉树得储备结构 第 33 页,共 70 页学 次序储备结构 过 程 链式储备结构 师生双边活动 : 提问 : 举例 : 演示试验 : 教具预备 :

23、 课后 6, 6,6, 11 作业 教学 后记 编号 17 第 34 页,共 70 页周次 9日期 10,29 课时支配 2课题 遍历二叉树与线索二叉树 教材 重点 :1 二叉树得遍历算法及其相关应用 得 重 点 , 难 点 分析 难点 :1 二叉树得非递归遍历算法 1 娴熟把握二叉树得各种遍历 教 学 2 能灵敏运用遍历算法实现二叉树得基本运算 3 把握二叉树得线索化及相应算法 目 标 教学 方法 与 教学 手段 教学内容支配与板书设计 : 6.3 遍历二叉树与线索二叉树 教 学 过 程 6.3.1 遍历二叉树 遍历二叉树得递归算法 先序遍历 中序遍历 后序遍历 教 遍历二叉树得非递归算法

24、第 35 页,共 70 页学 遍历二叉树得其她算法 过 程 二叉树得其她操作 6.3.2 线索二叉树 线索二叉树及其储备结构 二叉树得线索化 师生双边活动 : 提问 : 举例 : 演示试验 : 教具预备 : 课后 6, 43,6, 47,6,56 作业 教学 后记 编号 18 第 36 页,共 70 页周次 9日期 11,1 课时支配 2课题 重点 :1 树得储备结构 树与森林 教材 得 重 点 , 难 点 分析 难点 :1 森林,树与二叉树之间得转换 1 把握树得储备结构及其特点 教 学 2 娴熟把握森林,树与二叉树之间得转换方法 3 把握森林与树得遍历 目 标 教学 方法 与 教学 手段

25、教学内容支配与板书设计 : 6.4 树与森林 教 学 过 程 6.4.1 树得储备结构 双亲表示法 孩子表示法 孩子兄弟表示法 教 6.4.2 森林与二叉树得转换 第 37 页,共 70 页学 森林与二叉树得对应关系 过 程 二叉树与森林得对应关系 6.4.3 树与森林得遍历 先序遍历森林 中序遍历森林 师生双边活动 : 提问 : 举例 : 演示试验 : 教具预备 : 课后 6, 60,6, 66 作业 教学 后记 编号 19 第 38 页,共 70 页周次 10 日期 11,5 课时支配 2课题 重点 :1 赫夫曼编码 赫夫曼树及其应用 教材 得 重 点 , 难 点 分析 难点 :1 赫夫曼

26、编码 1 把握最优化二叉树得特性,娴熟把握建立最优二叉树得方法 教 2 娴熟把握哈夫曼编码得方法 学 目 标 教学 讲授法 方法 与 教学 手段 教学内容支配与板书设计 : 6.6 赫夫曼树 教 学 过 程 6.6.1 最优二叉树 最优二叉树得概念 构造赫夫曼树 最优判定算法 6.6.2 赫夫曼编码 教 求赫夫曼编码 第 39 页,共 70 页学 过 程 师生双边活动 : 提问 : 举例 : 演示试验 : 教具预备 : 课后 6, 26 作业 教学 后记 编号 20 第 40 页,共 70 页周次 10 日期 11,8 课时支配 2课题 习题课 教材 得 重 点 , 难 点 分析 教 学 目

27、标 教学 讲授法 方法 与 教学 手段 教学内容支配与板书设计 : 教 学 过 程 教 第 41 页,共 70 页学 过 程 师生双边活动 : 提问 : 举例 : 演示试验 : 教具预备 : 课后 作业 教学 后记 编号 21 第 42 页,共 70 页周次 11 日期 11,12 课时支配 2课题 图得定义与术语,图得储备结构 教材 重点 :1 图得储备 得 重 点 , 难 点 分析 1 熟识图得有关术语与概念 教 2 娴熟把握图得四种储备结构与建立算法 学 目 标 教学 方法 与 教学 手段 教 教学内容支配与板书设计 : 第七章 图 7.1 图得定义与术语 学 图得类型定义 过 程 图得

28、分类 连通图,连通重量,生成树 教 7.2 图得储备结构 第 43 页,共 70 页学 过 程 7.2.1 数组表示法 图得邻接矩阵 网及其邻接矩阵 7.2.2 邻接表 图得邻接表储备表示 邻接表与逆邻接表 师生双边活动 : 提问 : 举例 : 演示试验 : 教具预备 : 课后 7, 14,7, 15 作业 教学 后记 编号 22 第 44 页,共 70 页周次 11 日期 11,15 课时支配 2课题 十字链表,邻接多重表,图得遍历 教材 重点 :1 图得遍历 得 重 点 , 难 点 分析 难点 :1 图得遍历非递归算法 1 娴熟把握图得四种储备结构与建立算法 教 2 娴熟把握图得深度优先遍

29、历与广度优先遍历 学 目 标 教学 方法 与 教学 手段 教学内容支配与板书设计 : 7.2.3 十字链表 教 学 过 程 有向图得十字链表储备表示 构造有向图 7.2.4 邻接多重表 无向图得邻接多重表 教 7.3 图得遍历 第 45 页,共 70 页学 过 7.3.1 深度优先搜寻 程 7.3.2 广度优先搜寻 师生双边活动 : 提问 : 举例 : 演示试验 : 教具预备 : 课后 7, 22,7, 28 作业 教学 后记 编号 23 第 46 页,共 70 页周次 12 日期 11,19 课时支配 2课题 图得连通性问题 教材 重点 :1 最小生成树得构造 得 重 点 , 难 点 分析

30、把握最小生成树得两种构造方法 教 学 目 标 教学 方法 与 教学 手段 教学内容支配与板书设计 : 7.4 图得连通性问题 教 7.4.1 无向图得连通重量与生成树 学 过 程 7.4.2 有向图得强连通重量 教 7.4.3 最小生成树 第 47 页,共 70 页学 过 程 Prim 算法 Kruskal 算法 7.4.3 关节点与重连通重量 师生双边活动 : 提问 : 举例 : 演示试验 : 教具预备 : 课后 7, 32 作业 教学 后记 编号 24 第 48 页,共 70 页周次 12 日期 11,22 课时支配 2课题 重点 :1 拓扑排序 有向无环图及其应用 教材 得 重 2 求关

31、键路径 点 , 难 点 分析 难点 :1 求关键路径 1 把握拓扑排序得方法 教 2 把握关键路径得求法 学 目 标 教学 方法 与 教学 手段 教学内容支配与板书设计 : 7.5 有向无环图及其应用 教 学 过 程 DAG 7.5.1 拓扑排序 7.5.2 关键路径 AOE 网 关键路径 教 第 49 页,共 70 页学 过 程 师生双边活动 : 提问 : 举例 : 演示试验 : 教具预备 : 课后 7, 36 作业 教学 后记 编号 25 第 50 页,共 70 页周次 13 日期 11,26 课时支配 2课题 重点 :1 求最短路径 最短路径 教材 得 重 点 , 难 点 分析 难点 :

32、1 求每一对顶点之间得最短路径 娴熟把握从某个源点到其余各顶点得最短路径得求法 把握求每一对顶点之间得最短路径得求法 教 学 目 标 教学 方法 与 教学 手段 教学内容支配与板书设计 : 7.6 最短路径 教 学 过 7.6.1 从某个源点到其余各顶点得最短路径 Dijkstra 算法 程 7.6.2 每一对顶点之间得最短路径 教 第 51 页,共 70 页学 过 程 师生双边活动 : 提问 : 举例 : 演示试验 : 教具预备 : 课后 7, 42 作业 教学 后记 编号 26 第 52 页,共 70 页周次 13 日期 11,29 课时支配 2课题 重点 :1 次序查找 静态查找表 教材

33、 得 重 2 折半查找 点 , 难 点 分析 1 娴熟把握静态查找得各种方法 教 学 目 标 教学 方法 与 教学 手段 教 学 过 程 教 教学内容支配与板书设计 : 第八章 查找 查找表与静态查找表与动态查找表 关键字与主关键字与次关键字 查找与成功与不成功 8.1 静态查找表 第 53 页,共 70 页学 静态查找表得类型定义 过 程 8.1.1 次序表得查找 次序查找 平均查找长度 8.1.2 有序表得查找 折半查找 折半查找得性能分析 8.1.3 静态树表得查找 8.1.4 索引次序表得查找 表其索引表 分块查找 师生双边活动 : 提问 : 举例 : 演示试验 : 教具预备 : 课后

34、 9, 29 作业 教学 后记 编号 27 第 54 页,共 70 页周次 14 日期 12,3 课时支配 2课题 二叉排序树与平稳二叉树 教材 重点 :1 动态查找表及查找算法 得 重 2 二叉排序树 点 , 难 点 分析 难点 :1 二叉排序树 1 娴熟把握二叉排序树得构造方法及查找过程 教 2 把握 AVL 树得构造 学 目 标 教学 方法 与 教学 手段 教学内容支配与板书设计 : 8.2 动态查找表 教 学 过 程 动态查找表得类型定义 8.2.1 二叉排序树与平稳二叉树 1,二叉排序树及其查找过程 二叉排序树 教 2,二叉排序树得插入与删除 第 55 页,共 70 页学 二叉排序树

35、得构造 过 程 二叉排序树得删除 3,二叉排序树得查找分析 4,平稳二叉树 平稳二叉树与不平稳得二叉树 平稳树得生成过程 二叉排序树得平稳旋转 二叉排序树得类型定义 5,平稳树查找得分析 师生双边活动 : 提问 : 举例 : 演示试验 : 教具预备 : 课后 9, 33 作业 教学 后记 编号 28 第 56 页,共 70 页周次 14 日期 12,6 课时支配 2课题 B -树与 B+树 教材 得 重 点 , 难 点 分析 教 1 把握 B -树与 B+ 树得构造与查找 2 明白键树得构造方法 学 目 标 教学 方法 与 教学 手段 教 教学内容支配与板书设计 : B-树与 B +树 1,

36、B-树及其查找 学 过 程 2, B-树查找分析 教 3, B- 树得插入与删除 第 57 页,共 70 页学 过 程 4, B + 树 8.2.3 键树 师生双边活动 : 提问 : 举例 : 演示试验 : 教具预备 : 课后 作业 教学 后记 编号 29 第 58 页,共 70 页周次 15 日期 12,10 课时支配 2课题 哈希表 教材 得 重 点 , 难 点 分析 难点 :1 哈希表及查找算法 1 娴熟把握哈希表得建表方法,冲突得处理及查找过程 教 学 2 懂得哈希表与其它储备结构得表得本质区分 3 娴熟把握哈希表得平均查找长度得运算 等概率 目 标 教学 方法 与 教学 手段 教学内

37、容支配与板书设计 : 8.3 哈希表 教 学 过 程 8.3.1 什么就是哈希表 哈希函数 冲突 散列 教 8.3.2 哈希函数得构造方法 第 59 页,共 70 页学 过 程 1,直接定址法 2,数字分析法 3,平方取中法 4,折叠法 5,除留余数法 6,随机数法 8.3.3 处理冲突得方法 1,开放定址法 2,再哈希法 3,链地址法 4,建立一个公共溢出区 8.3.4 哈希表得查找及其分析 师生双边活动 : 提问 : 举例 : 演示试验 : 教具预备 : 课后 9, 46 作业 教学 后记 编号 30 第 60 页,共 70 页周次 15 日期 12,13 课时支配 2课题 重点 :1 希

38、尔排序 排序概述,插入排序 教材 得 重 点 , 难 点 分析 1 深刻懂得插入排序得基本思想及其特点 教 学 2 娴熟把握插入排序方法得排序过程 3 把握插入排序算法时间复杂度得分析方法并熟记其分析结论 目 标 教学 方法 与 教学 手段 教 教学内容支配与板书设计 : 第九章 排序 9.1 排序概述 学 排序 过 程 排序方法得稳固性 内部排序与外部排序 教 9.2 插入排序 第 61 页,共 70 页学 过 9.2.1 直接插入排序 程 9.2.2 其她插入排序 1,折半插入排序 2, 2-路插入排序 3,表插入排序 9.2.3 希尔排序 师生双边活动 : 提问 : 举例 : 演示试验 : 教具预备 : 课后 10, 25 作业 教学 后记 编号 31 第 62 页,共 70 页周次 16 日期 12,17 课时支配 2课题 重点 :1 快速排序 快速排序,选择排序 教材 得 重 2 堆排序 点 , 难 点 分析 难点 :1 快速排序 2堆排序 1 深刻懂得快速排序得基本思想及其特点 教 学 目 标 2 娴熟把握快速排序方法得排序过程 3 把握快速排序算法时间复杂度得分析方法并熟记其分析结论 4 深刻懂得选择排序得基本思想及其特