第四章 字符串处理

单击此处编辑母版样式,单击此处编辑幻灯片母版样式,第二层,第三层,第四层,第五层,*,第四章 字符串处理,4.1 简单的字符串操作示例,4.2 例题: 统计字符数,4.3 例题: 487-3279,4.4 例题: 子串,4.5 例题: 最难的问题,1,字符串,每个字符串是一个特殊的数组，满足两个条件,元素的类型为char,最后一个元素的值为0 , Ascii码就是 0,字串用字符型数组存储 char strN;,从0号元素开始存储,最大存储长度为N-1的字符串，N是数组大小。,字串“hello”在长度为10的字符串数组中的存储格式,h,e,l,l,o,0,0,0,0,0,2,字符串表示,字符串常量,“CHINA” ”C program!”,字符数组方式,char str =“abcd1234n”,指针方式,char *str=“abcd1234n”,输入/出：单个输入/出字符 scanf(“%c,”, &stri,),整体输入/出字串 scanf(“%s”,str),循环条件：,stri!=0,i 0), scanf(%s, str);,for(i = 0; i 26; i+) sumi=0;,for(i = 0; i strlen(str); i+) sum stri - a+;,max = 0;,/求出现次数最多的字符的元素下标,for( i = 1; i summax) max = i;,printf(%c %dn, max+a, summax);,cases-; ,stri!=0,9,4.3 487-3279,电话号码转换成字符串,企业喜欢用容易被记住的电话号码。让电话号码容易被记住的一个办法是将它写成一个容易记住的单词或者短语；另一个办法是以一种好记的方式对号码的数字进行分组。,电话号码的,标准格式,是七位十进制数，并在第三、第四位数字之间有一个连接符。电话拨号盘提供了从字母到数字的映射，映射关系如下：,A, B, 和C 映射到 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 映射到 9,Q,(7),和Z,(9),没有映射到任何数字，连字符不需要拨号，可以任意添加和删除。TUT-GLOP的标准格式是888-4567，310-GINO的标准格式是310-4466，3-10-10-10的标准格式是310-1010。如果两个号码有相同的标准格式，那么他们就是等同的（相同的拨号）。某人正在为本地的公司编写一个电话号码薄。作为质量控制的一部分，你想要检查是否有两个和多个公司拥有相同的电话号码。,10,4.3 487-3279,输入：第一行指定电话薄中号码的数量（最多100000）。余下每行是一个由,数字，大写字母以及连接符,构成的电话号码。,输出：对于每个重复号码产生一行输出，输出的是号码的标准格式紧跟一个空格然后是重复次数。如果存在多个重复号码按照字典升序输出。如果没有则输出No duplicates。,问题分析：将电话号码译成单词、短语时有多种方式。为判断是否有重复号码，要解决两个问题。,将各种电话号码表示转换成标准表示：一个长度为8的字符串，前三个字符是数字、第4 个字符是-、后四个字符是数字。,对全部电话号码进行排序，相同号码排在相邻位置。,11,4.3 487-3279,解决方案：用二维数组telNumbers1000009存储全部电话号码的标准表示。每读入一个电话号码，先转换成标准格示，然后存储到二维数组中。全部电话号码输入完后，用函数模板qsort进行排序，用函数strcmp比较telNumbers中相邻号码，判断是否有重复的电话号码、并计算重复次数。,实现技巧,用字符串map表示从电话拨号盘的字母到数字的映射关系：mapj表示字母j+A映射成的数字。,char map = 22233344455566677778889999;,使用C/C+的函数：qsort排序；strcmp比较。,对程序进行模块化和使用全局变量，号码标准化用函数standardizeTel，数组map和telNumbers作为全局变量。,12,#include ,#include ,#include ,char map = 22233344455566677778889999;,char str80, telNumbers1000009;,int compare(const void *elem1, const void *elem2), return (strcmp(char*)elem1, (char*)elem2); ,13,void standardizeTel(int n) ,int j, k;,j = k = -1 ;,while ( k=A & strj=Z), telNumbersnk=mapstrj-A; continue; ,telNumbersnk=strj; /,是数字字符,telNumbersnk=0;,14,void main(), int n, i, j; bool noduplicate;,scanf(%d,for(i=0;in;i+),/输入电话号码, scanf(%s,str); standardizeTel(i); ,qsort(telNumbers,n,9, compare);,noduplicate = true; i=0;,while ( in ), j=i; i+;,while (i1),/表示有重复, printf(%s %dn, telNumbersj, i-j);,noduplicate = false; ,if ( noduplicate ) printf(No duplicates.n); ,15,4.4 子 串,有一些由字母组成的大小写敏感的字符串。请编程找到一个最长的字符串x，使得对于已经给出的任意一个字符串y，x或者是y的子串、或者x中的字符反序之后得到的新字符串是y的子串。,输入：第一行是一个整数t(1=t=10)，表示测试数目。对于每一组测试数据，第一行是一个整数n (1=nt=100)，表示已经给出n个字符串。接下来n行，每行给出一个长度在1和100之间的字符串。,输出：对于每一组测试数据，输出一行，给出题目中要求的字符串x的长度；如果找不到符合要求的字符串，则输出0,16,思路：,随机选择输入数据中的一个字符串，从长到短选择该字符串的所有子串，判断是否符合题目要求，直到找到符合题目要求为止。,改进：,不要随机拿，选择输入数据中最短的那个。从长到短找出它的所有子串，依次判断是否符合题目要求。,算法：(1)输入n个字符串 (2) 找最短字符串 (3) 按子串长度由长到短，依次判断子串是否是其他所有字符串的子串，是则结束,4.4 子串,17,#include ,#include ,int t, n;,char str100101;,int searchMaxSubString(char* source);,void,main(), int i, minStrLen, subStrLen;,char minStr101;,scanf(%d, ,while (t-), scanf(%d, ,minStrLen = 100;,/记录输入数据中最短字符串的长度,for (i = 0; i n; i+) ,/输入一组字符串,scanf(%s, stri);,if ( strlen(stri) 0 ),/搜索不同长度子串，从最长的子串开始搜索,for (i = 0; i = sourceStrLen - subStrLen; i+),/搜索长度为subStrLen的全部子串,strncpy (subStr, source+i, subStrLen);,strncpy (revSubStr, source+i, subStrLen);,subStrsubStrLen = revSubStrsubStrLen = 0;,strrev(revSubStr);,/,将字符串 s 颠倒,foundMaxSubStr = true;,for( j = 0; j 0 ), for (i = 0; i = sourceStrLen - subStrLen; i+) ,strncpy(subStr, source+i, subStrLen);,strncpy(revSubStr, source+i, subStrLen);,subStrsubStrLen = revSubStrsubStrLen = 0;,strrev(revSubStr);,foundMaxSubStr = true;,for( j = 0; j n; j+),if ( strstr(strj, subStr) = NULL & strstr(strj, revSubStr) = NULL ),foundMaxSubStr = false; break; ,if (foundMaxSubStr),return(subStr);,subStrLen-; ,return,(无满足条件的子串！);,调用时将函数返回值复制给字符数组,20,4.5,Caesar密码,Julius Caesar生活在充满危险和阴谋的年代。为了生存，他首次发明了密码，用于军队的消息传递。假设你是Caesar军团中一名军官，需要把Caesar发送的消息破译出来、并提供给你的将军。消息加密的办法是：对消息原文中的每个字母，分别用该字母之后的第5个字母替换（A用F换，B用G换Z用E换），其他字符不变，并且消息原文的所有字母都是大写的。,原文字母：V W X Y Z A B C D E F G H I J K L M N O P Q R S T U,密码字母：A B C D E F G H I J K L M N O P Q R S T U V W X Y Z,21,输入,（密文）,最多不超过100个数据集组成。每个数据集由3部分组成,起始行：START,密码消息：由1到200个字符组成，一行，表示Caesar发出的一条消息,结束行：END,在最后一个数据集之后，是ENDOFINPUT,输出,（明文）,每个数据集对应一行，是,Caesar,的原始消息。,22,#include ,#include ,void decipher(char message);,/解密函数声明,void main( ),char message201;,gets(message);,/输入起始行,while (strcmp(message, START)=0), decipher(message);,printf(%sn,message);,gets(message);,/输入下一个起始行,return; ,方法一,23,void decipher ( char message ),/解密函数, char plain27=VWXYZABCDEFGHIJKLMNOPQRSTU;,char cipherEnd201;,int i, cipherLen;,gets(message);,/输入密文,cipherLen = strlen(message);,for ( i=0; i=A & messagei= A & szLinei = Z ), szLinei -= 5;,if( szLineiA) szLinei = Z-(A-szLinei) +1;,cout szLine; cout endl;,return 0;,判断数据是否读完cin.getline读取一行，第一个参数是缓冲区地址；第二个参数是缓冲区大小，为了防止越界用的。缓冲区不够大，就自动截断。它会自动往缓冲区末尾添加 0。,方法二,25,输入若干行单词（不含空格），请按字典序顺序输出。大小写有区别，单词一共不超过100个，每个单词不超过20字符,单词排序,Sample output:,About,Tell,What,back,man,Sample input:,What,man,Tell,About,back,算法,：(1)输入若干单词 存入,Word10021;,(2) 排序,(3) 输出单词,26,#include ,#include ,#include ,char Word10021;,int MyCompare( const void * e1, const void * e2 ), return strcmp( (char * ) e1, (char * ) e2 ); ,int main(), int n = 0; /单词个数,while (scanf(%s,Wordn) !=EOF &,Wordn0 ),n +;,qsort (Word, n,sizeof(Word0),MyCompare);,for( int i = 0; i 0 ),i = 0;,for(j = 0 ; si j + ),if( tj = si ) i +;,if ( si = 0),printf(Yesn);,else,printf(Non);,return 0;,31,实验题(七),求指定字符在字符串中第一次出现的位置并输出。当字符串为“,This Is a c Program,指定字符为,a,时，则输出,Result is :8,把字符串中所有小写字母（例如,o,）左边的字符串内容移到该串的右边，然后把小写字母,o,删除，余下内容移到已处理字符串的左边。最后输出字符串,原字串,:He can create an index on any field.,结果,: n any,field.He,can create an index,判断两个由大小写字母和空格组成的字符串在忽略大小写和压缩掉空格后是否相等。,4.,密码,(ai2818),5.,最短前缀,(ai2797),6.,浮点数格式,(ai2799),32,