《程序設計與C語言》課件第6章

第6章數(shù)組6.1數(shù)組的概念6.2一維數(shù)組6.3一維字符數(shù)組6.4二維數(shù)組6.5多維數(shù)組習題66.1數(shù)組的概念在實際問題中，常常需要處理大量的有相同性質(zhì)的數(shù)據(jù)，比如要登記一個年級250名學生的期末成績并求平均值，我們不可能定義250個變量來一一地進行賦值，再把250個變量相加來求平均值。解決這個問題的最好辦法是使用數(shù)組。數(shù)組是一種數(shù)據(jù)類型，它可以把多個相同類型的數(shù)據(jù)組合在一起，用一個變量名表示，這個變量名稱為數(shù)組名，如學生數(shù)組stud。各個具體的數(shù)據(jù)用數(shù)組名加下標來表示，比如第5號學生的成績?yōu)閟tud［5］。數(shù)組的設置為我們提供了極大的方便。構成數(shù)組的單元稱為數(shù)組元素，數(shù)組元素的序號稱為下標。C語言中數(shù)組的下標從0開始計數(shù)，最大下標比數(shù)組元素個數(shù)少1。比如數(shù)組a有5個整數(shù)元素，a［0］是它的第0號元素(第1個元素)，a［4］是它的第4號元素(第5個元素)。數(shù)組a在內(nèi)存中的形式如圖6-1所示。數(shù)組元素的序號用方括號括起來。方括號又被稱為下標運算符，具有最高的優(yōu)先級。下標必須是一個整數(shù)或一個整型表達式，如i=1，j=2，則a［i+j］就表示a［3］。帶了下標的數(shù)組名在這里就相當于該類型的一個變量，因此可以作為賦值語句的左值，例如：

a［4］+=3；圖6-1數(shù)組在內(nèi)存中的形式6.2一維數(shù)組6.2.1一維數(shù)組變量的定義只有在聲明了數(shù)組元素的類型和個數(shù)之后，編譯器才能為該數(shù)組分配合適的內(nèi)存，這種聲明就是數(shù)組的定義。對一維數(shù)組來說，其定義的一般形式為：

〈類型標識符〉〈數(shù)組名〉［〈整型常量表達式〉］其中，類型標識符指數(shù)組元素的類型；數(shù)組名是個標識符，是數(shù)組類型變量；整型常量表達式表示該數(shù)組的大小，應該大于0。例如語句＃defineM20inta［10］;floatb［5］;charch［M+6］；定義a是有10個整型元素的數(shù)組名，b是有5個浮點型元素的數(shù)組名，ch是有M+6即26個元素的字符型數(shù)組變量名。一個數(shù)組中的元素在內(nèi)存中是連續(xù)存放的，數(shù)組名代表了這個數(shù)組第1個元素的地址，如a也代表了&a［0］，b也代表了&b［0］。定義數(shù)組變量時最常見的錯誤有兩種：

(1)將下標運算符寫成圓括號，如：

inta(10);

(2)將數(shù)組變量定義成動態(tài)數(shù)組，即數(shù)組的大小依賴于程序運行時變量的取值，如：intn;scanf(″%d″，&n);inta［n］;6.2.2一維數(shù)組元素的引用引用數(shù)組元素的一般形式是：

〈數(shù)組名〉［〈整型表達式〉］例如，對上節(jié)定義的數(shù)組a，可以用a［2］、a［i+1］、a［i+j］等來表示a的某個元素(其中i、j為已取值的整型變量)。要注意整型表達式的取值范圍：

0≤〈整型表達式〉≤元素個數(shù)-1通常情況下常用for結構來操作數(shù)組，其一般格式是：

for(i=0;i<=數(shù)組大小-1；i++){…a［i］…}或

for(i=數(shù)組大小-1；i>=0;i--){…a［i］…}以此來順序或逆序地遍歷一維數(shù)組中的所有元素。

【例6-1】給數(shù)組賦值并以反序輸出。＃include<stdio.h>main(){inti，a［10］

for(i=0;i<=9;i++)a［i］=1+2*i;for(i=9;i>=0;i--)printf(″%d″，a［i］);return0;}運行輸出：

191715131197531程序定義整型數(shù)組a有10個元素，通過for循環(huán)對數(shù)組元素賦以連續(xù)的奇數(shù)值：1，3，5，…，19，然后以反序輸出。在第一個for循環(huán)頭的第二個表達式中寫上數(shù)組的最大下標可以預防“丟一錯誤”，即最好寫成i<=9而不要寫成i<10或i<9這種形式。6.2.3一維數(shù)組變量的初始化上面程序中對數(shù)組元素的賦值是通過循環(huán)語句實現(xiàn)的，這要占用運行時間。事實上，還可以在定義一個數(shù)組變量的同時就給它賦值，這稱為數(shù)組的初始化。數(shù)組初始化有以下兩種情況：

(1)對全部數(shù)組元素初始化，如：

inta［5］={1，2，3，4，5};是將初始化的值放入花括號中并以逗號分開，按它們出現(xiàn)的順序分別賦給數(shù)組的第0號、第1號、…、第i號元素。這相當于做以下的賦值：

a［0］=1;a［1］=2;a［2］=3;a［3］=4;a［4］=5;可見用初始化的方法可以提高賦值效率，而且這是在程序編譯時進行的，不占用系統(tǒng)的運行時間。

(2)只給部分數(shù)組元素賦初值。這又可分為兩種情況：①如果只給數(shù)組的前半部分元素賦初值，可連續(xù)寫出初值，如：

