信息学奥林匹克竞赛C语言课程胶片5-定向原创V10

1、C语言Part 5 for NOI1. 高级函数2. 指针 在调用一个函数的过程中又出现直接或间接地调在调用一个函数的过程中又出现直接或间接地调用该函数本身，称为函数的递归调用。语言的用该函数本身，称为函数的递归调用。语言的特点之一就在于允许函数的递归调用。特点之一就在于允许函数的递归调用。函数的递归调用 要求使用递归和递推两种方法 递推方法 递归方法例8.5 求n!) 1()!1() 1 , 0(1)(fnnnnn#include int main() long fac(int n); int n, y; printf(Please input an integer number:n); s

2、canf(%d, &n); y = fac(n); printf(%d!=%ldn, n, y); n = 0; if(n = 0, n = 1) /整个逗号表达式的值为最右边表达式的值 printf(comma expression, true for n=1. n=%d, n); else printf(comma expression, false for n=1. n=%d, n); return 0;long fac(int n) long f; if(n 0) printf(n 0, data error!); else if(n = 0, n = 1) /最好写为n =

3、0 | n = 1 f = 1; else f = fac(n - 1) * n; return (f);例8.5 递归代码fac(5)fac(4)*5fac(3)*4fac(2)*3fac(1)*2n=5(未知)n=4(未知)n=3(未知)n=2(未知)1n=1(边界)main(未知)已知已知已知已知已知#include int main() long fac(int n); int n, y; printf(Please input an integer number:n); scanf(%d, &n); y = fac(n); printf(%d!=%ldn, n, y); re

4、turn 0;long fac(int n) long f = 1; for(int i = 1; i = n; i+) f = f * i; return (f);例8.5 递推方法 Hanoi（汉诺）塔问题。这是一个古典的数学问题，是一个用递归方法解题的典型例子。问题是这样的：古代有一个梵塔，塔内有3个座A、B、C，开始时座上有个盘子，盘子大小不等，大的在下，小的在上。有一个老和尚想把这个盘子从座移到座，但每次只允许移动一个盘，且在移动过程中在3个座上都始终保持大盘在下，小盘在上。在移动过程中可以利用座，要求编程序打印出移动的步骤。例8.6汉诺塔问题例8.6为便于理解，我们先分析将座上个盘

5、子移到座上的过程：(1) 将座上个盘子移到座上（借助）；(2) 将座上个盘子移到座上；(3) 将座上个盘子移到座上（借助）。其中第()步可以直接实现。第步又可用递归方法分解为：1.1将上个盘子从移到；1.2将上个盘子从移到；1.3 将上个盘子从移到。第()步可以分解为：3.1将上个盘子从移到上；3.2将上个盘子从移到上；3.3将上个盘子从移到上。例8.6将以上综合起来，可得到移动3个盘子的步骤为，。由上面的分析可知：将个盘子从座移到座可以分解为以下3个步骤：(1) 将上个盘借助座先移到座上。(2) 把座上剩下的一个盘移到座上。(3) 将个盘从座借助于座移到座上。#include int mai

6、n() void hanoi(int n, char one, char two, char three); /* 对hanoi函数的声明 */ int m; printf(“Input the number of disks:); scanf(%d, &m); printf(The step to moving %d disks:n,m); hanoi(m, A, B, C); return 0;void hanoi(int n, char one, char two, char three) /* 定义hanoi函数,将个盘从one座借助two座，移到three座 */ void

7、move(char x,char y); /* 对move函数的声明 */ if(n=1) move(one,three); else hanoi(n-1,one,three,two); move(one,three); hanoi(n-1,two,one,three); void move(char x, char y) /* 定义move函数 */ printf(%c-%cn, x, y);例8.6 源代码Input the number of disks:3The step to moving 3 disks:A-CA-BC-BA-CB-AB-CA-C 也是单向传递 也是值传送方式 数组

8、元素只能作为函数实参，不能作为形参使用数组元素作为函数实参 有两只运动队a和b，各有10个队员，每个队员有一个综合成绩。将两个队的每个队员的成绩按顺序一一对应地逐个比较（即a对第一个队员和b队第一个队员比较，）。如果a队队员成绩高于b队队员成绩的数目多余b队队员成绩高于a队队员成绩的数目（例如：a队赢6次，b队赢4次），则认为a队胜。统计出两队队员比较的结果（a队高于、等于和低于b队的次数）例8.7统计两支运动队的成绩#include int main() int higher(int, int); int a10, b10, i, n = 0, m = 0, k = 0; printf(En

9、ter the array a team:n); for(i = 0; i 10; i+) scanf(%d, &ai); printf(n); printf(Enter the array b team:n); for(i = 0; i 10; i+) scanf(%d, &bi); printf(n); for(i = 0; i k) printf(a team wins!n); else if(n y) flag = 1; else if(x y) flag = -1; else flag = 0; return (flag);例8.7例8.8 有10个学生成绩，用一个函

