数据结构和算法--概论.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2017/1/22,#,第一章 概论,第一章 概论,一、教学内容：,1,、数据结构基本概念,数据,、数据元素、数据对象、数据类型和数据结构等概念,2,、算法及算法分析,算法,的概念及特征；衡量算法的性能标准；,时间空间复杂,度度量,2,第一章 概论,二、教学要求,：,1,、,了解,数据,、,数据元素,、,数据对象,、,数据类型,、,数据结构,、数据的,逻辑结构,与数据的,物理结构,概念及逻辑结构与物理结构间的,关系,2,、,了解算法的,定义,、算法的,特性,、算法的,时间代价,、算法的,空间代价,3,、,掌握计算语句频度和估算算法时间复杂度的,方法,3,第一章 概论,1.,0,什么是数据结构,1.1,数据结构的基本概念,1.3,算法和算法分析,1.0,什么是,数据结构,一、为什么要学习,数据结构,？,电子计算机的主要用途：,早期：,主要,用于,数值,计算。,后来：,处理逐渐扩大到,非数值,计算,领域,(,能,处理多种复杂的具有一定结构关系的,数据,),。,5,数值计算解决问题的一般步骤：,数学模型,选择计算机语言,编出程序,测试,最终,解答,数值计算,的关键是,：如何得出,数学模型,(,方程,),？,程序设计,人员比较关注,程序设计的技巧,。,非数值计算问题：,数据,元素之间的相互关系一般,无法,用数学,方程式加以描述,解决问题的关键,：,合适的,数据结构,及,有效的,算法,6,数据结构讨论的范畴,。,尼克莱斯,沃思,(,Niklaus,Wirth,),在,计算机领域人尽皆知的,名言,Algorithm+Data Structures=Programs,程序设计,：,算法,：,数据结构,：,为计算机处理问题,编制一,组指令集,处理问题的策略,问题的数学模型,7,非,数值计算问题,：,例,1,电话号码查询,问题,(1),按,顺序存储方式,：,8,需遍历表,要,写出,好,的,查找,算法，取决于这张表的,结构,及,存储方式,。,电话号码表的结构和存储方式,决定,了,查找,(,算法,),的,效率2),按姓氏索引方式,：,索引,线性表结构,非,数值计算问题,：,例,2,田径赛,的时间安排,问题：,无向图,的着色,问题,设有,六个,比赛项目，,规定,每个选手至多可参加,三个,项目，有,五人,报名参加,比赛,(,如下,表所,示,),设计,比赛日程表，使得在尽可能,短,的时间内完成比赛,。,姓名,项目,1,项目,2,项目,3,丁一,跳高,跳远,100,米,马二,标枪,铅球,张三,标枪,100,米,200,米,李四,铅球,200,米,跳高,王五,跳远,200,米,9,非数值计算问题：,田径赛,的时间安排问题,解法,设用如下六个不同的代号代表不同的项目：,跳高,跳远,标枪 铅球,100,米,200,米,A B C D E F,用,顶点,代表比赛,项目,不能,同时进行比赛的项目之间连上一条,边,。,某选手比赛的项目必定有,边,相连,(,不能,同时,比赛,),10,姓名,项目,1,项目,2,项目,3,丁一,A,B,E,马二,C,D,张三,C,E,F,李四,D,F,A,王五,B,F,比赛时间,比赛项目,1,A,，,C,2,D,，,E,3,B,4,F,只需安排,四个,单位时间进行比赛,11,韦尔奇,.,鲍威尔（,Welch Powell),方法,：,1.,将,图,G,中的结点按,度,递减的顺序排列。,2.,用,没有用过的颜色对第一个点着色，并且按排列次序，对与前面着色点,不相邻,的点着相同颜色。,3.,从,序列中删除第,2,步着过色的点,。,4.,重复,第,2,、,3,步，直到序列为空,。,12,执行算法第,1,步结果为：,结点按,度,递减的顺序排列,F,A,E,B,C,D,重复执行第,2，3,步序列变化为：,A,E,B,C,D,E,B,D,B,图,的变化为：,13,求解,非数值计算的问题：,主要考虑,的是设计出合适的,数据结构,及相应的,算法,。,即：,首先要考虑对相关的各种信息如何,表示,、,组织,和,存储,？,因此，可以认为：,数据结构,是一门研究非数值计算的程序设计问题中,计算机的操作对象以及它们之间的关系和操作的学科,。,14,学习数据结构有什么用？,答：,计算机内的数值运算依靠方程式，而,非数值,运算,(,如,表,、,树,、,图,等,),则,要依靠,数据结构,。,同样的数据对象,，用,不同的数据结构,来表示，运算,效率,可能有明显的差异。,程序设计的,实质,是对实际问题选择一个,好的数据结构,，加之设计一个,好的算法,。,而好的,算法,在很大程度上取决于描述实际问题的,数据结构,。,二、数据结构课程的形成和发展,：,形成阶段：,60,年代初期，“数据结构”有关的内容散见于,操作系统,、,编译原理,和,表处理语言,等课程。,1968,年，“,数据结构,”被列入美国一些大学计算机科学系的教学计划。,发展阶段：,数据结构的概念不断扩充，包括了网络、集合代数论、关系等“,离散数学结构,”的内容,。,1978,年，,我国高校陆续开设“,数据结构,”课程,。,16,三、,数据结构,课程所,处的,地位,17,1.1,数据结构的基本概念,P2,几个概念,：,数据,(Data,)：,是,对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称,。,数据,元素,(Data Element,)：,是,数据,的基本单位，在计算机程序中通常作为一个整体进行考虑和处理,。,一,个,数据元素,可由若干个,数据项,组成,。,数据项,(Data item)：,是,数据的不可分割的最小单位,。,18,数据对象,(Data Object),是性质相同的,数据元素,的集合。是,数据,的一个子集。,例如,，整数数据对象的集合可表示为,Z,0,1,2,.,，字母字符数据对象的集合可表示为,C=A,B,Z,。,例如：,学生卡片记录表,学号,姓名,性别,籍贯,电话,通讯地址,880001,丁一,男,长沙,8639000,麓山南路,327,号,880002,马二,男,北京,23456789,学院路,435,号,880003,张三,女,广州,30472589,天河路,478,号,880004,李四,男,上海,41237568,南京路,1563,号,880005,王五,女,南京,5013472,南京大学,880006,赵六,女,昆明,4089651,云南大学,数据类型,(Data Type),：,是,具有,相同,性质的,计算机数据的集合,及在该集合上的,一组,操作,。如：,整数：,-maxint,maxint,区间上的,整数,(maxint,是依赖于所使用的计算机及语言的,最大整数,),，及在这个整数集上可以进行的,加,、,减,、,乘,、,整除,及,取模,等,操作,。,20,数据的逻辑结构,集合,：,结构中的数据元素之间除了“同属于一个集合”的关系之外，别无其它关系,。,线性结构,：,结构中的数据元素之间存在一个对一个的关系。,树形结构,：,结构中的数据元素之间存在一个对多个的关系。,图形结构,：,结构中的数据元素之间存在多个对多个的关系。,数据结构,(,Data Structure,)：,数据的存储结构,逻辑结构在存储器中的映象。,数据,的存储结构是逻辑结构用计算机语言的实现；,数据,的存储结构依赖于计算机语言。,顺序存储表示,链接存储表示,索引存储表示,散列存储表示,主要用于内存的存储表示,主要用于外存,(,文件,),的存储表示,数据结构,(Data Structure,)：,数据结构定义,1：,是相互之间存在一种或多种特定关系的数据元素的集合。,形式化定义如下,：,数据结构,是一个二元组,Data_Structure,=,(D,R),其中,，,D,是数据元素的有限集合，,R,是,D,上关系的,集合,23,数据结构,(,Data Structure,)：,数据结构,定义,2：,按一定的,逻辑,关系,组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并,按某种,存储结构,把,它们存储在计算机的存储器中，并,在这些数据上,定义了一个,运算集合,。,具体来说，,数据结构,包含,三个方面,的内容，即,数据的,逻辑结构,，,数据的,存储结构,和,对数据所施加的,运算,（操作）,。,24,这三个方面的关系为：,（,1,）数据的,逻辑结构,独立于计算机，是数据本身所固有的。,（,2,）,存储结构,是逻辑结构在,计算机存储器,中的映像，必须依赖于计算机。,（,3,）,运算,是指所施加的一组操作总称。,运算的定义,直接依赖于逻辑结构,，但,运算的实现,必须依赖,于存储结构,。,25,逻辑结构,划分,方法,一、集合,结构中的数据元素除了同属于一种类型外，别无其它关系。,二、线性结构,结构中的数据元素之间存在一对一的关系。,a,1,a,2,a,3,a,4,a,5,26,三、树型结构,结构中的数据元素之间存在一对多的关系,。,b,c,d,a,h,g,f,e,树形结构抽象描述示意图,27,四、图状结构或网状结构,结构中的数据元素之间存在多对多的关系,。,3,5,4,2,1,6,图形结构抽象描述示意图,28,存储,结构,(,Storage Structure,),数据结构在计算机中的表示,(,或称,映象,),称为,数据的,存储结构,，又称为,物理结构,。,四种基本的存储方法：,（,1,）,顺序,存储方法（顺序存储结构）,（,2,）,链接,存储方法（链式存储结构）,（,3,）,索引,存储方法,（,4,）,散列,存储方法,同一种逻辑结构可采用不同的存储方法,（以上四种之一或组合），这主要考虑的是运算方便及算法的时空要求,。,29,顺序存储,结构,：,用数据,元素在存储器中,的,存储,位置,来,表示,数据元素之间的逻辑,关系,。,x,y,z,链式存储结构：,在每一个数据元素中增加一个存放地址的,指针,，用此,指针,来,表示,数据元素之间的逻辑,关系,。,x,y,z,30,数据的逻辑结构,数据的存储结构,数据的运算：,检索、排序、插入、删除、修改等,线性结构,非线性结构,顺序存储,链式存储,线性表,栈,队列,树形结构,图形结构,数据结构的三个方面：,散列存储,索引存储,串及数组,31,例：,用图形表示下列数据结构，并,指出,它们是属于,线性,结构,还,是,非线性,结构,。,（,1,）,S=(D,R),D=a,b,c,d,e,f,R=,解,：,上述,表达式可用图形表示为：,b c a e f d,故，此结构为,线性,的。,32,（2,）,S=(D,R)D=d,i,|1,i,5 R=|,i,0),n=n+;,输出,n,的值,;,一个不超过,100,次的算法,n=1;s=0;,While(n=100),s+=n;n+;,输出,n,的值,;,35,2,、算法,描述,算法具有以下五个特性,：,P5,（,1,）有穷性,一,个算法必须总是在执行,有穷步,之后结束，且每一步都在,有穷时间,内完成。,（,2,）确定性,算法,中每一条指令必须有确切的含义。不存在二义性。且算法只有,一个入口,和,一个出口,。,36,（,3,）可行性,一,个算法是,可行的,。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。,（4,）输入,一,个算法,有,0,个,或多个输入，这些输入取自于某个特定的对象集合。,（5,）输出,一,个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量,。,37,算法设计的,要求,评价一个好的算法有以下几个,标准,：,(1),正确性,(Correctness),：,算法,应满足具体问题的需求。,(2),可读性,(Readability),：,算法,应该好读。以有利于阅读者对程序的理解，便于调试和修改。,(3),健状性,(Robustness),：,算法,应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。,(4),效率与存储量,需求：,效率,指的是算法执行的时间；,存储量需求,指算法执行过程中所需要的最大存储空间。一般，这两者与,问题的规模,有关,。,38,注意：,算法和程序的,关系,P6,算法,的含义与,程序,十分相似，但二者是有,区别,的：,一,个程序不一定满足有穷性,（死循环,）,另外,，,程序中的指令必须是机器可执行的,，而算法中的指令则无此限制,。,一,个算法若用计算机语言来书写，则它就可以是一个程序,。,39,二、算法的描述和实现,算法的描述,可,采用自然语言、数学语言或约定的符号语言。,算法的实现,必须,借助程序设计语言提供的数据类型及其运算。,本课的,描述,采用,C,语言,。,P6,40,三、,算法分析,P8,算法分析的,目的,在于选择合适算法和改进算法。一个算法的,评价,主要从,时间复杂度,和,空间复杂度,来考虑,。,(,一,),时间,复杂度,1.,时间,频度,一,个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且,一个算法花费的时间与算法中语句的执行次数成正比例,，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或,时间频度,。记为,T(n),。,41,例,1：,求,下列算法段的语句频度,for(i=1,;i=n;i,+),for(j,=1;j=i;j,+),x=x+1,;,分析：,该算法为一个,二重循环,，,执行次数,为内、外循环次数相乘，但,内循环次数不固定，与外循环有关,，,因些，时间,频度,42,2.,时间,复杂度,P9,在刚才提到的时间频度中，,n,称为,问题的规模,，,当,n,不断变化时，时间频度,T(,n,),也会不断变化,。但有时我们想知道它,变化时呈现什么规律,。为此，我们引入时间复杂度概念。,一般情况下，,算法中基本操作重复执行的次数是问题规模,n,的某个函数,，用,T(,n,),表示，若有某个辅助函数,f(,n,)，,使,得当,n,趋近于无穷大时，,T(,n,),/,f(,n,),的,极限值为,不等于零的常数,，则称,f(,n,),是,T(,n,),的,同数量级函数,。记作,T(,n,)=,(f(,n,),，称,(f(,n,),为算法的,渐近时间复杂度,，简称,时间复杂度,。,例如,，若,T(,n,)=,n,(,n+,1)/2,，则,有,1/4T(,n,)/,n,2,1,，故它的时间复杂度为,(,n,2,)，,即,(,n,),与,n,2,数量级相同,。,43,算法效率的度量：采用,时间复杂,度,例,1.2,分析以下程序段的时间复杂度,for,(i=1;in;i+),y=y+1,;,for,(j=0,;j=(2*n,);,j,+),x,+;,/*,语句,1 */,/*,语句,2 */,44,分析：,语句的,频度,指的是该语句重复执行的次数。一个算法中所有语句的频度之和构成了该算法的运行时间。,语句,1,的频度是：,n-1,语句,2,的频度,是：,(n-1)(2n+1,)=2n2,-n-1,则该程序段的,时间复杂度,：,T(n,)=2n,2,-2=O(n),45,例,1.3,分析以下程序段的时间复杂度,i,=,1,;,while,(,i,=,n,),i,=,i*2,;,语句,1,的频度是：,1,设语句,2,的频度是,f,(,n,),，则有：即，,取最大值：,则该程序段的时间复杂度为：,/*,语句,1 */,/*,语句,2 */,46,例,1.4,x,=1;,for,(,i,=1;,i,=,n,;,i,+),for,(,j,=1;,j,=,i,;,j,+),for,(,k,=1;,k,=,j,;,k,+),x,+;,由于内循环的执行次数虽与规模,n,无直接关系，但与外循环的变量取值有关。因此,从内层向外层循环分析执行次数,。,47,分析算法规律可知时间频度,T(n,)=1+(1+2)+(1+2+3)+.+(1+2+3+n),=,=,=,+,=+,由于有,1/6,T(,n,)/,n,3,1,，故,时间复杂度,为,(,n,3,),。,48,常见函数的时间复杂度按数量递增排列及,增长率,常数阶,O(1),对数阶,O(log,2,n,),线性阶,O(,n,),线性对数阶,O(,n,log,2,n,),平方阶,O(,n,2,),立方阶,O(,n,3,),k,次方阶,O(,n,k,),指数,阶,O(2,n,),P9,49,(,二,),空间,复杂,度,P10,与时间复杂度类似，,空间复杂度,是指算法在计算机内执行时所需存储空间的度量。记,作,：,S,(,n,),=O,(,f,(,n,),我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似，不再赘述,。,50,本章小结,数据、数据结构等基本概念,数据结构的三个方面的内容,线性和非线性结构的逻辑特征,数据存储的四种基本方法,算法、算法的时间复杂度及其分析的简易,方法,51,算法,+,数据结构,=,程序,也就是说，程序不仅仅是算法的实现。,求解问题要设计恰当的数据结构，并把它和求解算法结合起来。,只有经过大量的实践训练，才能真正深入理解数据结构与算法的精髓，,熟练掌握各种经典,的算法和数据结构,，,更有效地组织数据、设计高效的算法，完成高质量的程序，以满足错综复杂的实际需要。,数据结构经过经运算后结构保持不变,。,作业：,书后习题,(P11,),：,1.2,，,1.3,第一章 概论自测题,复习,C,语言，重点是指针、结构类型和递归概念,53,