目前最完整的數(shù)據(jù)結(jié)構(gòu)1800題包括完整答案線性表答案

1、第2章 線性表一選擇題 1.A2.B3.C4.A5.D6.D7.D8.C9.B10.B,C11.1I11.2I11.3E11.4B11.5C12.B13.C14.C15.C16.A17.A18.A19.D20.C21.B22.D23.C24.B25.B26.A27.D二判斷題1. ×2.3. 4.×5.×6. ×7. ×8.×9.×10.×11.×12.×13. ×14. 15.×16. 部分答案解釋如下。1、 頭結(jié)點并不“僅起”標識作用，并且使操作統(tǒng)一。另外，頭結(jié)點數(shù)據(jù)域可

2、寫入鏈表長度，或作監(jiān)視哨。4兩種存儲結(jié)構(gòu)各有優(yōu)缺點，應(yīng)根據(jù)實際情況選用，不能籠統(tǒng)說哪一個好。7集合中元素無邏輯關(guān)系。9非空線性表第一個元素無前驅(qū)，最后一個元素無后繼。13線性表是邏輯結(jié)構(gòu)，可以順序存儲，也可鏈式存儲。三填空題1順序 2（n-1）/2 3py->next=px->next; px->next=py4 n-i+15主要是使插入和刪除等操作統(tǒng)一，在第一個元素之前插入元素和刪除第一個結(jié)點不必另作判斷。另外，不論鏈表是否為空，鏈表指針不變。6O(1)，O(n) 7單鏈表，多重鏈表，（動態(tài)）鏈表，靜態(tài)鏈表8f->next=p->next; f->prio

3、r=p; p->next->prior=f; p->next=f;9p.prior s.prior.next10 指針 11物理上相鄰 指針 124 213從任一結(jié)點出發(fā)都可訪問到鏈表中每一個元素。14u=p->next; p->next=u->next; free(u); 15L->next->next=L 16p->next!=null17L->next=L && L->prior=L 18s->next=p->next;p->next=s;19(1) IF pa=NIL THEN retu

4、rn(true);(2) pb<>NIL AND pa.data>=pb.data(3) return(inclusion(pa,pb);(4) pb:=pb.next;(5) return(false);非遞歸算法：(1)pre:=pb; (2) pa<>NIL AND pb<>NIL AND pb.data>=pa.data (3)pa:=pa.next; pb:=pb->next;(4)pb:=pre.next;pre:=pb;pa:=pa.next;(5)IF pa=NIL THEN return(true) ELSE return

5、(false);注：本題是在鏈表上求模式匹配問題。非遞歸算法中用指針pre指向主串中開始結(jié)點（初始時為第一元素結(jié)點）。若主串與子串對應(yīng)數(shù)據(jù)相等，兩串工作指針pa和pb后移；否則，主串工作指針從pre的下一結(jié)點開始（這時pre又指向新的開始結(jié)點），子串工作指針從子串第一元素開始，比較一直繼續(xù)到循環(huán)條件失敗。若pa為空，則匹配成功，返回true，否則，返回false。20AVAR head:ptr B. new(p) C. p.data:=k D. q.next:=p E. q:=p(帶頭結(jié)點)21（1）new(h);生成頭結(jié)點，以便于操作。 （2）r.next:=p; (3) r.next:=q

6、; (4) IF (q=NIL) THEN r.next:=p;22A: r.link.data<>max AND q.link.data<>maxB: r:=r.link C: q.link D: q.link E: r.link F: r.linkG: r:=s（或r:= r.link） H: r:=r.link I: q.link:=s.link 23(1)la (2)0 (3)j<i-1 (4)p.next (5)i<1 24.(1)head.left:=s head的前驅(qū)指針指向插入結(jié)點(2)j:=1;(3)p:=p.right 工作指針后移(4)

7、s.left:=p(5)p.right.left:=s; p后繼的前驅(qū)是s(6)s.left:=p;25.(1)i<=L.last L.last 為元素個數(shù) (2)j:=j+1 有值不相等的元素(3)L.elemj:=L.elemi 元素前移(4)L.last:=j 元素個數(shù)26.(A)p.link:=q;拉上鏈，前驅(qū)指向后繼 (B)p:=q;新的前驅(qū) (C)p.link:=head;形成循環(huán)鏈表 (D)j:=0; 計數(shù)器，記被刪結(jié)點 (E)q:=p.link記下被刪結(jié)點 (F)p.link=q.link 刪除結(jié)點27. (1)p:=r;r指向工作指針s的前驅(qū)，p指向最小值的前驅(qū)。 (2

8、)q:=s;q指向最小值結(jié)點，s是工作指針(3)s:=s.link工作指針后移(4)head:=head.next;第一個結(jié)點值最?。?5)plink:=q.link;跨過被刪結(jié)點（即刪除一結(jié)點）28(1) l.key:=x;頭結(jié)點l這時起監(jiān)視哨作用 (2) l.freq:=p.freq 頭結(jié)點起監(jiān)視哨作用(3) q->pre->next=q->next; q->next->pre=q->pre; 先將q結(jié)點從鏈表上摘下q.next:=p; q.pre:=p.pre; p.pre->next:=q; p.pre:=q; 結(jié)點q插入結(jié)點p前(4) q.f

