算法競(jìng)賽入門經(jīng)典授課教案第3章數(shù)組和字符串(精心排版,并擴(kuò)充部分內(nèi)容)

1、第3章 數(shù)組和字符串第3章 數(shù)組和字符串【教學(xué)內(nèi)容相關(guān)章節(jié)】3.1數(shù)組 3.2字符數(shù)組 3.3最長(zhǎng)回文子串3.4小結(jié)與習(xí)題【教學(xué)目標(biāo)】（1）掌握一維數(shù)組的聲明和使用方法；（2）掌握二維數(shù)組的聲明和使用方法；（3）掌握字符串的聲明、賦值、比較和連接方法；（4）熟悉字符的ASCII碼和ctype.h；（5）正確認(rèn)識(shí)+、+=等能修改變量的運(yùn)算符；（6）學(xué)會(huì)編譯選項(xiàng)-Wall獲得更多的警告信息；（7）掌握f(shuō)getc和getchar的使用方法；（8）了解不同操作系統(tǒng)中換行符的表示方法；（9）掌握f(shuō)gets的使用方法并了解gets的“緩沖區(qū)溢出”的漏洞；（10）理解預(yù)處理和迭代開(kāi)發(fā)的技巧?！窘虒W(xué)要求】（1

2、）掌握一維數(shù)組和二維數(shù)組的聲明和使用方法；（2）掌握字符串的聲明、相關(guān)的操作； （3）掌握f(shuō)getc和getchar的使用方法；（3）掌握f(shuō)gets和gets的使用方法?！窘虒W(xué)內(nèi)容提要】通過(guò)對(duì)第2章的學(xué)習(xí)，了解了計(jì)算機(jī)的計(jì)算優(yōu)勢(shì)，但沒(méi)有發(fā)揮出計(jì)算機(jī)的存儲(chǔ)優(yōu)勢(shì)只用了屈指可數(shù)的變量。盡管有的程序也處理了大量的數(shù)據(jù)，但這些數(shù)據(jù)都只是“過(guò)客”，只參與了計(jì)算、并沒(méi)有被保存下來(lái)。本章介紹數(shù)組和字符串，二者都能保存大量的數(shù)據(jù)。字符串是一種數(shù)組（字符數(shù)組），但由于其應(yīng)用的特殊性，適用一些特別的處理方式?！窘虒W(xué)重點(diǎn)、難點(diǎn)】教學(xué)重點(diǎn)：（1）掌握一維數(shù)組和二維數(shù)組的聲明和使用方法；（2）掌握字符串的聲明、相關(guān)的操作

3、； （3）掌握f(shuō)getc和getchar的使用方法；（3）掌握f(shuō)gets和gets的使用方法。教學(xué)難點(diǎn)：（1）掌握一維數(shù)組和二維數(shù)組的聲明和使用方法；（2）掌握字符串的聲明、相關(guān)的操作及字符串處理函數(shù)的使用。 【課時(shí)安排（共5學(xué)時(shí)）】3.1數(shù)組 3.2字符數(shù)組 3.3最長(zhǎng)回文子串3.4小結(jié)與習(xí)題 3.1 數(shù) 組下面從一個(gè)問(wèn)題出發(fā)，說(shuō)明一下為何使用數(shù)組。問(wèn)題：讀入一些整數(shù)，逆序輸出到一行中，已知整數(shù)不超過(guò)100個(gè)。【分析】首先通過(guò)循環(huán)來(lái)讀取100個(gè)整數(shù)的輸入，然后把每個(gè)數(shù)都存下來(lái)，存放在數(shù)組中，最后輸出。程序3-1 逆序輸出#include <stdio.h>#define MAXN

4、 100 + 10int aMAXN;int main() int i, x, n = 0; while(scanf("%d", &x) = 1) an+ = x; for(i = n-1; i >= 1; i-) printf("%d ", ai); printf("%dn", a0); return 0;說(shuō)明：語(yǔ)句int a100聲明了一個(gè)包含100個(gè)整型變量的數(shù)組，它們是：a0,a1,a2,a99。注意，沒(méi)有a100。提示3-1：語(yǔ)句int aMAXN聲明了一個(gè)包含MAXN個(gè)整型變量的數(shù)組，即a0,a1,a2,aM

5、AXN-1，但不包含aMAXN。MAXN必須是常數(shù)，不能是變量。在本程序中，聲明MAXN為100+10而不是100，主要是為了保險(xiǎn)起見(jiàn)。提示3-2：在算法競(jìng)賽中，常常難以精確計(jì)算出需要的數(shù)組大小，數(shù)組一般會(huì)聲明得稍大些。在空間夠用的前提下，浪費(fèi)一點(diǎn)不要緊。語(yǔ)句an+=x;的等價(jià)于兩條語(yǔ)句an=x; n+;，循環(huán)結(jié)束后，數(shù)據(jù)被存在了a0,a1,an-1，其中變量n個(gè)整數(shù)的個(gè)數(shù)。在數(shù)組中存放整數(shù)后，依次輸出an-1,an,a1和a0。一般要求輸出的行首行尾均無(wú)空格，相鄰兩個(gè)數(shù)據(jù)間用單個(gè)空格隔開(kāi)，一共需要輸出n個(gè)整數(shù)，但只有n-1個(gè)空格，所以只好分兩條語(yǔ)句輸出。也可以采用如下程序：for(i = n

6、-1; i >= 0; i-)if(n!=0)printf("%d ", ai);elseprintf("%dn", a0);在上述程序中，數(shù)組a被聲明在main函數(shù)的外面。簡(jiǎn)單地說(shuō)，只有在放外面時(shí)，數(shù)組a才可以開(kāi)得很大；放在main函數(shù)內(nèi)時(shí)，數(shù)組稍大就會(huì)異常退出。分別運(yùn)行一下以下兩個(gè)程序，觀察運(yùn)行結(jié)果：#include <stdio.h>#define MAXN 10000000int aMAXN;int main()return 0;#include <stdio.h>#define MAXN 10000000int m

