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

第7章數(shù)組7.1一維數(shù)組7.2二維數(shù)組7.3數(shù)組與運算符7.4數(shù)組與函數(shù)7.5字符數(shù)組與字符串7.6數(shù)組應用實例

7.1一維數(shù)組

7.1.1一維數(shù)組的定義

同其他基本數(shù)據(jù)類型的變量一樣，在C語言中使用數(shù)組變量也遵循“先定義、后使用”的原則。

一維數(shù)組的定義方式為

類型說明符數(shù)組名[常量表達式]；

其中：

類型說明符可以是任一種基本數(shù)據(jù)類型或構造數(shù)據(jù)類型的說明符。數(shù)組的類型實際上是指各個數(shù)組元素的數(shù)據(jù)類型。對于同一個數(shù)組，其所有元素的數(shù)據(jù)類型都是相同的。

數(shù)組名是用戶定義的數(shù)組標識符，其書寫規(guī)則應符合標識符的書寫規(guī)定，且不能與其他變量同名。

方括號中的常量表達式表示數(shù)組元素的個數(shù)，也稱為數(shù)組的長度。它同時規(guī)定了數(shù)組中各個數(shù)組元素下標的取值范圍。如a[5]表示數(shù)組a有5個元素，其下標從0開始計算，因此這5個元素分別為a[0]、a[1]、a[2]、a[3]、a[4]。

例如：

inta[10];

/*說明整型數(shù)組a有10個元素*/

floatb[10]，c[20];/*說明實型數(shù)組b有10個元素，實型數(shù)組c有20個元素*/

charch[20];

/*說明字符數(shù)組ch有20個元素*/我們知道，執(zhí)行到變量定義語句時系統(tǒng)會在內存為變量分配相應的存儲空間。例如，為整型變量分配2個字節(jié)，為字符型變量分配1個字節(jié)。那么，系統(tǒng)是怎樣為數(shù)組變量分配存儲空間的呢？

實際上，系統(tǒng)會分配一段連續(xù)的存儲空間來依次存儲數(shù)組中的各個數(shù)組元素，如圖7-1所示。為了能夠訪問數(shù)組中的各個元素，系統(tǒng)將這段空間的第一個內存單元地址記入數(shù)組名，即數(shù)組名對應的是數(shù)組的首地址。假設首地址為10000H，則數(shù)組名對應的地址值即為10000H。因此，數(shù)組名與變量名有著本質的區(qū)別：程序中直接使用變量名代表的是該變量中存放的數(shù)據(jù)值；若直接使用數(shù)組名則代表的是該數(shù)組的首地址，它是一個地址值，而不是數(shù)據(jù)值。變量可被賦值，而數(shù)組名是常量，不能被賦值。圖7-1一維數(shù)組的存儲由于數(shù)組元素是順序存放的，所以很容易可以由數(shù)組的首地址計算出數(shù)組中第i個元素的存放地址。因此，數(shù)組是一種可直接存取的線性結構。

系統(tǒng)為數(shù)組分配的存儲空間大小由數(shù)組類型和數(shù)組長度共同決定，即數(shù)組所占用的存儲空間等于所有數(shù)組元素占用空間之和。例如，對于數(shù)組定義語句“inta[10]；”，由于每個數(shù)組元素都是int類型，均需要占用2個字節(jié)，所以系統(tǒng)會分配20個字節(jié)用來存儲該數(shù)組。定義數(shù)組還應特別注意：

(1)不能在方括號中用變量來表示元素的個數(shù)，但是可以用符號常量或常量表達式來表示元素的個數(shù)。考慮到在程序的后續(xù)維護過程中可能需要修改數(shù)組的長度，因此較好的做法是用宏來定義數(shù)組的長度。

例如：

#defineFD5

main()

{

inta[3+2]，b[7+FD];

…

}

是合法的。但是下述說明方式是錯誤的：

main()

{

intn=5;

inta[n];

…

}

(2)允許在同一個類型說明中說明多個數(shù)組和多個變量。例如：

inta，b，c，d，k1[10]，k2[20];

(3)在數(shù)組定義前加const可將數(shù)組變?yōu)椤俺Ａ俊?。例如?/p>

constintmonth[]={31，28，31，30，31，30，31，31，30，31，30，31};

C語言規(guī)定不允許修改常量數(shù)組中各元素的值。將程序執(zhí)行過程中其值不希望改變的數(shù)組聲明為常量數(shù)組有利于編譯器發(fā)現(xiàn)錯誤，避免不必要的錯誤發(fā)生。7.1.2一維數(shù)組的引用

雖然所有的數(shù)組元素是用一條語句同時定義的，但我們可能并不期望同時操作所有的數(shù)組元素，而有可能只對其中的某個或某幾個數(shù)組元素進行操作。因此，在使用數(shù)組時，我們期望能夠對數(shù)組元素進行單獨操作，也就是單獨引用數(shù)組元素。

數(shù)組元素是組成數(shù)組的基本單元，其標識方法為數(shù)組名后跟一個下標，下標表示該數(shù)組元素在數(shù)組中的順序號。這樣系統(tǒng)就可以根據(jù)數(shù)組名、數(shù)組類型及數(shù)組元素的下標值計算出該數(shù)組元素的存放地址，進而對該數(shù)組元素進行讀/寫操作。一維數(shù)組元素也稱為單下標變量，其表示形式為

數(shù)組名[下標表達式]

其中：下標表達式只能為整型常量、整型變量或整型表達式。若為小數(shù)，在編譯時將自動取整。

這里的下標表達式和數(shù)組定義中的常量表達式在形式上有些相似，但這兩者具有完全不同的含義。數(shù)組定義時方括號中給出的是數(shù)組的長度，即下標的有效范圍值；而數(shù)組元素中的下標是該元素在數(shù)組中的位置標識。前者只能是常量，后者可以是常量、變量或表達式。例如，a[5]、a[i]、a[i+j]?都是合法的數(shù)組元素。數(shù)組元素通常也稱為下標變量。

注意

對于“inta[10];”，數(shù)組元素a[10]?是不合法的引用，因為10超出了該數(shù)組的有效下標范圍。

必須先定義數(shù)組，才能使用下標變量。一個下標變量本質上相當于一個同類型(數(shù)組類型)的普通變量。例如，若有定義inta[5]，則a[0]、a[1]、a[2]、a[3]、a[4]?這5個下標變量在程序中的作用相當于5個普通的整型變量。在C語言中只能逐個地使用下標變量，而不能一次引用整個數(shù)組。例如，輸出有10個元素的數(shù)組必須使用循環(huán)語句逐個輸出各下標變量：

for(i=0;i<10;i++)

printf(“%d”，a[i]);

而不能用一個語句輸出整個數(shù)組。

對數(shù)組a，下面的寫法是錯誤的：

printf("%d"，a);

數(shù)組下標可以是任何整型表達式，如下面的例7.1中的兩個程序是完全等價的。但若將程序2中的語句“a[i++]=i;”修改為“a[++i]=i;”，兩個程序就不再等價了。因此，當下標中包含自增操作時一定要特別注意。

【例7.2】錄入一串數(shù)，然后反向輸出這串數(shù)。

