数据结构新版教案数据结构教程Java语言描述李春葆清华大学出版社.docx

数据结构新版教案数据结构教程Java语言描述李春葆清华大学出版社.docx

《数据结构新版教案数据结构教程Java语言描述李春葆清华大学出版社.docx》由会员分享，可在线阅读，更多相关《数据结构新版教案数据结构教程Java语言描述李春葆清华大学出版社.docx（29页珍藏版）》请在冰点文库上搜索。

数据结构新版教案数据结构教程Java语言描述李春葆清华大学出版社

武汉大学教案

2017—2018学年第一学期

课程名称数据结构

授课教师李春葆

教师所在院系计算机学院

授课对象2016级卓越工程师班

总学时、学分72学时、4学分

武汉大学

第1章-绪论教案

一、教学目的（黑体五号）

通过本章的学习，学生应达到如下基本要求：

1、掌握数据结构的基本概念。

2、掌握数据逻辑结构和存储结构的映射关系。

3、掌握数据类型和数据结构的区别和联系。

4、掌握利用抽象数据类型表述求解问题的方法。

5、掌握算法的特性和采用C/C++语言描述算法的方法。

6、掌握算法设计目标和分析方法，包括时间复杂度和空间复杂度分析。

7、掌握从数据结构的角度设计好算法的过程。

二、教学内容（黑体五号）

1、数据结构的概念。

2、数据逻辑结构类型和存储结构类型。

3、数据结构和数据类型的关系。

4、抽象数据类型的作用和描述方法。

5、算法的概念，算法的特性，算法的描述方法。

6、算法的时间复杂度和空间复杂度分析。

7、算法设计的基本过程。

三、教学重点与难点（黑体五号）

1、用抽象数据类型描述求解问题。

2、算法特性，理解算法和程序的异同。

3、算法的时间复杂度分析，特别是递归算法的时间复杂度分析。

4、算法的空间复杂度分析，特别是递归算法的空间复杂度分析。

5、设计“好”算法的过程。

四、教学方法（黑体五号）

讲授、讨论、提问

五、教学时间分配（黑体五号）

本章共4学时，安排如下：

1、教学内容1～4：

2学时。

2、教学内容5～7：

2学时。

六、教具准备（黑体五号）

教学PPT

七、拟向学生提问的问题（黑体五号）

1、学习数据结构课程有什么体会？

2、如何进行从数据设计到应用程序的设计。

八、复习题（黑体五号）

对应第1章的测验题和作业题，见附件（含参考答案），共20题。

九、选用教材（名称、作者、出版社及出版时间）

[1]数据结构教程（第5版），清华大学出版社，李春葆等2017。

[2]数据结构教程（第5版）学习指导，清华大学出版社，李春葆等2017。

十、参考书目（名称、作者、出版社及出版时间）

[1]数据结构（C语言），清华大学出版社，严蔚敏，2002。

[2].数据结构基础，Horowitz,E.等著（朱仲涛译），清华大学出版社，2009

[3].算法导论，Cormen,T.H.等著（潘金贵等译），机械工业出版社，2006

第2章-线性表教案

一、教学目的（黑体五号）

通过本章的学习，学生应达到如下基本要求：

1、掌握线性表的逻辑结构特点，线性表抽象数据类型的描述方法。

2、掌握线性表的两类存储结构设计方法以及各自的优缺点。

3、掌握顺序表算法设计方法。

4、掌握单链表、双链表和循环链表算法设计方法。

5、利用线性表求解复杂的应用。

6、掌握有序表的特点和有序表的归并算法设计方法。

二、教学内容（黑体五号）

1、线性表的概念。

2、线性表抽象数据类型的描述方法。

3、线性表的顺序存储结构。

4、顺序表的算法设计方法。

5、线性表的链式存储结构。

6、单链表的算法设计方法。

7、双链表的算法设计方法。

8、循环链表的算法设计方法。

9、利用线性表求解复杂问题的方法。

10、有序表的特点和归并算法设计。

三、教学重点与难点（黑体五号）

1、线性表的顺序存储结构和链式存储结构的优缺点。

2、顺序表的插入和删除操作过程及其实现。

