|
数组
在計算機科學中，陣列資料結構（英語：array data structure），簡稱数组（英語：Array），是由相同类型的元素（element）的集合所組成的資料結構，分配一块连续的内存来存储。利用元素的索引（index）可以计算出该元素對應的儲存地址。 最簡單的資料結構類型是一維陣列。例如，索引為0到9的32位元(4個位元組)整數陣列，可儲存10個變量，位於記憶體位址2000，2004，2008，...2036中，因此索引為i的元素即在記憶體中的2000+4×i位址。陣列第一個元素的記憶體位址稱為第一位址或基礎位址。 二维数组，对应于數學上的矩陣概念，可表示為二維矩形格。例如：在C语言中表示為 在某些情況下，“向量”一詞也可能代表二维陣列，雖然在數學意義上更確切地稱呼為元组（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。與基於樹實作的資料結構相比，基於陣列實作的資料結構通常是簡單和有空間效率的（隱式資料結構），空間成本開銷很少；但陣列需要修改時則空間的複雜性相對比較差（已排序的陣列結構，與搜索樹相比）。 一或多個大型陣列有時用於模擬程式內的動態記憶體分配，特別是固定記憶區塊規劃。從歷史上看，這有時是可移植地分配“動態記憶體”的唯一方法。 陣列可用於決定程式中的部份或完整控制流程，簡潔地替代多個 元素標識符和定址公式當資料物件儲存在陣列中時，個別物件通常藉由非負整數的索引變數來選取。索引也稱為下標，可將陣列的值對應到儲存物件。 有三種方式對陣列的元素進行索引：
陣列可以具備多個維度，因此常見使用多重索引來存取陣列。例如，從零開始索引的情況下，有三行和四列的二維陣列 指定元素所需的索引數稱為陣列的維度，維數或陣列的秩。 標準陣列中每個索引會被限制在一定範圍內的連續整數（或某些枚舉類型的連續值）， 而元素位址則是對索引值的“線性”計算公式。 一維陣列一維（或單維）陣列是一種線性陣列，其中元素的存取是以行或列索引的單一下標表示。 譬如考慮C編程語言的数组声明语句 語法為： 在上述範例中，被宣告的陣列將包含 對於以線性定址的向量，索引為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]：
例如， 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语言标准中的规定，表达式 数组下标运算符C语言标准中定义，数组下标运算（array subscripting）有两个运算数，一个为到类型type的指针表达式，另一个运算符为整数表达式，结果为类型type。但没有规定两个运算数的先后次序[註 5]。因此，有以下推论：
例如： 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];
}
程式設計數組設計之初是在形式上依賴內存分配而成的，所以必須在使用前預先請求空間。這使得數組有以下特性：
因為簡單數組強烈倚賴電腦硬件之內存，所以不適用於現代的程序設計。欲使用可變大小、硬件無關性的數據類型，Java等程式設計語言均提供了更高級的數據結構：ArrayList、Vector等動態陣列。 注释
参考文献外部連結参见 |
