《字符串处理》PPT课件.ppt

第四章 字符串处理,4.1 简单的字符串操作示例 4.2 例题: 统计字符数 4.3 例题: 487-3279 4.4 例题: 子串 4.5 例题: 最难的问题,字符串,每个字符串是一个特殊的数组，满足两个条件 元素的类型为char 最后一个元素的值为0 , Ascii码就是 0 字串用字符型数组存储 char strN; 从0号元素开始存储 最大存储长度为N-1的字符串，N是数组大小。 字串“hello”在长度为10的字符串数组中的存储格式,字符串表示,字符串常量 “CHINA” ”C program!” 字符数组方式 char str =“abcd1234n” 指针方式 char *str=“abcd1234n” 输入/出：单个输入/出字符 scanf(“%c”, &stri) 整体输入/出字串 scanf(“%s”,str) 循环条件：stri!=0 istrlen(str),字符串处理函数,字符串输入：scanf、gets 字符串输出：printf、puts 将格式化数据写入字符串：sprintf 字符串长度查询函数： strlen 字符串复制函数：strcpy、strncpy（部分拷贝） 字符串连接函数： strcat 字符串比较函数： strcmp、strncmp、stricmp(区分大小写)、strnicmp 字符串搜索函数： strcspn、strspn、strstr、strtok、strchr 字符串大小写转换函数： strlwr、strupr,【算法分析】 删除字符串中的字符用覆盖算法。方法是将后面的字符覆盖要删除的字符。具体做法：对字符数组设定两个指针变量(两个下标)，一个(p)用于访问所有的元素，另一个(q)用于复制不删除的元素，最后赋0值作为新字符串结束标志。在表达式*q+中，q先结合+运算符，取地址值结合*后q自增。 注意对*q赋值是有条件的，这就实现删除全部ch字符。删除ch字符后，要添加结束标志。 由于p、q都已移动，要用首地址str输出。,例 在指定字符串中删除指定的字符,#include void main() char str80, *p, *q, ch; printf(“Input a string:n“); gets(str); printf(“Input a character you want delete:n“); ch=getchar( ); p=q=str; for(;*p!= 0;p+) if(*p!=ch) *q+ =*p; *q=0; puts(str); ,int i=j=0; for (; stri!=0; i+) if (stri!=c) strj+=stri; strj=0;,4.2 统计字符个数,例：判断一个由a-z组成的字符串中哪个字符出现的次数最多 输入：第1行是测试数据的组数n，每组测试数据是一个由a-z这26个字符组成的字符串，每组测试数据占一行，每行数据不超过1000个字符且非空。 输出：n行，每行输出对应一个输入。每一行输出包括出现次数最多的字符和该字符出现的次数，中间是一个空格。如果有多个字符出现的次数相同且最多，那么输出ASCII码最小的那一个字符。,统计字符个数,读入字符串存入数组，依次判断并统计各个字母在字符串中出现的次数并找到出现次数最多的。注意三点： (1)一次输入一个字符串。scanf函数通过空格或者回车结束。 (2)通过字符型数组的下标访问各个元素。使用函数strlen计算字符个数。 (3)输入的字符串中，可能有多个字符出现次数相同且最多的情况。此时输出Ascii码最小的字符。 解决方案： char str1001存放输入字符串，可存储最多1000个字符，其中多一个元素存储字符串结束标志0。数组 int sum26记录字符串中每个字母的出现次数。字母c的出现的次数记录在sumc-a中。,统计字符数,#include #include void main( ) int cases, sum26, i, max; char str1001; scanf(“%d“, ,stri!=0,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。如果两个号码有相同的标准格式，那么他们就是等同的（相同的拨号）。某人正在为本地的公司编写一个电话号码薄。作为质量控制的一部分，你想要检查是否有两个和多个公司拥有相同的电话号码。,4.3 487-3279,输入：第一行指定电话薄中号码的数量（最多100000）。余下每行是一个由数字，大写字母以及连接符构成的电话号码。 输出：对于每个重复号码产生一行输出，输出的是号码的标准格式紧跟一个空格然后是重复次数。如果存在多个重复号码按照字典升序输出。如果没有则输出No duplicates。 问题分析：将电话号码译成单词、短语时有多种方式。为判断是否有重复号码，要解决两个问题。 将各种电话号码表示转换成标准表示：一个长度为8的字符串，前三个字符是数字、第4 个字符是-、后四个字符是数字。 对全部电话号码进行排序，相同号码排在相邻位置。,4.3 487-3279,解决方案：用二维数组telNumbers1000009存储全部电话号码的标准表示。每读入一个电话号码，先转换成标准格示，然后存储到二维数组中。全部电话号码输入完后，用函数模板qsort进行排序，用函数strcmp比较telNumbers中相邻号码，判断是否有重复的电话号码、并计算重复次数。 实现技巧 用字符串map表示从电话拨号盘的字母到数字的映射关系：mapj表示字母j+A映射成的数字。 char map = “22233344455566677778889999“; 使用C/C+的函数：qsort排序；strcmp比较。 对程序进行模块化和使用全局变量，号码标准化用函数standardizeTel，数组map和telNumbers作为全局变量。,#include #include #include char map = “22233344455566677778889999“; char str80, telNumbers1000009; int compare(const void *elem1, const void *elem2) return (strcmp(char*)elem1, (char*)elem2); ,void standardizeTel(int n) int j, k; j = k = -1 ; while ( k=A ,void main() int n, i, j; bool noduplicate; scanf(“%d“, ,4.4 子 串,有一些由字母组成的大小写敏感的字符串。请编程找到一个最长的字符串x，使得对于已经给出的任意一个字符串y，x或者是y的子串、或者x中的字符反序之后得到的新字符串是y的子串。 输入：第一行是一个整数t(1=t=10)，表示测试数目。对于每一组测试数据，第一行是一个整数n (1=nt=100)，表示已经给出n个字符串。接下来n行，每行给出一个长度在1和100之间的字符串。 输出：对于每一组测试数据，输出一行，给出题目中要求的字符串x的长度；如果找不到符合要求的字符串，则输出0,思路：随机选择输入数据中的一个字符串，从长到短选择该字符串的所有子串，判断是否符合题目要求，直到找到符合题目要求为止。 改进：不要随机拿，选择输入数据中最短的那个。从长到短找出它的所有子串，依次判断是否符合题目要求。 算法：(1)输入n个字符串 (2) 找最短字符串 (3) 按子串长度由长到短，依次判断子串是否是其他所有字符串的子串，是则结束,4.4 子串,#include #include int t, n; char str100101; int searchMaxSubString(char* source); void main() int i, minStrLen, subStrLen; char minStr101; scanf(“%d“, ,int searchMaxSubString(char* source) int subStrLen = strlen(source), sourceStrLen = strlen(source); int i, j; bool foundMaxSubStr; char subStr101, revSubStr101; while ( subStrLen 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 n; j+) /遍历所有输入的字符串 if ( strstr(strj, subStr) = NULL ,要求返回满足条件的子串,char *searchMaxSubString(char* source) int subStrLen = strlen(source), sourceStrLen = strlen(source), i, j; bool foundMaxSubStr; char subStr101, revSubStr101; while ( subStrLen 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 ,调用时将函数返回值复制给字符数组,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,输入（密文） 最多不超过100个数据集组成。每个数据集由3部分组成 起始行：START 密码消息：由1到200个字符组成，一行，表示Caesar发出的一条消息 结束行：END 在最后一个数据集之后，是ENDOFINPUT 输出（明文） 每个数据集对应一行，是Caesar 的原始消息。,#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; ,方法一,void decipher ( char message ) /解密函数 char plain27=“VWXYZABCDEFGHIJKLMNOPQRSTU“; char cipherEnd201; int i, cipherLen; gets(message); /输入密文 cipherLen = strlen(message); for ( i=0; i=A ,#include #include using namespace std; int main() char szLine300; while( 1 ) cin.getline(szLine,210); /读取密文 if( strcmp( szLine,“ENDOFINPUT“) = 0) break; for( int i = 0; szLinei; i + ) if( szLinei = A ,判断数据是否读完cin.getline读取一行，第一个参数是缓冲区地址；第二个参数是缓冲区大小，为了防止越界用的。缓冲区不够大，就自动截断。它会自动往缓冲区末尾添加 0。,方法二,输入若干行单词（不含空格），请按字典序顺序输出。大小写有区别，单词一共不超过100个，每个单词不超过20字符,单词排序,Sample output: About Tell What back man,Sample input: What man Tell About back,算法：(1)输入若干单词 存入Word10021; (2) 排序 (3) 输出单词,#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 ,为了对付有可能最后一行读入的是空行,问题描述：给定两个字符串s和t，请判断s是否是t的子序列。即从t中删除一些字符，将剩余的字符连接起来，即可获得s。 输入：包括若干个测试数据。每个测试数据是由数字和字母构成的串s和t组成，s和t的长度不超过100000。 输出：对每个测试数据，如果s是t的子序列则输出“Yes”，否则输出“No”。,All in All,样例输入 sequence subs