数据结构教案课程.docx

数据结构教案课程.docx

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

数据结构教案课程

2015至2016学年第二学期

数据结构课程

教

案

课程编码：

1261D03

总学时／周学时：

80/5

开课时间：

2016年2月24日第1周至第16周

授课年级、专业、班级：

15级网工程2班

使用教材严蔚敏.数据结构（C语言版）[M]北京：

清华大学出版社，2011.

系别/教研室：

信息工程学院/物联网工程

授课教师：

刘波

教学目标：

《数据结构》是物联网工程专业的一门专业必修课。

用计算机解决任何问题都需要进行数据表示和数据处理，而数据表示和数据处理正是《数据结构》要研究的内容。

主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。

通过本课程教学，使学生了解数据结构的基本概念，理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，掌握算法描述及算法的评价标准，熟悉在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会，旨在培养学生基本的、良好的程序设计技能，编制高效可靠的程序，并为学生日后学习操作系统和数据库等后续课程奠定基础。

教学要求:

本课程主要是以抽象数据类型的观点来组织和讲解线性表、栈、队列、树、二叉树、图等各种主要的数学模型并定义为相应的抽象数据类型，给出各种物理表示法和有关算法，关于数据处理技术介绍几种主要的排序和查找算法。

学生通过学习该课程后主要应掌握以下内容：

1．了解数据结构及有关的基本概念；

2．了解各种抽象数据类型的性质；

3．掌握各种抽象数据类型的实现和基本算法；

4．对算法的时间和空间复杂性有一定的分析能力；

5．能够选择适当的数据结构和存储结构以及设计有效的算法，解决实际问题；

6．掌握数据结构在排序和查找等常用算法中的应用。

教学重点：

抽象数据类型、顺序表、单链表、循环链表、栈、队列、数组、特殊矩阵、树和二叉树、最小生成树、拓扑排序、查找、内部排序

教学难点：

单链表、栈、循环队列、特殊矩阵、二叉树、关键路径、最短路径

教学方法与手段：

1．理论部分以讲授法为主，结合讨论及课堂练习实现教学目的。

2．传统教学手段与多媒体等现化手段相结合。

3．重视实验教学，要求学生利用一切可利用的时间和机会去实验室，实现并验证书本上的各种算法，达到真正实现教学目的。

考核与成绩评定方式：

本课程为考试科目，课程结束后采用闭卷考试。

考核总成绩中，平时成绩占30%（出勤占10%，实验占10%，书面作业占10%），期末考试占70%；考核范围为教学大纲规定的基本要求教学内容。

教材与主要参考书目：

1．教材

严蔚敏、吴伟民.数据结构（C语言版）[M]北京：

清华大学出版社，2011.

2．主要参考书目

严蔚敏、李冬梅、吴伟民，《数据结构》（C语言版）[M]北京：

人民邮电出版社，2011.

周次

授课章节及主要内容

实践教学环节内容

实验或课程设计等

学时

作业

主要

参考书目

1

1.1~1.4数据结构基本概念和术语及ADT，算法和算法分析2.1~2.2线性表的定义，顺序实现

4

2

2.3链式实现；2.4一元多项式相加

4

3

3.1~3.2栈的定义和应用

4

4

3.3栈与递归3.4队列

4

5

4.1~4.4串的定义和实现模式匹配，串的应用；

5.1~5.2数组的定义和实现

复习C语言的基本操作：

函数实现

6

6

5.3~5.5矩阵的压缩存储，广义表；6.1~6.2树和二叉树的定义，二叉树的性质

顺序表的操作

6

7

6.2~6.3二叉树存储，遍历和线索二叉树；6.4树和森林

单链表的操作

6

8

6.6赫夫曼树和赫夫曼编码

单链表的操作

6

9

7.1~7.2图的定义、存储；

7.3图的遍历

栈的应用：

括号匹配

6

10

7.4图的连通性；7.5拓扑排序、关键路径

队列的应用：

模拟病人看病

6

11

7.6最短路径；

9.1静态查找表

二叉树的遍历及应用

6

12

9.2动态查找表；9.3哈希表

二叉树的遍历及应用

6

13

10.1~10.4插入、希尔、快速排序

图的遍历

6

14

10.4~10.7选择、归并、基数排序，各种排序的比较

图的遍历

6

15

查找算法设计与实现

2

16

排序算法设计与实现

2

17

18

19

20

第一讲：

绪论

（一）

周次：

第1周，第1次

授课章节

第1章绪论1.1~1.4

任课教师

严小燕

教学方法

与手段

多媒体教学与板书相结合

课时安排

2

教学目的与要求