9、req=0 鏈表中無值為x的結(jié)點，將新建結(jié)點插入到鏈表最后（頭結(jié)點前）。29(1)a.key:=a的頭結(jié)點用作監(jiān)視哨，取不同于a鏈表中其它數(shù)據(jù)域的值 (2)b.key:=p.keyb的頭結(jié)點起監(jiān)視哨作用 (3)p:=p.next找到a,b表中共同字母，a表指針后移 (4)0(m*n)30. C 部分：(1)p!=null 鏈表未到尾就一直作(2)q 將當前結(jié)點作為頭結(jié)點后的第一元素結(jié)點插入31. (1)L=L->next; 暫存后繼 (2)q=L; 待逆置結(jié)點 (3)L=p; 頭指針仍為L32. (1) p.next<>p0 (2)r:= p.next (3) p.next:

10、= q0; (4) q0:= p; (5) p:=r33. (1)r (2)NIL (3)x<head.data (4)p.data<x (5)p:=p.next (6)p.data>=x; (7)r (8)p (9)r (10)NIL (11)NIL34(1)pa!=ha 或pa->exp!=-1 (2)pa->exp=0 若指數(shù)為0，即本項為常數(shù)項 (3)q->next=pa->next 刪常數(shù)項 (4)q->next 取下一元素 (5)=pa->coef*pa->exp (6)- 指數(shù)項減1 (7)pa 前驅(qū)后移,或q->

11、next (8)pa->next 取下一元素 35(1)q:=p; q是工作指針p的前驅(qū)(2)p.data>m p是工作指針(3)r:=q; r 記最大值的前驅(qū)，(4)q:=p; 或q:=q.next;(5)r.next:=q.next; 或r.next:=r.next.next 刪最大值結(jié)點36(1)L->next=null 置空鏈表,然后將原鏈表結(jié)點逐個插入到有序表中 (2)p!=null 當鏈表尚未到尾，p為工作指針 (3)q!=null 查p結(jié)點在鏈表中的插入位置，這時q是工作指針。 (4)p->next=r->next 將p結(jié)點鏈入鏈表中 (5)r-&g

