数据结构第一章.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,2/8/2026,学时数：,48,学时（,16,学时实验）,教 材：,数据结构,C,语言版,严蔚敏、吴伟民,-,清华大学出版社（配题集）,参考书：,1,殷人昆等，数据结构（用面向对象方法与,C+,描述），清华,大学出版社,2,数据结构,C,语言篇,习题与解析，李春葆，清华大学出版社,3,丁宝康等，数据结构自学考试指导，清华大学出版社,课程介绍,学习要求,1,、上课认真听讲，适当做好笔记，按时交作业。,2,、复习和预习。,3,、课后需要多读课本和参考书，上网查看相关内容，在理解基本内容的基础上，多看、多做习题。,4,、上机实践。,1.1,什么是数据结构,1.2,基本概念和术语,1.3,抽象数据类型的表示和实现,1.4,算法和算法分析,第,1,章 绪论,数据结构与程序的关系,思考,:,下表是,10,次,C,语言课程的测验成绩，请设计一个小程序计算这,10,次测验的总分和平均分。,测验,成绩,1,80,2,76,3,65,4,90,5,56,6,68,7,94,8,51,9,73,10,86,1.1,什么是数据结构,方法一,:,void main(),int t1,t2,t3,t4,t5,t6,t7,t8,t9,t10;,int sum;,int average;,t1=;,t2=;,t3=;,t4=;,t5=;,t6=;,.,sum=t1+.t10;,average=sum/10;,方法二,:,void main(),int,t10=80,.;,int,sum;,int,average;,int,i;,sum=0;,for(i=0;i,数据元素,数据项,例：,学生档案,个人记录,姓名、性别、籍贯,1.2,基本概念和术语,数据对象,（,Data Object,）,-,是性质相同的数据元素的集合，,是数据的一个子集。,数据结构,（,Data Structure,）,-,是相互之间存在一种或多种,特定,关系,的,数据元素,的集合。,表示为：,Data_Structure,=(D,S),元素有限集,关系有限集,例,1,：用数据结构表示一周中的七天。,Data_Structure,=(D,S),其中，,D=,S=,Mon,Tue,Wen,Thu,Fri,Sat,Sun,1.2,基本概念和术语,（,1,）,Data_Structure,=(D,S),，其中，,D=01,，,02,，,03,，,04,，,05 ,S=,（,2,）,S=(D,R),D=,a,b,c,d,e,f,R=,解,:,上述表达式可用图形表示为：,a,e,b,c,f,d,例,2,：将下述表达式用图形的形式表示出来,集合结构,线性结构,1.2,基本概念和术语,（,3,）,Data_Structure,=(D,S),其中，,D=01,，,02,，,03,，,04,，,05,，,06,，,07 ,S=(01,02),，,(01,03),，,(01,04),，,(02,05),，,(02,06),，,(03,07),（,4,）,S=(D,R)D=,d,i,|1i5,1j5,R=,ij,d,1,d,2,d,3,d,4,d,5,01,02,03,04,05,06,07,树形结构,图状结构,1.2,基本概念和术语,逻辑结构,-,数据元素之间的逻辑关系，即结构中定义的,“关系”,。,逻辑结构可细分为,4,类：,集合结构,线性结构,树形结构,图状结构,一对一关系,一对多关系,多对多关系,非线性结构,1.2,基本概念和术语,0100,0101,物理结构,-,也称存储结构，是,数据的逻辑结构在计算机存,储器内的表示（映像）。,顺序映像,非顺序映像,特点是借助元素在存储器中的,相对位置,来表示数据元素之间的逻辑关系。,特点是借助指示元素存储地址的,指针,表示数据元素之间的逻辑关系。,例：,复数,3.0-2.3i,的存储形式,3.0,-2.3,0100,0201,0101,0201,3.0,-2.3,算法的设计取决于选定的数据（逻辑）结构,算法的实现依赖于采用的存储结构,-,顺序存储结构,-,链式存储结构,1.2,基本概念和术语,数据类型,-,是一个,值的集合,和定义在这个值集上的,一组操作,的总称。,抽象数据类型,由用户定义，用以表示应用问题的数据模型。它由基本的数据类型组成，并包含一组相关的操作。,抽象数据类型,可用,ADT=,（,D,，,S,，,P,）,三元组表示,数据对象,D,上的关系集,D,上的操作集,ADT,抽象数据类型名,数据,对象,：,数据对象的定义,数据,关系,：,数据关系的定义,基本,操作,：,基本操作的定义,ADT,抽象数据类型名,ADT,常用定义格式：,1.3,抽象数据类型的表示与实现,例：,给出自然数（,Natural Number,）,的抽象数据类型定义。,IsZero(x,):Boolean,if(x=0),返回,True,else,返回,False,Add(x,y):,NaturalNumber,if(,x+y,=,MaxInt,),返回,x+y,else,返回,MaxInt,Subtract(x,y):,NaturalNumber,if(x y),返回 0,else,返回,x-y,Equal(x,y):Boolean,if(x=y),返回,True,else,返回,False,ADT,NaturalNumber,NaturalNumber,数据对象,:,数据关系,:,数据操作,:,一个整数的有序子集合,它开始于,0,结束于机器能表示的最大整数。,1.3,抽象数据类型的表示与实现,一、算法：,算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。,二、算法的,5,个特性：,有穷性、确定性、可行性、输入和输出,三、算法设计的要求：,正确性、可读性、健壮性、效率与低存储需求,时间复杂度,空间复杂度,1.4,算法和算法分析,时间复杂度：,一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。,一个算法中语句的执行次数称为语句频度或时间频度，记为,T(n,),。,算法中基本操作重复执行的次数是,问题规模,n,的某个函数，算法的时间量度记作,T,（,n,）,=O,（,f,（,n,）,随着问题规模的增大，算法执行时间的增长率和,f,（,n,）,的增长率相同，称为,算法的渐近时间复杂度,，简称,时间复杂度,。,1.4,算法和算法分析,从算法中选取一种对于所研究的问题来说是,基本操作,的原操作，以该基本操作,在算法中重复执行的次数,作为算法运行时间的衡量准则。,算法的时间复杂度由嵌套最深层语句的频度决定,1.4,算法和算法分析,时间复杂度,一般没有必要精确地计算出算法的时间复杂度,只要大致计算出相应的数量级即可。,3n+2=O(n),因为,3,n+2,4n,当,n2,时,6*2,n,+n,2,=O(2,n,),因为,6*2,n,+n,2,7*2,n,当,n4,例：,渐进符号,（,O,）,的定义,：,当且仅当存在一个正的常数,C,，,使得对所有的,n n,0,，有,f(n),Cg(n),，,则：,f(n,)=,O,(g(n),+,x;s,=0;,for(i,=1;i=,n;+i,),+,x;s,+=x;,for(j,=1;j=,n;+j,),for(k,=1;k=,n;+k,),+,x;s,+=x;,O,（1）,O,（n）,O,（n,2,）,算法的时间复杂度由嵌套最深的语句的频度决定的,i=1;,while(i,=n)i=i*2;,O,（log,2,n）,1.4,算法和算法分析,常数阶,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,),1.4,算法和算法分析,算法分析应用举例,算法中,基本操作重复执行的次数,是问题规模,n,的某个函数，其时间量度记作,T(n,)=,O(f(n,),，称作算法的渐近时间复杂度,(,Asymptotic Time complexity,),，简称,时间复杂度,。,一般地，常用,最深层循环内,的语句中的原操作的,执行频度,(,重复执行的次数,),来表示。,“,O”,的定义：若,f(n,),是正整数,n,的一个函数，则,O(f(n,),表示,M,0,，使得当,n,n,0,时，,|,f(n,)|,M,|f(n,0,)|,。,表示,时间复杂度,的阶有：,O(1),：常量时间阶,O(n),：线性时间阶,O(n,),：对数时间阶,O(nn,),：线性对数时间阶,O(,n,k,),：,k,2,，,k,次方时间阶,例 两个,n,阶方阵的乘法,for(i,=1,，,i=n;+i),for(j,=1;j=n;+j),cij,=0;,for(k,=1;k=n;+k),cij,+=,aik,*,bkj,;,由于是一个三重循环，每个循环从,1,到,n,，则总次数为：,nnn,=n,3,时间复杂度为,T(n,)=O(n,3,),例,+x;s=0;,将,x,自增看成是基本操作，则语句频度为，即时间复杂度为,(1),。,如果将,s=0,也看成是基本操作，则语句频度为，其时间复杂度仍为,(1),，即常量阶。,例,for(i,=1;i=n;+i),+x;s+=x;,语句频度为：,2n,，其时间复杂度为：,O(n,),，即为线性阶。,例,for(i,=1;i=n;+i),for(j,=1;j=n;+j),+x;s+=x;,语句频度为：,2n,2,，其时间复杂度为：,O(n,2,),，即为平方阶。,定理,：,若,A(n,)=a,m,n,m,+a,m-1,n,m-1,+a,1,n+a,0,是一个,m,次多项式，则,A(n,)=,O(n,m,),例,for(i,=2;i=,n;+i,),for(j,=2;j=i-1;+j),+x;,ai,j,=x;,语句频度为：,1+2+3+,+n-2=(1+n-2)(n-2)/2,=(n-1)(n-2)/2=n,2,-3n+2,时间复杂度为,O(n,2,),，即此算法的时间复杂度为平方阶。,一个算法时间为,O(1),的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为,O(n,2,),的算法则由一个二次多项式来限界。,以下六种计算算法时间的多项式是最常用的。其关系为：,O(1),O(n,),O(n,),O(nn,)O(n,2,)O(n,3,),指数时间的关系为：,O(2,n,),O(n,!),O(n,n,),当,n,取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。,有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。,例,1,：,素数的判断算法。,Void prime(,int,n),/*n,是一个正整数 *,/,int,i=2;,while(n%i)!=0&i*1.0,sqrt(n,),printf(“&d,是一个素数,n”,n);,else,printf(“&d,不是一个素数,n”,n);,嵌套的最深层语句是,i+,；其频度由条件,(n%i)!=0&i*1.0,sqrt(n,),决定，显然,i*1.01 -i),for(j=0;jaj+1),aj,aj+1;change=TURE;,最好情况：,0,次,最坏情况：,1+2+3+,+n-1=n(n-1)/2,平均时间复杂度为：,O(n,2,),1.3.4,算法的空间分析,空间复杂度,(,Space complexity,),：是指算法编写成程序后，在计算机中运行时所需存储空间大小的度量。记作：,S(n,)=,O(f(n,),其中：,n,为问题的规模,(,或大小,),该存储空间一般包括三个方面：,指令常数变量所占用的存储空间,;,输入数据所占用的存储空间,;,辅助,(,存储,),空间。,一般地，算法的,空间复杂度,指的是,辅助空间,。,一维数组,an,：空间复杂度,O(n,),二维数组,anm,：空间复杂度,O(n,*m),要求：,1,、了解数据结构的相关术语,:,数据、数据元素、数据对象、,数据类型、数据结构、数据的逻辑结构与物理结构概念,及逻辑结构与物理结构间的关系。,2,、了解算法的定义、算法的特性、算法的时间代价、算法,的空间代价。,3,、掌握计算语句频度和估算算法时间复杂度的方法。,第,1,章 总结,作业,