程序如下：

#include<stdio.h>

#defineN10

/*定義常量N*/

main()

{

inta[N]，i;

/*定義長度為N的數(shù)組a*/

printf(“Enter%dnumbers:”，N);

for(i=0;i<N;i++)

scanf(“%d”，&a[i]); /*從鍵盤輸入10個數(shù)，初始化數(shù)組a*/

printf(“Inreverseorder:”);

for(i=N-1;i>=0;i--)

printf(“%d”，a[i]); /*逆序輸出數(shù)組a中的各個元素*/

printf("\n");

}從例7.2中不難看到，僅僅通過變換數(shù)組下標就可以方便地訪問數(shù)組中的各個元素。下標的變換往往通過循環(huán)變量的變化來控制，所以找到它們之間的關系就成為程序設計中處理數(shù)組的關鍵。另外，這個程序很好地體現(xiàn)了用宏定義數(shù)組長度的好處，不但提高了程序的可讀性，而且日后想要修改數(shù)組的長度時，只需要改一個地方就能做到“一改全改”，方便又快捷。

數(shù)組元素的下標總是從0開始的，所以長度為n的數(shù)組，其有效的數(shù)組下標范圍為0～n-1，因此，只有當下標表達式的值在該范圍內時數(shù)組引用才是有效的。但實際上C語言并不要求對下標范圍進行檢查，即編譯器不認為數(shù)組下標越界是語法錯誤。這就造成存在數(shù)組下標越界問題的程序在編譯時能通過，執(zhí)行時卻得不到預期的正確結果，甚至運行時會產生錯誤。對數(shù)組的越界訪問會造成不可預計的后果。越界取得的數(shù)據(jù)顯然沒有意義，使用這種數(shù)據(jù)可能導致程序給出莫名其妙的結果。越界賦值則更危險，這種操作的后果是非常可怕的。越界賦值會破壞被賦值位置的原有數(shù)據(jù)，其后果難以預料，因為根本無法知道被這個操作破壞的到底是什么，可能是其他程序的變量值，也可能是重要的內部控制信息。實際中惡意攻擊者或惡意程序最常用的一種技術就是設法造成程序執(zhí)行中出現(xiàn)數(shù)組越界訪問，并借機取得被攻擊計算機系統(tǒng)的控制權。總之，保證對數(shù)組元素的訪問不超出合法范圍是非常重要的。7.1.3一維數(shù)組的初始化

給數(shù)組賦值的方法除了用賦值語句對數(shù)組元素逐個賦值外，還可以采用初始化賦值的方法。數(shù)組初始化賦值是指在數(shù)組定義時給數(shù)組元素賦予初值。數(shù)組初始化是在編譯階段進行的，這樣將減少運行時間，提高效率。

初始化賦值的一般形式為

類型說明符數(shù)組名[常量表達式]={值，值，…，值}；

其中：在{?}中的各數(shù)據(jù)值即為各元素的初值，各值之間用逗號間隔。

例如，“inta[10]={0，1，2，3，4，5，6，7，8，9};”相當于“a[0]=0;a[1]=1，…，a[9]=9;”。

C語言對數(shù)組的初始化賦值還有以下幾點規(guī)定：

(1)可以只給部分元素賦初值。當?{?}?中值的個數(shù)少于元素個數(shù)時，只給前面部分元素賦值，其余元素自動賦0值。

例如：

inta[10]={0，1，2，3，4};

表示只給a[0]～a[4]5個元素賦值，而后5個元素自動賦0值。因此，若想將數(shù)組a中的各元素均初始化為0，可簡寫為“inta[10]={0};”。

(2)只能給元素逐個賦值，不能給數(shù)組整體賦值。

例如，給10個元素全部賦1值，只能寫為

inta[10]={1，1，1，1，1，1，1，1，1，1};

而不能寫為

inta[10]=1;

(3)如給全部元素賦值，則在數(shù)組說明中可以不給出數(shù)組元素的個數(shù)，數(shù)組長度由{?}中值的個數(shù)決定。

例如，“inta[10]={1，2，3，4，5};”與“inta[]={1，2，3，4，5};”是不等價的。前一個數(shù)組長度為10，而后一個數(shù)組長度為5。7.1.4一維數(shù)組應用舉例

可以在程序執(zhí)行過程中對數(shù)組作動態(tài)賦值。這時可用循環(huán)語句配合scanf函數(shù)逐個對數(shù)組元素賦值。

【例7.3】輸入10個數(shù)，輸出其中的最大數(shù)及其序號。

程序如下：

main()

{

inti，max，maxi，a[10];

printf(“input10numbers:\n”);

for(i=0;i<10;i++)/*用循環(huán)語句配合scanf函數(shù)逐個對數(shù)組元素賦值*/

scanf(“%d”，&a[i]);

max=a[0];maxi=0;

for(i=1;i<10;i++)

if(a[i]>max)

{

max=a[i];

maxi=i;

}

printf("max%d:%d\n"，maxi，max);

}本例程序中第一個for語句逐個輸入10個數(shù)到數(shù)組a中，然后把a[0]?送入max中。在第二個for語句中，從a[1]?到a[9]?逐個與max中的內容比較，若比max的值大，則把該下標變量送入max中，同時記下其下標值。因此max總是在已比較過的下標變量中的最大者。比較結束，輸出max及其序號的值。

【例7.4】

把一個整數(shù)按大小順序插入已排好序的數(shù)組中。

為了把一個數(shù)按大小順序插入已排好序的數(shù)組中，應首先確定排序是從大到小還是從小到大進行的。設排序是從大到小排序的，則可把欲插入的數(shù)與數(shù)組中的各數(shù)逐個比較，當找到第一個比插入數(shù)小的元素i時，該元素之前即為插入位置。然后從數(shù)組最后一個元素開始到該元素為止，逐個后移一個單元。最后把插入數(shù)賦予元素i即可。如果被插入數(shù)比所有的元素值都小，則插入最后位置。程序如下：

main()

{

inti，j，p，q，s，n，a[11]={127，3，6，28，54，68，87，105，162，18};

for(i=0;i<10;i++)

{

p=i;q=a[i];

for(j=i+1;j<10;j++)

if(q<a[j])

{p=j;q=a[j];}

if(p!=i)

{s=a[i];a[i]=a[p];a[p]=s;}

printf("%d"，a[i]);

}

printf(“\ninputnumber:\n”);

scanf(“%d”，&n);

for(i=0;i<10;i++)

if(n>a[i])

{

for(s=9;s>=i;s--)a[s+1]=a[s];

break;

}

a[i]=n;

for(i=0;i<=10;i++)

printf(“%d”，a[i]);

printf("\n");

}本程序首先對數(shù)組a中的10個數(shù)從大到小排序并輸出排序結果。然后輸入要插入的整數(shù)n。再用一個for語句把n和數(shù)組元素逐個比較，當發(fā)現(xiàn)有n?>?a[i]?時，則由一個內循環(huán)把i以下各元素值順次后移一個單元。后移應從后向前進行(從a[9]?開始到a[i]?為止)。后移結束，跳出外循環(huán)。插入點為i，把n賦予a[i]?即可。如所有的元素均大于被插入數(shù)，則不進行后移工作。此時i=10，結果是把n賦予a[10]。最后一個循環(huán)輸出插入n后的數(shù)組各元素值。