12、t;next=p r是q的前驅(qū)，u是下個待插入結(jié)點的指針。37程序（a） PASCAL部分(編者略）程序（b） C部分(1)(A!=null && B!=null) 兩均未空時循環(huán)(2)A->element=B->element 兩表中相等元素不作結(jié)果元素(3)B=B->link 向后移動B表指針(4)A!=null 將A 表剩余部分放入結(jié)果表中(5)last->link=null 置鏈表尾四、 應(yīng)用題 1（1）選鏈式存儲結(jié)構(gòu)。它可動態(tài)申請內(nèi)存空間，不受表長度（即表中元素個數(shù)）的影響，插入、刪除時間復(fù)雜度為O（1）。 （2）選順序存儲結(jié)構(gòu)。順序表可以隨機

13、存取，時間復(fù)雜度為O（1）。 2鏈式存儲結(jié)構(gòu)一般說克服了順序存儲結(jié)構(gòu)的三個弱點。首先，插入、刪除不需移動元素，只修改指針，時間復(fù)雜度為O(1)；其次，不需要預(yù)先分配空間，可根據(jù)需要動態(tài)申請空間；其三，表容量只受可用內(nèi)存空間的限制。其缺點是因為指針增加了空間開銷，當空間不允許時，就不能克服順序存儲的缺點。3采用鏈式存儲結(jié)構(gòu)，它根據(jù)實際需要申請內(nèi)存空間，而當不需要時又可將不用結(jié)點空間返還給系統(tǒng)。在鏈式存儲結(jié)構(gòu)中插入和刪除操作不需要移動元素。4線性表 棧 隊列 串 順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。 順序存儲結(jié)構(gòu)的定義是： CONST maxlen=線性表可能達到的最大長度； TYPE sqlisttp=

14、RECORD elem:ARRAY1.maxlen OF ElemType; last:0.maxlen; END; 鏈式存儲結(jié)構(gòu)的定義是： TYPE pointer=nodetype; nodetype=RECORD data:ElemType; next:pointer; END; linklisttp=pointer;5.順序映射時，ai與ai+1的物理位置相鄰；鏈表表示時ai與ai+1的物理位置不要求相鄰。6在線性表的鏈式存儲結(jié)構(gòu)中，頭指針指鏈表的指針，若鏈表有頭結(jié)點則是鏈表的頭結(jié)點的指針，頭指針具有標識作用，故常用頭指針冠以鏈表的名字。頭結(jié)點是為了操作的統(tǒng)一、方便而設(shè)立的，放在第一元

15、素結(jié)點之前，其數(shù)據(jù)域一般無意義（當然有些情況下也可存放鏈表的長度、用做監(jiān)視哨等等），有頭結(jié)點后，對在第一元素結(jié)點前插入結(jié)點和刪除第一結(jié)點，其操作與對其它結(jié)點的操作統(tǒng)一了。而且無論鏈表是否為空，頭指針均不為空。首元結(jié)點也就是第一元素結(jié)點，它是頭結(jié)點后邊的第一個結(jié)點。7見上題6。8(1)將next域變?yōu)閮蓚€域: pre和next，其值域均為0.maxsize。初始化時，頭結(jié)點（下標為0的元素）其next域值為1，其pre域值為n（設(shè)n是元素個數(shù)，且n<maxsize） (2) staliststalistp.pre.pre;(3) stalistp.next; 9. 在單鏈表中不能從當前結(jié)點

16、（若當前結(jié)點不是第一結(jié)點）出發(fā)訪問到任何一個結(jié)點，鏈表只能從頭指針開始，訪問到鏈表中每個結(jié)點。在雙鏈表中求前驅(qū)和后繼都容易，從當前結(jié)點向前到第一結(jié)點，向后到最后結(jié)點，可以訪問到任何一個結(jié)點。 10本題是鏈表的逆置問題。設(shè)該鏈表帶頭結(jié)點，將頭結(jié)點摘下，并將其指針域置空。然后從第一元素結(jié)點開始，直到最后一個結(jié)點為止，依次前插入頭結(jié)點的后面，則實現(xiàn)了鏈表的逆置。 11該算法的功能是判斷鏈表L是否是非遞減有序，若是則返回“true”；否則返回“false“。pre指向當前結(jié)點，p指向pre的后繼。 12q=p->next; p->next=q->next; free(q); 13.

17、設(shè)單鏈表的頭結(jié)點的頭指針為head,且pre=head； while(pre->next!=p) pre=pre->next; s->next=p; pre->next=s; 14.設(shè)單鏈表帶頭結(jié)點，工作指針p初始化為p=H->next; (1) while(p!=null && p->data!=X) p=p->next; if(p= =null) return(null);查找失敗else return(p);查找成功(2) while(p!=null && p->data<X ) p=p->nex

18、t; if(p=null | p->data>X) return(null);查找失敗 else return(p);(3) while(p!=null && p->data>X) p=p->next; if(p=null | p->data<X) return(null); 查找失敗 else return(p); 查找成功 15.本程序段功能是將pa和pb鏈表中的值相同的結(jié)點保留在pa鏈表中（pa中與pb中不同結(jié)點刪除），pa是結(jié)果鏈表的頭指針。鏈表中結(jié)點值與從前逆序。S1記結(jié)果鏈表中結(jié)點個數(shù)（即pa與pb中相等的元素個數(shù)）。S2記

19、原pa鏈表中刪除的結(jié)點個數(shù)。 16設(shè) q:=p.llink; 則 q.rlink:=p.rlink; p.rlink.llink:=q; p.llink:=q.llink;q.llink.rlink:=p; p.rlink:=q; q.llink:=p 17.(1)前兩個語句改為： p.llink.rlink<- p.rlink; p.rlink.llink<- p.llink;(2)后三個語句序列應(yīng)改為：q.rlink<- p.rlink;以下三句的順序不能變 p.rlink.llink<- q; p.rlink<- q; 18mp是一個過程，其內(nèi)嵌套有過程su

