【正文】 頭結點并不“僅起”標識作用，并且使操作統(tǒng)一。 13．線性表是邏輯結構，可以順序存儲，也可鏈式存儲。 9． p^.prior s^.prior^.next 10． 指針 11．物理上相鄰 指針 12． 4 2 13．從任一結點出發(fā)都可訪問到鏈 表中每一個元素。 19． (1) IF pa=NIL THEN return(true)。pre:=pb。∥生成頭 結點，以便于操作?！卫湘?，前驅指向后繼 (B)p:=q?！慰邕^被刪結點（即刪除一結點） 28． (1) l^.key:=x。 29． (1)a^.key:=’ ’∥ a的頭結點用作監(jiān)視哨，取不同于 a鏈表中其它數(shù)據(jù)域的值 (2)b^.key:=p^.key∥ b的頭結點起監(jiān)視哨作用 (3)p:=p^.next∥找到 a,b表中共同字母， a表指針后移 (4)0(m*n) 30. C 部 分： (1)p!=null ∥鏈表未到尾就一直作 (2)q ∥將當前結點作為頭結點后的第一元素結點插入 31. (1)L=Lnext。 ∥ r 記最大值 的前驅， (4)q:=p。它可動態(tài)申請內(nèi)存空間，不受表長度（即表中元素個數(shù)）的影響，插入、刪 除時間復雜度為 O（ 1）。 4．線性表 棧 隊列 串 順序存儲結構和鏈式存儲結構。 linklisttp=pointer。初始化時，頭結點（下標為 0的元素）其 next域值為 1，其 pre域值為 n（設 n是元素個數(shù)，且 nmaxsize） (2) stalist[stalist[p].pre].pre。 pre指向當前結點， p指向 pre的后繼。 (1) while(p!=null amp。 if(p==null || pdataX) return(null)。鏈表中結點值與從前逆序。 p^.rlink:=q。 subp(pa,pb)調(diào)用結果是將 pa 到 pb的前驅構造為循環(huán)鏈表。 20． (A) f1NIL并且 f2NIL (B) f1↑ .data f2↑ .data (C) f2↑ .dataf1↑ .data (D) f3↑ .dataf1↑ .data (E) f1 f1↑ .link 或 f2=f2↑ .link?！魏笠浦羔?，再將新結點插入 到適當位置。 ∥ la 作結果鏈表的頭指針，先將結果鏈表初始化為空。 pa=r。 ∥恢復 pb為當前待比較結點。 lanext=pb。算法中最后兩個 while語句，不可能執(zhí)行兩個，只能二者取一，即哪個表尚未到尾，就將其逆置到結 果表中，即將剩余結點依次前插入到結果表的頭結點后面。 ∥ pa是 ha鏈表的工作指針 pb=hb。} else if(padatapbdata)∥處理 hb中數(shù)據(jù)。 } else∥處理 padata=pbdata。 else prenext=pb。∥ pc是結果鏈表中當前結點的前驅 while(paamp。} if(pa)pcnext=pa。 本題與上面 1．（ 2）基本相同，不同之處 1．（ 2）中鏈表是“非遞減有序”，（可能包含相等元素），本題是元素“遞增有序”（不準有相同元素）。 pc=ha。pc=pb。} if(pa) pcnext=pa。 (2) 本題是求交集，即只有同時出現(xiàn)在兩集合中的元素才出現(xiàn)在結果表中。 { pcnext=pa。free(u)。 pb=pbnext。pb=L2next。free(u)。free(u)。free(u)。pb=Bnext。pa=panext。 if(pbamp。}∥ B， C公共元素為結果表第一元素。 else if(pbdatapcdata) pc=pcnext。 {prenext=pa。pc=pcnext。 }∥算法 Union結束 [算法討論 ]本算法先找結果鏈表的第一個元素，這是因為題目要求結果表要遞增有序（即刪除重復元素）。 最后一個問題是，當 B， C有一表為空（即 B和 C已無公共元素時），要將 A的剩余部分鏈入結果表。 {if(m==0)return(L2)。 free(L1)?！螌?L2的元素結點插入到 L1 循環(huán)單鏈表的第一元素結點前。 { q=lanext。 }∥算法結束。 ∥返回結果單循環(huán)鏈表的尾指針 lb。 若兩鏈表均不帶頭結點，則算法片段如下： q=hbnext。另外，題中敘述“線性表空間足夠大”也暗示出另外合并方式，即應從線性表的最后一個元素開始比較，大者放到最終位置上。 k:=m+n。] ELSE[[k]:=[j]。 [算法討論 ]算法中數(shù)據(jù)移動是主要操作。本算法將該鏈表按結點數(shù)據(jù)域的值的大小，從小到大重新鏈接。 if(qdatapdata)∥處理待排序結點 p比第一個元素結點小的情況。 plink=qlink。兩種存儲結構下最佳和最差情況的比較次數(shù)相同，在鏈表情況下，不移動 元素，而是修改結點指針。amp。本算法利用直接插入原則將鏈表整理成遞增的有序鏈表。 q=la。 p=r。 s:=listhead。 IF pre^.DATAs^.DATA THEN[s^.NEXT:=pre。 IF Q=NIL THEN[Q:=s。 IF pre^.NEXT^.DATAs^.DATA THEN pre:=pre^.NEXT。如有頭結點，算法不必單獨處理在第一個結點前插入結點情況，算法會規(guī)范統(tǒng)一，下面的（ 1）是處理帶頭結點的例子。 C=(LinkedList )malloc(sizeof(LNode))。 ∥暫存 p的后繼?！?p指向新的待處理結點。鏈表中結點的相對順序同原鏈表?！?ra和 rb將分別指向將創(chuàng)建的 A表和 B表的尾結點。 i++。 ra=p。 {i=0。 ∥ 若當前元素為大于等于零，則指針前移。 if(ij) a[j]=a[i]。對此問題的擴充是若元素包含正數(shù)、負數(shù)和零，并要求按負數(shù)、零、正數(shù)的順序重排線性表，統(tǒng)計負數(shù)、零、正數(shù)的個數(shù)。 while(ij) {while(ij amp。 a[j]t) j。本算法將 A拆成 B和 C 兩個表， B中存放大于 ∥等于零的元素， C中存放小于零的元素。 ∥將大于零的元素放入 B表。本算法將 n個元素中所有大于等于 19的整數(shù)放在所有小于 19 的整數(shù)之后。所以算法應首先遍歷鏈表，求得最小值結點及其前驅。 while（ pnext!=null） {if（ pnextdataqdata） {pre=p； q=pnext； } ∥查最小值結 點 p=pnext； ∥指針后移。 LinkedList delinsert（ LinkedList list） ∥ list 是非空線性鏈表，鏈結點結構是（ data， link）， data 是數(shù)據(jù)域， link 是鏈域。 qrlink=prlink； ∥ p的前驅的后繼為 p的后繼。 else high=mid1； ∥到中點 mid的左部去查。 [算法討論 ] 首先是線性表的描述。將鏈表的前一半元素依次進棧。 {s[i]=pdata； p=pnext； } i。比較過程中遇到不相等時，立即退出 while 循環(huán)，不再進行比較。 {if（ i1 || len1 || j1） {printf（“參數(shù)錯誤 \n”）； exit（ 0）； }∥參數(shù)錯，退出算法。 if（ klen） {printf（“給的 %d太大 \n” ,len）； exit（ 0）； } pnext=q；∥ A鏈表刪除了 len個元素。amp。這時應繼續(xù)查到 A的尾結點，得到刪除元素后的 A鏈表。 while（ p!=null amp。這時若棧是空棧，則得出鏈表中心對稱的結論；否則，當鏈表中一元素與棧中彈出元素不等時，結論為鏈表非中心對稱，結束算法的執(zhí)行。若使用結構體，對元素的引用應使用[i]。amp。 12． [題目分析 ] 順序存儲的線性表遞增有序，可以順序查找，也可折半查找。 {p=listlink；∥ p是鏈表的工作指針 pre=list； ∥ pre指向鏈表中數(shù)據(jù)域最小值結點的前驅。 [算法討論 ] 算法中函數(shù)頭是按本教材類 C 描述語言書寫的。 LinkedList Delete（ LinkedList L） ∥ L是帶頭結點的單鏈表，本算法刪除其最小值結點。 [算法討論 ] 分界元素 t放入 a[i]，而不論它的值如何。若采用教材中的線性表，則元素的表示作相應改變，例 如 [i]，而最后 B和 C表應置上表的長度，如 =j和 =k。 ∥ i， j， k是工作指針，分別指向 A、 B和 C表的當前元素。 if(ij) a[i++]=a[j]。 a[i]=t) i++。 類似本題的選了 5 個題，其解答如下： （ 1）與上面第 8題不同的是，這里要求以 an為參考元素，將線性表分成左右兩部分。 } a[i]=t。i++。 ∥ i,j為工作指針（下標），初始指向線性表 a的第 1個和第 n個元素。 ∥將 p恢復為指向新的待處理結點。 {pnext=rbnext。rb=B。∥ i記鏈表中結點的序號。 [算法討論 ]因為本題并未要求鏈表中結點的數(shù)據(jù)值有序，所以算法中采取最簡單方式：將新結點前插到頭結點后面（即第一元素之前）。 {pnext=Bnext。 Cnext=null ∥ C初始化為空表。 類似本題的其它題解答如下： （ 1） [題目分析 ]本題基本類似于上面第 7 題，不同之處有二?！捂溔氪私Y點。] ∥第一奇數(shù)鏈結點。∥插入當前最小值結點修改頭指針 ] ELSE[WHILE pre^.NEXTNIL DO IF pre^.NEXT^.DATAs^.DATA THEN pre:=pre^.NEXT。 ∥暫存 s的后繼。 7． [題目分析 ]本題要求將一個鏈表分解成兩個鏈表，兩個鏈表都要有序，兩鏈表建立過程中不得使用 NEW過程申請空間，這就是要利用原鏈表空間，隨著原鏈表的分解，新建鏈表隨之排序。amp。 {p=lanextnext。 plink=qlink。如果 list是頭結點的指針，則相應處理要簡單些，其算法片段如下： p=listlink。 qlink=p。 list=p。 ∥ p是工作指針，指向待排序的當前元素。因數(shù)據(jù)合并到 LA 中，所以在退出第一個 WHILE循環(huán)后，只需要一 個 WHILE循環(huán)，處理 LB中剩余元素。j:=j1。 i:=m。這樣從后向前，直到第一個元素為止。 hbnext=ha。 其核心算法片段如下（設兩鏈表均有頭結點） q=hbnext。 ∥ q指向 lb的頭結點； lbnext=lanext。 lanext=lbnext。 free(L2)。 } }∥處理完 mn情況 else∥ 下面處理 L2長度小于等于 L1的情況 {if(n==0)return(L1)。 else{p=L1。題目要求“用最快速度將兩表合并“，因此應找結點個數(shù)少的鏈表查其尾結點。由于初始 pre=A（頭結點的頭指針），這時的 data域無意義，不能與后繼比較元素大小，因此就需要確定第一個元素。 } }∥ while(paamp。pa=panext。 ∥ B表和 C表有公共元素。amp。pc)∥ 因共同元素而非 B表或 C表空而退出上面 while 循環(huán)。amp?！卧O置三個工作指針。 ∥置結果鏈表尾。 else{ pcnext=pa。 ∥ pb指針后移 else ∥處理交集元素 {if(pc==L1) {pcnext=pa。 pc=L1。}∥釋放結點空間 pcnext=null。 pb=pbnext。pa=panext。pb=lbnext。