程序運行時，輸入47。從結果中可以看出47已插入到54和28之間。 7.2二維數(shù)組

前面討論的一維數(shù)組可以表示數(shù)學中的向量、數(shù)據(jù)的有限序列等一維線性結構的數(shù)據(jù)，但在實際應用中還存在一些不是線性結構的數(shù)據(jù)關系。例如，數(shù)值計算中經常用到的矩陣，它有兩個維，不是線性結構，矩陣中的元素必須通過兩個下標指定，程序中如何描述這樣的數(shù)據(jù)呢？

C語言支持定義二維及更高維的數(shù)組，并且把二維數(shù)組看做數(shù)組類型為一維數(shù)組的數(shù)組，即數(shù)組中的所有數(shù)組元素又都是同類型同長度的一維數(shù)組。三維數(shù)組可看成是數(shù)組類型為二維數(shù)組的數(shù)組，依此類推，n維數(shù)組即為數(shù)組類型為n-1維數(shù)組的數(shù)組。本節(jié)只介紹二維數(shù)組，多維數(shù)組可由二維數(shù)組類推得到。7.2.1二維數(shù)組的定義

二維數(shù)組定義的一般形式為

類型說明符數(shù)組名[常量表達式1][常量表達式2]

其中：常量表達式1表示第一維下標的長度；常量表達式2表示第二維下標的長度。

例如：

inta[3][4];

說明了一個三行四列的數(shù)組，數(shù)組名為a，其下標變量的類型為整型。該數(shù)組的下標變量共有3?×?4個，即

a[0][0]，a[0][1]，a[0][2]，a[0][3]

a[1][0]，a[1][1]，a[1][2]，a[1][3]

a[2][0]，a[2][1]，a[2][2]，a[2][3]二維數(shù)組在邏輯上是二維的，即其下標在兩個方向上變化，下標變量在數(shù)組中的位置也處于一個平面之中，而不是像一維數(shù)組只是一個向量。但是，實際的硬件存儲器卻是連續(xù)編址的，也就是說存儲器單元是按一維線性排列的。

要在一維存儲器中存放二維數(shù)組，可有兩種方式：一種是按行排列，即放完一行之后順次放入第二行；另一種是按列排列，即放完一列之后再順次放入第二列。二維數(shù)組a的兩種存放形式如圖7-2所示。圖7-2二維數(shù)組a的兩種存放形式在C語言中，二維數(shù)組是按行排列的，即先存放a[0]?行，再存放a[1]?行，最后存放a[2]行。每行中的四個元素也是依次存放的。由于數(shù)組a說明為int類型，該類型占兩個字節(jié)的內存空間，所以每個元素均占2個字節(jié)，總的存儲空間為3?×?4?×?2個字節(jié)。

思考

如何根據(jù)數(shù)組名、數(shù)組類型、各下標值計算多維數(shù)組元素的存放地址？7.2.2二維數(shù)組的引用

二維數(shù)組的元素也稱為雙下標變量，其表示形式為

數(shù)組名[下標][下標]

其中：下標應為整型常量或整型表達式。

例如：

a[3][4]

表示a數(shù)組中有三行四列的元素。

同一維數(shù)組一樣，這里每一維的下標都必須小于該維的長度規(guī)定，否則就會出現(xiàn)數(shù)組越界，造成不可預知的后果。

就像前面用單重循環(huán)處理一維數(shù)組一樣，雙重循環(huán)是處理二維數(shù)組的理想選擇。

【例7.5】

一個學習小組有5個人，每個人有3門課程的考試成績，如表7-1所示。求各門課程的平均成績和所有課程的總平均成績?？稍O一個二維數(shù)組a[5][3]存放5個人3門課程的成績。再設一個一維數(shù)組v[3]存放所求得的各門課程的平均成績，設變量average為所有課程的總平均成績。

程序如下：

main()

{inti，j，s=0，average，v[3]，a[5][3];

printf(“inputscore\n”);

for(i=0;i<3;i++)

{

for(j=0;j<5;j++)

{

scanf("%d"，&a[j][i]);

s=s+a[j][i];}

v[i]=s/5;

s=0;

}

average=(v[0]+v[1]+v[2])/3;

printf("math:%d\nclanguage:%d\ndbase:%d\n"，v[0]，v[1]，v[2]);

printf("total:%d\n"，average);

}程序中首先用了一個雙重循環(huán)。在內循環(huán)中依次讀入某一門課程的各個學生的成績，并把這些成績累加起來，退出內循環(huán)后再把該累加成績除以5送入v[i]之中，這就是該門課程的平均成績。外循環(huán)共循環(huán)3次，分別求出3門課各自的平均成績并存放在v數(shù)組之中。退出外循環(huán)之后，把v[0]、v[1]、v[2]相加除以3即得到所有課程的總平均成績。最后按題意輸出成績。7.2.3二維數(shù)組的初始化

二維數(shù)組的初始化是指在數(shù)組定義時給各下標變量賦以初值。二維數(shù)組可按行分段賦值，也可按行連續(xù)賦值。

例如，對數(shù)組a[5][3]，按行分段賦值可寫為

inta[5][3]={{80，75，92}，{61，65，71}，{59，63，70}，{85，87，90}，{76，77，85}};

按行連續(xù)賦值可寫為

inta[5][3]={80，75，92，61，65，71，59，63，70，85，87，90，76，77，85};

這兩種賦初值的結果是完全相同的。對于二維數(shù)組初始化賦值還有以下說明：

(1)可以只對部分元素賦初值，未賦初值的元素自動取0值。

例如：

inta[3][3]={{1}，{2}，{3}};

是對每一行的第一列元素賦值，未賦值的元素取0值。賦值后各元素的值為

100

200

300

又如：

inta[3][3]={{0，1}，{0，0，2}，{3}};

賦值后的元素值為

010

002

300

(2)如果對全部元素賦初值，則第一維的長度可以不給出。

例如：

inta[3][3]={1，2，3，4，5，6，7，8，9};

可以寫為

inta[][3]={1，2，3，4，5，6，7，8，9};

【例7.6】請以矩陣的形式輸出矩陣A與矩陣B相加之和。

程序如下：

main()

{

inti，j;

inta[5][3]={{80，75，92}，{61，65，71}，{59，63，70}，{85，87，90}，{76，77，85}};

intb[5][3]={{1}，{0，1}，{0，0，1}};

for(i=0;i<3;i++)

{

for(j=0;j<5;j++)

printf(“%4d”，a[i][j]+b[i][j]);

printf(“\n”);

}

}7.2.4二維數(shù)組的分解

數(shù)組是一種構造類型的數(shù)據(jù)結構。二維數(shù)組可以看做是由一維數(shù)組的嵌套構成的。設一維數(shù)組的每個元素又都是一個數(shù)組，就組成了二維數(shù)組。當然，前提是各元素類型必須相同。根據(jù)這樣的分析，一個二維數(shù)組也可以分解為多個一維數(shù)組。C語言允許這種分解。

