摘要訊息 : 幾乎所有程式設計語言都內建了陣列這個資料結構, 它和向量又有什麼不同?

0. 前言

陣列幾乎是所有程式設計語言的內建資料結構, 和《【資料結構】向量 (順序表)》中的向量不同, 很多語言陣列的大小都是不能改變的. 在本篇文章中, 我們主要討論的是固定大小的陣列, 對於動態大小的陣列, 那就是向量.

更新紀錄 :

• 2022 年 4 月 27 日進行第一次更新和修正.

1. 定義

定義 1. 設有線性表 \boldsymbol {A}_{n} = \left \{ \boldsymbol {\alpha}_{1}, \boldsymbol {\alpha}_{2}, ..., \boldsymbol {\alpha}_{n} \right \}. 若 \boldsymbol {A}_{n} 的大小是固定的, 總有 n 個元素, 那麼我們稱 \boldsymbol {A}_{n} 為陣列 (array).

其實廣義地說, 陣列也算是一種向量, 或者說它歸屬於向量.

定義 2. 對於陣列 \boldsymbol {A} = \left \{ \boldsymbol {A}_{1}, \boldsymbol {A}_{2}, ..., \boldsymbol {A}_{n} \right \}, 如果 \boldsymbol {A}_{i} 也是一個陣列, 那麼我們稱 \boldsymbol {A} 為多維陣列 (multi-dimensional array).

對應地, 如果某個陣列中儲存的是元素, 那麼根據定義 2 稱其為一維陣列; 如果某個陣列中儲存的是陣列, 而儲存的陣列當中儲存的是元素, 那麼根據定義 2 稱其為二維陣列. 對於二維陣列, 如果我們要存取某個元素, 那麼我們需要存取其中一個陣列之後, 再存取其中的元素. 如果一個陣列是 k 維陣列, 那麼我們需要存取到某個元素的話, 需要存取 k - 1 個陣列之後才能獲得那個元素. 對於維度比較低的陣列, 我們可以像上面一樣用文字來描述, 但是對於維度比較高的陣列, 用文字描述過於累贅, 因此我們有必要約定一種記號來表示這個元素. 其實在程式設計中, 我們通常使用陣列注標來存取陣列中的元素.

像 Figure 1 中的陣列, 如果我要存取到 12 這個元素, 那麼在程式設計中我們通常使用 array[1][3] 這樣的形式, 將 [1][3] 影射到具體的元素.

定義 3. 設陣列 \boldsymbol {A} 的維度為 k (k \geq 1), 稱 \displaystyle {\mathop {\mathrm {map}}_{\boldsymbol {A}}(i_{1}, i_{2}, ..., i_{k}) = e} 為陣列 A 的影射函數 (mapping function), 簡記為 A[i_{1}][i_{2}]...[i_{k}] = e. 其中, i_{1}, i_{2}, ..., i_{k} 是某個維度上的陣列索引 (index), i_{j} (j = 1, 2, ..., k) 表示取第 j 個維度上第 i_{j} 個元素.

根據定義 3, 如果想要存取陣列 \boldsymbol {A} 第 3 維度上第 j 個元素, 那麼我們可以寫為 \displaystyle {\mathop {\mathrm {map}}_{\boldsymbol {A}}(3, j) = \boldsymbol {A}[3][j]}.

2. 規範陣列

定義 4. 如果多維陣列 \boldsymbol {A} 在維度 k 上, 所有子陣列中持有的元素數量都相等, 那麼我們稱陣列 \boldsymbol {A} 為規範陣列 (regular array). 類似地, 如果子陣列中持有的元素數量存在不同, 那麼我們稱陣列 \boldsymbol {A} 為不規範陣列 (irregular array).

在 C 和 C++ 中, 所有內建的多維陣列都是規範陣列. 例如我們宣告 int array[5][6];, 那麼 array[0], array[1], array[2], array[3] 和 array[5] 這些子陣列上都有 6 個元素. 如果我們要在 C/C++ 中宣告一個不規範陣列, 則需要借助動態記憶體配置 :

