点击查看第一章
点击查看第二章

第3章

函数和数组
除基本类型外，C还包含派生类型。图3-1显示了C中基本类型和派生类型的图形表示。基本类型与派生类型的关系好比是砖与墙的关系。派生类型使用一个或多个基本类型作为构建块构建。函数和数组都是C中的派生类型。

在C中，可以通过多种方式解释函数的概念。这里有些例子：
□函数是子程序。它允许你将大型计算任务分解为较小的计算任务。
□函数是由大括号分隔的一段代码，它执行一些明确定义的任务并返回一个值。
□函数是程序的构建块。它有助于使现有代码可重用。
□函数也被视为C中的派生类型。请参见图3-1。
□函数是扩展C语言库的一种方法。
每个函数都需要编写。编写函数意味着编写该函数的程序语句。C中的函数可以分为三类：main()函数、库函数和用户定义函数。在此简要描述这些类别：
□main()函数：C程序中此函数必不可少。每个C程序中都会有一个（也是唯一一个）main()函数。当操作系统执行C程序时，它实际上执行的是main()函数。main()函数根据要求调用库函数和用户定义的函数。程序员需要编写main()函数的代码。
□库函数：这些函数也称为系统定义函数或内置函数。例如，printf()和scanf()是库函数。库函数在C程序中是可选的。但是，构建一个没有库函数的有用程序几乎是不可能的。程序员不需要编写库函数代码。编译器开发人员对库函数进行编码，编译它们，并将它们放在库中供你使用。
□用户定义函数：用户定义函数在C程序中是可选的。用户定义函数根据要求调用其他用户定义函数或库函数。程序员需要对用户定义函数进行编写。
从技术上讲，main()函数也是用户定义函数，因为程序员（即用户）需要编写（即定义）该函数。但是在程序可能包含的所有函数中，函数main()享有特殊的状态。实际上，函数main()代表一个完整的C程序。当操作系统执行C程序时，它实际上执行的是main()函数。没有其他函数可以调用main()函数。另一方面，main()函数当然可以调用其他函数。main()函数在C程序中是必需的，而其他函数都是可选的。这证明了main()函数的类别是单独的。
□数组：数组是具有相同数据类型和名称，但下标或索引不同的项目列表。数组可以是一维的或多维的。一维数组可以图形方式表示为列表。二维数组可以图形方式表示为表格。三维数组可以图形方式表示为方块或立方体。对于四维和更高维数组，不能进行图形表示。

3.1　确定圆周率的值

问题
你想确定数学常数的值。
解决方案
编写一个C程序，使用蒙特卡洛方法确定数学常数的值，使用以下规格说明：
□程序要求用户输入投掷次数为N（2≤N≤5000）。如果用户输入该范围之外的数字N，则程序要求用户重新输入此数字。
□每次投掷都会生成一对坐标x和y，范围为0≤x, y≤1，用来表示一个点。然后测试它以确定产生的点是否位于圆内。
程序使用图3-2中所示的标准公式，计算的值。
代码
以下是使用这些规格说明编写的C程序的代码。在文本编辑器中键入以下C程序，并将其保存在文件夹C:Code中，文件名为monte.c：

编译并执行此程序。这个程序的运行结果在这里给出：

工作原理
（pi）的准确值是3.141 59。阻止你接近此准确值的最重要因素是C编译器生成的随机值不是真正随机的。尽管有这个缺点，此程序已经足够准确地确定了的值。如果使用函数srand()，则可以向此函数输入种子值，然后生成的随机值将更随机。
蒙特卡洛市位于摩纳哥，以赌博和赌场而闻名。蒙特卡洛方法基于简单的概率定律，其工作原理如下：想象一个边长为2r的正方形和半径为r的圆，两者都与坐标系的原点O同心。为简单起见，你只考虑第一象限中这些图形的四分之一部分，如图3-2所示。如果你随机在正方形内的任何地方生成大量的点，那么这些点将几乎均匀地占据所有可用空间。在此程序中，你最多可以生成5 000个点。
在LOC 18～21中，创建一对坐标（fltX和fltY），其值在0～1的范围内（包括边界值），并且这对坐标定义位于正方形某处的点（如图3-2所示）。函数rand()创建一个0～RAND_MAX范围内的随机整数，其中RAND_MAX是编译器定义的常量。在LOC 22中，计算原点与产生的点之间的距离fltR。生成的每个点都会增加intSquare的值，但是，如果该点的fltR值等于或小于1，那么该点也会增加intCircle的值。在图3-2中，变量intCircle和intSquare分别由项N_Circle和N_Square表示。
跨越LOC 17～25的for循环迭代intToss次。程序在LOC 26中计算的值。在LOC 27中，将该值显示在屏幕上。

