北大的高級(jí)程序設(shè)計(jì)-CPP08-5PPT課件

1、程序設(shè)計(jì)實(shí)習(xí)課程 (C+ Programming Practice)2021/7/231程序設(shè)計(jì)實(shí)習(xí)程序設(shè)計(jì)實(shí)習(xí)第五講第五講 字符串處理字符串處理主講教師：田永鴻http:/ o程序設(shè)計(jì)練習(xí)o作業(yè)北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23字符串o每個(gè)字符串是一個(gè)特殊的數(shù)組，滿足兩個(gè)條件n元素的類型為charn最后一個(gè)元素的值為0o以字符型數(shù)組存儲(chǔ)n從0號(hào)元素開(kāi)始存儲(chǔ)n最大可以存儲(chǔ)長(zhǎng)度為N-1的字符串，N是數(shù)組的大小。o字符串“hello”在長(zhǎng)度為10的字符串?dāng)?shù)組中的存儲(chǔ)hello 0北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23字符串處理函數(shù)o將格式化數(shù)據(jù)寫(xiě)入字符串：sprintfo字

2、符串長(zhǎng)度查詢函數(shù)： strleno字符串復(fù)制函數(shù)：strcpy、strncpyo字符串連接函數(shù)： strcato字符串比較函數(shù)： strcmp、strncmp、stricmp、strnicmpo字符串搜索函數(shù)： strcspn、strspn、strstr、strtok、strchro字符串大小寫(xiě)轉(zhuǎn)換函數(shù)： strlwr、strupr北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23把”hello world”復(fù)制到str2把str2復(fù)制到str1查詢str1中字符串的長(zhǎng)度strcpy、strlen#include #include void main() char str110=hello, s

3、tr212; 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;北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23oOutputnlength:5(str1); 11(str2)nlength:11(str1); 11(str2)nhello world

4、ostr1存儲(chǔ)了11個(gè)非n字符？nstrcpy在復(fù)制字符串str2到str1時(shí)，不檢查str2是否超出了str1的存儲(chǔ)容量，而是直接將str2中存儲(chǔ)的字符串復(fù)制到從str1開(kāi)始的一段連續(xù)區(qū)域n在程序中要特別注意這種情況所引發(fā)的程序運(yùn)行 不確定性北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23hello0 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()北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492

5、021/7/23把”world”添加到str1中原字符串的末尾strcat#include #include 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中原字符串的末尾北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23hello0 str1-0 str2 main()

6、strcat(str1, world); !0 ! !0 str3hellow o r l str1d 0 -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北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23strcmp、stricmp#include #include char string1 = The quick brown dog jumps over the lazy fo

7、x;char string2 = The QUICK brown dog jumps over the lazy fox;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); ret

8、urn;北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23oOutput:nstrcmp: result=1nstrcmp: result=0北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23字符串比較函數(shù)匯總ostrcmp(const char *s1, const char *s2)：對(duì)串s1和s2進(jìn)行無(wú)符號(hào)比較，直至對(duì)應(yīng)字符不同或到串尾ostricmp(const char *s1, const char *s2)：對(duì)串s1和s2進(jìn)行無(wú)符號(hào)比較，忽略字符的大小寫(xiě)ostrncmp(const char *s1, const char *s2, size _t maxlen)：對(duì)串s1和s2進(jìn)行

9、無(wú)符號(hào)比較， 最多只比較maxlen個(gè)字符ostrnicmp：對(duì)串s1和s2進(jìn)行無(wú)符號(hào)比較，忽略字符的大小寫(xiě)， 最多只比較maxlen個(gè)字符北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23字符串搜索函數(shù)匯總ostrchr(const char *s, char c)：在串s中正向查找字符costrstr(const char *s1, const char *s2)：在串s1中找串s2的第一次出現(xiàn)ostrcspn(const char *s1, const char *s2)：在串s1中找“串s2中任何字符”出現(xiàn)的第一次位置ostrspn(const char *s1, const char

10、*s2)：在串s1中找“不是串s2字符”的第一次出現(xiàn)位置ostrtok(const char *s1, const char *s2)：將s1看成包含0個(gè)或多個(gè)文本單詞的序列，由分隔符串s2中1個(gè)或多哦個(gè)字符分隔n第一次調(diào)用strtok時(shí)，返回指向s1中第一個(gè)單詞的第一個(gè)字符，并在返回單詞好后立即寫(xiě)0到s1中第一個(gè)單詞的尾部之后n后繼的調(diào)用用NULL作為第一個(gè)參數(shù)，將繼續(xù)用這種方法掃描s1，直到?jīng)]有剩余單詞北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23strstr#include #include char str = lazy;char string = The quick brown d

11、og 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 %dnn, str, result ); else printf( %s not foundn, str );在string中搜索str，返回str在string中第一次出現(xiàn)的位置北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23strchr#

