北大的高级程序设计 CPP08-5

1、程序设计实习课程 (C+ Programming Practice)整理课件程序设计实习第五讲 字符串处理主讲教师：田永鸿http:/ o程序设计练习o作业北京大学程序设计实习课程/49整理课件字符串o每个字符串是一个特殊的数组，满足两个条件n元素的类型为charn最后一个元素的值为0o以字符型数组存储n从0号元素开始存储n最大可以存储长度为N-1的字符串，N是数组的大小。o字符串“hello”在长度为10的字符串数组中的存储hello 0北京大学程序设计实习课程/49整理课件字符串处理函数o将格式化数据写入字符串：sprintfo字符串长度查询函数： strleno字符串复制函数：strcp

2、y、strncpyo字符串连接函数： strcato字符串比较函数： strcmp、strncmp、stricmp、strnicmpo字符串搜索函数： strcspn、strspn、strstr、strtok、strchro字符串大小写转换函数： strlwr、strupr北京大学程序设计实习课程/49整理课件把”hello world”复制到str2把str2复制到str1查询str1中字符串的长度strcpy、strlen#include #include void main() char str110=hello, str212; strcpy(str2, hello world); p

3、rintf(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(%sn, str1); return;北京大学程序设计实习课程/49整理课件oOutputnlength:5(str1); 11(str2)nlength:11(str1); 11(str2)nhello worldostr1存储了11个非n字符？nstrcpy在复制字符串str2到str1时，

4、不检查str2是否超出了str1的存储容量，而是直接将str2中存储的字符串复制到从str1开始的一段连续区域n在程序中要特别注意这种情况所引发的程序运行 不确定性北京大学程序设计实习课程/49整理课件hello0 str1 str2hello0 str1hello w or l d0 str2strcpy(str2, hello world);hello str1hello w or l d0 str2strcpy(str1,str2); w or l d0 main()北京大学程序设计实习课程/49整理课件把”world”添加到str1中原字符串的末尾strcat#include #inc

5、lude void main()char str115=hello, str25=_, str35=! ;strcat(str1, world); printf(%sn, str1); strcat(str1, str2); printf(%sn, str1); strcat(str1, str3);printf(%sn, str1);return;把str2中的字符串添加到str1中原字符串的末尾北京大学程序设计实习课程/49整理课件hello0 str1-0 str2 main()strcat(str1, world); !0 ! !0 str3hellow o r l str1d 0 -

6、0 str2 ! !0 str3strcat(str1, str2);hellow o r l str1d - 0-0 str2 ! !0 str3strcat(str1, str3);hellow o r l str1d - !-0 str2 ! !0 str3北京大学程序设计实习课程/49整理课件strcmp、stricmp#include #include char string1 = The quick brown dog jumps over the lazy fox;char string2 = The QUICK brown dog jumps over the lazy fox

7、;void main( void ) int result; printf( Compare strings:nt%snt%snn, string1, string2 ); result = strcmp( string1, string2 ); printf( strcmp: result=%dn, result); result = stricmp( string1, string2 ); printf( stricmp: result=%dn, result); return;北京大学程序设计实习课程/49整理课件oOutput:nstrcmp: result=1nstrcmp: res

8、ult=0北京大学程序设计实习课程/49整理课件字符串比较函数汇总ostrcmp(const char *s1, const char *s2)：对串s1和s2进行无符号比较，直至对应字符不同或到串尾ostricmp(const char *s1, const char *s2)：对串s1和s2进行无符号比较，忽略字符的大小写ostrncmp(const char *s1, const char *s2, size _t maxlen)：对串s1和s2进行无符号比较， 最多只比较maxlen个字符ostrnicmp：对串s1和s2进行无符号比较，忽略字符的大小写， 最多只比较maxlen个字符

9、北京大学程序设计实习课程/49整理课件字符串搜索函数汇总ostrchr(const char *s, char c)：在串s中正向查找字符costrstr(const char *s1, const char *s2)：在串s1中找串s2的第一次出现ostrcspn(const char *s1, const char *s2)：在串s1中找“串s2中任何字符”出现的第一次位置ostrspn(const char *s1, const char *s2)：在串s1中找“不是串s2字符”的第一次出现位置ostrtok(const char *s1, const char *s2)：将s1看成包含

10、0个或多个文本单词的序列，由分隔符串s2中1个或多哦个字符分隔n第一次调用strtok时，返回指向s1中第一个单词的第一个字符，并在返回单词好后立即写0到s1中第一个单词的尾部之后n后继的调用用NULL作为第一个参数，将继续用这种方法扫描s1，直到没有剩余单词北京大学程序设计实习课程/49整理课件strstr#include #include char str = lazy;char string = The quick brown dog jumps over the lazy fox;void main( void ) char *pdest; int result; pdest = st

11、rstr( string, str ); result = pdest - string + 1; if( pdest != NULL ) printf( %s found at position %dnn, str, result ); else printf( %s not foundn, str );在string中搜索str，返回str在string中第一次出现的位置北京大学程序设计实习课程/49整理课件strchr#include #include int ch = r;char string = The quick brown dog jumps over the lazy fox

12、;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 %dnn, ch, result ); else printf( Result:t%c not foundn ); 在string中搜索ch，返回str在string中第一次出现的位置北京大学程序设计实习课程/49整理课件#include #include int m

