數組
 | 此條目沒有列出任何參考或來源。 (2018年10月17日) |
在計算機科學中，陣列資料結構（英語：array data structure），簡稱數組（英語：Array），是由相同類型的元素（element）的集合所組成的資料結構，分配一塊連續的內存來存儲。利用元素的索引（index）可以計算出該元素對應的儲存地址。
最簡單的資料結構類型是一維陣列。例如，索引為0到9的32位元整數陣列，可作為在記憶體位址2000，2004，2008，...2036中，儲存10個變量，因此索引為i的元素即在記憶體中的2000+4×i位址。陣列第一個元素的記憶體位址稱為第一位址或基礎位址。
二維數組，對應於數學上的矩陣概念，可表示為二維矩形格。例如：在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維。
多維數組的數組名字，在表達式中自動轉換為數組首元素地址值，但這個首元素實際上是去除數組下標第一維之後的數組剩餘部分。例如：
int a[10][15];
int (*p)[15] = a; // a在表达式中自动转换为指向具有15个int的数组的指针值
C/C++標準中的數組
[編輯]C/C++數組概念有雙重含義，一是數據類型，二是實體（entity）。 C語言標準中規定，一個數組類型描述了連續分配的非空的具有特定元素對象類型的對象集合。這些元素對象的類型稱為元素類型（element type）。數組類型由元素類型與元素的數目確定[註 1]。
在C語言中，可以顯式定義一個數組類型，例如：
typedef int myArrayType [101];
數組名作為數組實體的標識符，具有特殊性，不同於整型、浮點型、指針型或結構類型等變量標識符。這是因為數組是一組元素的聚集，不能把一個聚集看作一個值直接讀出（這個值指的是右值），也不能把一個聚集看作一個地址直接賦值（即左值）。因此，數組名作為左值、右值，在C語言標準中都有特殊規定[註 2]：
- 作為
sizeof的操作數，數組名代表數組對象本身； - 作為取地址運算符
&的操作數，數組名代表數組對象本身[註 3]； - 作為字符串字面量用於初始化一個數組；
- 其他情形，表達式中的數組名從數組類型被自動轉化為指向數組首元素的指針類型表達式（右值）。[註 4]
例如，
char s[] = "hello";
int main() {
char (*p1)[6] = &s; // OK!
char (*p2)[6] = s; // compile error: cannot convert 'char*' to 'char (*)[6]'
char *p3 = &s; // compile error: cannot convert 'char (*)[6]' to 'char*' in initialization
}
根據上述C語言標準中的規定，表達式&s的值的類型是char (*)[6]，即指向整個數組的指針；而表達式 s 則被隱式轉換為指向數組首元素的指針值，即 char* 類型。同理，表達式s[4]，等效於表達式*(s+4)。
數組下標運算符
[編輯]C語言標準中定義，數組下標運算（array subscripting）有兩個運算數，一個為到類型type的指針表達式，另一個運算符為整數表達式，結果為類型type。但沒有規定兩個運算數的先後次序[註 5]。因此，有以下推論：
- 兩個運算數可以交換順序，即 p[N] 與 N[p] 是等價的，為 *(p+N) ；
- 數組下標運算，既可以適用於數組名（實際上隱式把數組名轉換為指向數組首元素的指針表達式），也可以適用於指針表達式；
- 整型表達式可以取負值。
例如：
int a[10], *p = a;
p[0] = 10;
(p + 1)[0] = 20;
0[p + 1] = 10;
不完整的數組類型
[編輯]不完整的數組類型屬於不完整類型（incomplete type），即缺乏信息去確定其尺寸。例如：
extern int a[]; // 外部变量声明
void foo(int b[]) {} // 函数形参
void bar(int b[][10]) {} // 多维数组形参
int a[] = { 10, 20 }; // 初始化
柔性數組成員
[編輯]C99規定，struct的最後一個成員可以是不完整的數組類型。例如：
struct test {
int a;
double b;
char c[];
};
Visual C++ 2015支持上述語法。
可變長數組
[編輯]C99引入了可變長數組（variable length array，簡稱VLA），只能定義在塊作用域或函數原型作用域，必須無鏈接性。其數組長度在編譯期可變，但在運行期該數組對象一旦生成就不可改變數組長度了。例如：
void foo(int m，int n) {
int v[m][n];
int *p[n];
}
程式設計
[編輯]數組設計之初是在形式上依賴內存分配而成的，所以必須在使用前預先請求空間。這使得數組有以下特性：
- 請求空間以後大小固定，不能再改變（數據溢出問題）；
- 在內存中有空間連續性的表現，中間不會存在其他程序需要調用的數據，為此數組的專用內存空間；
- 在舊式程式語言中（如有中階語言之稱的C），程式不會對數組的操作做下界判斷，也就有潛在的越界操作的風險（比如會把數據寫在運行中程式需要調用的核心部份的內存上）。
因為簡單數組強烈倚賴電腦硬件之內存，所以不適用於現代的程序設計。欲使用可變大小、硬件無關性的數據類型，Java等程式設計語言均提供了更高級的數據結構：ArrayList、Vector等動態陣列。
注釋
[編輯]- ^ C99語言標準6.2.5節中規定：An array type describes a contiguously allocated nonempty set of objects with a particular member object type, called the element type. Array types are characterized by their element type and by the number of elements in the array. An array type is said to be derived from its element type, and if its element type is T, the array type is sometimes called 「array of T」. The construction of an array type from an element type is called 「array type derivation」.
- ^ C99標準中的第「6.3.2.1 Lvalues, arrays, and function designators」小節中規定：Except when it is the operand of the sizeof operator or the unary & operator, or is a string literal used to initialize an array, an expression that has type 「array of type」 is converted to an expression with type 「pointer to type」 that points to the initial element of the array object and is not an lvalue. If the array object has register storage class, the behavior is undefined.
- ^ 只能對具有左值的數組名執行取地址的
&操作。對右值數組，例如函數調用結果是一個數組類型時，對該數組取地址 & 則會編譯報錯：taking address of temporary - ^ C++98標準中規定：An lvalue or rvalue of type 「array of N T」 or 「array of unknown bound of T」 can be converted to an rvalue of type 「pointer to T.」 The result is a pointer to the first element of the array.
- ^ C99語言標準「6.5.2.1 Array subscripting」中有：Constraints One of the expressions shall have type 『『pointer to object type’』, the other expression shall have integer type, and the result has type 『『type’』.