inta［5］={1，2};其作用是把1賦給a［0］，把2賦給a［1］，而對后面的元素全部自動賦以初值0，即a［2］=a［3］=a［4］=0；②如果只給數(shù)組的后半部分元素或某些不連續(xù)的元素賦初值，則花括號中分隔數(shù)值的逗號不能缺少，即把要賦的值寫入適當?shù)牡胤剑挥栀x值的地方寫為0(對數(shù)值型數(shù)組)，如： inta［5］={0，3，0，7，9};則對數(shù)組元素a［1］、a［3］、a［4］賦了初值3、7、9，而a［0］、a［2］元素值均為0。數(shù)組初始化時的常見錯誤有以下兩種：

·在實際數(shù)值之間留有空位，如：

inta［5］={1，，3，，5};是錯誤的，即在1和3之間、3和5之間必須有具體數(shù)值，即使是0也必須寫上。

·初始值的個數(shù)大于元素的個數(shù)，如：

inta［5］={1，2，3，4，5，6};也是錯誤的，因為數(shù)組只有5個元素，而提供了6個初值，這會造成編譯錯誤。為了避免出現(xiàn)這種個數(shù)不相符的錯誤，可以在初始化時不指定數(shù)組的大小，而以實際提供的初值個數(shù)自動確定數(shù)組的大小。如：

inta［］={1，3，5，0，9，11};因提供了6個數(shù)值，所以a的大小即為6，最大下標的元素為a[5]。6.2.4一維數(shù)組的應用數(shù)組是一種非常有用的數(shù)據(jù)結構，當要處理同一種類型的多個數(shù)據(jù)時，首先就要想到利用數(shù)組，而不是去定義多個同一類型的變量。利用數(shù)組求解問題的一般步驟如下：

(1)定義數(shù)組。根據(jù)所要處理的數(shù)據(jù)的類型和多少，定義合適的數(shù)組，編譯系統(tǒng)會根據(jù)定義分配適當?shù)膬?nèi)存空間。

(2)輸入數(shù)組。數(shù)組定義之后，尚未有確定的內(nèi)容，必須根據(jù)問題用一種合適的輸入方式使數(shù)組中的每個元素具有所需要的值。

(3)處理數(shù)組。對已經(jīng)具有數(shù)值的數(shù)組按照任務的要求進行處理。

(4)輸出數(shù)組。以上幾步對數(shù)組的處理都是在內(nèi)存中進行的，外界看不到，要想查看數(shù)組中的內(nèi)容，必須以適當?shù)男问捷敵?。比如，為清晰整齊起見，每行輸出確定個數(shù)的數(shù)據(jù)；對于二維數(shù)組，按行進行輸出等，這就需要進行適當?shù)目刂啤Ｔ趯嶋H問題中，有時(2)、(3)步會結合進行，因為對數(shù)組處理的本身就隱含在對數(shù)組各元素的確定上。因為數(shù)組是由同類型的多個元素組成的，所以對各元素的處理都是相似的，因此處理數(shù)組很自然地就要使用循環(huán)語句，尤其是for語句。for語句的循環(huán)控制變量也就是數(shù)組的下標，可以根據(jù)數(shù)組下標的范圍來確定循環(huán)控制變量的初值和終值。

【例6-2】將數(shù)組倒置，如把12345變?yōu)?4321。編程思路：設數(shù)組a有n個元素，為實現(xiàn)前后倒置，只要把數(shù)組前后對應的元素逐個地進行交換即可，如圖6-2所示。也就是：

a［0］←→a［n-1］

a［1］←→a［n-2］

圖6-2交換示意圖如果n為偶數(shù)，則要對換n/2對元素；如果n為奇數(shù)，則要對換(n-1)/2對元素，即處于正中間的那個元素(下標為(n-1)/2)不需和任何元素對換。但不管n是偶數(shù)還是奇數(shù)，都要進行n/2次對換?？梢远x兩個整型變量i和j，分別作為數(shù)組前部元素和后部元素的下標，i的初值為0，j的初值為n-1，它們隨著操作的進行不斷向中間收縮，直至進行完n/2次交換。＃defineN10＃include<stdio.h>main(){inti，j，t，a［N］;printf(″Input10integers:＼n″);for(i=0;i<=N-1;i++)scanf(″%d″，&a［i］);printf(″Beforeinverse:＼n″);for(i=0;i<=N-1;i++)printf(″%3d″，a［i］);printf(″＼n″);for(i=0，j=N-1;i<N/2;i++，j--){t=a［i］;a［i］=a［j］;a［j］=t;}printf(″Afterinverse:＼n″);for(i=0;i<=N-1;i++)printf(″%3d″，a［i］);return0;}運行輸出：Input10integers:1234567890↙

Beforeinverse:1234567890↙Afterinverse:0987654321↙這里N=10，進行了N/2=5次對換，最后一次是a［4］和a［5］的對換。

【例6-3】一頭母牛一年生育一頭小母牛，小母牛從第4年開始又生育小母牛，問20年之內(nèi)，每年有多少頭牛?

編程思路：首先列出年數(shù)和牛數(shù)的對照表，以便發(fā)現(xiàn)其中的規(guī)律：從表中可以看出，從第4年起，每一年的頭數(shù)是前一年和前三年的頭數(shù)之和，即：tn=tn-1+tn-3(n≥4)可以建立一個數(shù)組來記錄每年的頭數(shù)：年數(shù)作為下標，頭數(shù)作為數(shù)組值。年數(shù)0123456…

