《数据结构》教案.docx

《数据结构》教案 安庆师范学院 教案（课时计划） 课程名称：数据结构授课班级： 授课地点： 主讲教师：程玉胜 2 3 PAGE PAGE 100 目 录 01、数据结构的概念及相关术语 02、抽象数据类型的表示与实现、算法和算法分析 03、线性表的类型定义、线性表的顺序表示和实现 04、线性表的链式表示和实现（线性链表） 05、循环链表、双向链表、一元多项式的表示及相加 06、栈、栈应用举例（数制转换、括号匹配、行编辑） 07、迷宫求解、表达式求值、栈与递归的实现 08、队列 09、机动 10、习题课 11、串类型的定义、串的表示和实现 12、串的模式匹配算法、串操作应用举例 13、数组的定义、顺序表示和实现、矩阵的压缩存储 14、稀疏矩阵的存储结构、广义表 15、树的定义和基本术语、二叉树的定义 16、二叉树的性质、二叉树的存储结构 17、遍历二叉树和线索二叉树 18、树和森林 19、赫夫曼树及其应用 20、习题课 21、图的定义和术语、图的存储结构 22、十字链表、邻接多重表、图的遍历 23、图的连通性问题 24、有向无环图及其应用 25、最短路径 26、静态查找表 27、二叉排序树和平衡二叉树 28、B-树和 B+树 29、哈希表 30、排序概述、插入排序 31、快速排序、选择排序 32、归并排序、基数排序 33、外部排序、各种排序方法的比较 34、文件 编号 1 周次 1 日期 9.3 课时安排 2 课题 数据结构的概念及相关术语重点：(1)数据结构的逻辑结构 的重教材 (2)数据结构的存储结构 的重 难点点、 (3)抽象数据类型的概念 难点 分析 掌握数据、数据元素、数据对象的 教 学 概念 目 标 熟练掌握数据结构的概念及其逻 辑结构和物理结构的分类 掌握抽象数据类型的定义方法 讲授法 教学方法 教学和 多媒体 教学 手段 教学内容安排与板书设计： 第一章绪论 1．1 什么是数据结构 教 非数值计算问题举例 学 过 《数据结构》产生的背景 程 《数据结构》在计算机科学中的地 位和作用 教 1．2 基本概念和术语 数据 学 数据元素 过 数据对象数据结构 程 数 据 结 构 的 形 式 定 义 Data-Structure = (D, S) 数据的逻辑结构及分类：集合、线性、树形、图形结构 数据的物理结构：顺序存储结构与链式存储结构 数据类型 抽象数据类型 抽象数据类型的形式定义 ADT = (D, S, P) 抽象数据类型定义举例— Triplet 师生双边活动： 课后作业 课后 作业 提问：什么是数据类型？ 举例： 演示实验： 教具准备： 1.2,1.19 教材： [1]严蔚敏 吴伟民编著：数据结构（C 语言版），清华大学出版社，1997 年 教学 后记 参考书目： [1]Wirth N：Algorithms+Data Structures=Programs，Prentice-Hall Inc.，1976 [2][美]S 巴斯：计算机算法：设计和分析引论，复旦大学出版社， 1985 编号 编号 2 周次 1 日期 9.6 课时安排 2 课题 教材的重点、难点 分析 抽象数据类型的表示与实现、算法 和算法分析 重点：(1)算法复杂度的分析方法 难点：(1)算法复杂度的分析方法 (1)理解数据抽象的意义(2)熟悉类 C 语言 (3)掌握抽象数据类型的表示和实 教 现方法 学 目 (4)掌握算法描述和算法分析的方 标 法 教学方法和 教学手段 教学内容安与排板书设计： 抽象数据类型的表示和实现 教 学 数据抽象的意义 过 程 类 C 语言 抽象数据类型的表示和实现举例 算法和算法分析算法 算法的定义 算法的特性：有穷性、确定性、可行性、输入、输出 算法设计的要求 教 正确性、可读性、健壮性、效 学 率与低存储量需求算法效率的度量 过 时间度量的方法分析 程 时间复杂度 T(n) = O(f(n)) 时间复杂度的计算算法的存储空间需求 S(n) = O(f(n)) 师生双边活动： 课后作业 课后 作业 提问： 举例： 演示实验： 教具准备： 1.4,1.20 教学 后记 编号 编号 3 周次 2 日期 9.10 课时安排 2 课题 教材的重点、难点 线性表的类型定义、线性表的顺序 表示和实现 重点：(1)顺序表的基本运算 (2)顺序表上实现的各种算 分析 法的时间性能分析 理解线性表的逻辑结构特征 熟练掌握顺序表的描述方法、特点及有关概念 教 学 (3)熟练掌握顺序表的基本运算 目 标 教学方法和 教学手段 教学内容安排与板书设计： 教 第二章线性表 学 过 线性结构的特点 程 线性表的类型定义 线性表的定义及其表示线性表的类型定义 线性表操作举例：用线性表表示集合、线性表的合并 线性表的顺序表示和实现线索性表