程序设计II 第三讲 字符串处理.

Presentation on theme: "程序设计II 第三讲 字符串处理."— Presentation transcript:

1 程序设计II 第三讲 字符串处理

2 内容提要 字符串的存储、字符串处理函数 将数组传递给函数 例题：ai2767 Caesar密码 (P115) 例题：单词排序
例题：ai2744 子串 (P112) 例题：POJ1936 All in All

3 字符串 每个字符串是一个特殊的数组，满足两个条件 元素的类型为char 最后一个元素的值为‘\0’ ,Ascii码就是 0 以字符型数组存储
从0号元素开始存储 最大可以存储长度为N-1的字符串，N是数组的大小。 字符串“hello”在长度为10的字符串数组中的存储 h e l l o \0

4 字符串处理函数 将格式化数据写入字符串：sprintf 字符串长度查询函数： strlen 字符串复制函数：strcpy、strncpy
字符串连接函数： strcat 字符串比较函数： strcmp、strncmp、stricmp、strnicmp 字符串搜索函数： strcspn、strspn、strstr、strtok、strchr 字符串大小写转换函数： strlwr、strupr 这些函数都要求 #include <string.h>

5 字符串拷贝和求字符串长度 char *strcpy(char *dest, const char *src);
int strlen(const char *s); 查询str1中字符串的长度 #include <stdio.h> #include <string.h> void main() { char str1[10]="hello", str2[12]; strcpy(str2,"hello world"); printf("length:%d(str1); %d(str2)\n", strlen(str1), strlen(str2)); strcpy(str1, str2); printf("length:%d(str1); %d(str2)\n", strlen(str1), strlen(str2)); printf("%s\n", str1); return; } 把”hello world”复制到str2 把str2复制到str1

6 输出结果： length:5(str1); 11(str2) length:11(str1); 11(str2) hello world str1存储了11个非’\0’字符？ strcpy在复制字符串str2到str1时，不检查str2是否超出了str1的存储容量，而是直接将str2中存储的字符串复制到从str1开始的一段连续区域 在程序中要特别注意这种情况所引发的程序运行 不确定性

7 strcpy(str2,“hello world");
main() str1 h e l l o \0 str2 strcpy(str2,“hello world"); str1 h e l l o \0 str2 h e l l o w o r l d \0 strcpy(str1,str2); str1 h e l l o w o r l d \0 str2 h e l l o w o r l d \0

8 用strlen时常犯的错误 int MyStrchr(char * s, char c) //看s中是否包含 c {
for( int i = 0; i < strlen(s); i ++ ) if( s[i] == c) return 1; return 0; } 哪里不好？这个函数执行时间和 s 的长度是什么关系？ strlen 是一个o(N)的函数，每次判断 i < strlen(s) – 1 都要执行，太浪费时间了

9 字符串添加 strcat char *strcat(char *dest, const char *src);
把src内容加到dest后面，同样不会考虑 dest是否够长 #include <stdio.h> #include <string.h> void main() { char str1[100]="hello", str2[10]="^_^"; strcat(str1," world "); printf("%s\n", str1); strcat(str1, str2); return; } 把”world”添加到str1中原字符串的末尾 把str2中的字符串添加到str1中原字符串的末尾 输出： hello world hello world ^_^

10 字符串比较函数strcmp（分大小写）、stricmp（不分大小写）
int strcmp(const char *s1, const char *s2); Return Value If s1 is... return value is... less than s2 < 0 the same as s2 == 0 greater than s2 > 0 int stricmp(const char *s1, const char *s2); Compares one string to another, without case sensitivity. Return Value If s1 is... return value is... less than s2 < 0 the same as s2 == 0 greater than s2 > 0

11 关于 stricmp 的注意事项 stricmp 不是严格意义上的C++标准库函数，所以不同编译器的实现有所不同。 比如在POJ上交题，编译器选C++时，该函数应写为： _stricmp 不同编译器的 _stricmp 库函数执行过程也可能不一样，有的是把小写转换成大写后比较，有的是把大写转换成小写后比较，所以，在待比较字符串里面有非字母字符，比如标点符号时，不同编译器的 _stricmp执行的结果有可能不同

12 字符串比较函数strcmp、stricmp
#include <string.h> #include <stdio.h> char string1[] = "The quick brown dog jumps over the lazy fox"; char string2[] = "The QUICK brown dog jumps over the lazy fox"; void main( void ) { int result; printf( "Compare strings:\n\t%s\n\t%s\n\n", string1, string2 ); result = strcmp( string1, string2 ); printf( "strcmp: result=%d\n", result); result = stricmp( string1, string2 ); printf( "stricmp: result=%d\n", result); return; }

13 输出： Compare strings: The quick brown dog jumps over the lazy fox The QUICK brown dog jumps over the lazy fox strcmp: result=1 stricmp: result=0

14 查找子串strstr char *strstr(char *s1, char *s2);
Scans a string for the occurrence of a given substring. 查找给定字符串在字符串中第一次出现的位置，返回位置指针 strstr scans s1 for the first occurrence of the substring s2. Return Value strstr returns a pointer to the element in s1, where s2 begins (points to s2 in s1). If s2 does not occur in s1, strstr returns null. 如果找到，返回指针，指向s1中第一次出现s2的位置 如果找不到，返回 NULL

15 在string中搜索str，返回str在string中第一次出现的位置
#include <string.h> #include <stdio.h> char str[] = "lazy"; char string[] = "The quick brown dog jumps over the lazy fox"; void main( void ) { char *pdest; int result; pdest = strstr( string, str ); result = pdest - string + 1; if( pdest != NULL ) printf( "%s found at position %d\n\n", str, result ); else printf( "%s not found\n", str ); } 输出： lazy found at position 36 在string中搜索str，返回str在string中第一次出现的位置

16 在字符串中查找字符 strchr char *strchr(char *s, int c);
Scans a string for the first occurrence of a given character. 查找给定字符在字符串中第一次出现的位置，返回位置指针 strchr scans a string in the forward direction, looking for a specific character. strchr finds the first occurrence of the character c in the string s. Return Value strchr returns a pointer to the first occurrence of the character c in s; if c does not occur in s, strchr returns null.

17 在string中搜索ch，返回str在string中第一次出现的位置
在字符串中查找字符 strchr #include <string.h> #include <stdio.h> int ch = 'r'; char string[] = "The quick brown dog jumps over the lazy fox"; void main( void ) { char *pdest; int result; pdest = strchr( string, ch ); result = pdest - string + 1; if( pdest != NULL ) printf( "Result:\tfirst %c found at position %d\n\n", ch, result ); else printf( "Result:\t%c not found\n" ); } 输出： Result: first r found at position 12 在string中搜索ch，返回str在string中第一次出现的位置

18 字符串部分拷贝 strncpy char *strncpy(char *dest, char *src, int maxlen); 将前 maxlen 个字符从src拷贝到dest 1）如果src中字符不足 maxlen 个，则连’\0’一起拷贝，’\0’后面的不拷贝 2) 如果src中字符大于等于maxlen个，则拷贝 maxlen个字符

