数据结构教案.docx
- 文档编号:4412735
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:18
- 大小:20.30KB
数据结构教案.docx
《数据结构教案.docx》由会员分享,可在线阅读,更多相关《数据结构教案.docx(18页珍藏版)》请在冰点文库上搜索。
数据结构教案
湖北大学知行学院
教
案
2009――2010学年第一学期
课程名称:
《数据结构》
专业班次:
课时总数:
其中:
教师名称:
尤新华
授课时间
第2周第1-2次课
授课题目
第1章绪论
授课类型
理论课(是);实践课()
教学时数
2学时
教
学
目
的
及
要
求
1、理解计算机信息处理中数据组织与运算处理的关系;
2、熟悉各名词、术语的含义,掌握数据结构相关基本概念,特别是数据、数据元素、数据对象、数据结构、逻辑结构、存储结构等;
3、了解数据的逻辑结构和存储结构之间的关系,了解常见的“集合、线性表、树、图”的逻辑结构形式和“顺序、链表、索引、散列”存储组织方法;
4、了解抽象数据类型的定义、表示与实现方法。
5、算法
教
学
内
容
提
要
1、数据结构研究的主要内容与涉及的基本概念;
2、数据类型与抽象数据类型。
3、算法
教
学
重
点
及
难
点
1、数据的逻辑结构、存储结构与运算方法之间的关系
2、算法时间复杂度的衡量
教
学
手
段
讲授法、案例教学法
作
业
、
讨
论
、
思
考
思考:
1、抽象数据类型与数据类型的区别?
2、时间复杂度的比较?
课
后
小
结
本章重点讲解了数据结构的相关概念、几种常见的数据结构,难点是抽象数据类型的定义以及算法时间复杂度的分析。
数据结构教案
授课时间
第2周第3-4次课
授课题目
第2章线性表
授课类型
理论课(是);实践课()
教学时数
4学时
教
学
目
的
及
要
求
1、掌握线性表的逻辑表示
2、掌握线性表的顺序表示和算法的实现
3、掌握线性表的链式表示和算法实现
教
学
内
容
提
要
2.1线性表的逻辑表示
2.2顺序表
2.2.1顺序表的表示
2.2.2顺序表的实现
2.3单链表
2.3.1链表的表示
2.3.2单链表的实现
2.3.3循环链表的表示与实现
教
学
重
点
及
难
点
重点:
1、顺序表的表示
2、链表的表示
3、算法的实现
难点:
1、链表的表示与实现
教
学
手
段
讲授法、案例教学法
作
业
、
讨
论
、
思
考
讨论:
1、顺序表与链表的使用环境?
2、顺序表与链表各自的优缺点?
课
后
小
结
本章介绍了一种简单的数据结构—线性结构的表示与实现,要求掌握的内容:
1.线性表的逻辑表示
2.顺序表,利用高级语言实现顺序表的算法。
3.链表的表示与实现
数据结构教案
授课时间
第3周第5次课
授课题目
第2章线性表
授课类型
理论课(是);实践课()
教学时数
4学时
教
学
目
的
及
要
求
1、掌握线性表的应用
教
学
内
容
提
要
1、线性表的合并;
2、一元多项式的相加的实现
教
学
重
点
及
难
点
重点:
1、线性表的应用
难点:
1、一元多项式的链式实现
教
学
手
段
讲授法、案例教学法
作
业
、
讨
论
、
思
考
1、一元多项式相加与有序表的合并有什么异同?
课
后
小
结
本节介绍了线性结构的应用实例—有序表的合并和一元多项式的相加。
数据结构教案
授课时间
第3周第6次课
授课题目
第4章栈与队列
授课类型
理论课(是);实践课()
教学时数
2学时
教学
目的
及要
求
1、栈
2、栈的应用
教
学
内
容
提
要
§3.1栈
3.1.1抽象数据类型栈的定义
3.1.2栈的表示和实现
§3.2栈的应用举例
3.2.1数制转换
3.2.2括号匹配的检验
3.2.3行编辑程序
3.2.4迷宫求解
3.2.5表达式求值
§3.3栈与递归的实现
教学
重点及难
点
重点:
1、抽象数据类型栈的定义
2、栈的表示和实现
难点:
1、抽象数据类型栈的定义
教学
手段
讲授法、案例教学法
作业
、
讨论
、
思考
1、顺序栈与链栈之间的区别?
2、链栈的抽象数据类型的表示?
3、链栈抽象数据类型的实现?
课
后
小
结
本章主要介绍了线性表中的一个特例—栈,它其实是操作受限制的线性表,即总在一端进行操作。
它的特点是先进后出。
在函数调用和操作系统中的应用非常的广泛。
数据结构教案
授课时间
第4周第7-8次课
授课题目
第3章栈与队列
授课类型
理论课(是);实践课()
教学时数
2学时
教
学
目
的
及
要
求
1、掌握队列的抽象数据类型的定义
2、掌握队列的实现
3、理解队列的特点
4、掌握队列的应用
教
学
内
容
提
要
§3.4队列
3.4.1抽象数据类型队列的定义
3.4.2链队列----队列的链式表示和实现
3.4.3循环队列-----队列的顺序表示和实现
§3.5离散事件模拟(选讲)
教
学
重
点
及
难
点
重点:
1、队列的抽象数据类型的表示
2、队列的实现
难点:
1、队列的应用
教
学
手
段
讲授法、案例教学法
作业
讨论
思考
1、链式队列是否受限制?
2、链式队列的实现与表示?
课
后
小
结
1、掌握队列与线性表之间的联系;
2、了解队列与栈之间的区别;
3、区分栈与队列在实现细节上的不同;
4、熟悉栈的特点是先进后出,队列的特点是先进先出;
数据结构教案
授课时间
第5周第9-10次课
授课题目
第4章串
授课类型
理论课(是);实践课()
教学时数
4学时
教
学
目
的
及
要
求
通过本章的学习,应使学生掌握串的各种基本操作以及串的实际应用。
教
学
内
容
提
要
§4.1串类型的定义
§4.2串的表示和实现
4.2.1定长顺序存储表示
4.2.2堆分配存储表示
4.2.3串的块链存储表示
§4.3串的模式匹配算法
4.3.1求子串位置的定位函数Index(S,T,pos)
4.3.2模式匹配的一种改进算法
§4.4串操作应用举例(选讲)
4.4.1文本编辑
4.4.2建立词索引表
教
学
重
点
及
难
点
重点:
1、串在定长顺序存储结构下的各种基本操作;
2、理解有回溯的模式匹配和无回溯的模式匹配(KMP)算法数组的应用
难点:
模式匹配算法
教
学
手
段
讲授法、案例教学法
作
业
、
讨
论
、
思
考
1、讨论串的两种表示的不同?
2、串的模式匹配与传统的匹配有那些方面的改进?
课
后
小
结
本章介绍了串的表示与实现,以及串的应用——模式匹配算法,该算法在图形图像处理方面应用非常的广泛。
本章主要的讲解内容如下:
1.串的存储方式
2.在不同的存储方式下的实现
3.模式匹配算法
数据结构教案
授课时间
第6-7周第11-14次课
授课题目
第5章数组与广义表
授课类型
理论课(是);实践课()
教学时数
7学时
教
学
目
的
及
要
求
1、掌握数组的抽象数据类型的定义;
2、熟练掌握稀疏距阵的表示与地址的计算;
3、掌握三元组的定义和使用;
4、了解广义表的定义;
5、掌握广义表的各种计算;
6、了解广义表的各种存储方式;
教
学
内
容
提
要
§5.1数组的定义
§5.2数组的顺序表示和实现
§5.3矩阵的压缩存储
5.3.1特殊矩阵
5.3.2稀疏矩阵
§5.4广义表的定义
§5.5广义表存储结构
§5.6m元多项式的表示
§5.7广义表的递归算法
5.7.1求广义表的深度
5.7.2复制广义表
5.7.3建立广义表的存储结构
教
学
重
点
及
难
点
重点:
1、稀疏矩阵的定义与表示
2、三元组的定义和应用
3、广义表各种计算
难点:
1、稀疏矩阵求地址
2、三元组的应用
3、广义表的存储结构的表示
教
学
手
段
讲授法、案例教学法
作
业
、
讨
论
、
思
考
思考:
1、稀疏矩阵中各种特殊矩阵的地址的计算?
2、用三元组实现一元多项式的相加?
3、广义表中各种操作的实现?
课
后
小
结
1、掌握对特殊矩阵的压缩存储以及三元组存储
2、熟练运用特殊矩阵的基本操作
3、了解广义表的概念、应用范围和基本操作
数据结构教案
授课时间
第8-9周第15-18次课
授课题目
第6章树和二叉树
授课类型
理论课(是);实践课()
教学时数
8学时
教
学
目
的
及
要
求
1、了解树的基本概念;
2、理解二叉树的性质和存储结构;
3、掌握遍历二叉树和线索二叉树;
4、熟悉树的存储结构和遍历;
5、了解集合的一种表示方法;
6、掌握哈夫曼树及其应用
教
学
内
容
提
要
1、树的定义和存储结构(1学时)
2、二叉树的定义、性质、存储结构(2学时)
3、二叉树的遍历、线索算法(2学时)
4、树和二叉树的转换(1学时)
5、哈夫曼树及其应用(2学时)
教
学
重
点
及
难
点
重点:
1、二叉树的概念、性质;
2、二叉树的遍历方式;
3、构造二叉排序树
难点:
1、二叉树的遍历方式;
2、二叉排序树的构造方法;
3、二叉树的线索化。
教
学
手
段
讲授法、案例教学法
作
业
、
讨
论
、
思
考
完成课本中没有完成的有关二叉树的基本操作的实现。
课
后
小
结
树及二叉树在实际应用中使用很广,通过本章的学习,学生要熟练掌握二叉树的性质、基本操作以及二叉树的各种应用。
数据结构教案
授课时间
第10-11周第19-21次课
授课题目
第7章图
授课类型
理论课(是);实践课()
教学时数
2学时
教
学
目
的
及
要
求
1、学习图的基本概念;
2、掌握图的存储结构;
3、理解图的遍历及应用{最小生成树,最短路径等};
4、理解并掌握拓扑排序和关键路径等内容的学习,能解决生活中网络问题。
教
学
内
容
1、图的定义
2、图的存储结构
3、图的遍历操作(2学时)
4、图的几个典型应用问题(4学时
重
点
及
难
点
重点:
1、图的存储结构、典型应用问题
难点:
图的典型应用问题
教
学
手
段
讲授法、案例教学法
作
业
、
讨
论
、
思
考
编程完成拓扑排序、最短路径和关键路径。
课
后
小
结
本章介绍了一种重要的数据结构——图,图的逻辑描述和物理描述都是比较复杂的,因此,在存储上也比较复杂,同时有4中不同类型的图的存在,丰富的类型,导致了图的广泛应用,尤其在网络描述上用的更多;几种常见的应用是需要同学们理解并掌握的:
最小生成树、最短路径、拓扑排序和关键路径。
数据结构教案
授课时间
第11-12周第21-24次课
授课题目
第9章查找
授课类型
理论课(是);实践课()
教学时数
8学时
教
学
目
的
及
要
求
1、掌握静态查找表(顺序表,有序表,索引顺序表);
2、理解动态查找表(二叉排序树,平衡二叉树的建立和查找;
3、掌握哈希表的建立,查找及分析的查找性能,在应用中选择合适的查找方法。
教
学
内
容
提
要
1、静态查找表及查找算法:
顺序查找、折半查找(2学时)
2、动态查找表及查找算法:
二叉排序树(2学时)
3、哈希表及查找算法(2学时)
教
学
重
点
及
难
点
重点:
1、二叉排序树的构造方法;
2、二叉平衡树的建立方法;
3、哈希表的构造、应用;
难点:
1、二叉排序树的构造及应用;
2、哈希表的构造方法;
3、查找的性能分析
教
学
手
段
讲授法、案例教学法
作
业
、
讨
论
、
思
考
1、举例完成一个静态查找:
要求用三种不同的查找方法实现,并指出用二分查找的注意事项;
2、用一个实例完成二叉排序树,并将顺序打乱,看看相同的数据,不同的顺序构造的二叉排序树是否相同?
并描述影响二叉排序树性能的因素;
3、了解平衡二叉树的构造,当一棵树不是平衡二叉树时如何调整成一棵平衡二叉树;
4、分析哈希表与其他存储方式的不同,并比较哈希查找与构造哈希表之间的联系。
课
后
小
结
本章主要介绍了三种不同的查找方法:
静态查找和动态查找以及哈希查找方法。
其中静态查找有三种典型的算法:
顺序查找——适用于任何数据结构;二分查找——只用于顺序存储的有序表的查找;
索引查找。
动态查找介绍了两种典型的查找算法——二叉排序树和平衡二叉树。
哈希表是一种特殊的查找方式,必须先找到一种构造查找表的函数即哈希函数,然后根据哈希函数得到关键字的存储位置,构造查找表,查找过程和构造表的过程相同,在构造哈希表的时候要注意冲突的处理。
数据结构教案
授课时间
第13-14周第25-28次课
授课题目
第10章内部排序
授课类型
理论课(是);实践课()
教学时数
8学时
教
学
目
的
及
要
求
掌握插入排序、交换排序(起泡排序,快速排序)、选择排序(简单选择,树形选择,堆)、归并排序、基数排序等算法。
教
学
内
容
提
要
1、插入排序(2学时)
2、交换排序(2学时)
3、选择排序(2学时)
4、归并排序
5、基数排序(2学时)
教
学
重
点
及
难
点
重点:
1、各种排序方法的特点及其应用;实现排序的各种算法
难点:
各种排序算法的时间复杂度分析及应用中排序方法的选择
教
学
手
段
讲授法、案例教学法
作
业
、
讨
论
、
思
考
1、用一组数据,采用不同的方法进行排序,比较各种排序方法在最好和最坏的情况下的比较次数。
2、分析各种排序方法的适用场合。
课
后
小
结
本章主要介绍了多种内部排序方法:
插入排序、选择排序等等,这些排序方法在日常工作和生活中应用广泛,是需要同学们掌握并能运用的,关键的是要掌握各种排序方法的思路和特点,在实际应用中能快速的选择一种合适的算法。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 教案