數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案總結(jié)(編輯修改稿)
2024-07-20 20:48 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 為宜；反之， 若需要對(duì)線性表進(jìn)行頻繁地插入或刪除等的操作時(shí)，宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。并且，若鏈表的插入和刪除主要發(fā)生在表的首尾兩端，則采用尾指針表示的單循環(huán)鏈表為宜。 下述算法的功能是什么?LinkList Demo(LinkList L){ // L 是無頭結(jié)點(diǎn)單鏈表ListNode *Q,*P。if(Lamp。amp。Lnext){Q=L。L=Lnext。P=L。while (Pnext) P=Pnext。Pnext=Q。 Qnext=NULL。}return L。}// Demo答：該算法的功能是：將開始結(jié)點(diǎn)摘下鏈接到終端結(jié)點(diǎn)之后成為新的終端結(jié)點(diǎn)，而原來的第二個(gè)結(jié)點(diǎn)成為新的開始結(jié)點(diǎn)，返回新鏈表的頭指針。 設(shè)順序表L是一個(gè)遞增有序表，試寫一算法，將x插入L中，并使L仍是一個(gè)有序表。答：因已知順序表L是遞增有序表，所以只要從順序表終端結(jié)點(diǎn)（設(shè)為i位置元素）開始向前尋找到第一個(gè)小于或等于x的元素位置i后插入該位置即可。在尋找過程中，由于大于x的元素都應(yīng)放在x之后，所以可邊尋找，邊后移元素，當(dāng)找到第一個(gè)小于或等于x的元素位置i時(shí)，該位置也空出來了。算法如下：//void InsertIncreaseList( Seqlist *L , Datatype x ){int i。if ( Llength=ListSize)Error(“overflow)。for ( i=L length 。 i0 amp。amp。 Ldata[ i1 ] x 。 i)Ldata[ i ]=Ldata[ i ] 。 // 比較并移動(dòng)元素Ldata[ i ] =x。L length++。} 設(shè) A和B是兩個(gè)單鏈表，其表中元素遞增有序。試寫一算法將A和B歸并成一個(gè)按元素值遞減有序的單鏈表C，并要求輔助空間為O(1)，請(qǐng)分析算法的時(shí)間復(fù)雜度。解：根據(jù)已知條件，A和B是兩個(gè)遞增有序表，所以可以先取A表的表頭建立空的C表。然后同時(shí)掃描A表和B表，將兩表中最大的結(jié)點(diǎn)從對(duì)應(yīng)表中摘下，并作為開始結(jié)點(diǎn)插入C表中。如此反復(fù)，直到A表或B表為空。最后將不為空的A表或B表中的結(jié)點(diǎn)依次摘下并作為開始結(jié)點(diǎn)插入C表中。這時(shí)，得到的C表就是由A表和B表歸并成的一個(gè)按元素值遞
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1