第2单元控制结构 第2单元控制结构 本单元教学目标 介绍结构化程序设计方法的基本思想以及C++的基本控制结构和控制转移语句 学习要求 通过本单元学习,掌握结构化程序设计方法的基本思想和C++的几种基本控制转移语 句,熟悉使用伪代码的编程方法 授课内容 21程序的基本控制结构 我们知道,C++源程序由若干函数构成,而函数又是由语句构成的。对于一个程序员来 说,编程序的一个主要内容就是如何将解决一个应用问题所使用的算法用C++的语句和函 数来描述。换句话说,也就是如何组织C++程序的结构。在本单元中,首先要介绍的是构 成程序的几种基本结构,并进而介绍如何使用这些基本结构编写比较复杂的程序。 结构化设计方法是以模块化设计为中心,将待开发的软件系统划分为若干个相互独立的 模块,这样使完成每一个模块的工作变单纯而明确,为设计一些较大的软件打下了良好的基 础。由于模块相互独立,因此在设计其中一个模块时,不会受到其它模块的牵连,因而可将 原来较为复杂的问题化简为一系列简单模块的设计。模块的独立性还为扩充已有的系统、建 立新系统带来了不少的方便,因为我们可以充分利用现有的模块作积木式的扩展。按照结构 化设计方法设计出的程序具有结构清晰、可读性好、易于修改和容易验证的优点。C++是 种支持结构化程序设计思想的程序设计语言,使用C++编写程序时,应该遵循结构化程 序设计方法 在结构化程序设计方法中,模块是一个基本概念。一个模 块可以是一条语句、一段程序、一个函数等。在流程图中,模 程序模块 块用一个矩形框表示,如图2-1所示。模块的基本特征是其仅 有一个入口和一个出口,即要执行该模块的功能,只能从该模 块的入口处开始执行(用图2-1矩形上面的有向线段表示)执 行完该模块的功能后,从模块的出口转而执行其他模块的功图2-1程序模块 能(用图2-1矩形下面的有向线段表示),即使模块中包含多个
第 2 单元 控制结构 - 17 - 第 2 单元 控制结构 本单元教学目标 介绍结构化程序设计方法的基本思想以及Ｃ++的基本控制结构和控制转移语句。 学习要求 通过本单元学习，掌握结构化程序设计方法的基本思想和Ｃ++的几种基本控制转移语 句，熟悉使用伪代码的编程方法。 授课内容 2.1 程序的基本控制结构 我们知道，Ｃ++源程序由若干函数构成, 而函数又是由语句构成的。对于一个程序员来 说，编程序的一个主要内容就是如何将解决一个应用问题所使用的算法用Ｃ++的语句和函 数来描述。换句话说，也就是如何组织Ｃ++程序的结构。在本单元中，首先要介绍的是构 成程序的几种基本结构，并进而介绍如何使用这些基本结构编写比较复杂的程序。 结构化设计方法是以模块化设计为中心，将待开发的软件系统划分为若干个相互独立的 模块, 这样使完成每一个模块的工作变单纯而明确，为设计一些较大的软件打下了良好的基 础。由于模块相互独立，因此在设计其中一个模块时，不会受到其它模块的牵连，因而可将 原来较为复杂的问题化简为一系列简单模块的设计。模块的独立性还为扩充已有的系统、建 立新系统带来了不少的方便，因为我们可以充分利用现有的模块作积木式的扩展。按照结构 化设计方法设计出的程序具有结构清晰、可读性好、易于修改和容易验证的优点。Ｃ++是 一种支持结构化程序设计思想的程序设计语言, 使用Ｃ++编写程序时, 应该遵循结构化程 序设计方法。 在结构化程序设计方法中, 模块是一个基本概念。一个模 块可以是一条语句、一段程序、一个函数等。在流程图中, 模 块用一个矩形框表示, 如图 2-1 所示。模块的基本特征是其仅 有一个入口和一个出口, 即要执行该模块的功能, 只能从该模 块的入口处开始执行 (用图2-1矩形上面的有向线段表示), 执 行完该模块的功能后, 从模块的出口转而执行其他模块的功 能 (用图2-1矩形下面的有向线段表示), 即使模块中包含多个 程序模块 图2-1 程序模块
第2单元控制结构 语句,也不能随意从其他语句开始执行,或提前退出模块 按照结构化程序设计的观点,任何算法功能都可以通过由程序模块组成的三种基本程 序结构的组合:顺序结构、选择构和循环结构来实现。 顺序结构由两个程序模块串接构成,如图2-2左部所示。由图中可以看出,这两个程序 模块是顺序执行的,即首先执行<程序模块1>,然后执行<程序模块2>。 顺序结构中的两个程 序模块可以合并成一个新 的程序模块,即将图2-2 程序模块1 中的左边部分整个看成一1 个新的模块,如图2-2的1 新程序模块 右部。通过这种方法,可 程序模块2 以将许多顺序执行的语句 合并成一个比较大的程序 模块。但无论怎样合并, 生成的新的程序模块仍然 是一个整体,只能从模块 图2-2顺序结构 的顶部(入口)进入模块 开始执行模块中的语句,执行完模块中的所有语句之后再从模块的底部(出口)退出模块。 事实上,顺序结构是最常见的程序结构形式,在一般程序中大量存在。但是设想一下,是不 是所有程序都可以只使用顺序结构编写呢?显然答案是否定的。在求解实际问题时,常常要 根据输入数据的实际情况进行逻辑判断,对不同的结果分别进行不同的处理:或者需要反复 执行某些程序段落,以避免多次重复编写结构相似的程序段落带来的程序结构上的臃肿。这 就需要在程序中引入选择结构和循环结构。一个结构化程序正是由这三种基本程序结构交替 综合而构成的。 选择结构如图2-3所 示。从图中可以看出,根 据逻辑条件成立与否,分 不成立 条件 别选择执行<模块1>或 者<模块2>。虽然选择结 成立 新程序模块 构比顺序结构稍微复杂了 程序模块1 程序模块2 点,但是仍然可以将其 整个作为一个新的程序模 块:一个入口(从顶部进 入模块开始判断),一个出 图2-3选择结构(多分支) 口(无论执行了<模块1>还 是<模块2>,都应从选择结构框的底部出去)。 在编程实践中,还可能遇到选择结构中的一个分支没有实际操作的情况,如图2-4所示。 这种形式的选择结构可以看成是图2-3中的选择结构的特例
第 2 单元 控制结构 - 18 - 语句, 也不能随意从其他语句开始执行, 或提前退出模块。 按照结构化程序设计的观点, 任何算法功能都可以通过由程序模块组成的三种基本程 序结构的组合: 顺序结构、选择构和循环结构来实现。 顺序结构由两个程序模块串接构成, 如图 2-2 左部所示。由图中可以看出, 这两个程序 模块是顺序执行的, 即首先执行<程序模块 1>, 然后执行<程序模块 2>。 顺序结构中的两个程 序模块可以合并成一个新 的程序模块，即将图 2-2 中的左边部分整个看成一 个新的模块，如图 2-2 的 右部。通过这种方法，可 以将许多顺序执行的语句 合并成一个比较大的程序 模块。但无论怎样合并， 生成的新的程序模块仍然 是一个整体，只能从模块 的顶部 (入口) 进入模块 开始执行模块中的语句，执行完模块中的所有语句之后再从模块的底部 (出口) 退出模块。 事实上，顺序结构是最常见的程序结构形式，在一般程序中大量存在。但是设想一下，是不 是所有程序都可以只使用顺序结构编写呢？显然答案是否定的。在求解实际问题时，常常要 根据输入数据的实际情况进行逻辑判断，对不同的结果分别进行不同的处理；或者需要反复 执行某些程序段落，以避免多次重复编写结构相似的程序段落带来的程序结构上的臃肿。这 就需要在程序中引入选择结构和循环结构。一个结构化程序正是由这三种基本程序结构交替 综合而构成的。 选择结构如图 2-3 所 示。从图中可以看出，根 据逻辑条件成立与否，分 别选择执行 <模块 1>或 者<模块 2>。虽然选择结 构比顺序结构稍微复杂了 一点，但是仍然可以将其 整个作为一个新的程序模 块：一个入口 (从顶部进 入模块开始判断)，一个出 口(无论执行了<模块 1>还 是<模块 2>，都应从选择结构框的底部出去)。 在编程实践中，还可能遇到选择结构中的一个分支没有实际操作的情况，如图 2-4 所示。 这种形式的选择结构可以看成是图 2-3 中的选择结构的特例。 程序模块1 图2-2 顺序结构 程序模块2 新程序模块 图2-3 选择结构(多分支） 程序模块1 新程序模块 条件 程序模块2 不成立 成立
循环结构如图2-5所 示。在进入循环结构后首先---- 判断条件是否成立,如果成 不成立1 立则执行<程序模块>,反之 条件 则退出循环结构。执行完< 成立 新程序模块 程序模块>后再去判断条件 如果条件仍然成立则再次执1程序模块 行内嵌的<程序模块>,循环 往复,直至条件不成立时退L_ 出循环结构。 与顺序和选择结构相 图2-4一个分支没有实际操作的选择结构 同,循环结构也可以抽象为 个新的模块。图2-5中的循 环结构可以描述为“当条件成 立时反复执行程序模块”,故 不成立 又称为 while(当)型循环。除 成立 程序模块 了 while型循环以外,还可以 构造出其他类型的循环来,如 程序模块 do- while型循环结构,其特点 是进入循环结构后首先执行< 程序模块>,然后再判断条件 是否成立,如果成立则再次执 图2.5 while循环结构 行<程序模块>,直到条件不成 立时退出循环结构。do- while型循环结构如图2-6所示。 程序模块 新程序模块 条件 不成立 图2-6do- while型循环
第 2 单元 控制结构 - 19 - 循环结构如图 2-5 所 示。在进入循环结构后首先 判断条件是否成立，如果成 立则执行<程序模块>，反之 则退出循环结构。执行完< 程序模块>后再去判断条件, 如果条件仍然成立则再次执 行内嵌的<程序模块>，循环 往复，直至条件不成立时退 出循环结构。 与顺序和选择结构相 同, 循环结构也可以抽象为 一个新的模块。图 2-5 中的循 环结构可以描述为“当条件成 立时反复执行程序模块”，故 又称为 while (当) 型循环。除 了 while 型循环以外, 还可以 构造出其他类型的循环来，如 do-while 型循环结构，其特点 是进入循环结构后首先执行< 程序模块>，然后再判断条件 是否成立，如果成立则再次执 行<程序模块>，直到条件不成 立时退出循环结构。do-while 型循环结构如图 2-6 所示。 图2-4 一个分支没有实际操作的选择结构 程序模块 新程序模块 条件 不成立 成立 条件 成立 不成立 图2-6 do-while型循环 新程序模块 程序模块 图2.5 while循环结构 条件 成立 不成立 新程序模块 程序模块
22“自顶向下,逐步求精”的程序设计方法 在上面介绍的顺序、选择和循环三种基本程序结构中的程序模块又可以是由这三种基本 程序结构抽象而成的新程序模块,因此可以通过组合、嵌套这些基本程序结构来构造更复杂 的程序。已经证明,一个合理的程序,总可以化为顺序、选择和循环这三种基本程序结构的 某种组合。 结构化程序设计支持“自顶向下,逐步求精”的程序设计方法。自顶向下的程序设计方 法从问题本身开始,经过逐步求精,将解决问题的步骤分解为由基本程序结构模块组成的结 构化程序框图,据此就很容易编写出结构良好、易于调试的程序来。 「例2-1“验证”哥德巴赫猜想。哥德巴赫猜想是数论中的一个著名难题,是由法国数学 爱好者克里斯蒂安·德巴赫于1742年在给著名数学家欧拉的一封信中提出的。“哥德巴赫 猜想”可以表述为:任何一个大于等于4的偶数均可以表示为两个素数之和。尽管这个问题 看来如此简明清晰,但二百多年来虽有无数数学家为其呕心沥血、绞尽脑汁,却始终无人 能够证明或者证伪这个猜想2。 我们将这个问题作为一个练习,在有限的范围内验证哥德巴赫猜想:编写一段程序,验 证大于4,小于某一上限M的所有偶数是否都能被分解为两个素数之和。如果一但发现某个 偶数不能被分解为两个素数之和,则证实了哥德巴赫猜想是错误的(果真如此,则可称是数 学史上的一大发现!):否则证实哥德巴赫猜想在所给的范围内成立 算法:首先画出代表解决该问题的程序模块,见图2-7 然后根据题意对图27中的程序模块进行初步 分解,其思路如下:逐个生成由4到M之间的所有 偶数,一一验证其是否能够被分解为两个素数之和。 验证哥德巴赫猜想 具体方法是声明一个变量x,令其初值等于4,然后 每次在x上加2,以产生各偶数并验证x是否可以被 分解为两个素数之和直到x不小于M为止。显然,图2-7验证哥德巴赫猜想 这是一个循环结构,其分解图见图2-8。 在图2-8中的初步分解中用粗线框表示了基本程序结构的嵌套组合情况。从图中可以 看出,最内层的粗线框中是两个顺序排列的程序模块,它们一起构成了循环结构的内嵌程序 模块。循环模块又和最前面的语句模块构成了顺序结构 1如果一个程序满足下列条件,就是一个合理的程序 1.整个程序只有一个入口和一个出口 2.从程序的入口到所有模块都至少有一条路径可达。 这些条件是非常容易满足的。通过合并那些不止一个的入口和出口,以及删除那些不可到达的模块(这些模 块对程序的功能没有任何影响,任何程序都可以化为一个合理的程序。 260-70年代,我国数学家陈景润证明了一个条件略宽的定理,即“任何一个大于4的偶数,均可以分解为 一个素数与两个素数的积之和”,从而向最终解决哥德巴赫猜想又迈进了一步
第 2 单元 控制结构 - 20 - 2.2 “自顶向下, 逐步求精”的程序设计方法 在上面介绍的顺序、选择和循环三种基本程序结构中的程序模块又可以是由这三种基本 程序结构抽象而成的新程序模块, 因此可以通过组合、嵌套这些基本程序结构来构造更复杂 的程序。已经证明, 一个合理的程序1 , 总可以化为顺序、选择和循环这三种基本程序结构的 某种组合。 结构化程序设计支持“自顶向下, 逐步求精”的程序设计方法。自顶向下的程序设计方 法从问题本身开始，经过逐步求精，将解决问题的步骤分解为由基本程序结构模块组成的结 构化程序框图，据此就很容易编写出结构良好、易于调试的程序来。 [例 2-1]“验证”哥德巴赫猜想。哥德巴赫猜想是数论中的一个著名难题, 是由法国数学 爱好者克里斯蒂安·哥德巴赫于 1742 年在给著名数学家欧拉的一封信中提出的。“哥德巴赫 猜想”可以表述为：任何一个大于等于 4 的偶数均可以表示为两个素数之和。尽管这个问题 看来如此简明清晰, 但二百多年来, 虽有无数数学家为其呕心沥血、绞尽脑汁, 却始终无人 能够证明或者证伪这个猜想2。 我们将这个问题作为一个练习, 在有限的范围内验证哥德巴赫猜想：编写一段程序, 验 证大于 4, 小于某一上限 M 的所有偶数是否都能被分解为两个素数之和。如果一但发现某个 偶数不能被分解为两个素数之和, 则证实了哥德巴赫猜想是错误的 (果真如此, 则可称是数 学史上的一大发现！)；否则证实哥德巴赫猜想在所给的范围内成立。 算 法: 首先画出代表解决该问题的程序模块, 见图 2-7。 然后根据题意对图 2-7 中的程序模块进行初步 分解, 其思路如下：逐个生成由 4 到 M 之间的所有 偶数，一一验证其是否能够被分解为两个素数之和。 具体方法是声明一个变量 x, 令其初值等于 4, 然后 每次在 x 上加 2, 以产生各偶数并验证 x 是否可以被 分解为两个素数之和, 直到 x 不小于 M 为止。显然, 这是一个循环结构, 其分解图见图 2-8。 在图 2-8 中的初步分解中用粗线框表示了基本程序结构的嵌套组合情况。 从图中可以 看出, 最内层的粗线框中是两个顺序排列的程序模块, 它们一起构成了循环结构的内嵌程序 模块。循环模块又和最前面的语句模块构成了顺序结构。 1 如果一个程序满足下列条件, 就是一个合理的程序: 1. 整个程序只有一个入口和一个出口; 2. 从程序的入口到所有模块都至少有一条路径可达。 这些条件是非常容易满足的。通过合并那些不止一个的入口和出口, 以及删除那些不可到达的模块(这些模 块对程序的功能没有任何影响), 任何程序都可以化为一个合理的程序。 2 60-70 年代, 我国数学家陈景润证明了一个条件略宽的定理, 即“任何一个大于 4 的偶数, 均可以分解为 一个素数与两个素数的积之和”, 从而向最终解决哥德巴赫猜想又迈进了一步。 验证哥德巴赫猜想 图2-7验证哥德巴赫猜想
图2-8中的框图是相当粗糙的,因为如何“验证x是否能被分解为两个素数之和”并不 清楚,因此继续对这个问题进行分解。“验证x是否能被分解为两个素数之和”的步骤可以 这样考虑:首先用x减去最小的素数2,然后看其差是否仍为素数,如果是,则验证结束,可 以打印出该偶数的分解表达式。否则,换一个更大的素数,再看x与这个素数的差是否为素 数。如果不是则仍进行循环,直到用于检测的素数已经大于x2而x与其差仍不是素数。这 时即可宣布一个伟大的发现:哥德巴赫猜想不成立!(?!) 图2-9给出了图2-8中的程序模块“验 证x是否能被分解为两个素数之和”的进 步分解。这里引入了一个新的变量p,用 于存放已经生成的素数。 图2-9中的模块“生成下一个素数” 还可以继续分解。实际上,在大多数程序 否 设计语言中,条件“x-p不是素数?”并不 能简单地写成一个表达式,也需要进一步 细化分解。在实际编程时,既可以将图2-9 直接代入图2-8,编成一个较大的程序,也 验证x是否能被分 解为两个素数之和 可以单独将图2-9中的程序模块编写为一 个函数,由主函数调用。一般来讲,一个程 序模块的大小最好不要超过一页打印纸1 +2 (约60行左右),这样程序的结构比较清 晰。如果程序模块太大则可以进一步分解 以上过程可以总结如下: 首先从题目本身开始,找出解决问题:L 的基本思路,并将其用结构化框图表示出 来。这个框图可能是非常粗糙的,仅仅是 一个算法的轮廓,但可以作为进一步分析图2-8验证哥德巴赫猜想的初步分解 x/2且xD不是常费、否 验证x是否能分解为 两个素数之和 生成下一个素数 不成立的情况 打印出X的分解情况 图2-9“验证x是否能分解为两个素数之和”的进一步分解
第 2 单元 控制结构 - 21 - 图 2-8 中的框图是相当粗糙的，因为如何“验证 x 是否能被分解为两个素数之和”并不 清楚, 因此继续对这个问题进行分解。“验证 x 是否能被分解为两个素数之和”的步骤可以 这样考虑: 首先用 x 减去最小的素数 2, 然后看其差是否仍为素数, 如果是, 则验证结束, 可 以打印出该偶数的分解表达式。否则, 换一个更大的素数, 再看 x 与这个素数的差是否为素 数。如果不是则仍进行循环, 直到用于检测的素数已经大于 x/2 而 x 与其差仍不是素数。这 时即可宣布一个伟大的发现: 哥德巴赫猜想不成立!(?!) 图 2-9 给出了图 2-8 中的程序模块“验 证 x 是否能被分解为两个素数之和”的进 一步分解。这里引入了一个新的变量 p, 用 于存放已经生成的素数。 图 2-9 中的模块“生成下一个素数” 还可以继续分解。实际上, 在大多数程序 设计语言中，条件“x–p 不是素数?”并不 能简单地写成一个表达式, 也需要进一步 细化分解。在实际编程时, 既可以将图 2-9 直接代入图2-8, 编成一个较大的程序, 也 可以单独将图 2-9 中的程序模块编写为一 个函数, 由主函数调用。一般来讲, 一个程 序模块的大小最好不要超过一页打印纸 （约 60 行左右），这样程序的结构比较清 晰。如果程序模块太大则可以进一步分解。 以上过程可以总结如下： 首先从题目本身开始, 找出解决问题 的基本思路, 并将其用结构化框图表示出 来。这个框图可能是非常粗糙的, 仅仅是 一个算法的轮廓, 但可以作为进一步分析 x = 4 x < M 验证x 是否能被分 解为两个素数之和 图2-8 验证哥德巴赫猜想的初步分解 x = x+2 否 是 验证x是否能分解为 两个素数之和 p = 2 p<x/2且x-p不是常数 生成下一个素数 是 p>=x/2? 处理哥德巴赫猜想 不成立的情况 打印出X的分解情况 否 是 否 图2-9 “验证x是否能分解为两个素数之和”的进一步分解