程序猿修仙之路--數(shù)據(jù)結(jié)構(gòu)之你是否真的懂數(shù)組？

但凡IT江湖俠士，算法與數(shù)據(jù)結(jié)構(gòu)為必修之課。早有前輩已經(jīng)明確指出：程序=算法+數(shù)據(jù)結(jié)構(gòu) 。要想在之后的江湖歷練中通關(guān)，數(shù)據(jù)結(jié)構(gòu)必不可少。數(shù)據(jù)結(jié)構(gòu)與算法相輔相成，亦是陰陽互補之法。

成都創(chuàng)新互聯(lián)主要從事網(wǎng)站制作、網(wǎng)站設計、網(wǎng)頁設計、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務。立足成都服務大興安嶺,10余年網(wǎng)站建設經(jīng)驗,價格優(yōu)惠、服務專業(yè),歡迎來電咨詢建站服務:028-86922220

開篇

說道數(shù)組，幾乎每個IT江湖人士都不陌生，甚至過半人還會很自信覺的它很簡單。
的確，在菜菜所知道的編程語言中幾乎都會有數(shù)組的影子。不過它不僅僅是一種基礎的數(shù)據(jù)類型，更是一種基礎的數(shù)據(jù)結(jié)構(gòu)。如果你覺的對數(shù)組足夠了解，那能不能回答一下：

• 數(shù)組的本質(zhì)定義？
• 數(shù)組的內(nèi)存結(jié)構(gòu)？
• 數(shù)組有什么優(yōu)勢？
• 數(shù)組有什么劣勢？
• 數(shù)組的應用場景？
• 數(shù)組為什么大部分都從0開始編號？
• 數(shù)組能否用其他容器來代替，例如c#中的List<T>？

定義

百科

所謂數(shù)組，是相同的元素序列。數(shù)組是在程序設計中，為了處理方便，把具有相同類型的若干元素按無序的形式組織起來的一種形式。

正如以上所述，數(shù)組在應用上屬于數(shù)據(jù)的容器。不過我還是要補充兩點：

1. 數(shù)組在數(shù)據(jù)結(jié)構(gòu)范疇屬于一種線性結(jié)構(gòu)，也就是只有前置節(jié)點和后續(xù)節(jié)點的數(shù)據(jù)結(jié)構(gòu)，除數(shù)組之外，像我們平時所用的隊列，棧，鏈表等也都屬于線性結(jié)構(gòu)。
   

有線性結(jié)構(gòu)當然就有非線性結(jié)構(gòu)，比如之后我們要介紹的二叉樹，圖 等等，這里不再展開~~~

2. 數(shù)組元素在內(nèi)存分配上是連續(xù)的。這一點對于數(shù)組這種數(shù)據(jù)結(jié)構(gòu)來說非常重要，甚至可以說是它最大的“殺手锏”。下邊會有更詳細的介紹。

優(yōu)勢和劣勢

優(yōu)勢

我相信所有人在使用數(shù)組的時候都知道數(shù)組可以按照下標來訪問，例如 array[1] 。作為一種最基礎的數(shù)據(jù)結(jié)構(gòu)是什么使數(shù)組具有這樣的隨機訪問方式呢？天性聰慧的你可能已經(jīng)想到了：內(nèi)存連續(xù)+相同數(shù)據(jù)類型。
現(xiàn)在我們抽象一下數(shù)據(jù)在內(nèi)存上分配的情景。

• 說到數(shù)組按下標訪問，不得不說一下大多數(shù)人的一個“誤解”：數(shù)組適合查找元素。為什么說是誤解呢,是因為這種說法不夠準確，準確的說數(shù)組適合按下標來查找元素，而且按照下標查找元素的時間復雜度是O(1)。為什么呢？我們知道要訪問數(shù)組的元素需要知道元素在內(nèi)存中對應的內(nèi)存地址，而數(shù)組指向的內(nèi)存的地址為首元素的地址，即：array[0]。由于數(shù)組的每個元素都是相同的類型，每個類型占用的字節(jié)數(shù)系統(tǒng)是知道的，所以要想訪問一個數(shù)組的元素，按照下標查找可以抽象為：

  array[n]=array[0]+size*n

以上是元素地址的運算，其中size為每個元素的大小，如果為int類型數(shù)據(jù)，那size就為4個字節(jié)。其實確切的說，n的本質(zhì)是一個離首元素的偏移量，所以array[n]就是距離首元素n個偏移量的元素，因此計算array[n]的內(nèi)存地址只需以上公式。

論證一下，如果下標從1開始計算，那array[n]的內(nèi)存地址計算公式就會變?yōu)椋?/p>

array[n]=array[0]+size*(n-1)

對比很容易發(fā)現(xiàn)，從1開始編號比從0開始編號每次獲取內(nèi)存地址都多了一次 減法運算，也就多了一次cpu指令的運行。這也是數(shù)組從0下標開始訪問一個原因。

其實還有一種可能性，那就是所有現(xiàn)代編程語言的鼻祖：C語言，它是從0開始計數(shù)下標的，所以現(xiàn)在所有衍生出來的后代語言也就延續(xù)了這個傳統(tǒng)。雖然不符合人類的思想，但是符合計算機的原理。當然也有一些語言可以設置為不從下標0開始計算，這里不再展開，有興趣的可以去搜索一下。

• 由于數(shù)組的連續(xù)性，所以在遍歷數(shù)組的時候非?？?，不僅得益于數(shù)組的連續(xù)性，另外也得益于cpu的緩存，因為cpu讀取緩存只能讀取連續(xù)內(nèi)存的內(nèi)容，所以數(shù)組的連續(xù)性正好符合cpu緩存的指令原理，要知道cpu緩存的速度要比內(nèi)存的速度快上很多。

