【導(dǎo)讀】部分答案解釋如下。4．兩種存儲(chǔ)結(jié)構(gòu)各有優(yōu)缺點(diǎn)，應(yīng)根據(jù)實(shí)際情況選用，不能籠統(tǒng)說哪一個(gè)好。7．集合中元素?zé)o邏輯關(guān)系。9．非空線性表第一個(gè)元素?zé)o前驅(qū)，最后一個(gè)元素?zé)o后繼。另外，不論鏈表是否為空，鏈表指針不變。13．從任一結(jié)點(diǎn)出發(fā)都可訪問到鏈表中每一個(gè)元素。非遞歸算法中用指針pre指向主串中開始結(jié)點(diǎn)（初。若主串與子串對(duì)應(yīng)數(shù)據(jù)相等，兩串工作指針pa和pb后移；否則，串第一元素開始，比較一直繼續(xù)到循環(huán)條件失敗。若pa為空，則匹配成功，返回true，否。q->pre->next=q->next;q->next->pre=q->pre;∥先將q結(jié)點(diǎn)從鏈表上摘下。=null∥鏈表未到尾就一直作

　　

【正文】 的算法解答如下： void Rearrange2(int A[],B[],C[]) ∥線性表 A有 n個(gè)整型元素，順序存儲(chǔ)。本算法將 A拆成 B和 C 兩個(gè)表， B中存放大于 ∥等于零的元素， C中存放小于零的元素。 {i=0。 ∥ i， j， k是工作指針，分別指向 A、 B和 C表的當(dāng)前元素。 j=k=1。 ∥ j， k初始化為 1。 while(in) {if(A[i]0) C[++k]=A[i++]。 ∥將小于零的元素放入 C表。 else B[++j]=A[i++]。 ∥將大于零的元素放入 B表。 [算法討論 ]本題用一維數(shù)組存儲(chǔ)線性表，結(jié)果線性表 B和 C中分別有 j+1和 k+1個(gè)元素。若采用教材中的線性表，則元素的表示作相應(yīng)改變，例 如 [i]，而最后 B和 C表應(yīng)置上表的長(zhǎng)度，如 =j和 =k。 (3) 本題與第 8題本質(zhì)上相同，第 8題要求分開正數(shù)和負(fù)數(shù)，這里要求分開奇數(shù)和偶數(shù)，判別方式是 a[i]%2==0，滿足時(shí)為偶數(shù)，反之為奇數(shù)。 (4) 本題與第 8題相同，只是敘述不同。 (5) 本題與第 8題基本相同，不同之處在于這里的分界元素是整數(shù) 19（鏈表中并不要求一定有 19）。本題要求用標(biāo)準(zhǔn) pascal描述算法，如下所示。 TYPE arr=ARRAY[1..1000] OF integer； VAR a： arr； PROCEDURE Rearrange5（ VAR a： arr）； ∥ a是 n（設(shè) n=1000）個(gè)整數(shù)組成的線性表，用一維數(shù)組存儲(chǔ)。本算法將 n個(gè)元素中所有大于等于 19的整數(shù)放在所有小于 19 的整數(shù)之后。 VAR i,j,t： integer； BEGIN i:=1； j:=n； t:=a[1] ；∥ i,j指示順序表的首尾元素的下標(biāo)， t暫存分界元素 WHILE（ ij） DO BEGIN WHILE （ ij） AND（ a[j]=19） DO j:=j1； IF（ ij） THEN BEGIN A[i]:=A[j]； i:=i+1 END； WHILE （ ij） AND（ a[i] 19） DO i:=i+1； IF（ ij） THEN BEGIN A[j]:=A[i]； j:=j1 END； END； a[i]:=t； END。 [算法討論 ] 分界元素 t放入 a[i]，而不論它的值如何。算法中只用了一個(gè) t中間變量，符合空間復(fù)雜度 O(1)的要求。算法也滿足時(shí)間復(fù)雜度 O(n)的要求。 9． [題目分析 ] 本題要求在單鏈表中刪除最小值結(jié)點(diǎn)。單鏈表中刪除結(jié)點(diǎn)，為使結(jié)點(diǎn)刪除后不出現(xiàn)“斷鏈”，應(yīng)知道被刪結(jié)點(diǎn)的前驅(qū)。而“最小值結(jié)點(diǎn)”是在遍歷整個(gè)鏈表后才能知道。所以算法應(yīng)首先遍歷鏈表，求得最小值結(jié)點(diǎn)及其前驅(qū)。遍歷 結(jié)束后再執(zhí)行刪除操作。 LinkedList Delete（ LinkedList L） ∥ L是帶頭結(jié)點(diǎn)的單鏈表，本算法刪除其最小值結(jié)點(diǎn)。 {p=Lnext； ∥ p為工作指針。指向待處理的結(jié)點(diǎn)。假定鏈表非空。 pre=L； ∥ pre指向最小值結(jié)點(diǎn)的前驅(qū)。 q=p； ∥ q指向最小值結(jié)點(diǎn)，初始假定第一元素結(jié)點(diǎn)是最小值結(jié)點(diǎn)。 while（ pnext!=null） {if（ pnextdataqdata） {pre=p； q=pnext； } ∥查最小值結(jié) 點(diǎn) p=pnext； ∥指針后移。 } prenext=qnext；∥從鏈表上刪除最小值結(jié)點(diǎn) free（ q）； ∥釋放最小值結(jié)點(diǎn)空間 }∥結(jié)束算法 delete。 [算法討論 ] 算法中函數(shù)頭是按本教材類 C 描述語(yǔ)言書寫的。原題中 void delete（ linklist amp。L），是按 C++的“引用”來寫的，目的是實(shí)現(xiàn)變量的“傳址”，克服了 C 語(yǔ)言函數(shù)傳遞只是“值傳遞”的缺點(diǎn)。 10． [題目分析 ] 本題要求將鏈表中數(shù)據(jù)域值最小的結(jié)點(diǎn)移到鏈表的最前面。首先要查找最小值結(jié)點(diǎn) 。將其移到鏈表最前面，實(shí)質(zhì)上是將該結(jié)點(diǎn)從鏈表上摘下（不是刪除并回收空間），再插入到鏈表的最前面。 LinkedList delinsert（ LinkedList list） ∥ list 是非空線性鏈表，鏈結(jié)點(diǎn)結(jié)構(gòu)是（ data， link）， data 是數(shù)據(jù)域， link 是鏈域。 ∥本算法將鏈表中數(shù)據(jù)域值最小的那個(gè)結(jié)點(diǎn)移到鏈表的最前面。 {p=listlink；∥ p是鏈表的工作指針 pre=list； ∥ pre指向鏈表中數(shù)據(jù)域最小值結(jié)點(diǎn)的前驅(qū)。 q=p； ∥ q指向數(shù)據(jù)域最小值結(jié)點(diǎn)，初始假 定是第一結(jié)點(diǎn) while （ plink!=null） {if（ plinkdataqdata） {pre=p； q=plink； } ∥找到新的最小值結(jié)點(diǎn)； p=plink； } if (q!=listlink) ∥若最小值是第一元素結(jié)點(diǎn)，則不需再操作 {prelink=qlink； ∥將最小值結(jié)點(diǎn)從鏈表上摘下； qlink= listlink；∥將 q結(jié)點(diǎn)插到鏈表最前面。 listlink=q； } }∥算法結(jié)束 [算法討論 ] 算法中假定 list帶有頭結(jié)點(diǎn)，否則，插入操作變?yōu)?qlink=list； list=q。 11． [題目分析 ] 知道雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，與前驅(qū)交換涉及到四個(gè)結(jié)點(diǎn)（ p結(jié)點(diǎn)，前驅(qū)結(jié)點(diǎn)，前驅(qū)的前驅(qū)結(jié)點(diǎn)，后繼結(jié)點(diǎn)）六條鏈。 void Exchange（ LinkedList p） ∥ p是雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，本算法將 p所指結(jié)點(diǎn)與其前驅(qū)結(jié)點(diǎn)交換。 {q=pllink； qllinkrlink=p； ∥ p的前驅(qū)的前驅(qū)之后繼為 p pllink=qllink； ∥ p的前驅(qū)指向其前 驅(qū)的前驅(qū)。 qrlink=prlink； ∥ p的前驅(qū)的后繼為 p的后繼。 qllink=p； ∥ p與其前驅(qū)交換 prlinkllink=q； ∥ p的后繼的前驅(qū)指向原 p的前驅(qū) prlink=q； ∥ p的后繼指向其原來的前驅(qū) }∥算法 exchange結(jié)束。 12． [題目分析 ] 順序存儲(chǔ)的線性表遞增有序，可以順序查找，也可折半查找。題目要求“用最少的時(shí)間在表中查找數(shù)值為 x的元素”，這里應(yīng)使用折半查找方法。 void SearchExchangeInsert（ ElemType a[]； ElemType x） ∥ a是具有 n個(gè)元素的遞增有序線性表，順序存儲(chǔ)。本算法在表中查找數(shù)值為 x的元素，如查到則與其后繼交換位置；如查不到，則插入表中，且使表仍遞增有序。 { low=0； high=n1； ∥ low和 high指向線性表下界和上界的下標(biāo) while（ low=high） {mid=（ low+high） /2； ∥找中間位置 if（ a[mid]==x） break； ∥ 找到 x，退出 while循環(huán)。 else if （ a[mid] x） low=mid+1；∥到中點(diǎn) mid的右半去查。 else high=mid1； ∥到中點(diǎn) mid的左部去查。 } if（ a[mid]==x amp。amp。 mid!=n）∥ 若最后一個(gè)元素與 x相等，則不存在與其后繼交換的操作。 {t=a[mid]； a[mid]=a[mid+1]； a[mid+1]=t； } ∥ 數(shù)值 x與其后繼元素位置交換。 if（ lowhigh） ∥查找失敗，插入數(shù)據(jù)元素 x {for（ i=n1； ihigh； i） a[i+1]=a[i]；∥后移元素。 a[i+1]=x；∥插入 x。 } ∥結(jié)束插入 }∥結(jié)束本算法。 [算法討論 ] 首先是線性表的描述。算法中使用一維數(shù)組 a表示線性表，未使用包含數(shù)據(jù)元素的一維數(shù)組和指示線性表長(zhǎng)度的結(jié)構(gòu)體。若使用結(jié)構(gòu)體，對(duì)元素的引用應(yīng)使用[i]。另外元素類型就假定是 ElemType，未指明具體類型。其次， C 中一維數(shù)組下標(biāo)從 0開始，若說有 n個(gè)元素的一維數(shù)組，其最后一個(gè)元素的下標(biāo)應(yīng)是 n1。第三，本算法可以寫成三 個(gè)函數(shù)，查找函數(shù)，交換后繼函數(shù)與插入函數(shù)。寫成三個(gè)函數(shù)顯得邏輯清晰，易讀。 13． [題目分析 ] 判斷鏈表中數(shù)據(jù)是否中心對(duì)稱，通常使用棧。將鏈表的前一半元素依次進(jìn)棧。在處理鏈表的后一半元素時(shí)，當(dāng)訪問到鏈表的一個(gè)元素后，就從棧中彈出一個(gè)元素，兩元素比較，若相等，則將鏈表中下一元素與棧中再?gòu)棾鲈乇容^，直至鏈表到尾。這時(shí)若棧是空棧，則得出鏈表中心對(duì)稱的結(jié)論；否則，當(dāng)鏈表中一元素與棧中彈出元素不等時(shí)，結(jié)論為鏈表非中心對(duì)稱，結(jié)束算法的執(zhí)行。 int dc（ LinkedList h， int n） ∥ h 是帶頭結(jié)點(diǎn)的 n 個(gè)元素單鏈表，鏈表中結(jié)點(diǎn)的數(shù)據(jù)域是字符。本算法判斷鏈表是否是中心對(duì)稱。 {char s[]。 int i=1；∥ i記結(jié)點(diǎn)個(gè)數(shù)， s字符棧 p=hnext；∥ p是鏈表的工作指針，指向待處理的當(dāng)前元素。 for（ i=1； i=n/2； i++）∥ 鏈表前一半元素進(jìn)棧。 {s[i]=pdata； p=pnext； } i。 ∥恢復(fù)最后的 i值 if（ n%2==1） p=pnext； } ∥若 n是奇數(shù)，后移過中心結(jié)點(diǎn)。 while（ p!=null amp。amp。 s[i]==pdata） {i； p=pnext； } ∥測(cè)試是否中心對(duì)稱。 if（ p==null） return（ 1）；∥鏈表中心對(duì)稱 else return（ 0）； ∥鏈表不中心對(duì)稱 }∥算法結(jié)束。 [算法討論 ] 算法中先將“鏈表的前一半”元素（字符）進(jìn)棧。當(dāng) n為偶數(shù)時(shí)，前一半和后一半的個(gè)數(shù)相同；當(dāng) n為奇數(shù)時(shí)，鏈表中心結(jié)點(diǎn)字符不必比較，移動(dòng)鏈表指針到下一字符開始比較。比較過程中遇到不相等時(shí)，立即退出 while 循環(huán)，不再進(jìn)行比較。 14． [題目分析 ] 在單鏈表中刪除自第 i個(gè)元素起的共 len 個(gè)元素，應(yīng)從 第 1個(gè)元素起開始計(jì)數(shù)，記到第 i個(gè)時(shí)開始數(shù) len個(gè)，然后將第 i1個(gè)元素的后繼指針指向第 i+len個(gè)結(jié)點(diǎn)，實(shí)現(xiàn)了在 A鏈表中刪除自第 i個(gè)起的 len個(gè)結(jié)點(diǎn)。這時(shí)應(yīng)繼續(xù)查到 A的尾結(jié)點(diǎn)，得到刪除元素后的 A鏈表。再查 B鏈表的第 j個(gè)元素，將 A鏈表插入之。插入和刪除中應(yīng)注意前驅(qū)后繼關(guān)系，不能使鏈表“斷鏈”。另外，算法中應(yīng)判斷 i， len和 j的合法性。 LinkedList DelInsert（ LinkedList heada， headb， int i， j， len） ∥ heada和 headb均是帶頭結(jié)點(diǎn)的單鏈表。本算法刪除 heada鏈表中自第 i個(gè)元素起的共len個(gè)元素，然后將單鏈表 heada插入到 headb的第 j個(gè)元素之前。 {if（ i1 || len1 || j1） {printf（“參數(shù)錯(cuò)誤 \n”）； exit（ 0）； }∥參數(shù)錯(cuò)，退出算法。 p=heada；∥ p為鏈表 A的工作指針，初始化為 A的頭指針，查到第 i個(gè)元素時(shí)， p指向第 i1個(gè)元素 k=0；∥計(jì)數(shù) while（ p!=null amp。amp。 ki1）∥查找第 i個(gè)結(jié)點(diǎn)。 {k++； p=pnext； } if（ p==null） {printf（“給的 %d太大 \n” ,i）； exit（ 0）； } ∥ i太大，退出算法 q=pnext；∥ q為工作指針，初始指向 A鏈表第一個(gè)被刪結(jié)點(diǎn)。 k=0； while（ q!=null amp。amp。 klen） {k++； u=q， q=qnext； free（ u）； } ∥刪除結(jié)點(diǎn)，后移指針。 if（ klen） {printf（“給的 %d太大 \n” ,len）； exit（ 0）； } pnext=q；∥ A鏈表刪除了 len個(gè)元素。 if (headanext!=null) ∥ headanext=null 說明鏈表中結(jié)點(diǎn)均已刪除，無需往 B表 插入 {while