第四章 函数 对付复杂性大程序的一种有效方法是把它局部化、模块化。 函数 函数有两类： 1）系统提供的标准函数库； 2）自定义的函数。 第四章 函数 对付复杂性大程序的一种有效方法是把它局部化、模块化。 函数 C语言中是程序模块；也称为子例程（procedure） 函数有两类： 1）系统提供的标准函数库； 2）自定义的函数。 函数的使用是通过函数调用实现的。

系统提供的函数库 ANSI C 标准函数 专用函数库（厂商提供） 如：printf( )，scanf( )等预先准备好的函数 支持常见的数学运算、字符串处理、输入输出等众多功能（见附录B） 专用函数库（厂商提供） 图象处理、用户界面、数据库访问…(Win32 API) 支持各种专用资源和设备的处理和控制

4.1 标准函数的使用 函数调用方式（函数调用表达式） 先说明、后引用 例如： 函数名（实在表达式1，实在表达式2，) 4.1 标准函数的使用 函数调用方式（函数调用表达式） 函数名（实在表达式1，实在表达式2，) 先说明、后引用 #include 头文件 包含厂商提供的头文件（包含文件） 例如： 标准输入输出：stdio.h 字符串处理：string.h 数学函数：math.h 字符处理：ctype.h

例4-1：数学函数的使用 #include <stdio.h> #include <math.h> /* 数学函数头文件 */ main( ) { double x, y; /* 双精度数 */ scanf( “%lf”, &x ); /* 读入x */ y = sin( x ); /* 求sin(x) */ printf( “sin(%lf) = %lf\n”, x, y ) /* 输出sin(x) */ printf( “cos(%lf) = %lf\n”, x, cos(x) ); /* 输出cos(x) */ }

函数原型的概念 代表函数的类型 例如：标准函数的函数原型说明 函数 sqrt 和 sin 的类型相同 包括函数参数个数、顺序、参数类型、返回值类型 例如：标准函数的函数原型说明 double sqrt( double x )； 求 x 的平方根 double sin( double x )； 求 x 的正弦值 int rand( void )； 求一个随机数 /* void 表示无参数 */ 出现在头文件中 math.h 函数 sqrt 和 sin 的类型相同 函数原型相同；规定了实参的类型

随机数的产生 #include <stdio.h> #include <stdlib.h> 指定头文件（函数原型） #include <stdio.h> #include <stdlib.h> main( ) // 阅读程序 { int i = 1; while( i <= 20 ) { printf( “%10d”, 1 + rand()%6 ); if( 0 == i++%5 ) printf( “\n” ); } 生成一个随机数 rand1.c

程序读解 循环 控制变量 i i=1, i<=20, i++ 循环 20 次 每次输出 1+ rand() % 6 取值为 1-6 的随机数 i%5 时输出\n 每5次循环，输出换行 该程序的功能： 输出 20 个随机数，每 5 个数据在一行

随机数的产生 C语言的标准库提供了函数rand()和srand()。可实现如模拟和游戏等方面的应用。 函数rand和srand的函数原型在stdlib.h中 函数rand( )产生一个在0到RAND_MAX之间的整数值（随机数）。 RAND_MAX是符号常量，其值为32767。 调用形式：n = rand（）；

可缩放和移动函数rand所产生的值，确定指定范围。 一般方法：n=a + rand( ) % b; 其中：a为移动值，等于所需的连续整数值范围内的第一个数； b是比例因子，等于所需的连续整数值范围的宽度。

4.2 自定义函数 目的 结构化程序设计的观点 支持代码复用（reuse、重用） 支持软件模块化：C语言的程序结构 = 若干个函数 4.2 自定义函数 目的 支持代码复用（reuse、重用） 支持软件模块化：C语言的程序结构 = 若干个函数 支持结构化程序设计 结构化程序设计的观点 自顶向下、逐步求精、信息隐蔽 算法设计首先考虑整体功能，逐步细化，考虑子功能的实现； 函数（子例程）是实现子功能的主要手段

