【正文】 k=0； while（ q!=null amp。另外，算法中應(yīng)判斷 i， len和 j的合法性。 if（ p==null） return（ 1）；∥鏈表中心對(duì)稱 else return（ 0）； ∥鏈表不中心對(duì)稱 }∥算法結(jié)束。 {char s[]。第三，本算法可以寫成三 個(gè)函數(shù)，查找函數(shù)，交換后繼函數(shù)與插入函數(shù)。 if（ lowhigh） ∥查找失敗，插入數(shù)據(jù)元素 x {for（ i=n1； ihigh； i） a[i+1]=a[i]；∥后移元素。本算法在表中查找數(shù)值為 x的元素，如查到則與其后繼交換位置；如查不到，則插入表中，且使表仍遞增有序。 11． [題目分析 ] 知道雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，與前驅(qū)交換涉及到四個(gè)結(jié)點(diǎn)（ p結(jié)點(diǎn)，前驅(qū)結(jié)點(diǎn)，前驅(qū)的前驅(qū)結(jié)點(diǎn)，后繼結(jié)點(diǎn)）六條鏈。 10． [題目分析 ] 本題要求將鏈表中數(shù)據(jù)域值最小的結(jié)點(diǎn)移到鏈表的最前面。假定鏈表非空。 9． [題目分析 ] 本題要求在單鏈表中刪除最小值結(jié)點(diǎn)。 (5) 本題與第 8題基本相同，不同之處在于這里的分界元素是整數(shù) 19（鏈表中并不要求一定有 19）。 while(in) {if(A[i]0) C[++k]=A[i++]。 ∥參考元素置于分界位置。 ∥將大于參考元素的元素后移。j=n。算法只是按題目要求把正負(fù)數(shù)分開，如要求統(tǒng)計(jì)負(fù)數(shù)和大于等于零的個(gè)數(shù)，則最后以 t來定。amp。 while(ij) {while(ij amp。 int Rearrange（ SeqList a?！?rb指向新的尾結(jié)點(diǎn)； } else∥處理原序號(hào)為奇數(shù)的結(jié)點(diǎn)。 Anext=null。 Bnext=null。分解后的 A 表含有原表中序號(hào)為奇數(shù)的元素， B表含有原 A表中序號(hào)為偶數(shù)的元素。 else {pnext=Cnext。 Bnext=null。 void DisCreat1(LinkedList A) ∥ A是帶頭結(jié)點(diǎn)的單鏈表，鏈表中結(jié)點(diǎn)的數(shù)據(jù)類型為整型?！?s指向新的待排序結(jié)點(diǎn)。 Q:=s。 ∥鏈入此結(jié)點(diǎn)。P^.NEXT:=NIL。 P:=NIL。 pnext=qnext。∥直接插入原則認(rèn)為第一元素有序，然后從第二元素起依次插入。 } 6． [題目分析 ]本題明確指出單鏈表帶頭結(jié)點(diǎn)，其結(jié)點(diǎn)數(shù)據(jù)是正整數(shù)且不相同，要求利用直接插入原則把鏈表整理成遞增有序鏈表?！斡行蜴湵沓跏蓟癁榭? while(p!=null) {r=plink。 } } [算法討論 ]算法時(shí)間復(fù)雜度的分析與用順序存儲(chǔ)結(jié)構(gòu)時(shí)的情況相同。 {while(qlink!=nullamp。 while(p!=null) {r=plink。 5． [題目分析 ]本題實(shí)質(zhì)上是一個(gè)排序問題，要求“不得使用除該鏈表結(jié)點(diǎn)以外的任何鏈結(jié)點(diǎn)空間”。j:=j1。 WHILE(i0)AND(j0)DO IF [i]=[j] THEN[[k]:=[i]。 m:=。 ∥頭指針指向 hb的首元結(jié)點(diǎn)。 hanext=qnext。 ∥ la的后繼結(jié)點(diǎn)為 lb的第一元素結(jié)點(diǎn)。 ∥將 lb指向 la的第一元素結(jié)點(diǎn)，實(shí)現(xiàn)了 lb接在 la后。 類似本題敘述的其它題解答如下： （ 1） [題目分析 ]本題將線性表 la和 lb連接，要求時(shí)間復(fù)雜度為 O（ 1），且占用輔助空間盡量小。 while(pnext!=L2) p=pnext。 pnext=L2next。 ∥本算法用最快速度將 L1和 L2合并成一個(gè)循環(huán)單鏈表。 算法中的 第二個(gè)問題是要求時(shí)間復(fù)雜度為 O（ |A|+|B|+|C|）。amp。pb=pbnext。pc) {while(paamp。pc) {while(pbamp。pre=pb。 else if(pbdatapcdata)pc=pcnext。 if(padatapbdata||padatapcdata)∥ A 中第一個(gè)元素為結(jié)果表的第一元素。 （ 5） [題目分析 ]本題首先求 B和 C的交集，即求 B和 C中共有元素，再與 A求并集，同時(shí)刪除重復(fù)元素，以保持結(jié)果 A遞增。} ∥交集元素并入結(jié)果表。} ∥處理第一個(gè)相等的元素。amp。 ∥注： 本算法中也可對(duì) B表不作釋放空間的處理 （ 3）本題基本與（ 2）相同，但要求無重復(fù)元素，故在算法中，待合并結(jié)點(diǎn)數(shù)據(jù)要與其前驅(qū)比較 ，只有在與前驅(qū)數(shù)據(jù)不同時(shí)才并入鏈表。 pa=panext。free(u)。 while(paamp。 ∥釋放 hb頭結(jié)點(diǎn) return(ha)。 u=pb。pc=pa。 { pa=hanext。 算法時(shí)間復(fù)雜度為 O（ m+n），其中 m和 n分別為鏈表 la和 lb的長度。} else {pcnext=pb。pb=hbnext。 pb=pbnext。∥將新結(jié)點(diǎn)鏈入結(jié)果鏈表。pb) if(padatapbdata)∥處理 ha中數(shù)據(jù) {prenext=pa。 lanext=ha。pb),兩遞增有序表合并成遞減有序表時(shí)，上述算法是邊合并邊逆置。 pa=r。 ∥將 pb結(jié)點(diǎn)鏈于結(jié)果表中，同時(shí)逆置。 panext=lanext。 { pa=lanext?！危?2）（ 3）將 q結(jié)點(diǎn)插入 (3)pnext=q。 snext=p。 p^.rlink q。 p^.rlink^.llink:=q。 if(p==null || pdataX) return(null)?！尾檎页晒? (2) while(p!=null amp。 snext=p。設(shè)該鏈表帶頭結(jié)點(diǎn)，將頭結(jié)點(diǎn)摘下，并將其指針域置空。首元結(jié)點(diǎn)也就是第一元素結(jié)點(diǎn)，它是頭結(jié) 點(diǎn)后邊的第一個(gè)結(jié)點(diǎn)。 nodetype=RECORD data:ElemType。其缺點(diǎn)是因?yàn)橹羔樤黾恿丝臻g開銷，當(dāng)空間不允 許時(shí)，就不能克服順序存儲(chǔ)的缺點(diǎn)。 37．程序（ a） PASCAL部分 (編者略） 程序（ b） C部分 (1)(A!=null amp。 (5) p:=r 33. (1)r (2)NIL (3)xhead^.data (4)p^.datax (5)p:=p^.next (6)p^.data=x。 p^.prenext:=q。 (2)q:=s。 (3)p:=p^.right ∥工作指針后移 (4)s^.left:=p (5)p^.right^.left:=s。若主串與子串對(duì)應(yīng)數(shù)據(jù)相等，兩串工作指針 pa和 pb 后移；否則，主串工作指針從 pre的下一結(jié)點(diǎn)開始（這時(shí) pre 又指向新的開始結(jié)點(diǎn)），子串工作指針從子串第一元素開始，比較一直繼續(xù)到循環(huán)條件失敗。 (2) paNIL AND pbNIL AND pb^.data=pa^.data (3)pa:=pa^.next。amp。 fprior=p。 4．兩種存儲(chǔ)結(jié)構(gòu)各有優(yōu)缺點(diǎn)，應(yīng)根據(jù)實(shí)際情況選用，不能籠統(tǒng)說哪一個(gè)好。 7．集合中元素?zé)o邏輯關(guān)系。 pnextprior=f。 Lprior==L 18． snext=pnext。 pb:=pbnext。若 pa為空，則匹配成功，返回 true，否則，返回 false。 ∥ p后繼的前驅(qū)是 s (6)s^.left:=p?！?q指向最小值結(jié)點(diǎn)， s是工作指針 (3)s:=s^.link∥工作指針后移 (4)head:=head^.next。 p^.pre:=q。 (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。amp。 3．采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，它根據(jù)實(shí)際需要申請(qǐng)內(nèi)存空間，而當(dāng)不需要時(shí)又可將不用結(jié)點(diǎn)空間返還給系統(tǒng)。 next:pointer。 7． 見上題 6。然后從第一元素結(jié)點(diǎn)開始，直到最后一個(gè)結(jié)點(diǎn)為止，依次前插入頭結(jié)點(diǎn)的后面，則實(shí)現(xiàn)了鏈表的逆置。 prenext=s。amp。 ∥查找失敗 else return(p)。 p^.llink:=q^.llink。 18． mp是一個(gè)過程，其內(nèi)嵌套有過程 subp。 pprenext=s。 (4)r=rnext。 pb=lbnext。 ∥將 pa結(jié)點(diǎn)鏈于結(jié)果表中，同時(shí)逆置。 lanext=pb。 } while(pb!=null) {r=pbnext。也可先合并完，再作鏈表逆置?！紊暾?qǐng)頭結(jié)點(diǎn)，以便操作。pre=pa。 pb=pbnext?！尾灰?hb的相等數(shù)據(jù) } if(pa!=null)prenext=pa。 lc=(LinkedList )malloc(sizeof(LNode))。pc=pb。 2． [題目分析 ]本組題有 6個(gè)，本質(zhì)上都是鏈表的合并操作，合并中有各種條件。pb=hbnext。pa=panext。pb=pbnext。 }∥算法 Union結(jié)束。amp。} else if(padatapbdata) {u=pa。 free(u)。其核心語句段如下。pb) if(padatapbdata) {u=pa。 else if(pcdata==padata){ u=pa。 } ∥ while while(pa) {u=pa。 LinkedList union(LinkedList A,B,C) ∥ A,B和 C均是帶頭結(jié)點(diǎn)的遞增有序的單鏈表，本算法實(shí)現(xiàn) A= A∪（ B∩ C），使求解結(jié)構(gòu)保 持遞增有序。 {prenext=pa。 else break。pb=pbnext。amp。amp。pc=pcnext。pc) if(pa) prenext=pa。這就要求各個(gè)表的工作指針只能后移（即不能每次都從頭指針開始查找）。 {if(m0||n0) {printf(“表長輸入錯(cuò)誤 \n” )； exit(0)。∥將 L1 循環(huán)單鏈表的元素結(jié)點(diǎn)插入到 L2 的第一元素結(jié)點(diǎn)前?！尾樽詈笤亟Y(jié)點(diǎn)。應(yīng)該使用只設(shè)尾指針的單循環(huán)鏈表。 return(lb)。 free(q)。 ∥將指向原單鏈表第一元素的指針指向循環(huán)單鏈表第一結(jié)點(diǎn) free(q)。 4． [題目分析 ]順序存儲(chǔ)結(jié)構(gòu)的線性表的插入，其時(shí)間復(fù)雜度為 O（ n），平均移動(dòng)近一半的元素。n:=。k:=k1。] :=m+n。鏈表上的排序采用直接插入排序比較方便，即首先假定第一個(gè)結(jié)點(diǎn)有序，然后，從第二個(gè)結(jié)點(diǎn)開始，依次插入到前面有序鏈表中，最終達(dá)到整個(gè)鏈表有序。 ∥ r是 p的后繼。amp。但順序存儲(chǔ)結(jié)構(gòu)將第 i(i1)個(gè)元素插入到前面第 1 至第 i1 個(gè)元素的有序表時(shí)，是將第 i 個(gè)元素先與第 i1個(gè)元素比較?！伪４婧罄^ q=list。這就要求從第二結(jié)點(diǎn)開釋，將各結(jié)點(diǎn)依次插入到有序鏈表中。 while(p!=null) {r=pnext?！螌?p結(jié)點(diǎn)鏈入鏈表。Q:=NIL。] ∥第一個(gè)偶數(shù)鏈結(jié)點(diǎn)。 pre^.NEXT:=s。 ]∥修改頭指針。 ]∥結(jié)束“ WHILE(sNIL)DO” ENDP；∥結(jié)束整個(gè)算法。本算法將 A分解成兩個(gè)單鏈表B和 C， B中結(jié)