在計(jì)算機(jī)的世界中挑势，數(shù)據(jù)可以有各種各樣的組織形式，比如啦鸣，模擬現(xiàn)實(shí)中排隊(duì)取錢(qián)的隊(duì)列潮饱，代表復(fù)雜的社交網(wǎng)絡(luò)的圖結(jié)構(gòu)等，不同的數(shù)據(jù)結(jié)構(gòu)各自適應(yīng)不同的情況诫给。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)香拉，我們能夠?yàn)槲覀円鉀Q的問(wèn)題，選擇合適的數(shù)據(jù)結(jié)構(gòu)進(jìn)行數(shù)據(jù)存儲(chǔ)中狂，從而使得程序更加高效凫碌。
數(shù)組
數(shù)組，是數(shù)據(jù)結(jié)構(gòu)中最簡(jiǎn)單胃榕，也最常用的一個(gè)數(shù)據(jù)結(jié)構(gòu)盛险。所謂數(shù)組，是有序的元素序列勋又。若將有限個(gè)類(lèi)型相同的變量>苦掘，那么這個(gè)名稱(chēng)為數(shù)組名。組成數(shù)組的各個(gè)變量稱(chēng)為數(shù)組的分量楔壤，也稱(chēng)為數(shù)組的元素鹤啡，有時(shí)也稱(chēng)為下標(biāo)變量。用于區(qū)分?jǐn)?shù)組的各個(gè)元素的數(shù)字編號(hào)稱(chēng)為下標(biāo)蹲嚣。數(shù)組是在程序設(shè)計(jì)中递瑰，為了處理方便， 把具有相同類(lèi)型的若干元素按無(wú)序的形式組織起來(lái)的一種形式端铛。這些無(wú)序排列的同類(lèi)數(shù)據(jù)元素的集合稱(chēng)為數(shù)組泣矛。
查找元素
數(shù)組是一個(gè)順序存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)疲眷，如圖所示是一個(gè)長(zhǎng)度為10的數(shù)組禾蚕，它的特點(diǎn)是存取速度快。通過(guò)指定下標(biāo)狂丝，我們可以很快的取值换淆。比如a[0],a[5]等操作哗总，都可以在O(1)時(shí)間內(nèi)完成。然而倍试，如果我們并不提前知道元素所在的位置的呢讯屈？假如我們要查找的元素為100，偽代碼表示如下
for(int i=0;i<n;i++){
if(a[i]==100){
return i;//返回元素所在下標(biāo)
}
}
return -1;//如果遍歷完都沒(méi)有找到县习，則返回-1.
最好情況下涮母，100在a[0]的位置，一下子就能找到躁愿，最壞情況下叛本，100在數(shù)組的最后面，甚至是不存在彤钟，則需要遍歷整個(gè)數(shù)組来候。****所以在數(shù)組中查找元素的時(shí)間復(fù)雜度為O(n)。
插入元素
如果我們要在數(shù)組中插入一個(gè)新的元素逸雹，根據(jù)插入位置的不同营搅，效率也有所不同。以上圖為例梆砸，如果要插入的位置在a[5]转质，那么直接a[5]=x就好。如果要插入的位置在a[0]呢帖世？就需要將所有的元素往后移動(dòng)一格峭拘，再把a(bǔ)[0]賦值為x。把所有元素往后移動(dòng)一格的時(shí)間復(fù)雜度為O(n)狮暑，所以在數(shù)組中插入新元素時(shí)鸡挠，時(shí)間復(fù)雜度為O(n)。其偽代碼如下：
for(i=n;i>=insert_index;i--){//從后往前遍歷到插入位置之后搬男，把前面的數(shù)賦值給后面的數(shù)
a[i]=a[i-1];
}
a[i]=x;//跳出循環(huán)后拣展，i剛好位于插入位置，直接賦值新插入的元素缔逛。
a.length = a.length+1;
刪除元素
除了新增备埃，刪除也是同理。如果要?jiǎng)h除a[4]位置的99褐奴，直接把a(bǔ).length減少1就好按脚。在計(jì)算機(jī)中，通常刪除一個(gè)東西敦冬，并不是真的要去刪除它辅搬，而是不再去管理它，再也訪問(wèn)不到它脖旱，就當(dāng)做刪除了堪遂。而如果是刪除a[1]處的90介蛉，除了將a.length減1之外，還需要將a[2]到a[4]的數(shù)據(jù)往前移一格溶褪，變?yōu)閍[1]到a[3]币旧，把插入位置后的所有元素前移一格的時(shí)間復(fù)雜度為O(n)。所以數(shù)組刪除元素時(shí)猿妈，時(shí)間復(fù)雜度為O(n)吹菱。
for(i=delete_index-1;i<n-1;i++){//從刪除位置開(kāi)始，用后面一個(gè)位置的值覆蓋前面的值彭则。
a[i]=a[i+1];
}
a.length = a.length - 1;
總結(jié)
時(shí)間復(fù)雜度：訪問(wèn)元素O(1)毁葱，查找元素O(n)，插入元素O(n)贰剥，刪除元素O(n)
優(yōu)點(diǎn)****：連續(xù)存儲(chǔ)倾剿，具有在O(1)時(shí)間內(nèi)隨機(jī)存取的特性。
缺點(diǎn)：沒(méi)有用到的空間被浪費(fèi)了蚌成。
公眾號(hào)：萌凱的程序人生
一枚IT研究生前痘，致力于分享自己的學(xué)習(xí)經(jīng)歷和總結(jié)！
喜歡的話(huà)請(qǐng)點(diǎn)贊關(guān)注担忧，謝謝您芹缔！
