在本章介紹了線性表的邏輯結構及它的兩種存儲結構：順序表和鏈表。通過對它們的討論可知它們各有優缺點，順序存儲有三個優點：
(1) 方法簡單，各種高級語言中都有數組，容易實現。
(2) 不用為表示結點間的邏輯關系而增加額外的存儲開銷。
(3) 順序表具有按元素序號隨機訪問的特點。
但它也有兩個缺點：
(1) 在順序表中做插入刪除操作時，平均移動大約表中一半的元素，因此對n較大的順序表效率低。
(2) 需要預先分配足夠大的存儲空間，估計過大，可能會導致順序表后部大量閑置；預先分配過小，又會造成溢出。
鏈表的優缺點恰好與順序表相反。在實際中怎樣選取存儲結構呢？通常有以下幾點考慮：
１．基于存儲的考慮
順序表的存儲空間是靜態分配的，在程序執行之前必須明確規定它的存儲規模，也就是說事先對＂MAXSIZE＂要有合適的設定，過大造成浪費，過小造成溢出?？梢妼€性表的長度或存儲規模難以估計時，不宜采用順序表；鏈表不用事先估計存儲規模，但鏈表的存儲密度較低，存儲密度是指一個結點中數據元素所占的存儲單元和整個結點所占的存儲單元之比。顯然鏈式存儲結構的存儲密度是小于１的。
２．基于運算的考慮
在順序表中按序號訪問ai的時間性能時O(1)，而鏈表中按序號訪問的時間性能O(n)，所以如果經常做的運算是按序號訪問數據元素，顯然順序表優于鏈表；而在順序表中做插入、刪除時平均移動表中一半的元素，當數據元素的信息量較大且表較長時，這一點是不應忽視的；在鏈表中作插入、刪除，雖然也要找插入位置，但操作主要是比較操作，從這個角度考慮顯然后者優于前者。
３．基于環境的考慮
順序表容易實現，任何高級語言中都有數組類型，鏈表的操作是基于指針的，相對來講前者簡單些，也是用戶考慮的一個因素。
總之，兩中存儲結構各有長短，選擇那一種由實際問題中的主要因素決定。通常“較穩定”的線性表選擇順序存儲，而頻繁做插入刪除的即動態性較強的線性表宜選擇鏈式存儲。
posted on 2007-08-01 09:15
★yesjoy★ 閱讀(4812)
評論(0) 編輯 收藏 所屬分類:
數據結構