算法竞赛入门经典授课教案第3章 数组和字符串.doc

第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学时） 3.1 数 组下面从一个问题出发，说明一下为何使用数组。问题：读入一些整数，逆序输出到一行中，已知整数不超过100个。【分析】首先通过循环来读取100个整数的输入，然后把每个数都存下来，存放在数组中，最后输出。程序3-1 逆序输出#include #define MAXN 100 + 10int aMAXN;int main() int i, x, n = 0; while(scanf(%d, &x) = 1) an+ = x; for(i = n-1; i = 1; i-) printf(%d , ai); printf(%dn, a0); return 0;说明：语句int a100声明了一个包含100个整型变量的数组，它们是：a0,a1,a2,a99。注意，没有a100。提示3-1：语句int aMAXN声明了一个包含MAXN个整型变量的数组，即a0,a1,a2,aMAXN-1，但不包含aMAXN。MAXN必须是常数，不能是变量。在本程序中，声明MAXN为100+10而不是100，主要是为了保险起见。提示3-2：在算法竞赛中，常常难以精确计算出需要的数组大小，数组一般会声明得稍大些。在空间够用的前提下，浪费一点不要紧。语句an+=x;的等价于两条语句an=x; n+;，循环结束后，数据被存在了a0,a1,an-1，其中变量n个整数的个数。在数组中存放整数后，依次输出an-1,an,a1和a0。一般要求输出的行首行尾均无空格，相邻两个数据间用单个空格隔开，一共需要输出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盏灯，编号为1n，第1个人把所有灯打开，第2个人按下所有编号为2的倍数的开关（这些灯将被关掉），第3个人按下所有编号为3的倍数的开关（其中关掉的灯被打开，开着灯将被关闭），依此类推。一共有k个人，问最后有哪些灯开着？输入：n和k，输出开着的灯编号。kn1000。样例输入：7 3样例输出：1 5 6 7【分析】用a1,a2,an表示编号为1,2,3,n的灯是否开着，模拟这些操作即可。代码如下：程序3-2 开灯问题逆序输出#include #include #define MAXN 1000 + 10int aMAXN; /* 一维数组存储n盏电灯 */int main() int i, j, n, k, first = 1; memset(a, 0, sizeof(a); /* 初始化电灯状态 */ scanf(%d%d, &n, &k); /* 模拟活动过程 */ for(i = 1; i = k; i+) /* 第i个人参与活动 */ for(j = 1; j = n; j+) /* 对第i盏灯进行操作 */ if(j % i = 0) aj = !aj; /* 输出活动结果 */ for(i = 1; i = n; i+) if(ai) if(first) first = 0; else printf( );printf(%d, i); printf(n); return 0;说明：（1）memset(a,0,sizeof(a)的作用是把数组a清零，它也在string.h中定义。使用memset比for循环更方便、快捷。memset函数原型如下：void *memset(void *buffer, char c, int count);它的功能是把buffer所指内存区域的前count个字节设置成字符c，第三个参数指的是字节的个数，返回指向buffer的指针，在程序中需包含头文件：#include 。由memset函数的头文件可以知道，其主要是对字符数组进行设置，当然也可以对数组进行初始赋值（一般是0,-1）。（2）有一个技巧是在输出：为了避免输出多余空格，设置了一个标志变量first，可以表示当前要输出的变量是否为第一个。第一个变量前不应有空格，但其他都有。例3-2 蛇形填数。在n*n方阵里填入1,2,n*n，要求填成蛇形。例如n=4时方阵为10 11 12 19 16 13 28 15 14 37 6 5 4上面的方阵中，多余的空格只是为了便于观察规律，不必严格输出。n8。【分析】与数学的矩相比，可以用一个所谓的二维数组来存储题目中的方阵。只需声明一个int aMAXNMAXN，就可以获得一个大小为MAXNMAXN的方阵。在声明时，两维的大小不必相同。提示3-4：用int aMAXNMAXN生成一个整型的二维数组，其中MAXN和MAXN不必相等。这个数组共有MAXNMAXN个元素，分别为a00,a01,a0MAXN-1,a10,a11,a1MAXN-1,aMAXN-10,aMAXN-11, aMAXN-1MAXN-1。假设从1开始依次填这写。设“笔”的坐标为(x,y)，则一开始x=0，y=n-1，即第0行第n-1列（注意行列的范围是0n-1，没有第n列）。“笔”的移动轨迹是：下、下、下、左、左、左、上、上、上、右、右、下、下、左、上。总之，先是下，到不能填了为止，然后是左，接着是上，最后是右。“不能填”是指再走就出界（例如45）或者再走就要走到以前填过的格子（例如1213）。如果把所有格式初始化为0，就能很方便地加以判断。程序3-3 蛇形填数#include#include#define MAXN 10int aMAXNMAXN;int main() int n, x, y, tot = 0; scanf(%d, &n); memset(a, 0, sizeof(a); tot = ax=0y=n-1 = 1; while(tot n*n) while(x+1=0 & !axy-1) ax-y = +tot; /* 向左走 */ while(x-1=0 & !ax-1y) a-xy = +tot; /* 向上走 */ while(y+1n & !axy+1) ax+y = +tot; /* 向右走 */ for(x = 0; x n; x+) for(y = 0; y n; y+) printf(%3d, axy); printf(n); return 0;说明：本程序利用了C语言的简洁的优势。首先，赋值x=0和y=n-1后马上作为a数组的下标，可以合并完成；tot和a0n-1都要赋值1，也可以合并完成。用一条语句可以完成多件事情，并且不有牺牲程序的可读性。提示3-5：可以利用C语言简洁的语法，但前提是保持代码的可读性。提示3-6：在很多情况下，最好是在做一件事之前检查是不是可以做，而不要做完再后悔。因为“悔棋”往往也比较麻烦。说明：本程序对于与x+1n类似的情况，像x+1是否越界？如果x+1n为假，&是短路运算符，将不会计算!ax+1y，也就不会越界了。3.2 字 符 数 组文本处理在计算机应用中占有重要地位。在C语言中，字符串其实就是字符数组可以像处理普通数组一样处理字符串，只需要注意输入输出和字符串函数的使用。例3-3 竖式问题。找出所有形如abc*de（三位数乘以两位数）的算式，使得在完整的竖式中，所有数字都属于一个特定的数字集合。输入数字集合（相邻数字之间没有空格），输出所有竖式。每个竖式前应有编号，之后应有一个空行。最后输出解的总数。具体格式见样例输出（为了便于观察，竖式中的空格改用小数点显示，但你的程序应该输出空格，而非小数点）。样例输入：2357样例输出：.775x.33-.23252325.-25575The number of solutions=1【分析】本题的解题策略是尝试所有的abc和de，判断是否满足条件。写出如下的伪代码： char s20; int count = 0; scanf(%s, s); for(abc = 111; abc = 999; abc+) for(de = 11; de = 99; de+) if(“abc*de”是个合法的竖式) printf(n, +count); 打印abc*de的竖式和其后的空行 count+; printf(The number of solutions = %dn, count);说明：（1）char s20是一个定义字符数组的语句，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 sMAXN MAXL,可以用scanf(%s,si)读取第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#includeint main() int i, ok, abc, de, x, y, z, count = 0; char s20, buf99; scanf(%s, s); for(abc = 111; abc = 999; abc+) 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, bufi) = NULL) ok = 0; if(ok) printf(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, bufi)的功能是查找字符串s中首次出字符bufi的位置。如果strchr(s, bufi)=NULL，则表明字符串s中没有bufi的字符。（3）sprintf函数、printf函数、fprintf函数的区别printf输出到屏幕，fprintf输出到文件，而sprintf输出到字符串。需要注意是应该保证写入的字符串有足够的空间。提示3-9：可以用sprintf把信息输出到字符串，用法和printf、fprintf类似。但你应当保证字符串足够大，可以容纳输出信息。字符串的空间应为字符个数加1，这是因为C语言的字符串是以空字符0结尾的。函数strlen(s)的作用是获取字符串s的实际长度，即函数strlen(s)返回的是结束标记之前的字符个数。因此这个字符串中的各个字符依次是s0,s1,sstrlen(s)-1，而sstrlen(s)正是结束标记0。提示3-10：C语言中的字符串是0结尾的字符数组，可以用strlen(s)返回字符串s中结束标记之前的字符个数。字符串中的各个字符是：s0,s1,sstrlen(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：滥用+、-、+=等可以修改变量值的运算符很容易带来隐蔽的错误。建议每条语句最多只用一次这种运算符，并且它所修改的变量在整条语句中只出现一次。提示3-13：但编译选项-Wall编译程序时，会给出很多（但不是所有）警告信息，以帮助程序员查错。但并不能解决所有的问题：有些“错误”程序是合法的，只是这些动作不是你所期望的。3.3 最长回文子串例3-4 回文串。输入一个字符串，求出其中最长的回文子串。子串的含义是：在原串中连续出现的字符串片段。回文的含义是：正着看和倒着看相同。如abba和yyxyy。在判断时，应该忽略所有标点符号和空格，且忽略大小写，但输出应保持原样（在回文串的首部和尾部不要输出多余字符）。输入字符串长度不超过5000，且占据单独的一行。应该输出最长的回文串，如果有多个，输出起始位置最靠左的。样例输入：Confuciuss say:Madam,Im Adam.样例输出：Madam,Im 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 bufMAXN。这个函数读取不超过MAXN-1个字符，然后在末尾上结束符0，因此不会出现越界的情况。之所以说可以用这个函数读取完整的一行，是因为一旦读到回车符n,读取工作将会停止，而这个n也会是buf字符串中最后一个有效字符（再往后就是字符串的结束符0了）。只有一种情况下，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 s100，你完全可以赋值s10000=a（甚至-Wall也不会警告），但后果自负。提示3-18：C语言中的gets(s)存在缓冲区溢出漏洞，不推荐使用。选择fgets函数可以解决“输入有空格”的问题，它可以一次性读取一行，最为方便。接下来，解决“判断时忽略标点，输出进却要按原样”的问题，可以用一个通用的方案：预处理。构造一个新字符串，不包含原来的标点符号，而且所有字符变成大写（顺便解决了大小写的问题）：n = strlen(buf);m=0;for(i = 0; i n; i+) if(isalpha(bufi) sm+ = toupper(bufi);说明：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是否为数字（09），如果是数字，则返回1；否则返回0。（3）isprint(c)用来检查c是否为可打印字符（不包括空格），其ASCII码值在0x210x7e之间，如果是可打印字符，则返回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 max) max = j-i+1;“当前最大值”变量max，它保存的是目前为止发现的最长回文子串的长度。如果串s的第i个字符到第j个字符（记为si.j）是回文串，则检查长度j-i+1是否超过max。最后，判断si.j是否为回文串的方法如下：int ok = 1;for(k = i; k = j; k+) if(sk != si+j-k) ok = 0;sk的“对称”位置是si+j-k，因为只要一次比较失败，就应把标记变量ok置为0。完整的程序如下：程序3-5 最长回文子串（1）#include #include #include #define MAXN 5000 + 10char bufMAXN, sMAXN;int main() int n, m = 0, max = 0; int i, j, k; fgets(buf, sizeof(s), stdin); n = strlen(buf); for(i = 0; i n; i+) if(isalpha(bufi) sm+ = toupper(bufi); for(i = 0; i m; i+) for(j = i; j m; j+) int ok = 1; for(k = i; k max) max = j-i+1; printf(max = %dn, max); return 0;在实际编程时，经常先编写一个具备主要功能的程序，再加以完善。甚至可以先写一个只有输入输出功能的“骨架”，但是要确保它正确。这样，每次只添加一点点功能，而且写一点就测试一点，和一次写整个程序相比，更加不容易出错。这种方法称为迭代式开发。提示3-21：在程序比较复杂时，除了在设计阶段可以用伪代码理清思路外，编码阶段可以采用迭代时开发每次只实现一点小功能，但要充分测试，确保它工作正常。程序3-5能顺利求出样例数据中最长回文串的长度。现在接下来的任务是输出这个回文串：要求原样输出，并且尽量靠左。由于是从左到右枚举的，所以现在只剩下唯一的问题：原样输出。由于在求max值时，不知道si和sj在原串buf中的位置。因此，必须增加一个数组p，用pi保存si在buf中的位置。在预处理得到，然后在更新max的同时把pi和pj保存到x和y，最后输出bufx到bufy中的所有字符。但是上面的方法发现速度很慢，所以换一种方式：枚举回文串的“中间”位置i，然后不断往外扩展，直到有字符不同。提示：长度为奇数和偶数的处理方式是不一样的。完整的程序如下：程序3-6 最长回文子串（2）#include#include#include#define MAXN 5000 + 10char bufMAXN, sMAXN;int pMAXN;int main() int n, m = 0, max = 0, x, y; int i, j; fgets(buf, sizeof(s), stdin); n = strlen(buf); for(i = 0; i n; i+) if(isalpha(bufi) pm = i; sm+ = toupper(bufi); for(i = 0; i = 0 & i+j max) max = j*2+1; x = pi-j; y = pi+j; for(j = 0; i-j = 0 & i-j+1 max) max = j*2+2; x = pi-j; y = pi+j+1; for(i = x; i =a & ch=A & ch=0 & ch=9) return 1; else return 0;3.4.5 字符串处理的常见问题tot=1;for(i = 0; i strlen(s); i+) if(si = 1) tot+;printf(There are %d character(s) 1 in the string.n,tot);本程序的功能是统计字符串中字符1的个数。实验1：添加字符串s的声明语句，长度不小于107。提示：放在main函数内还是外？ 解答：添加字符串s的声明语句如下：#define MAXN 10000000char sMAXN;应放在main函数外。实验2：添加读取语句，测试上述程序是否输出了期望的结果。如果不是，请改正。 解答：得不到期望的结果，改正如下： if(si = 1) tot+; 改为if(si = 1) tot+;实验3：把输入语句注释掉，添加语句，用程序生成一个长度至少为105的字符串，并用程序验证字符串长度确实不小于105。 解答：程序如下：#include #include #define MAXN 10000000char sMAXN;int main() int i,tot=0; /* gets(s); 从键盘输入一个字符串给s */ for(i = 0; i 100000; i+) /* 用程序生成一个长度至少为105的字符串 */ si = 1; for(i = 0; i strlen(s); i+) if(si = 1) tot+; printf(There are %d character(s) 1 in the string.n,tot); return 0;实验4：用计时函数测试这段程序的运行时间随着字符串长度的变化规律。如何改进？ 解答：程序如下：#include #include #include #define MAXN 10000000char sMAXN;int main() int i,tot=0;clock_t start, finish; start=clock(); for(i = 0; i 1000000; i+) si = 1; for(i = 0; i strlen(s); i+) if(si = 1) tot+; printf(There are %d character(s) 1 in the string.n,tot);finish=clock(); printf(Time used=%.5lf secondsn,(finish-start)/(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 关于输入输出1getchar函数当程序请求键盘输入时，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。2sscanf函数（1）sscanf()表示从一个字符串中读取与指定格式相符的数据。它的函数原型如下：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 #include using namespace std;int main() string s; while(cin s) count s n; return 0;注意：（1）这里声明的是C+中的字符串，否则无法使用输入输出流。（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 using namespace std;int main() int ch; while(ch=getchar() != EOF