数据结构--PPT.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数 据 结 构,-,1,第一章 绪 论,1.1,数据结构研究什么？,将现实世界中的数据描述及关系表示出来，并存储到计算机内，供用户程序操作。,现实世界中的数据描述及关系：,4,种：离散型，线性结构，层次结构，网状结构。,离散数学：研究离散型。,数据结构：研究线性结构，层次结构和网状结构。,线性结构：线性表表示。,层次结构：,树形结构表示。,网状结构：图结构表示。,数据结构研究：数据逻辑结构，存储结构及施加其上的运算。,2,例,1,L=(20,-5,66,15,44),是一个线性表,例,2,一张,登记表,DL,序号 姓 名 性 别 年 龄,1,李 刚 男,25,记录,1,2,王 霞 女,29,记录,2,3,刘大海 男,40,记录,3,4,李爱林 男,44,记录,4,其中：姓名、性别、年龄是,数据项,(item),、,数据域,(field),；,(,姓名，性别，年龄,),是,记录,(record),C,语言将,记录,(record),定义为,”,结构,”,(struct),；,登记表也是一个线性表。,3,例,3,家族中,父子关系是一种,层次结构,-,树,T,张一,张三,张二一,张三一,张三小,张三大,张二,张四,层次结构：,部门之间的隶属关系：,学校,-,系,-,科,-,班,领导和被领导之间领导关系：,主席,-,部长,-,司长,-,处长,-,科长,4,例,4,无向图,G,A,B,D,C,E,F,G,其中：,A,、,B,、,C,等是,顶点,(vertex),图中任意两个顶点之间都可能有关系。,网络结构：,电网，电信网，计算机通信网等。,5,1.,基本数据结构的定义、特性、运算与算法,1.1,线性结构：线性表；栈,队列,双队列；数组,串。,1.2,非线性结构：树,二叉树；图,网络。,2.,数据结构的存储结构与实现,选择存储结构,设计算法,3.,查找算法：顺序,折半,分块,哈希,二叉排序树等,4.,排序算法：内部排序,外部排序,5.,文件,6.,基本应用与综合应用,要求具备的知识：,c,语言及程序设计，具有一定的程序设计能力。,本课程的内容和任务,6,1.2,基本概念和术语,1.,数据（,data),-,所有能输入到计算机中并被计算机程序加工、处理,的符号的总称。,如：整数、实数、字符、声音、图象、图形等。,2.,数据元素,(data element),-,数据的基本单位。（元素、记录、结点、顶点）,在计算机程序中通常作为一个整体进行考虑和处理。,3.,数据项,(data item),-,是数据的不可分割的最小单位。如：姓名、年龄等,一个数据元素可由一个或多个数据项组成。,如,:(,姓名、年龄,),7,4.,数据对象,(data object),由性质相同,(,类型相同,),的数据元素组成的集合。,数据对象是数据的一个子集。,例,1,由,4,个整数组成的数据对象,D1=20,-30,88,45,例,2,由正整数组成的数据对象,D2=1,2,3,.,例,3,由,26,个字母组成的数据对象,D3=A,B,C,.,Z,其中：,D1,，,D3,是有穷集，,D2,是无穷集。,5.,抽象数据对象,ElemSet,=,某种同类型的数据元素,8,6.,数据结构,(data structure),-,数据之间的相互关系，即数据的组织形式。,内容,包括：数据逻辑结构、数据存储结构和数据运算。,数据逻辑结构：数据元素之间的逻辑关系。,数据存储结构：数据元素及其关系在存储器中的存储表示。,数据运算：定义在数据逻辑结构上的操作。如：查询，插入，,删除和修改，排序等。,数据逻辑结构有两大类：,线性结构,：特征：若结构是非空集，则仅有一个开始结点和一个终止结点；其他结点都只有一个前趋结点和一个后继结点。,非线性结构,：特征：一个结点有多个前趋结点和后继结点。,数据存储结构有,4,种：顺序存储结构，链接存储结构，索引存储结构和散列存储结构。,9,数据逻辑结构和存储结构与运算三者之间有紧密的关系：,如：给定一种数据的逻辑结构，可采取顺序存储结构或,链接存储结构进行存储；,按定义的运算和运算性质的不同，施加于同一数据结构,上，则会导致有不同的种类的数据结构产生。,如：限制在线性表的一端做插入和删除操作，称该线,性表为栈；,若限制在线性表的一端插入，另一端删除操作，称该,线性表为队。,其栈和队都有顺序存储结构或链接存储结构，则它们存储结构称为：顺序栈，链式栈，顺序队，链式队。,10,1.,线性表,2.,栈,线性结构,3.,队列,双队列,4.,数组,数据结构,5.,字符串,非 线 性,1.,树,二叉树,结 构,2.,图,数据逻辑结构,分类,11,数据顺序,存储结构和链式存储结构（,物理结构，存储表示,物理表示,）,数据结构在计算机存储器中的,映象,(mapping),。,(1),顺序存储结构,(,向量,一维数组,),例,.char a5=A,B,C,D,；,A B C D E,0 1 2 3 4,a,是一维数组,(2),非顺序存储结构,(,链接表：指针类型和结构类型定义）,例,.,单链表,data next,Head A B C D ,4,个结点的单链表,12,7.,数据类型（,data type),-,是一个值的集合和定义在这个值上的一组操作的总称。,用数据类型定义数据结构。,(1),原子类型,(,如：,int,char,float,等,),(2),结构类型,(,如：数组,结构,联合体等）,8.,抽象数据类型,(Abstract Data Type)-,与计算机的实现无关的数据类型。,形式定义：,ADT,抽象数据类型名,1.,数据对象；,2.,数据关系,:,一个或多个关系；,3.,一组基本操作,/,运算,ADT,抽象数据类型名,注意,：常用,DataType,表示抽象元素类型。,13,1.3,算法和算法分析 数据的运算是通过算法描述的。,1.,算法,-,求解一个特定任务的指令的有限序列。,例,.,求,a0.n-1,中,n,个数的平均值,(,假定,n0),。,float average(float a,int n),int i,；,float s=0.0,；,/,累加器赋初值,for(i=0,；,in,；,i+),s=s+ai,；,/ai,累加到,s,中,s=s/n,；,/,计算平均值,printf(,“,ave=%f,”,s),；,/,输出,return(s),；,/,返回,其中：,a,n,为输入量；,s,为输出量。,14,2.,算法的,5,个特征,(1),有穷性,：在有限步,(,或有限时间,),之后算法终止。,例,.i=0,；,s=0,；,while(i10),s+,；,i+,；,(2),确定性,：无二义性。,例,.x=5,；,y=10,；,z=x+y,；,printf(,“,%d,%d,%d,”,x,y,z),；,x+y,解释为：,x+(+y),？,(x+)+y,？,15,(3),可行性,：可以在计算机上实现。,for(i=1,s=0,；,i=0,；,i+)/,死循环,s+,；,/,不能终止,例,2,float suanfa2(),int xy,；,scanf(,“,%d,”,&x),；,y=sqrt(x),；,/,当,x0,时,出错,return(y),；,17,4.,算法,的,时间复杂度,衡量算法性能：,a.,算法正确性；,b.,执行算法所消耗的时间；,c.,执行算法所消耗的空间（主要考虑辅存空间）；,d.,算法易读易理解，易于编码，易于调试等。,主要讨论算法执行时间。,算法所消耗的时间：算法中每条语句执行时间之和。,每条语句执行时间,=,语句的执行次数,一次执行该语句的时间。,语句的频度：设,n,为求解的,问题的规模,基本操作,(,或语句,),执行次数总和称为,语句频度,记作,f(n),。,问题的规模,n,：指线性表的长度多项式的项数，矩阵的阶数，树的结点数，图中的顶点或边数等。,注：一次执行语句的时间是很难精确算出的：它与机器的执行速度，编译程序编译质量及运行环境等因素有关。,算法所消耗的时间粗略地用算法中语句执行的最大次数来度量。,18,/,求两个,n,阶方阵的乘积：,C=A*B,#define n 100,int Multiply(int ann,int bnn,int cnn),int j,i,k,；语句的频度,f(n),(1)for(i=0,；,in,；,i+)n+1,(2)for(j=0,；,jn,；,j+)n(n+1),(3)cij=0,；,n,2,(4)for(k=0,；,kn,；,k+)n,2,(n+1),(5)cij=cij+aik*bkj,；,n,3,算法所消耗的时间就是所有语句频度之和,T(n):,T(n)=2n,3,+3n,2,+2n+1 T(n),是矩阵的阶数,n,的函数。,当,n,，,2n,3,+3n,2,+2n+1,与,n,3,同阶，即同一数量级。记为：,T(n)=O(f(n)=O(n,3,),即与,f(n),中最高的阶相同。,19,例,1 int s,；语句的频度,f(n),scanf(,“,%d,”,&s),；,1,s+,；,1,printf(,“,%d,”,s),；,1,其中：语句频度为：,f(n)=f(1)=3,与问题规模,n,无关的常数。,时间复杂度为：,T(n)=O(f(n)=O(3)=O(1,）,O(1),称成为常量阶,/,常量数量级,只要算法的执行时间不随问题规模,n,增大而增长，即使算法中有上千条语句，其执行的时间只不过是一个较大的常数，算法的时间复杂度仍然是常数阶,O(1),。,20,例,2,分析下面的算法,void sum(int a,int n)f(n,）,int s=0,i,；,/1,次,for(i=0,；,in,；,i+)/n,次,s=s+ai,；,/,n,次,printf(,“,%d,”,s),；,/1,次,其中：语句频度为：,f(n)=1+n+n+1,时间复杂度为：,T(n)=O(f(n)=O(2n+2)=O(,n,）,On),称成为线性阶,/,线性数量级,一般情况下，对步进循环，只考虑循环体中的语句执行的次数，可忽略步长加,1,，终值判断，控制转移等成分。,21,例,3,分析下面的算法,1.void sum(int m,int n),2.int i,j,s=0,；,/1,次,3.for(i=1,；,i=m,；,i+)/m,次,4.for(j=1,；,j=n,；,j+)/m*n,次,5.s+,；,/,m*n,次,6.printf(,“,%d,”,s),；,/m,次,7.,8.,其中,:f(m,n)=1+m+2*m*n+m=2mn+2m+1,当,m=n,时,f(n)=2n,2,+2n+1,T(n)=O(f(n)O(2n,2,+2n+1)=O(,n,2,),平方阶。,对嵌套层次的循环结构，时间的复杂度,T(n),由最内层循环体语句的频度,f(n),决定。,22,例,4,分析下面的算法,1.void sum(int n),2.int i,j,s=0,；,/1,次,3.for(i=1,；,i=n,；,i+)/n,次,4.for(j=1,；,j=0&(ai!=k),(3)i-;,(4)return i;,(3),语句的频度不仅问题规模,n,有关，而且与,a,数组各元素和,k,的取值有关。若,a,中没有要找的,k,值，,(3),语句的频度为,f(n)=n;,若,a,中最前一个元素是要找的,k,，则,(3),语句的频度为常数,0,。在这种情况下，,采用最坏的时间复杂度作为算法的时间复杂度：,T(n)=0(n),24,常用时间复杂度递增依次为：,常数阶,O(1),对数阶,O(log,2,n),线性阶,O(n),线性对数阶,O(nlog,2,n),平方阶,O(n,2,),立方阶,O(n,3,),K,方阶,O(n,k,),，,指数阶,O(2,n,),。,O(1),算法效率最高，,O(2,n,),算法效率最低,。,5.,算法的,空间复杂度,执行算法所需存储空间的大小。也是问题规模,n,的函数。,6.,算法的复杂度,包括：算法时间复杂度和算法空间复杂度。,低,高,25,例,6,冒泡排序,的,C,语言算法,/对数组,a,中,n,个数按递增次序作冒泡排序,1.Void bubble1(int a,int n),2.int i,j,temp,；,3.for(i=0,；,i=n-2,；,i+)/,？次,4.for(j=0,；,jaj+1)/,？次,6.temp=aj,；,/,？次,7.aj=aj+1,；,/,？次,8.aj+1=temp,；,/,？次,9.,10.for(i=0,；,i1&change,；,i-),3.change=,FALSE,；,/change,为交换标志,4.for(j=0,；,jaj+1),6.aj,aj+1,；,/,交换元素,7.change=,TRUE,；,/,修改交换标志,8.,9.,10.,思考：在最好情况下，,f(n)=?T(n)=O(f(n)=?,在最坏情况下，,f(n)=?T(n)=O(f(n)=?,27,