第四章數組及其應用
迄今為止，我們使用的都是屬於基本類型（整形、字符型、實型）的數據，C語言還提供了構造類型的數據，它們有：數組類型、結構體類型、共用體類型。構造類型數據是由基本類型數據按照一定的規則組成的，因此有的書又稱它們為“導出類型”。
本章將隻介紹數組。數組是具有相同數據類型且按一定次序排列的一組變量的集合體，構成一個數組的這些變量稱為數組元素。數組有一個統一的名字叫數組名，每個數組元素並沒有另外的名字，它可通過數組名及其在數組中的位置（叫下標）來確定。即數組元素是用數組名後跟用方括號（［］）括住的下標來表示。例如name［15］、list［5］［10］等。數組按下標個數分類，有一維、二維和三維數組等，二維以上數組統稱為多維數組。
4.1 一維數組
4.1.1 一維數組的定義
一維數組是數組名後隻有一對方括號的數組，其定義方式為：
數據類型 數組名［元素個數］；
例如：
char str［50］
此語句定義了一個由50個元素組成的一維數組，數組名為str，這50個元素分別為str［0］、str［1］、str［2］、str［3］…str［49］，每個元素都是字符型變量。關於數組的定義，應注意如下幾點：
（1）數組名後用方括號括住數組元素的個數，不能使用圓括號。
（2）元素個數可以是整型常量，也可以是整型常量表達式，但決不能含有變量，因為此表達式的值是在編譯時計算出來的，而編譯時係統並不能確定變量的取值。
（3）數組元素個數必須大於或等於1。
（4）數組元素的下標是從0開始編號的，因此，對於定義：float a［8］，其第一個元素是a［0］而不是a［1］，最後一個元素是a［7］，而不是a［8］。
根據上述要點可以判斷，下麵四個定義是非法的：
int size1，size2；
folat height［size1］； （使用變量做下標是錯誤的）
float width［size1+size2+1］； （用含變量的表達式做下標是錯誤的）
int number［-8］ （使用負數做下標是錯誤的）
int m（8） （數組名後麵用（）是錯誤的）
而下麵的數組定義是合法的：
# define STRSIZE 50
char string［STRSIZE］；
int m［15* STRSIZE］；
float x［3*32+1］；
4.1.2 一維數組的存儲形式
一維數組在內存中存儲時，按下標遞增的次序連接存放。對於int a［15］數組名a或a［0］是數組存儲區域的首地址，即數組第一個元素存放的地址。其中＆是地址運算符，它表示取a［0］的地址。因此，數組名是一個地址常量，不能對其進行賦值和進行＆運算。
4.1.3 一維數組的引用
與變量類似，任何一個數組都應先定義或說明，然後再引用。在C語言中不能對數組整體進行操作，例如不能對整個數組進行賦值或其他各種運算。隻能對數組元素進行操作。數組的引用形式為：
數組名［下標］
其中下標既可以是整型常量表達式，也可以是含有變量的整型表達式。例如，在例中的x［k+2］。
# define SIZE 4
# include < stdio.h >
main（）
{
float x[SIZE],sum= =0.0;
int k =0;
scanf（" % d % d % d",x）; / * 對數組進行整體輸入是錯誤的 * /
scanf（" % d",& x[3]）; / * 正確的輸入方式 * /
while（k sum + = x[k]; / * 正確的引用方式 * /
k + +;
}
k=0
printf（" % d % d % d % d \ n",x）; / * 對數組進行整體輸出是錯誤的 * /
printf（" % d % d \ n",x[k+1],x[k+2]）; / * 正確的引用方式 * /
printf（" % d \ n",x[SIZE]）; / * 下標越界 * /
}
在C語言中，編譯和執行程序時，係統並不自動檢查數組下標是否越界，因此可能訪問到數組所占的內存空間以外的存儲單元，而這種訪問往往是十分危險的，因此程序員要特點注意下標越界的問題。
4.1.4 一維數組的初始化
初始化就是給數組元素賦初始值，有如下兩種初始化方法：
1．用賦值語句初始化
用賦值語句初始化是在程序執行時實現的。
2．在數組定義時初始化
這種初始化是在編譯時進行的。其一般形式如下：
數據類型 數組名［數組元素個數］＝｛值1，值2，…值n｝；
對上述形式說明如下：
?花括號中的值是初始值，用逗號分開。例如：
int m［3］=｛0，1，2｝；
那麼各數組元素的初始值為：m［0］＝0，m［1］＝1，m［2］＝2。
?如果花括號中值的個數少於數組元素的個數，則多餘的數組元素初始化為0。例如：
int m［3］=｛0，1｝；
則各數組元素的初始值為：m［0］＝0，m［1］＝1，m［2］＝0。
?可對數組中的部分元素賦值，這時對不賦值的數組元素可在括號中缺少相應的值，但逗號不能省略，而缺省值視為0。例如：
int m［3］=｛0， ，1｝；
此時各數組元素的初始值為：m［0］＝1，m［1］＝0，m［2］＝1。
?在數組定義中，可缺省方括號（［］）中的元素個數，而用花括號中初始值的個數來決定數組元素個數。例如：
int m［］=｛0，1，2｝；
相當於：
int m［3］=｛0，1，2｝；
?對於靜態或全局類型的數組，如果不在定義顯示初始化，則多數編譯係統都將其初始化為0。
4.1.5 一維數組的應用舉例
【例4-1】有一遞推數列，滿足：f（0）＝0，f（1）＝1，f（2）＝2，f（n+1）=f（n）+2f（n-1）f（n-2）（n>=2）。使用數組編寫程序，順序打印出f（0）到f（10）的值。
分析：可以定義一個整型數組，用於存放f（0）到f（10）這11個整數。先將f（0）、f（1）、f（2）的值直接賦給數組的前三個元素，然後建立一個循環，每次取出數組中的三個元素（最後一個元素必須是上一次進行循環體時剛計算出來的），通過遞推公式求出下一項的值並存入數組中，直到11項都被計算出來為止。
程序如下：
# include < stdio.h >
main（）
{
int f[11],k;
f[0]=0,f[1]=1,f[2]=2; / * 前三項賦初值 * /
for[k=3;k <11;k + +）
f[k]=f[k-1]+ 2 * f[k-2] * f[k-3]; / * 遞推求解每一項的值 * /
for（k=0;k<11;k+ +）
printf（" % d,",f[k]）;
}
從上例中可以看出，使用數組的方便之處之一是通過下標存取數組元素正好同循環控製變量及其表達式相匹配，因此，數組+循環就可以簡單地實現順序地、逆序地或跳躍地對大量數據進行連續處理，這是僅使用基本數據類型無法辦到的。
【例4-2】請用戶輸入一個含有12個浮點數的一維數組，請分別計算出數組中所有的正數的和以及所有的負數的和。
分析：顯然應該建立一個循環，從頭到尾地將整個數組搜索一遍，同時將其中所有的正數和負數分別累加起來以求得結果。程序如下：
# include < stdio.h >
main（）
{float data[12]; / * 存放浮點數的一維數組 * /
float result1=0.0,result2=0.0; / * 將要用於分別存放正數和，負數和 * /
int i;
printf（"please input 12 float numbers: \ n"）;
for（i=0;i<12;i++）
scanf（" % f",& data[i]）; / * 逐一輸入數據 * /
for（i=0;i<12;i+ +）
{ if（data[i]>0.0）
result 1 + =data[i]; / * 累加正數 * /
else
result2 + =data[i]; / * 累加負數 * /
}
printf（" the sum of all the positive numbers is % .3f \ n",result1）;
printf（" the sum of all the positive numbers is % .3f \ n",result2）;
}
【例4-3】使用直接插入法對12個整數進行排序（按從小到大的順序排列）。
直接插入排序的算法描述如下：
比較待排序數組中前兩個數的大小，按要求的順序排列好；將第三個數加入到由前兩個數組成的有序子序列中，保證此三個數的排列依然保持所要求的順序；以此類推，當前N個數已按從小到大的順序排好後，將第N+1個數依次同前麵的各數相比較，直到找到一個合適的位置將其插入，使前N+1個數保持從小到大的順序排列：重複上述過程，直到整個數組中的所有元素都被處理過為止。
程序如下：
# include < stdio.h >
main（）
{
int array[12],i,j;
printf（"input 12 integers: \ n"）;
for（i =0;i<12;i+ +）
scanf（" % d",& array[i]）; / * 逐一輸入數據 * /
for（i=0;i<12;i+ +） / * 從第二個數開始，逐一將當前數據插入到此數之
前的數據序列中，所以，當前數以前的數據序列總是有序 * /
{ int temp =array[i];
for（j =i-1;j > =0;j - -） / * 逐一搜索當前數以前的有序數據序列 * /
{if（array[j]>temp） / * 未達到插入點，則將原序列中的數據依次後移 * /
{if（array[j+1]=array[j];
else
{array[j+1]=temp;
break;
}
}
if（j= = -1） / * 前序列中的第一個數都比此數小，則插入到第一的位置 * /
array[0]=temp;
}
for（i=0;i<12;i+ +）
printf（"% d,",array[i]）;
}
【例4-4】用數組來處理求Fibonacci數列問題。
程序如下：
main（）
{
int i;
static int f[20]={1,1};
for（i=2;i<20;i++）
f[i]=f[i-2]+f[i-1];
for（i=0;i<20;i++）
{
if（i%5= =0）printf（"
"）;
printf（"%12d",f[i]）;
}
}
運行結果如下：
1 1 2 3 5
8 13 21 34 55
89 144 233 377 610
987 1597 2584 4181 6765
if語句用來控製換行，每行輸出5個數據。
4.2 多維數組
數組名後有兩對方括號的數組叫二維數組，有三對方括號的數組叫三維數組，方括號對數大於或等於二的數組統稱多維數組。
4.2.1 多維數組的定義
多維數組定義的一般形式如下：
數據類型標識符 數組名［常量表達式e1］［常量表達式e2］…；
多維數組定義的數組元素個數為：e1*e2…
同一維數組一樣，多維數組每一維元素的下標也都從0開始。例如：
char c［2］［2］；
此二維數組共有四個元素，分別為：c［0］［0］，c［0］［1］，c［1］［0］，c［1］［1］。這四個數組元素的類型均為字符型。又如：
int n［2］［3］［2］；
此三維數組共有12個元素，分別為：
n［0］［0］［0］n［0］［0］［1］n［0］［1］［0］n［0］［1］［1］n［0］［2］［0］n［0］［2］［1］
n［1］［0］［0］n［1］［0］［1］n［1］［1］［0］n［1］［1］［1］n［1］［2］［0］n［1］［2］［1］
這些元素均為整型變量。一維數組定義需注意的問題對多維數組也適用，此處不再一一例舉。
4.2.2 多維數組的存儲形式
多維數組在內存中按下標順序依次存儲在內存的連續空間中。
對於二維數組，是按先行後列的順序存放，如：char c［2］［2］；先存放第一行，且順序為c［0］［0］，c［0］［1］，然後再存放第二行，且順序為c［1］［0］，c［1］［1］，數組c［2］［2］在內存中的連續存放順序如圖4-1a所示。
C語言允許使用多維數組，下麵介紹多維數組是如何存儲的。
以三維數組為例，如int n［2］［3］［2］；則先存放n［0］［0］［0］，n［0］［0］［1］，然後再存放n［0］［1］［0］，n［0］［1］［1］，…，最後存放n［1］［2］［0］，n［1］［2］［1］，如圖4-1b所示。
圖4-1 數組元素在內存中的連續存放示意圖
4.2.3 多維數組的引用
不論是一維數組還是多維數組，都不能對其進行整體引用，隻能對具體元素進行引用。引用格式與一維數組類似。
二維數組的引用形式：
數組名［e1］［e2］；
三維數組的引用形式：
數組名［e1］［e2］［e3］
其中e1 e2 e3是值大於或等於0的整型表達式，這些表達式可包含變量。例如，對於數組：