前言：本篇文章只是記錄王爭的數(shù)據(jù)結(jié)構(gòu)與算法之美的學(xué)習(xí)筆記，寫下來能強迫自己系統(tǒng)的再過一遍，加深理解。這門課以實際開發(fā)中遇到的問題為例，引入解決問題涉及到的的數(shù)據(jù)結(jié)構(gòu)和算法，但不會講的太細，最好結(jié)合一本實體書進行學(xué)習(xí)。

大部分編程語言中，數(shù)組都是從 0 開始的，為什么數(shù)組要從 0 開始編號，而不是從 1 開始呢？

1. 相關(guān)定義

數(shù)組(Array)是一種線性表數(shù)據(jù)結(jié)構(gòu)，用一組連續(xù)的內(nèi)存空間，來存儲一組具有相同類型的數(shù)據(jù)。

線性表：
線性表就是數(shù)據(jù)排成一條線一樣的結(jié)構(gòu)，每個線性表上的數(shù)據(jù)最多只有前和后兩個方向，比如鏈表、隊列、棧等。

image.jpeg

非線性表：
比如二叉樹、堆、圖等，數(shù)據(jù)之間并不是簡單的前后關(guān)系。

image.jpeg

數(shù)組具有連續(xù)的內(nèi)存空間和相同類型數(shù)據(jù)的特點，這兩個特點讓數(shù)組可以進行”隨機訪問“。相對應(yīng)的是這也限制了數(shù)組的很多操作變得比較低效，比如數(shù)組中刪除、插入一個數(shù)據(jù)，為了保證連續(xù)性，之后的數(shù)據(jù)都要相應(yīng)的進行搬移。

2. 數(shù)組如何根據(jù)下標訪問數(shù)組元素

以int[] a = new int[10]來舉例，在下圖中，計算機給數(shù)組 a[10]分配了一塊連續(xù)內(nèi)存空間 1000~1039，其中，內(nèi)存的首地址為 base_address = 1000，如下：

image.jpeg

計算機會給每個內(nèi)存單元分配一個地址，計算機就是通過地址來訪問內(nèi)存中的數(shù)據(jù)。那么數(shù)組中元素存儲的內(nèi)存地址就需要通過下面的尋址公式計算得出了：

a[I]_address = base_address + i * data_type_size(每個元素的大小，這里為 4 字節(jié))

注意：數(shù)組適合查找操作，但并不是說查找的時間復(fù)雜度為 O(1)。因為即便是排好的數(shù)組，用二分查找，時間復(fù)雜度也是 O(logn)。
正確表述：數(shù)組支持隨機訪問，根據(jù)下標隨機訪問的時間復(fù)雜度為 O(1)。

3. 插入和刪除操作

3.1 插入操作

舉例一個數(shù)組長度為 n，現(xiàn)在將一個數(shù)據(jù)插入到第 k 個位置，為了把第 k 個位置騰出來，需要將k~n這部分的元素都順序的往后挪一位。這樣操作的平均時間復(fù)雜度為 O(n)，最好的情況是在最后的位置插入，時間復(fù)雜度為 O(1)，最壞的情況是在開頭插入，時間復(fù)雜度為 O(n)。

如果數(shù)組中的數(shù)據(jù)是有序的，在插入操作時，必須按照剛才的方法去搬移數(shù)據(jù)。但是如果數(shù)組中存儲的數(shù)據(jù)并沒有任何規(guī)律，數(shù)組只是被當(dāng)做一個存儲數(shù)據(jù)的集合，這種情況下，為了避免大規(guī)模的數(shù)據(jù)搬移，有一個簡單的辦法，就是將k位的數(shù)據(jù)放到數(shù)組的最后，把新元素放到第 k 個位置。

比如 a[10] 中存儲了 5 個元素：a b c d e，我們需要將 x 插入到第三個位置，那么按照上面的辦法，我們可以將 c 放到 a[5]，然后將 a[2]賦值為 x，如下圖：

image.jpeg

利用這種處理技巧，在特定場景下，在第 k 個位置插入一個元素的時間復(fù)雜度就會降為 O(1)。

3.2 刪除操作

比如要刪除指定位置的數(shù)據(jù)，為了內(nèi)存的連續(xù)性，跟插入操作一樣，也需要搬運數(shù)據(jù)，時間復(fù)雜度類似。

實際上，在一些特殊場景下，我們并不一定非得追求數(shù)組中數(shù)據(jù)的連續(xù)性。可以將多次刪除操作集中在一起執(zhí)行，這樣刪除的效率會提高很多。

4. 數(shù)組的訪問越界問題

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;
}

這段代碼會無限打印 hello world，是因為當(dāng) i = 3 時，數(shù)組 a[3]訪問越界。
在 C 語言中，只要不是訪問受限的內(nèi)存，所有內(nèi)存都是可以自由訪問的，根據(jù)之前講的數(shù)組尋址公式，a[3]也會被定位到某塊不屬于數(shù)組的內(nèi)存地址上（i 和 數(shù)組先后被壓入棧中），而這個地址正好是存儲變量 i 的內(nèi)存地址，所以 a[3] = 0，相當(dāng)于i = 0，導(dǎo)致代碼無限循環(huán)。

數(shù)組越界在 C 語言中是一種未決行為，并沒有規(guī)定數(shù)組訪問越界時編譯器應(yīng)該如何處理。

訪問數(shù)組的本質(zhì)就是訪問一段連續(xù)的內(nèi)存，只要數(shù)組通過偏移計算得到的內(nèi)存地址是可用的，那么程序可能不會報任何錯誤。

5. 容器類

容器類將數(shù)組的很多操作封裝起來，使用更方便，另外，支持動態(tài)擴容，一般我們用這個容器足夠了，但是在追求極致性能的時候，還是使用數(shù)組。

6. 數(shù)組為什么要從 0 開始編號？

歷史原因，C 語言設(shè)計者用 0 開始計數(shù)數(shù)組下標，之后的 Java、JavaScript 等高級語言都效仿了 C 語言，或者說，為了在一定程度上減少 C 語言程序員學(xué)習(xí) Java 的學(xué)習(xí)成本，因此繼續(xù)沿用了從 0 開始計數(shù)的習(xí)慣。

從數(shù)組存儲的內(nèi)存模型上看，“下標”最確切的定義應(yīng)該是“偏移”。如果數(shù)組從 1 開始計數(shù)，那么隨機訪問數(shù)組都需要先進行一次減 1 運算，對于 CPU 來說，多了一次減法指令，耗費性能。

7. 練習(xí)操作

• 數(shù)組基本操作：
  指定位置插入元素，后面其他元素后移
  指定位置刪除元素，后面其他元素前移

• 合并兩個有序數(shù)組

• 兩數(shù)之和