C语言字符串(精品)

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,ACM程序设计,福州大学至诚学院,冯新,第四讲,字符串处理,常用函数介绍,复制,char*,strcpy,(char*s1,const char*s2);,将字符串,s2,复制到,s1,指定的地址,char*,strncpy,(char*s1,const char*s2,size_t,len,);,将,s2,的前,len,个字符,(,字节,),复制到,s1,中指定的地址,不加,0,连接,char*,strcat,(char*s1,const char*s2);,将字符串,s2,连接到,s1,尾部,char*,strncat,(char*s1,const char*s2,size_t,len,);,将字符串,s2,的前,len,个字符连接到,s1,尾部,不加,0,比较,int,strcmp,(const char*s1,const char*s2);,比较字符串,s1,和,s2,int,strncmp,(const char*s1,const char*s2,size_t,len,);,对,s1,和,s2,的前,len,个字符,(,字节,),作比较,查找,char*,strchr,(const char*s,int,ch,);,在,s,中查找给定字符,(,字节值,),ch,第一次出现的位置,char*,strrchr,(const char*s,int,ch,);,在串,s,中查找给定字符,ch,最后一次出现的位置,r,表示从串尾开始,char*,strstr,(const char*s1,const char*s2);,在串,s1,中查找指定字符串,s2,第一次出现的位置,其他,size_t,strlen,(const char*s);,求字符串,s,的长度,字符转换,所谓字符转换就是将字符按照某种规律转换成对应的字符,曾经最难的问题（,HDU 1048,）,题目描述：,恺撒大帝生活在充满危险和阴谋的时代。恺撤大帝面临最严峻的形势就是如何生存下去，为了生存，他决定设计一种密码。这种密码设计得是如此难以置信的合理，以至于不知道它的原理就无法破译。,你是恺撒军队的一个小队长。你的工作就是对恺撒发布的密文进行解码，然后告诉军头的司令官。加密的规则其实很简单：对原文中的每个字母，转换成字母表后面第,5,个字母，如原文中的字符为字母,A,，则密文中对应的字符为,F,。因为你的工作是解码，所以要将密文文翻译成原文。,ciphertext,(,密文,):ABCDEFGHIJKLMNOPQRSTUVWXYZ,plaintext (,原文,):VWXYZABCDEFGHIJKLMNOPQRSTU,加密时，只有字母字符才按照上述规则进行加密。任何非字母字符保持不变，而且所有享母字符均为大写字母。,输入数据：,输入文件（非空）最多包含,100,组数据。每组数据为下面的格式，每组数据之间没有空行，所有的字符为大写。,每组数据由,3,行组成：,(1),首行为字符串,START,；,(2),第,2,行为密文，包含的字符个数大于等于,1,，小于等于,200,，表示恺撒发布的密文；,(3),第,3,行为字符串,END,。,最后一组数据后有,ENDOFINPUT,，表示输入结束。,输出描述：,对每组数据，输出一行，为你解密出来的原文。,输入数据：,输入文件（非空）最多包含,100,组数据。每组数据为下面的格式，每组数据之间没有空行，所有的字符为大写。,每组数据由,3,行组成：,(1),首行为字符串,START,；,(2),第,2,行为密文，包含的字符个数大于等于,1,，小于等于,200,，表示恺撒发布的密文；,(3),第,3,行为字符串,END,。,最后一组数据后有,ENDOFINPUT,，表示输入结束。,输出描述：,对每组数据，输出一行，为你解密出来的原文。,Sample Input,START,NS BFW,JAJSYX TK NRUTWYFSHJ FWJ YMJ WJXZQY TK YWNANFQ HFZXJX,END,START,IFSLJW PSTBX KZQQ BJQQ YMFY HFJXFW NX RTWJ IFSLJWTZX YMFS MJ,END,ENDOFINPUT,Sample Output,IN WAR,EVENTS OF IMPORTANCE ARE THE RESULT OF TRIVIAL CAUSES,DANGER KNOWS FULL WELL THAT CAESAR IS MORE DANGEROUS THAN HE,题目分析,分析本题针对的大写字母，把每个字母转换成字母表前,5,个字母，形成环状序列。,F,转换成,A,G,转换成,B,，,，,Z,转换成,U,，,A,、,B,、,C,、,D,、,E,分别转换成,V,、,W,、,X,、,Y,、,Z,。,转换公式：,ai,=(ai-5-65)%26+65;,或者,ai,=(ai+21-65)%26+65;,温馨提示：,A,在,ASCII,码中是,65,本题还要特别注意输入数据的格式，每组数据占,3,行，但只有中间一行是需要处理的，在读人数据时要跳过第,1,行和第,3,行。另外，输入数据结束“,ENDOFINPUT”,为标志的。,while(gets(a),if(strcmp(a,ENDOFINPUT)=0),break;,gets(a);,int i=0;,while(ai!=0),if(ai=A&ai=Z),ai=(ai+21-65)%26+65;,i+;,puts(a);,gets(a);,#include,#include,int,main(),char a210;,while(gets(a,),if(strcmp(a,ENDOFINPUT)=0),break;,gets(a,);,int,i=0;,while(ai,!=0),if(ai,=A&,ai,=Z),ai,=(ai+21-65)%26+65;,i+;,puts(a,);,gets(a,);,return 0;,字符编码,所谓字符编码就是将字符串中的每个字符按照编码规则转换成一个数字或一串数字或者将字符串中具有某种规律的子串转换成一串数字或其他字符等。,Soundex,（,ZJU 1858,）,Soundex,编码方法根据单词的拼写将单词进行分组，使得同一组的单词发音很接近。例如，“,can”,与“,khawn,”,，“,con”,与“,gone”,在,Soundex,编码下是相同的。,Soundex,编码方法将每个单词转换成一串数字，每个数字代表一个字母。规则如下：,1,代表,B,，,F,，,P,或,V,；,2,代表,C,，,G,，,J,，,K,，,Q,，,S,，,X,或,Z,；,3,代表,D,或,T,；,4,代表,L,；,5,代表,M,或,N,；,6,代表,R,。,而字母,A,，,E,，,I,，,O,，,U,，,H,，,W,和,Y,不用任何数字编码，并且相邻的、具有相同编码值的字母只用一个对应的数字代表。具有相同,Soundex,编码值的单词被认为是相同的单词。,输入描述：,输入文件中的每行为一个单词，单词中的字母都是大写，每个单词长度不超过,20,个字母。,输出描述：,对输入文件中的每个单词，输出一行，为该单词的,Soundex,编码。,样例输入：样例输出：,KHAWN 25,PFISTER 1236,BOBBY 11,题目分析,比如样例输入中的第一个单词,”,KHAWN”,，它的,Soundex,编码值之所以是“,25”,，是因为第一个字母“,K”,的编码值为“,2”,，而接下来的三个字母“,H”,、“,A”,和“,W”,都没有编码值，最后一个字母“,N”,的编码值为“,5”,。样例输入中的最后一个单词“,BOBBY”,，它的,Soundex,编码值之所以是“,11”,，是因为第一个字母。,“,B”,的编码值为“,1”,，第,2,个字母“,O”,没有编码值，之后两个字母“,B”,相邻，只编码成一个“,1”,，最后一个字母“,Y”,没有编码值。,从上面的分析可以看出，题目中提到的“相邻的、具有相同编码值的字母只用一个对应的数字代表”，如果具有相同编码值的字母之间间隔了若干个没有编码值的字母，则要单独编码。例如,BB,编码成“,l”,，“,BV”,也编码成“,1”,，而“,BOB”,编码成“,11”,。,本题在处理时可以把,26,个字符的编码值（数字字符）按顺序存放到一个字符数组中，对没有编码值的字符，用“*”号表示。然后对字符串中的每个字符，输出其对应的数字；如果后一个字母的编码值跟前一个字母的编码值一样，则后一个字母的编码值不输出。,#include,#include,int,main(),char change27=*123*12*22455*12623*1*2*2;,char input21;,int,i;,while(scanf(%s,input)!=EOF),int,len,;,char temp;,char,prev,=0;,len,=,strlen(input,);,for(i,=0;i,len,;i+),temp=,changeinputi,-A;,if(temp,=*),prev,=0;,continue;,if(temp=,prev,),continue;,printf(%c,temp);,prev,=temp;,printf(n,);,return 0;,回文的判断与处理,所谓回文,(palindrome),字符串，就是从左向右读和从右向左读结果相同的字符串。回文的判断与处理经常出现在,ACM/ICPC,题目中。,判断回文的方法很简单，假设字符串长度为,n,，只需依次判断字符串中第,i,个字符与第,n-l-i,个字符是否相等即可，,i=0,，,1,，,2,，,3,，,，,n/2,。,int huiwen(char*s),char*p1,*p2;,int i,t=1;,p1=s;,p2=s+strlen(s)-1;,for(i=0;i strlen(s)/2;i+),if(*p1!=*p2),t=0;,break;,p1+;,p2-;,return t;,子串处理,字符串中任意一个连续的字符组成的字符序列被称为该字符串的子串。有时，从字符串中抽取不连续的字符所组成的字符序列，也可以看成是字符串的子串。,需要说明的是，子串处理中的问题大多都属于子串匹配的问题，其中涉及的算法（如,KMP,算法）比较复杂，我们不在这里进行讨论。,字符串的包含问题（,ZJU 1970,）,题目描述：,给定两个字符串,s,和,t,，判断,s,是否是,t,的子串，也就是说，是否能通过从,t,中去掉一些字符，使得剩余的字符构成的字符串为,s,。,输入描述：,输入文件包含多个测试数据，每个测试数据占一行，为两个字符串,s,和,t,，这两个字符串是由大小写字母字符构成的，两个字符串之间用空格隔开。输人数据一直到文件尾。,输出描述：,对输入文件中的每个测试数据，判断,s,是否为,t,的子串。,样例输入：样例输出：,person compression No,VERDI,vivaVittorioEmanueleReDiltalia,Yes,题目分析,对字符串,s,的第,0,个字符,s0,，在字符串,t,中进行查找，假设查找到，其第一次出现的位置为,t0,；在字符串,t,的,t0,下一个位置继续查找,s1,，假设查找到，其（第一次出现的）位置为,t1l,；在字符串,t,的,t1,下一个位置继续查找,s2,。如果都能查找到,s,中的每个字符，则,s,是,t,的“子串”；否则如果,s,中后面某些字符在,t,中没有找到对应的字符，则,s,不是,t,的“子串”。,例如，对样例输入中的第,1,个测试数据，按照上述方式在字符串,t,中查找到字符串,