牛數(shù)12346913…＃include<stdio.h>main(){inti，ncow［21］;ncow［1］=2，ncow［2］=3，ncow［3］=4；

for(i=4;i<=20;i++)ncow［i］=ncow［i-1］+ncow［i-3］;for(i=1;i<=20;i++){printf(″%-10d″，ncow［i］);if(i%5==0)printf(″＼n″);}return0;}運行輸出：

2 3 4 6 9 13 19 28 41 60 88 129 189 277 407 595 872 1278 1873 2745

【例6-4】用起泡法對數(shù)據(jù)進行排序。編程思路：起泡法的特點是將相鄰的兩個元素進行比較，把較小的元素調(diào)到前面(升序)或后面(降序)。如果數(shù)組有n個元素，那么用起泡法排序最多進行n-1遍比較。每一遍都是第1個元素和第2個元素比，第2個和第3個比，…，第i-1個和第i個比。在比較的過程中，只要發(fā)現(xiàn)相鄰元素逆序，就把它們交換，這樣當?shù)谝槐楸容^之后，最大的元素就被放到了最后(升序)；然后進行第二遍的排序，方法如上，只是排序的元素個數(shù)減少了1，最后這n-1個元素中的最大者被放在倒數(shù)第二位……這樣反復進行，直到最后數(shù)組中只余下兩個元素進行比較處理。設數(shù)組有6個元素，則其起泡排序過程可表示如下，其中“”表示比較，下劃線表示交換。第一遍：

879142 789142 789142 781942 781492

781429通過這一遍的比較，數(shù)組的最大元素9被放到了最后，然后對余下的5個元素進行第二遍排序。第二遍：

78142 78142 71842 71482

71428這一遍把次最大的元素8放到倒數(shù)第二位。第三遍：

7142 1742 1472

1427第四遍: 142 142 124第五遍：

12 12可以看出，每比較一遍就去掉一個元素，這樣數(shù)組中留待排序的元素就越來越少，直至最后只余下兩個元素進行比較。對上面的數(shù)組共比較了5遍，是比較次數(shù)最多的情況，而且每一遍都有交換事件的發(fā)生。但對有些數(shù)組，n個元素不一定要比較n-1遍，也許可以提早結束。如有數(shù)組：214397，進行第一遍比較：

214397 124397 124397 123497 123497 123479可以看出，只進行了一遍就將數(shù)組排好序，如果還按原計劃對其進行5遍比較操作，顯然后來的操作全是無用功。我們可以設法避免這種情況，即在不需要繼續(xù)比較的時候，讓程序發(fā)出一種信息，以及時退出不必要的循環(huán)。常用的方法是設置一個開關變量，令它的值是0或1。在每遍比較開始時，把它設為1，如果在該遍比較中發(fā)生過交換操作，就將其置為0，否則就保持其值為1。當下一遍比較時先判斷這個開關量是否為0，若為0，說明可能還有未排序的情況，可繼續(xù)進行，若為1，說明整個數(shù)組已全部排序，不需要繼續(xù)進行了。根據(jù)以上分析，可寫出如下程序。＃include<stdio.h>＃defineM500main(){inti，j，n，t，a［M］，fini，count，times;printf(″Inputn(<=%d)＼n″，M);

scanf(″%d″，&n);

printf(″Input%dnumberstobesorted:＼n″，n);for(i=0;i<=n-1;i++)scnaf(″%d″，&a［i］);fini=count=times=0;for(i=1;i<n&&!fini;i++){fini=1;count++;for(j=0;j<n-i;j++)if(a［j］>a［j+1］){ t=a［j］; a［j］=a［j+1］; a［j+1］=t; times++; fini=0;}}printf(″\npassnumber=%d\n，exchangetimes=%d\n″，count，times);for(i=0;i<n;i++){printf(″%d″，a［i］);if((i+1)%10==0)printf(″＼n″);}return0;}變量fini為開關變量，count為比較遍數(shù)的計數(shù)器，times為交換次數(shù)計數(shù)器。程序中首先定義一個大數(shù)組，在此范圍內(nèi)可以對任意個元素的數(shù)組進行排序，這樣處理比較靈活。運行輸出：Inputn(n<=500)6↙

Input6numberstobesorted:879142↙passnumber=5exchangetimes=11124789再次運行：Inputn(n<=500)10↙

Input10numberstobesorted:9817634541passnumber=9exchangetimes=331134456789上面的排序過程是由后向前進行的，即數(shù)組的后半部是排好序的，前半部是尚待排序的。在排序過程中，后半部逐漸增加，前半部逐漸減少，直至變?yōu)橐粋€元素。也可以采用相反的排序過程，即由前向后地進行排序，這只需對循環(huán)控制變量的初值和終值加以適當?shù)脑O置即可。比如可以寫為：for(i=1;i<n;i++)for(j=n-1，k=0;k<n-i;k++，j--){ if(a［j］<a［j-1］) { t=a［j］

a［j］=a［j-1］

a［j-1］=t; }}在這里，內(nèi)循環(huán)中另外使用了一個變量k來控制循環(huán)次數(shù)，其實也可以不用新增變量，只要把外循環(huán)的控制變量的初值和終值作適當改變即可：for(i=0;i<n-1;i++)for(j=n-1;j>i;j--){…}請讀者自行分析其執(zhí)行過程。

