Array

在計算機科學中，**陣列資料結構**（英語：array data structure），簡稱**陣列**（英語：Array），是由相同類型的元素（element）的集合所組成的資料結構，分配一塊連續的記憶體來儲存。利用元素的索引（index）可以計算出該元素對應的儲存位址。

最簡單的資料結構類型是**一維陣列**。例如，索引為 0 到 9 的 32 位元整數陣列，可作為在記憶體位址 2000，2004，2008，...2036 中，儲存 10 個變數，因此索引為 i 的元素即在記憶體中的 2000+4×i 位址。陣列第一個元素的記憶體位址稱為第一位址或基礎位址。

**二維陣列**，對應於數學上的矩陣概念，可表示為二維矩形格。例如： $a={\begin{bmatrix}3&6&2\\0&1&-4\\2&-1&0\end{bmatrix}}$ 在 C 語言中表示為 `int a[3][3] = {{3, 6, 2}, {0, 1, -4}, {2, -1, 0}};`。

在某些情況下，「向量」一詞也可能代表二維陣列，雖然在數學意義上更確切地稱呼為元組（tuple），而不是向量。但需要注意的是：電腦科學的某些領域，如 Matlab，元組是指類似 C 語言 struct 類型，具有固定的往往是不同類型的資料成員的資料結構。

陣列通常用於實作資料庫的表格，特別是查詢表；表格有時也被當作是陣列的同義詞。

陣列是最早期和最重要的資料結構之一，很多程式都會用到陣列。它們也用於實作許多其他資料結構，譬如列表（list）和字串（string）。它們有成效地開展了計算機的定址邏輯。在大多數現代計算機和許多外部儲存裝置中，記憶體如同一維陣列，索引就是其位址。編譯器、處理單元（特別是向量處理器），經常會針對陣列操作進行優化。

因為在程式運行時可以計算元素的索引，陣列是很有用的。此外，也能以單一迭代語句就處理陣列的許多元素。為此，陣列資料結構的元素必須具有相同的大小，而且應該使用相同的資料型別表示。

陣列一詞通常用於表示陣列資料類型，一種大多數高階程式語言都會內建的資料型別。陣列型別通常由陣列結構來實作；然而在某些語言中，它們可以由雜湊表、連結串列、搜尋樹或其它資料結構來實現。

在演算法的描述中，陣列一詞特別著重意義為關聯陣列或「抽象的陣列」，一種理論上的計算機科學模型（抽象數據類型或 ADT），專注於陣列的基本性質上。

## 歷史

第一台數位計算機使用機器語言程式設計來設定和存取資料表，向量和矩陣計算的陣列結構，以及許多其它目的。1945 年，在建立第一個范紐曼型架構計算機時，約翰・馮・紐曼（John von Neumann）寫了第一個陣列排序程式（合併排序）。陣列索引最初是通過自修改代碼，後來使用索引暫存器和間接定址來完成的。1960 年代設計的一些主機，如 Burroughs B5000 及其後繼者，使用記憶體分段來執行硬體中的索引邊界檢查。

除了機器硬體本身提供的，機器語言並沒有特別支援陣列。最早的高階程式語言包括 FORTRAN（1957）、Lisp（1958）、COBOL（1960）和 ALGOL 60（1960），則開始支援多維陣列，C（1972）也是如此。在 C++（1983）中，對於維度固定和彈性的多維陣列，提供了類別模板。

## 應用

陣列實作數學向量和矩陣，以及其它類型的長方表格。許多資料庫是由元素為（或包含）記錄的一維陣列所組成。
陣列也用於實作其它資料結構，例如列表、堆積、雜湊表、雙向佇列、佇列、
堆疊、字串和 VLists。與基於樹實作的資料結構相比，基於陣列實作的資料結構通常是簡單和有空間效率的（隱式資料結構），空間成本開銷很少；但陣列需要修改時則空間的複雜性相對比較差（已排序的陣列結構，與搜尋樹相比）。

一或多個大型陣列有時用於類比程式內的動態記憶體分配，特別是固定記憶區塊規劃。從歷史上看，這有時是可移植地分配「動態記憶體」的唯一方法。

陣列可用於決定程式中的部份或完整控制流程，簡潔地替代多個 `IF` 語句。它們在上下文中被稱為控制表，並與專門構建的解釋器結合使用，其控制流將依照陣列所含有的值來變動。該陣列可能含有指向執行子程式的指針（或由 `SWITCH` 語句執行的相關子程式編號）。

## 元素標識符和定址公式

當資料物件儲存在陣列中時，個別物件通常藉由非負整數的索引變數來選取。索引也稱為下標，可將陣列的值對應到儲存物件。

有三種方式對陣列的元素進行索引：

* **0**（從零開始索引）：陣列的第一個元素由下標為 0 開始的索引。如 C/C++。
* **1**（從 1 開始索引）：陣列的第一個元素由下標為 1 開始的索引。如 Pascal、Delphi 語言。
* **n**（從 n 開始索引）：可自由選擇陣列的基本索引。通常，允許從 n 開始索引的程式語言還允許負數索引值和諸如列舉的其他純量資料類型，也可以將字元當作陣列的索引。

陣列可以具備多個維度，因此常見使用多重索引來存取陣列。例如，從零開始索引的情況下，有三行和四列的二維陣列 `A` 需要存取第二行和第四列的元素時，表達式可為 `A[1,3]`。因此，二維陣列使用兩個索引下標，三維陣列使用三個索引下標，n 維陣列使用 n 個索引下標。

指定元素所需的索引數稱為陣列的維度，維數或陣列的秩。

