新版数据结构教案.docx
《新版数据结构教案.docx》由会员分享，可在线阅读，更多相关《新版数据结构教案.docx（66页珍藏版）》请在冰点文库上搜索。
新版数据结构教案
五邑大学信息学院
《数据结构》教案
2007~2008年度第二学期
课程名称数据结构
课程主讲人白明、金旺春
课程所属教研室软件工程、计算机科学与技术
课程类型及学时理论课（含实验）、72学时
授课教材版本《数据结构（C++版）》
清华大学出版社
授课班级计算机科学与技术2006级1班、2班
网络工程2006级1班
软件工程2006级1班
授课日期2008年3月~7月
五邑大学信息学院制
二○○七年一月
教学专题——开课
1-1
教学专题
开课—课程综述
授课学时
1学时（50分钟）
教学章节
组织
授课对象
计算机学科各专业本科生
教学类型
理论课
授课形式
课堂讲授
教学重点
为什么要学习数据结构这门课以及如何学习
教学难点
认识课程，找到学好课程的方法
教学内容
和
教学过程
课程引入：
介绍数据结构课程在教学计划中的位置
5分钟
1．课程性质：
核心地位
2．课程学习目标
（1）学习知识角度
（2）培养能力角度
3．介绍教材：
主教材和与之配套的辅助教材
4．介绍参考文献资料：
多角度、全方位学习
5．介绍网络教学资源：
6．学习方法及要求
（1）坚持上课
（2）学会读书：
预习+复习+拓展
（3）认真作业和实验
（4）下载课件、演示系统，提高记忆效率
（5）理解知识+自主实践
7．考核要求：
作业+考勤+实验+自主实践（期中考核）+期末考试
5分钟
15分钟
3分钟
3分钟
5分钟
10分钟
2分钟
课程总结：
下定决心、树立信心、坚持恒心、改革创新
2分钟
教学提示
1．开课要精彩，激发兴趣，认识重要性
2．明确课程目标：
学些什么，达到的目标
3．需要具备的基本知识，对基础差的同学多鼓励—从现在做起==追赶—超出
4．为什么学，怎样学，如何学好
5．考研
思考题
课后导读
你对你所学的专业了解多少？
你对学习这门课应该如何准备？
在数据结构方面，最早的权威性著作是Knuth所著的系列丛书《计算机程序设计艺术》，这套书非常值得一看
教学后记
教学专题——数据结构的研究对象
1-2
教学专题
数据结构的兴起和发展
授课学时
1学时（50分钟）
教学章节
1．1、1．2
授课对象
计算机学科各专业本科生
教学类型
理论课
授课形式
课堂讲授
教学重点
抽象与数据类型；数据结构的研究对象
教学难点
数据结构与类的对应关系
教学内容
和
教学目标
知识点
学习要求
了解
理解
掌握
熟练掌握
程序设计的性质
√
数据结构的起源和发展
√
数据结构与程序设计的关系
√
计算机求解问题的一般过程
√
数据结构的研究对象
√
教学过程
课程引入：
介绍数据结构课程体系的起源。
了解历史—专业素养
3分钟
1．提出问题：
程序设计的实质是什么？
通过具体实例得出答案
2．介绍数据结构与程序设计的关系，强调数据结构始终是程序设计的基础，强调从面向对象角度看待数据结构
3．从发展的观点和应用的观点讨论数据结构的发展
4．从计算机求解问题的一般过程入手，建立抽象和数据模型的初步概念
5．通过具体实例总结数据结构的研究对象，注意引申数据元素之间的关系
3分钟
5分钟
12分钟
3分钟
15分钟
10分钟
课程总结：
数据结构研究的对象是非数值计算问题
2分钟
教学提示
1．从问题求解过程入手，理解“数据结构+算法=程序”，理解数据结构和算法在问题求解中的作用
2．通过结构化程序和面向对象程序对比，从框架上理解为什么将数据结构从结构化发展到面向对象
3．数据结构是从非数值问题抽象出来的数据模型，这个阶段的学生还没有抽象和模型的概念，需要补充抽象和模型的相关知识
媒体使用
多媒体课件：
Kunth的照片及介绍；用动画辅助解释基本概念
教学网络平台：
相关教学材料
思考题
课后导读
在数据结构方面，最早的权威性著作是Knuth所著的系列丛书《计算机程序设计艺术》，这套书非常值得一看
许多人致力于计算机科学中的问题求解，实际上这正是该领域吸引人的地方。
《如何求解问题》（曹宏庆.中国水电出版社）是提高问题求解能力的经典著作
教学后记
教学专题——数据结构的基本概念
2-30
教学专题
数据结构的基本概念
授课学时
1.4学时（70分钟）
教学章节
1.3
授课对象
计算机学科各专业本科生
教学类型
理论课
授课形式
课堂讲授
教学重点
数据结构及相关概念；数据的逻辑结构和存储结构之间的关系
教学难点
数据元素；逻辑关系；抽象数据类型
教学内容
和
教学目标
知识点
学习要求
了解
理解
掌握
熟练掌握
数据、数据项、数据对象
√
数据元素
√
数据结构
√
数据的逻辑结构
√
数据的存储结构
√
逻辑结构和存储结构之间的关系
√
数据结构的访问接口
√
抽象数据类型
√
教学过程
课程引入：
根据生活中的实例简单理解什么是数据结构
3分钟
1．给出数据的定义，举例说明什么是数据
2．给出数据元素和数据项的定义，根据上一讲得个例子体会如何界定数据元素，总结数据、数据元素、数据项之间的关系
3．给出数据结构的定义，从问题求解的角度强调数据结构包含逻辑结构和存储结构两个方面
4．给出逻辑结构的定义重点解释逻辑关系
5．给出存储结构的定义，重点强调如何表示逻辑关系
6．从数据表示的角度总结逻辑结构和存储结构的关系
7．在理解数据类型抽象的基础上，给出抽象数据类型的定义，说明：
数据模型+一组操作=ADT
8．结合抽象数据类型的定义说明数据结构的访问接口
5分钟
8分钟
6分钟
10分钟
15分钟
5分钟
10分钟
5分钟
课程总结：
数据的逻辑结构、存储结构及其相互关系
3分钟
教学提示
1．注意对基本概念的引入和阐述，抓住要点，注意用生活中的实例进行类比逻辑
2．关系较抽象、较难理解，通过实例在具体数据模型中理解逻辑关系
3．抽象数据类型是贯穿课程始终的概念，不要求学生开始就深刻理解，在后续的课程中反复应用抽象数据类型的三个视图—同心圆式的教学方法
媒体使用
多媒体课件：
用动画实现存储结构；用动画辅助解释基本概念
教学网络平台：
相关教学材料
思考题
课后导读
[美]WilliamFord,WilliamTopp著,刘卫东，沈官林译，数据结构C++语言描述，清华大学出版社,第3章抽象数据类型和类和第7章形式数据类型
教学后记
教学专题——算法的基本概念
3-1+30
教学专题
算法的基本概念
授课学时
1.6学时（80分钟）
教学章节
1.3
授课对象
计算机学科各专业本科生
教学类型
理论课
授课形式
课堂讲授
教学重点
算法的定义及特性；伪代码描述算法
教学难点
算法的特性；伪代码描述算法
教学内容
和
教学目标
知识点
学习要求
了解
理解
掌握
熟练掌握
算法及算法的特性
√
算法和程序的关系
√
算法的描述方法—自然语言
√
算法的描述方法—程序流程图
√
算法的描述方法—程序设计语言
√
算法的描述方法—伪代码
√
用C++语言中的函数描述算法
√
教学过程
课程引入：
根据生活中的实例简单理解什么是算法
5分钟
1．给出算法的定义，从使用的角度讲解算法的特性
2．提出问题：
算法=程序？
指出程序设计的核心是算法
3．分别用自然语言、程序设计流程图和C++语言举例描述算法，从应用角度介绍优点、缺点、使用方法、注意事项
4．综合自然语言、程序设计流程图和C++语言描述算法的优缺点，给出伪代码描述，反映伪代码描述的优势
5．介绍用C++语言中的函数描述算法，强调用伪代码和C++描述算法是两种抽象级别，体现了抽象分级的思想
6．课堂练习用伪代码描述算法
10分钟
5分钟
20分钟
12分钟
15分钟
8分钟
课程总结：
算法的定义和描述方法；算法与程序的关系
5分钟
教学提示
1．算法特性要讲清楚透彻，从应用的角度讲解每一个特性的含义，其用途在于判断一个算法在形式上是否正确
2．伪代码描述算法比较灵活，但掌握存在难度，应先从框架上理解，再通过事例掌握基本方法
3．强调算法的作用，是不能直接执行的
媒体使用
多媒体课件：
用动画辅助解释基本概念
教学网络平台：
相关教学材料
思考题
课后导读
《计算与算法导论》章小莉等译，电子工业出版社。
关于如何设计一个好的算法请阅读第2章和第8章
教学后记
教学专题——算法及算法分析
3-2
教学专题
算法及算法分析
授课学时
1学时（50分钟）
教学章节
1．4
授课对象
计算机学科各专业本科生
教学类型
理论课
授课形式
课堂讲授
教学重点
用大O记号表示算法的时间
教学难点
算法分析的方法；用大O记号表示算法的时间性能
教学内容
和
教学目标
知识点
学习要求
了解
理解
掌握
熟练掌握
度量算法效率的方法—事后度量
√
度量算法效率的方法—事前估算
√
算法分析的目的
√
问题规模、基本语句
√
大O记号
√
估算算法时间复杂度的基本方法
√
最好、最坏、平均情况时间性能
√
教学过程
课程引入：
通过复习数据结构和算法的基本概念引出本讲内容
5分钟
1．提出问题：
什么是算法分析？
为什么要进行算法分析？
指出算法分析的目的决定了算法分析的方法
2．给出事后度量方法并指出该方法的局限性，引出事前估算的度量方法
3．根据一个算法实例给出算法分析的方法
4．给出问题规模和基本语句概念，从不同角度讲解大O记号
5．结合顺序查找算法，分析最好、最坏、平均情况的时间性能
6．说明空间复杂度的分析方法
5分钟
3分钟
15分钟
10分钟
5分钟
5分钟
课程总结：
算法分析的事前估算方法；用大O记号表示算法的时间性能
2分钟
教学提示
1．注意讲授算法分析过程中的思维变换
2．深刻理解大O记号的含义
媒体使用
多媒体课件：
用动画给出算法分析方法的过程；再用板书总结
教学网络平台：
相关教学材料
思考题
课后导读
《算法分析导论》冯舜玺译，机械工业出版社。
关于算法分析较深入的讨论见
第1章算法分析概述
教学后记
教学专题——线性表
（一）
4
教学专题
1．线性表的逻辑结构
2．线性表的顺序存储结构
授课学时
2学时（100分钟）
教学章节
2．1、2．2
授课对象
计算机学科各专业本科生
教学类型
理论课
授课形式
课堂讲授
教学重点
线性表的定义；线性表的逻辑特征；顺序表的存储特点；顺序表的基本操作
教学难点
线性表的抽象数据类型定义；用伪代码描述算法，描述顺序表的基本操作
教学内容
和
教学目标
知识点
学习要求
了解
理解
掌握
熟练掌握
线性表的定义
√
线性表的逻辑特征
√
线性表的抽象数据类型定义
√
线性表的基本操作
√
顺序表的存储特点
√
顺序表类
√
顺序表的基本操作
√
顺序表的插入、删除操作的时间性能
√
顺序表的优缺点
√
教学过程
课程引入：
通过几个二维表的实例
3分钟
1．给出线性表的定义，总结线性表的逻辑特性
2．复习ADT的三个视图（定义视图、设计视图、实现视图）
3．给出线性表的抽象数据类型定义
4．给出顺序表的存储示意图，总结存储特点
5．复习存储地址的有关内容，给出顺序表的随机存取特性
6．顺序表类的声明、构造函数、析构函数
7．给出顺序表插入操作的执行过程，写出伪代码，再写出C++描述
8．分析插入算法的时间性能，总结算法分析的一般步骤
9．对于顺序表的删除操作，给出必要的提示，要求学生自行完成
10．给出顺序表的查找操作的执行过程和算法
11．总结顺序表的优缺点
10分钟
5分钟
7分钟
10分钟
10分钟
15分钟
15分钟
5分钟
3分钟
7分钟
5分钟
课程总结：
线性表的逻辑结构；顺序表的存储特点和基本操作
5分钟
教学提示
1．线性表的定义要讲清楚透彻，向学生渗透一种理解概念的方法—问题分析、抓住要点、引申理解
2．通过线性表抽象数据类型进一步理解抽象数据类型的三个视图，理解模块化思想，掌握其使用方法
3．从实用角度出发复习C++语言相关知识
4．对于顺序表的基本操作算法，要讲思路、讲方法、讲过程，注意培养抽象思维能力和逻辑思维能力。
媒体使用
多媒体课件：
用动画辅助解释基本概念和模拟顺序表类的基本操作的执行过程
教学网络平台：
相关教学材料
思考题
课后导读
《数据结构（C语言版）》严蔚敏编著，清华大学出版社。
参阅相关章节：
关于线性表的定义采用二元组的形式
《数据结构与算法》齐德昱编著，清华大学出版社。
参阅相关章节：
注意顺序表的实现与本教材不同
教学后记
教学专题——线性表
（二）
5
教学专题
线性表的链接存储结构及实现
授课学时
2学时（100分钟）
教学章节
2．3、2．4
授课对象
计算机学科各专业本科生
教学类型
理论课
授课形式
课堂讲授
教学重点
单链表的存储特点；单链表的基本操作的算法及时间性能
教学难点
单链表查找、插入和删除算法
教学内容
和
教学目标
知识点
学习要求
了解
理解
掌握
熟练掌握
单链表的存储要点及存储特点
√
单链表类
√
单链表的顺序存取特性
√
单链表的插入、删除操作
√
单链表插入、删除操作的时间性能
√
单链表类的构造函数和析构函数
√
顺序表和单链表的比较
√
教学过程
课程引入：
通过分析顺序表的缺点引出链接存储结构
5分钟
1．根据一个实例给出线性表链接存储的实际内存状态，复习C++语言中指针的相关知识，抽象出单链表的存储结构示意图
2．区分指针变量和结点变量，说明头指针、头结点和尾指针
3．给出单链表类的声明，引申单链表类与顺序表类的关系
4．给出单链表查找的算法，总结单链表算法的设计模式
5．设计单链表的插入算法，分析时间性能
6．比较带头结点和不带头结点的单链表上的插入操作
7．设计单链表的删除算法，注意分析边界情况
8．对单链表类的构造函数，给出头插法和尾插法的算法
9．对单链表类的析构函数，给出必要的提示，要求学生自行完成
20分钟
10分钟
5分钟
10分钟
15分钟
10分钟
5分钟
12分钟
3分钟
课程总结：
将顺序表和单链表进行比较，总结并比较存储结构及实现方法
5分钟
教学提示
1．熟练使用指针是学好单链表的基本前提
2．单链表算法设计的关键是多练，安排一节习题课是非常必要的，如果学时较紧，至少通过课堂对相关作业进行点评
媒体使用
多媒体课件：
用动画模拟单链表各种操作的执行过程
教学网络平台：
相关教学材料
思考题
课后导读
《数据结构与算法》齐德昱编著，清华大学出版社。
参阅相关章节：
注意单链表表的实现与本教材不同
教学后记
教学专题——线性表（三）
6
教学专题
1．线性表的其它存储方法
2．线性表的应用举例
授课学时
2学时（100分钟）
教学章节
2．5及课后思考题和习题
授课对象
计算机学科各专业本科生
教学类型
理论课
授课形式
课堂讲授
教学重点
循环链表、双链表
教学难点
双链表的基本操作
教学内容
和
教学目标
知识点
学习要求
了解
理解
掌握
熟练掌握
循环链表的存储结构
√
循环链表的操作
√
双链表的存储结构
√
双链表的基本操作
√
静态链表的存储结构
√
静态链表的操作
√
间接寻址存储结构
√
约瑟夫环问题描述
√
设计算法求解约瑟夫环问题
√
教学过程
课程引入：
通过提出问题：
在单链表中如何查找某结点的前驱？
2分钟
1．将循环链表的插入算法与单链表的插入算法进行比较
2．在有头结点的循环链表中，如何查找第1个结点和最后1个结点，引出带尾指针的循环链表
3．如何更快速得到某结点的前驱（空间换时间），引出双链表
4．通过图示理解双链表的插入和删除操作，给出算法
5．如何通过连续存储实现连接关系，引出静态链表
6．通过图示理解静态链表的插入和删除操作过程
7．提出问题：
将数组和指针结合起来存储线性表会怎样？
引出间接寻址
8．通过图示理解间接存储结构上如何实现插入和删除操作，并与顺序表进行比较
9．给出约瑟夫环问题的描述，介绍该问题的起源
10．从逻辑上理解约瑟夫环问题的求解过程
11．分别用顺序存储结构和单链表存储结构实现约瑟夫环问题
12．其它问题或习题举例
8分钟
5分钟
5分钟
10分钟
5分钟
15分钟
5分钟
5分钟
5分钟
5分钟
20分钟5分钟
课程总结：
线性表的各种逻辑结构；线性表的存储特点和基本操作
5分钟
教学提示
1．循环链表和双链表是单链表的变形
2．静态链表和间接寻址是顺序存储和连接存储相结合的产物
3．重点在于灵活设计各种存储结构的思想
4．通过例题检验学生掌握线性表及其存储结构的教学效果。
媒体使用
多媒体课件：
用动画模拟算法和示例的执行过程，用动画辅助解释基本概念
教学网络平台：
相关教学材料
思考题
课后导读
《数据结构—C++实现》穆淮扣等编著，科学出版社。
参阅相关章节：
关于双链表的实现
上网查找约瑟夫环及其变形问题的解决方法，完成关于该问题的课程作业
教学后记
教学专题——栈
7
教学专题
栈
授课学时
2学时（100分钟）
教学章节
3．1、3．4．1
授课对象
计算机学科各专业本科生
教学类型
理论课
授课形式
课堂讲授
教学重点
栈的操作特性、顺序栈及实现、链栈及实现
教学难点
两栈共享空间
教学内容
和
教学目标
知识点
学习要求
了解
理解
掌握
熟练掌握
栈的定义及操作特性
√
栈的抽象数据类型定义
√
顺序栈及实现
√
两栈共享空间
√
链栈及实现
√
顺序栈和链栈的比较
√
顺序栈应用举例
√
教学过程
课程引入：
通过复习线性表的插入和删除操作引出栈
5分钟
1．给出栈的定义，通过实例说明栈的操作特性
2．根据顺序栈存储示意图给出入栈和出栈算法，分析时间性能。
总结：
顺序栈算法是顺序表算法的简化
3．如何提高栈空间的利用率？
引出两栈共享空间算法
4．复习单链表，如何改造成链栈？
5．根据链栈存储示意图给出入栈和出栈算法，分析时间性能。
总结：
链栈算法是单链表算法的简化
6．回顾顺序表和单链表的比较方法，引导学生得出顺序栈和链栈的比较结果
7．给出递归的定义，结合具体实例说明递归是一种描述问题和解决问题的基本方法
8．递归问题举例
9．给出描述递归函数运行轨迹的图示方法，强调递归的层次
10．总结递归函数，强调注意事项
10分钟
15分钟
25分钟
2分钟
15分钟
3分钟
5分钟
5分钟
5分钟5分钟
课程总结：
栈的操作特性；栈的基本操作和栈的应用
5分钟
教学提示
1．栈是计算机技术及程序设计中常用的数据结构之一，熟练掌握对后续学习有益
2．根据生活实例深刻理解栈的操作特性，并与线性表进行比较
3．从实用角度出发复习C++语言递归知识
4．通过递归函数的运行轨迹，引导学生理解递归的调用层次以及实参和形参的结合方法，及程序运行过程中工作栈的变化
媒体使用
多媒体课件：
用动画辅助解释基本概念和模拟各操作的执行过程
教学网络平台：
相关教学材料
思考题
课后导读
《数据结构与算法》齐德昱编著，清华大学出版社。
参阅相关章节：
注意用抽象类和继承类实现栈
《数据结构》刘大友等编著，高等教育出版社，相关章节对递归和汉诺塔问题进行了较深入的介绍
教学后记
教学专题——队列
8
教学专题
队列
授课学时
2学时（100分钟）
教学章节
3．2、3．4．2
授课对象
计算机学科各专业本科生
教学类型
理论课
授课形式
课堂讲授
教学重点
队列的操作特性、循环队列及实现、链队列及实现
教学难点
循环队列的存储方法及队空和队满的判断
教学内容
和
教学目标
知识点
学习要求
了解
理解
掌握
熟练掌握
队列的定义及操作特性
√
队列的抽象数据类型定义
√
顺序队列的假溢出现象
√
循环队列及实现
√
链队列及实现
√
循环队列和链队列的比较
√
队列的应用举例
√
教学过程
课程引入：
通过复习线性表和栈的插入、删除操作引出栈
5分钟
1．给出队列的定义，通过实例说明队列的操作特性
2．如何存储？
引出队列的顺序存储和链接存储
3．假溢出问题？
改造顺序表，得出循环队列的存储方法
4．如何判断队空和队满？
分析各种解决方案
5．如何改造单链表实现队列的链接存储
6．链式队列的出队算法需注意边界情况（判断队空）
7．引导学生比较循环队列和链式队列
8．队列问题应用举例
10分钟
5分钟
25分钟
15分钟
10分钟
15分钟
5分钟
5分钟
课程总结：
队列的操作特性；队列的基本操作和队列的应用
5分钟
教学提示
1．队列是程序设计中常用的数据结构之一，熟练掌握对后续学习有益
2．根据
升级会员 