【例6-5】用Shell排序法對數(shù)據(jù)排序。在起泡排序法中每兩個相鄰的元素都要進行比較，這樣比較的次數(shù)就比較多。能否減少比較次數(shù)，加快排序的進行呢?Shell排序法可以做到。它的基本思想是允許第一次跳過較大的間隔去和后面的元素進行比較，當接近目的時，再跳過較小的間隔和后面的元素進行比較，直到間隔為1才進行相鄰元素的比較。每次跳過多大的間隔為好呢?通常采用一種簡單的方案：開始時跳過的間隔是數(shù)組長度的一半，以后每一遍再取上一間隔的一半。為了說明Shell排序的原理，我們以10個元素的數(shù)組為例作詳細的圖解說明。10個元素的跳步共有3種：10/2=5，5/2=2，2/2=1，即跳步jump可以取值5、2、1。原始數(shù)據(jù)：9817634541 jump=5:

9817634541 3817694541 3417698541 3417698541 3414698571 3414198576在這一遍中，第i個元素和第i+jump個元素比較，即第一個元素和第6個元素比較，第2個和第7個比較……，直到第5個和第10個比較。帶下劃線的數(shù)據(jù)表示是一對逆序數(shù)據(jù)，要對它們進行交換，交換后的結果在下一行顯示出來。當一遍進行完后，再重復這樣的操作，直到在當前跳步(jump=5)下再沒有應該交換的元素為止。上面最后一行已符合這樣的要求，于是把跳步縮小一半，對上一跳步下的結果繼續(xù)進行比較。在這一遍中，第i個元素和第i+jump個元素比較，即第一個元素和第6個元素比較，第2個和第7個比較……，直到第5個和第10個比較。帶下劃線的數(shù)據(jù)表示是一對逆序數(shù)據(jù)，要對它們進行交換，交換后的結果在下一行顯示出來。當一遍進行完后，再重復這樣的操作，直到在當前跳步(jump=5)下再沒有應該交換的元素為止。上面最后一行已符合這樣的要求，于是把跳步縮小一半，對上一跳步下的結果繼續(xù)進行比較。 jump=2:

3414198576 1434198576 1434198576 1414398576 1414398576 1414398576 1414358976 1414357986 1414357689在這一遍中是第i個和第i+jump比，比較結果如最后一行所示，再對其進行一遍類似的操作，未發(fā)現(xiàn)有逆序現(xiàn)象，于是轉(zhuǎn)入下一跳步操作。

jump=1: 1414357689 1414357689 1144357689 1144357689 1143457689 1143457689 1143457689 1143456789 1143456789最后一行是在本跳步下比較一遍之后的結果，但里面仍有逆序現(xiàn)象，必須在當前跳步下再重復一遍同樣的操作，然后繼續(xù)檢查，直至當前跳步下沒有逆序為止。最后的結果為：1134456789從上面的排序可以看出，Shell排序需要三重循環(huán)：最外層循環(huán)控制跳步的大?。蛔顑?nèi)層循環(huán)執(zhí)行掃描、比較和交換；中間一層的循環(huán)控制在當前跳步下重復檢查的次數(shù)，為此可設一個開關變量alldone來控制，其值為1表示進行內(nèi)循環(huán)，其值為0表示不再進行內(nèi)循環(huán)。設n為數(shù)組長度，a為數(shù)組名，則可用如下框架描述Shell排序過程：jump=n/2;while(jump>=1){alldone=1;while(alldone==1) {alldone=0; for(i=0;i<n-jump;i++) { j=i+jump; if(a［i］>a［j］) {交換a［i］和a［j］

alldone=1; } }}jump=jump/2;}由此可寫出完整的程序，程序中用jump表示跳步間隔，用count表示比較遍數(shù)，用times表示交換次數(shù)。＃include<stdio.h>＃defineM500main(){intt，i，j，n，jump，count，times，a［M］，alldone;printf(″Inputn(n<=%d):＼n″，M);

scanf(″%d″，&n);

printf(″Input%dnumberstobesortedinshell:＼n″，n);for(i=0;i<=n-1;i++)scanf(″%d″，&a［i］);count=times=0;jump=n/2;while(jump>=1){alldone=1;while(alldone==1){alldone=0; for(i=0;i<n-jump;i++) {j=i+jump; if(a［i］>a［j］) {t=a［i］; a［i］=a［j］; a［j］=t; alldone=1; times++; } } count++; } jump=jump/2;}for(i=0;i<=n-1;i++){printf(″%3d″，a［i］);if((i+1)%10==0) printf(″＼n″);}printf(″passnumber=%d\nexchangetimes=%d\n″，

count，times);return0;}運行輸出：Inputn(n<=500)10↙

Input10numberstobesortedinshell:9817634541↙

1134456789passnumber=7exchangetimes=13和起泡法相比，Shell排序法的比較遍數(shù)和交換次數(shù)都有所降低，說明Shell排序法是個更有效的排序方法。6.2.5數(shù)組作為函數(shù)的參數(shù)在前面的函數(shù)中，我們定義和使用的參數(shù)類型都是基本類型，其實數(shù)組也可以作為參數(shù)使用。數(shù)組作參數(shù)具有一些特殊的性質(zhì)，利用這樣的性質(zhì)可以對數(shù)組進行需要的加工處理。數(shù)組作參數(shù)時，實參和形參的關系也和普通數(shù)據(jù)類型一樣，必須作到個數(shù)、類型、次序相一致；形參數(shù)組和實參數(shù)組必須分別定義，但其大小不一定一樣。在函數(shù)中對形參數(shù)組處理時必須特別小心，如形參數(shù)組大，實參數(shù)組小，則對函數(shù)中形參過長的部分不能加以引用，若引用將出現(xiàn)錯誤。如： 實參數(shù)組： 形參數(shù)組：

