陣列

陣列的定義

• 陣列是儲存在連續記憶體位置的相似型別資料項的集合。
• 陣列是C語言中的派生資料型別，它可儲存原始型別的資料，如：int，char，double，float等。
• 陣列是最簡單的資料結構，它的每個資料元素都可以使用索引號隨機存取。
• 例如，如果想要將學生的6個科目的分數儲存，那麼不需要為每個科目的分數定義不同的變數。而是定義一個陣列，將每個科目的分數儲存在連續記憶體位置。

陣列marks[10]定義了10個不同科目的學生分數，每個科目分數位於陣列的特定下標，即marks[0]表示第一個科目的分數，marks[1]表示第二個科目的分數等。

陣列的屬性

• 每個元素具有相同的資料型別並且具有相同的大小，即int = 4個位元組。
• 陣列的元素儲存在連續的儲存器位置，第一個元素儲存在最小的儲存器位置。
• 陣列可以隨機存取陣列的元素，因為可使用給定的基址和資料元素的大小來計算陣列的每個元素的地址。

例如，在C語言中，宣告陣列的語法如下：

int arr[10]; char arr[10]; 
float arr[5];

使用陣列

在計算機程式設計中，大多數情況需要儲存大量相似型別的資料。 要儲存這樣的資料量，需要定義大量的變數。 在編寫程式時，很難記住所有變數的名稱。也沒有必要使用不同的名稱命名所有變數，最好定義一個陣列並將所有元素儲存到其中。

下面的範例說明了陣列在編寫特定問題的程式碼時如何使用。
在下面的例子中，要記錄一個學生六個科目的考試分數。這個問題旨在計算一個學生所有分數的平均值。為了說明陣列的重要性，這裡建立了兩個程式，一個是不使用陣列，另一個是使用陣列來儲存學生的分數。

不使用陣列的程式：

#include <stdio.h>  
void main ()  
{  
    int marks_1 = 56, marks_2 = 78, marks_3 = 88, marks_4 = 76, marks_5 = 56, marks_6 = 89;   
    float avg = (marks_1 + marks_2 + marks_3 + marks_4 + marks_5 +marks_6) / 6 ;   
    printf("%f", avg);   
}

使用陣列的程式：

#include <stdio.h>  
void main ()  
{  
    int marks[6] = {56,78,88,76,56,89};  
    int i;    
    int sum;
    for (i=0; i<6; i++ )   
    {  
        sum = sum + marks[i];   
    }
    float avg = sum / 6;
    printf("%f", avg);   
}

陣列操作的複雜性

陣列操作的時間和空間複雜性在下表中描述。

時間複雜性

空間複雜性
在陣列中，最壞情況下的空間複雜度是O(n)。

陣列的優點

• 陣列為同一型別的變數組提供單一名稱，因此很容易記住陣列中所有元素的名稱。
• 遍歷陣列是一個非常簡單的過程，只需要遞增陣列的基址，就可以逐個存取每個元素。
• 可以使用索引直接存取陣列中的任何元素。

記憶體分配陣列

如前面所提到的，陣列的所有資料元素都儲存在主記憶體儲器中的連續位置。 陣列名稱表示主記憶體儲器中的基地址或第一個元素的地址。 陣列的每個元素都由適當的索引表示。
可以用三種方式定義陣列的索引。

• 0(從零開始索引)：陣列的第一個元素是arr[0]。
• 1(基於一個索引)：陣列的第一個元素是arr [1]。
• n(基於n的索引)：基於陣列的第一個元素，可以定位任何隨機索引值。

在下圖中，展示了大小為5的陣列arr的記憶體分配。該陣列遵循基於0的索引方法。陣列的基址是第100位元組，它將是arr[0]的地址。 這裡，int的大小是4個位元組，因此每個元素在記憶體中占用4個位元組。

在基於0的索引中，如果陣列的大小是n，那麼它是最大索引號，則最後一個元素使用n-1來存取。 但是，如果使用基於1的索引，那麼它的最大索引值將是n。

存取陣列的元素

要存取陣列的任何隨機元素，需要以下資訊：

• 陣列的基址。
• 元素的大小(以位元組為單位)。
• 陣列的索引型別。

可以使用以下公式計算一維陣列的元素地址：

 A[i] 元素的位元組地址  = 基地址 + size * ( i - 第1個索引)

範例：

在陣列中, A[-10 ..... +2 ], 基地址 (BA) = 999, 元素的大小 = 2 位元組,   
找出 A[-1] 的位置如下 -   
L(A[-1]) = 999 + [(-1) - (-10)] x 2  
       = 999 + 18   
       = 1017

將陣列傳遞給函式

如前面提到的那樣，陣列的名稱代表陣列第一個元素地址或陣列的起始地址。 可以使用基址遍歷陣列的所有元素。

以下範例說明了如何將陣列傳遞給函式。

範例：

#include <stdio.h>  
int summation(int[]);  
void main ()  
{  
    int arr[5] = {0,1,2,3,4};  
    int sum = summation(arr);   
    printf("%d",sum);   
}   

int summation (int arr[])   
{  
    int sum=0,i;   
    for (i = 0; i<5; i++)   
    {  
        sum = sum + arr[i];   
    }   
    return sum;   
}