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