1．了解数据结构的发展及所处的地位

2．深刻理解数据结构的基本概念和术语

3．了解抽象数据类型的定义、表示和实现方法

4．掌握算法描述及算法的评价标准

5．理解算法五个要素的确切含义

6．掌握计算语句频度和估算算法时间复杂度的方法

教学内容

1．什么是数据结构

2．基本概念和术语

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

4．算法设计的要求基本概念和术语

5．算法效率的度量

6．算法的存储空间需求

7．第1章总结与复习及例题讲解

教学重点

数据结构的概念和术语

抽象数据类型的表示与实现

算法的五个要素

计算语句频度和估算算法时间复杂度

教学难点

数据结构的意义及数据结构的基本内容

数据结构及数据、数据元素等相关概念

算法描述的方法

算法时间复杂度的计算

作业布置

课堂练习

使用教材和

主要参考书

教材：

严蔚敏.数据结构.清华大学出版社,2011

参考书：

严蔚敏、李冬梅.数据结构（C语言版）人民邮电出版社，2011.

备注

授课的详细内容参见讲稿

第二讲：

线性表

（一）

周次：

第1周，第2次

授课章节

第2章线性表2.1~2.2

任课教师

严小燕

教学方法

与手段

多媒体教学与板书相结合

课时安排

2

教学目的与要求

1．理解线性表的概念、存储结构

2．深刻理解线性表的顺序存储结构的特点、类型描述，熟练掌握插入、删除、查找操作的算法实现

教学内容

1．线性表的类型定义

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

教学重点

线性表的定义及逻辑上的特点

顺序表上插入、删除和定位运算的实现

教学难点

线性表与线性结构的联系与区别

线性表的顺序存储结构及其运算

作业布置

课堂练习

使用教材和

主要参考书

教材：

严蔚敏.数据结构.清华大学出版社,2011

参考书：

严蔚敏、李冬梅.数据结构（C语言版）人民邮电出版社，2011.

备注

授课的详细内容参见讲稿

第三讲：

线性表

（二）

周次：

第2周，第1次

授课章节

第2章线性表2.3

任课教师

严小燕

教学方法

与手段

多媒体教学与板书相结合

课时安排

2

教学目的与要求

熟练掌握线性表的链式存储结构的特点、类型描述，插入、删除、查找操作的算法实现

教学内容

线性表的链式表示和实现——单链表

教学重点

单链表的结构特点及类型说明

头指针和头结点的作用及区别和指针操作

插入、删除、查找运算在单链表上的实现

教学难点

头结点在链表中的作用和指针的操作

单链表存储结构定义，插入、删除运算中的指针操作顺序

作业布置

课堂练习

使用教材和

主要参考书

教材：

严蔚敏.数据结构.清华大学出版社,2011

参考书：

严蔚敏、李冬梅.数据结构（C语言版）人民邮电出版社，2011.

备注

授课的详细内容参见讲稿

第四讲：

线性表（三）

周次：

第2周，第2次

授课章节

第2章线性表2.3

任课教师

严小燕

教学方法

与手段

多媒体教学与板书相结合

课时安排

2

教学目的与要求

掌握循环链表、双向链表及其基本操作的算法

教学内容

1．线性表的链式表示和实现——循环链表

2．线性表的链式表示和实现——双向链表

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

教学重点

循环链表插入与删除运算的实现

双向链表的结构特点及其插入与删除运算的实现

教学难点

循环链表、双向链表上指针的操作顺序及其相关运算

作业布置

课堂练习

使用教材和

主要参考书

教材：

严蔚敏.数据结构.清华大学出版社,2011

参考书：

严蔚敏、李冬梅.数据结构（C语言版）人民邮电出版社，2011.

备注

授课的详细内容参见讲稿

第五讲：

线性表（四）

周次：

第3周，第1次

授课章节

第2章线性表2.3

任课教师

严小燕

教学方法

与手段

多媒体教学与板书相结合

课时安排

2

教学目的与要求

第2章总结与复习及习题讲解

教学内容

1．线性表的链式表示和实现——循环链表

2．线性表的链式表示和实现——双向链表

教学重点

线性表各存储结构定义，插入、删除等运算的应用

教学难点

线性表各存储结构定义，插入、删除等运算的应用

作业布置

课堂练习

使用教材和

主要参考书

教材：

严蔚敏.数据结构.清华大学出版社,2011

参考书：

严蔚敏、李冬梅.数据结构（C语言版）人民邮电出版社，2011.

备注

授课的详细内容参见讲稿

第六讲：

栈和队列

（一）

周次：

第3周，第2次

授课章节

第3章栈和队列3.1~3.2

