數(shù)據(jù)結(jié)構(gòu)題集答案(C語言版)(嚴(yán)蔚敏-吳偉民著)

1、第1章緒論1.1簡述以下術(shù)語：數(shù)據(jù)，數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)、數(shù)據(jù)類 型和抽象數(shù)據(jù)類型。解：數(shù)據(jù)是對客觀事物的符號表示。在計算機科學(xué)中是指所有能輸入到計算機中 并被計算機程序處理的符號的總稱。數(shù)據(jù)元素是數(shù)據(jù)的根本單位，在計算機程序中通常作為一個整體進(jìn)行考慮和 處理數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計算機中的表示。數(shù)據(jù)類型是一個值的集合和定義在這個值集上的一組操作的總稱。抽象數(shù)據(jù)類型是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。是對一般數(shù)據(jù)類型的擴(kuò)展。1.2試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型

2、的概念與程序設(shè)計語言中數(shù)據(jù)類型概念的 區(qū)別。解：抽象數(shù)據(jù)類型包含一般數(shù)據(jù)類型的概念，但含義比一般數(shù)據(jù)類型更廣、 更抽象。一般數(shù)據(jù)類型由具體語言系統(tǒng)內(nèi)部定義，直接提供應(yīng)編程者定義用戶數(shù)據(jù)，因此稱它們?yōu)轭A(yù)定義數(shù)據(jù)類型。 抽象數(shù)據(jù)類型通常由編程者定義， 包括定義 它所使用的數(shù)據(jù)和在這些數(shù)據(jù)上所進(jìn)行的操作。 在定義抽象數(shù)據(jù)類型中的數(shù)據(jù)部 分和操作局部時，要求只定義到數(shù)據(jù)的邏輯結(jié)構(gòu)和操作說明，不考慮數(shù)據(jù)的存儲 結(jié)構(gòu)和操作的具體實現(xiàn)，這樣抽象層次更高，更能為其他用戶提供良好的使用接 口。1.3設(shè)有數(shù)據(jù)結(jié)構(gòu)(D,R)，其中，R r，r d1,d2 , d2,d3 , d3,d4試按圖論中圖的畫法慣例畫出其邏

3、輯結(jié)構(gòu)圖。解:1.4試仿照三元組的抽象數(shù)據(jù)類型分別寫出抽象數(shù)據(jù)類型復(fù)數(shù)和有理數(shù)的定義 (有理數(shù)是其分子、分母均為自然數(shù)且分母不為零的分?jǐn)?shù))。解:ADT Complex數(shù)據(jù)對象：D=r.i|r.i 為實數(shù)數(shù)據(jù)關(guān)系：R=<r.i>根本操作：In itComplex(&C,re,im)操作結(jié)果：構(gòu)造一個復(fù)數(shù) C,其實部和虛局部別為re和imDestroyCmoplex(&C)操作結(jié)果：銷毀復(fù)數(shù)CGet(C,k,&e)操作結(jié)果：用 e 返回復(fù)數(shù) C 的第 k 元的值Put(&C,k,e) 操作結(jié)果：改變復(fù)數(shù) C 的第 k 元的值為 eIsAscending(

4、C) 操作結(jié)果：如果復(fù)數(shù) C 的兩個元素按升序排列，那么返回 1，否那么 返回 0IsDescending(C) 操作結(jié)果：如果復(fù)數(shù) C 的兩個元素按降序排列，那么返回 1，否那么 返回 0Max(C,&e) 操作結(jié)果：用 e 返回復(fù)數(shù) C 的兩個元素中值較大的一個Min(C,&e) 操作結(jié)果：用 e 返回復(fù)數(shù) C 的兩個元素中值較小的一個 ADT ComplexADT RationalNumber數(shù)據(jù)對象：D=s,m|s,m為自然數(shù)，且m不為0 數(shù)據(jù)關(guān)系： R=<s,m>根本操作：InitRationalNumber(&R,s,m)操作結(jié)果：構(gòu)造一個有理數(shù)

5、 R,其分子和分母分別為s和mDestroyRationalNumber(&R)操作結(jié)果：銷毀有理數(shù) RGet(R,k,&e) 操作結(jié)果：用 e 返回有理數(shù) R 的第 k 元的值Put(&R,k,e) 操作結(jié)果：改變有理數(shù) R 的第 k 元的值為 eIsAscending(R)操作結(jié)果：假設(shè)有理數(shù)R的兩個元素按升序排列，那么返回1,否那么 返回 0IsDescending(R)操作結(jié)果：假設(shè)有理數(shù)R的兩個元素按降序排列，那么返回1,否那么 返回 0Max(R,&e)操作結(jié)果：用e返回有理數(shù)R的兩個元素中值較大的一個Min(R,&e)操作結(jié)果：用e返回有理

