数据结构函数

1、l函数概述l函数定义的一般形式l函数的调用、参数和返回值l局部变量和全局变量l变量的存储类型l内部函数和外部函数lC语言用函数实现程序模块化l一个程序由一个或多个源程序文件组成l一个源程序文件由一个或多个函数组成lC程序的执行从main函数开始，并回到main函数结束l函数之间可以相互调用，或调用自身l不能调用main函数l函数之间相互独立，不存在从属关系l函数定义形式n返回类型 函数名(参数声明) 声明部分 语句l返回类型、参数、函数体内容都可没有ndummy()/* does nothing & returns nothing */l关于“返回类型”n指函数返回值的类型n若省略此项

2、，则认为返回类型是intn若无返回值，则定义返回类型为voidl关于“参数声明”n类型 形参名, 类型 形参名, .l关于“声明部分”n指变量、函数的声明int max(int x, int y)int z;z = xy?x:y;return z;int min(int x, int y)return xy?x:y; nmax(a, 3); /*函数调用*/l值传递n实参对形参的数据传递是“值传递”l单向传递n只能把实参的值传递给形参n不能把形参的值传递给实参n对形参的值所作的改变不能带回给实参l实参和形参是不同的变量n具有不同的存储空间n具有不同的生存期和作用域void swap(int x

3、, int y)int t;t=x, x=y, y=t;void main()int a=1, b=4;swap(a, b);1a4b1x4y41l形式n形式一：return;n形式二：return expression;l功能n函数返回语句n结束函数调用n如果需要，还可以带回函数返回值l返回值的说明n函数返回值的类型在函数定义中指定n函数返回值通过函数中的return语句获得n若函数无返回值，则可以没有return语句nreturn语句后的表达式类型，应与函数返回值类型相同，或可以兼容赋值；两者类型不同时，自动做类型转换n函数需要返回值时，若缺少return语句，或return语句未带返回值

