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

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

一個單鏈表由頭指針的名字來命名。
對于單鏈表，其操作運算主要有建立單鏈表(頭插法、尾插法和在鏈表開始結(jié)點前附加一個頭結(jié)點的算法)、查找(按序號和按值)、插入運算、刪除運算等。以上各運算的平均時間復雜度均為O(n).其主要時間是耗費在查找操作上。

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

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

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

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

--------------------------------------------------------------------------------
(答案及點評) 2.2 何時選用順序表、何時選用鏈表作為線性表的存儲結(jié)構(gòu)為宜?

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

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

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

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