10、数求全体学生的平均成绩#include int main() float average(float); float scores10, avg; int i; printf(Input 10 scores:n); for(i = 0; i 10; i+) scanf(%f, &scoresi); avg = average(scores); printf(Average score is %5.2f:n, avg); return 0;float average(float array10) int i; float avg, sum = array0; for(i = 0; i 1

11、0; i+) sum += arrayi; avg = sum / 10; return (avg);用数组名作为函数参数Input 10 scores:89 98 77 38 67 66 56 89 99 100Average score is 86.80:调用函数时array并不新分配内存空间，实际传送的是数组首地址。本质上也是单向传送地址的值。#include int main() void sort(int, int); int array10, i; printf(Enter the array:n); for(i=0; i10; i+) scanf(%d, &arrayi)

12、; sort(array, 10); printf(The sorted array:n); for(i=0; i10; i+) printf(%d , arrayi); return 0;void sort(int array, int n) int i, j, k, t; for(i=0; in; i+) k = i; for(j=i+1; jn; j+) if(arrayj arrayk) k=j; /把当前最小元素的序号j保存在k中 t = arrayk; arrayk = arrayi; arrayi = t;/将最小元素和第i个元素对换 例8.9 用一个函数实现10个数的升序排序，

13、采用选择排序方法所谓选择法就是先将所谓选择法就是先将10个数中最小的数与个数中最小的数与a0对换对换;再将再将a1到到a9中最小的数与中最小的数与a1对换对换每比较一轮每比较一轮,找出一个未经排序的数中最找出一个未经排序的数中最小的一个。共比较小的一个。共比较9轮。轮。Enter the array:5 7 -3 21 -43 67 321 33 51 0The sorted array:-43 -3 0 5 7 21 33 51 67 321#include int main() float highest_score(float 5); /第二个中括号中必须写长度 float scores

