Microsoft PowerPoint - CPP-Ch ppt [兼容模式]

Transcription

1 Chapter 6 Functions and an Introduction to Recursion 杨明 yangming2002@seu.edu.cn

2 OBJECTIVES To construct programs modularly from functions. To use common math functions available in the C++ Standard Library. To create functions with multiple parameters. The mechanisms for passing information between functions and returning results. How the function call/return mechanism is supported by the function call stack and activation records. To use random number generation to implement game-playing applications. How the visibility of identifiers is limited to specific regions of programs. To write and use recursive functions, i.e., functions that call themselves. 2

3 Topics 6.1 Introduction 6.2 Program Components in C Math Library Functions 6.4 Function Definitions with Multiple Parameters 6.5 Function Prototypes and Argument Coercion 6.6 C++ Standard Library Header Files 6.7 Case Study: Random Number Generation 6.8 Case Study: Game of Chance and Introducing enum 6.9 Storage Classes 6.10 Scope Rules 3

4 Topics 6.11 Function Call Stack and Activation Records 6.12 Functions with Empty Parameter Lists 6.13 Inline Functions 6.14 References and Reference Parameters 6.15 Default Arguments 6.16 Unary Scope Resolution Operator 6.17 Function Overloading 6.18 Function Templates 6.19 Recursion 6.20 Example Using Recursion: Fibonacci Series 6.21 Recursion vs. Iteration 4

5 6.1 Introduction How to develop and maintain large programs? divide and conquer( 分治法 ), 模块化编程 使程序由小到大构建, 易于管理 software reusability avoid repeating code makes the program easier to debug and maintain. Module: Classes + Functions 5

6 GradeBook::dispalyMessage() 类成员函数 6.1 Introduction int main() Global Function( 全局函数 ), 不是任何类的成员的函数. 如 :<cmath> 中的 pow() 函数 6

7 Function ( 函数 ) 6.1 Introduction 完成一项特定任务的代码行串, 由一个或多个语句块组成. 定义函数的语句通常只写一次, 这些语句对其它函数是不可见的 输入 黑盒 输出 7

8 6.1 Introduction Function is invoked by a function call 1 Provide function name and 实参 arguments (data) 2 Function performs its task 3 Function returns a result or simply returns control to the caller 8

9 Topics 6.1 Introduction 6.2 Program Components in C Math Library Functions 6.4 Function Definitions with Multiple Parameters 6.5 Function Prototypes and Argument Coercion 6.6 C++ Standard Library Header Files 6.7 Case Study: Random Number Generation 6.8 Case Study: Game of Chance and Introducing enum 6.9 Storage Classes 6.10 Scope Rules 12

10 6.2 Program Components in C C++ programs are typically written by combining new functions and classes with prepackaged functions and classes available in the C++ Standard Library. 13

11 6.2 Program Components in C++ 用户定义函数 标准库函数 common mathematical calculations, string manipulations, character manipulations, input/output, error checking and many other useful operations 14

12 Topics 6.1 Introduction 6.2 Program Components in C Math Library Functions 6.4 Function Definitions with Multiple Parameters 6.5 Function Prototypes and Argument Coercion 6.6 C++ Standard Library Header Files 6.7 Case Study: Random Number Generation 6.8 Case Study: Game of Chance and Introducing enum 6.9 Storage Classes 6.10 Scope Rules 15

13 6.3 Math Library Functions double ceil( double x ); rounds x to the smallest integer not less than x, 不小于 x 的最小整数 (>=) ceil(9.2) is 10.0, ceil( -9.8 ) is -9.0, ceil(2.0) is 2.0 double floor( double x ); rounds x to the largest integer not greater than x, 不大于 x 的最大整数 (<=) floor(9.2) is 9.0, floor(-9.8) is -10.0, floor(2.0) is

14 6.3 Math Library Functions double exp( double x ); exponential function e x, 指数函数 exp( 1.0 ) is , exp( 2.0 ) is double pow( double x, double y ); x raised to power y ( x y ), 幂函数 pow( 2, 7 ) is 128, pow( 9,.5 ) is 3 17

15 6.3 Math Library Functions double fmod( double x, double y ); remainder of x/y as a floating-point number,x 除以 y 的余数 (%, 整数 ) fmod( 2.6, 1.2 ) is 0.2 double sqrt( double x ); square root of x (where x is a nonnegative value), 非负数 x 的平方根 sqrt( 9.0 ) is

16 6.3 Math Library Functions double log( double x ); natural logarithm of x (base e), x 的自然对数 log( ) is 1.0, log( ) is 2.0 double log10( double x ); logarithm of x (base 10), x 的以 10 为底的对数值 log10( 10.0 ) is 1.0, log10( ) is

17 6.3 Math Library Functions double sin( double x ); trigonometric sine of x (x in radians), 弧度 x 的正弦值 sin( 0.0 ) is 0 double cos( double x ); trigonometric cosine of x (x in radians), 弧度 x 的余弦值 cos( 0.0 ) is

18 6.3 Math Library Functions double tan( double x ); trigonometric tangent of x (x in radians), x 的正切值 tan( 0.0 ) is 0 double fabs( double x ); absolute value of x, x 的绝对值 fabs( 5.1 ) is 5.1, fabs( 0.0 ) is 0.0, fabs( ) is

19 Topics 6.1 Introduction 6.2 Program Components in C Math Library Functions 6.4 Function Definitions with Multiple Parameters 6.5 Function Prototypes and Argument Coercion 6.6 C++ Standard Library Header Files 6.7 Case Study: Random Number Generation 6.8 Case Study: Game of Chance and Introducing enum 6.9 Storage Classes 6.10 Scope Rules 22

20 6.4 Function Definition with Multiple Parameters int maximum( int x, int y, int z ) ; 1. 函数定义 : 形式参数列表, 每个参数都必须指定类型, 参数之间逗号分隔 接口声明时, 函数参数名可以不指定 函数体定义时, 应指定参数名 23

21 6.4 Function Definition with Multiple Parameters maximum (10, a, b*c ); 2. 函数调用 : 实际参数列表, 参数不能包含类型说明, 逗号隔开 实参可以是常量 变量或者表达式 非逗号表达式, 取值顺序因编译器而异 maximum(x++, x+y, y); // x=0, y=1 NO! 24

22 6.4 Function Definition with Multiple Parameters 3. 函数调用返回 如果没有返回数据, void 则可以 return; 直接返回 没有 return 语句时, 至函数体右括号返回 如果有返回数据, 则 return expression; 返回 expression 可为常量 变量或者表达式 25

23 6.4 Function Definition with Multiple Parameters 1. void getnum() 2. { 3. int a = 0, b = 0; return; a = 3; 7. } 1. int getdate(){ 2. int day = 10; 3. int year = 9; return 0; 6. return day; 7. return year+2000; 8. } 26

24 Topics 6.1 Introduction 6.2 Program Components in C Math Library Functions 6.4 Function Definitions with Multiple Parameters 6.5 Function Prototypes and Argument Coercion 6.6 C++ Standard Library Header Files 6.7 Case Study: Random Number Generation 6.8 Case Study: Game of Chance and Introducing enum 6.9 Storage Classes 6.10 Scope Rules 27

25 6.5 Function Prototypes and Argument Coercion 1.Function Prototypes( 函数原型 ) 作用 : 告诉编译器和用户函数名 输入参数 ( 个数 类型 顺序 ) 返回类型返回类型函数名 ( 形式参数列表 ); 若无返回数据, 则 void 函数名必须为标识符 (identifier) 形参是需要被初始化的局部变量, 生命周期和可见性仅限于该函数内部 若无参数, 则 () 内为 void 或空 int maximum( int, int, int ); 28

