《数据结构教程》第一章 绪论.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数 据 结 构,南京航空航天大学,数据结构课题组,第一章,绪 论,1.1,数据结构讨论的范畴,1.2,基本概念,1.3,算法和算法的度量,1.1,数据结构讨论的范畴,Niklaus,Wirth,：,Algorithm,+Data Structures=Programs,程序设计,:,算法,:,数据结构,:,为计算机处理问题编制,一组指令集,处理问题的策略,问题的数学模型,非数值计算的程序设计问题,例一,:,求一组,(n,个,),整数,中的最大值,算法,:,?,模型：,？,基本操作是“,比较两个数的大小,”,取决于,整数值的范围,例二：,计算机对弈,算法：,?,模型：,?,对弈的规则和策略,棋盘及棋盘的格局,例三：,足协的数据库管理,算法：,?,模型：,?,需要管理的项目？,如何管理？用户界面,？,各种表格,概括地说：,数据结构是一门讨论,“,描述现实世界实体的数学模型,(,非数值计算,),及其上的操作在计算机中如何表示和实现,”,的学科。,1.2,基本概念,一、数据与数据结构,二、数据类型,三、抽象数据类型,一、数据与数据结构,所有能,被输入,到计算机中，且能被计算机,处理的符号,的集合。,数据,:,是,计算机操作的对象,的总称。,是计算机处理的,信息的,某种特定的符号,表示形式,。,是数据（集合）中的一个“,个体,”,数据元素,:,是数据结构中讨论的,基本,单位,数据项：,是数据结构中讨论的,最小,单位,数据元素可以是数据项的集合,例如：,描述一个运动员的数据元素可以是,称之为组合项,数据结构：,带,结构,的数据元素的集合,假设用,三个,4,位的十进制数,表示一个含,12,位数的十进制数。,3214,6587,9345,a1,(3214),a2,(6587),a3,(9345),则在数据元素,a1,、,a2,和,a3,之间存在着,“次序”关系,a1,a2,、,a2,a3,3214,，,6587,，,9345,a1 a2 a3,6587,，,3214,，,9345,a2 a1 a3,例如,:,又例，在,2,行,3,列的二维数组,a1,a2,a3,a4,a5,a6,中六个元素之间,存在两个关系,:,行的次序关系,:,列的次序关系,:,row=,col,=,a1 a3 a5,a2 a4 a6,a1 a2 a3,a4 a5 a6,数据结构：,带,结构,的数据元素的集合,再例，在一维数组,a1,a2,a3,a4,a5,a6,的数据元素之间存在如下的,次序关系,:,|i=1,2,3,4,5,或者说，,数据结构,是,相互之间存在着某种逻辑关系的数据元素的集合,。,数据结构：,带,结构,的数据元素的集合,可见，不同的,“,关系,”,构成不同的,“,结构,”,数据的,逻辑结构,可归结为以下,四类,:,线性,结构,树形,结构,图状,结构,集合,结构,数据结构的形式定义,为,:,数据结构,是一个二元组,Data_Structures=(D,S),其中,:,D,是,数据元素的有限集,，,S,是,D,上,关系的有限集,。,数据的,存储结构,逻辑结构在存储器中的,映象,“,数据元素,”,的映象？,“,关系,”,的映象？,数据元素的映象方法：,用二进制位,(bit),的位串表示数据元素,(321),10,=(501),8,=(101000001),2,A =(101),8,=(001000001),2,关系的映象方法：,（,表示,x,y,的方法,）,顺序映象,以相对的存储位置表示后继关系,例如,:,令,y,的存储位置和,x,的存储位置之间差一个常量,C,而,C,是一个隐含值，,整个存储结构中只含数据元素本身的信息,x y,链式映象,以附加信息,(,指针,),表示后继关系,需要用一个和,x,在一起的,附加信息,指示,y,的存储位置,y x,在不同的编程环境中，,存储结构可有不同的描述方法。,当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之,。,例如,:,以三个带有次序关系的整数表示一个长整数时，可利用,C,语言中提供的整数数组类型。,typedef,int,Long_int,3,定义长整数,为,:,二、数据类型,在用高级程序语言编写的程序中，,必须对程序中出现的每个变量、,常量或表达式，,明确说明,它们所,属的,数据类型,。,例如，,C,语言中提供的,基本数据类型,有,:,整型,int,浮点型,float,字符型,char,逻辑型,bool,双精度型,double,数据类型,是一个,值的集合,和定义在此集合上的,一组操作,的总称。,不同类型的变量，其所能取的,值的范围,不同，所能,进行的操作,不同。,三、抽象数据类型,(,A,bstract,D,ata,T,ype,简称,ADT,),是指一个数学模型以及定义在此数学模型上的一组操作。,例如，,抽象数据类型,复数,的定义：,数据对象：,D,e1,e2,e1,e2RealSet ,数据关系：,R1,|e1,是复数的实数部分,|e2,是复数的虚数部分,ADT Complex,基本操作：,AssignComplex,(&Z,v1,v2),操作结果：构造复数,Z,其实部和虚部,分别被赋以参数,v1,和,v2,的值。,DestroyComplex,(&Z),操作结果：复数,Z,被销毁。,GetReal,(Z,&,realPart,),初始条件：复数已存在。,操作结果：用,realPart,返回复数,Z,的实部值。,GetImag,(Z,&,ImagPart,),初始条件：复数已存在。,操作结果：用,ImagPart,返回复数,Z,的虚部值。,Add(z1,z2,&sum),初始条件：,z1,z2,是复数。,操作结果：用,sum,返回两个复数,z1,z2,的,和值。,ADT Complex,假设,:z1,和,z2,是上述定义的复数,则,Add(z1,z2,z3),操作的结果,z3=z1+z2,即为用户期望的结果,ADT,有两个重要特征,:,数据抽象,用,ADT,描述程序处理的实体时，强调的是其,本质的特征,、,其所能完成的功能,以及它和,外部用户的接口,（即,外界使用它的方法,）。,数据封装,将实体的,外部特性和其内部实现细节分离,，并且,对外部用户隐藏,其内部实现细节。,抽象数据类型的描述方法,抽象数据类型可用,（,D,，,S,，,P,）,三元组表示。,其中：,D,是数据对象；,S,是,D,上的关系集；,P,是对,D,的基本操作集。,ADT,抽象数据类型名,数据对象：,数据对象的定义,数据关系：,数据关系的定义,基本操作：,基本操作的定义,ADT,抽象数据类型名,其中基本操作的定义格式为,:,基本操作名,（参数表）,初始条件：,初始条件描述,操作结果,：,操作结果描述,赋值参数,只为操作提供输入值。,引用参数,以,&,打头，除可提供输入值外，,还将返回操作结果。,初始条件,描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。,操作结果,说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。,抽象数据类型的表示和实现,抽象数据类型需要通过,固有数据类型,(,高级编程语言中已实现的数据类型,),来实现。,例如，对以上定义的复数。,typedef,struct,float,realpart,；,float,imagpart,；,complex,；,/-,存储结构的定义,/-,基本操作的函数原型说明,void,Assign(complex,&,Z,float,realval,float,imagval,),；,/,构造复数,Z,其实部和虚部分别被赋以参数,/,realval,和,imagval,的值,float,GetReal,(,cpmplex,Z),；,/,返回复数,Z,的实部值,float,Getimag,(,cpmplex,Z),；,/,返回复数,Z,的虚部值,void,add(complex z1,complex z2,complex&sum),；,/,以,sum,返回两个复数,z1,z2,的和,/-,基本操作的实现,void,add(complex z1,complex z2,complex&sum),/,以,sum,返回两个复数,z1,z2,的和,sum.realpart,=z1.realpart+z2.realpart;,sum.imagpart,=z1.imagpart+z2.imagpart;,其它省略,1.3,算法和算法的衡量,一、算法,二、算法设计的原则,三、算法效率的衡量方法和准则,四、算法的存储空间需求,算法,是为了解决某类问题而规定的一个有限长的,操作序列,。一个算法必须满足以下,五,个重要,特性,：,1,有穷性,2,确定性,3,可行性,4,有输入,5,有输出,一、算法,1,有穷性,对于任意一组合法输入值，在执行,有穷步骤,之后一定能结束，即：,算法中的每个步骤都能在,有限时间,内完成。,2,确定性,对于,每种情况,下所应执行的操作，在算法中都有,确切,的规定，使算法的执行者或阅读者都能明确其含义及如何执行。,并且,在任何条件下，算法都只有一条执行路径。,3,可行性,算法中的所有操作都必须,足够基本,，都可以通过已经实现的基本操作运算有限次实现之。,4,有输入,作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。,5,有输出,它是一组与“输入”有确,定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。,二、算法设计的原则,设计算法时，通常应考虑达到以下目标：,1,正确性,2,.,可读性,3,健壮性,4,高效率与低存储量需求,1,正确性,首先，,算法应当,满足,以特定的,“规格说明”,方式给出的,需求,。,其次，,对算法是否,“,正确,”的,理解可以有以下,四个层次,：,a,程序中不含语法错误；,b,程序对于几组输入数据能够得出满足要求的结果；,c,程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；,通常以,第,c,层,意义的正确性作为衡量一个算法是否合格的标准。,d,程序对于一切合法的输入数据都能得出满足要求的结果；,2,.,可读性,算法主要是为了人的,阅读与交流,，,其次才是为计算机执行，因此算法应该,易于,人的,理解,；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。,3,健壮性,当,输入的数据,非法,时，算法应当恰当地作出反映或,进行相应处理,，而不是产生莫名奇妙的输出结果。并且，,处理出错的方法,不应是中断程序的执行，而应是,返回,一个,表示错误或错误性质的值,，以便在更高的抽象层次上进行处理。,4,高效率与低存储量需求,通常，效率指的是,算法执行时间,；,存储量指的是算法执行过程中,所需的,最大存储空间,，两者都与问题的规模,有关。,三,、算法效率的,衡量方法和准则,通常有,两种,衡量算法效率的方法,:,事后统计法,事前分析估算法,缺点：,1,必须执行程序,2,其它因素掩盖算法本质,和算法执行,时间,相关的,因素,：,1,算法,选用,的策略,2,问题的规模,3,编写程序的,语言,4,编译,程序产生的机器代码,的质量,5,计算机,执行指令,的速度,一个特定,算法的“运行工作量,”,的大小，只依赖于,问题的规模,（通常用整数量,n,表示），或者说，,它,是问题规模的函数,。,假如，随着问题规模,n,的增长，,算法执行时间的增长率和,f(n),的增长率相同,，则可记作：,T(n)=O(f(n),称,T(n),为算法的,(,渐近,),时间复杂度。,如何估算,算法的时间复杂度？,算法,=,控制结构,+,原操作,（固有数据类型的操作）,算法的执行时间,=,原操作,(i),的执行次数,原操作,(i),的执行时间,算法的执行时间,与,原操作执行次数之和,成正比,从算法中选取一种对于所研究的问题来说是,基本操作,的原操作，以该基本操作,在算法中重复执行的次数,作为算法运行时间的衡量准则。,例,一,两,个,矩,阵,相,乘,void,mult(,int,a,int,b,int,&,c),/,以二维数组存储矩阵元素，,c,为,a,和,b,的乘积,for,(i=1;i=n;+i),for,(j=1;j=n;+j),ci,j=0;,for,(k=1;k=n;,+,k),ci,j+=,ai,k,*,bk,j;,/for,/,mult,基本操作,:,乘法,操作,时间复杂度,:,O(n,3,),例,二,选,择,排,序,void,select_sort(,int,&,a,int,n),/,将,a,中整数序列重新排列成自小至大有序的整数序列,。,/select_sort,基本操作,:,比较,(,数据元素,),操作,时间复杂度,:,O(n,2,),j=i;,/,选择第,i,个最小元素,for,(k=i+1;k n;,+,k),if,(ak,aj),j=k;,for,(i=0;i1,&,change,;-i),/bubble_sort,基本操作,:,赋值,操作,时间复杂度,:,O(n,2,),change=FALSE;,/change,为元素进行交换标志,for,(j=0;j aj+1),aj,aj+1;,change=TRUE,;,/,一趟起泡,四、算法的存储空间需求,算法的,空间复杂度定义为,:,表示随着问题规模,n,的增大，,算法运行所需存储量的增长率,与,g(n),的增长率相同。,S(n)=O(g(n),算法的存储量,包括,:,1,输入数据,所占空间,2,程序本身,所占空间,3,辅助变量,所占空间,若,输入数据,所占空间只取决于问题,本身，,和算法无关,，则只需要分析,除,输入和程序之外的,辅助变量,所占,额外,空间,。,若所需额外空间相对于输入数据量,来说是常数，则称此算法为,原地工作,。,若所需存储量依赖于特定的输入，,则通常按最坏情况考虑。,1.,熟悉各名词、术语的含义，掌握基本概念。,2.,理解算法五个要素的确切含义。,本章学习要点,3.,掌握计算语句频度和估算算法时间复杂度的方法。,