数据结构教案第一章绪论

《数据结构教案第一章绪论》由会员分享，可在线阅读，更多相关《数据结构教案第一章绪论（4页珍藏版）》请在金锄头文库上搜索。

1、教学主题或章、教学主题或章、 节节课程导论 第一章 绪论(1.1 节、1.2 节)授课类型授课类型理论课 实验课 实习或课程设计 练习课 其他教学过程教学过程前面导论 10 分钟，新课 78 分钟，布置作业 2 分钟教学方式教学方式讲授 讨论 阅读 示范操作 练习 提问 其他教学资源教学资源多媒体课件 演示动画 相关软件 音像 其他教学目的及要求（分掌握、理解、了解三个层次）：教学目的及要求（分掌握、理解、了解三个层次）： 本次课程要求学生了解什么是数据结构、数据结构课程的特点、数据结构研究的内容是什么， 理解在解决问题过程中所涉及问题中数据之间的逻辑关系，掌握本课程所涉及到的基本名词、 术语

2、和概念，特别是数据的逻辑结构和存储结构之间的关系及性质。教学内容提要：教学内容提要： 第一部分第一部分 前面章节简要回顾前面章节简要回顾（约（约10分钟）分钟） 介绍数据结构课程的性质、特点、课程的整体框架介绍、本课程学习过程的说明、以及 最终的考核方法。理论课和实验课的要求、所需要的参考教材和习题辅导教材、学好本课程 的意义、以及如何学好数据结构这门课程。 第二部分第二部分 新课新课（约（约78分钟）分钟） 第一章第一章 绪论绪论 本章内容概述本章内容概述（约（约3分钟）分钟） 简述本章基本要求、学习内容、重点、以及本章教学内容安排 1.1 什么是数据结构什么是数据结构（约（约35分钟）分钟

3、） 提问：什么是数据结构？ 分析用计算机可以解决那些问题，其发展的背景以及解决问题的整体过程，引出在用计算机 解决问题的过程中，需要考虑到数据与数据之间的关系。 举例说明： （1）图书检索系统中所涉及到的数据之间的关系线性关系 （2）人家对弈问题过程中所涉及到的棋盘与棋盘数据之间的关系树型结构 （3）十字路口交通灯颜色设计的问题中数据之间的关系图型结构 引出数据结构的定义、研究的内容、及其基本概念、发展史和在整个学科中的地位和作用。 2 基本概念和术语基本概念和术语（约（约45分钟）分钟） （1）通过例子引出几个基本概念）通过例子引出几个基本概念（约（约5分钟）分钟） 数据：是信息的载体，是描

4、述客观事物的数、字符、以及所有能输入到计算机中并被计算机 程序识别和处理的符号的集合, 是计算机程序加工的”原料”。 数据对象：数据对象是具有相同性质的数据元素的集合。举例说明。 数据元素：数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。有时一个数 据元素可以由若干数据项(Data Item)组成。举例说明。 数据项：数据项是数据不可分割的最小标识单位。举例说明。 说明几者之间的关系和区别。引出数据元素之间的关系、数据结构的定义。 （2）数据之间的按照关系不同的分类）数据之间的按照关系不同的分类（约（约5分钟）分钟） 集合：数据元素之间无特殊关系； 线性结构：数据元素之间存在着一个

5、对一个的关系； 树型结构：数据元素之间存在着一个对多个的关系； 图型结构。数据元素之间存在着多对多的关系。 （3）数据结构的形式定义（二元组定义）数据结构的形式定义（二元组定义）（约（约10分钟）分钟） Data_Structure = （D, S）其中，D 是数据元素的有限集（即一个数据对象），S 是该对象 中所有数据成员之间的关系的有限集合。 举例说明：以复数为例，说明复数类的数据结构形式定义方式。以一个事务管理的程序为例，说明该程序中数据之间的关系， （4）数据的逻辑结构定义、逻辑结构的分类）数据的逻辑结构定义、逻辑结构的分类（约（约10分钟）分钟） 数据的逻辑结构从逻辑关系上描述数据，

