6.8　函数与结构化程序设计

人类进行程序设计只有几十年的历史。在最初进行软件生产的年代，软件的生产并没有什么章法可循，生产效率十分低下，失败的项目比比皆是。

大约从有科学家反对goto语句开始，人类才开始认真思考软件应该如何编写。在这方面有限的若干成果之一就是结构化程序设计思想。

结构化程序设计思想是现代编程技术的基础，甚至是基础的基础。这个思想大体是在20世纪的60年代末期和70年代，断断续续地由若干人提出并互相补充汇集而成的，目标是使程序的结构更清晰、更容易理解（“可读性”通常是衡量代码质量时仅次于正确性的一个指标，除了在对性能要求特别高的地方）、易于修改、易于调试、减少错误从而达到提高软件开发效率和成功率的目的。

“自顶向下”（top-down）、“逐步细化”（Stepwise Refinement）是结构化程序设计思想的主要内容之一，而函数是实现这种思路的一种强有力的主要的技术支持手段。

要完成一个较大的任务，首先把它分解成若干小问题；要完成一个复杂的问题，首先把它解析为若干简单的问题。这就是“自顶向下”、“逐步细化”（或称之为“逐步求精”）的主要含义——先考虑整体，再考虑局部，最后考虑细节。下面以一个程序从构思到完成的完整过程来说明这种思路以及如何通过函数达到程序的实现。

题目：求调和奇数的前n项的和，要求给出精确的结果。

6.8.1　明确程序功能

分析：由于题目要求给出精确的结果，所以double、float这些数据类型显然不可能加以考虑，结果只可能以分数形式给出。然而C语言没有分数这种类型，那么就只能自己创造出这种类型——这就是所谓数据结构的含义。可以考虑以两个int类型的量来分别表示一个分数的分子和分母，这虽然是一种很初级、很粗糙的数据结构，但依据目前所学的内容，也只能如此。

程序的功能应该是输入一个整数n的值，然后输出H(n)的分子和分母。此外应该注意到输入非正整数是没有意义的，而且输入的n不可以太大。

前面描述了程序的输入与输出，实际上完成了对程序功能的定义。现在可以写代码了。

且慢，这段代码完全无法编译！是的，没关系，反正现在离编译还早着呢。写上的这些内容并不会白写，至少以后可以作为程序的注释。结构化程序设计强调的是计划的正确性，然后逐步地渐进。如果一个程序的最初目标都是错的，那么基本上最后很难写正确。审题比做题更重要，难道不是么？

像这种用非程序设计语言描述程序或写出示意性代码的形式叫伪代码（Pseudocode），它可以用来描述程序员的思路并帮助程序员进行构思。可以在源代码编辑器中写，如果你不喜欢编译器因为对这些语言的不理解而引起的编译错误，可以把伪代码写成注释的形式，如同下面那样。当然也可以把伪代码独立地写在源程序之外，作为程序的一个文档。

有些人从来不使用伪代码或流程图。对于比较复杂的程序，这样很容易在细节中迷失正确的方向，甚至可能发生连题目都没搞清楚就开始编程的情形。与把题目做错相比，把题意弄错显然是更坏的事情。

6.8.2　确定程序的基本框架

在确定程序的基本框架之前，首先需要确定程序涉及的数据对象的数据结构。

由于程序的数据结构（用两个int类型的量分别表示和的分子、分母）已经确定，程序的基本功能也已经明确，所以可以进一步勾勒出程序的基本结构和框架。

尽管离全部完成尚早，但是这段代码已经可以运行并接受程序测试了。编译完成后，运行并输入－1、0，可以确信，程序的部分功能已经实现。

现在考虑n的值的界限问题。由于：

所以暂时可以把n！取值在int表示的范围内作为评估n的上限的临界条件。由于12! = 479001600, 13! = 6227020800，后者超出了int类型的表示范围，所以n的上限可以暂定为12。这仅仅是暂时的，为的是尽快完成主函数并进一步测试。

6.8.3　设计数据结构和算法

测试正确后，就可以专心考虑程序的核心算法了。为了总结出算法，一个切实可行的方法是自己用手工的方式把题目试着做几次（对于初学者尤其必要），如果用纸张、笔都无法完成，就绝对不可能编程了。

假设n的值为6，计算的步骤如下：

可以看到当n为6时整个计算过程是分6次完成的，而每次进行的计算的步骤是相同的。这显然可以用循环语句来描述。而且从上面可以看到，为了使计算的过程统一，和的分子的初值应该设为0，和的分母的初值应该设为1。下面的代码再向前推进一步，完成变量hfz、hfm的定义、循环语句及输出的功能。

计算部分没有完成，但是已经可以测试输出格式是否合乎要求了（执行printf("H(n)为%d/%d\n", n, hfz, hfm);）。

下面重点分析循环体内的算法，也就是“//计算”的部分。

6.8.4　任务的分解及函数原型

