數據結構 - 數組 - ⎝⎛CodingNote.cc ⎞⎠

數據結構 – 數組

簡介

數組本質上是一種線性表數據結構，它用一組連續的記憶體空間，來存儲一組具有相同類型的數據。

線性表

如上圖所示，線性表就是數據排成一條線一樣的結構，因此每個線性表中的數據只有前後兩個方向。像數組、鏈表、棧、隊列都是線性表結構。

與線性表對應的就是非線性表結構，非線性表中的數據會存在多個方向，數據之間不是簡單的前後關係。像樹、堆都是非線性表結構。

連續的記憶體空間

數組存儲使用的記憶體空間是連續的，在數組存儲的這一片空間只會存儲數組元素，不會再拆分出來存儲其他的數據。

相同類型的數據

在數組的原始定義中，數組只能存儲相同類型的數據，這樣可以保證數組中每個元素佔用的記憶體空間都能保持一致。

正是數組存在「連續的記憶體空間」和「相同類型的數據」這兩個限制，才讓它擁有了隨機存取這個高效的特性，但同時也使得數組在插入、刪除數據的時候會比較低效。

數組的特性

就數組增刪改查的操作而言，數組擁有高效隨機存取的特性，也存在低效插入、刪除的劣勢。

隨機存取

這裡的「隨機存取」指的的是通過下標訪問數組元素，然後對這個元素做存取操作。

電腦會給每個記憶體單元分配一個地址，然後通過地址來訪問記憶體中的數據。當電腦需要隨機訪問數組中的數據時，它可以通過下面的定址公式來計算出對應下標的記憶體地址：

address[i] = base_address + data_type_size * i

其中 base_address 表示數組的起始地址，data_type_size 表示每個元素佔用的空間大小。

可想而知，同時具有「連續的記憶體空間」和「相同類型的數據」兩個限制的數組結構，通過下標查找數組中的元素能達到 \(O(1)\) 的時間複雜度。

插入、刪除

同隨機存儲的高效不同，對一個數組做插入、刪除操作是非常低效的。這裡的低效體現在插入和刪除元素之後，需要對數組中的其他元素做搬移操作，以保證數組元素的連續性。

在一個長度為 n 的數組中，假如要在第 k 個位置插入一個元素，這不是修改元素的操作，不能直接替換掉第 k 個元素，而是需要依次將第 k 個及之後的元素都往後挪一位，然後才能在第 k 個位置上存入這個元素。

數組刪除元素時和插入元素類似，為了避免刪除元素之後導致數組中間出現空洞，需要將刪除位置之後的元素往前挪一位。

通過計算得知，插入、刪除的最好時間複雜度為 \(O(1)\)、最壞時間複雜度為 \(O(n)\)，平均時間複雜度為 \(O(n)\)。

使用上的問題

數組越界

數組可以通過定址公式做到高效隨機訪問，但這並沒有限制使用超出數組長度的下標訪問數組，通常把訪問的數組下標超出數組長度的情況稱為數組越界。

在 C 語言中，編譯器不會檢測出數組越界的問題，如果出現數組越界的情況而又沒處理的話，極可能出現如程式碼進入死循環等不可預知的情況。

int main(int argc, char* argv[]){
    int i = 0;
    int arr[3] = {0};
    for(; i<=3; i++){
        arr[i] = 0;
        printf("hello world\n");
    }
    return 0;
}

如上述程式碼，在位元組對齊和分配記憶體的特性下，先後定義了 i 和 arr 共佔據了 8 個位元組，表現為 {arr[0], arr[1], arr[2], i} 的形式，當循環到下標為 3 時，實際 arr[3] 指向的就是 i 所在地址，也就出現 arr[3] = i = 3，出現死循環。

相比較下，使用 Java 會更加安全，Java 不會把檢查數組越界的工作丟給程式設計師來做，其本身就會做越界檢查，如果出現錯誤則會拋出 java.lang.ArrayIndexOutOfBoundsException 異常，而不是出現死循環。

容器和數組的選擇

這裡說的容器指的是封裝了數組的操作方法、並且支援動態擴容的容器類，比如 Java 中的 ArrayList 類。

與原生數組相比，ArrayList 擁有非常大的優勢，但並不是所有地方都必須使用 ArrayList 而不使用數組，在某些地方使用數組更方便、效率更高。以下情況可以選擇原生數組：

追求極致性能選擇原生數組。Java 的 ArrayList 不支援存儲基本類型，而是存儲基本類型封裝後的對象，自動裝箱、拆箱會有一定的性能消耗
操作簡單，僅使用原生功能選擇原生數組。雖然 ArrayList 提供了非常多額外的功能，但也額外增加了風險，使用原生數組更簡單便捷

為什麼數組從 0 開始編號

這個問題可以通過數組的定址公式來回答。

首先需要重新定義數組下標：下標不是只數組的第幾個元素，而是指數組元素的偏移。

在使用時，使用 0 作為起始下標，數組使用下述的表達式作為定址公式：

address[i] = base_address + data_type_size * i

如果使用 1 作為起始下標，將不能直接使用上面的定址公式，而是需要修改如下：

address[i] = base_address + data_type_size * (i - 1)

在對比前後兩個定址公式之後，可以發現，使用 1 作為起始下標的定址公式會比使用 0 作為起始下標的定址公式多一個簡單的減法指令。

對於非常底層的程式來說，即使只是多出一個簡單的減法指令，也是一種性能的損耗，為了做到極致優化，選擇 0 作為起始下標會更好。

當然還有一個歷史原因，C 語言使用了 0 作為數組的起始下標，後續 Java、JavaScript 都紛紛仿效，這也算是為了統一，降低程式設計師的學習成本。

Tags: 數據結構數據結構與演算法