数据结构授课教案-第1章

山东轻工业学院教师授课教案课程名称：数据结构（计科）课程代码：0301306学分：4.5课程类别：必修开课单位:信息科学与技术学院授课班级：授课教师：杨春花山东轻工业学院教务处制授课时间年月日星期第节年月日星期第节年月日星期第节授课内容概要第一章绪论第一节什么是数据结构第二节基本概念和术语第三节抽象数据类型的表示与实现第四节算法和算法分析目的要求目的：了解数据结构课程及相关的基本术语，了解算法的描述和分析。基本要求：掌握数据结构的基本概念和相关术语、数据的逻辑结构和存储结构的分类、时间复杂度的概念和分析方法；了解数据类型和抽象数据类型的概念；理解数据的逻辑结构、存储结构和运算之间的关系，理解算法的描述方法、概念、特性和设计目标；。重点数据结构的基本概念；数据的逻辑结构、存储结构和运算之间的关系；数据的逻辑结构和存储结构的分类；算法的时间复杂度的概念和分析方法。难点算法的时间复杂度计算。作业布置习题1参考书1.数据结构题集(C语言版),严蔚敏，清华大学出版社，2002。3.数据结构、算法与应用－C++语言描述，(美)SartajSahni著，汪诗林等译，机械工业出版社，2002。课型理论课学时分配复习分钟主要教具投影、黑板讲授分钟教学方法讲解、提问、示例指导分钟教学手段板书、课件总结分钟备注共4学时注：课型一栏填写理论课、实验课、习题课等授课内容备注课程介绍：教材:数据结构（C语言版），严蔚敏吴伟民，清华大学出版社，2002参考教材:1数据结构题集（C语言版），严蔚敏吴伟民，清华大学出版社2数据结构（C语言篇）－－习题与解析，李春葆，清华大学出版社学时数：72（讲课：64，实验：8）；课程设计（1周）课程性质及特点数据结构是一门专业基础课，是十分重要的核心课程。难度大综合性强必须下苦功学习学习方法:1戒骄戒躁，踏实学习，打好基础；2听、记、练结合，积极思考。第一章绪论第一节什么是数据结构1数据结构课程研究的内容数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。2数据结构课程体系的形成1968年美国唐·欧·克努特（DonaldE.Knuth）教授开创了数据结构的最初体系：它所著的《计算机程序设计技巧》（TheArtofComputerProgramming）第一卷《基本算法》是第一本系统阐述数据的逻辑结构和存储结构及其操作的著作。第二节基本概念和术语1数据数据(Data):是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。2数据元素数据元素(DataElement)：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。3数据对象的概念数据对象(DataObject)：是性质相同的数据元素的集合。是数据的一个子集。在某个具体问题中，数据元素都具有相同的性质（元素值不一定相等），属于同一数据对象。4数据结构的概念和分类数据结构(DataStructure)：是相互之间存在一种或多种特定关系的数据元素的集合。－－－－数据的逻辑结构数据结构的分类：1)集合：结构中的数据元素“同属于一个集合”。2)线性结构：结构中的数据元素之间存在一对一的关系。3)树型结构：结构中的数据元素之间存在一对多的关系。4)图状结构或网状结构：结构中的数据元素之间存在多对多的关系。例：某班学生基本情况登记表家族的族谱对每种数据结构，主要讨论如下两方面的问题：1）数据的逻辑结构，数据结构的基本操作；2）数据的存储结构，数据结构基本操作的实现；数据结构的另一种定义：把按某种逻辑关系组织起来的一组节点（数据元素），按一定的存储方式存储于计算机中，并在其上定义一个运算的集合，称为数据结构。数据结构的三个组成部分：1)数据的逻辑结构2)数据的存储结构3)数据的运算一、数据（逻辑）结构的表示1)图示表示2)二元组表示Data_Structrue=（D，S）其中:D是数据元素集合，S是D上关系的集合。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型，它与数据的存储无关二、数据的存储结构1)定义数据结构在计算机中的表示或实现称为数据的物理结构，又称为存储结构。2)表示包括数据元素的表示及元素间关系的表示。数据元素的表示:在计算机中，可用二进制位串表示一个数据元素，称这个位串为元素（Element）或结点（Node）。元素间关系的表示3分类根据数据元素之间的关系在计算机中的不同表示方法，数据的存储结构分类如下4类：1)顺序存储结构2)链式存储结构3)索引存储4)散列存储4描述本书采用在高级语言中的数据类型（Datatype）来描述存储结构。如：对数据元素，可用基本类型（整型、字符型等）或结构类型来描述对关系：可用一维数组描述顺序存储结构用“指针”描述链式存储结构三、数据的运算数据的运算是在数据的逻辑结构上定义的操作算法。如检索、插入、删除等。数据的运算是在逻辑结构上定义，在具体的存储结构上实现。5数据类型和抽象数据类型的概念。数据类型（DataType）:是一个值的集合和定义在该值集上的一组操作的总称。抽象数据类型（AbstructDataType，简称ADT）:是指一个数学模型以及定义在该模型上的一组操作。（D，S，P）其中，D表示数据对象，S表示关系集，P表示基本操作集。本书实际用ADT来描述数据的逻辑结构及运算。第三节抽象数据类型的表示与实现数据元素的表示数据类型typedef定义新类型算法的描述类C语言函数几点说明：1typedef2数据元素的定义3算法的书写采用类C语言、函数描述算法的输入、输出参数传递方式例：已知学生信息表，存储在数组中。书写算法实现根据学号查找学生所在专业。第四节算法和算法分析1.4.1算法算法的概念:算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列。算法的五个特性：（1）有穷性（2）确定性（3）可行性（4）输入（5）输出1.4.2算法设计的要求要设计一个好的算法通常要考虑以下的要求。⑴正确性(Correctness):算法应满足具体问题的需求。⑵可读性性(Readability):算法应该好读。以有利于阅读者对程序的理解。⑶健壮性(Robustness):算法应具有容错处理。⑷效率与低存储量要求:效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。1.4.3算法效率的度量算法执行时间分析方法的分类：事后统计事前分析度量方法采用时间复杂度来估计算法的算法的执行时间T(n)=O(f(n))即：如果存在两个正常数c和n0，对于所有的n≧n0，有︱T(n)︳≦c｜f(n)︳它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作渐近时间复杂度（AsymptoticTimeComplexity），简称时间复杂度。时间复杂度的求法：基本操作（原操作）语句的频度：语句执行的次数定理：若A(n)=amnm+am-1nm-1+…+a1n+a0是一个m次多项式，则A(n)=O(nm)方法：确定基本操作，求各语句的频度之和，根据定理求出最后结果。示例:常用的时间复杂度关系：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)…«O(2n)O(n!)O(nn)若算法中基本操作重复执行的次数随问题输入数据集不同而不同，这时可计算最坏情况下的时间复杂度或平均时间复杂度。1.4.4算法的存储空间需求空间复杂度:算法所需存储空间的度量，记作:S(n)=O(f(n))其中n为问题的规模(或大小)一般只考查算法所需的辅助空间的大小作为算法所需空间的度量。