7、ain()int aMAXN;return 0;提示3-3：比較大的數(shù)組應(yīng)盡量聲明在main函數(shù)外。C語(yǔ)言數(shù)組中使用過(guò)程中，有一些特殊的情況。例如，數(shù)組不能夠進(jìn)行賦值操作，即不能將一個(gè)整體賦值給另外一個(gè)數(shù)組。補(bǔ)充：memcpy函數(shù)原型如下：void *memcpy(void *dest, void *src, unsigned int count);功能：從源src所指的內(nèi)存地址的起始位置開(kāi)始拷貝n個(gè)字節(jié)到目標(biāo)dest所指的內(nèi)存地址的起始位置中。，使用memcpy函數(shù)要包含頭文件string.h。示例1：從數(shù)組a復(fù)制到k個(gè)元素到數(shù)組b：memcpy(b,a,sizeof(int)*k);示例2

8、：若數(shù)組a和b都是浮點(diǎn)型的，復(fù)制時(shí)要寫成：memcpy(b,a,sizeof(double)*k);示例3：如果需要把數(shù)組a全部復(fù)制到數(shù)組b中，可以寫成：memcpy(b,a,sizeof(a);例3-1 開(kāi)燈問(wèn)題。有n盞燈，編號(hào)為1n，第1個(gè)人把所有燈打開(kāi)，第2個(gè)人按下所有編號(hào)為2的倍數(shù)的開(kāi)關(guān)（這些燈將被關(guān)掉），第3個(gè)人按下所有編號(hào)為3的倍數(shù)的開(kāi)關(guān)（其中關(guān)掉的燈被打開(kāi)，開(kāi)著燈將被關(guān)閉），依此類推。一共有k個(gè)人，問(wèn)最后有哪些燈開(kāi)著？輸入：n和k，輸出開(kāi)著的燈編號(hào)。kn1000。樣例輸入：7 3樣例輸出：1 5 6 7【分析】用a1,a2,an表示編號(hào)為1,2,3,n的燈是否開(kāi)著，模擬這些操作即

9、可。代碼如下：程序3-2 開(kāi)燈問(wèn)題逆序輸出#include <stdio.h>#include <string.h>#define MAXN 1000 + 10int aMAXN; /* 一維數(shù)組存儲(chǔ)n盞電燈 */int main()int i, j, n, k, first = 1;memset(a, 0, sizeof(a); /* 初始化電燈狀態(tài) */scanf("%d%d", &n, &k);/* 模擬活動(dòng)過(guò)程 */for(i = 1; i <= k; i+) /* 第i個(gè)人參與活動(dòng) */for(j = 1; j <

10、;= n; j+) /* 對(duì)第i盞燈進(jìn)行操作 */if(j % i = 0) aj = !aj;/* 輸出活動(dòng)結(jié)果 */for(i = 1; i <= n; i+)if(ai) if(first) first = 0; else printf(" ");printf("%d", i); printf("n");return 0;說(shuō)明：（1）memset(a,0,sizeof(a)的作用是把數(shù)組a清零，它也在string.h中定義。使用memset比f(wàn)or循環(huán)更方便、快捷。補(bǔ)充：memset函數(shù)原型如下：void *memset(

11、void *buffer, char c, int count);功能：把buffer所指內(nèi)存區(qū)域的前count個(gè)字節(jié)設(shè)置成字符c，第三個(gè)參數(shù)指的是字節(jié)的個(gè)數(shù)，返回指向buffer的指針，在程序中需包含頭文件：#include <string.h>。由memset函數(shù)的頭文件可以知道，其主要是對(duì)字符數(shù)組進(jìn)行設(shè)置，當(dāng)然也可以對(duì)數(shù)組進(jìn)行初始賦值（一般是0,-1）。（2）有一個(gè)技巧是在輸出：為了避免輸出多余空格，設(shè)置了一個(gè)標(biāo)志變量first，可以表示當(dāng)前要輸出的變量是否為第一個(gè)。第一個(gè)變量前不應(yīng)有空格，但其他都有。例3-2 蛇形填數(shù)。在n*n方陣?yán)锾钊?,2,n*n，要求填成蛇形。例如n

12、=4時(shí)方陣為10 11 12 19 16 13 28 15 14 37 6 5 4上面的方陣中，多余的空格只是為了便于觀察規(guī)律，不必嚴(yán)格輸出。n8?！痉治觥颗c數(shù)學(xué)的矩陣相比，可以用一個(gè)所謂的二維數(shù)組來(lái)存儲(chǔ)題目中的方陣。只需聲明一個(gè)int aMAXNMAXN，就可以獲得一個(gè)大小為MAXN×MAXN的方陣。在聲明時(shí)，兩維的大小不必相同。提示3-4：用int aMAXNMAXM生成一個(gè)整型的二維數(shù)組，其中MAXN和MAXM不必相等。這個(gè)數(shù)組共有MAXN×MAXM個(gè)元素，分別為a00,a01,a0MAXM-1,a10,a11,a1MAXM-1,aMAXN-10,aMAXN-11,

13、aMAXN-1MAXM-1。假設(shè)從1開(kāi)始依次填這寫。設(shè)“筆”的坐標(biāo)為(x,y)，則一開(kāi)始x=0，y=n-1，即第0行第n-1列（注意行列的范圍是0n-1，沒(méi)有第n列）。“筆”的移動(dòng)軌跡是：下、下、下、左、左、左、上、上、上、右、右、下、下、左、上?？傊仁窍?，到不能填了為止，然后是左，接著是上，最后是右?！安荒芴睢笔侵冈僮呔统鼋纾ɡ?5）或者再走就要走到以前填過(guò)的格子（例如1213）。如果把所有格式初始化為0，就能很方便地加以判斷。程序3-3 蛇形填數(shù)#include<stdio.h>#include<string.h>#define MAXN 10int aMAX

14、NMAXN;int main() int n, x, y, tot = 0; scanf("%d", &n); memset(a, 0, sizeof(a); tot = ax=0y=n-1 = 1; while(tot < n*n) while(x+1<n && !ax+1y) a+xy = +tot; /* 向下走 */ while(y-1>=0 && !axy-1) ax-y = +tot; /* 向左走 */ while(x-1>=0 && !ax-1y) a-xy = +tot; /*

15、 向上走 */ while(y+1<n && !axy+1) ax+y = +tot; /* 向右走 */ for(x = 0; x < n; x+) for(y = 0; y < n; y+) printf("%3d", axy); printf("n"); return 0;說(shuō)明：本程序利用了C語(yǔ)言的簡(jiǎn)潔的優(yōu)勢(shì)。首先，賦值x=0和y=n-1后馬上作為a數(shù)組的下標(biāo)，可以合并完成；tot和a0n-1都要賦值1，也可以合并完成。用一條語(yǔ)句可以完成多件事情，并且不有犧牲程序的可讀性。提示3-5：可以利用C語(yǔ)言簡(jiǎn)潔的語(yǔ)法，但前

16、提是保持代碼的可讀性。提示3-6：在很多情況下，最好是在做一件事之前檢查是不是可以做，而不要做完再后悔。因?yàn)椤盎谄濉蓖脖容^麻煩。說(shuō)明：本程序?qū)τ谂cx+1<n類似的情況，像x+1是否越界？如果x+1<n為假，&&是短路運(yùn)算符，將不會(huì)計(jì)算!ax+1y，也就不會(huì)越界了。3.2 字 符 數(shù) 組文本處理在計(jì)算機(jī)應(yīng)用中占有重要地位。在C語(yǔ)言中，字符串其實(shí)就是字符數(shù)組可以像處理普通數(shù)組一樣處理字符串，只需要注意輸入輸出和字符串函數(shù)的使用。例3-3 豎式問(wèn)題。找出所有形如abc*de（三位數(shù)乘以兩位數(shù)）的算式，使得在完整的豎式中，所有數(shù)字都屬于一個(gè)特定的數(shù)字集合。輸入數(shù)字集合（