3.2　从数字列表中选择质数

问题
你想从序列号列表中选择质数，例如1到1000。
解决方案
编写一个C程序，使用埃拉托斯特尼的筛法从1到N的整数列表中选择质数，具有以下规格说明：
□程序生成从1到N的整数列表。
□程序删除列表中的第一个数字1，因为根据定义，1不是质数。然后程序删除列表中2的倍数，但不删除2，因为2是质数。
□程序删除列表中3的倍数（3表示2之后的下一个未删除数字），然后是5的倍数（5表示3之后的下一个未删除数字），然后是下一个未删除数（最多为N的平方根）的倍数。
最后，你将获得一个质数列表。
代码
以下是使用这些规格说明编写的C程序的代码。在文本编辑器中键入以下C程序并将其保存在文件夹C:Code中，文件名为erato.c：

编译并执行此程序。这个程序的运行结果在这里给出：

工作原理
埃拉托斯特尼筛法的工作原理很简单。当你想要计算前N个质数时，此方法特别有用。在这种方法中，简单地从1到N的序列号列表中逐个删除非质数，最后，在1到N的序列号列表中只留下质数。图3-3说明了埃拉托斯特尼筛法的工作原理。

在LOC 5～24中定义的函数sieve()执行筛选数字和选择质数的任务。在LOC 4中定义了一个名为status大小为 SIZE的int类型数组，SIZE定义为1000。此数组中的所有单元格都将填充1或0。这些1和0是状态指示器，0表示质数，1表示非质数。例如，单元格status[17]将填充0，表示17是质数；单元格status[20]将填充1，表示20是非质数，等等。
在LOC 8和9中，借助于for循环，该数组填充0。你忽略此数组中的第一个单元格，即status[0]。根据定义，数1不是质数，因此，在LOC 23中，程序将整数1置于单元格status[1]中。你知道数字2和3是质数，因此不会影响相应单元格的状态，因为这些单元格中已经填充了0。
在LOC 12～14中，程序在for循环的帮助下删除列表中的所有偶数（2除外）。实际上，程序用状态指示符1填充相应的单元格。在LOC 15～22中，程序删除列表中剩余的非质数。实际上，程序用状态指示符1填充相应的单元格。
在LOC 28中调用函数sieve()，并使用所需的状态指示符填充数组status。当LOC 28执行完成时，质数列表已经在机器的存储器中准备好了。LOC 30要求你输入数字N，范围为1～1000。在LOC 34～35中，在屏幕上显示数字1到N范围内的质数。

3.3　使用递归进行数字求和

问题
你希望使用递归来进行数字求和。
解决方案
首先，你必须以递归形式表达此问题。如果符号表示求和，则表示递归形式中n个数的求和问题如下：

每次递归调用，计算n的问题都会简化到计算(n｜1)的问题。随着每次递归调用n的值减1，递归将以有限数量的步骤终止（递归调用）。
根据以下规格说明编写一个使用递归执行数字求和的C程序：
□程序使用名为summation()的用户定义函数来执行数字求和。
□函数summation()调用自身来执行求和。
代码
以下是使用这些规格说明编写的C程序的代码。在文本编辑器中键入以下C程序，并将其保存在文件夹C:Code中，文件名为sum2.c：

编译并执行此程序。这个程序的运行结果在这里给出：

工作原理
在这个程序中，LOC 3～9包含main()函数的定义。LOC 10～16由summation()函数的定义组成。在LOC 6中，调用函数summation()，并将整数值4作为参数传递给该函数。这是函数summation()的第一次调用。参数的值（即4）被赋值给参数intM，它作为函数summation()内的局部变量。函数summation()由两个return语句组成：如果intM的值为1，则返回值1，否则，返回一个由函数调用组成的表达式（参见LOC 15）。因为intM的值是4，所以执行LOC 15，它想要返回以下值：

