數(shù)據(jù)結(jié)構(gòu)第二章習題課

1、1、試描述頭指針、頭結(jié)點、開始結(jié)點的區(qū)別、并說明頭指針和頭結(jié)點的作用。試描述頭指針、頭結(jié)點、開始結(jié)點的區(qū)別、并說明頭指針和頭結(jié)點的作用。答：開始結(jié)點是指鏈表中的第一個結(jié)點，也就是沒有直接前趨的那個結(jié)點。答：開始結(jié)點是指鏈表中的第一個結(jié)點，也就是沒有直接前趨的那個結(jié)點。鏈表的頭指針是一指向鏈表開始結(jié)點的指針鏈表的頭指針是一指向鏈表開始結(jié)點的指針(沒有頭結(jié)點時沒有頭結(jié)點時)，單鏈表由頭指針唯一確，單鏈表由頭指針唯一確定，因此單鏈表可以用頭指

2、針的名字來命名。定，因此單鏈表可以用頭指針的名字來命名。頭結(jié)點是我們?nèi)藶榈卦阪湵淼拈_始結(jié)點之前附加的一個結(jié)點。有了頭結(jié)點之后，頭指頭結(jié)點是我們?nèi)藶榈卦阪湵淼拈_始結(jié)點之前附加的一個結(jié)點。有了頭結(jié)點之后，頭指針指向頭結(jié)點，不論鏈表否為空，頭指針總是非空。而且頭指針的設(shè)置使得對鏈表的第一針指向頭結(jié)點，不論鏈表否為空，頭指針總是非空。而且頭指針的設(shè)置使得對鏈表的第一個位置上的操作與在表其他位置上的操作一致個位置上的操作與在表其他位置上的操作一致

3、(都是在某一結(jié)點之后都是在某一結(jié)點之后)。2、何時選用順序表、何時選用鏈表作為線性表的存儲結(jié)構(gòu)為宜何時選用順序表、何時選用鏈表作為線性表的存儲結(jié)構(gòu)為宜答：在實際應(yīng)用中，應(yīng)根據(jù)具體問題的要求和性質(zhì)來選擇順序表或鏈表作為線性表的存儲答：在實際應(yīng)用中，應(yīng)根據(jù)具體問題的要求和性質(zhì)來選擇順序表或鏈表作為線性表的存儲結(jié)構(gòu)，通常有以下幾方面的考慮：結(jié)構(gòu)，通常有以下幾方面的考慮：1)基于空間的考慮。當要求存儲的線性表長度變化不大，易于事先確定其大小時，

4、基于空間的考慮。當要求存儲的線性表長度變化不大，易于事先確定其大小時，為了節(jié)約存儲空間，宜采用順序表；反之，當線性表長度變化大，難以估計其存儲規(guī)模為了節(jié)約存儲空間，宜采用順序表；反之，當線性表長度變化大，難以估計其存儲規(guī)模時，采用動態(tài)鏈表作為存儲結(jié)構(gòu)為好。時，采用動態(tài)鏈表作為存儲結(jié)構(gòu)為好。2)基于時間的考慮。若線性表的操作主要是進行查找，很少做插入和刪除操作時，基于時間的考慮。若線性表的操作主要是進行查找，很少做插入和刪除操作時，采用順

5、序表做存儲結(jié)構(gòu)為宜；反之，采用順序表做存儲結(jié)構(gòu)為宜；反之，若需要對線性表進行頻繁地插入或刪除等操作時，宜若需要對線性表進行頻繁地插入或刪除等操作時，宜采用鏈表做存儲結(jié)構(gòu)。并且，若鏈表的插入和刪除主要發(fā)生在表的首尾兩端，則采用尾指采用鏈表做存儲結(jié)構(gòu)。并且，若鏈表的插入和刪除主要發(fā)生在表的首尾兩端，則采用尾指針表示的單循環(huán)鏈表為宜。針表示的單循環(huán)鏈表為宜。3、在順序表中插入和刪除一個結(jié)點需平均移動多少個結(jié)點在順序表中插入和刪除一個結(jié)點需平均

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

