PowerPoint Presentation

Size: px

Start display at page:

Download "PowerPoint Presentation"

蒂钮
6 years ago
Views:

1 程序设计 II 第 4 讲字符串处理计算机学院黄章进 zhuang@ustc.edu.cn

2 内容字符串处理函数例题 :Caesar 密码 2767 例题 : 单词排序例题 : 子串 2744 例题 :All in All

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

4 字符串的读与写 Writing a string is easy using either printf or puts. Reading a string is a bit harder, because the input may be longer than the string variable into which it s being stored. To read a string in a single step, we can use either scanf or gets. As an alternative, we can read strings one character at a time.

5 用 printf 和 puts 写字符串字符串的读与写 The %s conversion specification allows printf to write a string: char str[] = "Are we having fun yet?"; printf("%s\n", str); The output will be Are we having fun yet? printf writes the characters in a string one by one until it encounters a null character.

6 用 printf 和 puts 写字符串字符串的读与写 To print part of a string, use the conversion specification %.ps. p is the number of characters to be displayed. The statement printf("%.6s\n", str); will print Are we

7 用 printf 和 puts 写字符串字符串的读与写 The %ms conversion will display a string in a field of size m. If the string has fewer than m characters, it will be right-justified within the field. To force left justification instead, we can put a minus sign in front of m. The m and p values can be used in combination. A conversion specification of the form %m.ps causes the first p characters of a string to be displayed in a field of size m.

8 用 printf 和 puts 写字符串字符串的读与写 printf isn t the only function that can write strings. The C library also provides puts: puts(str); After writing a string, puts always writes an additional new-line character.

9 用 scanf 和 gets 读字符串字符串的读与写 The %s conversion specification allows scanf to read a string into a character array: scanf("%s", str); str is treated as a pointer, so there s no need to put the & operator in front of str. When scanf is called, it skips white space, then reads characters and stores them in str until it encounters a white-space character. scanf always stores a null character at the end of the string.

10 用 scanf 和 gets 读字符串字符串的读与写 scanf won t usually read a full line of input. A new-line character will cause scanf to stop reading, but so will a space or tab character. To read an entire line of input, we can use gets. Properties of gets: Doesn t skip white space before starting to read input. Reads until it finds a new-line character. Discards the new-line character instead of storing it; the null character takes its place.

11 用 scanf 和 gets 读字符串字符串的读与写 Consider the following program fragment: char sentence[sent_len+1]; printf("enter a sentence:\n"); scanf("%s", sentence); Suppose that after the prompt Enter a sentence: the user enters the line To C, or not to C: that is the question. scanf will store the string "To" in sentence.

12 用 scanf 和 gets 读字符串字符串的读与写 Suppose that we replace scanf by gets: gets(sentence); When the user enters the same input as before, gets will store the string " To C, or not to C: that is the question." in sentence.

13 用 scanf 和 gets 读字符串字符串的读与写 As they read characters into an array, scanf and gets have no way to detect when it s full. Consequently, they may store characters past the end of the array, causing undefined behavior. scanf can be made safer by using the conversion specification %ns instead of %s. n is an integer indicating the maximum number of characters to be stored. gets is inherently unsafe; fgets is a much better alternative.

14 字符串处理函数 #include <string.h> 将格式化数据写入字符串 :sprintf 字符串长度查询函数 : strlen 字符串复制函数 :strcpy strncpy 字符串连接函数 : strcat 字符串比较函数 : strcmp strncmp _stricmp _strnicmp 字符串搜索函数 : strcspn strspn strstr strtok strchr 字符串大小写转换函数 : strlwr strupr 14

15 字符串拷贝和求字符串长度 char *strcpy(char *dest, const char *src); int strlen(const char *s); #include <stdio.h> #include <string.h> int 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 0; 把 "hello world" 复制到 str2 把 str2 复制到 str1 查询 str1 中字符串的长度 } 15

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

