(高等教育)數(shù)據(jù)結(jié)構(gòu)各章習(xí)題答案

第1章 緒論一、選擇題 1.B2.C3.1C3.2B4.B5.D6.C7.C8.D9.D10.A11.C12.D13.D14.A15.C16.A17.C二、判斷題1. 2. 3.4.5. 6. 7. 8. 9.10.11.12. 13. 三填空題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+1)/2。101+（1+2+（1+2+3）+（1+2+n）=n(n+1)(n+2)/6 O(n3) 16. (1)1 (2)1 (3)f(m,n-1) (4)n 9 17. n(n-1)/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)酱鎯Γ?，但由于其運(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ù)。10D是數(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ù)組中。因一般無增刪操作，故宜采用順序存儲。 typedef struct int num;/學(xué)號 char name8;/姓名 float score;/平均成績 node； node student100;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ù)雜度為O（n）；而在鏈?zhǔn)酱鎯Ψ绞较拢迦牒蛣h除時間復(fù)雜度都是O（1）。17對算法A1和A2的時間復(fù)雜度T1和T2取對數(shù)，得nlog2和2logn。顯然，算法A2好于A1。18. struct node int year,month,day; ; typedef struct int num;/帳號 char name8;/姓名 struct node date;/開戶年月日 int tag;/儲蓄類型，如：0- 零存，1- 一年定期 float put;/存入累加數(shù)； float interest;/利息 float total;/帳面總數(shù) count；19(1)n (2)n+1 (3)n (4)(n+4)(n-1)/2 (5)(n+2)(n-1)/2 (6)n-1 這是一個遞歸調(diào)用，因k的初值為1，由語句（6）知，每次調(diào)用k增1，故第(1)語句執(zhí)行n次。（2）是FOR循環(huán)語句，在滿足(1)的條件下執(zhí)行，該語句進(jìn)入循環(huán)體(3)n次，加上最后一次判斷出界，故執(zhí)行了n+1次。(4)也是循環(huán)語句，當(dāng)k=1時判斷n+1次（進(jìn)入循環(huán)體(5)n次），k=2時判斷n次，最后一次k=n-1時判斷3次，故執(zhí)行次數(shù)是（n+1）+n+3=(n+4)(n-1)/2次。語句(5)是(4)的循環(huán)體，每次比(4)少一次判斷，故執(zhí)行次數(shù)是n+(n-1)+2=(n+2)(n-1)/2次。注意分析時，不要把(2)分析成n次，更不是1次。204 （這時i=4， s=100） REPEAT語句先執(zhí)行循環(huán)體，后判斷條件，直到條件為真時退出循環(huán)。21算法在最好情況下，即二進(jìn)制數(shù)的最后一位為零時，只作一次判斷，未執(zhí)行循環(huán)體，賦值語句Ai執(zhí)行了一次；最壞情況出現(xiàn)在二進(jìn)制數(shù)各位均為1（最高位為零，因題目假設(shè)無溢出），這時循環(huán)體執(zhí)行了n-1次，時間復(fù)雜度是O(n)，循環(huán)體平均執(zhí)行n/2次，時間復(fù)雜度仍是O(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ù)雜度是O(n)。23第一層FOR循環(huán)判斷n+1次，往下執(zhí)行n次，第二層FOR執(zhí)行次數(shù)為(n+(n-1)+(n-2)+1)，第三層循環(huán)體受第一層循環(huán)和第二層循環(huán)的控制，其執(zhí)行次數(shù)如下表： i= 1 2 3 n j=n n n n n j=n-1 n-1 n-1 n-1 j=3 3 3j=2 2 2j=1 1執(zhí)行次數(shù)為(1+2+n)+(2+3+n)+n=n*n(n+1)/2-n(n2-1)/6。在n=5時，f(5)=55，執(zhí)行過程中，輸出結(jié)果為：sum=15,sum=29,sum=41,sum=50,sum=55（每個sum= 占一行,為節(jié)省篇幅，這里省去換行）。24O(n2),m的值等于賦值語句m:=m+1的運(yùn)行次數(shù)，其計(jì)算式為25(1)O(1) (2)O(n2) (3)O(n3) 26(1)O(n) (2)O(n2)27.（1）由斐波那契數(shù)列的定義可得：Fn=Fn-1+Fn-2 =2Fn-2+Fn-3 =3Fn-3+2Fn-4 =5Fn-4+3Fn-5 =8Fn-5+5Fn-6 =pF1+qF0設(shè)Fm的執(zhí)行次數(shù)為Bm(m=0、1、2、n-1)，由以上等式可知，F(xiàn)n-1被執(zhí)行一次，即Bn-1=1；Fn-2被執(zhí)行兩次，即Bn-2=2；直至F1被執(zhí)行p次、F0被執(zhí)行q次，即B1=p，B0=q。Bm的執(zhí)行次數(shù)為前兩等式第一因式系數(shù)之和，即Bm=Bm-1+Bm-2，再有Bn-1=1和Bn-2=2，這也是一個斐波那契數(shù)列?？梢越獾茫築m=()n-m+2-()n-m+2 (m=0,1,2,n-1)（2）時間復(fù)雜度為O(n)28從小到大排列為：logn, n1/2+logn, n, nlogn, n2+logn，n3, n-n3+7n5, 2n/2, (3/2)n, n!, 第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é)點(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)酱鎯?。三填空題1順序 2（n-1）/2 3py-next=px-next; px-next=py4 n-i+15主要是使插入和刪除等操作統(tǒng)一，在第一個元素之前插入元素和刪除第一個結(jié)點(diǎn)不必另作判斷。另外，不論鏈表是否為空，鏈表指針不變。6O(1)，O(n) 7單鏈表，多重鏈表，（動態(tài)）鏈表，靜態(tài)鏈表8f-next=p-next; f-prior=p; p-next-prior=f; p-next=f;9p.prior s.prior.next10 指針 11物理上相鄰 指針 124 213從任一結(jié)點(diǎn)出發(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 return(true);(2) pbNIL AND pa.data=pb.data(3) return(inclusion(pa,pb);(4) pb:=pb.next;(5) return(false);非遞歸算法：(1)pre:=pb; (2) paNIL AND pbNIL 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(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，否則，返回false。20AVAR head:ptr B. new(p) C. p.data:=k D. q.next:=p E. q:=p(帶頭結(jié)點(diǎn))21（1）new(h);生成頭結(jié)點(diǎn)，以便于操作。 （2）r.next:=p; (3) r.next:=q; (4) IF (q=NIL) THEN r.next:=p;22A: r.link.datamax AND q.link.datamaxB: 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)ji-1 (4)p.next (5)i1 24.(1)head.left:=s head的前驅(qū)指針指向插入結(jié)點(diǎn)(2)j:=1;(3)p:=p.right 工作指針后移(4)s.left:=p(5)p.right.left:=s; p后繼的前驅(qū)是s(6)s.left:=p;25.(1)ipre-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(1)a.key:=a的頭結(jié)點(diǎn)用作監(jiān)視哨，取不同于a鏈表中其它數(shù)據(jù)域的值 (2)b.key:=p.keyb的頭結(jié)點(diǎn)起監(jiān)視哨作用 (3)p:=p.next找到a,b表中共同字母，a表指針后移 (4)0(m*n)30. C 部分：(1)p!=null 鏈表未到尾就一直作(2)q 將當(dāng)前結(jié)點(diǎn)作為頭結(jié)點(diǎn)后的第一元素結(jié)點(diǎn)插入31. (1)L=L-next; 暫存后繼 (2)q=L; 待逆置結(jié)點(diǎn) (3)L=p; 頭指針仍為L32. (1) p.nextp0 (2)r:= p.next (3) p.next:= q0; (4) q0:= p; (5) p:=r33. (1)r (2)NIL (3)xhead.data (4)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，即本項(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(1)q:=p; q是工作指針p的前驅(qū)(2)p.datam p是工作指針(3)r:=q; r 記最大值的前驅(qū)，(4)q:=p; 或q:=q.next;(5)r.next:=q.next; 或r.next:=r.next.next 刪最大值結(jié)點(diǎn)36(1)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-element=B-element 兩表中相等元素不作結(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ù)雜度為O（1）。 （2）選順序存儲結(jié)構(gòu)。順序表可以隨機(jī)存取，時間復(fù)雜度為O（1）。 2鏈?zhǔn)酱鎯Y(jié)構(gòu)一般說克服了順序存儲結(jié)構(gòu)的三個弱點(diǎn)。首先，插入、刪除不需移動元素，只修改指針，時間復(fù)雜度為O(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線性表 棧 隊(duì)列 串 順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。 順序存儲結(jié)構(gòu)的定義是： CONST maxlen=線性表可能達(dá)到的最大長度； TYPE sqlisttp=RECORD elem:ARRAY1.maxlen OF ElemType; last:0.maxlen; END; 鏈?zhǔn)酱鎯Y(jié)構(gòu)的定義是： TYPE pointer=nodetype; nodetype=RECORD data:ElemType; next:pointer; END; linklisttp=pointer;5.順序映射時，ai與ai+1的物理位置相鄰；鏈表表示時ai與ai+1的物理位置不要求相鄰。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ù)，且nnext; 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);查找失敗else return(p);查找成功(2) while(p!=null & p-datanext; if(p=null | p-dataX) return(null);查找失敗 else return(p);(3) while(p!=null & p-dataX) p=p-next; if(p=null | p-dataX) return(null); 查找失敗 else return(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.llink- q; p.rlinkpre=p-pre; s-next=p; p-pre-next=s; p-pre=s; 20(A) f1NIL并且f2NIL(B) f1.data f2.data(C) f2.dataf1.data(D) f3.dataf1.data(E) f1prior=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)逆置。LinkedList Union(LinkedList la,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-datadata) 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)。 elser=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)后面。 與本題類似的其它題解答如下：（）問題分析與上題類似，不同之處在于：一是鏈表無頭結(jié)點(diǎn)，為處理方便，給加上頭結(jié)點(diǎn)，處理結(jié)束再刪除之；二是數(shù)據(jù)相同的結(jié)點(diǎn)，不合并到結(jié)果鏈表中；三是hb鏈表不能被破壞，即將hb的結(jié)點(diǎn)合并到結(jié)果鏈表時，要生成新結(jié)點(diǎn)。LinkedList Union(LinkedList ha, hb) ha和hb是兩個無頭結(jié)點(diǎn)的數(shù)據(jù)域值遞增有序的單鏈表，本算法將hb中并不出現(xiàn)在ha中的數(shù)據(jù)合并到ha中，合并中不能破壞hb鏈表。LinkedList la; 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-datadata)處理ha中數(shù)據(jù) pre-next=pa;pre=pa;pa=pa-next; else if(pa-datapb-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é)果鏈表。else pre-next=pb;free(la);釋放頭結(jié)點(diǎn).ha,hb指針未被破壞。算法nion結(jié)束。 (2)本題與上面兩題類似，要求結(jié)果指針為lc，其核心語句段如下： pa=la-next;pb=hb-next; lc=(LinkedList )malloc(sizeof(LNode); pc=lc;pc是結(jié)果鏈表中當(dāng)前結(jié)點(diǎn)的前驅(qū) while(pa&pb) if(pa-datadata) pc-next=pa;pc=pa;pa=pa-next; else pc-next=pb;pc=pb;pb=pb-next; if(pa)pc-next=pa; else pc-next=pb; free(la);free(lb);釋放原來兩鏈表的頭結(jié)點(diǎn)。 算法時間復(fù)雜度為O（m+n），其中m和n分別為鏈表la和lb的長度。 2題目分析本組題有6個，本質(zhì)上都是鏈表的合并操作，合并中有各種條件。與前組題不同的是，敘述上是用線性表代表集合，而操作則是求集合的并、交、差（AB，AB，A-B）等。本題與上面1（2）基本相同，不同之處1（2）中鏈表是“非遞減有序”，（可能包含相等元素），本題是元素“遞增有序”（不準(zhǔn)有相同元素）。因此兩表中合并時，如有元素值相等元素，則應(yīng)刪掉一個。 LinkedList Union(LinkedList ha,hb) 線性表A和B代表兩個集合，以鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲，元素遞增有序。ha和hb分別是其鏈表的頭指針。本算法求A和B的并集AB，仍用線性表表示，結(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-datadata) pc-next=pa;pc=pa;pa=pa-next; else if(pa-datapb-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é)果表。 else pc-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); else if(pa-datadata) 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(lb); 注： 本算法中也可對B表不作釋放空間的處理（3）本題基本與（2）相同，但要求無重復(fù)元素，故在算法中，待合并結(jié)點(diǎn)數(shù)據(jù)要與其前驅(qū)比較，只有在與前驅(qū)數(shù)據(jù)不同時才并入鏈表。其核心語句段如下。 pa=L1-next;pb=L2-next;pa、pb是兩鏈表的工作指針。 pc=L1;L1作結(jié)果鏈表的頭指針。 while(pa&pb) if(pa-datadata) u=pa;pa=pa-next;free(u);刪除L1表多余元素 else if (pa-datapb-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ù)元素不進(jìn)入L1表。 else pc-next=pa;pc=pa;pa=pa-next; 交集元素并入結(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é)點(diǎn)的遞增有序的單鏈表，本算法實(shí)現(xiàn)A= A（BC），使求解結(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-datadata|pa-datadata)A中第一個元素為結(jié)果表的第一元素。 pre-next=pa;pre=pa;pa=pa-next;elsewhile(pb&pc) 找B表和C表中第一個公共元素。 if(pb-datadata)pb=pb-next; else if(pb-datapc-data)pc=pc-next; else break; 找到B表和C表的共同元素就退出while循環(huán)。 if(pb&pc) 因共同元素而非B表或C表空而退出上面while循環(huán)。 if(pa-datapb-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-datadata) pb=pb-next; else if(pb-datapc-data) pc=pc-next; else break; B表和C表有公共元素。 if(pb&pc) while(pa&pa-datadata) 先將A中小于B，C公共元素部分鏈入。 pre-next=pa;pre=pa;pa=pa-next; if(pre-data!=pb-data