C语言高级语言程序设计(一)PPT教学课件-第四章 程序设计方法-模块化与算法设计.ppt

外部变量* 外部变量（global variable ）：在函数外面定义的变量。 作用域（scope）为整个程序，即可在程序的所有函数中使用。 外部变量有隐含初值0。 生存期（life cycle）：外部变量（存储空间）在程序执行过程中始终存在。 外部变量说明（extern）* C程序可以分别放在几个文件上，每个文件可作为一个编译单位分别编译。外部变量只需在某个文件上定义一次，其它文件若要引用此变量时，应用extern加以说明。（外部变量定义时不必加extern关键字）。 在同一文件中，若前面的函数要引用后面定义的外部（在函数之外）变量时，也应在函数里加以extern说明。 外部变量说明（extern）（续）* 例如，对问题4.2的代码实现中，如果外部变量N不在程序头部定义，则需要用extern加以说明。 … extern int N; int main() { … } int N = 0; void insertData(int array[], int data) { … } 外部变量定义 外部变量说明 外部变量说明（extern）（续）* 使用外部变量的原因： 解决函数单独编译的协调； 与变量初始化有关； 外部变量的值是永久的； 解决数据共享； 外部变量的副作用： 使用外部变量的函数独立性差，通常不能使用在其他的程序中。而且，如果多个函数都使用到某个外部变量，一旦出现差错，就很难发现问题是由哪个函数引起的。在程序中的某个部分引起外部变量的错误，很容易误以为是由另一部分引起的。 递归（Recursion）* 通过调用自身解决问题的过程称为递归。递归是解决某些复杂问题的有效方法。如： 递归（续）* 例：求n! #include stdio.h int fact(int n); main( ) { printf(“3!=%d, 5!=%d\n”, fact(3), fact(5)); } int fact(int n) { int res=0; if( n = 1) res = 1; else res = n * fact(n-1)); return res; } 在C语言中，一个函数直接或间接调用自已称为递归。 1 fact(3) 3*fact(2) 2*fact(1) 2 6 1 递归（续）* 递归算法十分简洁，编译后得到的目标代码也很短，但它并不节省（实际上还要增加）运行时所需的时间和空间，因为它必须维持一个要处理的值的栈。 此外，递归算法并不是语言必须的，不用它同样可以实现相应功能，如上例中，递归函数fact可用非递归方法 实现： int fact(int n) { int f = 1; while(n){ f *= n; n--; } return ( f); } 例：汉诺塔(hanoi tower)游戏 void hanoi( int n, char a, char b, char c) { if( n 0 ) { hanoi(n-1, a, c, b); printf(“MOVE %d: %c ? %c\n”, n, a, c); hanoi(n-1, b, a, c); } } main( ) { int n; printf(“Please input the number of hanoi tower:”); scanf(“%d”, n); hanoi(n, ‘A’, ‘B’, ‘C’); } B A C 如果要移动64个盘子,则移动次数为264-1.如果每秒移动一个盘子,则需要约5*1011年.一般认为地球的寿命为50亿年(约5*109). 以每秒10亿次的移动速度计算,约需要500年. 问题4.3： 一个经典递归程序示例* 问题4.4：生成全排列数* 【问题描述】输入整数N( 1 = N = 10 )，生成从1~N所有整数的全排列。 【输入形式】输入整数N。【输出形式】输出有N!行，每行都是从1~N所有整数的一个全排列，各整数之间以空格分隔。各行上的全排列不重复。输出各行遵循“小数优先”原则, 在各全排列中，较小的数尽量靠前输出。如果将每行上的输出看成一个数字，则所有输出构成升序数列。具体格式见输出样例。【样例输入1】3? 【样例输出1】1 2 31 3 22 1 32 3 13 1 23 2 1【样例说明1】输入整数N=3，要求整数1、2、3的所有全排列, 共有N!=6行。且先输出1开头的所有排列数，再输出2开头的所有排列数，最后输出3开头的所有排列数。在以1开头的所有全排列中同样遵循此原则。【样例输入2】10 【样例输出2】1 2 3 4 5 6 7 8 9 101 2 3 4