【正文】 if（ klen） {printf（“給的 %d太大 \n” ,len）； exit（ 0）； } pnext=q；∥ A鏈表刪除了 len個元素。amp。 {k++； p=pnext； } if（ p==null） {printf（“給的 %d太大 \n” ,i）； exit（ 0）； } ∥ i太大，退出算法 q=pnext；∥ q為工作指針，初始指向 A鏈表第一個被刪結(jié)點。amp。 {if（ i1 || len1 || j1） {printf（“參數(shù)錯誤 \n”）； exit（ 0）； }∥參數(shù)錯，退出算法。 LinkedList DelInsert（ LinkedList heada， headb， int i， j， len） ∥ heada和 headb均是帶頭結(jié)點的單鏈表。插入和刪除中應(yīng)注意前驅(qū)后繼關(guān)系，不能使鏈表“斷鏈”。這時應(yīng)繼續(xù)查到 A的尾結(jié)點，得到刪除元素后的 A鏈表。比較過程中遇到不相等時，立即退出 while 循環(huán)，不再進行比較。 [算法討論 ] 算法中先將“鏈表的前一半”元素（字符）進棧。 s[i]==pdata） {i； p=pnext； } ∥測試是否中心對稱。 while（ p!=null amp。 {s[i]=pdata； p=pnext； } i。 int i=1；∥ i記結(jié)點個數(shù)， s字符棧 p=hnext；∥ p是鏈表的工作指針，指向待處理的當(dāng)前元素。本算法判斷鏈表是否是中心對稱。這時若棧是空棧，則得出鏈表中心對稱的結(jié)論；否則，當(dāng)鏈表中一元素與棧中彈出元素不等時，結(jié)論為鏈表非中心對稱，結(jié)束算法的執(zhí)行。將鏈表的前一半元素依次進棧。寫成三個函數(shù)顯得邏輯清晰，易讀。其次， C 中一維數(shù)組下標(biāo)從 0開始，若說有 n個元素的一維數(shù)組，其最后一個元素的下標(biāo)應(yīng)是 n1。若使用結(jié)構(gòu)體，對元素的引用應(yīng)使用[i]。 [算法討論 ] 首先是線性表的描述。 a[i+1]=x；∥插入 x。 {t=a[mid]； a[mid]=a[mid+1]； a[mid+1]=t； } ∥ 數(shù)值 x與其后繼元素位置交換。amp。 else high=mid1； ∥到中點 mid的左部去查。 { low=0； high=n1； ∥ low和 high指向線性表下界和上界的下標(biāo) while（ low=high） {mid=（ low+high） /2； ∥找中間位置 if（ a[mid]==x） break； ∥ 找到 x，退出 while循環(huán)。 void SearchExchangeInsert（ ElemType a[]； ElemType x） ∥ a是具有 n個元素的遞增有序線性表，順序存儲。 12． [題目分析 ] 順序存儲的線性表遞增有序，可以順序查找，也可折半查找。 qrlink=prlink； ∥ p的前驅(qū)的后繼為 p的后繼。 void Exchange（ LinkedList p） ∥ p是雙向循環(huán)鏈表中的一個結(jié)點，本算法將 p所指結(jié)點與其前驅(qū)結(jié)點交換。 listlink=q； } }∥算法結(jié)束 [算法討論 ] 算法中假定 list帶有頭結(jié)點，否則，插入操作變?yōu)?qlink=list； list=q。 {p=listlink；∥ p是鏈表的工作指針 pre=list； ∥ pre指向鏈表中數(shù)據(jù)域最小值結(jié)點的前驅(qū)。 LinkedList delinsert（ LinkedList list） ∥ list 是非空線性鏈表，鏈結(jié)點結(jié)構(gòu)是（ data， link）， data 是數(shù)據(jù)域， link 是鏈域。首先要查找最小值結(jié)點 。L），是按 C++的“引用”來寫的，目的是實現(xiàn)變量的“傳址”，克服了 C 語言函數(shù)傳遞只是“值傳遞”的缺點。 [算法討論 ] 算法中函數(shù)頭是按本教材類 C 描述語言書寫的。 while（ pnext!=null） {if（ pnextdataqdata） {pre=p； q=pnext； } ∥查最小值結(jié) 點 p=pnext； ∥指針后移。 pre=L； ∥ pre指向最小值結(jié)點的前驅(qū)。指向待處理的結(jié)點。 LinkedList Delete（ LinkedList L） ∥ L是帶頭結(jié)點的單鏈表，本算法刪除其最小值結(jié)點。所以算法應(yīng)首先遍歷鏈表，求得最小值結(jié)點及其前驅(qū)。單鏈表中刪除結(jié)點，為使結(jié)點刪除后不出現(xiàn)“斷鏈”，應(yīng)知道被刪結(jié)點的前驅(qū)。算法也滿足時間復(fù)雜度 O(n)的要求。 [算法討論 ] 分界元素 t放入 a[i]，而不論它的值如何。本算法將 n個元素中所有大于等于 19的整數(shù)放在所有小于 19 的整數(shù)之后。本題要求用標(biāo)準(zhǔn) pascal描述算法，如下所示。 (4) 本題與第 8題相同，只是敘述不同。若采用教材中的線性表，則元素的表示作相應(yīng)改變，例 如 [i]，而最后 B和 C表應(yīng)置上表的長度，如 =j和 =k。 ∥將大于零的元素放入 B表。 ∥將小于零的元素放入 C表。 ∥ j， k初始化為 1。 ∥ i， j， k是工作指針，分別指向 A、 B和 C表的當(dāng)前元素。本算法將 A拆成 B和 C 兩個表， B中存放大于 ∥等于零的元素， C中存放小于零的元素。 (2) [題目分析 ]本題要求將線性表 A分成 B和 C兩個表，表 B和表 C不另占空間，而是利用表 A的空間，其算法與第 8題相同。 } a[i]=t。 if(ij) a[i++]=a[j]。 a[j]t) j。 while(ij amp。 if(ij) a[j]=a[i]。 a[i]=t) i++。 while(ij) {while(ij amp。 t=a[n]。其算法主要片段語句如下 : i=1。 類似本題的選了 5 個題，其解答如下： （ 1）與上面第 8題不同的是，這里要求以 an為參考元素，將線性表分成左右兩部分。對此問題的擴充是若元素包含正數(shù)、負數(shù)和零，并要求按負數(shù)、零、正數(shù)的順序重排線性表，統(tǒng)計負數(shù)、零、正數(shù)的個數(shù)。如 t為負數(shù)，則 0至 i共 i+1個負數(shù)， n1i個正數(shù)（包括零）。 } [算法討論 ] 本算法時 間復(fù)雜度為 O（ n）。 } a[i]=t。 if(ij) a[j]=a[i]。a[i]0)i++。 while(ij amp。i++。 ∥ 若當(dāng)前元素為大于等于零，則指針前移。amp。 ∥暫存樞軸元素。 ∥ i,j為工作指針（下標(biāo)），初始指向線性表 a的第 1個和第 n個元素。 {i=0。 int n) ∥ a是具有 n個元素的線性表，以順序存儲結(jié)構(gòu)存儲，線性表的元素是整數(shù)。這可采用快速排序的思想來實現(xiàn)，只是提出暫存的第一個元素（樞 軸）并不作為以后的比較標(biāo)準(zhǔn)，比較的標(biāo)準(zhǔn)是元素是否為負數(shù)。 ∥將 p恢復(fù)為指向新的待處理結(jié)點。 ra=p。 {pnext=ranext。 rb=p。 {pnext=rbnext。 i++。 ∥置空新的 A表 while(p!=null) {r=pnext。 ∥ p為鏈表工作指針，指向待分解的結(jié)點。rb=B?！?ra和 rb將分別指向?qū)?chuàng)建的 A表和 B表的尾結(jié)點。 ∥ B表的初始化。∥創(chuàng)建 B表表頭?！?i記鏈表中結(jié)點的序號。鏈表中結(jié)點的相對順序同原鏈表。由于要求分解后兩表中元素結(jié)點的相對順序不變，故采用在鏈表尾插入比較方便，這使用一指向表尾的指針即可方便實現(xiàn)。 （ 3） [題目分析 ]本題中的鏈表有頭結(jié)點，分解成 表 A 和表 B，均帶頭結(jié)點。 [算法討論 ]因為本題并未要求鏈表中結(jié)點的數(shù)據(jù)值有序，所以算法中采取最簡單方式：將新結(jié)點前插到頭結(jié)點后面（即第一元素之前）?！?p指向新的待處理結(jié)點。 Cnext=p。 }∥將小于 0的結(jié)點鏈入 B表。 {pnext=Bnext。 ∥暫存 p的后繼。 ∥ B表初始化。 ∥ p為工作指針。 Cnext=null ∥ C初始化為空表。 C=(LinkedList )malloc(sizeof(LNode))。本算法將 A分解成兩個單鏈表B和 C， B中結(jié)點的數(shù)據(jù)小于零， C中結(jié)點的數(shù)據(jù)大于零。由于沒明確要求用類 PASCAL 書寫算法，故用 C書寫如下。 類似本題的其它題解答如下： （ 1） [題目分析 ]本題基本類似于上面第 7 題，不同之處有二。如有頭結(jié)點，算法不必單獨處理在第一個結(jié)點前插入結(jié)點情況，算法會規(guī)范統(tǒng)一，下面的（ 1）是處理帶頭結(jié)點的例子。 ]∥結(jié)束“ WHILE(sNIL)DO” ENDP；∥結(jié)束整個算法。 ] ]∥結(jié)束奇數(shù)鏈結(jié) 點 s:=r?！捂溔氪私Y(jié)點。 IF pre^.NEXT^.DATAs^.DATA THEN pre:=pre^.NEXT。 ]∥修改頭指針。 IF pre^.DATAs^.DATA THEN[s^.NEXT:=pre。] ∥第一奇數(shù)鏈結(jié)點。 IF Q=NIL THEN[Q:=s。 pre^.NEXT:=s。 s^.NEXT:=pre^.NEXT?！尾迦氘?dāng)前最小值結(jié)點修改頭指針 ] ELSE[WHILE pre^.NEXTNIL DO IF pre^.NEXT^.DATAs^.DATA THEN pre:=pre^.NEXT。 IF pre^.DATAs^.DATA THEN[s^.NEXT:=pre。] ∥第一個偶數(shù)鏈結(jié)點。 THEN IF P=NIL THEN[P:=s。 ∥暫存 s的后繼。 s:=listhead。Q:=NIL。本算法將鏈表 listhead分解成奇數(shù)鏈表和偶數(shù)鏈表，分解由 P和 Q指向，且 P和 Q鏈表是有序的。 7． [題目分析 ]本題要求將一個鏈表分解成兩個鏈表，兩個鏈表都要有序，兩鏈表建立過程中不得使用 NEW過程申請空間，這就是要利用原鏈表空間，隨著原鏈表的分解，新建鏈表隨之排序。 p=r?！螌?p結(jié)點鏈入鏈表?！尾檎也迦胛恢?。amp。 q=la。 while(p!=null) {r=pnext。 lanextnext=null。 {p=lanextnext。本算法利用直接插入原則將鏈表整理成遞增的有序鏈表。這就要求從第二結(jié)點開釋，將各結(jié)點依次插入到有序鏈表中。 q=r。 plink=qlink。amp?！伪４婧罄^ q=list。 listlink=null。如果 list是頭結(jié)點的指針，則相應(yīng)處理要簡單些，其算法片段如下： p=listlink。兩種存儲結(jié)構(gòu)下最佳和最差情況的比較次數(shù)相同，在鏈表情況下，不移動 元素，而是修改結(jié)點指針。但順序存儲結(jié)構(gòu)將第 i(i1)個元素插入到前面第 1 至第 i1 個元素的有序表時，是將第 i 個元素先與第 i1個元素比較。∥ p指向下個待排序結(jié)點。 qlink=p。 plink=qlink。amp。 } else∥查找元素值最小的結(jié)點。 list=p。 if(qdatapdata)∥處理待排序結(jié)點 p比第一個元素結(jié)點小的情況。 ∥ r是 p的后繼?！渭俣ǖ谝粋€元素有序，即鏈表中現(xiàn)只有一個結(jié)點。 ∥ p是工作指針，指向待排序的當(dāng)前元素。本算法將該鏈表按結(jié)點數(shù)據(jù)域的值的大小，從小到大重新鏈接。鏈表上的排序采用直接插入排序比較方便，即首先假定第一個結(jié)點有序，然后，從第二個結(jié)點開始，依次插入到前面有序鏈表中，最終達到整個鏈表有序。本算法利用了題目中“線性表空間足夠大”的條件，“最大限度的避免移動元素”，是“一種高效算法”。因數(shù)據(jù)合并到 LA 中，所以在退出第一個 WHILE循環(huán)后，只需要一 個 WHILE循環(huán)，處理 LB中剩余元素。 [算法討論 ]算法中數(shù)據(jù)移動是主要操作。] :=m+n。k:=k1。j:=j1。] ELSE[[k]:=[j]。k:=k1。 ∥ i， j分別為線性表 LA和 LB的工作指針（下標(biāo)）。 i:=m。 k:=m+n。n:=。LB:SeqList) ∥ LA和 LB是順序