第一篇：算法竞赛入门经典授课教案第3章 数组和字符串
第3章 数组和字符串
第3章 数组和字符串
【教学内容相关章节】
3.1数组 3.2字符数组 3.3最长回文子串 3.4小结与习题 【教学目标】
（1）掌握一维数组的声明和使用方法；（2）掌握二维数组的声明和使用方法；
（3）掌握字符串的声明、赋值、比较和连接方法；（4）熟悉字符的ASCII码和ctype.h；
（5）正确认识++、+=等能修改变量的运算符；（6）学会编译选项-Wall获得更多的警告信息；（7）掌握fgetc和getchar的使用方法；
（8）了解不同操作系统中换行符的表示方法；
（9）掌握fgets的使用方法并了解gets的“缓冲区溢出”的漏洞；（10）理解预处理和迭代开发的技巧。【教学要求】
（1）掌握一维数组和二维数组的声明和使用方法；（2）掌握字符串的声明、相关的操作；（3）掌握fgetc和getchar的使用方法；（3）掌握fgets和gets的使用方法。【教学内容提要】
通过对第2章的学习，了解了计算机的计算优势，但没有发挥出计算机的存储优势——只用了屈指可数的变量。尽管有的程序也处理了大量的数据，但这些数据都只是“过客”，只参与了计算、并没有被保存下来。
本章介绍数组和字符串，二者都能保存大量的数据。字符串是一种数组（字符数组），但由于其应用的特殊性，适用一些特别的处理方式。【教学重点、难点】
教学重点：
（1）掌握一维数组和二维数组的声明和使用方法；（2）掌握字符串的声明、相关的操作；（3）掌握fgetc和getchar的使用方法；（3）掌握fgets和gets的使用方法。教学难点：
（1）掌握一维数组和二维数组的声明和使用方法；
（2）掌握字符串的声明、相关的操作及字符串处理函数的使用。【课时安排（共5学时）】
3.1数组 3.2字符数组 3.3最长回文子串 3.4小结与习题（1学时）
第 52页
第3章 数组和字符串
3.1 数 组
下面从一个问题出发，说明一下为何使用数组。
问题：读入一些整数，逆序输出到一行中，已知整数不超过100个。【分析】
首先通过循环来读取100个整数的输入，然后把每个数都存下来，存放在数组中，最后输出。
程序3-1 逆序输出
#include
提示3-1：语句int a[MAXN]声明了一个包含MAXN个整型变量的数组，即a[0],a[1],a[2] ,„,a[MAXN-1]，但不包含a[MAXN]。MAXN必须是常数，不能是变量。
在本程序中，声明MAXN为100+10而不是100，主要是为了保险起见。
提示3-2：在算法竞赛中，常常难以精确计算出需要的数组大小，数组一般会声明得稍大些。在空间够用的前提下，浪费一点不要紧。
语句a[n++]=x;的等价于两条语句a[n]=x;n++;，循环结束后，数据被存在了a[0],a[1] ,„,a[n-1]，其中变量n个整数的个数。
在数组中存放整数后，依次输出a[n-1],a[n],„,a[1]和a[0]。一般要求输出的行首行尾均无空格，相邻两个数据间用单个空格隔开，一共需要输出n个整数，但只有n-1个空格，所以只好分两条语句输出。
在上述程序中，数组a被声明在main函数的外面。简单地说，只有在放外面时，数组a才可以开得很大；放在main函数内时，数组稍大就会异常退出。
提示3-3：比较大的数组应尽量声明在main函数外。
C语言数组中使用过程中，有一些特殊的情况。例如，数组不能够进行赋值操作，即不能将一个整体赋值给另外一个数组。如果从数组a复制到k个元素到数组b，可以这个语句： memcpy(b,a,sizeof(int)*k)。如果数组a和b都是浮点型的，复制时要写成memcpy(b,a, sizeof(double)*k)。另外需要注意的是，使用memcpy函数要包含头文件string.h。如果需要把数组a全部复制到数组b中，可以写成：memcpy(b,a,sizeof(a))。
说明：memcpy函数原型如下：
void *memcpy(void *dest, void *src, unsigned int count);它的功能是由src所指内存区域复制count个字节到dest所指内存区域，src和dest所指内存区域不能重叠，函数返回指向dest的指针。主要功能是对字符串进行拷贝，也可以对数组进行操作。在程序中需包含头文件：#include
例3-1 开灯问题。
有n盏灯，编号为1～n，第1个人把所有灯打开，第2个人按下所有编号为2的倍数的开关（这些灯将被关掉），第3个人按下所有编号为3的倍数的开关（其中关掉的灯被打开，开着灯将被关闭），依此类推。一共有k个人，问最后有哪些灯开着？
输入：n和k，输出开着的灯编号。k≤n≤1000。样例输入：7 3 样例输出：1 5 6 7
第 53页
第3章 数组和字符串
【分析】
用a[1],a[2],„,a[n]表示编号为1,2,3,„,n的灯是否开着，模拟这些操作即可。代码如下：
程序3-2 开灯问题逆序输出
#include
memset函数原型如下：
void *memset(void *buffer, char c, int count);它的功能是把buffer所指内存区域的前count个字节设置成字符c，第三个参数指的是字节的个数，返回指向buffer的指针，在程序中需包含头文件：#include
（2）有一个技巧是在输出：为了避免输出多余空格，设置了一个标志变量first，可以表示当前要输出的变量是否为第一个。第一个变量前不应有空格，但其他都有。
例3-2 蛇形填数。
在n*n方阵里填入1,2,„,n*n，要求填成蛇形。例如n=4时方阵为 10 11 12 1 9 16 13 2 8 15 14 3 7 6 5 4 上面的方阵中，多余的空格只是为了便于观察规律，不必严格输出。n≤8。【分析】
与数学的矩相比，可以用一个所谓的二维数组来存储题目中的方阵。只需声明一个int a[MAXN][MAXN]，就可以获得一个大小为MAXN×MAXN的方阵。在声明时，两维的大小不必相同。
提示3-4：用int a[MAXN][MAXN]生成一个整型的二维数组，其中MAXN和MAXN不必相等。这个数组共有MAXN×MAXN个元素，分别为a[0][0],a[0][1],„,a[0][MAXN-1],a[1][0] ,a[1][1],„,a[1][MAXN-1],„,a[MAXN-1][0],a[MAXN-1][1],„, a[MAXN-1][MAXN-1]。
第 54页
第3章 数组和字符串
假设从1开始依次填这写。设“笔”的坐标为(x,y)，则一开始x=0，y=n-1，即第0行第n-1列（注意行列的范围是0～n-1，没有第n列）。“笔”的移动轨迹是：下、下、下、左、左、左、上、上、上、右、右、下、下、左、上。总之，先是下，到不能填了为止，然后是左，接着是上，最后是右。“不能填”是指再走就出界（例如4→5）或者再走就要走到以前填过的格子（例如12→13）。如果把所有格式初始化为0，就能很方便地加以判断。
程序3-3 蛇形填数
#include 提示3-5：可以利用C语言简洁的语法，但前提是保持代码的可读性。 提示3-6：在很多情况下，最好是在做一件事之前检查是不是可以做，而不要做完再后悔。因为“悔棋”往往也比较麻烦。 说明：本程序对于与x+1 3.2 字 符 数 组 文本处理在计算机应用中占有重要地位。在C语言中，字符串其实就是字符数组——可以像处理普通数组一样处理字符串，只需要注意输入输出和字符串函数的使用。 例3-3 竖式问题。 找出所有形如abc*de（三位数乘以两位数）的算式，使得在完整的竖式中，所有数字都属于一个特定的数字集合。输入数字集合（相邻数字之间没有空格），输出所有竖式。每个竖式前应有编号，之后应有一个空行。最后输出解的总数。具体格式见样例输出（为了便于观察，竖式中的空格改用小数点显示，但你的程序应该输出空格，而非小数点）。 样例输入：2357 样例输出： <1>..775 x..33----- 第 55页 第3章 数组和字符串 .2325 2325.-----25575 The number of solutions=1 【分析】 本题的解题策略是尝试所有的abc和de，判断是否满足条件。写出如下的伪代码： char s[20];int count = 0;scanf(“%s”, s);for(abc = 111;abc <= 999;abc++)for(de = 11;de <= 99;de++)if(“abc*de”是个合法的竖式){ printf(“<%d>n”, ++count);打印abc*de的竖式和其后的空行 count++;} printf(“The number of solutions = %dn”, count);说明：（1）char s[20]是一个定义字符数组的语句，scanf(“%s”,s)表示从键盘输入一个字符串给字符数组s。 （2）char是“字符型”的意思，而字符是一种特殊的整数。每一个字符都有一个整数编码，称为ASCII码。C语言中允许用直接的方法表示字符，还有以反斜线开头的字符（转义序列，Escape Sequence）。 （3）在stdlib.h中有一个函数atoi，它的函数原型如下： int atoi(char *s)它表示将字符串s中的内容转换成一个整型数返回，如字符串“1234”,则函数返回值是1234。 （4）在stdlib.h中有一个函数itoa，它的函数原型如下： char *itoa(int value,char *string,int radix)它表示将整数value转换成字符串存入string, radix为转换时所用基数(保存到字符串中的数据的进制基数 2 8 10 16)，返回指向转换后的字符串的指针。 例如，itoa(32,string,10)是将32变成十进制数一个字符串“32”，并返回指向这个字符串的指针；itoa(32,string,16)是将32变成十进制数一个字符串“20”，并返回指向这个字符串的指针。 提示3-7：C语言中的字符型用char表示，它实际存储的是字符的ASCII码。字符常量可以用单引号法表示。在语法上可以把字符当作int型使用。 语句scanf(“%s”, s);表示读入一个不含空格、TAB和回车符的字符串，存入字符数组s中，s前面没有&符号。 提示3-8：在scanf(“%s”,s)中，不要在s前面加上&符号。如果是字符数组char s[MAXN] [MAXL],可以用scanf(“%s”,s[i])读取第i个字符串。 接下来有两个问题：判断和输出。先考虑输出。首先计算第一行乘积x=abc*e，然后是第二行y=abc*d，最后是总乘积z=abc*de，然后一次性打印出来： printf(“%5dnX%4dn-----n%5dn%4dn-----n%5dnn”,abc,de,x,y,z);完整程序如下： 程序3-4 竖式问题 #include 第 56页 第3章 数组和字符串 for(de = 11;de <= 99;de++){ x = abc*(de%10);y = abc*(de/10);z = abc*de;sprintf(buf, “%d%d%d%d%d”, abc, de, x, y, z);ok = 1;for(i = 0;i < strlen(buf);i++)if(strchr(s, buf[i])== NULL)ok = 0;if(ok){ printf(“<%d>n”, ++count);printf(“%5dnX%4dn-----n%5dn%4dn-----n%5dnn”,abc,de,x,y,z);} } printf(“The number of solutions = %dn”, count);return 0;} 说明：（1）sprintf函数 sprintf是个变参函数，定义如下： int sprintf(char *buffer, const char *format [, argument]...);除了前两个参数类型固定外，后面可以接任意多个参数。而它的精华，显然就在第二个参数格式化字符串上。 此函数的功能是把格式化的数据写入某个字符串，它的返回值是字符串长度。包含此函数的头文件是stdio.h。 例如，本程序中的sprintf(buf,“%d%d%d%d%d”,abc,de,x,y,z);语句的功能是将整数abcdexyx打印成字符串存储在串buff中。 （2）strchr函数 strchr函数定义如下： char *strchr(const char *s,char c);此函数的功能是查找字符串s中首次出现字符c的位置。它的返回值是返回首次出现c的位置的指针，如果s中不存在c则返回NULL。包含此函数的头文件是string.h。 例如，本程序的if语句中strchr(s, buf[i])的功能是查找字符串s中首次出字符buf[i]的位置。如果strchr(s, buf[i])==NULL，则表明字符串s中没有buf[i]的字符。 （3）sprintf函数、printf函数、fprintf函数的区别 printf输出到屏幕，fprintf输出到文件，而sprintf输出到字符串。需要注意是应该保证写入的字符串有足够的空间。 提示3-9：可以用sprintf把信息输出到字符串，用法和printf、fprintf类似。但你应当保证字符串足够大，可以容纳输出信息。 字符串的空间应为字符个数加1，这是因为C语言的字符串是以空字符' '结尾的。函数strlen(s)的作用是获取字符串s的实际长度，即函数strlen(s)返回的是结束标记之前的字符个数。因此这个字符串中的各个字符依次是s[0],s[1],„,s[strlen(s)-1]，而s[strlen(s)]正是结束标记' '。 提示3-10：C语言中的字符串是' '结尾的字符数组，可以用strlen(s)返回字符串s中结束标记之前的字符个数。字符串中的各个字符是：s[0],s[1],„,s[strlen(s)-1]。 提示3-11：由于字符串的本质是数组，它也不是“一等公民”，只能用strcpy(a,b)、strcmp(a,b)、strcat(a,b)来执行“赋值”、“比较”和“连接”操作。而不能用=、==、<=、+等运算符。上述函数都在string.h中声明。 除了字符串之外，还要注意++count和count++的用法。++count本身的值是加1以后的，但count++的值是加1之前的（原来的值）。 注意：滥用++count和count++会带来很多隐蔽的错误，所以最好的方法是避开它们。提示3-12：滥用++、--、+=等可以修改变量值的运算符很容易带来隐蔽的错误。建议每条语句最多只用一次这种运算符，并且它所修改的变量在整条语句中只出现一次。 第 57页 第3章 数组和字符串 提示3-13：但编译选项-Wall编译程序时，会给出很多（但不是所有）警告信息，以帮助程序员查错。但并不能解决所有的问题：有些“错误”程序是合法的，只是这些动作不是你所期望的。 3.3 最长回文子串 例3-4 回文串。 输入一个字符串，求出其中最长的回文子串。子串的含义是：在原串中连续出现的字符串片段。回文的含义是：正着看和倒着看相同。如abba和yyxyy。在判断时，应该忽略所有标点符号和空格，且忽略大小写，但输出应保持原样（在回文串的首部和尾部不要输出多余字符）。输入字符串长度不超过5000，且占据单独的一行。应该输出最长的回文串，如果有多个，输出起始位置最靠左的。 样例输入：Confuciuss say:Madam,I'm Adam.样例输出：Madam,I'm Adam 【分析】 由于输入的字符比较复杂，首先，不能用scanf(“%s”)输入字符串，可用下述两种方法解决下列问题： 第1种方法是使用fgetc(fin)，它读取一个打开的文件fin，读取一个字符，然后返回一个int值。因为如果文件结束，fgetc将返回一个特殊标记EOF，它并不是一个char。如果要从标准输入读取一个字符，可以用getchar()，它等价于fgetc(stdin)。 提示3-14：使用fgetc(fin)可以打开的文件fin中读取一个字符。一般情况下应当在检查它不是EOF后再将其转换成char值。从标准输入读取一个字符可以用getchar()，它等价于fgetc(stdin)。 fgetc()和getchar()将读取“下一个字符”，如果是空格，会正常读取；若是换行，读取到的将是回车符'n'。 潜在的陷阱：不同操作系统的回车换行符是不一致的。Windows是'r'和'n'两个字符，Linux是'n'，而MacOS是'r'。如果在Windows下读到Windows文件，fgetc()和getchar()会把'r'吃掉，只剩下'n'；但如要要在Linux下读取同样一个文件，它们会先读到'r'，然后才是'n'。这个问题在竞赛时一定要注意。 提示3-15：在使用fgetc和getchar时，应该避免写出和操作系统相关的程序。 第2种方法是使用fgets(buf,MAXN,fin)读了完整的一行，其中buf的声明为char buf[MAXN]。这个函数读取不超过MAXN-1个字符，然后在末尾上结束符' '，因此不会出现越界的情况。之所以说可以用这个函数读取完整的一行，是因为一旦读到回车符'n',读取工作将会停止，而这个'n'也会是buf字符串中最后一个有效字符（再往后就是字符串的结束符' '了）。只有一种情况下，buf不会以'n'结尾：读到文件结束符，并且文件的最后一个不是以'n'结尾。 提示3-16：fgets(buf,MAXN,fin)将读取完整的一行放在字符数组buf中。你应当保证buf足够存放下文件的一行内容。除了在文件结束符前没有遇到'n'这种特殊情况外，buf总是以'n'结尾。当一个字符都没有读到时，fgets返回NULL。 gets(s)表示从标准输入设备读取字符串存入s所指向的数组中，成功时返回指针s，否则返回NULL。但是gets(s)没有指明读到的最大字符数，gets函数也不管s的可用空间有多大。 提示3-17：C语言并不禁止程序读写“非法内存”。例如你声明的是char s[100]，你完全可以赋值s[10000]='a'（甚至-Wall也不会警告），但后果自负。 提示3-18：C语言中的gets(s)存在缓冲区溢出漏洞，不推荐使用。 选择fgets函数可以解决“输入有空格”的问题，它可以一次性读取一行，最为方便。接下来，解决“判断时忽略标点，输出进却要按原样”的问题，可以用一个通用的方案：预处理。构造一个新字符串，不包含原来的标点符号，而且所有字符变成大写（顺便解决了大小写的问题）： n = strlen(buf);m=0; 第 58页 第3章 数组和字符串 for(i = 0;i < n;i++)if(isalpha(buf[i]))s[m++] = toupper(buf[i]);说明：isalpha(c)的原型包含在ctype.h中，它用于判断字符c是否为字母（大写或小写）。用toupper(c)返回c的大写形式。这样处理之后，buf保存的就是原串的所有字母了。 提示3-19：当任务比较复杂时，可以用预处理的方式简化输入，并提供更多的数据供使用复杂的字符串处理题目往往可以通过合理的预处理简化任务，便于调试。 提示3-20：头文件ctype.h中定义的isalpha、isdigit、isprint等工具可以用来判断字符的属性，而toupper、tolower等工具可以用来转换大小写。 说明：（1）isalpha(c)用来检查c是否为字母，如果是字母，则返回1；否则返回0。（2）isdigit(c)用来检查c是否为数字（0～9），如果是数字，则返回1；否则返回0。（3）isprint(c)用来检查c是否为可打印字符（不包括空格），其ASCII码值在0x21～0x7e之间，如果是可打印字符，则返回1；否则返回0。 （4）toupper(c)用来将c字符转换为大写字母，返回c对应的大写字母。（5）tolower(c)用来将c字符转换为小写字母，返回c对应的小写字母。下面来枚举回文串的起点和终点，然后判断它是否真的是回文串。int max=0;for(i = 0;i < m;i++)for(j = i;j < m;j++)if(s[i..j]是回文串 && j-i+1 > max)max = j-i+1;“当前最大值”变量max，它保存的是目前为止发现的最长回文子串的长度。如果串s的第i个字符到第j个字符（记为s[i..j]）是回文串，则检查长度j-i+1是否超过max。 最后，判断s[i..j]是否为回文串的方法如下： int ok = 1;for(k = i;k <= j;k++)if(s[k]!= s[i+j-k])ok = 0;s[k]的“对称”位置是s[i+j-k]，因为只要一次比较失败，就应把标记变量ok置为0。完整的程序如下： 程序3-5 最长回文子串（1） #include 第 59页 第3章 数组和字符串 在实际编程时，经常先编写一个具备主要功能的程序，再加以完善。甚至可以先写一个只有输入输出功能的“骨架”，但是要确保它正确。这样，每次只添加一点点功能，而且写一点就测试一点，和一次写整个程序相比，更加不容易出错。这种方法称为迭代式开发。 提示3-21：在程序比较复杂时，除了在设计阶段可以用伪代码理清思路外，编码阶段可以采用迭代时开发——每次只实现一点小功能，但要充分测试，确保它工作正常。 程序3-5能顺利求出样例数据中最长回文串的长度。现在接下来的任务是输出这个回文串：要求原样输出，并且尽量靠左。由于是从左到右枚举的，所以现在只剩下唯一的问题：原样输出。 由于在求max值时，不知道s[i]和s[j]在原串buf中的位置。因此，必须增加一个数组p，用p[i]保存s[i]在buf中的位置。在预处理得到，然后在更新max的同时把p[i]和p[j]保存到x和y，最后输出buf[x]到buf[y]中的所有字符。 但是上面的方法发现速度很慢，所以换一种方式：枚举回文串的“中间”位置i，然后不断往外扩展，直到有字符不同。提示：长度为奇数和偶数的处理方式是不一样的。 完整的程序如下： 程序3-6 最长回文子串（2） #include 3.4 小结与习题 到目前为止，C语言的核心内容已经全部讲完了。理论上，运用算法前3章的知识足以编写大部分算法竞赛程序了。 第 60页 第3章 数组和字符串 3.4.1 必要的存储量 3.4.2 用ASCII编码表示字符 在C语言除了字符常量，还有一种特殊形式的字符常量，就是以一个字符“”开头的字符序列。在转义符中还可以用一个ASCII码（八进制数或十六进制数）来表示字符。 提示3-22：字符还可以直接用ASCII码表示。如果八进制，应该写成ddd，它表示1到3位八进制所代表的字符；如果用十六进制，应该写成xhh，它表示1到2位十六进制所代表的字符。 3.4.3 补码表示法 计算机中的二进制是没有符号的，但是对于正号和负号可以一个二进制位就可以了。一个带符号32位整数，在计算机内部采用“补码的表示法”（Complement Representation）。 32例如，语句printf(“%un”,-1)的输出是4294967295=2-1。把-1换成- 2、- 3、- 4、„ 32后，可总结一个规律：-n的内部表示是2-n。 提示3-23：在多数计算机内部，整数采用的是补码表示法。采用补码表示法的主要原因是可以将符号位和其它位统一处理；同时，减法也可按加法来处理。另外，两个用补码表示的数相加时，如果最高位（符号位）有进位，则进位被舍弃。 在通常情况下，int是32位（4字节）的。3.4.4 重新实现库函数 在学习字符串时，重新实现一些库函数的功能是有益的。 练习1：只用getchar函数读入一个整数。假设它占据单独的一行，读到行末为止，包括换行符。输入保证读入的整数可以保存在int中。 练习2：只用fgets函数读入一个整数。假设它占据单独的一行，读到行末为止，包括换行符。输入保证读入的整数可以保存在int中。 练习3：只用getchar实现fgets的功能，即用每次一个字符的方式读取整行。 练习4：实现strchr的功能，即在一个字符串中查找一个字符。解答：下面编写一个函数strchr1实现strchr的功能： char *strchr1(char *str,int ch){ int i;for(i=0;str[i]!= ' ';i++)if(str[i] == ch)return str+i;return NULL;} 练习5：实现isalpha和isdigit的功能，即判断字符是否为字母/数字。解答：（1）下面编写一个函数isapha1实现isalpha的功能： int isalpha1(char ch){ if((ch>='a' && ch<='z')||(ch>='A' && ch<='Z'))return 1;else return 0;}（2）下面编写一个函数isdigit1实现isdigit的功能： int isdigit1(char ch){ if(ch>='0' && ch<='9')return 1;else return 0;} 3.4.5 字符串处理的常见问题 tot=1; 第 61页 第3章 数组和字符串 for(i = 0;i < strlen(s);i++)if(s[i] == 1)tot++;printf(“There are %d character(s)'1' in the string.n”,tot);本程序的功能是统计字符串中字符1的个数。 7实验1：添加字符串s的声明语句，长度不小于10。提示：放在main函数内还是外？ 解答：添加字符串s的声明语句如下： #define MAXN 10000000 char s[MAXN];应放在main函数外。 实验2：添加读取语句，测试上述程序是否输出了期望的结果。如果不是，请改正。 解答：得不到期望的结果，改正如下： if(s[i] == 1)tot++;改为if(s[i] == '1')tot++; 5实验3：把输入语句注释掉，添加语句，用程序生成一个长度至少为10的字符 5串，并用程序验证字符串长度确实不小于10。 解答：程序如下： #include 解答：程序如下： #include clock_t start, finish; start=clock();for(i = 0;i < 1000000;i++)s[i] = '1';for(i = 0;i < strlen(s);i++)if(s[i] == '1')tot++;printf(“There are %d character(s)'1' in the string.n”,tot); finish=clock();printf(“Time used=%.5lf secondsn”,(finish-start) 第 62页 第3章 数组和字符串 /(double)CLOCKS_PER_SEC);return 0;} 这段程序的运行时间是当字符串的长度为10000时，运行时间为0.05秒；当字符串的长度为100000时，运行时间为5.32秒；当字符串的长度为1000000时，运行时间为558.56秒。所以这段程序的运行时间的规律是当字符串的长度增长到原来的10倍，则运行时间增长到原来的近100倍。 说明：（1）clock函数是C/C++中的计时函数，而与其相关的数据类型是clock_t。在MSDN中，查得对clock函数定义如下： clock_t clock(void);（2）clock函数返回从“开启这个程序进程”到“程序中调用clock()函数”时之间的CPU时钟计时单元（clock tick）数，在MSDN中称之为挂钟时间（wal-clock）；若挂钟时间不可取，则返回-1。其中clock_t是用来保存时间的数据类型，在头文件time.h中，可以找到对它的定义： #ifndef _CLOCK_T_DEFINED typedef long clock_t;#define _CLOCK_T_DEFINED #endif 说明clock_t是一个长整形数。 （3）在头文件time.h文件中，还定义了一个常量CLOCKS_PER_SEC，它用来表示一秒钟会有多少个时钟计时单元，其定义如下： #define CLOCKS_PER_SEC((clock_t)1000)3.4.6 关于输入输出 1．getchar函数 当程序请求键盘输入时，getchar()函数只要用户回车键时，就可以返回。不一定是输入第一字符，就按回车键，也可以是输入许多字符，最后按回车键。 如果直接输入文件结束符（Windows是Ctrl+Z键），getchar()读到的是ASCII码中不可显示的控制字符（ASCII码值为10，LF表示行满，需要换行）。 说明：（1）getchar有一个int型的返回值。当程序调用getchar时，程序就等着用户按键，用户输入的字符被存放在键盘缓冲区中，直到用户按回车为止(回车字符也放在缓冲区中)。当用户键入回车之后，getchar才开始从stdio流中每次读入一个字符。 （2）getchar函数的返回值是用户输入的第一个字符的ASCII码，如出错返回-1，且将用户输入的字符回显到屏幕。 （3）如用户在按回车之前输入了不止一个字符，其他字符会保留在键盘缓存区中，等待后续getchar调用读取。也就是说,后续的getchar调用不会等待用户按键，而直接读取缓冲区中的字符，直到缓冲区中的字符读完为后，才等待用户按键。 如果把getchar函数放在循环里，也能实现读入一串字符。例如“要读入一串字符，直到按下回车键表示结束”，可以使用下面的结构： char ch;while((ch = getchar())!= 'n'){ „ /* 处理该字符ch */ } 上述循环的执行过程是：先从键盘上读入一个字符，把字符赋值给ch，然后判断ch是否为换行符'n'，如果是，循环就结束了；如果不是，则执行循环体。因此该结构可以读入多个字符，一直到按下回车键为止（按下回车键实际上输入了两个字符：“回车”字符和“换行”字符，ASCII编码分别为13和10。 2．sscanf函数 （1）sscanf()表示从一个字符串中读取与指定格式相符的数据。它的函数原型如下： 第 63页 第3章 数组和字符串 int sscanf(const char *, const char *, „)需要的头文件是stdio.h。 （2）sscanf与scanf类似，都是用于输入的，只是后者以键盘(stdin)为输入源，前者以固定字符串为输入源。 如果有一个格式为HH:MM:SS的字符串s（例如，“12:34:56”），用一条sscanf语句得到HH、MM、SS的值如下： sscanf(s,“%d:%d:%”,&HH,&MM,&SS);将s替换成“12:34:56”，可以得到HH的值为12，MM的值为34，SS的值为56。 3.4.7 I/O的效率 题目是“直接输出”：输入不超过1000行字符串，然后直接输出。每行都是长度不超过10000的字符串，包含大写字母和小写字母，不包含任意空白（如空格、TAB）。 第1种方法是用C++中的流和字符串对象。#include （2）C++字符串和C语言的字符数组是可以相互转换的：如果s是一个字符数组，那么string(s)就是相应的字符串；如果s是一个字符串，则s.c_str()就是相应的字符数组。 （3）c_str()返回的内容是只读的。例如，可以用printf(“%s”,s.c_str())来输出，但不能用scanf(“%s”,s.c_str())来输入。 第2种方法是用getchar。#include 第 64页 第3章 数组和字符串 int main(){ char s[1000];cin.getline(s, 1000, 'n');stringstream ss(s);int a, b;ss >> a >> b;count << a+b << “n”;return 0;} 上面的函数先从cin读取一行。Getline函数的第3个参数是行分隔符。它的默认值就是'n'，因此可以简化为cin.getline(s,1000)，其中1000的含义和fgets中的类似。 3.4.8 小结 数组和字符串意味着大数据量，而处理大数据量时通常给遇到“访问非法内存”的错误。在语法上，C语言并不禁止程序访问非法内存，但后果难料。可以采取两种方法来解决，通过在访问数组前检查下标是否合法来缓解；适当把数组开大。对于gets函数，存在缓冲区溢出漏洞。对于strcpy也有类似问题——如源字符串并不是以' '结尾的，复制工作将可能覆盖到缓冲区之外的内存。 在数组和字符串处理程序中，下标的计算是极为重要的。 理解字符编码对于正确地使用字符串是至关重要的。算法竞赛中涉及的字符一般是ASCII表中的可打印字符。对于中文的GBK编码，如果char值为正，则是西文字符；如果为负，则汉字的前一半（这时需要再读一个char）。 3.4.9 上机练习 习题3-1 分数统计（stat） 输入一些学生的分数，哪个分数出现的次数最多？如果有多个并列，从小到大输出。 说明：（1）假设输入分数的个数不超过10000；如果没有这个假设，这个问题就不好办了。 （2）如果有多个并列，从小到大输出。（注意，书中这里有个定义模糊的地方，我把它明确一下：对于相同的分数，只要输出一次。 任务1：分数均为不超过100的非负整数。输入文件：习题3-1，分数统计（stat）a.in 输出到屏幕 【分析】 解题所用的数据结构： （1）用一个数组marks存储输入的分数 （2）用另一个数组counts存储对应分数出现的次数 解题思路和步骤： （1）输入数据，并处理好marks和counts数组中的数据； （2）扫描一遍counts，看看出现次数最多的，是多少？记为maxTimes（3）将出现次数为maxTimes的分数，从小到大输出。 由于学生到此为止，还没有学习过排序的算法，所以这一步就比较麻烦了。具体的做法如下： （1）扫描counts数组，找到次数为maxTimes的、最小的分数，将其输出 （2）将刚刚输出的那个分数所对应的maxTimes值减量1（为的是下一次不再输出这个值了）。 （3）重复（1）、（2）两步，直至再也找不到次数为maxTimes的分数了。完整的程序如下： #include 第 65页 第3章 数组和字符串 int newData, /*新输入的数据*/ i,j, /*辅助变量*/ exists, /*输出结果时所用的辅助变量*/ maxTimes, /*最大的出现次数*/ min;int marks[MAX], /*存储输入的数据*/ counts[MAX];/*存储数据的计数*/ freopen(“习题3-1，分数统计（stat）a.in”,“r”,stdin);for(i=0;i marks[i]=NOMARK;/*初始化数组；想想看：为啥要初始化为-1？*/ counts[i]=0;/*初始化数组；想想看：为啥要初始化为0？*/ } /*====================== 输入数据 ===============================*/ while(scanf(“%d”,&newData)==1){ /*当还有分数输入的时候*/ i=0; while(marks[i]!=newData && marks[i]!=NOMARK)i=i+1; marks[i]=newData;/*即使marks[i]==newData,这句话也是没有副作用。*/ counts[i]=counts[i]+1;/*计数器增量*/ } /*===== 扫描counts数组，寻找最大的出现次数（maxTimes）==========*/ i=0;maxTimes=0;/*一开始，不妨假设最大的出现次数为0*/ while(counts[i]!=0){ if(counts[i]>maxTimes)maxTimes=counts[i]; i=i+1;} /*printf(“最大的出现次数 maxTimes=%dn”,maxTimes);*/ /*======= 将拥有最大出现次数的那些分数，由小到大输出 ============*/ exists=1;/*假设存在某个分数，他的出现次数为maxTimes*/ while(exists){ exists=0; i=0; min=101;/*出现次数为maxTimes的众多分数中，最小的那个分数就是min；一开始，我们假设min为101，为的是确保所有出现次数为maxTimes的分数都会比一开始的min小。*/ while(counts[i]!=0){ /*扫描counts数组，在其中寻找出现次数为maxTimes的、最小的那个分数*/ if(counts[i]==maxTimes){ exists=1;/*表明在此次扫描中，又找到了出现次数为 maxTimes 的分数*/ if(marks[i] min=marks[i]; j=i; } } i=i+1; } /*至此，j应该指向目前marks数组中，出现次数为maxTimes，并且值最小的那个元素*/ if(exists)printf(“%d ”,marks[j]); 第 66页 第3章 数组和字符串 counts[j]=counts[j]-1;/*将这个元素的出现次数-1，以确保它不会被再次输出*/ } return 0;} 任务2：分数均为不超过100的非负实数，但最多保留两位小数。【分析】 同任务1的分析。完整的程序如下： #include exists, /*输出结果时所用的辅助变量*/ maxTimes;/*最大的出现次数*/ float min，newData;/*新输入的数据*/ float marks[MAX];/*存储输入的数据*/ int counts[MAX];/*存储数据的计数*/ freopen(“习题3-1，分数统计（stat）b.in”,“r”,stdin);for(i=0;i marks[i]=NOMARK;/*初始化数组；想想看：为啥要初始化为-1？*/ counts[i]=0;/*初始化数组；想想看：为啥要初始化为0？*/ } /*====================== 输入数据 ===============================*/ while(scanf(“%f”,&newData)==1){ /*当还有分数输入的时候*/ i=0; while(marks[i]!=newData && marks[i]!=NOMARK)i=i+1; marks[i]=newData;/*即使marks[i]==newData,这句话也是没有副作用。*/ counts[i]=counts[i]+1;/*计数器增量*/ } /*===== 扫描counts数组，寻找最大的出现次数（maxTimes）==========*/ i=0;maxTimes=0;/*一开始，不妨假设最大的出现次数为0*/ while(counts[i]!=0){ if(counts[i]>maxTimes)maxTimes=counts[i]; i=i+1;} /*printf(“最大的出现次数 maxTimes=%dn”,maxTimes);*/ /*======= 将拥有最大出现次数的那些分数，由小到大输出 ============*/ exists=1;/*假设存在某个分数，他的出现次数为maxTimes*/ while(exists){ exists=0; i=0; min=101;/*出现次数为maxTimes的众多分数中，最小的那个分数就是min；一开始，我们假设min为101，为的是确保所有出现次数为maxTimes的分数都会比一开始的min小。*/ while(counts[i]!=0){ /*扫描counts数组，在其中寻找出现次数为maxTimes的、最小的那个分数*/ if(counts[i]==maxTimes){ 第 67页 第3章 数组和字符串 exists=1;/*表明在此次扫描中，又找到了出现次数为 maxTimes 的分数*/ if(marks[i] min=marks[i]; j=i; } } i=i+1; } /*至此，j应该指向目前marks数组中，出现次数为maxTimes，并且值最小的那个元素*/ if(exists)printf(“%.2f ”,marks[j]); counts[j]=counts[j]-1;/*将这个元素的出现次数-1，以确保它不会被再次输出*/ } return 0;}习题3-2 单词的长度（word） 输入若干个单词，输出它们的平均长度。单词只包含大写字母和小写字母，用一个或多个空格隔开。 【分析】 解决本题，需要用到字符串的知识。字符串，也就是一维的字符数组。结束输入的方法按Ctrl+Z键，回车，回车。 使用的策略是：scanf(“%s”,...);遇到空格时，会自动截断，很适合用在这种环境。strlen();用于计算字符串的长度 操作步骤如下： （1）读入一个单词； （2）计数器增量1； （3）计算单词长度，累加总长度； （4）总长度/计数器---->平均长度。完整的程序如下： #include count=0;while(scanf(“%s”,word)!=0){ /*表示有数据输入*/ count=count+1; lengthSum=lengthSum+strlen(word);} if(count==0) printf(“没有单词输入”);else printf(“输入的单词平均长度为：%f”,lengthSum/(count*1.0));return 0;}习题3-3 乘积的末3位（product） 第 68页 第3章 数组和字符串 输入若干个整数（可以是正整数、负数或者零），输出它们的乘积的末3位。这些整数中会混入一些由大写字母组成的字符串，你的程序应当忽略它们。提示：试试看，在执行scanf(“%d”)时输入一个字符串会怎样？ 【分析】 每个输入的数据（无论是整数还是字符串）之间，都用回车或空格来分隔。对于乘积不足3位的情况，就输出完整的乘积，左侧不用补0。对于乘积为负数的情况，左侧不必加上-。输入的整数可能有很多个，所以最后的乘积可能会很大。“由大写字母组成的字符串”指的是字符串中全部都是大写字母。输入数据，以“Ctrl+Z，回车，回车”结束。 假设输入的整数不会超过int的表示范围，如果没有任何输入数据，则输出0。采取的策略如下： （1）对于输入的数据都要做为字符串来看待。 （2）对于每一个输入的数据，要判断其是否为数字。若是，要将“数字字符串”转为“整型数据”；否则，忽略这个数据。 （3）为了计算(x*y)的末三位，其实只要计算(x的末三位)*(y的末三位)，看其结果的末三位即可。 完整的程序如下： #include result=0, /*得到的结果。之所以初始化为0，而非1；是要考虑到用户可能没有输入任何整数的情况。*/ p,counts=0;/*count为计数器，用于统计用户输入的数字个数*/ char inStr[100];/*输入的字符串数据*/ while(scanf(“%s”,inStr)!=0){ if(inStr[0]>='A' && inStr[0]<='Z')/*说明读到的数据是“由大写字母组成的字符串”*/ continue; /*有数字字符串输入*/ counts=counts+1; if(counts==1)result=1; /*printf(“字符串：%st”,inStr);*/ /*将“数字字符串”的后3位转为整数*/ p=strlen(inStr)-1; newData=0; if(p>=0 && inStr[p]>='0' && inStr[p]<='9')newData=inStr[p]-'0'; p=p-1; if(p>=0 && inStr[p]>='0' && inStr[p]<='9')newData=newData+(inStr[p]-'0')*10; p=p-1; if(p>=0 && inStr[p]>='0' && inStr[p]<='9')newData=newData+(inStr[p]-'0')*100; /*printf(“后三位转为整数：=%dn”,newData);*/ result=(result*newData)%1000;/*乘积取最后三位*/ /*printf(“....%dn”,result);*/ /*调试信息*/ } printf(“%d”,result);return 0;}习题3-4 计算器（calculator） 第 69页 第3章 数组和字符串 编写程序，读入一行恰好包含一个加号、减号或乘号的表达式，输出它的值。这个运算符保证是二元运算符，且两个运算数均为不超过100的非负整数。运算数和运算符可以紧挨着，也可以用一个或多个空格、TAB隔开。行首末为均可以有空格。提示：选择合适的输入方法可以将问题简化。 样例输入：1+1 样例输出：2 样例输入：2-5 样例输出：-3 样例输入：0 *1982 样例输出：0 【分析】 使用的策略如下：（1）读取一行str（2）扫描str，忽视其中的“空格，t, n”，生成strX, strY, 和 operator（3）把 strX 转为 x, strY 转为 y（4）根据 operator，计算 x operator y（5）输出结果 说明：（1）使用gets()读取字符串，可以将输入字符串中的 空格, t 一起读入；但不会读入字符串最后的回车； （2）x, y 位于[0,100]之间； （3）假设输入的字符串总长度不超过MAXLEN=10000（题目没有说明空格等字符的上限）； （4）假设用户输入的数据总是合法的。完整的程序如下： #include i,j, /*临时变量*/ p, /*指针*/ power;/*位权*/ char str[MAXLEN], /*输入的字符串*/ strX[4], /*x，位于[0,100]，所以长度4就足够了*/ strY[4], /*y，位于[0,100]，所以长度4就足够了*/ operator;gets(str);/*printf(“strlen(str)=%dn”,strlen(str));*//*调试代码*/ /*============ 解析出str中的 strX ===============*/ p=0;for(i=0;str[i]!='+' && str[i]!='-' && str[i]!='*';i=i+1){ if(str[i]>='0' && str[i]<='9'){ strX[p]=str[i]; p=p+1; } } strX[p]=0;/*给字符串的末尾加上结束标记*/ /*printf(“%st%dn”,strX,strlen(strX));*//*调试代码*/ /*============ 解析出str中的 operator ===============*/ operator=str[i];/*============ 解析出str中的 strY ===============*/ p=0; 第 70页 第3章 数组和字符串 while(i<=strlen(str)-1){ if(str[i]>='0' && str[i]<='9'){ strY[p]=str[i]; p=p+1; } i=i+1;} strY[p]=0;/*给字符串的末尾加上结束标记*/ /*printf(“%st%dn”,strY,strlen(strY));*/ /*调试代码*/ /*========== 将strX转为x,strY转为y ============*/ x=0;for(i=strlen(strX)-1;i>=0;i=i-1){ power=1; for(j=1;j<=(strlen(strX)-1)-i;j=j+1)power=power*10; x=x+(strX[i]-'0')*power;} y=0;for(i=strlen(strY)-1;i>=0;i=i-1){ power=1; for(j=1;j<=(strlen(strY)-1)-i;j=j+1)power=power*10; y=y+(strY[i]-'0')*power;} /*printf(“x=%dty=%dn”,x,y);*/ /*调试代码*/ if(operator=='+')printf(“%d”,x+y);if(operator=='-')printf(“%d”,x-y);if(operator=='*')printf(“%d”,x*y);return 0;}习题3-5 旋转（rotate） 0输入一个n*n字符矩阵，把它左转90后输出。【分析】 本题描述存在一个问题：没有明确指出n*n字符矩阵是以何种格式输入的。在解决问题的时候，程序员需要自己定义输入数据的格式。在此，我们定义输入数据的格式如下： （1）先输入一个整数n，表示n*n字符矩阵；（2）再输入n*n个字符，表示矩阵中的数据； （3）假设用户输入的数据都是合法的，设 0<=n<=100。输出数据：逆时针转90度后的n*n矩阵 举例说明： 输入： 4 a b c d e f g h i j k l m n o p 输出： d h l p c g k o b f j n a e i m 采用的数据结构是用100*100的二维数组来存储数据。 第 71页 第3章 数组和字符串 使用的策略是仔细观察输入和输出的样例。和输入矩阵对比，输出矩阵是以行为单位输出，对于n个输出行而言，是从右向左按列输出“输入矩阵”。 完整的程序如下： #include x, /* 行 */ y;/* 列 */ /*=============== 数据输入 =================*/ scanf(“%d”,&n);for(x=0;x<=n-1;x=x+1){ for(y=0;y<=n-1;y=y+1){ scanf(“%c”,&m[x][y]); /* 由于输入的是字符数据，所以要跳过可能存在回车、换行、空格、制 表符等不可见字符 */ while(m[x][y]=='n' || m[x][y]=='t' || m[x][y]==' ') scanf(“%c”,&m[x][y]); } } /*调试代码：打印刚刚输入的用户数据*/ /* for(x=0;x<=n-1;x=x+1){ for(y=0;y<=n-1;y=y+1){ printf(“%c ”,m[x][y]); } printf(“n”);} */ /*=============== 输出数据 ================*/ for(y=n-1;y>=0;y=y-1){ for(x=0;x<=n-1;x=x+1){ printf(“%c ”,m[x][y]); } printf(“n”);} return 0;} 说明：使用输入输出重定向的办法，可以更方便地测试更大规模的数据。习题3-6 进制转换1（base1） 输入基数b（2<=b<=10）和正整数n（十进制），输出n的b进制表示。 【分析】 假设0 采取的策略是模拟手工转换的过程。关键是，在计算的过程中，从一维数组的低位开始向高位存储；而输出的时候，从高位开始向低位输出。 完整的程序如下： #include 第 72页 第3章 数组和字符串 int b, /*基数*/ n, /*正整数*/ i;int ans[100];/*结果*/ scanf(“%d%d”,&b,&n);i=0;while(n!=0){ ans[i]=n%b; n=n/b; i=i+1;} for(i=i-1;i>=0;i=i-1){ printf(“%d”,ans[i]);} return 0;}习题3-7 进制转换2（base2） 输入基数b（2<=b<=10）和正整数n（b进制），输出n的十进制表示。 【分析】 假设用户输入的数据都是合法的，假设n作为十进制来看待的时候，位数不超过19位。这时候，就需要用64位整数来存储n。例如，输入：3 212 输出：23 输入：2 101 输出：5 采用的策略是模拟手工计算的过程。采取的数据结构是本题的解决可以不采用数组的数据结构的，这样做似乎更加方便，代码更加简洁明了。但是由于本章讲的是数组。所以我使用一个一维数组，来存储输入的正整数n中的每一位。n的最低位，存放在数组下标为0的元素上，以此类推。 完整的程序如下： #include i,j,k;long long m, /*位权*/ n, /*b进制的正整数n*/ result;/*结果*/ int s[20];scanf(“%d%I64d”,&b,&n);/*printf(“%d% I64dn”,b,n);*/ /*测试代码*/ /*======= 把n的每一位存入一维数组 =================================*/ /*======= n的最低位，存放在数组下标为0的元素上，以此类推。========*/ i=0;while(n!=0){ s[i]=n%10; n=n/10; i=i+1;} result=0;m=1;for(k=0;k<=(i-1);k=k+1){ /*从下标0开始，向高位计算，可以节省计算位 第 73页 第3章 数组和字符串 权的时间*/ result=result+s[k]*m; m=m*b;/*计算更高一位的位权*/ } printf(“%I64d”,result);return 0;}习题3-8 手机键盘（keyboard）输入一个由小写字母组成的英文单词，输出用手机的默认英文输入法的敲键序列。例如要打出pig这个单词，需要按1次p，3次i，（稍作停顿后）1次g，记为p1i3g1（显然，书中这部分描述存在明显的错误，应以这里的描述为准）。 【分析】 假设用户总是能输入合法的英文单词（不包括空格、数字等）；单词的字符个数不超过300。 解题的策略是用一个一维数组的数据结构，来表示手机键盘。解题的步骤是：（1）读入单词，（2）从左至右其中的每一个字符，查询之前存储的“手机键盘”，输出查询的结果。完整的程序如下： #include word[300];int i, /*用于指向输入单词中的字符*/ j;/*用于指向键盘上的按键*/ gets(word);for(i=0;i j=0; while(pad[j+1]<=word[i])j=j+1; printf(“%c%d”,word[i],word[i]-pad[j]+1);} return 0;} 本 章 小 结 （1）本章先介绍了动态规划算法的基本步骤，然后通过10个典型的例子，介绍了动态规划算法的分析和设计的过程。 （2）动态规划方法是一种对具有重叠子问题的问题进行求解的技术。一般来说，这样的子问题出现在求解给定问题的递推关系中，这个递推关系中包含了相同类型的更小子问题的解。动态规划法建议，与其对重叠子问题的子问题一次又一次地求解，还不如对每个较小的子问题只解一次并把结果记录在表中，这样就可以从表中得出原始问题的解。 （3）对一个最优问题应用动态规划方法要求该问题满足最优性原则（最优性原则是动态规划求解问题的必要条件）：一个最优问题的任何实例的最优解是由该实例的子实例的最优解组成的。是否满足子问题的 （4）从算法的时间复杂度而言，动态规划通常设置地维以上数组，通过二重以上循环 2递推完成最优值求解，一般都在O(n)以上。 （5）当动态规划需设置三维数组时，其空间复杂度都比较高，大大限制求解的范围。随着问题维数的增加，其效率与求解范围受到限制。 第 74页 第3章 数组和字符串 布 置 作 业 习题3 3- 2、3- 3、3- 4、3- 5、3- 6、3-9题 第 75页 第4章 函数和递归 第4章 函数和递归 【教学内容相关章节】 4.1数学函数 4.2地址的指针 4.3递归 4.4本章小结 【教学目标】 （1）掌握多参数、单返回值的数学函数的定义和使用方法；（2）学会用typedef定义结构体；（3）学会用assert宏帮助调试； （4）理解函数调用时用实参给形参赋值的过程；（5）学会定义局部变量和全局变量； （6）理解调用栈和栈帧，学会用gdb查看调用栈并选择栈桢；（7）理解地址和指针； （8）理解递归定义和递归函数； （9）理解可执行文件中的正文段、数据段和BSS段；（10）熟悉堆栈段，了解栈溢出的常见原因。【教学要求】 掌握带参函数的调用、赋值过程及函数的返回值，理解地址和指针的概念，理解递归定义和递归函数，理解段的概念。【教学内容提要】 运用前3章的知识尽管在理论上已经足以写出多数算法程序了，但实际上稍微复杂一点的程序往往由多个函数组成。函数是“过程式程序设计”的产物，但也产生了局部变量、参数传递方式、递归等诸多新的知识点。本章淡化例题，重点在于理解最后的语法。同时，通过请出gdb这一王牌，从根本上帮助读者理解，看清事物的本质。【教学重点、难点】 教学重点： （1）掌握多参数、单返回值的数学函数的定义和使用方法；（2）理解函数调用时用实参给形参赋值的过程；（3）理解地址和指针； （4）理解递归定义和递归函数； （5）理解可执行文件中的正文段、数据段和BSS段。教学难点：贪心算法的基本要素。【课时安排（共3学时）】 4.1数学函数 4.2地址的指针 4.3递归 4.4本章小结 （0.5学时） 第 91 页 第4章 函数和递归 4.1 数学函数 4.1.1 简单函数的编写 下面给出一个计算两点欧几里德距离的函数： double dist(double x1, double y1, double x2, double y2){ return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));} 提示4-1：C语言中的数学函数可以定义成“返回类型 函数名(参数列表){ 函数体 }”，其中函数体的最后一条语句应该是“return 表达式；”。 提示4-2：函数的参数和返回值最好是“一等公民”int或double（注意char是一种特殊的int）。其他“非一等公民”作为以参数和返回值要复杂一些。 提示4-3：如果函数在执行的过程中碰到了return语句，将直接退出这个函数，不去执行后面的语句。相反，如果在执行过程中始终没有return语句，则会返回一个不确定的值。幸好，-Wall可以捕捉到这一可疑情况并产生警告。 main函数是有返回值的，假设返回值为0。main函数是整个程序的入口，如果有一个“其他的程序”来调用这个main函数——如操作系统、IDE、调试器，甚至自动评测系统，这个0代表“正常结束”，就是返回给这些调用者的。在算法竞赛中，除了有特殊规定之外，请总是让它返回0，以免评测系统错误地认为你的程序是异常退出。 提示4-4：在算法竞赛中，请总是让main函数返回0。下面给出上述函数的另一种方法： double dist(double x1, double y1, double x2, double y2){ double dx=x1-x2;double dy=y1-y2;return hypot(dx,dy);} 说明：（1）hypot函数的功能是计算一直角三角形的斜边长度。 （2）函数hypot(x,y)表示根据直角三角形的两直解边长度x和y计算其斜边的长度。或者是从标点(x,y)到原点的距离，该函数的算法等同于sqrt(x*x+y*y)。 4.1.2 使用结构体的函数 由于平面的点坐标(x,y)可以看用一个整体，所以可以定义一个结构体,它的名称是Point，让它包含点的坐标x和y。 struct Point{ double x, y;};double dist(struct Point a, struct Point b){ return hypot(a.x-b.x, a.y-b.y);} 提示4-5：在C语言中，定义结构体的方法为：“struct 结构体名称{ 域定义 };”,注意花括号的后面还有一个分号。 由于上面的定义在所有用到Piont的地方都得写一个“struct”，所以给出一个简洁的写法如下： typedef struct Point{ double x, y;}Point;double dist(Point a, Point b){ return hypot(a.x-b.x, a.y-b.y);} 提示4-6：为了方便，往往用“typedef struct{ 域定义 }类型名;”的方式定义一个新类型名。这样，就可以像原生数据类型一样使用这个自定义类型。 4.1.3 应用举例 例4-1 组合数。 第 92 页 第4章 函数和递归 输入非负整数m和n，输出组合数Cnmn!m!(nm)!，其中m≤n≤20。 【分析】 由组合数的公式可知，多次出现阶乘，所以将求阶乘作为一个函数： 程序4-1 组合数 #include int main(){ int m, n;scanf(“%d%d”, &m, &n);printf(“%dn”, f(n)/(f(m)*f(n-m)));return 0;} 注意：编好程序后，一定要别忘了测试程序。 提示4-7：即使最终答案在我们选择的数据类型范围之内，计算的中间结果仍然可能溢出。 例4-2 孪生素数。 如果n和n+2都是素数，则称它们是孪生素数。输入m，输出两个数均不超过m的最大孪生素数。5≤m≤10000。例如m=20时答案是17、19，m=1000时答案是881、883。 【分析】 被1和它自身整除的、大于1的整数称为素数。由于要判断n和n+2是否是素数，所以把“判断素数”可以写成一个函数，只需调用这个函数两次就可以了。这样的“判断一个事物是否具有某一性质”的函数还有一个学术名称——谓词（predicate）。 程序4-2 孪生素数（1） #include int main(){ int i, m;scanf(“%d”, &m);for(i = m-2;i >= 3;i--)if(is_prime(i)&& is_prime(i+2)){ printf(“%d %dn”, i, i+2);break;} 第 93 页 第4章 函数和递归 return 0;} 说明：（1）在is_prime函数的编写中，用到了两上小技巧。一是只判断不超过sqrt(x)的整数i；二是及时退出：一旦发现x有一个大于1的因子，立刻返回0（假），只有最后才返回1（真）。 （2）函数的命名应注意做到“见名知意”，即选有含义的英文单词（或其缩写）作为函数名。例如，“is_prime”取自英文“is is a prime?”（它是素数吗？）。 提示4-8：建议把谓词（用来判断某事物是否具有某种特性的函数）命名成“is_xxx”的形式。它返回int值，非0表示值，0表示假。 提示4-9：编写函数时，应尽量保证它能对任何合法参数都能得到正确的结果。如若不然，应在显著位置标明函数的缺陷，以避免误用。 下面改进之后的版本： 程序4-3 孪生素数（2） #include int main(){ int i, m;scanf(“%d”, &m);for(i = m-2;i >= 3;i--)if(is_prime(i)&& is_prime(i+2)){ printf(“%d %dn”, i, i+2);break;} return 0;} 除了特判n==1的情况外，程序中还使用了变量m，一方面避免了每次重复计算sqrt(x)，另一方面也通过四舍五入避免了浮点误差。 最后，程序使用了assert.h的assert宏来限制非法的函数调用：当x>=0不成立时，程序将异常终止，并给出了提示信息。 说明：（1）断言（assert）的语义如下：如果表达式的值为0（假），则输出错误消息并终止程序的执行（一般还会出对话框，说明在什么地方引发了assert）；如果表达式为真，则不进行任何操作。因此，断言失败就表明程序存在一个bug。 （2）C/C++的宏（assert）就是这样的断言，当表达式为假时，调用库函数abort()终止程序。 （3）程序中可以把assert看成一个在任何系统状态下都可以安全使用的无害测试手段，所以不要把程序中的assert语句删除掉。 （4）如果程序在assert处终止了，并不是说含有该assert的函数有错误，而是调用函数出了差错，assert可以帮助我们追踪到错误发生的原因。 （5）在函数的入口处，建议使用断言来检查参数的有效性（合法性）。请给assert语句加注释，告诉人们assert语句究竟要干什么。 第 94 页 第4章 函数和递归 提示4-10：编程时合理利用assert宏，将给调试带来很大的方便。总而言之，在实际的系统中，“一个地方的参数错误就引起整个程序异常退出”是不可取的，在编写和调试算法程序中，assert会“迫使”编写出更高质量的程序。 4.2 地址和指针 有时候，我们编程时为了完成某些操作——如交换两个变量，或者需要返回两个甚至更多的值——如解一个二元一次方程组。 4.2.1 变量交换 程序4-4 用函数交换变量（错误） #include int main(){ int a = 3, b = 4;swap(3, 4);printf(“%d %dn”, a, b);return 0;} 说明：（1）下面来说一下函数调用的过程： ①计算参数的值（若是数学表达式，需要计算）。程序4-4中函数调用语句swap(a, b);中的a和b就是实际参数（简称实参），它们的值分别为3和4。实参可以是常量、变量或表达式。 ②把实参赋值给函数声明中的a和b。函数声明中的a和b称为形式参数（简称形参）。然后在函数内部完成计算或操作。注意实参向形参的数据传递是“值传递”，即单向传递，只由实参传给形参，而不能由形参传回来给实参。 （2）下面来说一下几个概念： ①局部变量（local variable） 函数（包括main函数）的形参和在该函数里定义的变量都被称为该函数的局部变量。不同的局部变量相互独立，无法访问其他函数的局部变量，也就是说，局部变量只能在定义它的函数内部使用，超出了局部变量的作用域范围，局部变量是无效的。 局部变量的存储空间是临时分配的，函数执行完毕时，局部变量的空间将被释放，其中的值无法保留到下次使用。 ②静态局部变量（static local variable） 有时希望函数中的局部变量的值在函数调用结束后不消失而保留原值，这时就应该指定局部变量为“静态局部变量”，用关键字static进行声明。 静态局部变量在程序整个运行期间都不释放，而局部变量在函数调用结束后即释放。静态局部变量在编译时赋初值，即只赋初值一次；而对自动变量赋初值是在函数调用时进行，每调用一次函数重新给一次初值，相当于执行一次赋值语句。 如果在定义局部变量时不赋初值的话，则对静态局部变量来说，编译时自动赋初值0（对数值型变量）或空字符（对字符变量）。而对自动变量来说，如果不赋初值则它的值是一个不确定的值。 静态局部变量在函数调用结束后仍然存在，其它函数是不能引用它们的。③全局变量（global variable） 将变量写在所有函数的外面，这样的变量是全局变量。全局变量可以在任何时候，由任何函数访问。如果某局部变量和某个全局变量的名字一样，那么在该局部变量的作用域中，起作用的是局部变量，全局变量被同名的局部变量屏蔽掉了，不起作用。 需要注意的是，全局变量是非常危险的，应该谨慎使用。 第 95 页 第4章 函数和递归 提示4-11：函数的形参和在函数内声明的变量都是该函数的局部变量。无法访问其他函数的局部变量。局部变量的存储空间是临时分配的，函数执行完毕时，局部变量的空间将 释放，其中的值无法保留到下次使用。在函数外声明的变量是全局变量，它们可以被任何函数使用。操作全局变量有风险，应谨慎使用。 下面就变量的生存期和可见性给出一个例子。 例4-3 写出下面程序的运行结果。#include void other(){ static int a=2;static int b;/*a,b为静态局部变量，具有全局寿命，局部可见，只第一次进入函数进入 函数时初始化*/ int c=10;/*c为局部变量，具有动态生存期，每次进入函数时都初始化*/ a=a+2;i=i+32;c=c+5;printf(“-----OTHER------n”);printf(“i:%d a:%d b:%d c:%dn”,i,a,b,c);b=a;} 解答： 运行结果为如下：-------Main--------i:1 a:0 b:-10 c:0------Other--------i:33 a:4 b:0 c:15-------Main--------i:33 a:0 b:-10 c:8-------Other-------i:75 a:6 b:4 c:15 4.2.2 调用栈 调用栈描述的是函数之间的调用关系。它由多个栈帧（Stack Frame）组成，每个栈帧对应着一个未运行完的函数。栈帧中保存了该函数的返回地址和局部变量，因而不仅能在执行完毕后找到正确的返回地址，还很自然地保证了不同函数的局部变量互不相干——因为不同函数对应着不同的栈帧。 第 96 页 第4章 函数和递归 提示4-12：C语言调用栈（Call Stack）来描述函数之间的调用关系。调用栈由栈帧（Stack Frame）组成，每个栈帧对应着一个未运行完的函数。在gdb中可以用backtrace（简称bt）命令打印所有栈帧信息。若要用p命令打印一个当前栈帧的局部变量，可以用frame命令选择另一个栈帧。 下面给出用gdb完成上述操作的命令和结果。（1）第一步：编译程序。gcc 4-4.c-g（2）第二步：运行gdb。gdb a.exe 这样，gdb在运行时会自动装入刚才生成的可执行程序。（3）第三步：查看源码。(gdb)l 这里(gdb)是gdb的提示符，字母l是输入的命令，它是list（列出程序清单）的缩写。（4）第四步：加断点并运行。(gdb)b 4(gdb)r 其中b命令把断点设在了第4行，r命令运行程序，之后碰到了断点并停止。接下来，查看调用栈。 （5）第四步：查看调用栈。(gdb)bt(gdb)p a(gdb)p b(gdb)up(gdb)p a(gdb)p b 这一步是关键。根据bt命令，调用栈中包含两个栈帧：0#和1#，其中0号是当前栈帧——swap函数，1号是它的“上一个”栈帧——main函数。 使用p命令可以打印变量值。p a和p b表示查看当前栈帧中变量a和b的值。up命令表示选择上一个栈帧。然后用p a和p b查看当前栈帧中变量a和b的值。最后用q命令退出gdb。 说明：gdb是GNU开源组织发布的一个强大的UNIX下的程序调试工具。或许，大家比较喜欢那种图形界面方式的，像VC、BCB等IDE的调试，但如果是在 UNIX平台下做软件，会发现gdb这个调试工具有比VC、BCB的图形化调试器更强大的功能。 4.2.3 用指针实现变量交换 程序4-4不能实现两个变量的值交换，用指针可以实现两个变量的值交换。 程序4-5 用函数交换变量（正确） #include int main(){ int a = 3, b = 4;swap(&a, &b);printf(“%d %dn”, a, b);return 0;} 语句swap(&a, &b);中变量名前面加&得到的是该变量的地址。 提示4-13：C语言的变量都是放在内存中的，而内存中的每个字节都有一个称为地址（address）的编号。每个变量都占有一定数目的字节（可用sizeof运算符获得），其中第一个字节的地址称为变量的地址。 第 97 页 第4章 函数和递归 提示4-14：用int* a声明的变量a是指向int型变量的指针。赋值a=&b的含义是把变量b的地址存放在指针a中，表达式*a代表a指向的变量，它既可以放在赋值符号的左边（左值），也可以放在右边（右值）。 提示4-15：千万不要滥用指针，这不仅会把自己搞糊涂，还会让程序产生各种奇怪的错误。事实上，本书的程序会很少用指针。 4.2.4 初学者易犯的错误 一种典型的错误写法是： void swap(int* a, int* b){ int *t = a;a = b;b = t;} 它交换了swap函数的局部变量a和b（辅助变量t必须是指针。int a是错误的），但却始终没有修改它们指向的内容，因此main函数中的a和b不会改变。 另一种错误写法是： void swap(int* a, int* b){ int *t;*t = *a;*a = *b;*b = *t;} 这个程序去替换程序4-5，可能得到的结果是“4 3”。但是它还是错误的，因为t是一个变量（指针也是一个变量，只不过类型是“指针”而已），所以根据规则，它在赋值之前是不确定的。如果这个“不确定的值”所代表的内存单元恰好是能写入的，那么这个程序将正常工作；但如果它是只读的，程序可能会崩溃。 4.3 递 归 4.3.1 递归的定义和递归函数 1．基本概念 一个函数在它的函数体内调用它自身称为递归调用。这种函数称为递归函数。Ｃ语言允许函数的递归调用。在递归调用中，主调函数又是被调函数。执行递归函数将反复调用其自身，每调用一次就进入新的一层。例如： int f(int x){ int y;z=f(y);return z;} 本函数是一个递归函数。但是运行该函数将无休止地调用其自身，这当然是不正确的。这个递归函数是一个死递归（无限递归，Infinite Recursion）函数。为了防止递归调用无终止地进行，必须在函数内有终止递归调用的手段。常用的办法是加条件判断，满足某种条件后就不再作递归调用，然后逐层返回。 2．递归函数的构成要素 递归函数必须满足两个条件： （1）必须有一个终止准则（递归的边界条件、递归的结束条件）； （2）在每一次调用自己时，必须是（在某种意义上）更接近于解（递推公式或递归方程）； 边界条件与递归方程是递归函数的二个要素。若没有条件（1），则递归无从终止；若没有条件（2），则不是递归。 3．递归调用过程（两个阶段）（1）递推阶段 将原问题不断地分解为新的子问题，逐渐从未知的向已知的方向推进，最终达到已知的条件，即递归结束条件，这时递推阶段结束。 （2）回归阶段 第 98 页 第4章 函数和递归 从已知条件出发，按照“递推”的逆过程，逐一求值回归，最终到达“递推”的开始处，结束回归阶段，完成递归调用。 例4-4 用递归法计算n!。 用递归法计算n!，阶乘函数f(n)=n!可定义为： ff(0)=1(n)f(n1)n(n1)【分析】 本题是一个递归问题。下面给出求f(5)的递归过程如下：（1）递推过程 f(5)=5×f(4)→f(4)=4×f(3)→f(3)=3×f(2)→f(2)=2×f(1)→f(1)=1×f(0)→f(0)=1 未知----→已知（2）回归过程 f(5)=5×f(4)←f(4)=4×f(3)←f(3)=3×f(2)←f(2)=2×f(1)←f(1)=1×f(0)← f(0)=1 =120 =24 =6 =2 =1 未知←---已知 对应的程序如下： 程序4-6 用递归计算阶乘 #include int main(){ printf(“%dn”, f(3));return 0;} 提示4-16：C语言支持递归——函数可以直接或间接调用自己。但要注意为递归函数编写终止条件，否则将产生无限递归。 4.3.2 C语言对递归的支持 可以借助于gdb来调试程序4-6。首先用bf命令设置断点——除了可以按行号设置外，也可以直接给出函数名，断点将设置在函数的开头。可以用r命令运行程序，并在断点处停下来，接下来用s命令单步执行。 每次执行完s指令，都会有一层递归调用终止，直到返回main函数。事实上，如果在递归调用初期查看调用栈，会发现每次递归调用都会多一个栈帧——和普通的函数调用并没有什么不同。确实如此，由于使用了调用栈，C语言自然支持了递归。在C语言的函数中，调用自己和调用其他函数并没有任何本质区别，都是建立新栈帧，传递参数并修改“当前代码行”，在函数体执行完毕后删除栈帧，处理返回值并修改“当前代码行”。 提示4-17：由于使用了调用栈，C语言支持递归。在C语言中，调用自己和调用其他函数并没有本质不同。 4.3.3 段错误与栈溢出 “段”（segmentation）是指二进制文件内的区域，所有某种特定类型信息被保存在里面。可以用size程序得到可执行文件中各个段的大小。 提示4-18：在可执行文件中，正文段（Text Segment）储存指令，数据段（Data Segment）储存已初始化的全局变量，BSS段（BSS Segment）储存未赋值的全局变量所需的空间。 调用栈所在的段为堆栈段（Stack Segment）。和其他段一样，它也有自己的大小，不能被越界访问，否则就会出现段错误（Segment Fault）。 每次递归调用都需要往调用栈里增加一个栈帧，久而久之就越界了。用术语把它叫做栈溢出（Stack Overflow）。 提示4-19：在运行时，程序会动态创建一个堆栈段，里面存放着调用栈，因此保存着函数的调用关系和局部变量。 第 99 页 第4章 函数和递归 栈空间与操作系统有关。在Linux中，栈大小是由系统命令ulimit指定的，例如ulimit –a显示当前栈大小，而ulimit-s 32768将把栈大小指定为32MB。但在Windows中，栈大小是储存在可执行文件的。使用gcc可以这样指定可执行文件的栈大小：gcc –Wl,--stack =16777216，这样栈大小就变为16MB。 提示4-20：在Linux中，栈大小并没有储存在可执行程序中，只能用ulimit命令修改；在Windows中，栈大小储存在可执行程序中，用gcc编译时可以通过-Wl,--stack= 说明：（1）在介绍数组时，“把较大的数组放在main函数外”是因为这样定义的数组是全局数组，放在数据段。 （2）局部变量放在堆栈段。栈溢出不见得是递归调用太多，也可能是局部变量太大。只要总大小超过了允许的范围，就会产生栈溢出。 4.4 本 章 小 结 本章涉及了整个C语言中最难理解的两个东西：指针和递归。4.4.1 小问题集锦 首先，来编写一个函数solve，给定浮点数a,b,c,d,e,f，求解方程组ax+by=c,dx+ey=f。【分析】 下面利用线性代数知识来分析方程组的什么时候有唯一解、无解或无穷多解？方程组为如下： axbyc dxeyf设它的系数矩阵为A=行变换如下： a ba b c，它的增广矩阵为B=[A ]=b，对B实施初等d ed e fa b ca b cB= d e f0 ea-bd fa-cd（1）当ea-bd≠0时，系数矩阵A的秩R(A)=2，增广矩阵的秩R(B)=2,即R(A)=R(B)=2，此时线性方程组有唯一解。 cebfxeabd afcdyeabd（2）当ea-bd=0时 ①当fa-cd=0时，R(A)=R(B)=1<2,此时线性方程组有无穷多组解。 ②当fa-cd≠0时，R(A)=1，R(B)=2,则R(A) 函数solve如下： void solve(float a, float b, float c, float d, float e, float f){ float x, y;assert(e * a – b * d== 0 && f * a – c * d== 0);//使用断言，解不唯一退出 if(e * a – b * d!= 0){ //此方程的解是唯一的 printf(“The solution of equation is unique:n ”);printf(“x=%f”,(c * e – b * f)/(e * a – b * d));printf(“y=%f”,(a * f – c * d)/(e * a – b * d));return; 第 100 页 第4章 函数和递归 } if(e * a – b * d == 0 && f * a – c * d!= 0){ //此方程无解 printf(“The equation is no solutio:n ”);return;} } 任务2：解不唯一时仍然正常返回，但调用者有办法知道解的数量（无解、唯一解、无穷多组解）。 解答： 函数solve如下： int void solve(float a, float b, float c, float d, float e, float f){ float x, y;if(e * a – b * d== 0 && f * a – c * d== 0){ //此方程的解是不唯一 printf(“The solution of equation is not unique:n ”);return 2;} if(e * a – b * d!= 0){ //此方程的解是唯一的 printf(“The solution of equation is unique:n ”);printf(“x=%f”,(c * e – b * f)/(e * a – b * d));printf(“y=%f”,(a * f – c * d)/(e * a – b * d));return 1;} if(e * a – b * d == 0 && f * a – c * d!= 0){ //此方程无解 printf(“The equation is no solutio:n ”);return 0;} } 然后，请编写一个程序，包含3个函数f()、g()和h()，3个函数均无参数，返回值均为int型。 任务1：定义int a,b，要求在依次执行a=f()和b=f()后，a和b的值不同。解答： 程序如下： #include int g(){ c++;return c;} int h(){ c++;return c; 第 101 页 第4章 函数和递归 } void main(){ int a,b;a=f();b=f();printf(“a=%,b=%d”,a,b);} 很显然，依次执行a=f()和b=f()后，a=2和b=3，a和b的值不同。任务2：定义int a,b，要求在依次执行a=(f()+g())+h()和b=f()+(g()+h())后，a和b的值不同。 解答：将上面的程序a=f();和b=f();，换成a=(f()+g())+h()和b=f()+(g()+h())。很显然，依次执行a=(f()+g())+h()和b=f()+(g()+h())后，a=9和b=18，a和b的值不同。 接下来做两个编程探索。 问题1：局部变量是否可以和全局变量重名？如果可以，实际上使用的是哪个？这可能会引起什么样的难以察觉到的错误？ 解答：局部变量可以和全局变量同名，但在局部变量的作用域内，实际上使用是局部变量，全局变量失效。 问题2：如果在函数中声明一个局部变量，然后返回它的地址，调用者获取该地址时，该地址是否是有效的？为什么？ 解答：该局部变量的地址是无效的。因为局部变量的存储空间是临时分配的，函数执行完毕时，局部变量的空间将被释放。 4.4.2 小结 本章介绍了数组和指针，尽管它们在很多地方可以混用，但指针和数组不是一回事。要尽量回避指针。 递归要从从概念和语言两个方面理解。从概念上，递归就是“自己使用自己”的意思。递归调用就是自己调用自己，递归定义就是自己定义自己。“使用自己”可以是直接的，也可以是间接的。由于重点是设计算法和编写程序，理解递归函数的执行过程是非常重要的。 布 置 作 业 习题1 请写出下列程序的输出结果。程序如下： #include void main(){ print(3);putchar(“n”); 第 102 页 第4章 函数和递归 } 解答：输出结果如下： 1 2 2 3 3 3习题2 用递归方法求解下面问题。 有5个人坐在一起，问第5个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第3个人，又说比第2个人大2岁。问第2个人，说比第1个人大2岁。最后问第1个人，他说是10岁。请问第5个人多大。 【分析】 本题是一个递归问题。若第i个人的年龄用age(i)表示，根据题意可得如下递推关系： age(5)=age(4)+2 age(4)=age(3)+2 age(3)=age(2)+2 age(2)=age(1)+2 age(1)=10 可以用数学公式表述如下： age(n)10 n=1 age(n-1)+2 n>1求第5个人的年龄的递归过程如下：（1）递推过程 age(5)=age(4)+2→age(4)=age(3)+2→age(3)=age(2)+2→age(2)=age(1)+2→age(1)=10 未知→已知（2）回归过程 age(5)=age(4)+2←age(4)=age(3)+2←age(3)=age(2)+2←age(2)=age(1)+2←age(1)=10 =18 =16 =14 =12 未知←------------------------------已知 程序如下（其中函数age是递归函数）： #include void main(){ printf(“%dn”,age(5));} 第 103 页 实验11：字符数组与字符串 一、实验目的1、理解字符数组和字符串的概念。 2、掌握字符数组的定义、初始、数组元素引用、输入输出。 3、掌握字符数组的处理 4、掌握常用字符串处理函数 二、实验内容 1、编制程序：对键盘输入的字符串进行逆序，逆序后的字符串仍然保留在原来字符数组中，最后输出。 （1）不得调用任何字符串处理函数，包括strlen； （2）允许使用可用的字符串处理函数。 例如：输入hello world 输出dlrow olleh2、编写程序：对键盘输入的两个字符串进行连接。 （1）尽管我们知道strcat()可以简单完成此任务，仍然规定不得调用任何字符串处理函数，包括strlen； （2）允许使用可用的字符串处理函数。 例如：输入hello （1）不得调用任何字符串处理函数，包括strlen； （2）允许使用可用的字符串处理函数。 例如：输入：Hello World!输出：hELLO wORLD! 三、实验小结 实验中碰到的问题，以及思考。 C语言字符串指针变量与字符数组的区别 用字符数组和字符指针变量都可实现字符串的存储和运算。但是两者是有区别的。在使用时应注意以下几个问题： 1)字符串指针变量本身是一个变量，用于存放字符串的首地址。而字符串本身是存放在以该首地址为首的一块连续的内存空间中并以 作为串的结束。字符数组现金网96y.org是由于若干个数组元素组成的，它可用来存放整个字符串。 2)对字符串指针方式 char *ps=C Language; 可以写为： char *ps; ps=C Language; 而对数组方式： static char st[]={C Language}; 不能写为： char st[20]; st={C Language}; 而只能对字符数组的各元素逐个赋值。 从以上几点可以看出字符串指针变量与字符数组在使用时的区别，同时也可看出使用指针变量更加方便。 前面说过，当一个指针变量在未取得确定地址前使用是危险的，容易引起错误。但是博彩娱乐棋牌q07i5.org对指针变量直接赋值是可以的。因为C系统对指针变量赋值时要给以确定的地址。 因此，char *ps=C Langage; 或者 char *ps; ps=C Language; 都是合法的。 一、教学内容：算法和算法的描述（选修1算法与程序设计 广东教育出版社） 二、教学课时：1课时 三、教学地点：计算机室2 四、教学目标： 1、知识目标 （1）明白算法的概念，理解算法的特征。（2）掌握算法描述的三种方法，能看懂流程图。（3）了解算法的意义，找出三种算法描述的优缺点。 2、技能目标 （1）知道在什么场合应该用什么算法描述。 （2）能对算法和算法的描述正确定位，能用算法解决实际问题，为学习后面的程序设计打下基础。 3、情感目标 （1）能把现实社会中的问题用算法描述出来，培养学生们的合作精神和想象能力，以提高学生们的信息素养。 五、教学方法：任务驱动法 六、教学重点： 算法的概念、描述算法的三种方法。 七、教学难点： 用流程图描述算法。 八、教学过程 1.激发兴趣、创设情景 这节课内容主要是一些概念和理论，而算法的概念和理论都太抽象，讲起来非常的枯燥乏味，那么就要把这些抽象的东西变得通俗易懂，使学生能轻松而又愉快的接受并理解。 举出一个例子如炒土豆丝如何做？引导学生们一步步说出步骤，最后教师总结：算法就是解决问题的方法和步骤。在以后的编程中也要记住了，有些步骤是可以颠倒的，不影响程序的结果；但是有些一但颠倒了那最终的结果也就全变了。 2.讲.解 激发学生的兴趣后对算法、算法的特征（确定性、有穷性）进行讲解，注意运用生活中的实例，以便让学生们理解。 讲述算法的三种描述方法：自然语言、流程图、伪代码。学生们比较熟悉的是自然语言，陌生难理解的是流程图和伪代码。 先带学生们了解自然语言，然后讲伪代码，讲完伪代码后，引导学生们如何把这些程序用流程图表示出来。流程图的基本图形及其功能 给出一个程序，让学生们先读这个程序，再用流程图表示这个程序如： Private Sub Command1_Click()a = InputBox(“输入数字”)If a Mod 2 = 0 Then Print a & “是偶数” Else Print a & “是奇数” End If End Sub 学生们自学后，由教师引导发现这是一个判断奇偶数的程序，找一个学生展示他的流程图，然后大家共同检查这个流程图是否正确。 九、课堂作业 再给学生们一个程序，让学生们读并且在word中画出流程图，然后教到主机上。 十、课后反思： 在本节课中进行任务驱动式教学，充分发挥学生的主观能动性。同时这节课内容多，而且难以理解，练习生活中的实例，既可以激发学生们的兴趣，又有助于知识的迁移和内化。第二篇：算法竞赛入门经典授课教案第4章 函数和递归
第三篇：实验：字符数组与字符串
第四篇：C语言字符串指针变量与字符数组的区别
第五篇：算法和算法描述教案
点击咨询 