数组
 | 此條目没有列出任何参考或来源。 (2018年10月17日) |
在計算機科學中，陣列資料結構（英語：array data structure），簡稱数组（英語：Array），是由相同类型的元素（element）的集合所組成的資料結構，分配一块连续的内存来存储。利用元素的索引（index）可以计算出该元素對應的儲存地址。
最簡單的資料結構類型是一維陣列。例如，索引為0到9的32位元(4個位元組)整數陣列，可儲存10個變量，位於記憶體位址2000，2004，2008，...2036中，因此索引為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’’.