函数的编制 基本结构 程序例：计算两个整数中的最大值 返回值类型 函数名（类型 参数名，类型 参数名…） { /* 形式参数 */ 返回值类型 函数名（类型 参数名，类型 参数名…） { /* 形式参数 */ 变量说明（局部变量） 语句组 } 程序例：计算两个整数中的最大值 int max( int a, int b ) { if( a > b ) return a; /* 返回a */ else return b; 函数的编制

函数的调用 main( ) { int x, y； scanf( “%d%d”, &x, &y ); printf( “max = %d\n”, max(x, y) ); } 基本要求 实参和形参个数相等，按顺序匹配，类型相符 返回值作为函数调用表达式的值参加计算，类型应符合计算要求 实在参数

函数调用过程 计算参数表达式（实参） 将求值结果传递给函数的参数（形参） 开始执行函数中的语句 执行到最后一条语句，或return语句 如：对于 cos( x+20, x++ )，先求x+20和x++ 将求值结果传递给函数的参数（形参） 虚实结合、按值调用 开始执行函数中的语句 执行到最后一条语句，或return语句 得到返回的结果，返回 继续参加调用方的计算 非确定性 多个参数的求值顺序不定（取决于各自的编译）

没有返回值的函数 负责完成某个处理过程 程序例 void read( int n, double x[ ] ) { 不要求将计算结果返回给调用者 或仅通过参数返回数据 程序例 void read( int n, double x[ ] ) { int i; for( i=0; i<n; i++ ) /* 循环n次 */ scanf( “%lf”, x[ i ] ); /* 读入双精度数 */ } 数组可用于返回数据 表示无返回值

例4-2： 程序读解 #include <stdio.h> int gcd( int m, int n ); int main( ) { int a1, a2, b1, b2, x1, x2; char c; scanf(“%d/%d%c%d/%d”, &a1,&a2,&c,&b1,&b2 ); if( ‘+’ == c ) { x2 = a2 * b2; x1 = a1 * b2 + a2 * b1; } else if( ‘*’ == c ) { x1 = a1 * b1; } else return 0; printf(“result=%d/%d\n”, x1/gcd(x1,x2), x2/gcd(x1,x2));

程序分析 1. 函数原型出现在引用之前 int gcd( int m, int n )； 2. 数据输入格式 %d/%d%c%d/%d 必须和输入数据匹配 合法例：12/35+9/41 3/7*1/2 3. 计算例 1. x2=35*41 x1=12*41+9*35 2. x2=7*2 x1=3*1 4. 输出 (为分数形式：%d/%d) result = x1/gcd(x1,x2) / x2/gcd(x1,x2)

函数定义 int gcd( int m, int n ) { int r, t; if( m < n ) { // 数据交换 t = m; m = n; n = t; } while( 0 != (r = m%n) ) { m = n; // 余数不等于0 时 n = x; return n; // 求最大公约数 fenshu.c

例4-3：在多行数据中求最长行 任务： 基本思路 数据对象考虑 从键盘输入若干行数据，输出最长的一行； 空行表示输入结束 逐行输入；经过比较保存最长行；直至结束。 数据对象考虑 最长行数据 maxline[ MAX ] 当前行数据 buf[ MAX ]

算法描述 初始化 读1行数据 buf 将buf复制到 maxline N N buf长度> 长度=0 maxline长度 Y Y

算法细节 模块功能： 读一行数据，得到长度len len  0 ch  读字符 若ch等于换行符 则返回 len 将ch添加到buf, ch=‘\n’ 返回 len buf ← ch len增1 模块功能： 读一行数据，得到长度len len  0 ch  读字符 若ch等于换行符 则返回 len 将ch添加到buf, len加一 重复2-4 可单独设计一个函数 合一

程序实现 用全局变量保存最长行、当前行 设置函数：负责行的读入 利用字符串处理函数 设置局部变量保存行的长度 char maxline[ 80 ]; char buf[ 80 ]; 设置函数：负责行的读入 int getline( void ) 返回长度 利用字符串处理函数 实现行的复制strcpy、输出printf 字符串:是以空字符‘\0’ 结尾的字符数组 设置局部变量保存行的长度 int len, max

全局变量与函数getline #include <stdio.h> #include <string.h> /* 字符串函数说明 */ #define MAX 80 char maxline[ MAX ], buf[ MAX ]; /* 全局变量 */ int getline( void ) { int c, len = 0; /* 当前字符，计数器 */ while( (c = getchar( )) != ‘\n’ && len < MAX-1 ) /* 不超过数组上界 */ buf[ len++ ] = c; /* 填充字符 */ buf[ len ] = ‘\0’; /* 字符串结尾 */ return len; /* 返回字符个数 */ } 全局变量与函数getline

实现技巧 利用 getchar( ) 宏定义 利用混合运算（字符和整数） 逻辑运算 字符串的实现 C 语言的逻辑值 函数返回值 从标准输入stdin 读一个字符 返回字符的ASCII值（整型） 利用混合运算（字符和整数） 比较 c==‘\n’ 赋值 buf[ i ] = c 字符串的实现 字符数组中设置结束符‘\0’ 函数返回值 return i; 宏定义 #define MAX 80 便于维护 逻辑运算 && || ！ 与 或 非 C 语言的逻辑值 0 表示假 非 0 整数表示真

主程序 main( ) { int len, max = 0; /* 当前行和最长行长度 */ while( (len = getline( )) > 0 ) { /* 读入一行 */ if( len > max ) { /* 比较行长度 */ max = len; strcpy( maxline, buf ); /* 保存新的行 */ } if( max > 0 ) /* 如果存在最长行 */ printf( “%s\n”, maxline ); /* 输出最长行 */

程序设计方法分析 结构化程序设计 局部化（信息隐蔽） 利用存在的资源：标准函数库 字符串存储 算法设计：自顶向下、逐步求精 将功能相对独立的部分，采用函数来实现 局部化（信息隐蔽） main 实现主算法； getline 实现行的读取 尽可能不使用全局变量 利用存在的资源：标准函数库 字符串复制 strcpy 字符串输出转换符 %s 字符串存储 所需单元要比实际字符数多一个单元

4.3 函数与数组 数组作为函数参数 改写后的 getline 不必填写数组大小 数组名表示内存空间的首地址 参数传递实质上是地址的赋值 4.3 函数与数组 数组作为函数参数 数组名表示内存空间的首地址 参数传递实质上是地址的赋值 改写后的 getline int getline( char buf[ ] ) { int c, i = 0; while( (c=getchar()) != ‘\n’ && i<MAX-1 ) buf[ i++ ] = c; buf[ i ] = ‘\0’; return i; } /* 数组常用于返回数据 */ 不必填写数组大小

改写后的主程序 全局变量改为局部变量 main( ) { int len, max = 0; /* 当前行和最长行长度 */ char line[80], maxline[80]; while( (len = getline( line )) > 0 ) { /* 读入一行 */ if( len > max ) { /* 比较行长度 */ max = len; strcpy( maxline, line ); /* 保存新的行 */ } if( max > 0 ) /* 如果存在最长行 */ printf( “%s\n”, maxline ); /* 输出最长行 */

信息隐蔽的实现 局部化 特殊情况 每个函数的输入：来自参数、或IO函数 每个函数的输出：返回值、参数、或IO函数 程序设计可以在本函数中，找到需要的所有数据（尽可能做到） 特殊情况 数据量很大的情况：如大数组 众多函数共享的数据

数组使用小结 数组说明与初始化 数组的使用 字符串与数组 int digits[ 10 ] = { 1, 2, 3, 4 } 前四个元素被赋值 数组的使用 数组元素 digits[ 4 ] 函数参数 digits 代表内存地址（可存返回值） 字符串与数组 字符串常数 “Welcome to C\n” 是以 \0 结尾的字符数组（没有名字，其大小等于字符个数加1） 可以参加运算，如作为函数参数、数组初始化

4.4 函数的递归调用 函数的嵌套调用 函数的递归调用 应用需求 如：main( )  getline( )  getchar( ) 4.4 函数的递归调用 函数的嵌套调用 如：main( )  getline( )  getchar( ) 函数的递归调用 调用本身（直接或间接） 应用需求 如：欧几里德算法（采用递归定义） 可以采用循环结构实现，但影响可读性

函数的递归调用 一个函数直接或通过另一个函数间接调用自身的函数，称递归函数。构成了函数的递归调用。 两个互相调用的函数定义： 直接调用自身： int h(int x) {.... .... .. h(...) .. .... .... } 两个互相调用的函数定义： int h(int x) { int g(int y) { .... .... .. g(...) .. .. h(...) .. } }

任务一 计算 n! 的递归函数 问题分析 n! = n * (n - 1)! 注意：递归调用必须在一定条件下结束。

可确定阶乘函数的类型特征为： int fact( int ) 更合适的选择为： long fact( int ) 函数定义： long fact (int n) { if(n == 0) return 1; else return(n * fact (n -1)); }

计算中fact被递归调用的次数由实际参数确定。 #include <stdio.h> long fact (int); main(){ int i; for( i=1; i <= 10; i ++) printf("\n%2d!=%ld", i, fact( i ) ); } long fact(int number) { if (number ==0) return 1; else return(number * fact(number -1)); 递归的终止条件 递归调用

fact 递归函数的计算过程： 调用fact (5) fact (5) 5 * fact (4) 返回值 120 返回值 2 返回值 6 返回值 24 返回值 120

例4-3：Fibonacci数列的计算 n if n < 2 Fib( n ) = Fib( n-1 ) + Fib( n-2 ) 程序实现： unsigned long Fib( unsigned long n ) { unsigned long m; if( n < 2 ) return n; m = Fib( n-1 ); return m + Fib( n-2 ); } 无符号长整型

函数调用过程 Fib( 2 ) Fib( 3 ) Fib( 1 ) Fib( 0 ) Fib( 1 )

程序分析 局部变量和形式参数 函数调用返回 unsigned long 每层函数调用中代表不同的数据 同名变量使用不同的内存空间 局部变量和形参失效 返回值参与调用方的计算 unsigned long 代表无符号长整型 32bit

定义辅助函数，是实现复杂程序功能的常用手段。 如：欧几里德算法（采用递归定义） 可以采用循环结构实现，但影响可读性 算法（欧几里德算法） n 如果 m 整除 n gcd( m, n ) = gcd( n, mod(m,n) ) 否则 条件 m > n mod(m, n) 表示除法余数

定义辅助函数 long gcd(long m, long n){ if(m < 0) m = -m; if(n < 0) n = -n; if(n == 0 ) return m; else return gcd1(m, n); } long gcd1(long m, long n) { if(m % n == 0) return n; else return gcd1(n, m%n); 对负参数值的处理

/* 求两个整数的最大公约数的递归函数 */ #include<stdio.h> long gcd(long, long); long gcd1(long, long); main( ) { long integer1,integer2; printf("\n\n Enter two long integers "); scanf("%ld%ld",&integer1,&integer2); printf("\n gcd(%ld,%ld)= %ld", integer1, integer2, gcd(integer1, integer2)); return 0; }

递归定义的实质 任何有意义的递归定义总是由两部分组成： 1）递归方式 2）递归终止条件

递归与迭代的比较 计算大于或等于0的整数n的阶乘。 递归方法 迭代方法 long fact (int n) { if (n == 0) return 1; else return(n * fact (n -1)); } 递归方法 迭代方法 long fact (int n) { int fac = 1, count； for（count = n； count >= 1； count--） fac = fac * count； }

递归与迭代的比较 迭代过程 递归定义 递归算法比较自然，简洁，容易理解。 循环处理过程：用while等循环语句实现 也可以用递归定义的函数实现 递归定义 算法过程的递归调用；用递归定义的函数实现（使用选择结构） 也可以用循环语句实现 递归算法比较自然，简洁，容易理解。

递归与迭代的比较 性能比较 可读性 推荐 循环语句优于函数的递归调用 函数的递归定义优于循环结构 采用递归函数处理复杂算法 采用循环语句满足高性能要求 递归与迭代的比较

常见的程序设计错误: 在需要返回值时忘记从递归函数返回; 遗漏了基本实例或编写了不正确的递归函数，而导致无法递归，最终耗尽内存。 输入不正确的数据也可能导致无限递归。

4.5 作用域和存储类别 C语言源程序的多文件处理过程 src1.c 编译 src2.c src3.c 目标程序 src1.obj src2.obj src3.obj 连接 库程序 cc.lib等 可执行程序 src1.exe 每个源程序文件中可包含若干个函数和全局变量说明

作用域：标识符的有效范围 全局标识符号（函数名、外部变量名） 外部说明 函数参数(形式参数) 局部变量 同名标识符 定义在函数外部，在整个程序范围有效； 外部说明 在使用其他文件定义的标识符时,应说明； extern int x; 或 用函数原型说明 函数参数(形式参数) 在函数定义体内部有效 局部变量 在复合语句内部有效（花括弧之间） 同名标识符 不同的作用域可以使用同名的标识符

i为全局变量，隐含初值为0 i未赋初值，其值不可预料 (2) (1) #include<stdio.h> main() { void inc(); inc(); } void inc() { int i; i++; printf(“%d”, i); #include<stdio.h> main() { void inc(); inc(); } int i; void inc() { i++; printf(“%d”, i); i为全局变量，隐含初值为0 i未赋初值，其值不可预料

不同函数间数据传递方式 （1）通过函数参数传递 （2）通过return语句返回值 （3）全局变量

例：企图输出用“#”组成的66的方阵。 #include<stdio.h> int i; main() { void prt(); for(i = 0; i <= 5; ++i) prt(); } void prt() { for(i = 0; i <= 5; ++i) printf(“# ”); printf(“\n”); } 运行结果： # # # # # #

使用全局变量应该注意的地方 不论是否需要，全局变量在整个程序运行期间都占用内存空间； 全局变量必须在函数以外定义，影响了函数的独立性； 使用全局变量，容易因疏忽或使用不当而导致全局变量的值被意外地更改，从而引起副作用，最终产生难以查找的错误。

变量的存储类别 存储类别规定了所说明对象在内存中的存储方式（位置），从而确定所说明对象的作用域和生存期。 生存期：在内存中占据一定空间的时间

用户执行程序所占用的内存空间（称用户区），分三个区 函数返回地址、自动类别的局部变量 动态存储区 全局变量和静态类别的局部变量。 静态存储区 程序代码区 用户执行程序所占用的内存空间（称用户区），分三个区

4种存储类别的说明符 auto 局部变量和函数参数的缺省类别 函数执行后，自动释放所用空间 register 利用寄存器保存的变量（高性能） extern 说明外部变量（在其他文件中说明） static 说明变量的内存空间在程序执行全过程有效，开始执行时一次性被分配和初始化

静态变量的使用 任务 int getNum( ) { static int x = 0; /* 仅初始化一次 */ return ++x; } 首次 getNum( ) 返回 1 再次 getNum( ) 返回 2 

函数的副作用 其作用不仅反映在返回值，而且和使用过程有关 使用外部输入输出的函数，其功能和环境有关 过程型语言的特征 （包括；C/C++/Java等主流语言） 也是程序中函数与数学函数的主要区别 程序设计必须利用副作用来完成计算任务

C语言小结 if语句 和 while语句 函数 数据对象 运算 这些功能已经足以支撑任何算法的实现 支持各种控制结构的实现 支持程序模块的实现，子任务的完成 标准函数库：scanf, printf… 数据对象 基本数据类型：整数、浮点数、双精度数、字符 一维数组 运算 算术、关系、逻辑 这些功能已经足以支撑任何算法的实现

4.6 函数实例研究 实例1： 实例2： 函数设置（功能独立、上下文无关） 排序算法 将一维数组中的元素排序 查找算法 在一维数组中查找指定元素 函数设置（功能独立、上下文无关） 设置 void Sort( int n, int a[ ] )，结果在数组中 设置 int Search( int key，int n, int a[ ] )，返回元素下标 其中，n是元素个数，a是数组

例4-4：冒泡排序的实现 算法思想： 数据对象 针对一组 n个数据 a1、a2、…、an 逐个比较相邻的数据，如果后面的数据小于前面的数据，则进行交换 进行 n-1 次比较后，从头开始第 2 遍扫描 进行 n-1 遍处理后，数组形成升序排列 数据对象 数组 a 元素个数 n 计数器 i

排序过程 49 38 65 97 76 13 27 初始 38 49 65 76 13 27 97 第一趟后 38 49 65 13 27 79 97 第二趟后 38 49 13 27 65 79 97 第三趟后 38 13 27 49 65 79 97 第四趟后 13 27 38 49 65 79 97 第五趟后 13 27 38 49 65 79 97 第六趟后

算法设计 Sort( n, a ) 1. 重复以下处理 n-1 次 输入： a 数组，n 元素个数 输出： a 数组 1.1 1  i 1.2 若 i = n，则退出 1.3 若 ai > ai+1，则交换 ai 和 ai+1 1.4 i+1  i 1.5 重复 1.2 - 1.3 的处理 若i从0开始，只要到n-1则退出

实现方法 循环的实现 数组下标范围 交换的实现 基于计数器 采用 for 语句 双重循环：各自的计数器 0 - n-1 ai 的实现 a[ i-1 ] 交换的实现 缓冲区变量 int tmp

程序实现 数组数据交换 void Sort( int n, int a[ ] ) { int i, j, tmp; for( j=0; j<n-1; j++ ) for( i=0; i<n-1; i++ ) if( a[ i ] > a[ i+1 ] ) { tmp = a[ i ]; a[ i ] = a[ i+1 ]; a[ i+1 ] = tmp; } 数组数据交换

测试例 数组元素的输入 数组元素的输出 main( ) { int i, x[ 20 ]; for( i=0; i<20; i++ ) scanf( “%d”, &x[ i ] ); sort( 20, x ); printf( “%d”, x[ i ] ); } 数组元素的输出

例4-6 二分查找的实现 任务 算法思想 在一组数据中查找指定的数据 将数据按照升序排序成数组 以整个数组为查找范围 例4-6 二分查找的实现 任务 在一组数据中查找指定的数据 算法思想 将数据按照升序排序成数组 以整个数组为查找范围 用给定值Key与中间位置元素的值比较 若相等，则查找成功; 若 Key值小，继续对左半部分进行查找（重复3-6）； 若 Key值大，继续对右半部分进行查找（重复3-6）。 如此重复，直到查找成功 或查找范围缩小为空，即查找失败为止。

算法设计(1/2) 数据对象设计 函数设计 保存所有数据的数组 a、元素个数 n 给定值 key 查找范围：下界 low, 上界 high 中间元素的下标 mid 函数设计 int Search( int key, int n, int a[ ] ); /* 在数组a中查找元素key, 返回下标或-1 */

算法设计(2/2) 排序 a 0low n-1high (low+high)/2 mid F T key>a[mid] F mid-1high mid+1low T T F high≥low 返回-1 返回mid

程序实现 int Search( int key, int n, int a[ ] ) { int low, mid, high; Sort( n, a ); /* 排序 */ low = 0; high = n-1; do { mid = (low + high) / 2; if( key == a[mid] ) return mid; if( key > a[mid] ) low = mid + 1; /* 改变下限 */ else high = mid – 1; /* 改变上限 */ } while ( low <= high ); return -1; /* 未找到 */ }

在 26,14,54,83,20,8中查找26的过程 排序后，得到 8, 14, 20, 26, 54, 83 low high mid key a[mid] 1 5 2 26 20 3 4 54

算法设计(1/2) 方法二 递归实现 int Search(int Key, int n, int a[]) { } Sort(n,a); 方法二 递归实现 int Search(int Key, int n, int a[]) { Sort(n,a); return Search0(Key,a,0,n-1); }

算法设计(2/2) { } int Search0(int Key, int x[ ], int low, int high) int mid; if(low>high) return -1; mid = (low+high) / 2; if (Key == x[mid]) return mid; if (Key > x[mid]) return Search0(Key, a, mid+1, high); else return Search0(Key, a, low, mid-1); }

函数设计小结 功能设计 局部化 常用限制 功能相对独立，规模适当 支持功能抽象，简化算法描述 对于复杂的算法，进一步采用功能抽象 尽可能不使用外部变量 用局部变量和形参描述所有数据对象 常用限制 复合语句层次不超过 3 层 函数代码长度小于30-40 行

TURBO C 对多文件处理的支持 建立工程文件 指定工程文件 编译和运行 如 Test.PRJ, 内容如下： src1.c src2.c ALT + P 后，选择 Project Name，输入工程文件名 编译和运行 ALT + C 后，选择 Make 或 Build All 或者，直接用 Ctrl + F9 系统将生成执行文件 Test.EXE 每个文件中包含几个函数定义

第四章 作业 阅读第五章 程序设计练习 上机作业 自我测验5.2 5.4 5.6 5.7 第四章 作业 阅读第五章 自我测验5.2 5.4 5.6 5.7 程序设计练习 5.9 5.16 5.27 5.39 5.46 5.47 上机作业 实验3.1 实验3.2 实验3.3