int main(int argc, char *argv[]) {
    constexpr int length[] {6, 3, 4, 2, 7};
    int *irregular_array[sizeof length / sizeof length[0]] {};
    for(auto i {0}; i < sizeof length / sizeof length[0]; ++i) {
        irregular_array[i] = new int[length[i]] {};
    }
    // do something on irregular_array...
    for(auto i {0}; i < sizeof length / sizeof length[0]; ++i) {
        delete[] irregular_array[i];
    }
}

3. 元素排列

在 C/C++ 中, 不論陣列是否是多維的, 一般來說元素在空間中都是線性排列的. 例如陣列 int arr[2][2][3] {{{1, 2, 3}, {2, 3, 4}}, {{5, 6, 7}, {7, 8, 9}}};, 它由兩個二維陣列組成, 即 arr[0] 和 arr[1]. 在理論上, 它應該是這樣排列的 :

但是實際上, 經過編碼器編碼之後, arr 的排列就是 1, 2, 3, 2, 3, 4, 5, 6, 7, 7, 8, 9. 它們在空間上是連續的. 在後面如果要使用這些元素, 編碼器就是通過影射函數來存取的. 此時, 我們可以進一步擴展影射函數, 使得其有能力在線性的排列上存取到正確位置的元素.

3.1 行主次序

像 Figure 2 中那樣, 以行為單位依次將元素排開的方式我們稱為行主次序 (row-dominated order). 對於行主次序排列的 k 維陣列 \boldsymbol {A} 來說, 影射函數可以寫成 \displaystyle {\begin {aligned} &\mathop {\mathrm {map}}_{\boldsymbol {A}}(i_{1}, i_{2}, ..., i_{k}) = (i_{1} - 1) \max \left \{ i_{2} \right \} \max \left \{ i_{3} \right \} ... \max \left \{ i_{k} \right \} + \mathop {\mathrm {map}}_{\boldsymbol {A}[i_{1}]}(i_{2}, i_{3}, ..., i_{k}) \\ &= (i_{1} - 1)\prod \limits_{j = 2}^{k} \max \left \{ i_{j} \right \} + \mathop {\mathrm {map}}_{\boldsymbol {A}[i_{1}]}(i_{2}, i_{3}, ..., i_{k}) \\ &= (i_{1} - 1)\prod \limits_{j = 2}^{k} \max \left \{ i_{j} \right \} + (i_{2} - 1)\prod \limits_{j = 3}^{k} \max \left \{ i_{j} \right \} + \mathop {\mathrm {map}}_{\boldsymbol {A}[i_{1}][i_{2}]}(i_{3}, i_{4}, ..., i_{k}) \\ &= ... \\ &= (i_{1} - 1)\prod \limits_{j = 2}^{k} \max \left \{ i_{j} \right \} + (i_{2} - 1)\prod \limits_{j = 3}^{k} \max \left \{ i_{j} \right \} + ... + (i_{k - 1} - 1)\prod \limits_{j = k}^{k} \max \left \{ i_{j} \right \} + i_{k} \\ &= \sum \limits_{l = 1}^{k - 1}(i_{l} - 1)\prod \limits_{j = l + 1}^{k} \max \left \{ i_{j} \right \} + i_{k}. \end {aligned}} 其中, \max \left \{ i_{j} \right \} 表示第 j 維度上 i_{j} 可以取到的最大值. 這裡要注意的是, 在程式設計中 i_{j} 通常從 0 開始, 但是 i_{j} 在 \mathop {\mathrm {map}}_{\boldsymbol {A}}(i_{1}, i_{2}, ..., i_{k}) 中是從 1 開始的.

例題 1. 設 C++ 陣列 int A[2][2][3] {{{1, 2, 3}, {2, 3, 4}}, {{5, 6, 7}, {7, 8, 9}}} 經過編碼器編碼之後在空間中橫向排列為 1, 2, 3, 2, 3, 4, 5, 6, 7, 7, 8, 9. 寫出 A[1][1][2] 的影射過程.

解 :

