《大数据结构》教案设计.docx

资源描述

《大数据结构》教案设计.docx

《《大数据结构》教案设计.docx》由会员分享，可在线阅读，更多相关《《大数据结构》教案设计.docx（60页珍藏版）》请在冰点文库上搜索。

《大数据结构》教案设计.docx

《大数据结构》教案设计

师学院

教案（课时计划）

课程名称：

数据结构

授课班级：

授课地点：

主讲教师：

程玉胜

2015----2016学年第2学期

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、文件

编号

周次

日期

9.3

课时安排

课题

数据结构的概念及相关术语

教材的重点、难点分析

重点：

（1）数据结构的逻辑结构

（2）数据结构的存储结构

（3）抽象数据类型的概念

教

学

目

标

掌握数据、数据元素、数据对象的概念

熟练掌握数据结构的概念及其逻辑结构和物理结构的分类

掌握抽象数据类型的定义方法

教学方法和教学手段

讲授法

多媒体

教

学

过

程

教学容安排与板书设计：

第一章绪论

1．1什么是数据结构

非数值计算问题举例

《数据结构》产生的背景

《数据结构》在计算机科学中的地位和作用

教

学

过

程

1．2基本概念和术语

数据

数据元素

数据对象

数据结构

数据结构的形式定义Data-Structure=（D,S）

数据的逻辑结构及分类：

集合、线性、树形、图形结构

数据的物理结构：

顺序存储结构与链式存储结构

数据类型

抽象数据类型

抽象数据类型的形式定义ADT=（D,S,P）

抽象数据类型定义举例—Triplet

师生双边活动：

提问：

什么是数据类型？

举例：

演示实验：

教具准备：

课后作业

1.2,1.19

教学后记

教材：

[1]严蔚敏吴伟民编著：

数据结构（C语言版），清华大学，1997年

参考书目：

[1]WirthN：

Algorithms+DataStructures=Programs，Prentice-HallInc.，1976

[2][美]S巴斯：

计算机算法：

设计和分析引论，复旦大学，1985

编号

周次

日期

9.6

课时安排

课题

抽象数据类型的表示与实现、算法和算法分析

教材的重点、难点分析

重点：

（1）算法复杂度的分析方法

难点：

（1）算法复杂度的分析方法

教

学

目

标

（1）理解数据抽象的意义

（2）熟悉类C语言

（3）掌握抽象数据类型的表示和实现方法

（4）掌握算法描述和算法分析的方法

教学方法和教学手段

教

学

过

程

教学容安与排板书设计：

1．3抽象数据类型的表示和实现

数据抽象的意义

类C语言

抽象数据类型的表示和实现举例

教

学

过

程

1．4算法和算法分析

算法

算法的定义

算法的特性：

有穷性、确定性、可行性、输入、输出

算法设计的要求

正确性、可读性、健壮性、效率与低存储量需求

算法效率的度量

时间度量的方法分析

时间复杂度

T（n）=O（f（n））

时间复杂度的计算

算法的存储空间需求

S（n）=O（f（n））

师生双边活动：

提问：

举例：

演示实验：

教具准备：

课后作业

1.4,1.20

教学后记

编号

周次

日期

9.10

课时安排

课题

线性表的类型定义、线性表的顺序表示和实现

教材的重点、难点分析

重点：

（1）顺序表的基本运算

（2）顺序表上实现的各种算法的时间性能分析

教

学

目

标

（1）理解线性表的逻辑结构特征

（2）熟练掌握顺序表的描述方法、特点及有关概念

（3）熟练掌握顺序表的基本运算

教学方法和教学手段

教

学

过

程

教学容安排与板书设计：

第二章线性表

线性结构的特点

2．1线性表的类型定义

线性表的定义及其表示

线性表的类型定义

线性表操作举例：

用线性表表示集合、线性表的合并

教

学

过

程

2．2线性表的顺序表示和实现

线索性表的顺序表示

线性表的顺序存储结构的定义及其特征

顺序表的基本运算

顺序表的初始化

顺序表的插入操作

顺序表的删除操作

顺序表的合并

顺序表基本操作的时间复杂度计算

