数据结构课程教案-20170330

《数据结构课程教案-20170330》由会员分享，可在线阅读，更多相关《数据结构课程教案-20170330（83页珍藏版）》请在金锄头文库上搜索。

1、安徽大学本科教学课程教案安徽大学本科教学课程教案课程代码：课程代码： ZJ36007 课程名称：课程名称： 数据结构数据结构 授课专业：授课专业： 计算机科学与技术计算机科学与技术 授课教师：授课教师： 邹邹 海海 职称职称/学位：学位： 副教授副教授/ 博士博士 开课时间：二开课时间：二一六一六至二至二一七一七 学年第学年第 二二 学期学期第第 1 次课程教学方案次课程教学方案周次周次1课时数课时数2教学教学 章节章节第一章、绪论 1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分析目标目标 要求要求（1）掌握数据、数据元素、数据对象、数据

2、结构、存储结构和数据类型等基本概念，特别是逻 辑结构与存储结构之间的关系；（2）了解抽象数据类型的定义、表示和实现方法；（3）理解 算法的基本要素及含义；（4）掌握算法的时间复杂度和空间复杂度分析。重点重点 难点难点（1）数据结构包含的逻辑结构、存储结构和运算三方面的相互关系；（2）各种逻辑结构即线 性结构、树形结构和图形结构之间的差别；（3）数据结构和数据类型的差别和联系；（4）算 法的时间复杂度和空间复杂度分析。教学教学 方式方式 课堂讲授 小组活动 实验演示 难点答疑 提问 作业讲评 实践教学 考试测验 其他活动 媒体媒体 资源资源 文字教材 电子教案 录像材料 录音材料 直播课堂 CA

3、I 课件 IP 课件 其他资源： 课后课后 作业作业（1）数据的逻辑结构和存储结构有什么不同？（2）数据类型和抽象数据类型有什么不同？ （3）算法和程序有什么不同？（4）为什么要进行算法的时间复杂度分析？板板 书书 设设 计计1、什么是数据结构、什么是数据结构 指数据以及数据元素相互之间的联系。可以看作是相互之间存在着某种特定关系的数据元素 的集合。也可看成是带结构的数据元素的集合。逻辑结构的类型：线性结构、树型结构、图状结构、集合 2、基本概念与术语、基本概念与术语1）数据；2）数据元素；3）数据对象 3、抽象数据类型的表示与实现、抽象数据类型的表示与实现1）数据对象2）数据关系3）基本操作

4、 4、算法和算法分析、算法和算法分析 （1）算法：对特定问题求解步骤的一种描述。 （2）算法的 5 个重要特征：有穷性，确定性，可执行性，输入，输出。 （3）算法设计的目标： 1）正确性； 2）可读性； 3）健壮性； 4）效率与低存储量需求第第 1 次教学活动设计次教学活动设计教学教学 环节环节内容设计与手段内容设计与手段导导 入入 新新 课课从计算机科学课程体系设置情况，导入数据结构这门课程所处的地位：承上启下。 先修课程：计算机基础、高级语言程序设计、离散数学。 后期课程：操作系统、编译原理、数据库原理、软件工程等。 数据结构课程的主要研究内容。 学习和讲授的方法：演译法和归纳法。讲讲 授

5、授 内内 容容1、什么是数据结构、什么是数据结构 指数据以及数据元素相互之间的联系。可以看作是相互之间存在着某种特定关系的数据 元素的集合。也可看成是带结构的数据元素的集合。逻辑结构的类型：线性结构、树型结构、图状结构、集合 2、基本概念与术语、基本概念与术语 1）数据；2）数据元素；3）数据对象 4）逻辑结构与存储结构的区别与联系 3、抽象数据类型的表示与实现、抽象数据类型的表示与实现 1）数据对象 2）数据关系 3）基本操作 4、算法和算法分析、算法和算法分析归归 纳纳 总总 结结1、数据结构的定义，数据结构包含的逻辑结构、存储结构和运算三方面的相互关系。 2、各种逻辑结构即线性结构、树形

