数组
 | 此条目没有列出任何参考或来源。 (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’’.
