數(shù)據(jù)結(jié)構(gòu)1800習(xí)題答案

第1章緒論

一、選擇題

1.B2.C3.1C3.2B4.B5.D6.C7.C8.D9.D10.A11.C

12.D13.D14.A15.C16.A17.C

二、刖斷題

1.X2.x3.x4.x5.76.x7.x8.49.x10.x11.X12.A/

13.x

三.填空題

1.數(shù)據(jù)元素數(shù)據(jù)元素間關(guān)系2.集合線性結(jié)構(gòu)樹形結(jié)構(gòu)圖狀結(jié)構(gòu)或

網(wǎng)狀結(jié)構(gòu)。

3.數(shù)據(jù)的組織形式，即數(shù)據(jù)元素之間邏輯關(guān)系的總體。而邏輯關(guān)系是指數(shù)據(jù)元素之間

的關(guān)聯(lián)方式或稱“鄰接關(guān)系”。

4.表示(又稱映像)。5.(1)邏輯特性(2)在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)(3)

數(shù)學(xué)特性。

6.算法的時間復(fù)雜度和空間復(fù)雜度。7.(1)邏輯結(jié)構(gòu)(2)物理結(jié)構(gòu)(3)操作(運(yùn)算)

(4)算法。

8.(1)有窮性(2)確定性(3)可行性。

9.(1)n+1(2)n(3)n(n+3)/2(4)n(n+l)/2?

10.1+(1+2++(1+2+3)+—+(l+2+—+n)=n(n+l)(n+2)/60(n3)

z

11.log2n12.nlog2n13.log2n14.(n+3)(n-2)/215.0(n)

16.①(1)1(2)1(3)f(m,n-1)(4)n②917.n(n-l)/2

四.應(yīng)用題

1.數(shù)據(jù)結(jié)構(gòu)是門研究在非數(shù)值計(jì)算的程序設(shè)計(jì)問題中，計(jì)算機(jī)的操作對象及對象間

的關(guān)系和施加于對象的操作等的學(xué)科。

2.四種表示方法

(1)順序存儲方式。數(shù)據(jù)元素順序存放，每個存儲結(jié)點(diǎn)只含?個元素。存儲位置反映數(shù)

據(jù)元素間的邏輯關(guān)系。存儲密度大，但有些操作(如插入、刪除)效率較差。

(2)鏈?zhǔn)酱鎯Ψ绞健Ｃ總€存儲結(jié)點(diǎn)除包含數(shù)據(jù)元素信息外還包含一組(至少?個)指針。

指針反映數(shù)據(jù)元素間的邏輯關(guān)系。這種方式不要求存儲空間連續(xù)，便于動態(tài)操作(如插入、

刪除等)，但存儲空間開銷大(用于指針)，另外不能折半查找等。

(3)索引存儲方式。除數(shù)據(jù)元素存儲在一地址連續(xù)的內(nèi)存空間外，尚需建立一個索引表,

索引表中索引指示存儲結(jié)點(diǎn)的存儲位置(下標(biāo))或存儲區(qū)間端點(diǎn)(下標(biāo))，兼有靜態(tài)和動態(tài)

特性。

(4)散列存儲方式。通過散列函數(shù)和解決沖突的方法，將關(guān)鍵字散列在連續(xù)的有限的地

址空間內(nèi)，并將散列函數(shù)的值解釋成關(guān)鍵字所在元素的存儲地址，這種存儲方式稱為散列存

儲。其特點(diǎn)是存取速度快，只能按關(guān)鍵字隨機(jī)存取，不能順序存取，也不能折半存取。

3.數(shù)據(jù)類型是程序設(shè)計(jì)語言中的一個概念，它是一個值的集合和操作的集合。如C語

言中的整型、實(shí)型、字符型等。整型值的范圍(對具體機(jī)器都應(yīng)有整數(shù)范圍)，其操作有加、

減、乘、除、求余等。實(shí)際上數(shù)據(jù)類型是廠家提供給用戶的已實(shí)現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)。“抽象數(shù)

據(jù)類型(ADT)”指一個數(shù)學(xué)模型及定義在該模型上的一組操作?！俺橄蟆钡囊饬x在于數(shù)據(jù)

類型的數(shù)學(xué)抽象特性。抽象數(shù)據(jù)類型的定義僅取決于它的邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如

何表示和實(shí)現(xiàn)無關(guān)。無論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變就不影響它的外部使

用。抽象數(shù)據(jù)類型和數(shù)據(jù)類型實(shí)質(zhì)上是一個概念。此外，抽象數(shù)據(jù)類型的范圍更廣，它已不

再局限于機(jī)器已定義和實(shí)現(xiàn)的數(shù)據(jù)類型，還包括用戶在設(shè)計(jì)軟件系統(tǒng)時自行定義的數(shù)據(jù)類

型。使用抽象數(shù)據(jù)類型定義的軟件模塊含定義、表示和實(shí)現(xiàn)三部分，封裝在一起，對用戶透

明（提供接口），而不必了解實(shí)現(xiàn)細(xì)節(jié)。抽象數(shù)據(jù)類型的出現(xiàn)使程序設(shè)計(jì)不再是“藝術(shù)”，而

是向“科學(xué)”邁進(jìn)了一步。

4.（1）數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系（即數(shù)據(jù)元素之間的關(guān)聯(lián)方式或

“鄰接關(guān)系”），數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示，包括數(shù)據(jù)元素的表示及其關(guān)

系的表示。數(shù)據(jù)的運(yùn)算是對數(shù)據(jù)定義的一組操作，運(yùn)算是定義在邏輯結(jié)構(gòu)上的，和存儲結(jié)構(gòu)

無關(guān)，而運(yùn)算的實(shí)現(xiàn)則是依賴于存儲結(jié)構(gòu)。

（2）邏輯結(jié)構(gòu)相同但存儲不同，可以是不同的數(shù)據(jù)結(jié)構(gòu)。例如，線性表的邏輯結(jié)構(gòu)屬于

