什么是數(shù)組？

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

第二個(gè)是連續(xù)的內(nèi)存空間和相同類型的數(shù)據(jù)。

優(yōu)點(diǎn)：兩限制使得具有隨機(jī)訪問(wèn)的特性缺點(diǎn)：刪除，插入數(shù)據(jù)效率低

什么是線性表結(jié)構(gòu)

線性表就是數(shù)據(jù)排成像一條線一樣的結(jié)構(gòu)。每個(gè)線性表上的數(shù)據(jù)最多只有前和后兩個(gè)方向。其實(shí)除了數(shù)組，鏈表、隊(duì)列、棧等也是線性表結(jié)構(gòu)。

非線性表，比如二叉樹(shù)、堆、圖等。之所以叫非線性，是因?yàn)?，在非線性表中，數(shù)據(jù)之間并不是簡(jiǎn)單的前后關(guān)系。

如何實(shí)現(xiàn)根據(jù)下標(biāo)隨機(jī)訪問(wèn)數(shù)組元素的嗎？

a[i]_address = base_address + i * data_type_size

base_address 內(nèi)存塊的首地址

data_type_size表示數(shù)組中每個(gè)元素的大小

數(shù)組的復(fù)雜度？

鏈表適合插入、刪除，時(shí)間復(fù)雜度O(1)；數(shù)組支持隨機(jī)訪問(wèn)，根據(jù)下標(biāo)隨機(jī)訪問(wèn)的時(shí)間復(fù)雜度為O(1)。

為什么數(shù)據(jù)需要從0開(kāi)始呢？

1. 存儲(chǔ)的內(nèi)存模型上來(lái)看，下標(biāo)”最確切的定義應(yīng)該是“偏移（offset）；a[0]就是偏移為0的位置，也就是首地址；如果從1開(kāi)始，計(jì)算的時(shí)候需要多做一次減法操作；效率的優(yōu)化不夠極致

2. 歷史的原因；C語(yǔ)言設(shè)計(jì)者用0開(kāi)始計(jì)數(shù)數(shù)組下標(biāo)，降低學(xué)習(xí)成本

如果數(shù)組從1開(kāi)始計(jì)數(shù)，那我們計(jì)算數(shù)組元素a[k]的內(nèi)存地址就會(huì)變?yōu)椋?/p>

a[k]_address = base_address + (k-1)*type_size

對(duì)比兩個(gè)公式，我們不難發(fā)現(xiàn)，從1開(kāi)始編號(hào)，每次隨機(jī)訪問(wèn)數(shù)組元素都多了一次減法運(yùn)算，對(duì)于CPU來(lái)說(shuō)，就是多了一次減法指令。