数据结构与算法讲解

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,数据结构与算法,主讲老师：刘斌,Email: nj_liubin,QQ,：,1263447339,课程简介,结构,:,实体,+,关系，把某些成份按一定的规律或方式组织在,一起的实体或某些成分组织在一起的方式,在这里，我们把实体看作数据,算法是对特定问题求解方法和步骤的一种描述。,大公因数的求解算法,元二次方程的求解,周长、圆面积,方体的表面积和边长,排序,治、贪心、动态规划,数据结构,+,算法,=,程序,程序：为计算机解决问题编制的指令集，是按照事先设计的功能和性能要求执行的指令序列,从程序设计的观点来看，,信息的表示：“数据结构”研究的问题,信息的处理：“算法”研究的问题,了解计算机原理、掌握程序设计的必由之路。,课程目标,学会怎样组织信息，以便支持高效的数据处理,掌握常用的数据结构及其应用,学会合理组织数据、有效地处理数据,基本掌握算法的设计与分析方法,提高程序设计能力,学会分析和研究计算机处理的数据对象的特性,掌握,常用数据结构内在的逻辑关系、在机内的存储表示,掌,握常用数据结构上的运算操作的动态性质和执行算法,.,能够为实际应用选择适当的数据结构、存储结构和相应算法；,初步掌握算法性能的分析方法。,与计算机专业其他课程的关系,建议的学习方案,听课，思考，提问，讨论,三人行，必我我师焉,学而不思则罔，思而不学则殆,不耻下问,独学而无友则孤陋而寡闻,上机,纸上得来终觉浅，绝知此事要躬行,听懂很容易，学会才是真,教材和参考书,教材：,廖明宏等，,数据结构与算法,-(,第,4,版,),，高等教育，,2007,年,11,月。,参考书：,算法与数据结构,-C,语言描述（第,2,版），,张乃孝主编，高等教育出版社,2006,1,数据结构,-C,语言版，（有配套习题集与习题解,答）严蔚敏等，清华大学出版社,数据结构算法与应用,-C+,语言描述，大量的习,题），网上,PDF,格式，翻译教材,课程资源,北大计算机系课程资源,(,包含课程的视频,C+,语言,), 6.0,要求,认真准备，有备而来；,严禁玩游戏；,及时向老师反映问题；,培养独立解决问题的能力。,第一章 绪论,1.1,数据结构的研究对象,1.2,数据结构的发展概况,1.3,抽象数据型,(ADT),1.4,算法及其复杂性,1.5,逐步求精的程序设计方法,1.6,关于描述语言,1.1,数据结构的研究对象,1.1.1,基本概念和术语,1.1.2,四种基本的数据结构,1.1.3,数据结构的研究对象,1.1.1,基本概念和术语,1.,数据,:,数据是用于描述客观事物的数值、字符，以及一切可以输入到计算机中的并由计算机程序加以处理的符号的集合。其范围随着计算机技术的发展而不断发展。,2.,数据元素,数据的基本单位是数据元素，在计算机程序中通常作为一个整体进行考虑和处理。,3.,数据项,是数据的不可分割的最小单位，一个数据元素可由若干个数据项组成。,4.,数据对象,性质相同的元素的集合叫做数据对象。,1.1.1,基本概念和术语,5.,结点,数据元素在机内的位串表示，即数据元素在计算机内的映象。,6.,域,/,字段,当数据元素由若干个数据项组成时，位串中对应于各个数据项的子串称为域,/,字段，是数据元素中数据项在计,算机中的映象。,7.,信息表,计算机程序所作用的一组数据通常称为信息表，是数据对象在计算机中的映象。,1.1.1,基本概念和术语,8.,数据结构,数据结构指的是数据元素之间的相互关系，这种关系是抽象的，即并不涉及数据元素的具体内容。是数据元素及其相互间的关系的数学描述。,9.,逻辑结构和存储结构,(1),逻辑结构,数据结构中描述的是数据元素之间的抽象关系,(,逻辑,关系,),，称为逻辑结构。,(2),存储结构,/,物理结构,数据结构在计算机中的表示（映象）称为存储结构,/,物,理结构。,1.1.1,基本概念和术语,(3),数据元素之间的关系（逻辑结构）在计算机中有两,种表示方法：顺序映象,(,表示,),和非顺序映象,(,表示,),，从而,导致两种不同的存储结构：顺序结构和链式结构。,顺序映象（表示）的特点是借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。,非顺序映象（表示）的特点是借助指示数据元素存储地址的指针来表示数据元素之间的逻辑关系。,1.1.2,四种基本的逻辑结构,1.,集合结构,结构中的数据元素之间除了,属于同一个集合的关系,之外，别无其他关系。关系比较松散，可用其他结构来表示。,2.,线性结构,结构中的数据元素之间存在一个对一个的关系，即线性关系，每个元素至多有一个直接前导和后继。,3.,树型结构,结构中的数据元素之间存在一个对多个的关系，即层次关系，即每一层上的元素可能与下层的多个元素相关，而至多与上层的一个元素相关。,1.1.2,四种基本的逻辑结构,4.,网状,/,图型结构,结构中的数据元素之间存在多个对多个的关系，即任意关系，任何元素之间都可能有关系。,一般将逻辑结构分为线性结构（,2,）和非线性结构（,1,，,3,，,4,）两种。,结构中的数据元素之间存在多个对多个的关系，即任意关系，任何元素之间都可能有关系,1.1.3,数据结构的研究对象,1.,数据对象的结构形式,各种数据结构的性质,(,逻辑结,构,);,2.,数据对象和关系在计算机中的表示,(,物理结构,/,存,储结构,);,3.,数据结构上定义的基本操作,(,算法,);,4.,算法的效率,;,5.,数据结构的应用,如数据分类,检索,.,1.2,数据结构的发展概况,1.,程序设计方法学的发展极大地促进了数据结构的发展,(1),计算机科学及其应用的发展使数据结构成为独立学科,.,(2),以数据为中心的程序设计方法推动了数据结构的发展,.,面向过程的程序设计的特点是以程序为中心，侧重于建立程序，程序在简单的数据结构上进行复杂的运算，软件设计的主要工作就是设计求解问题的过程。注重于程序设计技巧，适合于数值计算。,结构化特别是面向对象的程序设计以数据,(,结构,),为中心，系统采用复杂的数据结构来描述系统状态，程序围绕数据结构进行加工。这种编程语言更适合于非数值计算。,2.,数据结构在计算机科学中的地位,(1),是计算机科学的一门专业基础和核心课程。,(2),是学习、设计和实现操作系统、编译系统、数据库系统和,其它应用系统的重要基础。,1.3,抽象数据型,(ADT),1.3.1,抽象数据型的定义,1.3.2,数据型,数据结构和,ADT,1.3.3,抽象数据型的实现,1.3.4,多层次抽象技术,1.3.5,抽象数据型的优点,1.3.1,抽象数据型的定义,一,.,抽象数据型的定义,1.,定义,:,是一个数学模型和在该模型上定义的操作集合的,总称。,注,: ADT,是程序设计语言中数据类型概念的进一步,推广和进一步抽象。,ADT int=(x|x,Z,，,+,-,*,/,%,=,=),2.ADT,的优点,使用者只要知道这些操作的用途就可以编程序了；至于这些操作是怎样实现的，以及整型数在内存中是如何表示的，并不影响使用者所编程序的编码形式。,1.3.1,抽象数据型的定义,二,.,抽象数据型的实现,1.,抽象型实现的含义,就是将,ADT,转换成程序设计语言的说明语句，加上对,应于该,ADT,中的每个操作的函数。换句话说，就是用适当,的数据结构来表示,ADT,中的数学模型,并用一组函数来实,现该模型上的各种操作。,2.,注意事项,(1),同一数学模型上定义不同的操作集，则它们代表不,同的,ADT;,(2),把,ADT,的描述与用某种程序设计语言实现,ADT,加以,区别，这是大型程序设计中当前的发展趋势。,1.3.2,数据型,数据结构和,ADT,1.,三个概念的各自含义及相互关系,(1),各自含义,数据型是该类型变量的存储格式和所有可能取值的集合,;,数据结构则是抽象数据型中数学模型的表示,;,抽象数据型是一个数学模型及在该模型上定义的操作集的总称。,(2),相互关系,数据型是根据数据结构分类的，同类型的数据元素的数据结构相同；,数据结构是,ADT,中数学模型的表示；,ADT,是数据类型的进一步推广和进一步抽象。,2.,信息聚集的三种方式,数组、结构（体）和文件,1.3.3,抽象数据型的实现,一,.ADT,的实现原则,(1),应符合规格描述的定义；,(2),应有尽可能好的通用性；,(3),应尽可能具有良好的独立性，在结构上应成为独立,的模块；将内部细节屏蔽起来。,二,.ADT,的实现举例（,ADT,栈的带头结点的链式实现）,1),数据结构描述,enum booleanFALSE,TRUE;,struct node,elementtype val;,node *next;,;/,结点的类型,typedef node *stack;/,栈的类型,1.3.3,抽象数据型的实现,2),基本操作的实现,stack NEWSTACK(), stack s;,s=new node,；,/*s=(node *)malloc(sizeof(node);*/,s-next=NULL,；,return s;,1.3.3,抽象数据型的实现,void PUSH(elementtypeelm, stack stk),stack s;,s=new node;,s-val=elm;,s-next=stk-next;,stk-next=s;,1.3.3,抽象数据型的实现,void POP(stack stk), stack s;,if (stk-next),/*stk-next!=NULL*/,s=stk-next;,stk-next=s-next;,delete s; /* free(s) */,1.3.3,抽象数据型的实现,elementtype TOP(stack stk),if (stk-next),return (stk-next-val),；,else,return NULLELE;,1.3.3,抽象数据型的实现,boolean EMPTY(stack stk), if (stk-next),return FALSE;,else,return TRUE;,1.3.4,多层次抽象技术,1.,逐层抽象方法,对于较复杂的数据类型，先将较简单、较基本的数据类型抽象出来,给出定义；再用已定义的数据类型去定义更复杂的数据类型,完成对后者的抽象。就是说，用已定义的类型来表述正要定义的类型的定义域，并用前者的操作来表述后者的操作这就是所谓逐层抽象的方法。,逐层抽象实质是用已知的简单数据类型定义更复杂的数据类型。,1.3.4,多层次抽象技术,2.,优点,(1),由于在定义高层数据类型时不必考虑低层数据类型及其操作的内部细节,因而对复杂数据类型进行抽象可以简化许多琐事。,(2),多层次抽象化通常可以采用自底向上的方式进行，先抽象出最基本的数据类型，然后利用它们定义上一层数据类型，如此逐层向上，直至到达最高层的数据类型为止,这样可以防止低层次倒过来引用高层数据类型，保证整个系统的有序层次结构。,3.,缺点,多层次抽象化的最终目的是建立最高层的数据类型，因此低层应该服从高层的要求。自底向上方式是底层的抽象带有一定的盲目性，在抽象过程中，可能从高层返回低层作修正，也就是不得不穿插一些自顶向下的过程。,1.3.5,抽象数据型的优点,采用抽象数据型的方法进行软件（特别是大型软件）系统的设计，具有许多明显的优点：,首先，它降低了软件设计的复杂性。,其次，抽象数据型可提高程序的可读性和可维护性。,第三，由于抽象数据型的使用降低了程序的复杂度，使程序的各部分相对分离，因而程序的正确性容易得到保证。,第四，有利于软件重用。,1.4,算法及其复杂性,1.4.1,算法及其性能评价准则,1.4.2,算法时间复杂性分析方法,1.4.1,算法及其性能评价准则,一、算法、算法的特征和算法描述,算法（,Algorithm,）：是对特定问题求解步骤的一种描述，它是指,令（规则）的有限序列，其中每一条指令表示一个或多个操作。,算法的特征：,有穷性、确定性、能行性、输入、输出,算法描述：,自然语言；程序设计语言；类语言,；,1.4.1,算法及其性能评价准则,一、算法、算法的特征和算法描述,算法（,Algorithm,）：是对特定问题求解步骤的一种描述，它是指,令（规则）的有限序列，其中每一条指令表示一个或多个操作。,算法的特征：,有穷性、确定性、能行性、输入、输出,算法描述：,自然语言；程序设计语言；类语言,；,常用的算法设计方法：,递归法（,Recursion,）、分治法,(Divide-and Conquer),、,贪心法,(Greedy),、动态规划,(Dynamic Programming),、,搜索与遍历、回溯（,Backtracking,）、解空间局部搜索,近似算法,(Approximation),、在线算法（,On-Line,）等,1.4.1,算法及其性能评价准则,二、,好的算法的标准,1.,正确性,(Correctness),正确性的含义：是指对于一切合法的输入数据经有限时间或有限步后均可得到正确（满足规格说明要求）的结果；,算法包括两方面的内容： 解决问题的方法； 实现这一方法的一系列指令,(,语句、步骤,),算法的正确性证明：需要一组相关的引理和定理，确认一个算法所使用的方法和公式的正确性； 在证明一系列的语句确实做了符合规定的动作。,算法的正确性的严格的形式化证明还未取得突破，还是一项令人生畏的工作。只有那些比较简单的算法，其正确性才能被形式化证明。,1.4.1,算法及其性能评价准则,二、,好的算法的标准,2.,时间复杂性,(Time Complexity),如何计算和比较算法的执行时间：,实验测量法（实际执行时间、执行指令的条数）,优点：精确,缺点： 必须先运行根据算法编制的的程序；所得的时间统计量依赖于计算机的硬件、软件等环境因素，容易掩盖算法本身的优劣。,1.4.1,算法及其性能评价准则,二、,好的算法的标准,事前分析,(,估计,),法,高级语言编写的程序在计算机上运行时间取决于下列因素：,依据的算法本身选择何种策略,问题的规模（输入的规模，输入的大小）。如求素数问题,程序设计语言：算法的实现语言级别越高，执行效率越低,编译程序产生的机器代码的质量,及其执行指令的速度,表明用绝对的时间单位衡量一个算法的效率是不适合的,1.4.1,算法及其性能评价准则,二、,好的算法的标准,算法的时间复杂性, 认为一个特定的算法执行时间,(,运行工作量的大小,),，只依赖于问题的规模，即算法执行时间是问题规模的函数,由于算法的执行时间由组成算法的控制结构（顺序、分支和循环）和基本操作的综合效果，因此从算法中选择对于研究问题来说是基本的操作（基本运算）,把算法的基本操作的重复执行的次数作为算法的时间度量,通常，我们并不关心,T(n),的具体值，而是关心它的增长率,即,T(n),随问题规模,n,（是一个整数）的增大的变化趋势（界限）,算法的复杂性定义,算法中基本操作重复执行的次数是问题规模,n,的某个函数,f(n),，算法的时间度量记作,T,（,n,）,= O,（,f,（,n,）。它表示随问题规模,n,的增大，算法执行时间的增长率不会超过,f,（,n,），称为算法的渐进时间复杂性，简称时间复杂性。,1.4.1,算法及其性能评价准则,二、,好的算法的标准,3.,空间复杂性,(Space Complexity),算法的空间复杂性是指算法在执行过程中的存储量需求,一个算法的存储量需求除了存放算法本身所有的指令、常数、变量和输入数据外，还包括对数据进行操作的工作单元和存储实现计算所需信息的辅助空间,算法的存储量需求与输入的规模、表示方式、算法采用的数据结构、算法的设计以及输入数据的性质有关,算法的执行的不同时刻，其空间需求可能是不同的,算法的空间复杂性是指算法在执行过程中的最大存储量需求,空间复杂性的渐进表示,-,空间复杂度,T,（,n,）,= O,（,f,（,n,） 其中，,n,为问题的输入规模,1.4.1,算法及其性能评价准则,二、,好的算法的标准,4.,可读性,(Readability),可读性好的算法有助于设计者和和他人阅读、理解、修改和重用,晦涩难懂的算法不仅容易隐藏错误，而且还增加了阅读,难度,可读性好的算法，常常也具有简单性,5.,健壮性,(Robustness),当输入数据非法时，能作出适当的反应（如对输入数据进行语法检查，提出修改输入建议并提供重新输入的机会），避免异常出错,6.,一个好的算法还应该具有灵活性（,Flexibility,）、可重用性,(Reuseabale),和自适应性,(Adaptability),等,1.4.2,算法时间复杂性分析方法,一、算法的时间复杂性,定义,1.1,设一个领域问题的输入的规模为,n,，,D,n,是该领域问题的所有输入集合，任意一个输入,I,D,n,是,P(I),是,I,出现的概率，,I,D n,P(I)=1,，,T(I),是（解决该领域问题的）算法在输入,I,下所执行的基本运算的次数。,称,E(n)=,I D n,P(I)* T(I),为该算法的期望复杂性（平均时间复杂性）,称,W(n)=max,I D n, T(I),为该算法的最坏时间复杂性,1.4.2,算法时间复杂性分析方法,一、算法的时间复杂性,例,1.1,A,是一个由,n,个不同元素的实数数组，给出求其最大和最小元素的算法和时间复杂性,void SM(double A, int n, double &max, double &min ), max=min=A0;,for ( k=1; kmax ) max=Ak;,if ( Akmin ) min=Ak;,容易看出，算法,SM,对大小为,n,的数组需要,2,（,n-1,）比较，算,法,SM,的基本运算是元素比较，则复杂性为,2,（,n-1,）,1.4.2,算法时间复杂性分析方法,一、算法的时间复杂性,例,1.2,A,是一个由,n,个不同元素的实数数组，给出确定给定实数,K,是否在,A,中的算法及其时间复杂性,int SK(double A, int n, double K ), int j=0;,while ( jn),if ( Aj=K ) break;,else j+;,return j ;/,若,j n,，则,K,在,A,中，否则,(j=n) K,不在,A,中,1.4.2,算法时间复杂性分析方法,一、算法的时间复杂性,算法,SK,的基本运算是元素与,K,的比较,假定,q,表示,K,在,A,中的概率，有假设,K,等于,A,的每个元素有相,同的概率。令,D,n,= I,0, I,1, I,n-1, I,n,，其中,I,j,( 0 j n ),表示,K=A j,的任意输入，,I,n,表示,K,不是,A,中元素的任意一个输,入，由上述说明有：当,0,j n,时，,P(I,j,)=q / n,，,T (I,j,)=j+1,，,P(I,n,)=1-q,，,T (I,n,)=n,算法,SK,的期望复杂性和最坏复杂性为,E(n)=,j D n, P(I,j,)* T(I,j,),= ,j=0,n-1, (q /n)*(j+1) + (1-q)*n,=1/2( n+1)q + (1-q)n=1/2(n+1) (K,在,A,中，,q=1),W(n)=max T(I,j,)| 0 j n = n,1.4.2,算法时间复杂性分析方法,二、函数阶的比较,定义,1.2,设,f(n),、,T(n),是整数集到实数集上的函数，称,函数,f(n ),是,T(n),增长率的上界，当且仅当存在一个正常数,C,和整数,n,0,，使得对任意的,n n,0,时，有,T (n) C f(n),记作：,T(n)= O(,f(n),此时也称,T(n),的阶至多为,f(n),*一个算法的时间复杂性为,O(,f(n),，表明它的基本操作次,数至多是,f(n),的某个常数倍,例,1.3,设函数,T(n)=3n,5,+4n,2,+1,，证明：,T(n)=(n,5,),证明：,f(n)= n,5,.,取,n,0,=0, C=8,则当,n n,0,时有,T(n)= 3n,5,+4n,2,+18n,5,= C f(n),证毕,1.4.2,算法时间复杂性分析方法,二、函数阶的比较,定义,1.3,设,f(n),、,T(n),是整数集到实数集上的函数，称,函数,f(n),是,T(n),增长率的下界，当且仅当存在一个正常数,C,和整数,n,0,，使得对任意的,n n,0,时，有,T ( n ) C f( n ),，,记作：,T(n)=,(f(n),此时也称,T(n),的阶至少为,f(n),*一个算法的时间复杂性为,(f(n),，表明它的基本操作,次数至少是,f(n),的某个常数倍,例,1.4,设函数,T(n)=3n,5,+4n,2,+1,，证明：,T(n)=,(n,5,),证明：,f(n)= n,5,.,取,n,0,=0, C=1,则当,n n,0,时有,T(n)= 3n,5,+4n,2,+1 1*n,5,= C f(n),证毕,1.4.2,算法时间复杂性分析方法,定理,2.1,若,A(n)=a,m,n,m,+a,1,n+a,0,是关于,n,的,m,次多项式，则,A(n)=(n,m,),*,此定理说明，时间复杂性仅取决于多项式的最高次幂，而与最高次幂的系数和其他低次项无关,(1),表示时间复杂性为常数,常见的时间复杂性及其比较,(,1,), ,(,n),(,n),(n),(nn), ,(n,2,),(n,3,),(,2,n,),1.4.2,算法时间复杂性分析方法,1.4.2,算法时间复杂性分析方法,三、时间复杂性的运算法则,设,T,1,(n)=O( f(n) ),，,T,2,(n)=O( g(n) ),，则,加法规则：,T,1,(n)+T,2,(n) = O( max f(n), g(n) ),乘法规则：,T,1,(n)+T,2,(n) = O( f(n) g(n) ),1.4.2,算法时间复杂性分析方法,例,1.5,：,s = 0 ;, f(n) = 1; T,2,(n) = O(f(n) = O(1),常量阶,for ( i=1 ; i = n ; +i ) +x; s += x; , f(n) = 3n+1; T1(n) = O(f(n) = O(n),线性阶,for ( i=1; i=n ; +i ),for( j=1 ; j =n ; +j ) +x ; s += x; , f(n) = 3n,2,+2n+1; T3(n) = O(f(n) = O(n2),平方阶,for ( i=1; i=n ; +i ),for ( j=1 ; j =n ; +j ), cij = 0;,for ( k=1 ; k 1,else,return( n * fact( n 1 ) );,T( n ) = G +f( n 1),T( n 1) = G+ f( n 2),T( n 2) = G + f( n 3),T( 2 ) = G + f( 1 ),+ T( 1 ) = C,T( n ) = G,（,n-1,）,+ C,1.5,逐步求精的程序设计方法,1.5.1,如何求解一个问题,一,.,算法的定义,1.,计算能由一个给定的计算模型机械地执行的规则,(,或步骤,),序列称为该计算模型的一个计算,.,注,:,一个计算机程序是一个计算,(,计算模型是计算机,);,计算可能永远不停止,不是算法,.,2.,算法是一个满足下列条件的一个计算：,(1),有穷性,/,终止性：总是在执行有穷步后停止,;,(2),确定性：每一步必须有严格的定义和确定的动作,;,(3),能行性：每个动作都能被精确地机械执行,;,(4),输入：有,0,个和多个满足约束条件的输入,;,(5),输出：有一个或多个满足约束条件的结果,.,1.5,逐步求精的程序设计方法,1.5.1,如何求解一个问题,一,.,算法的定义,1.,计算能由一个给定的计算模型机械地执行的规则,(,或步骤,),序列称为该计算模型的一个计算,.,注,:,一个计算机程序是一个计算,(,计算模型是计算机,);,计算可能永远不停止,不是算法,.,2.,算法是一个满足下列条件的一个计算：,(1),有穷性,/,终止性：总是在执行有穷步后停止,;,(2),确定性：每一步必须有严格的定义和确定的动作,;,(3),能行性：每个动作都能被精确地机械执行,;,(4),输入：有,0,个和多个满足约束条件的输入,;,(5),输出：有一个或多个满足约束条件的结果,.,1.5,逐步求精的程序设计方法,1.5.1,如何求解一个问题,一,.,算法的定义,3.,算法的逐步求精,就是对用自然语言等描述的算法逐步细致化、精确化和,形式化，追求的目标是把算法变成可以执行的程序。,1.5,逐步求精的程序设计方法,1.5.1,如何求解一个问题,二,.,求解问题的一般过程,1.,模型化：对实际问题进行分析，选择适当的数学模型来描述问题，即模型化,;,2.,确定算法：根据模型，找出解决问题的方法,(,算法,);,3.,逐步求精：就是对用自然语言等描述的算法逐步细致化、精确化和形式化，这一阶段可能包括多步求精。当逐步求精到某一步时，根据程序中所使用的数据形式，定义若干,ADT,，并且用,ADT,中的操作代替对应的非形式语句；,4.ADT,的实现：对每个,ADT,，选择适当的数据结构表示数学模型，并用相应的函数实现每个操作。,1.5,逐步求精的程序设计方法,1.5.2,算法逐步求精,例,1.7,交叉路口的交通安全管理问题,问题描述：,一个具有多条通路的交叉路口,当允许某些通路上,的车辆在交叉路口拐弯时,必须对其他一些通路上,的车辆加以限制,不允许同时在交叉路口拐弯,以免,发生碰撞,.,所有这些可能的拐弯组成一个集合,.,有,5,条组成的交叉路口,其中有,2,条路是单行道,把从一条路到另一条路的通路称为拐弯,有的拐弯可以同时通过,有些拐弯不能同时通过,共有,13,个拐弯,.,要求,:,(1),设置一组交通灯,实现安全管理,(2),使交通灯的数目最少,.,基本要求：把这个集合分成尽可能少的组,使得每组中所有的拐弯都能同时进行而不发生碰撞,.,这样,每组对应一个指挥灯,因而实现了用尽可能少的指非灯完成交叉路口的管理,.,1.5,逐步求精的程序设计方法,1.5.2,算法逐步求精,模型化：,(1),用图作为交叉路口的数学模型,;(2),每个拐弯对应图中的一个顶点,;(3),若两个拐弯不能同时进行,则用用一条边把这两个拐弯所对应的两个结点连接起来,并且说这两个顶点是相邻的。,1.5,逐步求精的程序设计方法,1.5.2,算法逐步求精,确定算法：,(1),穷举法,;(2),试探法,(,3),贪心法,贪心算法的思想是首先用第一种颜色对,图中尽可能多的顶点着色,(,尽可能多表现,出贪心,),然后用第二种颜色对余下的顶点中,尽可能多的顶点着色如此等等，直至所有,的顶点都着完色。,当用一种新颜色对余下的顶点着色时我们采取下列步骤,:,（,1,）选取某个未着色的顶点，并且用新颜色对它着色。,（,2,）扫描所有未着色的顶点集，对其中的每个顶点，确定它是否与已着新颜色的任何顶点相邻。若不相邻，则用新颜色对它着色。,1.5,逐步求精的程序设计方法,1.5.2,算法逐步求精,用,C+,语言描述的,贫心,算法如下,:,void greedy(GRAPH G, SET newclr),/*,类型,GRAPH,和,SET,有待具体说明*,/,/*,本程序把,G,中可以着同一色的顶点放入,newclr*/, (1) newclr=F,(2) while (G,中有未着色的顶点,v),(3) if(v,不与,newclr,中的任何顶点相邻,),(4),对,v,着色；,(5),将,v,放入,newclr,；,;,其中，,G,是被着色的图，,newclr,的初值为空，算法执行的结果形成可以着相同颜色的顶点的集合,newclr,。只要重复调用,greedy,算法，直到图中的所有顶点都被着色为止，即可求出问题的解。,1.5,逐步求精的程序设计方法,1.5.2,算法逐步求精,逐步求精：第一步求精：,void greedy(GRAPH G, SET newclr) /*,类型,GRAPH,和,SET,有待具体说明*,/, int found;,(1) newclr=F ;,(2) while(G,中有未着色的顶点,v),(3.1) found=0;/*found,的初值为,false*/,(3.2) for (newclr,中的每一个顶点,w,）,(3.3) if(v,与,w,相邻,),(3.4) found=1;,(3.5) if(found=0) /*v,与,newclr,中的任何顶点都不相邻*,/,(4),对,v,着色；,(5),将,v,放入,newclr,；, ;,1.5,逐步求精的程序设计方法,1.5.2,算法逐步求精,逐步求精：第二步求精：,void greedy(GRAPH G, SET newclr), int found; newclr=%; v=G,中第一个未着色的顶点；,while (v!=0) /*G,中还有未着色的顶点,v*/,found=0; w=newclr,中的第一个顶点；,while(w!=0) /*newclr,中的顶点还没取尽*,/,if(v,与,w,相邻,) found=1;,w=newclr,中的下个顶点；,;,if(found=0),对,v,着色；将,v,放入,newclr,；,v=G,中下一个未着色的顶点；, ;,1.5,逐步求精的程序设计方法,1.5.2,算法逐步求精,逐步求精：第三步求精：,由上一步求精的结果可见，算法中大部分操作都归结为对图和集合的操作。设,G,和,S,分别是抽象数据型,GRAPH,和,SET,的实例，我们在,G,上规定如下操作：,(1)FIRSTG(G),返回,G,中的第一个未加标记的（未着色的）元素；若,G,中没有这样的元素存在，则返回,NULL,。,(2)EDGE(v,w,G),若,v,和,w,在,G,中相邻，则返回,true,，否则返回,false,。,(3)MARK(v,G),标记,G,中的元素,v,。,(4)ADDG(v,G),将元素,v,放入,G,中。,(5)NEXTG(G),返回,G,中下一个未标记得元素，若,G,中没有这样的元素存在，则返回,NUL,。,在,S,上规定如下操作：,(1)MAKENULL(S),将集合,S,置空。,(2)FIRSTS(S),返回,S,中的第一个元素；若,S,为空集，则返回,NULL,。,(3)NEXTS(S),返回,S,中的下一个元素；若,S,中没有下一个元素，则返回,NULL,。,(4)ADDS(v,S),将,v,放入,S,中。,1.5,逐步求精的程序设计方法,1.5.2,算法逐步求精,逐步求精：第三步求精：,void greedy(GRAPH G, SET newclr) /*,类型,GRAPH,和,SET,有待说明*,/, int found; elementtype v,w;/*elementtype,可以自定义*,/,MAKENULL(newclr); v=FIRSTG(G);,while(v!=NULL),found=0; w=FIRSTS(newclr);,while(w!=NULL),if(EDGE(v,w,G) found=1;,w=NEXTS(newclr);,;,v=NEXTG(G);,;,1.5,逐步求精的程序设计方法,1.5.2,算法逐步求精,ADT,的实现：,按上述函数，最后一步工作就是给出类型,elementtype,的定义和实现抽象数据型,GRAPH,及,SET,。此后，上述函数就是可执的程序了。,1.6,关于描述语言,