線性結(jié)構(gòu)，采用順序存儲結(jié)構(gòu)為順序表，而采用鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表。

（3）棧和隊(duì)列的邏輯結(jié)構(gòu)相同，其存儲表示也可相同（順序存儲和鏈?zhǔn)酱鎯Γ捎谄?/p>

運(yùn)算集合不同而成為不同的數(shù)據(jù)結(jié)構(gòu)。

（4）數(shù)據(jù)結(jié)構(gòu)的評價非常復(fù)雜，可以考慮兩個方面，一是所選數(shù)據(jù)結(jié)構(gòu)是否準(zhǔn)確、完整

的刻劃了問題的基本特征；二是是否容易實(shí)現(xiàn)（如對數(shù)據(jù)分解是否恰當(dāng)；邏輯結(jié)構(gòu)的選擇是

否適合于運(yùn)算的功能，是否有利于運(yùn)算的實(shí)現(xiàn)；基本運(yùn)算的選擇是否恰當(dāng)。）

5.評價好的算法有四個方面。一是算法的正確性；二是算法的易讀性；三是算法的健

壯性；四是算法的時空效率（運(yùn)行）。

6.（1）見上面題3（2）見上面題4（3）見上面題3

（4）算法的時間復(fù)雜性是算法輸入規(guī)模的函數(shù)。算法的輸入規(guī)模或問題的規(guī)模是作為該

算法輸入的數(shù)據(jù)所含數(shù)據(jù)元素的數(shù)目，或與此數(shù)目有關(guān)的其它參數(shù)。有時考慮算法在最壞情

況下的時間復(fù)雜度或平均時間復(fù)雜度。

（5）算法是對特定問題求解步驟的描述，是指令的有限序列，其中每一條指令表示一個

或多個操作。算法具有五個重要特性：有窮性、確定性、可行性、輸入和輸出。

（6）頻度。在分析算法時間復(fù)雜度時，有時需要估算基本操作的原操作，它是執(zhí)行次數(shù)

最多的一個操作，該操作重復(fù)執(zhí)行的次數(shù)稱為頻度。

7.集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形或網(wǎng)狀結(jié)構(gòu)。8.邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、操作

（運(yùn)算）。

9.通常考慮算法所需要的存儲空間量和算法所需要的時間量。后者又涉及到四方面：

程序運(yùn)行時所需輸入的數(shù)據(jù)總量，對源程序進(jìn)行編譯所需時間，計(jì)算機(jī)執(zhí)行每條指令所需時

間和程序中指令重復(fù)執(zhí)行的次數(shù)。

10.D是數(shù)據(jù)元素的有限集合，S是D上數(shù)據(jù)元素之間關(guān)系的有限集合。

11.“數(shù)據(jù)結(jié)構(gòu)”這一術(shù)語有兩種含義，?是作為一門課程的名稱；二是作為一個科學(xué)

的概念。作為科學(xué)概念，目前尚無公認(rèn)定義，一般認(rèn)為，討論數(shù)據(jù)結(jié)構(gòu)要包括三個方面，-

是數(shù)據(jù)的邏輯結(jié)構(gòu)，二是數(shù)據(jù)的存儲結(jié)構(gòu)，三是對數(shù)據(jù)進(jìn)行的操作（運(yùn)算）。而數(shù)據(jù)類型是

值的集合和操作的集合，可以看作是已實(shí)現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)，后者是前者的一種簡化情況。

12.見上面題2。

13.將學(xué)號、姓名、平均成績看成一個記錄（元素，含三個數(shù)據(jù)項(xiàng)），將100個這樣的

記錄存于數(shù)組中。因一般無增刪操作，故宜采用順序存儲。

typedefstruct

{intnum;〃學(xué)號

charname[8];〃姓名

floatscore;/平均成績

}node；

nodestudent[100];

14.見上面題4(3)。

15.應(yīng)從兩方面進(jìn)行討論：如通訊錄較少變動(如城市私人電話號碼)，主要用于查詢，

以順序存儲較方便，既能順序查找也可隨機(jī)查找；若通訊錄經(jīng)常有增刪操作，用鏈?zhǔn)酱鎯Y(jié)

構(gòu)較為合適，將每個人的情況作為一個元素(即一個結(jié)點(diǎn)存放一個人)，設(shè)姓名作關(guān)鍵字，

鏈表安排成有序表，這樣可提高查詢速度。

16.線性表中的插入、刪除操作，在順序存儲方式下平均移動近一半的元素，時間復(fù)雜

度為0(n)；而在鏈?zhǔn)酱鎯Ψ绞较?，插入和刪除時間復(fù)雜度都是0(1)。

17.對算法A1和A2的時間復(fù)雜度T1和T2取對數(shù)，得nlog，和21og"。顯然，算法A2

好于A1。

18.structnode

{intyear,month,day;};

typedefstruct

{intnum;〃帳號

charname[8];〃姓名

structnodedate;〃開戶年月日

inttag;〃儲蓄類型,如:0-零存，1-一年定期……

floatput;〃存入累加數(shù)；

floatinterest;〃利息

floattotal;〃帳面總數(shù)

}count；

19.(l)n(2)n+l(3)n(4)(n+4)(n-l)/2(5)(n+2)(n-l)/2(6)n-l

這是一個遞歸調(diào)用，因k的初值為1,由語句(6)知，每次調(diào)用k增1,故第⑴語句

執(zhí)行n次(2)是FOR循環(huán)語句，在滿足(1)的條件下執(zhí)行，該語句進(jìn)入循環(huán)體(3)n次，加

