進階陣列
C 語言中陣列變數的彈性帶給程式很大的效率優點,
但是也讓學 C 語言的設計者很多的困擾。
在繼續下去之前,
請先瞭解
-
基本的陣列
-
指標變數
陣列之宣告與記憶體配置
陣列及指標兩者的複合宣告是 C 語法中最複雜的部份, 初學者常常容易誤用
-
陣列的成員:
-
基本型態變數:char、short、int、long、float、double x[10];
-
基本型態變數之指標:char*、short*、int*、long*、float*、double *x[10];
-
使用者自定結構變數:struct tag {..........} x[10];
-
使用者自定結構變數之指標:struct tag {..........} *x[10];
- 陣列: int x[10][1000];, float x[10][25][4];
-
宣告範例與其記憶體配置:
-
int x[10];
代表 10-element ARRAY of int
(x 為一 10 元素的陣列,
每個元素是一個 int 型態變數)
其記憶體配置如下圖:
注意:
int [10] 為陣列變數 x 之型態 sizeof (int [10]) = 20
int 為變數 x[0], x[1], x[2]......x[9] 個別之型態
-
char x[5][3];
依照運算子 (算符) 之優先順序與結合律,
此定義可以解釋為:
char ((x[5])[3]);
代表 5-element ARRAY of (3-element ARRAY of char)
(x 為一 5 個元素的陣列,
每一元素又一個 3 個元素的陣列,
其一元素為一字元)
其記憶體配置如下圖:
注意:
- char[5][3] 亦即 char (* const)[3] 為變數 x 之型態。
- char [3] 亦即 char *const 為變數 x[0], x[1]......x[4] 之型態。
-
char 為變數 x[0][0], x[0][1]......x[4][2] 個別之型態。
-
二維陣列在大部份人的想法裡都是用行列的矩陣思考它,
但是在電腦記憶體中實際上它是排成一串的,
以 C 語言來說,
是先排一列裡所有的元素再排下列所有的元素,
這種方式我們稱為 row major,
以別於 FORTRAN 裡頭的 column major 方式。
-
double *x[4][2];
依照運算子 (算符) 之優先順序與結合律,
此定義可以解釋為:
double (*((x[4])[2]));
代表 4-element ARRAY of (2-element ARRAY of (POINTER to a double))
(x 為一 4 元素的陣列,
每一元素是一 2 元素的陣列,
此 2 元素的陣列之每一元素為一指向倍精準浮點變數之指標)
其記憶體配置如下圖:以 Turbo C NEAR Pointer (16位元位址) 為例
注意:
- double *[4][2] 或是 double * (*)[2] 為變數 x 之型態
sizeof(x)
= sizeof(double *[4][2])
= sizeof(double *[2])*4
= sizeof(double *)*2*4
= 2 * 2 * 4
= 16
- double * [2] 或是 double ** 為變數 x[0], x[1], x[3]之型態
sizeof(x[0])
= sizeof(double *[2])
= sizeof(double*) * 2
= 2 * 2
= 4
-
double * 為變數 x[0][0], x[0][1]......x[3][1] 之型態。
-
double 為變數 *x[0][0], *x[0][1]......*x[3][1] 之型態。
-
double (*x)[4][2];
依照運算子 (算符) 之優先順序以及結合律,
此定義可以解釋為
double (((*x)[4])[2]);
代表 POINTER to (a 4-element ARRAY of (a 2-element ARRAY of double))
(x 變數為一指標,
指向一 4 元素之陣列,
其每一元素為一 2 元素之陣列,
此 2 元素陣列的每一元素為一倍精準浮點數。)
其記憶體配置如下圖:
注意:
- double (*) [4][2] 或是為指標變數 x 之型態
sizeof(x)
= sizeof(double (*) [4][2])
= 2
- double [4][2] 或是 double (*)[2] 為陣列變數 *x 之型態
sizeof(*x)
= sizeof(double [4][2])
= sizeof(double [2]) * 4
= sizeof(double) *2 *4
= 8 * 2 * 4
= 64 bytes
- double [2] 或是 double * 為陣列變數 (*x)[0], (*x)[1], (*x)[2],
(*x)[3] 之型態
sizeof((*x)[2])
= sizeof(double [2])
= sizeof(double) *2
= 8 * 2
= 16 bytes
-
double 為變數 (*x)[0][0], (*x)[0][1]......(*x)[3][1] 之型態
sizeof((*x)[2][1])
= sizeof(double)
= 8 bytes
-
由上面幾個範例的說明,
我們可以說 C 語言裡的陣列嚴格來講都只是一維的,
所謂的 N 維陣列其實只是一個一維陣列、
而其中每一個元素都是一個 N-1 維的陣列而已。
何時可將陣列視為一個整體來使用?
C 語言中並沒有定義陣列的等號,
不能以下面的程式來拷貝整個陣列的資料:
int i;
int x[10], y[10];
for (i=0; i<10; i++)
x[i] = i * (i-1);
y = x;
必須以迴圈來處理陣列內資料的拷貝,如下:
for (i=0; i<10; i++)
y[i] = x[i];
程式設計者感覺到陣列是一個整體的唯一時機是在將陣列變傳遞到函式裡的時候,
例如:列印陣列資料的函式:
void printArray(int iArray[], int numberOfElements)
{
int i ;
for (i=0; i<numberOfElements; i++)
printf("%d", iArray[i]);
}
............
void main(void)
{
int iScores[100];
............
printArray(iScores, 100)
............
}
注意:
函式的參數為一陣列時,
對於編譯器來說只要該陣列元素的型態清楚即可,
陣列到底有幾個元素並不重要,
因為在函式內並不替該陣列配置新的記憶體,
以陣列為參數叫用某一函式時,
僅將陣列的起始位址傳進函式而已,
函式內透過傳入的位址可以直接存取陣列的內容,
(函式參數宣告為陣列的型態 int iArray[100],
也可以宣告為未定個數的陣列型態 int iArray[],
或是整數指標的型態 int *iArray),
可以使用 iArray[i] 來存取個別變數之內容。
請注意雖然 iScores 是陣列裡第一個元素的位址,
&iScores 是 100個整數陣列的起始位址,
好像應該把整個陣列傳進函式才比較有道理,
可是如果你寫 printArray(&iScores, 100);
函式宣告需要配合成為 void printArray(int (*iArray)[100], int numberOfElements);,
資料透過 (*iArray)[i] 來存取,
或是把函式宣告為 void printArray(int iArray[][100], int numberOfElements);,
資料透過 iArray[0][i] 來存取, 反而變得很奇怪。
陣列變數與指標常數
陣列變數的定義隱含了許多意義:
例一:int x[15];
-
在資料區或是系統堆疊上保留 15 * sizeof(int) 個連續的位元組來存放資料
-
定義了 15 個整數變數 x[0], x[1], ..., x[14] (&x[0], &x[1], ..., &x[14] 代表個別變數的記憶體位址)
-
定義了 1 個指向該陣列第一個元素的指標常數 x (型態是 int *const, sizeof(*x)==sizeof(*&x[0])==sizeof(x[0])==sizeof(int))
- &x 則是以整個陣列為一個資料單位的起始位址 (型態是 int (*const)[15], sizeof(*&x)==sizeof(x)==sizeof(int[15])==15*sizeof(int))。
注意:
x 是一個指標常數,
指向該陣列的第一個元素,
若我們定義一個指標變數 int *y = x;
則在大部分的地方都可以用 y 來取代 x,
例如:y[5], y[i],
唯一不一樣的地方是
sizeof(x)==15 * sizeof(int) 而 sizeof(y)==sizeof(int *),
除了陣列名稱 x 之外,所有指標變數或是指標常數的大小都是記憶體位址的大小 sizeof(int *),在 32 位元作業系統上是 4。
例二:int x[15][20];
-
在資料區或是堆疊上保留 15 * 20 * sizeof(int) 個位元組來存放資料
-
定義了 15 * 20 個整數變數 x[0][0], x[0][1], ..., x[14][19]
&x[0][0], &x[0][1], ..., &x[14][19] 為個別變數的記憶體位址
sizeof(x[0][0])==sizeof(int), sizeof(&x[0][0])==sizeof(int *)
-
定義了 15 個陣列指標常數 x[0], x[1], ..., x[14], 型態是 int *
代表個別 int[20] 型態的陣列的第一個元素的記憶體位址 x[0]==&x[0][0], x[1]==&x[1][0], ...
&x[0], &x[1], ..., &x[14] 為個別 int[20] 型態變數的記憶體位址, 型態是 int (*)[20]
sizeof(x[0][0])==sizeof(int), sizeof(&x[0][0])==sizeof(int *),
sizeof(x[0])==sizeof(*&x[0])==sizeof(int[20])==20*sizeof(int),
sizeof(&x[0])==sizeof(int(*)[20])==sizeof(int *)
-
定義了一個指向 int [15][20] 陣列的指標常數 x,型態是 int (*const)[20],
指向該陣列的第一個 int [20] 型態的元素
&x 是一個指標常數,型態是 int (*const)[15][20]
sizeof(x)==sizeof(*&x)==sizeof(int[15][20])==300*sizeof(int),
sizeof(&x)==sizeof(int(*)[15][20])==sizeof(int *)
指標常數的用法
以 int x[15] 為例,
陣列變數 x 本身是一個指標常數,
sizeof(x)雖然是整個陣列的大小,
但是 x 可以當做一般的 int * 型態指標來使用,
例如:
*(x+3) = 10;
*x = *(x+5) * *(x+10);
注意:
-
在 C 語言中 int x[15]; 這樣子的變數 x 而言,
x[3] = 1; 和 *(x+3) = 1;
是完完全全一樣的敘述。
當然和 *(3+x) = 1;
也是完全一樣的東西,
你要不要試看看 3[x] = 1; 呢?
-
我們常常看到 int main(int argc, char *argv[]);
或是 int main(int argc, char **argv); 的宣告,
其中 char *argv[] 與 char **argv 有何差異?
第一個是 ARRAY of POINTER to char,
第二個則是 POINTER to POINTER to char,
原則上兩種 argv 的用法幾乎完全一樣,
唯一不同的地方是:
第二種定義方法 char **argv,
因為不是定義為 char * (* const) argv,
所以 argv 是個可以更改的變數,
而第一種定義方法的話 argv 是個常數,
程式執行時無法更動。
在函式參數定義陣列時所代表的意義
在函式參數定義陣列變數和一般的陣列不一樣的地方:
-
並不配置陣列內資料的存放空間,
而只在堆疊上定義一個指標常數來存放陣列中第一變數的位址,
以便存取陣列內變數之內容。
-
由於不配置資料存放區域,
所以除了需要定義每一元素的型態之外,
不需要定義陣列內元素的個數。
例如:
int average(int intAry[], int numElements)
{
double sum = 0;
int i;
for (i=0; i<numElements; i++)
sum = sum + intAry[i];
return sum / numElements;
}
此範例中,
必須知道 intAry[] 陣列每一個元素是 int 型態的變數,
如此 intAry[i] 的寫法才能順利取得第 i 個元素內存放的資料,
同時在處理 sum + intAry[i]
時才知道 intAry[i] 需要轉換為 double 型態。
注意:
如果是二維的陣列如下例,
則至少需要填寫一個維度元素的個數,
否則函式內無法存取到正確的變數。
int average(int intAry[][10], int numElements)
{
double sum = 0;
int i, j ;
for (i=0; i<numElements; i++)
for (j=0; j<10, j++)
sum += intAry[i][j];
return sum / numElements / 10;
}
void main(void)
{
int x[30][10];
............
average(x,30);
............
}
指標陣列與陣列中陣列 (多維陣列) 的比較
-
二維陣列:char twoDimAry[10][5];
-
指標陣列:char *ptrAry[10];
二維陣列
定義了 10 個指向 char[5] 型態變數的指標常數
twoDimAry[0], twoDimAry[1],...... twoDimAry[9],
1 個指向 char[10][5] 型態變數的指標常數 twoDimAry,
以及 50 個 char 型態的變數,
使用起來可以用下面的語法:
for (i=0; i<10; i++)
for (j=0; j<5; j++)
sum = sum + twoDimAry[i][j];
注意:
-
記憶體內共需
sizeof(char[10][5])
= 10 * sizeof(char[5])
= 10 * 5 * sizeof(char)
= 50 個位元組
-
如果要存放在這個 twoDimAry 中的資料有 5 個是 5 個位元組,
有 5 個是 1 個位元組,
那麼存放 1 個位元組的就比較浪費,
萬一有的資料是 20 個位元組,
有的是 1 個位元組,
也必須定義陣列為 char[10][20] 才能放下所有的資料。
指標陣列
只定義了 10 個指標變數
ptrAry[0], ptrAry[1],......ptrAry[10],
及一個 ptrAry 指向陣列的指標常數,
記憶體內共需
sizeof(ptrAry)
= 10 * sizeof(char*)
= 20 個位元組
真正用來存放資料的記憶體空間需要另外以 malloc 動態配置,
例如:
for (i=0; i<10; i++)
ptrAry[i] = (char*) malloc(sizeof(char[5]));
如此配置的記憶體架構如下圖:
注意:
-
這樣子配置的資料變數使用起來和二維的陣列完全一樣,
例如:
for (i=0; i<10; i++)
for (j=0; j<5; j++)
sum = sum + ptrAry[i][j];
prtAry[i] 的型態雖然是一個字元指標 char*,
但是在 C 語言中允許程式設計者用字元陣列 char[] 的語法來存取,
所以可以用 ptrAry[i][j]
來存取 ptrAry[i] 所指向字元陣列的第 j 個字元,
ptrAry[i][j] 和 *(*(ptrAry+i)+j) 是完全一樣的。
不過請注意存取的效率是有差別的,
詳見 testArrayEfficiency.cpp
-
請注意記憶體內共需 10 * 5 + 10 * sizeof(char) = 70 個位元組,
其中存放資料的僅為 50 個位元組,
此 50 個位元組不見得為連續的 50 個位元組。
-
所需的記憶體似乎比 char twoDimAry[10][5] 的 50 個位元組多,
為何要這樣子使用呢?
事實上指標陣列最有用的地方是當每一個元素的資料長度差異很大的時候,
例如有的需要 50 個位元組,
有的需要 2 個位元組,
若是宣告 char[10][50] 就太浪費了。