大學(xué)《數(shù)據(jù)結(jié)構(gòu)》第二章：線性表-第四節(jié)-順序表和鏈表的比較

1、第四節(jié)順序表和鏈表的比擬一、順序表的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：空間利用率高?？梢詫?shí)現(xiàn)隨機(jī)存取。缺點(diǎn)：插入、刪除操作中要大量移動(dòng)結(jié)點(diǎn)，時(shí)間性能差。需要事先確定順序表的大小，估計(jì)小了會(huì)發(fā)生溢出現(xiàn)象，估計(jì)大了又將造成空間的浪費(fèi)。二、鏈表的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：插入、刪除操作中無(wú)需移動(dòng)結(jié)點(diǎn)，時(shí)間性能好。因?yàn)槭莿?dòng)態(tài)分配存儲(chǔ)空間，所以只要有空閑空間就不會(huì) 發(fā)生溢出現(xiàn)象。缺點(diǎn)：因?yàn)槊總€(gè)結(jié)點(diǎn)都要額外設(shè)置指針域，因此空間利用率低。三、順序表和鏈表比擬通過(guò)上述比擬，可以看出算法的時(shí)間性能與空間性能往往是一對(duì)矛 盾，時(shí)間性能的改善要以犧牲空間性能為代價(jià),反之亦然。因此在實(shí) 際中，要根據(jù)具體情況來(lái)確定采用哪種存儲(chǔ)結(jié)構(gòu)。對(duì)線性表的操作是經(jīng)常性

2、的查找運(yùn)算，以順序表形式存儲(chǔ)為宜。 因?yàn)轫樞虼鎯?chǔ)可以隨機(jī)訪問(wèn)任一結(jié)點(diǎn)，訪問(wèn)每個(gè)結(jié)點(diǎn)的復(fù)雜度均為0 (l)o而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)必須從表頭開(kāi)始沿鏈逐一訪問(wèn)各結(jié)點(diǎn)，其時(shí)間復(fù) 雜度為0 (n)o如果經(jīng)常進(jìn)行的運(yùn)算是插入和刪除運(yùn)算，以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)為宜。 因?yàn)轫樞虮碜鞑迦牒蛣h除操作需要移動(dòng)大量結(jié)點(diǎn)，而鏈?zhǔn)浇Y(jié)構(gòu)只需要 修改相應(yīng)的指針。對(duì)于線性表結(jié)點(diǎn)的存儲(chǔ)密度問(wèn)題，也是選擇存儲(chǔ)結(jié)構(gòu)的一個(gè)重要 依據(jù)。所謂存儲(chǔ)密度就是結(jié)點(diǎn)空間的利用率。它的計(jì)算公式為存儲(chǔ)密度=（結(jié)點(diǎn)數(shù)據(jù)域所占空間）/（整個(gè)結(jié)點(diǎn)所占空間）結(jié)點(diǎn)存儲(chǔ)密度越大，存儲(chǔ)空間的利用率就越高。真題選解（例題填空題）1、鏈表結(jié)點(diǎn)定義如下：typedef struct

3、nodechar data 16 ;struct node *next; LinkStrNode ;如果每個(gè)字符占1個(gè)字節(jié)，指針占4個(gè)字節(jié)，那么該鏈表的存儲(chǔ)密度是隱藏答案【答案】0.8【解析】存儲(chǔ)密度=（結(jié)點(diǎn)數(shù)據(jù)域所占空間）/（整個(gè)結(jié)點(diǎn)所占空 間）=16/（16+4）=0.8。（例題單項(xiàng)選擇題）2、與線性表的順序存儲(chǔ)不相符的特性是（）AA.不便于插入和刪除C.可隨機(jī)訪問(wèn)E.存儲(chǔ)容量固定A.不便于插入和刪除C.可隨機(jī)訪問(wèn)EA.不便于插入和刪除C.可隨機(jī)訪問(wèn)E.存儲(chǔ)容量固定F.需另外開(kāi)辟空間來(lái)保存元素間的關(guān)系隱藏答案【答案】F【解析】線性表的順序存儲(chǔ)是用一片地址連續(xù)的空間來(lái)存放數(shù)據(jù)元 素，其特點(diǎn)是邏輯上相鄰的元素在物理位置上也相鄰，數(shù)據(jù)元素之間 邏輯上的先后關(guān)系自動(dòng)隱含在物理位置的相鄰之中，因此不需要另外開(kāi)辟空間來(lái)保存元素之間的關(guān)系。當(dāng)前講授本章小結(jié)本章著重介紹了線性表在順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上各種運(yùn)算 實(shí)現(xiàn)的算法，并給出了算法的時(shí)間復(fù)雜度的分析。本章是整個(gè)數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，也是考試的重點(diǎn)內(nèi)容，尤其考試大綱 要求：利用順序表和鏈表設(shè)計(jì)算法