北大的高级程序设计ppt课件.ppt

1、程序设计实习第五讲 字符串处理,主讲教师：田永鸿 2008年3月5日,1,2,内容提要,字符串的存储、字符串处理函数 将数组传递给函数 程序阅读练习 程序设计练习 作业,3,字符串,每个字符串是一个特殊的数组，满足两个条件 元素的类型为char 最后一个元素的值为0 以字符型数组存储 从0号元素开始存储 最大可以存储长度为N-1的字符串，N是数组的大小。 字符串“hello”在长度为10的字符串数组中的存储,h,e,l,l,o,0,4,字符串处理函数,将格式化数据写入字符串：sprintf 字符串长度查询函数： strlen 字符串复制函数：strcpy、strncpy 字符串连接函数： st

2、rcat 字符串比较函数： strcmp、strncmp、stricmp、strnicmp 字符串搜索函数： strcspn、strspn、strstr、strtok、strchr 字符串大小写转换函数： strlwr、strupr,5,把”hello world”复制到str2,把str2复制到str1,查询str1中字符串的长度,strcpy、strlen,#include #include void main() char str110=hello, str212; strcpy(str2, hello world); printf(length:%d(str1); %d(str2)n,

3、 strlen(str1), strlen(str2); strcpy(str1, str2); printf(length:%d(str1); %d(str2)n, strlen(str1), strlen(str2); printf(%sn, str1); return; ,6,Output length:5(str1); 11(str2) length:11(str1); 11(str2) hello world str1存储了11个非n字符？ strcpy在复制字符串str2到str1时，不检查str2是否超出了str1的存储容量，而是直接将str2中存储的字符串复制到从str1开始的

4、一段连续区域 在程序中要特别注意这种情况所引发的程序运行 不确定性,7,h,e,l,l,o,0,str1,str2,h,e,l,l,o,0,str1,h,e,l,l,o,w,o,r,l,d,0,str2,strcpy(str2, hello world);,h,e,l,l,o,str1,h,e,l,l,o,w,o,r,l,d,0,str2,strcpy(str1,str2);,w,o,r,l,d,0,main(),8,把”world”添加到str1中原字符串的末尾,strcat,#include #include void main() char str115=hello, str25=_,

5、str35=! ; strcat(str1, world); printf(%sn, str1); strcat(str1, str2); printf(%sn, str1); strcat(str1, str3); printf(%sn, str1); return; ,把str2中的字符串添加到str1中原字符串的末尾,9,h,e,l,l,o,0,str1,-,0,str2,main(),strcat(str1, world);,!,0,!,!,0,str3,h,e,l,l,o,w,o,r,l,str1,d,0,-,0,str2,!,!,0,str3,strcat(str1, str2);

6、,h,e,l,l,o,w,o,r,l,str1,d,-,0,-,0,str2,!,!,0,str3,strcat(str1, str3);,h,e,l,l,o,w,o,r,l,str1,d,-,!,-,0,str2,!,!,0,str3,10,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; void main( void ) int res

7、ult; 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; ,11,Output: strcmp: result=1 strcmp: result=0,12,字符串比较函数汇总,strcmp(const char *s1,

8、 const char *s2)：对串s1和s2进行无符号比较，直至对应字符不同或到串尾 stricmp(const char *s1, const char *s2)：对串s1和s2进行无符号比较，忽略字符的大小写 strncmp(const char *s1, const char *s2, size _t maxlen)：对串s1和s2进行无符号比较， 最多只比较maxlen个字符 strnicmp：对串s1和s2进行无符号比较，忽略字符的大小写， 最多只比较maxlen个字符,13,字符串搜索函数汇总,strchr(const char *s, char c)：在串s中正向查找字符c

9、strstr(const char *s1, const char *s2)：在串s1中找串s2的第一次出现 strcspn(const char *s1, const char *s2)：在串s1中找“串s2中任何字符”出现的第一次位置 strspn(const char *s1, const char *s2)：在串s1中找“不是串s2字符”的第一次出现位置 strtok(const char *s1, const char *s2)：将s1看成包含0个或多个文本单词的序列，由分隔符串s2中1个或多哦个字符分隔 第一次调用strtok时，返回指向s1中第一个单词的第一个字符，并在返回单词好

10、后立即写0到s1中第一个单词的尾部之后 后继的调用用NULL作为第一个参数，将继续用这种方法扫描s1，直到没有剩余单词,14,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 = strstr( string, str ); result = pdest - string + 1; if( pdest != NULL ) printf( %s fo

11、und at position %dnn, str, result ); else printf( %s not foundn, str ); ,在string中搜索str，返回str在string中第一次出现的位置,15,strchr,#include #include 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 - st

12、ring + 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中第一次出现的位置,16,#include #include int main(void) char *string1 = 1234567890; char *string2 = 747DC8; int length; length = strcspn(string1, string2

13、); printf(Character where strings intersect is at position %dn, length); return 0; 输出: Character where strings intersect is at position 3,strcspn,17,#include #include int main(void) char *string1 = 1234567890; char *string2 = 123DC8; int length; length = strspn(string1, string2); printf(Character wh

14、ere strings differ is at position %dn, length); return 0; 输出: Character where strings differ is at position 3,strspn,18,#include #include int main(void) char input16 = 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);

