【正文】 查 p結(jié)點(diǎn)在鏈表中的插入位置，這時(shí) q是工作指針。 END。在雙鏈表中求前驅(qū)和后繼都容易，從 當(dāng)前結(jié)點(diǎn)向前到第一結(jié)點(diǎn)，向后到最后結(jié)點(diǎn)，可以訪問(wèn)到任何一個(gè)結(jié)點(diǎn)。 if(p= =null) return(null)。 16．設(shè) q:=p^.llink。第一個(gè)循環(huán)鏈表包含從 pa 到 pb 的前驅(qū) ,L中除剛構(gòu)造的 pa到 pb前驅(qū)外的結(jié)點(diǎn)形成第二個(gè)循環(huán)鏈表。故在合并的同時(shí)，將鏈表結(jié)點(diǎn)逆置。∥ 將 pb 的后繼結(jié)點(diǎn)暫存于 r。 ［算法討論］上面兩鏈表均不為空的表達(dá)式也可簡(jiǎn)寫(xiě)為 while(paamp。 while(paamp。 pa=panext。pc=pa。 ha和 hb分別是其鏈表的頭指針。pc=pa?！卧O(shè)工作指針 pa和 pb； pc=la。 free(u)?！?L1作結(jié)果鏈表的頭指針。pc=pa。 pre=A。 if(padatapbdata)∥ A表當(dāng)前元素值大于 B表和 C表的公共元素，先將 B表元素鏈入。 if(pbamp。amp。 LinkedList Union(LinkedList L1,L2。∥ L2為空表。 ∥將 lb的最后元素結(jié)點(diǎn)接到 lb 的第一元素。 ∥單向循環(huán)鏈表的表頭指針 hbnext=hanext。 PROC Union(VAR LA:SeqList。] WHILE(j0) DO [[k]:=[j]。 listlink=null。 } p=r。 qlink=p。qnextdatapdata)q=qnext。 IF s^.DATA DIV 2=0 ∥處理偶數(shù)。 ELSE[pre:=Q。一是帶頭結(jié)點(diǎn)，二是分解后的兩個(gè)鏈表，一個(gè)是數(shù)據(jù)值小于 0，另一個(gè)是數(shù)據(jù)值大于 0。 Bnext=p。 B=(LinkedList)malloc(sizeof(LNode)。∥在 B表尾插入新結(jié)點(diǎn)； rbnext=p。 t=a[0]。 ∥將原第一元素放到最終位置。 ∥當(dāng)前元素不大于參考元素時(shí)，指針 i后移。 j=k=1。算法中只用了一個(gè) t中間變量，符合空間復(fù)雜度 O(1)的要求。原題中 void delete（ linklist amp。題目要求“用最少的時(shí)間在表中查找數(shù)值為 x的元素”，這里應(yīng)使用折半查找方法。另外元素類(lèi)型就假定是 ElemType，未指明具體類(lèi)型。amp。 ki1）∥查找第 i個(gè)結(jié)點(diǎn)。本算法刪除 heada鏈表中自第 i個(gè)元素起的共len個(gè)元素，然后將單鏈表 heada插入到 headb的第 j個(gè)元素之前。 for（ i=1； i=n/2； i++）∥ 鏈表前一半元素進(jìn)棧。 } ∥結(jié)束插入 }∥結(jié)束本算法。 {q=pllink； qllinkrlink=p； ∥ p的前驅(qū)的前驅(qū)之后繼為 p pllink=qllink； ∥ p的前驅(qū)指向其前 驅(qū)的前驅(qū)。 q=p； ∥ q指向最小值結(jié)點(diǎn)，初始假定第一元素結(jié)點(diǎn)是最小值結(jié)點(diǎn)。 TYPE arr=ARRAY[1..1000] OF integer； VAR a： arr； PROCEDURE Rearrange5（ VAR a： arr）； ∥ a是 n（設(shè) n=1000）個(gè)整數(shù)組成的線性表，用一維數(shù)組存儲(chǔ)。這里僅把表 B和表 C另設(shè)空間的算法解答如下： void Rearrange2(int A[],B[],C[]) ∥線性表 A有 n個(gè)整型元素，順序存儲(chǔ)。 ∥暫存參考元素。 ∥ 當(dāng)前元素為負(fù)數(shù)時(shí)指針后移。本算法重排線性表 a， ∥使所有值為負(fù)數(shù)的元素移到所有值為正數(shù)的數(shù)的前面。 ∥暫存 p的后繼。 void DisCreat3(LinkedList A) ∥ A 是帶頭結(jié)點(diǎn)的單鏈表，本算法將其分解成兩個(gè)帶頭結(jié)點(diǎn)的單鏈表， A表中含原表中序號(hào)為奇數(shù) ∥的結(jié)點(diǎn)， B表中含原表中序號(hào)為偶數(shù)的結(jié)點(diǎn)。 while(p!=null) {r=pnext。 [算法討論 ]由于算法要求“不得使用 NEW過(guò)程申請(qǐng)空間，也沒(méi)明確指出鏈表具有頭結(jié)點(diǎn)，所以上述算法復(fù)雜些，它可能需要在第一個(gè)結(jié)點(diǎn)前插入新結(jié)點(diǎn)，即鏈表的頭指針會(huì)發(fā)生變化。 ] ] ELSE∥處理奇數(shù)鏈。∥ P和 Q鏈表初始化為空表?！螘捍?p的后繼。 while(qlink!=null amp。qlinkdatapdata)q=qlink。 LinkedList LinkListSort(LinkedList list) ∥ list是不帶頭結(jié)點(diǎn)的線性鏈表，鏈表結(jié)點(diǎn)構(gòu)造為 data和 link兩個(gè)域， data 是數(shù)據(jù)域， link是指針域。i:=i1。線性表 LA和 LB合并時(shí)，若從 第一個(gè)元素開(kāi)始，一定會(huì)造成元素后移，這不符合本題“高效算法”的要求。 ∥釋放 lb的頭結(jié)點(diǎn) return(lb)。 LinkedList Union(LinkedList la,lb) ∥ la和 lb是兩個(gè)無(wú)頭結(jié)點(diǎn)的循環(huán)單鏈表的尾指針，本算法將 lb接在 la后，成為一個(gè)單循環(huán)鏈表。 L2next=L1next。本算法滿足這一要求。} else{pb=pbnext。pc) if(pbdatapcdata) pb=pbnext。 ∥找到 B表和 C表的共同元素就退出 while 循環(huán)。 {pa=Anext。pa=panext。 pa=L1next。pa=panext。 與本題類(lèi)似的其它幾個(gè)題解答如下： (1) 解答完全同 上 2。} else if(padatapbdata) {pcnext=pb。與前組題不同的是，敘述上是用線性表代表集合，而操作則是求集合的并、交、差（ A∪ B， A∩ B， AB）等。 pc=lc?！?hb鏈表中工作指針后移。 pa=ha。 pbnext=lanext。 lanext=pa?；?r=qnext。 subp(s,q)的作用是構(gòu)造從 s到 q的循環(huán)鏈表。 ∥查找成功 pa和 pb鏈表中的值相同的結(jié)點(diǎn)保留在 pa鏈表中（ pa中與 pb中不同結(jié)點(diǎn)刪除）， pa是結(jié)果鏈表的頭指針。 ，工作指針 p初始化為 p=Hnext。 8． (1)將 next域變?yōu)閮蓚€(gè)域 : pre和 next，其值域均為 0..maxsize。在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中插入和刪除操作不需要移動(dòng)元素。 ∥ q是工作指針 p的前驅(qū) (2)p^.datam ∥ p是工作指針 (3)r:=q?！蔚谝粋€(gè)結(jié)點(diǎn)值最?。? (5)p^link:=q^.link。 20． A． VAR head:ptr B. new(p) C. p^.data:=k D. q^.next:=p E. q:=p(帶頭結(jié)點(diǎn) ) 21．（ 1） new(h)。pnext=s。 9．非空線性表第一個(gè)元素?zé)o前驅(qū)，最后一個(gè)元素?zé)o后繼。 6． O(1)， O(n) 7．單鏈表， 多重 鏈表，（動(dòng)態(tài)）鏈表，靜態(tài)鏈表 8． fnext=pnext。 非遞歸算法： (1)pre:=pb。 22． A: r^.link^.datamax AND q^.link^.datamax B: r:=r^.link C: q^.link D: q^.link E: r^.link F: r^.link G: r:=s（或 r:= r^.link） H: r:=r^.link I: q^.link:=s^.link 23． (1)la (2)0 (3)ji1 (4)p↑ .next (5)i1 24.(1)head^.left:=s ∥ head的前驅(qū)指針指向插入結(jié)點(diǎn) (2)j:=1。 q^.pre:=p^.pre。 (4)pnext=rnext ∥將 p結(jié)點(diǎn)鏈入鏈表中 (5)rnext=p ∥ r是 q的前驅(qū)， u是下個(gè)待插入結(jié)點(diǎn)的指針。 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的定義是： TYPE pointer=↑ nodetype。 10．本題是鏈表的逆置問(wèn)題?！尾檎沂? else return(p)。 則 q^.rlink:=p^.rlink。 19．在指針 p所指結(jié)點(diǎn)前插入結(jié)點(diǎn) s的語(yǔ)句如下： spre=ppre。 LinkedList Union(LinkedList la,lb) ∥ la,lb分別是帶頭結(jié)點(diǎn)的兩個(gè)單鏈表的頭指針，鏈表中的元素值按遞增序排列，本算法將兩鏈表合并成一個(gè)按元素值遞減次序排列的單鏈表。 pbnext=lanext。amp。amp?！蝺山Y(jié)點(diǎn)數(shù)據(jù)相等時(shí)，只將 ha的數(shù)據(jù)鏈入。pa=panext。本算法求 A 和 B 的并集 A∪ B，仍用線性表表示，結(jié)果鏈表元素也是遞增有序。pa=panext?！谓Y(jié)果表中當(dāng)前合并結(jié)點(diǎn)的前驅(qū)的指針。} while(pa){ u=pa。 while(paamp。pa=panext。 ∥ pre指向結(jié)果鏈表中當(dāng)前待合并結(jié)點(diǎn)的前驅(qū)。 {prenext=pb。amp。pbamp。int m,n) ∥ L1和 L2分別是兩循環(huán)單鏈表的頭結(jié)點(diǎn)的指針， m和 n分別是 L1和 L2的長(zhǎng)度。 else{p=L2。 lbnext=q。 ∥將循環(huán)單鏈表最后元素結(jié)點(diǎn)接在 ha 第一元素前。LB:SeqList) ∥ LA和 LB是順序存儲(chǔ)的非遞減有序線性表，本算法將 LB合并到 LA中，元素仍非遞減有序。k:=k1?！渭俣ǖ谝粋€(gè)元素有序，即鏈表中現(xiàn)只有一個(gè)結(jié)點(diǎn)。∥ p指向下個(gè)待排序結(jié)點(diǎn)。 q=r?！尾檎也迦胛恢?。 THEN IF P=NIL THEN[P:=s。 IF pre^.DATAs^.DATA THEN[s^.NEXT:=pre。由于沒(méi)明確要求用類(lèi) PASCAL 書(shū)寫(xiě)算法，故用 C書(shū)寫(xiě)如下。 }∥將小于 0的結(jié)點(diǎn)鏈入 B表?！蝿?chuàng)建 B表表頭。 rb=p。 ∥暫存樞軸元素。 } [算法討論 ] 本算法時(shí) 間復(fù)雜度為 O（ n）。 if(ij) a[j]=a[i]。 ∥ j， k初始化為 1。算法也滿足時(shí)間復(fù)雜度 O(n)的要求。L），是按 C++的“引用”來(lái)寫(xiě)的，目的是實(shí)現(xiàn)變量的“傳址”，克服了 C 語(yǔ)言函數(shù)傳遞只是“值傳遞”的缺點(diǎn)。 void SearchExchangeInsert（ ElemType a[]； ElemType x） ∥ a是具有 n個(gè)元素的遞增有序線性表，順序存儲(chǔ)。其次， C 中一維數(shù)組下標(biāo)從 0開(kāi)始，若說(shuō)有 n個(gè)元素的一維數(shù)組，其最后一個(gè)元素的下標(biāo)應(yīng)是 n1。 s[i]==pdata） {i； p=pnext； } ∥測(cè)試是否中心對(duì)稱(chēng)。 {k++； p=pnext； } if（ p==null） {printf（“給的 %d太大 \n” ,i）； exit（ 0）； } ∥ i太大，退出算法 q=pnext；∥ q為工作指針，初始指向 A鏈表第一個(gè)被刪結(jié)點(diǎn)。 LinkedList DelInsert（ LinkedList heada， headb， int i， j， len） ∥ heada和 headb均是帶頭結(jié)點(diǎn)的單鏈表。 int i=1；∥ i記結(jié)點(diǎn)個(gè)數(shù)， s字符棧 p=hnext；∥ p是鏈表的工作指針，指向待處理的當(dāng)前元素。 a[i+1]=x；∥插入 x。 void Exchange（ LinkedList p） ∥ p是雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，本算法將 p所指結(jié)點(diǎn)與其前驅(qū)結(jié)點(diǎn)交換。 pre=L； ∥ pre指向最小值結(jié)點(diǎn)的前驅(qū)。本題要求用標(biāo)準(zhǔn) pascal描述算法，如下所示。 (2) [題目分析 ]本題要求將線性表 A分成 B和 C兩個(gè)表，表 B和表 C不另占空間，而是利用表 A的空間，其算法與第 8題相同。 t=a[n]。a[i]0)i++。 int n) ∥ a是具有 n個(gè)元素的線性表，以順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，線性表的元素是整數(shù)。 ∥置空新的 A表 while(p!=null) {r=pnext。由于要求分解后兩表中元素結(jié)點(diǎn)的相對(duì)順序不變，故采用在鏈表尾插入比較方便，這使用一指向表尾的指針即可方便實(shí)現(xiàn)。