例如，二維數(shù)組a[3][4]可分解為三個一維數(shù)組，其數(shù)組名分別為a[0]、a[1]、a[2]。對這三個一維數(shù)組不需另作說明即可使用。這三個一維數(shù)組都有4個元素，如一維數(shù)組a[0]的元素為a[0][0]、a[0][1]、a[0][2]、a[0][3]。必須強調的是，a[0]、a[1]、a[2]不能當做數(shù)組元素(下標變量)使用，它們是數(shù)組名，不是一個單純的數(shù)組元素(下標變量)。

7.3數(shù)組與運算符

7.3.1數(shù)組與算術/賦值/邏輯運算符

因為數(shù)組中實際存儲數(shù)據(jù)的是各個數(shù)組元素，而數(shù)組名代表的只是數(shù)組首地址(一個地址常量)，所以，只有用數(shù)組元素作為算術運算和邏輯運算的操作數(shù)才是有意義的。用數(shù)組名作為操作數(shù)時，實際參與運算的是地址值而不是數(shù)據(jù)值。例如，將數(shù)組a和數(shù)組b中各元素對應相加的結果存放在數(shù)組c中，則不能簡單地

寫為

inta[10]，b[10]，c[10];

c=a+b;/*數(shù)組名中存放的是數(shù)組首地址，并且是常量，不允許修改*/

而應該用循環(huán)語句將各個元素分別相加才能得到想要的結果：

for(i=0;i<10;i++)

c[i]=a[i]+b[i]另外，對于賦值運算也是如此。我們可以利用賦值運算將變量a的值賦值給變量b，卻不能簡單地用賦值運算符完成數(shù)組之間的賦值操作。例如：

#defineN10

main()

{

inta[N]，b[N];

printf(“Enter%dnumbers:”，N);

for(i=0;i<N;i++)

scanf(“%d”，&a[i]);

b=a;

printf(“b:”);

for(i=0;i<N;i++)

printf(“%d”，b[i]);

printf("\n");

}編譯該程序，編譯器會給出錯誤信息，為什么呢？首先，C語言的賦值運算符不支持數(shù)組賦值。其次，前面我們講到數(shù)組名中存放的是數(shù)組首地址，它是常量，是不允許出現(xiàn)在賦值運算符的左側的。

那么要想完成數(shù)組間的復制應該如何做呢？最簡單的辦法就是利用循環(huán)對數(shù)組元素進行逐個復制。另一種方法是使用string.h中的內存復制函數(shù)memcpy。例如，將數(shù)組a復制給數(shù)組b，使用memcpy的寫法為

memcpy(b，a，sizeof(b));

一般地，對于大型數(shù)組，使用memcpy函數(shù)效率會比較高。7.3.2對數(shù)組使用sizeof運算符

前面講過對變量名使用sizeof運算符可以得到該變量占用內存的字節(jié)數(shù)，同樣對數(shù)組名使用sizeof運算符也可以確定數(shù)組的大小，即獲得數(shù)組占用內存的字節(jié)數(shù)。

例如，有

inta[10];

則sizeof(a)就等于20。

同理，也可以用sizeof運算符計算某數(shù)組元素的大小。例如：

sizeof(a[0])因此，數(shù)組的長度就可以表示為

sizeof(a)/sizeof(a[0])

將上式用于程序中，即使日后需要修改數(shù)組的長度，循環(huán)也不需要修改。例如：

for(i=0;i<sizeof(a)/sizeof(a[0]);i++)

a[i]=0;

通常在程序中定義靜態(tài)“求”數(shù)組元素個數(shù)的宏(帶參數(shù)的宏)：

#defineNUM(ax)sizeof(ax)/sizeof(ax[0])

7.4數(shù)?組?與?函?數(shù)

7.4.1數(shù)組元素作為函數(shù)實參

數(shù)組元素即下標變量本質上與普通變量并無區(qū)別，因此它作為函數(shù)實參使用與普通變量作為函數(shù)實參使用是完全相同的。此時，與之對應的形參必定是同類型(數(shù)組類型)的普通變量。在發(fā)生函數(shù)調用時，系統(tǒng)為形參分配存儲空間，使得作為實參的數(shù)組元素與形參變量占用不同的存儲空間，然后將實參數(shù)組元素的值傳送給形參變量，實現(xiàn)“單向值傳遞”，函數(shù)執(zhí)行過程中對形參值的修改不會影響實參數(shù)組元素的值。

【例7.7】判別一個整數(shù)數(shù)組中各元素的值，若大于0則輸出該值，若小于等于0則輸出0值。

程序如下：

voidnzp(intv)

{

if(v>0)

printf(“%d”，v);

else

printf(“%d”，0);

}

main()

{

inta[5]，i;

printf(“input5numbers\n”);

for(i=0;i<5;i++)

{

scanf(“%d”，&a[i]);

nzp(a[i]);

}

}本程序中首先定義一個無返回值函數(shù)nzp，并說明其形參v為整型變量。在函數(shù)體中根據(jù)v值輸出相應的結果。在main函數(shù)中用一個for語句輸入數(shù)組各元素，每輸入一個就以該元素作為實參調用一次nzp函數(shù)，即把a[i]的值傳送給形參v，供nzp函數(shù)使用。7.4.2數(shù)組名作為函數(shù)參數(shù)

我們知道數(shù)組名對應的是一個地址值—數(shù)組首地址，那么，數(shù)組名作為函數(shù)參數(shù)時該用什么樣的形參與之對應呢？函數(shù)調用時的參數(shù)傳遞又是如何規(guī)定的呢？

其實，無論是數(shù)組名作為函數(shù)實參還是數(shù)組元素作為函數(shù)實參，其函數(shù)間的數(shù)據(jù)傳遞都遵循“單向值傳遞”的原則。但由于數(shù)組名中存放的是一個地址值(數(shù)組首地址)，而數(shù)組元素中存放的是普通數(shù)據(jù)值，又使得兩者之間存在著本質的區(qū)別。第一，數(shù)組元素作為實參時，只要數(shù)組類型和函數(shù)形參變量的類型一致，那么作為下標變量的數(shù)組元素的類型也和函數(shù)形參變量的類型是一致的。因此，并不要求函數(shù)的形參也是下標變量。換句話說，對數(shù)組元素的處理是按普通變量對待的。數(shù)組名作為函數(shù)參數(shù)時，則要求形參和相對應的實參都必須是類型相同的數(shù)組，且有明確的數(shù)組說明。當形參和實參二者不一致時，即會發(fā)生錯誤。第二，普通變量或下標變量作為函數(shù)參數(shù)時，形參變量和實參變量占用由編譯系統(tǒng)分配的兩個不同的內存單元。在函數(shù)調用時發(fā)生的值傳送是把實參變量的值賦予形參變量。而數(shù)組名作為函數(shù)參數(shù)時，不是進行值的傳送，即不是把實參數(shù)組的每一個元素的值都賦予形參數(shù)組的各個元素，而僅僅是傳送一個地址值。這是因為實際上形參數(shù)組并不存在，編譯系統(tǒng)不為形參數(shù)組分配實際的內存。那么，數(shù)據(jù)的傳送是如何實現(xiàn)的呢?在前面我們曾介紹過，數(shù)組名中存放的是數(shù)組的首地址。因此，這里的“單向值傳遞”只是將實參數(shù)組名中的地址值傳送給形參數(shù)組名。這樣當形參數(shù)組名取得該首地址之后，就可以訪問實參數(shù)組了。實際上，形參數(shù)組和實參數(shù)組為同一數(shù)組，對應內存中的同一段空間。圖7-3說明了這種情形。圖中設a為實參數(shù)組，類型為整型。a占用以2000為首地址(起始地址)的一塊內存區(qū)。b為形參數(shù)組名。當發(fā)生函數(shù)調用時，進行地址傳送，把實參數(shù)組a的首地址傳送給形參數(shù)組名b，于是b也取得該地址2000。因此，a、b兩數(shù)組共同占用以2000為首地址的一段連續(xù)內存單元。從圖中還可以看出，a和b下標相同的元素實際上也占用相同的兩個內存單元(整型數(shù)組每個元素占兩個字節(jié))。例如，a[0]?和b[0]?都占用2000和2001單元，當然a[0]?等于b[0]。依此類推，則有a[i]等于b[i]。圖7-3數(shù)組名作為函數(shù)參數(shù)