17、相鄰數(shù)字之間沒(méi)有空格），輸出所有豎式。每個(gè)豎式前應(yīng)有編號(hào)，之后應(yīng)有一個(gè)空行。最后輸出解的總數(shù)。具體格式見(jiàn)樣例輸出（為了便于觀察，豎式中的空格改用小數(shù)點(diǎn)顯示，但你的程序應(yīng)該輸出空格，而非小數(shù)點(diǎn)）。樣例輸入：2357樣例輸出：<1>.775x.33-.23252325.-25575The number of solutions=1【分析】本題的解題策略是嘗試所有的abc和de，判斷是否滿足條件。寫出如下的偽代碼： char s20; int count = 0; scanf("%s", s); for(abc = 111; abc <= 999; abc+)

18、for(de = 11; de <= 99; de+) if(“abc*de”是個(gè)合法的豎式) printf("<%d>n", +count); 打印abc*de的豎式和其后的空行 count+; printf("The number of solutions = %dn", count);說(shuō)明：（1）char s20是一個(gè)定義字符數(shù)組的語(yǔ)句，scanf("%s",s)表示從鍵盤輸入一個(gè)字符串給字符數(shù)組s。（2）char是“字符型”的意思，而字符是一種特殊的整數(shù)。每一個(gè)字符都有一個(gè)整數(shù)編碼，稱為ASCII碼。C語(yǔ)言中

19、允許用直接的方法表示字符，還有以反斜線開(kāi)頭的字符（轉(zhuǎn)義序列，Escape Sequence）。（3）在stdlib.h中有一個(gè)函數(shù)atoi，它的函數(shù)原型如下：int atoi(char *s)它表示將字符串s中的內(nèi)容轉(zhuǎn)換成一個(gè)整型數(shù)返回，如字符串“1234”,則函數(shù)返回值是1234。（4）在stdlib.h中有一個(gè)函數(shù)itoa，它的函數(shù)原型如下：char *itoa(int value,char *string,int radix)它表示將整數(shù)value轉(zhuǎn)換成字符串存入string, radix為轉(zhuǎn)換時(shí)所用基數(shù)(保存到字符串中的數(shù)據(jù)的進(jìn)制基數(shù) 2 8 10 16)，返回指向轉(zhuǎn)換后的字符串的指針

20、 。例如，itoa(32,string,10)是將32變成十進(jìn)制數(shù)一個(gè)字符串“32”，并返回指向這個(gè)字符串的指針；itoa(32,string,16)是將32變成十進(jìn)制數(shù)一個(gè)字符串“20”，并返回指向這個(gè)字符串的指針。（5）stdlib 頭文件即standard library標(biāo)準(zhǔn)庫(kù)頭文件，該文件包含了的C語(yǔ)言標(biāo)準(zhǔn)庫(kù)函數(shù)的定義，聲明了數(shù)值與字符串轉(zhuǎn)換函數(shù), 偽隨機(jī)數(shù)生成函數(shù), 動(dòng)態(tài)內(nèi)存分配函數(shù), 進(jìn)程控制函數(shù)等公共函數(shù)。輸入樣式： C語(yǔ)言模式：#include <stdlib.h> C+樣式：#include <cstdlib> 提示3-7：C語(yǔ)言中的字符型用