由於在 C++ 中陣列注標從 0 開始, 故 A[1][1][2] 實際上對應了 A[2][2][3], 即 \mathop {\mathrm {map}}_{A}(2, 2, 3). 由於 A 在記憶體中以行主次序橫向排列, 故有 \displaystyle {\begin {aligned} \mathop {\mathrm {map}}_{A}(2, 2, 3) &= 1 \times 2 \times 3 + \mathop {\mathrm {map}}_{A[2]}(2, 3) \\ &= 6 + 1 \times 3 + \mathop {\mathrm {map}}_{A[2][2]}(3) \\ &= 6 + 3 + 3 = 12. \end {aligned}}. 因此 A[2][2][3] 實際上對應了橫向排列元素中的第十二個元素, 即 9.

\blacksquare

3.2 列主次序

對於陣列 int arr[2][2][3] {{{1, 2, 3}, {2, 3, 4}}, {{5, 6, 7}, {7, 8, 9}}};, 如果它不是像 Figure 2 那樣橫向排列的, 而是縱向排列的 :

像這樣排列的陣列我們稱為列主次序 (column-dominated order). 對於行主次序排列的 k 維陣列 \boldsymbol {A} 來說, 影射函數可以寫成 \displaystyle {\begin {aligned} &\mathop {\mathrm {map}}_{\boldsymbol {A}}(i_{1}, i_{2}, ..., i_{k}) = (i_{k} - 1)\prod \limits_{j = 1}^{k - 1} \max \left \{ i_{j} \right \} + \mathop {\mathrm {map}}_{\boldsymbol {A}[i_{k}]}(i_{1}, i_{2}, ..., i_{k - 1}) \\ &= (i_{k} - 1)\prod \limits_{j = 1}^{k - 1} \max \left \{ i_{j} \right \} + \mathop {\mathrm {map}}_{\boldsymbol {A}[i_{k - 1}][i_{k}]}(i_{1}, i_{2}, ..., i_{k - 1}) \\ &= ... \\ &= (i_{k} - 1)\prod \limits_{j = 1}^{k - 1} \max \left \{ i_{j} \right \} + (i_{k - 1} - 1)\prod \limits_{j = 1}^{k - 2} \max \left \{ i_{j} \right \} + ... + (i_{2} - 1)\prod \limits_{j = 1}^{1} \max \left \{ i_{j} \right \} + i_{1} \\ &= \sum \limits_{l = 2}^{k}(i_{l} - 1)\prod \limits_{j = 1}^{l - 1} \max \left \{ i_{j} \right \} + i_{1}. \end {aligned}}

3.3 模擬多維陣列

對於現代程式設計語言來說, 無論多麼高維度的陣列, 都會將高維陣列最終展開為一個一維陣列連續存取. 因此, 我們可以通過手動接管編碼器這個工作, 使用一維陣列和相應的影射函數去模擬一個多維陣列.

4. 和陣列有關的演算法

由於陣列中的元素數量是固定的, 即便是多維陣列, 它在某一個維度上的數量也是固定的, 所以陣列不存在插入和移除元素的演算法. 除了這兩個操作之外, 剩下應用於向量的演算法都可以應用在陣列上, 包括搜尋, 字典比較和旋轉. 這些演算法在《【資料結構】向量 (順序表)》中可以找到, 此處不再累贅.

5. 實作

我自己用 C++ 實作了陣列 : https://github.com/Jonny0201/data_structure/blob/master/data_structure/array.hpp, 大家可以參考後自行實作.

大家在看程式碼的時候, 可能會對 array<T, 0> 的樣板特製化產生疑問, 此處我要解釋一下這個樣板偏特製化的作用. 當大家使用樣板進行編碼的時候, 很可能出現 sizeof...(args) == 0 或著樣板引數為 0 的情況. 此時, 如果沒有針對 array<T, 0> 進行特製化, 各個編碼器就會出現不同的表現. Clang 以及 GCC 下可以通過編碼, MSVC 下將會產生編碼錯誤 (因為 Clang 和 GCC 允許陣列的維度為 0). 這個特製化就是為了當上述情況出現的時候, 統一行為防止出現編碼錯誤而設定的. 一般來說, 我們不應該主動使用 array<T, 0>, 這種偏特製化被具現化的情況是第二個樣板參數未知的時候被動產生的. 而且 array<T, 0> 的很多成員函式都是不可用的 (例如 fill 和 swap), 使用它們會產生編碼錯誤.