熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構之順序表和鏈表的比較[2]

2013-11-15 15:07:54  來源: 數據結構 

  鏈表的優缺點基本上與順序表是相反在實際應用中選取哪種存儲結構應根據實際情況在存儲和操作上進行權衡考慮

  基於存儲的考慮

  順序表的存儲空間是靜態分配的在程序執行之前必須明確規定它的存儲規模也就是說事先對MAXSIZE要有合適的設定過大造成浪費過小造成溢出如果對線性表的長度或存儲規模難以估計時不宜采用順序表;鏈表不用事先估計存儲規模但鏈表的存儲密度較低(存儲密度是指一個結點中數據元素所占的存儲單元和整個結點所占的存儲單元之比)

  基於操作的考慮

  在順序表中按序號訪問元素的時間性能為O()而鏈表中按序號訪問的時間性能是O(n)所以如果經常做的運算是按序號訪問數據元素顯然順序表優於鏈表;而在順序表中做插入刪除時需移動元素當數據元素的信息量較多且表較長時這一點是不應忽視的;在鏈表中作插入刪除雖然也要找插入位置但主要是比較操作從這個角度考慮顯然鏈表較優

  基於開發語言的考慮

  順序表容易實現任何高級語言中都有數組類型鏈表的操作是基於指針的有些語言不支持指針類型並且相對指針來講順序表較簡單

  總之兩種存儲結構各有長短選擇那一種存儲方式應由實際問題決定通常較穩定的線性表選擇順序存儲而頻繁做插入刪除的即動態性較強的線性表宜選擇鏈式存儲

[]  []  


From:http://tw.wingwit.com/Article/program/sjjg/201311/22892.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.