26 6.5 Function Prototypes and Argument Coercion 函数原型的应用原则 : 函数必须先声明后使用 1 函数定义 ( 实现代码 ) 在前, 调用在后时, OK; 2 函数调用在前, 定义在后时? 必须在调用函数前给出函数原型 29

27 6.5 Function Prototypes and Argument Coercion 1. // 编写一个求 x 的 n 次方的函数 2. #include <iostream> 3. using namespace std; double power (double x, int n) 6. { 7. double val = 1.0; 8. while (n--) 9. val = val*x; 10. return val; 11. } 12. int main() 13. { 14. cout << "5 to the power 2 is " << power(5, 2) << endl; 15. return 0; 16. } 30

28 6.5 Function Prototypes and Argument Coercion 1. #include <iostream> 2. using namespace std; double power (double x, int n); // 用函数原型声明函数 5. int main() 6. { 7. cout << "5 to the power 2 is " << power(5, 2) << endl; 8. return 0; 9. } double power (double x, int n) 12. { 13. double val = 1.0; 14. while (n--) 15. val = val * x; 16. return val; 17. } error C2065: 'power' : undeclared identifier 31

29 6.5 Function Prototypes and Argument Coercion 2. 函数签名 (function signature) 作用 : 用于唯一确定所调用的函数! 函数原型中的函数名 + 参数 不包括函数返回类型 函数签名在同一个作用域内须唯一, 函数的作用域即程序中函数 " 可见 " ( 允许被访问 ) 的范围 int printlargestnum (int num1, int num2); void printlargestnum (int num1, int num2); int main() { printlargestnum (23, 76); return 0; } 32

30 1. // GradeBook.h 2. #include <string> error C2371: 'setcoursename' : redefinition; different basic types 3. using std::string; // GradeBook class definition 6. class GradeBook { 7. public: 8. GradeBook( string ); 9. void setcoursename( string ); 10. bool setcoursename( string ); 11. string getcoursename(); 12. void displaymessage(); 13. void determineclassaverage(); 14. private: string coursename; }; // end class GradeBook 33

31 6.5 Function Prototypes and Argument Coercion 3.Argument Coercion( 实参的强制类型转化 ) 函数原型 : double mysqrt (double); 函数调用 : int num = 4; cout << mysqrt( num ); 结果 : 能正确地求值 mysqrt(4). 34

32 6.5 Function Prototypes and Argument Coercion 3-1 提升规则 (promotion rule)- 隐性转化在不丢失数据的前提下, 将一种类型转换为另一种类型 1 函数的实参 函数实参类型不符合函数定义中指定的参数类型时, 自动将其转换为正确类型之后再进行函数调用 double pow(double, double); pow(1.0 + rate, year) int year; 35

33 6.5 Function Prototypes and Argument Coercion 3-1 提升规则 (promotion rule)- 隐性转化在不丢失数据的前提下, 将一种类型转换为另一种类型 2 混合类型表达式 (mixed-type expression) 表达式中每个值的类型提升为所在子表达式中最高的类型 生成每个值的临时值并在表达式中使用, 原值保持不变 int gradecounter = 2, counter = 2; num = 2.4 / gradecounter + 5 / counter; 36

34 基本数据类型的 高 - 低 顺序 Data types long double double float 字节 unsigned long int long int unsigned int int unsigned short int short int unsigned char char bool (synonymous with unsigned long) (synonymous with long) (synonymous with unsigned) (synonymous with unsigned short) (synonymous with short) 37

35 基本数据类型的 高 - 低 顺序 char short int long int 隐性转换方向相容数据类型! float unsigned char unsigned short unsigned int unsigned long double long double 38

36 6.5 Function Prototypes and Argument Coercion 3-2 显式转化若将 高级别 基本数据类型数据转化为 低级别 数据, 则会造成数据丢失, 必须进行显式转化. 1 赋值 1. int num = 4.3; 2. int square (int num); square(4.3); 相容数据类型可以进行 双向 的转化 39

37 6.5 Function Prototypes and Argument Coercion 3-2 显式转化若将 高级别 基本数据类型数据转化为 低级别 数据, 则会造成数据丢失, 必须进行显式转化. 2 类型转化操作符 double dnum = 4.3; int num = static_cast<int>(dnum); 40

38 Topics 6.1 Introduction 6.2 Program Components in C Math Library Functions 6.4 Function Definitions with Multiple Parameters 6.5 Function Prototypes and Argument Coercion 6.6 C++ Standard Library Header Files 6.7 Case Study: Random Number Generation 6.8 Case Study: Game of Chance and Introducing enum 6.9 Storage Classes 6.10 Scope Rules 42

39 6.6 C++ Standard Library Header Files C++ 头文件 : 1 标准 C 语言库函数的头文件, 带有.h 后缀 : #include <string.h> 2 标准 C++ 语言类库的头文件, 不带.h 后缀 : #include <iostream> 3 由标准 C 语言库函数头文件转换获得的标准 C++ 的头文件, 把原有标准 C 语言库函数头文件去掉.h 后缀而加上 c 前缀 #include <cstring> 43

40 6.6 C++ Standard Library Header Files 每个标准库都有对应的头文件, 包含库中所有抽象类型接口定义 函数原型, 以及这些函数所需各种常量的定义 C++ 标准库的内容在 50 个标准头文件中定义, 其中 18 个提供了 C 库的功能 44

41 6.6 C++ Standard Library Header Files 1. 语言支持 : 标准库中与语言支持功能相关 2. 输入 / 输出 : 支持流输入 / 输出 3. 诊断 : 与诊断功能相关 4. 一般工具 : 定义工具函数 5. 字符串 : 支持字符串处理 6. 容器 : 定义容器类的模板 7. 迭代器支持 : 支持迭代器 8. 算法 : 有关算法 9. 数值操作 : 有关数值操作 10. 本地化 : 有关本地化 45

42 输入 / 输出类头文件 <iostream> 支持标准流 cin/cout/cerr/clog 的输入和输出 <iomanip> 提供流操作算子, 允许改变流的状态, 从而改变输出的格式 <ios> 定义 iostream 的基类 <istream> 管理输入流缓存区的输入定义模板类 <ostream> 管理输出流缓存区的输出定义模板类 <fstream> 支持文件的流输入输出 <cstdio> 为标准流提供 C 样式的输入和输出 46

43 字符串类头文件 <string> 为字符串类型提供支持和定义, 包括单字节字符串 ( 由 char 组成 ) 和多字节字符串 <cctype> 单字节字符类别 <cwctype> 多字节字符类别 <cstring> C 类型字符串的处理函数 <cwchar> 为处理 执行 I/O 和转换多字节字符序列提供函数 <cstdlib> 为把单字节字符串转换为数值 在多字节字符和多字节字符串之间转换提供函数 47

44 数值操作类头文件 <complex> 支持复杂数值的定义和操作 <valarray> 支持数值矢量的操作 <numeric> 在数值序列上定义一组一般数学操作 <cmath> 这是 C 数学库, 并附加了重载函数以支持 C++ 约定 <cstdlib> 提供的函数可以提取整数的绝对值, 对整数进行取余数操作 48

45 工具类头文件 <utility> 定义重载的关系运算符, 简化关系运算符的写入, 它还定义了 pair 类型, 该类型是一种模板类型, 可以存储一对值 <functional> 定义了许多函数对象类型和支持函数对象的功能 <memory> 给容器 管理内存的函数和 auto_ptr 模板类定义标准内存分配器 <ctime> 支持系统时钟函数 49

46 Topics 6.1 Introduction 6.2 Program Components in C Math Library Functions 6.4 Function Definitions with Multiple Parameters 6.5 Function Prototypes and Argument Coercion 6.6 C++ Standard Library Header Files 6.7 Case Study: Random Number Generation 6.8 Case Study: Game of Chance and Introducing enum 6.9 Storage Classes 6.10 Scope Rules 50

