清華數(shù)據(jù)結(jié)構(gòu)習(xí)題集答案(C語言版嚴(yán)蔚敏)

《清華數(shù)據(jù)結(jié)構(gòu)習(xí)題集答案(C語言版嚴(yán)蔚敏)》由會(huì)員分享，可在線閱讀，更多相關(guān)《清華數(shù)據(jù)結(jié)構(gòu)習(xí)題集答案(C語言版嚴(yán)蔚敏)（123頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 清華數(shù)據(jù)結(jié)構(gòu)習(xí)題集答案 (C 語言版嚴(yán)蔚敏 ) 第 1 章 緒論 1.1 簡(jiǎn)述下列術(shù)語：數(shù)據(jù)，數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)類型和抽象數(shù)據(jù)類型。 解：數(shù)據(jù) 是對(duì)客觀事物的符號(hào)表示。在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。 數(shù)據(jù)元素 是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。 數(shù)據(jù)對(duì)象 是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。 數(shù)據(jù)結(jié)構(gòu) 是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。 存儲(chǔ)結(jié)構(gòu) 是數(shù)據(jù)

2、結(jié)構(gòu)在計(jì)算機(jī)中的表示。 數(shù)據(jù)類型 是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。 抽象數(shù)據(jù)類型 是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。是對(duì)一般數(shù)據(jù)類型的擴(kuò)展。 1.2 試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念與程序設(shè)計(jì)語言中數(shù)據(jù)類型概念的區(qū)別。 解：抽象數(shù)據(jù)類型包含一般數(shù)據(jù)類型的概念，但含義比一般數(shù)據(jù)類型更廣、更抽象。一般數(shù)據(jù)類型由具體語言系統(tǒng)內(nèi)部定義，直接提供給編程者定義用戶數(shù)據(jù)，因此稱它們?yōu)轭A(yù)定義數(shù)據(jù)類型。抽象數(shù)據(jù)類型通常由編程者定義，包括定義它所使用的數(shù)據(jù)和在這些數(shù)據(jù)上所進(jìn)行的操作。在定義抽象數(shù)據(jù)類型中的數(shù)據(jù)部分和操作部分時(shí)，要求只定義到數(shù)據(jù)的邏輯結(jié)構(gòu)和操作