19 字符串部分拷贝 strncpy 输出： abcd abcd567890 #include <iostream>
using namespace std; #include <stdio.h> int main(void) { char s1[20] = " "; char s2[] = "abcd" ; strncpy( s1,s2,5); cout << s1 << endl; strcpy( s1," "); strncpy( s1,s2,4); return ; } 输出： abcd abcd567890

20 数组作为函数的参数 #include <iostream> using namespace std;
char str1[200] = "Hello,World"; char str2[100] = "Computer"; void swap( char s1[ ], char * s2) //交换两个字符串的内容 { char c; for( int i = 0; s1[i] || s2[i]; i ++ ){ // ‘\0’的Ascii 码就是 0 c = s2[i]; s2[i] = s1[i]; s1[i] = c; } s1[i+1] = s2[i+1] = 0; int main() swap(str1,str2); cout << str1 << endl << str2; return 0; 输出： Computer Hello,World

21 例题：ai2767 Caesar密码 (P115) 问题描述
Julius Caesar 生活在充满危险和阴谋的年代。为了生存，他首次发明了密码，用于军队的消息传递 假设你是Caesar 军团中的一名军官，需要把Caesar 发送的消息破译出来、并提供给你的将军。消息加密的办法是：对消息原文中的每个字母，分别用该字母之后的第5个字母替换（例如：消息原文中的每个字母A都分别替换成字母F，V替换成A,W替换成B…），其他字符不 变，并且消息原文的所有字母都是大写的。

22 密码消息：由1到200个字符组成一行，表示Caesar发出的一条消息 结束行：END
密码字母：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 原文字母：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 输入 最多不超过100个数据集组成。每个数据集由3部分组成 起始行：START 密码消息：由1到200个字符组成一行，表示Caesar发出的一条消息 结束行：END 在最后一个数据集之后，是另一行：ENDOFINPUT 输出 每个数据集对应一行，是Caesar 的原始消息。

23 样例输入 START NS BFW, JAJSYX TK NRUTWYFSHJ FWJ YMJ WJXZQY TK YWNANFQ HFZXJX END N BTZQI WFYMJW GJ KNWXY NS F QNYYQJ NGJWNFS ANQQFLJ YMFS XJHTSI NS WTRJ IFSLJW PSTBX KZQQ BJQQ YMFY HFJXFW NX RTWJ IFSLJWTZX YMFS MJ ENDOFINPUT 样例输出 IN 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