为了计算该表达式的值，计算机再次使用参数3调用函数summation()。这是对summation()的第二次调用。summation()中的局部变量在第一次执行时的值存储在堆栈中而不会被丢弃。在summation()的第二次执行期间，intM的值为3，因此，再次执行LOC 15，现在想要返回以下值：

要计算此表达式的值，计算机再次使用参数2调用函数summation()。这是对summation()的第三次调用。summation()中的局部变量在第二次执行期间的值存储在堆栈中而不会被丢弃。在summation()的第三次执行期间，M的值为2，因此，再次执行LOC 15，现在想要返回以下值：

为了计算该表达式的值，计算机再次使用参数1调用函数summation()。这是对summation()的第四次调用。summation()中的局部变量在第三次执行期间的值存储在堆栈中而不会被丢弃。在summation()的第四次执行期间，intM的值为1，因此，此时执行LOC 13（而不是LOC 15）。LOC 13由return语句组成，执行此return语句并返回整数值1。随着return语句的执行，summation()的第四次执行也变得完整。
现在计算机控制被转移回summation()的第三次执行。回想一下，在计算表达式C时（即在summation()的第三次执行期间）对第四次执行summation()进行了调用。第四次执行summation()返回的值只是1，而这是summation(1)的值。在表达式C中插入此值，如下所示：

因此，表达式C的值为3，这是summation()的第三次执行。计算机执行return语句并返回值3以完成LOC 15的执行以及summation()的第三次执行。
现在计算机控制被转移回summation()的第二次执行。回想一下，在计算表达式B时（即在第二次执行summation()期间），调用了summation()的第三次执行。第三次执行summation()返回的值只是3，这是summation(2)的值。在表达式B中插入此值，如下所示：

因此，表达式B的值变为6，这是summation()的第二次执行。计算机执行return语句并返回值6，以便完成LOC 15的执行以及summation()的第二次执行。
现在计算机控制被转移回summation()的第一次执行。回想一下，在计算表达式A时（即在第一次执行summation()期间），调用了第二次执行summation()。第二次执行summation()返回的值只是6，而这是summation(3)的值。在表达式A中插入此值，如下所示：

因此，表达式A的值变为10，这是summation()的第一次执行。计算机执行return语句并返回值10以完成LOC 15的执行以及summation()的第一次执行。第一次执行summation()的调用是在LOC 6中完成的。第一次执行summation()返回的值（现在只有10）现在被赋值给intR（参见LOC 6）。这是整数1到4的求和的结果。在执行LOC 7之后，在屏幕上显示该结果。

3.4　使用递归计算斐波那契数列

问题
你想使用递归计算斐波那契数列。
解决方案
编写一个C程序，使用具有以下规格说明的递归计算斐波那契数列：
□程序应计算前N个斐波那契数。
□程序由一个名为fib()的用户定义函数组成，该函数递归调用自身以计算斐波那契数。
□在屏幕上显示计算出的斐波那契数。
代码
以下是使用这些规格说明编写的C程序的代码。在文本编辑器中键入以下C程序，并将其保存在文件夹C:Code中，文件名为fibona2.c：

编译并执行此程序。这个程序的运行结果在这里给出：

工作原理
此程序计算前N个斐波那契数。跨越LOC 6～9的do-while循环接受数字N的值，并将其赋值给int类型变量intN。跨越LOC 11～15的for循环计算N个斐波那契数。LOC 13在屏幕上显示计算出的斐波那契数。LOC 13还使用输入参数intK调用函数fib()。函数fib()在LOC 19～27中定义。在LOC 26中，对该函数进行两次递归调用。在第一次递归调用中，输入参数的值减1，而在第二次递归调用中，输入参数的值减少2，在连续的递归调用中，输入参数的值继续减小，并且当它变为0或1时，返回第一和第二个斐波那契数的标准值，如LOC 21～24所示。

3.5　使用递归计算数字的阶乘