上最后一次判斷出界，故執(zhí)行了n+1次。(4)也是循環(huán)語句，當(dāng)k=l時判斷n+1次(進(jìn)入循

環(huán)體(5)n次，k=2時判斷n次，最后一次k=n-l時判斷3次，故執(zhí)行次數(shù)是(n+1)+n+-

+3=(n+4)(n-1)/2次。語句⑸是⑷的循環(huán)體，每次比⑷少一次判斷，故執(zhí)行次數(shù)是

n+(n-i)+...+2=(n+2)(n-l)/2次?注意分析時，不要把(2)分析成n次，更不是1次。

20.4(這時i=4,s=100)REPEAT語句先執(zhí)行循環(huán)體，后判斷條件，直到條件為真

時退出循環(huán)。

21.算法在最好情況下，即二進(jìn)制數(shù)的最后一位為零時，只作一次判斷，未執(zhí)行循環(huán)體,

賦值語句A[i]執(zhí)行了?次：最壞情況出現(xiàn)在二進(jìn)制數(shù)各位均為1(最高位為零，因題目假設(shè)

無溢出)，這時循環(huán)體執(zhí)行了n-1次，時間復(fù)雜度是0(n),循環(huán)體平均執(zhí)行n/2次，時間復(fù)

雜度仍是0(n)。

22.該算法功能是將原單循環(huán)鏈表分解成兩個單循環(huán)鏈表：其?包括結(jié)點(diǎn)h到結(jié)點(diǎn)g

的前驅(qū)結(jié)點(diǎn)；另一個包括結(jié)點(diǎn)g到結(jié)點(diǎn)h的前驅(qū)結(jié)點(diǎn)。時間復(fù)雜度是0(n)。

23.第一層FOR循環(huán)判斷n+1次，往下執(zhí)行n次，第二層FOR執(zhí)行次數(shù)為

(n+(n-l)+(n-2)+-+l),第三層循環(huán)體受第?層循環(huán)和第二層循環(huán)的控制，其執(zhí)行次數(shù)如下

表：

i=123…n

j=nnnnn

j=n-ln-1n-1n-1

j=333

j=222

j=l1

執(zhí)行次數(shù)為(1+2+…+n)+(2+3+…+n)+…+n=n*n(n+l)/2-n(nJD/6。在n=5時，f(5)=55,執(zhí)

行過程中，輸出結(jié)果為:sum=15,sunr=29,sum=41,sum=50,sum=55(每個sum=占一行，為節(jié)

省篇幅，這里省去換行)。

，，/22

^(n-2z+l)=—

24.0(/),加的值等于賦值語句m:=m+l的運(yùn)行次數(shù)，其計(jì)算式為閆4

25.⑴0⑴(2)0(/)(3)0(一)26.(l)0(n)(2)0(n2)

27.(1)由斐波那契數(shù)列的定義可得：

Fn=Fn-|+Fn-2

=2Fn.2+Fn.3

=3Fn.3+2Fn.4

=5Fn.4+3Fn,5

=8Fn.5+5Fn.6

=pF,+qF0

設(shè)F.的執(zhí)行次數(shù)為B.（m=0、1、2、…、n-1）,由以上等式可知，F(xiàn)-被執(zhí)行一次，即氏,=1；

被執(zhí)行兩次，即B?-2=2；直至Fl被執(zhí)行P次、F。被執(zhí)行q次，即B|=P，B°=q。B?的執(zhí)行次

數(shù)為前兩等式第一因式系數(shù)之和，即B產(chǎn)B-+B?2,再有B“I=1和B.2=2,這也是一個斐波那契

數(shù)列?？梢越獾茫?/p>

在1+行1-V5

2

Bm=T[(2)-*-(2嚴(yán)(m=0,l,2,…，nT)

(2)時間復(fù)雜度為O(n)

28.從小到大排列為：logn,n12+logn,n,nlogn,n2+logn,n3,n-n3+7n\2"2,(3/2)",

第2章線性表

選擇題

1.A2.B3.C4.A5.D6.D7.D8.C9.B10.B,C11.1111.2111.3E

11.4B11.5C12.B13.C14.C15.C16.A17.A18.A19.D20.C21.B

22.D23.C24.B25.B26.A27.D

判斷題

1.X2.V3.4.X5.6.7.8.9.10.11.12.

JXXXXXXXX

13.14.15.16.

XJXV

部分答案解釋如下。

1、頭結(jié)點(diǎn)并不“僅起”標(biāo)識作用，并且使操作統(tǒng)一。另外，頭結(jié)點(diǎn)數(shù)據(jù)域可寫入鏈表長度,

或作監(jiān)視哨。

4.兩種存儲結(jié)構(gòu)各有優(yōu)缺點(diǎn)，應(yīng)根據(jù)實(shí)際情況選用，不能籠統(tǒng)說哪一個好。

7.集合中元素?zé)o邏輯關(guān)系。

9.非空線性表第?個元素?zé)o前驅(qū)，最后?個元素?zé)o后繼。

13.線性表是邏輯結(jié)構(gòu)，可以順序存儲，也可鏈?zhǔn)酱鎯Α?/p>

三.填空題

1.順序2.(n-l)/23.py->next=px->next;px->next=py

4,n-i+1

5.主要是使插入和刪除等操作統(tǒng)一，在第一個元素之前插入兀素和刪除第?個結(jié)點(diǎn)不必

另作判斷。另外，不論鏈表是否為空，鏈表指針不變。

6.0(1),0(n)7.單鏈表，多重鏈表，(動態(tài))鏈表，靜態(tài)鏈表

8.f->next=p->next;f->prior=p;p->next->prior=f;p->next=f;

9.p\priors\prior",next

10.指針I(yè)L物理上相鄰指針12.42

13.從任一結(jié)點(diǎn)出發(fā)都可訪問到鏈表中每一個元素。

14?u=p->next;p->next=u->next;free(u);15.L->next->next==L

16.p->next!=null

17.L->next==L&&L->prior==L18.s->next=p->next;p->next=s;

19.(1)IFpa=NILTHENreturn(true);

(2)pbONILANDpa\data>=pb\data

(3)return(inclusion(pa,pb));

(4)pb:=pb\next;

(5)return(false);

非遞歸算法：

(l)pre:=pb;(2)paONILANDpbONILANDpb\data>=pa\data(3)pa:=pa\next;

pb:=pb->next;