3、单链表的查找、插入和删除操作过程及其实现。

4、双链表的查找、插入和删除操作过程及其实现。

5、循环链表的查找、插入和删除操作过程及其实现。

6、有序表归并算法的思路及其实现算法，该算法的时间复杂度分析。

7、利用线性表求解复杂的应用问题。

四、教学方法（黑体五号）

讲授、讨论、提问

五、教学时间分配（黑体五号）

本章共10学时，安排如下：

1、教学内容1～3：

2学时

2、教学内容4～5：

2学时

3、教学内容6：

2学时

4、教学内容7～8：

2学时

5、教学内容9～10：

2学时

六、教具准备（黑体五号）

教学PPT

七、拟向学生提问的问题（黑体五号）

1、顺序表和链表的异同？

2、顺序表算法设计有哪些基本方法？

3、单链表算法设计有哪些基本方法？

4、如何利用线性表设计较复杂的应用程序？

八、复习题（黑体五号）

对应第2章的测验题和作业题，见附件（含参考答案），共40题。

九、选用教材（名称、作者、出版社及出版时间）

[1]数据结构教程（第5版），清华大学出版社，李春葆等2017。

[2]数据结构教程（第5版）学习指导，清华大学出版社，李春葆等2017。

十、参考书目（名称、作者、出版社及出版时间）

[1]数据结构（C语言），清华大学出版社，严蔚敏，2002。

[2].数据结构基础，Horowitz,E.等著（朱仲涛译），清华大学出版社，2009

[3].算法导论，Cormen,T.H.等著（潘金贵等译），机械工业出版社，2006

第3章-栈和队列教案

一、教学目的（黑体五号）

通过本章的学习，学生应达到如下基本要求：

1、掌握栈的逻辑结构特性，栈抽象数据类型的描述方法。

2、掌握栈的先进后出特点。

3、掌握栈基本运算在两类存储结构下的实现算法。

4、掌握栈在实际求解问题中的应用方法。

5、掌握队列的逻辑结构特性，队列抽象数据类型的描述方法。

6、掌握队列的先进后出特点。

7、掌握队列基本运算在两类存储结构下的实现算法。

8、掌握队列在实际求解问题中的应用方法。

二、教学内容（黑体五号）

1、栈的逻辑结构特性。

2、栈抽象数据类型的描述方法。

3、顺序栈的算法设计方法。

4、链栈的算法设计方法。

5、栈在表达式求值中的应用。

6、栈在求迷宫问题中的应用。

7、队列的逻辑结构特性。

8、队列抽象数据类型的描述方法。

9、顺序队的算法设计方法。

10、链队的算法设计方法。

11、队列在求迷宫问题中的应用。

三、教学重点与难点（黑体五号）

1、栈、队列和线性表的异同。

2、顺序栈的基本运算算法设计。

3、链栈的基本运算算法设计。

4、顺序队的基本运算算法设计。

5、循环队列和非循环队列的特点。

6、链队的基本运算算法设计。

7、利用栈/队列求解复杂的应用问题。

四、教学方法（黑体五号）

讲授、讨论、提问

五、教学时间分配（黑体五号）

本章共8学时，安排如下：

1、教学内容1～4：

2学时

2、教学内容5～6：

2学时

3、教学内容7～10：

2学时

4、教学内容11：

2学时

六、教具准备（黑体五号）

教学PPT

七、拟向学生提问的问题（黑体五号）

1、在何时使用栈，何时使用队列？

2、非循环队列为什么会出现假溢出？

3、栈和队列求解迷宫问题各有什么特点？

八、复习题（黑体五号）

对应第3章的测验题和作业题，见附件（含参考答案），共25题。

九、选用教材（名称、作者、出版社及出版时间）

[1]数据结构教程（第5版），清华大学出版社，李春葆等2017。

[2]数据结构教程（第5版）学习指导，清华大学出版社，李春葆等2017。

十、参考书目（名称、作者、出版社及出版时间）

[1]数据结构（C语言），清华大学出版社，严蔚敏，2002。

[2].数据结构基础，Horowitz,E.等著（朱仲涛译），清华大学出版社，2009