3、說明，不考慮數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和操作的具體實(shí)現(xiàn)，這樣抽象層次更高，更能為其他用戶提供良好的使用接口。 1.3 設(shè)有數(shù)據(jù)結(jié)構(gòu) (D,R) ，其中 D d1, d 2, d 3, d 4 ， R r ， r d1, d 2 , d 2,d 3 , d 3, d 4 試按圖論中圖的畫法慣例畫出其邏輯結(jié)構(gòu)圖。 解： 1.4 試仿照三元組的抽象數(shù)據(jù)類型分別寫出抽象數(shù)據(jù)類型復(fù)數(shù)和有理數(shù)的定義（有理數(shù)是其分子、分母均 為自然數(shù)且分母不為零的分?jǐn)?shù)） 。 解： ADT Complex{ 數(shù)據(jù)對(duì)象： D={r,i|r,i 為實(shí)數(shù) }

4、 數(shù)據(jù)關(guān)系： R={} 基本操作： InitComplex(&C,re,im) 操作結(jié)果：構(gòu)造一個(gè)復(fù)數(shù) C，其實(shí)部和虛部分別為 re 和 im DestroyCmoplex(&C) 操作結(jié)果：銷毀復(fù)數(shù) C Get(C,k,&e) 操作結(jié)果：用 e 返回復(fù)數(shù) C的第 k 元的值 Put(&C,k,e) 操作結(jié)果：改變復(fù)數(shù) C的第 k 元的值為 e IsAscending(C) 操作結(jié)果：如果復(fù)數(shù) C的兩個(gè)元素按升序排列，則返回 1，否則返回 0 IsDescending(C) 操作結(jié)果：如果復(fù)

5、數(shù) C的兩個(gè)元素按降序排列，則返回 1，否則返回 0 Max(C,&e) 操作結(jié)果：用 e 返回復(fù)數(shù) C的兩個(gè)元素中值較大的一個(gè) Min(C,&e) 操作結(jié)果：用 e 返回復(fù)數(shù) C的兩個(gè)元素中值較小的一個(gè) }ADT Complex ADT RationalNumber{ 數(shù)據(jù)對(duì)象： D={s,m|s,m 為自然數(shù)，且 m不為 0} 數(shù)據(jù)關(guān)系： R={} 基本操作： InitRationalNumber(&R,s,m) 操作結(jié)果：構(gòu)造一個(gè)有理數(shù) R，其分子和分母分別為 s 和 m DestroyRatio

6、nalNumber(&R) 操作結(jié)果：銷毀有理數(shù) R Get(R,k,&e) 操作結(jié)果：用 e 返回有理數(shù) R 的第 k 元的值 Put(&R,k,e) 操作結(jié)果：改變有理數(shù) R 的第 k 元的值為 e IsAscending(R) 操作結(jié)果：若有理數(shù) R的兩個(gè)元素按升序排列，則返回 1，否則返回 0 IsDescending(R) 操作結(jié)果：若有理數(shù) R的兩個(gè)元素按降序排列，則返回 1，否則返回 0 Max(R,&e) 操作結(jié)果：用 e 返回有理數(shù) R 的兩個(gè)元素中值較大的一個(gè) Min(R,&e) 操作結(jié)果：用 e

7、 返回有理數(shù) R 的兩個(gè)元素中值較小的一個(gè) }ADT RationalNumber 1.5 試畫出與下列程序段等價(jià)的框圖。 (1) product=1; i=1; while(i<=n){ product *= i; i++; } (2) i=0; do { i++; } while((i!=n) && (a[i]!=x)); (3) switch { case x

8、s(y); } 1.6 在程序設(shè)計(jì)中，常用下列三種不同的出錯(cuò)處理方式： (1) 用 exit 語句終止執(zhí)行并報(bào)告錯(cuò)誤； (2) 以函數(shù)的返回值區(qū)別正確返回或錯(cuò)誤返回； (3) 設(shè)置一個(gè)整型變量的函數(shù)參數(shù)以區(qū)別正確返回或某種錯(cuò)誤返回。試討論這三種方法各自的優(yōu)缺點(diǎn)。 解： (1)exit 常用于異常錯(cuò)誤處理，它可以強(qiáng)行中斷程序的執(zhí)行，返回操作系統(tǒng)。 (2) 以函數(shù)的返回值判斷正確與否常用于子程序的測(cè)試，便于實(shí)現(xiàn)程序的局部控制。 (3) 用整型函數(shù)進(jìn)行錯(cuò)誤處理的優(yōu)點(diǎn)是可以給出錯(cuò)誤類型，便于迅速確定錯(cuò)誤。 1.7 在程序設(shè)計(jì)中，可采用下列三種

9、方法實(shí)現(xiàn)輸出和輸入： (1) 通過 scanf 和 printf 語句； (2) 通過函數(shù)的參數(shù)顯式傳遞； (3) 通過全局變量隱式傳遞。 試討論這三種方法的優(yōu)缺點(diǎn)。 解：(1) 用 scanf 和 printf 直接進(jìn)行輸入輸出的好處是形象、 直觀，但缺點(diǎn)是需要對(duì)其進(jìn)行格式控制， 較為煩瑣，如果出現(xiàn)錯(cuò)誤，則會(huì)引起整個(gè)系統(tǒng)的崩潰。 (2) 通過函數(shù)的參數(shù)傳遞進(jìn)行輸入輸出，便于實(shí)現(xiàn)信息的隱蔽，減少出錯(cuò)的可能。 (3) 通過全局變量的隱式傳遞進(jìn)行輸入輸出最為方便， 只需修改變量的值即可， 但過多的全局變量使程序的維護(hù)較為困難。 1.8 設(shè)