问题
你希望使用递归计算数字的阶乘。
解决方案
编写一个C程序，使用具有以下规格说明的递归计算数字的阶乘：
□程序要求用户输入数字N（1≤N≤12）。如果输入0，则程序停止。
□程序定义了函数fact()。程序使用递归计算数字的阶乘。它以递归方式调用函数fact()来进行此计算。
□在屏幕上显示计算结果。
代码
以下是使用这些规格说明编写的C程序的代码。在文本编辑器中键入以下C程序，并将其保存在C:Code文件夹中，文件名为fact2.c：

编译并执行此程序。这个程序的运行结果在这里给出：

工作原理
在LOC 10中，用户输入的数字N被程序接受并赋值给变量intN。在LOC 13中，通过调用函数fact()来计算intN的阶乘。函数fact()在LOC 19～25中定义。在此函数中，在LOC 24中，函数fact()以递归方式调用自身。每次调用时，输入参数的值减1。当输入参数的值为1时，返回值1，如LOC 21～22所示。

3.6　搜索整数数组中的最大元素

问题
你希望使用递归搜索整数数组中的最大元素。
解决方案
编写一个C程序，使用以下规格说明搜索整数数组中的最大元素：
□程序要求用户输入数组N的大小（2≤N≤14）。程序然后要求用户输入N个整数。
□定义名为largest()的函数，该函数递归调用自身并计算整数数组中的最大元素。
□程序在屏幕上显示搜索出的最大元素的值。
代码
以下是使用这些规格说明编写的C程序的代码。在文本编辑器中键入以下C程序并将其保存在文件夹C:Code中，文件名为maxnum.c：

编译并执行此程序。这个程序的运行结果在这里给出：

工作原理
LOC 6～9由一个do-while循环组成，它接受用户输入的数组的长度。LOC 11～12由一个for循环组成，它接受用户输入的数组元素（它们都是整数）。LOC 13显示数组中最大元素的值，并且它还调用函数largest()。LOC 17～30包含函数largest()的定义，它通过递归调用自身来搜索数组的最大元素，然后返回这个最大的元素。LOC 13使用函数largest()返回的值，借助函数printf()将其显示在屏幕上。

3.7　解决经典的汉诺塔问题

你想用递归的方法解决汉诺塔的经典问题。
解决方案
编写一个C程序，按照以下规格说明使用递归方法解决汉诺塔的经典问题：
□程序要求用户输入圆盘数n（1≤n≤10）。
□程序定义了函数move()，它以递归方式调用自身来解决问题。
□程序在屏幕上显示计算结果。
代码
以下是使用这些规格说明编写的C程序的代码。在文本编辑器中键入以下C程序，并将其保存在文件夹C:Code中，文件名为Hnoi.c：

编译并执行此程序。这个程序的运行结果在这里给出：

工作原理
传说汉诺塔位于汉诺城的一座寺庙中，该地位于亚洲。有三个如图3-4所示的立柱，此外，还有64个金盘，所有金盘的半径都不同。每个圆盘在中心都有一个孔，这样圆盘可以堆叠在任何立柱上，从而形成一个塔，就像一堆堆成纺锤形的CD。首先，圆盘按照从上到下逐渐增加的半径的顺序堆叠在左立柱上（参见图3-4，但该图仅显示了四个圆盘）。寺庙中的僧侣试图将所有64个圆盘都移动到右立柱。中间的立柱可用于临时存放。他们的行为受到以下条件的限制：
□应一次移动一个圆盘。
□从立柱上取下的圆盘不能放在地上。它必须放在三个立柱中的一个上面。
□较大的圆盘不能放在较小的圆盘上面。你当然可以将较小的圆盘放在较大的圆盘上面。

人们相信，当完成分配给僧侣的任务时，世界将会终结。计算机科学家对这个问题表现出浓厚的兴趣，因为它显示了递归的效用，而不是因为他们对世界末日的可能性感到担忧。使用递归，可以通过编写一个简单的程序来解决这个问题。虽然你也可以简单地利用迭代而不使用递归来解决这个问题，但程序会变得非常复杂。
出于编程目的，你可以假设左立柱周围堆叠了n个圆盘，其中n是整数变量。圆盘从上到下依次编号，最上面的圆盘编号为1，最下面的圆盘编号为n。让我们开发一个程序，用于将n个圆盘从左立柱移动到右立柱，而不违反前面提到的三个条件中的任何一个。问题可以用递归形式表示如下：
1.使用右立柱来临时存放，将顶部的（n-1）个圆盘从左立柱移动到中间立柱。
2.将第n个圆盘（最大的圆盘，因此也是最下面的圆盘）从左立柱移动到右立柱。
3.使用左立柱来临时存放，将（n-1）个圆盘从中间立柱移动到右立柱。
所有这三个步骤准确无误地出现在LOC 19～25中定义的递归函数move()中。对于每次递归调用，n的值减1，因此递归在有限数量的调用之后停止。此外，n＝0是此程序的停止条件。

