陣列

在電腦科學中，陣列資料結構可以計算出該元素對應的儲存地址。最簡單的資料結構型別是一維陣列。例如，索引為0到9的32位元整數陣列，可作為在記憶體位址2000，2004，2008，...2036中，儲存10個變數，因此索引為i的元素即在記憶體中的2000+4×i位址。陣列第一個元素的記憶體位址稱為第一位址或基礎位址。二維陣列，對應於數學上的矩陣概念，可表示為二維矩形格。例如：formula_1在C語言中表示為int a[3][3] = ;。在某些情況下，“向量”一詞也可能代表二維陣列，雖然在數學意義上更確切地稱呼為元組，而不是向量。但需要注意的是：計算機科學的某些領域，如Matlab，元組是指類似C語言struct型別，具有固定的往往是不同型別的資料成員的資料結構。陣列通常用於實作資料庫的表格，特別是查詢表；表格有時也被當作是陣列的同義詞。陣列是最早期和最重要的資料結構之一，很多程式都會用到陣列。它們也用於實作許多其他資料結構，譬如列表，經常會針對陣列操作進行最佳化。因為在程式執行時可以計算元素的索引，陣列是很有用的。此外，也能以單一迭代語句就處理陣列的許多元素。為此，陣列資料結構的元素必須具有相同的大小，而且應該使用相同的資料型別表示。陣列一詞通常用於表示陣列資料型別，一種大多數高階程式語言都會內建的資料型別。陣列型別通常由陣列結構來實作；然而在某些語言中，它們可以由雜湊表、連結串列、搜尋樹或其它資料結構來實現。在演演算法的描述中，陣列一詞特別著重意義為關聯陣列或“抽象的陣列”，一種理論上的電腦科學模型，專注於陣列的基本性質上。歷史.第一臺數位計算機使用機器語言程式設計來設定和訪問資料表，向量和矩陣計算的陣列結構，以及許多其它目的。1945年，在建立第一個範紐曼型架構計算機時，約翰·馮·諾伊曼。陣列索引最初是透過自修改程式碼，後來使用索引暫存器和間接定址來完成的。1960年代設計的一些主機，如Burroughs B5000及其後繼者，使用記憶體分段來執行硬體中的索引邊界檢查。除了機器硬體本身提供的，機器語言並沒有特別支援陣列。最早的高階程式語言包括FORTRAN中，對於維度固定和彈性的多維陣列，提供了類別模板。應用.陣列實作數學向量和矩陣，以及其它型別的長方表格。許多資料庫是由元素為記錄的一維陣列所組成。陣列也用於實作其它資料結構，例如列表、堆積、雜湊表、雙向佇列、佇列、堆疊、字串和VLists。與基於樹實作的資料結構相比，基於陣列實作的資料結構通常是簡單和有空間效率的。一或多個大型陣列有時用於模擬程式內的動態記憶體分配，特別是固定記憶區塊規劃。從歷史上看，這有時是可移植地分配“動態記憶體”的唯一方法。陣列可用於決定程式中的部份或完整控制流程，簡潔地替代多個codice_1語句。它們在上下文中被稱為控制表，並與專門構建的直譯器結合使用，其控制流將依照陣列所含有的值來變動。該陣列可能含有指向執行子程式的指標。元素識別符號和定址公式.當資料物件儲存在陣列中時，個別物件通常藉由非負整數的索引變數來選取。索引也稱為下標，可將陣列的值對應到儲存物件。有三種方式對陣列的元素進行索引：陣列可以具備多個維度，因此常見使用多重索引來存取陣列。例如，從零開始索引的情況下，有三行和四列的二維陣列codice_3需要存取第二行和第四列的元素時，表示式可為codice_4。因此，二維陣列使用兩個索引下標，三維陣列使用三個索引下標，n維陣列使用n個索引下標。指定元素所需的索引數稱為陣列的維度，維數或陣列的秩。標準陣列中每個索引會被限制在一定範圍內的連續整數，而元素位址則是對索引值的“線性”計算公式。一維陣列.一維陣列是一種線性陣列，其中元素的存取是以行或列索引的單一下標表示。譬如考慮C程式語言的陣列宣告語句codice_5語法為：datatype anArrayName [sizeofArray];在上述範例中，被宣告的陣列將包含codice_6型別的10個元素，可為任何整數值。這樣，陣列元素的索引下標則為0-9。例如，codice_7和codice_8分別是第一個和最後一個元素的表達。對於以線性定址的向量，索引為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++陣列概念有雙重含義，一是資料型別，二是實體。C語言標準中規定，一個數組型別描述了連續分配的非空的具有特定元素物件型別的物件集合。這些元素物件的型別稱為元素型別。陣列型別由元素型別與元素的數目確定。在C語言中，可以顯式定義一個數組型別，例如：typedef int myArrayType [101];陣列名作為陣列實體的識別符號，具有特殊性，不同於整型、浮點型、指標型或結構型別等變數識別符號。這是因為陣列是一組元素的聚集，不能把一個聚集看作一個值直接讀出。因此，陣列名作為左值、右值，在C語言標準中都有特殊規定：例如，char s[] = "hello";int main() {char (*p1)[6] = &amp;s; // OK!char (*p2)[6] = s; // compile error: cannot convert 'char*' to 'char (*)[6]'char *p3 = &amp;s; // compile error: cannot convert 'char (*)[6]' to 'char*' in initialization根據上述C語言標準中的規定，表示式codice_11的值的型別是char (*)[6]，即指向整個陣列的指標；而表示式 s 則被隱式轉換為指向陣列首元素的指標值，即 char* 型別。同理，表示式codice_12，等效於表示式codice_13。陣列下標運算子.C語言標準中定義，陣列下標運算有兩個運算數，一個為到型別type的指標表示式，另一個運算子為整數表示式，結果為型別type。但沒有規定兩個運算數的先後次序。因此，有以下推論：例如：int a[10], *p = a;p[0] = 10;(p + 1)[0] = 20;0[p + 1] = 10;不完整的陣列型別.不完整的陣列型別屬於不完整型別，即缺乏資訊去確定其尺寸。例如：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引入了可變長陣列，只能定義在塊作用域或函式原型作用域，必須無連結性。其陣列長度在編譯期可變，但在執行期該陣列物件一旦生成就不可改變陣列長度了。例如：void foo(int m，int n) {int v[m][n];int *p[n];程式設計.陣列設計之初是在形式上依賴記憶體分配而成的，所以必須在使用前預先請求空間。這使得陣列有以下特性：因為簡單陣列強烈倚賴電腦硬體之記憶體，所以不適用於現代的程式設計。欲使用可變大小、硬體無關性的資料型別，Java等程式設計語言均提供了更高階的資料結構：ArrayList、Vector等動態陣列。