6、數(shù)R的兩個元素中值較小的一個ADT RationalNumber1.5 試畫出與以下程序段等價的框圖。(1) product=1; i=1; while(i<=n) product *= i; i+;(2) i=0;do i+; while(i!=n) && (ai!=x);(3) switch case x<y: z=y-x; break;case x=y: z=abs(x*y); break;default: z=(x-y)/abs(x)*abs(y);1.6 在程序設(shè)計中，常用以下三種不同的出錯處理方式：(1) 用 exit 語句終止執(zhí)行并報告錯誤；(2) 以

7、函數(shù)的返回值區(qū)別正確返回或錯誤返回；(3) 設(shè)置一個整型變量的函數(shù)參數(shù)以區(qū)別正確返回或某種錯誤返回。 試討論這三種方法各自的優(yōu)缺點。解：(1)exit常用于異常錯誤處理，它可以強行中斷程序的執(zhí)行，返回操作 系統(tǒng)。(2) 以函數(shù)的返回值判斷正確與否常用于子程序的測試，便于實現(xiàn)程序的局 部控制。(3) 用整型函數(shù)進(jìn)行錯誤處理的優(yōu)點是可以給出錯誤類型，便于迅速確定錯 誤。1.7 在程序設(shè)計中，可采用以下三種方法實現(xiàn)輸出和輸入：(1) 通過 scanf 和 printf 語句；(2) 通過函數(shù)的參數(shù)顯式傳遞；(3) 通過全局變量隱式傳遞。 試討論這三種方法的優(yōu)缺點。解： (1) 用 scanf 和 p

8、rintf 直接進(jìn)行輸入輸出的好處是形象、 直觀， 但缺點 是需要對其進(jìn)行格式控制， 較為煩瑣，如果出現(xiàn)錯誤， 那么會引起整個系統(tǒng)的崩潰。(2) 通過函數(shù)的參數(shù)傳遞進(jìn)行輸入輸出，便于實現(xiàn)信息的隱蔽，減少出錯的 可能。(3) 通過全局變量的隱式傳遞進(jìn)行輸入輸出最為方便，只需修改變量的值即 可，但過多的全局變量使程序的維護(hù)較為困難。1.8 設(shè) n 為正整數(shù)。試確定以下各程序段中前置以記號 的語句的頻度：(1) i=1; k=0;while(i<=n-1) k += 10*i;i+;(2) i=1; k=0;do k += 10*i;i+; while(i<=n-1);(3) i=1;