17 strcpy 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

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

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

20 字符串比较函数 int strcmp(const char *s1, const char *s2); 区分大小写 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); 不分大小写, 不是标准 C 库函数 20

21 字符串比较函数 #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"; int 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 0; } 21

22 字符串比较函数输出 : 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 22

23 查找子串 strstr char *strstr(char *s1, char *s2); 查找给定字符串在字符串中第一次出现的位置, 返回位置指针如果找到, 返回指针, 指向 s1 中第一次出现 s2 的位置如果找不到, 返回 NULL 23

24 查找子串 strstr #include <string.h> #include <stdio.h> char str[] = "lazy"; char string[] = "The quick brown dog jumps over the lazy fox"; int main( void ) { char *pdest; int result; pdest = strstr( string, str ); result = pdest - string + 1; if ( pdest!= NULL ) 输出 : lazy found at position 36 printf( "%s found at position %d\n\n", str, result ); else printf( "%s not found\n", str ); return 0; } 24

25 查找字符 strchr char *strchr(char *s, int c); 查找给定字符在字符串中第一次出现的位置, 返回位置指针如果找到, 返回指针, 指向 c 在 s 中第一次出现的位置如果找不到, 返回 NULL 25

26 查找字符 strchr #include <string.h> #include <stdio.h> int ch = 'r'; char string[] = "The quick brown dog jumps over the lazy fox"; int 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" ); return 0; 输出 : Result: first r found at position 12 26

27 字符串部分拷贝 strncpy char *strncpy(char *dest, char *src, int maxlen); 将前 maxlen 个字符从 src 拷贝到 dest 如果 src 中字符不足 maxlen 个, 则连 '\0' 一起拷贝, '\0' 后面的不拷贝如果 src 中字符大于等于 maxlen 个, 则拷贝 maxlen 个字符返回值 :dest 的地址 27

28 字符串部分拷贝 strncpy #include <string.h> #include <stdio.h> int main(void) { char s1[20] = " "; char s2[] = "abcd" ; strncpy( s1, s2, 5); printf("%s\n", s1); strcpy( s1, " "); strncpy( s1, s2, 4); printf("%s\n", s1); return 0; } 输出 : abcd abcd

29 数组作为函数参数 #include <stdio.h> char str1[200] = "Hello, World"; char str2[100] = "Computer"; void swap( char s1[ ], char *s2) // 交换两个字符串的内容 { char c; int i; for ( 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); printf("%s\n%s\n", str1, str2); return 0; } 输出 : Computer Hello, World 29

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

31 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 G H I J K L M N O P Q R S T U 输入最多不超过 100 个数据集组成每个数据集由 3 部分组成起始行 :START 密码消息 : 由 1 到 200 个字符组成一行, 表示 Caesar 发出的一条消息结束行 :END 在最后一个数据集后, 是另一行 :ENDOFINPUT 输出每个数据集对应一行, 是 Caesar 的原始消息 31

32 Caesar 密码输入样例 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 输出样例 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 32 HE

33 Caesar 密码问题分析关键是识别输入数据中的消息行读入消息行的数据输入数据中, 每个消息行包括多个单词以及若干个标点符号识别非字母符号采用哪种输入函数, 可以用 scanf 吗? 33

34 2767 Caesar 密码 #include<stdio.h> #include<string.h> int main(void) { char s[201]; char map[] = "VWXYZABCDEFGHIJKLMNOPQRSTU"; while(1) { gets(s); if (strcmp(s, "ENDOFINPUT")==0) break; if (strcmp(s, "START")==0 strcmp(s, "END")==0) int len = strlen(s); for (int i = 0; i < len; i++) { if (s[i] >= A && s[i] <= Z ) // 请写出下一行代码 continue; else printf("%c", s[i]); } printf("\n"); } return 0; } 34