21、char表示，它實(shí)際存儲(chǔ)的是字符的ASCII碼。字符常量可以用單引號(hào)法表示。在語(yǔ)法上可以把字符當(dāng)作int型使用。語(yǔ)句scanf("%s", s);表示讀入一個(gè)不含空格、TAB和回車符的字符串，存入字符數(shù)組s中，s前面沒(méi)有&符號(hào)。提示3-8：在scanf("%s",s)中，不要在s前面加上&符號(hào)。如果是字符數(shù)組char sMAXN MAXL,可以用scanf("%s",si)讀取第i個(gè)字符串。接下來(lái)有兩個(gè)問(wèn)題：判斷和輸出。先考慮輸出。首先計(jì)算第一行乘積x=abc*e，然后是第二行y=abc*d，最后是總乘積z=abc*d

22、e，然后一次性打印出來(lái)：printf("%5dnX%4dn-n%5dn%4dn-n%5dnn",abc,de,x,y,z);完整程序如下：程序3-4 豎式問(wèn)題#include<stdio.h>#include<string.h>int main()int i, ok, abc, de, x, y, z, count = 0;char s20, buf99;scanf("%s", s);for(abc = 111; abc <= 999; abc+)for(de = 11; de <= 99; de+)x = abc*(

23、de%10);y = abc*(de/10);z = abc*de;sprintf(buf, "%d%d%d%d%d", abc, de, x, y, z);ok = 1;for(i = 0; i < strlen(buf); i+)if(strchr(s, bufi) = NULL)ok = 0;if(ok)printf("<%d>n", +count);printf("%5dnX%4dn-n%5dn%4dn-n%5dnn",abc,de,x,y,z);printf("The number of solu

24、tions = %dn", count);return 0;說(shuō)明：（1）sprintf函數(shù)sprintf是個(gè)變參函數(shù)，定義如下：int sprintf( char *buffer, const char *format , argument . );除了前兩個(gè)參數(shù)類型固定外，后面可以接任意多個(gè)參數(shù)。功能：把格式化的數(shù)據(jù)寫入字符串buf，它的返回值是字符串長(zhǎng)度。包含此函數(shù)的頭文件是stdio.h。例如，本程序中的sprintf(buf,"%d%d%d%d%d",abc,de,x,y,z);語(yǔ)句的功能是將整數(shù)abcdexyx打印成字符串存儲(chǔ)在串buff中。可以直接接受

25、其返回值：int len=sprintf(buf, "%d%d%d%d%d", abc, de, x, y, z);（2）strchr函數(shù)strchr函數(shù)定義如下：char *strchr(const char *s,char c);功能：查找字符串s中首次出現(xiàn)字符c的位置。它的返回值是返回首次出現(xiàn)c的位置的指針，如果s中不存在c則返回NULL。包含此函數(shù)的頭文件是string.h。例如，本程序的if語(yǔ)句中strchr(s, bufi)的功能是查找字符串s中首次出字符bufi的位置。如果strchr(s, bufi)=NULL，則表明字符串s中沒(méi)有bufi的字符。（3）sp

26、rintf函數(shù)、printf函數(shù)、fprintf函數(shù)的區(qū)別printf輸出到屏幕，fprintf輸出到文件，而sprintf輸出到字符串。需要注意是應(yīng)該保證寫入的字符串有足夠的空間。提示3-9：可以用sprintf把信息輸出到字符串，用法和printf、fprintf類似。但你應(yīng)當(dāng)保證字符串足夠大，可以容納輸出信息。字符串的空間應(yīng)為字符個(gè)數(shù)加1，這是因?yàn)镃語(yǔ)言的字符串是以空字符'0'結(jié)尾的。函數(shù)strlen(s)的作用是獲取字符串s的實(shí)際長(zhǎng)度，即函數(shù)strlen(s)返回的是結(jié)束標(biāo)記之前的字符個(gè)數(shù)（需包含頭文件string.h）。因此這個(gè)字符串中的各個(gè)字符依次是s0,s1,ss

27、trlen(s)-1，而sstrlen(s)正是結(jié)束標(biāo)記'0'。提示3-10：C語(yǔ)言中的字符串是'0'結(jié)尾的字符數(shù)組，可以用strlen(s)返回字符串s中結(jié)束標(biāo)記之前的字符個(gè)數(shù)。字符串中的各個(gè)字符是：s0,s1,sstrlen(s)-1。提示3-11：由于字符串的本質(zhì)是數(shù)組，它也不是“一等公民”，只能用strcpy(a,b)、strcmp(a,b)、strcat(a,b)來(lái)執(zhí)行“賦值”、“比較”和“連接”操作。而不能用=、=、<=、+等運(yùn)算符。上述函數(shù)都在string.h中聲明。除了字符串之外，還要注意+count和count+的用法。+count本身的

28、值是加1以后的，但count+的值是加1之前的（原來(lái)的值）。注意：濫用+count和count+會(huì)帶來(lái)很多隱蔽的錯(cuò)誤，所以最好的方法是避開(kāi)它們。提示3-12：濫用+、-、+=等可以修改變量值的運(yùn)算符很容易帶來(lái)隱蔽的錯(cuò)誤。建議每條語(yǔ)句最多只用一次這種運(yùn)算符，并且它所修改的變量在整條語(yǔ)句中只出現(xiàn)一次。提示3-13：但編譯選項(xiàng)-Wall編譯程序時(shí)，會(huì)給出很多（但不是所有）警告信息，以幫助程序員查錯(cuò)。但并不能解決所有的問(wèn)題：有些“錯(cuò)誤”程序是合法的，只是這些動(dòng)作不是你所期望的。3.3 最長(zhǎng)回文子串例3-4 回文串。輸入一個(gè)字符串，求出其中最長(zhǎng)的回文子串。子串的含義是：在原串中連續(xù)出現(xiàn)的字符串片段。回文

