5. 字符串处理.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《5. 字符串处理.ppt》由会员分享,可在线阅读,更多相关《5. 字符串处理.ppt(49页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第五讲第五讲字符中处理字符中处理ACMACM算法与程序设计算法与程序设计2/45字符串字符串字符串:可变长的字符数组.本文中串S的第i个字符用Si表示,从第i个到第j个字符用Si.j表示实现:可以在末尾加一个结束标志,如0,也可以记录字符串的长度基本操作:取长度,取指定位置的字符,取子串,模式匹配3/45一个简单的字符串操作的例子一个简单的字符串操作的例子#include#include#include#include char strl=“The quick brown dog jumps over the lazy fox”;char strl=“The quick brown dog j
2、umps over the lazy fox”;char str250=“The QUICK brown dog Jumps over the lazy fox”char str250=“The QUICK brown dog Jumps over the lazy fox”;char str340=“The QUICK brown dog Jumps over the lazy fox”char str340=“The QUICK brown dog Jumps over the lazy fox”;/错误:字符串共有错误:字符串共有错误:字符串共有错误:字符串共有4343个字符,需要一个长
3、度至少为个字符,需要一个长度至少为个字符,需要一个长度至少为个字符,需要一个长度至少为4444的字符串变量存储。的字符串变量存储。的字符串变量存储。的字符串变量存储。/易忽略在字符串的末尾要添加表示结束的额外标志字符易忽略在字符串的末尾要添加表示结束的额外标志字符易忽略在字符串的末尾要添加表示结束的额外标志字符易忽略在字符串的末尾要添加表示结束的额外标志字符/0/0。char str450char str450;void main(void)void main(void)int result;int result;str4=“The QUICK brown DOG jumps over the
4、 lazy fox”;str4=“The QUICK brown DOG jumps over the lazy fox”;/错误:不能将一个字符串常量赋值给另一个字符串变量。错误:不能将一个字符串常量赋值给另一个字符串变量。错误:不能将一个字符串常量赋值给另一个字符串变量。错误:不能将一个字符串常量赋值给另一个字符串变量。str4=str2;/str4=str2;/错误:不能将一个字符串变量赋值绘另一个字符串变量错误:不能将一个字符串变量赋值绘另一个字符串变量错误:不能将一个字符串变量赋值绘另一个字符串变量错误:不能将一个字符串变量赋值绘另一个字符串变量 str4=str1;/str4=st
5、r1;/错误:不能将一个字符串变量赋值给另一个字符串变量错误:不能将一个字符串变量赋值给另一个字符串变量错误:不能将一个字符串变量赋值给另一个字符串变量错误:不能将一个字符串变量赋值给另一个字符串变量 printf(“Compare strings:nt%snt%snn”,strlprintf(“Compare strings:nt%snt%snn”,strl,str2);str2);4/45问题问题1:替换连续空格替换连续空格问题:把连续空格改为单个空格.例如对输入s=There are many spaces.,输出为There are many spaces.5/45分析分析算法一:每遇
6、到空格就把后面的字符往前移算法二:用两个指针,读指针持续移动,当遇到第二个空格时写指针不动.比较:算法一最坏O(N2)的,算法二是O(N)的启发启发:字符串问题一般容易设计正确的算法字符串问题一般容易设计正确的算法,但需但需要深入分析才能找到高效算法要深入分析才能找到高效算法6/45问题问题2:字符串排序字符串排序给n个字符串把它们按字典序字典序从小到大排序7/45分析分析和数值排序类似,基本操作是字符串比较由于字符串可能比较长,一般不移动字符串本身,只修改指针8/45Look and Say 1、链接地址、链接地址http:/ input consists of a number of ca
7、ses.The first line gives the number of cases to follow.Each case consists of a line of up to 1000 digits.OutputFor each test case,print the string that follows the given string.Sample Input3122344111111111111112345Sample Output1122132431101111213141510/453、解题思路解题思路本题是处理重复子串的问题。虽然输入的都是数字,但应本题是处理重复子串的
8、问题。虽然输入的都是数字,但应当把它们当成字符串处理。当把它们当成字符串处理。由于本题时限一秒,每个字符串的长度多达由于本题时限一秒,每个字符串的长度多达1000位,所以,位,所以,不好的算法容易超时。不好的算法容易超时。scanf和和printf所用的时间大大少于所用的时间大大少于cin和和cout所消耗的时间。所消耗的时间。由于本题需要频繁输出,采用由于本题需要频繁输出,采用cout则会超过一秒;但使用则会超过一秒;但使用printf则不会超过一秒。这点是则不会超过一秒。这点是ACM竞赛中节约时间的常识。竞赛中节约时间的常识。一般地,由于一般地,由于cin和和cout调试很方便,所以调试期
9、间使用它调试很方便,所以调试期间使用它们,但是提交判题系统后,如果发现超时,可尝试将们,但是提交判题系统后,如果发现超时,可尝试将cin和和cout改为改为scanf和和printf,看看是不是由于输入输出过于频繁,看看是不是由于输入输出过于频繁而导致的。而导致的。11/454、参考程序、参考程序#include#includeint main()char s1001,t;int c,i,j,n,len,temp;scanf(%d,&n);for(i=0;in;i+)scanf(%s,s);c=0;t=s0;temp=0;len=strlen(s);12/454、参考程序for(j=0;jle
10、n;j+)if(sj=t)temp+;if(j=len-1)printf(%d%c,temp,t);elseprintf(%d%c,temp,t);t=sj;temp=1;if(j=len-1)printf(%d%c,temp,t);printf(n);return 0;13/45CDOJ_1035 论文搜索论文搜索 http:/ Output每组数据输出一个整数每组数据输出一个整数M,表示,表示allenlowesy认为有用的论认为有用的论文数。文数。如果没有一篇论文的标题包含有关键词,则输出如果没有一篇论文的标题包含有关键词,则输出“Donotfind”。在每组输出结果后再输出一个空行。在
11、每组输出结果后再输出一个空行。15/45SampleInput32fiberopticalfiberopticalFiber3SensorsOpticalFiberSensinginMechanicalMeasurementANewApproachtoBuildAdvancedSensorsComparisontodifferentSensors2xmmlcysilentsky SampleOutput11Donotfind16/45论文的标题的字符串是由空格隔开,可拆成一个一个的单论文的标题的字符串是由空格隔开,可拆成一个一个的单词,然后和查询的字符串比较即可。词,然后和查询的字符串比较即可
12、。将标题字符串拆分可以用普通处理字符串的方式实现将标题字符串拆分可以用普通处理字符串的方式实现麻烦麻烦应掌握更简便的方法:使用各种字符串处理函数:应掌握更简便的方法:使用各种字符串处理函数:(#include)C语言:语言:strtok;C+:istringstream 除此之外,还有如:除此之外,还有如:strcspn,setmem,strstr,strlen,strncat,strncmp,strncpy,strpbrk 等等scanf在从在从stdin流读取输入时,遇到回车键即流读取输入时,遇到回车键即n,则停,则停止,止,n仍留在输入流中,且忽略空格,使用时,如果有仍留在输入流中,且忽
13、略空格,使用时,如果有多个输入函数被调用,需注意对多余回车的读取,一般使多个输入函数被调用,需注意对多余回车的读取,一般使用用getchar();17/45char*strtok(char*s,char*delim);功能:分解字符串为一组字符串。功能:分解字符串为一组字符串。s为要分解的字符串,为要分解的字符串,delim为分隔符字符串。实质上的处理是,为分隔符字符串。实质上的处理是,strtok在在s中查中查找包含在找包含在delim中的字符并用中的字符并用NULL(0)来替换来替换,直到找遍直到找遍整个字符串。整个字符串。说明:首次调用时,说明:首次调用时,s指向要分解的字符串,之后再次
14、调指向要分解的字符串,之后再次调用要把用要把s设成设成NULL。strtok在在s中查找包含在中查找包含在delim中的字中的字符并用符并用NULL(0)来替换,直到找遍整个字符串。来替换,直到找遍整个字符串。返回值:从返回值:从s开头开始的一个个被分割的串。当没有被分开头开始的一个个被分割的串。当没有被分割的串时则返回割的串时则返回NULL。所有。所有delim中包含的字符都会被滤中包含的字符都会被滤掉,并将被滤掉的地方设为一处分割的节点。掉,并将被滤掉的地方设为一处分割的节点。18/45#include#include#include#include using namespace std
15、;void consume(char ch)while(getchar()!=ch);char key32,title128;int main()int T,N;scanf(%d,&T);while(T-)scanf(%d,&N);consume(n);int res=0;gets(key);19/45 for(int i=0;i N;i+)gets(title);bool useful=false;char*token=strtok(title,);while(token!=NULL)if(strcmp(token,key)=0)useful=true;break;token=strtok(
16、NULL,);if(useful)res+;20/45 if(res=0)printf(Do not findnn);elseprintf(%dnn,res);return 0;21/45字符串分割掌握了么?字符串分割掌握了么?给一道作业给一道作业CDOJ_1081 统计上机成绩统计上机成绩 http:/ void sort(char*s,int*a,int n);/必必须是是稳定的排序定的排序 int main(void)char s130,s21100,t1100;int a30;int i,j,k,k1,k2;gets(s1);/读入密入密钥 gets(s2);/读入待加密字符串入待加密
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 5. 字符串处理 字符串 处理
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内