算法竞赛入门经典算法实现pdf,算法竞赛基础
目录
第三章数组与字符串3.1数组程序3-1逆序输出示例3-1开灯。程序3-2开灯问题，逆序输出。例3-2蛇形数字填充。程序3-3蛇填充
3.2字符数组例题3-3竖排问题。程序3-4竖排问题3.3最长回文子串示例3-4回文子串。程序3-5最长回文子串(1)程序3-6最长回文子串(2) 3.4总结和练习3.4.1必要的存储3.4.2用ASCII编码表示字符3.4.3补码表示法3.4.4库函数的重新实现3.4.5字符串处理常见问题实验1:添加字符串S的声明语句，无长度提示：在主函数内部还是外部？实验二：添加一条阅读语句，测试上面的程序是否输出了想要的结果。如果没有，请改正。实验三：注释掉输入的语句，添加语句，用程序生成长度至少为105的字符串，用程序验证字符串长度不小于105。实验四：用带计时功能的字符串的长度来检验这个程序运行时间的规律。如何改善？3.4.6关于I/O 1.getchar函数2.sscanf函数3.4.7 I/O效率3.4.8总结3.4.9练习3-1分数统计(stat)任务1:分数均为不超过100的非负整数。任务二：分数都是不超过100的非负实数，最多保留两位小数。练习3-2单词的长度(word)练习3-3乘积的最后3位数字练习3-4计算器练习3-5旋转练习3-6二进制转换1(base1)练习3-7二进制转换2(base2)练习3-8手机键盘
第3章数组和字符串[与学习内容相关的章节]
3.1数组3.2字符数组3.3最长回文子串3.4小结和练习
[学习目标]
(1)掌握一维数组的声明和用法；
(2)掌握二维数组的声明和用法；
(3)掌握字符串的声明、赋值、比较和连接方法；
(4)熟悉ASCII码和ctype.h的人物；
(5)正确理解可以修改变量的运算符，如=；
(6)学会编译option -Wall，获取更多的预警信息；
(7)掌握fgetc和getchar的用法；
(8)了解换行在不同操作系统中的表示方式；
(9)掌握fgets的用法，了解gets的“缓冲区溢出”漏洞；
(10)了解预处理和迭代开发的技巧。
[学习要求]
(1)掌握一维数组和二维数组的声明和用法；
(2)掌握字符串的语句及相关操作；
(3)掌握fgetc和getchar的用法；
(3)掌握fgets和gets的用法。
[学习总结]
通过第二章的学习，我们了解到了计算机的计算优势，但是没有充分发挥计算机的存储优势。只使用了少数几个变量。有些程序虽然也处理大量数据，但这些数据只是“过客”，只参与计算，不保存。
本章介绍了数组和字符串，两者都可以存储大量的数据。字符串是数组(字符数组)，但由于其特殊的应用，适合一些特殊的处理方法。
【学习的重点和难点】
学习重点：
(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输出#以相反顺序包含
#定义MAXN 100 10
int a[MAXN]；
int main() {
int i，x，n=0；
while (scanf(%d ，x)==1)
a[n]=x；
for(I=n-1；我我-)
printf(%d ，a[I])；
printf(%d\n ，a[0])；
返回0；
}描述：
语句int a[100]声明一个包含100个整型变量的数组，分别是：a[0]，a[1]，a[2]，…，a[99]。注意没有a[100]。
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指示的存储区复制到dest指示的存储区。src和dest指示的内存区域不能重叠，函数返回一个指向dest的指针。主要功能是复制字符串，也可以对数组进行操作。头文件：#include string.h应该包含在程序中。
例3-1开灯。灯有n个，编号从1到n，第一个人打开所有的灯，第二个人按下所有编号为2的倍数的开关(这些灯会熄灭)，第三个人按下所有编号为3的倍数的开关(熄灭的灯点亮，点亮的灯熄灭)，以此类推。总共有k个人。最后亮着什么灯？
输入：n和k，输出亮着的灯的数量。kn1000 .
样本输入：7 3
样本输出：1 5 6 7
[分析]
用a[1]，a[2]，…，a[n]表示编号为1，2，3，…，n的灯是否亮。只是模拟这些操作。
代码如下：
程序3-2开机问题#的反向输出包括
#包括
#定义MAXN 1000 10
int a[MAXN]；/*一维数组存储N个电灯*/
int main() {
int i，j，n，k，first=1；
memset(a，0，sizeof(a))；/*初始化灯光状态*/
scanf(%d%d ，n，
/*模拟活动过程*/
for(I=1；I)/*第I个人参加活动*/
for(j=1；J)/*操作第I个灯*/
if (j % i==0) a[j]=！a[j]；
/*输出活动结果*/
for(I=1；我我)
if (a[i]) {
if(first)first=0；
else printf( )；
printf(%d ，I)；
}
printf( \ n )；
返回0；
}描述：(1)memset(a，0，sizeof(a))用于清空数组A，数组A也是在string.h中定义的，memset比for循环更方便快捷。
Memset函数原型如下：
void *memset(void *buffer，char c，int count)；
它的作用是将buffer指向的内存区域的第一个count字节设置为字符C，第三个参数是指字节数，返回一个指向buffer的指针。头文件：#include string.h应该包含在程序中。从memset函数的头文件可以知道，它主要是设置字符数组，当然也可以对数组进行初始赋值(一般是0，-1)。
(2)一招输出：为了避免输出多余的空格，设置了一个标志变量first，可以表示当前要输出的变量是否为第一个。第一个变量前不应该有空格，其他都是。
例3-2蛇形填充。在nn方阵中填入1，2，…，NN，要求填入一个蛇形。例如，当n=4时，方阵为
10 11 12 1
9 16 13 2
8 15 14 3
7 6 5 4
上面的方阵中，多出来的空格只是为了方便遵守规则，没必要严格输出。n8 .
[分析]
相对于数学中的矩，可以用一个所谓的二维数组来存储题目中的方阵。只要声明一个int a[MAXN][MAXN]，就可以得到一个大小为MAXNMAXN的方阵。在声明的时候，两个维度不一定要一样大。
技巧3-4:用int a[MAXN][MAXN]生成一个二维整数数组，其中MAXN和MAXN不必相等。这个数组中有MAXNMAXN个元素，分别是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].
假设你从1开始，依次填写这个写法。设“笔”的坐标为(x，y)，那么首先x=0，y=n-1，即第0行，第n-1列(注意行列的范围是0 ~ n-1，没有第n列)。笔的运动轨迹是：下，下，左，左，上，上，右，右，下，下，左，上。一句话，先是往下，直到填不完，然后向左，再往上，最后向右。“不能填”是指出界(如45)或去之前填好的格子(如1213)。如果所有格式都初始化为0，就很容易判断了。
程序3-3蛇形填充#包括
#包括
#定义最大数量10
int a[MAXN][MAXN]；
int main() {
int n，x，y，tot=0；
scanf(%d ，
memset(a，0，sizeof(a))；
tot=a[x=0][y=n-1]=1；
while (tot n * n) {
while (x 1 n！a[x ^ 1][y])a[x][y]=tot；/*下去*/
while (y - 1=0！a[x][y-1])a[x][-y]=tot；/*向左*/
while (x - 1=0！a[x-1][y])a[-x][y]=tot；/*向上*/
while (y 1 n！a[x][y ^ 1])a[x][y]=tot；/*向右走*/
}
for(x=0；x x ) {
for(y=0；y y ) printf(=，a[x][y])；
printf( \ n )；
}
返回0；
}描述：这个程序利用了C语言的简单性。首先，赋值x=0，y=n-1作为数组A的下标可以组合。Tot和a[0][n-1]都应该被赋值为1，或者它们可以被组合。您可以用一条语句完成许多事情，而不会牺牲程序的可读性。
技巧3-5:你可以利用C语言简洁的语法，但前提是代码是可读的。
技巧3-6:很多情况下，最好在做某件事之前先检查一下这件事能不能做，而不是做了之后再后悔。因为“后悔棋”往往更麻烦。
说明：对于类似于x 1 n的情况，比如x 1，这个过程是不是越界了？如果x ^ 1n为假，是短路算符，则不计算！A[x 1][y]，也不会出格。
3.2字符号码组
文本处理在计算机应用中起着重要的作用。在C语言中，字符串实际上是字符数组——。可以像处理普通数组一样处理字符串，只需要注意输入输出和字符串函数的使用。
例3-3垂直问题。找出所有类似abc*de(三位数乘以两位数)的公式，这样在一个完整的竖式中，所有的数都属于一组特定的数。输入一组数字(相邻数字之间没有空格)，输出所有竖排形式。每条竖线前都要编号，后面是一个空行。最终输出解决方案的总数。具体格式见示例输出(为了便于观察，竖排形式中的空格以小数点显示，但你的程序应该输出空格而不是小数点)。
样本输入：2357
样本输出：
一个
.775
x.33
-
.2325
2325.
-
25575
解的数量=1【解析】
本题的解题策略是尝试所有的abc和de来确定是否满足条件。编写以下伪代码：
char s[20]；
int count=0；
scanf(%s ，s)；
for(ABC=111；abc=999abc)
for(de=11；de=99德)
If ("ABC * DE "是合法的垂直市场){
printf( %d \n ，count)；
打印abc*de的垂直位置及其后的空行。
数数；
}
printf(解的数量=%d\n ，计数)；注意：(1)char s[20]是定义字符数组的语句，scanf(%s ，s)表示从键盘输入一个字符串到字符数组s。
(2)char的意思是“字符类型”，而character是一个特殊的整数。每个字符都有一个整数代码，称为ASCII码。c语言允许以直接的方式表达字符，也允许以反斜杠(转义序列)开头的字符。
(3)stdlib . h中有一个函数atoi，它的函数原型如下：
int atoi(字符)
意思是将字符串S中的内容转换成整数返回，比如字符串“1234”，函数的返回值是1234。
(4)stdlib . h中有一个函数itoa，它的函数原型如下：
char itoa(int value，char string，int radix)
表示将整数值转换为字符串并存储在字符串中，radix是转换中使用的基数(字符串中存储的数据的基数是2 8 10 16)，它返回一个指向转换后的字符串的指针。
比如itoa(32，string，10)是一个字符串“32”，它把32变成十进制数，并返回指向这个字符串的指针；Itoa(32，string，16)是一个字符串“20”，它将32变成一个十进制数，并返回指向该字符串的指针。
技巧3-7:C语言中的字符类型是用char表示的，它实际上存储的是字符的ASCII码。字符常量可以用单引号表示。从语法上讲，字符可以用作int类型。
语句scanf(%s ，s)；就是读取一个没有空格，制表符和回车的字符串，存储在字符数组S中，S前面没有符号。
3-8:在scanf(%s ，s)中，不要在s前放符号，如果是字符数组char s[MAXN] [MAXL]，可以用scanf(%s ，s[i])读取第I个字符串。
接下来是两个问题：判断和输出。先考虑产量。先算第一线积x=abce，再算第二线积y=abcd，最后总积z=abcde，然后一下子打印出来：
printf(]\ nXM \ n-\ n]\ nM \ n-\ n]\ n \ n ，abc，de，x，y，z)；完整的过程如下：
计划3-4垂直问题#包括
#包括
int main(){
int i，ok，abc，de，x，y，z，count=0；
char s[20]，buf[99]；
scanf(%s ，s)；
for(ABC=111；abc=999abc)
for(de=11；de=99de ) {
x=abc*(de)；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)；我)
if(strchr(s，buf[I])==NULL)ok=0；
如果(正常){
printf( %d \n ，count)；
printf(]\ nXM \ n-\ n]\ nM \ n-\ n]\ n \ n ，abc，de，x，y，z)；
}
}
printf(解的数量=%d\n ，计数)；
返回0；
}描述：(1)**sprint**f函数
Sprintf是一个可变参数函数，定义如下：
int sprintf( char *buffer，const char *format [，argument].);
除了前两个参数的固定类型之外，还可以跟任意数量的参数。而它的本质显然在第二个参数格式字符串里。
这个函数的作用是将格式化的数据写入一个字符串，它的返回值是字符串的长度。包含这个函数的头文件是stdio.h
比如这个程序中的Sprintf (BUF， % d% d% d% d ，ABC，DE，X，Y，Z)；该语句的作用是将整数abcdexyx打印为字符串，并存储在字符串buff中。
(2) * * strrch * *函数
Strchr函数定义如下：
char *strchr(const char *s，char c)；
这个函数的作用是找到字符C在字符串s中第一次出现的位置。它的返回值是指向第一次出现的C的指针，如果s中没有C，则为NULL。包含这个函数的头文件是string.h
比如这个程序的if语句中strrch (S，buf[i])的作用就是寻找字符串S中第一个字符BUF [I]的位置，如果strrch (s，buf[i]==null，则表示字符串S中没有BUF[I]字符。
(3)3)sprintf函数、printf函数和fprintf函数之间的区别
Printf输出到屏幕，fprintf输出到文件，sprintf输出到字符串。应该注意，应该有足够空间用于写入的字符串。
技巧3-9:可以使用sprintf将信息输出到一个字符串，这与printf和fprintf类似。但是您应该确保该字符串足够大，能够容纳输出信息。
字符串的空格应该是字符数加1，因为C语言中的字符串以空字符 \0 结尾。
函数strlen(s)用于获取字符串s的实际长度，即函数strlen(s)返回结束标记之前的字符数。所以这个字符串中的字符依次是s[0]，s[1]，…，s[strlen(s)-1]，s[strlen(s)]是结束标记 \0 。
3-10:C语言中的字符串是以 \0 结尾的字符数组。可以使用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:滥用可以修改变量值如，-，=的运算符很容易带来隐藏的错误。建议每个语句最多只使用一次该运算符，它修改的变量在整个语句中只出现一次。
提示3-13:但是用option -Wall编译程序时，会给出很多(但不是全部)警告信息，帮助程序员检查错误。但并不能解决所有问题：有些“错误”的程序是合法的，但这些行为并不是你所期望的。
3.3最长的回文子串
例3-4回文。输入一个字符串，找到最长的回文子串。substring的含义是：在原字符串中连续出现的字符串片段。回文的意思是：和向后看是一样的。比如abba和yyxyy。判断时，所有标点符号和空格都要忽略，大小写也要忽略，但输出要保持原样(不输出回文串开头和结尾的多余字符)。输入字符串的长度不超过5000，并且占用单独的一行。应该输出最长的回文字符串。如果有多个回文，起始位置在最左边。
输入示例：confinius说：女士，我是adam。
样本输出：夫人，我是亚当
[分析]
因为输入的字符比较复杂，首先不能用scanf(%s )输入字符串。以下两种方法可用于解决以下问题：
第一种方法是使用fgetc(fin)，它读取一个打开的文件fin，读取一个字符，然后返回一个int值。因为如果文件结束，fgetc会返回一个特殊的标志EOF，这个标志不是char。如果想从标准输入中读取一个字符，可以使用getchar()，它相当于fgetc(stdin)。
提示3-14:使用fgetc(fin)从可以打开的文件fin中读取一个字符。一般来说，在将它转换为char值之前，应该检查它不是EOF。可以使用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时，应避免编写与操作系统相关的程序。
第二种方法是使用fgets(buf，MAXN，fin)读取一整行，其中buf的声明是char buf[MAXN]。这个函数读取不超过MAXN-1个字符，然后在末尾终止字符 \0 ，所以不会越界。这个函数之所以可以用来读取一个完整的行，是因为一旦读取了回车 \n ，读取就会停止，这个 \n 也将是buf字符串中的最后一个有效字符(后面跟着字符串结束符 \0 )。buf不以 \n 结尾的情况只有一种：读取文件结尾，最后一个文件不以 \n 结尾。
3-16: FGETS (buf，MAXN，FIN)将读取的完整行放入字符数组buf中。您应该确保buf足以容纳文件的一行。除了在文件终止符前没有遇到 \n 之外，buf总是以 \n 结尾。当没有读取字符时，fgets返回NULL。
Get (s)表示从标准输入设备读取的字符串存放在s指向的数组中，成功则返回指针s，否则返回NULL。但是gets(s)并不表示读取的最大字符数，gets函数并不关心S有多少可用空间。
提示3-17: C语言并没有禁止程序读写“非法内存”。比如你声明char s[100]，你完全可以赋值s[10000]=a (even -Wall不会警告你)，但是后果自负。
3-18:C语言的gets(s)有缓冲区溢出漏洞，不推荐使用。
选择fgets函数可以解决“输入带空格”的问题。它可以一次读一行，最方便。
接下来，要解决“判断时忽略标点，但保持输入输出原样”的问题，可以用一个通用的方案：预处理。构造一个不包含原标点的新字符串，所有字符都变成大写(顺便解决了大小写问题):
n=strlen(buf)；
m=0；
for(I=0；我我)
if(is alpha(buf[I])s[m]=toupper(buf[I])；说明：ctype.h中包含了isalpha(c)的原型，用来判断字符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；我我)
for(j=I；j j)
如果(s[i.j]是回文串j-I 1 max)max=j-I 1；“Current Maximum”变量max，保存目前为止找到的最长回文子串的长度。如果字符串s的第I到j个字符(表示为s[i.j])是回文，检查长度j-i 1是否超过max。
最后，判断s[I]是否.j]是一个如下的回文：
int ok=1；
for(k=I；k k)
if(s[k]！=s[I j-k])ok=0；s[k]的“对称”位置是s[i j-k]，因为只要一次比较失败，标记变量ok就要设置为0。
完整的过程如下：
程序3-5最长回文子串(1)#包含
#包括
#包括
#定义MAXN 5000 10
char buf[MAXN]，s[MAXN]；
int main() {
int n，m=0，max=0；
int i，j，k；
fgets(buf，sizeof(s)，stdin)；
n=strlen(buf)；
for(I=0；我我)
if(is alpha(buf[I])s[m]=toupper(buf[I])；
for(I=0；我我)
for(j=I；j j ) {
int ok=1；
for(k=I；k k)
if (s[k]！=s[I j-k])ok=0；
if(ok j-i1 max)max=j-i1；
}
printf(max=%d\n ，max)；
返回0；
}实际编程中，往往是先写一个有主要功能的程序，然后再完善。你甚至可以先写一个只有输入输出函数的“骨架”，但要确保它是正确的。这样每次只增加一点功能，比一次写完整个程序更不容易出错。这种方法被称为迭代开发。
技巧3-21:程序复杂时，除了在设计阶段用伪代码理清思路，在编码阶段可以使用迭代开发3354，每次只实现一点点功能，但要充分测试，确保正常工作。
程序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
#包括
#包括
#定义MAXN 5000 10
char buf[MAXN]，s[MAXN]；
int p[MAXN]；
int main() {
int n，m=0，max=0，x，y；
int i，j；
fgets(buf，sizeof(s)，stdin)；
n=strlen(buf)；
for(I=0；我我)
if(is alpha(buf[I]){
p[m]=I；
s[m]=toupper(buf[I])；
}
for(I=0；i i ) {
for(j=0；i - j=0 i j j ) {
if (s[i - j]！=s[I j])break；
if (j * 2 1最大值){
max=j * 2 ^ 1；
x=p[I-j]；
y=p[I j]；
}
}
for(j=0；i - j=0 i - j 1 j ) {
if (s[i - j]！=s[I-j 1])break；
if (j * 2最大值2){
max=j * 2 ^ 2；
x=p[I-j]；
y=p[I j 1]；
}
}
}
for(I=x；我我)
printf(%c ，buf[I])；
printf( \ n )；
返回0；
}
3.4总结和练习
至此，C语言的核心内容已经全部学完。理论上，算法前三章的知识足够写大部分算法竞赛程序了。
3.4.1必要的存储容量3.4.2用ASCII编码表示C语言中的字符，除了字符常量以外，还有一种特殊形式的字符常量，即以一个字符“\”开头的字符序列。您也可以使用ASCII码(八进制数或十六进制数)来表示转义字符中的字符。
提示3-22:字符也可以直接用ASCII码表示。如果是八进制，应该写成\ddd，代表1到3个八进制数字所代表的字符；如果用十六进制，应该写成\xhh，表示用1到2个十六进制数字表示的字符。
3.4.3补码记数法计算机中的二进制是无符号的，但对于正号和负号可以是二进制位。有符号的32位整数，在计算机中采用“补码表示法”。
例如，printf(%u\n ，-1)语句的输出是4294967295=232-1。用-2，-3，-4，…代替-1后，可以总结出一个规律：n的内部表示是232-n。
提示3-23:在大多数计算机中，整数是用补码表示的。
采用补码表示法的主要原因是符号位和其他位可以统一处理；同时，减法也可以当作加法。另外，当用补码表示的两个数相加时，如果最高位(符号位)有进位，则舍弃该进位。
一般来说，int是32位(4字节)。
3.4.4重新实现库函数在学习字符串时，重新实现一些库函数是有益的。
练习1:只使用getchar函数读入一个整数。假设它占据一行直到行尾，包括换行符。确保输入的读入整数可以保存在int中。
练习2:只使用fgets函数读入一个整数。假设它占据一行直到行尾，包括换行符。确保输入的读入整数可以保存在int中。
练习3:只用getchar实现fgets的功能，即一次读取整行一个字符。
练习4:实现strchr的功能，即在字符串中查找一个字符。
回答：下面写一个函数strcr1，实现strcr1的功能：
char *strchr1(char *str，int ch)
{
int I；
for(I=0；str[i]！=\0;我)
if(str[i]==ch)返回str I；
返回NULL
}练习5:实现isalpha和isdigit的功能，即判断字符是否为字母/数字。
答：(1)下面写一个函数isalpha 1，实现is alpha的函数：
int isalpha1(char ch)
{
if((ch= A ch= Z ) (ch= A ch= Z ))返回1；
否则返回0；
}(2)下面写一个函数isdigit1，实现isdigit的功能：
int isdigit1(char ch)
{
if(ch=0 ch=9 )返回1；
否则返回0；
}3.4.5字符串处理常见问题tot=1；
for(I=0；I strlen(s)；我)
if(s[I]==1)tot；
printf(字符串中有%d个字符 1 。\n ，tot)；这个程序的功能是计算一个字符串中字符1的个数。
实验1:添加字符串S的声明语句，长度不小于107。提示：在主函数内部还是外部？答：添加字符串S的声明语句如下：
#定义MAXN 10000000
char s[MAXN]；应该放在主函数之外。
实验二：添加一条阅读语句，测试上面的程序是否输出了想要的结果。如果没有，请改正。回答：如果不能得到想要的结果，按如下方式改正：
if(s[I]==1)tot；改为if(s[I]= 1 )tot；实验三：注释掉输入的语句，添加语句，用程序生成长度至少为105的字符串，用程序验证字符串长度不小于105。答：程序如下：#include
#包括
#定义MAXN 10000000
char s[MAXN]；
int main() {
int i，tot=0；
/*获取；从键盘输入一个字符串到s */
for(I=0；我100000；I) /*用程序生成长度至少为105的字符串*/
s[I]= 1 ；
for(I=0；I strlen(s)；我)
if(s[I]== 1 )tot；
printf(字符串中有%d个字符 1 。\n ，tot)；
返回0；
}实验四：用带计时功能的字符串的长度来检验这个程序运行时间的规律。如何改善？答：程序如下：
#包括
#包括
#包括
#定义MAXN 10000000
char s[MAXN]；
int main() {
int i，tot=0；
clock_t开始，结束；
start=时钟()；
for(I=0；我1000000；我)
s[I]= 1 ；
for(I=0；I strlen(s)；我)
if(s[I]== 1 )tot；
printf(字符串中有%d个字符 1 。\n ，tot)；
finish=clock()；
printf(所用时间=%.5lf秒\n ，(完成-开始)
/(双)时钟_每秒)；
返回0；
}此程序在字符串长度为10000时的运行时间为0.05秒；字符串长度为100000时，运行时间为5.32秒；当字符串长度为1000000时，运行时间为558.56秒。所以这个程序运行时间的规律是，当字符串长度增加到10倍时，运行时间增加到近100倍。
注：(1)时钟函数是C/C中的计时函数，其相关数据类型为clock _ t，在MSDN，Chad对时钟函数的定义如下：
clock _ t clock(void)；
(2)clock函数返回从“启动本程序进程”到“调用程序中的clock()函数”的CPU时钟滴答数，称为wal-clock)；在MSDN；如果挂钟时间不合适，返回-1。其中clock_t是用于节省时间的数据类型，其定义可以在头文件time.h中找到：
#ifndef _CLOCK_T_DEFINED
typedef长时钟_ t；
#定义_时钟_时间_定义
#endif表示clock_t是一个长整数。
(3)在头文件time.h中，还定义了一个常数CLOCKS_PER_SEC，用来表示一秒钟内会有多少个时钟计数单位。其定义如下：
# DEFINE CLOCKS _ PER _ SEC((CLOCK _ T)1000)3 . 4 . 6关于I/O 1.getchar函数当程序请求键盘输入时，只要用户输入键就可以返回getchar()函数。不一定要输入第一个字符，回车即可，也可以输入多个字符，最后回车即可。
如果直接输入文件终止符(Windows中的Ctrl Z键)，getchar()读取ASCII码中无法显示的控制字符(ASCII码值为10，LF表示该行已满，需要换行)。
说明：(1)getchar有一个int返回值。当程序调用getchar时，程序等待用户按键，用户输入的字符存储在键盘缓冲区中，直到用户按enter(输入的字符也放在缓冲区中)。在用户输入之后，Getchar开始从stdio流中一次读取一个字符。
(2)2)getchar函数的返回值是用户输入的第一个字符的ASCII码。如果出现错误，它返回-1，用户输入的字符显示回屏幕。
(3)如果用户在按enter键之前输入了不止一个字符，其他字符将保留在键盘缓存区中，等待随后的getchar调用读取。也就是说，后续的getchar调用不会等待用户按键，而是直接读取缓冲区中的字符，等待用户按键，直到缓冲区中的字符读完。
如果将getchar函数放在一个循环中，也可以读取一个字符串。例如，“读入一个字符串，直到按下回车键表示结束”，可以使用以下结构：
char ch
while((ch=getchar())！=\n )
{
…/*处理该字符ch */
}上述循环的执行过程是：先从键盘读取一个字符，将该字符赋给ch，然后判断ch是否为换行符 \n 。如果是，则循环结束；否则，执行循环体。所以这个结构可以读入多个字符，直到按下回车键(按下回车键实际上输入了两个字符：“回车”字符和“换行”字符，ASCII码分别是13和10。
2.sscanf函数(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的字符串，包含大写字母和小写字母，不包含任何空格(如空格、制表符)。
第一种方法是在c中使用流和字符串对象。
#包括
#包括
使用命名空间std
int main()
{
字符串s；
while(CIN s)count s \ n ；
返回0；
}注意：(1)这里声明C中的字符串，否则不能使用iostream。
(2)C语言中的C字符串和字符数组可以相互转换：如果s是字符数组，那么string(s)就是对应的字符串；如果s是一个字符串，那么s.c_str()就是对应的字符数组。
(3)c _ str()返回的内容为只读。比如可以用printf(%s ，s.c_str())输出，但是不能用scanf(%s ，s.c_str())输入。
第二种方法是使用getchar。
#包括
使用命名空间std
int main()
{
int ch
while((ch=getchar())！=EOF)putchar(ch)；
返回0；
}注意：赋值语句本身是有值的，所以在读取一个字符的时候可以立刻判断是不是EOF。
第三种方法是使用fgets。
#包括
使用命名空间std
#定义MAXN 100010
int main()
{
int ch
while(fgets(s，MAXN，stdin)！=NULL)看跌期权；
返回0；
} C中还有一个“字符串流”，可以实现类似sscanf和sprintf的功能：
#包括
#包括
使用命名空间std
#定义MAXN 100010
int main()
{
char s[1000]；
cin.getline(s，1000， \ n )；
string stream ss(s)；
int a，b；
ss a b；
计数a b \ n
返回0；
}上面的函数首先读取cin的一行。Getline函数的第三个参数是行分隔符。它的默认值是 \n ，所以可以简化为cin.getline(s，1000)，其中1000的含义类似于fgets中的含义。
3.4.8汇总数组和字符串意味着数据量很大，在处理大量数据时，通常会遇到“访问非法内存”的错误。从语法上来说，C语言并没有禁止程序访问非法内存，但是后果是无法预料的。有两种方法可以解决这个问题：在访问数组之前检查下标是否合法；适当放大数组。gets函数存在缓冲区溢出漏洞。strcpy (3354)也有类似的问题。如果源字符串没有以 \0 结尾，那么副本可能会覆盖缓冲区之外的内存。
在数组和字符串处理程序中，下标的计算极其重要。
理解字符编码对于正确使用字符串至关重要。算法中涉及的字符一般是ASCII表中可打印的字符。对于中文GBK编码，如果char值为正，则为西文字符；如果为负数，则为汉字的前半部分(此时需要读取另一个char)。
3.4.9电脑上的练习3-1分数统计(stat)输入部分学生的分数。哪个乐谱出现的频率最高？如果有多个并行，输出从小到大。注：(1)假设输入分数个数不超过10000；没有这个假设，这个问题就难了。
(2)如果有多个并列，从小到大输出。(注意书中这里有一个模糊的定义。我说清楚：对于同一个分数，只输出一次。
1:分数都是不超过100的非负整数。输入：练习3-1，分数统计
输出到屏幕
[分析]
用于解决问题的数据结构：
(1)使用数组标记来存储输入的分数。
(2)使用另一个数组计数来存储相应分数出现的次数。
解决问题的思路和步骤：
(1)输入数据并处理标记和计数数组中的数据；
(2)扫描计数一次，看哪一个出现频率最高。这是什么？写为maxTimes
(3)输出maxTimes出现次数从小到大的分数。
由于学生到目前为止还没有学会排序算法，这一步比较麻烦。
具体做法如下：
(1)扫描counts数组，用maxTimes找到最小的分数并输出。
(2)将刚刚输出的分数对应的maxTimes值减1(为了下次不输出这个值)。
(3)重复步骤(1)和(2)，直到再也找不到有maxTimes的分数。
完整的过程如下：
#包括
#定义最大10000 /*最多有几个输入数据*/
#define NOMARK -1 /*表示“无效”分数；或者可以理解为“不得分”*/
int main() {
Intdata，/*新输入的数据*/
I，j，/*辅助变量*/
存在，/*输出结果时使用的辅助变量*/
MaxTimes，/*最大出现次数*/
min
Int标志[MAX]，/*存储输入数据*/
计数[MAX]；/*存储数据的计数*/
Freopen(练习3-1，分数统计(stat)a.in ， r ，stdin)；
for(I=0；任务二：分数都是不超过100的非负实数，最多保留两位小数。[分析]
与任务1相同的分析。
完整的过程如下：
#包括
#定义最大10000 /*最多有几个输入数据*/
#define NOMARK -1 /*表示“无效”分数；或者可以理解为“不得分”*/
int main() {
Int，j，/*辅助变量*/
存在，/*输出结果时使用的辅助变量*/
maxTimes/*最大出现次数*/
浮动最小值，
newData/*新输入的数据*/
浮动标记[最大值]；/*存储输入数据*/
int counts[MAX]；/*存储数据的计数*/
Freopen(练习3-1，分数统计(stat)b.in ， r ，stdin)；
for (i=0; i习题3-2 单词的长度（word）输入若干个单词，输出它们的平均长度。单词只包含大写字母和小写字母，用一个或多个空格隔开。
【分析】
解决本题，需要用到字符串的知识。字符串，也就是一维的字符数组。结束输入的方法按Ctrl+Z键，回车，回车。
使用的策略是：scanf("%s",...); 遇到空格时，会自动截断，很适合用在这种环境。strlen(); 用于计算字符串的长度
操作步骤如下：
（1）读入一个单词；
（2）计数器增量1；
（3）计算单词长度，累加总长度；
（4）总长度/计数器---- 平均长度。
完整的程序如下：
#include
#define MAXLENGTH 189819 /*最长的单词有多长？请看：http://en.wikipedia.org/
wiki/Longest_word_in_English*/
int main() {
char word[MAXLENGTH]; /*单词*/
int lengthSum=0, /*单词长度总和*/
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）输入若干个整数（可以是正整数、负数或者零），输出它们的乘积的末3位。这些整数中会混入一些由大写字母组成的字符串，你的程序应当忽略它们。提示：试试看，在执行scanf("%d")时输入一个字符串会怎样？
【分析】
每个输入的数据（无论是整数还是字符串）之间，都用回车或空格来分隔。对于乘积不足3位的情况，就输出完整的乘积，左侧不用补0。对于乘积为负数的情况，左侧不必加上-。输入的整数可能有很多个，所以最后的乘积可能会很大。“由大写字母组成的字符串”指的是字符串中全部都是大写字母。输入数据，以“Ctrl+Z，回车，回车”结束。
假设输入的整数不会超过int的表示范围，如果没有任何输入数据，则输出0。
采取的策略如下：
（1）对于输入的数据都要做为字符串来看待。
（2）对于每一个输入的数据，要判断其是否为数字。若是，要将“数字字符串”转为“整型数据”；否则，忽略这个数据。
（3）为了计算(xy)的末三位，其实只要计算(x的末三位)(y的末三位)，看其结果的末三位即可。
完整的程序如下：
#include
#include
#include
int main() {
int newData, /*新输入数据的后三位*/
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("字符串：%s\t",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("后三位转为整数：=%d\n",newData);*/
result = (result * newData) % 1000; /*乘积取最后三位*/
/*printf("....%d\n",result);*/ /*调试信息*/
}
printf("%d", result);
return 0;
}习题3-4 计算器（calculator）编写程序，读入一行恰好包含一个加号、减号或乘号的表达式，输出它的值。这个运算符保证是二元运算符，且两个运算数均为不超过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
#include
#define MAXLEN (10000)
int main() {
int x,y, /*用于计算*/
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)=%d\n",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("%s\t%d\n",strX,strlen(strX));*//*调试代码*/
/*============ 解析出str中的 operator ===============*/
operator=str[i];
/*============ 解析出str中的 strY ===============*/
p=0;
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("%s\t%d\n",strY,strlen(strY));*/ /*调试代码*/
/*========== 将strX转为x,strY转为y ============*/
x=0;
for(i=strlen(strX)-1; i 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 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=%d\ty=%d\n",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）输入一个nn字符矩阵，把它左转900后输出。
【分析】
本题描述存在一个问题：没有明确指出nn字符矩阵是以何种格式输入的。在解决问题的时候，程序员需要自己定义输入数据的格式。在此，我们定义输入数据的格式如下：
（1）先输入一个整数n，表示nn字符矩阵；
（2）再输入nn个字符，表示矩阵中的数据；
（3）假设用户输入的数据都是合法的，设 0 =n =100。
输出数据：逆时针转90度后的nn矩阵
举例说明：
输入：
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
采用的数据结构是用100100的二维数组来存储数据。
使用的策略是仔细观察输入和输出的样例。和输入矩阵对比，输出矩阵是以行为单位输出，对于n个输出行而言，是从右向左按列输出“输入矩阵”。
完整的程序如下：
#include
int main() {
char m[100][100]; /* n*n矩阵 */
int n, /* 矩阵每行的元素个数 */
x, /* 行 */
y; /* 列 */
/*=============== 数据输入 =================*/
scanf("%d",
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 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 n 100000，用户输入的都是合法数据。例如，
输入：2 11
输出：1011
采用的数据结构是用一个一维数组存储输出结果中的每一位。
采取的策略是模拟手工转换的过程。关键是，在计算的过程中，从一维数组的低位开始向高位存储；而输出的时候，从高位开始向低位输出。
完整的程序如下：
#include
int main() {
int b, /*基数*/
n, /*正整数*/
i;
int ans[100]; /*结果*/
scanf("%d%d", b,
i=0;
while (n!=0) {
ans[i]=n%b;
n=n/b;
i=i+1;
}
for (i=i-1;i 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
int main() {
int b, /*基数（2 =b =10）*/
i,j,k;
long long m, /*位权*/
n, /*b进制的正整数n*/
result; /*结果*/
int s[20];
scanf("%d%I64d", b,
/*printf("%d% I64d\n",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开始，向高位计算，可以节省计算位权的时间*/
result=result+s[k]*m;
m=m*b; /*计算更高一位的位权*/
}
printf("%I64d",result);
return 0;
}习题3-8 手机键盘（keyboard）输入一个由小写字母组成的英文单词，输出用手机的默认英文输入法的敲键序列。例如要打出pig这个单词，需要按1次p，3次i，（稍作停顿后）1次g，记为p1i3g1（显然，书中这部分描述存在明显的错。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。