什么是數(shù)組护蝶？
- 數(shù)組（Array）是一種<u>線性表</u>數(shù)據(jù)結(jié)構(gòu)。它用一組<u>連續(xù)的內(nèi)存空間</u>翩迈，來存儲一組具有相同類型的數(shù)據(jù)
- 線性表：數(shù)據(jù)排成像一條線一樣的結(jié)構(gòu)（數(shù)組持灰、鏈表、隊(duì)列负饲、棧）
- 連續(xù)的內(nèi)存空間和相同的數(shù)據(jù)類型：因?yàn)檫@兩個(gè)限制堤魁，數(shù)組有“隨機(jī)訪問”的特性，但是讓數(shù)組的很多操作變得低效返十，如 刪除妥泉、插入，為了保證連續(xù)性洞坑，需要大量數(shù)據(jù)搬遷
非線性表 ：數(shù)據(jù)之間并不是簡單的前后關(guān)系盲链，如 二叉樹、堆迟杂、圖等
訪問數(shù)組元素的原理
如 一個(gè)長度為10 的 int 類型數(shù)組
Java：int[] a = new int[10]刽沾，分配了一塊連續(xù)內(nèi)存空間 1000～1039（Java 的 int 的長度為 4 字節(jié)），內(nèi)存首地址為 base_address=1000
Go: var a:=[10]int{1,2,3,4,5,6,7,8,9,10} 排拷，分配一塊連續(xù)內(nèi)存空間 32位系統(tǒng)下 1000～1039侧漓，64位系統(tǒng)下 1000～1079 （Go 的 int 的長度是根據(jù)系統(tǒng)位數(shù)來決定的，32位系統(tǒng)是4字節(jié)监氢，64位系統(tǒng)是8字節(jié)）
尋址公式：
<pre class="cm-s-default" style="color: rgb(89, 89, 89); margin: 0px; padding: 0px; background: none 0% 0% / auto repeat scroll padding-box border-box rgba(0, 0, 0, 0);">a[i]_address = base_address + i * data_type_size</pre>
data_type_size 是int類型字節(jié)大小
低效的“插入”和“刪除”
插入
有序數(shù)組
- 往數(shù)組插入一個(gè)數(shù)據(jù)到 K 位置布蔗，為了給第 K 個(gè)位置騰出來給新數(shù)據(jù)藤违，需要將第 K～N這部分的數(shù)據(jù)順序的往后挪一位，時(shí)間復(fù)雜度為 O(n)
- 如果在末尾插入元素纵揍，不需要移動數(shù)據(jù)纺弊，時(shí)間復(fù)雜度為 O(1)
- 如果在數(shù)據(jù)開頭插入元素，那所有的數(shù)據(jù)都要依次往后挪一位骡男，所以最壞時(shí)間復(fù)雜度為O(n)
- 因?yàn)樵诿總€(gè)位置插入元素的概率是一樣的，所以平均時(shí)間復(fù)雜度為(1+2+...+n)/n=O(n)
無序數(shù)組
- 往數(shù)組插入一個(gè)數(shù)據(jù)到 K 位置傍睹，可以把 K 位置的數(shù)據(jù)搬到數(shù)組元素的最后隔盛，把新的元素直接放入到 K 位置
刪除
刪除第 K 個(gè)位置的數(shù)據(jù)，為了內(nèi)存的連續(xù)性拾稳，需要搬移數(shù)據(jù)吮炕，不然中間會出現(xiàn)空洞，內(nèi)存就不連續(xù)了
特殊場景下访得，并不一定非要追求數(shù)組中數(shù)據(jù)的連續(xù)性龙亲。如果將多次刪除操作集中在一起執(zhí)行，刪除效率會提高
為了避免d,e,f,g,h被多次搬移悍抑，可以先記錄下已經(jīng)被刪除的數(shù)據(jù)鳄炉。每次的刪除操作并不是真正的搬移數(shù)據(jù)，只是記錄數(shù)據(jù)已經(jīng)被刪除搜骡。讓數(shù)組沒有更多的空間存儲數(shù)據(jù)時(shí)拂盯，再出發(fā)執(zhí)行一次真正的刪除操作，這樣就減少了刪除操作導(dǎo)致的數(shù)據(jù)搬移记靡。
數(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;
}
運(yùn)行代碼會無限打印“ hello world”谈竿，因?yàn)閿?shù)組大小為3，a[0],a[1],a[2]摸吠，for 循環(huán)條件寫錯(cuò) i<=3,當(dāng)i=3時(shí)空凸，數(shù)組a[3]訪問越界
在C中，只要不是訪問受限的內(nèi)存寸痢，所有的內(nèi)存空間都是可以自由訪問的呀洲，所以，根據(jù)數(shù)組尋址公式轿腺，a[3]也會被定位到某塊不屬于數(shù)組的內(nèi)存地址上两嘴，而這個(gè)地址正好是存儲變量 i 的內(nèi)存地址，那么 a[3]=0 就相當(dāng)于 i=0族壳，所以會導(dǎo)致代碼無限循環(huán)（函數(shù)體內(nèi)的局部變量存在棧上憔辫，且是連續(xù)壓棧。在Linux進(jìn)程的內(nèi)存布局中仿荆，棧區(qū)在高地址空間贰您，從高向低增長坏平。變量i和arr在相鄰地址，且i比arr的地址大锦亦，所以arr越界正好訪問到i舶替。當(dāng)然，前提是i和arr元素同類型杠园，否則那段代碼仍是未決行為顾瞪。）<u>操作系統(tǒng)或計(jì)算機(jī)體系結(jié)構(gòu)的教材應(yīng)該會講到</u>
數(shù)組越界在 C 語言中是一種未決行為，并沒有規(guī)定數(shù)組訪問越界時(shí)編譯器應(yīng)該如何處理抛蚁。因?yàn)槌滦眩L問數(shù)組的本質(zhì)就是訪問一段連續(xù)內(nèi)存，只要數(shù)組通過偏移計(jì)算得到的內(nèi)存地址是可用的瞧甩，那么程序就可能不會報(bào)任何錯(cuò)誤钉跷。
數(shù)組優(yōu)化
- 支持動態(tài)擴(kuò)容
- 事先指定數(shù)據(jù)大小
為什么大多數(shù)編程語言數(shù)組要從 0 開始編號
- 為了性能
- 如果從0開始編號， a[k]_address = base_address + k * type_size
- 如果從1開始編號肚逸， a[k]_address = base_address + (k-1) * type_size
從 1 開始編號每次隨機(jī)訪問對CPU來說都會多一次減法運(yùn)算爷辙，數(shù)組作為非常基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)朦促，通過下標(biāo)是非诚チ溃基礎(chǔ)的操作，效率的優(yōu)化得做到極致务冕，所以為了減少一次減法操作玷犹，數(shù)組選擇了從0開始編號
還有一種說法是C設(shè)計(jì)用 0 開始計(jì)數(shù)數(shù)組下標(biāo)，之后的語言為了降低學(xué)習(xí)成本洒疚，所以沿用了數(shù)組下標(biāo)從0開始計(jì)數(shù)歹颓。