3.8　解决八皇后问题

问题
你想利用回溯法来解决八皇后问题。
解决方案
回溯法是一种通用算法，用于查找计算问题的一些或所有可能的解决方案。在回溯中，首先考虑所有可能的候选者（可能成功），然后丢弃无法成功的候选者。最后，只剩下那些成功解决问题的候选人。在国际象棋棋盘上，八个皇后的排列方式使得没有皇后可以攻击另一个皇后。一个成功的解决方案要求没有两个皇后在相同的行、列或对角线上。编写一个C程序，依照以下规格说明使用递归来解决八皇后问题：
□定义名为queen()的函数。两个int值将作为输入参数传递给此函数：棋盘上的行号和棋盘上的皇后数（在本例中为8）。
□函数queen()以递归方式调用函数print()、函数place()以及函数queen()本身。
□函数place()检查将皇后放置在棋盘上方格的可能性。如果一切正常，则返回1，否则，它返回0。
□函数print()在屏幕上显示皇后的成功位置。
以下是使用这些规格说明编写的C程序的代码。在文本编辑器中键入以下C程序，并将其保存在文件夹C:Code中，文件名为queens.c：

编译并执行此程序。请注意，这个问题有92种成功的解决方案。执行开始时，屏幕上会显示解决方案1，如此处所示。按Enter键，然后屏幕上显示解决方案2。如果你对查看所有92种解决方案不感兴趣，只需按住Enter键并保持几秒钟即可。
这个程序的运行结果在这里给出：

工作原理
LOC 5～10定义main()函数。在LOC 7中，int变量p的值设置为8，因为棋盘上的皇后数是8。在LOC 8中，调用函数queen()。queen()的第一个参数是int值1，它表示第1行，queen()的第二个参数是int变量p，p的值设置为int值8（即棋盘上的皇后个数）。LOC 47～61定义了函数queen()。函数queen()调用函数place()来检查放置情况（正在考虑中）对于皇后是否安全。如果一切正常，则place()返回1，一旦找到了皇后的一种成功放置情况，那么函数queen()调用函数print()来在屏幕上显示成功的放置情况，如LOC 56所示。在LOC 58中，函数queen()递归调用自己，进一步调查正在考虑的放置情况。

3.9　计算给定对象集的排列和组合

问题
你想要计算给定对象集的排列和组合。
解决方案
编写一个C程序，用以下规格说明计算给定对象集的排列和组合：
□程序使用图3-5中所示的公式，并计算从n个对象中一次取r个对象的排列和组合。
a）从总共n个对象一次取r个对象的排列的公式
b）从总共n个对象一次取r个对象的组合的公式

□程序在屏幕上显示计算结果，并询问用户是否要继续。
代码
以下是使用这些规格说明编写的C程序的代码。在文本编辑器中键入以下C程序，并将其保存在文件夹C:Code中, 文件名为p&c.c：

编译并执行此程序。这个程序的运行结果在这里给出：

工作原理
此程序包含两个do-while循环。第一个do-while循环跨越LOC 9～13。此循环接受n（对象总数）的整数值，范围为1≤n≤7。第二个do-while循环跨越LOC 15～19。此循环接受r的整数值（一次取出的对象数目），范围为1≤r≤n。函数combination()在LOC 31～36中定义。函数permutation()在LOC 37～42中定义。函数fact()在LOC 43～52中定义。在LOC 20～21中调用函数combination()和permutation()。LOC 22～23在屏幕上显示计算出的组合和排列的值。

3.10　对两个矩阵求和