任课教师

严小燕

教学方法

与手段

多媒体教学与板书相结合

课时安排

2

教学目的与要求

1．理解栈的概念、逻辑特点及存储结构

2．熟练掌握顺序存储和链式存储两种结构下的进栈、出栈的算法

教学内容

1．栈的定义

2．栈的应用举例（数制转换，括号匹配）

教学重点

栈的顺序存储结构

进栈、出栈等运算在顺序栈上的实现

教学难点

顺序栈基本运算的实现

顺序栈的溢出判断条件

作业布置

课堂练习

使用教材和

主要参考书

教材：

严蔚敏.数据结构.清华大学出版社,2011

参考书：

严蔚敏、李冬梅.数据结构（C语言版）人民邮电出版社，2011.

备注

授课的详细内容参见讲稿

第七讲：

栈和队列

（二）

周次：

第4周，第1次

授课章节

第3章栈和队列3.2，3.3

任课教师

严小燕

教学方法

与手段

多媒体教学与板书相结合

课时安排

2

教学目的与要求

掌握利用栈实现表达式求值的算法；

理解递归算法执行过程中栈的状态变化过程，了解将递归程序转换为非递归程序的方法。

教学内容

1.栈的应用举例，如迷宫求解和表达式求值。

2.栈与递归的实现，递归程序转换为非递归程序的方法。

教学重点

递归算法执行过程中栈的状态变化过程

教学难点

递归算法执行过程中栈的状态变化过程

作业布置

课堂练习

使用教材和

主要参考书

教材：

严蔚敏.数据结构.清华大学出版社,2011

参考书：

严蔚敏、李冬梅.数据结构（C语言版）人民邮电出版社，2011.

备注

授课的详细内容参见讲稿

第八讲：

栈和队列（三）

周次：

第4周，第2次

授课章节

第3章栈和队列3.4

任课教师

严小燕

教学方法

与手段

多媒体教学与板书相结合

课时安排

2

教学目的与要求

1．理解队列的概念、存储结构

2．熟练掌握顺序存储和链式存储两种结构下的入队、出队的算法

教学内容

1．队列的定义

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

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

4．第3章总结与复习及例题讲解

教学重点

队列的定义及逻辑特点

入队、出队等基本运算在顺序、链式队列上的实现

教学难点

循环队列的队空、队满判断条件；循环队列上的插入、删除操作

作业布置

课堂练习

使用教材和

主要参考书

教材：

严蔚敏.数据结构.清华大学出版社,2011

参考书：

严蔚敏、李冬梅.数据结构（C语言版）人民邮电出版社，2011.

备注

授课的详细内容参见讲稿

第九讲：

串

（一）

周次：

第5周，第1次

授课章节

第4章串

任课教师

严小燕

教学方法

与手段

多媒体教学与板书相结合

课时安排

2

教学目的与要求

1．掌握串的定义、存储方式和常用的串运算

2．熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法

3．了解串的堆存储结构及块链存储结构

4.掌握串的模式匹配算法的基本算法和改进算法

教学内容

1．串类型的定义

2．串的表示和实现

3．串的模式匹配算法

4．串操作应用举例

5．第4章总结与复习及例题讲解

教学重点

串的两种存储方式

字符串的运算

串的模式匹配算法

教学难点

串的模式匹配算法

作业布置

课堂练习

使用教材和

主要参考书

教材：

严蔚敏.数据结构.清华大学出版社,2011

参考书：

严蔚敏、李冬梅.数据结构（C语言版）人民邮电出版社，2011.

备注

授课的详细内容参见讲稿

第十讲：

数组和广义表

（一）

周次：

第5周，第2次

授课章节

第5章数组和广义表5.1~5.2

任课教师

严小燕

教学方法

与手段

多媒体教学与板书相结合

课时安排

2

教学目的与要求

掌握多维数组的结构特点和在内存中的两种顺序存储方式

教学内容

1．数组的定义

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

教学重点

多维组的逻辑结构，两种顺序存储方式

计算给定元素在存储区中的地址

教学难点

数组的两种存储表示方法，数组在以行为主的存储结构中的地址计算方法

作业布置

课堂练习

使用教材和

主要参考书

教材：

严蔚敏.数据结构.清华大学出版社,2011

参考书：

严蔚敏、李冬梅.数据结构（C语言版）人民邮电出版社，2011.

备注

授课的详细内容参见讲稿

第十一讲：

数组和广义表

（二）

周次：

第6周，第1次

授课章节

第5章数组和广义表5.3~5.5

任课教师

严小燕

教学方法

与手段

多媒体教学与板书相结合

课时安排