35 例题 : 单词排序输入若干行单词 ( 不含空格 ), 请按字典序排序输出大小写有区别单词一共不超过 100 行, 每个单词不超过 20 字符输入样例 What man Tell About back 输出样例 About Tell What back man 35

36 单词排序用什么保存多个单词? 采用二维字符数组 char Word[100][21]; 则表达式 Word[i] 的类型就是 char[21] Word[i] 就是数组中的一行, 就是一个字符串 Word[i][0] 就是 Word[i] 这个字符串的头一个字符如何排序? qsort 36

37 qsort 函数 qsort 函数是 ANSI C 标准库中提供的可给任意数组排序的通用函数, 声明在 stdlib.h 文件中因为数组元素可能是任何类型的, 必须告诉 qsort 如何确定两个数组元素哪一个更小通过传递给 qsort 一个比较函数指针 37

38 qsort 函数 void qsort( void *base, size_t nelem, size_t size, int (*comp)(const void *,const void *) ); 对数组按升序排序 base 指向待排序数组的第一个元素 nelem 待排序元素的个数 size 数组元素的大小 ( 字节数 ) comp 指向比较函数的指针 int comp(const void *a, const void *b); *a 小于 *b, 返回负整数值 *a 等于 *b, 返回 0 *a 大于 *b, 返回正整数值 38

39 qsort 函数 #include <stdio.h> #include <stdlib.h> int compare_ints(const void* a, const void* b) { int arg1 = *(const int*)a; int arg2 = *(const int*)b; return (arg1 - arg2); } int main(void) { int i, ints[] = { -2, 99, 0, -743, 2, 3, 4 }; int size = sizeof ints / sizeof *ints; qsort(ints, size, sizeof(int), compare_ints); for (i = 0; i < size; i++) { printf("%d ", ints[i]); } printf("\n"); return EXIT_SUCCESS; } 输出 :

40 单词排序 #include <stdlib.h> #include <stdio.h> #include <string.h> int MyCompare( const void *e1, const void *e2 ) { // 请写出下一行代码 } int main() { int n = 0; // 单词个数 char Words[100][21]; } 为了处理有可能最后一行读入的是空行 while (scanf("%s", Words[n])!= EOF && Words[n][0]) n++; qsort(words, n, sizeof(words[0]), MyCompare); for ( int i = 0; i < n; i++ ) printf("%s\n", Words[i]); return 0; 40

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

42 子串输入样例 2 3 ABCD BCDFF BRCD 2 rose orchid 输出样例

43 子串思路 : 随便拿出输入数据中的一个字符串, 从长到短找出它的所有子串, 直到找到否符合题目要求的子串改进 : 不要随便拿, 要拿输入数据中最短的那个从长到短找出它的所有子串, 直到找到否符合题目要求的子串 43

44 2744 子串 #include <stdio.h> #include <string.h> #include <stdbool.h> int searchmaxsubstring(char* source); int n; char str[100][101]; int main(){ int i, t, 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; } 44