29、的含義是：正著看和倒著看相同。如abba和yyxyy。在判斷時(shí)，應(yīng)該忽略所有標(biāo)點(diǎn)符號(hào)和空格，且忽略大小寫，但輸出應(yīng)保持原樣（在回文串的首部和尾部不要輸出多余字符）。輸入字符串長(zhǎng)度不超過(guò)5000，且占據(jù)單獨(dú)的一行。應(yīng)該輸出最長(zhǎng)的回文串，如果有多個(gè)，輸出起始位置最靠左的。樣例輸入：Confuciuss say:Madam,I'm Adam.樣例輸出：Madam,I'm Adam【分析】由于輸入的字符比較復(fù)雜，首先，不能用scanf("%s")輸入字符串，可用下述兩種方法解決下列問(wèn)題：第1種方法是使用fgetc(fin)，它讀取一個(gè)打開(kāi)的文件fin，讀取一個(gè)字符，

30、然后返回一個(gè)int值。因?yàn)槿绻募Y(jié)束，fgetc將返回一個(gè)特殊標(biāo)記EOF，它并不是一個(gè)char。如果要從標(biāo)準(zhǔn)輸入讀取一個(gè)字符，可以用getchar()，它等價(jià)于fgetc(stdin)。補(bǔ)充：fgetc()介紹功能：從流中讀取字符。用法：int fgetc(FILE *stream);意為從文件指針stream指向的文件中讀取一個(gè)字符,讀取一個(gè)字節(jié)后，光標(biāo)位置后移一個(gè)字節(jié)。這個(gè)函數(shù)的返回值，是返回所讀取的一個(gè)字節(jié)。如果讀到文件末尾或者讀取出錯(cuò)時(shí)返回EOF。提示3-14：使用fgetc(fin)可以從打開(kāi)的文件fin中讀取一個(gè)字符。一般情況下應(yīng)當(dāng)在檢查它不是EOF后再將其轉(zhuǎn)換成char值。從標(biāo)

31、準(zhǔn)輸入讀取一個(gè)字符可以用getchar()，它等價(jià)于fgetc(stdin)。fgetc()和getchar()將讀取“下一個(gè)字符”，如果是空格，會(huì)正常讀?。蝗羰菗Q行，讀取到的將是回車符'n'。補(bǔ)充：getchar()介紹功 能: 從stdio流中讀字符用 法: int getchar(void);getchar函數(shù)的返回值是用戶輸入的第一個(gè)字符的ASCII碼,如出錯(cuò)返回-1。可以利用getchar()函數(shù)讓程序調(diào)試運(yùn)行結(jié)束后等待編程者按下鍵盤才返回編輯界面，用法：在主函數(shù)結(jié)尾，return 0;之前加上getchar();#include <stdio.h>int

32、 main(void)int c;while (c = getchar() != -1)/while (c = getchar() != EOF)printf("%c", c);return 0;#include <stdio.h>int main(void)for(int i=1;i<=10;i+)printf("%d ",i);getchar();/用以暫停程序return 0;潛在的陷阱：不同操作系統(tǒng)的回車換行符是不一致的。Windows是'r'和'n'兩個(gè)字符，Linux是'n'，

33、而MacOS是'r'。如果在Windows下讀到Windows文件，fgetc()和getchar()會(huì)把'r'吃掉，只剩下'n'；但如要要在Linux下讀取同樣一個(gè)文件，它們會(huì)先讀到'r'，然后才是'n'。這個(gè)問(wèn)題在競(jìng)賽時(shí)一定要注意。提示3-15：在使用fgetc和getchar時(shí)，應(yīng)該避免寫出和操作系統(tǒng)相關(guān)的程序。第2種方法是使用fgets(buf,MAXN,fin)讀了完整的一行，其中buf的聲明為char bufMAXN。這個(gè)函數(shù)讀取不超過(guò)MAXN-1個(gè)字符，然后在末尾上結(jié)束符'0'，因此不

34、會(huì)出現(xiàn)越界的情況。之所以說(shuō)可以用這個(gè)函數(shù)讀取完整的一行，是因?yàn)橐坏┳x到回車符'n',讀取工作將會(huì)停止，而這個(gè)'n'也會(huì)是buf字符串中最后一個(gè)有效字符（再往后就是字符串的結(jié)束符'0'了）。只有一種情況下，buf不會(huì)以'n'結(jié)尾：讀到文件結(jié)束符，并且文件的最后一個(gè)不是以'n'結(jié)尾。補(bǔ)充：fgets()介紹函數(shù)原型：char *fgets(char *buf, int bufsize, FILE *stream); 參數(shù)： *buf: 字符型指針，指向?qū)⒋鎯?chǔ)到的數(shù)據(jù)地址。bufsize: 整型數(shù)據(jù)，指明buf指向的字符

35、數(shù)組的大小。*stream: 文件結(jié)構(gòu)體指針，將要讀取的文件流。功能:從文件結(jié)構(gòu)體指針stream中讀取數(shù)據(jù)，每次讀取一行。讀取的數(shù)據(jù)保存在buf指向的字符數(shù)組中，每次最多讀取bufsize-1個(gè)字符（第bufsize個(gè)字符賦'0'），如果文件中的該行，不足bufsize個(gè)字符，則讀完該行就結(jié)束。如果函數(shù)讀取成功，則返回指針buf，失敗則返回NULL。提示3-16：fgets(buf,MAXN,fin)將讀取完整的一行放在字符數(shù)組buf中。你應(yīng)當(dāng)保證buf足夠存放下文件的一行內(nèi)容。除了在文件結(jié)束符前沒(méi)有遇到'n'這種特殊情況外，buf總是以'n'