4687不可引用反過來，如形參數(shù)組定義過小，則實參數(shù)組后面多余的元素就會被舍掉而得不到處理。如： 實參數(shù)組： 形參數(shù)組：4687543被舍掉為了避免這兩種情況，使形參數(shù)組具有較大的適應性，在定義形參數(shù)組時可以不指定大小，而把實參數(shù)組的大小再用一個參數(shù)表示出來。例如：函數(shù)定義為：

floataverage(floata［］，int);在主調(diào)函數(shù)中，若有兩個數(shù)組：

floats1［5］={34，68，79.6，87.5，68.4} floats2［8］={91.3，62.4，81，76，66，95.5，87.2，77.8};則可以調(diào)用函數(shù)average如下：ave1=average(s1，5);ave2=average(s2，8);這樣average函數(shù)就處理了長度為5和8的兩個實際數(shù)組。數(shù)組名作參數(shù)有個最重要的特征是傳遞數(shù)組的首地址，就是說把實參數(shù)組的首地址傳給形參數(shù)組，使形參和實參都用同樣的內(nèi)存空間，因而函數(shù)中對形參數(shù)組的處理也就是對實參數(shù)組的處理。這是和其他類型作參數(shù)不同的地方。其他類型作參數(shù)時，向函數(shù)傳遞的是實參的一個拷貝，函數(shù)中是對實參拷貝的處理，與實參變量本身沒有關系，這就是所謂的“傳值調(diào)用”。數(shù)組名代表數(shù)組的首地址，把實參數(shù)組名傳給函數(shù)，函數(shù)中對該數(shù)組的處理就像在主調(diào)函數(shù)中對它的處理一樣。在程序設計中往往利用這一特點來改變數(shù)組，如對數(shù)組進行排序等。

【例6-6】用選擇法對數(shù)組排序。編程思路：選擇法的要點是首先從有n個元素的數(shù)組a中選出一個最小的元素，把它和a［0］交換，再從余下的n-1個元素中選出一個最小的元素和a［1］交換……。每進行一遍選擇就可確定一個排序元素，把它放到數(shù)組的前部。重復這樣的過程，直到最后只剩下兩個元素進行比較。為了提高排序效率，不必在發(fā)現(xiàn)一個比a［0］小的元素如a［i］后就和a［0］交換，也許后面還有比a［i］更小的元素a［i+j］呢!處理的辦法是記住當前最小元素的下標，在一遍比較中，該下標可能有變化，在一遍比較結束后再來決定是否和a［0］交換。把該算法用一個函數(shù)來實現(xiàn)，即為voidselsort(inta［］，intn){inti，j，k，t;for(i=0;i<n-1;i++){k=i;for(j=i+1;j<n;j++) if(a［j］<a［k］)k=j;if(k!=i){t=a［k］;a［k］=a［i］;a［i］=t;}}}這里的k用以標記當前最小元素的下標，初值置為i，即當前數(shù)組第一個元素的下標。在內(nèi)循環(huán)結束之后，要檢查k的值是否發(fā)生了變化，若發(fā)生了變化，即k不再等于i，則說明后面的元素a［k］比a［i］小，這時應將它們交換。如果最后k仍然等于i，則說明a［i］就是當前數(shù)組的最小元素，不需要交換操作。主調(diào)函數(shù)調(diào)用該函數(shù)時，把一個真實的數(shù)組名作為實在參數(shù)代入，程序如下。＃include<stdio.h>voidselsort(int［］，int);main(){inti，j，a［10］;printf(″Input10integers:＼n″);for(i=0;i<=9;i++)scanf(″%d″，&a［i］);selsort(a，10);printf(″sortedarrayare:＼n″);for(i=0;i<=9;i++)printf(″%3d″，a［i］);return0;}運行輸出：Input10integers:3642518794↙

sortedarrayare:1234456789主函數(shù)中的

voidselsort(int［］，int);是函數(shù)原型聲明，當參數(shù)是數(shù)組時可以不給出數(shù)組名，只用“<類型名>［］”就可以表示在這里有一個這種類型的數(shù)組。函數(shù)調(diào)用語句

selsort(a，10);的功能是完成對數(shù)組a的排序，不要求函數(shù)返回值。

