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