第6章过程封装--函数

第6章过程封装--函数内容摘要：

存储类型  在 C++语言中，每个变量有两个属性： 类型：变量所存储的数据类型 存储类型：变量所存储的区域：  标准的变量定义： 存储类型 数据类型 变量名；  存储类型： 自动变量： auto 寄存器变量： register 外部变量： extern 静态变量： static 《 程序设计 》 程序设计 52 auto  在函数内或块内定义的变量缺省时是auto。 如 auto int i；  当进入块时，系统为自动变量分配空间。 当退出块时，系统释放分配给自动变量的值。 因此自动变量的值就消失了。 当再次进入该块时，系统重新分配空间。 《 程序设计 》 程序设计 53 register  存储在寄存器中，代替自动变量或形参，可以提高变量的访问速度。  如无合适的寄存器可用，则编译器把它设为自动变量。 《 程序设计 》 程序设计 54 extern  声明一个不在本模块作用范围内的全局变量。 如： extern int num。 num为一个的全局变量。  用途：  在某函数中引用了一个声明在本函数后的全局变量时，需要在函数内用 extern声明此全局变量。  当一个程序有多个源文件组成时，用 extern可引用另一文件中的全局变量。 《 程序设计 》 程序设计 55 // include iostream using namespace std。 void f()。 extern int x。 //外部变量的声明 int main() { f()。 cout in main(): x= “ x endl。 return 0。 } // include iostream using namespace std。 int x。 //全局变量的定义 void f() { cout in f(): x= “ x endl。 } 《 程序设计 》 程序设计 56 static  为在整个程序的运行期间都存在的变量限定访问范围。  两类静态变量： 静态的局部变量 静态的外部变量 《 程序设计 》 程序设计 57 静态的局部变量  允许局部变量保存它的原有值，以便在次进入块时还可以使用此值。 eg. int f(int a) { int b=0。 static int c=3。 b=b+1。 c=c+1。 return(a+b+c)。 } void main() {int a=2,i。 for (i=0。 i3。 ++i) cout f(a)。 } 运行结果为：7 8 9 《 程序设计 》 程序设计 58 静态的外部变量  用 static说明的全局变量其他源文件不能用 extern引用它  用 extern还可以用在函数定义或说明中。 该函数只能被用于本源文件中，其他源文件不能调用此函数。 《 程序设计 》 程序设计 59 静态变量的使用  未被程序员初始化的静态变量都由系统初始化为 0。  局部静态变量的初值是编译时赋的。 当运行时重复调用此函数时，不重复赋初值。  虽然局部静态变量在函数调用结束后仍然存在，但其他函数不能引用它。 《 程序设计 》 程序设计 60 void a()。 void b()。 void c()。 void d()。 main() { int x=6。 cout ―x in main is ― x endl。 a()。 b()。 c()。 d(x)。 x++。 a()。 b()。 c()。 d(x)。 cout ―x in main is ‖ x endl。 } void a() {int x=25。 cout ―x in a is ‖ x endl。 } void b() {static int x=50。 cout ―x in b is ‖ x++ endl。 } void c() { extern int x。 x*=10。 cout ―x in c is ‖ x endl。 } int x=2。 void d(int x) { cout ―x in d is ‖ ++x endl。 } 结果： x in main is 6 x in a is 25 x in b is 50 x in c is 20 x in d is 7 x in a is 25 x in b is 51 x in c 200 x in d is 8 x in main is 7 《 程序设计 》 程序设计 61 第 6章 过程封装－－函数  函数  自己编写函数  函数的使用  数组作为参数  带默认值的函数  内联函数  重载函数  函数模版  变量的作用域  变量的存储类别  递归函数  基于递归的算法 《 程序设计 》 程序设计 62 递归用途  递归程序设计：将一个大问题简化为 同样形式 的较小问题。 在一个递归求解中，分解的子问题与最初的问题具有一样的形式 作为处理问题的工具，递归技术是一种非常有力的工具。 利用递归不但可以使得书写复杂度降低，而且使程序看上去更加美观  递归调用：在一个函数中直接或间接地调用函数本身 《 程序设计 》 程序设计 63 递归条件  必须有递归终止的条件  函数有与递归终止条件相关的参数  在递归过程中，决定终止条件的参数有规略地递增或递减 《 程序设计 》 程序设计 64 递归的 标准模式  有可对函数的入口进行 测试的基本情况 if (条件 ) return (不需要递归的简单答案 )。 else return (递归调用同一函数 )； 基本情况 《 程序设计 》 程序设计 65 典型的递归函数 —阶乘函数 n!=1*2*3*4*…*(n 1)*n (n1)! 递归形式： 其他)!1(*01!nnnn递归终止条件 long p(int n) {if (n == 0) return 1。 else return n * p(n1)。 } 《 程序设计 》 程序设计 66 简单应用 ——求 n的 k次幂 int RaiseIntToPower(int n, int k) { if (k == 0) { return(1)。 } else { return( n * RaiseIntToPower( n, k 1))。 } } 《 程序设计 》 程序设计 67 Fibonacci函数 0 0 1 1 2 1 3 2 4 3 5 5 6 8 其他)2()1(1100)(nFnFnnnFint f(int n) {if (n==0) return 0。 elseif (n==1) return 1。 else return (f(n1)+f(n2))。 } 《 程序设计 》 程序设计 68 理解递归  问题：求解 n! 可以用循环的方法 ， 即从 1开始 ， 乘 2， 再乘 3… ..一直乘到 n。 这种方法容易理解 ， 也容易实现 由于 n! = n (n1)! 数学里定义 0。 ＝ 1，从而 n!可以用下面的递归公式表示： )1()!1()1,0(1{!nnnnn《 程序设计 》 程序设计 69 递归函数设计 int p(int n) { if(n= = 0) return (1)。 else return (n * p(n1))。 } 《 程序设计 》 程序设计 70 递归执行的过程 求 p(4) 1)0(*1)1(*2)2(*3)3(*4)4(ppppp递归过程 回溯 《 程序设计 》 程序设计 71 递归与迭代的选择  对于大多数常用的递归都有简单、等价的迭代程序。 究竟使用哪一种，凭你的经验选择。  迭代程序复杂，但效率高。  递归程序逻辑清晰，但往往效率较低。 《 程序设计 》 程序设计 72 Fibonacci函数的递归实现 int f(int n) {if (n==0) return 0。 elseif (n==1) return 1。 else return (f(n1)+f(n2))。 }  实现效率分析：消费的时间是灾难性的。 《 程序设计 》 程序设计 73 Fibonacci函数的迭代实现 int f(int n) { int i, fn, fn_1 = 0, fn_2 = 1。 if (n == 0) return 0。 if (n == 1) return 1。 for ( i = 2。 i=n。 ++i) { fn = fn_1 + fn_2。 fn_2 = fn_1。 fn_1 = fn。 } return fn。 } 消耗的时间：执行 n次加法和 3n次赋值。 《 程序设计 》 程序设计 74 系统考虑 对递归函数的每次调用都需要内存空间。 由于很多调用的活动都是同时进行的，操作系统可能会耗尽可用的内存 ,避免在处理过大的 n时产生溢出问题。 《 程序设计 》 程序设计 75 递归过程 数字旋转方阵（蛇阵）  数字旋转方阵如右图所示。 编程输出任意 N*N的蛇阵。 1 20 19 18 17 16 2 21 32 31 30 15 3 22 33 36 29 14 4 23 34 35 28 13 5 24 25 26 27 12 6 7 8 9 10 11 《 程序设计 》 程序设计 76 用递归的观点看问题  先填最外圈，然后再填内部内部的填法同上。 也是先填最外圈，再填内部。  根据上述思想，可以设计一个递归函数 fill。 该函数先填外圈，然后递归调用自己填内部。  函数原型： void fill(int number, int begin, int size) number：表示要填入的起始数据 begin：表示要填的起始位置 size：蛇阵的规模  要生成一个 6*6的蛇阵只要调用： fill(1,0,6) 《 程序设计 》 程序设计 77 Main函数 int p[20][20]。 void fill(int, int,int)。 int main() { int row, col, size。 cout 请输入蛇阵的规模：。 cin size。 fill(1,0,size)。 for (row = 0。 row size。 ++row) { cout endl。 for (col = 0。 col size。 ++col) cout p[row][col] 39。 \t39。