2011年軟考程序員考試復習筆試知識點整理(7)

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

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

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

　　A. 內(nèi)存空間占用的少，因為鏈表節(jié)點會附加上一塊或兩塊下一個節(jié)點的信息。

　　但是數(shù)組在建立時就固定了。所以也有可能會因為建立的數(shù)組過大或不足引起內(nèi)存上的問題。

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

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

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

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

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

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

　　C. 鏈表的擴展性比數(shù)組好。因為一個數(shù)組建立后所占用的空間大小就是固定的，如果滿了就沒法擴展，只能新建一個更大空間的數(shù)組;而鏈表不是固定的，可以很方便的擴展。

　　相關推薦：

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

　　2011年上半年軟考報名時間及方式匯總

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