《数组和字符串》PPT课件.ppt

3.1 数组,程序3-1 逆序输出 #include #define MAXN 100 + 10 int aMAXN; int main() int i,x,n=0; while(scanf(“%d“, ,3.1 数组,提示3-1：语句int aMAXN声明了一个包含MAXN个整型变量的数组，即a0,a1,aMAXN-1，但不包含aMAXN。MAXN必须是常数，不能是变量。 提示3-2：在算法竞赛中，常常难以精确计算出需要的数组大小，数组一般会声明得稍大一些。在空间够用的前提下，浪费一点不要紧。 提示3-3：比较大的数组应尽量声明在main函数外。,3.1 数组,例题3-1 开灯问题 有n盏灯，编号为1n。第1个人把所有灯打开，第2个人按下所有编号为2的倍数的开关（这些灯将被关掉），第3个人按下所有编号为3的倍数的开关（其中关掉的灯将被打开，开着的灯将被关闭），依次类推。一共有k个人，问最后有哪些打开着？输入：n和k，输出开着的灯编号。k=n=1000 样例输入：7 3 样例输出：1 5 6 7,#include #include #define MAXN 1000+10 int aMAXN; int main() int i,j,n,k,first=1; memset(a,0,sizeof(a); scanf(“%d%d“, ,3.1 数组,例题3-2 蛇形填数 在nn方阵里填入1，2，nn，要求填成蛇形。例如n=4时方阵为 上面的方阵中，多余的空格只是为了便于观察规律，不必严格输出。n=8,3.1 数组,提示3-4：可以用int aMAXNMAXM生成一个整型的二维数组，其中MAXN和MAXM不必相等。这个数组共有MAXN*MAXM个元素，分别为a00,a01,a0MAXM-1,a10,a11,a1MAXM-1,aMAXN-10,aMAXN-11,aMAXN-1MAXM-1。,#include #include #define MAXN 10 int aMAXNMAXN; int main() int n,x,y,tot = 0; scanf(“%d“, ,for(x = 0; x n; x+) for(y = 0; y n; y+) printf(“%3d“,axy); printf(“n“); return 0; ,3.1 数组,提示3-5：可以利用C语言简洁的语法，但前提是保持代码的可读性。 提示3-6：在很多情况下，最好是在做一件事之前检查是不是可以做，而不要做完再后悔。因为“悔棋”往往比较麻烦。,3.2 字符数组,例题3-3 竖式问题 找出所有形如abc*de（三位数乘以两位数）的算式，使得在完整的竖式中，所有数字都属于一个特定的数字集合。输入数字集合（相邻数字之间没有空格），输出所有竖式。每个竖式前应有编号，之后应有一个空行。最后输出解的总数。具体格式见样例输出（为了便于观察，竖式中的空格改用小数点显示，但你的程序应该输出空格，而非小数点）。,样例输入：2357 样例输出： 2357 325 X 77 - 2275 2275 - 25025, 775 X 33 - 2325 2325 - 25575 The number of solutions = 4, 555 X 55 - 2775 2775 - 30525 755 X 55 - 3775 3775 - 41525,3.2 字符数组,提示3-7：C语言中的字符型用关键字char表示，它实际储存的是字符的ASCII码。字符常量可以用引号法表示。在语法上可以把字符当作int型使用。 提示3-8：在scanf(“%s”,s)中，不要在s前面加上&符号。如果是字符串数组char sMAXNMAXL，可以用scanf(“%s”,si)读取第i个字符串。,#include #include int 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“,abc,de,x,y,z); ok = 1;,for(i = 0; i n“,+count); printf(“%5dnX%4dn-n%5dn%4dn-n%5dnn“,abc,de,x,y,z); printf(“The number of solutions = %dn“,count); return 0; ,3.2 字符数组,提示3-9：可以用sprintf把信息输出到字符串，用法和printf、fprintf类似。但你应当保证字符串足够大，可以容纳输出信息。 提示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中声明。,3.2 字符数组,提示3-12：滥用+、-、+=等可以修改变量值的运算符很容易带来隐蔽的错误。建议每条语句最多只用一次这种运算符，并且它所修改的变量在整条语句中只出现一次。 提示3-13：用编译选项-Wall编译程序时，会给出很多（但不是所有）警告信息，以帮助程序员查错。但这并不能解决所有的问题：有些“错误”程序是合法的，只是这些动作不是你所期望的。,3.3 最长回文子串,例题3-4 回文串 输入一个字符串，求出其中最长的回文串。子串的含义是：在原串中连续出现的字符串片段。回文的含义是：正着看和倒着看相同，如abba和yyxyy。在判断时，应该忽略所有标点符号和空格，且忽略大小写，但输出应保持原样（在回文串的首部和尾部不要输出多余字符）。输入字符串长度不超过5000，且占据单独的一行。应该输出最长的回文串，如果有多个，输出起始位置最靠左的。 样例输入：Confuciuss say:Madam,Im Adam. 样例输出：Madam，Im,3.3 最长回文子串,提示3-14：使用fgetc(fin)可以从打开的文件fin中读取一个字符。一般情况下应当在检查它不是EOF后再将其转换成char值。从标准输入读取一个字符可以用getchar()，它等价于fgetc(stdin)。 提示3-15：在使用fgetc和getchar时，应该避免写出和操作系统相关的程序。 提示3-16：fgets(buf,MAXN,fin)将读取完整的一行放在字符数组buf中。你应当保证buf足够存放下文件的一行内容。除了在文件结束前没有遇到n这种特殊情况外，buf总是以n结尾。当一个字符都没有读到时，fgets返回NULL。,3.3 最长回文子串,提示3-17：C语言并不禁止程序读写“非法内存”。例如你声明的是char s100，你完全可以赋值s10000=a（甚至-Wall也不会警告），但后果自负。 提示3-18：C语言中的gets(s)存在缓冲区溢出漏洞，不推荐使用。 提示3-19：当任务比较复杂时，可以用预处理的方式简化输入，并提供更多的数据供使用。复杂的字符串处理题目往往可以通过合理的预处理简化任务，便于调试。,3.3 最长回文子串,提示3-20：头文件ctype.h中定义的isalpha、isdigit、isprint等工具可以用来判断字符的属性，而toupper、tolower等工具可以用来转换大小写。,#include #include #include #define MAXN 5000+10 char 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 max) max = j-i+1; printf(“max = %dn“,max); return 0; ,3.3 最长回文子串,提示3-21：在程序比较复杂时，除了在设计阶段可以用伪代码理清思路外，编码阶段可以采用迭代时开发每次只实现一点小功能，但要充分测试，确保它工作正常。,#include #include #include #define MAXN 5000+10 char 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 ,for(i = x; i = y; i+) printf(“%c“,bufi); printf(“n“); return 0; ,3.4 小结与习题,3.4.1 必要的存储量 输入一些数，统计个数。 输入一些数，求最大值、最小值和平均数。 输入一些数，哪两个数最接近。 输入一些数，求第二大的值。 输入一些数，求它们的方差。 输入一些数，统计不超过平均数的个数。,3.4 小结与习题,3.4.2 用ASCII编码表示字符 提示3-22：字符还可以直接用ASCII码表示。如果用八进制，应该写成o,oo或ooo（o为一个八进制数字）；如果用十六进制，应该写成xh（h为十六进制数字串）,3.4 小结与习题,3.4.3 补码表示法 提示3-23：在多数计算机内部，整数采用的是补码表示法。,3.4 小结与习题,3.4.4 重新实现库函数 练习1：只用getchar函数读入一个整数。假设它占据单独的一行，读到行末为止，包括换行符。输入保证读入的整数可以保存在int中。 练习2：只用fgets函数读入一个整数。假设它占据单独的一行，读到行末为止，包括换行符。输入保证读入的整数可以保存在int中。 练习3：只用getchar实现fgets的功能，即用每次一个字符的方式读取整行。 练习4：实现strchr的功能，即在一个字符串中查找一个字符。 练习5：实现isalpha和isdigit的功能，即判断字符是否为字母/数字。,3.4 小结与习题,3.4.5 字符串处理的常见问题 tot = 0; for(i = 0; i strlen(s); i+) if(si = 1) tot+; printf(“There are %d character(s) 1 in the string.n“,tot); 实验1：添加字符串s的声明语句，长度不小于107。提示：放在main函数内还是外？ 实验2：添加读取语句，测试上述程序是否输出了期望的结果。如果不是，请改正。 实验3：把输入语句注释掉，添加语句，用程序生成一个长度至少为105的字符串，并用程序验证字符串长度确实不小于105。 实验4：用计时函数测试这段程序的运行时间随着字符串长度的编号规律。如果改进？,上机练习,习题3-1 分数统计 输入一些学生的分数，哪个分数出现的次数最多？如果有多个并列，从小到大输出。 任务1：分数均为不超过100的非负整数 任务2：分数均为不超过100的非负实数，但最多保留两位小数。 习题3-2 单词的长度 输入若干个单词，输出它们的平均长度。单词只包含大写字母和小写字母，用一个或多个空格隔开。 习题3-3 乘积的末3位 输入若干个整数（可以是正数、负数或者零），输出它们的乘积的末3位。这些整数中会混入一些由大写字母组成的字符串，你的程序应当忽略它们。提示：试试看，在执行scanf(“%d”)时输入一个字符串会怎样？,上机练习,习题3-4 计数器 编写程序，读入一行恰好包含一个加号、减号或乘号的表达式，输出它的值。这个运算符保证是二元运算符，且两个运算数均为不超过100的非负整数。运算数和运算符可以紧挨着，也可以用一个或多个空格、TAB隔开。行首末尾均可以有空格。提示：选择合适的输入方法可以将问题简化。 样例输入：1+1 样例输出：2 样例输入：2- 5 样例输出：-3 样例输入：0 *1982 样例输出：0,上机练习,习题3-5 旋转 输入一个n*n字符矩阵，把它左转90度后输出。 习题3-6 进制转换1 输入基数b（2=b=10）和正整数n（十进制），输出n的b进制表示。 习题3-7 进制转换2 输入基数b（2=b=10）和正整数n（b进制），输出n的十进制表示。 习题3-8 手机键盘 输入一个由小写字母组成的英文单词，输出用手机的默认英文输入法的敲键序列。例如要打出pig这个单词，需要按1次p，3次i，（稍作停顿后）1次g，记为p1i3g1,