1、程序設(shè)計(jì)實(shí)習(xí) 第三講 字符串處理,內(nèi)容提要,字符串的存儲、字符串處理函數(shù) 將數(shù)組傳遞給函數(shù) 例題：ai2767 Caesar密碼 (P115) 例題：單詞排序 例題：ai2744 子串 (P112) 例題：POJ1936 All in All,字符串,每個字符串是一個特殊的數(shù)組，滿足兩個條件 元素的類型為char 最后一個元素的值為0 ,Ascii碼就是 0 以字符型數(shù)組存儲 從0號元素開始存儲 最大可以存儲長度為N-1的字符串，N是數(shù)組的大小。 字符串“hello”在長度為10的字符串?dāng)?shù)組中的存儲,h,e,l,l,o,0,字符串處理函數(shù),將格式化數(shù)據(jù)寫入字符串：sprintf 字符串長度查詢

2、函數(shù)： strlen 字符串復(fù)制函數(shù)：strcpy、strncpy 字符串連接函數(shù)： strcat 字符串比較函數(shù)： strcmp、strncmp、stricmp、strnicmp 字符串搜索函數(shù)： strcspn、strspn、strstr、strtok、strchr 字符串大小寫轉(zhuǎn)換函數(shù)： strlwr、strupr 這些函數(shù)都要求 #include ,把”hello world”復(fù)制到str2,把str2復(fù)制到str1,查詢str1中字符串的長度,字符串拷貝和求字符串長度,char *strcpy(char *dest, const char *src); int strlen(cons

3、t char *s);,#include #include void main() char str110=hello, str212; 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(%sn, str1); return; ,輸出結(jié)果： length:5(str1); 11(str2)

4、length:11(str1); 11(str2) hello world str1存儲了11個非0字符？ strcpy在復(fù)制字符串str2到str1時，不檢查str2是否超出了str1的存儲容量，而是直接將str2中存儲的字符串復(fù)制到從str1開始的一段連續(xù)區(qū)域 在程序中要特別注意這種情況所引發(fā)的程序運(yùn)行 不確定性,h,e,l,l,o,0,str1,str2,main(),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,str

5、2,strcpy(str1,str2);,w,o,r,l,d,0,用strlen時常犯的錯誤,int MyStrchr(char * s, char c) /看s中是否包含 c for( int i = 0; i strlen(s) -1 ; i + ) if( si = c) return 1; return 0; 哪里不好？這個函數(shù)執(zhí)行時間和 s 的長度是什么關(guān)系？,strlen 是一個o(N)的函數(shù)，每次判斷 i strlen(s) 1 都要執(zhí)行，太浪費(fèi)時間了,#include #include void main() char str1100=hello, str210=_; strc

6、at(str1, world ); printf(%sn, str1); strcat(str1, str2); printf(%sn, str1); return; ,把”world”添加到str1中原字符串的末尾,字符串添加 strcat,把str2中的字符串添加到str1中原字符串的末尾,char *strcat(char *dest, const char *src);,把src內(nèi)容加到dest后面，同樣不會考慮 dest是否夠長,輸出： hello world hello world _,字符串比較函數(shù)strcmp（分大小寫）、stricmp（不分大小寫）,int strcmp(co

7、nst char *s1, const char *s2);,int stricmp(const char *s1, const char *s2);,Return Value If s1 is.return value is. less than s2 0,Compares one string to another, without case sensitivity.,Return Value If s1 is.return value is. less than s2 0,關(guān)于 stricmp 的注意事項(xiàng)stricmp 不是嚴(yán)格意義上的C+標(biāo)準(zhǔn)庫函數(shù)，所以不同編譯器的實(shí)現(xiàn)有所不同。比如在

8、POJ上交題，編譯器選C+時，該函數(shù)應(yīng)寫為：_stricmp不同編譯器的 _stricmp 庫函數(shù)執(zhí)行過程也可能不一樣，有的是把小寫轉(zhuǎn)換成大寫后比較，有的是把大寫轉(zhuǎn)換成小寫后比較，所以，在待比較字符串里面有非字母字符，比如標(biāo)點(diǎn)符號時，不同編譯器的 _stricmp執(zhí)行的結(jié)果有可能不同,字符串比較函數(shù)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 fo