[3].算法导论，Cormen,T.H.等著（潘金贵等译），机械工业出版社，2006

第4章-串教案

一、教学目的（黑体五号）

通过本章的学习，学生应达到如下基本要求：

1、掌握串的逻辑结构特性和串抽象数据类型的描述方法。

2、掌握串的两类存储结构设计方法以及各自的优缺点。

3、掌握顺序串算法设计方法。

4、掌握链串算法设计方法。

5、掌握串的模式匹配算法设计方法。

二、教学内容（黑体五号）

1、串的概念。

2、串抽象数据类型的描述方法。

3、串的顺序存储结构及顺序串算法设计方法。

4、串的链式存储结构及链串算法设计方法。

5、串的模式匹配的概念。

6、串的简单模式匹配算法。

7、KMP算法及其提高串匹配效率的特点。

三、教学重点与难点（黑体五号）

1、串的顺序存储结构和链式存储结构的优缺点。

2、顺序串运算算法设计。

3、链串运算算法设计。

4、简单模式匹配算法设计。

5、KMP算法设计，KMP算法是如何提高串匹配效率的。

四、教学方法（黑体五号）

讲授、讨论、提问

五、教学时间分配（黑体五号）

本章共4学时，安排如下：

1、教学内容1～4：

2学时

2、教学内容5～7：

2学时

六、教具准备（黑体五号）

教学PPT

七、拟向学生提问的问题（黑体五号）

1、串的两种存储结构各有什么优缺点？

2、KMP算法是如何提高模式匹配效率的？

八、复习题（黑体五号）

对应第4章的测验题和作业题，见附件（含参考答案），共15题。

九、选用教材（名称、作者、出版社及出版时间）

[1]数据结构教程（第5版），清华大学出版社，李春葆等2017。

[2]数据结构教程（第5版）学习指导，清华大学出版社，李春葆等2017。

十、参考书目（名称、作者、出版社及出版时间）

[1]数据结构（C语言），清华大学出版社，严蔚敏，2002。

[2].数据结构基础，Horowitz,E.等著（朱仲涛译），清华大学出版社，2009

[3].算法导论，Cormen,T.H.等著（潘金贵等译），机械工业出版社，2006

第5章-递归教案

一、教学目的（黑体五号）

通过本章的学习，学生应达到如下基本要求：

1、掌握递归和递归模型的概念。

2、掌握递归算法的执行过程。

3、掌握递归算法的实现原理。

4、掌握递归算法设计的一般步骤。

5、基于递归数据结构的递归算法设计方法。

6、基于递归求解方法的递归算法设计方法。

二、教学内容（黑体五号）

1、递归的概念。

2、什么情况使用递归。

3、什么是递归模型。

4、递归算法的执行过程。

5、递归调用的实现原理。

6、递归算法设计的一般步骤。

7、基于递归数据结构的递归算法设计。

8、基于递归求解方法的递归算法设计。

三、教学重点与难点（黑体五号）

1、何时使用递归。

2、如何从递归角度提取求解问题的递归模型。

3、递归算法的执行过程。

4、递归算法的实现原理。

5、递归算法设计的一般步骤。

6、理解递归数据结构的特征。

7、利用递归思想求解复杂的应用问题。

四、教学方法（黑体五号）

讲授、讨论、提问

五、教学时间分配（黑体五号）

本章共4学时，安排如下：

1、教学内容1～5：

2学时

2、教学内容6～8：

2学时

六、教具准备（黑体五号）

教学PPT

七、拟向学生提问的问题（黑体五号）

1、举出我们实际生活中用到递归的两个示例？

2、递归算法设计的基本规律？

八、复习题（黑体五号）

对应第5章的测验题和作业题，见附件（含参考答案），共10题。

九、选用教材（名称、作者、出版社及出版时间）

[1]数据结构教程（第5版），清华大学出版社，李春葆等2017。

[2]数据结构教程（第5版）学习指导，清华大学出版社，李春葆等2017。

十、参考书目（名称、作者、出版社及出版时间）

[1]数据结构（C语言），清华大学出版社，严蔚敏，2002。

[2].数据结构基础，Horowitz,E.等著（朱仲涛译），清华大学出版社，2009

