線性表作業(yè)-答案

《線性表作業(yè)-答案》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第二章線性表作業(yè)評(píng)講2.1試描述頭指針、頭結(jié)點(diǎn)、開始結(jié)點(diǎn)的區(qū)別、并說明頭指針和頭結(jié)點(diǎn)的作用。2.2何時(shí)選用順序表、何時(shí)選用鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)為宜?2.3在順序表中插入和刪除一個(gè)結(jié)點(diǎn)需平均移動(dòng)多少個(gè)結(jié)點(diǎn)?具體的移動(dòng)次數(shù)取決于哪兩個(gè)因素?2.4為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好?2.5在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點(diǎn)，不知道頭指針，能否將結(jié)點(diǎn)*p從相應(yīng)的鏈表中刪去?若可以，其時(shí)間復(fù)雜度各為多少?作業(yè)：2.5、2.7、2.9、2.11做在作業(yè)本上，交，其余堂下練習(xí)2.6設(shè)有一個(gè)雙鏈表，每個(gè)結(jié)點(diǎn)中除有prior、data和nex

2、t三個(gè)域外，還有一個(gè)訪問頻度域freq，在鏈表被起用之前，其值均初始化為零。每當(dāng)在鏈表進(jìn)行一次LocateNode(L,s)運(yùn)算時(shí)，令元素值為x的結(jié)點(diǎn)中freq域的值加1，并調(diào)整表中結(jié)點(diǎn)的次序，使其按訪問頻度的遞減序排列，以便使頻繁訪問的結(jié)點(diǎn)總是靠近表頭。試寫一符合上述要求的LocateNode運(yùn)算的算法。2.7寫一算法在單鏈表上實(shí)現(xiàn)線性表的ListLength(L)運(yùn)算。2.8已知由單鏈表表示的線性表中，含有三類字符的數(shù)據(jù)元素(如：字母字符、數(shù)字字符和其它字符)，試編寫算法構(gòu)造三個(gè)以循環(huán)鏈表表示的線性表，使每個(gè)表中只含同一類的字符，且利用原表中的結(jié)點(diǎn)空間作為這

3、三個(gè)表的結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另辟空間。2.9假設(shè)在長度大于1的單循環(huán)鏈表中，既無頭結(jié)點(diǎn)也無頭指針。s為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫算法刪除結(jié)點(diǎn)*s的直接前趨結(jié)點(diǎn)。2.10設(shè)順序表L是一個(gè)遞增有序表，試寫一算法，將x插入L中，并使L仍是一個(gè)有序表。2.11寫出以下鏈表操作的算法1）創(chuàng)建一個(gè)空的雙向循環(huán)鏈表statusCreateList_Dul(DuLinkList&L);2）取得雙向循環(huán)鏈表中第i個(gè)數(shù)據(jù)元素的位置指針statusGetElemP_Dul(DuLinkListL,inti);3）將單鏈表置逆statusReverseList_L(LinkList

4、&L);2.1試描述頭指針、頭結(jié)點(diǎn)、開始結(jié)點(diǎn)的區(qū)別、并說明頭指針和頭結(jié)點(diǎn)的作用。開始結(jié)點(diǎn)是指鏈表中的第一個(gè)結(jié)點(diǎn)，沒有直接前趨的那個(gè)結(jié)點(diǎn)。鏈表的頭指針是一指向鏈表開始結(jié)點(diǎn)的指針(沒有頭結(jié)點(diǎn)時(shí))，單鏈表由頭指針唯一確定，因此單鏈表可以用頭指針的名字來命名。頭結(jié)點(diǎn)在鏈表的開始結(jié)點(diǎn)之前附加的一個(gè)結(jié)點(diǎn)。有了頭結(jié)點(diǎn)之后，頭指針指向頭結(jié)點(diǎn)，不論鏈表否為空，頭指針總是非空。而且頭指針的設(shè)置使得對鏈表的第一個(gè)位置上的操作與在表其他位置上的操作一致(都是在某一結(jié)點(diǎn)之后)。2.2何時(shí)選用順序表、何時(shí)選用鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)為宜?1.基于空間的考慮。當(dāng)要求存儲(chǔ)的線性表長度變化不大，