24 #include <iostream>
#include <string.h> using namespace std; int main() { char szLine[300]; while( cin.getline(szLine,210) ) { //可用此方式判断数据是否读完 /*cin.getline 读取一行，第一个参数是缓冲区地址；第二个参数是缓冲区大小，为了防止越界用的。缓冲区不够大，就自动截断。它会自动往缓冲区末尾添加 ‘\0’。*/ if( strcmp( szLine,"ENDOFINPUT") == 0) break; cin.getline(szLine,210); //读取密文 for( int i = 0; szLine[i]; i ++ ) if( szLine[i] >= 'A' && szLine[i] <= 'Z' ) { szLine[i] -= 5; if( szLine[i] < 'A' ) szLine[i] = 'Z' - ('A' - szLine[i]) + 1; } cout << szLine; cout << endl; cin.getline(szLine,210); //读取 END } return 0;

25 例题：单词排序 输入若干行单词（不含空格），请按字典序排序输出。大小写有区别。单词一共不超过100行，每个单词不超过20字符
Sample input: What man Tell About back Sample output: About Tell What back man

26 例题：单词排序 用什么保存多个单词？ 答：用二维字符数组 char Word[100][30];
则表达式 Word[i] 的类型就是 char * Word[i] 就是数组中的一行，就是一个字符串 Word[i][0] 就是Word[i] 这个字符串的头一个字符 二维字符数组也能初始化，例如： char week[7][10]={"Saturday", "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday"};

27 例题：单词排序 #include <stdlib.h> #include <stdio.h>
#include <string.h> char Word[100][30]; int MyCompare( const void * e1, const void * e2 ) { return strcmp( (char * ) e1, (char * ) e2 ); } int main() int n = 0; //单词个数 while(scanf("%s",Word[n]) != EOF && Word[n][0]) n ++; qsort(Word, n,sizeof(Word[0]),MyCompare); for( int i = 0; i < n; i ++ ) printf(“%s\n”,Word[i]); // ‘\n’表示换行 return 0; 为了对付有可能最后一行读入的是空行

28 例题：ai2744 子串 (P112) 问题描述：给出一些由英文字符组成的大小写敏感的字符串的集合s，请找到一个最长的字符串x，使得对于s中任意字符串y，x或者是y的子串，或者x中的字符反序之后得到的新字符串是y的子串。 输入：输入的第一行是一个整数t (1 <= t <= 10)，t表示测试数据的数目。对于每一组测试数据，第一行是一个整数n (1 <= n <= 100)，表示已经给出n个字符串。接下来n行，每行给出一个长度在1和100之间的字符串。

29 例题：ai2744 子串 (P112) 输出：对于每一组测试数据，输出一行，给出题目中要求的字符串x的长度。 Sample Input: 2
3 ABCD BCDFF BRCD rose orchid Sample Output 2 2

30 例题：ai2744 子串 (P112) 思路： 随便拿出输入数据中的一个字符串，从长到短找出它的所有子串，直到找到否符合题目要求的。 改进：
不要随便拿，要拿输入数据中最短的那个。从长到短找出它的所有子串，直到找到否符合题目要求的。

31 #include <stdio.h>
#include <string.h> int t, n; char str[100][101]; int searchMaxSubString(char* source); int main() { int i, minStrLen, subStrLen; char minStr[101]; scanf("%d", &t); while(t--) { scanf("%d", &n); minStrLen = 100; //记录输入数据中最短字符串的长度 for (i = 0; i < n; i++) {//输入一组字符串 scanf("%s", str[i]); if ( strlen(str[i]) < minStrLen ) {//找其中最短字符串 strcpy(minStr, str[i]); minStrLen = strlen(minStr); } subStrLen = searchMaxSubString(minStr);//找答案 printf("%d\n", subStrLen); } return 0;

32 int searchMaxSubString(char* source) {
int subStrLen = strlen(source), sourceStrLen = strlen(source); int i, j; bool foundMaxSubStr; char subStr[101], revSubStr[101]; while ( subStrLen > 0 ) {//搜索不同长度的子串，从最长的子串开始搜索 for (i = 0; i <= sourceStrLen - subStrLen; i++) { //搜索长度为subStrLen的全部子串 strncpy(subStr, source+i, subStrLen); strncpy(revSubStr, source+i, subStrLen); subStr[subStrLen] = revSubStr[subStrLen] = '\0'; _strrev(revSubStr); foundMaxSubStr = true; for( j = 0; j < n; j++) //遍历所有输入的字符串 if ( strstr(str[j], subStr) == NULL && strstr(str[j], revSubStr) == NULL ) { foundMaxSubStr = false; break; } if (foundMaxSubStr) return subStrLen; subStrLen--; return(0); _strrev (char * s) 将字符串 s 颠倒