【例7.8】多項式求值。設數(shù)組p中保存著多項式anxn+an-1xn-1+…+a1x+a0的各項系數(shù)，元素p[i]存放系數(shù)ai。要求寫一個函數(shù)求出數(shù)組p表示的多項式在某個指定點x的值。

有多種方法可以實現(xiàn)多項式求值，下面介紹最快速的秦九韶多項式算法。根據(jù)數(shù)學知識，任何多項式均可以變換為下面的規(guī)范形式：按照這個公式，求值的循環(huán)可以寫為

for(sum=0.0，i=n-1;i>=0;i--)

sum=sum*x+p[i];

完整的程序如下：

#include“stdio.h”

#defineN6

main()

{

doublef(doublep[]，doublex);

doublex,p[N]={2.3,1.4,5.2,6.7,8.4,1.3};

printf(“pleaseinputx:”);

scanf("%lf",&x);

printf(“\nf(%lf)=%lf\n”,x,f(p，x));

}

doublef(doubleq[]，doublex)

{

doublesum;

inti;

for(sum=0.0，i=N-1;i>=0;i--)

sum=sum*x+q[i];

returnsum;

}如果在上述程序中的函數(shù)f中加入修改數(shù)組q中元素的語句，此時在主函數(shù)中輸出數(shù)組p時，其相應的數(shù)組元素也會發(fā)生改變，這就說明了實參數(shù)組p與形參數(shù)組q是共用存儲空間的。讀者可自行測試。

第三，前面已經討論過，變量作為函數(shù)參數(shù)時，所進行的值傳送是單向的，即只能從實參傳向形參，不能從形參傳回實參。形參的初值和實參相同，而形參的值發(fā)生改變后，實參并不變化，兩者的終值是不同的。而當數(shù)組名作為函數(shù)參數(shù)時，情況則不同。由于實際上形參和實參為同一數(shù)組，因此當形參數(shù)組發(fā)生變化時，實參數(shù)組也隨之變化。當然這種情況不能理解為發(fā)生了“雙向”的值傳遞。但從實際情況來看，調用函數(shù)之后，實參數(shù)組的值將隨著形參數(shù)組值的變化而變化。

【例7.9】題目同例7.7，改用數(shù)組名作為函數(shù)參數(shù)。

程序如下：

voidnzp(inta[5])

{

inti;

printf(“\nvaluesofarrayaare:\n”);

for(i=0;i<5;i++)

{

if(a[i]<0)a[i]=0;

printf(“%d”，a[i]);

}

}

main()

{

intb[5]，i;

printf(“\ninput5numbers:\n”);

for(i=0;i<5;i++)

scanf(“%d”，&b[i]);

printf(“initialvaluesofarraybare:\n”);

for(i=0;i<5;i++)

printf(“%d”，b[i]);

nzp(b);

printf(“\nlastvaluesofarraybare:\n”);

for(i=0;i<5;i++)

printf("%d"，b[i]);

}本程序中函數(shù)nzp的形參為整型數(shù)組a，長度為5。主函數(shù)中實參數(shù)組b也為整型，長度也為5。在主函數(shù)中首先輸入數(shù)組b的值，然后輸出數(shù)組b的初始值。之后以數(shù)組名b為實參調用nzp函數(shù)。在nzp中，按要求把負值單元清0，并輸出形參數(shù)組a的值。返回主函數(shù)之后，再次輸出數(shù)組b的值。從運行結果可以看出，數(shù)組b的初值和終值是不同的，數(shù)組b的終值和數(shù)組a是相同的。這說明實參和形參為同一數(shù)組，它們的值同時得以改變。用數(shù)組名作為函數(shù)參數(shù)時還應注意以下幾點：

(1)形參數(shù)組和實參數(shù)組的類型必須一致，否則將引起錯誤。

(2)形參數(shù)組和實參數(shù)組的長度可以不相同，因為在調用時，只傳送首地址而不檢查形參數(shù)組的長度。當形參數(shù)組的長度與實參數(shù)組不一致時，雖不會出現(xiàn)語法錯誤(編譯能通過)，但程序執(zhí)行結果可能與實際不符(如例7.10所示)，這是應予以注意的。

(3)在函數(shù)形參表中，允許不給出形參數(shù)組的長度，或用一個變量來表示數(shù)組元素的個數(shù)。例如，可以寫為

voidnzp(inta[])

或寫為

voidnzp(inta[]，intn)

其中形參數(shù)組a沒有給出長度，而由n值動態(tài)地表示數(shù)組的長度。n的值由主調函數(shù)的實參進行傳送，如例7.11。

(4)多維數(shù)組也可以作為函數(shù)的參數(shù)。在函數(shù)定義時對形參數(shù)組可以指定每一維的長度，也可省去第一維的長度。因此，以下寫法都是合法的：

intMA(inta[3][10])

或

intMA(inta[][10])

【例7.10】把例7.9修改如下：

voidnzp(inta[8])

{

inti;

printf(“\nvaluesofarrayaare:\n”);

for(i=0;i<8;i++)

{

if(a[i]<0)a[i]=0;

printf(“%d”，a[i]);

}

}

main()

{

intb[5]，i;

printf(“\ninput5numbers:\n”);

for(i=0;i<5;i++)

scanf(“%d”，&b[i]);

printf(“initialvaluesofarraybare:\n”);

for(i=0;i<5;i++)

printf(“%d”，b[i]);

nzp(b);

printf(“\nlastvaluesofarraybare:\n”);

for(i=0;i<5;i++)

printf("%d"，b[i]);

}本程序與例7.9的程序相比，nzp函數(shù)的形參數(shù)組長度改為8，函數(shù)體中，for語句的循環(huán)條件也改為i?<?8。因此，形參數(shù)組a和實參數(shù)組b的長度不一致。編譯能夠通過，但從結果來看，數(shù)組a的元素a[5]、a[6]、a[7]?顯然是無意義的。