⑷pb:=pre.next;pre:二pb;pa:=pa.next;⑸IFpa=NILTHENreturn(true)ELSE

return(false);

［注］:本題是在鏈表上求模式匹配問題。非遞歸算法中用指針pre指向主串中開始結(jié)點(diǎn)(初

始時為第一元素結(jié)點(diǎn))。若主串與子串對應(yīng)數(shù)據(jù)相等，兩串工作指針pa和pb后移；否則，

主串工作指針從pre的下一結(jié)點(diǎn)開始(這時pre又指向新的開始結(jié)點(diǎn))，子串工作指針從子

串第一元素開始，比較一直繼續(xù)到循環(huán)條件失敗。若pa為空，則匹配成功，返回true,否

則，返回falseo

20.A.VARhead:ptrB.new(p)C.p\data:=kD.next:=pE.q:二p(帶頭

結(jié)點(diǎn))

21.(1)new(h);〃生成頭結(jié)點(diǎn)，以便于操作。

(2)r".next:=p;(3)r\next:=q;(4)IF(q二NIL)THENr\next:=p;

22.A:r.link.dataOmaxANDq.link.dataOmax

B:r:=r.linkC:q\linkD:q二linkE:r\linkF:r\link

G:r:=s(或r:=r\link)H:r:=r*.linkI:q二link:二s二link

23.(l)la(2)0(3)j<i-l(4)pf.next(5)i<l

24.(l)head\left:=s//head的前驅(qū)指針指向插入結(jié)點(diǎn)

(2)j:=l;

(3)p:=p\right〃工作指針后移

(4)s\left:=p

(5)p\right*.left:=s;〃p后繼的前驅(qū)是s

(6)s.left:二p;

25.(1)i<=L.last/7L.last為元素個數(shù)

(2)j:=j+l〃有值不相等的元素

(3)L.elem[j]:=L.elem[i]〃元素前移

(4)L.last:二j〃元素個數(shù)

26.(A)p二link:=q;〃拉上鏈,前驅(qū)指向后繼

(B)p:=q;〃新的前驅(qū)

(C)p二link:二head;〃形成循環(huán)鏈表

(D)j-O;〃計(jì)數(shù)器，記被刪結(jié)點(diǎn)

(E)q:二p，link〃記下被刪結(jié)點(diǎn)

(F)p\link=q\link〃刪除結(jié)點(diǎn)

27.⑴p:=r;〃r指向工作指針s的前驅(qū)，p指向最小值的前驅(qū)。

(2)q:=s;〃q指向最小值結(jié)點(diǎn),s是工作指針

(3)s:=s\link〃工作指針后移

(4)head:=head\next;〃第一個結(jié)點(diǎn)值最?。?/p>

⑸p」ink:二q:link;〃跨過被刪結(jié)點(diǎn)(即刪除一結(jié)點(diǎn))

28.(1)寸.key:=x;〃頭結(jié)點(diǎn)1這時起監(jiān)視哨作用

(2)freq:=p\freq〃頭結(jié)點(diǎn)起監(jiān)視哨作用

(3)q->pre->next=q->next;q->next->pre=q->pre;〃先將q結(jié)點(diǎn)從鏈表上摘下

q\next:=p;q\pre:=p\pre;p\pre->next:=q;p\pre:=q;〃結(jié)點(diǎn)q插入

結(jié)點(diǎn)P前

(4)q二freq二0〃鏈表中無值為x的結(jié)點(diǎn)，將新建結(jié)點(diǎn)插入到鏈表最后(頭結(jié)點(diǎn)

29.(l)a二key:二'@'〃"的頭結(jié)點(diǎn)用作監(jiān)視哨，取不同于a鏈表中其它數(shù)據(jù)域的值

(2)b\key:=p\key/7b的頭結(jié)點(diǎn)起監(jiān)視哨作用

(3)p:=p\next〃找到a,b表中共同字母，a表指針后移

(4)0(m*n)

30.C部分：(l)p!=null〃鏈表未到尾就一直作

〃將當(dāng)前結(jié)點(diǎn)作為頭結(jié)點(diǎn)后的第一元素結(jié)點(diǎn)插入

(l)L=L->next;〃暫存后繼

(2)q=L;〃待逆置結(jié)點(diǎn)

(3)L=p;〃頭指針仍為L

(1)p^.nextOpo(2)r:=p(3)p\next:=q0;

(4)qo：=p;(5)p:=r

⑴r(2)NIL(3)x<head\data⑷p二data<x

⑸p:二p二next(6)p\data>=x;⑺r(8)p

(9)r(10)NIL(ll)NIL

(l)pa!=ha〃或pa->exp!=-l

(2)pa->exp==0〃若指數(shù)為0,即本項(xiàng)為常數(shù)項(xiàng)

(3)q->next=pa->next〃刪常數(shù)項(xiàng)

(4)q->next〃取下一元素

(5)=pa-〉coef*pa->exp

(6)一〃指數(shù)項(xiàng)減1

(7)pa〃前驅(qū)后移，或q->next

(8)pa->next〃取下一元素

35.(l)q：=P；〃q是工作指針p的前驅(qū)

(2)p-.data>m〃p是工作指針

⑶r:=q;〃r記最大值的前驅(qū)，

⑷q：=p；〃或q:=q~.next;

(5)r".next:=q.next;〃或r".next:=r.next,next刪最大值結(jié)點(diǎn)

36.(l)L->next-null〃置空鏈表，然后將原鏈表結(jié)點(diǎn)逐個插入到有序表中

(2)p!=null〃當(dāng)鏈表尚未到尾，p為工作指針

(3)q!=null〃查p結(jié)點(diǎn)在鏈表中的插入位置，這時q是工作指針。

(4)p->next=r->next〃將p結(jié)點(diǎn)鏈入鏈表中

(5)r->next=p〃r是q的前驅(qū)，u是下個待插入結(jié)點(diǎn)的指針。

37.程序(a)PASCAL部分(編者略)

程序(b)C部分

(1)(A!=null&&B!=null)〃兩均未空時循環(huán)

(2)A->e1ement—B->e1ement〃兩表中相等元素不作結(jié)果元素

(3)B=B->link〃向后移動B表指針

(4)A!=null〃將A表剩余部分放入結(jié)果表中

(5)last->link=null〃置鏈表尾

四、應(yīng)用題

1.(1)選鏈?zhǔn)酱鎯Y(jié)構(gòu)。它可動態(tài)申請內(nèi)存空間，不受表長度(即表中元素個數(shù))的