10、n 為正整數(shù)。試確定下列各程序段中前置以記號(hào) @的語句的頻度： (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; k=0; while (i<=n-1) { i++; @ k += 10*i; } (4) k=0; for(i=1; i<=n; i++) { for(j=i; j<=n; j++) @ k++; } (5) for(i=1; i<

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

12、++; } 解： (1) n-1 (2) n-1 (3) n-1 (4) n+(n-1)+(n-2)+...+1= n(n 1) 2 (5) 1+(1+2)+(1+2+3)+...+(1+2+3+...+n)= n i (i 1) 2 i 1 = 1 n i (i 1) 1 n (i 2 i ) 1 n i 2 1

13、 n i 2 i 1 2 i 1 2 i 1 2 i 1 1 1 1 ( 1)(2 3) n(n 1)( 2n 1) n(n 1) = 12 4 12 (6) n (7) n 向下取整 (8) 1100 1.9  假設(shè) n 為 2 的乘冪， 并且 n>2，試求下列算法的時(shí)間復(fù)雜度及變量 int Time(int n) { count =

14、0; x=2; while(x

15、 運(yùn)算的時(shí)間為  10 7  秒（100 多天），又每秒可執(zhí)行基本操作 （根據(jù)這些操作來估算算法時(shí)間復(fù)雜度）  105  次。 試問在此條件下，  這兩個(gè)算法可解問題的規(guī)模  （即  n 值的范圍） 各為多少？哪個(gè)算法更適宜？請(qǐng)說明理由。 解： 2 n  1012  n=40 n10  1012  n=16 則對(duì)于同樣的循環(huán)次數(shù) n，在這個(gè)規(guī)模下，第二種算法所花費(fèi)的代價(jià)要大得多。故在這個(gè)規(guī)模下，第

16、 一種算法更適宜。 1.12 設(shè)有以下三個(gè)函數(shù)： f n 21 4 n 2 1000 ， g n 15n 4 500n 3 ， h n 500n 3.5 nlog n n 請(qǐng)判斷以下斷言正確與否： (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) 對(duì) (2) 錯(cuò) (3) 錯(cuò) (4)

17、對(duì) (5) 錯(cuò) 1.13 試設(shè)定若干 n 值，比較兩函數(shù) n 2 和 50n log 2 n的增長(zhǎng)趨勢(shì)，并確定 n 在什么范圍內(nèi)，函數(shù) n 2 的值 大于 50n log 2 n 的值。 解： n 2 的增長(zhǎng)趨勢(shì)快。但在 n 較小的時(shí)候， 50n log 2 n 的值較大。 當(dāng) n>438 時(shí)， n 2 50n log 2 n 1.14 判斷下列各對(duì)函數(shù) f n 和 g n ，當(dāng) n 時(shí)，哪個(gè)函數(shù)增長(zhǎng)更快？ (1) f n 10n 2 ln

18、n! 10n3 ， g n 2n4 n 7 (2) f n ln n! 5 2 ， g n 13n2.5 (3) f n n2.1 n 4 1 ， g n ln n! 2 n (4) f n 2 n3 2n 2 ， g n n n 2 n5 解： (1)g(n) 快 (2)g(n) 快 (3)f(n) 快 (4) f(n) 快 1.15 試用數(shù)學(xué)歸納法證明： n i 2 1 2n 1 / 6 n 0 (1) n n i 1

19、 n x i x n 1 1 / x 1 x 1, n 0 (2) i 0 n 2i 1 2n 1 n 1 (3) i 1 n 2i 1 n 2 n 1 (4) i 1 1.16 寫一算法，自大至小依次 出 序 入的三個(gè)整數(shù) X， Y 和 Z 的 解： int max3(int x,int y,int z) { if(x>y)

20、 if(x>z) return x; else return z; else if(y>z) return y; else return z; } 1.17 已知 k 斐波那契序列的定 f 0  0 ，  f1  0 ， ?，  f k  2  0 ，  fk 1  1； f n  f n 1  f n 2  fn k ， n  k ,k  1, 寫求  k

21、 斐波那契序列的第  m 的函數(shù)算法，  k 和 m均以 用的形式在函數(shù)參數(shù)表中出 。 解： k>0 數(shù)，  n 數(shù)列的第  n 項(xiàng) int Fibonacci(int k,int n) { if(k<1) exit(OVERFLOW); int *p,x; p=new int[k+1]; if(!p) exit(OVERFLOW); int i,j; for(i=0;i

22、r(i=k+1;i

23、edef enum{Female,Male} SexType; typedef struct{ char event[3]; // 目 SexType sex; SchoolName school; int score; } Component; typedef struct{ int MaleSum;  // 男 分 int FemaleSum;  / /  女 分 int TotalSum; //  體 分 } Sum; Sum SumScor

24、e(SchoolName sn,Component a[],int n) { Sum temp; temp.MaleSum=0; temp.FemaleSum=0; temp.TotalSum=0; int i; for(i=0;i

25、p.MaleSum+temp.FemaleSum; return temp; } 1.19 寫算法， 算  i!* 2i  的 并存入數(shù)  a[0..arrsize-1]  的第  i-1  個(gè)分量中  (i=1,2,  ?,n)  。假 算機(jī)中允 的整數(shù)最大  maxint  ， 當(dāng)  n>arrsize  或 某個(gè)  k 1  k

26、 n  ，使  k!?2  k  max int  ， 按出 理。注意 你 好的出 理方法。 解： #include #include #define MAXINT 65535 #define ArrSize 100 int fun(int i); int main() { int i,k; int a[ArrSize]; cout<<"Enter k:"; ci

27、n>>k; if(k>ArrSize-1) exit(0); for(i=0;i<=k;i++){ if(i==0) a[i]=1; else{ if(2*i*a[i-1]>MAXINT) exit(0); else a[i]=2*i*a[i-1]; } } for(i=0;i<=k;i++){ if(a[i]>MAXINT) exit(0); else cout<

28、值 Pn x0 ，并確定算法中每一語句的執(zhí)行次數(shù) i 0 和整個(gè)算法的時(shí)間復(fù)雜度。 注意選擇你認(rèn)為較好的輸入和輸出方法。 本題的輸入為 ai i 0,1, , n ，x0 和 n ，輸出為 Pn x0 。 解： #include #include #define N 10 double polynomail(int a[],int i,double x,int n); int main() {

29、 double x; int n,i; int a[N]; cout<<" 輸入變量的值 x:"; cin>>x; cout<<" 輸入多項(xiàng)式的階次 n:"; cin>>n; if(n>N-1) exit(0); cout<<" 輸入多項(xiàng)式的系數(shù) a[0]--a[n]:"; for(i=0;i<=n;i++) cin>>a[i]; cout<<"The polynomail value is "<

30、0) return a[n-i]+polynomail(a,i-1,x,n)*x; else return a[n]; } 本算法的時(shí)間復(fù)雜度為 o(n) 。 第 2 章 線性表 2.1 描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元結(jié)點(diǎn)（第一個(gè)元素結(jié)點(diǎn)） 。 解：頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針。首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。頭結(jié) 點(diǎn)是在首元

31、結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)元素，其指針域指向首元結(jié)點(diǎn)，其作用主要是為 了方便對(duì)鏈表的操作。它可以對(duì)空表、非空表以及首元結(jié)點(diǎn)的操作進(jìn)行統(tǒng)一處理。 2.2 填空題。 解： (1) 在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng) 表中一半元素，具體移動(dòng)的元素個(gè)數(shù)與  元素 在表中的位置有關(guān)。 (2) 順序表中邏輯上相鄰的元素的物理位置  必定緊鄰。單鏈表中邏輯上相鄰的元素的物理位置  不一定 緊鄰。 (3) 在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)

32、的存儲(chǔ)位置由  其前驅(qū)結(jié)點(diǎn)的鏈域的值 指示。 (4) 在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是 插入和刪除首元結(jié)點(diǎn)時(shí)不用進(jìn)行特殊處理 。 2.3 在什么情況下用順序表比鏈表好？ 解：當(dāng)線性表的數(shù)據(jù)元素在物理位置上是連續(xù)存儲(chǔ)的時(shí)候，用順序表比用鏈表好，其特點(diǎn)是可以進(jìn)行隨機(jī)存取。 2.4 對(duì)以下單鏈表分別執(zhí)行下列各程序段，并畫出結(jié)果示意圖。 解：

33、 2.5 畫出執(zhí)行下列各行語句后各指針及鏈表的示意圖。 L=(LinkList)malloc(sizeof(LNode)); P=L; for(i=1;i<=4;i++){ P->next=(LinkList)malloc(sizeof(LNode)); P=P->next; P->data=i*2-1; } P->next=NULL; for(i=4;i>=1;i--) Ins_LinkList(L,i+1,i*2); for(i=1;i<=3;i++) Del_LinkList(L,i); 解：

34、 2.6 已知 L 是無表頭結(jié)點(diǎn)的單鏈表，且 P 結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列提供的答案中 選擇合適的語句序列。 a. 在 P 結(jié)點(diǎn)后插入 S 結(jié)點(diǎn)的語句序列是 __________________。 b. 在 P 結(jié)點(diǎn)前插入 S 結(jié)點(diǎn)的語句序列是 __________________。 c. 在表首插入 S 結(jié)點(diǎn)的語句序列是 __________________。 d. 在表尾插入 S 結(jié)點(diǎn)的語句序列是 __________________。 (1) P->next=S; (2) P->next=P->

35、next->next; (3) P->next=S->next; (4) S->next=P->next; (5) S->next=L; (6) S->next=NULL; (7) Q=P; (8) while(P->next!=Q) P=P->next; (9) while(P->next!=NULL) P=P->next; (10) P=Q; (11) P=L; (12) L=S; (13) L=P; 解： a. (4) (1) b. (7) (11) (8) (4) (1) c. (5) (12)

36、d. (9) (1) (6) 2.7 已知 L 是帶表頭結(jié)點(diǎn)的非空單鏈表，且 P 結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列提供的答 案中選擇合適的語句序列。 a. 刪除 b. 刪除  P 結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列是 P 結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語句序列是  ____________________ 。 ____________________ 。 c. 刪除 P 結(jié)點(diǎn)的語句序列是 ____________________。 d. 刪除首元結(jié)點(diǎn)的語句序列是 ____________________。 e. 刪除尾元結(jié)點(diǎn)的

37、語句序列是 ____________________。 (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) P=P->next; (8) while(P->next->next!=Q) P=P->next; (9) while(P->next->n

38、ext!=NULL) P=P->next; (10) Q=P; (11) Q=P->next; (12) P=L; (13) L=L->next; (14) free(Q); 解： a. (11) (3) (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é)點(diǎn)是某雙向鏈表的中間結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語句序列。 a. 在 P 結(jié)點(diǎn)

39、后插入 S 結(jié)點(diǎn)的語句序列是 _______________________。 b. 在 P 結(jié)點(diǎn)前插入 S 結(jié)點(diǎn)的語句序列是 _______________________。 c. 刪除 P 結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列是 _______________________。 d. 刪除 P 結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語句序列是 _______________________。 e. 刪除 P 結(jié)點(diǎn)的語句序列是 _______________________。 (1) P->next=P->next->next; (2) P->priou=P-

40、>priou->priou; (3) P->next=S; (4) P->priou=S; (5) S->next=P; (6) S->priou=P; (7) S->next=P->next; (8) 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->

41、priou; (15) Q=P->next; (16) Q=P->priou; (17) free(P); (18) free(Q); 解： a. (7) (3) (6) (12) b. (8) (4) (5) (13) c. (15) (1) (11) (18) d. (16) (2) (10) (18) e. (14) (9) (17) 2.9 簡(jiǎn)述以下算法的功能。 (1) Status A(LinkedList L) { //L 是無表頭結(jié)點(diǎn)的單鏈表 if(L && L->next) { Q=L; L=L->n

42、ext; 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->next; p->next =s; } void AA(LNode *pa, LNode *pb) { //pa 和 pb 分別指向單循環(huán)鏈表中的兩個(gè)結(jié)點(diǎn) BB(pa,pb); BB(pb,pa); } 解： (

43、1) 如果 L 的長(zhǎng)度不小于 2，將 L 的首元結(jié)點(diǎn)變成尾元結(jié)點(diǎn)。 (2) 將單循環(huán)鏈表拆成兩個(gè)單循環(huán)鏈表。 2.10 指出以下算法中的錯(cuò)誤和低效之處，并將它改寫為一個(gè)既正確又高效的算法。 Status DeleteK(SqList &a,int i,int k) { // 本過程從順序存儲(chǔ)結(jié)構(gòu)的線性表a 中刪除第 i 個(gè)元素起的 k 個(gè)元素 if(i<1||k<0||i+k>a.length) return INFEASIBLE;//  參數(shù)不合法 else { for(count=1;count

44、 // 刪除第一個(gè)元素 for(j=a.length;j>=i+1;j--) a.elem[j-i]=a.elem[j]; a.length--; } return OK; } 解： Status DeleteK(SqList &a,int i,int k) { // 從順序存儲(chǔ)結(jié)構(gòu)的線性表 a 中刪除第 i 個(gè)元素起的 k 個(gè)元素 // 注意 i 的編號(hào)從 0 開始 int j; if(i<0||i>a.length-1||k<0||k>a.length-i) return INFEASIBLE;

45、 for(j=0;j<=k;j++) a.elem[j+i]=a.elem[j+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)r

46、eturn(OVERFLOW); for(i=va.length;i>0,x

47、表。若  A  B  空表，則  A  B ；若  A  =空表，而  B  空表，或者兩者均不為空表，且  A 的首元小于  B  的首元，則  A  B ；否則  A  B 。試寫一個(gè)比較  A ， B 大小的算法。 解： Status CompareOrderList(SqList &A,SqList &B) { int i,k,j; k=A.length>B.length?A.length:

48、B.length; for(i=0;iB.elem[i]) j=1; if(A.elem[i]k) j=1; if(B.length>k) j=-1; if(A.length==B.length) j=0; return j; } 2.13 試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作 Locate(L,x); 解： int LocateElem_L(LinkList &L,ElemType x) {

49、 int i=0; LinkList p=L; while(p&&p->data!=x){ p=p->next; i++; } if(!p) return 0; else return i; } 2.14 試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作 Length(L) 。 解： // 返回單鏈表的長(zhǎng)度 int ListLength_L(LinkList &L) { int i=0; LinkList p=L; if(p) p=p-next; while(p){ p

50、=p->next; i++; } return i; } 2.15 已知指針 ha 和 hb 分別指向兩個(gè)單鏈表的頭結(jié)點(diǎn)，并且已知兩個(gè)鏈表的長(zhǎng)度分別為 m和 n。試寫一算 法將這兩個(gè)鏈表連接在一起， 假設(shè)指針 hc 指向連接后的鏈表的頭結(jié)點(diǎn)， 并要求算法以盡可能短的時(shí)間完成 連接運(yùn)算。請(qǐng)分析你的算法的時(shí)間復(fù)雜度。 解： void MergeList_L(LinkList &ha,LinkList &hb,LinkList &hc) { LinkList pa,pb; pa=ha; pb=hb; while(p

51、a->next&&pb->next){ pa=pa->next; pb=pb->next; } if(!pa->next){ hc=hb; while(pb->next) pb=pb->next; pb->next=ha->next; } else{ hc=ha; while(pa->next) pa=pa->next; pa->next=hb->next; } } 2.16 已知指針 la 和 lb 分別指向兩個(gè)無頭結(jié)點(diǎn)單鏈表中的首元結(jié)點(diǎn)。下列算法是從表 la 中刪除自第 i 個(gè)元素起共 len 個(gè)元素

52、后，將它們插入到表 lb 中第 i 個(gè)元素之前。 試問此算法是否正確？若有錯(cuò)， 請(qǐng)改正之。 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(knext; k++; } q=p; while(k<=len){ q=q->next; k++; } s=lb; k=1; while(knext; k++;

53、 } 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 個(gè)結(jié)點(diǎn) p=la; while(p&&k

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

55、ext=lb; lb=p; } else{ s=lb; k=1; while(s&&knext; k++; } if(!s)return INFEASIBLE; q->next=s->next; s->next=p; // 完成插入 } return OK; } 2.17 試寫一算法，在無頭結(jié)點(diǎn)的動(dòng)態(tài)單鏈表上實(shí)現(xiàn)線性表操作 Insert(L,i,b) ，并和在帶頭結(jié)點(diǎn)的動(dòng)態(tài)單 鏈表上實(shí)現(xiàn)相同操作的算法進(jìn)行比較。 2.18 試寫一算法，實(shí)現(xiàn)線性表操作

56、Delete(L,i) ，并和在帶頭結(jié)點(diǎn)的動(dòng)態(tài)單鏈表上實(shí)現(xiàn)相同操作的算法進(jìn) 行比較。 2.19 已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu)。試寫一高效的算法，刪除表中所有 值大于 mink 且小于 maxk的元素（若表中存在這樣的元素） ，同時(shí)釋放被刪結(jié)點(diǎn)空間， 并分析你的算法的時(shí) 間復(fù)雜度（注意， mink 和 maxk 是給定的兩個(gè)參變量，它們的值可以和表中的元素相同，也可以不同） 。 解： Status ListDelete_L(LinkList &L,ElemType mink,ElemType maxk) { LinkLi

57、st p,q,prev=NULL; if(mink>maxk)return ERROR; p=L; prev=p; p=p->next; while(p&&p->datadata<=mink){ prev=p; p=p->next; } else{ prev->next=p->next; q=p; p=p->next; free(q); } } return OK; } 2.20 同 2.19 題條件，試寫一高效的算法，刪除表中所有值相同的多余元素（使得

58、操作后的線性表中所有 元素的值均不相同） ，同時(shí)釋放被刪結(jié)點(diǎn)空間，并分析你的算法的時(shí)間復(fù)雜度。 解： void ListDelete_LSameNode(LinkList &L) { LinkList p,q,prev; p=L; prev=p; p=p->next; while(p){ prev=p; p=p->next; if(p&&p->data==prev->data){ prev->next=p->next; q=p; p=p->next; free(q); }

59、 } } 2.21 試寫一算法，實(shí)現(xiàn)順序表的就地逆置，即利用原表的存儲(chǔ)空間將線性表  a1 ,  , an  逆置為 an ,  , a1  。 解： // 順序表的逆置 Status ListOppose_Sq(SqList &L) { int i; ElemType x; for(i=0;i

60、L.length-1-i]=x; } return OK; } 2.22 試寫一算法，對(duì)單鏈表實(shí)現(xiàn)就地逆置。 解： // 帶頭結(jié)點(diǎn)的單鏈表的逆置 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; } return OK; } 2.23 設(shè)線性表