2

教学目的与要求

1．掌握对特殊矩阵进行压缩存储时的下标变换公式；

2．领会稀疏矩阵的压缩方式和简单运算

3．了解广义表的定义、表示及存储

教学内容

1．矩阵的压缩存储

2．广义表的定义及存储结构

3．第5章总结与复习及例题讲解

教学重点

对称矩阵、三角矩阵的压缩存储方式

稀疏矩阵的三元组表表示方法

了解广义表的定义、表示及存储

教学难点

稀疏矩阵的压缩存储表示下的运算的实现

稀疏矩阵的三类压缩存储方法的特点和适用范围，以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法

广义表的结构特点及其存储表示方法

作业布置

课堂练习

使用教材和

主要参考书

教材：

严蔚敏.数据结构.清华大学出版社,2011

参考书：

严蔚敏、李冬梅.数据结构（C语言版）人民邮电出版社，2011.

备注

授课的详细内容参见讲稿

第十二讲：

树和二叉树

（一）

周次：

第6周，第2次

授课章节

第6章树和二叉树6.1~6.2

任课教师

严小燕

教学方法

与手段

多媒体教学与板书相结合

课时安排

2

教学目的与要求

1．理解树的定义和基本术语

2．深刻理解二叉树的定义、性质及其存储方法

3．熟练掌握二叉树的顺序存储方式、结点结构和类型定义

教学内容

1．树的定义和基本术语

2．二叉树的定义和性质

教学重点

二叉树的定义、性质、逻辑特点及五种基本形态、基本运算

教学难点

二叉树的递归定义

作业布置

课堂练习

使用教材和

主要参考书

教材：

严蔚敏.数据结构.清华大学出版社,2011

参考书：

严蔚敏、李冬梅.数据结构（C语言版）人民邮电出版社，2011.

备注

授课的详细内容参见讲稿

第十三讲：

树和二叉树

（二）

周次：

第7周，第1次

授课章节

第6章树和二叉树6.2~6.3

任课教师

严小燕

教学方法

与手段

多媒体教学与板书相结合

课时安排

2

教学目的与要求

1．熟练掌握二叉树的链式存储方式、结点结构和类型定义

2．理解并掌握二叉树的三种遍历算法

教学内容

1．二叉树的链式存储结构

2．遍历二叉树

教学重点

二叉树的链式存储结构及组织方式

二叉树的三种遍历方法及其算法

教学难点

二叉树链式存储结构的组织方式

三种遍历的主要区别

作业布置

课堂练习

使用教材和

主要参考书

教材：

严蔚敏.数据结构.清华大学出版社,2011

参考书：

严蔚敏、李冬梅.数据结构（C语言版）人民邮电出版社，2011.

备注

授课的详细内容参见讲稿

第十四讲：

树和二叉树（三）

周次：

第7周，第2次

授课章节

第6章树和二叉树6.3~6.4

任课教师

严小燕

教学方法

与手段

多媒体教学与板书相结合

课时安排

2

教学目的与要求

1．灵活运用二叉树的遍历方法解决相关的应用问题

2．理解并掌握二叉树的线索化方法

3．熟练掌握森林与二叉树间的相互转换

4．了解树的简单应用

教学内容

1．二叉树的遍历方法的应用

2．线索二叉树

3．树的存储结构

4．森林与二叉树的转换

教学重点

以遍历为基础在二叉树上实现的几种运算

中序线索化

森林与二叉树的转换

教学难点

二叉树上的复杂运算

森林与二叉树的转换

作业布置

课堂练习

使用教材和

主要参考书

教材：

严蔚敏.数据结构.清华大学出版社,2011

参考书：

严蔚敏、李冬梅.数据结构（C语言版）人民邮电出版社，2011.

备注

授课的详细内容参见讲稿

第十五讲：

树和二叉树（四）

周次：

第8周，第1次

授课章节

第6章树和二叉树6.6

任课教师

严小燕

教学方法

与手段

多媒体教学与板书相结合

课时安排

2

教学目的与要求

掌握哈夫曼树的构造方法

教学内容

1．赫夫曼树的定义

2．赫夫曼树的构造

教学重点

哈夫曼树的构造方法

教学难点

哈夫曼树的构造方法

作业布置

课堂练习

使用教材和

主要参考书

教材：

严蔚敏.数据结构.清华大学出版社,2011

参考书：

严蔚敏、李冬梅.数据结构（C语言版）人民邮电出版社，2011.

备注

授课的详细内容参见讲稿

第十六讲：

树和二叉树（五）

周次：

第8周，第2次

授课章节

第6章树和二叉树6.6

任课教师

