2011年軟考程序員考試復(fù)習(xí)筆試知識(shí)點(diǎn)整理(7)

　　11、數(shù)組和鏈表的優(yōu)缺點(diǎn)

　　數(shù)組，在內(nèi)存上給出了連續(xù)的空間。鏈表，內(nèi)存地址上可以是不連續(xù)的，每個(gè)鏈表的節(jié)點(diǎn)包括原來(lái)的內(nèi)存和下一個(gè)節(jié)點(diǎn)的信息(單向的一個(gè)，雙向鏈表的話，會(huì)有兩個(gè))。

　　數(shù)組優(yōu)于鏈表的:

　　A. 內(nèi)存空間占用的少，因?yàn)殒湵砉?jié)點(diǎn)會(huì)附加上一塊或兩塊下一個(gè)節(jié)點(diǎn)的信息。

　　但是數(shù)組在建立時(shí)就固定了。所以也有可能會(huì)因?yàn)榻�立的�?shù)組過(guò)大或不足引起內(nèi)存上的問(wèn)題。

　　B. 數(shù)組內(nèi)的數(shù)據(jù)可隨機(jī)訪問(wèn)，但鏈表不具備隨機(jī)訪問(wèn)性。這個(gè)很容易理解，數(shù)組在內(nèi)存里是連續(xù)的空間，比如如果一個(gè)數(shù)組地址從100到200，且每個(gè)元素占用兩個(gè)字節(jié)，那么100-200之間的任何一個(gè)偶數(shù)都是數(shù)組元素的地址，可以直接訪問(wèn)。

　　鏈表在內(nèi)存地址可能是分散的。所以必須通過(guò)上一節(jié)點(diǎn)中的信息找能找到下一個(gè)節(jié)點(diǎn)。

　　C. 查找速度上。這個(gè)也是因?yàn)閮?nèi)存地址的連續(xù)性的問(wèn)題，不羅索了。

　　鏈表優(yōu)于數(shù)組的:

　　A. 插入與刪除的操作。如果數(shù)組的中間插入一個(gè)元素，那么這個(gè)元素后的所有元素的內(nèi)存地址都要往后移動(dòng)。刪除的話同理。只有對(duì)數(shù)據(jù)的最后一個(gè)元素進(jìn)行插入刪除操作時(shí)，才比較快。鏈表只需要更改有必要更改的節(jié)點(diǎn)內(nèi)的節(jié)點(diǎn)信息就夠了。并不需要更改節(jié)點(diǎn)的內(nèi)存地址。

　　B. 內(nèi)存地址的利用率方面。不管你內(nèi)存里還有多少空間，如果沒(méi)辦法一次性給出數(shù)組所需的要空間，那就會(huì)提示內(nèi)存不足，磁盤(pán)空間整理的原因之一在這里。而鏈表可以是分散的空間地址。

　　C. 鏈表的擴(kuò)展性比數(shù)組好。因?yàn)橐粋�(gè)數(shù)組建立后所占用的空間大小就是固定的，如果滿了就沒(méi)法擴(kuò)展，只能新建一個(gè)更大空間的數(shù)組;而鏈表不是固定的，可以很方便的擴(kuò)展。

　　相關(guān)推薦：

　　軟考程序員考試歷年真題重點(diǎn)題總結(jié)及答案

　　2011年上半年軟考報(bào)名時(shí)間及方式匯總

　　軟考程序員考試歷年真題匯總(2007年-2010年)