影響，插入、刪

除時間復(fù)雜度為0(1)?

(2)選順序存儲結(jié)構(gòu)。順序表可以隨機(jī)存取，時間復(fù)雜度為0(l)o

2.鏈?zhǔn)酱鎯Y(jié)構(gòu)一般說克服了順序存儲結(jié)構(gòu)的三個弱點(diǎn)。首先，插入、刪除不需移動

元素，只修改指針，時間復(fù)雜度為0(1);其次，不需要預(yù)先分配空間，可根據(jù)需要動態(tài)申

請空間；其三，表容量只受可用內(nèi)存空間的限制。其缺點(diǎn)是因?yàn)橹羔樤黾恿丝臻g開銷，當(dāng)空

間不允許時，就不能克服順序存儲的缺點(diǎn)。

3.采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，它根據(jù)實(shí)際需要申請內(nèi)存空間，而當(dāng)不需要時又可將不用結(jié)點(diǎn)

空間返還給系統(tǒng)。在鏈?zhǔn)酱鎯Y(jié)構(gòu)中插入和刪除操作不需要移動元素。

4.線性表?xiàng)ｊ?duì)列串順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。

順序存儲結(jié)構(gòu)的定義是：

CONSTlnaxlen=線性表可能達(dá)到的最大長度；

TYPEsqlisttp=RECORD

elem:ARRAY[l..maxlen]OFElemType;

last:0..maxlen;

END;

鏈?zhǔn)酱鎯Y(jié)構(gòu)的定義是：

TYPEpointer=fnodetype;

nodetype=RECORD

data:ElemType;

next:pointer;

END;

linklisttp=pointer;

5.順序映射時，ai與ai+1的物理位置相鄰；鏈表表示時af與aw的物理位置不要求相鄰。

6.在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，頭指針指鏈表的指針，若鏈表有頭結(jié)點(diǎn)則是鏈表的頭

結(jié)點(diǎn)的指針，頭指針具有標(biāo)識作用，故常用頭指針冠以鏈表的名字。頭結(jié)點(diǎn)是為了操作的統(tǒng)

一、方便而設(shè)立的，放在第一元素結(jié)點(diǎn)之前，其數(shù)據(jù)域一般無意義(當(dāng)然有些情況下也可存

放鏈表的長度、用做監(jiān)視哨等等)，有頭結(jié)點(diǎn)后，對在第一元素結(jié)點(diǎn)前插入結(jié)點(diǎn)和刪除第一

結(jié)點(diǎn)，其操作與對其它結(jié)點(diǎn)的操作統(tǒng)一了。而且無論鏈表是否為空，頭指針均不為空。首元

結(jié)點(diǎn)也就是第一元素結(jié)點(diǎn)，它是頭結(jié)點(diǎn)后邊的第一個結(jié)點(diǎn)。

7.見上題6。

8.(1)將next域變?yōu)閮蓚€域：pre和next,其值域均為0..maxsize。初始化時，頭結(jié)

點(diǎn)(下標(biāo)為0的元素)其next域值為1,其pre域值為n(設(shè)n是元素個數(shù)，且nQiaxsize)

(2)stalist[stalist[p].pre],pre;

(3)stalist[p].next;

9.在單鏈表中不能從當(dāng)前結(jié)點(diǎn)(若當(dāng)前結(jié)點(diǎn)不是第一結(jié)點(diǎn))出發(fā)訪問到任何一個結(jié)點(diǎn)，

鏈表只能從頭指針開始，訪問到鏈表中每個結(jié)點(diǎn)。在雙鏈表中求前驅(qū)和后繼都容易，從當(dāng)前

結(jié)點(diǎn)向前到第一結(jié)點(diǎn)，向后到最后結(jié)點(diǎn)，可以訪問到任何一個結(jié)點(diǎn)。

10.本題是鏈表的逆置問題。設(shè)該鏈表帶頭結(jié)點(diǎn)，將頭結(jié)點(diǎn)摘下，并將其指針域置空。

然后從第一元素結(jié)點(diǎn)開始，直到最后一個結(jié)點(diǎn)為止，依次前插入頭結(jié)點(diǎn)的后面，則實(shí)現(xiàn)了鏈

表的逆置。

11.該算法的功能是判斷鏈表L是否是非遞減有序，若是則返回“true"；否嵋1"false

pre指向當(dāng)前結(jié)點(diǎn)，p指向pre的后繼。

12.q=p->next;p->next=q->next;free(q);

13.設(shè)單鏈表的頭結(jié)點(diǎn)的頭指針為head,且pre二head；

while(pre->next!=p)pre=pre->next;

s->next=p;pre->next=s;

14.設(shè)單鏈表帶頭結(jié)點(diǎn)，工作指針p初始化為p=H->next;

(1)while(p!=null&&p->data!=X)p=p->next;

if(p==null)return(null)；〃查找失敗

elsereturn(p);〃查找成功

(2)while(p!=null&&p->data<X)p=p->next;

