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