【正文】 ，對在第一元素結(jié)點前插入結(jié)點和刪除第一結(jié)點，其操作與對其它結(jié)點的操作統(tǒng)一了。 END。 END。在鏈式存儲結(jié)構(gòu)中插入和刪除操作不需要移動元素。 2．鏈式存儲結(jié)構(gòu)一般說克服了順序存儲結(jié)構(gòu)的三個弱點。 B!=null) ∥兩均未空時循環(huán) (2)Aelement==Belement ∥兩表中相等元素不作結(jié)果元素 (3)B=Blink ∥向后移動 B表指針 (4)A!=null ∥將 A 表剩余部分放入結(jié)果表中 (5)lastlink=null ∥置鏈表尾 四、 應(yīng)用題 1．（ 1）選鏈式存儲結(jié)構(gòu)。 ∥或 r^.next:=r^.next^.next 刪最大值結(jié)點 36． (1)Lnext=null ∥置空鏈表 ,然后將原鏈表結(jié)點逐個插入到有序表中 (2)p!=null ∥當(dāng)鏈表尚未到尾， p為工作指針 (3)q!=null ∥查 p結(jié)點在鏈表中的插入位置，這時 q是工作指針。 ∥ q是工作指針 p的前驅(qū) (2)p^.datam ∥ p是工作指針 (3)r:=q。 ∥頭指針仍為 L 32. (1) p^.nextp0 (2)r:= p^.next (3) p^.next:= q0。 ∥結(jié)點 q插入結(jié)點 p前 (4) q^.freq=0 ∥鏈表中無值為 x的結(jié)點，將新建結(jié)點插入到鏈表最后（頭結(jié)點前）。 ∥先將 q結(jié)點從鏈 表上摘下 q^.next:=p?！蔚谝粋€結(jié)點值最小； (5)p^link:=q^.link。 ∥計數(shù)器，記被刪結(jié)點 (E)q:=p^.link∥記下被刪結(jié)點 (F)p^.link=q^.link ∥刪除結(jié)點 27. (1)p:=r。 25.(1)i= ∥ 為元素 個數(shù) (2)j:=j+1 ∥有值不相等的元素 (3)[j]:=[i] ∥元素前移 (4):=j ∥元素個數(shù) 26.(A)p^.link:=q。 (4) IF (q=NIL) THEN r^.next:=p。 20． A． VAR head:ptr B. new(p) C. p^.data:=k D. q^.next:=p E. q:=p(帶頭結(jié)點 ) 21．（ 1） new(h)。 [注 ]：本題是在鏈表上求模式匹配問 題。 (4)pb:=pre^.next。 (5) return(false)。pnext=s。 free(u)。 pnext=f。另外，不論鏈表是否為空，鏈表指針不變。 9．非空線性表第一個元素?zé)o前驅(qū)，最后一個元素?zé)o后繼。 頭結(jié)點并不“僅起”標識作用，并且使操作統(tǒng)一。另外，頭結(jié)點數(shù)據(jù)域可寫入鏈表長度，或作監(jiān)視哨。 13．線性表是邏輯結(jié)構(gòu)，可以順序存儲，也可鏈式存儲。 6． O(1)， O(n) 7．單鏈表， 多重 鏈表，（動態(tài)）鏈表，靜態(tài)鏈表 8． fnext=pnext。 9． p^.prior s^.prior^.next 10． 指針 11．物理上相鄰 指針 12． 4 2 13．從任一結(jié)點出發(fā)都可訪問到鏈 表中每一個元素。 15 ． Lnextnext==L 16． pnext!=null 17． Lnext==L amp。 19． (1) IF pa=NIL THEN return(true)。 非遞歸算法： (1)pre:=pb。pre:=pb。非遞歸算法中用指針 pre指向主串中開始結(jié)點（初始時為第一元素結(jié)點）?！紊深^ 結(jié)點，以便于操作。 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?！卫湘湥膀?qū)指向后繼 (B)p:=q。∥ r指向工作指針 s的前驅(qū)， p指向最小值的前驅(qū)?！慰邕^被刪結(jié)點（即刪除一結(jié)點） 28． (1) l^.key:=x。 q^.pre:=p^.pre。 29． (1)a^.key:=’ ’∥ a的頭結(jié)點用作監(jiān)視哨，取不同于 a鏈表中其它數(shù)據(jù)域的值 (2)b^.key:=p^.key∥ b的頭結(jié)點起監(jiān)視哨作用 (3)p:=p^.next∥找到 a,b表中共同字母， a表指針后移 (4)0(m*n) 30. C 部 分： (1)p!=null ∥鏈表未到尾就一直作 (2)q ∥將當(dāng)前結(jié)點作為頭結(jié)點后的第一元素結(jié)點插入 31. (1)L=Lnext。 (4) q0:= p。 ∥ r 記最大值 的前驅(qū)， (4)q:=p。 (4)pnext=rnext ∥將 p結(jié)點鏈入鏈表中 (5)rnext=p ∥ r是 q的前驅(qū)， u是下個待插入結(jié)點的指針。它可動態(tài)申請內(nèi)存空間，不受表長度（即表中元素個數(shù)）的影響，插入、刪 除時間復(fù)雜度為 O（ 1）。首先，插入、刪除不需移動元素，只修改指針，時間復(fù)雜度為 O(1)；其次，不需要預(yù)先分配空間，可根據(jù)需要動態(tài)申請空間；其三，表容量只受可用內(nèi)存空間的限制。 4．線性表 棧 隊列 串 順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。 鏈式存儲結(jié)構(gòu)的定義是： TYPE pointer=↑ nodetype。 linklisttp=pointer。而且無論鏈表是否為空，頭指針均不為空。初始化時，頭結(jié)點（下標為 0的元素）其 next域值為 1，其 pre域值為 n（設(shè) n是元素個數(shù)，且 nmaxsize） (2) stalist[stalist[p].pre].pre。 10．本題是鏈表的逆置問題。 pre指向當(dāng)前結(jié)點， p指向 pre的后繼。 13. 設(shè)單鏈表的頭結(jié)點的 頭指針為 head,且 pre=head； while(prenext!=p) pre=prenext。 (1) while(p!=null amp?！尾檎沂? else return(p)。 if(p==null || pdataX) return(null)。 pdataX) p=pnext。鏈表中結(jié)點值與從前逆序。 則 q^.rlink:=p^.rlink。 p^.rlink:=q?！我韵氯涞捻樞虿荒茏? p^.rlink^.llink q。 subp(pa,pb)調(diào)用結(jié)果是將 pa 到 pb的前驅(qū)構(gòu)造為循環(huán)鏈表。 19．在指針 p所指結(jié)點前插入結(jié)點 s的語句如下： spre=ppre。 20． (A) f1NIL并且 f2NIL (B) f1↑ .data f2↑ .data (C) f2↑ .dataf1↑ .data (D) f3↑ .dataf1↑ .data (E) f1 f1↑ .link 或 f2=f2↑ .link。 (2)pnextprior=q?！魏笠浦羔?，再將新結(jié)點插入 到適當(dāng)位置。 LinkedList Union(LinkedList la,lb) ∥ la,lb分別是帶頭結(jié)點的兩個單鏈表的頭指針，鏈表中的元素值按遞增序排列，本算法將兩鏈表合并成一個按元素值遞減次序排列的單鏈表。 ∥ la 作結(jié)果鏈表的頭指針，先將結(jié)果鏈表初始化為空。 ∥將 pa 的后繼結(jié)點暫存于 r。 pa=r。 pbnext=lanext。 ∥恢復(fù) pb為當(dāng)前待比較結(jié)點。 lanext=pa。 lanext=pb。amp。算法中最后兩個 while語句，不可能執(zhí)行兩個，只能二者取一，即哪個表尚未到尾，就將其逆置到結(jié) 果表中，即將剩余結(jié)點依次前插入到結(jié)果表的頭結(jié)點后面。 la=(LinkedList)malloc(sizeof(LNode))。 ∥ pa是 ha鏈表的工作指針 pb=hb。amp。} else if(padatapbdata)∥處理 hb中數(shù)據(jù)。 pre=r。 } else∥處理 padata=pbdata。∥兩結(jié)點數(shù)據(jù)相等時，只將 ha的數(shù)據(jù)鏈入。 else prenext=pb。 (2)本題與上面兩題類似，要求結(jié)果指針為 lc，其核心語句段如下： pa=lanext?！?pc是結(jié)果鏈表中當(dāng)前結(jié)點的前驅(qū) while(paamp。pa=panext。} if(pa)pcnext=pa。∥釋放原來兩鏈表的頭結(jié)點。 本題與上面 1．（ 2）基本相同，不同之處 1．（ 2）中鏈表是“非遞減有序”，（可能包含相等元素），本題是元素“遞增有序”（不準有相同元素）。本算法求 A 和 B 的并集 A∪ B，仍用線性表表示，結(jié)果鏈表元素也是遞增有序。 pc=ha。pb) if(padatapbdata) {pcnext=pa。pc=pb。pa=panext。} if(pa) pcnext=pa。 free(hb)。 (2) 本題是求交集，即只有同時出現(xiàn)在兩集合中的元素才出現(xiàn)在結(jié)果表中?！谓Y(jié)果表中當(dāng)前合并結(jié)點的前驅(qū)的指針。 { pcnext=pa。pb=pbnext。free(u)。} while(pa){ u=pa。 pb=pbnext。 free(lb)。pb=L2next。 while(paamp。free(u)。pa=panext。free(u)。pa=panext。free(u)。 （ 4） 本題與上面（ 3）算法相同，只是結(jié)果表要另辟空間。pb=Bnext。 ∥ pre指向結(jié)果鏈表中當(dāng)前待合并結(jié)點的前驅(qū)。pa=panext。 if(pbdatapcdata)pb=pbnext。 if(pbamp。 {prenext=pb。}∥ B， C公共元素為結(jié)果表第一元素。amp。 else if(pbdatapcdata) pc=pcnext。amp。 {prenext=pa。pre=pb。pc=pcnext。pbamp。 }∥算法 Union結(jié)束 [算法討論 ]本算法先找結(jié)果鏈表的第一個元素，這是因為題目要求結(jié)果表要遞增有序（即刪除重復(fù)元素）。因此先將第一結(jié)點鏈入是可取的。 最后一個問題是，當(dāng) B， C有一表為空（即 B和 C已無公共元素時），要將 A的剩余部分鏈入結(jié)果表。int m,n) ∥ L1和 L2分別是兩循環(huán)單鏈表的頭結(jié)點的指針， m和 n分別是 L1和 L2的長度。 {if(m==0)return(L2)。∥查最后一個元素結(jié)點。 free(L1)。 else{p=L2?！螌?L2的元素結(jié)點插入到 L1 循環(huán)單鏈表的第一元素結(jié)點前。 } }∥算法結(jié)束。 { q=lanext。 lbnext=q。 }∥算法結(jié)束。 lanext=qnext。 ∥返回結(jié)果單循環(huán)鏈表的尾指針 lb。 ∥將循環(huán)單鏈表最后元素結(jié)點接在 ha 第一元素前。 若兩鏈表均不帶頭結(jié)點，則算法片段如下： q=hbnext。 ha=q。另外，題中敘述“線性表空間足夠大”也暗示出另外合并方式，即應(yīng)從線性表的最后一個元素開始比較，大者放到最終位置上。LB:SeqList) ∥ LA和 LB是順序存儲的非遞減有序線性表，本算法將 LB合并到 LA中，元素仍非遞減有序。 k:=m+n。 ∥ i， j分別為線性表 LA和 LB的工作指針（下標）。] ELSE[[k]:=[j]。k:=k1。 [算法討論 ]算法中數(shù)據(jù)移動是主要操作。本算法利用了題目中“線性表空間足夠大”的條件，“最大限度的避免移動元素”，是“一種高效算法”。本算法將該鏈表按結(jié)點數(shù)據(jù)域的值的大小，從小到大重新鏈接?！渭俣ǖ谝粋€元素有序，即鏈表中現(xiàn)只有一個結(jié)點。 if(qdatapdata