if(p==null|'p->data>X)return(null)；〃查找失敗

elsereturn(p);

(3)while(p!=null&&p->data>X)p=p->next;

if(p==null|p->data<X)return(null);〃查找失敗

elsereturn(p);〃查找成功

15.本程序段功能是將pa和pb鏈表中的值相同的結(jié)點(diǎn)保留在pa鏈表中(pa中與pb中不

同結(jié)點(diǎn)刪除)，pa是結(jié)果鏈表的頭指針。鏈表中結(jié)點(diǎn)值與從前逆序。S1記結(jié)果鏈表中結(jié)點(diǎn)個

數(shù)(即pa與pb中相等的元素個數(shù))。S2記原pa鏈表中刪除的結(jié)點(diǎn)個數(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*.11ink<-q;

p".rlink<-q;

18.mp是一個過程，其內(nèi)嵌套有過程subp。

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é)點(diǎn)形成第二個循環(huán)鏈表。

19.在指針p所指結(jié)點(diǎn)前插入結(jié)點(diǎn)s的語句如下：

s->pre=p->pre;s->next=p;p->pre->next=s;p->pre=s;

20.(A)f1ONIL并且f2〈>NIL

(B)flt.data<f2t.data

(C)f2t.data<f1t.data

(D)f3t.data<f1t.data

(E)fl<-flt,link或f2=f2t.link;

21.1)本算法功能是將雙向循環(huán)鏈表結(jié)點(diǎn)的數(shù)據(jù)域按值自小到大排序，成為非遞減(可

能包括數(shù)據(jù)域值相等的結(jié)點(diǎn))有序雙向循環(huán)鏈表。

2)(l)r->prio廠q-〉prior;〃將q結(jié)點(diǎn)摘下，以便插入到適當(dāng)位置。

(2)p->next->prior=q;//(2)(3)將q結(jié)點(diǎn)插入

(3)p->next=q;

(4)r=r->next;或r=q->next;〃后移指針，再將新結(jié)點(diǎn)插入到適當(dāng)位置。

五、算法設(shè)計(jì)題

1.［題目分析］因?yàn)閮涉湵硪寻丛刂颠f增次序排列，將其合并時，均從第一個結(jié)點(diǎn)起

進(jìn)行比較，將小的鏈入鏈表中，同時后移鏈表工作指針。該問題要求結(jié)果鏈表按元素值遞減

次序排列。故在合并的同時:將鏈表結(jié)點(diǎn)逆置。

LinkedListUnion(LinkedListla,lb)

〃la,lb分別是帶頭結(jié)點(diǎn)的兩個單鏈表的頭指針，鏈表中的元素值按遞增序排列，本算法

將兩鏈表合并成?個按元素值遞減次序排列的單鏈表。

{pa=la->next;pb=lb->next;//pa,pb分別是鏈表la和lb的工作指針

la->next=null;//la作結(jié)果鏈表的頭指針，先將結(jié)果鏈表初始化為

空。

while(pa!=null&&pb!=null)〃當(dāng)兩鏈表均不為空時作

if(pa->data<=pb->data)

{r=pa->next;〃將pa的后繼結(jié)點(diǎn)暫存于r。

pa->next=la->next;〃將pa結(jié)點(diǎn)鏈于結(jié)果表中，同時逆置。

la->next=pa;

pa=r;〃恢復(fù)pa為當(dāng)前待比較結(jié)點(diǎn)。

else

{r=pb->next;//將pb的后繼結(jié)點(diǎn)暫存于r。

pb->next=la->next;〃將pb結(jié)點(diǎn)鏈于結(jié)果表中，同時逆置。

la->next=pb;

pb=r;〃恢復(fù)pb為當(dāng)前待比較結(jié)點(diǎn)。

)

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é)束。

［算法討論］上面兩鏈表均不為空的表達(dá)式也可簡寫為while(pa&&pb),兩遞增有序表

合并成遞減有序表時，上述算法是邊合并邊逆置。也可先合并完，再作鏈表逆置。后者不如

前者優(yōu)化。算法中最后兩個while語句，不可能執(zhí)行兩個，只能二者取-，即哪個表尚未到

尾，就將其逆置到結(jié)果表中，即將剩余結(jié)點(diǎn)依次前插入到結(jié)果表的頭結(jié)點(diǎn)后面。

與本題類似的其它題解答如下：

(1)［問題分析］與上題類似，不同之處在于：一是鏈表無頭結(jié)點(diǎn)，為處理方便，給

加上頭結(jié)點(diǎn)，處理結(jié)束再刪除之；二是數(shù)據(jù)相同的結(jié)點(diǎn)，不合并到結(jié)果鏈表中；三是hb鏈

表不能被破壞，即將hb的結(jié)點(diǎn)合并到結(jié)果鏈表時，要生成新結(jié)點(diǎn)。

LinkedListUnion(LinkedListha,hb)

〃ha和hb是兩個無頭結(jié)點(diǎn)的數(shù)據(jù)域值遞增有序的單鏈表，本算法將hb中并不出現(xiàn)在ha

中的數(shù)據(jù)合并到ha中，合并中不能破壞hb鏈表。

{LinkedListla;

la=(LinkedList)malloc(sizeof(LNode));

la->next=ha;//申請頭結(jié)點(diǎn)，以便操作。

pa二ha;〃pa是ha鏈表的工作指針

pb二hb;〃pb是hb鏈表的工作指針

pre=la;//pre指向當(dāng)前待合并結(jié)點(diǎn)的前驅(qū)。

while(pa&&pb)

if(pa->data<pb->data)〃處理ha中數(shù)據(jù)

{pre->next=pa;pre=pa;pa=pa->next;}

elseif(pa->data>pb->data)〃處理hb中數(shù)據(jù)。

{r=(LinkedList)malloc(sizeof(LNode));//申請空間

r->data=pb->data;pre->next=r;

pre=r;〃將新結(jié)點(diǎn)鏈入結(jié)果鏈表。

pb=pb->next;〃hb鏈表中工作指針后移。

)

else〃處理pa->data=pb->data;

{pre->next=pa;pre=pa;

pa=pa->next;〃兩結(jié)點(diǎn)數(shù)據(jù)相等時，只將ha的數(shù)據(jù)鏈入。

pb=pb->next;〃不要hb的相等數(shù)據(jù)

}

if(pa!=null)pre->next=pa;//將兩鏈表中剩余部分鏈入結(jié)果鏈表。

elsepre->next=pb;

free(la);〃釋放頭結(jié)點(diǎn).ha,hb指針未被破壞。

)〃算法nion結(jié)束。

(2)本題與上面兩題類似，要求結(jié)果指針為1c,其核心語句段如下：

pa=la->next;pb=hb->next;

lc=(LinkedList)malloc(sizeof(LNode));

pc=lc;/7pc是結(jié)果鏈表中當(dāng)前結(jié)點(diǎn)的前驅(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;elsepc->next=pb;

free(la);free(lb);〃釋放原來兩鏈表的頭結(jié)點(diǎn)。

算法時間復(fù)雜度為0(m+n),其中m和n分別為鏈表la和1b的長度。

2.［題目分析］本組題有6個，本質(zhì)上都是鏈表的合并操作，合并中有各種條件。與前

組題不同的是，敘述上是用線性表代表集合，而操作則是求集合的并、交、差(AUB,A

AB,A-B)等。

本題與上面L(2)基本相同，不同之處L(2)中鏈表是“非遞減有序”，(可能包含

相等元素)，本題是元素“遞增有序”(不準(zhǔn)有相同元素)。因此兩表中合并時，如有元素值

相等元素，則應(yīng)刪掉一個。

LinkedListUnion(LinkedListha,hb)

〃線性表A和B代表兩個集合，以鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲，元素遞增有序。ha和hb分別

是其鏈表的頭指針。本算法求A和B的并集AUB,仍用線性表表示，結(jié)果鏈表元

素也是遞增有序。

{pa=ha->next;pb=hb->next;〃設(shè)工作指針pa和pb。

pc二ha;〃pc為結(jié)果鏈表當(dāng)前結(jié)點(diǎn)的前驅(qū)指針。

while(pa&&pb)

if(pa->data<pb->data)

{pc->next=pa;pc=pa;pa=pa->next;}

elseif(pa->data>pb->data)

{pc->next=pb;pc=pb;pb=pb->next;}

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é)果表。

elsepc->next=pb;〃若hb表未空，則鏈入結(jié)果表。

free(hb);〃釋放hb頭結(jié)點(diǎn)

return(ha);

}〃算法Union結(jié)束。

與本題類似的其它幾個題解答如下：

(1)解答完全同上2。

(2)本題是求交集，即只有同時出現(xiàn)在兩集合中的元素才出現(xiàn)在結(jié)果表中。其核心語句

段如下：

pa=la->next;pb=lb->next;〃設(shè)工作指針pa和pb；

pc=la;〃結(jié)果表中當(dāng)前合并結(jié)點(diǎn)的前驅(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);}

