c程序第2章-算法.ppt

2.1算法的概念算法的概念2.2简单算法举例简单算法举例2.3算法的特性算法的特性2.4怎样表示一个算法怎样表示一个算法2.5结构化程序设计方法结构化程序设计方法习题习题第2章 程序的灵魂算法一个程序应包括以下两方面内容一个程序应包括以下两方面内容:(1)对数据的描述。在程序中要指定数据的类型和数对数据的描述。在程序中要指定数据的类型和数据的组织形式，即数据结构据的组织形式，即数据结构(data structure)。(2)对操作的描述。即操作步骤，对操作的描述。即操作步骤，也就是算法也就是算法(algorithm)。数据是操作的对象，操作的目的是对数据进行加工数据是操作的对象，操作的目的是对数据进行加工处理，以得到期望的结果。作为程序设计人员，必处理，以得到期望的结果。作为程序设计人员，必须认真考虑和设计数据结构和操作步骤须认真考虑和设计数据结构和操作步骤(即算法即算法)。因此，著名计算机科学家沃思因此，著名计算机科学家沃思(Nikiklaus Wirth)提出一个公式提出一个公式数据结构数据结构+算法算法=程序程序实际上，一个程序除了以上两个主要要素之外，还实际上，一个程序除了以上两个主要要素之外，还应当采用结构化程序设计方法进行程序设计，并且应当采用结构化程序设计方法进行程序设计，并且用某一种计算机语言表示。因此，可以这样表示：用某一种计算机语言表示。因此，可以这样表示：程序程序=算法算法+数据结构数据结构+程序设计方法程序设计方法+语言工具语言工具和环境和环境也就是说，以上也就是说，以上4个方面是一个程序设计人员所应具个方面是一个程序设计人员所应具备的知识。在设计一个程序时要综合运用这几方面备的知识。在设计一个程序时要综合运用这几方面的知识。在这的知识。在这4个方面中，算法是灵魂，数据结构个方面中，算法是灵魂，数据结构是加工对象，语言是工具，编程需要采用合适的方是加工对象，语言是工具，编程需要采用合适的方法。算法是解决法。算法是解决“做什么做什么”和和“怎么做怎么做”的问题。的问题。程序中的操作语句，实际上就是算法的体现。显然，程序中的操作语句，实际上就是算法的体现。显然，不了解算法就谈不上程序设计。不了解算法就谈不上程序设计。我们的目的是使读者通过学习本书，能够知道怎样我们的目的是使读者通过学习本书，能够知道怎样编写一个编写一个C程序，并且能够编写出不太复杂的程序，并且能够编写出不太复杂的C程程序。书中将通过一些实例把以上序。书中将通过一些实例把以上4个方面的知识结个方面的知识结合起来，介绍如何编写一个合起来，介绍如何编写一个C程序。程序。由于算法的重要性，在本章中先介绍有关算法的初由于算法的重要性，在本章中先介绍有关算法的初步知识，以便为后面各章的学习建立一定的基础。步知识，以便为后面各章的学习建立一定的基础。2.1 算算 法法 的的 概概 念念从事各种工作和活动，都必须事先想好进行的步骤，从事各种工作和活动，都必须事先想好进行的步骤，然后按部就班地进行，才能避免产生错乱。然后按部就班地进行，才能避免产生错乱。不要认为只有不要认为只有“计算计算”的问题才有算法。广义地说，的问题才有算法。广义地说，为解决一个问题而采取的方法和步骤，就称为为解决一个问题而采取的方法和步骤，就称为“算算法法”。对同一个问题，可以有不同的解题方法和步骤。方对同一个问题，可以有不同的解题方法和步骤。方法有优劣之分。有的方法只需进行很少的步骤，而法有优劣之分。有的方法只需进行很少的步骤，而有些方法则需要较多的步骤。一般说，希望采用简有些方法则需要较多的步骤。一般说，希望采用简单的和运算步骤少的方法。因此单的和运算步骤少的方法。因此，为了有效地进，为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法。质量，选择合适的算法。本书所关心的当然只限于计算机算法，即计算机能本书所关心的当然只限于计算机算法，即计算机能执行的算法。执行的算法。计算机算法可分为两大类别：数值算法和非数值算计算机算法可分为两大类别：数值算法和非数值算法。数值运算的目的是求数值解法。数值运算的目的是求数值解。非数值运算包。非数值运算包括的面十分广泛，最常见的是用于事务管理领域。括的面十分广泛，最常见的是用于事务管理领域。目前，计算机在非数值运算方面的应用远远超过了目前，计算机在非数值运算方面的应用远远超过了在数值运算方面的应用。由于数值运算有现成的模在数值运算方面的应用。由于数值运算有现成的模型，可以运用数值分析方法，因此对数值运算的算型，可以运用数值分析方法，因此对数值运算的算法研究比较深入，算法比较成熟。对各种数值运算法研究比较深入，算法比较成熟。对各种数值运算都有比较成熟的算法可供选用。人们常常把这些算都有比较成熟的算法可供选用。人们常常把这些算法汇编成册法汇编成册(写成程序形式写成程序形式)，或者将这些程序存放，或者将这些程序存放在磁盘或磁带上，供用户调用。在磁盘或磁带上，供用户调用。而非数值运算的种类繁多，要求各异，难以规范化，而非数值运算的种类繁多，要求各异，难以规范化，因此只对一些典型的非数值运算算法因此只对一些典型的非数值运算算法(例如排序算例如排序算法法)作比较深入的研究。其他的非数值运算问题，作比较深入的研究。其他的非数值运算问题，往往需要使用者参考已有的类似算法重新设计解决往往需要使用者参考已有的类似算法重新设计解决特定问题的专门算法。特定问题的专门算法。本书不可能罗列所有算法，只是想通过一些典型算本书不可能罗列所有算法，只是想通过一些典型算法的介绍，帮助读者了解如何设计一个算法，推动法的介绍，帮助读者了解如何设计一个算法，推动读者举一反三。希望读者通过本章介绍的例子了解读者举一反三。希望读者通过本章介绍的例子了解怎样提出问题，怎样思考问题，怎样表示一个算法。怎样提出问题，怎样思考问题，怎样表示一个算法。2.2 简单算法举例简单算法举例例例2.1 求求12345。可以用最原始的方法进行。可以用最原始的方法进行。步骤步骤1：先求先求12，得到结果，得到结果2。步骤步骤2：将步骤将步骤1得到的乘积得到的乘积2再乘以再乘以3，得到结果，得到结果6。步骤步骤3：将将6再乘以再乘以4，得，得24。步骤步骤4：将将24再乘以再乘以5，得，得120。这就是最后的结果。这就是最后的结果。这样的算法虽然是正确的，但太繁琐。如果要求这样的算法虽然是正确的，但太繁琐。如果要求121000，则要写，则要写999个步骤，显然是不可取个步骤，显然是不可取的。而且每次都直接使用上一步骤的数值结果的。而且每次都直接使用上一步骤的数值结果(如如2，6，24等等)，也不方便。应当找到一种通用的表示，也不方便。应当找到一种通用的表示方法。方法。可以设两个变量，一个变量代表被乘数，一个变量可以设两个变量，一个变量代表被乘数，一个变量代表乘数。不另设变量存放乘积结果，而直接将每代表乘数。不另设变量存放乘积结果，而直接将每一步骤的乘积放在被乘数变量中。今设一步骤的乘积放在被乘数变量中。今设p为被乘数，为被乘数，i为乘数。用循环算法来求结果。可以将算法改写为乘数。用循环算法来求结果。可以将算法改写如下：如下：S1：使使p=1S2：使使i=2S3：使使pi，乘积仍放在变量，乘积仍放在变量p中，可表示为中，可表示为pi=pS4：使使i的值加的值加1，即，即i+1=iS5：如果如果i不大于不大于5，返回重新执行步骤，返回重新执行步骤S3以及其后以及其后的步骤的步骤S4和和S5；否则，算法结束。最后得到；否则，算法结束。最后得到p的值的值就是就是5!的值。的值。上面的上面的S1，S2代表步骤代表步骤1，步骤，步骤2S是是step(步步)的缩写。这是写算法的习惯用法。的缩写。这是写算法的习惯用法。请读者仔细分析这个算法，能否得到预期的结果。请读者仔细分析这个算法，能否得到预期的结果。显然这个算法比前面列出的算法简练。显然这个算法比前面列出的算法简练。如果题目改为求如果题目改为求1357911。算法只需作很少的改动即可：算法只需作很少的改动即可：S1：1=pS2：3=iS3：pi=pS4：i+2=iS5：若若i11，返回，返回S3；否则，结束。否则，结束。可以看出，用这种方法表示的算法具有通用性、灵可以看出，用这种方法表示的算法具有通用性、灵活性。活性。S3到到S5组成一个循环，在实现算法时，要组成一个循环，在实现算法时，要反复多次执行反复多次执行S3、S4、S5等步骤，直到某一时刻，等步骤，直到某一时刻，执行执行S5步骤时经过判断，乘数步骤时经过判断，乘数i已超过规定的数值已超过规定的数值而不返回而不返回S3步骤为止。此时算法结束，变量步骤为止。此时算法结束，变量p的值的值就是所求结果。就是所求结果。由于计算机是高速进行运算的自动机器，实现循环由于计算机是高速进行运算的自动机器，实现循环是轻而易举的，所有计算机高级语言中都有实现循是轻而易举的，所有计算机高级语言中都有实现循环的语句。因此，上述算法不仅是正确的，而且是环的语句。因此，上述算法不仅是正确的，而且是计算机能实现的较好的算法。计算机能实现的较好的算法。请读者仔细分析循环结束的条件，即请读者仔细分析循环结束的条件，即S5步骤。如果步骤。如果在求在求1211时，将时，将S5步骤写成步骤写成S5：若若i11，返回，返回S3。这样会有什么问题这样会有什么问题?会得到什么结果会得到什么结果?例例2.2 有有50个学生，要求将他们之中成绩在个学生，要求将他们之中成绩在80分以上分以上者打印出来。用者打印出来。用n表示学生学号，表示学生学号，n1代表第一个学代表第一个学生学号，生学号，ni代表第代表第i个学生学号。用个学生学号。用g代表学生成绩，代表学生成绩，gi代表第代表第i个学生成绩，算法可表示如下。个学生成绩，算法可表示如下。S1：1=iS2：如果：如果gi80，则打印，则打印ni和和gi，否则不打印，否则不打印S3：i+1=iS4：如果：如果i50，返回，返回S2，继续执行；否则，算法结，继续执行；否则，算法结束。束。本例中，变量本例中，变量i作为下标，用它来控制序号作为下标，用它来控制序号(第几个学第几个学生，第几个成绩生，第几个成绩)。当。当i超过超过50时，表示已对时，表示已对50个学个学生的成绩处理完毕，算法结束。生的成绩处理完毕，算法结束。例例2.3 判定判定20002500年中的每一年是否闰年，将结年中的每一年是否闰年，将结果输出。果输出。闰年的条件是：闰年的条件是：能被能被4整除，但不能被整除，但不能被100整除的整除的年份都是闰年，如年份都是闰年，如1996年，年，2004年是闰年；年是闰年；能被能被100整除，又能被整除，又能被400整除的年份是闰年。如整除的年份是闰年。如1600年、年、2000年是闰年。不符合这两个条件的年份不是闰年。年是闰年。不符合这两个条件的年份不是闰年。算法可表示如下：算法可表示如下：设设y 为被检测的年份。可采取以下步骤：为被检测的年份。可采取以下步骤：S1：2000=yS2：y不能被不能被4整除，则输出整除，则输出y“不是闰年不是闰年”。然后转。然后转到到S6S3：若：若y能被能被4整除，不能被整除，不能被100整除，则输出整除，则输出y“是闰是闰年年”。然后转到。然后转到S6S4：若：若y能被能被100整除，又能被整除，又能被400整除，输出整除，输出y“是闰是闰年年”；否则输出；否则输出“不是闰年不是闰年”。然后转到然后转到S6S5：输出：输出y“不是闰年不是闰年”S6：y+1=yS7：当：当y2500时，转时，转S2继续执行，如继续执行，如y2500，算法，算法停止。停止。在这个算法中，采取了多次判断。先判断在这个算法中，采取了多次判断。先判断y能否被能否被4整除，如不能，则整除，如不能，则y必然不是闰年。如必然不是闰年。如y 能被能被4整除，整除，并不能马上决定它是否闰年，还要看它能否被并不能马上决定它是否闰年，还要看它能否被100整除。如不能被整除。如不能被100整除，则肯定是闰年整除，则肯定是闰年(例如例如1996年年)。如能被。如能被100整除，还不能判断它是否闰年，还整除，还不能判断它是否闰年，还要被要被400整除，如果能被整除，如果能被400整除，则它是闰年，否整除，则它是闰年，否则不是闰年。则不是闰年。在这个算法中，每做一步，都分别分离出一些范围在这个算法中，每做一步，都分别分离出一些范围(巳能判定为闰年或非闰年巳能判定为闰年或非闰年)，逐步缩小范围，使被，逐步缩小范围，使被判断的范围愈来愈小，直至执行判断的范围愈来愈小，直至执行S5时，只可能是时，只可能是非闰年。见图非闰年。见图2.1示意。示意。图图 2.1从图从图2.1可以看出：可以看出：“其他其他”这一部分，包括能被这一部分，包括能被4整整除，又能被除，又能被100整除，而不能被整除，而不能被400整除的那些年份整除的那些年份(如如1900年年)，是非闰年。，是非闰年。在考虑算法时，应当仔细分析所需判断的条件，如在考虑算法时，应当仔细分析所需判断的条件，如何一步一步缩小被判断的范围。有的问题，判断的何一步一步缩小被判断的范围。有的问题，判断的先后次序是无所谓的，而有的问题，判断条件的先先后次序是无所谓的，而有的问题，判断条件的先后次序是不能任意颠倒的，读者可根据具体问题决后次序是不能任意颠倒的，读者可根据具体问题决定其逻辑。定其逻辑。例例2.4 求求1-1/2+1/3-1/4+1/99-1/100。算法可以表示如下：算法可以表示如下：S1：1=signS2：1=sumS3：2=denoS4：(-1)sign=signS5：sign(1/deno)=termS6：sum+term=sumS7：deno+1=denoS8：若：若deno100返回返回S4；否则算法结束。；否则算法结束。在步骤在步骤S1中先预设中先预设sign（代表级数中各项的符号，它（代表级数中各项的符号，它的值为的值为1或或-1）。在步骤）。在步骤S2中使中使sum等于等于1，相当，相当于已将级数中的第一项放到了于已将级数中的第一项放到了sum中。在步骤中。在步骤S3中中使分母的值为使分母的值为2。在步骤。在步骤S4中使中使sign的值变为的值变为-1。在步骤在步骤S5中求出级数中第中求出级数中第2项的值项的值-1/2。在步骤。在步骤S6中将刚才求出的第二项的值中将刚才求出的第二项的值-1/2累加到累加到sum中。至中。至此，此，sum的值是的值是1-1/2。在步骤。在步骤S7中使分母中使分母deno的值的值加加1（变成（变成3）。执行）。执行S8步骤，由于步骤，由于deno100，故，故返回返回S4步骤，步骤，sign的值改为的值改为1，在，在S5中求出中求出term的的值为值为1/3，在，在S6中将中将1/3累加到累加到sum中。然后中。然后S7再使再使分母变为分母变为4。按此规律反复执行。按此规律反复执行S4到到S8步骤，直到步骤，直到分母大于分母大于100为止。一共执行了为止。一共执行了99次循环，向次循环，向sum累加入了累加入了99个分数。个分数。sum最后的值就是级数的值。最后的值就是级数的值。例例2.5 对一个大于或等于对一个大于或等于3的正整数，判断它是不是的正整数，判断它是不是一个素数。一个素数。所谓素数，是指除了所谓素数，是指除了1和该数本身之外，不能被其他和该数本身之外，不能被其他任何整数整除的数。例如，任何整数整除的数。例如，13是素数，因为它不能是素数，因为它不能被被2，3，4，12整除。整除。判断一个数判断一个数n(n3)是否素数的方法是很简单的：将是否素数的方法是很简单的：将n作为被除数，将作为被除数，将2到到(n-1)各个整数轮流作为除数，各个整数轮流作为除数，如果都不能被整除，则如果都不能被整除，则n为素数。为素数。算法可以表示如下：算法可以表示如下：S1：输入：输入n的值的值S2：2=i（i作为除数）作为除数）S3：n被被i除，得余数除，得余数rS4：如果：如果r=0，表示，表示n能被能被i整除，则打印整除，则打印n“不是素数不是素数”，算法结束；否则执行，算法结束；否则执行S5S5：i+1=iS6：如果：如果in-1，返回，返回S3；否则打印；否则打印 n“是素数是素数”，然后结束。然后结束。实际上实际上n不必被不必被2到到(n-1)的整数除，只需被的整数除，只需被2到到n的开的开方间整数除即可，甚至只需被方间整数除即可，甚至只需被2到到n之间的整数除之间的整数除即可。例如，判断即可。例如，判断13是否素数，只需将是否素数，只需将13被被2、3除除即可，如都除不尽，即可，如都除不尽，n 必为素数。必为素数。S6步骤可改为：步骤可改为：S6：如果：如果in，返回，返回S2；否则算法结束。；否则算法结束。通过以上几个例子，可以初步了解怎样设计一个算通过以上几个例子，可以初步了解怎样设计一个算法。法。2.3 算法的特性算法的特性一个算法应该具有以下特点：一个算法应该具有以下特点：1.有穷性有穷性一个算法应包含有限的操作步骤，而不能是无限的。一个算法应包含有限的操作步骤，而不能是无限的。事实上，事实上，“有穷性有穷性”往往指往往指“在合理的范围之内在合理的范围之内”。究竟什么算究竟什么算“合理限度合理限度”，并无严格标准，由人们，并无严格标准，由人们的常识和需要而定。的常识和需要而定。2.确定性确定性算法中的每一个步骤都应当是确定的，而不应当是算法中的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的。含糊的、模棱两可的。3.有零个或多个输入有零个或多个输入所谓输入是指在执行算法时需要从外界取得必要的所谓输入是指在执行算法时需要从外界取得必要的信息。一个算法也可以没有输入。信息。一个算法也可以没有输入。4.有一个或多个输出有一个或多个输出算法的目的是为了求解，算法的目的是为了求解，“解解”就是输出。没有输就是输出。没有输出的算法是没有意义的。出的算法是没有意义的。5.有效性有效性算法中的每一个步骤都应当能有效地执行，并得到算法中的每一个步骤都应当能有效地执行，并得到确定的结果。确定的结果。对于不熟悉计算机程序设计的人来说，他们可以只对于不熟悉计算机程序设计的人来说，他们可以只使用别人已设计好的现成算法，只需根据算法的要使用别人已设计好的现成算法，只需根据算法的要求给以必要的输入，就能得到输出的结果。对他们求给以必要的输入，就能得到输出的结果。对他们来说，算法如同一个来说，算法如同一个“黑箱子黑箱子”一样一样，他们可以，他们可以不了解不了解“黑箱子黑箱子”中的结构，只是从外部特性上了中的结构，只是从外部特性上了解算法的作用，即可方便地使用算法。例如，对一解算法的作用，即可方便地使用算法。例如，对一个个“输入输入3个数，求其中最大值个数，求其中最大值”的算法，可以用的算法，可以用图图2.2表示，只要输入表示，只要输入a，b，c3个数，执行算法后个数，执行算法后就能得到其中最大的数。但对于程序设计人员来说，就能得到其中最大的数。但对于程序设计人员来说，必须会设计算法，并且根据算法编写程序。必须会设计算法，并且根据算法编写程序。图图2.22.4 怎样表示一个算法怎样表示一个算法为了表示一个算法，可以用不同的方法。常用的有为了表示一个算法，可以用不同的方法。常用的有自然语言、传统流程图、结构化流程图、伪代码、自然语言、传统流程图、结构化流程图、伪代码、PAD图等。图等。2.4.1 用自然语言表示算法用自然语言表示算法在在2.2节中介绍的算法是用自然语言表示的。用自然节中介绍的算法是用自然语言表示的。用自然语言表示通俗易懂，但文字冗长，语言表示通俗易懂，但文字冗长，容易出现容易出现“歧歧义性义性”。自然语言表示的含义往往不太严格，要根。自然语言表示的含义往往不太严格，要根据上下文才能判断其正确含义。此外，用自然语言据上下文才能判断其正确含义。此外，用自然语言描述包含分支和循环的算法，不很方便描述包含分支和循环的算法，不很方便(如例如例2.5的的算法算法)。因此，除了很简单的问题以外，一般不用。因此，除了很简单的问题以外，一般不用自然语言描述算法。自然语言描述算法。2.4.2 用流程图表示算法用流程图表示算法流程图是用一些图框表示各种操作。用图形表示算流程图是用一些图框表示各种操作。用图形表示算法，直观形象，易于理解。美国国家标准化协会法，直观形象，易于理解。美国国家标准化协会ANSI(American National Standard Institute)规定规定了一些常用的流程图符号了一些常用的流程图符号(见图见图2.3)。图图2.3中菱形框的作用是对一个给定的条件进行判断，中菱形框的作用是对一个给定的条件进行判断，根据给定的条件是否成立来决定如何执行其后的操根据给定的条件是否成立来决定如何执行其后的操作。它有一个入口，两个出口。见图作。它有一个入口，两个出口。见图2.4。连接点连接点(小圆圈小圆圈)是用于将画在不同地方的流程线连是用于将画在不同地方的流程线连接起来。如图接起来。如图2.5中有两个以中有两个以为标志的连接点为标志的连接点(在在连接点圈中写上连接点圈中写上“1”)，它表示这两个点是互相连，它表示这两个点是互相连接在一起的。实际上它们是同一个点，只是画不下接在一起的。实际上它们是同一个点，只是画不下才分开来画。用连接点，可以避免流程线的交叉或才分开来画。用连接点，可以避免流程线的交叉或过长，使流程图清晰。过长，使流程图清晰。图图 2.3图图 2.4 图图 2.5下面对下面对2.2节中所举的几个算法例子，改用流程图表节中所举的几个算法例子，改用流程图表示。示。例例2.6 将例将例2.1求求5!的算法用流程图表示，流程图见图的算法用流程图表示，流程图见图2.6。菱形框两侧的菱形框两侧的“Y”和和“N”代表代表“是是”(yes)和和“否否”(no)。如果需要将最后结果打印出来，可以在菱。如果需要将最后结果打印出来，可以在菱形框的下面再加一个输出框，见图形框的下面再加一个输出框，见图2.7。例例2.7 将例将例2.2的算法用流程图表示。将的算法用流程图表示。将50名学生中成名学生中成绩在绩在80分以上者的学号和成绩打印出来，见图分以上者的学号和成绩打印出来，见图2.8。在此算法中没有包括输入在此算法中没有包括输入50个学生数据的部分，如个学生数据的部分，如果包括这个输入数据的部分，流程图如图果包括这个输入数据的部分，流程图如图2.9所示。所示。图图2.6 图图2.7 图图2.8例例2.8 将例将例2.3判定闰年的算法用流程图表示。判定闰年的算法用流程图表示。见图见图2.10。显然，用图。显然，用图2.10表示算法要比用文字描述表示算法要比用文字描述算法逻辑清晰、易于理解。算法逻辑清晰、易于理解。请读者考虑，如果例请读者考虑，如果例2.3所表示的算法中，所表示的算法中，S2步骤内步骤内没有最后没有最后“转到转到S6”这一句话，而只是这一句话，而只是S2：若：若y不能被不能被4整除，则打印整除，则打印y“不是闰年不是闰年”这样就意味着执行完这样就意味着执行完S2步骤后，不论步骤后，不论S2的执行情况的执行情况如何都应执行如何都应执行S3步骤。请读者画出相应的流程图。步骤。请读者画出相应的流程图。请思考这样的算法在逻辑上有什么错误，从流程图请思考这样的算法在逻辑上有什么错误，从流程图上是很容易发现其错误的。上是很容易发现其错误的。图图2.9 图图2.10例例2.9 将例将例2.4的算法用流程图表示。见图的算法用流程图表示。见图2.11。例例2.10 将例将例2.5判断素数的算法用流程图表示，见图判断素数的算法用流程图表示，见图2.12。一个流程图包括以下几部分：一个流程图包括以下几部分：表示相应操作的框；表示相应操作的框；带箭头的流程线；带箭头的流程线；框内外必要的文字说明。需框内外必要的文字说明。需要提醒的是流程线不要忘记画箭头，因为它是反映要提醒的是流程线不要忘记画箭头，因为它是反映流程的执行先后次序的。流程的执行先后次序的。用流程图表示算法直观形象，比较清楚地显示出各用流程图表示算法直观形象，比较清楚地显示出各个框之间的逻辑关系。但是这种流程图占用篇幅较个框之间的逻辑关系。但是这种流程图占用篇幅较多，尤其当算法比较复杂时，画流程图既费时又不多，尤其当算法比较复杂时，画流程图既费时又不方便。在结构化程序设计方法推广之后，许多书刊方便。在结构化程序设计方法推广之后，许多书刊已用已用 N-S结构化流程图代替这种传统的流程图。但结构化流程图代替这种传统的流程图。但是每一个程序编制人员都应当熟练掌握传统流程图。是每一个程序编制人员都应当熟练掌握传统流程图。图图2.11 图图2.122.4.3 三种基本结构和改进的流程图三种基本结构和改进的流程图1.传统流程图的弊端传统流程图的弊端传统的流程图用流程线指出各框的执行顺序，对流传统的流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制。因此，使用者可以不受程线的使用没有严格限制。因此，使用者可以不受限制地使流程随意地转来转去，使流程图变得毫无限制地使流程随意地转来转去，使流程图变得毫无规律。这种情况如图规律。这种情况如图2.13所示。所示。这种算法难以阅读，也难以修改，从而使算法的可这种算法难以阅读，也难以修改，从而使算法的可靠性和可维护性难以保证。如果我们写出的算法能靠性和可维护性难以保证。如果我们写出的算法能限制流程的无规律任意转向，阅读起来就很方便。限制流程的无规律任意转向，阅读起来就很方便。图图2.13但是，算法上难免会包含一些分支和循环，而不可但是，算法上难免会包含一些分支和循环，而不可能全部由一个一个框顺序组成。例如图能全部由一个一个框顺序组成。例如图2.6到图到图2.12都不是由各框顺序进行的，都包含一些流程的向前都不是由各框顺序进行的，都包含一些流程的向前或向后的非顺序转向。为了解决这个问题，人们设或向后的非顺序转向。为了解决这个问题，人们设想，规定出几种基本结构，然后由这些基本结构按想，规定出几种基本结构，然后由这些基本结构按一定规律组成一个算法结构一定规律组成一个算法结构(如同用一些基本预制如同用一些基本预制构件来搭成房屋一样构件来搭成房屋一样)，整个算法的结构是由上而，整个算法的结构是由上而下地将各个基本结构顺序排列起来的。如果能做到下地将各个基本结构顺序排列起来的。如果能做到这一点这一点，算法的质量就能得到保证和提高。，算法的质量就能得到保证和提高。2.三种基本结构三种基本结构1966年，年，Bohra和和Jacopini提出了以下三种基本结构，提出了以下三种基本结构，作为表示一个良好算法的基本单元。作为表示一个良好算法的基本单元。(1)顺序结构，如图顺序结构，如图2.14所示，虚线框内是一个顺序所示，虚线框内是一个顺序结构。结构。(2)选择结构，或称选取结构，或称分支结构，如图选择结构，或称选取结构，或称分支结构，如图2.15所示。所示。请注意，无论请注意，无论 p 条件是否成立，只能执行条件是否成立，只能执行A框或框或B框框之一，不可能既执行之一，不可能既执行A框又执行框又执行B框。无论走哪一框。无论走哪一条路径，在执行完条路径，在执行完A或或B之后，都经过之后，都经过b点，然后脱点，然后脱离本选择结构。离本选择结构。A或或B两个框中可以有一个是空的两个框中可以有一个是空的，即不执行任何操作，如图，即不执行任何操作，如图2.16所示。所示。图图2.14 图图2.15 图图2.16(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.19图图2.18和图和图2.19的作用都是打印的作用都是打印5个数：个数：1，2，3，4，5。可以看到，。可以看到，对同一个问题既可以用当型循环对同一个问题既可以用当型循环来处理，也可以用直到型循环来处理。来处理，也可以用直到型循环来处理。以上三种基本结构，有以下共同特点：以上三种基本结构，有以下共同特点：(1)只有一个入口。只有一个入口。(2)只有一个出口。请注意，一个菱形判断框有两个只有一个出口。请注意，一个菱形判断框有两个出口，而一个选择结构只有一个出口。不要将菱形出口，而一个选择结构只有一个出口。不要将菱形框的出口和选择结构的出口混淆。框的出口和选择结构的出口混淆。(3)结构内的每一部分都有机会被执行到。对每一个结构内的每一部分都有机会被执行到。对每一个框来说，都应有一条从入口到出口的路径通过它。框来说，都应有一条从入口到出口的路径通过它。图图2.20中没有一条从入口到出口的路径通过中没有一条从入口到出口的路径通过A框。框。(4)结构内不存在结构内不存在“死循环死循环”(无终止的循环无终止的循环)。图。图2.21就是一个死循环。就是一个死循环。图图2.20 图图2.21已经证明，由以上三种基本结构顺序组成的算法结已经证明，由以上三种基本结构顺序组成的算法结构，可以解决任何复杂的问题。由基本结构所构成构，可以解决任何复杂的问题。由基本结构所构成的算法属于的算法属于“结构化结构化”的算法，它不存在无规律的的算法，它不存在无规律的转向，只在本基本结构内才允许存在分支和向前或转向，只在本基本结构内才允许存在分支和向前或向后的跳转。向后的跳转。其实，基本结构不一定只限于上面三种，只要具有其实，基本结构不一定只限于上面三种，只要具有上述上述4个特点的都可以作为基本结构。人们可以自个特点的都可以作为基本结构。人们可以自己定义基本结构，并由这些基本结构组成结构化程己定义基本结构，并由这些基本结构组成结构化程序。例如，可以将图序。例如，可以将图2.22和图和图2.23这样的结构定义这样的结构定义为基本结构。图为基本结构。图2.23所示的是一个多分支选择结构，所示的是一个多分支选择结构，根据给定的表达式的值决定执行哪一个框。图根据给定的表达式的值决定执行哪一个框。图2.22和图和图2.23虚线框内的结构也是一个入口和一个出口，虚线框内的结构也是一个入口和一个出口，并且有上述全部的并且有上述全部的4个特点。由它们构成的算法结个特点。由它们构成的算法结构也是结构化的算法。但是，可以认为像图构也是结构化的算法。但是，可以认为像图2.22和和图图2.23那样的结构是由三种基本结构派生出来的。那样的结构是由三种基本结构派生出来的。因此，人们都普遍认为最基本的是本节介绍的三种因此，人们都普遍认为最基本的是本节介绍的三种基本结构。基本结构。图图2.22 图图2.232.4.4 用用N-S流程图表示算法流程图表示算法既然用基本结构的顺序组合可以表示任何复杂的算既然用基本结构的顺序组合可以表示任何复杂的算法结构，那么基本结构之间的流程线就属多余的了。法结构，那么基本结构之间的流程线就属多余的了。1973年美国学者年美国学者I.Nassi和和B.Shneiderman提出了一种提出了一种新的流程图形式。在这种流程图中，完全去掉了带新的流程图形式。在这种流程图中，完全去掉了带箭头的流程线。全部算法写在一个矩形框内，在该箭头的流程线。全部算法写在一个矩形框内，在该框内还可以包含其他的从属于它的框，或者说，由框内还可以包含其他的从属于它的框，或者说，由一些基本的框组成一个大的框。这种流程图又称一些基本的框组成一个大的框。这种流程图又称N-S结构化流程图。这种流程图适于结构化程序设结构化流程图。这种流程图适于结构化程序设计，因而很受欢迎。计，因而很受欢迎。N-S流程图用以下的流程图符号：流程图用以下的流程图符号：(1)顺序结构顺序结构:用图用图2.24形式表示。形式表示。A和和B两个框组两个框组成一个顺序结构。成一个顺序结构。(2)选择结构：用图选择结构：用图2.25表示。它与图表示。它与图2.15相应。当相应。当p条件成立时执行条件成立时执行A操作，操作，p不成立则执行不成立则执行B操作。请操作。请注意图注意图2.25是一个整体，代表一个基本结构。是一个整体，代表一个基本结构。图图2.24 图图2.25(3)循环结构：循环结构：当型循环结构用图当型循环结构用图2.26形式表示。形式表示。图图2.26表示当表示当p1条件成立时反复执行条件成立时反复执行A操作，直到操作，直到p1条件不成立为止。条件不成立为止。直到型循环结构用图直到型循环结构用图2.27形式表示。形式表示。用以上用以上3种种N-S流程图中的基本框，可以组成复杂的流程图中的基本框，可以组成复杂的N-S流程图，以表示算法。流程图，以表示算法。应当说明，在图应当说明，在图2.24、图、图2.25、图、图2.26、图、图2.27中的中的A框或框或B框，可以是一个简单的操作框，可以是一个简单的操作(如读入数据或如读入数据或打印输出等打印输出等)，也可以是，也可以是3个基本结构之一。例如，个基本结构之一。例如，图图2.24所示的顺序结构，其中的所示的顺序结构，其中的A框可以又是一个框可以又是一个选择结构，选择结构，B框可以又是一个循环结构。如图框可以又是一个循环结构。如图2.28所示那样，由所示那样，由A和和B这两个基本结构组成一个顺序这两个基本结构组成一个顺序结构。结构。图图2.26 图图2.27 图图2.28通过下面的几个例子，读者可以了解如何用通过下面的几个例子，读者可以了解如何用N-S流程流程图表示算法。图表示算法。例例2.11 将例将例2.1的求的求5!算法用算法用N-S图表示。见图图表示。见图2.29，它和图它和图2.7对应。对应。例例2.12 将例将例2.2的算法用的算法用N-S图表示。将图表示。将50名名 学生中学生中成绩高于成绩高于80分的学号和成绩打印出来。见图分的学号和成绩打印出来。见图2.30和和图图2.31，它们与图，它们与图2.8和图和图2.9对应。对应。例例2.13 将例将例2.3判定闰年的算法用判定闰年的算法用N-S图表示。见图图表示。见图2.32，它和图，它和图2.10对应。对应。例例2.14 将例将例2.4的算法用的算法用N-S图表示。见图图表示。见图2.33，它和，它和图图2.11对应，只是最后加了一个对应，只是最后加了一个“打印打印sum”框。框。例例2.15 将例将例2.5判别素数的算法用判别素数的算法用N-S流程图表示。流程图表示。图图2.29 图图2.30 图图2.31图图2.32 图图2.33由图由图2.12可以看出，这个流程图不是由三种基本结构可以看出，这个流程图不是由三种基本结构组成的。图中间那个循环部分，有两个出口组成的。图中间那个循环部分，有两个出口(一个一个从第二个菱形框下面出口，另一个在第一个菱形框从第二个菱形框下面出口，另一个在第一个菱形框右边出口右边出口)，不符合基本结构的特点。由于不能分，不符合基本结构