[3].算法导论，Cormen,T.H.等著（潘金贵等译），机械工业出版社，2006

第6章-数组和稀疏矩阵教案

一、教学目的（黑体五号）

通过本章的学习，学生应达到如下基本要求：

1、掌握数组的逻辑结构特性，数组抽象数据类型的描述方法。

2、掌握数组的顺序存储结构及其特点。

3、掌握对称矩阵、上三角矩阵、下三角矩阵和三对角矩阵的压缩存储。

4、掌握稀疏矩阵的特点。

5、掌握稀疏矩阵的两种压缩存储方法。

二、教学内容（黑体五号）

1、数组的逻辑结构特性。

2、数组的顺序存储结构及其特点。

3、对称矩阵、上三角矩阵、下三角矩阵和三对角矩阵的压缩存储。

4、稀疏矩阵的特点。

5、稀疏矩阵的三元组和十字链表存储结构。

三、教学重点与难点（黑体五号）

1、数组的顺序存储结构及其特点。

2、对称矩阵、上三角矩阵、下三角矩阵和三对角矩阵的压缩存储方法。

3、稀疏矩阵的三元组表示及其基本运算算法设计。

四、教学方法（黑体五号）

讲授、讨论、提问

五、教学时间分配（黑体五号）

本章共4学时，安排如下：

教学内容1～3：

2学时

教学内容4～5：

2学时

六、教具准备（黑体五号）

教学PPT

七、拟向学生提问的问题（黑体五号）

1、为什么所有的高级语言都提供数组类型？

2、为什么特殊矩阵和稀疏矩阵要采用压缩存储？

八、复习题（黑体五号）

对应第6章的测验题和作业题，见附件（含参考答案），共15题。

九、选用教材（名称、作者、出版社及出版时间）

[1]数据结构教程（第5版），清华大学出版社，李春葆等2017。

[2]数据结构教程（第5版）学习指导，清华大学出版社，李春葆等2017。

十、参考书目（名称、作者、出版社及出版时间）

[1]数据结构（C语言），清华大学出版社，严蔚敏，2002。

[2].数据结构基础，Horowitz,E.等著（朱仲涛译），清华大学出版社，2009

[3].算法导论，Cormen,T.H.等著（潘金贵等译），机械工业出版社，2006

第7章-树和二叉树教案

一、教学目的（黑体五号）

通过本章的学习，学生应达到如下基本要求：

1、掌握树的定义及其逻辑结构特性，数组抽象数据类型的描述方法。

2、掌握树的逻辑结构表示方法和树的性质。

3、掌握树的遍历方法和树的存储结构。

4、掌握树的算法设计。

5、掌握二叉树的定义及其性质。

6、掌握二叉树与树、森林之间的转换。

7、掌握二叉树的两种存储结构。

8、掌握二叉树的基本运算算法设计。

9、掌握二叉树的遍历过程、算法设计及其应用。

10、掌握二叉树的构造过程。

11、掌握线索二叉树的特点及其构造过程。

12、掌握哈夫曼树和哈夫曼编码的构造过程。

二、教学内容（黑体五号）

1、树的逻辑结构特性及树抽象数据类型的描述。

2、树的逻辑表示方法及树的基本术语。

3、树的性质。

4、树的遍历方法。

5、树的存储结构。

6、二叉树的递归定义和二叉树的性质。

7、完全二叉树和满二叉树的特点。

8、二叉树与树、森林之间的转换方法。

9、二叉树的两种存储结构及其特点。

10、二叉树的基本运算算法设计方法。

11、二叉树的遍历过程。

12、二叉树的先序、中序和后序遍历递归和非递归算法设计及其应用。

13、二叉树的层次遍历算法设计及其应用。

14、二叉树的构造过程。

15、线索二叉树的构造过程及其特点。

16、哈夫曼树和哈夫曼编码的构造过程及其特点。

三、教学重点与难点（黑体五号）

1、树的递归特点。

2、树的性质、树的遍历和树的存储结构。

3、二叉树与树、森林之间的转换方法。

4、二叉树的递归特点、二叉树的性质和二叉树的两种存储结构。