问题
你想要对两个矩阵求和。
解决方案
图3-6说明了矩阵的加法。编写一个C程序，求两个矩阵A和B的和，使得A＋B＝C（C也是一个矩阵），使用以下规格说明：
□程序要求用户输入矩阵的秩（即矩阵中的行数和列数）。
□程序接受两个矩阵A和B的数据。只要矩阵具有相同的行数和列数，就可以相互相加或相减。
□在程序中，定义三个函数：input()，output()和add()。函数input()接受来自键盘的数据，用于矩阵A和B。函数output()在屏幕上显示矩阵A、B和C。函数add()执行矩阵A和B的求和并填充矩阵C中的值。

代码
以下是使用这些规格说明编写的C程序的代码。在文本编辑器中键入以下C程序，并将其保存在文件夹C:Code中，文件名为summat.c：

编译并执行此程序。这个程序的运行结果在这里给出：

工作原理
此程序包含两个do-while循环。第一个do-while循环接受行数的整数值，范围为1≤M≤12。第二个do-while循环接受列数的整数值，范围为1≤N≤12。LOC 18和23分别调用函数input()并接受矩阵A和B的数据。LOC 21和26分别调用函数output()并在屏幕上显示矩阵A和B。LOC 27调用函数add()，执行矩阵A和B的求和，并填充矩阵C中的值。LOC 30调用函数output()并在屏幕上显示矩阵C。LOC 34～43定义了函数input()。LOC 44～55定义了函数output()。LOC 56～66定义了函数add()。

3.11　计算矩阵的转置

问题
你想要计算矩阵的转置。
解决方案
编写一个C程序，计算矩阵A的转置，使A的转置＝B（B也是矩阵，见图3-7），使用以下规格说明：
□程序要求用户输入矩阵的顺序（即矩阵中的行数和列数）。
□程序接受矩阵A的数据。它计算矩阵A的转置并在屏幕上显示结果矩阵B。
代码
以下是使用这些规格说明编写的C程序的代码。在文本编辑器中键入以下C程序并将其保存在文件夹C:Code中，文件名为transp.c：

编译并执行此程序。这个程序的运行结果在这里给出：

工作原理
此程序包含两个do-while循环。第一个do-while循环接受矩阵A的行数的整数值，范围为0＜R＜13。第二个do-while循环接受矩阵A的列数的整数值，范围为0＜C＜13。LOC 14～19由for循环组成，它接受矩阵A的数据。LOC 21～28由for循环组成，在屏幕上显示矩阵A。LOC 29～35由for循环组成，它计算矩阵A的转置。LOC 37～44由for循环组成，它在屏幕上显示矩阵A的转置。图3-7说明了矩阵转置的概念。

3.12　计算矩阵的乘积

问题
你想要计算矩阵A和B的乘积。
解决方案
编写一个C程序，计算矩阵A和B的乘积，使得A×B＝C（C也是矩阵，见图3-8），使用以下规格说明：
□程序要求用户输入矩阵A的秩和矩阵B中的列数。程序还在屏幕上显示矩阵A和B。
□程序包含三个函数：input()、output()和product()。函数input()接受来自键盘的数据，函数output()在屏幕上显示矩阵，函数product()计算矩阵A和B的乘积并填充矩阵C中的数据值。
□程序计算矩阵A和B的乘积，并在屏幕上显示结果。

代码
以下是使用这些规格说明编写的C程序的代码。在文本编辑器中键入以下C程序，并将其保存在文件夹C:Code中，文件名为promat.c：

编译并执行此程序。这个程序的运行结果在这里给出：

工作原理
此程序包含三个do-while循环。第一个do-while循环接受矩阵A的行数的整数值，范围为1≤M≤8。第二个do-while循环接受矩阵A的列数的整数值，范围为1≤N≤8。第三个do-while循环接受矩阵B的列数的整数值，范围为1≤P≤8。LOC 26和32分别调用函数input()并接受矩阵A和B的数据。LOC 29和35分别调用函数output()并在屏幕上显示矩阵A和B。LOC 37调用函数product()，执行矩阵A和B的乘积，并填充矩阵C中的值。LOC 39调用函数output()并在屏幕上显示矩阵C。LOC 44～53定义了函数input()。LOC 54～65定义了函数output()。LOC 66～80定义了函数product()。