47 6.7 Case Study: Random Number Generation 1. 随机数的产生 int rand(); #include <cstdlib> 返回伪随机数 ( 整型 ), 0 ~ RAND_MAX RAND_MAX, symbolic constant( 符号常量 ) #define RAND_MAX 0x7fff //

48 6.7 Case Study: Random Number Generation 2. 随机数种子的设置 void srand( unsigned int seed ); 通过设置 种子 (SEED) 来产生不同的随机数的序列, 程序中调用一次即可 只要种子不同, 那么通过多次 rand() 函数调用得到的随机数序列就不同 ; 反之, 如果种子一样, 那么通过 rand() 得到的随机数就是相同的 unsigned int 可简写为 unsigned 52

49 6.7 Case Study: Random Number Generation 53

50 6.7 Case Study: Random Number Generation 3. 种子的选择 time_t time( time_t *timer ); #include <ctime> 返回当前时间, 自 1970 年 1 月 1 日 0 点至今过去的秒数, 其中 time_t 即 long 数据类型 timer 设置为 NULL(==0) 即可 即 : srand ( time ( 0 ) ); 54

51 6.7 Case Study: Random Number Generation 4. 如何生成合适大小的随机数 Scaling, 按比例缩放, 等概率 Shifting, 平移 0 ~ RAND_MAX 0 ~ 5 Scaling& Shifting rand() % (b-a+1)+a rand() % 6 Scaling rand() % ~ 6 Shifting a ~ b ScalingFactor: 6, b-a+1 ShiftingValue: 1, a 55

52 6.7 Case Study: Random Number Generation 5. 结论 // 设置随机 SEED srand(time(0)); // 取 [a, b] 之间的随机数 int number = a + rand() % (b a + 1); 56

53 Topics 6.1 Introduction 6.2 Program Components in C Math Library Functions 6.4 Function Definitions with Multiple Parameters 6.5 Function Prototypes and Argument Coercion 6.6 C++ Standard Library Header Files 6.7 Case Study: Random Number Generation 6.8 Case Study: Game of Chance and Introducing enum 6.9 Storage Classes 6.10 Scope Rules 57

54 C++ 数据类型 数据类型 6.8 Case Study: Game of Chance and Introducing enum 基本数据类型 ( 系统提供 ) 构造数据类型 ( 用户定义 ) 抽象数据类型 ( 用户定义 ) 整数类型 : int 浮点类型 : float, double 字符类型 : char 布尔类型 : bool 空值类型 : void 枚举类型数组类型结构和联合类型指针类型引用类型 类 派生类 58

55 6.8 Case Study: Game of Chance and Introducing enum 如何表示周一 周二 周日?(1-7) 如何表示一月 二月 十二月?(1-12) 如何表示 RGB 三原色, 即红 绿 蓝?(1-3) 不直观, 易出错! int day = 1 表示周日? 周一? int day = 8? month = 13? 59

56 6.8 Case Study: Game of Chance and Introducing enum Enumeration type( 枚举数据类型 ): 用户自定义的构造数据类型, 其值集由用户程序定义 enum 枚举类型名 { 枚举值表 }; 例如 : enum Day { SUN, MON, TUE, WED, THU, FRI, SAT }; enum Month { JAN, FEB, MAR, APR, MAY, JUN, JUL, AUG, SEP, OCT, NOV, DEC}; enum Color { RED, GREEN, BLUE }; 60

57 6.8 Case Study: Game of Chance and Introducing enum enum Day { SUN, MON, TUE, WED, THU, FRI, SAT }; 每个枚举值都应是标识符, 对应一个整数值, 通常第一个枚举值对应常量值 0, 第二个对应 1, 依次递增类推 SUN 为 0, MON 为 1, TUE 为 2, WED 为 3, THU 为 4, FRI 为 5, SAT 为 6 61

58 6.8 Case Study: Game of Chance and Introducing enum 在定义枚举类型时, 也可以指定枚举值对应的常量, 后续值依次递增至结束或者至下一个指定 : enum Day { SUN=7, MON=1, TUE, WED, THU, FRI, SAT }; SUN 为 7, MON 为 1, TUE 为 2, WED 为 3, THU 为 4, FRI 为 5, SAT 为 6 注意 : 枚举值表中枚举值不能同名, 但是可以对应相同的整数常量值 62

59 6.8 Case Study: Game of Chance and Introducing enum enum Test { AA=3, BB, CC=3, DD=1, AA }; error C2086: 'AA' : redefinition enum Test { AA=3, BB, CC=3, DD=1, EE }; AA=3, BB=4, CC=3, DD=1, EE=2 63

60 6.8 Case Study: Game of Chance and Introducing enum enum Test { AA=3, BB, CC=3, DD=1, EE }; 两种定义方式 1 enum Test tt; 2 Test tt; 变量的赋值 1 tt = AA; // OK 2 tt = 3; // ERROR, 用户构造 / 基本类型非相容类型 64

61 enum Test { AA=3, BB, CC=3, DD=1, EE }; 6.8 Case Study: Game of Chance and Introducing enum 枚举变量的应用 : 根据对应的整数值 关系运算 : ==, >, <, >=, <= switch 比对 1. enum Test tt; 2. tt = AA; 3. cout <<boolalpha << (tt == CC) << endl; 4. cout <<boolalpha << (tt == 3) << endl; 65

62 6.8 Case Study: Game of Chance and Introducing enum Craps 双色子赌博游戏 1. 第一把 1 掷出点数为 7 或 11, 则玩家 WON; 2 掷出点数为 2 3 或 12, 则玩家 LOST; 3 否则记下该点数 (Point), 进入 2; 2. 继续掷色子, CONTINUE 1 掷出 7, 则玩家 LOST; 2 掷出点数 ==Point, 则玩家 WON; 3 否则重复 2., CONTINUE 66

63 6.8 Case Study: Game of Chance and Introducing enum Craps 双色子赌博游戏 1. 掷色子 : 1 6 点随机数生成 srand(time(0)) / rand() 2. 根据两个色子点数和 (2 12), 判断游戏者状态 选择语句, 多选 switch 3. 游戏状态 WON/LOST/CONTINUE 枚举类型 enum 67

64 Topics 6.1 Introduction 6.2 Program Components in C Math Library Functions 6.4 Function Definitions with Multiple Parameters 6.5 Function Prototypes and Argument Coercion 6.6 C++ Standard Library Header Files 6.7 Case Study: Random Number Generation 6.8 Case Study: Game of Chance and Introducing enum 6.9 Storage Classes 6.10 Scope Rules 69

65 6.9 Storage Classes - Introduction (1) 标识符 (Identifier) 用于变量 类型 函数与标签等的命名 由字母 (a ~ z 或 A ~ Z) 数字 (0 ~ 9) 下划线 ( _ ) 组成 必须由字母或下划线开头 大小写敏感 70

66 6.9 Storage Classes - Introduction (2) 变量 (Variable) 在程序运行过程中从程序外部获得或在程序运行过程中通过计算产生值的 其值可以变化的数据 在内存中占据一定的逻辑存储空间 变量的基本属性 : 1 名字 Name 2 类型 Type 3 值 Value 4 内存空间 ( 地址 ) Size 71

67 6.9 Storage Classes - Introduction (3) 常量 (Constant) 在程序执行过程中值保持不变的数据 分为直接常量和符号常量两类 : 1 直接常量.65, a, \141, \x61, \\, a, This is a string 2 符号常量 #define < 符号 > < 值 > #define EOF -1 #define PI const < 类型名 > < 常量名 >=< 值 >; const double PI = ; // 命名常量 72