9、x; 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; ,輸出： Compare strings: The quick brown dog jumps over

10、the lazy fox The QUICK brown dog jumps over the lazy fox strcmp: result=1 stricmp: result=0,查找子串strstr,char *strstr(char *s1, char *s2); Scans a string for the occurrence of a given substring. 查找給定字符串在字符串中第一次出現(xiàn)的位置，返回位置指針 strstr scans s1 for the first occurrence of the substring s2. Return Value strs

11、tr 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中第一次出現(xiàn)s2的位置 如果找不到，返回 NULL,查找子串strstr,#include #include char str = lazy; char string = The quick brown dog jumps over the lazy fox; void main( void ) char *p

12、dest; int result; pdest = strstr( string, str ); result = pdest - string + 1; if( pdest != NULL ) printf( %s found at position %dnn, str, result ); else printf( %s not foundn, str ); 輸出： lazy found at position 36,在string中搜索str，返回str在string中第一次出現(xiàn)的位置,在字符串中查找字符 strchr,char *strchr(char *s, int c);,Scan

13、s a string for the first occurrence of a given character. 查找給定字符在字符串中第一次出現(xiàn)的位置，返回位置指針 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 o

14、f the character c in s; if c does not occur in s, strchr returns null.,在字符串中查找字符 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 - string + 1; if( pdest != NULL ) p

15、rintf( Result:tfirst %c found at position %dnn, ch, result ); else printf( Result:t%c not foundn ); 輸出： Result: first r found at position 12,在string中搜索ch，返回str在string中第一次出現(xiàn)的位置,字符串部分拷貝 strncpy,char *strncpy(char *dest, char *src, int maxlen); 將前 maxlen 個字符從src拷貝到dest 1）如果src中字符不足 maxlen 個，則連0一起拷貝，0后面

16、的不拷貝 2) 如果src中字符大于等于maxlen個，則拷貝 maxlen個字符,#include using namespace std; #include int main(void) char s120 = 1234567890; char s2 = abcd ; strncpy( s1,s2,5); cout s1 endl; strcpy( s1,1234567890); strncpy( s1,s2,4); cout s1 endl; return ; ,字符串部分拷貝 strncpy,輸出： abcd abcd567890,數(shù)組作為函數(shù)的參數(shù),#include using na

17、mespace std; char str1200 = Hello,World; char str2100 = Computer; void swap( char s1 , char * s2) /交換兩個字符串的內(nèi)容 char c; for( int i = 0; s1i | s2i; i + ) / 0的Ascii 碼就是 0 c = s2i; s2i = s1i; s1i = c; int main() swap(str1,str2); cout str1 endl str2; return 0; ,輸出： Computer Hello,World,例題：ai2767 Caesar密碼

18、(P115),問題描述 Julius Caesar 生活在充滿危險(xiǎn)和陰謀的年代。為了生存，他首次發(fā)明了密碼，用于軍隊(duì)的消息傳遞 假設(shè)你是Caesar 軍團(tuán)中的一名軍官，需要把Caesar 發(fā)送的消息破譯出來、并提供給你的將軍。消息加密的辦法是：對消息原文中的每個字母，分別用該字母之后的第5個字母替換（例如：消息原文中的每個字母A都分別替換成字母F，V替換成A,W替換成B），其他字符不 變，并且消息原文的所有字母都是大寫的。,輸入 最多不超過100個數(shù)據(jù)集組成。每個數(shù)據(jù)集由3部分組成 起始行：START 密碼消息：由1到200個字符組成一行，表示Caesar發(fā)出的一條消息 結(jié)束行：END 在最后