45 子串 int searchmaxsubstring(char* source){ int substrlen = strlen(source), sourcestrlen = strlen(source); int i, j; 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'; strrev1(revsubstr); // 将字符串反序, 也可调用非标准 C 库函数 _strrev bool 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; } 45

46 子串 char *strrev1(char *source) { char temp[200]; int i, len = strlen(source); strcpy(temp, source); for(i = 0; i < len; i++) source[i] = temp[len-1-i]; } return source; 46

47 例题 :All in All 问题描述给定两个字符串 s 和 t, 请判断 s 是否是 t 的子序列即从 t 中删除一些字符, 将剩余的字符连接起来, 即可获得 s 输入包括若干个测试数据每个测试数据由两个 ASCII 码的数字和字母串 s 和 t 组成, s 和 t 的长度不超过输出对每个测试数据, 如果 s 是 t 的子序列则输出 "Yes", 否则输出 "No" 47

48 All in All 输入样例 :s t sequence subsequence person compression VERDI vivavittorioemanuelerediitalia casedoesmatter CaseDoesMatter 输出样例 Yes No Yes No 48

49 All in All 思路关键是看 t 中是否可以找到 s 的所有字符, 而且顺序与 s 一致设两个指针, 分别指向 s 和 t 的开头 t 的指针不停向前每次移动一个字符, 如果 t 的指针指向的字符和 s 的指针指向的字符相同, 则将 s 的指针向前移动一个字符直到 s 的指针指向末尾的 '\0', 说明 Yes; 或 t 的指针指向末尾的 '\0' 时,s 的指针还没有指到末尾, 说明 No 49

50 2976 All in All #include <stdio.h> int main() { int i, j; // i 指向 s, j 指向 t char s[100001], t[100001]; while (scanf( %s%s, s, t) > 0 ) { // 请写出循环体代码 } } return 0; 50

51 bsearch 函数 C 语言中可以用 bsearch 实现二分查找同 qsort 一样,bsearch 也包含在 <stdlib.h> 库中, 且同样要自定义比较函数 bsearch 函数在有序数组中搜索一个特定的值 ( 键 ) qsort 函数可以对任何数组进行排序可以在 bsearch 函数搜索数组之前先用 qsort 函数对其进行排序 51

52 bsearch 函数 void* bsearch( const void *key, const void *base, size_t nelem, size_t size, int (*comp)(const void*, const void*) ); 在有序数组中查找值等于 *key 的元素 key 指向键值 base 指向待查找数组的第一个元素 nelem 待查找元素的个数 size 数组元素的大小 ( 字节数 ) comp 指向比较函数的指针待查找数组必须是已按照 comp 规则升序排序返回值 : 一个指向与键匹配的元素的指针 ; 找不到, 则返回空指针若有多个元素与键值相等, 返回哪个元素的指针是未定的 52

53 bsearch 函数 #include <stdio.h> #include <stdlib.h> int compare(const void *p, const void *q) { return (*(int *)p - *(int *)q); } int main(void) { int array[8] = {9, 2, 7, 11, 3, 87, 34, 6}; int key = 3; int *p; qsort(array, 8, sizeof(int), compare); 输出 : found p = (int *) bsearch(&key, array, 8, sizeof(int), compare); (p == NULL)? puts("not found") : puts("found"); return 0; } 53

54 bsearch 函数 #include <stdlib.h> #include <stdio.h> struct data { int nr; char const *value; } dat[] = { {1, "Foo"}, {2, "Bar"}, {3, "Hello"}, {4, "World"} }; int data_cmp(void const *lhs, void const *rhs) { struct data const *const l = lhs; struct data const *const r = rhs; return (l->nr > r->nr) - (l->nr < r->nr); // 返回 1, 0 or -1 } 54

55 bsearch 函数 int main(void) { } struct data key = {.nr = 3 }; struct data const *res = bsearch(&key, dat, sizeof(dat)/sizeof(dat[0]), if (!res) { sizeof(dat[0]), data_cmp); printf("no %d not found\n", key.nr); } else { } printf("no %d: %s\n", res->nr, res->value); 输出 : No 3: Hello 55

56 词典作业提示采用 bsearch 查找函数怎么判断读到空行? char s[100]; 可以用 gets(s) 一次读取一行, 然后再用 sscanf 从 s 中分出英文和外文 gets(s) 读到空行时,s 的长度为 0, 即 s[0] = 0 读到文件尾时,gets 返回 NULL scanf 返回 EOF 也可以说明到了文件尾巴注意 : 文件尾可能有空行 57

新・明解Ｃ言語入門編『索引』

新・明解Ｃ言語入門編『索引』 !... 75!=... 48 "... 234 " "... 9, 84, 240 #define... 118, 213 #include... 148 %... 23 %... 23, 24 %%... 23 %d... 4 %f... 29 %ld... 177 %lf... 31 %lu... 177 %o... 196 %p... 262 %s... 242, 244 %u... 177