数组

在计算机科学中，数组数据结构（英语：array data structure），简称数组（英语：Array），是由相同类型的元素（element）的集合所组成的数据结构，分配一块连续的内存来存储。利用元素的索引（index）可以计算出该元素对应的存储地址。最简单的数据结构类型是一维数组。例如，索引为0到9的32位整数数组，可作为在存储器地址2000，2004，2008，...2036中，存储10个变量，因此索引为i的元素即在存储器中的2000+4×i地址。数组第一个元素的存储器地址称为第一地址或基础地址。二维数组，对应于数学上的矩阵概念，可表示为二维矩形格。例如： a = [ 3 6 2 0 1 − 4 2 − 1 0 ] {displaystyle a={begin{bmatrix}3&6&2\0&1&-4\2&-1&0end{bmatrix}}} 在C语言中表示为int a = {{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语句运行的相关子程序编号）。当数据对象存储在数组中时，个别对象通常借由非负整数的索引变量来选取。索引也称为下标，可将数组的值对应到存储对象。有三种方式对数组的元素进行索引：数组可以具备多个维度，因此常见使用多重索引来访问数组。例如，从零开始索引的情况下，有三行和四列的二维数组A需要访问第二行和第四列的元素时，表达式可为A。因此，二维数组使用两个索引下标，三维数组使用三个索引下标，n维数组使用n个索引下标。指定元素所需的索引数称为数组的维度，维数或数组的秩。标准数组中每个索引会被限制在一定范围内的连续整数（或某些枚举类型的连续值）， 而元素地址则是对索引值的“线性”计算公式。一维（或单维）数组是一种线性数组，其中元素的访问是以行或列索引的单一下标表示。譬如考虑C编程语言的数组宣告 int anArrayName ;语法为： datatype anArrayName ;在上述示例中，被宣告的数组将包含int类型的10个元素，可为任何整数值。这样，数组元素的 索引下标则为0-9（含）。例如，anArrayName和anArrayName分别是第一个和最后一个元素的表达。对于以线性定址的向量，索引为i的元素处于地址B+c×i，其中B是固定的基底地址，c为常量， 有时称为地址增量或跨步。如果有效的元素索引从0开始，则常量B只是数组第一个元素的地址。因此C语言指定 数组的索引一定从0开始；许多开发人员会将该元素称为“第零”而不是“第一”。然而若适当选择基底地址B，来作为第一个元素的索引起始值。譬如数组有五个元素，索引为1到5，基底地址B以B+30c来替换，则相同数组的这些元素索引将转为31到35。如果编号从0开始，则常量B可能不是任何元素的地址。普通数组采用一个整数来作下标。多维数组（高维数组）的概念特别是在数值计算和图形应用方面非常有用。我们在多维数组之中采用一系列有序的整数来标注，如在 。这种整数列表之中整数的个数始终相同，且被称为数组的“维度”。关于每个数组维度的边界称为“维”。维度为k的数组通常被称为k维。多维数组的数组名字，在表达式中自动转换为数组首元素地址值，但这个首元素实际上是去除数组下标第一维之后的数组剩余部分。例如：C/C++数组概念有双重含义，一是数据类型，二是实体（entity）。 C语言标准中规定，一个数组类型描述了连续分配的非空的具有特定元素对象类型的对象集合。这些元素对象的类型称为元素类型（element type）。数组类型由元素类型与元素的数目确定。在C语言中，可以显式定义一个数组类型，例如：数组名作为数组实体的标识符，具有特殊性，不同于整型、浮点型、指针型或结构类型等变量标识符。这是因为数组是一组元素的聚集，不能把一个聚集看作一个值直接读出（这个值指的是右值），也不能把一个聚集看作一个地址直接赋值（即左值）。因此，数组名作为左值、右值，在C语言标准中都有特殊规定：例如，根据上述C语言标准中的规定，表达式&s的值的类型是char (*)，即指向整个数组的指针；而表达式 s 则被隐式转换为指向数组首元素的指针值，即 char* 类型。同理，表达式s，等效于表达式*(s+4)。C语言标准中定义，数组下标运算（array subscripting）有两个运算数，一个为到类型type的指针表达式，另一个运算符为整数表达式，结果为类型type。但没有规定两个运算数的先后次序。因此，有以下推论：例如：不完整的数组类型属于不完整类型（incomplete type），即缺乏信息去确定其尺寸。例如：C99规定，struct的最后一个成员可以是不完整的数组类型。例如：Visual C++ 2015支持上述语法。C99引入了可变长数组（variable length array，简称VLA），只能定义在块作用域或函数原型作用域，必须无链接性。其数组长度在编译期可变，但在运行期该数组对象一旦生成就不可改变量组长度了。例如：数组设计之初是在形式上依赖内存分配而成的，所以必须在使用前预先请求空间。这使得数组有以下特性：因为简单数组强烈倚赖电脑硬件之内存，所以不适用于现代的程序设计。欲使用可变大小、硬件无关性的数据类型，Java等程序设计语言均提供了更高级的数据结构：ArrayList、Vector等动态数组。