今天要介紹的主角就是-陣列，陣列也是資料呈線性排列的一種資料結構，與前一節中的鏈表不同，在陣列中，訪問資料十分簡單，而添加和洗掉資料比較耗工夫，這和什么是資料結構那篇文章中講到的姓名按拼音順序排列的電話簿類似，
陣列
如上就是陣列的概念圖，Blue、Yellow、Red 作為資料存盤在陣列中，其中 a 是陣列的名字，后面 [] 中的數字表示該資料是陣列中的第幾個資料，該數字也就是陣列下標，下標從 0 開始計數，比如 Red 就是陣列 a 的第 2 個資料，
那么為什么許多編程語言中的陣列都從 0 開始編號的呢？先別急，可以先自己思考下，將會在文末進行講解，
從圖中可以看出來，陣列的資料是按順序存盤在記憶體的連續空間內的，
由于資料是存盤在連續空間內的，所以每個資料的記憶體地址（在記憶體上的位置）都可以通過陣列下標算出，我們也就可以借此直接訪問目標資料，也就是隨機訪問，
比如現在我們想要訪問 Red，如果是鏈表的話，只能使用指標就只能從頭開始查找，但在陣列中，只需要指定 a[2]，便能直接訪問 Red，
但是，如果想在任意位置上添加或者洗掉資料，陣列的操作就要比鏈表復雜多了，這里我們嘗試將 Green 添加到第 2 個位置上，
首先，在陣列的末尾確保需要增加的存盤空間，
為了給新資料 Green 騰出位置，要把已有資料一個個移開，首先把 Red 往后移，
然后把 Yellow 往后移，
最后在空出來的位置上寫入 Green，
添加資料的操作就完成了，
反過來，如果想要洗掉 Green 呢？
首先，刪掉目標資料 Green，
然后把后面的資料一個個往空位移，先把 Yellow 往前移，
接下來移動 Red，
最后再刪掉多余的空間，這樣一來 Green 便被刪掉了，
補充
這里講解一下對陣列操作所花費的運行時間，假設陣列中有 n 個資料，由于訪問資料時使用的是隨機訪問（通過下標可計算出記憶體地址），所以需要的運行時間僅為恒定的 O（1），
通過陣列下標計算出記憶體地址的尋址公式如下：
a[i]_address = base_address + i * data_type_size
其中 base_address 為記憶體塊的首地址，data_type_size 表示陣列中每個元素的大小，
但另一方面，想要向陣列中添加新資料時，必須把目標位置后面的資料一個個移開，所以，如果在陣列頭部添加資料，就需要 O（n） 的時間，洗掉操作同理，
在鏈表和陣列中，資料都是線性地排成一列，在鏈表中訪問資料較為復雜，添加和洗掉資料較為簡單；而在陣列中訪問資料比較簡單，添加和洗掉資料卻比較復雜，
我們可以根據哪種操作較為頻繁來決定使用哪種資料結構，
最后，讓我們一起來思考下剛開始提到的問題：為什么很多編程語言中陣列都從 0 開始編號？
解惑
從陣列存盤的記憶體模型上來看，“下標”最確切的定義應該是“偏移（offset）”，如果用 a 來表示陣列的首地址，a[0] 就是偏移為 0 的位置，也就是首地址，a[k] 就表示偏移 k 個 type_size 的位置，所以計算 a[k] 的記憶體地址只需要用這個公式：
a[k]_address = base_address + k * type_size
但是，如果陣列從 1 開始計數，那我們計算陣列元素 a[k] 的記憶體地址就會變為：
a[k]_address = base_address + (k-1)*type_size
對比兩個公式，可以發現，從 1 開始編號，每次隨機訪問陣列元素都多了一次減法運算，對于 CPU 來說，就是多了一次減法指令，
陣列作為非常基礎的資料結構，通過下標隨機訪問陣列元素又是其非常基礎的編程操作，效率的優化就要盡可能做到極致，所以為了減少一次減法操作，陣列選擇了從 0 開始編號，而不是從 1 開始，
除此之外還有歷史原因，C 語言設計者用 0 開始計數陣列下標，之后的 Java、JavaScript 等高級語言都效仿了 C 語言，或者說，為了在一定程度上減少 C 語言程式員學習 Java 的學習成本，因此繼續沿用了從 0 開始計數的習慣，實際上，很多語言中陣列也并不是從 0 開始計數的，比如 Matlab，甚至還有一些語言支持負數下標，比如 Python，
總結
這篇文章主要介紹了資料結構中常用的陣列，陣列用一塊連續的記憶體空間，來存盤相同型別的一組資料，最大的特點就是支持隨機訪問，但插入、洗掉操作也因此變得比較低效，平均情況時間復雜度為 O(n)，有一種高效的查找演算法是二分查找法，就是利用了陣列隨機訪問的特性，
總得來說，陣列適用于多操作多、寫操作少的場景，和我們上一篇文章中的鏈表正好相反，
參考
《我的第一本演算法書》
資料結構與演算法之美
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/91947.html
標籤：其他