9、k=0;while (i<=n-1) i+； k += 10*i; k=0;for(i=1; i<=n; i+) for(j=i; j<=n; j+) k+;(5) for(i=1; i<=n; i+) for(j=1; j<=i; j+) for(k=1; k<=j; k+) x += delta; i=1; j=0;while(i+j <=n) if(i>j) j+;else i+;x=n; y=0;/ n是不小于1的常數(shù)while(x>=(y+1)*(y+1) y+;(8) x=91; y=100; while(y>0) if(

10、x>100) x -= 10; y-; else x+; 解：n-1n-1n-1n(n 1)2(5) 1+(1+2)+(1+2+3)+.+(1+2+3+.+n)=i(i1)2 i(i2 i 11)(i2i)i22i丄 n(n 1)(2n 1)12n(n41)n(n121)(2n 3)(4) n+(n-1)+( n-2)+.+1 =n 向下取整(8) 11001.9假設(shè)n為2的乘幕，并且n>2,試求以下算法的時間復(fù)雜度及變量 count的 值(以 n 的函數(shù)形式表示)。int Time(int n) count = 0;x=2;while(x<n/2) x *= 2; coun

11、t+;return count;解： o(log 2 n)count= log2 n 21.11有實現(xiàn)同一功能的兩個算法，其時間復(fù)雜度分別為0 2n和On10，假 設(shè)現(xiàn)實計算機可連續(xù)運算的時間為 107秒( 1 00多天)，又每秒可執(zhí)行根本操作(根 據(jù)這些操作來估算算法時間復(fù)雜度) 105 次。試問在此條件下，這兩個算法可解 問題的規(guī)模(即n值的范圍)各為多少？哪個算法更適宜？請說明理由。解： 2n 1012n=40n10 1012n=16那么對于同樣的循環(huán)次數(shù)n,在這個規(guī)模下，第二種算法所花費的代價要大得 多。故在這個規(guī)模下，第一種算法更適宜。1.12 設(shè)有以下三個函數(shù)：f n 21n4 n

12、2 1000 ， g n 15n4 500n3 ， h n500 n 3.5 nlog n請判斷以下斷言正確與否：(1) f(n) 是 O(g(n)(2) h(n) 是 O(f(n)(3) g(n) 是 O(h(n)(4) h(n) 是 O(n3.5)(5) h(n) 是 O(nlogn)解：(1)對 (2) 錯 (3) 錯 (4) 對 (5) 錯1.13試設(shè)定假設(shè)干n值，比擬兩函數(shù)n2和50n log 2 n的增長趨勢，并確定 n在什 么范圍內(nèi)，函數(shù)n2的值大于50nlog2n的值。解：n2的增長趨勢快。但在n較小的時候，50nlogzn的值較大。當(dāng) n>438 時，n 50n Iog

13、2n1.14判斷以下各對函數(shù)f n和g n，當(dāng)n時，哪個函數(shù)增長更快?f nIn n! 5 2，g n2.513nf n2.14n- n 1，g nInn! 2 nf n322n 2n ，g nn2 n5 n解:(1)g( n)快(2)g( n)快(3)f( n)快(4) f(n)試用數(shù)學(xué)歸納法證明：(1)n2 ii 1n n 1 2n 1/6n 0ni xi 0xn1 1 / x1x1,n0n2i 1i 12n 1n 1n2i1 n2n 1(1) f ng ni 1快1.152n410n2 Inn!10n31.16試寫一算法，自大至小依次輸出順序讀入的三個整數(shù)解：int max3(i nt

14、x,i nt y,i nt z)if(x>y)if(x>z) retur n x;else return z;elseif(y>z) retur n y; else return z;1.17k階斐波那契序列的定義為X，Y和Z的值fo 0 , f10 ,，fk 20 , fk 11 ；n k，n k,k 1,k和m均以值調(diào)用的形試編寫求k階斐波那契序列的第m項值的函數(shù)算法, 式在函數(shù)參數(shù)表中出現(xiàn)。解：k>0為階數(shù)，n為數(shù)列的第n項int Fib on acci (int k,i nt n)if(k<1) exit(OVERFLOW);int *p,x;p=new

15、in tk+1;if(!p) exit(OVERFLOW);int i,j;for(i=0;i<k+1;i+)if(i<k-1) pi=0;else pi=1;for(i=k+1;i< n+1;i+)x=p0;for(j=0;j<k;j+) pj=pj+1;pk=2*pk-1-x;return pk;1.18假設(shè)有A, B, C, D, E五個高等院校進(jìn)行田徑對抗賽，各院校的單項成績 均已存入計算機，并構(gòu)成一張表，表中每一行的形式為工程名稱性別校名成績得分編寫算法，處理上述表格，以統(tǒng)計各院校的男、女總分和團(tuán)體總分，并輸出解：typedef en umA,B,C,D,E

16、SchoolName;typedef enu mFemale,Male SexType;typedef structchar eve nt3; / 工程SexType sex;SchoolName school;int score; Comp onent;typedef structint MaleSum;/ 男團(tuán)總分int FemaleSum;/ 女團(tuán)總分int TotalSum; / 團(tuán)體總分 Sum;Sum SumScore(SchoolName sn. Comp onent a,i nt n)Sum temp;temp.MaleSum=0;temp.FemaleSum=0;temp.T

17、otalSum=0;int i;for(i=0;i< n;i+)if(ai.school=s n)if(ai.sex=Male) temp.MaleSum+=ai.score; if(ai.sex=Female) temp.FemaleSum+=ai.score;temp.TotalSum=temp.MaleSum+temp.FemaleSum;return temp;1.19試編寫算法，計算i!*2,的值并存入數(shù)組a0.arrsize-1 的第i-1個分量 中(i=1,2,n)。假設(shè)計算機中允許的整數(shù)最大值為maxi nt，那么當(dāng)n >arrsize或?qū)δ硞€ k1 k n ，使

18、k!?2k max int 時，應(yīng)按出錯處理。注意選擇你認(rèn)為較 好的出錯處理方法。解：#include<iostream.h>#include<stdlib.h>#define MAXINT 65535#define ArrSize 100int fun(int i);int main()int i,k;int aArrSize;cout<<"Enter k:"cin>>k;if(k>ArrSize-1) exit(0); for(i=0;i<=k;i+)if(i=0) ai=1;else if(2*i*ai-1&

19、gt;MAXINT) exit(0); else ai=2*i*ai-1;for(i=0;i<=k;i+)if(ai>MAXINT) exit(0);else cout<<ai<<" "return 0;1.20試編寫算法求一元多項式的值Pnnaixi 的值 Pn x0 ，并確定算法中每 i0一語句的執(zhí)行次數(shù)和整個算法的時間復(fù)雜度。注意選擇你認(rèn)為較好的輸入和輸出方法。此題的輸入為aj i 0,1, ,n , xo和n，輸出為巳x。解：#i nclude<iostream.h>#i nclude<stdlib.h>#

20、define N 10double polyno mail(i nt a,i nt i,double x,i nt n);int mai n()double x;int n,i;int aN;cout«"輸入變量的值x:"cin> >x;cout«"輸入多項式的階次n:"cin>>n;if(n>N-1) exit(0);cout«"輸入多項式的系數(shù)a0-an:"for(i=0;i<=n ;i+) cin> >ai;cout<<"The

21、polyno mail value is "<<po lyno mail(a ,n,x,n)«en dl; return 0;double polyno mail(i nt a,i nt i,double x,i nt n)if(i>0) return a n-i+poly no mail(a,i-1,x ,n )*x;else return an;本算法的時間復(fù)雜度為o(n)。第2章線性表2.1描述以下三個概念的區(qū)別：頭指針，頭結(jié)點，首元結(jié)點(第一個元素結(jié)點)。 解：頭指針是指向鏈表中第一個結(jié)點的指針。首元結(jié)點是指鏈表中存儲第一個數(shù)據(jù)元素的結(jié)點。頭結(jié)點是

22、在首元結(jié)點之前附設(shè)的一個結(jié)點，該結(jié)點不存儲數(shù) 據(jù)元素，其指針域指向首元結(jié)點，其作用主要是為了方便對鏈表的操作。它可以對空表、非空表以及首元結(jié)點的操作進(jìn)行統(tǒng)一處理。2.2填空題。解：(1)在順序表中插入或刪除一個元素，需要平均移動表中一半元素,具 體移動的元素個數(shù)與 元素在表中的位置 有關(guān)。(2) 順序表中邏輯上相鄰的元素的物理位置必定緊鄰。單鏈表中邏輯上相鄰 的元素的物理位置不一定緊鄰。(3) 在單鏈表中，除了首元結(jié)點外，任一結(jié)點的存儲位置由 其前驅(qū)結(jié)點的鏈 域的值指示。(4) 在單鏈表中設(shè)置頭結(jié)點的作用是插入和刪除首元結(jié)點時不用進(jìn)行特殊處理。2.3在什么情況下用順序表比鏈表好？用順序表比用鏈

23、解：當(dāng)線性表的數(shù)據(jù)元素在物理位置上是連續(xù)存儲的時候， 表好，其特點是可以進(jìn)行隨機存取。2.4對以下單鏈表分別執(zhí)行以下各程序段，并畫出結(jié)果示意圖。L J 2f 5» 7f 3f £IX5 TI PL1 r,27L一 27P14lbTsI 12.5畫出執(zhí)行以下各行語句后各指針及鏈表的示意圖L=(L in kList)malloc(sizeof(LNode);P=L;for(i=1;i<=4;i+)P->n ext=(L in kList)malloc(sizeof(LNode); P=P->next; P->data=i*2-1;P-> next=

24、NULL;for(i=4;i>=1;i-) Ins_LinkList(L,i+1,i*2); for(i=1;i<=3;i+) Del_LinkList(L,i); 解：FP2.6L是無表頭結(jié)點的單鏈表，且P結(jié)點既不是首元結(jié)點，也不是尾元結(jié)點，試從以下提供的答案中選擇適宜的語句序列。a. 在P結(jié)點后插入S結(jié)點的語句序列是 。b. 在 P結(jié)點前插入 S結(jié)點的語句序列是 。c. 在表首插入 S結(jié)點的語句序列是 。d. 在表尾插入S結(jié)點的語句序列是。(1) P-> next=S;(2) P->n ext=P->n ext- >n ext;(3) P-> ne

25、xt=S-> next;(4) S-> next=P-> next;(5) S-> next=L; S-> next=NULL; Q=P;(8) while(P-> next!=Q) P=P->n ext;(9) while(P->next!=NULL) P=P->next;(10) P=Q;(11) P=L;(12) L=S;(13) L=P;解：a. (4) (1)b. (11) (8)c. (12)d. (9) (1) (6)2.7L是帶表頭結(jié)點的非空單鏈表，且P結(jié)點既不是首元結(jié)點，也不是尾元結(jié)點，試從以下提供的答案中選擇適宜的語句序

26、列。a. 刪除P結(jié)點的直接后繼結(jié)點的語句序列是。b. 刪除 P 結(jié)點的直接前驅(qū)結(jié)點的語句序列是 。c. 刪除 P 結(jié)點的語句序列是 。d. 刪除首元結(jié)點的語句序列是 。e. 刪除尾元結(jié)點的語句序列是 。(1) P=P->next;(2) P->next=P;(3) P->next=P->next->next;(4) P=P->next->next;(5) while(P!=NULL) P=P->next;(6) while(Q->next!=NULL) P=Q; Q=Q->next; (7) while(P->next!=Q)

27、P=P->next;(8) while(P->next->next!=Q) P=P->next;(9) while(P->next->next!=NULL) P=P->next;(10) Q=P;(11) Q=P->next;(12) P=L;(13) L=L->next;(14) free(Q);解：a. (11)(14)b. (10) (12) (8) (3) (14)c. (10) (12) (7) (3) (14)d. (12) (11) (3) (14)e. (9) (11) (3) (14)2.8 P 結(jié)點是某雙向鏈表的中間結(jié)點

28、，試從以下提供的答案中選擇適宜的 語句序列。a. 在P結(jié)點后插入S結(jié)點的語句序列是 。b. 在 P結(jié)點前插入 S結(jié)點的語句序列是 。c. 刪除P結(jié)點的直接后繼結(jié)點的語句序列是 。d. 刪除P結(jié)點的直接前驅(qū)結(jié)點的語句序列是 。e. 刪除P結(jié)點的語句序列是 。(1) P->next=P->next->next;(2) P->priou=P->priou->priou;(3) P->next=S;(4) P->priou=S;(5) S->next=P;(6) S->priou=P;(7) S->next=P->next;(8)

29、 S->priou=P->priou;(9) P->priou->next=P->next;(10) P->priou->next=P;(11) P->next->priou=P;(12) P->next->priou=S;(13) P->priou->next=S;(14) P->next->priou=P->priou;(15) Q=P->next;(16) Q=P->priou;(17) free(P);(18) free(Q);解：a.(12)b. (8) (4) (5) (13

30、)c. (15) (1) (11) (18)d. (16) (2) (10) (18)e. (14) (9) (17)2.9 簡述以下算法的功能。(1) Status A(LinkedList L) /L是無表頭結(jié)點的單鏈表if(L && L->next) Q=L; L=L->next; P=L;while(P->next) P=P->next;P->next=Q; Q->next=NULL;return OK;(2) void BB(LNode *s, LNode *q) p=s;while(p->next!=q) p=p->n

31、ext;p->next =s;void AA(LNode *pa, LNode *pb) /pa 和 pb 分別指向單循環(huán)鏈表中的兩個結(jié)點BB(pa,pb);BB(pb,pa);解：(1)如果L的長度不小于2,將L的首元結(jié)點變成尾元結(jié)點。(2) 將單循環(huán)鏈表拆成兩個單循環(huán)鏈表。2.10 指出以下算法中的錯誤和低效之處,并將它改寫為一個既正確又高效的算 法。Status DeleteK(SqList &a,int i,int k)/本過程從順序存儲結(jié)構(gòu)的線性表a中刪除第i個元素起的k個元素if(i<1|k<0|i+k>a.length) return INFEAS

32、IBLE;/參數(shù)不合法else for(count=1;count<k;count+)/ 刪除第一個元素for(j=a.length;j>=i+1;j-) a.elemj-i=a.elemj;a.length-;return OK;解：Status DeleteK(SqList &a,int i,int k)/從順序存儲結(jié)構(gòu)的線性表a中刪除第i個元素起的k個元素/ 注意 i 的編號從 0 開始int j;if(i<0|i>a.length-1|k<0|k>a.length-i) return INFEASIBLE; for(j=0;j<=k;j

33、+)a.elemj+i=a.elemj+i+k;a.length=a.length-k;return OK;2.11 設(shè)順序表 va 中的數(shù)據(jù)元素遞增有序。試寫一算法，將 x 插入到順序表的 適當(dāng)位置上，以保持該表的有序性。解：Status InsertOrderList(SqList &va,ElemType x)/ 在非遞減的順序表 va 中插入元素 x 并使其仍成為順序表的算法int i;if(va.length=va.listsize)return(OVERFLOW); for(i=va.length;i>0,x<va.elemi-1;i-)va.elemi=va.

34、elemi-1;va.elemi=x;va.length+;return OK;2.12設(shè)A ai, ,am和B bi, ,bn均為順序表，A和B分別為A和B中除 去最大共同前綴后的子表。假設(shè) A B 空表，那么A B ;假設(shè)A二空表，而B 空 表，或者兩者均不為空表，且 A的首元小于B的首元，那么A B ;否那么A B。 試寫一個比擬A，B大小的算法。解：Status CompareOrderList(SqList &A,SqList &B)int i,k,j;k=A.length>B.length?A.length:B.length;for(i=0;i<k;i+

35、)if(A.elemi>B.elemi) j=i;if(A.elemi<B.elemi) j=-i;if(A.length>k) j=i;if(B.length>k) j=-i;if(A.length=B.length) j=0;return j;Locate(L,x);Length(L) 。2.13 試寫一算法在帶頭結(jié)點的單鏈表結(jié)構(gòu)上實現(xiàn)線性表操作 解：int LocateElem_L(LinkList &L,ElemType x)int i=0;LinkList p=L; while(p&&p->data!=x) p=p->nex

36、t; i+;if(!p) return 0; else return i;2.14 試寫一算法在帶頭結(jié)點的單鏈表結(jié)構(gòu)上實現(xiàn)線性表操作 解：/ 返回單鏈表的長度int ListLength_L(LinkList &L)int i=0;LinkList p=L;if(p) p=p-next;while(p)p=p->next;i+;return i;2.15指針ha和hb分別指向兩個單鏈表的頭結(jié)點，并且兩個鏈表的長 度分別為m和n。試寫一算法將這兩個鏈表連接在一起，假設(shè)指針he指向連接后的鏈表的頭結(jié)點，并要求算法以盡可能短的時間完成連接運算。請分析你的 算法的時間復(fù)雜度。解：void

37、 MergeList_L(LinkList &ha,LinkList &hb,LinkList &he) LinkList pa,pb;pa=ha;pb=hb; while(pa->next&&pb->next) pa=pa->next; pb=pb->next; if(!pa->next)he=hb;while(pb->next) pb=pb->next;pb->next=ha->next;elsehc=ha;while(pa->next) pa=pa->next;pa->next

38、=hb->next;2.16 指針 la 和 lb 分別指向兩個無頭結(jié)點單鏈表中的首元結(jié)點。以下算法 是從表 la 中刪除自第 i 個元素起共 len 個元素后，將它們插入到表 lb 中第 i 個元素之前。試問此算法是否正確？假設(shè)有錯，請改正之。Status DeleteAndInsertSub(LinkedList la,LinkedList lb,int i,int j,int len)if(i<0|j<0|len<0) return INFEASIBLE;p=la; k=1;while(k<i) p=p->next; k+; q=p;while(k&l

39、t;=len) q=q->next; k+; s=lb; k=1;while(k<j) s=s->next; k+; s->next=p; q->next=s->next;return OK;解：Status DeleteAndInsertSub(LinkList &la,LinkList &lb,int i,int j,int len)LinkList p,q,s,prev=NULL;int k=1;if(i<0|j<0|len<0) return INFEASIBLE;/ 在 la 表中查找第 i 個結(jié)點p=la;whi

40、le(p&&k<i)prev=p;p=p->next;k+;if(!p)return INFEASIBLE;/ 在 la 表中查找第 i+len-1 個結(jié)點 q=p; k=1;while(q&&k<len)q=p->next;k+;if(!q)return INFEASIBLE;/ 完成刪除，注意， i=1 的情況需要特殊處理if(!prev) la=q->next;else prev->next=q->next;/ 將從 la 中刪除的結(jié)點插入到 lb 中if(j=1)q->next=lb;lb=p;elses=

41、lb; k=1;while(s&&k<j-1)s=s->next; k+;if(!s)return INFEASIBLE;q->next=s->next;s->next=p; / 完成插入return OK;2.17 試寫一算法， 在無頭結(jié)點的動態(tài)單鏈表上實現(xiàn)線性表操作 Insert(L,i,b) ， 并和在帶頭結(jié)點的動態(tài)單鏈表上實現(xiàn)相同操作的算法進(jìn)行比擬。2.18 試寫一算法，實現(xiàn)線性表操作 Delete(L,i) ，并和在帶頭結(jié)點的動態(tài)單鏈 表上實現(xiàn)相同操作的算法進(jìn)行比擬。2.19 線性表中的元素以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試寫一

42、高效的算法，刪除表中所有值大于 mink 且小于 maxk 的元素(假設(shè)表中存在這樣 的元素)，同時釋放被刪結(jié)點空間，并分析你的算法的時間復(fù)雜度(注意， mink 和 maxk 是給定的兩個參變量，它們的值可以和表中的元素相同，也可以不同) 。解：Status ListDelete_L(LinkList &L,ElemType mink,ElemType maxk) LinkList p,q,prev=NULL; if(mink>maxk)return ERROR; p=L;prev=p;p=p->next; while(p&&p->data<m

43、axk) if(p->data<=mink) prev=p; p=p->next;elseprev->next=p->next;q=p;p=p->next; free(q);return OK;2.20 同 2.19 題條件， 試寫一高效的算法， 刪除表中所有值相同的多余元素 (使 得操作后的線性表中所有元素的值均不相同) ，同時釋放被刪結(jié)點空間，并分析 你的算法的時間復(fù)雜度。解：void ListDelete_LSameNode(LinkList &L)LinkList p,q,prev;p=L;prev=p;p=p->next;while(

44、p)prev=p;p=p->next;if(p&&p->data=prev->data) prev->next=p->next; q=p;p=p->next;free(q);2.21 試寫一算法，實現(xiàn)順序表的就地逆置，即利用原表的存儲空間將線性表a1, ,an 逆置為 an , ,a1 。解：/ 順序表的逆置Status ListOppose_Sq(SqList &L)int i;ElemType x;for(i=0;i<L.length/2;i+)x=L.elemi;L.elemi=L.elemL.length-1-i;L.e

45、lemL.length-1-i=x;return OK;2.22 試寫一算法，對單鏈表實現(xiàn)就地逆置。 解：/ 帶頭結(jié)點的單鏈表的逆置Status ListOppose_L(LinkList &L)LinkList p,q;p=L;p=p->next;L->next=NULL;while(p)q=p; p=p->next; q->next=L->next;L->next=q;b1,b2 , ,bn ，試寫一個按以下規(guī)那么合并return OK;A，B為線性表C 的算法，即使得Ca1,b1,am,bm,bm 1,bn當(dāng)m n時;Ca1,b1,an,bn

46、,an 1,am當(dāng) m n 時。2.23設(shè)線性表 A a1,a2, ,am ， B線性表A, B和C均以單鏈表作存儲結(jié)構(gòu)，且 C表利用A表和B表中的結(jié)點空間 構(gòu)成。注意：單鏈表的長度值m和n均未顯式存儲。解：/將合并后的結(jié)果放在C表中，并刪除B表Status ListMerge_L(LinkList &A,LinkList &B,LinkList &C)LinkList pa,pb,qa,qb;pa=A->next;pb=B->next;C=A;while(pa&&pb)qa=pa; qb=pb; pa=pa->next; pb=pb-

47、>next; qb->next=qa->next; qa->next=qb;if(!pa)qb->next=pb;pb=B; free(pb); return OK;2.24假設(shè)有兩個按元素值遞增有序排列的線性表A和B,均以單鏈表作存儲結(jié)構(gòu)，請編寫算法將A表和B表歸并成一個按元素值遞減有序(即非遞增有序， 允許表中含有值相同的元素)排列的線性表C,并要求利用原表(即A表和B表) 的結(jié)點空間構(gòu)造C表。解：/將合并逆置后的結(jié)果放在 C表中，并刪除B表Status ListMergeOppose_L(LinkList &A,LinkList &B,Lin

48、kList &C)LinkList pa,pb,qa,qb;pa=A;pb=B;qa=pa; / 保存 pa 的前驅(qū)指針qb=pb; / 保存 pb 的前驅(qū)指針pa=pa->next;pb=pb->next;A->next=NULL;C=A;while(pa&&pb)if(pa->data<pb->data)qa=pa;pa=pa->next;qa->next=A->next; /將當(dāng)前最小結(jié)點插入A表表頭 A->next=qa;elseqb=pb;pb=pb->next;qb->next=A-&g

49、t;next; /將當(dāng)前最小結(jié)點插入A表表頭 A->next=qb;while(pa)qa=pa;pa=pa->next;qa->next=A->next; A->next=qa;while(pb)qb=pb;pb=pb->next;qb->next=A->next;A->next=qb;pb=B;free(pb);return OK;2.25假設(shè)以兩個元素依值遞增有序排列的線性表A和B分別表示兩個集合(即同一表中的元素值各不相同)，現(xiàn)要求另辟空間構(gòu)成一個線性表C,其元素為A和B中元素的交集，且表C中的元素有依值遞增有序排列。試對順序表編寫

50、求C的算法。解：/將A、B求交后的結(jié)果放在C表中Status ListCross_Sq(SqList &A,SqList &B,SqList &C)int i=0,j=0,k=0;while(i<A.length && j<B.length)if(A.elemi<B.elemj)i+;elseif(A.elemi>B.elemj)j+;elseListInsert_Sq(C,k,A.elemi);i+;k+;return OK;2.26要求同2.25題。試對單鏈表編寫求 C的算法。解：/將A、B求交后的結(jié)果放在C表中，并刪除B表S

51、tatus ListCross_L(LinkList &A,LinkList &B,LinkList &C)LinkList pa,pb,qa,qb,pt;pa=A;pb=B;qa=pa; / 保存 pa 的前驅(qū)指針qb=pb; / 保存 pb 的前驅(qū)指針pa=pa->next;pb=pb->next;C=A;while(pa&&pb)if(pa->data<pb->data)pt=pa;pa=pa->next;qa->next=pa;free(pt);elseif(pa->data>pb->d

52、ata) pt=pb; pb=pb->next; qb->next=pb; free(pt);elseqa=pa; pa=pa->next;while(pa)pt=pa;pa=pa->next;qa->next=pa;free(pt);while(pb)pt=pb;pb=pb->next;qb->next=pb;free(pt);pb=B;free(pb);return OK;2.27對2.25題的條件作以下兩點修改，對順序表重新編寫求得表C的算法<(1) 假設(shè)在同一表(A或B)中可能存在值相同的元素，但要求新生成的表 C中的元素值各不相同；(2

53、) 利用A表空間存放表C。解：(1)/ A、B求交，然后刪除相同元素，將結(jié)果放在C表中Status ListCrossDelSame_Sq(SqList &A,SqList &B,SqList &C)int i=0,j=0,k=0;while(i<A.length && j<B.length)if(A.elemi<B.elemj)i+;elseif(A.elemi>B.elemj) j+;elseif(C.length=0)ListInsert_Sq(C,k,A.elemi);k+;elseif(C.elemC.length-1!

54、=A.elemi)ListInsert_Sq(C,k,A.elemi);k+;i+;return OK;(2)/ A 、B 求交，然后刪除相同元素，將結(jié)果放在A 表中Status ListCrossDelSame_Sq(SqList &A,SqList &B)int i=0,j=0,k=0;while(i<A.length && j<B.length)if(A.elemi<B.elemj) i+;elseif(A.elemi>B.elemj) j+;elseif(k=0)A.elemk=A.elemi;k+;elseif(A.elemk!

55、=A.elemi) A.elemk=A.elemi; k+;i+;A.length=k;return OK;2.28對2.25題的條件作以下兩點修改，對單鏈表重新編寫求得表C的算法<(1)假設(shè)在同一表(A或B)中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同；(2)利用原表(A表或B表)中的結(jié)點構(gòu)成表C,并釋放A表中的無用結(jié)點 空間。解：(1)/ A、B求交，結(jié)果放在C表中，并刪除相同元素Status ListCrossDelSame_L(LinkList &A,LinkList &B,LinkList &C)LinkList pa,pb,qa,qb,

56、pt;pa=A;pb=B;qa=pa; / 保存 pa 的前驅(qū)指針qb=pb; / 保存 pb 的前驅(qū)指針 pa=pa->next;pb=pb->next;C=A;while(pa&&pb) if(pa->data<pb->data) pt=pa;pa=pa->next;qa->next=pa; free(pt); else if(pa->data>pb->data) pt=pb; pb=pb->next; qb->next=pb; free(pt); else if(pa->data=qa->data) pt=pa; pa=pa->next; qa->next=pa; free(pt);else qa=pa; pa=pa->next; while(pa) pt=pa