北航計(jì)算機(jī)考研材料第2章線性表答案

1、第2章線性表選擇題1. A2.B3. C4. A5.D6.D7.D8.C9.B10. B, C11. 1111.2111.3E11.4B11. 5C12. B13. C14. C15. C16. A17. A18. A19. D20. C21. B22. D23. C24. B25. B26. A27. D判斷題1. X2. V3.V4. X5.X6.X7.X8.X9.X10.X11.X12.X13.X14.15.X16.V部分答案解釋如下。1、頭結(jié)點(diǎn)并不“僅起”標(biāo)識(shí)作用，并且使操作統(tǒng)一。另外，頭結(jié)點(diǎn)數(shù)據(jù)域可寫入鏈表長(zhǎng)度或作監(jiān)視哨。4. 兩種存儲(chǔ)結(jié)構(gòu)各有優(yōu)缺點(diǎn)，應(yīng)根據(jù)實(shí)際情況選用，不能籠統(tǒng)說(shuō)哪

2、一個(gè)好。7.集合中元素?zé)o邏輯關(guān)系。9.非空線性表第一個(gè)元素?zé)o前驅(qū)，最后一個(gè)元素?zé)o后繼。13.線性表是邏輯結(jié)構(gòu)，可以順序存儲(chǔ)，也可鏈?zhǔn)酱鎯?chǔ)。三.填空題1.順序2. (nT) /23. py-n ext=px-n ext: px-n ext=py4 . n-i+15.主要是使插入和刪除等操作統(tǒng)一，在第一個(gè)元素之前插入元素和刪除第-個(gè)結(jié)點(diǎn)不必另作判斷。另外，不論鏈表是否為空，鏈表指針不變6.0(1), 0(n)7.單鏈表，多重鏈表，(動(dòng)態(tài))鏈表，靜態(tài)鏈表8. f-n ext=p-n ext; f-prior=p; p-n ext-prior=f; p-n ext=f;9. p prior s pri

3、or , n ext10. 指針11.物理上相鄰 指針12. 413.從任一結(jié)點(diǎn)出發(fā)都可訪問到鏈表中每一個(gè)元素。14 . u=p-n ext; p-n ext=u-n ext; free(u);16.p next!=null17. L- next=L & L- prior=L19. (1) IF pa 二 NIL THEN return(true);(2) pbONIL AND pa, data 二 pb. data(3) retur n(i nclusi on( pa, pb);(4) pb:=pb n ext;(5) return (false);非遞歸算法：15 . L-n ext- n

4、 ext=L18. s-n ext=p-n ext;p-n ext=s;(l) pre:=pb; paONIL AND pbONIL AND pb data二 pa, data (3)pa:二 pa, next;pb:=pb n ext;(4)pb: 二 pre, next;pre:二 pb;pa: 二 pa, next;(5) IF paNIL THEN retur n( true)ELSE return(false);注:本題是在鏈表上求模式匹配問題。非遞歸算法中用指針pre指向主串中開始結(jié)點(diǎn)(初始時(shí)為第一元素結(jié)點(diǎn))。若主串與子串對(duì)應(yīng)數(shù)據(jù)相等，兩串工作指針pa和pb后移；否則，20.結(jié)點(diǎn))