【例6-7】二分法查找。查找是一種用途廣泛的操作。查找有很多種方法。如果一個數(shù)組未加排序，那么可以使用順序查找法，從第一個元素起一個一個地考查，直到發(fā)現(xiàn)所求元素，或者查完數(shù)組也未發(fā)現(xiàn)要找的元素。如果數(shù)組中有n個元素，則用順序查找法時平均要查找n/2次。如果數(shù)組已經(jīng)排序(假設為按升序排序)，則可以用二分法查找。它的基本思想是：首先把數(shù)組中間的那個元素和所求元素進行比較，看是否為所求元素，若是，則查找結束；如果不是，則進一步比較該元素和所求元素的大小關系，若所求元素小，則說明應該到數(shù)組的前半部分中找，否則就應該到后半部分中找，這樣把查找范圍一下子縮小了一半。以后在較小范圍內(nèi)仍按同樣的方法進行查找，這樣很快就可以得到結果。用這種方法查找有n個元素的數(shù)組的最大查找次數(shù)為lbn(即以2為底n的對數(shù))。當對有10億(近似于230)個元素的數(shù)組進行查找時，用順序查找平均需要5億次，而用二分法查找則最多只需30次，真是天壤之別!二分法查找算法可用一個迭代函數(shù)bis來實現(xiàn)。該函數(shù)有4個參數(shù)：數(shù)組名、關鍵字key、最小下標low和最大下標high。如果關鍵字和當前查找的數(shù)組的中間元素(下標為mid)不匹配，就修改最小下標low或最大下標high，從而在一個更小的范圍內(nèi)查找。如果關鍵字key小于中間元素，就把最大下標置為mid-1，并繼續(xù)在low和mid-1之間查找；如果關鍵字大于中間元素，就把最小下標low置為mid+1，然后繼續(xù)在mid+1和high之間查找。對當前考查范圍內(nèi)的中間元素在顯示時都打上“*”號標記，代表是該元素和關鍵字進行比較，這種顯示方法也單獨用一個函數(shù)來實現(xiàn)。程序中全局變量m是一個記錄查找次數(shù)的計數(shù)器。程序如下：＃include<stdio.h>＃defineM15intm=0;intbis(int［］，int，int，int);voidprintr(int［］，int，int，int);main(){

inti，k，result，a［M］;

printf(″Input%dnumbersinorder:＼n″，M);

for(i=0;i<=M-1;i++)scanf(″%d″，&a［i］);printf(″Enteranumbertofind:＼n″);scanf(″%d″，&k);result=bis(a，k，0，M-1);

if(result!=-1) printf(″%dfoundinarrayelement%d\n″，k，result); else printf(″%dnotfound!＼n″，k); printf(″searchtimes=%d＼n″，m); return0; }intbis(intb［］，intkey，intlow，inthigh){intmid;while(low<=high){ mid=(low+high)/2; m++; printr(b，low，mid，high); if(key==b［mid］) returnmid; elseif(key<b［mid］) high=mid-1; elselow=mid+1;}return-1;}voidprintr(intb［］，intlow，intmid，inthigh){inti;for(i=0;i<=M-1;i++)if(i<low‖i>high) printf(″″);elseif(i==mid) printf(″%3d*″，b［i］);elseprintf(″%3d″，b［i］);printf(″＼n″);}運行輸出：Input15numbersinorder:123456789101112131415↙

Enteranumbertofind:5↙

12345678*91011121314151234*56756*75*5foundinarrayelement4searchtimes=4對于二分法查找算法，我們還可以用遞歸函數(shù)來實現(xiàn)。該算法的遞歸形成為：intbis(intb［］，intkey，intlow，inthigh){intmid;if(low>high)return-1;mid=(low+high)/2;m++;printr(b，low，mid，high);if(key==b［mid］)returnmid;elseif(key<b［mid］) returnbis(b，key，low，mid-1);else returnbis(b，key，mid+1，high);}對照兩個函數(shù)，我們可以發(fā)現(xiàn)，在迭代算法中使用的是循環(huán)語句，而在遞歸算法中是不用循環(huán)語句的，它是對函數(shù)自身的調(diào)用，只是要修改函數(shù)的參數(shù)。一個數(shù)組可以看作是由兩部分組成的：數(shù)組的第一個元素和除第一個元素之外的其他部分。這余下的部分又是個小數(shù)組，又可以看作由兩部分組成。由此可以得知：數(shù)組也是一個遞歸的數(shù)據(jù)類型，可以用遞歸的方法對數(shù)組進行處理。

【例6-8】請說出下面程序的功能。＃include<stdio.h>intsum(int［］，int);main(){inttotal，a［10］={1，2，3，4，5，6，7，8，9，10};total=sum(a，10);printf(″Total=%d＼n″，total);return0;}intsum(intb［］，intn){if(n==1)return(b［0］);elsereturn(b［n-1］+sum(b，n-1));}

sum函數(shù)有一個數(shù)組作為形參，調(diào)用時主調(diào)函數(shù)給它賦以實在數(shù)組名a。函數(shù)sum用遞歸的方法對數(shù)組進行處理。若數(shù)組只有一個元素(n=1)，則把其惟一的元素b［0］返回，這也是遞歸的邊界條件。如果數(shù)組有多個元素(n>1)，那么先求出其前n-1個元素的和，再把最后一個元素b［n-1］加上去。由此就可斷定，對前n-1個元素的處理實際上是求前n-1個元素的和。遞歸調(diào)用時，參數(shù)在遞減，數(shù)組在變短，所以每次的“最后元素”也是個相對的概念，它只是當前所考慮數(shù)組的最后元素。最后一定會變到只有一個元素b［0］，作為邊界條件終止遞歸調(diào)用。由以上分析可知，該程序的功能是計算a［0］+a［1］+…+a［9］的值，所以運行輸出為：

Total=55

【例6-9】將數(shù)字1、2、3、4、5、6、7、8、9分成3組，使每一組構成的3位數(shù)均是完全平方數(shù)，且3組中的數(shù)字均不相同。

