Download presentation
Presentation is loading. Please wait.
Published byΠαρασκευή Μπλέτσας Modified 5年之前
1
第四章 函数 对付复杂性大程序的一种有效方法是把它局部化、模块化。 函数 函数有两类: 1)系统提供的标准函数库; 2)自定义的函数。
第四章 函数 对付复杂性大程序的一种有效方法是把它局部化、模块化。 函数 C语言中是程序模块;也称为子例程(procedure) 函数有两类: 1)系统提供的标准函数库; 2)自定义的函数。 函数的使用是通过函数调用实现的。
2
系统提供的函数库 ANSI C 标准函数 专用函数库(厂商提供) 如:printf( ),scanf( )等预先准备好的函数
支持常见的数学运算、字符串处理、输入输出等众多功能(见附录B) 专用函数库(厂商提供) 图象处理、用户界面、数据库访问…(Win32 API) 支持各种专用资源和设备的处理和控制
3
4.1 标准函数的使用 函数调用方式(函数调用表达式) 先说明、后引用 例如: 函数名(实在表达式1,实在表达式2,)
4.1 标准函数的使用 函数调用方式(函数调用表达式) 函数名(实在表达式1,实在表达式2,) 先说明、后引用 #include 头文件 包含厂商提供的头文件(包含文件) 例如: 标准输入输出:stdio.h 字符串处理:string.h 数学函数:math.h 字符处理:ctype.h
4
例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) */ }
5
函数原型的概念 代表函数的类型 例如:标准函数的函数原型说明 函数 sqrt 和 sin 的类型相同
包括函数参数个数、顺序、参数类型、返回值类型 例如:标准函数的函数原型说明 double sqrt( double x ); 求 x 的平方根 double sin( double x ); 求 x 的正弦值 int rand( void ); 求一个随机数 /* void 表示无参数 */ 出现在头文件中 math.h 函数 sqrt 和 sin 的类型相同 函数原型相同;规定了实参的类型
6
随机数的产生 #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
7
程序读解 循环 控制变量 i i=1, i<=20, i++ 循环 20 次 每次输出 1+ rand() % 6
取值为 1-6 的随机数 i%5 时输出\n 每5次循环,输出换行 该程序的功能: 输出 20 个随机数,每 5 个数据在一行
8
随机数的产生 C语言的标准库提供了函数rand()和srand()。可实现如模拟和游戏等方面的应用。
函数rand和srand的函数原型在stdlib.h中 函数rand( )产生一个在0到RAND_MAX之间的整数值(随机数)。 RAND_MAX是符号常量,其值为32767。 调用形式:n = rand();
9
可缩放和移动函数rand所产生的值,确定指定范围。
一般方法:n=a + rand( ) % b; 其中:a为移动值,等于所需的连续整数值范围内的第一个数; b是比例因子,等于所需的连续整数值范围的宽度。
10
4.2 自定义函数 目的 结构化程序设计的观点 支持代码复用(reuse、重用) 支持软件模块化:C语言的程序结构 = 若干个函数
4.2 自定义函数 目的 支持代码复用(reuse、重用) 支持软件模块化:C语言的程序结构 = 若干个函数 支持结构化程序设计 结构化程序设计的观点 自顶向下、逐步求精、信息隐蔽 算法设计首先考虑整体功能,逐步细化,考虑子功能的实现; 函数(子例程)是实现子功能的主要手段
11
函数的编制 基本结构 程序例:计算两个整数中的最大值 返回值类型 函数名(类型 参数名,类型 参数名…) { /* 形式参数 */
返回值类型 函数名(类型 参数名,类型 参数名…) { /* 形式参数 */ 变量说明(局部变量) 语句组 } 程序例:计算两个整数中的最大值 int max( int a, int b ) { if( a > b ) return a; /* 返回a */ else return b; 函数的编制
12
函数的调用 main( ) { int x, y; scanf( “%d%d”, &x, &y );
printf( “max = %d\n”, max(x, y) ); } 基本要求 实参和形参个数相等,按顺序匹配,类型相符 返回值作为函数调用表达式的值参加计算,类型应符合计算要求 实在参数
13
函数调用过程 计算参数表达式(实参) 将求值结果传递给函数的参数(形参) 开始执行函数中的语句 执行到最后一条语句,或return语句
如:对于 cos( x+20, x++ ),先求x+20和x++ 将求值结果传递给函数的参数(形参) 虚实结合、按值调用 开始执行函数中的语句 执行到最后一条语句,或return语句 得到返回的结果,返回 继续参加调用方的计算 非确定性 多个参数的求值顺序不定(取决于各自的编译)
14
没有返回值的函数 负责完成某个处理过程 程序例 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 ] ); /* 读入双精度数 */ } 数组可用于返回数据 表示无返回值
15
例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));
16
程序分析 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)
17
函数定义 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
18
例4-3:在多行数据中求最长行 任务: 基本思路 数据对象考虑 从键盘输入若干行数据,输出最长的一行; 空行表示输入结束
逐行输入;经过比较保存最长行;直至结束。 数据对象考虑 最长行数据 maxline[ MAX ] 当前行数据 buf[ MAX ]
19
算法描述 初始化 读1行数据 buf 将buf复制到 maxline N N buf长度> 长度=0 maxline长度 Y Y
20
算法细节 模块功能: 读一行数据,得到长度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 可单独设计一个函数 合一
21
程序实现 用全局变量保存最长行、当前行 设置函数:负责行的读入 利用字符串处理函数 设置局部变量保存行的长度
char maxline[ 80 ]; char buf[ 80 ]; 设置函数:负责行的读入 int getline( void ) 返回长度 利用字符串处理函数 实现行的复制strcpy、输出printf 字符串:是以空字符‘\0’ 结尾的字符数组 设置局部变量保存行的长度 int len, max
22
全局变量与函数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
23
实现技巧 利用 getchar( ) 宏定义 利用混合运算(字符和整数) 逻辑运算 字符串的实现 C 语言的逻辑值 函数返回值
从标准输入stdin 读一个字符 返回字符的ASCII值(整型) 利用混合运算(字符和整数) 比较 c==‘\n’ 赋值 buf[ i ] = c 字符串的实现 字符数组中设置结束符‘\0’ 函数返回值 return i; 宏定义 #define MAX 80 便于维护 逻辑运算 && || ! 与 或 非 C 语言的逻辑值 0 表示假 非 0 整数表示真
24
主程序 main( ) { int len, max = 0; /* 当前行和最长行长度 */
while( (len = getline( )) > 0 ) { /* 读入一行 */ if( len > max ) { /* 比较行长度 */ max = len; strcpy( maxline, buf ); /* 保存新的行 */ } if( max > 0 ) /* 如果存在最长行 */ printf( “%s\n”, maxline ); /* 输出最长行 */
25
程序设计方法分析 结构化程序设计 局部化(信息隐蔽) 利用存在的资源:标准函数库 字符串存储 算法设计:自顶向下、逐步求精
将功能相对独立的部分,采用函数来实现 局部化(信息隐蔽) main 实现主算法; getline 实现行的读取 尽可能不使用全局变量 利用存在的资源:标准函数库 字符串复制 strcpy 字符串输出转换符 %s 字符串存储 所需单元要比实际字符数多一个单元
26
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; } /* 数组常用于返回数据 */ 不必填写数组大小
27
改写后的主程序 全局变量改为局部变量 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 ); /* 输出最长行 */
28
信息隐蔽的实现 局部化 特殊情况 每个函数的输入:来自参数、或IO函数 每个函数的输出:返回值、参数、或IO函数
程序设计可以在本函数中,找到需要的所有数据(尽可能做到) 特殊情况 数据量很大的情况:如大数组 众多函数共享的数据
29
数组使用小结 数组说明与初始化 数组的使用 字符串与数组 int digits[ 10 ] = { 1, 2, 3, 4 }
前四个元素被赋值 数组的使用 数组元素 digits[ 4 ] 函数参数 digits 代表内存地址(可存返回值) 字符串与数组 字符串常数 “Welcome to C\n” 是以 \0 结尾的字符数组(没有名字,其大小等于字符个数加1) 可以参加运算,如作为函数参数、数组初始化
30
4.4 函数的递归调用 函数的嵌套调用 函数的递归调用 应用需求 如:main( ) getline( ) getchar( )
4.4 函数的递归调用 函数的嵌套调用 如:main( ) getline( ) getchar( ) 函数的递归调用 调用本身(直接或间接) 应用需求 如:欧几里德算法(采用递归定义) 可以采用循环结构实现,但影响可读性
31
函数的递归调用 一个函数直接或通过另一个函数间接调用自身的函数,称递归函数。构成了函数的递归调用。 两个互相调用的函数定义: 直接调用自身:
int h(int x) {.... .... .. h(...) .. } 两个互相调用的函数定义: int h(int x) { int g(int y) { .. g(...) h(...) .. } }
32
任务一 计算 n! 的递归函数 问题分析 n! = n * (n - 1)! 注意:递归调用必须在一定条件下结束。
33
可确定阶乘函数的类型特征为: int fact( int ) 更合适的选择为: long fact( int ) 函数定义:
long fact (int n) { if(n == 0) return 1; else return(n * fact (n -1)); }
34
计算中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)); 递归的终止条件 递归调用
35
fact 递归函数的计算过程: 调用fact (5) fact (5) 5 * fact (4) 返回值 120
返回值 2 返回值 6 返回值 24 返回值 120
36
例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 ); } 无符号长整型
37
函数调用过程 Fib( 2 ) Fib( 3 ) Fib( 1 ) Fib( 0 ) Fib( 1 )
38
程序分析 局部变量和形式参数 函数调用返回 unsigned long 每层函数调用中代表不同的数据 同名变量使用不同的内存空间
局部变量和形参失效 返回值参与调用方的计算 unsigned long 代表无符号长整型 32bit
39
定义辅助函数,是实现复杂程序功能的常用手段。
如:欧几里德算法(采用递归定义) 可以采用循环结构实现,但影响可读性 算法(欧几里德算法) n 如果 m 整除 n gcd( m, n ) = gcd( n, mod(m,n) ) 否则 条件 m > n mod(m, n) 表示除法余数
40
定义辅助函数 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); 对负参数值的处理
41
/* 求两个整数的最大公约数的递归函数 */
#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; }
42
递归定义的实质 任何有意义的递归定义总是由两部分组成: 1)递归方式 2)递归终止条件
43
递归与迭代的比较 计算大于或等于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; }
44
递归与迭代的比较 迭代过程 递归定义 递归算法比较自然,简洁,容易理解。 循环处理过程:用while等循环语句实现
也可以用递归定义的函数实现 递归定义 算法过程的递归调用;用递归定义的函数实现(使用选择结构) 也可以用循环语句实现 递归算法比较自然,简洁,容易理解。
45
递归与迭代的比较 性能比较 可读性 推荐 循环语句优于函数的递归调用 函数的递归定义优于循环结构 采用递归函数处理复杂算法
采用循环语句满足高性能要求 递归与迭代的比较
46
常见的程序设计错误: 在需要返回值时忘记从递归函数返回; 遗漏了基本实例或编写了不正确的递归函数,而导致无法递归,最终耗尽内存。 输入不正确的数据也可能导致无限递归。
47
4.5 作用域和存储类别 C语言源程序的多文件处理过程
src1.c 编译 src2.c src3.c 目标程序 src1.obj src2.obj src3.obj 连接 库程序 cc.lib等 可执行程序 src1.exe 每个源程序文件中可包含若干个函数和全局变量说明
48
作用域:标识符的有效范围 全局标识符号(函数名、外部变量名) 外部说明 函数参数(形式参数) 局部变量 同名标识符
定义在函数外部,在整个程序范围有效; 外部说明 在使用其他文件定义的标识符时,应说明; extern int x; 或 用函数原型说明 函数参数(形式参数) 在函数定义体内部有效 局部变量 在复合语句内部有效(花括弧之间) 同名标识符 不同的作用域可以使用同名的标识符
49
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未赋初值,其值不可预料
50
不同函数间数据传递方式 (1)通过函数参数传递 (2)通过return语句返回值 (3)全局变量
51
例:企图输出用“#”组成的66的方阵。 #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”); } 运行结果: # # # # # #
52
使用全局变量应该注意的地方 不论是否需要,全局变量在整个程序运行期间都占用内存空间; 全局变量必须在函数以外定义,影响了函数的独立性;
使用全局变量,容易因疏忽或使用不当而导致全局变量的值被意外地更改,从而引起副作用,最终产生难以查找的错误。
53
变量的存储类别 存储类别规定了所说明对象在内存中的存储方式(位置),从而确定所说明对象的作用域和生存期。 生存期:在内存中占据一定空间的时间
54
用户执行程序所占用的内存空间(称用户区),分三个区
函数返回地址、自动类别的局部变量 动态存储区 全局变量和静态类别的局部变量。 静态存储区 程序代码区 用户执行程序所占用的内存空间(称用户区),分三个区
55
4种存储类别的说明符 auto 局部变量和函数参数的缺省类别 函数执行后,自动释放所用空间 register 利用寄存器保存的变量(高性能)
extern 说明外部变量(在其他文件中说明) static 说明变量的内存空间在程序执行全过程有效,开始执行时一次性被分配和初始化
56
静态变量的使用 任务 int getNum( ) { static int x = 0; /* 仅初始化一次 */ return ++x;
} 首次 getNum( ) 返回 1 再次 getNum( ) 返回 2
57
函数的副作用 其作用不仅反映在返回值,而且和使用过程有关 使用外部输入输出的函数,其功能和环境有关 过程型语言的特征
(包括;C/C++/Java等主流语言) 也是程序中函数与数学函数的主要区别 程序设计必须利用副作用来完成计算任务
58
C语言小结 if语句 和 while语句 函数 数据对象 运算 这些功能已经足以支撑任何算法的实现 支持各种控制结构的实现
支持程序模块的实现,子任务的完成 标准函数库:scanf, printf… 数据对象 基本数据类型:整数、浮点数、双精度数、字符 一维数组 运算 算术、关系、逻辑 这些功能已经足以支撑任何算法的实现
59
4.6 函数实例研究 实例1: 实例2: 函数设置(功能独立、上下文无关) 排序算法 将一维数组中的元素排序 查找算法
在一维数组中查找指定元素 函数设置(功能独立、上下文无关) 设置 void Sort( int n, int a[ ] ),结果在数组中 设置 int Search( int key,int n, int a[ ] ),返回元素下标 其中,n是元素个数,a是数组
60
例4-4:冒泡排序的实现 算法思想: 数据对象 针对一组 n个数据 a1、a2、…、an
逐个比较相邻的数据,如果后面的数据小于前面的数据,则进行交换 进行 n-1 次比较后,从头开始第 2 遍扫描 进行 n-1 遍处理后,数组形成升序排列 数据对象 数组 a 元素个数 n 计数器 i
61
排序过程 初始 第一趟后 第二趟后 第三趟后 第四趟后 第五趟后 第六趟后
62
算法设计 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 重复 的处理 若i从0开始,只要到n-1则退出
63
实现方法 循环的实现 数组下标范围 交换的实现 基于计数器 采用 for 语句 双重循环:各自的计数器
0 - n-1 ai 的实现 a[ i-1 ] 交换的实现 缓冲区变量 int tmp
64
程序实现 数组数据交换 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; } 数组数据交换
65
测试例 数组元素的输入 数组元素的输出 main( ) { int i, x[ 20 ]; for( i=0; i<20; i++ )
scanf( “%d”, &x[ i ] ); sort( 20, x ); printf( “%d”, x[ i ] ); } 数组元素的输出
66
例4-6 二分查找的实现 任务 算法思想 在一组数据中查找指定的数据 将数据按照升序排序成数组 以整个数组为查找范围
例4-6 二分查找的实现 任务 在一组数据中查找指定的数据 算法思想 将数据按照升序排序成数组 以整个数组为查找范围 用给定值Key与中间位置元素的值比较 若相等,则查找成功; 若 Key值小,继续对左半部分进行查找(重复3-6); 若 Key值大,继续对右半部分进行查找(重复3-6)。 如此重复,直到查找成功 或查找范围缩小为空,即查找失败为止。
67
算法设计(1/2) 数据对象设计 函数设计 保存所有数据的数组 a、元素个数 n 给定值 key 查找范围:下界 low, 上界 high
中间元素的下标 mid 函数设计 int Search( int key, int n, int a[ ] ); /* 在数组a中查找元素key, 返回下标或-1 */
68
算法设计(2/2) 排序 a 0low n-1high (low+high)/2 mid F T key>a[mid] F
mid-1high mid+1low T T F high≥low 返回-1 返回mid
69
程序实现 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; /* 未找到 */ }
70
在 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
71
算法设计(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); }
72
算法设计(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); }
73
函数设计小结 功能设计 局部化 常用限制 功能相对独立,规模适当 支持功能抽象,简化算法描述 对于复杂的算法,进一步采用功能抽象
尽可能不使用外部变量 用局部变量和形参描述所有数据对象 常用限制 复合语句层次不超过 3 层 函数代码长度小于30-40 行
74
TURBO C 对多文件处理的支持 建立工程文件 指定工程文件 编译和运行 如 Test.PRJ, 内容如下: src1.c src2.c
ALT + P 后,选择 Project Name,输入工程文件名 编译和运行 ALT + C 后,选择 Make 或 Build All 或者,直接用 Ctrl + F9 系统将生成执行文件 Test.EXE 每个文件中包含几个函数定义
75
第四章 作业 阅读第五章 程序设计练习 上机作业 自我测验5.2 5.4 5.6 5.7
第四章 作业 阅读第五章 自我测验 程序设计练习 上机作业 实验3.1 实验3.2 实验3.3
Similar presentations