收藏 分销(赏)

数据结构清华大学严蔚敏PPT绪论图文.ppt

上传人:精*** 文档编号:14520159 上传时间:2026-10-05 格式:PPT 页数:35 大小:576.04KB 下载积分:10 金币
下载 相关
数据结构清华大学严蔚敏PPT绪论图文.ppt_第1页
第1页 / 共35页
数据结构清华大学严蔚敏PPT绪论图文.ppt_第2页
第2页 / 共35页


点击查看更多>>
资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,算法与数据结构,教材,:,数据结构,(C,语言版,),。严蔚敏,吴伟民 编 著。清华大学出版社。,参考文献,:,1,数据结构,。张选平,雷咏梅 编,严蔚敏 审。机械工业出版社。,2,数据结构与算法分析,。,Clifford A.Shaffer,著,张 铭,刘晓丹 译。电子工业出版社。,3 ,数据结构习题与解析,(C,语实言版,),。李春葆。,清华大学出版社。,4 ,数据结构与算法,。夏克俭 编著。国防工业出版社。,第,1,章 绪 论,目前,计算机已深入到社会生活的各个领域,其应用已不再仅仅局限于科学计算,而更多的是用于控制,管理及数据处理等非数值计算领域。计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题:信息的,表示,,信息的,处理,。,信息的表示和组织又直接关系到处理信息的程序的效率。随着应用问题的不断复杂,导致信息量剧增与信息范围的拓宽,使许多系统程序和应用程序的规模很大,结构又相当复杂。因此,必须分析待处理问题中的对象的特征及各对象之间存在的关系,这就是数据结构这门课所要研究的问题。,编写解决实际问题的程序的一般过程,:,如何用数据形式描述问题,?,即由问题抽象出一个适当的数学模型,;,问题所涉及的数据量大小及数据之间的关系,;,如何在计算机中存储数据及体现数据之间的关系,?,处理问题时需要对数据作何种运算,?,所编写的程序的性能是否良好,?,上面所列举的问题基本上由数据结构这门课程来回答。,计算机求解问题的一般步骤,1.1,数据结构及其概念,算法与数据结构,是计算机科学中的一门综合性专业基础课。是介于数学、计算机硬件、计算机软件三者之间的一门核心课程,不仅是一般程序设计的基础,而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。,数据结构的例子,姓名,电话号码,陈海,13612345588,李四锋,13056112345,。,。,例1:号码查询系统,设有一个 号码薄,它记录了N个人的名字和其相应的 号码,假定按如下形式安排:(a1,b1),(a2,b2),(an,bn),其中ai,bi(i=1,2n)分别表示某人的名字和 号码。本问题是一种典型的表格问题。如表1-1,数据与数据成简单的一对一的线性关系。,表,1-1,线性表结构,例,2,:磁盘目录文件系统,磁盘根目录下有很多子目录及文件,每个子目录里又可以包含多个子目录及文件,但每个子目录只有一个父目录,依此类推,:,本问题是一种典型的树型结构问题,如图,1-1,,数据与数据成一对多的关系,是一种典型的非线性关系结构,树形结构,。,图,1-1,树形,结构,例,3,:交通网络图,从一个地方到另外一个地方可以有多条路径。本问题是一种典型的,网状结构,问题,数据与数据成多对多的关系,是一种非线性关系结构。,佛山,惠州,广州,中山,东莞,深圳,珠海,图,1-2,网状结构,数据,(,Data,),:是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。,数据元素,(,Data Element,),:是数据的基本单位,在程序中通常,作为一个整体,来进行考虑和处理。,一个数据元素可由若干个,数据项,(,Data Item,),组成。数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。,数据对象,(,Data Object,),:是性质相同的数据元素的集合,是数据的一个子集。如字符集合,C=,A,B,C,。,基本概念和术语,数据结构,(,Data Structure,),:是指相互之间具有,(,存在,),一定联系,(,关系,),的数据元素的集合。元素之间的相互联系,(,关系,),称为,逻辑结构,。数据元素之间的逻辑结构有四种基本类型,如图,1-3,所示。,集合,:结构中的数据元素除了“同属于一个集合”外,没有其它关系。,线性结构,:结构中的数据元素之间存在一对一的关系。,树型结构,:结构中的数据元素之间存在一对多的关系。,图状结构或网状结构,:结构中的数据元素之间存在多对多的关系。,数据结构的形式定义是一个二元组:,Data-Structure=(D,,,S),其中:,D,是数据元素的有限集,,S,是,D,上关系的有限集。,例,2,:设数据逻辑结构,B=,(,K,,,R,),K=k,1,k,2,k,9,R=,,,,,,,,,,,,,,,,,,,,,画出这逻辑结构的图示,并确定那些是起点,那些是终点,数据结构的形式定义,图,1-3,四类基本,结构图,数据结构的存储方式,数据元素之间的关系可以是元素之间代表某种含义的自然关系,也可以是为处理问题方便而人为定义的关系,这种,自然或人为定义的,“关系”,称为数据元素之间的,逻辑关系,,相应的,结构,称为,逻辑结构,。,数据结构在计算机内存中的存储包括,数据元素的存储,和,元素之间的关系的表示,。,元素之间的关系在计算机中有两种不同的表示方法:顺序表示和非顺序表示。由此得出两种不同的存储结构:,顺序存储结构,和,链式存储结构,。,顺序存储结构,:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构,(,关系,),。,链式存储结构,:在每一个数据元素中增加一个存放另一个元素地址的指针,(pointer),,用该指针来表示数据元素之间的逻辑结构,(,关系,),。,例:,设有数据集合,A=3.0,2.3,5.0,-8.5,11.0,,两种不同的存储结构。,顺序结构:数据元素存放的,地址是连续的,;,链式结构:数据元素存放的,地址是否连续没有要求,。,数据的逻辑结构和物理结构是密不可分的两个方面,一个,算法的设计取决于,所选定的,逻辑结构,,而,算法的实现依赖于,所采用的,存储结构,。,在,C,语言中,用,一维数组,表示顺序存储结构,;,用,结构体类型,表示链式存储结构。,数据结构的三个组成部分:,逻辑结构,:,数据元素之间逻辑关系的描述,D_S=,(,D,,,S,),存储结构,:,数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。,数据操作,:,对数据要进行的运算。,本课程中将要讨论的三种逻辑结构及其采用的存储结构如图,1-4,所示。,数据的逻辑结构,非线性结构,集合,图状结构,有向图,无向图,树形结构,一般树,二叉树,线性结构,一般线性表,线性表推广,广义表,数组,串,受限线性表,栈和队列,图,1-5,数据逻辑结构层次关系图,图,1-4,逻辑结构与所采用的存储结构,线性表,树,图,顺序存储结构,链式存储结构,复合存储结构,逻辑结构,物理结构,数据类型,(,Data Type,),:指的是,一个值的集合,和定义在,该值集上的一组操作,的总称。,数据类型是和数据结构密切相关的一个概念。在,C,语言中数据类型有:基本类型和构造类型。,数据结构不同于数据类型,也不同于数据对象,它不仅要描述数据类型的数据对象,而且要描述数据对象各元素之间的相互关系。,数据类型,数据结构的主要运算包括:,建立,(Create),一个数据结构;,消除,(Destroy),一个数据结构;,从一个数据结构中删除,(Delete),一个数据元素;,把一个数据元素插入,(Insert),到一个数据结构中;,对一个数据结构进行访问,(Access),;,对一个数据结构,(,中的数据元素,),进行修改,(Modify),;,对一个数据结构进行排序,(Sort),;,对一个数据结构进行查找,(Search),。,数据结构的运算,抽象数据类型,(,Abstract Data Type,,简称,ADT,),:是指一个数学模型以及定义在该模型上的一组操作。,ADT,的定义仅是一组逻辑特性描述,与其在计算机内的表示和实现无关。因此,不论,ADT,的内部结构如何变化,只要其数学特性不变,都不影响其外部使用。,ADT,的形式化定义是三元组:,ADT=(D,,,S,,,P),其中:,D,是,数据对象,,,S,是,D,上的,关系集,,,P,是对,D,的,基本操作集,。,1.2,抽象数据类型,ADT,的一般定义形式是:,ADT,数据对象:,数据关系:,基本操作:,ADT,其中数据对象和数据关系的定义用伪码描述。,基本操作的定义是:,(),初始条件:,操作结果:,初始条件:描述操作执行之前数据结构和参数应满足的条件,;,若不满足,则操作失败,返回相应的出错信息。,操作结果:描述操作正常完成之后,数据结构的变化状况和 应返回的结果。,因此,必须分析待处理问题中的对象的特征及各对象之间存在的关系,这就是数据结构这门课所要研究的问题。,ADT的一般定义形式是:,数据结构不同于数据类型,也不同于数据对象,它不仅要描述数据类型的数据对象,而且要描述数据对象各元素之间的相互关系。,问题:必须先运行依据算法编制的程序;,且算法只有一个入口和一个出口。,0sqrt(n),线性结构:结构中的数据元素之间存在一对一的关系。,4 算法分析的目的是什么?算法分析的主要方面是什么?,链式存储结构:在每一个数据元素中增加一个存放另一个元素地址的指针(pointer),用该指针来表示数据元素之间的逻辑结构(关系)。,例 +x;s=0;,cij=0;,效率与存储量需求:效率指的是算法执行的时间;,2 数据结构与算法分析。,对一个数据结构进行访问(Access);,int sum=0,m,t;,算法,算法,(,Algorithm,),:是对特定问题求解方法,(,步骤,),的一种描述,是指令的有限序列,其中每一条指令表示一个或多个操作。,算法具有以下五个特性,有穷性,:一个算法必须总是在执行有穷步之后结束,且每一步都在有穷时间内完成。,确定性,:算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。,可行性,:一个算法是能行的。即算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。,1.3,算法分析初步,输入,:一个算法有零个或多个输入,这些输入取自于某个特定的对象集合。,输出,:一个算法有一个或多个输出,这些输出是同输入有着某些特定关系的量。,一个算法可以用多种方法描述,主要有:使用自然语言描述;使用形式语言描述;使用计算机程序设计语言描述。,算法和程序是两个不同的概念,。一个计算机程序是对一个算法使用某种程序设计语言的具体实现。算法必须可终止意味着不是所有的计算机程序都是算法。,在本门课程的学习、作业练习、上机实践等环节,算法都用,C,语言来描述。在上机实践时,为了检查算法是否正确,应编写成完整的,C,语言程序。,评价一个好的算法有以下几个标准,正确性,(,Correctness,),:算法应满足具体问题的需求。,可读性,(,Readability,),:算法应容易供人阅读和交流。可读性好的算法有助于对算法的理解和修改。,健壮性,(,Robustness,),:算法应具有容错处理。当输入非法或错误数据时,算法应能适当地作出反应或进行处理,而不会产生莫名其妙的输出结果。,通用性,(,Generality,),:算法应具有一般性,即算法的处理结果对于一般的数据集合都成立。,算法设计的要求,算法执行时间需通过依据该算法编制的程序在计算机上运行所消耗的时间来度量。其方法通常有两种:,事后统计,:计算机内部进行执行时间和实际占用空间的统计。,问题:必须先运行依据算法编制的程序;依赖软硬件环境,容易掩盖算法本身的优劣;没有实际价值。,事前分析,:求出该算法的一个时间界限函数。,算法效率的度量,效率与存储量需求,:效率指的是算法执行的时间;存储量需求指算法执行过程中所需要的最大存储空间。一般地,这两者与问题的规模有关。,与此相关的因素有:,依据算法选用何种策略;,问题的规模;,程序设计的语言;,编译程序所产生的机器代码的质量;,机器执行指令的速度;,撇开软硬件等有关部门因素,可以认为一个特定算法,“,运行工作量,”,的大小,只依赖于问题的规模(通常用,n,表示),或者说,它,是问题规模的函数,。,一个计算机程序是对一个算法使用某种程序设计语言的具体实现。,操作结果:描述操作正常完成之后,数据结构的变化状况和 应返回的结果。,如字符集合C=A,B,C,。,链式结构:数据元素存放的地址是否连续没有要求。,由此得出两种不同的存储结构:顺序存储结构和链式存储结构。,算法执行时间需通过依据该算法编制的程序在计算机上运行所消耗的时间来度量。,顺序结构:数据元素存放的地址是连续的;,cij=0;,对一个数据结构(中的数据元素)进行修改(Modify);,算法分析应用举例,算法中,基本操作重复执行的次数,是问题规模,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!)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,),算法的空间分析,空间复杂度,(,Space complexity,),:是指算法编写成程序后,在计算机中运行时所需存储空间大小的度量。记作:,S(n)=O(f(n),其中:,n,为问题的规模,(,或大小,),该存储空间一般包括三个方面:,指令常数变量所占用的存储空间,;,输入数据所占用的存储空间,;,辅助,(,存储,),空间。,一般地,算法的,空间复杂度,指的是,辅助空间,。,一维数组,an,:空间复杂度,O(n),二维数组,anm,:空间复杂度,O(n*m),习 题 一,1,简要回答术语:数据,数据元素,数据结构,数据类型。,2,数据的逻辑结构?数据的物理结构?逻辑结构与物理结构的区别和联系是什么?,3,数据结构的主要运算包括哪些?,4,算法分析的目的是什么?算法分析的主要方面是什么?,5,分析以下程序段的时间复杂度,请说明分析的理由或原因。,Sum1(int n),int p=1,sum=0,m;,for(m=1;m=n;m+),p*=m;sum+=p;,return(sum);,Sum2(int n),int sum=0,m,t;,for(m=1;m=n;m+),p=1;,for(t=1;t=m;t+)p*=t;,sum+=p;,return(sum);,递归函数,fact(int n),if(n=1)return(1);,else return(n*fact(n-1);,
展开阅读全文

开通  VIP、SVIP  下载更划算
下载10份以上建议开通 VIP 会员
下载20份以上建议开通SVIP会员


开通VIP      成为共赢上传

当前位置:首页 > 教育专区 > 其他

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        关注我们

©2010-2026 宁波自信网络信息技术有限公司  版权所有

客服电话:0574-28810668  投诉电话:18658249818

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :微信公众号    抖音    微博    LOFTER 

客服