14、45 = 61,73,85.5,87,90, 72,84,66,88,78, 75,87,93.5,81,96, 65,85,64,76,71; printf(The highest score is %6.2f.n, highest_score(scores); return 0;float highest_score(float scores5) int i, j; float max; max = scores00; for(i=0;i4;i+) for(j=0;jmax) max=scoresij; return (max);例8.10 利用多维数组模拟：四个学生五门课程，并设计一个函

15、数，求其中的最高成绩。 内部变量或者局部变量 函数或者复合语句内定义的变量 形参也是局部变量 全局变量或者外部变量 函数之外定义的变量 从定义变量的位置开始到本源程序文件结束变量的作用域#include int StudentNo, CourseNo;int main() float highest_score(float 5); /第二个中括号中必须写长度 float scores45 = 61,73,85.5,87,90, 72,84,66,88,78, 75,87,93.5,81,96, 65,85,64,76,71; printf(The highest score is %6.2f.

16、n, highest_score(scores); printf(Student no. is %d.n, StudentNo); printf(Course no. is %d.n, CourseNo); return 0;float highest_score(float scores5) int i, j; float max; max = scores00; for(i=0;i4;i+) for(j=0;jmax) max=scoresij; StudentNo = i; CourseNo = j; return (max);例8.11 在8.10基础上输出最高成绩所述学生和课程只有在

17、逼不得已的情况下使用全局变量，因为：1.全称占用内存，2.使函数具有弱通用性，3.降低可读性 变量的存在时间 有的变量存在于程序的整个运行过程 有的变量存在于函数被调用期间 生存期和存储方式是一个事物的两面 存储方式有两种： 静态存储方式 动态存储方式变量的生存期 静态存储方式 在程序运行期间由系统在静态存储区分配存储空间，在程序运行期间不释放 动态存储方式 在函数调用期间根据需要在动态存储区分配存储空间 全局变量 采用静态存储方式 每个变量和函数都有两个属性 数据类型 数据的存储类别auto，static，register，extern变量的存储方式（变量的可见性） auto int b,

18、c=3; Auto关键词，可以省略 函数中大多数变量属于自动变量自动变量 静态局部变量 在函数中声明静态变量，实现：在函数调用结束后变量的值还继续保留原值静态变量#include int main() int fac(int); int i, n; printf(Please input an integer number:n); scanf(%d, &n); for(i=1; i=n; i+) printf(%d!=%dn, i, fac(i); return 0;int fac(int n) static int f = 1; f=f*n; return (f);例8.12 阶乘n

19、！，要求在函数中使用静态局部变量F保留了上次调用结束时的值此句表示在上次的f值基础上乘以nPlease input an integer number:51!=12!=23!=64!=245!=120 C语言允许把局部变量放在CPU的寄存器中 优化程序执行效率：如果变量执行次数频繁，那么应把局部变量改为寄存器变量 register int f; 现代编译器能够自动优化，所以一般不手工使用register 寄存器变量 extern A; 在一个文件内扩展外部变量的作用域 将外部变量的作用域扩展到其他文件外部变量的可见性变量的存储类变量的存储类别别函数内作用域函数内作用域函数内存在性函数内存在性函

20、数外作用域函数外作用域函数外存在性函数外存在性自动变量寄存器变量静态局部变量静态全局变量（仅限本文件）外部变量作用域和生存期汇总 内部函数，又称静态函数 只能在本文件中被其他函数调用 格式：static 类型标识符 函数名(形参表); 外部函数 可被其他文件的函数调用 格式：extern 类型标识符 函数名(形参表); 定义函数时可省略extern 声明函数时使用extern表示所调用的函数在其他文件中内部函数和外部函数例8.13 有一个字符串，内含若干字符，现输入一个字符，如果字符串中含有此字符，则把此字符从字符串中删除。要求使用外部函数实现。This is a c program.cThi

21、s is a program.#include int main() extern void enter_strng(char str); extern void delete_string(char str, char ch); extern void print_string(char str); char c; char str80; enter_string(str); scanf(%c, &c); delete_string(str, c); print_string(str); return 0;Main.c#include void enter_string(char s

22、tr) gets(str);enter.c#include void delete_string(char str, char ch) int i, j; for(i=j=0; stri!=0; i+) if(stri!=ch) strj+=stri; strj = 0;#include void print_string(char str) printf(%sn, str);print.cdelete.c 有的编译器从左到右顺序求实参的值 有的编译器从右到左顺序求实参的值 例8.14 求证所用编译器实参求值顺序 int i = 0, j = 0; printf(%d,%dn, j=i, +i

23、); if(j = 0) printf(实参求值顺序：从左到右n); else printf(实参求值顺序：从右到左n);实参求值的顺序1. 高级函数2. 指针 指针是指向变量的内存单元的地址 编译器给变量分配的内存单元的每个字节都有一个编号 直接访问 直接按变量名对变量内存单元进行访问 间接访问 通过指针变量对变量内存单元进行访问 指针变量是特殊变量，用于存放地址 指针变量的值是地址什么是指针 int a = 100, b = 10; int *ptr1, *ptr2; ptr1 = &a; ptr2 = &b; printf(a=%d, b=%dn, a, b); prin

24、tf(*ptr1=%d, *ptr2=%dn, *ptr1, *ptr2); printf(ptr1=0 x%X, ptr2=0 x%Xn, ptr1, ptr2); printf(ptr1=0%o, ptr2=0%on, ptr1, ptr2); printf(&ptr1=0 x%x, &ptr2=0 x%xn, &ptr1, &ptr2);例9.1通过指针变量访问整型变量数字0作为前缀表示八进制数字0 x作为前缀表示十六进制a=100, b=10*ptr1=100, *ptr2=10ptr1=0 x22FF1C, ptr2=0 x22FF18ptr1=010