36、結(jié)尾。當(dāng)一個(gè)字符都沒(méi)有讀到時(shí)，fgets返回NULL。gets(s)表示從標(biāo)準(zhǔn)輸入設(shè)備讀取字符串存入s所指向的數(shù)組中，成功時(shí)返回指針s，否則返回NULL。但是gets(s)沒(méi)有指明讀到的最大字符數(shù)，gets函數(shù)也不管s的可用空間有多大。補(bǔ)充：gets()介紹頭文件：stdio.h（c中），c+不需包含此頭文件原 型：char *gets(char *buffer);功 能：從stdio流中讀取字符串，直至接受到換行符或EOF時(shí)停止，并將讀取的結(jié)果存放在buffer指針?biāo)赶虻淖址麛?shù)組中。換行符不作為讀取串的內(nèi)容，讀取的換行符被轉(zhuǎn)換為null值，并由此來(lái)結(jié)束字符串。返回值：讀入成功，返回與參數(shù)b

37、uffer相同的指針；讀入過(guò)程中遇到EOF(End-of-File)或發(fā)生錯(cuò)誤，返回NULL指針。所以在遇到返回值為NULL的情況，要用ferror或feof函數(shù)檢查是發(fā)生錯(cuò)誤還是遇到EOF。注 意：本函數(shù)可以無(wú)限讀取，不會(huì)判斷上限，所以程序員應(yīng)該確保buffer的空間足夠大，以便在執(zhí)行讀操作時(shí)不發(fā)生溢出。如果溢出，多出來(lái)的字符將被寫入到堆棧中，這就覆蓋了堆棧原先的內(nèi)容，破壞一個(gè)或多個(gè)不相關(guān)變量的值，為了避免這種情況，我們可以用fgets()來(lái)替換gets（）。提示3-17：C語(yǔ)言并不禁止程序讀寫“非法內(nèi)存”。例如你聲明的是char s100，你完全可以賦值s10000='a'

38、（甚至-Wall也不會(huì)警告），但后果自負(fù)。提示3-18：C語(yǔ)言中的gets(s)存在緩沖區(qū)溢出漏洞，不推薦使用。選擇fgets函數(shù)可以解決“輸入有空格”的問(wèn)題，它可以一次性讀取一行，最為方便。接下來(lái)，解決“判斷時(shí)忽略標(biāo)點(diǎn)，輸出進(jìn)卻要按原樣”的問(wèn)題，可以用一個(gè)通用的方案：預(yù)處理。構(gòu)造一個(gè)新字符串，不包含原來(lái)的標(biāo)點(diǎn)符號(hào)，而且所有字符變成大寫（順便解決了大小寫的問(wèn)題）：n = strlen(buf);m=0;for(i = 0; i < n; i+) if(isalpha(bufi) sm+ = toupper(bufi);說(shuō)明：isalpha(c)的原型包含在ctype.h中，它用于判斷字符

39、c是否為字母（大寫或小寫）。用toupper(c)返回c的大寫形式。這樣處理之后，buf保存的就是原串的所有字母了。補(bǔ)充1：isalpha函數(shù)介紹原型：int isalpha（int ch）用法：頭文件加入#include <cctype>(C語(yǔ)言使用<ctype.h>)功能：判斷字符ch是否為英文字母，當(dāng)ch為英文字母a-z或A-Z時(shí)，在標(biāo)準(zhǔn)c中相當(dāng)于使用“isupper(ch)|islower(ch)”做測(cè)試，返回非零值(不一定是1)，否則返回零。補(bǔ)充2：isupper函數(shù)介紹原型：extern int isupper(int c); 頭文件：<cctype&

40、gt;( C語(yǔ)言使用<ctype.h>)功能：判斷字符c是否為大寫英文字母 說(shuō)明：當(dāng)參數(shù)c為大寫英文字母(A-Z)時(shí)，返回非零值，否則返回零。 附加說(shuō)明： 此為宏定義，非真正函數(shù)。 補(bǔ)充3：islower函數(shù)介紹頭文件：#include<cctype>( C語(yǔ)言使用<ctype.h>)用法：int islower(int c) 函數(shù)說(shuō)明：檢查參數(shù)c是否為小寫英文字母。 返回值：若參數(shù)c為小寫英文字母，則返回TRUE，否則返回NULL(0)。 附加說(shuō)明：此為宏定義，非真正函數(shù)。 補(bǔ)充4：toupper函數(shù)介紹原型：extern int toupper(int

41、c);用法：#include <ctype.h>功能：將字符c轉(zhuǎn)換為大寫英文字母說(shuō)明：如果c為小寫英文字母，則返回對(duì)應(yīng)的大寫字母；否則返回原來(lái)的值。補(bǔ)充5：tolower函數(shù)介紹功 能: 把字符轉(zhuǎn)換成小寫字母,非字母字符不做出處理頭文件：在VC6.0可以是ctype.h或者stdlib.h，常用ctype.h用 法: int tolower(int c); 說(shuō)明：如果c為大寫英文字母，則返回對(duì)應(yīng)的小寫字母；否則返回原來(lái)的值。補(bǔ)充6：isdigit函數(shù)介紹原型：extern int isdigit(char c);用法：#include <ctype.h>功能：判斷字符c

