【正文】 return(lb)。 lanext=lbnext。應(yīng)該使用只設(shè)尾指針的單循環(huán)鏈表。 free(L2)?！尾樽詈笤亟Y(jié)點(diǎn)。 } }∥處理完 mn情況 else∥ 下面處理 L2長(zhǎng)度小于等于 L1的情況 {if(n==0)return(L1)?！螌?L1 循環(huán)單鏈表的元素結(jié)點(diǎn)插入到 L2 的第一元素結(jié)點(diǎn)前。 else{p=L1。 {if(m0||n0) {printf(“表長(zhǎng)輸入錯(cuò)誤 \n” )； exit(0)。題目要求“用最快速度將兩表合并“，因此應(yīng)找結(jié)點(diǎn)個(gè)數(shù)少的鏈表查其尾結(jié)點(diǎn)。這就要求各個(gè)表的工作指針只能后移（即不能每次都從頭指針開始查找）。由于初始 pre=A（頭結(jié)點(diǎn)的頭指針），這時(shí)的 data域無意義，不能與后繼比較元素大小，因此就需要確定第一個(gè)元素。pc) if(pa) prenext=pa。 } }∥ while(paamp。pc=pcnext。pa=panext。amp。 ∥ B表和 C表有公共元素。amp。amp。pb=pbnext。pc)∥ 因共同元素而非 B表或 C表空而退出上面 while 循環(huán)。 else break。amp。 {prenext=pa?！卧O(shè)置三個(gè)工作指針。 LinkedList union(LinkedList A,B,C) ∥ A,B和 C均是帶頭結(jié)點(diǎn)的遞增有序的單鏈表，本算法實(shí)現(xiàn) A= A∪（ B∩ C），使求解結(jié)構(gòu)保 持遞增有序。 ∥置結(jié)果鏈表尾。 } ∥ while while(pa) {u=pa。 else{ pcnext=pa。 else if(pcdata==padata){ u=pa。 ∥ pb指針后移 else ∥處理交集元素 {if(pc==L1) {pcnext=pa。pb) if(padatapbdata) {u=pa。 pc=L1。其核心語(yǔ)句段如下。}∥釋放結(jié)點(diǎn)空間 pcnext=null。 free(u)。 pb=pbnext。} else if(padatapbdata) {u=pa。pa=panext。amp。pb=lbnext。 }∥算法 Union結(jié)束。 else pcnext=pb。pb=pbnext。} else∥處理 padata=pbdata. {pcnext=pa。pa=panext。 while(paamp。pb=hbnext。 LinkedList Union(LinkedList ha,hb) ∥線性表 A和 B代表兩個(gè)集合，以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)，元素遞增有序。 2． [題目分析 ]本組題有 6個(gè)，本質(zhì)上都是鏈表的合并操作，合并中有各種條件。 free(la)。pc=pb。pb) if(padatapbdata) {pcnext=pa。 lc=(LinkedList )malloc(sizeof(LNode))?！吾尫蓬^結(jié)點(diǎn) .ha,hb指針未被破壞。∥不要 hb的相等數(shù)據(jù) } if(pa!=null)prenext=pa。 pre=pa。 pb=pbnext?！紊暾?qǐng)空間 rdata=pbdata。pre=pa。 ∥ pre指向當(dāng)前待合并結(jié)點(diǎn)的前驅(qū)?！紊暾?qǐng)頭結(jié)點(diǎn)，以便操作。 LinkedList Union(LinkedList ha, hb) ∥ ha 和 hb 是兩個(gè)無頭結(jié)點(diǎn)的數(shù)據(jù)域值遞增有序的單鏈表，本算法將 hb 中并不出現(xiàn)在 ha中的數(shù)據(jù)合并到 ha中，合并中不能破壞 hb鏈表。也可先合并完，再作鏈表逆置。 } }∥算法 Union結(jié)束。 } while(pb!=null) {r=pbnext。 {r=panext。 lanext=pb。 } else {r=pbnext。 ∥將 pa結(jié)點(diǎn)鏈于結(jié)果表中，同時(shí)逆置。amp。 pb=lbnext。該問題要求結(jié)果鏈表按元素值遞減次序排列。 (4)r=rnext。 2） (1)rprior=qprior。 pprenext=s。 總之，兩次調(diào)用將 L 循環(huán)鏈表分解為兩個(gè)。 18． mp是一個(gè)過程，其內(nèi)嵌套有過程 subp。 p^.rlink^.llink p^.llink。 p^.llink:=q^.llink。 S2 記原 pa鏈表中刪除的結(jié)點(diǎn)個(gè)數(shù)。 ∥查找失敗 else return(p)。 (3) while(p!=null amp。amp。 pdata!=X) p=pnext。 prenext=s。 pnext=qnext。然后從第一元素結(jié)點(diǎn)開始，直到最后一個(gè)結(jié)點(diǎn)為止，依次前插入頭結(jié)點(diǎn)的后面，則實(shí)現(xiàn)了鏈表的逆置。 9. 在單鏈表中不能從當(dāng)前結(jié)點(diǎn)（若當(dāng)前結(jié)點(diǎn)不是第一結(jié)點(diǎn)）出發(fā)訪問到任何一個(gè)結(jié)點(diǎn)，鏈表只能從頭指針開始，訪問到鏈表中每個(gè)結(jié)點(diǎn)。 7． 見上題 6。 6．在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，頭指針指鏈表的指針，若鏈表有頭結(jié)點(diǎn)則是鏈表的頭結(jié)點(diǎn)的指針，頭指針具有標(biāo)識(shí)作用，故常用頭指針冠以鏈表的名字。 next:pointer。 last:0..maxlen。 3．采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，它根據(jù)實(shí)際需要申請(qǐng)內(nèi)存空間，而當(dāng)不需要時(shí)又可將不用結(jié)點(diǎn)空間返還給系統(tǒng)。順序表可以隨機(jī)存取，時(shí)間復(fù)雜度為 O（ 1）。amp。 (5)r^.next:=q^.next。 (7)r (8)p (9)r (10)NIL (11)NIL 34． (1)pa!=ha ∥或 paexp!=1 (2)paexp==0 ∥若指數(shù)為 0，即本項(xiàng)為常數(shù)項(xiàng) (3)qnext=panext ∥刪常數(shù)項(xiàng) (4)qnext ∥取下一元素 (5)=pacoef*paexp (6) ∥指數(shù)項(xiàng)減 1 (7)pa ∥前驅(qū)后移 ,或 qnext (8)panext ∥取下一元素 35． (1)q:=p。 ∥待逆置結(jié)點(diǎn) (3)L=p。 p^.pre:=q。 qnextpre=qpre?！?q指向最小值結(jié)點(diǎn)， s是工作指針 (3)s:=s^.link∥工作指針后移 (4)head:=head^.next?！涡纬裳h(huán)鏈表 (D)j:=0。 ∥ p后繼的前驅(qū)是 s (6)s^.left:=p。 (3) r^.next:=q。若 pa為空，則匹配成功，返回 true，否則，返回 false。(5)IF pa=NIL THEN return(true) ELSE return(false)。 pb:=pbnext。 (4) pb:=pb^.next。 Lprior==L 18． snext=pnext。 pnext=unext。 pnextprior=f。 pxnext=py 4 ． ni+1 5．主要是使插入和刪除等操作統(tǒng)一，在第一個(gè)元素之前插入 元素 和刪除第一個(gè)結(jié)點(diǎn)不必另作判斷。 7．集合中元素?zé)o邏輯關(guān)系。第 2 章 線性表 一．選擇題 ,C 二．判斷題 1. 2.√ 3. √ 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. √ 15. 16. √ 部分答案解釋如下。 4．兩種存儲(chǔ)結(jié)構(gòu)各有優(yōu)缺點(diǎn)，應(yīng)根據(jù)實(shí)際情況選用，不能籠統(tǒng)說哪一個(gè)好。 三．填空題 1．順序 2．（ n1） /2 3． pynext=pxnext。 fprior=p。 14 ． u=pnext。amp。 (2) pbNIL AND pa^.data=pb^.data (3) return(inclusion(pa,pb))。 (2) paNIL AND pbNIL AND pb^.data=pa^.data (3)pa:=pa^.next。pa:=pa^.next。若主串與子串對(duì)應(yīng)數(shù)據(jù)相等，兩串工作指針 pa和 pb 后移；否則，主串工作指針從 pre的下一結(jié)點(diǎn)開始（這時(shí) pre 又指向新的開始結(jié)點(diǎn)），子串工作指針從子串第一元素開始，比較一直繼續(xù)到循環(huán)條件失敗。 （ 2） r^.next:=p。 (3)p:=p^.right ∥工作指針后移 (4)s^.left:=p (5)p^.right^.left:=s?！涡碌那膀?qū) (C)p^.link:=head。 (2)q:=s。∥頭結(jié)點(diǎn) l這時(shí)起監(jiān)視哨作用 (2) l^.freq:=p^.freq ∥頭結(jié)點(diǎn)起監(jiān)視哨作用 (3) qprenext=qnext。 p^.prenext:=q。 ∥暫存后繼 (2)q=L。 (5) p:=r 33. (1)r (2)NIL (3)xhead^.data (4)p^.datax (5)p:=p^.next (6)p^.data=x。 ∥或 q:=q^.next。 37．程序（ a） PASCAL部分 (編者略） 程序（ b） C部分 (1)(A!=null amp。 （ 2）選順序存儲(chǔ)結(jié)構(gòu)。其缺點(diǎn)是因?yàn)橹羔樤黾恿丝臻g開銷，當(dāng)空間不允 許時(shí)，就不能克服順序存儲(chǔ)的缺點(diǎn)。 順序存儲(chǔ)結(jié)構(gòu)的定義是： CONST maxlen=線性表可能達(dá)到的最大長(zhǎng)度； TYPE sqlisttp=RECORD elem:ARRAY[1..maxlen] OF ElemType。 nodetype=RECORD data:ElemType。 射時(shí)， ai與 ai+1的物理位置相鄰；鏈表表示時(shí) ai與 ai+1的物理位置不要求相鄰。首元結(jié)點(diǎn)也就是第一元素結(jié)點(diǎn)，它是頭結(jié) 點(diǎn)后邊的第一個(gè)結(jié)點(diǎn)。 (3) stalist[p].next。設(shè)該鏈表帶頭結(jié)點(diǎn)，將頭結(jié)點(diǎn)摘下，并將其指針域置空。 12． q=pnext。 snext=p。amp?！尾檎页晒? (2) while(p!=null amp?！尾檎沂? else return(p)。 if(p==null || pdataX) return(null)。 S1記結(jié)果鏈表中結(jié)點(diǎn)個(gè)數(shù)（即 pa與 pb中相等的元素個(gè)數(shù)）。 p^.rlink^.llink:=q。 q^.llink:=p 17.(1)前兩個(gè)語(yǔ)句改為： ^.rlink p^.rlink。 p^.rlink q。 subp(pb,pa)調(diào)用結(jié)果是將 pb到 pa的前驅(qū)（指在 L鏈表中，并非剛構(gòu)造的 pa循環(huán)鏈表中）構(gòu)造為循環(huán)鏈表。 snext=p。 21. 1）本算法功能是將雙向循環(huán)鏈表結(jié)點(diǎn)的數(shù)據(jù)域按值自小到大排序，成為非遞減（可能包括數(shù)據(jù)域值相等的結(jié)點(diǎn)）有序雙向循環(huán)鏈表?！危?2）（ 3）將 q結(jié)點(diǎn)插入 (3)pnext=q。 五、 算法設(shè)計(jì)題 1． [題目分析 ]因?yàn)閮涉湵硪寻丛刂颠f增次序排列，將其合并時(shí)，均從第一個(gè)結(jié)點(diǎn)起進(jìn)行比較，將小的鏈入鏈表中，同時(shí)后移鏈表工作指針。 { pa=lanext。 while(pa!=null amp。 panext=lanext。 ∥恢復(fù) pa為當(dāng)前待比較結(jié)點(diǎn)。 ∥將 pb結(jié)點(diǎn)鏈于結(jié)果表中，同時(shí)逆置。 } while(pa!=null) ∥將 la表的剩余部分鏈入結(jié)果表，并逆置。 pa=r。 pb=r。pb),兩遞增有序表合并成遞減有序表時(shí)，上述算法是邊合并邊逆置。 與本題類似的其它題解答如下： （１）［問題分析］與上題類似，不同之處在于：一是鏈表無