师生双边活动：

提问：

举例：

演示实验：

教具准备：

课后作业

2.12

教学后记

编号

周次

日期

9.13

课时安排

课题

线性表的链式表示和实现（线性链表）

教材的重点、难点分析

重点：

（1）链表的基本运算

（2）链表上实现的各种算法的时间性能分析

教

学

目

标

（1）熟练掌握链表的描述方法、特点及有关概念

（2）掌握链表的基本运算

（3）掌握静态链表的构造方法

教学方法和教学手段

教

学

过

程

教学容安排与板书设计：

2．3线性表的链式表示和实现

2．3．1线性链表

单链表的定义

单链表的存储结构特征

单链表的基本操作：

插入

教

学

过

程

删除

有序链表的合并

静态链表

静态链表的定义

静态链表的操作举例

师生双边活动：

提问：

malloc（）free（）

举例：

演示实验：

教具准备：

课后作业

2.17,2.25

教学后记

编号

周次

日期

9.17

课时安排

课题

循环链表、双向链表、一元多项式的表示及相加

教材的重点、难点分析

难点：

（1）循环链表

教

学

目

标

（1）掌握循环链表的特点

（2）掌握双向链表的特点

（3）从时空角度综合比较顺序表和链表的不同特点及使用场合

（4）能应用线性表解决一些实际问题

教学方法和教学手段

教

学

过

程

教学容安排与板书设计：

2．3．2循环链表

循环链表的定义

循环链表的操作

教

学

过

程

2．3．3双向链表

双向链表的定义

双向链表的操作特点

线性链表的类型定义

2．4一元多项式的表示及相加

一元多项式的表示

一元多项式的相加

一元多项式的类型定义

多项式的相加算法

师生双边活动：

提问：

举例：

演示实验：

教具准备：

课后作业

2.32

教学后记

编号

周次

日期

9.20

课时安排

课题

栈、栈应用举例（数制转换、括号匹配、行编辑）

教材的重点、难点分析

重点：

（1）栈在两种存储结构上实现的基本运算。

难点：

栈满栈空的条件及它们的描述

教

学

目

标

（1）掌握栈这种数据结构的特点

（2）熟悉栈与线性表的关系

（3）重点掌握顺序栈和链式栈的五种基本运算

（4）掌握栈的应用方法

教学方法和教学手段

教

学

过

程

教学容安排与板书设计：

第三章栈与队列

3．1栈

3．1．1抽象数据类型栈的定义

栈及其与线性表的关系

栈的类型定义

教

学

过

程

3．1．2栈的表示和实现

顺序栈的定义

链栈的定义

3．2栈的应用举例

3．2．1数制转换

3．2．2括号匹配的检验

3．2．3行编辑程序

师生双边活动：

提问：

举例：

演示实验：

教具准备：

课后作业

3.15

教学后记

编号

周次

日期

9.24

课时安排

课题

迷宫求解、表达式求值、栈与递归的实现

教材的重点、难点分析

教

学

目

标

（1）能应用栈解决一些实际问题

（2）了解递归算法执行过程中栈的变化过程

教学方法和教学手段

教

学

过

程

教学容安排与板书设计：

3．2．4迷宫求解

3．2．5表达式求值

3．3栈与递归的实现

教

学

过

程

师生双边活动：

提问：

举例：

演示实验：

教具准备：

课后作业

3.19,3.25

教学后记

编号

周次

日期

9.27

课时安排

课题

队列

教材的重点、难点分析

重点：

（1）队列在两种存储结构上实现的基本运算。

难点：

（1）循环队列（注意队满队空的条件及它们的描述）

教

学

目

标

（1）掌握队列这种数据结构的特点

（2）熟悉队列与线性表的关系

（3）掌握循环队列和链式队列的五种基本运算

（4）能应用队列解决一些实际问题

教学方法和教学手段

教

学

过

程

教学容安排与板书设计：

3．4队列

3．4．1抽象数据类型队列的定义

队列的定义（FIFO）

队列的类型定义

教

学

过

程

3．4．2链队列—队列的链式表示和实现

单链队列的定义

单链队列的操作