標準陣列中每個索引會被限制在一定範圍內的連續整數（或某些枚舉類型的連續值），
而元素位址則是對索引值的「線性」計算公式。

### 一維陣列

一維（或單維）陣列是一種線性陣列，其中元素的存取是以行或列索引的單一下標表示。

譬如考慮 C 程式語言的陣列宣告 
`int anArrayName [10];`

語法為： 

datatype anArrayName [sizeofArray];

在上述範例中，被宣告的陣列將包含 `int` 型別的 10 個元素，可為任何整數值。這樣，陣列元素的索引下標則為 0-9（含）。例如，`anArrayName[0]` 和 `anArrayName[9]` 分別是第一個和最後一個元素的表達。

對於以線性定址的向量，索引為 i 的元素處於位址 B+c×i，其中 B 是固定的基底位址，c 為常數，
有時稱為位址增量或跨步。

如果有效的元素索引從 0 開始，則常數 B 只是陣列第一個元素的位址。因此 C 語言指定陣列的索引一定從 0 開始；許多開發人員會將該元素稱為「第零」而不是「第一」。

然而若適當選擇基底位址 B，來作為第一個元素的索引起始值。譬如陣列有五個元素，索引為 1 到 5，基底位址 B 以 B+30c 來替換，則相同陣列的這些元素索引將轉為 31 到 35。如果編號從 0 開始，則常數 B 可能不是任何元素的位址。

### 多維陣列

普通陣列採用一個整數來作下標。**多維陣列**（**高維陣列**）的概念特別是在數值計算和圖形應用方面非常有用。我們在多維陣列之中採用一系列有序的整數來標註，如在 [3,1,5] 。這種整數列表之中整數的個數始終相同，且被稱為陣列的「維度」。關於每個陣列維度的邊界稱為「維」。維度為 _k_ 的陣列通常被稱為 _k_ 維。

多維陣列的陣列名字，在表達式中自動轉換為陣列首元素位址值，但這個首元素實際上是去除陣列下標第一維之後的陣列剩餘部分。例如：

### C/C++ 標準中的陣列

C/C++ 陣列概念有雙重含義，一是資料類型，二是實體（entity）。
C 語言標準中規定，一個**陣列類型**描述了連續分配的非空的具有特定元素物件類型的物件集合。這些元素物件的類型稱為元素類型（element type）。陣列類型由元素類型與元素的數目確定。

在 C 語言中，可以顯式定義一個陣列類型，例如：

```
 typedef int myArrayType [101];
```

**陣列名**作為**陣列實體**的識別碼，具有特殊性，不同於整型、浮點型、指標型或結構類型等變數識別碼。這是因為陣列是一組元素的聚集，不能把一個聚集看作一個值直接讀出（這個值指的是右值），也不能把一個聚集看作一個位址直接賦值（即左值）。因此，陣列名作為左值、右值，在 C 語言標準中都有特殊規定：

* 作為 `sizeof` 的運算元，陣列名代表陣列物件本身；
* 作為取位址運算子 `&` 的運算元，陣列名代表陣列物件本身；
* 作為字串字面量用於初始化一個陣列；
* 其他情形，表達式中的陣列名從陣列類型被自動轉化為指向陣列首元素的指標類型表達式（右值）。

例如，

根據上述 C 語言標準中的規定，表達式 `&s` 的值的類型是 char (\*)[6]，即指向整個陣列的指標；而表達式 s 則被隱式轉換為指向陣列首元素的指標值，即 char\* 類型。同理，表達式 `s[4]`，等效於表達式 `*(s+4)`。

### 陣列下標運算子

C 語言標準中定義，陣列下標運算（array subscripting）有兩個運算數，一個為到類型 type 的指標表達式，另一個運算子為整數表達式，結果為類型 type。但沒有規定兩個運算數的先後次序。因此，有以下推論：

* 兩個運算數可以交換順序，即 p [N] 與 N [p] 是等價的，為 \*(p+N) ；
* 陣列下標運算，既可以適用於陣列名（實際上隱式把陣列名轉換為指向陣列首元素的指標表達式），也可以適用於指標表達式；
* 整型表達式可以取負值。

例如：

### 不完整的陣列類型

不完整的陣列類型屬於不完整類型（incomplete type），即缺乏資訊去確定其尺寸。例如：

### 柔性陣列成員

C99 規定，struct 的最後一個成員可以是不完整的陣列類型。例如：

Visual C++ 2015 支援上述語法。

### 可變長陣列

C99 引入了可變長陣列（variable length array，簡稱 VLA），只能定義在塊作用域或函式原型作用域，必須無連結性。其陣列長度在編譯期可變，但在執行期該陣列物件一旦生成就不可改變陣列長度了。例如：

## 程式設計

陣列設計之初是在形式上依賴記憶體分配而成的，所以必須在使用前預先請求空間。這使得陣列有以下特性：

1. 請求空間以後大小固定，不能再改變（數據溢位問題）；
2. 在記憶體中有空間連續性的表現，中間不會存在其他程式需要調用的數據，為此陣列的專用記憶體空間；
3. 在舊式程式語言中（如有**中階語言**之稱的 C），程式不會對陣列的操作做下界判斷，也就有潛在的越界操作的風險（比如會把數據寫在運行中程式需要調用的核心部份的記憶體上）。

因為簡單陣列強烈倚賴電腦硬體之記憶體，所以不適用於現代的程式設計。欲使用可變大小、硬體無關性的數據類型，Java 等程式設計語言均提供了更高級的數據結構：ArrayList、Vector 等動態陣列。

## 注釋

## 參考文獻

## 外部連結

* NIST's Dictionary of Algorithms and Data Structures: Array

## 參見

* 一維陣列
* 二維陣列 (矩陣)