比較順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)

1、1、試比較順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)的優(yōu)缺點。在什么情況下用順序表比鏈表好?答： 順序存儲時，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲單元的地址必須是連續(xù)的。優(yōu)點：存儲密度大（二1）,存儲空間利用率高。缺點：插入或刪除元素時不方便。鏈式存儲時，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結(jié)點值， 另一部分存放表示結(jié)點間關系的指針優(yōu)點：插入或刪除元素時很方便，使用靈活。缺點：存儲密度小（1），存儲空間利用率低。順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動態(tài)操作。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較

2、大，且其主要操作是插入、刪除操作，則采用鏈表。順序表與鏈表的比較基于空間的比較存儲分配的方式順序表的存儲空間是靜態(tài)分配的鏈表的存儲空間是動態(tài)分配的存儲密度=結(jié)點數(shù)據(jù)本身所占的存儲量/結(jié)點結(jié)構(gòu)所占的存儲總量順序表的存儲密度=1鏈表的存儲密度 < 1基于時間的比較存取方式順序表可以隨機存取，也可以順序存取鏈表是順序存取的插入/ 刪除時移動元素個數(shù)順序表平均需要移動近一半元素鏈表不需要移動元素，只需要修改指針順序表和鏈表的比較順序表和鏈表各有短長。在實際應用中究竟選用哪一種存儲結(jié)構(gòu)呢？這要根據(jù)具體問 題的要求和性質(zhì)來決定。通常有以下幾方面的考慮 ：鏈表順序表I基丨分丨靜態(tài)分配。程序執(zhí)行之前必須

3、明確丨動態(tài)分配只要內(nèi)存空間尚有空閑，1I于丨配丨規(guī)定存儲規(guī)模。若線性表長度 n變丨就不會產(chǎn)生溢出。因此，當線性表|I空丨方丨化較大，則存儲規(guī)模難于預先確定丨的長度變化較大，難以估計其存儲II間丨式丨估計過大將造成空間浪費，估計太丨規(guī)模時，以采用動態(tài)鏈表作為存儲II考I I小又將使空間溢出機會增多。I結(jié)構(gòu)為好。I 慮一I11I I存I為1。當線性表的長度變化不大，I <1I I儲I易于事先確定其大小時，為了節(jié)約II I密I存儲空間，宜采用順序表作為存儲II I度I結(jié)構(gòu)。II基I存I隨機存取結(jié)構(gòu)，對表中任一結(jié)點都I順序存取結(jié)構(gòu)，鏈表中的結(jié)點，需II于I取I可在0( 1)時間內(nèi)直接取得I從頭指

4、針起順著鏈掃描才能取得。II時I方I線性表的操作主要是進行查找，很II間I法I少做插入和刪除操作時，采用順序II考II表做存儲結(jié)構(gòu)為宜。II丨插丨在順序表中進行插入和刪除，平均丨在鏈表中的任何位置上進行插入和丨I I入I要移動表中近一半的結(jié)點，尤其是I刪除，都只需要修改指針。對于頻II I刪I當每個結(jié)點的信息量較大時，移動I繁進行插入和刪除的線性表，宜采II I除I結(jié)點的時間開銷就相當可觀。I用鏈表做存儲結(jié)構(gòu)。若表的插入和III操II刪除主要發(fā)生在表的首尾兩端，貝UIII作II采用尾指針表示的單循環(huán)鏈表為宜I為什么在單循環(huán)鏈表中設置尾指針比設置頭指針更好？答：尾指針是指向終端結(jié)點的指針，用它來表示單循環(huán)鏈表可以使得查找鏈表的開始結(jié)點和終端結(jié)點都很方便，設一帶頭結(jié)點的單循環(huán)鏈表，其尾指針為rear，則開始結(jié)點和終端結(jié)點的位置分別是rear->next->next和rear,查找時間都是0(1)。若用頭指針來表示該鏈表，則查找終端結(jié)點的時間為0(n)。在鏈表中設置頭結(jié)點有什么好處？頭結(jié)點即在鏈表的首元結(jié)點之前附設的一個結(jié)點，該結(jié)