數(shù)組定義
數(shù)組是一種線性表數(shù)據(jù)結(jié)構(gòu)。它用一組連續(xù)的內(nèi)存空間，來存儲一組具有相同類型的數(shù)據(jù)。
線性表
線性表就是數(shù)據(jù)排成一條線一樣的結(jié)構(gòu)。每個線性表上的數(shù)據(jù)最多只有前和后兩個方向。數(shù)組、鏈表、隊(duì)列、棧等也是線性表。而像樹、堆、圖就是非線形
連續(xù)內(nèi)存空間和相同的數(shù)據(jù)類型
正是有了連續(xù)內(nèi)存空間和相同的數(shù)據(jù)類型，才能“隨機(jī)訪問”。如下圖每個元素的內(nèi)存地址a[i]_address = base_address + i * data_type_size。
低效的刪除和插入操作
也是因?yàn)檫B續(xù)內(nèi)存空間的限制，數(shù)組的刪除和插入效率相對比較低
1.刪除
比如數(shù)組a[n]。要刪除第i位的元素，就必須把i+1～n-1位的統(tǒng)一向前移動一位。最好情況i就是最后一位，不需要移動元素時(shí)間復(fù)雜度為O(1)。如果不幸i就是第0個元素，那么n-1個元素需要移動，時(shí)間復(fù)雜度為O(n)。平均時(shí)間復(fù)雜度為(0+1+2+...+n-1)/n = O(n)
2.插入
比如數(shù)組a[n]。要在第i位要插入元素，就必須把i~n-1位統(tǒng)一向后移動一位。最好的情況i就在數(shù)組末尾，不需要移動任何元素時(shí)間復(fù)雜度為O(1)。最壞的情況是i為0在數(shù)組第一位，需要移動n個元素時(shí)間復(fù)雜度為O(n)。平均時(shí)間復(fù)雜度(1+2+...+n)/n = O(n)
容器
數(shù)組因?yàn)樘崆胺峙鋬?nèi)存的特點(diǎn)長度必須是固定的，對于業(yè)務(wù)開發(fā)人員來說很不靈活，因?yàn)楹芏嗲闆r下在定義變量并不能精確的知道數(shù)據(jù)量的多少。為了方便很多編程語言提供了容器。比如go中的切片。這樣的容器雖然方便的業(yè)務(wù)開發(fā)，但是他的底層依然用的是數(shù)組，當(dāng)切片的長度大于底層數(shù)組長度，就需要重新開辟一塊更大的連續(xù)空間。先copy再重新賦值。這個過程內(nèi)存的申請和銷毀，也是需要一定的時(shí)間（雖然這個在業(yè)務(wù)開發(fā)層面幾乎感覺不到）。所以對于可以確定長度的情況下，還是建議使用數(shù)組替代容器。效率可能會高。
為什么大多數(shù)編程語言數(shù)組從0開始編號
1.數(shù)組下標(biāo)可以其實(shí)就是距離首地址的偏移量，其實(shí)a[0]就是數(shù)組的首地址?；氐缴线呎f的數(shù)組每個元素的內(nèi)存訪問地址a[i]_address = base_address + i * data_type_size。如果編號從1開始公式就變成了a[i]_address = base_address + （i-1) * data_type_size。多了一次計(jì)算
2.應(yīng)該一開始c語言就是從0開始為了減少開發(fā)的學(xué)習(xí)成本，以后語言多采用從0開始。