5、易于事先確定其大小時(shí)，為了節(jié)約存儲(chǔ)空間，宜采用順序表；反之，當(dāng)線性表長度變化大，難以估計(jì)其存儲(chǔ)規(guī)模時(shí)，采用動(dòng)態(tài)鏈表作為存儲(chǔ)結(jié)構(gòu)為好。2.基于時(shí)間的考慮。若線性表的操作主要是進(jìn)行查找，很少做插入和刪除操作時(shí)，采用順序表做存儲(chǔ)結(jié)構(gòu)為宜；反之，若需要對線性表進(jìn)行頻繁地插入或刪除等的操作時(shí)，宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。并且，若鏈表的插入和刪除主要發(fā)生在表的首尾兩端，則采用尾指針表示的單循環(huán)鏈表為宜。2.3在順序表中插入和刪除一個(gè)結(jié)點(diǎn)需平均移動(dòng)多少個(gè)結(jié)點(diǎn)?具體的移動(dòng)次數(shù)取決于哪兩個(gè)因素?在等概率情況下，順序表中插入一個(gè)結(jié)點(diǎn)需平均移動(dòng)n/2個(gè)結(jié)點(diǎn)。刪除一個(gè)結(jié)點(diǎn)需平均移動(dòng)(n-1)

6、/2個(gè)結(jié)點(diǎn)。具體的移動(dòng)次數(shù)取決于順序表的長度n以及需插入或刪除的位置i。i越接近n則所需移動(dòng)的結(jié)點(diǎn)數(shù)越少。2.4為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好?尾指針是指向終端結(jié)點(diǎn)的指針，用它來表示單循環(huán)鏈表可以使得查找鏈表的開始結(jié)點(diǎn)和終端結(jié)點(diǎn)都很方便，設(shè)一帶頭結(jié)點(diǎn)的單循環(huán)鏈表，其尾指針為rear，則開始結(jié)點(diǎn)和終端結(jié)點(diǎn)的位置分別是rear->next->next和rear,查找時(shí)間都是O(1)。若用頭指針來表示該鏈表，則查找終端結(jié)點(diǎn)的時(shí)間為O(n)。2.5在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點(diǎn)，不知道頭指針，能否將結(jié)點(diǎn)*p從相應(yīng)的鏈表中刪去?若

7、可以，其時(shí)間復(fù)雜度各為多少?1.單鏈表。當(dāng)我們知道指針p指向某結(jié)點(diǎn)時(shí)，能夠根據(jù)該指針找到其直接后繼，但是由于不知道其頭指針，所以無法訪問到p指針指向的結(jié)點(diǎn)的直接前趨。因此無法刪去該結(jié)點(diǎn)。2.雙鏈表。由于這樣的鏈表提供雙向鏈接，因此根據(jù)已知結(jié)點(diǎn)可以查找到其直接前趨和直接后繼，從而可以刪除該結(jié)點(diǎn)。其時(shí)間復(fù)雜度為O(1)。3.單循環(huán)鏈表。根據(jù)已知結(jié)點(diǎn)位置，我們可以直接得到其后相鄰的結(jié)點(diǎn)位置(直接后繼)，又因?yàn)槭茄h(huán)鏈表，所以我們可以通過查找，得到p結(jié)點(diǎn)的直接前趨。因此可以刪去p所指結(jié)點(diǎn)。其時(shí)間復(fù)雜度應(yīng)為O(n)。2.6設(shè)有一個(gè)雙鏈表，每個(gè)結(jié)點(diǎn)中除有prior、data

8、和next三個(gè)域外，還有