【正文】 回“ false“。 pre指向當(dāng)前結(jié)點(diǎn)， p指向 pre的后繼。 12． q=pnext。 pnext=qnext。 free(q)。 13. 設(shè)單鏈表的頭結(jié)點(diǎn)的 頭指針為 head,且 pre=head； while(prenext!=p) pre=prenext。 snext=p。 prenext=s。 ，工作指針 p初始化為 p=Hnext。 (1) while(p!=null amp。amp。 pdata!=X) p=pnext。 if(p= =null) return(null)?！尾檎沂? else return(p)?！尾檎页晒? (2) while(p!=null amp。amp。 pdataX ) p=pnext。 if(p==null || pdataX) return(null)?！尾檎沂? else return(p)。 (3) while(p!=null amp。amp。 pdataX) p=pnext。 if(p==null || pdataX) return(null)。 ∥查找失敗 else return(p)。 ∥查找成功 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^.rlink:=p^.rlink。 p^.rlink^.llink:=q。 p^.llink:=q^.llink。 q^.llink^.rlink:=p。 p^.rlink:=q。 q^.llink:=p 17.(1)前兩個(gè)語句改為： ^.rlink p^.rlink。 p^.rlink^.llink p^.llink。 (2)后三個(gè)語句序列應(yīng)改為： q^.rlink p^.rlink?！我韵氯涞捻樞虿荒茏? p^.rlink^.llink q。 p^.rlink q。 18． mp是一個(gè)過程，其內(nèi)嵌套有過程 subp。 subp(s,q)的作用是構(gòu)造從 s到 q的循環(huán)鏈表。 subp(pa,pb)調(diào)用結(jié)果是將 pa 到 pb的前驅(qū)構(gòu)造為循環(huán)鏈表。 subp(pb,pa)調(diào)用結(jié)果是將 pb到 pa的前驅(qū)（指在 L鏈表中，并非剛構(gòu)造的 pa循環(huán)鏈表中）構(gòu)造為循環(huán)鏈表。 總之，兩次調(diào)用將 L 循環(huán)鏈表分解為兩個(gè)。第一個(gè)循環(huán)鏈表包含從 pa 到 pb 的前驅(qū) ,L中除剛構(gòu)造的 pa到 pb前驅(qū)外的結(jié)點(diǎn)形成第二個(gè)循環(huán)鏈表。 19．在指針 p所指結(jié)點(diǎn)前插入結(jié)點(diǎn) s的語句如下： spre=ppre。 snext=p。 pprenext=s。 ppre=s。 20． (A) f1NIL并且 f2NIL (B) f1↑ .data f2↑ .data (C) f2↑ .dataf1↑ .data (D) f3↑ .dataf1↑ .data (E) f1 f1↑ .link 或 f2=f2↑ .link。 21. 1）本算法功能是將雙向循環(huán)鏈表結(jié)點(diǎn)的數(shù)據(jù)域按值自小到大排序，成為非遞減（可能包括數(shù)據(jù)域值相等的結(jié)點(diǎn)）有序雙向循環(huán)鏈表。 2） (1)rprior=qprior?！螌?q結(jié)點(diǎn)摘下，以便插入到適當(dāng)位置。 (2)pnextprior=q?！危?2）（ 3）將 q結(jié)點(diǎn)插入 (3)pnext=q。 (4)r=rnext。或 r=qnext?！魏笠浦羔?，再將新結(jié)點(diǎn)插入 到適當(dāng)位置。 五、 算法設(shè)計(jì)題 1． [題目分析 ]因?yàn)閮涉湵硪寻丛刂颠f增次序排列，將其合并時(shí)，均從第一個(gè)結(jié)點(diǎn)起進(jìn)行比較，將小的鏈入鏈表中，同時(shí)后移鏈表工作指針。該問題要求結(jié)果鏈表按元素值遞減次序排列。故在合并的同時(shí)，將鏈表結(jié)點(diǎn)逆置。 LinkedList Union(LinkedList la,lb) ∥ la,lb分別是帶頭結(jié)點(diǎn)的兩個(gè)單鏈表的頭指針，鏈表中的元素值按遞增序排列，本算法將兩鏈表合并成一個(gè)按元素值遞減次序排列的單鏈表。 { pa=lanext。 pb=lbnext?！?pa， pb分別是 鏈表 la和 lb 的工作指針 lanext=null。 ∥ la 作結(jié)果鏈表的頭指針，先將結(jié)果鏈表初始化為空。 while(pa!=null amp。amp。 pb!=null) ∥當(dāng)兩鏈表均不為空時(shí)作 if(padata=pbdata) { r=panext。 ∥將 pa 的后繼結(jié)點(diǎn)暫存于 r。 panext=lanext。 ∥將 pa結(jié)點(diǎn)鏈于結(jié)果表中，同時(shí)逆置。 lanext=pa。 pa=r。 ∥恢復(fù) pa為當(dāng)前待比較結(jié)點(diǎn)。 } else {r=pbnext?！? 將 pb 的后繼結(jié)點(diǎn)暫存于 r。 pbnext=lanext。 ∥將 pb結(jié)點(diǎn)鏈于結(jié)果表中，同時(shí)逆置。 lanext=pb。 pb=r。 ∥恢復(fù) pb為當(dāng)前待比較結(jié)點(diǎn)。 } while(pa!=null) ∥將 la表的剩余部分鏈入結(jié)果表，并逆置。 {r=panext。 panext=lanext。 lanext=pa。 pa=r。 } while(pb!=null) {r=pbnext。 pbnext=lanext。 lanext=pb。 pb=r。 } }∥算法 Union結(jié)束。 ［算法討論］上面兩鏈表均不為空的表達(dá)式也可簡(jiǎn)寫為 while(paamp。amp。pb),兩遞增有序表合并成遞減有序表時(shí)，上述算法是邊合并邊逆置。也可先合并完，再作鏈表逆置。后者不如前者優(yōu)化。算法中最后兩個(gè) while語句，不可能執(zhí)行兩個(gè)，只能二者取一，即哪個(gè)表尚未到尾，就將其逆置到結(jié) 果表中，即將剩余結(jié)點(diǎn)依次前插入到結(jié)果表的頭結(jié)點(diǎn)后面。 與本題類似的其它題解答如下： （１）［問題分析］與上題類似，不同之處在于：一是鏈表無頭結(jié)點(diǎn)，為處理方便，給加上頭結(jié)點(diǎn)，處理結(jié)束再刪除之；二是數(shù)據(jù)相同的結(jié)點(diǎn)，不合并到結(jié)果鏈表中；三是 hb 鏈表不能被破壞，即將 hb的結(jié)點(diǎn)合并到結(jié)果鏈表時(shí)，要生成新結(jié)點(diǎn)。 LinkedList Union(LinkedList ha, hb) ∥ ha 和 hb 是兩個(gè)無頭結(jié)點(diǎn)的數(shù)據(jù)域值遞增有序的單鏈表，本算法將 hb 中并不出現(xiàn)在 ha中的數(shù)據(jù)合并到 ha中，合并中不能破壞 hb鏈表。 ｛ LinkedList la。 la=(LinkedList)malloc(sizeof(LNode))。 lanext=ha。∥申請(qǐng)頭結(jié)點(diǎn)，以便操作。 pa=ha。 ∥ pa是 ha鏈表的工作指針 pb=hb。 ∥ pb是 hb鏈表的工作指針 pre=la。 ∥ pre指向當(dāng)前待合并結(jié)點(diǎn)的前驅(qū)。 while(paamp。amp。pb) if(padatapbdata)∥處理 ha中數(shù)據(jù) {prenext=pa。pre=pa。pa=panext。} else if(padatapbdata)∥處理 hb中數(shù)據(jù)。 {r=(LinkedList)malloc(sizeof(LNode))?！紊暾?qǐng)空間 rdata=pbdata。 prenext=r。 pre=r?！螌⑿陆Y(jié)點(diǎn)鏈入結(jié)果鏈表。 pb=pbnext。∥ hb鏈表中工作指針后移。 } else∥處理 padata=pbdata。 {prenext=pa。 pre=pa。 pa=panext。∥兩結(jié)點(diǎn)數(shù)據(jù)相等時(shí)，只將 ha的數(shù)據(jù)鏈入。 pb=pbnext?！尾灰?hb的相等數(shù)據(jù) } if(pa!=null)prenext=pa?！螌涉湵碇惺Ｓ嗖糠宙溔虢Y(jié)果鏈表。 else prenext=pb。 free(la)?！吾尫蓬^結(jié)點(diǎn) .ha,hb指針未被破壞。 }∥算法 nion結(jié)束。 (2)本題與上面兩題類似，要求結(jié)果指針為 lc，其核心語句段如下： pa=lanext。pb=hbnext。 lc=(LinkedList )malloc(sizeof(LNode))。 pc=lc?！?pc是結(jié)果鏈表中當(dāng)前結(jié)點(diǎn)的前驅(qū) while(paamp。amp。pb) if(padatapbdata) {pcnext=pa。pc=pa。pa=panext。} else {pcnext=pb。pc=pb。pb=pbnext。} if(pa)pcnext=pa。 else pcnext=pb。 free(la)。free(lb)。∥釋放原來兩鏈表的頭結(jié)點(diǎn)。 算法時(shí)間復(fù)雜度為 O（ m+n），其中 m和 n分別為鏈表 la和 lb的長(zhǎng)度。 2． [題目分析 ]本組題有 6個(gè)，本質(zhì)上都是鏈表的合并操作，合并中有各種條件。與前組題不同的是，敘述上是用線性表代表集合，而操作則是求集合的并、交、差（ A∪ B， A∩ B， AB）等。 本題與上面 1．（ 2）基本相同，不同之處 1．（ 2）中鏈表是“非遞減有序”，（可能包含相等元素），本題是元素“遞增有序”（不準(zhǔn)有相同元素）。因此兩表中合并 時(shí)，如有元素值相等元素，則應(yīng)刪掉一個(gè)。 LinkedList Union(LinkedList ha,hb) ∥線性表 A和 B代表兩個(gè)集合，以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)，元素遞增有序。 ha和 hb分別是其鏈表的頭指針。本算法求 A 和 B 的并集 A∪ B，仍用線性表表示，結(jié)果鏈表元素也是遞增有序。 { pa=hanext。pb=hbnext?！卧O(shè)工作指針 pa 和 pb。 pc=ha?！?pc為結(jié)果鏈表當(dāng)前結(jié)點(diǎn)的前驅(qū)指針。 while(paamp。amp。pb) if(padatapbdata) {pcnext=pa。pc=pa。pa=panext。} else if(padatapbdata) {pcnext=pb。pc=pb。pb=pbnext。} else∥處理 padata=pbdata. {pcnext=pa。pc=pa。pa=panext。 u=pb。pb=pbnext。free(u)。} if(pa) pcnext=pa。∥ 若 ha表未空，則鏈入結(jié)果表。 else pcnext=pb?！稳?hb表未空，則鏈入結(jié)果表。 free(hb)。 ∥釋放 hb頭結(jié)點(diǎn) return(ha)。 }∥算法 Union結(jié)束。 與本題類似的其它幾個(gè)題解答如下： (1) 解答完全同 上 2。 (2) 本題是求交集，即只有同時(shí)出現(xiàn)在兩集合中的元素才出現(xiàn)在結(jié)果表中。其核心語句段如下： pa=lanext。pb=lbnext?！卧O(shè)工作指針 pa和 pb； pc=la?！谓Y(jié)果表中當(dāng)前合并結(jié)點(diǎn)的前驅(qū)的指針。 while(paamp。amp。pb) if(padata==pbdata)∥交集并入結(jié)果表中。 { pcnext=pa。pc=pa。pa=panext。 u=pb。pb=pbnext。free(u)。} else if(padatapbdata) {u=pa。pa=panext。free(u)。} else {u=pb。 pb=pbnext。 free(u)。} while(pa){ u=pa。 pa=panext。 free(u)。}∥ 釋放結(jié)點(diǎn)空間 while(pb) {u=pb。 pb=pbnext。 free(u)。}∥釋放結(jié)點(diǎn)空間 pcnext=null?！沃面湵砦矘?biāo)記。 free(lb)。 ∥注： 本算法中也可對(duì) B表不作釋放空間的處理 （ 3）本題基本與（ 2）相同，但要求無重復(fù)元素，故在算法中，待合并結(jié)點(diǎn)數(shù)據(jù)要與其前驅(qū)比較 ，只有在與前驅(qū)