算法与程序设计基础

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数据库系统概论国脉信息学院,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,数据库系统概论国脉信息学院,第,2,章,算法与程序设计基础,2.1,算法,2.2,程序设计方法与风格,2.3,结构化程序设计,2.4,面向对象的程序设计,2.5,小结,2.1,算法,2.2.1,算法的基本概念,2.2.2,算法的复杂度,2.1.1,算法的基本概念,1,算法的定义,算法,是指对解题方案的准确而完整的描述，即解决问,题的操作步骤。,算法,不等于,数学上的,计算方法,，也,不等于程序,。,在用计算机,解决实际问题时,，往往,先设计算法,，,然后,再用具体的程序设计语言描述此算法（即,编程,）。,在编程时，由于要受到计算机系统运行环境的限制，,程序的编制通常不能优于算法的设计,。,2,算法的基本特征,可行性,确定性,有穷性,拥有足够的情报,操作步骤为有限个，,每个步骤都能在有限时间内完成。,算法执行应当能够得出满意的结果，,即必须有一个或多个输出。,对算法中每一步的描述都是明确的，没有多义性，,只要输入相同，初始状态相同，则无论执行多少遍，所得的结果都应该相同。,算法在拥有足够的输入信息和初始化信息时，,才是有效的。,3.,算法的基本要素,算法的功能取决于两个方面因素：,选用的操作,和,各个操作之间的顺序,一个算法通常由,两种基本要素,组成,对数据对象的运算和操作,算法的控制结构,，即运算或操作间的顺序。,4,类基本的运算和操作,运算类型,操 作,例 子,算术运算,+,、,、,2+3,、,8,2,逻辑运算,与（）、或（,|,）、非（！）,！,1,、,1|0,、,1&1,关系运算,、,b,、,a=c,、,bc,数据传输,赋值、输入、输出,A=0,、,b=3,算法的控制结构,算法的控制结构是算法中,各个操作之间的执行顺序,。,算法,一般,由顺序,、,选择,（又称分支）和,循环,（又称重复）,3,种基本结构组合而成,。,描述算法的工具,有,传统的流程图,、,N-S,结构化流程图,和,算法描述语言,等。,顺序结构流程图,A,B,图中,A,和,B,两个框是顺序执行的，即在执行完,A,框所指定的操作后，必然接着执行,B,框所指定的操作。,顺序结构是最简单的一种基本结构,选择结构流程图,选择结构根据给定的条件,P,是否成立而选择执行,A,框或,B,框。无论,P,条件是否成立，只能执行,A,框或,B,框之一，不可能既执行,A,框又执行,B,框。,无论走哪一条路径，在执行完,A,或,B,之后，都脱离本选择结构。,A,或,B,两个框中可以有一个是空的，即不执行任何操作。,A,B,P,P,A,当型（,While,型）循环结构的流程图,当型循环结构的功能是当给定的条件,P,成立时，执行,A,框操作，执行完,A,后，再判断条件,P,是否成立，如果仍然成立，再执行,A,框，如此反复执行,A,框，直到某一次,P,条件不成立为止，此时不执行,A,框，脱离本循环结构,直到型（,Until,型）循环结构,直到型循环结构的功能是先执行,A,框，然后判断给定的,P,条件是否成立，如果,P,条件不成立，则再执行,A,，然后再对,P,条件进行判断，如果,P,条件仍然不成立，又执行,A,，如此反复执行,A,，直到给定的,P,条件成立为止，此时不再执行,A,，脱离本循环结构。,三种结构的,N-S,结构化流程图,顺序结构的,N-S,图,选择结构的,N-S,图,当型循环结构,直到型循环结构,P,成立 不成立,A B,当,p,成立,A,A,直到,p,成立,4.,算法基本设计方法,常用的几种算法设计方法有,列举法,、,递推法,、,递归,法,、,贪婪法,、,分治法,和,动态规划法,等。,2.1.2,算法的复杂度,一个,算法,的,质量,可以,用算法,的,复杂度来衡量,。,算法的复杂度包括,算法的,时间复杂度,和算法的,空间复杂度,两种。,1,算法的时间复杂度,算法的时间复杂,度是指,执行算法所需要计算工作量,。,算法执行程序的,具体时间和,算法的,时间复杂度并不是一致的,。,算法的计算工作量是,用算法所执行的基本运算次数来度量的,，而算法所执行的基本运算次数是所要解决的问题的规模（通常用整数,n,表示）的函数,算法的工作量,=f(n),，其中整数,n,表示要解决的问题的规模。,算法的时间复杂度举例,第一个程序段如下：,x+,；,s=0,在这个程序段中，基本运算“,x+”,只,执行了一次,这个程序段的,时间复杂度,为,O(1),。,算法的时间复杂度举例,第二个程序段如下：,for,（,i=1,；,i=n,；,i+,）,x+,；,s+=x,；,/*,一个简单的,for,循环，循环体内操作执行了,n,次*,/,在这个程序段中，由于有一个循环，所以基本运算“,x+”,执行了,n,次,。,这个程序段的,时间复杂度,为,O(n,),。,算法的时间复杂度举例,第三个程序段如下：,for,（,i=1,；,i=n,；,i+,）,for,（,j=1,；,j=n,；,j+,）,x+,；,s+=x,；,/*,嵌套的双层,for,循环，循环体内操作执行了,n,2,次*,/,在这个程序段中，是一个嵌套的双层循环，所以基本运算“,x+”,执行了,n,2,次,。,这个程序段的时间复杂度,O(n,2,),。,2,算法的空间复杂度,算法的空间复杂度,是指,执行,这个,算法所需要的内存空间,。,算法执行期间所需要的存储空间包括,3,部分：,输入数据所占,的存储空间、,程序本身所占,的存储空间、,算法执行过程中,所需要的额外空间。,2.2,程序设计方法与风格,程序设计,是指,设计,、,编制,、,调试程序,的,方法和过程,。,程序设计,并不等同于,通常意义上的,编程,。,优先考虑清晰性，效率第二,程序的质量,主要,受到,程序,设计方法,、,技术,和程序,设计风格,等因素的,影响,。,本节主要介绍程序设计风格,(,也可看成程序设计时应遵循的一组规范,),程序设计由多个步骤组成，编程只是程序设计整个过程中的一小步。,(1),下列叙述中，不符合良好程序设计风格要求的是,(,A,),A),程序的效率第一，清晰第二,B),程序的可读性好,C),程序中要有必要的注释,D),输入数据前要有提示信息,(2),结构化程序设计主要强调的是,(,B,)A),程序的规模,B),程序的易读性,C),程序的执行效率,D),程序的可移植性,(3),在设计程序时，应采纳的原则之一是,(,A,),A),程序结构应有助于读者理解,B),不限制,goto,语句的使用,C),减少或取消注解行,D),程序越短越好,程序设计规范,源程序文档化,数据说明的方法,语句的结构,输入和输出,源程序,文档化,语句的,结构,程序设计规范,数据说明,的方法,输入和,输出,1,源程序文档化,源程序文档化,是指在源程序中可包含一些,内部文档,，以,帮助阅读和理解源程序,。,对源程序文档化的过程中，应考虑,符号名的命名,、,程序注释,、,视觉组织等,问题。,命名应具有一定的实际含义,在程序中添加一些空格、空行和缩进等，使人们在视觉上对程序的结构一目了然。,程序注释,在源程序中添加正确的注释,可以帮助理解程序,。,程序,注释,可以,分为,序言行注释,和,功能性注释,。,序言性注释,位于,程序的,起始部分,，,说明整个程序模块的功能,。,功能性注释,一般,嵌套在源程序,语句,内,，主要,描述相关语句或程序段的功能,。,2,数据说明的方法,为使程序中的,数据说明易于理解和维护,，可采用,次序应规范化、变量安排有序化和使用注释等数据说,明风格。,3,语句的结构,为使程序简单易懂，,语句构造,应该,简单直接,，每条,语句都能直截了当地反映程序员的意图，不能为了提高,效率而把语句复杂化。,4,输入和输出,设计好的程序能否被用户接受，往往取决于输入和,输出的风格。输入和输出的方式和格式应,尽量友好,，,方,便用户使用,。,2.3,结构化程序设计,2.3.1,结构化程序设计方法的重要原则,2.3.2,结构化程序的基本结构与特点,2.3.3,结构化程序设计的注意事项,2.3.1,结构化程序设计方法的重要原则,结构化程序设计方法的,重要原则,是：,自顶向下,逐步求精,模块化,限制使用,goto,语句,程序设计时，应先考虑总体，后考虑细节；,先考虑全局目标，后考虑局部目标。,对复杂问题，应设计一些子目标做过渡，逐步细化。,模块化就是把程序要解决的总目标分解为分目标，,再进一步分解为具体的小目标，,把每个小目标称为一个模块。,程序中大量使用,goto,语句，会导致程序结构的混乱，滥用,goto,语句对程序结构有害，应尽量避免使用。,2.3.2,结构化程序的基本结构与特点,1,顺序结构,按照程序语句行的先后顺序，一条语句接着一条语句地执行程序。,2,选择结构,选择结构又称分支结构,包括简单选择和多分支选择结构,可根据条件，判断应该选择哪一条分支来执行相应的语句序列。,3,重复结构,重复结构又称循环结构，,可根据给定条件，判断是否需要重复执行某一相同或类似的程序段，该程序段称为循环体,;,利用重复结构可以大量简化程序行,;,主要有两类循环结构，它们是当（,WHILE,）型循环结构和直到（,UNTIL,）型循环结构。,下面描述中，符合结构化程序设计风格的是,(,A,)A),使用顺序、选择和重复（循环）三种基本控制结构表示程序,的控制逻辑,B),模块只有一个入口，可以有多个出口,C),注重提高程序的执行效率,D),不使用,goto,语句,(2),结构化程序设计方法的主要原则可以概括为自顶向下、逐步求,精、,_,和限制使用,goto,语句。答：,模块化,(3),结构化程序所要求的基本结构不包括,(,B,),A),顺序结构,B)GOTO,跳转,C),选择（分支）结构,D),重复（循环）结构,2.3.3,结构化程序设计的注意事项,使用程序设计语言中的三种控制结构表示程序的控,制,逻辑,选用的控制结构只允许有一个入口和一个出口,复杂结构应该用嵌套的基本控制结构进行组合嵌套来,实现,语言中所有没有的控制结构，应该采用前后一致的方,法来模拟,严格控制,goto,语句的使用。,2.4,面向对象的程序设计,2.4.1,面向对象方法的基本概念,2.4.2,面向对象方法的优点,2.4.1,面向对象方法的基本概念,1,对象（,Object,）,对象,是面向对象方法中最基本的概念，它可以用来表示,客观世界中,的,任何实体,。,例：书本，课桌，老师，学生等,2,类和实例,类,是,具有共同属性、共同方法的对象的集合,，是关于,对象的抽象描述，它描述了属于该对象类型的所有对,象的性质。,例：教师类,(,类,),教师,(,实例,),任何一个具体对象都是该对象所属类的一个具体实例,，,即一个对象是其对应类的一个实例。,3,消息,消息,是一个实例与另一个实例之间传递的信息。,它统一了数据流和控制流,;,一个对象通过向另一个对象发送消息来请求其服务,;,消息只包含传递者的要求，它告诉接受者需要做哪些处理，并不指示接受者怎样去完成这些处理。,4,继承,继承,是指能够直接获得已有的性质和特征，而不必重,复地定义它们。,继承具有传递性,，,如果类,Z,继承类,Y,，类,Y,继承类,X,，则类,Z,继承类,X,。,一个类继承它上层的全部基类的特性,5,多态性,对象根据所接收的信息而做出动作，,同样的消息被不同的对象接收时可导致完全不同的行为,，该现象称为多态性。,(1),下面概念中，不属于面向对象方法的是,(,D,)A),对象,B),继承,C),类,D),过程调用,(2),在面向对象方法中，一个对象请求另一对象为其服务的方式是,通过发送,(,D,)A),调用语句,B),命令,C),口令,D),消息,(3),下面对对象概念描述错误的是,(,A,)A),任何对象都必须有继承性,B),对象是属性和方法的封装体,C),对象间的通讯靠消息传递,D),操作是对