elseif(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->next;free(u);}//釋放結(jié)點(diǎn)空間

while(pb){u=pb;pb=pb->next;free(u);}〃釋放結(jié)點(diǎn)空間

pc->next=null;〃置鏈表尾標(biāo)記。

free(1b);〃注：本算法中也可對B表不作釋放空間的處理

(3)本題基本與(2)相同，但要求無重復(fù)元素，故在算法中，待合并結(jié)點(diǎn)數(shù)據(jù)要與其前

驅(qū)比較，只有在與前驅(qū)數(shù)據(jù)不同時才并入鏈表。其核心語句段如下。

pa=Ll->next;pb=L2->next;〃pa、pb是兩鏈表的工作指針。

pc=L1;〃L1作結(jié)果鏈表的頭指針。

while(paft&pb)

if(pa->data<pb->data){u=pa;pa=pa->next;free(u);}〃刪除LI表多余元素

elseif(pa->data>pb->data)pb=pb->next;〃pb指針后移

else〃處理交集元素

{if(pc=二LI){pc->next=pa;pc=pa;pa=pa->next;}//處理第一個相等的元

素。

elseif(pc->data==pa->data){u=pa;pa=pa->next;free(u);}〃重復(fù)元

素不進(jìn)入LI表。

else{pc->next=pa;pc=pa;pa=pa->next;}//交集元素并入結(jié)果表。

}Awhile

while(pa){u=pa;pa=pa->next;free(u);}〃刪LI表剩余元素

pc->next=null;〃置結(jié)果鏈表尾。

注：本算法中對L2表未作釋放空間的處理。

(4)本題與上面(3)算法相同，只是結(jié)果表要另辟空間。

(5)［題目分析］本題首先求B和C的交集，即求B和C中共有元素，再與A求并集，同

時刪除重復(fù)元素，以保持結(jié)果A遞增。

LinkedListunion(LinkedListA,B,C)

〃A,B和C均是帶頭結(jié)點(diǎn)的遞增有序的單鏈表，本算法實(shí)現(xiàn)A二AU(BAC),使求解結(jié)

構(gòu)保持遞增有序。

{pa=A->next;pb=B->next;pc=C->next;//設(shè)置三個工作指針。

pre=A;//pre指向結(jié)果鏈表中當(dāng)前待合并結(jié)點(diǎn)的前驅(qū)。

if(pa->data<pb->data||pa->data<pc->data)〃A中第一個元素為結(jié)果表的第一無

素。

{pre->next=pa;pre=pa;pa=pa->next;}

else{while(pb&&pc)〃找B表和C表中第一個公共元素。

if(pb->data<pc->data)pb=pb->next;

elseif(pb->data>pc->data)pc=pc->next;

elsebreak;〃找到B表和C表的共同元素就退出while循環(huán)。

if(pb&&pc)//因共同元素而非B表或C表空而退出上面while循環(huán)。

if(pa->data>pb->data)〃A表當(dāng)前元素值大于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->data<pc->data)pb=pb->next;

elseif(pb->data>pc->data)pc=pc->next;

elsebreak;〃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;pc=pc->next;}

else{pb=pb->next;pc=pc->next;}//若A中已有B,C公共元素,則不再存

入結(jié)果表。

)

}//while(pa&&pb&&pc)

if(pa)pre->next=pa;〃當(dāng)B,C無公共元素(即一個表已空)，將A中剩余鏈入。

}〃算法Union結(jié)束