【例7.11】把例7.9修改如下：

voidnzp(inta[]，intn)

{

inti;

printf(“\nvaluesofarrayaare:\n”);

for(i=0;i<n;i++)

{

if(a[i]<0)a[i]=0;

printf(“%d”，a[i]);

}

}

main()

{

intb[5]，i;

printf(“\ninput5numbers:\n”);

for(i=0;i<5;i++)

scanf(“%d”，&b[i]);

printf(“initialvaluesofarraybare:\n”);

for(i=0;i<5;i++)

printf(“%d”，b[i]);

nzp(b，5);

printf(“\nlastvaluesofarraybare:\n”);

for(i=0;i<5;i++)

printf("%d"，b[i]);

} 7.5字符數(shù)組與字符串

字符數(shù)組就是數(shù)組類型為字符類型的數(shù)組，用于保存一系列字符。由于人們經常用C語言編寫處理字符序列或各種文本的程序，因此C語言為處理字符數(shù)組提供了專門的支持。

字符串是典型的非數(shù)值對象，其存儲模式是以字符數(shù)組作為存儲空間，結尾加結束標志符?'\0'。對字符串的基本操作主要通過標準庫提供的函數(shù)來實現(xiàn)。7.5.1字符數(shù)組的基本語法知識

1．字符數(shù)組的定義

字符數(shù)組的定義形式與前面介紹的數(shù)值數(shù)組相同。

例如：

charc[10];

由于字符型和整型通用，也可以定義為intc[10]，但這時每個數(shù)組元素占2個字節(jié)的內存單元。

字符數(shù)組也可以是二維或多維數(shù)組。

例如：

charc[5][10];

即為二維字符數(shù)組。

2．字符數(shù)組的初始化

字符數(shù)組也允許在定義時作初始化賦值。

例如：

charc[10]={‘C’，‘’，‘p’，‘r’，‘o’，‘g’，‘r’，‘a’，‘m’};

賦值后各元素的值為

數(shù)組c c[0]的值為‘C’

c[1]的值為‘’

c[2]的值為‘p’

c[3]的值為‘r’

c[4]的值為‘o’

c[5]的值為‘g’

c[6]的值為‘r’

c[7]的值為‘a’

c[8]的值為'm'其中c[9]?未賦值，系統(tǒng)自動賦予0值。

當對全體元素賦初值時也可以省去長度說明。

例如：

charc[]={'C'，''，'p'，'r'，'o'，'g'，'r'，'a'，'m'};

這時數(shù)組c的長度自動定為9。

3．字符數(shù)組的引用

字符數(shù)組的引用與數(shù)值數(shù)組的引用完全一致。

【例7.12】

二維字符數(shù)組的輸出。

程序如下：

main()

{

inti，j;

chara[][5]={{‘B’，‘A’，‘S’，‘I’，‘C’，}，{‘d’，‘B’，‘A’，‘S’，‘E’}};

for(i=0;i<=1;i++)

{

for(j=0;j<=4;j++)

printf(“%c”，a[i][j]);

printf(“\n”);

}

}7.5.2字符串和字符串結束標志

在Ｃ語言中沒有專門的字符串變量，通常用一個字符數(shù)組來存放一個字符串。前面介紹字符串常量時，已說明字符串總是以?'\0'?作為串的結束符。因此當把一個字符串存入一個數(shù)組時，也把結束符?'\0'?存入數(shù)組，并以此作為該字符串是否結束的標志。有了?'\0'?標志后，就不必再用字符數(shù)組的長度來判斷字符串的長度了。

C語言允許用字符串的方式對數(shù)組作初始化賦值。

例如：

charc[]={‘C’，‘’，‘p’，‘r’，‘o’，‘g’，‘r’，‘a’，‘m’};

可寫為

charc[]={“Cprogram”};

或去掉?{}?寫為

charc[]="Cprogram";

用字符串方式賦值比用字符逐個賦值要多占一個字節(jié)，用于存放字符串結束標志?'\0'。上面的數(shù)組c在內存中的實際存放情況為‘\0’?是由C編譯系統(tǒng)自動加上的。由于采用了?‘\0’?標志，所以在用字符串賦初值時一般無須指定數(shù)組的長度，而由系統(tǒng)自行處理。

思考

能否直接將一個字符串賦值給一個字符數(shù)組？為什么？

例如：

charc[10];

c="Cprogram";

根據(jù)前面的知識，我們知道字符串常量也是以字符數(shù)組的方式存儲的，編譯器把它看做是一個地址值(存放字符串的內存單元的首地址)。雖然數(shù)組名中存放的也是地址值，但因為它是常量，所以不能通過賦值的方式改變它的值。因此，上述語句是非法的。7.5.3字符數(shù)組的輸入/輸出

在采用字符串方式初始化賦值后，字符數(shù)組的輸入/輸出將變得簡單方便。

除了上述用字符串賦初值的辦法外，還可用scanf函數(shù)和printf函數(shù)一次性輸入/輸出一個字符數(shù)組中的字符串，而不必使用循環(huán)語句逐個地輸入/輸出每個字符。

【例7.13】以?“%s”?格式輸出字符串。

程序如下：

main()

{

charc[]=“BASIC\ndBASE”;

printf("%s\n"，c);

}

注意

在本例的printf函數(shù)中，使用的格式控制符為?“%s”，表示輸出的是一個字符串，而在輸出表列中給出數(shù)組名即可。不能寫為

printf(“%s”，c[]);

【例7.14】以?“%s”?格式輸入、輸出字符數(shù)組。

程序如下：

main()

{

charst[15];

printf(“inputstring:\n”);

scanf(“%s”，st);

printf("%s\n"，st);

}本例中由于定義數(shù)組長度為15，因此輸入的字符串長度必須小于15，以留出一個字節(jié)用于存放字符串結束標志?'\0'。應該說明的是，對一個字符數(shù)組，如果不作初始化賦值，則必須說明數(shù)組長度。還應該特別注意的是，當用scanf函數(shù)輸入字符串時，字符串中不能含有空格，否則將以空格作為串的結束符。

例如，當輸入的字符串中含有空格時，運行情況為

inputstring:

thisisabook

輸出為

this

【例7.15】以?“%s”?格式輸入、輸出字符串時對“空格”應作特殊處理。

程序如下：

main()

{

charst1[6]，st2[6]，st3[6]，st4[6];

printf(“inputstring:\n”);

scanf(“%s%s%s%s”，st1，st2，st3，st4);

printf("%s%s%s%s\n"，st1，st2，st3，st4);

}本程序分別設了四個數(shù)組，輸入的一行字符以空格分段分別裝入四個數(shù)組。然后分別輸出這四個數(shù)組中的字符串。