6、可以看作是从具体问题抽象出来的数据模型，与数 据的存储无关，也与数据元素本身的形式、内容、相对位置无关；举例说明； （5）数据的物理结构定义、物理结构的分类）数据的物理结构定义、物理结构的分类（约（约10分钟）分钟） 数据结构在计算机中的表示(或称映象）称为数据的存储结构，又称为物理结构。它包括数据 元素的表示和关系的表示。 物理结构的分类：着重讲解顺序存储结构和链式存储结构，并说明二者之间的不同，举例说 明。 综合比较数据逻辑结构和物理结构之间的关系，并举例说明。 （6）数据类型的定义和分类）数据类型的定义和分类（约（约5分钟）分钟） 数据类型是一个值的集合和定义在这个值集上的一组操作的总称

7、。数据类型可分两类：原子 类型和结构类型。 小结小结（约（约2分钟）分钟） 内容回顾、重点、难点。 第三部分第三部分 布置作业布置作业（约（约2分钟）分钟）习题练习。重点和难点：重点和难点：重点：数据结构所涉及的基本概念、数据结构的分类，数据的逻辑结构和物理结构、他们 之间的关系。参考资料：参考资料： 数据结构题集严蔚敏等编著，清华大学出版社 数据结构学习指导与习题详解张凤琴等编，清华大学出版社 数据结构（C 语言篇）习题与解析李春葆编，清华大学出版社注意事项及心得：注意事项及心得：注意把握时间。注：表中选项打“”【第二次（2 学时）】教学主题或章、教学主题或章、 节节前面章节简要回顾 1.3

8、 抽象数据类型、1.4 算法及其分析授课类型授课类型理论课 实验课 实习或课程设计 练习课 其他教学过程教学过程前面章节复习 5 分钟，新课 83 分钟，布置作业 2 分钟教学方式教学方式讲授 讨论 阅读 示范操作 练习 提问 其他教学资源教学资源多媒体课件 演示动画 相关软件 音像 其他教学目的及要求（分掌握、理解、了解三个层次）：教学目的及要求（分掌握、理解、了解三个层次）： 了解抽象数据类型的定义、表示和实现方法。理解算法设计的五个要素和基本要求；掌握算 法效率的度量方法，着重学习算法的时间复杂度分析。教学内容提要：教学内容提要： 第一部分第一部分 前面章节简要回顾前面章节简要回顾（约（

9、约5分钟）分钟） 前面第一节、第二节内容的简要回顾。 第二部分第二部分 新课新课（约（约83分钟）分钟） 本次内容概述本次内容概述（约（约3分钟）分钟） 简述本次课的基本要求、学习内容、重点、以及内容安排 1.3 抽象数据类型抽象数据类型（约（约25分钟）分钟）由数据类型定义引入抽象数据类型的定义。 抽象数据类型抽象数据类型：由用户定义，用以表示应用问题的数据模型，指一个数学模型以及定义在此 数学模型上的一组操作。 抽象数据类型的定义方式抽象数据类型的定义方式：ADT 抽象数据类型名 数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义 ADT 抽象数据类型名 抽象数据类型

10、的表示与实现，抽象数据类型的表示与实现，举例说明：三元组的表示与实现。 类类 C 语言的一些共同的约定。语言的一些共同的约定。 1.4 算法和算法分析算法和算法分析（约（约55分钟）分钟）一、算法的基本概念一、算法的基本概念（约（约10分钟）分钟） （1）算法的定义：算法的定义：是对特定问题求解步骤的一种描述,是一个有穷的指令集，这些指令表示 一个或多个操作。 （2）算法的特性算法的特性(要素要素) 有穷性：算法应在执行有穷步后结束,且每一步都在有穷时间内完成 确定性：每步定义都是确切、无歧义的 可行性：算法中描述的操作应能通过执行有限次已经实现的基本运算实现 输入：有 0 个或多个输入 输出

11、：有一个或多个输出(处理结果)。 （3）算法设计的要求算法设计的要求 正确性：不含有语法错误；对于各种合法的输入数据能够得到满足规格说明要求的结果。 可读性：要求程序有较好的人机交互性,有助于人们对算法的理解。 健壮性：对输入的非法数据能作出适当的响应或处理。 效率与低存储需求：主要指算法的执行时间和所需的最大存储空间，这两方面主要和问 题的规模有关。 二、算法效率的度量二、算法效率的度量（约（约45分钟）分钟） （1）衡量算法的方法衡量算法的方法（约（约5分钟）分钟） 算法的后期测试：在算法中的某些部位插装时间函数 time ( )测定算法完成 某一功能所 花费时间。 算法的事前估计：空间复

12、杂度、时间复杂度 （2）算法的时间效率度量方法（时间复杂度）算法的时间效率度量方法（时间复杂度）（约（约30分钟）分钟）依据的算法选用何种策略、问题的规模、书写程序的语言、编译程序所生成目标代码的质量、 硬件的速度。 一个特定算法“运行工作量”大小，只依赖于问题的规模（通常用整数 n 表示），或者说，它 是问题规模的函数。 一个算法所耗费的时间，应该是该算法中每条语句的执行时间之和，而每条语句的执行时间 又是该语句的执行次数（频度）与该语句执行一次所需时间的乘积。 语句的频度指的是该语句重复执行的次数。举例说明。语句的频度指的是该语句重复执行的次数。举例说明。 （a） +x; s=0； +x

13、的频度为 1 （b） for (i=1; i=n; +i) +x; s+=x; +x 的频度为 n （c） for (j=1;j=n;+j)for (k=1;k=n;+k)+x; s+=x; +x 的频度为 n2我们假定，每条语句一次执行的时间都是相同的，为单位时间。这样我们对时间的分析就可 以独立于软硬件系统。时间复杂度是问题规模的函数T( n )。 设解决一个问题的规模为 n ，基本操作被重复执行的次数是 n 的一个函数 f（n），假如， 随着问题规模 n 的增长，算法执行时间的增长率和 f(n)的增长率相同，则可记作：T (n) = O(f(n) 其中 T（n）叫算法的渐进时间复杂度，）

14、叫算法的渐进时间复杂度，简称时间复杂度， O 是 Order（数量级）的首字 母，意思是 T（n）与 f（n）只差一个常数倍。 举例说明时间复杂度的计算方法： 例对 n 个整数的序列进行选择排序。其中序列的“长度” n 为问题的规模。 void selectSort ( int a , int n ) /对 n 个整数 a0,a1,an-1按递增顺序排序for ( int i = 0; i n-1; i+ ) int k = i;/从 ai查到 an-1, 找最小整数, 在 akfor ( int j = i+1; j n; j+ )if ( aj ak ) k = j; int temp =

15、 ai; ai = ak; ak = temp; （3）算法的空间效率度量方法（空间复杂度）算法的空间效率度量方法（空间复杂度）（约（约5分钟）分钟） 空间复杂度空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，记作： S(n) = O(g(n) 表示随着问题规模 n 的增大，算法运行所需存储量的增长率与 g(n)的增长率相同。 算法的存储量包括： 输入数据所占空间； 程序本身所占空间； 辅助变量所占空间 小结小结（约（约3分钟）分钟） 内容回顾、重点、难点。 第三部分第三部分 布置作业布置作业（约（约2分钟）分钟） 书面作业：阅读教材程序段、分析其时间复杂度。并思考下列问题。 1 为什么要学习数据结构？ 2 学习数据结构什么内容？ 3 如何学习数据结构？重点和难点：重点和难点： 重点：掌握时间复杂度的概念、会计算问题的时间复杂度，了解空间复杂度。 难点：抽象数据类型概念的理解、问题时间复杂度的计算。参考资料：参考资料： 数据结构题集严蔚敏等编著，清华大学出版社 数据结构学习指导与习题详解张凤琴等编，清华大学出版社 数据结构（C 语言篇）习题与解析李春葆编，清华大学出版社注