2006年軟考程序員數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)筆記

在順序表中實(shí)現(xiàn)的基本運(yùn)算主要討論了插入和刪除兩種運(yùn)算。相關(guān)的算法我們通過(guò)練習(xí)掌握。對(duì)于順序表的插入和刪除運(yùn)算，其平均時(shí)間復(fù)雜度均為O(n)。

--------------------------------------------------------------------------------
線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它與順序表不同，鏈表是用一組任意的存儲(chǔ)單元來(lái)存放線性表的結(jié)點(diǎn)，這組存儲(chǔ)單元可以分布在內(nèi)存中任何位置上。因此，鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同。所以為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還存儲(chǔ)了其后繼結(jié)點(diǎn)的地址信息(即指針或鏈)。這兩部分信息組成鏈表中的結(jié)點(diǎn)結(jié)構(gòu)。 

一個(gè)單鏈表由頭指針的名字來(lái)命名。
對(duì)于單鏈表，其操作運(yùn)算主要有建立單鏈表(頭插法、尾插法和在鏈表開(kāi)始結(jié)點(diǎn)前附加一個(gè)頭結(jié)點(diǎn)的算法)、查找(按序號(hào)和按值)、插入運(yùn)算、刪除運(yùn)算等。以上各運(yùn)算的平均時(shí)間復(fù)雜度均為O(n).其主要時(shí)間是耗費(fèi)在查找操作上。

--------------------------------------------------------------------------------
循環(huán)鏈表是一種首尾相接的鏈表。也就是終端結(jié)點(diǎn)的指針域不是指向NULL空而是指向開(kāi)始結(jié)點(diǎn)(也可設(shè)置一個(gè)頭結(jié)點(diǎn))，形成一個(gè)環(huán)。采用循環(huán)鏈表在實(shí)用中多采用尾指針表示單循環(huán)鏈表。這樣做的好處是查找頭指針和尾指針的時(shí)間都是O(1)，不用遍歷整個(gè)鏈表了。
判別鏈表終止的條件也不同于單鏈表，它是以指針是否等于某一指定指針如頭指針或尾指針來(lái)確定。 

--------------------------------------------------------------------------------
雙鏈表就是雙向鏈表，就是在單鏈表的每個(gè)結(jié)點(diǎn)里再增加一個(gè)指向其直接前趨的指針域prior,這樣形成的鏈表就有兩條不同方向的鏈。使得從已知結(jié)點(diǎn)查找其直接前趨結(jié)點(diǎn)可以和查找其直接后繼結(jié)點(diǎn)的時(shí)間一樣縮短為O(1)。
雙鏈表一般也由頭指針head惟一確定。雙鏈表也可以頭尾相鏈接構(gòu)成雙(向)循環(huán)鏈表。

--------------------------------------------------------------------------------
關(guān)于順序表和鏈表的比較，請(qǐng)看下表：
具體要求 順序表 鏈表 
基于空間 適于線性表長(zhǎng)度變化不大，易于事先確定其大小時(shí)采用。 適于當(dāng)線性表長(zhǎng)度變化大，難以估計(jì)其存儲(chǔ)規(guī)模時(shí)采用。 
基于時(shí)間 由于順序表是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)，當(dāng)線性表的操作主要是查找時(shí)，宜采用。 鏈表中對(duì)任何位置進(jìn)行插入和刪除都只需修改指針，所以這類操作為主的線性表宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。若插入和刪除主要發(fā)生在表的首尾兩端，則宜采用尾指針表示的單循環(huán)鏈表。 

第二章 線性表習(xí)題及答案 
--------------------------------------------------------------------------------
一、基礎(chǔ)知識(shí)題
(答案及點(diǎn)評(píng)) 2.1 試描述頭指針、頭結(jié)點(diǎn)、開(kāi)始結(jié)點(diǎn)的區(qū)別、并說(shuō)明頭指針和頭結(jié)點(diǎn)的作用。
一、基礎(chǔ)知識(shí)題
2.1 答：
開(kāi)始結(jié)點(diǎn)是指鏈表中的第一個(gè)結(jié)點(diǎn)，也就是沒(méi)有直接前趨的那個(gè)結(jié)點(diǎn)。
鏈表的頭指針是一指向鏈表開(kāi)始結(jié)點(diǎn)的指針(沒(méi)有頭結(jié)點(diǎn)時(shí))，單鏈表由頭指針唯一確定，因此單鏈表可以用頭指針的名字來(lái)命名。
頭結(jié)點(diǎn)是我們?nèi)藶榈卦阪湵淼拈_(kāi)始結(jié)點(diǎn)之前附加的一個(gè)結(jié)點(diǎn)。有了頭結(jié)點(diǎn)之后，頭指針指向頭結(jié)點(diǎn)，不論鏈表否為空，頭指針總是非空。而且頭指針的設(shè)置使得對(duì)鏈表的第一個(gè)位置上的操作與在表其他位置上的操作一致(都是在某一結(jié)點(diǎn)之后)。

--------------------------------------------------------------------------------
(答案及點(diǎn)評(píng)) 2.2 何時(shí)選用順序表、何時(shí)選用鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)為宜?

2.2 答：
在實(shí)際應(yīng)用中，應(yīng)根據(jù)具體問(wèn)題的要求和性質(zhì)來(lái)選擇順序表或鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)，通常有以下幾方面的考慮：
1.基于空間的考慮。當(dāng)要求存儲(chǔ)的線性表長(zhǎng)度變化不大，易于事先確定其大小時(shí)，為了節(jié)約存儲(chǔ)空間，宜采用順序表；反之，當(dāng)線性表長(zhǎng)度變化大，難以估計(jì)其存儲(chǔ)規(guī)模時(shí)，采用動(dòng)態(tài)鏈表作為存儲(chǔ)結(jié)構(gòu)為好。
2.基于時(shí)間的考慮。若線性表的操作主要是進(jìn)行查找，很少做插入和刪除操作時(shí)，采用順序表做存儲(chǔ)結(jié)構(gòu)為宜；反之， 若需要對(duì)線性表進(jìn)行頻繁地插入或刪除等的操作時(shí)，宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。并且，若鏈表的插入和刪除主要發(fā)生在表的首尾兩端，則采用尾指針表示的單循環(huán)鏈表為宜。

--------------------------------------------------------------------------------
(答案及點(diǎn)評(píng)) 2.3 在順序表中插入和刪除一個(gè)結(jié)點(diǎn)需平均移動(dòng)多少個(gè)結(jié)點(diǎn)?具體的移動(dòng)次數(shù)取決于哪兩個(gè)因素?
2.3.答：
在等概率情況下，順序表中插入一個(gè)結(jié)點(diǎn)需平均移動(dòng)n/2個(gè)結(jié)點(diǎn)。刪除一個(gè)結(jié)點(diǎn)需平均移動(dòng)(n-1)/2個(gè)結(jié)點(diǎn)。具體的移動(dòng)次數(shù)取決于順序表的長(zhǎng)度n以及需插入或刪除的位置i。i越接近n則所需移動(dòng)的結(jié)點(diǎn)數(shù)越少。

--------------------------------------------------------------------------------
(答案及點(diǎn)評(píng)) 2.4 為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好?

2.4. 答：
尾指針是指向終端結(jié)點(diǎn)的指針，用它來(lái)表示單循環(huán)鏈表可以使得查找鏈表的開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)都很方便，設(shè)一帶頭結(jié)點(diǎn)的單循環(huán)鏈表，其尾指針為rear，則開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)的位置分別是rear->next->next 和 rear, 查找時(shí)間都是O(1)。