42、是否為數(shù)字說(shuō)明：當(dāng)c為數(shù)字0-9時(shí)，返回非零值，否則返回零。附加說(shuō)明:此為宏定義，非真正函數(shù)。補(bǔ)充7：isprint函數(shù)介紹原型：extern int isprint(char c);用法：#include <ctype.h>功能：判斷字符c是否為可打印字符（含空格）說(shuō)明：當(dāng)c為可打印字符（0x20-0x7e）時(shí)，返回非零值，否則返回零。附加說(shuō)明：此為宏定義，非真正函數(shù)。提示3-19：當(dāng)任務(wù)比較復(fù)雜時(shí)，可以用預(yù)處理的方式簡(jiǎn)化輸入，并提供更多的數(shù)據(jù)供使用復(fù)雜的字符串處理題目往往可以通過(guò)合理的預(yù)處理簡(jiǎn)化任務(wù)，便于調(diào)試。提示3-20：頭文件ctype.h中定義的isalpha、isdig

43、it、isprint等工具可以用來(lái)判斷字符的屬性，而toupper、tolower等工具可以用來(lái)轉(zhuǎn)換大小寫。說(shuō)明：（1）isalpha(c)用來(lái)檢查c是否為字母，如果是字母，則返回1；否則返回0。（2）isdigit(c)用來(lái)檢查c是否為數(shù)字（09），如果是數(shù)字，則返回1；否則返回0。（3）isprint(c)用來(lái)檢查c是否為可打印字符（不包括空格），其ASCII碼值在0x210x7e之間，如果是可打印字符，則返回1；否則返回0。（4）toupper(c)用來(lái)將c字符轉(zhuǎn)換為大寫字母，返回c對(duì)應(yīng)的大寫字母。（5）tolower(c)用來(lái)將c字符轉(zhuǎn)換為小寫字母，返回c對(duì)應(yīng)的小寫字母。下面來(lái)枚舉回文

44、串的起點(diǎn)和終點(diǎn)，然后判斷它是否真的是回文串。int max=0;for(i = 0; i < m; i+) for(j = i; j < m; j+) if(si.j是回文串 && j-i+1 > max) max = j-i+1;“當(dāng)前最大值”變量max，它保存的是目前為止發(fā)現(xiàn)的最長(zhǎng)回文子串的長(zhǎng)度。如果串s的第i個(gè)字符到第j個(gè)字符（記為si.j）是回文串，則檢查長(zhǎng)度j-i+1是否超過(guò)max。最后，判斷si.j是否為回文串的方法如下：int ok = 1;for(k = i; k <= j; k+) if(sk != si+j-k) ok = 0;sk的

45、“對(duì)稱”位置是si+j-k，因?yàn)橹灰淮伪容^失敗，就應(yīng)把標(biāo)記變量ok置為0。完整的程序如下：程序3-5 最長(zhǎng)回文子串（1）#include <stdio.h>#include <string.h>#include <ctype.h>#define MAXN 5000 + 10char bufMAXN, sMAXN;int main() int n, m = 0, max = 0; int i, j, k; fgets(buf, sizeof(s), stdin); n = strlen(buf); for(i = 0; i < n; i+) if(is

46、alpha(bufi) sm+ = toupper(bufi); for(i = 0; i < m; i+) for(j = i; j < m; j+) int ok = 1; for(k = i; k <= j; k+) if(sk != si+j-k) ok = 0; if(ok && j-i+1 > max) max = j-i+1; printf("max = %dn", max); return 0;在實(shí)際編程時(shí)，經(jīng)常先編寫一個(gè)具備主要功能的程序，再加以完善。甚至可以先寫一個(gè)只有輸入輸出功能的“骨架”，但是要確保它正確。這樣

47、，每次只添加一點(diǎn)點(diǎn)功能，而且寫一點(diǎn)就測(cè)試一點(diǎn)，和一次寫整個(gè)程序相比，更加不容易出錯(cuò)。這種方法稱為迭代式開(kāi)發(fā)。提示3-21：在程序比較復(fù)雜時(shí)，除了在設(shè)計(jì)階段可以用偽代碼理清思路外，編碼階段可以采用迭代時(shí)開(kāi)發(fā)每次只實(shí)現(xiàn)一點(diǎn)小功能，但要充分測(cè)試，確保它工作正常。程序3-5能順利求出樣例數(shù)據(jù)中最長(zhǎng)回文串的長(zhǎng)度?，F(xiàn)在接下來(lái)的任務(wù)是輸出這個(gè)回文串：要求原樣輸出，并且盡量靠左。由于是從左到右枚舉的，所以現(xiàn)在只剩下唯一的問(wèn)題：原樣輸出。由于在求max值時(shí)，不知道si和sj在原串buf中的位置。因此，必須增加一個(gè)數(shù)組p，用pi保存si在buf中的位置。在預(yù)處理得到，然后在更新max的同時(shí)把pi和pj保存到x和y

48、，最后輸出bufx到bufy中的所有字符。但是上面的方法發(fā)現(xiàn)速度很慢，所以換一種方式：枚舉回文串的“中間”位置i，然后不斷往外擴(kuò)展，直到有字符不同。提示：長(zhǎng)度為奇數(shù)和偶數(shù)的處理方式是不一樣的。完整的程序如下：程序3-6 最長(zhǎng)回文子串（2）#include<stdio.h>#include<string.h>#include<ctype.h>#define MAXN 5000 + 10char bufMAXN, sMAXN;int pMAXN;int main()int n, m = 0, max = 0, x, y;int i, j;fgets(buf, s