严小燕

教学方法

与手段

多媒体教学与板书相结合

课时安排

2

教学目的与要求

掌握哈夫曼编码算法

教学内容

1．赫夫曼树的应用

2．第6章总结与复习及例题讲解

教学重点

哈夫曼编码算法

教学难点

哈夫曼编码算法

作业布置

课堂练习

使用教材和

主要参考书

教材：

严蔚敏.数据结构.清华大学出版社,2011

参考书：

严蔚敏、李冬梅.数据结构（C语言版）人民邮电出版社，2011.

备注

授课的详细内容参见讲稿

第十七讲：

图

（一）

周次：

第9周，第1次

授课章节

第7章图7.1~7.2

任课教师

严小燕

教学方法

与手段

多媒体教学与板书相结合

课时安排

2

教学目的与要求

1．掌握图的基本概念及术语

2．掌握图的两种存储结构（邻接矩阵和邻接表）的表示方法

教学内容

1．图的定义和术语

2．图的存储结构

教学重点

理解图的定义、术语及其含义

各种图的邻接矩阵表示法及其类型说明

教学难点

正确理解与区别图的常用术语

区别图的两种存储结构的不同点及其应用场合

作业布置

课堂练习

使用教材和

主要参考书

教材：

严蔚敏.数据结构.清华大学出版社,2011

参考书：

严蔚敏、李冬梅.数据结构（C语言版）人民邮电出版社，2011.

备注

授课的详细内容参见讲稿

第十八讲：

图

（二）

周次：

第9周，第2次

授课章节

第7章图7.2~7.3

任课教师

严小燕

教学方法

与手段

多媒体教学与板书相结合

课时安排

2

教学目的与要求

掌握图的遍历（深度优先搜索遍历和广度优先搜索遍历）算法

教学内容

1．图的存储结构

2．图的遍历

教学重点

图的按深度优先搜索遍历方法和按广度优先搜索遍历方法

教学难点

图的按深度优先搜索遍历方法和按广度优先搜索遍历方法

作业布置

课堂练习

使用教材和

主要参考书

教材：

严蔚敏.数据结构.清华大学出版社,2011

参考书：

严蔚敏、李冬梅.数据结构（C语言版）人民邮电出版社，2011.

备注

授课的详细内容参见讲稿

第十九讲：

图（三）

周次：

第10周，第1次

授课章节

第7章图7.4

任课教师

严小燕

教学方法

与手段

多媒体教学与板书相结合

课时安排

2

教学目的与要求

1．理解连通分量、生成树和强连通分量的含义

2．掌握最小生成树的构造

教学内容

1．无向图的连通分量和生成树

2．有向图的强连通分量

3．最小生成树

教学重点

生成树和最小生成树的概念

由Prim算法思想构造最小生成树

教学难点

由Prim算法思想构造最小生成树

作业布置

课堂练习

使用教材和

主要参考书

教材：

严蔚敏.数据结构.清华大学出版社,2011

参考书：

严蔚敏、李冬梅.数据结构（C语言版）人民邮电出版社，2011.

备注

授课的详细内容参见讲稿

第二十讲：

图（四）

周次：

第10周，第2次

授课章节

第7章图7.5

任课教师

严小燕

教学方法

与手段

多媒体教学与板书相结合

课时安排

2

教学目的与要求

1．掌握拓扑排序的算法

2．掌握关键路径的算法

教学内容

1．拓扑排序

2．关键路径

教学重点

拓扑排序、关键路径的算法思想

教学难点

关键路径的算法思想

作业布置

课堂练习

使用教材和

主要参考书

教材：

严蔚敏.数据结构.清华大学出版社,2011

参考书：

严蔚敏、李冬梅.数据结构（C语言版）人民邮电出版社，2011.

备注

授课的详细内容参见讲稿

第二十一讲：

图（五）

周次：

第11周，第1次

授课章节

第7章图7.6

任课教师

严小燕

教学方法

与手段

多媒体教学与板书相结合

课时安排

2

教学目的与要求

掌握最短路径的算法

教学内容

1．从某个源点到其余各顶点的最短路径

2．每一对顶点之间的最短路径

3．第7章总结与复习及例题讲解最短路径

教学重点

最短路径的算法思想

教学难点

最短路径的算法思想

作业布置

课堂练习

使用教材和

主要参考书

教材：

严蔚敏.数据结构.清华大学出版社,2011

参考书：

严蔚敏、李冬梅.数据结构（C语言版）人民邮电出版社，2011.

备注

授课的详细内容参见讲稿

第二十二讲：

查找

（一）

周次：

第11周，第2次

授课章节

第9章