5、A. VAR head:ptr B. new(p) C. p data:=k D. qA. n ext:=pE. q:=p(帶頭21.(1)n ew(h) ; /生成頭結(jié)點(diǎn)，以便于操作。IF(q=NIL) THEN22.nrAljnlextlatpOmax AND(q liriknedataOnq;xAr:=r. link C: q. link D: q. link r:=s (或E: rL linkF:linkBr:二 r. link) H: r:=A. link (2)0(3)I: q link:二 s . link23. lajvi-l(4)p t . next(5)il開始，比較一直繼

6、續(xù)到循環(huán)條件失敗。若pa為空，則匹配成功，返回 true,否貝0，返回false。24. head, left:=s/head的前驅(qū)指針指向插入結(jié)點(diǎn) j：=l；(3) p:=p right工作指針后移(4) s. left:=p(5) p” . right. left:=s; p 后繼的前驅(qū)是 s(6) s. left:=p;25. (1) iprenext=q_next;q_next-pre=q-pre; 先將 q 結(jié)點(diǎn)從鏈表上摘下qnext:=p; q pre:=p . pre; p prenext:=q; p . pre: =q;結(jié)點(diǎn) q 插入結(jié)點(diǎn)P前(4) q freq=0鏈表中無(wú)值為

7、 x的結(jié)點(diǎn)，將新建結(jié)點(diǎn)插入到鏈表最后(頭結(jié)點(diǎn) 前)29. (l)aLkey:伊 &的頭結(jié)點(diǎn)用作監(jiān)視哨，取不同于a鏈表中其它數(shù)據(jù)域的值(2) b key:二p. key b的頭結(jié)點(diǎn)起監(jiān)視哨作用(3) p:=p next找到a, b表中共同字母，a表指針后移(4) 0 (m* n)30. C部分：(l)p!=null鏈表未到尾就一直作31. (l)L=L- next;暫存后繼(2)q=L;待逆置結(jié)點(diǎn)(3) L=p;頭指針仍為L(zhǎng)32. p . nextOpo(2)r:= p*. next(3) p next：=qo； qo : = p；(5) p :=r33. (l)r(2)NIL(3)xhead

8、.data(4)p . dataexp!=-l(2)pa-exp=0若指數(shù)為0,即本項(xiàng)為常數(shù)項(xiàng)(3) q- next=pa- next /刪常數(shù)項(xiàng)(4)q _n ext取卜兀素(5)=pa-coef*pa-exp一/指數(shù)項(xiàng)減1pa前驅(qū)后移，或q- next(8)pa-n ext.nW-取卜兀素35. (l)q:=p; q是工作指針P的前驅(qū)(2) p datamP是工作指針(3)r:二 q;/r記最大值的前驅(qū)，(4)q:=p;或 q:=q. next;(5)n ext:=q.n ext;或 r. n ext:=rA.n ext .n ext刪最大值結(jié)點(diǎn)四、36.37.(l)L- next=nul

9、l(5)p!=n ullq!=n ull p-n ext=r- n ext r-n ext=p置空鏈表，然后將原鏈表結(jié)點(diǎn)逐個(gè)插入到有序表中當(dāng)鏈表尚未到尾，P為工作指針查p結(jié)點(diǎn)在鏈表中的插入位置，這時(shí)q是工作指針。將p結(jié)點(diǎn)鏈入鏈表中 1是4的前驅(qū)，u是下個(gè)待插入結(jié)點(diǎn)的指針。程序(b) C部分(1)(A!=n ull & B匸n ull)兩均未空時(shí)循環(huán)(2)A-eleme nt=B-eleme nt兩表中相等兀素不作結(jié)果兀素(3)B=B-li nk向后移動(dòng)B表指針(4)A!=null將A表剩余部分放入結(jié)果表中(5)last-li nk=n ull置鏈表尾應(yīng)用題程序PASCAL部分(編者略)1. (

10、1)選鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它可動(dòng)態(tài)申請(qǐng)內(nèi)存空間，不受表長(zhǎng)度影響，插入、刪 除時(shí)間復(fù)雜度為 0(1)。(2)選順序存儲(chǔ)結(jié)構(gòu)。順序表可以隨機(jī)存取，時(shí)間復(fù)雜度為(即表中元素個(gè)數(shù))的0 (1)。2. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一般說(shuō)克服了順序存儲(chǔ)結(jié)構(gòu)的三個(gè)弱點(diǎn)。首先，插入、刪除不需移動(dòng)元素，只修改指針，時(shí)間復(fù)雜度為0(1);其次，不需要預(yù)先分配空間，可根據(jù)需要?jiǎng)討B(tài)申請(qǐng)空間；其三，表容量只受可用內(nèi)存空間的限制。其缺點(diǎn)是因?yàn)橹羔樤黾恿丝臻g開銷，當(dāng)空間不允許時(shí)，就不能克服順序存儲(chǔ)的缺點(diǎn)?？臻g返還3. 采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，它根據(jù)實(shí)際需要申請(qǐng)內(nèi)存空間，而當(dāng)不需要時(shí)又可將不用結(jié)點(diǎn) 給系統(tǒng)。在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中插入和刪除操作不需要移動(dòng)元素。

11、4. 線性表?xiàng)ｊ?duì)列串順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)的定義是：CONST maxle門=線性表可能達(dá)到的最大長(zhǎng)度；TYPE sqlisttp=RECORDelem: ARRAY1. . maxle n OF ElemType;last:0. maxle n;END;鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的定義是：TYPE poin ter= f no detype;nodetype=RECORDdata:ElemType; n ext:po in ter;END;lin klisttp=po in ter;5. 順序映射時(shí)，ai與ai+i的物理位置相鄰；鏈表表示時(shí)ai與ai+i的物理位置不要求相鄰。6. 在線性

12、表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，頭指針指鏈表的指針，若鏈表有頭結(jié)點(diǎn)則是鏈表的頭結(jié)點(diǎn)的指針，頭指針具有標(biāo)識(shí)作用，故常用頭指針冠以鏈表的名字。頭結(jié)點(diǎn)是為了操作的統(tǒng)一、方便而設(shè)立的，放在第一元素結(jié)點(diǎn)之前，其數(shù)據(jù)域一般無(wú)意義(當(dāng)然有些情況下也可存放鏈表的長(zhǎng)度、用做監(jiān)視哨等等)，有頭結(jié)點(diǎn)后，對(duì)在第一元素結(jié)點(diǎn)前插入結(jié)點(diǎn)和刪除第結(jié)點(diǎn)，其操作與對(duì)其它結(jié)點(diǎn)的操作統(tǒng)一了。而且無(wú)論鏈表是否為空，頭指針均不為空。首元結(jié)點(diǎn)也就是第一元素結(jié)點(diǎn)，它是頭結(jié)點(diǎn)后邊的第一個(gè)結(jié)點(diǎn)。7. 見上題6。8. (1)將next域變?yōu)閮蓚€(gè)域：pre和next,其值域均為O.maxsize。初始化時(shí)，頭結(jié) 點(diǎn)(下標(biāo)為 0的元素)其next域值為1,其pr

