数组

历史

第一台数字计算器使用机器语言编程来设置和访问数据表，向量和矩阵计算的数组结构，以及许多其它目的。1945年，在创建第一个范纽曼型架构计算器时，约翰·冯·诺伊曼（John von Neumann）写了第一个数组排序程序（合并排序）。数组索引最初是通过自修改代码，后来使用索引寄存器和间接定址来完成的。1960年代设计的一些主机，如Burroughs B5000及其后继者，使用存储器分段来运行硬件中的索引边界检查。
除了机器硬件本身提供的，机器语言并没有特别支持数组。最早的高端编程语言包括FORTRAN（1957）、Lisp（1958）、COBOL（1960）和ALGOL 60（1960），则开始支持多维数组，C（1972）也是如此。在C++（1983）中，对于维度固定和弹性的多维数组，提供了类别模板。

应用

数组实现数学向量和矩阵，以及其它类型的长方表格。许多数据库是由元素为（或包含）记录的一维数组所组成。
数组也用于实现其它数据结构，例如列表、堆、散列表、双向队列、队列、
堆栈、字符串和VLists。与基于树实现的数据结构相比，基于数组实现的数据结构通常是简单和有空间效率的（隐式数据结构），空间成本开销很少；但数组需要修改时则空间的复杂性相对比较差（已排序的数组结构，与搜索树相比）。
一或多个大型数组有时用于模拟程序内的动态存储器分配，特别是固定记忆区块规划。从历史上看，这有时是可移植地分配“动态存储器”的唯一方法。
数组可用于决定程序中的部分或完整控制流程，简洁地替代多个IF语句。它们在上下文中被称为控制表，并与专门构建的解释器结合使用，其控制流将依照数组所含有的值来变动。该数组可能含有指向运行子程序的指针（或由SWITCH语句运行的相关子程序编号）。

一维数组

一维（或单维）数组是一种线性数组，其中元素的访问是以行或列索引的单一下标表示。
譬如考虑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维。
多维数组的数组名字，在表达式中自动转换为数组首元素地址值，但这个首元素实际上是去除数组下标第一维之后的数组剩余部分。例如：
1 int a[10][15];2 int (*p)[15] = a; // a在表达式中自动转换为指向具有15个int的数组的指针值

不完整的数组类型

不完整的数组类型属于不完整类型（incomplete type），即缺乏信息去确定其尺寸。例如：
1 extern int a[];           // 外部变量声明2 void foo(int b[]) {}      // 函数形参3 void bar(int b[][10]) {}  // 多维数组形参4 int a[] = { 10, 20 };     // 初始化

柔性数组成员

C99规定，struct的最后一个成员可以是不完整的数组类型。例如：
1 struct test {2     int a;3     double b;4     char c[];5 };
Visual C++ 2015支持上述语法。

可变长数组

C99引入了可变长数组（variable length array，简称VLA），只能定义在块作用域或函数原型作用域，必须无链接性。其数组长度在编译期可变，但在运行期该数组对象一旦生成就不可改变数组长度了。例如：
1   
2 void foo(int m，int n) {3     int v[m][n];4     int *p[n];5 }