15、 /* 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,19,while ( p ) printf(%sn, p); p = strtok(NULL, ,); printf(%sn,input); return 0; 输出: abc de f abc,20,数组作为函数的参数：以地址方式传递参数,void myFunction( char str, in

16、t 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; ilength; 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

17、, 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(string, intArray, 5); printf(string in main: %s n, string); printf(the elements of intArray are:); for( i=0; i5; i+) printf(%d , intArrayi); return; ,22,O

18、utput: string in main: hello world the elements of intArray are:1 2 3 4 5 string in myFunction : hello world string in main: new string the elements of intArray are:0 0 0 0 0,23,数组作为函数的参数,注意事项 （1）用数组名作函数参数，应该在调用函数和被调用函数中分别定义数组，且数据类型必须一致，否则结果将出错。 （2）C编译系统对形参数组大小不作检查，所以形参数组可以不指定大小。如果指定形参数组的大小，则实参数组的大小

19、必须大于等于形参数组，否则因形参数组的部分元素没有确定值而导致计算结果错误。,24,多维数组作为函数的参数,二维数组名做函数参数时，形参的语法形式是：类型说明符 形参名 常量表达式M形参数组可以省略一维的长度。 由于实参代表了数组名，是“地址传递”，二维数组在内存中是按行优先存储，并不真正区分行与列，在形参中，就必须指明列的个数，才能保证实参数组与形参数组中的数据一一对应，因此，形参数组中第二维的长度是不能省略的。 调用函数时，与形参数组相对应的实参数组必须也是一个二维数组，而且它的第二维的长度与形参数组的第二维的长度必须相等。,25,int max_value(int array 4, in

20、t row) int i, j, k, max; max = array00; for(i = 0; i max) max = arrayij; 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); ,26,程序设计练习：POJ1298,问题描述 Julius Caesar 生活在充满危险和阴谋的年代。为了生存，他首次发明了密码，用于军队的消息传递 假设你是Caesar 军团中的一名军官，需要把Caesar 发送的

21、消息破译出来、并提供给你的将军。消息加密的办法是：对消息原文中的每个字母，分别用该字母之后的第5个字母替换（例如：消息原文中的每个字母A都分别替换成字母F），其他字符不 变，并且消息原文的所有字母都是大写的。,27,输入 最多不超过100个数据集组成。每个数据集由3部分组成 起始行：START 密码消息：由1到200个字符组成一行，表示Caesar发出的一条消息 结束行：END 在最后一个数据集之后，是另一行：ENDOFINPUT 输出 每个数据集对应一行，是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

22、 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,样例输入 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

23、 样例输出 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,29,解题思路,没有难度，关键在于会使用strcmp、strcat、strlen strcmp：识别输入数据中消息行的开始和结束 strcat：将消息行中单词后添加空格 strlen：计算加密消息中

24、每个单词的长度 要注意：scanf、cin每次只读一个单词(WORD)。在密码消息行中，通常有多个单词，单词之间以空格分隔,30,#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

25、plain27=VWXYZABCDEFGHIJKLMNOPQRSTU, cipher201; int i, wordLen; scanf(%s,cipher); message0 = 0; while ( strcmp(cipher, END)!=0 ) wordLen = strlen(cipher); for ( i=0; i=A ,32,另一种解法,输入以行入读 gets：读入一行字符串，允许字符串中包含空格 cin.getline 按行置换,#include #include #include void decode(char * message); void main() char

26、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; ,void decode(char * message) char plain27= VWXYZABCDEFGHIJKLMNOPQRSTU; int

27、 wordlen = strlen(message); for ( int i=0; i wordlen; i+ ) if( isalpha(messagei ) messagei = plainmessagei-A; ,35,程序设计练习：POJ1047,问题描述 当一个N位的整数X满足下列条件时，称其为循环数：X与任意一个整数1Y N相乘时，都将产生一个X的“循环”。即：分别将这两个整数的第1位数字与最后1位数字连在一起，可以得到一个相同的数字循环；当然两个整数在该数字循环中的起始位置不同。例如，142857是一个循环数 142857 *1 = 142857 142857 *2 = 285

28、714 142857 *3 = 428571 142857 *4 = 571428 142857 *5 = 714285 142857 *6 = 857142,36,输入 写一个程序判断一个整数是否是循环数。输入文件是一个整数序列，每个整数长度为260。注意：每个整数前面的零被看作是该整数的一部分，在计算N时要统计。例如“01”是一个2位的整数，而“1”是一个1位的整数。 输出 对每个输入整数，输出一行，说明该整数是否是循环数。,37,样例输入 142857 142856 142858 01 0588235294117647 样例输出 142857 is cyclic 142856 is no

29、t cyclic 142858 is not cyclic 01 is not cyclic 0588235294117647 is cyclic,38,解题思路,高精度的乘法：整数可能达60位 从1乘到N，如何以较低复杂度实现？ 如何判断乘积与算数成循环关系? 穷举：N位整数，循环移位可以有N种可能 子串查找方法：,#include #include int myAdd(char product, int digitsLen, int digits); void main() int digits60, digitsLen; char number61, product61,doublenu

30、mber121; int i; bool Cyclic; while(scanf(%s, number)!=EOF) digitsLen = strlen(number); for(i=0; idigitsLen; i+) digitsi=numberi-0; strcpy(product, number); strcpy(doublenumber, number); strcat(doublenumber, number);,Cyclic = true; for(i=2; i0) Cyclic = false; break; if (strstr(doublenumber, product)

31、 = NULL ) Cyclic = false; break; if (Cyclic = false ) printf(%s is not cyclicn, number); else printf(%s is cyclicn, number); return; ,int myAdd(char product, int digitsLen, int digits) int carry = 0, i; carry = 0; for ( i=digitsLen-1; i=0; i-) producti = producti + digitsi + carry; if (producti 9 )

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