61、  A  a1 , a2 ,  , am  ， B  b1 ,b2 ,  ,bn  ，試寫一個(gè)按下列規(guī)則合并  A，B 為線性表 C 的算法，即使得 C a1, b1 ,  , am , bm , bm 1 ,  ,bn  當(dāng) m  n 時(shí)； C a1, b1 ,  , an , bn  , an 1 ,  , am  當(dāng) m  n 時(shí)。

62、線性表 A，B 和 C 均以單鏈表作存儲(chǔ)結(jié)構(gòu)，且 C表利用 A 表和 B 表中的結(jié)點(diǎn)空間構(gòu)成。注意：?jiǎn)捂湵淼拈L(zhǎng)度 值 m和 n 均未顯式存儲(chǔ)。解： // 將合并后的結(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->next;

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

64、tatus ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C) { LinkList pa,pb,qa,qb; pa=A; pb=B; qa=pa; // 保存 qb=pb; // 保存  pa 的前驅(qū)指針 pb 的前驅(qū)指針 pa=pa->next; pb=pb->next; A->next=NULL; C=A; while(pa&&pb){ if(pa->datadata){ qa=pa; pa=pa->n

65、ext; qa->next=A->next; // 將當(dāng)前最小結(jié)點(diǎn)插入 A 表表頭 A->next=qa; } else{ qb=pb; pb=pb->next; qb->next=A->next; // 將當(dāng)前最小結(jié)點(diǎn)插入 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-

66、>next=A->next; A->next=qb; } pb=B; free(pb); return OK; } 2.25 假設(shè)以兩個(gè)元素依值遞增有序排列的線性表 同），現(xiàn)要求另辟空間構(gòu)成一個(gè)線性表 C，其元素為  A 和 B 分別表示兩個(gè)集合（即同一表中的元素值各不相 A 和 B 中元素的交集，且表 C 中的元素有依值遞增有序 排列。試對(duì)順序表編寫求  C 的算法。 解： // 將 A、 B 求交后的結(jié)果放在 C 表中 Status ListCross_Sq(SqList &A,SqList &B,SqList &C) { int i=0,j=0,k=0; while(iB.elem[j]) j++; else{ ListInsert_Sq(C,k,A.elem[i]);