線性表順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)的比較

《線性表順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)的比較》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、線性表順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)的比較存儲(chǔ)位置、存儲(chǔ)空間順序表的特點(diǎn)是邏輯上相鄰的數(shù)據(jù)元素，物理存儲(chǔ)位置也相鄰，并且，順序表的存儲(chǔ)空間需要預(yù)先分配。在鏈表中邏輯上相鄰的數(shù)據(jù)元素，物理存儲(chǔ)位置不一定相鄰，它使用指針實(shí)現(xiàn)元素之間的邏輯關(guān)系。并且，鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配的。優(yōu)缺點(diǎn)比較順序表優(yōu)點(diǎn)：（1）方法簡(jiǎn)單，各種高級(jí)語(yǔ)言中都有數(shù)組，容易實(shí)現(xiàn)。（2）不用為表示節(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲(chǔ)開(kāi)銷。（3）順序表具有按元素序號(hào)隨機(jī)訪問(wèn)的特點(diǎn)。鏈表優(yōu)點(diǎn)：插入、刪除運(yùn)算方便。順序表缺點(diǎn)：（1）在順序表中做插入、刪除操作時(shí)，平均移動(dòng)表中的一半元素，因此對(duì)n較大的順序表效率

2、低。（2）需要預(yù)先分配足夠大的存儲(chǔ)空間，估計(jì)過(guò)大，可能會(huì)導(dǎo)致順序表后部大量閑置；預(yù)先分配過(guò)小，又會(huì)造成溢出。鏈表缺點(diǎn)：（1）要占用額外的存儲(chǔ)空間存儲(chǔ)元素之間的關(guān)系，存儲(chǔ)密度降低。存儲(chǔ)密度是指一個(gè)節(jié)點(diǎn)中數(shù)據(jù)元素所占的存儲(chǔ)單元和整個(gè)節(jié)點(diǎn)所占的存儲(chǔ)單元之比。（2）鏈表不是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)，不能隨機(jī)存取元素實(shí)踐應(yīng)用（1）順序表的存儲(chǔ)空間是靜態(tài)分配的，在程序執(zhí)行之前必須明確規(guī)定它的存儲(chǔ)規(guī)模，也就是說(shuō)事先對(duì)“MaxSize”要有合適的設(shè)定，設(shè)定過(guò)大會(huì)造成存儲(chǔ)空間的浪費(fèi)，過(guò)小造成溢出。因此，當(dāng)對(duì)線性表的長(zhǎng)度或存儲(chǔ)規(guī)模難以估計(jì)時(shí)，不宜采用順序表。然而，鏈表的動(dòng)態(tài)分配

3、則可以克服這個(gè)缺點(diǎn)。鏈表不需要預(yù)留存儲(chǔ)空間，也不需要知道表長(zhǎng)如何變化，只要內(nèi)存空間尚有空閑，就可以再程序運(yùn)行時(shí)隨時(shí)地動(dòng)態(tài)分配空間，不需要時(shí)還可以動(dòng)態(tài)回收。因此，當(dāng)線性表的長(zhǎng)度變化較大或者難以估計(jì)其存儲(chǔ)規(guī)模時(shí)，宜采用動(dòng)態(tài)鏈表作為存儲(chǔ)結(jié)構(gòu)。但在鏈表中，除數(shù)據(jù)域外還需要在每個(gè)節(jié)點(diǎn)上附加指針。如果節(jié)點(diǎn)的數(shù)據(jù)占據(jù)的空間小，則鏈表的結(jié)構(gòu)性開(kāi)銷就占去了整個(gè)存儲(chǔ)空間的大部分。當(dāng)順序表被填滿時(shí)，則沒(méi)有結(jié)構(gòu)開(kāi)銷。在這種情況下，順序表的空間效率更高。由于設(shè)置指針域額外地開(kāi)銷了一定的存儲(chǔ)空間，從存儲(chǔ)密度的角度來(lái)講，鏈表的存儲(chǔ)密度小于1.因此，當(dāng)線性表的長(zhǎng)度變化不大而且事先容

4、易確定其大小時(shí)，為節(jié)省存儲(chǔ)空間，則采用順序表作為存儲(chǔ)結(jié)構(gòu)比較適宜?；谶\(yùn)算的考慮（時(shí)間）順序存儲(chǔ)是一種隨機(jī)存取的結(jié)構(gòu)，而鏈表則是一種順序存取結(jié)構(gòu)，因此它們對(duì)各種操作有完全不同的算法和時(shí)間復(fù)雜度。例如，要查找線性表中的第i個(gè)元素，對(duì)于順序表可以直接計(jì)算出a(i)的的地址，不用去查找，其時(shí)間復(fù)雜度為0(1).而鏈表必須從鏈表頭開(kāi)始，依次向后查找，平均需要0(n)的時(shí)間。所以，如果經(jīng)常做的運(yùn)算是按序號(hào)訪問(wèn)數(shù)據(jù)元素，顯然順表優(yōu)于鏈表。反之，在順序表中做插入，刪除時(shí)平均移動(dòng)表中一半的元素，當(dāng)數(shù)據(jù)元素的信息量較大而且表比較長(zhǎng)時(shí)，這一點(diǎn)是不應(yīng)忽視的；在鏈表中作插入

5、、刪除，雖然要找插入位置，但操作是比較操作，從這個(gè)角度考慮顯然后者優(yōu)于前者?；诃h(huán)境的考慮（語(yǔ)言）順序表容易實(shí)現(xiàn)，任何高級(jí)語(yǔ)言中都有數(shù)組類型；鏈表的操作是基于指針的。相對(duì)來(lái)講前者簡(jiǎn)單些，也用戶考慮的一個(gè)因素。總之，兩種存儲(chǔ)結(jié)構(gòu)各有長(zhǎng)短，選擇哪一種由實(shí)際問(wèn)題中的主要因素決定。通?！拜^穩(wěn)定”的線性表，即主要操作是查找操作的線性表，適于選擇順序存儲(chǔ)；而頻繁做插入刪除運(yùn)算的（即動(dòng)態(tài)性比較強(qiáng)）的線性表適宜選擇鏈?zhǔn)酱鎯?chǔ)。謝謝觀看！