6、结构和图形结构之间的差别。 3、数据结构和数据类型的差别和联系。 4、算法的定义及其特性。 5、算法的时间复杂度和空间复杂度分析。第第 2 次课程教学方案次课程教学方案周次周次1课时数课时数2教学教学 章节章节第二章、线性表 2.1 线性表的基本概念 2.2 线性表的抽象类型定义 2.3 线性表的顺序表示与实现目标目标 要求要求（1）掌握线性表的逻辑特征；（2）掌握顺序表的类型定义；（3）熟练掌握顺序表基本操作的 实现算法及其时间复杂度分析。重点重点 难点难点（1）顺序表的类型定义；（2）线性表（逻辑结构）到顺序表（存储结构）的具体映射方式； （3）顺序表基本操作的实现算法及其时间复杂度分析。

7、教学教学 方式方式 课堂讲授 小组活动 实验演示 难点答疑 提问 作业讲评 实践教学 考试测验 其他活动 媒体媒体 资源资源 文字教材 电子教案 录像材料 录音材料 直播课堂 CAI 课件 IP 课件 其他资源： 课后课后 作业作业（1）顺序存储结构下，线性表中数据关系是如何表示的？（2）设计一个算法，将一个顺序存 储的线性表实现逆转置？板板 书书 设设 计计1、线性表的基本概念、线性表的基本概念 线性表：n（n=0）个具有相同类型的数据元素所组成的有限序列。 线性表的特征：1）除了第一个元素之外，每个元素有唯一的前驱元素； 2）除了最后一个元素之外，每个元素有唯一的后继元素。 2、线性表的抽

8、象类型定义、线性表的抽象类型定义 1）数据对象： 2）数据关系： 3）基本操作： 3、线性表的顺序表示与实现（顺序表）、线性表的顺序表示与实现（顺序表） （1）顺序表的类型定义与表示（2）顺序表的主要特征：连续的存储单元；逻辑相邻则物理相邻。 （3）基本操作的实现 1）初始化操作： 2）插入操作： 3）删除操作：length elem 线性表 a1,a2,ai,an 直接映射 a1 a2 ai an n 顺序表 0 1 i-1 n-1 MaxSize-1MaxSize listsize 第第 2 次教学活动设计次教学活动设计教学教学 环节环节内容设计与手段内容设计与手段导导 入入 新新 课课由

9、前一讲的数据的逻辑结构分类：线性结构、树型结构、图状结构、集合。 导入本章所要讲述的主要内容：线性结构 首先讨论线性表的主要逻辑特征。 其次，引导学生思考，这种逻辑结构在计算机中如何来表示、存储及其操作？讲讲 授授 内内 容容1、线性表的基本概念、线性表的基本概念 线性表：n（n=0）个具有相同类型的数据元素所组成的有限序列。 线性表的特征：1）除了第一个元素之外，每个元素有唯一的前驱元素； 2）除了最后一个元素之外，每个元素有唯一的后继元素。 2、线性表的抽象类型定义、线性表的抽象类型定义 1）数据对象： 2）数据关系： 3）基本操作： 3、线性表的顺序表示与实现（顺序表）、线性表的顺序表示

10、与实现（顺序表） （1）顺序表的类型定义 （2）顺序表的主要特征：连续的存储单元；逻辑相邻则物理相邻。 （3）基本操作的实现：1）初始化操作；2）插入操作；3）删除操作等。归归 纳纳 总总 结结1、顺序表的主要特征：采用一组地址连续的存储单元依次的存储从表头到表尾的元素， 逻辑上相邻的两个元素其物理上也相邻。 2、顺序表的类型定义： 1）*elem：一组地址连续的存储单元； 2）length：线性表的长度； 3）listsize; 线性表当前分配的存储容量 3、顺序表中其插入和删除操作，主要借助数据元素的移动来实现。对于插入操作，最好 情况下，当 i=n+1 时，移动次数为 0，最坏情况下，当

