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