5、完全二叉树和满二叉树的特点。

6、二叉树的先序、中序和后序遍历递归和非递归算法设计。

7、二叉树层次遍历算法设计。

8、二叉树遍历算法的应用。

9、二叉树的构造过程。

10、线索二叉树的特点及其构造过程。

11、哈夫曼树的特点、哈夫曼树构造过程。

12、哈夫曼编码的特点、哈夫曼编码的构造过程。

13、灵活运用二叉树这种数据结构解决一些综合应用问题。

四、教学方法（黑体五号）

讲授、讨论、提问

五、教学时间分配（黑体五号）

本章共10学时，安排如下：

1、教学内容1～5：

2学时

2、教学内容6～8：

2学时

3、教学内容9～10：

2学时

4、教学内容11～13：

2学时

5、教学内容14～16：

2学时

六、教具准备（黑体五号）

教学PPT

七、拟向学生提问的问题（黑体五号）

1、树形结构有什么特点，举出我们实际生活中应用树的两个示例？

2、为什么树和二叉树是两种不同的树形结构？

3、为何要进行树和二叉树之间的转换？

4、如何应用递归方法设计二叉树算法？

5、哈夫曼树有何实际应用？

八、复习题（黑体五号）

对应第7章的测验题和作业题，见附件（含参考答案），共50题。

九、选用教材（名称、作者、出版社及出版时间）

[1]数据结构教程（第5版），清华大学出版社，李春葆等2017。

[2]数据结构教程（第5版）学习指导，清华大学出版社，李春葆等2017。

十、参考书目（名称、作者、出版社及出版时间）

[1]数据结构（C语言），清华大学出版社，严蔚敏，2002。

[2].数据结构基础，Horowitz,E.等著（朱仲涛译），清华大学出版社，2009

[3].算法导论，Cormen,T.H.等著（潘金贵等译），机械工业出版社，2006

第8章-图教案

一、教学目的（黑体五号）

通过本章的学习，学生应达到如下基本要求：

1、掌握图的定义及其逻辑结构特性，图抽象数据类型的描述方法。

2、掌握图的基本术语及其含义。

3、掌握图的邻接矩阵和邻接表两种主要的存储结构及其特点。

4、掌握图的深度优先和广度优先遍历算法。

5、掌握图遍历算法的应用。

6、掌握生成树和最小生成树的定义。

7、掌握求最小生成树的Prim和Kruskal算法。

8、掌握最短路径的概念和求最短路径的Dijkstra和Flody算法。

9、掌握拓扑排序过程。

10、掌握关键路径的定义及其构造过程。

二、教学内容（黑体五号）

1、图的定义及图抽象数据类型的描述方法。

2、图基本术语的定义及其含义。

3、图的邻接矩阵和邻接表两种存储结构。

4、基于图邻接矩阵和邻接表存储结构的基本算法设计。

5、图遍历的概念。

6、图的深度优先遍历算法及其在图搜索算法设计中的应用。

7、图的广度优先遍历算法及其在图搜索算法设计中的应用。

8、生成树、深度优先生成树和广度优先生成树的概念。

9、最小生成树的定义，求最小生成树的Prim和Kruskal算法。

10、求单源最短路径的Dijkstra算法。

11、求多源最短路径的Flody算法。

12、拓扑排序的意义及其算法设计。

13、AOE网的含义和关键路径的定义。

14、求关键路径的过程。

三、教学重点与难点（黑体五号）

1、图的特点。

2、图的概念，包括完全图、路径/简单路径、连通图/连通分量、强连通图/强连通分量等重要概念。

3、图的邻接矩阵和邻接表两种存储结构及其特点。

4、图的深度优先和广度优先遍历算法。

5、图的两种遍历算法在图搜索算法设计中的应用。

6、生成树和最小生成树的定义，求最小生成树的Prim和Kruskal算法

7、求单源最短路径的Dijkstra算法求多源最短路径的Flody算法

8、拓扑排序算法

9、求AOE网关键路径的过程

10、灵活运用图这种数据结构解决一些综合应用问题。

四、教学方法（黑体五号）

讲授、讨论、提问

五、教学时间分配（黑体五号）