11、 i=1 时，需要移动 n 次，平均移动次 数为 n/2。对于删除操作，最好情况下，当 i=n 时，移动次数为 0，最坏情况下，当 i=1 时， 需要移动 n-1 次，平均移动次数为（n-1）/2。第第 3 次课程教学方案次课程教学方案周次周次2课时数课时数2教学教学 章节章节第二章、线性表 2.4 线性表的链式表示与实现 2.4.1 线性表的链式存储 2.4.2 单链表目标目标 要求要求（1）掌握单链表的结点结构（2）掌握头结点、头指针和首元结点的概念；（3）单链表中数据 关系的表示方法；（4）单链表的特点；（5）掌握线性表链式存储结构下基本操作的实现。重点重点 难点难点（1）单链表的类型定

12、义；（2）头指针与头结点的概念；（3）单链表存储结构下，线性表基本 操作的实现。教学教学 方式方式 课堂讲授 小组活动 实验演示 难点答疑 提问 作业讲评 实践教学 考试测验 其他活动 媒体媒体 资源资源 文字教材 电子教案 录像材料 录音材料 直播课堂 CAI 课件 IP 课件 其他资源： 课后课后 作业作业（1）链表与顺序表的区别？（2）采用带头结点的单链表与不带头结点的单链表相比，有哪些 优点？（3）设计算法，将单链表的尾结点修改为首元结点？板板 书书 设设 计计1、线性表的链式存储、线性表的链式存储 结点是构成链表的基本单位。 结点的结构：数据域和指针域。其中数据域存储元素本身的信息，

13、指针域用来存储数据元素 之间的逻辑关系。 存储密度=结点数据本身占用的空间/结点占用的空间总量 由于每个结点带有指针域，导致存储密度降低。 2、单链表、单链表 （1）什么是单链表 由于顺序表中的每个元素至多只有一个前驱元素和一个后继元素，即数据元素之间是一对一 的逻辑关系，所以当进行链式存储时，一种最简单也最常用的方法是:在每个节点中除包含有数 据域外，只设置一个指针域，用以指向其后继节点，这样构成的链接表称为线性单向链接表， 简称单链表。（2）头结点与头指针：对于一个单链表头结点不是必需的，但头指针是必需的。 带头结点的单链表与不带头结点的单链表，一般情况下，指带头结点。 （3）单链表的类型

14、定义 （4）单链表的基本操作实现开始 节点 终端节点 头节点 a1 an a2 L 线性表 a1,a2,ai,an 映射 第第 3 次教学活动设计次教学活动设计教学教学 环节环节内容设计与手段内容设计与手段导导 入入 新新 课课针对上一讲的线性表的顺序存储，引导学生总结顺序存储的优点：结构简单，易于理解； 方便随机访问表中的每个元素；不需要再为表示元素间的逻辑关系而增加额外的存储空间 等。 指出顺序表的缺点： （1）顺序表的存储空间不易扩充； （2）顺序表易造成存储空间的利用率低，且不利于分散的存储单元的使用； （3）顺序表在插入和删除操作时，需要大量的移动数据元素。 针对顺序表的上述缺点，导

15、入线性表的另外一种存储结构链式存储结构。讲讲 授授 内内 容容1、线性表的链式存储、线性表的链式存储 采用随机的存储单元，并利用指针域来存储数据元素之间的逻辑关系。 注意与顺序表的主要区别。 2、单链表、单链表 （1）什么是单链表 由于顺序表中的每个元素至多只有一个前驱元素和一个后继元素，即数据元素之间是一 对一的逻辑关系，所以当进行链式存储时，一种最简单也最常用的方法是:在每个节点中除 包含有数据域外，只设置一个指针域，用以指向其后继节点，这样构成的链接表称为线性 单向链接表，简称单链表。 （2）头结点与头指针：对于一个单链表头结点不是必需的，但头指针是必需的。 带头结点的单链表与不带头结点的单链表，一般情况下，指带头结点。 （3）单链表的类型定义 （4）单链表的基本操作实现归归 纳纳 总总 结结1、与顺序表不同，链式存储结构采用随机的存储单元来存储线性表的元素，需要额外的存 储空间（指针域）来表示数据元素间的线性关系； 2、单链