3．4．3循环队列—队列的顺序表示和实现

队列的顺序存储结构

循环队列的基本操作

师生双边活动：

提问：

举例：

演示实验：

教具准备：

课后作业

3.29

教学后记

编号

周次

日期

10.1

课时安排

课题

机动

教材的重点、难点分析

教

学

目

标

教学方法和教学手段

教

学

过

程

教学容安排与板书设计：

教

学

过

程

师生双边活动：

提问：

举例：

演示实验：

教具准备：

课后作业

教学后记

编号

周次

日期

10.4

课时安排

课题

习题课

教材的重点、难点分析

教

学

目

标

教学方法和教学手段

讲授法

教

学

过

程

教学容安排与板书设计：

教

学

过

程

师生双边活动：

提问：

举例：

演示实验：

教具准备：

课后作业

教学后记

编号

周次

日期

10.8

课时安排

课题

串类型的定义、串的表示和实现

教材的重点、难点分析

重点：

（1）串的基本运算

难点：

（1）串的动态存储结构

教

学

目

标

（1）熟悉串的有关概念，串与线性表的关系

（2）掌握串的静态存储结构与动态存储结构和它们的优缺点

（3）熟练掌握串的基本运算

教学方法和教学手段

教

学

过

程

教学容安排与板书设计：

第四章串

4．1串类型的定义

串的概念

串类型的定义

教

学

过

程

4．2串的表示和实现

4．2．1定长顺序存储表示

串的定长顺序存储表示

串联接

求子串

4．2．2堆分配存储表示

串的堆分配存储表示

堆的基本操作

4．2．3串的块链存储表示

师生双边活动：

提问：

举例：

演示实验：

教具准备：

课后作业

4.17,4.22/4.24

教学后记

编号

周次

日期

10.11

课时安排

课题

串的模式匹配算法、串操作应用举例

教材的重点、难点分析

教

学

目

标

（1）理解串的模式匹配算法

（2）了解串的应用

教学方法和教学手段

教

学

过

程

教学容安排与板书设计：

4．3串的模式匹配算法

4．3．1求子串位置的定位函数

4．3．2模式匹配的一种改进算法

KMP算法

教

学

过

程

4．4串操作应用举例

4．4．1文本编辑

师生双边活动：

提问：

举例：

演示实验：

教具准备：

课后作业

4.8

教学后记

编号

周次

日期

10.15

课时安排

课题

数组的定义、顺序表示和实现、矩阵的压缩存储

教材的重点、难点分析

重点：

（1）多维数组的存储方式

（2）矩阵的压缩存储方式

难点：

（1）稀疏矩阵的压缩存储表示下实现的算法

教

学

目

标

（1）熟悉数组的按行（列）优先顺序的存储结构中的地址计算方法

（2）熟悉特殊矩阵在压缩存储时的下标变换

（3）理解稀疏矩阵的三元组和十字链表两种压缩存储表示

教学方法和教学手段

教

学

过

程

教学容安排与板书设计：

第五章数组和广义表

5．1数组的定义

数组的类型定义

二维数组

教

学

过

程

5．2数组的顺序表示和实现

二维数组的存储方式

数组的顺序存储表示和实现

5．3矩阵的压缩存储

5．3．1特殊矩阵

对称矩阵

对角矩阵

5．3．2稀疏矩阵

稀疏矩阵的类型定义

1、三元组顺序表

师生双边活动：

提问：

举例：

演示实验：

教具准备：

课后作业

5.21

教学后记

编号

周次

日期

10.18

课时安排

课题

稀疏矩阵的存储结构、广义表的定义和存储结构

教材的重点、难点分析

重点：

（1）广义表的定义及其运算

教

学

目

标

（1）掌握稀疏矩阵的存储结构

（2）熟悉广义表的有关概念和运算

（3）掌握广义表的两种存储结构

教学方法和教学手段

教

学

过

程

教学容安排与板书设计：

2、行逻辑的顺序表

3、十字链表

5．4广义表的定义

教

学

过

程

广义表的类型定义

广义表举例

广义表的特点

5．5广义表的存储结构

讨论：

M元多项式的表示

广义表的递归算法

