【正文】 頭結(jié)點(diǎn)，為處理方便，給加上頭結(jié)點(diǎn)，處理結(jié)束再刪除之；二是數(shù)據(jù)相同的結(jié)點(diǎn)，不合并到結(jié)果鏈表中；三是 hb 鏈表不能被破壞，即將 hb的結(jié)點(diǎn)合并到結(jié)果鏈表時(shí)，要生成新結(jié)點(diǎn)。 lanext=ha。 ∥ pb是 hb鏈表的工作指針 pre=la。pb) if(padatapbdata)∥處理 ha中數(shù)據(jù) {prenext=pa。 {r=(LinkedList)malloc(sizeof(LNode))?！螌⑿陆Y(jié)點(diǎn)鏈入結(jié)果鏈表。 {prenext=pa。 pb=pbnext。 free(la)。pb=hbnext。amp。} else {pcnext=pb。 else pcnext=pb。 算法時(shí)間復(fù)雜度為 O（ m+n），其中 m和 n分別為鏈表 la和 lb的長度。因此兩表中合并 時(shí)，如有元素值相等元素，則應(yīng)刪掉一個(gè)。 { pa=hanext?！?pc為結(jié)果鏈表當(dāng)前結(jié)點(diǎn)的前驅(qū)指針。pc=pa。pb=pbnext。 u=pb?！? 若 ha表未空，則鏈入結(jié)果表。 ∥釋放 hb頭結(jié)點(diǎn) return(ha)。其核心語句段如下： pa=lanext。 while(paamp。pc=pa。free(u)。} else {u=pb。 pa=panext。 free(u)。 ∥注： 本算法中也可對 B表不作釋放空間的處理 （ 3）本題基本與（ 2）相同，但要求無重復(fù)元素，故在算法中，待合并結(jié)點(diǎn)數(shù)據(jù)要與其前驅(qū)比較 ，只有在與前驅(qū)數(shù)據(jù)不同時(shí)才并入鏈表。∥ pa、 pb是兩鏈表的工作指針。amp。}∥刪除 L1表多余元素 else if (padatapbdata) pb=pbnext。} ∥處理第一個(gè)相等的元素。} ∥重復(fù)元素不進(jìn)入 L1表。} ∥交集元素并入結(jié)果表。} ∥ 刪 L1表剩余元素 pcnext=null。 （ 5） [題目分析 ]本題首先求 B和 C的交集，即求 B和 C中共有元素，再與 A求并集，同時(shí)刪除重復(fù)元素，以保持結(jié)果 A遞增。pc=Cnext。 if(padatapbdata||padatapcdata)∥ A 中第一個(gè)元素為結(jié)果表的第一元素。} else{while(pbamp。 else if(pbdatapcdata)pc=pcnext。amp。pre=pb。 }∥結(jié)束了結(jié)果表中第一元素的確定 while(paamp。pc) {while(pbamp。 else break。pc) {while(paamp。pre=pa。pb=pbnext。}∥ 若 A中已有 B， C公共元素，則不再存入結(jié)果表。amp。這就要求當(dāng)前待合并到結(jié)果表的元素要與其前驅(qū)比較。 算法中的 第二個(gè)問題是要求時(shí)間復(fù)雜度為 O（ |A|+|B|+|C|）。 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)前即可。 ∥本算法用最快速度將 L1和 L2合并成一個(gè)循環(huán)單鏈表?！?L1為空表。 pnext=L2next?！吾尫艧o用頭結(jié)點(diǎn)。 while(pnext!=L2) p=pnext。 L1next=L2next。 類似本題敘述的其它題解答如下： （ 1） [題目分析 ]本題將線性表 la和 lb連接，要求時(shí)間復(fù)雜度為 O（ 1），且占用輔助空間盡量小。 ∥ q指向 la的第一個(gè)元素結(jié)點(diǎn)。 ∥將 lb指向 la的第一元素結(jié)點(diǎn)，實(shí)現(xiàn)了 lb接在 la后。 [算法討論 ]若循環(huán)單鏈表帶有頭結(jié)點(diǎn)，則相應(yīng)算法片段如下： q=lbnext。 ∥ la的后繼結(jié)點(diǎn)為 lb的第一元素結(jié)點(diǎn)。 （ 2） [題目分析 ]本題要求將單向鏈表 ha和單向循環(huán)鏈表 hb合 并成一個(gè)單向鏈表，要求算法所需時(shí)間與鏈表長度無關(guān)，只有使用帶尾指針的循環(huán)單鏈表，這樣最容易找到鏈表的首、尾結(jié)點(diǎn)，將該結(jié)點(diǎn)序列插入到單向鏈表第一元素之前即可。 hanext=qnext。 ∥ q指向 hb首元結(jié)點(diǎn)。 ∥頭指針指向 hb的首元結(jié)點(diǎn)。設(shè)兩線性表的長度各為 m和 n ，則結(jié)果表的最后一個(gè)元素應(yīng)在 m+n位置上。 m:=。 ∥ k為結(jié)果線性表的工作指針（下標(biāo)）。 WHILE(i0)AND(j0)DO IF [i]=[j] THEN[[k]:=[i]。k:=k1。j:=j1。在最佳情況下（ LB的最小元素大于 LA的最大元素），僅將 LB的 n個(gè)元素移（拷貝）到 LA中，時(shí)間復(fù)雜度為 O（ n），最差情況， LA的所有元素都要移動(dòng)，時(shí)間復(fù)雜度為 O（ m+n）。 5． [題目分析 ]本題實(shí)質(zhì)上是一個(gè)排序問題，要求“不得使用除該鏈表結(jié)點(diǎn)以外的任何鏈結(jié)點(diǎn)空間”。 {p=listlink。 while(p!=null) {r=plink。 {plink=list。 {while(qlink!=nullamp。∥將當(dāng)前排序結(jié)點(diǎn)鏈入有序鏈表中。 } } [算法討論 ]算法時(shí)間復(fù)雜度的分析與用順序存儲(chǔ)結(jié)構(gòu)時(shí)的情況相同。 另一說明是，本題中線性鏈表 list 不帶頭結(jié)點(diǎn)，而且要求“不得使用除該鏈表以外的任何鏈結(jié)點(diǎn)空間“，所以處理復(fù)雜，需要考慮當(dāng)前結(jié)點(diǎn)元素值比有序鏈表第一結(jié)點(diǎn)的元素值還小的情況，這時(shí)要修改鏈表指針 list?！斡行蜴湵沓跏蓟癁榭? while(p!=null) {r=plink。 qlinkdatapdata)q=qlink。 } 6． [題目分析 ]本題明確指出單鏈表帶頭結(jié)點(diǎn)，其結(jié)點(diǎn)數(shù)據(jù)是正整數(shù)且不相同，要求利用直接插入原則把鏈表整理成遞增有序鏈表。 {if(lanext!=null)∥鏈表不為空表?！沃苯硬迦朐瓌t認(rèn)為第一元素有序，然后從第二元素起依次插入。 while(qnext!=nullamp。 pnext=qnext。 } 與本題有類似敘述的題的解答： （ 1）本題也是鏈表排序問題，雖沒象上題那樣明確要求“利用直接插入的原則”來排序，仍可用上述算法求解，這里不再贅述。 P:=NIL。 WHILE(sNIL)DO [r:=s^.NEXT。P^.NEXT:=NIL。P:=s。 ∥鏈入此結(jié)點(diǎn)。Q^.NEXT:=NIL。 Q:=s。 s^.NEXT:=pre^.NEXT。∥ s指向新的待排序結(jié)點(diǎn)。算法中偶數(shù)鏈上結(jié)點(diǎn)是靠數(shù)據(jù)整除 2 等于 0（ DATA DIV 2=0）判斷的。 void DisCreat1(LinkedList A) ∥ A是帶頭結(jié)點(diǎn)的單鏈表，鏈表中結(jié)點(diǎn)的數(shù)據(jù)類型為整型?！螢?C申請結(jié)點(diǎn)空間。 Bnext=null。 if (pdata0)∥小于 0的放入 B表。 else {pnext=Cnext。 } }∥算法結(jié)束。分解后的 A 表含有原表中序號為奇數(shù)的元素， B表含有原 A表中序號為偶數(shù)的元素。 {i=0。 Bnext=null。 ra=A。 Anext=null。 if(i%2==0) ∥處理原序號為偶數(shù)的鏈表結(jié)點(diǎn) 。∥ rb指向新的尾結(jié)點(diǎn)； } else∥處理原序號為奇數(shù)的結(jié)點(diǎn)。 } p=r。 int Rearrange（ SeqList a。 j=n1。 while(ij) {while(ij amp。 if(ij){a[i]=a[j]。amp。 ∥ 正數(shù)后移。算法只是按題目要求把正負(fù)數(shù)分開，如要求統(tǒng)計(jì)負(fù)數(shù)和大于等于零的個(gè)數(shù)，則最后以 t來定。請讀者利用上面解題思想自行解答。j=n。amp。 ∥將大于參考元素的元素后移。 ∥當(dāng)前元素大于參考元素時(shí)指針前移。 ∥參考元素置于分界位置。 {i=0。 while(in) {if(A[i]0) C[++k]=A[i++]。 [算法討論 ]本題用一維數(shù)組存儲(chǔ)線性表，結(jié)果線性表 B和 C中分別有 j+1和 k+1個(gè)元素。 (5) 本題與第 8題基本相同，不同之處在于這里的分界元素是整數(shù) 19（鏈表中并不要求一定有 19）。 VAR i,j,t： integer； BEGIN i:=1； j:=n； t:=a[1] ；∥ i,j指示順序表的首尾元素的下標(biāo)， t暫存分界元素 WHILE（ ij） DO BEGIN WHILE （ ij） AND（ a[j]=19） DO j:=j1； IF（ ij） THEN BEGIN A[i]:=A[j]； i:=i+1 END； WHILE （ ij） AND（ a[i] 19） DO i:=i+1； IF（ ij） THEN BEGIN A[j]:=A[i]； j:=j1 END； END； a[i]:=t； END。 9． [題目分析 ] 本題要求在單鏈表中刪除最小值結(jié)點(diǎn)。遍歷 結(jié)束后再執(zhí)行刪除操作。假定鏈表非空。 } prenext=qnext；∥從鏈表上刪除最小值結(jié)點(diǎn) free（ q）； ∥釋放最小值結(jié)點(diǎn)空間 }∥結(jié)束算法 delete。 10． [題目分析 ] 本題要求將鏈表中數(shù)據(jù)域值最小的結(jié)點(diǎn)移到鏈表的最前面。 ∥本算法將鏈表中數(shù)據(jù)域值最小的那個(gè)結(jié)點(diǎn)移到鏈表的最前面。 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)）六條鏈。 qllink=p； ∥ p與其前驅(qū)交換 prlinkllink=q； ∥ p的后繼的前驅(qū)指向原 p的前驅(qū) prlink=q； ∥ p的后繼指向其原來的前驅(qū) }∥算法 exchange結(jié)束。本算法在表中查找數(shù)值為 x的元素，如查到則與其后繼交換位置；如查不到，則插入表中，且使表仍遞增有序。 } if（ a[mid]==x amp。 if（ lowhigh） ∥查找失敗，插入數(shù)據(jù)元素 x {for（ i=n1； ihigh； i） a[i+1]=a[i]；∥后移元素。算法中使用一維數(shù)組 a表示線性表，未使用包含數(shù)據(jù)元素的一維數(shù)組和指示線性表長度的結(jié)構(gòu)體。第三，本算法可以寫成三 個(gè)函數(shù)，查找函數(shù)，交換后繼函數(shù)與插入函數(shù)。在處理鏈表的后一半元素時(shí)，當(dāng)訪問到鏈表的一個(gè)元素后，就從棧中彈出一個(gè)元素，兩元素比較，若相等，則將鏈表中下一元素與棧中再彈出元素比較，直至鏈表到尾。 {char s[]。 ∥恢復(fù)最后的 i值 if（ n%2==1） p=pnext； } ∥若 n是奇數(shù)，后移過中心結(jié)點(diǎn)。 if（ p==null） return（ 1）；∥鏈表中心對稱 else return（ 0）； ∥鏈表不中心對稱 }∥算法結(jié)束。 14． [題目分析 ] 在單鏈表中刪除自第 i個(gè)元素起的共 len 個(gè)元素，應(yīng)從 第 1個(gè)元素起開始計(jì)數(shù)，記到第 i個(gè)時(shí)開始數(shù) len個(gè)，然后將第 i1個(gè)元素的后繼指針指向第 i+len個(gè)結(jié)點(diǎn)，實(shí)現(xiàn)了在 A鏈表中刪除自第 i個(gè)起的 len個(gè)結(jié)點(diǎn)。另外，算法中應(yīng)判斷 i， len和 j的合法性。 p=heada；∥ p為鏈表 A的工作指針，初始化為 A的頭指針，查到第 i個(gè)元素時(shí)， p指向第 i1個(gè)元素 k=0；∥計(jì)數(shù) while（ p!=null amp。 k=0； while（ q!=null amp。 if (headanext!=null) ∥ headanext=null 說明鏈表中結(jié)點(diǎn)均已刪除，無需往 B表 插入 {whi