數據結構學習 2–數組
數據結構學習系列第二篇–數組
數組
數組是一個最基礎而且常見的數據結構，幾乎每種編程語言都有。
如何實現隨機訪問
數組的定義：
數組(Array)是一種線性表數據結構。它用一組連續的內存空間，來存儲一組具有相同類型的數據。
這裡指出了數組的三個特點：
- 線性表(Linear List)
- 連續的內存空間
- 存儲相同類型數據
首先，線性表就是數據排成一條線一樣的結構，每個線性表最多只有前後兩個方向，線性表結構如下圖所示，數組、鏈表、隊列和棧都屬於這種結構。
和線性表對立的就是非線性表，比如二叉樹、堆、圖等，它們不僅僅是簡單的前後關係，如下圖所示：
接着就是需要連續內存空間和保存相同類型的數據。這兩個特點讓數組有一個非常好的特性：隨機訪問。也就是根據下標訪問數組的時間複雜度是 O(1) ，但問題就是插入和刪除需要 O(n)，因為需要進行大量的數據移動操作。
那麼數組是如何實現隨機訪問的操作的呢？
首先，給定一個長度為 10 的 int 類型的數組 a[10] ，計算機會分配一塊存儲空間，這裡假設就是 1000~1039 ，其中內存塊的首地址是 base_address=1000，如下圖所示
計算機給每個內存單元分配一個地址，然後通過地址訪問內存中的數據。因此，這裡如果需要隨機訪問數組的某個元素，同樣也是根據地址訪問，也就是首先需要找到該元素存儲所在的地址，尋址公式如下所示：
a[i]_address = base_address + i * data_type_size
data_type_size 表示數組每個元素的大小，這裡 int 類型是 4 個位元組。
注意，對於數組來說，它支持隨機訪問，根據下標隨機訪問的時間複雜度是 O(1) ，但查找時間複雜度並非是 O(1) , 因為即便排好序的數值，通過二分查找，時間複雜度是 O(logn) 。
低效的插入和刪除
數組的插入和刪除操作由於其內存數據的連續性問題，這兩個操作會非常低效，那麼為什麼會導致低效，有哪些改進方法呢？
插入操作
假設數組長度是 n ，現在需要將一個數據插入到數組的第 k 位置，如果需要執行這樣的操作，需要將第 k 到 n 位置上的元素都按順序往後移動一位。這個操作的時間複雜度是多少呢？
最好的情況，就是末尾插入元素，這樣不需要移動，O(1) 複雜度；最壞的情況，數組開頭就插入元素，那麼就是 O(n) 的時間複雜度。平均情況時間複雜度則如下所示，每個位置插入元素概率是相同的：
$$
\frac{1+2+\cdots+n}{n}=O(n)
$$
當然，如果數組是有序的，就需要按照上述做法移動元素。如果數組無序呢，一個快速的方法就是僅移動目標位置的元素，即第 k 個位置的元素放到數組末尾，然後插入元素即可，這樣時間複雜度就是 O(1)。
一個簡單的例子如下圖所示，數組有 5 個元素：a,b,c,d,e，現在希望在第三個位置插入新元素 x，此時可以直接將 c 放到末尾，即 a[5] = a[2]，然後 a[2]=x，即可完成操作。
這種特殊的處理技巧，可以在特定場景下(比如數組無序)將插入元素的時間複雜度降到 O(1)。
刪除操作
和插入數據類似，刪除第 k 個位置元素，同樣需要將後續的元素往前移動。
- 最好的情況是刪除末尾數據，
O(1)； - 最壞就是刪除開頭的元素，
O(n)； - 平均情況時間複雜度也是
O(n)。
同樣在某些特定場景下，並不需要時刻追求數組中數組的連續性，可以將多次刪除操作集中在一起進行操作。
如下圖所示是一個長度為 10 的數組，存儲了 8 個元素，`現在是需要依次刪除前三個元素，a，b，c。如果每次刪除操作都將所有元素往前移動，那麼後續的 5 個元素總共需要移動 3 次，為了避免這個情況，我們可以先記錄被刪除的數據，每次操作僅僅記錄那個位置的元素被刪除。當數組沒有空間存儲數據時，再進行一次真正的刪除操作，這樣可以避免刪除操作導致的數據搬移。
這個做法其實就是 Java 中 JVM 標記清除垃圾回收算法的核心思想。
所以，我們對於數據結構和算法的學習，不應該只是死記硬背，而是需要了解它背後的思想和處理技巧，明白為什麼需要這種數據結構和這種算法。
數組的越界問題
首先來看一段 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;
}
這段代碼的問題就是打印結果的時候，因為循環結束條件問題，會無限打印 “hello world”，給定的數組長度是 3， 但是循環結束條件是 i<=3 ，而 a[3] 其實就是訪問越界了。
但是，在 C 語言中，只要不是訪問受限的內存，所有的內存空間都是可以自由訪問的。也就是說，a[3] 也是可以訪問的，但是會定位到非數組所在的內存上，而這個地址正好是存儲變量 i 的內存地址，也就是 a[3]=0 就相當於 i=0 ，最終導致代碼的無限循環。
數組越界在 C 語言中是一種未決行為，沒有規定這種情況編譯器應該如何處理，所以通常會出現各種奇怪的邏輯錯誤。
不過，其他編程語言並不會將數組越界的工作丟給程序員來做，它們會有做越界的檢查。
數組索引從0開始的原因
大多數的編程語言中，數組，或者說數據結構，索引都是從 0 開始，而不是從 1 開始。
首先，從數組存儲的內存模型上看，索引，或者說「下標」最確切的定義應該是偏移(offset)。
前面介紹了數組的尋址公式：
a[i]_address = base_address + i * data_type_size
如果數組是從 1 開始計數，那麼尋址公式就會為：
a[i]_address = base_address + (i-1) * data_type_size
對比兩個公式，可以知道每次訪問數組元素，從 1 開始計數的方式會多一次減法運算，相當於讓 CPU 多一次減法指令，但隨即訪問數組元素應該是非常基礎的操作，需要儘可能高效，因此，為了減少一次減法操作，數組採用從 0 開始計數，而非從 1 開始。
其次，主要是 C 語言設計者用 0 開始計數，後續的編程語言，如 Java 等都效仿了 C 語言，這也是方便 C 語言程序員學習其他語言的學習成本。當然，像 Python 還支持負數下標。
參考
極客時間的數據結構與算法之美課程
