c程序设计谭浩强第02章课件.ppt

2.1算法的概念算法的概念2.3算法的特性算法的特性2.4怎样表示一个算法怎样表示一个算法2.5结构化程序设计方法结构化程序设计方法第第2 2章章 程序的灵魂程序的灵魂算法算法一个程序应包括以下两方面内容一个程序应包括以下两方面内容:(1)对数据的描述。在程序中要指定数据的类型和数对数据的描述。在程序中要指定数据的类型和数据的据的组织形式组织形式，即数据结构，即数据结构(datastructure)。(2)对操作的描述。即操作步骤，对操作的描述。即操作步骤，也就是算法也就是算法(algorithm)。数据是操作的对象，操作的目的是对数据进行加工数据是操作的对象，操作的目的是对数据进行加工处理，以得到期望的结果。作为程序设计人员，必处理，以得到期望的结果。作为程序设计人员，必须认真考虑和设计数据结构和操作步骤须认真考虑和设计数据结构和操作步骤(即算法即算法)。因此，因此，Pascal之父沃思之父沃思(NikiklausWirth)提出一个提出一个公式公式:数据结构数据结构+算法算法=程序程序n实际上，一个程序除了以上两个主要要素之外，还应当采实际上，一个程序除了以上两个主要要素之外，还应当采用结构化程序设计方法进行程序设计，并且用某一种计算机用结构化程序设计方法进行程序设计，并且用某一种计算机语言表示。因此，可以这样表示：语言表示。因此，可以这样表示：程序程序=算法算法+数据结构数据结构+程序设计方法程序设计方法+语言工具和环境语言工具和环境也就是说，以上也就是说，以上4个方面是一个程序设计人员所应具备的知识。个方面是一个程序设计人员所应具备的知识。在设计一个程序时要综合运用这几方面的知识。在设计一个程序时要综合运用这几方面的知识。n在这在这4个方面中，算法是灵魂，数据结构是加工对象，语言个方面中，算法是灵魂，数据结构是加工对象，语言是工具，编程需要采用合适的方法。算法是解决是工具，编程需要采用合适的方法。算法是解决“做什么做什么”和和“怎么做怎么做”的问题。程序中的操作语句，实际上就是算法的问题。程序中的操作语句，实际上就是算法的体现。显然，不了解算法就谈不上程序设计。的体现。显然，不了解算法就谈不上程序设计。2.1算算法法的的概概念念n问题一：有两个杯子问题一：有两个杯子A和和B，分别放有酒精和纯净水，试着，分别放有酒精和纯净水，试着将两个杯子中的液体进行互换。将两个杯子中的液体进行互换。n问题二：有三个牧师和三个野人过河，只有一条能装下两问题二：有三个牧师和三个野人过河，只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于个人的船，在河的任何一方或者船上，如果野人的人数大于牧师的人数，那么牧师就会有被吃掉的危险。请找出一种安牧师的人数，那么牧师就会有被吃掉的危险。请找出一种安全的渡河方案。全的渡河方案。两个野人先过河，一个野人回来；两个野人先过河，一个野人回来；再两个野人过河，一个野人回来；再两个野人过河，一个野人回来；两个牧师过河，一个野人和一个牧师回来；两个牧师过河，一个野人和一个牧师回来；两个牧师过河，一个野人回来；两个牧师过河，一个野人回来；两个野人过河，一个野人回来；两个野人过河，一个野人回来；两个野人过河。两个野人过河。n算法算法是指为解决一个问题而采取的方法和是指为解决一个问题而采取的方法和步骤步骤。算法并不。算法并不是问题的结果，而是是问题的结果，而是解题的过程和策略解题的过程和策略。n又例：对又例：对有序表有序表关键字序列关键字序列5，10，19，21，31，37，42，48，50，52，查找查找k为为50的记录。的记录。n解一：顺序查找，从第解一：顺序查找，从第1个元素到最后个元素到最后1个元素，逐个进个元素，逐个进行比较，直至找到为止。共比较行比较，直至找到为止。共比较9次次n解二：折半查找，算法步骤：解二：折半查找，算法步骤：step1首先确定整个查找区间的中间位置，首先确定整个查找区间的中间位置，mid=（left+right）/2；step2用待查关键字值与中间位置的关键字值进行比较：用待查关键字值与中间位置的关键字值进行比较：若相等，则查找成功；若大于，则在后半区域继续进行若相等，则查找成功；若大于，则在后半区域继续进行二分查找；若小于，则在前半区域继续进行二分查找。二分查找；若小于，则在前半区域继续进行二分查找。Step3对确定的缩小区域再按二分公式，重复上述步骤；对确定的缩小区域再按二分公式，重复上述步骤；最后最后得到结果：要么，查找成功，要么，查找失败。得到结果：要么，查找成功，要么，查找失败。上例共比较上例共比较3次次n对同一个问题，可以有不同的解题方法和步骤，即不同对同一个问题，可以有不同的解题方法和步骤，即不同算法算法。n如何判断一个算法（程序）的优劣？时空复杂如何判断一个算法（程序）的优劣？时空复杂度（时间复杂度、空间复杂度）。度（时间复杂度、空间复杂度）。n一般来说，希望采用一般来说，希望采用简单简单的和的和运算步骤少运算步骤少的方的方法。法。n如果一个算法对其如果一个算法对其每一个每一个输入实例，都能输出输入实例，都能输出正确的结果并停止，则称它是正确的。正确的结果并停止，则称它是正确的。n因此因此，为了有效地进行解题，为了有效地进行解题，不仅需要保证算不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法正确，还要考虑算法的质量，选择合适的算法。法。计算机算法可分为两类：计算机算法可分为两类：n数值算法数值算法:数值运算的目的是求数值解，如求方根、数值运算的目的是求数值解，如求方根、求定积分等。研究深入，算法成熟，求定积分等。研究深入，算法成熟，“数学程序库数学程序库”。n非数值算法非数值算法:最常见的是用于事务管理领域，如排最常见的是用于事务管理领域，如排序和检索（查找）。参考已有类似算法，重新设计。序和检索（查找）。参考已有类似算法，重新设计。时间复杂度的转换n时间复杂度 运行算法所需要的时间 以语句的执行次数来代替时间 以语句执行次数的数量值来代替执行的次数(通常用数量级来表示)2.3算法的特性算法的特性1.有穷性有穷性一个算法应包含有限的操作步骤，而不能是无限的。一个算一个算法应包含有限的操作步骤，而不能是无限的。一个算法必须保证执行有限步之后结束；法必须保证执行有限步之后结束；2.确定性确定性算法的每一步骤必须有确切的定义；算法的每一步骤必须有确切的定义；3.有零个或多个输入有零个或多个输入所谓输入是指在执行算法时需要从外界取得必要的信息。一所谓输入是指在执行算法时需要从外界取得必要的信息。一个算法也可以没有输入。个算法也可以没有输入。4.有一个或多个输出有一个或多个输出算法的目的是为了求解，算法的目的是为了求解，“解解”就是输出。没有输出的算法就是输出。没有输出的算法是没有意义的。是没有意义的。5.有效性有效性算法中的每一个步骤都应当能有效地执行，并得到确定的结算法中的每一个步骤都应当能有效地执行，并得到确定的结果。果。2.4怎样表示一个算法怎样表示一个算法常用的有自然语言、传统流程图、结构化流程图、常用的有自然语言、传统流程图、结构化流程图、伪代码、伪代码、PAD图等。图等。2.4.1用自然语言表示算法用自然语言表示算法n通俗易懂，但文字冗长，通俗易懂，但文字冗长，容易出现容易出现“歧义性歧义性”。自然语言表示的含义往往不太严格，要根据上下文自然语言表示的含义往往不太严格，要根据上下文才能判断其正确含义。才能判断其正确含义。n此外，用自然语言描述包含分支和循环的算法，此外，用自然语言描述包含分支和循环的算法，不很方便。不很方便。n因此，除了很简单的问题以外，一般不用自然语因此，除了很简单的问题以外，一般不用自然语言描述算法。言描述算法。2.4.2用流程图表示算法用流程图表示算法流程图是用一些图框表示各种操作。用图形表示算流程图是用一些图框表示各种操作。用图形表示算法，直观形象，易于理解。美国国家标准化协会法，直观形象，易于理解。美国国家标准化协会ANSI(AmericanNationalStandardInstitute)规定了一些常用的流程图符号规定了一些常用的流程图符号(见图见图2.3)。n图图2.3中中菱形框菱形框的作用是对一个给定的条件进行判的作用是对一个给定的条件进行判断，根据给定的条件是否成立来决定如何执行其后断，根据给定的条件是否成立来决定如何执行其后的哪一个操作。它有一个入口，两个出口。见图的哪一个操作。它有一个入口，两个出口。见图2.4。n连接点连接点(小圆圈小圆圈)是用于将画在不同地方的流程线是用于将画在不同地方的流程线连接起来。如图连接起来。如图2.5中有两个以中有两个以为标志的连接点，为标志的连接点，它表示这两个点是互相连接在一起的它表示这两个点是互相连接在一起的,实际上它们是实际上它们是同一个点。用连接点，可以避免流程线的交叉或过同一个点。用连接点，可以避免流程线的交叉或过长，使流程图清晰。长，使流程图清晰。图 2.3 图 2.4 图 2.5 n需要提醒的是流程线不要忘记画需要提醒的是流程线不要忘记画箭头箭头，因为它是反，因为它是反映流程的执行先后次序的。映流程的执行先后次序的。n用流程图表示算法用流程图表示算法直观形象直观形象，比较清楚地显示出，比较清楚地显示出各个框之间的逻辑关系。各个框之间的逻辑关系。n但是但是占用占用篇幅较多篇幅较多，尤其当算法比较复杂时，画，尤其当算法比较复杂时，画流程图既费时又不方便。流程图既费时又不方便。n在结构化程序设计方法推广之后，许多书刊已用在结构化程序设计方法推广之后，许多书刊已用N-S结构化流程图结构化流程图代替这种传统的流程图。但是每一代替这种传统的流程图。但是每一个程序编制人员都应当熟练掌握传统流程图。个程序编制人员都应当熟练掌握传统流程图。2.4.3三种基本结构和改进的流程图三种基本结构和改进的流程图1.传统流程图的弊端传统流程图的弊端传统的流程图用流程线指出各框的执行顺序，对流传统的流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制。因此，使用者可以不受程线的使用没有严格限制。因此，使用者可以不受限制地使流程限制地使流程随意随意地转来转去，使流程图变得毫无地转来转去，使流程图变得毫无规律。这种情况如图规律。这种情况如图2.13所示。所示。这种算法难以阅读，也难以修改，从而使算法的可这种算法难以阅读，也难以修改，从而使算法的可靠性和可维护性难以保证。如果我们写出的算法能靠性和可维护性难以保证。如果我们写出的算法能限制限制流程的无规律任意转向流程的无规律任意转向，阅读起来就很方便。，阅读起来就很方便。图2.13为了解决这个问题，人们设想，为了解决这个问题，人们设想，规定出几种基本结构规定出几种基本结构，然后，然后按一定规律按一定规律将各个将各个基本结构顺序排列基本结构顺序排列起来组成一个算法结构起来组成一个算法结构(如同用一些基本预制构件来搭成房屋一样如同用一些基本预制构件来搭成房屋一样)。2.三种基本结构三种基本结构1966年，年，Bohra和和Jacopini提出了以下三种基本结构，作为提出了以下三种基本结构，作为表示一个良好算法的基本单元。表示一个良好算法的基本单元。(1)顺序结构，如图顺序结构，如图2.14所示。所示。(2)选择结构，或称分支结构，如图选择结构，或称分支结构，如图2.15、2.16所示。所示。图图2.14图图2.16图图2.15(3)循环结构。有两类循环结构：循环结构。有两类循环结构：当型当型(While型型)循环结构循环结构见图见图2.17(a)。它的功能是。它的功能是先判断先判断给定的给定的条件条件p1，成立时，成立时，再执行再执行A框操作框操作，执行完，执行完A后，再判断条件后，再判断条件p1是否成立，如果是否成立，如果仍然成立，再执行仍然成立，再执行A框，如此反复执行框，如此反复执行A框，框，直到直到某一次某一次p1条条件不成立件不成立为止，此时不执行为止，此时不执行A框，而从框，而从b点脱离循环结构。点脱离循环结构。直到型直到型(Until型型)循环循环见图见图2.17(b)。它的功能是。它的功能是先执行先执行A框框，然后判断然后判断给定的给定的p2条件条件是否成立，如果是否成立，如果p2条件不成立，则再执行条件不成立，则再执行A，然后再对，然后再对p2条件作判断，如果条件作判断，如果p2条件仍然不成立，又执行条件仍然不成立，又执行A如此如此反复执行反复执行A，直到直到给定的给定的p2条件成立条件成立为止，此时不再执行为止，此时不再执行A，从从b点脱离本循环结构。点脱离本循环结构。图图2.18是当型循环是当型循环图图2.19是直到型循环是直到型循环 图2.17 图2.18 图2.192.4.4用用N-S流程图表示算法流程图表示算法n1973年美国学者年美国学者I.Nassi和和B.Shneiderman提出提出了一种新的流程图形式。在这种流程图中，了一种新的流程图形式。在这种流程图中，完全去完全去掉了带箭头的流程线掉了带箭头的流程线。n全部算法写在一个矩形框内，在该框内还可以包全部算法写在一个矩形框内，在该框内还可以包含其他的从属于它的框，或者说，含其他的从属于它的框，或者说，由一些基本的框由一些基本的框组成一个大的框组成一个大的框。这种流程图又称。这种流程图又称N-S结构化流程图。结构化流程图。n这种流程图这种流程图适于结构化程序设计适于结构化程序设计，因而很受欢迎。，因而很受欢迎。nN-S流程图用以下的流程图符号：流程图用以下的流程图符号：(1)顺序结构顺序结构:用图用图2.24形式表示。形式表示。(2)选择结构：用图选择结构：用图2.25表示。表示。图2.24 图2.25(3)循环结构：循环结构：当型循环结构用图当型循环结构用图2.26形式表形式表示。示。图图2.26表示当表示当p1条件成立时反复执行条件成立时反复执行A操作，直到操作，直到p1条件不成立为止。条件不成立为止。直到型循环结构用图直到型循环结构用图2.27形式表示。形式表示。用以上用以上3种种N-S流程图中的基本框，可以组成复杂的流程图中的基本框，可以组成复杂的N-S流程图，以表示算法。流程图，以表示算法。当型循环结构当型循环结构直到型循环结构直到型循环结构n可以看出用可以看出用N-S图表示算法的优点。图表示算法的优点。n它比文字描述直观、形象、它比文字描述直观、形象、易于理解；易于理解；n比传统流程图紧凑易画，尤其是它废除了流程线；比传统流程图紧凑易画，尤其是它废除了流程线；nN-S流程图中的上下顺序就是执行时的顺序，即流程图中的上下顺序就是执行时的顺序，即图中位置在上面的先执行，位置在下面的后执行。图中位置在上面的先执行，位置在下面的后执行。写算法和看算法只需从上到下进行就可以了，十分写算法和看算法只需从上到下进行就可以了，十分方便。方便。n用用N-S图表示的算法都是结构化的算法图表示的算法都是结构化的算法(不可能出不可能出现流程无规律的跳转现流程无规律的跳转)。n归纳起来可知，一个结构化的算法是由一些基归纳起来可知，一个结构化的算法是由一些基本结构顺序组成的；每个基本结构又可以包含其本结构顺序组成的；每个基本结构又可以包含其他的基本结构；在基本结构之间不存在向前或向他的基本结构；在基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本结构范后的跳转，流程的转移只存在于一个基本结构范围之内围之内(如循环中流程的跳转如循环中流程的跳转)；n一个非结构化的算法一个非结构化的算法(如图如图2.12)可以用一个等可以用一个等价的结构化算法价的结构化算法(如图如图2.35)代替，其功能不变。代替，其功能不变。n如果一个算法不能分解为若干个基本结构，则如果一个算法不能分解为若干个基本结构，则它必然不是一个结构化的算法。它必然不是一个结构化的算法。nN-S图如同一个多层的盒子，又称盒图图如同一个多层的盒子，又称盒图(boxdiagram)。2.4.5用伪代码表示算法用伪代码表示算法n用传统的流程图和用传统的流程图和N-S图表示算法，直观易懂，图表示算法，直观易懂，但画起来比较费事。但画起来比较费事。n为了设计算法时方便，常用一种称为为了设计算法时方便，常用一种称为伪代码伪代码(pseudocode)的工具。的工具。n伪代码是用伪代码是用介于自然语言和计算机语言之间介于自然语言和计算机语言之间的文的文字和符号来描述算法。它不用图形符号，因此书写字和符号来描述算法。它不用图形符号，因此书写方便方便、格式紧凑，也比较好懂，便于向计算机语言、格式紧凑，也比较好懂，便于向计算机语言算法算法(即程序即程序)过渡。过渡。例如，例如，“打印打印x的绝对值的绝对值”的算法可以用伪代码表的算法可以用伪代码表示如下：示如下：IFxispositiveTHENprintxELSEprintxn也可以用汉字伪代码，如：也可以用汉字伪代码，如：若若x为正为正打印打印x否则否则打印打印xn也可以中英文混用，如：也可以中英文混用，如：IFx为正为正printxELSEprintxn用伪代码写算法并用伪代码写算法并无固定的、严格的语法规则无固定的、严格的语法规则，只，只要把意思表达清楚，并且书写的格式要写成要把意思表达清楚，并且书写的格式要写成清晰易清晰易读读的形式。的形式。伪代码的特点：伪代码的特点：n伪代码书写伪代码书写格式比较自由格式比较自由，容易表达出设计者的思，容易表达出设计者的思想。想。n同时，用伪代码写的算法很同时，用伪代码写的算法很容易修改容易修改。n用伪代码很用伪代码很容易写出结构化的算法容易写出结构化的算法。n但是用伪代码写算法但是用伪代码写算法不如流程图直观不如流程图直观，可能会出现，可能会出现逻辑上的逻辑上的错误错误。软件专业人员一般习惯使用伪代码，为便于理解，本软件专业人员一般习惯使用伪代码，为便于理解，本书在以后各章中主要采用形象化的书在以后各章中主要采用形象化的N-S图表示算法。图表示算法。2.4.6用计算机语言表示算法用计算机语言表示算法n要完成一件工作，包括要完成一件工作，包括设计设计算法和算法和实现实现算法两个算法两个部分。部分。n在用流程图或伪代码描述出一个算法后，还要将它在用流程图或伪代码描述出一个算法后，还要将它转换成计算机语言程序，才能编译执行。转换成计算机语言程序，才能编译执行。2.5结构化程序设计方法结构化程序设计方法（STRUCTUREDPROGRAMING，简称，简称SP）nSP方法主张使用顺序、选择、循环三种基本结构方法主张使用顺序、选择、循环三种基本结构来嵌套连结成具有复杂层次的来嵌套连结成具有复杂层次的“结构化程序结构化程序”。SP方法是方法是面向过程面向过程的设计方法。的设计方法。n面向对象的程序设计面向对象的程序设计(ObjectOrientProgramming，OOP)n结构化程序设计方法的结构化程序设计方法的基本思路基本思路是，把一个复杂问是，把一个复杂问题的求解过程题的求解过程分阶段分阶段进行，每个阶段处理的问题都控进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。制在人们容易理解和处理的范围内。n结构化程序设计的步骤：结构化程序设计的步骤：(1)自顶向下；自顶向下；(2)逐步逐步细化；细化；(3)模块化设计；模块化设计；(4)结构化编码。结构化编码。n在接受一个任务后应怎样着手进行呢在接受一个任务后应怎样着手进行呢?有两种不同有两种不同的方法：的方法：n一种是一种是自顶向下，逐步细化自顶向下，逐步细化；n一种是自下而上，逐步积累。一种是自下而上，逐步积累。n以写文章为例。如图以写文章为例。如图2.36示意。示意。图2.36n显然，采用显然，采用“自顶向下，自顶向下，逐步细化逐步细化”的方法的方法n考虑周全，结构清晰，层次分明；考虑周全，结构清晰，层次分明；n如果发现有需要修改的部分，只需相关段落即如果发现有需要修改的部分，只需相关段落即可，与其他部分无关。可，与其他部分无关。n我们提倡用这种方法设计程序，即用我们提倡用这种方法设计程序，即用工程的方法工程的方法设计程序。设计程序。n在程序设计中常采用在程序设计中常采用模块设计模块设计的方法，尤其是当的方法，尤其是当程序比较复杂时，更有必要。程序比较复杂时，更有必要。n模块化设计的思想实际上是一种模块化设计的思想实际上是一种“分而治之分而治之”的的思想，把一个大任务分为若干个相对简单的子任务，思想，把一个大任务分为若干个相对简单的子任务，或根据功能将复杂的大模块划分为若干个子模块。或根据功能将复杂的大模块划分为若干个子模块。这个过程采用自顶向下的方法来实现。这个过程采用自顶向下的方法来实现。n模块的根本特征是模块的根本特征是“相对独立，相对独立，功能单一功能单一”。n模块的好坏，通常用模块的好坏，通常用“耦合度耦合度”和和“内聚度内聚度”两个指标从两个指标从不同侧面而加以度量。不同侧面而加以度量。n所谓耦合度，是指模块之间相互依赖性大小的度量，耦所谓耦合度，是指模块之间相互依赖性大小的度量，耦合度越小，模块的相对独立性越大。合度越小，模块的相对独立性越大。n所谓内聚度，是指模块内各成份之间相互依赖性大小的所谓内聚度，是指模块内各成份之间相互依赖性大小的度量，内聚度越大，模块各成份之间联系越紧密，其功能度量，内聚度越大，模块各成份之间联系越紧密，其功能越强。越强。n因此在模块划分应当做到因此在模块划分应当做到“耦合度尽量小，内聚度尽量耦合度尽量小，内聚度尽量大大”，即，即“低耦合，高内聚低耦合，高内聚”。n程序中的程序中的子模块子模块在在C语言中通常用语言中通常用函数函数来实现。来实现。n程序中的子模块一般不超过程序中的子模块一般不超过50行行，即打印时不超过一页，即打印时不超过一页，这样的规模便于组织，也便于阅读。超过这样的规模便于组织，也便于阅读。超过50行的代码要重新行的代码要重新考虑将其拆分为两个或两个以上的函数。考虑将其拆分为两个或两个以上的函数。n学习程序设计的目的不只是学习一种特定的语言，学习程序设计的目的不只是学习一种特定的语言，而是学习进行程序设计的一般方法。而是学习进行程序设计的一般方法。n掌握了算法就是掌握了程序设计的灵魂，再学习掌握了算法就是掌握了程序设计的灵魂，再学习有关的计算机语言知识，就能够顺利地编写出任何有关的计算机语言知识，就能够顺利地编写出任何一种语言的程序。一种语言的程序。