在前面介紹過，scanf的各輸入項必須以地址方式出現(xiàn)，如&a、&b等，但在例7.15中卻是以數(shù)組名方式出現(xiàn)的，這是為什么呢?這是由于，在Ｃ語言中規(guī)定，數(shù)組名就代表了該數(shù)組的首地址，整個數(shù)組是以首地址開頭的一塊連續(xù)的內存單元。例如，有字符數(shù)組charc[10]，在內存中可表示如下：設數(shù)組c的首地址為2000，也就是說c[0]?單元地址為2000，則數(shù)組名c就代表這個首地址，因此在c前面不能再加地址運算符&。如果寫做“scanf("%s"，&c);”則是錯誤的。在執(zhí)行函數(shù)printf("%s"，c)時，按數(shù)組名c找到首地址，然后逐個輸出數(shù)組中各個字符直到遇到字符串終止標志?'\0'?為止。7.5.4字符串處理函數(shù)

Ｃ語言提供了豐富的字符串處理函數(shù)，大致可分為字符串的輸入、輸出、合并、修改、比較、轉換、復制、搜索幾類。使用這些函數(shù)可大大減輕編程的負擔。要使用字符串函數(shù)的輸入/輸出，在程序中應包含頭文件?"stdio.h"，使用其他字符串函數(shù)則應包含頭文件?"string.h"。

下面介紹幾個最常用的字符串函數(shù)。

1．字符串輸出函數(shù)puts

格式：

puts(字符數(shù)組名)

功能：把字符數(shù)組中的字符串輸出到顯示器，即在屏幕上顯示該字符串。

【例7.16】puts函數(shù)的使用。

程序如下：

#include“stdio.h”

main()

{

charc[]=“BASIC\ndBASE”;

puts(c);

}

從程序中可以看出，puts函數(shù)中可以使用轉義字符，因此輸出結果成為兩行。puts函數(shù)完全可以由printf函數(shù)取代。當需要按一定格式輸出時，通常使用printf函數(shù)。

2．字符串輸入函數(shù)gets

格式：

gets(字符數(shù)組名)

功能：從標準輸入設備鍵盤上輸入一個字符串。

本函數(shù)得到一個函數(shù)值，即為該字符數(shù)組的首地址。

【例7.17】gets函數(shù)的使用。

程序如下：

#include“stdio.h”

main()

{

charst[15];

printf(“inputstring:\n”);

gets(st);

puts(st);

}

3．字符串連接函數(shù)strcat

格式：

strcat(字符數(shù)組名1，字符數(shù)組名2)

功能：把字符數(shù)組2中的字符串連接到字符數(shù)組1中字符串的后面，并刪去字符串1后的串標志?'\0'。本函數(shù)返回值是字符數(shù)組1的首地址。

【例7.18】strcat函數(shù)的使用。

程序如下：

#include“string.h”

main()

{

staticcharst1[30]=“Mynameis”;

intst2[10];

printf(“inputyourname:\n”);

gets(st2);

strcat(st1，st2);

puts(st1);

}

4．字符串拷貝函數(shù)strcpy

格式：

strcpy(字符數(shù)組名1，字符數(shù)組名2)

功能：把字符數(shù)組2中的字符串拷貝到字符數(shù)組1中，串結束標志?'\0'?也一同拷貝。字符數(shù)名2也可以是一個字符串常量。這時相當于把一個字符串賦予一個字符數(shù)組。

【例7.19】strcpy函數(shù)的使用。

程序如下：

#include“string.h”

main()

{

charst1[15]，st2[]=“CLanguage”;

strcpy(st1，st2);

puts(st1);printf("\n");

}

本函數(shù)要求字符數(shù)組1有足夠的長度，否則不能全部裝入所拷貝的字符串。

5．字符串比較函數(shù)strcmp

格式：

strcmp(字符數(shù)組名1，字符數(shù)組名2)

功能：按照ASCII碼順序比較兩個數(shù)組中的字符串，并由函數(shù)返回值返回比較結果。

字符串1＝字符串2，返回值＝0；

字符串2>字符串2，返回值>0；

字符串1<字符串2，返回值<0。

本函數(shù)也可用于比較兩個字符串常量，或比較數(shù)組和字符串常量。

【例7.20】strcmp函數(shù)的使用。

程序如下：

#include“string.h”

main()

{

intk;

staticcharst1[15]，st2[]=“CLanguage”;

printf(“inputastring:\n”);

gets(st1);

k=strcmp(st1，st2);

if(k==0)printf(“st1=st2\n”);

if(k>0)printf(“st1>st2\n”);

if(k<0)printf("st1<st2\n");

}本程序中把輸入的字符串和數(shù)組st2中的串進行比較，比較結果返回到k中，根據(jù)k值再輸出結果提示串。當輸入為dBASE時，由ASCII碼可知?"dBASE"?大于?"CLanguage"，故k?>?0，輸出結果為?"st1>st2"。

6．測字符串長度函數(shù)strlen

格式：

strlen(字符數(shù)組名)

功能：測字符串的實際長度(不含字符串結束標志?'\0')并將其作為函數(shù)返回值。

【例7.21】strlen函數(shù)的使用。

程序如下：

#include“string.h”

main()

{

intk;

staticcharst[]=“CLanguage”;

k=strlen(st);

printf("Thelengthofthestringis%d\n"，k);

}

7.6數(shù)組應用實例

7.6.1數(shù)組中的查找算法

查找一般有幾種情況，如查找特定元素、查找最大元素、查找最小元素等。而且一般情況下的查找都需要兩種結果，即是否存在該元素及該元素在什么位置。

數(shù)組的查找是指根據(jù)給定的某個值，在數(shù)組中查找一個等于給定值的數(shù)組元素。若數(shù)組中存在一個這樣的數(shù)組元素，則稱查找是成功的；若數(shù)組中不存在這樣一個數(shù)組元素，則稱查找不成功。

1．順序查找

順序查找算法是最普通的查找算法，其實現(xiàn)最為簡單，也相當實用。在我們不知道待查找的數(shù)組是否有序的情況下，此算法很容易使用。

順序查找的基本思想非常簡單，就是依次將數(shù)組的第一個元素到數(shù)組的最后一個元素與給定值進行比較，最終得出查找成功或查找不成功的結論。

查找一個數(shù)組中的特定元素，返回該元素的位置，設定返回?-1時表示不存在。用函數(shù)實現(xiàn)的順序查找算法如下：

intsearch(inta[]，intkey，intn)

{

inti;

for(i=0;i<n;i++) /*查找范圍0～n-1*/

if(a[i]==key) /*查找元素key?*/

returni;

/*查找成功*/

return-1;

/*查找失敗*/

}

2．折半查找

折半查找的算法思想是將數(shù)列按有序化(遞增或遞減)排列，查找過程中采用跳躍式方式查找，即先以有序數(shù)列的中點位置為比較對象，如果要找的元素值小于該中點元素，則將待查序列縮小為左半部分，否則為右半部分。通過一次比較，將查找區(qū)間縮小一半。折半查找是一種高效的查找方法，它可以明顯減少比較次數(shù)，提高查找效率。但是，折半查找的先決條件是查找表中的數(shù)據(jù)元素必須有序。算法描述如下：

(1)確定整個查找區(qū)間的中間位置：mid=(left?+?right)/2。

(2)用待查關鍵字值與中間位置的關鍵字值進行比較。若相等，則查找成功；若前者大于后者，則在后(右)半個區(qū)域繼續(xù)進行折半查找；若前者小于后者，則在前(左)半個區(qū)域繼續(xù)進行折半查找。