25、577434, ptr2=010577430&ptr1=0 x22ff14, &ptr2=0 x22ff100 x22FF1C100ptr1a(*ptr1)指针变量的值每次运行都不一样变量内存单元十六进制，16位。如果是64位CPU，应该是多少位的地址int i, j, k, *i_pointer;基类型 *指针变量名 int *pointer_1, *pointer_2;基类型 基类型用来规定指针变量可以指向的变量的类型 基类型指数据类型，每个数据类型在内存占用的长度不同 方便进行指针操作：指针移动、指针加减运算指针运算符*，或者称为“间接访问”运算符, 表示指针变量取地址运

26、算符&不允许不同基类型的指针指向不同数据类型的变量 float a = 1.1; int *ptr1 = &a; /这句是错误的不允许指针变量被赋值为一个整数 int *ptr1; ptr1 = 100; /这句是错误的指针变量的定义 给指针变量赋值 int a = 10, *ptr = &a; /合法 Int a = 10, *ptr; ptr = &a; /合法 int *ptr = 100;/非法 int *ptr; ptr = NULL; /合法，NULL在stdio.h中定义#define NULL 0 int *ptr;/合法，但没有赋初值的指针有无

27、法预料的值 引用指针变量指向的变量 int *ptr; *ptr = 100; /合法 printf(“%d”, *p); /合法 引用指针变量的值 printf(“0%o”, ptr); /合法指针变量的引用 int *ptr1, *ptr2, *ptr, a, b; scanf(%d,%d, &a, &b); ptr1 = &a; ptr2 = &b; if (a b) ptr = ptr1; ptr1 = ptr2; ptr2 = ptr; /使两个指针互换 printf(a=%d, b=%dn, a, b); printf(max=%d, min=%dn

28、, *ptr1, *ptr2);例9.2 输入两个整数，按先大后小的顺序输出。方法1：直接互换指针#include int main() void swap(int*, int*); int *ptr1, *ptr2, a, b; scanf(%d,%d, &a, &b); ptr1 = &a; ptr2 = &b; if (a b) swap(ptr1, ptr2); /调用函数swap printf(a=%d, b=%dn, a, b); printf(max=%d, min=%dn, *ptr1, *ptr2); return 0;void swap(in

29、t *p1, int *p2) int temp; temp = *p1; /交换值，而不是交换指针 *p1 = *p2; *p2 = temp;例9.2 方法2：指针变量作为函数参数调用结束后形参p1和p2是否还存在？此处换为int *temp; *temp = *p1; *p1=*p2; *p2 = *temp;是错误的，为什么？swap换为如下代码是错误的，为什么？void swap(int x, int y) int temp; temp = x; x = y; y = temp;swap换为如下代码是错误的，为什么？void swap(int *p1, int *p2) int *p

