《最新字符串处理PPT课件》由会员分享，可在线阅读，更多相关《最新字符串处理PPT课件（47页珍藏版）》请在金锄头文库上搜索。
1、字符串处理字符串处理2/45校赛总结校赛总结http:/ 0;10/45Caesar密码密码http:/ Caesar 生活在充满危险和阴谋的年代。为了生存，生活在充满危险和阴谋的年代。为了生存，他首次发明了密码，用于军队的消息传递。假设你是他首次发明了密码，用于军队的消息传递。假设你是Caesar 军团中的一名军官，需要把军团中的一名军官，需要把Caesar 发送的消息破译出来、发送的消息破译出来、并提供给你的将军。消息加密的办法是：对消息原文中的每并提供给你的将军。消息加密的办法是：对消息原文中的每个字母，分别用该字母之后的第个字母，分别用该字母之后的第5个字母替换（例如：消息个字母替换（
2、例如：消息原文中的每个字母原文中的每个字母A都分别替换成字母都分别替换成字母F），其他字符不），其他字符不 变，变，并且消息原文的所有字母都是大写的。并且消息原文的所有字母都是大写的。 密码字母：密码字母：ABCDEFGHIJKLMNOPQRSTUVWXYZ原文字母：原文字母：VWXYZABCDEFGHIJKLMNOPQRSTU11/45Input最多不超过最多不超过100个数据集组成。每个数据集由个数据集组成。每个数据集由3部分组成：部分组成：起始行：起始行：START密码消息：由密码消息：由1到到200个字符组成一行，表示个字符组成一行，表示Caesar发出的一发出的一条消息条消息结束行：
3、结束行：END在最后一个数据集之后，是另一行：在最后一个数据集之后，是另一行：ENDOFINPUTOutput每个数据集对应一行，是每个数据集对应一行，是Caesar的原始消息。的原始消息。12/45Sample InputSTART NS BFW, JAJSYX TK NRUTWYFSHJ FWJ YMJ WJXZQY TK YWNANFQ HFZXJX END START N BTZQI WFYMJW GJ KNWXY NS F QNYYQJ NGJWNFS ANQQFLJ YMFS XJHTSI NS WTRJ END STARTIFSLJW PSTBX KZQQ BJQQ YMFY H
4、FJXFW NX RTWJ IFSLJWTZX YMFS MJ END ENDOFINPUT Sample OutputIN WAR, EVENTS OF IMPORTANCE ARE THE RESULT OF TRIVIAL CAUSES I WOULD RATHER BE FIRST IN A LITTLE IBERIAN VILLAGE THAN SECOND IN ROME DANGER KNOWS FULL WELL THAT CAESAR IS MORE DANGEROUS THAN HE 13/45问题分析问题分析问题需要将密码消息中的每个字母分别进行相应的变换。问题需要将密码
5、消息中的每个字母分别进行相应的变换。关键之处是识别输入数据中的消息行、读入消息行的数关键之处是识别输入数据中的消息行、读入消息行的数据。据。scanf函数使用输入字符串时，每个字符串中不能有空格。函数使用输入字符串时，每个字符串中不能有空格。gets函数一次可读入一行，但有可能会导致函数一次可读入一行，但有可能会导致warningmessage，gets接收输入时接收输入时,不对接收变量进行检查，容易不对接收变量进行检查，容易产生内存溢出；产生内存溢出；fgets(str,sizeof(str),stdin)中中sizeof(str)用于限定用于限定string接接收数据的上限，多数情况面向文
6、件收数据的上限，多数情况面向文件I/O， 由于溢出检查，由于溢出检查，fgets比比gets安全；安全；14/45解密时，需将消息中单词的字符串作为普通数组，解密时，需将消息中单词的字符串作为普通数组，一次变换其中每个字母。一次变换其中每个字母。需用以下几个字符串处理函数：需用以下几个字符串处理函数：gets：读入一行字符串，允许包含空格：读入一行字符串，允许包含空格strcmp：识别消息行的：识别消息行的start和和endstrlen：计算加密消息中的每个单词的长度：计算加密消息中的每个单词的长度15/45程序程序#include#includevoid decipher (char me
7、ssage);void main() char message201; gets(message); while(strcmp(message, “START” )= 0) decipher(message); printf(“%sn”, message); gets(message); return;16/45void decipher(char message) char plain27=“VWXYZABCDEFGHIJKLMNOPQRSTU”; char cipherEnd201; int i，cipherLen; gets(message); cipherLen = strlen(me
8、ssage); for(i = 0; i=A & messagei=Z) messagei = plainmessagei A; gets(cipherEnd); return;17/45CDOJ_1035 论文搜索论文搜索 http:/ 18/45Input含多组测试数据，输入首先是一个整数含多组测试数据，输入首先是一个整数T表示测试数据组表示测试数据组数数(T=20)。每组数据开始为一个整数每组数据开始为一个整数N(N=100),表示检索到的论文表示检索到的论文数。接下来数。接下来1行是行是allenlowesy搜索的关键词，长度不超过搜索的关键词，长度不超过20，只包括小写字母和大写字母
9、。接下来只包括小写字母和大写字母。接下来N行，每一行是一个论行，每一行是一个论文的标题，长度不超过文的标题，长度不超过100，只包括小写字母、大写字母和，只包括小写字母、大写字母和空格空格 Output每组数据输出一个整数每组数据输出一个整数M，表示，表示allenlowesy认为有用的论认为有用的论文数。文数。如果没有一篇论文的标题包含有关键词，则输出如果没有一篇论文的标题包含有关键词，则输出“Donotfind”。在每组输出结果后再输出一个空行。在每组输出结果后再输出一个空行。 19/45SampleInput32fiberopticalfiberopticalFiber3SensorsO
10、pticalFiberSensinginMechanicalMeasurementANewApproachtoBuildAdvancedSensorsComparisontodifferentSensors2xmmlcysilentsky SampleOutput11Donotfind20/45论文的标题的字符串是由空格隔开，可拆成一个一个的单论文的标题的字符串是由空格隔开，可拆成一个一个的单词，然后和查询的字符串比较即可。词，然后和查询的字符串比较即可。将标题字符串拆分可以用普通处理字符串的方式实现将标题字符串拆分可以用普通处理字符串的方式实现麻烦麻烦应掌握更简便的方法：使用各种字符串处理函
11、数：应掌握更简便的方法：使用各种字符串处理函数：（#include ） C语言：语言：strtok; C+：istringstream 除此之外，还有如：除此之外，还有如：strcspn ，setmem ，strstr ，strlen ，strncat，strncmp ，strncpy ，strpbrk 等等scanf在从在从stdin流流读读取取输输入入时时，遇到回，遇到回车键车键即即n，则则停停止，止，n仍留在仍留在输输入流中，且忽略空格，使用入流中，且忽略空格，使用时时，如果有，如果有多个多个输输入函数被入函数被调调用，需注意用，需注意对对多余回多余回车车的的读读取，一般使取，一般使用用
12、getchar()；21/45char*strtok(char*s,char*delim);功能：分解字符串为一组字符串。功能：分解字符串为一组字符串。s为要分解的字符串，为要分解的字符串，delim为分隔符字符串。实质上的处理是，为分隔符字符串。实质上的处理是，strtok在在s中查中查找包含在找包含在delim中的字符并用中的字符并用NULL(0)来替换来替换,直到找遍直到找遍整个字符串。整个字符串。说明：首次调用时，说明：首次调用时，s指向要分解的字符串，之后再次调指向要分解的字符串，之后再次调用要把用要把s设成设成NULL。strtok在在s中查找包含在中查找包含在delim中的字中的
13、字符并用符并用NULL(0)来替换，直到找遍整个字符串。来替换，直到找遍整个字符串。返回值：从返回值：从s开头开始的一个个被分割的串。当没有被分开头开始的一个个被分割的串。当没有被分割的串时则返回割的串时则返回NULL。所有。所有delim中包含的字符都会被滤中包含的字符都会被滤掉，并将被滤掉的地方设为一处分割的节点。掉，并将被滤掉的地方设为一处分割的节点。22/45#include #include #include #include using namespace std;void consume(char ch)while (getchar() != ch);char key32, ti
14、tle128;int main()int T, N;scanf(%d, &T);while (T-)scanf(%d, &N);consume(n);int res = 0;gets(key);23/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(NULL, );if (useful) res+;24/
15、45 if (res = 0)printf(Do not findnn);elseprintf(%dnn, res);return 0;25/45字符串分割掌握了么？字符串分割掌握了么？给一道作业给一道作业CDOJ_1081 统计上机成绩统计上机成绩 http:/ #include 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); /读入待加密字符串读入待加密字
16、符串 for(i=0,k=0;s2i!=0;i+)if(s2i!= )tk+=s2i;/去除字符串中的空格去除字符串中的空格k1=strlen(s1);k2=k;参考程序参考程序32/45参考程序参考程序if(i=k2%k1)!=0)/如果最后一组字节不足如果最后一组字节不足 for(j=0;ik1;j+,i+)tk2+j=E;k2+=j;for(i=0;ik1;i+)ai=i;sort(s1,a,k1);/排序后得到取列的顺序排序后得到取列的顺序 k=0;for(i=0;ik1;i+)/按列取按列取 for(j=ai;jk2;j+=k1)/取一列取一列 s2k+=tj;for(i=0;i=a
17、 & s2i=z)putchar(s2i+A-a);elseputchar(s2i);return 0;33/45void sort(char *s, int *a, int n)int i,j,k,t,flag;char ch;for(i=0;in-1;i+)flag=1;for(j=0;jsj+1)ch=sj;t=aj;sj=sj+1;aj=aj+1;sj+1=ch;aj+1=t;flag=0;if(flag) break;34/45会加密了，会不会解密会加密了，会不会解密再来一道作业再来一道作业CDOJ_1082 易位法字符串解密易位法字符串解密 http:/ A, B, 和和C 映射到
18、映射到 2 D, E, 和和F 映射到映射到 3 G, H, 和和I 映射到映射到 4 J, K, 和和L 映射到映射到 5 M, N, 和和O 映射到映射到 6 P, R, 和和S 映射到映射到 7 T, U, 和和V 映射到映射到 8 W, X, 和和Y 映射到映射到 937/45Q和和Z没有映射到任何数字，连字符不需要拨号，可没有映射到任何数字，连字符不需要拨号，可以任意添加和删除。以任意添加和删除。TUT-GLOP的标准格式是的标准格式是888-4567，310-GINO的标准格式是的标准格式是310-4466，3-10-10-10的标准格式是的标准格式是310-1010。如果两个号码
19、有相同的标准格式，那么他们就是等如果两个号码有相同的标准格式，那么他们就是等同的（相同的拨号）同的（相同的拨号）你的公司正在为本地的公司编写一个电话号码薄。你的公司正在为本地的公司编写一个电话号码薄。作为质量控制的一部分，你想要检查是否有两个和作为质量控制的一部分，你想要检查是否有两个和多个公司拥有相同的电话号码。多个公司拥有相同的电话号码。38/45Input输入的格式是，第一行是一个正整数，指定电话号码输入的格式是，第一行是一个正整数，指定电话号码薄中号码的数量（最多薄中号码的数量（最多100000）。余下的每行是一个）。余下的每行是一个电话号码。每个电话号码由数字，大写字母（除了电话号码
20、。每个电话号码由数字，大写字母（除了Q和和Z）以及连接符组成。每个电话号码中只会刚好有）以及连接符组成。每个电话号码中只会刚好有7个数字或者字母。个数字或者字母。Output对于每个出现重复的号码产生一行输出，输出是号码对于每个出现重复的号码产生一行输出，输出是号码的标准格式紧跟一个空格然后是它的重复次数。如果的标准格式紧跟一个空格然后是它的重复次数。如果存在多个重复的号码，则按照号码的字典升序输出。存在多个重复的号码，则按照号码的字典升序输出。如果输入数据中没有重复的号码，输出一行：如果输入数据中没有重复的号码，输出一行： No duplicates. 39/45Sample Input12
21、 4873279 ITS-EASY 888-4567 3-10-10-10 888-GLOP TUT-GLOP 967-11-11 310-GINO F101010 888-1200 -4-8-7-3-2-7-9- 487-3279 Sample Output310-1010 2 487-3279 4 888-4567 3 40/45问题分析问题分析关键是判断输入的电话号码中是否有重复号码关键是判断输入的电话号码中是否有重复号码解决方法：解决方法：(1)将各种电话号码表示转换成标准表示将各种电话号码表示转换成标准表示一个一个长度为长度为8的字符串，前的字符串，前3个字符是数字、第个字符是数字、
22、第4个字符个字符是是一一、后、后4个字符是数字。个字符是数字。(2)根据电话号码的标准表示，搜索重复的电话号根据电话号码的标准表示，搜索重复的电话号码。办法是对全部的电话号码进行排序，这样相码。办法是对全部的电话号码进行排序，这样相同的电话号码就排在相邻的位置。输出重复的电同的电话号码就排在相邻的位置。输出重复的电话号码时，按照号码的字典升序进行输出。话号码时，按照号码的字典升序进行输出。41/45解决方案解决方案用一个二维数组用一个二维数组telNumbers1000009来存储全部来存储全部的电话号码。每一行存储一个电话号码的标准表示。的电话号码。每一行存储一个电话号码的标准表示。每读入一
23、个电话号码首先将其转换成标准表示每读入一个电话号码首先将其转换成标准表示然后存储到二维数组然后存储到二维数组telNumbers中。中。全部电话号码都输入完毕后将数组全部电话号码都输入完毕后将数组telNumbers作作为一个一维数组。其中每个元素是一个字符串用为一个一维数组。其中每个元素是一个字符串用CC+提供的函数模板提供的函数模板sort对其进行排序。对其进行排序。用字符串比较函数用字符串比较函数strcmp比较比较telNumbers中相邻的中相邻的电话号码判断是否有重复的电话号码，并计算重电话号码判断是否有重复的电话号码，并计算重复的次数。复的次数。42/45#include#inc
24、lude#includechar map =“22233344455566677778889999”;/map表示从表示从电话拨电话拨号号盘盘的字母到数字的映射关系：的字母到数字的映射关系：mapj表示字母表示字母j+A映射成的数字。映射成的数字。char str80, telNumbers1000009;int compare(const void *eleml, const void *elem2) /为为函数模扳函数模扳sort定定义义数数组组元素的比元素的比较较函数函数strcmp查查找重复找重复的的电话电话号号码码 return(strcmp(char * )eleml, (char
25、 * )elem2);43/45void standardizeTel(int n) int j, k; j=k=-1; while(k= A & strj = Z) telNumbersnk = mapstrj - A; continue; telNumbersnk = strj; telNumbersnk = 0; return;44/45void main() int n,i,j; bool noduplicate; scanf(“%d”, &n); for (i=0; in; i+) scanf(“%s”, str); standardizeTel(i); qsort(telNumbe
26、rs, n, 9, compare);45/45 noduplicate = true; i = 0; while(i n) /搜索重复的搜索重复的电话电话号号码码并并进进行行输输出出 j = i; i+; while(i 1) printf(“%s%dn”, telNumbersj, i - j); noduplicate = false; if (noduplicate) printf (“No duplicates.n”);46/45总结：总结：习惯用数据结构来表示问题中的事实和关系。例如字符数习惯用数据结构来表示问题中的事实和关系。例如字符数组组map。而用一组条件判断语句来实现这个功
27、能。这样虽然。而用一组条件判断语句来实现这个功能。这样虽然也能够实现但程序代码看起来不简洁，也容易出错。也能够实现但程序代码看起来不简洁，也容易出错。尽量使用尽量使用CC+自带的函数来完成程序的功能简化程序自带的函数来完成程序的功能简化程序代码的实现。例如函数模板代码的实现。例如函数模板sort，字符串比较函数，字符串比较函数strcmp。对程序进行模块化把一个独立的功能作为一个函数。并对程序进行模块化把一个独立的功能作为一个函数。并用一个单词、短语对函数进行命名。在上面的程序中，对用一个单词、短语对函数进行命名。在上面的程序中，对电话号码标准化是一个独立的功能，定义一个函数电话号码标准化是一个独立的功能，定义一个函数standardizeTel，使得整个程序的结构清晰、简洁、易读。，使得整个程序的结构清晰、简洁、易读。不同的程序模块需要共同访问的数据作为全局变量。既可不同的程序模块需要共同访问的数据作为全局变量。既可简化函数的参数接口，又可以降低函数调用的参数传递开简化函数的参数接口，又可以降低函数调用的参数传递开销。例如，数组销。例如，数组map和和telNumbers都作为全局变量。都作为全局变量。