20、bp。subp(s,q)的作用是構(gòu)造從s到q的循環(huán)鏈表。subp(pa,pb)調(diào)用結(jié)果是將pa到pb的前驅(qū)構(gòu)造為循環(huán)鏈表。subp(pb,pa)調(diào)用結(jié)果是將pb到pa的前驅(qū)（指在L鏈表中，并非剛構(gòu)造的pa循環(huán)鏈表中）構(gòu)造為循環(huán)鏈表。總之，兩次調(diào)用將L循環(huán)鏈表分解為兩個。第一個循環(huán)鏈表包含從pa到pb的前驅(qū),L中除剛構(gòu)造的pa到pb前驅(qū)外的結(jié)點形成第二個循環(huán)鏈表。 19在指針p所指結(jié)點前插入結(jié)點s的語句如下：s->pre=p->pre; s->next=p; p->pre->next=s; p->pre=s; 20(A) f1<>NIL并且f2&l

21、t;>NIL(B) f1.data < f2.data(C) f2.data<f1.data(D) f3.data<f1.data(E) f1<- f1.link 或f2=f2.link; 21. 1）本算法功能是將雙向循環(huán)鏈表結(jié)點的數(shù)據(jù)域按值自小到大排序，成為非遞減（可能包括數(shù)據(jù)域值相等的結(jié)點）有序雙向循環(huán)鏈表。 2）(1)r->prior=q->prior;將q結(jié)點摘下，以便插入到適當位置。(2)p->next->prior=q;（2）（3）將q結(jié)點插入(3)p->next=q;(4)r=r->next;或r=q->n

22、ext;后移指針，再將新結(jié)點插入到適當位置。五、 算法設(shè)計題1題目分析因為兩鏈表已按元素值遞增次序排列，將其合并時，均從第一個結(jié)點起進行比較，將小的鏈入鏈表中，同時后移鏈表工作指針。該問題要求結(jié)果鏈表按元素值遞減次序排列。故在合并的同時，將鏈表結(jié)點逆置。LinkedList Union(LinkedList la,lb) la,lb分別是帶頭結(jié)點的兩個單鏈表的頭指針，鏈表中的元素值按遞增序排列，本算法將兩鏈表合并成一個按元素值遞減次序排列的單鏈表。 pa=la->next; pb=lb->next;pa，pb分別是鏈表la和lb的工作指針 la->next=null; la作

23、結(jié)果鏈表的頭指針，先將結(jié)果鏈表初始化為空。 while(pa!=null && pb!=null) 當兩鏈表均不為空時作 if(pa->data<=pb->data) r=pa->next; 將pa 的后繼結(jié)點暫存于r。 pa->next=la->next; 將pa結(jié)點鏈于結(jié)果表中，同時逆置。la->next=pa;pa=r; 恢復(fù)pa為當前待比較結(jié)點。 elser=pb->next; 將pb 的后繼結(jié)點暫存于r。pb->next=la->next; 將pb結(jié)點鏈于結(jié)果表中，同時逆置。la->next=pb;pb

24、=r; 恢復(fù)pb為當前待比較結(jié)點。 while(pa!=null) 將la表的剩余部分鏈入結(jié)果表，并逆置。 r=pa->next; pa->next=la->next; la->next=pa; pa=r; while(pb!=null) r=pb->next; pb->next=la->next; la->next=pb; pb=r; 算法Union結(jié)束。算法討論上面兩鏈表均不為空的表達式也可簡寫為while(pa&&pb),兩遞增有序表合并成遞減有序表時，上述算法是邊合并邊逆置。也可先合并完，再作鏈表逆置。后者不如前者優(yōu)化。算

25、法中最后兩個while語句，不可能執(zhí)行兩個，只能二者取一，即哪個表尚未到尾，就將其逆置到結(jié)果表中，即將剩余結(jié)點依次前插入到結(jié)果表的頭結(jié)點后面。 與本題類似的其它題解答如下：（）問題分析與上題類似，不同之處在于：一是鏈表無頭結(jié)點，為處理方便，給加上頭結(jié)點，處理結(jié)束再刪除之；二是數(shù)據(jù)相同的結(jié)點，不合并到結(jié)果鏈表中；三是hb鏈表不能被破壞，即將hb的結(jié)點合并到結(jié)果鏈表時，要生成新結(jié)點。LinkedList Union(LinkedList ha, hb) ha和hb是兩個無頭結(jié)點的數(shù)據(jù)域值遞增有序的單鏈表，本算法將hb中并不出現(xiàn)在ha中的數(shù)據(jù)合并到ha中，合并中不能破壞hb鏈表。LinkedList