編程思路：首先產(chǎn)生數(shù)字沒有重復的完全平方的3位數(shù)，并將它們放入一個一維數(shù)組中。然后對該數(shù)組中的各個元素進行相互比較，從中找出3個符合各位數(shù)字均無重復要求的三位數(shù)?？蓪⑴袛嘁粋€整數(shù)是否完全平方數(shù)編一個函數(shù)，再將判斷兩個整數(shù)各位數(shù)字是否相同也編為一個函數(shù)。如已知一個數(shù)是完全平方數(shù)，還要進一步求出它是哪一個數(shù)的平方，則可用另一個函數(shù)解決。判斷兩個三位數(shù)中有沒有重復數(shù)字的算法采用的是分解法，即先從兩個三位數(shù)中各分離出三個數(shù)字，再判斷這些數(shù)字有無重復。求解一個數(shù)(n)是哪個數(shù)(j)的平方的算法，是從這個數(shù)中不斷地減2，直到0為止，則減的次數(shù)即為所求的j值。產(chǎn)生沒有重復數(shù)字的三位數(shù)的方法是合成法，直接由不同的三個數(shù)字來構成三位數(shù)。＃include<stdio.h>intsq(intn)//判斷一個數(shù)是否完全平方數(shù){inti;for(i=1;i<n/2;i++)if(i*i==n) return1;return0;}intneq(intm，intn)//判斷兩個沒有重復數(shù)字的三位數(shù)是否完全不同，即沒有重復數(shù)字{inti1，j1，k1，i2，j2，k2;i1=m/100;j1=m%100/10;k1=m%10;i2=n/100;j2=n%100/10;k2=n%10;if(i1!=i2&&i1!=j2&&i1!=k2&&j1!=i2&&j1!=j2&&j1!=k2&&k1!=i2&&k1!=j2&&k1!=k2)return1;return0;}intksqr(intn)//求一個已知的平方數(shù)是哪個數(shù)的平方{inti，j;for(i=1，j=1;;i+=2)if((n-=i)!=0)j++;elsebreak;returnj;}main(){inti，j，k，r=0，b［15］，m;printf(″＼nSquarenumberhaving3digitsare：\n\n″);for(i=1;i<=9;i++)//求出本身沒有重復數(shù)字的且是完全平方的三位數(shù)

for(j=1;j<=0;j++)if(j!=i) for(k=1;k<=9;k++) if(k!=i&&k!=j&&sq(i*100+j*10+k)) {b［r++］=i*100+10*j+k; m=r-1; printf(″%5d=(%d)**2\n″,b[m]，ksqr(b[m]));}printf(″＼nTotalnumber:%d＼n″，r);printf(″＼=nThis3numbershavenotsamenumber:＼n″);for(i=0;i<r;i++)//求出互不相同的三個數(shù)，共包含1，

2，3，4，5，6，7，8，9九個數(shù)字