劣勢

1. 由于數(shù)組在內(nèi)存排列上是連續(xù)的，而且要保持這種連續(xù)性，所以當增加一個元素或刪除一個元素的時候，為了保證連續(xù)性，需要做大量元素的移動工作。
   舉個栗子：要在數(shù)組頭部插入一個新元素，為了在頭部騰出位置，所有的元素都要后移一位，假設元素個數(shù)為n，這就導致了時間復雜度為O（n）的一次操作，當然如果是在數(shù)組末尾插入新元素，其他所有元素都不必移動，操作的時間復雜度為O（1）。

當然這里有一個技巧：如果你的業(yè)務要求并不是數(shù)組連續(xù)有序的，當在位置k插入元素的時候，只需要把k元素轉(zhuǎn)移到數(shù)組末尾，新元素插入到k位置即可。當然仔細沉思一下這種業(yè)務場景可能性太小了，數(shù)組都可以無序，我直接插入末尾即可，沒有必要非得在k位置插入把。~~

當然還有一個特殊場景：如果是多次連續(xù)的k位置插入操作，我們完全可以合并為一次“批量插入”操作：把k之后的元素整體移動sum（插入次數(shù)）個位置，無需一個個位置移動，把三次操作的時間復雜度合并為一次。

與插入對應的就有刪除操作，同理，刪除操作數(shù)組為了保持連續(xù)性，也需要元素的移動。

綜上所述，數(shù)組在添加和刪除元素的場景下劣勢比較明顯，所以在具體業(yè)務場景下應該避免頻繁添加和刪除的操作。

2. 數(shù)組的連續(xù)性就要求創(chuàng)建數(shù)組的時候，內(nèi)存必須有相應大小的連續(xù)區(qū)塊，如果不存在，數(shù)組就有可能出現(xiàn)創(chuàng)建失敗的現(xiàn)象。在某些高級語言中（比如c#，golang，java）就有可能引發(fā)一次GC（垃圾回收）操作，GC操作在系統(tǒng)運行中是非常昂貴的，有的語言甚至會掛起所有線程的操作，對外的表現(xiàn)就是“暫停服務”。
3. 數(shù)組要求所有元素為同一個類型。在存儲數(shù)據(jù)維度，它可能算是一種劣勢，但是為了按照下標快速查找元素，業(yè)務中這也是一種優(yōu)勢。仁者見仁智者見智而已。
4. 數(shù)組是長度固定的數(shù)據(jù)結(jié)構(gòu)，所以在原始數(shù)組的基礎上擴容是不可能的，有的語言可能實現(xiàn)數(shù)組的“偽擴容”，為什么說是“偽”呢，因為原理其實是創(chuàng)建了一個容量更大的數(shù)組來存放原數(shù)組元素，發(fā)生了數(shù)據(jù)復制的過程，只不過對于調(diào)用者而已透明而已。
5. 數(shù)組有訪問越界的可能。我們按照下標訪問數(shù)組的時候如果下標超出了數(shù)組長度，在現(xiàn)代多數(shù)高級語言中，直接就會引發(fā)異常了，但是一些低級語言比如C 有可能會訪問到數(shù)組元素以外的數(shù)據(jù)，因為要訪問的內(nèi)存地址確實存在。

其他

1. 很多編程語言中你會發(fā)現(xiàn)“純數(shù)組”并沒有提供直接刪除元素的方法（例如：c#，golang），而是需要將數(shù)組轉(zhuǎn)化為另一種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)數(shù)組元素的刪除。比如在golang種可以轉(zhuǎn)化為slice。這也驗證了數(shù)組的不變性。

應用場景

我們學習的每個數(shù)據(jù)結(jié)構(gòu)其實都有對應的適合場景，只不過是場景多少的問題，具體什么時候用，需要我們對該數(shù)據(jù)結(jié)構(gòu)的特性做深入分析。
關(guān)于數(shù)組的特性，通過以上介紹可以知道最大的一個亮點就是按照下標訪問，那有沒有具體業(yè)務映射這種特性呢？

1. 相信很多IT人士都遇到過會員機制，每個會員到達一定的經(jīng)驗值就會升級，怎么判斷當前的經(jīng)驗是否到達升級條件呢？我們是不是可以這樣做：比如當前會員等級為3，判斷是否到達等級4的經(jīng)驗值，只需要array[4]的值判斷即可，大多數(shù)人把配置放到DB，資源耗費太嚴重。也有的人放到其他容器緩存。但是大部分場景下查詢的時間復雜度要比數(shù)組大很多。
2. 在分布式底層應用中，我們會有利用一致性哈希方案來解決每個請求交給哪個服務器去處理的場景。有興趣的同學可以自己去研究一下。其中有一個環(huán)節(jié)：根據(jù)哈希值查找對應的服務器，這是典型的讀多寫少的應用，而且比較偏底層。如果用其他數(shù)據(jù)結(jié)構(gòu)來解決大量的查找問題，可能會觸碰到性能的瓶頸。而數(shù)據(jù)按下標訪問時間復雜度為O(1)的特性，使得數(shù)組在類似這些應用中非常廣泛。

---

添加關(guān)注，查看更精美版本，收獲更多精彩

網(wǎng)站題目：程序猿修仙之路--數(shù)據(jù)結(jié)構(gòu)之你是否真的懂數(shù)組？
文章分享：http://bm7419.com/article32/goccsc.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供App開發(fā)、全網(wǎng)營銷推廣、建站公司、企業(yè)建站、品牌網(wǎng)站建設、網(wǎng)站內(nèi)鏈

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)