数据结构第一章绪论ppt课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构课程安排,说明：1、本课程的先修课程是,程序设计,和,离散数学,2、本课程是,操作系统、编译原理,和,数据库,的基础,数据结构课程安排说明：1、本课程的先修课程是程序设计和离,1,什么是数据结构,算法定义,算法的性能分析,第一章 绪论,什么是数据结构第一章 绪论,2,1.1 什么是数据结构,程序=算法+数据结构,数据结构是程序设计的基础。,算法是在数据结构的基础上建立的,。,1.1 什么是数据结构程序=算法+数据结构,3,数据,（data）,数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序识别和处理的符号的集合。,数值性数据,非数值性数据,1.2 数据结构的概念,数据（data）数据是对客观事物的符号表示，在计算机科学中是,4,数据元素,(data element),数据的,基本单位,。在计算机程序中常作为一个整体进行考虑和处理。,有时一个数据元素可以由若干,数据项,(Data Item),组成。,数据项,是,具有独立含义的最小标识单位,。,数据元素又称为元素、结点、记录。,如：每个学生的信息、棋盘中每个格局、比赛中每个项目,数据元素(data element)数据的基本单位。在计算,5,数据对象,(data object),数据对象是具有相同性质的数据元素的集合。,整数数据对象,N,=0,1,2,如:学生档案组成一个数据对象,棋所有格局构成一个数据对象,数据对象(data object)数据对象是具有相同性质的,6,数 据 结 构,定义,:,指某一数据对象的所有数据成员之间的关系。记为：,Data_Structure=（D,S),其中，,D,是某一数据对象，,S,是该对象中所有数据成员之间的关系的有限集合。,数 据 结 构定义:,7,数据结构,主要研究三方面内容：,数据元素间的,逻辑关系,，即数据的,逻辑结构,；,数据元素及其关系在计算机存储内的表示，即数据的,存储结构,；,数据的运算，即对数据元素施加的,操作,。,数据结构主要研究三方面内容：数据元素间的逻辑关系，即数据的逻,8,数据的逻辑结构,数据元素之间的逻辑关系,数据的逻辑结构,从逻辑关系上描述数据,，,与数据的存储无关,；,数据的逻辑结构可以看作是,从具体问题抽象出来的数据模型,；,数据的逻辑结构,与数据元素本身的形式、内容无关,；,线性结构：,线性表,非线性结构：,树、图（或网络）,数据的逻辑结构分类,数据的逻辑结构 数据元素之间的逻辑关系数,9,线性结构,树形结构,树 二叉树 二叉搜索树,3,1,5,8,7,10,11,9,6,13,9,8,7,4,5,6,2,3,1,a1,a2,a3,a4,a5,10,14,13,12,11,2,3,4,5,6,7,8,9,1,10,线性结构树形结构树 二叉树,10,堆结构,“,最大”堆,“,最小”堆,12,3,5,4,8,7,11,10,2,9,1,6,4,10,12,11,5,1,2,3,6,9,8,7,堆结构“最大”堆 “最小”堆12354871,11,图结构 网络结构,1,2,5,6,4,3,1,2,5,4,3,6,11,33,18,14,6,6,5,16,19,21,图结构 网络结构12564312543,12,数据的存储结构,数据元素及其关系在计算机存储器内的表示,数据的存储结构是逻辑结构用计算机语言的实现；,数据的存储结构 的主要方法:,顺序存储方法,链式存储方法,(索引存储方法,散列存储方法),数据的存储结构 数据元素及其关系在计算机存,13,a,1,a,2,a,3,a,4,a,5,a,6,1 2 3 4 5 6,顺序存储表示,结点间的逻辑关系由存储单元的邻接关系来体现,链式存储表示,a,0,a,1,a,2,a,3,a,4,结点间的逻辑关系由附加的指针字段来表示,a1 a2 a3 a4 a5 a6 1,14,索引存储表示,索引表,索引存储表示索引表,15,数据的,逻辑结构,与数据的,存储结构,之间的关系,同一种逻辑结构可以映象成,不同的存储结构,数据的存储结构一定要正确,反映出数据元素之间的逻辑关系,数据的逻辑结构数据的存储结构一定要正确,16,抽象数据类型（abstract data type,简称ADT),是指一个数学模型以及定义在该模型上的一组操作。,抽象数据类型可以用三元组表示：,（D，S，P),其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。,ADT抽象数据类型名,数据对象：数据对象的定义,数据关系：数据关系的定义,基本运算：基本运算的定义,ADT抽象数据类型名,抽象数据类型（abstract data type,简称AD,17,1.3,算 法,定义：,解决某一特定问题而采取的具体方法和步骤。,特性：,输入,有0个或多个输入,输出,有一个或多个输出(处理结果),确定性,每步定义都是确切、无歧义的,有穷性,算法应在执行有穷步后结束,可行性,算法中的每一步都具有可行性,描述：,一个算法可用自然语言、数学语言、图形及程序设计语言等来描述。,这里用类C语言。,1.3 算 法定义：解决某一特定问题而采取的具体方法,18,算法与程序,算法是独立于具体的计算机,与具体的程序设计语言,程序是利用具体的计算机语言,来描述算法,算法与程序算法是独立于具体的计算机,19,算法分析,就是衡量算法质量的优劣。,算法分析的目,在于改进算法。,算法分析主要从三方面考虑：,执行算法所耗费的时间（,时间性能,）,执行算法所耗存储空间（,空间性能,）,算法应易于理解，易于编码，,易于调试等等,算法分析就是衡量算法质量的优劣。,20,算法的时空性能分析,时间复杂度,空间复杂度,算法的时空性能分析时间复杂度,21,时间复杂度度量,运行时间=算法中每条语句执行时间之和。,每条语句执行时间=该语句的执行次数（频度）*语句执行一次所需时间。,语句执行一次所需时间取决于,机器的指令性能和速度,和,编译所产生的代码质量，,很难确定。,设每条语句执行一次所需时间为单位时间，则一个算法的运行时间就是该算法中所有语句的频度之和。,时间复杂度度量运行时间=算法中每条语句执行时间之和。,22,时间复杂度,算法中所有语句的频度之和是,矩阵阶数n,的函数,T(n)=,2n,3,+2n,2,+2n+1,一般地，称 n 是问题的规模。则时间复杂度 T(n)是问题规模 n 的函数。,当n,-,时，把时间复杂度的数量级（阶）称为算法的渐进时间复杂度,T(n)=O(n,3,),时间复杂度算法中所有语句的频度之和是矩阵阶数n的函数,23,渐进时间复杂度,大O表示法,加法规则,针对并列程序段,T(,n,)=T1(,n,)+T2(,n,),=O(max(,f,(,n,),g,(,n,),乘法规则,针对嵌套程序段,T(,n,)=T1(,n,)*T2(,n,)=O(,f,(,n,)*,g,(,n,),渐进时间复杂度大O表示法,24,常见时间复杂度：,（按数量级递增排列）,O,（1）、,O,（log,2,n）、,O（,n）、,O,（nlog,2,n）、,O（,n,2,）、,O,（n,3,）、,O（,2,n,）、,O,（3,n,）,常见时间复杂度：,25,例：设有两个算法在同一机器上运行，其执行时间分别为,100n,2,和,2,n,，问：要使前者快于后者，,n,至少要取多大？,解答：,问题是找出满足,100n,2,2,n,=8192,n=14,时，,100n,2,=19600,2,n,=16384,n=15,时，,100n,2,=22500,=0,&,Ai!,=,k),i,-,;,return,i;,算法的语句,i,-,的频度不仅与,n,有关，还与,A 中各元素的取值,，以及,k,的取值,有关。,通常要分析其,最好情况,、,最坏情况,及,平均情况,有时,算法的时间复杂度不仅依赖于问题规模n，还与输入实例的,27,空间复杂度度量,一,个算法在计算机存储器中所占用的空间有,存储算法本身所占用的空间,算法中要处理的数据所占用的空间,算法在运行过程中附加的存储空间,空间复杂度度量一个算法在计算机存储器中所占用的空间有存储,28,本 章 小 结,数据组织的三个层次：数据、数据元素和数据项,数据结构主要研究的三方面内容：,（1）数据的逻辑结构,（线性结构和非线结构）,（2）数据的存储结构,（顺序方式、链式方式、索引方式和散列方式）,（3）对数据实施的基本运算,算法分析：时间性能和空间性能,本 章 小 结数据组织的三个层次：数据、数据元素和数据项数据,29,