12、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 ) printf( Result:tfirst %c found at position %dnn, ch, result ); else printf( Result:t%c not f

13、oundn ); 在string中搜索ch，返回str在string中第一次出現(xiàn)的位置北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23#include #include int main(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 s

14、trings intersect is at position 3strcspn北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23#include #include int main(void) 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

15、differ is at position 3strspn北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23 #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); /* A second call to strtok using a NULL as the first parameter re

16、turns a pointer to the character following the token */ p = strtok(NULL, ,);strtok北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23while ( p ) printf(%sn, p);p = strtok(NULL, ,);printf(%sn,input); return 0; 輸出:abcdefabc北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23數(shù)組作為函數(shù)的參數(shù)：以地址方式傳遞參數(shù)void myFunction( char str, int array, int length) printf(string

17、 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;2021/7/23#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:

18、%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;北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23oOutput:ns

19、tring in main: hello worldnthe elements of intArray are:1 2 3 4 5nstring in myFunction : hello worldnstring in main: new stringnthe elements of intArray are:0 0 0 0 0北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23數(shù)組作為函數(shù)的參數(shù)o注意事項(xiàng)n（1）用數(shù)組名作函數(shù)參數(shù)，應(yīng)該在調(diào)用函數(shù)和被調(diào)用函數(shù)中分別定義數(shù)組，且數(shù)據(jù)類型必須一致，否則結(jié)果將出錯(cuò)。n（2）C編譯系統(tǒng)對(duì)形參數(shù)組大小不作檢查，所以形參數(shù)組可以不指定大小。如果指定形參數(shù)組

20、的大小，則實(shí)參數(shù)組的大小必須大于等于形參數(shù)組，否則因形參數(shù)組的部分元素沒(méi)有確定值而導(dǎo)致計(jì)算結(jié)果錯(cuò)誤。 北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23多維數(shù)組作為函數(shù)的參數(shù)o二維數(shù)組名做函數(shù)參數(shù)時(shí)，形參的語(yǔ)法形式是：類型說(shuō)明符 形參名 常量表達(dá)式M形參數(shù)組可以省略一維的長(zhǎng)度。n由于實(shí)參代表了數(shù)組名，是“地址傳遞”，二維數(shù)組在內(nèi)存中是按行優(yōu)先存儲(chǔ)，并不真正區(qū)分行與列，在形參中，就必須指明列的個(gè)數(shù)，才能保證實(shí)參數(shù)組與形參數(shù)組中的數(shù)據(jù)一一對(duì)應(yīng)，因此，形參數(shù)組中第二維的長(zhǎng)度是不能省略的。o調(diào)用函數(shù)時(shí)，與形參數(shù)組相對(duì)應(yīng)的實(shí)參數(shù)組必須也是一個(gè)二維數(shù)組，而且它的第二維的長(zhǎng)度與形參數(shù)組的第二維的長(zhǎng)度必須相等。

21、 北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23int 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 = 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);北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23程序設(shè)計(jì)練習(xí)：POJ1298o問(wèn)題

22、描述nJulius Caesar 生活在充滿危險(xiǎn)和陰謀的年代。為了生存，他首次發(fā)明了密碼，用于軍隊(duì)的消息傳遞n假設(shè)你是Caesar 軍團(tuán)中的一名軍官，需要把Caesar 發(fā)送的消息破譯出來(lái)、并提供給你的將軍。消息加密的辦法是：對(duì)消息原文中的每個(gè)字母，分別用該字母之后的第5個(gè)字母替換（例如：消息原文中的每個(gè)字母A都分別替換成字母F），其他字符不 變，并且消息原文的所有字母都是大寫(xiě)的。北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23o輸入n最多不超過(guò)100個(gè)數(shù)據(jù)集組成。每個(gè)數(shù)據(jù)集由3部分組成p 起始行：STARTp 密碼消息：由1到200個(gè)字符組成一行，表示Caesar發(fā)出的一條消息p 結(jié)束行：E