本章共10学时，安排如下：

1、教学内容1～4：

2学时

2、教学内容5～7：

2学时

3、教学内容8～9：

2学时

4、教学内容10～11：

2学时

5、教学内容12～14：

2学时

六、教具准备（黑体五号）

教学PPT

七、拟向学生提问的问题（黑体五号）

1、图结构有什么特点，举出我们实际生活中应用图的两个示例？

2、图如何存储？

邻接矩阵和邻接表有什么特点？

3、最小生成树有什么实际应用？

4、如何应用最短路径算法求解实际问题？

5、Kruskal和Dijkstra算法如何体现出贪心的思想？

八、复习题（黑体五号）

对应第8章的测验题和作业题，见附件（含参考答案），共50题。

九、选用教材（名称、作者、出版社及出版时间）

[1]数据结构教程（第5版），清华大学出版社，李春葆等2017。

[2]数据结构教程（第5版）学习指导，清华大学出版社，李春葆等2017。

十、参考书目（名称、作者、出版社及出版时间）

[1]数据结构（C语言），清华大学出版社，严蔚敏，2002。

[2].数据结构基础，Horowitz,E.等著（朱仲涛译），清华大学出版社，2009

[3].算法导论，Cormen,T.H.等著（潘金贵等译），机械工业出版社，2006

第9章-查找教案

一、教学目的（黑体五号）

通过本章的学习，学生应达到如下基本要求：

1、掌握查找的概念。

2、掌握线性表的顺序查找和折半查找算法，索引存储结构和分块查找方法。

3、掌握二叉排序树的定义、查找和插入算法、删除过程。

4、掌握平衡二叉树的特点及其调整方法。

5、掌握B-树的定义和基本操作过程，B+的定义。

6、掌握哈希表的定义及其特点。

7、掌握哈希函数构造方法和解决冲突的方法。

8、掌握各种查找方法的性能分析。

二、教学内容（黑体五号）

1、查找的定义和查找的相关概念。

2、顺序查找算法及其性能分析。

3、折半查找算法及其性能分析。

4、索引存储结构和分块查找算法。

5、二叉排序树的定义、查找和插入算法、删除过程。

6、平衡二叉排序树的定义、查找性能分析和调整过程。

7、B-树的定义和基本操作过程B+的定义。

8、哈希表的定义及其特点。

9、哈希函数构造方法和解决冲突的方法。

三、教学重点与难点（黑体五号）

1、顺序查找算法及其性能分析。

2、折半查找算法及其性能分析。

3、索引存储结构和分块查找的特点。

4、二叉排序树的查找和插入算法设计，删除过程。

5、平衡二叉树的调整过程和性能分析。

6、B-树的查找、插入和删除过程。

7、哈希表的特点、哈希函数构造方法和解决冲突的方法。

8、各种查找方法的特点和性能对比分析。

四、教学方法（黑体五号）

讲授、讨论、提问

五、教学时间分配（黑体五号）

本章共6学时，安排如下：

1、教学内容1～4：

2学时

2、教学内容5～7：

2学时

3、教学内容8～9：

2学时

六、教具准备（黑体五号）

教学PPT

七、拟向学生提问的问题（黑体五号）

1、折半查找为何比顺序查找好，它利用了数据中的什么信息？

2、索引查找方法给我们什么启示？

3、为什么需要平衡二叉树？

4、在组织大型数据时为什么采用B-树、B+树？

5、哈希表为何既是一种查找方法，又是一种存储结构？

八、复习题（黑体五号）

对应第9章的测验题和作业题，见附件（含参考答案），共30题。

九、选用教材（名称、作者、出版社及出版时间）

[1]数据结构教程（第5版），清华大学出版社，李春葆等2017。

[2]数据结构教程（第5版）学习指导，清华大学出版社，李春葆等2017。

十、参考书目（名称、作者、出版社及出版时间）

[1]数据结构（C语言），清华大学出版社，严蔚敏，2002。

[2].数据结构基础，Horowitz,E.等著（朱仲涛译），清华大学出版社，2009

[3].算法导论，Cormen,T.H.等著（潘金贵等译），机械工业出版社，2006