7、。4、為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好答：尾指針是指向終端結(jié)點的指針，用它來表示單循環(huán)鏈表可以使得查找鏈表的開始結(jié)點答：尾指針是指向終端結(jié)點的指針，用它來表示單循環(huán)鏈表可以使得查找鏈表的開始結(jié)點和終端結(jié)點都很方便，設(shè)一帶頭結(jié)點的單循環(huán)鏈表，其尾指針為和終端結(jié)點都很方便，設(shè)一帶頭結(jié)點的單循環(huán)鏈表，其尾指針為rear，則開始結(jié)點和終端，則開始結(jié)點和終端結(jié)點的位置分別是結(jié)點的位置分別

8、是rearnextnext和rear查找時間都是查找時間都是O(1)。若用頭指針來表示該鏈表，則查找終端結(jié)點的時間為若用頭指針來表示該鏈表，則查找終端結(jié)點的時間為O(n)。5、在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指針在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點，不知道頭指針，能指向某結(jié)點，不知道頭指針，能否將結(jié)點否將結(jié)點p從相應(yīng)的鏈表中刪去從相應(yīng)的鏈表中刪去若可以，其時間復(fù)雜度各為多少若可以，其時間復(fù)雜度各為多少答：我們

9、分別討論三種鏈表的情況。答：我們分別討論三種鏈表的情況。1)單鏈表。當我們知道指針單鏈表。當我們知道指針p指向某結(jié)點時，能夠根據(jù)該指針找到其直接后繼，但指向某結(jié)點時，能夠根據(jù)該指針找到其直接后繼，但是由于不知道其頭指針，所以無法訪問到是由于不知道其頭指針，所以無法訪問到p指針指向的結(jié)點的直接前趨。因此無法刪去該指針指向的結(jié)點的直接前趨。因此無法刪去該結(jié)點。結(jié)點。2)雙鏈表。由于這樣的鏈表提供雙向鏈接，因此根據(jù)已知結(jié)點可以查找到其直接前雙

10、鏈表。由于這樣的鏈表提供雙向鏈接，因此根據(jù)已知結(jié)點可以查找到其直接前趨和直接后繼，從而可以刪除該結(jié)點。其時間復(fù)雜度為趨和直接后繼，從而可以刪除該結(jié)點。其時間復(fù)雜度為O(1)。3)單循環(huán)鏈表。根據(jù)已知結(jié)點位置，我們可以直接得到其后相鄰的結(jié)點位置單循環(huán)鏈表。根據(jù)已知結(jié)點位置，我們可以直接得到其后相鄰的結(jié)點位置(直接后直接后繼)，又因為是循環(huán)鏈表，所以我們可以通過查找，得到，又因為是循環(huán)鏈表，所以我們可以通過查找，得到p結(jié)點的直接前趨。因此可

11、以刪去結(jié)點的直接前趨。因此可以刪去p所指結(jié)點。其時間復(fù)雜度應(yīng)為所指結(jié)點。其時間復(fù)雜度應(yīng)為O(n)。16、設(shè)順序表、設(shè)順序表L是一個非遞減有序表，試寫一算法，將是一個非遞減有序表，試寫一算法，將x插入插入L中，并使中，并使L仍是一個有序仍是一個有序表。表。解：解：因已知順序表因已知順序表L是遞增有序表，所以只要從頭找起找到第一個比它大是遞增有序表，所以只要從頭找起找到第一個比它大(或相等或相等)的結(jié)點的結(jié)點數(shù)據(jù)，把數(shù)據(jù)，把x插入到這個結(jié)點

12、所在的位置就是了。插入到這個結(jié)點所在的位置就是了。算法如下：算法如下：voidIncreaseList(SqlistLDatatypex)intif(i=0ilengthi)查找查找List(Lix)調(diào)用順序表插入函數(shù)調(diào)用順序表插入函數(shù)DecreaseList18、寫一算法在單鏈表上實現(xiàn)線性表的、寫一算法在單鏈表上實現(xiàn)線性表的ListLength(L)運算。運算。解：求單鏈表長只能用遍歷的方法了，從頭數(shù)到尾。解：求單鏈表長只能用遍歷的方

13、法了，從頭數(shù)到尾。算法如下：算法如下：intListLength(LinkListL)intlen=0ListNodepp=L設(shè)該表有頭結(jié)點設(shè)該表有頭結(jié)點while(pnext)p=pnextlenreturnlenListLength19、已知、已知L1和L2分別指向兩個單鏈表的頭結(jié)點，且已知其長度分別為分別指向兩個單鏈表的頭結(jié)點，且已知其長度分別為m和n。試寫一算。試寫一算法將這兩個鏈表連接在一起，請分析你的算法的時間復(fù)雜度。法將這