for(j=i+1;j<r;j++)for(k=j+1;k<r;k++)if(neq(b[i]，b[j])&&neq(b[i]，b[k])&&neq(b[j]，b[k])) printf(″%d=(%d)**2%d=(%d)**2%d=(%d)**2\n\n″,b[i]，ksqr(b[i]，b[j]，ksqr(b[j]，

b[k]，ksqr(b[k]));return0;}運行輸出：Squarenumberhaveing3digitsare:169=(12)**2196=(14)**2256=(16)**2289=(17)**2324=(18)**2361=(19)**2529=(23)**2576=(24)**2625=(25)**2729=(27)**2784=(28)**2841=(29)**2961=(31)**2Totalnumber:13This3numbershavenotsamenumber:361=(19)**2529=(23)**2784=(28)**2

【例6-10】從30名運動員中選出10名優(yōu)秀運動員，具體規(guī)則是：

(1)運動員按1，2，3，…順序編號；

(2)由鍵盤輸入選票，每張選票最多可寫10個不同的編號，按出現(xiàn)的順序表示名次；

(3)對應名次可以空缺，但必須用0表示；

(4)若編號超出規(guī)定的范圍(1~30)或編號出現(xiàn)了重復，則該編號無效，該票上的其他編號仍認為有效；

(5)每張票中的編號按順序得分為：15，12，9，7，6，5，4，3，2，1；

(6)按運動員所得分數(shù)從高到低排序，輸出前10名最佳運動員排名表，格式為： 名次編號得分得票數(shù)如得分相同，則得票多的在前：如得分和得票都相同，則編號小的在前。編程思路:

(1)一張票上有10個整數(shù)，用整型數(shù)組表示，通過循環(huán)語句實現(xiàn)輸入。如其中有重復的數(shù)字，則把這些數(shù)字全部置為0，表示不予考慮。這種重復數(shù)字置0的操作可用雙重循環(huán)實現(xiàn)。

(2)因票數(shù)未定，故用While語句實現(xiàn)循環(huán)，先輸入一個非負的整數(shù)開始循環(huán)，最后以輸入一個負數(shù)退出循環(huán)。在循環(huán)體中每讀入一張票(即10個整數(shù)），就對其進行有效性處理(1)。以整數(shù)所代表的運動員編號減1作為票數(shù)數(shù)組的下標，累加該運動員所得票數(shù)；而以該整數(shù)輸入時的順序作為權值數(shù)組的下標，求出相應的權值進行分數(shù)的累加。這里用一個數(shù)組元素作為另一個數(shù)組元素的下標，應考慮到運動員的編號(從1開始)與數(shù)組下標(從0開始)的差別。＃include<stdio.h>voidsort(inta[]，intx[]，intk)//按分數(shù)排序，讓序號跟著分數(shù)走。此處是對數(shù)組{//a(放分數(shù))排序，數(shù)組x(放序號)跟著走inti，j，m，n;for(i=1;i<k;i++){for(j=0;j<k-i;j++) if(a［j］<a［j+1］) {m=a［j］;n=x［j］; a［j］=a［j+1］;x［j］=x［j+1］; a［j+1］=m;x［j+1］=n; }}}main(){inta［30］={0}，aa［30］={0}，a1［10］，b［10］

={15，12，9，7，6，5，4，3，2，1},x［30］，i，

j，k，m，n，c;//數(shù)組a表示得票數(shù)，aa表示積分數(shù)，x表示編號，b表示權值，a1代表一張選票

n=0;for(i=0;i<30;i++) x［i］=i+1;while(1){printf(″Enteraninteger，negativetostop＼n″);scanf(″%d″，&c);//控制循環(huán)是否中止

if(c<0) break;printf(″Input10integers:0---30＼n″);for(i=0;i<10;i++); //每次讀入10個數(shù)據(jù)，算是一張選票

scanf(″%d″，&a1［i］);for(i=0;i<9;i++) //將一張選票中的重復數(shù)字全置為0{for(k=i+1;k<10;k++)if(a1［k］==a1［i］){a1［k］=0;n=1;}if(n==1){a1［i］=0;n=0;}}for(i=0;i<10;i++)//讓選票中有效的數(shù)字(1~30)，即a1數(shù)組的元素作為票數(shù)數(shù)組a的下標if(a1［i］>=1&&a1［i］<=30){a［a1［i］-1］++; //所得票數(shù)累加

aa［a1［i］-1］+=b［i］;//所得分數(shù)累加相應的權值

} } sort(aa，x，30);//按分數(shù)a降序排序，讓序號x跟著分數(shù)走for(i=0;i<10;i++) //只對積分數(shù)數(shù)組aa的前10個數(shù)據(jù)進行輸出

{for(j=i+1;j<10;j++)if(aa［j］==aa［i］)//兩人分數(shù)aa［］相等時

{if(a［j］>a［i］)//則票數(shù)a［］多的在前

{m=a［j］;n=x［j］;//序號x［］跟著票數(shù)a走

a［j］=a［i］;x［j］=x［i］;a［i］=m;x［i］=n;}if(a［j］==a［i］) //如票數(shù)a［］也相等

if(x［j］<x［i］) //則序號x［］小的在前

{m=x［j］; x［j］=x［i］; x［i］=m; }}}printf(″\n\n名次編號得分得票數(shù)\n\n″）; //每行輸出一個運動員的信息for(i=0;i<10;i++) //輸出前10名運動員

{printf(″%2d″，i+1);printf(″%2d″，x［i］+1);printf(″%2d″，aa［i］);printf(″%2d″，a［x［i］］);printf(″＼n″);}return0;}運行輸出：Enteraninteger，negativetostop999Input10integers:1---307865432890Enteraninteger，negativetostop999Input10integers:1---3015693409722Enteraninteger，negativetostop99Input10integers:1---302231142426281957Enteraninteger，negativetostop999Input10integers:1---306754311233478Enteraninteger，negativetostop-8名次編號得分得票數(shù)1 6 33 32 5 30 43 3 29 44 4 25 45 7 18 36 22 16 27 1 15 18 11 14 29 24 6 110 26 5 16.3一維字符數(shù)組元素類型為char的數(shù)組是字符數(shù)組。字符數(shù)組有和其他數(shù)組相同的共性，同時也有自己的特性，即有獨特的運算函數(shù)和處理方法，因此我們對字符數(shù)組作單獨的討論。6.3.1一維字符數(shù)組變量的定義和引用一維字符數(shù)組的定義格式和其他類型數(shù)組的定義格式一樣，如語句

charc［10］；定義了有10個字符元素的數(shù)組c，這10個元素分別用c［0］，c［1］，c［2］，…，c［9］表示。

【例6-11】從鍵盤輸入一行字符，以換行符結束，分別以正向和反向的次序輸出。＃include<stdio.h>＃defineM80main(){inti，n;chars［M］;for(i=0;i<=M-1;i++){s［i］=getchar();if(s［i］==′＼n′)break;}

for(n=0;n<i;n++)putchar(s［n］);putchar(′＼n′);for(n=i-1;n>=0;n--)putchar(s［n］);return0;}程序在從第一個for循環(huán)出來之后，i的值是小于M的一個整數(shù)，而且s［i］等于“＼n”，不可輸出顯示，因此在進行下面的正向和反向輸出時應當注意到這一點。6.3.2字符數(shù)組的輸入/輸出

1.字符數(shù)組的輸入字符數(shù)組有四種輸入方法：賦值輸入法、格式控制輸入法、連續(xù)字符輸入法和用gets函數(shù)輸入法。

(1)賦值輸入法。賦值輸入法通過對數(shù)組變量賦初值的方法使數(shù)組元素具有值。賦初值時，既可以逐字符地賦值，也可以以字符串的形式賦值。如：

charc1［10］，c2［20］，c3［］={′a′，′b′，′c′，′d′}，c4［］=″abcd″；

注意：c3和c4是有區(qū)別的：c3的長度是4，而c4的長度是5，因為字符串中包含一個看不見的“＼0”字符作為結束標志。如果數(shù)組定義時指定了長度，則輸入的字符應不大于定義的長度。使用賦值輸入法時常見的錯誤是在定義之后又對數(shù)組名進行賦值操作。如：c1={′c′，′d′，′e′};c2=″China″;是錯誤的，因為c1、c2是數(shù)組名，代表數(shù)組的首地址，它在內(nèi)存中是個常量，不能改變，因此不能作為賦值語句的左值使用。對其他類型的數(shù)組也都是如此。

(2)格式控制輸入法。此時使用的格式控制符是“%s”，例如對上面定義的數(shù)組，可以用下列語句輸入：

scanf(″%s″，c1);因為c1代表數(shù)組的首地址，所以在讀的時候，在c1前就不必再加取地址運算符“&”了。若從鍵盤輸入：

China↙

則c1中就有“China”的內(nèi)容。這樣輸入時也應保證輸入的字符個數(shù)小于數(shù)組的長度。如果輸入的串中含有空格，則這種輸入法將只把空格以前的部分讀入數(shù)組，空格以后的部分被舍棄，并在輸入部分的最后自動增加一個字符串結束標志′＼0′。如：

scanf(″%s″，c2);鍵盤輸入：

ChinaBeijing↙

則c2中只有“China”的內(nèi)容：利用數(shù)組