13、ain(void) char *string1 = 1234567890; char *string2 = 747DC8; int length; length = strcspn(string1, string2); printf(Character where strings intersect is at position %dn, length); return 0;输出: Character where strings intersect is at position 3strcspn北京大学程序设计实习课程/49整理课件#include #include int main(void

14、) char *string1 = 1234567890; char *string2 = 123DC8; int length; length = strspn(string1, string2); printf(Character where strings differ is at position %dn, length); return 0;输出: Character where strings differ is at position 3strspn北京大学程序设计实习课程/49整理课件 #include #include int main(void) char input16

15、= abc,de,f; char *p; /* strtok places a NULL terminator in front of the token, if found*/ p = strtok(input, ,); if (p) printf(%sn, p); /* A second call to strtok using a NULL as the first parameter returns a pointer to the character following the token */ p = strtok(NULL, ,);strtok北京大学程序设计实习课程/49整理课

16、件while ( p ) printf(%sn, p);p = strtok(NULL, ,);printf(%sn,input); return 0; 输出:abcdefabc北京大学程序设计实习课程/49整理课件数组作为函数的参数：以地址方式传递参数void myFunction( char str, int array, int length) printf(string in myFunction: %s n, str); if (strlen(str)10) strcpy(str, new string); else strcpy(str, ); for(int i=0; ileng

17、th; i+) arrayi=0; return;#include #include void myFunction( char str, int array, int length);void main() char string=hello world; int intArray5=1,2,3,4,5, i; printf(string in main: %s n, string); printf(the elements of intArray are:); for( i=0; i5; i+) printf(%d , intArrayi); printf(n); myFunction(s

18、tring, intArray, 5); printf(string in main: %s n, string); printf(the elements of intArray are:); for( i=0; i5; i+) printf(%d , intArrayi); return;北京大学程序设计实习课程/49整理课件oOutput:nstring in main: hello worldnthe elements of intArray are:1 2 3 4 5nstring in myFunction : hello worldnstring in main: new str

19、ingnthe elements of intArray are:0 0 0 0 0北京大学程序设计实习课程/49整理课件数组作为函数的参数o注意事项n（1）用数组名作函数参数，应该在调用函数和被调用函数中分别定义数组，且数据类型必须一致，否则结果将出错。n（2）C编译系统对形参数组大小不作检查，所以形参数组可以不指定大小。如果指定形参数组的大小，则实参数组的大小必须大于等于形参数组，否则因形参数组的部分元素没有确定值而导致计算结果错误。 北京大学程序设计实习课程/49整理课件多维数组作为函数的参数o二维数组名做函数参数时，形参的语法形式是：类型说明符 形参名 常量表达式M形参数组可以省略一维

20、的长度。n由于实参代表了数组名，是“地址传递”，二维数组在内存中是按行优先存储，并不真正区分行与列，在形参中，就必须指明列的个数，才能保证实参数组与形参数组中的数据一一对应，因此，形参数组中第二维的长度是不能省略的。o调用函数时，与形参数组相对应的实参数组必须也是一个二维数组，而且它的第二维的长度与形参数组的第二维的长度必须相等。 北京大学程序设计实习课程/49整理课件int max_value(int array 4, int row)int i, j, k, max;max = array00;for(i = 0; i row; i+)for(j = 0; j max) max = arr

