數組

數組的定義

• 數組是存儲在連續記憶體位置的相似類型資料項目的集合。
• 數組是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;
}