师生双边活动：

提问：

举例：

演示实验：

教具准备：

课后作业

5.26,5.12

教学后记

编号

周次

日期

10.22

课时安排

课题

树的定义和基本术语、二叉树的定义

教材的重点、难点分析

重点：

（1）树的基本术语

（2）二叉树的定义

教

学

目

标

（1）掌握树的定义和有关术语

（2）熟悉二叉树的递归定义，有关术语及基本概念

教学方法和教学手段

教

学

过

程

教学容安排与板书设计：

第六章树和二叉树

6．1树的定义和基本术语

树的类型定义

基本术语

教

学

过

程

6．2二叉树

6．2．1二叉树的定义

二叉树的类型定义

二叉树的基本形态

师生双边活动：

提问：

举例：

演示实验：

教具准备：

课后作业

6.2

教学后记

编号

周次

日期

10.25

课时安排

课题

二叉树的性质和和存储结构

教材的重点、难点分析

重点：

（1）二叉树的存储结构

难点：

（1）二叉树的性质

教

学

目

标

（1）熟练掌握二叉树的性质及证明方法

（2）熟练掌握二叉树的顺序和链式存储结构及特点

教学方法和教学手段

讲授法

教

学

过

程

教学容安排与板书设计：

6．2．2二叉树的性质

性质1

性质2

性质3

性质4

性质5

教

学

过

程

6．2．3二叉树的存储结构

顺序存储结构

链式存储结构

师生双边活动：

提问：

举例：

演示实验：

教具准备：

课后作业

6.6,6.11

教学后记

编号

周次

日期

10.29

课时安排

课题

遍历二叉树和线索二叉树

教材的重点、难点分析

重点：

（1）二叉树的遍历算法及其相关应用

难点：

（1）二叉树的非递归遍历算法

教

学

目

标

（1）熟练掌握二叉树的各种遍历

（2）能灵活运用遍历算法实现二叉树的基本运算

（3）掌握二叉树的线索化及相应算法

教学方法和教学手段

教

学

过

程

教学容安排与板书设计：

6．3遍历二叉树和线索二叉树

6．3．1遍历二叉树

遍历二叉树的递归算法

先序遍历

中序遍历

后序遍历

教

学

过

程

遍历二叉树的非递归算法

遍历二叉树的其他算法

二叉树的其他操作

6．3．2线索二叉树

线索二叉树及其存储结构

二叉树的线索化

师生双边活动：

提问：

举例：

演示实验：

教具准备：

课后作业

6.43,6.47,6.56

教学后记

编号

周次

日期

11.1

课时安排

课题

树和森林

教材的重点、难点分析

重点：

（1）树的存储结构

难点：

（1）森林、树与二叉树之间的转换

教

学

目

标

（1）掌握树的存储结构及其特点

（2）熟练掌握森林、树与二叉树之间的转换方法

（3）掌握森林和树的遍历

教学方法和教学手段

教

学

过

程

教学容安排与板书设计：

6．4树和森林

6．4．1树的存储结构

双亲表示法

孩子表示法

孩子兄弟表示法

教

学

过

程

6．4．2森林与二叉树的转换

森林与二叉树的对应关系

二叉树与森林的对应关系

6．4．3树和森林的遍历

先序遍历森林

中序遍历森林

师生双边活动：

提问：

举例：

演示实验：

教具准备：

课后作业

6.60,6.66

教学后记

编号

周次

日期

11.5

课时安排

课题

赫夫曼树及其应用

教材的重点、难点分析

重点：

（1）赫夫曼编码

难点：

（1）赫夫曼编码

教

学

目

标

（1）掌握最优化二叉树的特性、熟练掌握建立最优二叉树的方法

（2）熟练掌握哈夫曼编码的方法

教学方法和教学手段

讲授法

教

学

过

程

教学容安排与板书设计：

6．6赫夫曼树

6．6．1最优二叉树

最优二叉树的概念

构造赫夫曼树

最优判定算法

6．6．2赫夫曼编码

教

学

过

程

求赫夫曼编码

师生双边活动：

提问：

举例：

演示实验：

教具准

展开阅读全文