(3)對確定的縮小區(qū)域再按折半公式重復上述步驟。最后，得到結果：查找成功或查找失敗。

查找一個數(shù)組中的特定元素，返回該元素的位置，設定返回?-1時表示不存在。用函數(shù)實現(xiàn)的折半查找算法如下：

intsearch_Bin(inta[]，intkey，intn)

{

intlow，high，mid;

low=0;high=n-1; /*置區(qū)間初值*/

while(low<=high){

mid=(low+high)/2;

if(key==a[mid])returnmid; /*待查元素位置*/

elseif(key<a[mid])high=mid-1;

elselow=mid+1; /*繼續(xù)在后半區(qū)間進行查找*/

}

return-1;/*不存在待查元素*/

}7.6.2數(shù)組中的排序算法

數(shù)組排序是指將數(shù)組中的各個元素按照某種規(guī)則(從大到小、從小到大等)重新排列。常見的排序算法包括交換排序、選擇排序、插入排序和歸并排序，下面僅對前兩種算法作一介紹。

1．交換排序

交換排序包含冒泡排序(bubblesort)和快速排序(quicksort)。

1)冒泡排序

冒泡排序的基本思想是：依次比較相鄰的兩個數(shù)，將小數(shù)放在前面，大數(shù)放在后面。即在第一趟：首先比較第1個數(shù)和第2個數(shù)，將小數(shù)放前，大數(shù)放后；然后比較第2個數(shù)和第3個數(shù)，將小數(shù)放前，大數(shù)放后；如此繼續(xù)，直至比較最后兩個數(shù)，將小數(shù)放前，大數(shù)放后。至此第一趟結束，將最大的數(shù)放到了最后。在第二趟：仍從第一對數(shù)開始比較(因為可能由于第2個數(shù)和第3個數(shù)的交換，使得第1個數(shù)不再小于第2個數(shù))，將小數(shù)放前，大數(shù)放后，一直比較到倒數(shù)第二個數(shù)(倒數(shù)第一的位置上已經是最大的)，第二趟結束，在倒數(shù)第二的位置上得到一個新的最大數(shù)(其實在整個數(shù)列中是第二大的數(shù))。如此下去，重復以上過程，直至最終完成排序。由于在排序過程中總是小數(shù)往前放，大數(shù)往后放，相當于氣泡往上升，所以稱做冒泡排序。完整程序如下：

voidbubble_Sort(inta[]，intn)

{

intw;

i=n-1;

while(i>1){

lastExchangeIndex=1;

for(j=0;j<i;j++)

if(a[j+1]<a[j])

{/*逆序*/

w=a[j];a[j]=a[j+1];a[j+1]=w; /*交換*/

lastExchangeIndex=j;

}

i=lastExchangeIndex;

/*無序序列的最后記錄位置*/

}

}

2)快速排序

快速排序的基本思想是：選擇數(shù)組元素e作為“分割元素”，然后重新排列數(shù)組，使得位于分割元素e之前的元素都是小于或等于e的，而位于分割元素e之后的元素都是大于或等于e的。然后，再分別對前半部分的數(shù)組和后半部分的數(shù)組進行快速排序。顯然，快速排序的過程具有結構自相似性，用遞歸函數(shù)實現(xiàn)最為簡單。首先定義函數(shù)split實現(xiàn)第一步中的分割任務?？稍诔绦蛑惺褂脙蓚€標記：low和high。開始，low指向數(shù)組中的第一個元素，而high指向末尾元素。首先把第一個元素(分割元素)復制給一個臨時存儲單元，從而在數(shù)組中留出一個“空位”。接下來，從右向左移動high，直到high指向小于分割元素的數(shù)時停止。然后把這個數(shù)復制給low指向的空位，這將產生一個新的空位(high指向的)。現(xiàn)在從左向右移動low，尋找大于分割元素的數(shù)。在找到時，把這個找到的數(shù)復制給high指向的空位。重復執(zhí)行此過程，交替操作low和high，直到兩者在數(shù)組中間的某處相遇時停止。此時，兩個標記都指向空位，只要把分割元素復制給空位就可以了。然后，定義名為quicksort的遞歸函數(shù)，調用split函數(shù)進行快速排序。完整程序如下：

#include<stdio.h>

#defineN10

intmain(void)

{

voidquicksort(inta[]，intlow，inthigh);

inta[N]，i;

printf(“Enter%dnumberstobesorted:”，N); /*輸入*/

for(i=0;i<N;i++)

scanf(“%d”，&a[i]);

quicksort(a，0，N-1);

/*快速排序*/

printf(“Insortedorder:”); /*輸出*/

for(i=0;i<N;i++)

printf("%d"，a[i]);

printf(“\n”);

return0;

}

voidquicksort(inta[]，intlow，inthigh)

{

intmiddle;

intsplit(inta[]，intlow，inthigh);

if(low>=high)return; /*結束*/

middle=split(a，low，high); /*分割*/

quicksort(a，low，middle-1); /*遞歸*/

quicksort(a，middle+1，high);

}

intsplit(inta[]，intlow，inthigh)

{

intpart_element=a[low];

for(;;){

while(low<high&&part_element<=a[high])

high--;

if(low>=high)break;

a[low++]=a[high];

while(low<high&&a[low]<=part_element)

low++;

if(low>=high)break;

a[high--]=a[low];

}

a[high]=part_element;

returnhigh;

}雖然快速排序算法是目前效率最高的一種排序算法，但還可以從以下三個方面考慮對其進行改進：

(1)改進分割算法。不選擇數(shù)組中的第一個元素作為分割元素，而是取第一個元素、中間元素和最后一個元素的中間值作為分割元素。分割過程本身也可以加速，特別是在兩個while循環(huán)中要避免測試low?<?high。

(2)采用不同的方法進行小數(shù)組排序。不再遞歸地使用快速排序法對所有分割后的小數(shù)組進行排序，針對小數(shù)組(比方說，擁有的元素數(shù)量少于25個的數(shù)組)更好的方法是采用較為簡單的方法(如插入排序)。

(3)使得快速排序非遞歸。雖然快速排序本質上是遞歸算法，并且遞歸格式的快速排序是最容易理解的，但是實際上若去掉遞歸會更高效。

2．選擇排序

選擇排序包括簡單選擇排序和堆排序(heapsort)，這里只討論簡單選擇排序。

簡單選擇排序的基本思想是：每一趟從待排序的數(shù)據(jù)元素中選出最小(或最大)的一個元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。選擇排序是不穩(wěn)定的排序方法

【例7.22】輸入10個整數(shù)并用選擇排序法將它們按從大到小的順序排序。

程序如下：

main()

{

inti，j，p，q，s，a[10];

printf(“\ninput10numbers:\n”);

for(i=0;i<10;i++)

scanf(“%d”，&a[i]);

for(i=0;i<10;i++){

p=i;q=a[i];

for(j=i+1;j<10;j++)

if(q<a[j]){p=j;q=a[j];}

if(i!=p){

s=a[i];

a[i]=a[p];

a[p]=s;

}

printf(