49、izeof(s), stdin);n = strlen(buf);for(i = 0; i < n; i+)/如果bufi為字母，則在p中保存其的位置，/并將其轉(zhuǎn)變?yōu)榇髮懽帜福４嬖趕中if(isalpha(bufi) pm = i;sm+ = toupper(bufi);for(i = 0; i < m; i+) /1.若為奇數(shù)形式：abcbafor(j = 1; i-j >= 0 && i+j < m; j+) if(si-j != si+j) break;if(j*2+1 > max) max = j*2+1; x = pi-j; y = p

50、i+j; /printf("1:i=%d,j=%d,max=%d,x=%d,y=%dn",i,j,max,x,y);/2.若為偶數(shù)形式：abbafor(j = 0; i-j >= 0 && i+j+1 < m; j+) if(si-j != si+j+1) break;if(j*2+2 > max) max = j*2+2; x = pi-j; y = pi+j+1; /printf("2:i=%d,j=%d,max=%d,x=%d,y=%dn",i,j,max,x,y);for(i = x; i <= y; i+

51、)printf("%c", bufi);printf("n");return 0;3.4 小結(jié)與習(xí)題到目前為止，C語(yǔ)言的核心內(nèi)容已經(jīng)全部講完了。理論上，運(yùn)用算法前3章的知識(shí)足以編寫大部分算法競(jìng)賽程序了。3.4.1 必要的存儲(chǔ)量3.4.2 用ASCII編碼表示字符在C語(yǔ)言除了字符常量，還有一種特殊形式的字符常量，就是以一個(gè)字符“”開(kāi)頭的字符序列。在轉(zhuǎn)義符中還可以用一個(gè)ASCII碼（八進(jìn)制數(shù)或十六進(jìn)制數(shù)）來(lái)表示字符。提示3-22：字符還可以直接用ASCII碼表示。如果八進(jìn)制，應(yīng)該寫成ddd，它表示1到3位八進(jìn)制所代表的字符；如果用十六進(jìn)制，應(yīng)該寫成xhh，它

52、表示1到2位十六進(jìn)制所代表的字符。3.4.3 補(bǔ)碼表示法計(jì)算機(jī)中的二進(jìn)制是沒(méi)有符號(hào)的，但是對(duì)于正號(hào)和負(fù)號(hào)可以一個(gè)二進(jìn)制位就可以了。一個(gè)帶符號(hào)32位整數(shù)，在計(jì)算機(jī)內(nèi)部采用“補(bǔ)碼的表示法”（Complement Representation）。例如，語(yǔ)句printf("%un",-1)的輸出是4294967295=232-1。把-1換成-2、-3、-4、后，可總結(jié)一個(gè)規(guī)律：-n的內(nèi)部表示是232-n。提示3-23：在多數(shù)計(jì)算機(jī)內(nèi)部，整數(shù)采用的是補(bǔ)碼表示法。采用補(bǔ)碼表示法的主要原因是可以將符號(hào)位和其它位統(tǒng)一處理；同時(shí)，減法也可按加法來(lái)處理。另外，兩個(gè)用補(bǔ)碼表示的數(shù)相加時(shí)，如果最高

53、位（符號(hào)位）有進(jìn)位，則進(jìn)位被舍棄。在通常情況下，int是32位（4字節(jié)）的。3.4.4 重新實(shí)現(xiàn)庫(kù)函數(shù)在學(xué)習(xí)字符串時(shí)，重新實(shí)現(xiàn)一些庫(kù)函數(shù)的功能是有益的。練習(xí)1：只用getchar函數(shù)讀入一個(gè)整數(shù)。假設(shè)它占據(jù)單獨(dú)的一行，讀到行末為止，包括換行符。輸入保證讀入的整數(shù)可以保存在int中。練習(xí)2：只用fgets函數(shù)讀入一個(gè)整數(shù)。假設(shè)它占據(jù)單獨(dú)的一行，讀到行末為止，包括換行符。輸入保證讀入的整數(shù)可以保存在int中。練習(xí)3：只用getchar實(shí)現(xiàn)fgets的功能，即用每次一個(gè)字符的方式讀取整行。練習(xí)4：實(shí)現(xiàn)strchr的功能，即在一個(gè)字符串中查找一個(gè)字符。解答：下面編寫一個(gè)函數(shù)strchr1實(shí)現(xiàn)strch

54、r的功能：char *strchr1(char *str,int  ch) int i; for(i=0;stri != '0' i+) if(stri = ch) return str+i; return NULL;練習(xí)5：實(shí)現(xiàn)isalpha和isdigit的功能，即判斷字符是否為字母/數(shù)字。解答：（1）下面編寫一個(gè)函數(shù)isapha1實(shí)現(xiàn)isalpha的功能：int isalpha1(char ch) if(ch>='a' && ch<='z') |(ch>='A' &&

55、; ch<='Z') return 1; else return 0;（2）下面編寫一個(gè)函數(shù)isdigit1實(shí)現(xiàn)isdigit的功能：int isdigit1(char ch) if(ch>='0' && ch<='9') return 1; else return 0;3.4.5 字符串處理的常見(jiàn)問(wèn)題tot=1;for(i = 0; i < strlen(s); i+) if(si = 1) tot+;printf("There are %d character(s) '1' i

56、n the string.n",tot);本程序的功能是統(tǒng)計(jì)字符串中字符1的個(gè)數(shù)。實(shí)驗(yàn)1：添加字符串s的聲明語(yǔ)句，長(zhǎng)度不小于107。提示：放在main函數(shù)內(nèi)還是外？ 解答：添加字符串s的聲明語(yǔ)句如下：#define MAXN 10000000char sMAXN;應(yīng)放在main函數(shù)外。實(shí)驗(yàn)2：添加讀取語(yǔ)句，測(cè)試上述程序是否輸出了期望的結(jié)果。如果不是，請(qǐng)改正。 解答：得不到期望的結(jié)果，改正如下： if(si = 1) tot+; 改為if(si = '1') tot+;實(shí)驗(yàn)3：把輸入語(yǔ)句注釋掉，添加語(yǔ)句，用程序生成一個(gè)長(zhǎng)度至少為105的字符串，并用程序驗(yàn)證字符串長(zhǎng)度確實(shí)不小于105。 解答：程序如下：#include <stdio.h>#include <str