【正文】 點(diǎn)的數(shù)據(jù)小于零， C中結(jié)點(diǎn)的數(shù)據(jù)大于零。 ∥ B表初始化。 Cnext=p。由于要求分解后兩表中元素結(jié)點(diǎn)的相對(duì)順序不變，故采用在鏈表尾插入比較方便，這使用一指向表尾的指針即可方便實(shí)現(xiàn)。 ∥ B表的初始化。 ∥置空新的 A表 while(p!=null) {r=pnext。 {pnext=ranext。 int n) ∥ a是具有 n個(gè)元素的線性表，以順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，線性表的元素是整數(shù)。amp。a[i]0)i++。如 t為負(fù)數(shù)，則 0至 i共 i+1個(gè)負(fù)數(shù)， n1i個(gè)正數(shù)（包括零）。 t=a[n]。 while(ij amp。 (2) [題目分析 ]本題要求將線性表 A分成 B和 C兩個(gè)表，表 B和表 C不另占空間，而是利用表 A的空間，其算法與第 8題相同。 ∥將小于零的元素放入 C表。本題要求用標(biāo)準(zhǔn) pascal描述算法，如下所示。單鏈表中刪除結(jié)點(diǎn)，為使結(jié)點(diǎn)刪除后不出現(xiàn)“斷鏈”，應(yīng)知道被刪結(jié)點(diǎn)的前驅(qū)。 pre=L； ∥ pre指向最小值結(jié)點(diǎn)的前驅(qū)。首先要查找最小值結(jié)點(diǎn) 。 void Exchange（ LinkedList p） ∥ p是雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，本算法將 p所指結(jié)點(diǎn)與其前驅(qū)結(jié)點(diǎn)交換。 { low=0； high=n1； ∥ low和 high指向線性表下界和上界的下標(biāo) while（ low=high） {mid=（ low+high） /2； ∥找中間位置 if（ a[mid]==x） break； ∥ 找到 x，退出 while循環(huán)。 a[i+1]=x；∥插入 x。寫(xiě)成三個(gè)函數(shù)顯得邏輯清晰，易讀。 int i=1；∥ i記結(jié)點(diǎn)個(gè)數(shù)， s字符棧 p=hnext；∥ p是鏈表的工作指針，指向待處理的當(dāng)前元素。 [算法討論 ] 算法中先將“鏈表的前一半”元素（字符）進(jìn)棧。 LinkedList DelInsert（ LinkedList heada， headb， int i， j， len） ∥ heada和 headb均是帶頭結(jié)點(diǎn)的單鏈表。amp。 {k++； p=pnext； } if（ p==null） {printf（“給的 %d太大 \n” ,i）； exit（ 0）； } ∥ i太大，退出算法 q=pnext；∥ q為工作指針，初始指向 A鏈表第一個(gè)被刪結(jié)點(diǎn)。插入和刪除中應(yīng)注意前驅(qū)后繼關(guān)系，不能使鏈表“斷鏈”。 s[i]==pdata） {i； p=pnext； } ∥測(cè)試是否中心對(duì)稱(chēng)。本算法判斷鏈表是否是中心對(duì)稱(chēng)。其次， C 中一維數(shù)組下標(biāo)從 0開(kāi)始，若說(shuō)有 n個(gè)元素的一維數(shù)組，其最后一個(gè)元素的下標(biāo)應(yīng)是 n1。 {t=a[mid]； a[mid]=a[mid+1]； a[mid+1]=t； } ∥ 數(shù)值 x與其后繼元素位置交換。 void SearchExchangeInsert（ ElemType a[]； ElemType x） ∥ a是具有 n個(gè)元素的遞增有序線性表，順序存儲(chǔ)。 listlink=q； } }∥算法結(jié)束 [算法討論 ] 算法中假定 list帶有頭結(jié)點(diǎn)，否則，插入操作變?yōu)?qlink=list； list=q。L），是按 C++的“引用”來(lái)寫(xiě)的，目的是實(shí)現(xiàn)變量的“傳址”，克服了 C 語(yǔ)言函數(shù)傳遞只是“值傳遞”的缺點(diǎn)。指向待處理的結(jié)點(diǎn)。算法也滿(mǎn)足時(shí)間復(fù)雜度 O(n)的要求。 (4) 本題與第 8題相同，只是敘述不同。 ∥ j， k初始化為 1。 } a[i]=t。 if(ij) a[j]=a[i]。其算法主要片段語(yǔ)句如下 : i=1。 } [算法討論 ] 本算法時(shí) 間復(fù)雜度為 O（ n）。 while(ij amp。 ∥暫存樞軸元素。這可采用快速排序的思想來(lái)實(shí)現(xiàn)，只是提出暫存的第一個(gè)元素（樞 軸）并不作為以后的比較標(biāo)準(zhǔn)，比較的標(biāo)準(zhǔn)是元素是否為負(fù)數(shù)。 rb=p。 ∥ p為鏈表工作指針，指向待分解的結(jié)點(diǎn)?！蝿?chuàng)建 B表表頭。 （ 3） [題目分析 ]本題中的鏈表有頭結(jié)點(diǎn)，分解成 表 A 和表 B，均帶頭結(jié)點(diǎn)。 }∥將小于 0的結(jié)點(diǎn)鏈入 B表。 ∥ p為工作指針。由于沒(méi)明確要求用類(lèi) PASCAL 書(shū)寫(xiě)算法，故用 C書(shū)寫(xiě)如下。 ] ]∥結(jié)束奇數(shù)鏈結(jié) 點(diǎn) s:=r。 IF pre^.DATAs^.DATA THEN[s^.NEXT:=pre。 s^.NEXT:=pre^.NEXT。 THEN IF P=NIL THEN[P:=s。本算法將鏈表 listhead分解成奇數(shù)鏈表和偶數(shù)鏈表，分解由 P和 Q指向，且 P和 Q鏈表是有序的?！尾檎也迦胛恢谩? lanextnext=null。 q=r。 listlink=null?！?p指向下個(gè)待排序結(jié)點(diǎn)。 } else∥查找元素值最小的結(jié)點(diǎn)?！渭俣ǖ谝粋€(gè)元素有序，即鏈表中現(xiàn)只有一個(gè)結(jié)點(diǎn)。本算法利用了題目中“線性表空間足夠大”的條件，“最大限度的避免移動(dòng)元素”，是“一種高效算法”。k:=k1。 ∥ i， j分別為線性表 LA和 LB的工作指針（下標(biāo)）。LB:SeqList) ∥ LA和 LB是順序存儲(chǔ)的非遞減有序線性表，本算法將 LB合并到 LA中，元素仍非遞減有序。 ha=q。 ∥將循環(huán)單鏈表最后元素結(jié)點(diǎn)接在 ha 第一元素前。 lanext=qnext。 lbnext=q。 } }∥算法結(jié)束。 else{p=L2?！尾樽詈笠粋€(gè)元素結(jié)點(diǎn)。int m,n) ∥ L1和 L2分別是兩循環(huán)單鏈表的頭結(jié)點(diǎn)的指針， m和 n分別是 L1和 L2的長(zhǎng)度。因此先將第一結(jié)點(diǎn)鏈入是可取的。pbamp。pre=pb。amp。amp。 {prenext=pb。 if(pbdatapcdata)pb=pbnext。 ∥ pre指向結(jié)果鏈表中當(dāng)前待合并結(jié)點(diǎn)的前驅(qū)。 （ 4） 本題與上面（ 3）算法相同，只是結(jié)果表要另辟空間。pa=panext。pa=panext。 while(paamp。 free(lb)。} while(pa){ u=pa。pb=pbnext。∥結(jié)果表中當(dāng)前合并結(jié)點(diǎn)的前驅(qū)的指針。 free(hb)。pa=panext。pb) if(padatapbdata) {pcnext=pa。本算法求 A 和 B 的并集 A∪ B，仍用線性表表示，結(jié)果鏈表元素也是遞增有序。∥釋放原來(lái)兩鏈表的頭結(jié)點(diǎn)。pa=panext。 (2)本題與上面兩題類(lèi)似，要求結(jié)果指針為 lc，其核心語(yǔ)句段如下： pa=lanext?！蝺山Y(jié)點(diǎn)數(shù)據(jù)相等時(shí)，只將 ha的數(shù)據(jù)鏈入。 pre=r。amp。 la=(LinkedList)malloc(sizeof(LNode))。amp。 lanext=pa。 pbnext=lanext。 ∥將 pa 的后繼結(jié)點(diǎn)暫存于 r。 LinkedList Union(LinkedList la,lb) ∥ la,lb分別是帶頭結(jié)點(diǎn)的兩個(gè)單鏈表的頭指針，鏈表中的元素值按遞增序排列，本算法將兩鏈表合并成一個(gè)按元素值遞減次序排列的單鏈表。 (2)pnextprior=q。 19．在指針 p所指結(jié)點(diǎn)前插入結(jié)點(diǎn) s的語(yǔ)句如下： spre=ppre?！我韵氯涞捻樞虿荒茏? p^.rlink^.llink q。 則 q^.rlink:=p^.rlink。 pdataX) p=pnext?！尾檎沂? else return(p)。 13. 設(shè)單鏈表的頭結(jié)點(diǎn)的 頭指針為 head,且 pre=head； while(prenext!=p) pre=prenext。 10．本題是鏈表的逆置問(wèn)題。而且無(wú)論鏈表是否為空，頭指針均不為空。 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的定義是： TYPE pointer=↑ nodetype。首先，插入、刪除不需移動(dòng)元素，只修改指針，時(shí)間復(fù)雜度為 O(1)；其次，不需要預(yù)先分配空間，可根據(jù)需要?jiǎng)討B(tài)申請(qǐng)空間；其三，表容量只受可用內(nèi)存空間的限制。 (4)pnext=rnext ∥將 p結(jié)點(diǎn)鏈入鏈表中 (5)rnext=p ∥ r是 q的前驅(qū)， u是下個(gè)待插入結(jié)點(diǎn)的指針。 (4) q0:= p。 q^.pre:=p^.pre?！?r指向工作指針 s的前驅(qū)， p指向最小值的前驅(qū)。 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。非遞歸算法中用指針 pre指向主串中開(kāi)始結(jié)點(diǎn)（初始時(shí)為第一元素結(jié)點(diǎn)）。 非遞歸算法： (1)pre:=pb。 15 ． Lnextnext==L 16． pnext!=null 17． Lnext==L amp。 6． O(1)， O(n) 7．單鏈表， 多重 鏈表，（動(dòng)態(tài)）鏈表，靜態(tài)鏈表 8． fnext=pnext。另外，頭結(jié)點(diǎn)數(shù)據(jù)域可寫(xiě)入鏈表長(zhǎng)度，或作監(jiān)視哨。 9．非空線性表第一個(gè)元素?zé)o前驅(qū)，最后一個(gè)元素?zé)o后繼。 pnext=f。pnext=s。 (4)pb:=pre^.next。 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)。 25.(1)i= ∥ 為元素 個(gè)數(shù) (2)j:=j+1 ∥有值不相等的元素 (3)[j]:=[i] ∥元素前移 (4):=j ∥元素個(gè)數(shù) 26.(A)p^.link:=q?！蔚谝粋€(gè)結(jié)點(diǎn)值最??； (5)p^link:=q^.link。 ∥結(jié)點(diǎn) q插入結(jié)點(diǎn) p前 (4) q^.freq=0 ∥鏈表中無(wú)值為 x的結(jié)點(diǎn)，將新建結(jié)點(diǎn)插入到鏈表最后（頭結(jié)點(diǎn)前）。 ∥ q是工作指針 p的前驅(qū) (2)p^.datam ∥ p是工作指針 (3)r:=q。 B!=null) ∥兩均未空時(shí)循環(huán) (2)Aelement==Belement ∥兩表中相等元素不作結(jié)果元素 (3)B=Blink ∥向后移動(dòng) B表指針 (4)A!=null ∥將 A 表剩余部分放入結(jié)果表中 (5)lastlink=null ∥置鏈表尾 四、 應(yīng)用題 1．（ 1）選鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中插入和刪除操作不需要移動(dòng)元素。 END。 8． (1)將 next域變?yōu)閮蓚€(gè)域 : pre和 next，其值域均為 0..maxsize。 11．該算法的功能是判斷鏈表 L是否是非遞減有序，若是則返回“ true”；否則返回“ false“。 ，工作指針 p初始化為 p=Hnext。 pdataX ) p=pnext。 ∥查找成功 pa和 pb鏈表中的值相同的結(jié)點(diǎn)保留在 pa鏈表中（ pa中與 pb中不同結(jié)點(diǎn)刪除）， pa是結(jié)果鏈表的頭指針。 q^.llink^.rlink:=p。 subp(s,q)的作用是構(gòu)造從 s到 q的循環(huán)鏈表。 ppre=s?；?r=qnext?！?pa， pb分別是 鏈表 la和 lb 的工作指針 lanext=null。 lanext=pa。 pb=r。 pbnext=lanext。后者不如前者優(yōu)化。 pa=ha。pa=panext?！?hb鏈表中工作指針后移?！螌涉湵碇惺Ｓ嗖糠宙溔虢Y(jié)果鏈表。 pc=lc。pb=pbnext。與前組題不同的是，敘述上是用線性表代表集合，而操作則是求集合的并、交、差（ A∪ B， A∩ B， AB）等?！卧O(shè)工作指針 pa 和 pb。} else if(pa