23、NDn在最后一個(gè)數(shù)據(jù)集之后，是另一行：ENDOFINPUTo輸出n每個(gè)數(shù)據(jù)集對(duì)應(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 U2021/7/23o樣例輸入START NS BFW, JAJSYX TK NRUTWYFSHJ FWJ YMJ WJXZQY TK YWNANFQ HFZXJX END START N BTZQI WFYMJW GJ KNWXY NS F

24、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 IMPORTANCE ARE THE RESULT OF TRIVIAL CAUSESI WOULD RATHER BE FIRST IN A LITTLE IBERIAN VILLAGE THAN SECOND IN ROMEDANGER KNOWS FULL WELL THAT CAESAR

25、 IS MORE DANGEROUS THAN HE 北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23解題思路o沒(méi)有難度，關(guān)鍵在于會(huì)使用strcmp、strcat、strlennstrcmp：識(shí)別輸入數(shù)據(jù)中消息行的開(kāi)始和結(jié)束nstrcat：將消息行中單詞后添加空格nstrlen：計(jì)算加密消息中每個(gè)單詞的長(zhǎng)度o要注意：scanf、cin每次只讀一個(gè)單詞(WORD)。在密碼消息行中，通常有多個(gè)單詞，單詞之間以空格分隔北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23#include #include void decipher(char message);void main() char ciphe

26、r201,message201;scanf(%s,cipher);while(strcmp(cipher, START)=0)decipher(message);printf(%sn,message);scanf(%s,cipher);return;2021/7/23void decipher(char message)char plain27=VWXYZABCDEFGHIJKLMNOPQRSTU, cipher201;int i, wordLen; scanf(%s,cipher);message0 = 0;while ( strcmp(cipher, END)!=0 ) wordLen =

27、 strlen(cipher); for ( i=0; i=A & cipheri 0 ) strcat(message, );strcat(message, cipher);scanf(%s,cipher); return;北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23另一種解法o輸入以行入讀ngets：讀入一行字符串，允許字符串中包含空格ncin.getlineo按行置換2021/7/23#include #include #include void decode(char * message);void main() char cipher201;while(1) cin.ge

28、tline(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;2021/7/23void decode(char * message)char plain27=VWXYZABCDEFGHIJKLMNOPQRSTU;int wordlen = strlen(message);for

29、 ( int i=0; i wordlen; i+ )if( isalpha(messagei )messagei = plainmessagei-A;北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23程序設(shè)計(jì)練習(xí)：POJ1047o問(wèn)題描述n當(dāng)一個(gè)N位的整數(shù)X滿足下列條件時(shí)，稱其為循環(huán)數(shù)：X與任意一個(gè)整數(shù)1Y N相乘時(shí)，都將產(chǎn)生一個(gè)X的“循環(huán)”。即：分別將這兩個(gè)整數(shù)的第1位數(shù)字與最后1位數(shù)字連在一起，可以得到一個(gè)相同的數(shù)字循環(huán)；當(dāng)然兩個(gè)整數(shù)在該數(shù)字循環(huán)中的起始位置不同。例如，142857是一個(gè)循環(huán)數(shù)p 142857 *1 = 142857 142857 *2 = 285714 142857 *3

30、 = 428571 142857 *4 = 571428 142857 *5 = 714285 142857 *6 = 857142 北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23o輸入n寫(xiě)一個(gè)程序判斷一個(gè)整數(shù)是否是循環(huán)數(shù)。輸入文件是一個(gè)整數(shù)序列，每個(gè)整數(shù)長(zhǎng)度為260。注意：每個(gè)整數(shù)前面的零被看作是該整數(shù)的一部分，在計(jì)算N時(shí)要統(tǒng)計(jì)。例如“01”是一個(gè)2位的整數(shù)，而“1”是一個(gè)1位的整數(shù)。o輸出n對(duì)每個(gè)輸入整數(shù)，輸出一行，說(shuō)明該整數(shù)是否是循環(huán)數(shù)。北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23o樣例輸入142857 142856 142858 01 0588235294117647 o樣例輸出

31、142857 is cyclic 142856 is not cyclic 142858 is not cyclic 01 is not cyclic 0588235294117647 is cyclic 北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23解題思路o高精度的乘法：整數(shù)可能達(dá)60位n從1乘到N，如何以較低復(fù)雜度實(shí)現(xiàn)？o如何判斷乘積與算數(shù)成循環(huán)關(guān)系?n窮舉：N位整數(shù)，循環(huán)移位可以有N種可能n子串查找方法：1234567 12 34 5 67 0 2021/7/23#include #include int myAdd(char product, int digitsLen, int

32、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);strcpy(doublenumber, number);strcat(doublenumber, number);2021/7/23Cyclic =

33、 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;2021/7/23int myAdd(char product, int digitsLen, int digits)int carry = 0, i;carry = 0;for ( i=digitsLe

34、n-1; i=0; i-) producti = producti + digitsi + carry;if (producti 9 ) carry = 1;producti = producti - 10;else carry = 0; return (carry);高精度數(shù)相加，進(jìn)位處理問(wèn)題：為什么carry0就表示這個(gè)數(shù)不是循環(huán)數(shù)？以“字符+數(shù)”的方式來(lái)實(shí)現(xiàn)加法，同時(shí)使結(jié)果為字符串型北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23課堂練習(xí)：POJ1936o問(wèn)題描述：給定兩個(gè)字符串s和t，請(qǐng)判斷s是否是t的子序列。即從t中刪除一些字符，將剩余的字符連接起來(lái)，即可獲得s。o輸入：包括若干個(gè)測(cè)試數(shù)據(jù)。每個(gè)測(cè)試數(shù)據(jù)由兩個(gè)ASCII碼的數(shù)字和字母串s和t組成，s和t的長(zhǎng)度不超過(guò)100000。o輸出：對(duì)每個(gè)測(cè)試數(shù)據(jù)，如果s是t的子序列則輸出“Yes”，否則輸出“No”。北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程/492021/7/23o樣例輸入sequence subsequence person compression VERDI viv