30、; p = p1; p1 = p2; p2 = p; 数组元素的指针就是数组元素的地址 可用一个指针变量指向一个数组元素 引用数组元素除了下标法之外，还可使用指针法 int a10; printf(“%d”, a2); int a10; printf(“%d”, *(a + 2); 数组名代表数组的首元素的地址，以下语句等价： int a10, *p; p = &a0; Int a10, *p; p = a;数组元素的指针#include int main() void print1(int); void print2(int); void print3(int*); void pri

31、nt4(int); int i, a10, *p = a; for(i=0; i10; i+) scanf(%d, &ai); print1(a); print2(p); print3(a); print4(p); return 0;void print1(int array10) for(int i=0; i10; i+) printf(%d , arrayi); /下标法 printf(n);void print2(int array10) for(int i=0; i10; i+) printf(%d , *(array + i);/对数组名采用指针法 printf(n);voi

32、d print3(int *p) for(int i=0; i10; i+) printf(%d , *(p + i);/指针法 printf(n);void print4(int array10) for(int *p = array; p (array + 10); p+)/对指针变量做加操作 printf(%d , *p);/指针法 printf(n);例9.3 有一个数组存放10学生的年龄，使用下标法和指针法输出数组的所有元素。指针的加运算：不是直接在值上加i，而是加（i*数据类型的存储长度） ，和数组元素下标吻合此句改为如下是错误的，为什么？for(int *p = array; a

33、rray (p + 10); array+)思考：指针的减运算和加运算有什么不同？两个指针是否可以相减？两个指针是否可以比较实参和形参都可以从数组名、指针变量选其一#include int main() int a10, *p = a; for(int i=0; i10; i+) scanf(%d, p+); for(int i=0; i10; i+, p+) printf(%d , *p); printf(n); return 0;例9.3 错在哪里？for(int i=0, p=a; i10; i+, p+)void sort(int array, int n) int i, j, k,

34、t; for(i=0; in; i+) k = i; for(j=i+1; jn; j+) if(arrayj arrayk) k=j; /把当前最小元素的序号j保存在k中 t = arrayk; arrayk = arrayi; arrayi = t;/将最小元素和第i个元素对换 例9.4 改造选择法排序函数。要求参数改为指针，数组元素访问方法采用指针法#include int main() char *string = I love China!; printf(%sn, string); return 0;例9.5通过字符指针引用字符串不能称为字符串变量此句能否拆分为以下两句？char

35、*string;*string = “I love China!”;#include #include int main() char a100; printf(Please input a string:n); gets(a); char b100; strcpy(b, a); printf(%sn, b); return 0;例9.6 要求输入一个字符串，复制后原样输出。方法1：引用库函数#include int main() char a100; puts(Please input a string:); gets(a); char b100; int i = 0; for (; *(a

36、+i)!=0; i+) *(b+i) = *(a+i); *(b+i)=0; puts(b); return 0;例9.6 要求输入一个字符串，复制后原样输出。方法2：使用数组名地址法重写复制语句#include int main() char a100; puts(Please input a string:); gets(a); char b100; int i = 0; char *ptr1 = a, *ptr2 = b; for (; *(ptr1+i)!=0; i+) *(ptr2+i) = *(ptr1+i); *(ptr2+i)=0; puts(ptr2); return 0;例

37、9.6 要求输入一个字符串，复制后原样输出。方法3：使用指针变量重写复制语句字符数组b是否可以删除？#include int main() void mystrcpy(char*, const char*); char a100; puts(Please input a string:); gets(a); char b100, *ptr = b; mystrcpy(ptr, a); puts(ptr); return 0;void mystrcpy(char *p_dest, const char *p_source) for (; *p_source!=0; p_source+, p_de

38、st+) *p_dest = *p_source; *p_dest=0;例9.6 要求输入一个字符串，复制后原样输出。方法4：使用字符指针重写复制函数 while(*p_dest=*p_source)!=0) p_dest+; p_source+; while(*p_dest+=*p_source+)!=0); while(*p_source!=0) *p_dest+=*p_source+; *p_dest=0; while(*p_source) *p_dest+=*p_source+; *p_dest=0; while(*p_dest+=*p_source+); for(;*p_dest+=

39、*p_source+;);#include int main() char* mystrcat(char*, char*); char a100; puts(Please input first string:); gets(a); char b100; puts(Please input second string:); gets(b); mystrcat(a, b); puts(a); return 0;char *mystrcat(char *dest, char *src) int i; for(i=0; *dest!=0; i+) dest+; for(;*src!=0;dest+,

40、 src+) *dest = *src; *dest = 0; return dest;例9.7重写库函数strcat字符数组存放字符元素，而字符指针存放地址初始化char str14=“I love China”; /rightchar *ptr = “I love China”; /right赋值char str14; str=“I love China”; /errorchar str14; str=“I love China”; /errorchar *ptr; ptr = “I love China”; /right野指针没有初始化的指针，或者指向不存在的内存单元，或者指向无法管理的内存单元字符指针的值可以改变，而字符数组名是常量地址，不能改变字符指针和字符数组均可以使用下标法引用char *ptr=“china”; printf(“%c”, ptr3);字符数组的元素值能被修改，但是字