19、一個數(shù)據(jù)集之后，是另一行：ENDOFINPUT 輸出 每個數(shù)據(jù)集對應(yīng)一行，是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,樣例輸入 START NS BFW, JAJSYX TK NRUTWYFSHJ FWJ YMJ WJXZQY TK YWNANFQ HFZXJX END START N BTZQI WFYMJW GJ KNWXY NS F QNYYQJ NGJWNFS ANQQFLJ

20、 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 T

21、HAN HE,#include #include using namespace std; int main() char szLine300; while( cin.getline(szLine,210) ) /可用此方式判斷數(shù)據(jù)是否讀完 /*cin.getline 讀取一行，第一個參數(shù)是緩沖區(qū)地址；第二個參數(shù)是緩沖區(qū)大小，為了防止越界用的。緩沖區(qū)不夠大，就自動截?cái)?。它會自動往緩沖區(qū)末尾添加 0。*/ if( strcmp( szLine,ENDOFINPUT) = 0) break; cin.getline(szLine,210); /讀取密文 for( int i = 0; szLine

22、i; i + ) if( szLinei = A ,輸入若干行單詞（不含空格），請按字典序排序輸出。大小寫有區(qū)別。單詞一共不超過100行，每個單詞不超過20字符 Sample input: What man Tell About back,例題：單詞排序,Sample output: About Tell What back man,用什么保存多個單詞？,例題：單詞排序,答：用二維字符數(shù)組 char Word10030; 則表達(dá)式 Wordi 的類型就是 char * Wordi 就是數(shù)組中的一行，就是一個字符串 Wordi0 就是Wordi 這個字符串的頭一個字符 二維字符數(shù)組也能初始化，例

23、如： char week710=Saturday, Sunday, Monday, Tuesday, Wednesday, Thursday, Friday;,#include #include #include char Word10030; int MyCompare( const void * e1, const void * e2 ) return strcmp( (char * ) e1, (char * ) e2 ); int main() int n = 0; /單詞個數(shù) while(scanf(%s,Wordn) != EOF ,例題：單詞排序,為了對付有可能最后一行讀入的是空

24、行,例題：ai2744 子串 (P112),問題描述：給出一些由英文字符組成的大小寫敏感的字符串的集合s，請找到一個最長的字符串x，使得對于s中任意字符y，x或者是y的子串，或者x中的字符反序之后得到的新字符串是y的子串。 輸入：輸入的第一行是一個整數(shù)t (1 = t = 10)，t表示測試數(shù)據(jù)的數(shù)目。對于每一組測試數(shù)據(jù)，第一行是一個整數(shù)n (1 = n = 100)，表示已經(jīng)給出n個字符串。接下來n行，每行給出一個長度在1和100之間的字符串。,輸出：對于每一組測試數(shù)據(jù)，輸出一行，給出題目中要求的字符串x的長度。 Sample Input: 2 3 ABCD BCDFF BRCD 2 ros

25、e orchid,例題：ai2744 子串 (P112),Sample Output2 2,思路： 隨便拿出輸入數(shù)據(jù)中的一個字符串，從長到短找出它的所有子串，直到找到否符合題目要求的。,例題：ai2744 子串 (P112),改進(jìn)： 不要隨便拿，要拿輸入數(shù)據(jù)中最短的那個。從長到短找出它的所有子串，直到找到否符合題目要求的。,#include #include int t, n; char str100101; int searchMaxSubString(char* source); int main() int i, minStrLen, subStrLen; char minStr101;

26、 scanf(%d, ,_strrev (char * s) 將字符串 s 顛倒,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+) /搜索長度為su

27、bStrLen的全部子串 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 ,例題：POJ1936 All in All,問題描述：給定兩個字符串s和t，請判斷s是否是t的子序列。即從t中刪除一些字符，將剩余的字符連接起來，即可獲得s。 輸入：包括若干個測試數(shù)據(jù)。每個測試數(shù)據(jù)由兩個ASCII碼的數(shù)字和字母串s和t組成， s和t的長度不超過100000。 輸出：對每個測試數(shù)據(jù)，如果s是t的子序列則輸出“Yes”，否則輸出“No”。,樣例輸入 sequence subsequence person compression VERDI vivaVi