26、 la; la=(LinkedList)malloc(sizeof(LNode); la->next=ha;申請頭結(jié)點，以便操作。 pa=ha; pa是ha鏈表的工作指針pb=hb; pb是hb鏈表的工作指針pre=la; pre指向當前待合并結(jié)點的前驅(qū)。while(pa&&pb) if(pa->data<pb->data)處理ha中數(shù)據(jù) pre->next=pa;pre=pa;pa=pa->next; else if(pa->data>pb->data)處理hb中數(shù)據(jù)。 r=(LinkedList)malloc(sizeo

27、f(LNode);申請空間 r->data=pb->data; pre->next=r;pre=r;將新結(jié)點鏈入結(jié)果鏈表。 pb=pb->next;hb鏈表中工作指針后移。 else處理pa->data=pb->data; pre->next=pa; pre=pa; pa=pa->next;兩結(jié)點數(shù)據(jù)相等時，只將ha的數(shù)據(jù)鏈入。 pb=pb->next;不要hb的相等數(shù)據(jù) if(pa!=null)pre->next=pa;將兩鏈表中剩余部分鏈入結(jié)果鏈表。else pre->next=pb;free(la);釋放頭結(jié)點.ha,hb

28、指針未被破壞。算法nion結(jié)束。 (2)本題與上面兩題類似，要求結(jié)果指針為lc，其核心語句段如下： pa=la->next;pb=hb->next; lc=(LinkedList )malloc(sizeof(LNode); pc=lc;pc是結(jié)果鏈表中當前結(jié)點的前驅(qū) while(pa&&pb) if(pa->data<pb->data) pc->next=pa;pc=pa;pa=pa->next; else pc->next=pb;pc=pb;pb=pb->next; if(pa)pc->next=pa; else

29、pc->next=pb; free(la);free(lb);釋放原來兩鏈表的頭結(jié)點。 算法時間復(fù)雜度為O（m+n），其中m和n分別為鏈表la和lb的長度。 2題目分析本組題有6個，本質(zhì)上都是鏈表的合并操作，合并中有各種條件。與前組題不同的是，敘述上是用線性表代表集合，而操作則是求集合的并、交、差（AB，AB，A-B）等。本題與上面1（2）基本相同，不同之處1（2）中鏈表是“非遞減有序”，（可能包含相等元素），本題是元素“遞增有序”（不準有相同元素）。因此兩表中合并時，如有元素值相等元素，則應(yīng)刪掉一個。 LinkedList Union(LinkedList ha,hb) 線性表A和B代

30、表兩個集合，以鏈式存儲結(jié)構(gòu)存儲，元素遞增有序。ha和hb分別是其鏈表的頭指針。本算法求A和B的并集AB，仍用線性表表示，結(jié)果鏈表元素也是遞增有序。 pa=ha->next;pb=hb->next;設(shè)工作指針pa和pb。 pc=ha;pc為結(jié)果鏈表當前結(jié)點的前驅(qū)指針。 while(pa&&pb) if(pa->data<pb->data) pc->next=pa;pc=pa;pa=pa->next; else if(pa->data>pb->data) pc->next=pb;pc=pb;pb=pb->nex

31、t; else處理pa->data=pb->data. pc->next=pa;pc=pa;pa=pa->next; u=pb;pb=pb->next;free(u); if(pa) pc->next=pa; 若ha表未空，則鏈入結(jié)果表。 else pc->next=pb;若hb表未空，則鏈入結(jié)果表。 free(hb); 釋放hb頭結(jié)點 return(ha); 算法Union結(jié)束。 與本題類似的其它幾個題解答如下：(1) 解答完全同上2。(2) 本題是求交集，即只有同時出現(xiàn)在兩集合中的元素才出現(xiàn)在結(jié)果表中。其核心語句段如下：pa=la->next

32、;pb=lb->next;設(shè)工作指針pa和pb；pc=la;結(jié)果表中當前合并結(jié)點的前驅(qū)的指針。while(pa&&pb) if(pa->data=pb->data)交集并入結(jié)果表中。 pc->next=pa;pc=pa;pa=pa->next; u=pb;pb=pb->next;free(u); else if(pa->data<pb->data) u=pa;pa=pa->next;free(u);else u=pb; pb=pb->next; free(u);while(pa) u=pa; pa=pa->

33、next; free(u); 釋放結(jié)點空間while(pb) u=pb; pb=pb->next; free(u);釋放結(jié)點空間pc->next=null;置鏈表尾標記。free(lb); 注： 本算法中也可對B表不作釋放空間的處理（3）本題基本與（2）相同，但要求無重復(fù)元素，故在算法中，待合并結(jié)點數(shù)據(jù)要與其前驅(qū)比較，只有在與前驅(qū)數(shù)據(jù)不同時才并入鏈表。其核心語句段如下。 pa=L1->next;pb=L2->next;pa、pb是兩鏈表的工作指針。 pc=L1;L1作結(jié)果鏈表的頭指針。 while(pa&&pb) if(pa->data<pb

34、->data) u=pa;pa=pa->next;free(u);刪除L1表多余元素 else if (pa->data>pb->data) pb=pb->next; pb指針后移 else 處理交集元素if(pc=L1) pc->next=pa;pc=pa;pa=pa->next; 處理第一個相等的元素。 else if(pc->data=pa->data) u=pa;pa=pa->next;free(u); 重復(fù)元素不進入L1表。 else pc->next=pa;pc=pa;pa=pa->next; 交集元素并

35、入結(jié)果表。 while while(pa) u=pa;pa=pa->next;free(u); 刪L1表剩余元素 pc->next=null; 置結(jié)果鏈表尾。注： 本算法中對L2表未作釋放空間的處理。（4） 本題與上面（3）算法相同，只是結(jié)果表要另辟空間。（5） 題目分析本題首先求B和C的交集，即求B和C中共有元素，再與A求并集，同時刪除重復(fù)元素，以保持結(jié)果A遞增。LinkedList union(LinkedList A,B,C)A,B和C均是帶頭結(jié)點的遞增有序的單鏈表，本算法實現(xiàn)A= A（BC），使求解結(jié)構(gòu)保持遞增有序。pa=A->next;pb=B->next;p

36、c=C->next;設(shè)置三個工作指針。 pre=A; pre指向結(jié)果鏈表中當前待合并結(jié)點的前驅(qū)。 if(pa->data<pb->data|pa->data<pc->data)A中第一個元素為結(jié)果表的第一元素。 pre->next=pa;pre=pa;pa=pa->next;elsewhile(pb&&pc) 找B表和C表中第一個公共元素。 if(pb->data<pc->data)pb=pb->next; else if(pb->data>pc->data)pc=pc->ne

37、xt; else break; 找到B表和C表的共同元素就退出while循環(huán)。 if(pb&&pc) 因共同元素而非B表或C表空而退出上面while循環(huán)。 if(pa->data>pb->data)A表當前元素值大于B表和C表的公共元素，先將B表元素鏈入。 pre->next=pb;pre=pb;pb=pb->next;pc=pc->next; B，C公共元素為結(jié)果表第一元素。 結(jié)束了結(jié)果表中第一元素的確定while(pa&&pb&&pc) while(pb&&pc) if(pb->dat

38、a<pc->data) pb=pb->next; else if(pb->data>pc->data) pc=pc->next; else break; B表和C表有公共元素。 if(pb&&pc) while(pa&&pa->data<pb->data) 先將A中小于B，C公共元素部分鏈入。 pre->next=pa;pre=pa;pa=pa->next; if(pre->data!=pb->data)pre->next=pb;pre=pb;pb=pb->next;

39、pc=pc->next; elsepb=pb->next;pc=pc->next; 若A中已有B，C公共元素，則不再存入結(jié)果表。 while(pa&&pb&&pc) if(pa) pre->next=pa; 當B，C無公共元素（即一個表已空），將A中剩余鏈入。算法Union結(jié)束 算法討論本算法先找結(jié)果鏈表的第一個元素，這是因為題目要求結(jié)果表要遞增有序（即刪除重復(fù)元素）。這就要求當前待合并到結(jié)果表的元素要與其前驅(qū)比較。由于初始pre=A（頭結(jié)點的頭指針），這時的data域無意義，不能與后繼比較元素大小，因此就需要確定第一個元素。當然，不要這

40、樣作，而直接進入下面循環(huán)也可以，但在鏈入結(jié)點時，必須先判斷pre是否等于A，這占用了過多的時間。因此先將第一結(jié)點鏈入是可取的。 算法中的第二個問題是要求時間復(fù)雜度為O（|A|+|B|+|C|）。這就要求各個表的工作指針只能后移（即不能每次都從頭指針開始查找）。本算法滿足這一要求。 最后一個問題是，當B，C有一表為空（即B和C已無公共元素時），要將A的剩余部分鏈入結(jié)果表。 3題目分析循環(huán)單鏈表L1和L2數(shù)據(jù)結(jié)點個數(shù)分別為m和n ，將二者合成一個循環(huán)單鏈表時，需要將一個循環(huán)鏈表的結(jié)點（從第一元素結(jié)點到最后一個結(jié)點）插入到另一循環(huán)鏈表的第一元素結(jié)點前即可。題目要求“用最快速度將兩表合并“，因此應(yīng)找結(jié)

41、點個數(shù)少的鏈表查其尾結(jié)點。 LinkedList Union(LinkedList L1,L2;int m,n) L1和L2分別是兩循環(huán)單鏈表的頭結(jié)點的指針，m和n分別是L1和L2的長度。本算法用最快速度將L1和L2合并成一個循環(huán)單鏈表。if(m<0|n<0) printf(“表長輸入錯誤n”)；exit(0); if(m<n) 若m<n，則查L1循環(huán)單鏈表的最后一個結(jié)點。 if(m=0)return(L2);L1為空表。 elsep=L1; while(p->next!=L1) p=p->next;查最后一個元素結(jié)點。 p->next=L2->

42、next;將L1循環(huán)單鏈表的元素結(jié)點插入到L2的第一元素結(jié)點前。 L2->next=L1->next; free(L1);釋放無用頭結(jié)點。 處理完m<n情況else 下面處理L2長度小于等于L1的情況 if(n=0)return(L1);L2為空表。 elsep=L2; while(p->next!=L2) p=p->next;查最后元素結(jié)點。 p->next=L1->next;將L2的元素結(jié)點插入到L1循環(huán)單鏈表的第一元素結(jié)點前。 L1->next=L2->next; free(L2);釋放無用頭結(jié)點。算法結(jié)束。類似本題敘述的其它題解答如

43、下：（1）題目分析本題將線性表la和lb連接，要求時間復(fù)雜度為O（1），且占用輔助空間盡量小。應(yīng)該使用只設(shè)尾指針的單循環(huán)鏈表。 LinkedList Union(LinkedList la,lb) la和lb是兩個無頭結(jié)點的循環(huán)單鏈表的尾指針，本算法將lb接在la后，成為一個單循環(huán)鏈表。 q=la->next; q指向la的第一個元素結(jié)點。 la->next=lb->next; 將lb的最后元素結(jié)點接到lb的第一元素。 lb->next=q; 將lb指向la的第一元素結(jié)點，實現(xiàn)了lb接在la后。 return(lb); 返回結(jié)果單循環(huán)鏈表的尾指針lb。 算法結(jié)束。 算法

44、討論若循環(huán)單鏈表帶有頭結(jié)點，則相應(yīng)算法片段如下： q=lb->next; q指向lb的頭結(jié)點； lb->next=la->next; lb的后繼結(jié)點為la的頭結(jié)點。 la->next=q->next; la的后繼結(jié)點為lb的第一元素結(jié)點。 free(q); 釋放lb的頭結(jié)點 return(lb); 返回結(jié)果單循環(huán)鏈表的尾指針lb。（2）題目分析本題要求將單向鏈表ha和單向循環(huán)鏈表hb合并成一個單向鏈表，要求算法所需時間與鏈表長度無關(guān)，只有使用帶尾指針的循環(huán)單鏈表，這樣最容易找到鏈表的首、尾結(jié)點，將該結(jié)點序列插入到單向鏈表第一元素之前即可。 其核心算法片段如下（設(shè)兩

45、鏈表均有頭結(jié)點） q=hb->next; 單向循環(huán)鏈表的表頭指針 hb->next=ha->next; 將循環(huán)單鏈表最后元素結(jié)點接在ha第一元素前。 ha->next=q->next; 將指向原單鏈表第一元素的指針指向循環(huán)單鏈表第一結(jié)點 free(q); 釋放循環(huán)鏈表頭結(jié)點。 若兩鏈表均不帶頭結(jié)點，則算法片段如下： q=hb->next; q指向hb首元結(jié)點。 hb->next=ha; hb尾結(jié)點的后繼是ha第一元素結(jié)點。 ha=q; 頭指針指向hb的首元結(jié)點。 4題目分析順序存儲結(jié)構(gòu)的線性表的插入，其時間復(fù)雜度為O（n），平均移動近一半的元素。線性表

46、LA和LB合并時，若從第一個元素開始，一定會造成元素后移，這不符合本題“高效算法”的要求。另外，題中敘述“線性表空間足夠大”也暗示出另外合并方式，即應(yīng)從線性表的最后一個元素開始比較，大者放到最終位置上。設(shè)兩線性表的長度各為m和n ，則結(jié)果表的最后一個元素應(yīng)在m+n位置上。這樣從后向前，直到第一個元素為止。PROC Union(VAR LA:SeqList;LB:SeqList)LA和LB是順序存儲的非遞減有序線性表，本算法將LB合并到LA中，元素仍非遞減有序。 m:=LA.last;n:=LB.last;m，n分別為線性表LA和LB的長度。 k:=m+n; k為結(jié)果線性表的工作指針（下標）。

47、i:=m;j:=n; i，j分別為線性表LA和LB的工作指針（下標）。 WHILE(i>0)AND(j>0)DO IF LA.elemi>=LB.elemj THENLA.elemk:=LA.elemi;k:=k-1;i:=i-1; ELSELA.elemk:=LB.elemj;k:=k-1;j:=j-1; WHILE(j>0) DO LA.elemk:=LB.elemj;k:=k-1;j:=j-1; LA.last:=m+n; ENDP; 算法討論算法中數(shù)據(jù)移動是主要操作。在最佳情況下（LB的最小元素大于LA的最大元素），僅將LB的n個元素移（拷貝）到LA中，時間復(fù)雜

48、度為O（n），最差情況，LA的所有元素都要移動，時間復(fù)雜度為O（m+n）。因數(shù)據(jù)合并到LA中，所以在退出第一個WHILE循環(huán)后，只需要一個WHILE循環(huán)，處理LB中剩余元素。第二個循環(huán)只有在LB有剩余元素時才執(zhí)行，而在LA有剩余元素時不執(zhí)行。本算法利用了題目中“線性表空間足夠大”的條件，“最大限度的避免移動元素”，是“一種高效算法”。 5題目分析本題實質(zhì)上是一個排序問題，要求“不得使用除該鏈表結(jié)點以外的任何鏈結(jié)點空間”。鏈表上的排序采用直接插入排序比較方便，即首先假定第一個結(jié)點有序，然后，從第二個結(jié)點開始，依次插入到前面有序鏈表中，最終達到整個鏈表有序。 LinkedList LinkList

49、Sort(LinkedList list) list是不帶頭結(jié)點的線性鏈表，鏈表結(jié)點構(gòu)造為data和link兩個域，data是數(shù)據(jù)域，link是指針域。本算法將該鏈表按結(jié)點數(shù)據(jù)域的值的大小，從小到大重新鏈接。 p=list->link; p是工作指針，指向待排序的當前元素。 list->link=null;假定第一個元素有序，即鏈表中現(xiàn)只有一個結(jié)點。 while(p!=null) r=p->link; r是p的后繼。 q=list; if(q->data>p->data)處理待排序結(jié)點p比第一個元素結(jié)點小的情況。 p->link=list; list=

50、p;鏈表指針指向最小元素。 else查找元素值最小的結(jié)點。 while(q->link!=null&&q->link->data<p->data)q=q->link; p->link=q->link;將當前排序結(jié)點鏈入有序鏈表中。 q->link=p; p=r;p指向下個待排序結(jié)點。 算法討論算法時間復(fù)雜度的分析與用順序存儲結(jié)構(gòu)時的情況相同。但順序存儲結(jié)構(gòu)將第i(i>1)個元素插入到前面第1至第i-1個元素的有序表時，是將第i個元素先與第i-1個元素比較。而在鏈表最佳情況均是和第一元素比較。兩種存儲結(jié)構(gòu)下最佳和最差情況

51、的比較次數(shù)相同，在鏈表情況下，不移動元素，而是修改結(jié)點指針。 另一說明是，本題中線性鏈表list不帶頭結(jié)點，而且要求“不得使用除該鏈表以外的任何鏈結(jié)點空間“，所以處理復(fù)雜，需要考慮當前結(jié)點元素值比有序鏈表第一結(jié)點的元素值還小的情況，這時要修改鏈表指針list。如果list是頭結(jié)點的指針，則相應(yīng)處理要簡單些，其算法片段如下： p=list->link;p指向第一元素結(jié)點。 list->link=null;有序鏈表初始化為空 while(p!=null) r=p->link;保存后繼 q=list; while(q->link!=null && q->link->data<p->data)q=q->link; p->link=q->link; q->link=p;q=r; 6題目分析本題明確指出單鏈表帶頭結(jié)點，其結(jié)點數(shù)據(jù)是正整數(shù)且不相同，要求利用直接插入原則把鏈表整理成遞增有序鏈表。這就要求從第二結(jié)點開釋，將各結(jié)點依次插入到有序鏈表中。LinkedList LinkListInsertSort(