4、，则返回一个不确定值l一般形式n函数名(实参表列)l说明n即使没有实参，()也不能省略n多个实参之间用逗号分隔n实参与形参按顺序一一对应，类型应匹配n实参的求值顺序不确定，应避免对此敏感的调用形式printf(%d,%d, i, i+);l函数语句nprintf(%dn, i);l函数表达式n(c + d * max(a,b) % el函数参数ngcd(max(a,b), min(c, d)l说明n函数调用可以看作同返回类型的表达式使用n同时，函数调用还完成了函数中定义的操作l一般形式n类型 函数名(类型1, 类型2, .);n类型 函数名(类型1 形参1, 类型2 形参2, .);l举例ni

5、nt max(int, int);nint max(int x, int y);nvoid dummy(); /* 无参函数原型 */nvoid dummy(void); /* 同上 */l函数声明的形式即函数原型l在函数调用之前，应对函数进行声明l函数声明可以在主调函数的声明部分，也可以在函数外部l函数外部的声明，对所有主调函数都起作用，不需要在主调函数内再次声明l函数的定义也具有声明的作用l库函数的声明包括在头文件(*.h)里，不需在源程序里声明void main()int max(int x, int y); /* 函数声明 */int a, b, c;c = max(a, b);int

6、 max(int x, int y)return xy?x:y;int max(int x, int y); /* 函数声明 */void main()/* 不需要再次声明int max(int, int) */int a, b, c; c = max(a, b);int max(int x, int y)return xy?x:y;int max(int x, int y)/* 函数定义具有声明作用 */return xy?x:y;void main()/* 不需要再次声明int max(int, int) */int a, b, c;c = max(a, b);l调用一个函数的过程中，调用

7、另一函数main函数函数结束结束调用调用a函数函数b函数函数a函数函数调用调用b函数函数l一个函数直接或间接的调用它自身l必须有一定的条件判断语句，使得递归调用能够终止f函数函数调用调用f函数函数f1函数函数调用调用f2函数函数f2函数函数调用调用f1函数函数lHanoi塔 (汉诺塔、河内塔、梵塔)汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。上帝创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上安大小顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。l解法nN=1时，H

8、anoi(1)易解n若Hanoi(N-1)可解，则Hanoi(N)易解Step1. N-1个盘子，借助3，从1移至2Step2. 把最大的盘子从1移至3Step3. N-1个盘子，借助1，从2移至3l复杂度n移动次数：2N-1nN=64，移动次数1.84467E+19l作用域n变量有效的代码空间n变量在作用域才能被引用n变量可以分为局部变量和全局变量l生存期n变量有效的运行时间n变量在生存期内才存在n变量可以分为静态存储和动态存储l局部变量n函数或复合语句内部定义的变量l说明n作用域为本函数或复合语句范围n不同函数内的局部变量可以重名，它们是不同的变量，作用域不同，不会相互干扰n函数形参也是局

9、部变量的一种n若多个同名局部变量作用域重叠，则最内层复合语句中定义的局部变量有效 float foo(int x) int a, i, j; /* 局部变量 */ . . /* 只能用在foo内部 */ void main() int a, b, c; /* 局部变量 */ . . /* 只能用在main内部 */ x,a,i,j作用域a,b,c作用域void main() int a, b, i; . . int c, i; c = a + b; i = a - b; . . . .a,b,i作用域c,i作用域此范围内复合语句中定义的i有效l全局变量(外部变量)n函数之外定义的变量l说明n作

10、用域从变量定义处到本源程序文件结束n全局变量可以被本文件的函数所共用n增加函数间传递数据的渠道n若全局变量与局部变量重名，则局部变量在作用域内屏蔽全局变量n应限制使用过多全局变量int a=10, b=5, x, y; /* 全局变量 */int max(int x, int y) return xy?x:y;int c; /* 全局变量 */void main() int a=8; c=max(a, b); /* 引用局部变量a */全局变量c作用域全局变量a,b,x,y作用域形参x,y作用域局部变量a作用域l动态存储方式n程序运行期间根据需要动态分配存储空间n函数形参、自动变量等n每次调用

11、函数时，给该函数中的局部变量和形参分配存储空间，函数返回后释放空间l静态存储方式n程序运行期间分配固定的存储空间n全局变量全部存放在静态存储区中l自动变量autol寄存器变量registerl静态变量staticl外部变量externlauto变量n局部变量，用auto关键字修饰nauto可以省略，是缺省的存储方式n自动分配和释放存储空间l举例int foo(int x) auto int a, b, c=6; /* 定义自动变量a,b,c */ float f, g=0.1;/* 定义自动变量f,g */lregister变量n存放在CPU寄存器中，存取速度快n寄存器变量只能动态分配存储空间

12、(寄存器)n只有自动变量和形参可以作为寄存器变量l举例int foo(int x) register int i;/* 定义寄存器变量i */ for(i=0; i10000; i+). /* i用于循环变量 */l静态局部变量n局部变量，用static关键字修饰n静态局部变量为静态存储，整个程序运行期间都不释放，其值不会丢失n在函数调用结束后，静态局部变量虽仍然存在，但已经不在变量的作用域内，所以其他函数不能引用它n静态局部变量在编译时赋初值，且只赋一次n若不对静态局部变量赋初值，则初值为0int f(int a) int b=0; static int c=3; b+; c+; retur

13、n a+b+c;void main() int x=2, i; for(i=0;iy?x:y;void main() extern A, B;/* extern声明外部变量 */ printf(%d, max(A, B); /* 在定义之前使用外部变量 */int A=13, B=-8; /* 定义外部变量 */* file1.c */* 声明外部变量 */extern A, B;void main() int c; c=max(A, B); printf(%d, c);/* file2.c */* 定义外部变量 */int A=13, B=-8;int max(int x, int y) i

14、nt z; z=xy?x:y; return z;l静态外部变量n限制外部变量只能被本文件引用n静态外部变量不能被其他文件引用l举例/* file1.c */static int A;main() . ./* file2.c */extern int A;void foo(int n) A = A * n;不能引用静态外部变量Al声明 (Declaration)n对变量的某些属性加以说明l定义 (Definition)n定义一个新的变量，并分配存储空间n定义有声明的功能，但声明不一定都是定义l举例void main() extern A; /* 声明而非定义，声明A为已定义外部变量 */ .

15、.int A; /* 定义A为整型外部变量 */l局部变量n自动变量(离开函数，值就消失)n寄存器变量(离开函数，值就消失)n形式参数(可为自动或寄存器变量)n静态局部变量(离开函数，值仍保留)l全局变量n静态外部变量(只限本文件引用)n非静态外部变量(允许其他文件引用)l动态存储n自动变量(本函数内有效)n寄存器变量(本函数内有效)n形式参数(本函数内有效)l静态存储n静态局部变量(本函数内有效)n静态外部变量(本文件内有效)n非静态外部变量(其他文件可以引用)l内存动态存储区n自动变量n形式参数l内存静态存储区n静态局部变量n静态外部变量(本文件内有效)n非静态外部变量(其他文件可以引用)lCPU中的寄存器n寄存器变量变量存储类型函数内函数外作用域生存期作用域生存期自动变量 形式参数寄存器变量静态局部变量静态外部变量非静态外部变量只限本文件其他文件也可以引用l定义形式nstatic 类型 函数名(形参表)l说明n内部函数又称静态函数n内部函数只能在所在文件中使用n类似于静态外部变量的作用范围l举例nstatic int foo(int a, int b);l定义形式nextern 类型 函数名(形参表)l说明n可