数据基础结构 1

教案学院:课程名称:数据结构任课教师:专业班级:课程学时:64周学时:4年月日教案纸（首页）第1页第1次课2学时授课时间_______教学主题数据结构基本概念教学要求1、掌握数据结构的基本概念。2、掌握数据逻辑结构和存储结构的映射关系。3、掌握数据类型和数据结构的区别和联系。4、掌握利用抽象数据类型表述求解问题的方法。教学重点数据结构的逻辑结构、存储结构、数据运算三方面的概念及相互关系、抽象数据类型教学难点利用抽象数据类型表述求解问题的方法教学方法讲授教学手段多媒体+板书讲授要点1、数据结构的概念。2、数据逻辑结构类型和存储结构类型。3、数据结构和数据类型的关系。4、抽象数据类型的作用和描述方法。作业参考资料教材：数据结构教程（第5版），清华大学出版社，李春葆等2017。参考资料：数据结构（C语言），清华大学出版社，严蔚敏吴伟民编著。注：本页为每次课教案首页教案纸（首页）第1页教学内容备注与后记首先自我介绍和课程介绍。数据结构到底是什么，我们一起来看一看。1.1什么是数据结构1.1.1、数据与数据结构数据：是对客观事物的符号表示。所有能被输入到计算机中，且能被计算机处理的符号的集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。数据元素：是数据（集合）中的一个“个体”，是数据结构中讨论的基本单位。数据对象：是性质相同的数据元素的集合，是数据的一个子集。数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。这种集合称为结构。举例说明：学生成绩表结论：数据结构中讨论的元素关系主要是指相邻关系或邻接关系。由此得出，一个数据结构的构成：数据的逻辑结构:集合松散线性结构一对一树型结构一对多网状结构多对多每一种逻辑结构举实例进行说明，帮助学生加深理解。数据的存储结构：数据在计算机存储器中的存储方式就是存储结构。常用的四种基本存储类型有顺序存储、链式存储、顺序存储、哈希存储等。数据运算：数据运算是对数据的操作。1.1.2、数据类型数据类型是一个值的集合和定义在此集合上的一组操作的总称（一起复习C语言中已经学过的数据类型。）1.1.3、抽象数据类型抽象数据类型（ADT）指的是从求解问题的数学模型中抽象出来的数据逻辑结构和运算（抽象运算），而不考虑计算机的具体实现。抽象数据类型=数据逻辑结构+抽象运算抽象数据类型表示法：三元组表示：（D，S，P）其中D是数据对象，S是D上的关系集，P是对D的基本操作集。书中的定义格式：ADT抽象数据类型名{数据对象：<数据对象的定义>数据关系：<数据关系的定义>基本操作：<基本操作的定义>}ADT抽象数据类型名ADT有两个重要特征:数据抽象数据封装本课小结：熟悉各名词、术语的含义，掌握数据结构的基本概念，理解抽象数据类型的定义。

第2次课2学时授课时间__________教学主题算法的基本概念以及算法的分析教学要求1、掌握算法的特性和描述方法。2、掌握算法的分析方法，包括时间复杂度和空间复杂度分析。3、掌握从数据结构的角度设计好的算法的过程。教学重点算法特性，算法的时间复杂度分析和空间复杂度分析，设计好的算法的过程教学难点算法的时间复杂度分析和空间复杂度分析教学方法讲授、练习教学手段多媒体、上机实操讲授要点1、算法的特性，算法和程序的异同。2、算法的时间复杂度分析。3、算法的空间复杂度分析。4、设计好的算法的过程。作业完成学习通上的第一章测试题。参考资料教材：数据结构教程（第5版），清华大学出版社，李春葆等2017。参考资料：数据结构（C语言），清华大学出版社，严蔚敏吴伟民编著。注：本页为每次课教案首页教案纸（续页）教学内容备注与后记回顾上节课有关数据结构的基本概念，引入算法：1.2算法及其描述1.2.1什么是算法算法是对特定问题求解步骤的一种描述，它是指令的有限序列。算法的五个重要特性：（1）有穷性（2）确定性（3）可行性（4）有输入（5）有输出举例说明是否为算法，并说出原因。1.2.2算法的描述自然语言、伪代码、C\C++语言描述课上举例说明，课下练习学习通上的例题。1.3算法的分析算法分析目的：分析算法的时间和空间效率以便改进算法性能。1.3.1时间复杂度分析事前估算分析法：算法的执行时间是问题规模n的函数。一个算法由控制结构和原操作构成，求出算法所有原操作的执行次数，用T(n)表示。算法执行时间大致=原操作所需的时间×T(n)在算法分析时，原操作所需时间基本不变，仅仅考虑基本操作的运算次数，所以算法的执行时间用时间复杂度来表示O(f(n))=T(n)。记号“O”读作“大O”，它表示随问题规模n的增大算法执行时间的增长率和f(n)的增长率相同。T(T(n)nf(n)n0一般地，常用的有常数阶O(1)、线性阶O(n)、平方阶O(n2)、立方阶O(n3)、对数阶O(log2n)、指数阶O(2n)等。算法时间性能比较：假如求同一问题有两个算法：A和B，如果算法A的平均时间复杂度为O(n)，而算法B的平均时间复杂度为O(n2)。一般情况下，认为算法A的时间性能好比算法B。O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)补充：时间复杂性的运算法则求和规则：求积规则：1.3.2空间复杂度分析用于量度一个算法在运行过程中临时占用的存储空间大小。一般也作为问题规模n的函数，采用数量级形式描述，记作：S(n)=O(g(n))1.4其他情况的算法分析1.4.1