68 6.9 Storage Classes - Introduction (4) 表达式 (Expression) 由操作符 操作数等组成的运算式, 用于表达一个计算过程 单个操作数 ( 变量 常量 函数调用 ) 也是表达式, 称为基本表达式 表达式中的操作数可以是变量 常量 函数调用, 也可以是表达式 上述函数调用必须有返回值 73

69 6.9 Storage Classes - Introduction 标识符 描述 特性 类型变量函数名等存储类别 Storage Class 作用域 Scope 链接 Linkage 74

70 6.9 Storage Classes - Introduction 存储类别 (Storage Class) 决定标识符在内存中的生存期 : 有些标识符的存在时间很短, 有些重复生成和删除, 有些则存在于整个程序的执行期间 1. void inputgrade() 2. { 3. int grade;// 第 2 次调用时, 90 是否存在? 4. cin >> grade;// 第 1 次调用, 输入 } 75

71 6.9 Storage Classes - Introduction 作用域 (Scope, Ch 6.10) 指程序中能访问这个标识符的区域 : 有些标识符可以在整个程序中访问, 而有些标识符只能在程序中的有限部分访问 1. void GradeBook::inputGrade() 2. { 3. int grade1, grade2;// getaverage() 能否访问到这两个变量? 4. cin >> grade1 >> grade2; 5. } 6. double GradeBook::getAverage() 7. { 8. return (grade1+grade2) / 2.0; 9. } // ERROR 76

72 6.9 Storage Classes( 存储类别 ) 两种存储类别 : (1) Automatic Storage Class ( 自动存储类别, 变量 ) auto, register 说明符 (specifier) (2) Static Storage Class ( 静态存储类别, 变量和函数 ) static, extern 说明符 78

73 6.9 Storage Classes( 存储类别 ) (1) 自动存储类别 (Automatic Storage Class) 在进入程序块执行时生成, 退出时销毁 ( 释放内存 ) 只有函数的局部变量可以 ( 通常 ) 是自动存储类别, 包括函数内部定义的局部变量和形参, 简称自动变量 79

74 6.9 Storage Classes( 存储类别 ) 1. void test (int a) 2. { 3. int b; 4. cin >> b; 5. { 6. int c = a + b; 7. cout << c << endl; 8. } 9. } 80

75 6.9 Storage Classes( 存储类别 ) (2) 静态存储类别 (static storage class) 生存期为整个程序运行期间, 可适用于变量和函数 两种静态存储类别的标识符 1 External identifier: 全局变量名和全局函数名 2 static 修饰的局部变量名 83

76 6.9 Storage Classes( 存储类别 ) 说明符 1: static 1 用于修饰函数中的局部变量时 * 该变量属于静态存储类别 仅在变量声明时进行一次初始化 函数结束时, 保留变量的数值 ; 在下次调用时, 依然可以使用上次函数退出时的值 数值变量默认初始化为 0 2 还可以修饰全局变量和全局函数 (Linkage), 以及类成员函数和成员变量 84

77 6.9 Storage Classes( 存储类别 ) 说明符 2: extern 用于修饰全局函数 / 全局变量 static 和 extern 修饰全局函数和全局变量时, 涉及多源文件程序中的 Linkage 等问题 85

78 6.9 Storage Classes( 存储类别 ) void test () { static int n = 10; cout << n++ << ; } void test () { static int n; cout << n++ << ; } int main() { test(); test(); test(); return 0; } void test () { static int n; n = 10; cout << n++ << ; }

79 6.9 Storage Classes( 存储类别 ) 存储类别 进出定义标识符的块 自动存储类别 静态存储类别 整个程序运行期间 函数局部变量和形参为自动存储类别 但是 static 修饰的局部变量为静态存储类别 全局函数和全局变量为静态存储类别 87

80 Topics 6.1 Introduction 6.2 Program Components in C Math Library Functions 6.4 Function Definitions with Multiple Parameters 6.5 Function Prototypes and Argument Coercion 6.6 C++ Standard Library Header Files 6.7 Case Study: Random Number Generation 6.8 Case Study: Game of Chance and Introducing enum 6.9 Storage Classes 6.10 Scope Rules 88

81 6.10 Scope Rules( 作用域规则 ) scope( 作用域 ): 程序中一个标识符可以被使用的范围 (1) 函数作用域 (function scope) 整个函数, 可以在整个函数体的任何地方使用该标识符 标签 (label) 是唯一具有函数作用域的标识符 89

82 6.10 Scope Rules( 作用域规则 ) 1. void func( int x ) 2. { 3. int a = 2, b = 5; 4. goto start; 5. b = 3; 6. start: a = b; 7. cout << a << << b << endl; 8. }

83 6.10 Scope Rules( 作用域规则 ) (2) 文件作用域 (file scope) 声明 文件结束 : 从该标识符声明处起到文件末尾的任何函数中都可以访问 在函数和类外声明的标识符, 如全局变量名 全局函数名 91

84 6.10 Scope Rules( 作用域规则 ) 1. // 编写一个求 x 的 n 次方的函数, 文件作用域 2. #include <iostream> 3. using namespace std; int rubbish = 10; double power(double x, int n) 6. { 7. double val = 1.0; 8. while (n--) 9. val = val*x; 10. return val; 11. } 12. int main() 13. { 14. cout << "5 to the power 2 is " << power(5, 2) << endl; 15. return 0; 16. } 92

85 6.10 Scope Rules( 作用域规则 ) (3) 块作用域 (block scope) 声明 块尾 : 从标识符声明开始, 到所在块结束的右花括号处结束, 也称局部作用域 (Local Scope) 块中声明的标识符 93

86 6.10 Scope Rules( 作用域规则 ) 1. void test ( int a ) 2. { 3. int b; 4. cin >> b; 5. { 6. int c = a + b; 7. cout << c << endl; 8. } 9. } 94

87 6.10 Scope Rules( 作用域规则 ) (4) 函数原型作用域 (function-prototype scope) 参数列表 () 中, 函数原型中使用的标识符可以在程序中的其它地方复用, 不会产生歧义 函数原型中的形参名是唯一具有该作用域的标识符 函数原型不要求参数表给出名称, 只要求类型, 编译器将忽略给出的参数名 void uselocal( int a, int b ); // function prototype void max( int a, int b ); // function prototype 95

88 6.10 Scope Rules( 作用域规则 ) (5) 类作用域 Class Scope, Ch9 (6) 名空间作用域 Namespace Scope, Ch24 96

89 Topics 6.11 Function Call Stack and Activation Records 6.12 Functions with Empty Parameter Lists 6.13 Inline Functions 6.14 References and Reference Parameters 6.15 Default Arguments 6.16 Unary Scope Resolution Operator 6.17 Function Overloading 6.18 Function Templates 6.19 Recursion 6.20 Example Using Recursion: Fibonacci Series 6.21 Recursion vs. Iteration 97

90 6.11 Function Call Stack and Activation Records( 函数调用栈和活动记录 ) 程序占用内存区域的分布 : 代码区 (code area) 被编译程序的执行代码部分 全局数据区 (data area) 常量 ( 静态 ) 全局量和静态局部量等 堆区 (heap) 动态分配的内存, new / delete 栈区 (stack) 函数数据区, 函数形参和局部变量等自动变量所使用的内存区域 98

91 6.11 Function Call Stack and Activation Records( 函数调用栈和活动记录 ) 栈 : 后进先出 (LIFO: last-in, first-out) 访问 (top) 进栈 (push) 出栈 (pop) entry stack 99

92 6.11 Function Call Stack and Activation Records( 函数调用栈和活动记录 ) 1. // 测试阶乘计算函数的主程序 2. #include <iostream> 3. using namespace std; 4. double fun(int); 5. int main() 6. { 7. int n; 8. cin >> n; 9. cout << n << "! = " << fun(n) << endl; 10. return 0; 11.} 100

93 6.11 Function Call Stack and Activation Records( 函数调用栈和活动记录 ) 函数调用和返回的过程 101

94 6.11 Function Call Stack and Activation Records( 函数调用栈和活动记录 ) 利用栈保存函数的活动记录当前执行函数的活动记录总在栈顶 活动记录 调用函数的返回地址 (main) 被调用函数 (fun) 的自动变量 ( 函数形参和局部变量 ) 活动记录的作用 : 谁调用了我, 即当前函数执行完时返回哪儿 如何维护本地的自动变量数据 102

95 Step 1:OS 调用 main 函数 main 函数活动记录入栈 103

96 Step2:main 函数调用 square square 函数活动记录入栈 104

97 Step3:square 结束后返回到 main square 函数返回 main 函数执行至 return 0 105

98 Topics 6.11 Function Call Stack and Activation Records 6.12 Functions with Empty Parameter Lists 6.13 Inline Functions 6.14 References and Reference Parameters 6.15 Default Arguments 6.16 Unary Scope Resolution Operator 6.17 Function Overloading 6.18 Function Templates 6.19 Recursion 6.20 Example Using Recursion: Fibonacci Series 6.21 Recursion vs. Iteration 106

99 6.12 Functions with Empty Parameter Lists An empty parameter list ( 空参数列表 ) is specified by writing 1 either void or 2 nothing at all in parentheses 1. // function that takes no arguments 2. void function1(); // 空括号 3. // function that takes no arguments 4. void function2( void ); // 带 void 的括号 12. function1(); // 函数调用 13. function2(); // 无 void 107

100 Topics 6.11 Function Call Stack and Activation Records 6.12 Functions with Empty Parameter Lists 6.13 Inline Functions 6.14 References and Reference Parameters 6.15 Default Arguments 6.16 Unary Scope Resolution Operator 6.17 Function Overloading 6.18 Function Templates 6.19 Recursion 6.20 Example Using Recursion: Fibonacci Series 6.21 Recursion vs. Iteration 110

101 6.13 Inline Functions( 内联函数 ) 模块化编程, 把完成特定功能的代码包装成为函数 函数调用产生较为复杂的栈操作, 引起相应的开销 需求 : 对于代码量较小的功能模块, 如何既能进行包装以方便调用, 又能避免函数调用引起的性能开销? 111

102 6.13 Inline Functions( 内联函数 ) inline function 内联函数在函数返回类型前加 inline, 建议编译器在调用该函数的地方通过插入函数代码副本的方式来避免产生函数调用以及相应的开销 1. 建议 : 通常编译器不会按照 inline 的指示执行, 除非该函数代码特别简单 2. 代码副本 : 通过插入代码副本的方式避免函数调用, 会使程序体积变大 ; 如果内联函数代码发生了改变, 那么所有应用该内联函数的源码文件都需要重新编译 ; 即使接口实现分离, 也需要在头文件中给出函数定义! 112

103 1. // Fig. 6.18: fig06_18.cpp 2. // Using an inline function to calculate the volume of a cube. 3. #include <iostream> 4. using std::cout; 5. using std::cin; 6. using std::endl; // Definition of inline function cube. Definition of function appears 9. // before function is called, so a function prototype is not required. 10. // First line of function definition acts as the prototype. 11. inline double cube( const double side ) 12. { 13. return side * side * side; // calculate cube 14. } int main() 17. { 18. double sidevalue; // stores value entered by user 19. cout << "Enter the side length of your cube: "; 20. cin >> sidevalue; // read value from user // calculate cube of sidevalue and display result 23. cout << "Volume of cube with side " 24. << sidevalue << " is " << cube( sidevalue ) << endl; 25. return 0; // indicates successful termination 26. } const: side 为常变量, 在函数体中不能被赋值和修改. Principle of Least Privilege 最小授权原则, 仅赋予完成任务的最小权限! 115

104 6.13 Inline Functions( 内联函数 ) 1. inline double cube( const double side ) 2. { 3. side++; // side = side + 1; 4. return side*side*side; 5. } error C2166: l-value specifies const object 116

105 Topics 6.11 Function Call Stack and Activation Records 6.12 Functions with Empty Parameter Lists 6.13 Inline Functions 6.14 References and Reference Parameters 6.15 Default Arguments 6.16 Unary Scope Resolution Operator 6.17 Function Overloading 6.18 Function Templates 6.19 Recursion 6.20 Example Using Recursion: Fibonacci Series 6.21 Recursion vs. Iteration 117

106 6.14 References and Reference Parameters 传值 (pass-by-value) 1. int squarebyvalue( int x ) 2. { 3. return x *= x; 1 4. } 2 5. int main() 6. { 7. int x = 2; 8. cout << squarebyvalue(x) << << x; 9. return 0; 10. } 将实参 x 的值 2 传递给形参, 即 squarebyvalue 函数局部变量 x squarebyvalue 函数局部变量 x 初始化为 2, int x = 2 3 计算 x*=x, 即 x = x * x, 即 x = 4 4 返回乘法赋值表达式的值, 即

107 6.14 References and Reference Parameters 需求 1. void inputgrade( int grade ) 2. { 3. cout << 请输入下一个成绩 : ; 4. cin >> grade; // 输入 } 6. int main() 7. { 8. int grade = 0; 9. inputgrade( grade ); 10. cout << grade << endl; 11. return 0; 12. } 如何通过函数调用, 来对实参赋值或者修改实参值? 119

108 6.14 References and Reference Parameters 函数参数传递的两种方式 : Pass-by-Value, 传值 Pass-by-Reference, 传引用 Reference Parameter, 引用参数 Pointer Parameter, 指针参数 (Ch 8.4) 120

109 6.14 References and Reference Parameters Reference( 引用 ): 变量的别名 (Alias), 通过别名可以直接访问 ( 读 / 写 ) 该变量 1. int main() 2. { 3. int x = 3; x(y) int &y = x; // y refers to (is an alias for) x cout << "x = " << x << endl << "y = " << y << endl; 7. y = 7; // actually modifies x 8. cout << "x = " << x << endl << "y = " << y << endl; 9. return 0; 10. } 121

110 6.14 References and Reference Parameters 要求 : 声明引用变量时, 必须同时进行初始化, 即指出是哪个变量的引用 / 别名 1. int x = 100; 2. int &y; 3. y = x; error C2530: 'y' : references must be initialized 1. int x = 100, z = 200; 2. int &y = x; 3. y = z; 将 z 的值 200 赋值给别名 y 对应的内存空间 y = 200, x =

111 6.14 References and Reference Parameters Reference Parameter( 引用参数 ): 函数调用过程中, 建立实参的别名 1. void squarebyreference( int &numberref ){ 2. numberref *= numberref; numberref 是一指向整型变 3. } 量的引用 4. int main() 5. { int &numberref = z 6. int z = 4; 7. cout << "z = " << z << " before squarebyreference" << endl; 8. squarebyreference( z ); 9. cout << "z = " << z << " after squarebyreference" << endl; 10. return 0; 11. } // numberref 是指向 z 变量的引用 123

112 6.14 References and Reference Parameters 1. // 错误代码 2. void inputgrade( int grade ) 3. { 4. cout << 请输入成绩 : ; 5. cin >> grade; // 输入 } 7. int main() 8. { 9. int grade = 0; 10. inputgrade( grade ); 11. cout << grade << endl; 12. return 0; 13. } 1. // 正确代码 2. void inputgrade(int &graderef) 3. { 4. cout << 请输入成绩 : ; 5. cin >> graderef; 6. } 7. int main() 8. { 9. int grade = 0; 10. inputgrade( grade ); 11. cout << grade << endl; 12. return 0; 13. } 124

113 6.14 References and Reference Parameters 引用参数的意义 : 1 通过引用参数, 可以在函数体内设定或者改变实参的值 ; 2 避免函数调用时传值方式所需要的对实参进行的值拷贝操作, 可以有效提高程序性能. 125

114 6.14 References and Reference Parameters 问题 : 如何能既避免值拷贝操作, 又避免允许改变实参的值? 1. int squarebyreference( const int &numberref ) 2. { 3. return numberref * numberref; 4. } 5. int main() 6. { 7. int num = 4; 8. cout << squarebyreference( num ); 9. return 0; 1. numberref 是实参 num 的引用 ( 别名 ) 10. } 2. numberref 受 const 的限定 126

115 6.14 References and Reference Parameters Modifiable arguments, 引用或指针参数 void func( int &num ); void func( int *num ); Small non-modifiable arguments, 传值 int func( int num ); Large non-modifiable arguments, 常量参数引用 int func( const GradeBook &book ); 127

116 函数返回引用 1. int& test() int& ref = test(); 2. { 3. int ret = 0; 4. return ret; 5. } 6.14 References and Reference Parameters 1. int& test() 2. { 3. static int ret = 0; // 必须为静态变量 4. return ret; 5. } Dangling Reference warning C4172: returning address of local variable or temporary 128

117 Topics 6.11 Function Call Stack and Activation Records 6.12 Functions with Empty Parameter Lists 6.13 Inline Functions 6.14 References and Reference Parameters 6.15 Default Arguments 6.16 Unary Scope Resolution Operator 6.17 Function Overloading 6.18 Function Templates 6.19 Recursion 6.20 Example Using Recursion: Fibonacci Series 6.21 Recursion vs. Iteration 129

118 6.15 Default Arguments 需求 如果在调用函数时, 经常对某个 ( 些 ) 形参传递相同的实参值, 那么可以为这个 ( 些 ) 形参设置 Default Argument ( 默认 / 缺省实参 ) 缺省值可以是任意表达式, 包括常量 全局变量甚至函数调用 ( 返回值 ) 等. 130

119 6.15 Default Arguments 定义 默认实参应在函数名第一次出现时设定, 即函数原型 ( 或类接口 ), 或者函数定义的函数头部, 且仅设定一次. // Case1: 函数原型中设定默认实参 int boxvolume( int = length 1, int = 1, int width = 1 ); = 1, int height = 1 ); int main() { boxvolume(); } int boxvolume( int length, int width, int height ) { return length * width * height; } 131

120 6.15 Default Arguments 定义 默认实参应在函数名第一次出现时设定, 即函数原型 ( 或类接口 ), 或者函数定义的函数头部, 且仅设定一次. // Case 2: 函数定义的函数头中设定默认实参 int boxvolume( int length = 1, int width = 1, int height = 1 ) { return length * width * height; } int main() { boxvolume(); } 132

121 6.15 Default Arguments 定义 1. int boxvolume( int length, int width, int height ); 2. int main() 3. { 4. boxvolume(); 5. return 0; 6. } 7. int boxvolume( int length = 1, int width = 1, int height = 1) 8. { 9. return length * width * height; 10. } 无效设置, 编译器认为 boxvolume 函数无默认参数 error C2660: 'boxvolume' : function does not take 0 parameters 133

122 6.15 Default Arguments 定义 1. int boxvolume( int length = 1, int width = 1, int height = 1 ); 2. int main() 3. { } 6. int boxvolume( int length = 1, int width = 1, int height = 1) 7. { 8. return length * width * height; 9. } error C2572: 'boxvolume' : redefinition of default parameter 134

123 6.15 Default Arguments 定义 默认实参必须是函数参数列表中右端 ( 尾部 ) 的参数, 即 : 如果某个参数设定了默认实参, 那么该参数右边的所有参数都必须具有默认实参! // OK int boxvolume( int length = 1, int width = 1, int height = 1 ); int boxvolume( int length, int width = 1, int height = 1 ); int boxvolume( int length, int width, int height = 1 ); // ERROR int boxvolume( int length = 1, int width, int height = 1 ); int boxvolume( int length, int width=1, int height ); 135

124 6.15 Default Arguments - 函数调用 显式传递给函数的实参是从左至右给形参赋值 函数调用时, 若省略了某个 ( 些 ) 实参, 那么将自动插入默认实参 136

125 6.15 Default Arguments - 函数调用 int boxvolume( int length=1, int width=1, int height=1 ); 1. boxvolume(); length = 1, width = 1, height = 1 2. boxvolume(10); length = 10, width = 1, height = 1 3. boxvolume(10, 5); length = 10, width = 5, height = 1 4. boxvolume(10, 5, 2); length = 10, width = 5, height = 2 137

126 6.15 Default Arguments - 函数调用 1. class Test{ 2. public: 3. void abc(int = 1, int = 2, int = 3); 4. }; 1. #include "test.h" 2. int main() 3. { 4. Test test; 5. test.abc(2); test.abc(2, 3); 6. return 0; 7. } 1. #include <iostream> 2. using namespace std; 3. #include "test.h" 4. void Test::abc( int a, int b, int c ) 5. { 6. cout << "a=" << a << ", b=" << b << ", c=" << c << endl; 7. } a=2, b=2, c=3 a=2, b=3, c=3 138

127 Topics 6.11 Function Call Stack and Activation Records 6.12 Functions with Empty Parameter Lists 6.13 Inline Functions 6.14 References and Reference Parameters 6.15 Default Arguments 6.16 Unary Scope Resolution Operator 6.17 Function Overloading 6.18 Function Templates 6.19 Recursion 6.20 Example Using Recursion: Fibonacci Series 6.21 Recursion vs. Iteration 139

128 6.16 Unary Scope Resolution Operator 全局变量与局部变量同名, 如何访问全局变量? Unary Scope Resolution Operator, 一元作用域解析符 140

129 1. #include <iostream> 2. using std::cout; 3. using std::endl; int number = 7; // global variable named number 6. int main() 7. { 8. double number = 10.5; // local variable named number 9. // display values of local and global variables 10. cout << "Local double value of number = " << number 11. << "\nglobal int value of number = " << ::number << endl; 12. return 0; 13. } 6.16 Unary Scope Resolution Operator 即使没有同名局部变量存在, 也建议用 :: 修饰全局变量! 141

130 Topics 6.11 Function Call Stack and Activation Records 6.12 Functions with Empty Parameter Lists 6.13 Inline Functions 6.14 References and Reference Parameters 6.15 Default Arguments 6.16 Unary Scope Resolution Operator 6.17 Function Overloading 6.18 Function Templates 6.19 Recursion 6.20 Example Using Recursion: Fibonacci Series 6.21 Recursion vs. Iteration 142

131 6.17 Function Overloading 计算 int 型变量和 double 型变量的平方值 方案 1: double squared( double ); int squaren( int ); 缺点 : 针对每种类型参数, 需要调用对应的函数, 使用不方便 方案 2: double square( double ); 缺点 : 归于最高级别的操作数运算, 性能损失 143

132 6.17 Function Overloading 判断两 / 三个整型数之间的最大值 int max2( int, int ); int max3( int, int, int ); 缺点 : 使用不方便 144

133 6.17 Function Overloading 函数重载 : C++ 允许函数同名, 但要求参数不同 ( 数量 类型或顺序 ) double square( double ); int square( int ); double square( int ); // 函数签名必须不同 int max( int, int ); int max( int, int, int ); Function Overloading( 函数重载 ) Operator Overloading( 运算符重载 ) 145

134 6.17 Function Overloading C++ 中如何实现重载函数调用 double square( double ); int square( int ); square( 7.5 ); square( 7 ); 1. 编译器根据实参类型进行类型匹配, 以选择合适的函数进行调用 2. 如果没有能严格匹配的, 则根据相容类型的参数隐性转化 ( 类型提升 : 低 高 ) 来寻求匹配 3. 如果无法隐性转化, 则寻求相容类型的参数显式转化 ( 高 低 ) 来匹配 146

135 6.17 Function Overloading 1. double square( double num ){ 2. cout << "double version called!" << endl; 3. return num * num; 4. } 5. float square( float num ){ 6. cout << "float version called!" << endl; 7. return num * num; 8. } 9. int square( int num ){ 10. cout << "int version called!" << endl; 11. return num * num; 12. } int main() 15. { 16. square( 1.0 ); 17. square( 10 ); 18. square( 'a' ); 19. return 0; 20. } // double version called! // int version called! // int version called! 147

136 6.17 Function Overloading C++ 中如何支持重载函数 Name mangling (Name decoration) 编译器对函数名标识符结合函数参数的数量和类型进行编码, 以确保能调用正确的重载函数, 即进行类型安全的链接 (Type-safe linkage). 149

137 6.17 Function Overloading int square( int x ) double square( double y ) void nothing1( int a, float b, char c, int &d ) int nothing2( char a, int b, float &c, double &d ) int main() // Borland C , square $q square $q nothing1 $q i f c nothing2 $q c i rf rd _main // not mangled, 不能重载 150

138 6.17 Function Overloading int square( int x ) // VC6.0, 含返回类型? A H 前缀? 函数名 square@ 普通函数 函数访问方式 cdecl A 返回值 int H 参数 1 int H 151

139 重载与缺省参数 6.17 Function Overloading 1. void test ( int a ) = 1 ) 2. { 3. cout << "Function 1 is called" << endl; 4. } 5. void test() 6. { 7. cout << "Function 2 is called" << endl; 8. } 9. int main() 10. { 11. test(); 12. return 0; 13. } error C2668: 'test' : ambiguous call to overloaded function 153

140 Topics 6.11 Function Call Stack and Activation Records 6.12 Functions with Empty Parameter Lists 6.13 Inline Functions 6.14 References and Reference Parameters 6.15 Default Arguments 6.16 Unary Scope Resolution Operator 6.17 Function Overloading 6.18 Function Templates 6.19 Recursion 6.20 Example Using Recursion: Fibonacci Series 6.21 Recursion vs. Iteration 154

141 1. double square( double num ){ 2. return num * num; 3. } 4. float square( float num ){ 5. return num * num; 6. } 7. int square( int num ){ 8. return num * num; 9. } 如何避免重复编码? 6.18 Function Templates 155

142 6.18 Function Templates 重载函数是针对不同数据进行类似的操作 int max( int, int, int ); double max( double, double, double ); 更进一步, 如果操作的程序逻辑完全相同, 仅仅是操作数据的类型不同, 那么可以使用函数模板. 156

143 1. // Fig. 6.26: maximum.h 2. template < class T > // or template< typename T > 3. T maximum( T value1, T value2, T value3 ) 4. { 5. T maximumvalue = value1; // assume value1 is maximum // determine 参数称为 whether formal type value2 parameter is greater ( 形式类型参数 than maximumvalue ) 占位 8. if ( value2 符, 在函数调用时替换为实参的数据类型 > maximumvalue ). 9. maximumvalue 每个参数都必须以关键词 = value2; class ( 或 typename) 起头, 参数和参数之间必须以逗号分隔, 如 <class T, class V> // determine whether value3 is greater than maximumvalue 12. if ( value3 > maximumvalue ) 13. maximumvalue = value3; 14. template 关键字 + 尖括号 < > 括起来的 template parameter list ( 模板参数列表 ) 模板参数列表 : 15. return maximumvalue; 16. } // end function template maximum 6.18 Function Templates 157

144 1. // Fig. 6.26: maximum.h 2. template < class T > // or template< typename T > 3. T maximum( T value1, T value2, T value3 ) 4. { 5. T maximumvalue = value1; // assume value1 is maximum // determine whether value2 is greater than maximumvalue 8. if ( value2 量的类型 > maximumvalue ) 9. maximumvalue = value2; // determine whether value3 is greater than maximumvalue 12. if ( value3 > maximumvalue ) 13. maximumvalue = value3; return maximumvalue; 16. } // end function template maximum 6.18 Function Templates T 可用于指定函数返回值 形参以及局部变 应至少有一形参用 T 修饰 158

145 6.18 Function Templates 函数模板的调用与普通函数一致 maximum( 1, 2, 3 ); // int maximum( 1.0, 2.0, 3.0 ); // double maximum( 1, 2, 3 ); // char 编译器根据实参的类型对模板进行特化, 生成各个 function template specializations, 即使用实参的类型替换模板定义中的形式类型参数 ( 即占位符 T) 159

146 1. // Fig. 6.26: maximum.h 2. template // 形式类型参数 < class T 为 T int > 类型 3. int T maximum( T int value1, int T value2, int T value3 ) 4. { 5. int T maximumvalue = value1; Function Templates maximum(1, 2, 3 ); 编译器确定形式类型参数 T 为 int 型 生成函数模板特化 160

147 6.18 Function Templates 编译器将根据函数调用时的实参类型, 生成 maximum 函数模板的 int / double / char 三种数据类型的特化 Debug 版本目标文件 fig06_27.obj:? A A A 161

148 Topics 6.11 Function Call Stack and Activation Records 6.12 Functions with Empty Parameter Lists 6.13 Inline Functions 6.14 References and Reference Parameters 6.15 Default Arguments 6.16 Unary Scope Resolution Operator 6.17 Function Overloading 6.18 Function Templates 6.19 Recursion 6.20 Example Using Recursion: Fibonacci Series 6.21 Recursion vs. Iteration 164

149 6.19 Recursion( 递归 ) 概念 递归函数 (recursive function) 如果一个函数在其函数体中直接或间接地调用了自己, 则该函数称为 递归函数. // 直接调用自己 void f( ) { int n = 0; f( ); } // 间接调用自己 void h( ); void g( ) { h( ); } void h( ) { g( ); } 165

150 6.19 Recursion( 递归 ) 意义 例如 : 设计函数 factorial 求阶层 n! 1! 直接知道结果 1 if( n == 1) return 1; 100! 100 * 99! if( n > 1 ) return n * factorial( n 1 ); 166

151 6.19 Recursion( 递归 ) 设计 给定问题 分治 划分为两类问题 : 1. Know how to do (100) 2. Does not know how to do (99!) 对子问题 2, 模拟原问题继续划分 核心思路 : 每次函数调用时都使问题进一步简化, 从而产生越来越小的问题, 最终简化到基本情况. 这时函数能识别并处理这个基本情况. 直到能够直接求出子问题 2 的解 ( 达到问题的 base case), 递归结束. 逐级 return 问题的解 167

152 6.19 Recursion( 递归 ) n! 示例 168

153 6.19 Recursion( 递归 ) n! 示例 1. int f ( int n ){ 2. if (n == 1) 3. return 1; 4. else 5. return n*f(n-1); 6. } 递推推导比原问题简单的问题回归简单问题得到解后, 回归获得原问题的解 f(4) f(3) f(2) f(1) 24 4*f(3) 6 3*f(2) 2 2*f(1)

154 6.19 Recursion( 递归 ) n! 示例 main 函数 : f( 4 ); int f( int n ){ // 4 n==1: return 1; n!=1 : return n*f(n-1); } int f( int n ){ // 3 n==1: return 1; n!=1 : return n*f(n-1); } int f( int n ){ // 2 n==1: return 1; n!=1 : return n*f(n-1); } int f( int n ){ // 1 n==1: return 1; n!=1 : return n*f(n-1); } f() 函数局部变量 n=1 f() 函数局部变量 n=2 f() 函数局部变量 n=3 f() 函数局部变量 n=4 main 函数局部变量 函数调用栈 注意 : Stack overflow, 栈溢出问题 170

155 1. // Fig. 6.29: fig06_29.cpp 2. // Testing the recursive factorial function. 3. #include <iostream> 4. using std::cout; 5. using std::endl; #include <iomanip> 8. using std::setw; unsigned long factorial( unsigned long ); // function prototype int main() 13. { 14. // calculate the factorials of 0 through for ( int counter = 0; counter <= 10; counter++ ) 16. cout << setw( 2 ) << counter << "! = " << factorial( counter ) 17. << endl; return 0; // indicates successful termination 20. } // end main // recursive definition of function factorial 23. unsigned long factorial( unsigned long number ) 24. { 25. if ( number <= 1 ) // test for base case 26. return 1; // base cases: 0! = 1 and 1! = else // recursion step 28. return number * factorial( number - 1 ); 29. } // end function factorial 无符号长整型 : 没有符号位 unsigned long: 0 ~ (2^32-1) int: ~

156 6.19 Recursion( 递归 ) 迭代法 (iteration) 也称辗转法, 是一种不断用变量的旧值推导新值的过程. 1. double factorial( int number ) 2. { 3. double result = 1.0; 4. for ( int i = number; i >= 1; i-- ) 5. result *= i; // result = result * i; 6. return result; 7. } 172

157 6.19 Recursion( 递归 ) 如何设计迭代程序 : 确定迭代变量 至少存在一个直接或间接地不断由旧值递推出新值的变量 建立迭代关系式 如何从变量的前一个值推出其下一个值的公式 ( 或关系 ) 对迭代过程进行控制 何时结束迭代过程 : 一种是所需的迭代次数是个确定的值, 构建一个固定次数的循环来控制迭代过程 另一种是所需的迭代次数无法确定, 需要分析出结束迭代过程的条件 173

158 Topics 6.11 Function Call Stack and Activation Records 6.12 Functions with Empty Parameter Lists 6.13 Inline Functions 6.14 References and Reference Parameters 6.15 Default Arguments 6.16 Unary Scope Resolution Operator 6.17 Function Overloading 6.18 Function Templates 6.19 Recursion 6.20 Example Using Recursion: Fibonacci Series 6.21 Recursion vs. Iteration 174

159 6.20 Fibonacci Series( 斐波那契数列 ) - 问题描述 Fibonacci Series 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,... 从数列第 3 项开始, 每一项等于前两项之和 意义 : 随着数列项数的增加, 前一项与后一项之比越来越逼近黄金分割的数值 (1.618) 0 (n=0) 定义 fibonacci(n)= 1 (n=1) fibonacci(n-1) + fibonacci(n-2) (n 2) 175

160 6.20 Fibonacci Series( 斐波那契数列 ) - 问题分析 基本情况 (base case) n = 0 时, 结果为 0 n = 1 时, 结果为 1 一般情况 (general case) 问题可分解为 fibonacci(n-1) + fibonacci(n-2) (n 2) 176

161 6.20 Fibonacci Series( 斐波那契数列 ) 递归设计 1. unsigned long fib( unsigned long n ) 2. { 3. if (n == 0) 4. return 0; 5. else if (n == 1) 6. return 1; 7. else 8. return fib( n - 2 ) + fib( n - 1 ); 9. } 177

162 6.20 Fibonacci Series( 斐波那契数列 ) 178

163 6.20 Fibonacci Series( 斐波那契数列 ) 迭代实现 1. int currentfib, n; 2. int f1 = 0, f2 = 1; 3. cin >> n; 4. for( int i= 2; i <= n; i++ ) 5. { 6. currentfib = f1 + f2; 7. f1 = f2; 8. f2 = currentfib; 9. } f1 f2 Fib f1 f2 Fib 注意 : 迭代变量 递推公式 迭代结束条件 179

164 Topics 6.11 Function Call Stack and Activation Records 6.12 Functions with Empty Parameter Lists 6.13 Inline Functions 6.14 References and Reference Parameters 6.15 Default Arguments 6.16 Unary Scope Resolution Operator 6.17 Function Overloading 6.18 Function Templates 6.19 Recursion 6.20 Example Using Recursion: Fibonacci Series 6.21 Recursion vs. Iteration 180

165 控制语句 选择结构 vs 循环结构 停止条件 base case vs loop-continuation condition 递归 : 当且仅当存在预期的收敛时, 才可采用递归算法 使用不当 栈溢出 vs 死循环 6.21 Recursion vs. Iteration 开销 活动记录, 函数调用栈 迭代通常发生在函数内, 无需调用函数 181

166 6.21 Recursion vs. Iteration 当递归算法描述问题更加直观 清晰 时, 建议采用递归! 182

167 Summary 理解程序模块的设计和构建 熟练使用 C++ 中与函数相关标准库函数 ( 例如相关数学库函数 输入输出函数 工具类的函数 字符串等 ) 熟练掌握随机数的生成 会使用枚举类型 掌握函数的定义 调用 ( 包括函数原型 强制参数类型转换 函数签名的使用 ) 理解形参和实参 理解函数相关的标识符的存储类别 作用域规则 理解函数调用栈和活动记录 理解内联函数 掌握按值调用和按引用调用功能 理解函数重载和函数模板 了解递归算法的基本概念和基本原理 183

168 Homework 实验必选题目 ( 交实验报告 ): 24, 29, 30, 32, 40, 41, 45 实验任选题目 ( 不交实验报告 ): 27, 35~37, 38, 39, 42 作业题目 (Homework): 6.16, 6.20, 6.53,

169 汉诺塔 (Hanoi tower) 问题 传说 (legend) 印度某间寺院有三根柱子, 上串 64 个金盘. 寺院里的僧侣依照一个古老的预言, 每次只能移动一个圆盘, 并且大盘不能叠在小盘上面. 预言说当这些盘子移动完毕, 世界就会灭亡. 这个传说叫做梵天寺之塔问题 (Tower of Brahma puzzle). 185

170 汉诺塔 (Hanoi tower) 问题 - 问题描述 有三根相邻的柱子, 标号为 A, B, C. A 柱子上从下到上按金字塔状叠放着 n 个不同大小的圆盘, 现在把所有盘子一个一个移动到柱子 C 上, 可以借助于 B 柱. 要求每次移动 : 任何一根柱子上都不能出现大盘子在小盘子上方, 请打印移动的步骤. A B C 186

171 汉诺塔 (Hanoi tower) 问题 - 问题分析 1 187

172 汉诺塔 (Hanoi tower) 问题 n 个盘子 基本情况 如果只有一个盘子, 则不需要利用 B, 直接将盘子从 A 移动到 C. 一般情况 将 n-1 个盘子从 A 移到 B( 借助 C) 把第 n 个盘子从 A 移到 C 再把 n-1 个盘子从 B 移到 C( 借助 A) 189

173 1. void towers( int, char, char, char ); // function prototype 2. int main() 3. { 4. int ndisks; 5. cout << "Enter the starting number of disks: "; 6. cin >> ndisks; 7. towers( ndisks, A, C, B ); 8. return 0; 9. } 10. void towers( int disks, char start, char end, char temp ) 11. { 12. if ( disks == 1 ) // base case 13. cout << start << " --> " << end << '\n'; 14. else { 15. towers( disks - 1, start, temp, end ); 16. // move last disk from start to end 17. cout << start << " --> " << end << '\n'; 18. // move (disks-1) disks from temp to end 19. towers( disks - 1, temp, end, start ); 20. } 21. } 190