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

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

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

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

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

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

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

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

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

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

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

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

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

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