13、e域值為n (設(shè)n是元素個(gè)數(shù)，且 nnext=q_next; free(q):13. 設(shè)單鏈表的頭結(jié)點(diǎn)的頭指針為head,且pre=head ；while(pre-n ext!=p) pre=pre-n ext;s-n ext=p; pre-n ext=s:14. 設(shè)單鏈表帶頭結(jié)點(diǎn)，工作指針p初始化為p=H-next;(1) while(p!=null & p-data!=X) p=p-next;if (p= =n ull) return (n ull);查找失敗else return(p); 查找成功(2) while(p!=null & p-datanext;if (p=null | |

14、p-dataX) return (n ull) ; /查找失敗else return(p);(3) while(p!=null & p-dataX) p=p_next;if (p=null | | p-dataX) return (n ull);查找失敗else return (p);查找成功15. 本程序段功能是將 pa和pb鏈表中的值相同的結(jié)點(diǎn)保留在pa鏈表中(pa中與pb中不 同結(jié)點(diǎn)刪除)，pa是結(jié)果鏈表的頭指針。鏈表中結(jié)點(diǎn)值與從前逆序。S1記結(jié)果鏈表中結(jié)點(diǎn)個(gè)數(shù)(即pa與pb中相等的元素個(gè)數(shù))。S2記原pa鏈表中刪除的結(jié)點(diǎn)個(gè)數(shù)。16. 設(shè) q:=p llink; 則q rli nk:=p

15、 rli nk; p .rli nk . lli nk:=q; p lli nk:=q lli nk;q. 11i nk. rli nk:=p; p rli nk:=q;qL lli nk:=p17. (1)前兩個(gè)語(yǔ)句改為：p. lli nk . rli nk- p rli nk;p rlink . llink- p llink;(2)后三個(gè)語(yǔ)句序列應(yīng)改為：qL rli nk pL rlink; /以下三句的順序不能變p rli nk . lli nk q;p . rli nkpre=p-pre; sn ext=p; p-pre n ext=s; p-pre=s;20. (A) flONIL

16、并且 f2ONIL(B) fl f . data f2 t . data(C) f2 f . dataf1 t . data(D) f3 t . dataf1 t . data(E) f 1prior=q-prior; /將q結(jié)點(diǎn)摘下，以便插入到適當(dāng)位置。(2) p-next-prior=q; / (3)將 q 結(jié)點(diǎn)插入(3) p_n ext=q;(4) r=r-next;或r=q-next;后移指針，再將新結(jié)點(diǎn)插入到適當(dāng)位置。五、算法設(shè)計(jì)題1. 題目分析因?yàn)閮涉湵硪寻丛刂颠f增次序排列，將其合并時(shí)，均從第一個(gè)結(jié)點(diǎn)起進(jìn)行比較,將小的鏈入鏈表中，同時(shí)后移鏈表工作指針。該問題要求結(jié)果鏈表按元素值遞

17、減次序排列。故在合并的同時(shí)，將鏈表結(jié)點(diǎn)逆置。Lin kedList Union(Lin kedList la, lb) la,lb分別是帶頭結(jié)點(diǎn)的兩個(gè)單鏈表的頭指針，鏈表中的元素值按遞增序排列，本算法將兩鏈表合并成一個(gè)按元素值遞減次序排列的單鏈表。( pa=la-next; pb=lb-next;la-next=null;空。while (pa !=null & pb!=null) if(pa-datadata) ( r=pa-next; pa-next=la-next; la- next=pa; pa=r;pa, pb 分別是鏈表 la 和 lb 的工作指針/la 作結(jié)果鏈表的頭指針，先將結(jié)

18、果鏈表初始化為當(dāng)兩鏈表均不為空時(shí)作將 pa 的后繼結(jié)點(diǎn)暫存于 r 。將 pa 結(jié)點(diǎn)鏈于結(jié)果表中，同時(shí)逆置?；謴?fù) pa 為當(dāng)前待比較結(jié)點(diǎn)。else(r=pb-next; / 將 pb 的后繼結(jié)點(diǎn)暫存于 r 。pb-next=la-next; 將 pb 結(jié)點(diǎn)鏈于結(jié)果表中，同時(shí)逆置 lanext=pb;pb=r; 恢復(fù) pb 為當(dāng)前待比較結(jié)點(diǎn)。while (pa!=null) 將 la 表的剩余部分鏈入結(jié)果表，并逆置。(r=pa-next; pa-next=la-next; la-next=pa; pa=r; while(pb!=null)(r=pb-next; pb-next=la-next; l

19、a-next=pb; pb=r; 算法 Union 結(jié)束。算法討論上面兩鏈表均不為空的表達(dá)式也可簡(jiǎn)寫為 while (pa&pb), 兩遞增有序表 合并成遞 減有序表時(shí)，上述算法是邊合并邊逆置。也可先合并完，再作鏈表逆置。后者不如 前者優(yōu)化。算法中 最后兩個(gè) while 語(yǔ)句，不可能執(zhí)行兩個(gè)，只能二者取一，即哪個(gè)表尚未到 尾，就將其逆置到結(jié)果表中， 即將剩余結(jié)點(diǎn)依次前插入到結(jié)果表的頭結(jié)點(diǎn)后面。與本題類似的其它題解答如下：(1)問題分析 與上題類似，不同之處在于：一是鏈表無(wú)頭結(jié)點(diǎn)，為處理方便，給加上頭結(jié)點(diǎn)，處理結(jié)束再刪除之；二是數(shù)據(jù)相同的結(jié)點(diǎn)，不合并到結(jié)果鏈表中；三是 hb 鏈 表不能被破壞，即

20、將 hb 的結(jié)點(diǎn)合并到結(jié)果鏈表時(shí)，要生成新結(jié)點(diǎn)。LinkedList Union(LinkedList ha, hb)/ha 和 hb 是兩個(gè)無(wú)頭結(jié)點(diǎn)的數(shù)據(jù)域值遞增有序的單鏈表，本算法將 hb 中并不出現(xiàn)在 ha 中的數(shù)據(jù) 合并到 ha 中，合并中不能破壞 hb 鏈表。LinkedList la;la= (LinkedList)malloc(sizeof(LNode);la-next=ha; / 申請(qǐng)頭結(jié)點(diǎn)，以便操作。pa=ha; pa 是 ha 鏈表的工作指針pb=hb; pb 是 hb 鏈表的工作指針pre=la;/pre 指向當(dāng)前待合并結(jié)點(diǎn)的前驅(qū)。while (pa&pb)if (pa-

21、datadata) 處理 ha 中數(shù)據(jù)(prenext=pa;pre=pa;pa=pa-next;申請(qǐng)空間 r-data=pbdata;else if (pa-datapb-data)處理 hb 中數(shù)據(jù)。(r= (LinkedList)malloc (sizeof (LNode) ; / prenext=r;pre=r; 將新結(jié)點(diǎn)鏈入結(jié)果鏈表。pb=pb-next;/7hb 鏈表中工作指針后移。else 處理 pa-data=pbdata;(prenext=pa; pre=pa;pa=pa-next; 兩結(jié)點(diǎn)數(shù)據(jù)相等時(shí)，只將 ha 的數(shù)據(jù)鏈入。pb=pb-next; 不要 hb 的相等數(shù)據(jù)將兩

22、鏈表中剩余部分鏈入結(jié)果鏈表。if (pa!=null)pre-next=pa; /else prenext=pb;free (la); 釋放頭結(jié)點(diǎn) .ha, hb 指針未被破壞。 算法 nion 結(jié)束。pa=la-next;pb=hb-next;(2) 本題與上面兩題類似，要求結(jié)果指針為 ，其核心語(yǔ)句段如下： lc=(LinkedList )malloc(sizeof(LNode);pc=lc; pc 是結(jié)果鏈表中當(dāng)前結(jié)點(diǎn)的前驅(qū)while (pa&pb)if(pa-datadata)(pc-next=pa;pc=pa;pa=pa- next;else pc- next 二 pb;pc=pb;p

23、b=pb-next;if(pa)pc- next 二 pa; else pcnext=pb;的長(zhǎng)度。 合并中有各種條件。與前組題不(AUB, A AB, A-B) 等。本題與上面 1. (2) 基本相同，不同之處 1. (2) 中鏈表是“非遞減有序”，free (la) ; free (lb); 釋放原來(lái)兩鏈表的頭結(jié)點(diǎn)。算法時(shí)間復(fù)雜度為0 (m+n),其中m和n分別為鏈表la和lb( 可能包含 相等元素 ) ， 相等元素，則應(yīng)刪掉一ha 和 hb 分別 是其鏈表 素也是遞增有序。2. 題目分析本組題有 6 個(gè)，本質(zhì)上都是鏈表的合并操作， 同的是，敘述上是用線性表代表集合，而操作則是求集合的并、

24、交、差 本題是元素“遞增有序” (不準(zhǔn)有相同元素 ) 。因此兩表中合并時(shí)，如有元素值 個(gè)。LinkedList Union(LinkedList ha, hb)線性表 A 和 B 代表兩個(gè)集合，以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)，元素遞增有序。的頭指針。本算法求A和B的并集AUB,仍用線性表表示，結(jié)果鏈表元( pa=ha-next; pb=hb-next; /設(shè)工作指針 pa 和 pb 。pc=ha; pc 為結(jié)果鏈表當(dāng)前結(jié)點(diǎn)的前驅(qū)指針。while (pa&pb)if(pa-datadata)(pc-next=pa;pc=pa;pa=pa-next;else if(pa-datapb-data)(pcnext

25、=pb;pc=pb;pb=pb-next;else 處理 pa-data=pb-data.(pcnext=pa;pc=pa;pa=pa-next;u=pb;pb=pb-next;free(u);if (pa) pc-next=pa; /若 ha 表未空，則鏈入結(jié)果表。else pc-next=pb; / 若 hb 表未空，則鏈入結(jié)果表。 free(hb); 釋放 hb 頭結(jié)點(diǎn)return (ha); 算法 Union 結(jié)束。 與本題類似的其它幾個(gè)題解答如下：(1) 解答完全同上 2。(2) 本題是求交集，即只有同時(shí)出現(xiàn)在兩集合中的元素才出現(xiàn)在結(jié)果表中。其核心語(yǔ)句 段如下： pa=la-next

26、; pb=lbnext; 設(shè)工作指針 pa 和 pb ； pc=la; 結(jié)果表中當(dāng)前合并結(jié)點(diǎn)的前驅(qū)的指針。while(pa&pb)if (pa-data=pb-data) 交集并入結(jié)果表中。( pcnext=pa;pc=pa;pa=pa-next; u=pb;pb=pb-next;free (u); else if(pa-datadata) (u=pa;pa=pa-next;free(u); else (u=pb; pb=pb-next; free (u);while (pa) ( u=pa; pa=pa-next; free (u) ; / 釋放結(jié)點(diǎn)空間 while (pb) (u=pb;

27、pb=pb-next; free (u) ; / 釋放結(jié)點(diǎn)空間 pc-next=null; 置鏈表尾標(biāo)記。free (lb); 注：本算法中也可對(duì) B 表不作釋放空間的處理(3) 本題基本與 (2) 相同，但要求無(wú)重復(fù)元素，故在算法中，待合并結(jié)點(diǎn)數(shù)據(jù)要與其前 驅(qū)比較， 只有在與前驅(qū)數(shù)據(jù)不同時(shí)才并入鏈表。其核心語(yǔ)句段如下。pa=Ll-next;pb=L2-next; pa、 pb 是兩鏈表的工作指針。pc 二 LI; L1 作結(jié)果鏈表的頭指針。 while(pa&pb)if (pa-datadata) (u=pa; pa=pa-next; free (u) ; 刪除 LI 表多余元素 else

28、if (pa-datapb-data) pb=pb-next; pb 指針后移else 處理交集元素(if (pc=Ll) (pc-next=pa;pc=pa; pa=pa-next; / 處理第一個(gè)相等的元 素。 else if (pc-data=pa-data) ( u=pa; pa=pa-next; free (u) ; 重復(fù)元 素 不進(jìn)入 LI 表。else ( pcnext=pa; pc=pa;pa=pa-next; / 交集元素并入結(jié)果表。) whilewhile (pa) (u=pa; pa=pa-next; free (u) ; / 刪 LI 表剩余元素 pc-next=nul

29、l; 置結(jié)果鏈表尾。注：本算法中對(duì) L2 表未作釋放空間的處理。(4) 本題與上面 (3) 算法相同，只是結(jié)果表要另辟空間。(5) 題目分析本題首先求B和C的交集，即求 B和C中共有元素，再與A求并集，同時(shí)刪除重復(fù)元素，以保持結(jié)果 A 遞增。LinkedList union(LinkedList A, B, C) A,B和C均是帶頭結(jié)點(diǎn)的遞增有序的單鏈表，本算法實(shí)現(xiàn)A= AU (BAC)，使求解結(jié)構(gòu)保持遞增有序。(pa=A-next; pb=B-next; pc=C-next; /設(shè)置三個(gè)工作指針。中第一個(gè)元素為結(jié)果表的第一元pre=A; /pre 指向結(jié)果鏈表中當(dāng)前待合并結(jié)點(diǎn)的前驅(qū)。if (

30、pa-datadata| |pa-datadata) /A pre- next 二 pa;pre=pa;pa=pa-next;if(pb-datadata)pb=pb-next;else if(pb-datapcdata)pc=pcnext;else break; 找到 B 表和 C 表的共同元素就退出 while 循環(huán)。if (pb&pc) 11因共同元素而非 B表或C表空而退岀上面 while循環(huán)。if (pa-datapb-data) A表當(dāng)前元素值大于 B表和C表的公共元素，先將B表元素鏈入。(pre-next=pb;pre=pb;pb=pb-next; pc=pc-next; / B

31、, C公共元素為結(jié)果 表第一元素。 結(jié)束了結(jié)果表中第一元素的確定while(pa&pb&pc)(while(pb&pc)if(pb-datadata) pb=pb-next;else if(pb-datapcdata) pc=pcnext;else break; B表和C表有公共元素。if(pb&pc)(while (pa&pa-datadata)先將 A中小于 B, C公共元素部分鏈入。pre- next 二 pa;pre=pa;pa=pa-next;if(predata!=pb-data)(pre-next=pb;pre=pb;pb=pb-next;pc=pcnext;else(pb=pb

32、-next;pc=pc-next; /若 A 中已有 B, C 公共元素，則不再存 入結(jié)果表。 / while （pa&pb&pc）if （pa） pre-next=pa;當(dāng)B, C無(wú)公共元素（即一個(gè)表已空），將A中剩余鏈入。 算法 Union 結(jié)束 算法討論本算法先找結(jié)果鏈表的第一個(gè)元素，這是因?yàn)轭}目要求結(jié)果表要遞增有序（ 即刪除重復(fù)元素 ） 。這就要求當(dāng)前待合并到結(jié)果表的元素要與其前驅(qū)比較。由于初始pre=A （ 頭結(jié)點(diǎn)的頭指針 ），這時(shí)的 data 域無(wú)意義，不能與后繼比較元素大小，因此就需要確定第一個(gè)元素。當(dāng)然，不要這樣作，而直接進(jìn)入下面循環(huán)也可以，但在鏈入結(jié)點(diǎn)時(shí)，必須先判斷pre 是

33、否等于 A, 這占用了過多的時(shí)間。因此先將第一結(jié)點(diǎn)鏈入是可取的。算法中的第二個(gè)問題是要求時(shí)間復(fù)雜度為 0 （|A| + |B| + |C|）。這就要求各個(gè)表的工作指 針只能后移 （即不能每次都從頭指針開始查找 ）。本算法滿足這一要求。最后一個(gè)問題是，當(dāng)B, C有一表為空（即B和C已無(wú)公共元素時(shí)），要將A的剩余部分 鏈入結(jié)果表。3.題目分析循環(huán)單鏈表L1和L2數(shù)據(jù)結(jié)點(diǎn)個(gè)數(shù)分別為m和n ,將二者合成一個(gè)循環(huán)單鏈表時(shí)，需要將一個(gè)循環(huán)鏈表的結(jié)點(diǎn)（ 從第一元素結(jié)點(diǎn)到最后一個(gè)結(jié)點(diǎn)） 插入到另一循環(huán) 鏈表的第一元素結(jié)點(diǎn)前即可。題目要求“用最快速度將兩表合并“，因此應(yīng)找結(jié)點(diǎn)個(gè)數(shù)少的鏈表查其尾結(jié)點(diǎn)LinkedL

34、ist Union （LinkedList LI, L2;int m, n）/LI和L2分別是兩循環(huán)單鏈表的頭結(jié)點(diǎn)的指針，m和n分別是L1和L2的長(zhǎng)度。本算法用最快速度將(if (m01 |n0) (printf (if (m next!=LI) p=p- next;查最后一個(gè)元素結(jié)點(diǎn)。p-next=L2-next; 將 L1 循環(huán)單鏈表的元素結(jié)點(diǎn)插入到 L2 的第一元素結(jié)點(diǎn) 前。L2-next=Ll-next;free(Ll); 釋放無(wú)用頭結(jié)點(diǎn)。 處理完 mnext! =L2) p=p-next;查最后元素結(jié)點(diǎn)。p-next=Ll-next; 將 L2 的元素結(jié)點(diǎn)插入到 LI 循環(huán)單鏈表的第

35、一元素結(jié) 點(diǎn)前Ll-next=L2-next;free(L2); 釋放無(wú)用頭結(jié)點(diǎn)。 算法結(jié)束。類似本題敘述的其它題解答如下：(1) 題目分析本題將線性表 la 和 lb 連接，要求時(shí)間復(fù)雜度為 0(1), 且占用輔助空 間盡量 小。應(yīng)該使用只設(shè)尾指針的單循環(huán)鏈表。LinkedList Union(LinkedList la, lb)岳和 lb 是兩個(gè)無(wú)頭結(jié)點(diǎn)的循環(huán)單鏈表的尾指針，本算法將lb 接在 la 后，成為一 個(gè)單循環(huán)鏈表。( q=la-next; q 指向 la 的第一?個(gè)元素結(jié)點(diǎn)。la-next=lb-next; 將 lb 的最后元素結(jié)點(diǎn)接到 lb 的第一元素lb-next=q; r

36、eturn (lb); 算法結(jié)束。將 lb 指向 la 的第一元素結(jié)點(diǎn)，實(shí)現(xiàn)了 lb 接在 la 后。返回結(jié)果單循環(huán)鏈表的尾指針lb 。算法討論若循環(huán)單鏈表帶有頭結(jié)點(diǎn)，則相應(yīng)算法片段如下：q=lb-next; lb-next=la-next; la-next=q-next; free(q); q 指向 lb 的頭結(jié)點(diǎn)；/lb 的后繼結(jié)點(diǎn)為 la 的頭結(jié)點(diǎn)。/la 的后繼結(jié)點(diǎn)為 lb 的第一元素結(jié)點(diǎn)。釋放 lb 的頭結(jié)點(diǎn)return (lb); 返回結(jié)果單循環(huán)鏈表的尾指針 lb 。(2) 題目分析本題要求將單向鏈表ha和單向循環(huán)鏈表hb合并成一個(gè)單向鏈表，要求算法所需時(shí)間與鏈表長(zhǎng)度無(wú)關(guān)，只有使用

37、帶尾指針的循環(huán)單鏈表，這樣最容易找到鏈表的首、尾結(jié)點(diǎn)，將該結(jié)點(diǎn)序列插入到單向鏈表第一元素之前即可。其核心算法片段如下 ( 設(shè)兩鏈表均有頭結(jié)點(diǎn) )q=hb- next;單向循環(huán)鏈表的表頭指針hb- next=ha- next;將循環(huán)單鏈表最后元素結(jié)點(diǎn)接在 ha 第一元素前。ha- next=q- next; 將指向原單鏈表第一元素的指針指向循環(huán)單鏈表第一結(jié)點(diǎn)free(q):釋放循環(huán)鏈表頭結(jié)點(diǎn)。若兩鏈表均不帶頭結(jié)點(diǎn)，則算法片段如下：q=hb- next; q 指向 hb 首元結(jié)點(diǎn)。hb- next=ha; hb 尾結(jié)點(diǎn)的后繼是 ha 第一元素結(jié)點(diǎn)。ha=q; 頭指針指向 hb 的首元結(jié)點(diǎn)。4. 題

38、目分析 順序存儲(chǔ)結(jié)構(gòu)的線性表的插入，其時(shí)間復(fù)雜度為 0 (n), 平均移動(dòng)近一 半的元素。 線性表LA和LB合并時(shí)，若從第一個(gè)元素開始，一定會(huì)造成元素后移，這不符合本題“高效算法”的要求。另外，題中敘述“線性表空間足夠大”也喑示出另外合并方式，即應(yīng)從線性表的最后一個(gè)元素開始比較，大者放到最終位置上。設(shè)兩線性表的長(zhǎng)度各為m 和 n , 則結(jié)果表的最后一個(gè)元素應(yīng)在 m+n位置上。這樣從后向前，直到第一個(gè)元素為止。PROC Union(VAR LA:SeqList:LB:SeqList) LA和LB是順序存儲(chǔ)的非遞減有序線性表，本算法將LB合并到LA中，元素仍非遞減 有序。m: =LA. last

39、;n:=LB. last; m, n 分別為線性表 LA 和 LB 的長(zhǎng)度。k:=m+n; 10)AND(j0) DOIF LA. elemi =LB. elemjTHEN LA. elemk: =LA. elemi ;k: =kT ; i : =iT ;ELSE LA. elemk :=LB. elem j ;k:=kT : j :=jT :WHILE(j0) DO LA. elemk:=LB. elemj:k:=k-l:j:=j-l:LA. last:=m+n;ENDP;算法討論算法中數(shù)據(jù)移動(dòng)是主要操作。在最佳情況下(LB的最小元素大于 LA的最大 元素)，僅將LB的n個(gè)元素移(拷貝)到L

40、A中，時(shí)間復(fù)雜度為 0 (n),最差情況，LA的所 有元素都要移動(dòng)，時(shí)間 復(fù)雜度為0 (m+n)。因數(shù)據(jù)合并到 LA中，所以在退岀第一個(gè) WHILE循環(huán)后，只需要一個(gè)WHILE循環(huán)，處理 LB 中剩余元素。第二個(gè)循環(huán)只有在 LB 有剩余元素時(shí) 才執(zhí)行，而在 LA 有剩余元素時(shí)不執(zhí)行。本 算法利用了題目中“線性表空間足夠大”的條件，“最大限度的避免移動(dòng)元素”，是“一種高效算法”。5. 題目分析 本題實(shí)質(zhì)上是一個(gè)排序問題，要求“不得使用除該鏈表結(jié)點(diǎn)以外的任何鏈結(jié)點(diǎn)空間”。鏈表上的排序采用直接插入排序比較方便，即首先假定第一個(gè)結(jié)點(diǎn)有序，然后，從第二個(gè)結(jié)點(diǎn)開始，依次插入到前面有序鏈表中，最終達(dá)到整個(gè)鏈

41、表有序。LinkedList LinkListSort(LinkedList list)/list 是不帶頭結(jié)點(diǎn)的線性鏈表，鏈表結(jié)點(diǎn)構(gòu)造為 data 和 link 兩個(gè)域， data 是數(shù)據(jù) 域， link 是指針域。本算法將該鏈表按結(jié)點(diǎn)數(shù)據(jù)域的值的大小，從小到大重新鏈接。p=list- link; p 是工作指針，指向待排序的當(dāng)前元素。list- link=null; 假定第一個(gè)元素有序，即鏈表中現(xiàn)只有一個(gè)結(jié)點(diǎn)。while(p! 二 null)(r=p-link;是 p 的后繼。q=list;if (q-datap-data)處理待排序結(jié)點(diǎn) p 比第一?個(gè)元素結(jié)點(diǎn)小的情況。(p-link=l

42、ist;list=p; 鏈表指針指向最小元素。else 查找元素值最小的結(jié)點(diǎn)。/(while(q-link!=null&q-link-datadata)q=q-link; p-link=q-link;將當(dāng)前排序結(jié)點(diǎn)鏈入有序鏈表中。q-link=p; p=r; p 指向下個(gè)待排序結(jié)點(diǎn)算法討論算法時(shí)間復(fù)雜度的分析與用順序存儲(chǔ)結(jié)構(gòu)時(shí)的情況相同。但順序存儲(chǔ)結(jié)構(gòu)將 第 i(il) 個(gè)元素插入到前面第 1 至第 iT 個(gè)元素的有序表時(shí)，是將第 i 個(gè)元素先與第 i-1 個(gè)元素比較。而 在鏈表最佳情況均是和第一元素比較。兩種存儲(chǔ)結(jié)構(gòu)下最佳和最差情況的比 較次數(shù)相同，在鏈表情況 下，不移動(dòng)元素，而是修改結(jié)點(diǎn)指

43、針。list 不帶頭結(jié)點(diǎn)，而且要求“不得使用除該鏈表以外的 任何鏈結(jié) 還小的情況，這時(shí) 。如果 list 是頭結(jié)點(diǎn)的指針，則相應(yīng)處理要簡(jiǎn)單些 , 其算法片段如下： p 指向第一元素結(jié)點(diǎn)。有序鏈表初始化為空另一說(shuō)明是，本題中線性鏈表list點(diǎn)空間“，所以處理復(fù)雜，需要考慮當(dāng)前結(jié)點(diǎn)元素值比有序鏈表第一結(jié)點(diǎn)的元素值 要修改鏈表指針p=list-link;list-link=null;保存后繼while(p!=null)(r=p-link;q=list;while(q-link!=null & q-link-datadata)q=q-link;p-link=q-link;q-link=p;q 二 r

44、；6. 題目分析本題明確指出單鏈表帶頭結(jié)點(diǎn)，其結(jié)點(diǎn)數(shù)據(jù)是正整數(shù)且不相同，要求利 插入原則把鏈表整理成遞增有序鏈表。這就要求從第二結(jié)點(diǎn)開釋，將各結(jié)點(diǎn)依次插入 LinkedList LinkListlnsertSort (LinkedList la)房是帶頭結(jié)點(diǎn)的單鏈表，鏈表。其數(shù)據(jù)域是正整數(shù)。本算法利用直接插入原則將鏈表整理成遞用直接 到有序鏈表中。增的有序(if (la-next !=null)鏈表不為空表。 p 指向第一結(jié)點(diǎn)的后繼。直接插入原則認(rèn)為第一元素有序，然后從第二元素起依次插(p=la-next-next;入。查找插入位置。la-next-next=null;while(p!=nul

45、l)(r=p-next; 暫存 p 的后繼。q=la;while (q-next !=null&q-next-datadata) q=q-next; p-next=q-next; 將 p 結(jié)點(diǎn)鏈入鏈表。q-next=p;P=r;與本題有類似敘述的題的解答：(1) 本題也是鏈表排序問題，雖沒象上題那樣明確要求“利用直接插入的原則”來(lái)排序，仍可用上述算法求解，這里不再贅述。7. 題目分析 本題要求將一個(gè)鏈表分解成兩個(gè)鏈表，兩個(gè)鏈表都要有序，兩鏈表建立過程中不得使用NEW過程申請(qǐng)空間，這就是要利用原鏈表空間，隨著原鏈表的分解，新建鏈表隨之排序。PROC discreat(VAR listhead, P, Q:linkedlist)/listhead是單鏈表的頭指針，鏈表中每個(gè)結(jié)點(diǎn)由一個(gè)整數(shù)域DATA和指針域NEXT組成。本算法將鏈表listhead分解成奇數(shù)鏈表和偶數(shù)鏈表，分解由P和Q指向，且P和Q鏈表是 有序的。P: =NIL;Q: =NIL;s:=listhead;WHILE (sONIL) DO r:=sNEXT;IF s. DATA DIV