［算法討論］本算法先找結(jié)果鏈表的第一個元素，這是因?yàn)轭}目要求結(jié)果表要遞增有序

(即刪除重復(fù)元素)。這就要求當(dāng)前待合并到結(jié)果表的元素要與其前驅(qū)比較。由于初始pre=A

(頭結(jié)點(diǎn)的頭指針)，這時的data域無意義，不能與后繼比較元素大小，因此就需要確定第

一個元素。當(dāng)然，不要這樣作，而直接進(jìn)入下面循環(huán)也可以，但在鏈入結(jié)點(diǎn)時，必須先判斷

pre是否等于A,這占用了過多的時間。因此先將第一結(jié)點(diǎn)鏈入是可取的。

算法中的第二個問題是要求時間復(fù)雜度為0(|A|+|B|+|C|)。這就要求各個表的工作指

針只能后移(即不能每次都從頭指針開始查找)。本算法滿足這一要求。

最后一個問題是，當(dāng)B,C有一表為空(即B和C已無公共元素時)，要將A的剩余部分

鏈入結(jié)果表。

3.［題目分析］循環(huán)單鏈表L1和L2數(shù)據(jù)結(jié)點(diǎn)個數(shù)分別為m和n,將二者合成一個循環(huán)

單鏈表時，需要將一個循環(huán)鏈表的結(jié)點(diǎn)(從第一元素結(jié)點(diǎn)到最后一個結(jié)點(diǎn))插入到另一循環(huán)

鏈表的第一元素結(jié)點(diǎn)前即可。題目要求“用最快速度將兩表合并“，因此應(yīng)找結(jié)點(diǎn)個數(shù)少的

鏈表查其尾結(jié)點(diǎn)。

LinkedListUnion(LinkedListLI,L2;intm,n)

〃L1和L2分別是兩循環(huán)單鏈表的頭結(jié)點(diǎn)的指針，m和n分別是L1和L2的長度。

〃本算法用最快速度將L1和L2合并成一個循環(huán)單鏈表。

{if(m<0||n<0){printf(“表長輸入錯誤\n")；exit(0);)

if(m<n)〃若m<n,則查LI循環(huán)單鏈表的最后一個結(jié)點(diǎn)。

{if(m==0)return(L2);//L1為空表。

else{p=Ll;

while(p->next!=Ll)p=p->next;〃查最后一個元素結(jié)點(diǎn)。

p->next=L2->next;〃將L1循環(huán)單鏈表的元素結(jié)點(diǎn)插入到L2的第?元素結(jié)點(diǎn)

刖。

L2->next=Ll->next;

free(LI);〃釋放無用頭結(jié)點(diǎn)。

}

}〃處理完m<n情況

else//下面處理L2長度小于等于L1的情況

{if(n==0)return(LI);〃L2為空表。

else{p=L2;

while(p->next!=L2)p=p->next;〃查最后元素結(jié)點(diǎn)。

p->next=Ll->next;〃將L2的元素結(jié)點(diǎn)插入到L1循環(huán)單鏈表的第一元素結(jié)

點(diǎn)刖。

Ll->next=L2->next;

free(L2);〃釋放無用頭結(jié)點(diǎn)。

)

}〃算法結(jié)束。

類似本題敘述的其它題解答如下：

(1)［題目分析］本題將線性表la和1b連接，要求時間復(fù)雜度為0(1),且占用輔助空

間盡量小。應(yīng)該使用只設(shè)尾指針的單循環(huán)鏈表。

LinkedListUnion(LinkedListla,lb)

〃la和lb是兩個無頭結(jié)點(diǎn)的循環(huán)單鏈表的尾指針，本算法將1b接在la后，成為-

個單循環(huán)鏈表。

{q=la->next;〃q指向la的第一個元素結(jié)點(diǎn)。

la->next=lb->next;〃將1b的最后元素結(jié)點(diǎn)接到1b的第一元素。

lb->next=q;〃將1b指向la的第一元素結(jié)點(diǎn)，實(shí)現(xiàn)了1b接在la后。

return(1b);〃返回結(jié)果單循環(huán)鏈表的尾指針lb。

}〃算法結(jié)束。

［算法討論］若循環(huán)單鏈表帶有頭結(jié)點(diǎn)，則相應(yīng)算法片段如下：

q=lb->next;〃q指向1b的頭結(jié)點(diǎn)；

lb->next=la->next;/71b的后繼結(jié)點(diǎn)為la的頭結(jié)點(diǎn)。

la->next=q->next;//la的后繼結(jié)點(diǎn)為1b的第一元素結(jié)點(diǎn)。

free(q);〃釋放1b的頭結(jié)點(diǎn)

return(1b);〃返回結(jié)果單循環(huán)鏈表的尾指針1b。

(2)［題目分析］本題要求將單向鏈表ha和單向循環(huán)鏈表hb合并成一個單向鏈表，要求

算法所需時間與鏈表長度無關(guān),只有使用帶尾指針的循環(huán)單鏈表,這樣最容易找到鏈表的首、

尾結(jié)點(diǎn)，將該結(jié)點(diǎn)序列插入到單向鏈表第一元素之前即可。

其核心算法片段如下(設(shè)兩鏈表均有頭結(jié)點(diǎn))

q=hb->next;〃單向循環(huán)鏈表的表頭指針

hb->next=ha->next;〃將循環(huán)單鏈表最后元素結(jié)點(diǎn)接在ha第一元素前。

ha->next=q->next;〃將指向原單鏈表第一元素的指針指向循環(huán)單鏈表第一結(jié)

點(diǎn)

free(q);〃釋放循環(huán)鏈表頭結(jié)點(diǎn)。

若兩鏈表均不帶頭結(jié)點(diǎn)，則算法片段如下：

q=hb->next;//q指向hb首元結(jié)點(diǎn)。

hb->next=ha;〃hb尾結(jié)點(diǎn)的后繼是ha第一元素結(jié)點(diǎn)。

ha=q;〃頭指針指向hb的首元結(jié)點(diǎn)。

4.［題目分析