这部分的计算是求两个分数的和（“1/i”与“和的分子/和的分母”）。计算的第一步是通分，而通分的本质是求两个分母（“i”与“和的分母”）的最小公倍数。在求得最小公倍数之后，可以利用最小公倍数求得通分后两个分数的新的分子（“最小公倍数/i”及“最小公倍数/和的分母×和的分子”）及它们的和，这个和就是“和的分子/和的分母”加上“1/i”后得到的新的“和的分子”。此时可以把新的“和的分母”确定为刚刚求得的最小公倍数。最后对新得到的“和的分子/和的分母”还要进行约分（如果它们的最大公约数不为1的话）。这样“//计算”部分的算法可以进一步“细化”为：

以上的各个任务中，③可以简单地赋值实现，⑤在目前还做不到用一个函数完成（因为要改变两个变量的值，而函数只能求得一个值），其余的都可以用一个函数来完成。

由于完成①需要两个int类型的量（“i”与“和的分母”），求得一个int类型的量（最小公倍数），因而函数原型可写为：

完成②需要4个int类型的量（最小公倍数、“和的分子”、“i”、“和的分母”），求得的新的“和的分子”是一个int类型的量，因而函数原型写为：

同理，④的函数原型如下：

6.8.5　完成函数定义

函数定义及函数调用部分在此不再详述，下面是完成后的代码。此外n的上限经过计算验证可以达到24。

之后的任务就是程序的测试与调试了，如果没有错误被发现，程序就完成了。

从前面的例子可以看到，结构化程序设计有些像绘画时先打个草图或先画个轮廓，然后再逐步把各个部分绘制好一样。实际上生活中到处都可以看到top-down这种思想的影子，可惜的是在编程时很多人忘记了这点。经常看到有些初学者总是一行一行从上到下地写下去，这不是top-down。一行一行从上到下地写下去，不可能把代码写好，这种风格在程序稍微复杂些时就会显得左支右绌、捉襟见肘。

结构化程序设计不仅使得程序本身变得有条理、层次清晰，每个部分的结构和意图都清晰可见，实际上也使得编程过程本身变得很有条理，具有可规划性。在这种思想的指导下，编程的步骤本身也变得井井有条。下面分别对本小节程序的编程过程步骤以及程序结构的特点做一小结。

6.8.6　编程的步骤

（1）明确定义程序的总体目标或功能，而且越明确越好。可以把这种目标作为注释写在代码中或其他文档中，这是编程总的依据。

（2）将程序的目标粗略地分解为若干比较简单的问题，这时可以在保证程序结构正确性的前提下勾勒出main()的大致框架。那些比较简单的问题可以提炼成若干个函数（前提是不违背函数只能求一个值的原则），写出函数原型以及空的函数定义。

（3）审视main()的结构和框架，确保无误之后可以开始逐个考虑（1）中没有具体完成的各个函数定义。这些函数本身可能依然是比较大或比较复杂的任务，同样按照（1）的方式明确这些函数的功能，然后继续把这些函数解析成更小或更简单的任务。继续写出函数原型和空的函数定义，要保证函数的功能能够简单到可以被完全把握，然后再“各个击破”(divide and conquer)。不要写太长和太复杂的函数（本书对初学者的建议是每个函数不超过20行，不包括注释），如果一个函数太长说明编程者还没有透彻地对函数的功能进行分析和分解。如果你发现很难为一个函数取一个简洁的名字，同样说明你没有对它的功能进行透彻的分析或者分解。

（4）在进行（1）、（2）时尽量作到每个步骤都保证代码在语法上的正确性，可以用空函数、空语句、假设的数据以及注释来达到这个目的。这样便于在程序编写过程中进行不断测试以保证程序在总的大框架范围内的正确性。这还有另外一个好处，即使得编程以“一步一个脚印”的方式进行，有利于编程者对程序的正确性和进度增强信心。

（5）对各个功能模块进行透彻的分析并且明确地写出来，这样才能在进行完每个步骤之后都能进行程序测试，而这种测试对于编程具有极大的好处：要么会带给你自信，要么会帮助你发现程序中的问题。

6.8.7　代码结构

（1）结构化程序设计把问题分解为若干子问题，每个子问题用一个函数来完成，这样程序中每个函数的结构本身都比较简单，正确性容易保证。结构化程序设计要求各个模块之间的联系越弱越好（最近流行的术语叫“高内聚低耦合”），C语言中的形参只是简单获得实参的值以及函数只有一个返回值就体现了这种思想。

（2）结构化程序要求每个模块只有一个出口和入口，这要求每个函数应该只有一个return语句，这一点本书在函数功能十分简单且代码很容易被理解的情况下没有严格遵守。

（3）结构化程序设计通过函数调用来描述每个函数模块的功能而隐藏了各个被调用函数的实现细节，这种抽象实际上就是人类概括性思维在编程中的体现。只有通过概括性的思维才可能把握一个比较复杂的事物。写出函数原型的过程实际上就是在实现这种概括性思维。

（4）结构化程序设计中完成的各个简单的小函数，由于被局部化，所以易于被修改、管理，且具有可重用性。只要没修改函数的出口和入口（返回值的类型及形参的类型）以及函数的功能定义，那么这种修改就是局部的，不会影响全局、发生“牵一发而动全身”的情况，“牵一发而动全身”的情况是编程时极其忌讳的。从这里也可以看出对程序以及各个函数功能做透彻、正确的分析的重要性，因为对函数功能或出入口的修改很可能意味着程序的全面返工。

练习

独立完成例题程序。