21、ayij;return(max);void main(void ) static int a34 = 1,3,5,7,2,4,6,8,15,17,34,12;printf(max value is %dn, max_value(a, 3);北京大学程序设计实习课程/49整理课件程序设计练习：POJ1298o问题描述nJulius Caesar 生活在充满危险和阴谋的年代。为了生存，他首次发明了密码，用于军队的消息传递n假设你是Caesar 军团中的一名军官，需要把Caesar 发送的消息破译出来、并提供给你的将军。消息加密的办法是：对消息原文中的每个字母，分别用该字母之后的第5个字母替换（例如

22、：消息原文中的每个字母A都分别替换成字母F），其他字符不 变，并且消息原文的所有字母都是大写的。北京大学程序设计实习课程/49整理课件o输入n最多不超过100个数据集组成。每个数据集由3部分组成p 起始行：STARTp 密码消息：由1到200个字符组成一行，表示Caesar发出的一条消息p 结束行：ENDn在最后一个数据集之后，是另一行：ENDOFINPUTo输出n每个数据集对应一行，是Caesar 的原始消息。密码字母：密码字母：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

23、 G H I J K L M N O P Q R S T Uo样例输入START 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 START IFSLJW PSTBX KZQQ BJQQ YMFY HFJXFW NX RTWJ IFSLJWTZX YMFS MJ END ENDOFINPUT o样例输出IN WAR, EVENTS OF IMPORT

24、ANCE ARE THE RESULT OF TRIVIAL CAUSESI WOULD RATHER BE FIRST IN A LITTLE IBERIAN VILLAGE THAN SECOND IN ROMEDANGER KNOWS FULL WELL THAT CAESAR IS MORE DANGEROUS THAN HE 北京大学程序设计实习课程/49整理课件解题思路o没有难度，关键在于会使用strcmp、strcat、strlennstrcmp：识别输入数据中消息行的开始和结束nstrcat：将消息行中单词后添加空格nstrlen：计算加密消息中每个单词的长度o要注意：scan

25、f、cin每次只读一个单词(WORD)。在密码消息行中，通常有多个单词，单词之间以空格分隔北京大学程序设计实习课程/49整理课件#include #include void decipher(char message);void main() char cipher201,message201;scanf(%s,cipher);while(strcmp(cipher, START)=0)decipher(message);printf(%sn,message);scanf(%s,cipher);return;void decipher(char message)char plain27=VWX

26、YZABCDEFGHIJKLMNOPQRSTU, cipher201;int i, wordLen; scanf(%s,cipher);message0 = 0;while ( strcmp(cipher, END)!=0 ) wordLen = strlen(cipher); for ( i=0; i=A & cipheri 0 ) strcat(message, );strcat(message, cipher);scanf(%s,cipher); return;北京大学程序设计实习课程/49整理课件另一种解法o输入以行入读ngets：读入一行字符串，允许字符串中包含空格ncin.

27、getlineo按行置换#include #include #include void decode(char * message);void main() char cipher201;while(1) cin.getline(cipher,200);if( stricmp( cipher,START ) = 0 )continue;else if( stricmp( cipher,END ) = 0 )continue;else if( stricmp( cipher,ENDOFINPUT ) = 0)break;else decode( cipher);cout cipher endl;

28、void decode(char * message)char plain27=VWXYZABCDEFGHIJKLMNOPQRSTU;int wordlen = strlen(message);for ( int i=0; i wordlen; i+ )if( isalpha(messagei )messagei = plainmessagei-A;北京大学程序设计实习课程/49整理课件程序设计练习：POJ1047o问题描述n当一个N位的整数X满足下列条件时，称其为循环数：X与任意一个整数1Y N相乘时，都将产生一个X的“循环”。即：分别将这两个整数的第1位数字与最后1位数字连在一起，可以得到

29、一个相同的数字循环；当然两个整数在该数字循环中的起始位置不同。例如，142857是一个循环数p 142857 *1 = 142857 142857 *2 = 285714 142857 *3 = 428571 142857 *4 = 571428 142857 *5 = 714285 142857 *6 = 857142 北京大学程序设计实习课程/49整理课件o输入n写一个程序判断一个整数是否是循环数。输入文件是一个整数序列，每个整数长度为260。注意：每个整数前面的零被看作是该整数的一部分，在计算N时要统计。例如“01”是一个2位的整数，而“1”是一个1位的整数。o输出n对每个输入整数，输出

30、一行，说明该整数是否是循环数。北京大学程序设计实习课程/49整理课件o样例输入142857 142856 142858 01 0588235294117647 o样例输出142857 is cyclic 142856 is not cyclic 142858 is not cyclic 01 is not cyclic 0588235294117647 is cyclic 北京大学程序设计实习课程/49整理课件解题思路o高精度的乘法：整数可能达60位n从1乘到N，如何以较低复杂度实现？o如何判断乘积与算数成循环关系?n穷举：N位整数，循环移位可以有N种可能n子串查找方法：1234567 12

31、34 5 67 0 #include #include int myAdd(char product, int digitsLen, int digits);void main()int digits60, digitsLen;char number61, product61,doublenumber121;int i;bool Cyclic;while(scanf(%s, number)!=EOF)digitsLen = strlen(number);for(i=0; idigitsLen; i+)digitsi=numberi-0; strcpy(product, number);strc

32、py(doublenumber, number);strcat(doublenumber, number);Cyclic = true;for(i=2; i0)Cyclic = false;break;if (strstr(doublenumber, product) = NULL ) Cyclic = false;break;if (Cyclic = false )printf(%s is not cyclicn, number);elseprintf(%s is cyclicn, number);return;int myAdd(char product, int digitsLen, i

33、nt digits)int carry = 0, i;carry = 0;for ( i=digitsLen-1; i=0; i-) producti = producti + digitsi + carry;if (producti 9 ) carry = 1;producti = producti - 10;else carry = 0; return (carry);高精度数相加，进位处理问题：为什么carry0就表示这个数不是循环数？以“字符+数”的方式来实现加法，同时使结果为字符串型北京大学程序设计实习课程/49整理课件课堂练习：POJ1936o问题描述：给定两个字符串s和t，请判断s是否是t的子序列。即从t中删除一些字符，将剩余的字符连接起来，即可获得s。o输入：包括若干个测试数据。每个测试数据由两个ASCII码的数字和字母串s和t组成，s和t的长度不超过100000。o输出：对每个测试数据，如果s是t的子序列则输出“Yes”，否则输出“No”。北京大学程序设计实习课程/49整理课件o样例输入sequence subsequence person compressi