嚴蔚敏數(shù)據(jù)結構題集C語言版答案

可以失敗，不可以失志?？梢允豢梢越^望。只要眷戀奇跡，才會得到奇跡的眷戀。

嚴蔚敏數(shù)據(jù)結構C語言版答案詳解

第1章緒論

1.1簡述下列術語：數(shù)據(jù)

數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結構、存儲結構、數(shù)據(jù)類型和抽象數(shù)據(jù)類型

解：數(shù)據(jù)是對客觀事物的符號表示

在計算機科學中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱

數(shù)據(jù)元素是數(shù)據(jù)的基本單位

在計算機程序中通常作為一個整體進行考慮和處理

數(shù)據(jù)對象是性質相同的數(shù)據(jù)元素的集合

是數(shù)據(jù)的一個子集

數(shù)據(jù)結構是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合

存儲結構是數(shù)據(jù)結構在計算機中的表示

數(shù)據(jù)類型是一個值的集合和定義在這個值集上的?組操作的總稱

抽象數(shù)據(jù)類型是指一個數(shù)學模型以及定義在該模型上的一組操作

是對一般數(shù)據(jù)類型的擴展

1.2試描述數(shù)據(jù)結構和抽象數(shù)據(jù)類型的概念與程序設計語言中數(shù)據(jù)類型概念的區(qū)別

解：抽象數(shù)據(jù)類型包含一般數(shù)據(jù)類型的概念

但含義比一般數(shù)據(jù)類型更廣、更抽象

一般數(shù)據(jù)類型由具體語言系統(tǒng)內(nèi)部定義

直接提供給編程者定義用戶數(shù)據(jù)

因此稱它們?yōu)轭A定義數(shù)據(jù)類型

抽象數(shù)據(jù)類型通常由編程者定義

包括定義它所使用的數(shù)據(jù)和在這些數(shù)據(jù)上所進行的操作

在定義抽象數(shù)據(jù)類型中的數(shù)據(jù)部分和操作部分時

要求只定義到數(shù)據(jù)的邏輯結構和操作說明

不考慮數(shù)據(jù)的存儲結構和操作的具體實現(xiàn)

這樣抽象層次更高

更能為其他用戶提供良好的使用接口

1.3設有數(shù)據(jù)結構(D

R)

其中

試按圖論中圖的畫法慣例畫出其邏輯結構圖

解：

1.4試仿照三元組的抽象數(shù)據(jù)類型分別寫出抽象數(shù)據(jù)類型復數(shù)和有理數(shù)的定義(有理數(shù)是其

分子、分母均為自然數(shù)且分母不為零的分數(shù))

解：

ADTComplex{

數(shù)據(jù)對象：D={r

i|r

i為實數(shù)}

數(shù)據(jù)關系：R={<r

i>}

基本操作：

InitComplex(&C

re

im)

操作結果：構造一個復數(shù)C

其實部和虛部分別為re和im

DestroyCmoplex(&C)

操作結果：銷毀復數(shù)C

Get(C

k

&e)

操作結果：用e返回復數(shù)C的第k元的值

Put(&C

k

e)

操作結果：改變復數(shù)C的第k元的值為e

IsAscending(C)

操作結果：如果復數(shù)C的兩個元素按升序排列

則返回1

否則返回0

IsDescending(C)

操作結果：如果復數(shù)C的兩個元素按降序排列

則返回1

否則返回0

Max(C

&e)

操作結果：用e返回復數(shù)C的兩個元素中值較大的一個

Min(C

&e)

操作結果：用e返回復數(shù)C的兩個元素中值較小的一個

}ADTComplex

ADTRationalNumber{

數(shù)據(jù)對象：D={s

m|s

m為自然數(shù)

且m不為0}

數(shù)據(jù)關系：R={<s

m>}

基本操作：

InitRationalNumber(&R

s

m)

操作結果：構造一個有理數(shù)R

其分子和分母分別為s和m

DestroyRationalNumber(&R)

操作結果：銷毀有理數(shù)R

Get(R

k

&e)

操作結果：用e返回有理數(shù)R的第k元的值

Put(&R

k

e)

操作結果：改變有理數(shù)R的第k元的值為e

IsAscending(R)

操作結果：若有理數(shù)R的兩個元素按升序排列

則返回1

否則返回0

IsDescending(R)

操作結果：若有理數(shù)R的兩個元素按降序排列

則返回1

否則返回0

Max(R

&e)

操作結果：用e返回有理數(shù)R的兩個元素中值較大的一個

Min(R

&e)

操作結果：用e返回有理數(shù)R的兩個元素中值較小的一個

}ADTRationalNumber

1.5試畫出與下列程序段等價的框圖

(1)product=l;i=l;

while(i<=n){

product*=i;

i++;

)

(2)i=0：

do(

i++；

}while((i!=n)&&(a[i]!=x));

(3)switch{

casex<y:z=y-x;break;

casex=y:z=abs(x*y);break;

default:z=(x-y)/abs(x)*abs(y);

)

1.6在程序設計中

常用下列三種不同的出錯處理方式：

(1)用exit語句終止執(zhí)行并報告錯誤；

(2)以函數(shù)的返回值區(qū)別正確返回或錯誤返回；

(3)設置一個整型變量的函數(shù)參數(shù)以區(qū)別正確返回或某種錯誤返回

試討論這三種方法各自的優(yōu)缺點

解：(Dexit常用于異常錯誤處理

它可以強行中斷程序的執(zhí)行

返回操作系統(tǒng)

(2)以函數(shù)的返回值判斷正確與否常用于子程序的測試

便于實現(xiàn)程序的局部控制

(3)用整型函數(shù)進行錯誤處理的優(yōu)點是可以給出錯誤類型

便于迅速確定錯誤

1.7在程序設計中

可采用下列三種方法實現(xiàn)輸出和輸入：

(1)通過scanf和printf語句；

(2)通過函數(shù)的參數(shù)顯式傳遞；

(3)通過全局變量隱式傳遞

試討論這三種方法的優(yōu)缺點

解：(1)用scanf和printf直接進行輸入輸出的好處是形象、直觀

但缺點是需要對其進行格式控制

較為煩瑣

如果出現(xiàn)錯誤

則會引起整個系統(tǒng)的崩潰

(2)通過函數(shù)的參數(shù)傳遞進行輸入輸出

便于實現(xiàn)信息的隱蔽

減少出錯的可能

(3)通過全局變量的隱式傳遞進行輸入輸出最為方便

只需修改變量的值即可

但過多的全局變量使程序的維護較為困難

1.8設n為正整數(shù)

試確定下列各程序段中前置以記號@的語句的頻度：

(1)i=l;k=0;

while(i<=n-l){

@k+=10*i;

i++；

}

(2)i=l;k=0;

do(

?k+=10*i;

i++；

}while(i<=n-l);

⑶i=l;k=0;

while(i<=n-l){

1++；

@k+=10*i;

)

(4)k=0;

for(i=l;i〈=n;i++){

for(j=i;j<=n;j++)

@k++;

}

(5)for(i=l;i〈=n;i++){

for(j=l;j<=i;j++){

for(k=l;k<=j;k++)

@x+=delta;

)

(6)i=l;j=0;

while(i+j<=n){

@if(i>j)j++；

elsei++;

)

(7)x=n;y=0;〃n是不小于1的常數(shù)

while(x>=(y+l)*(y+l)){

@y++;

(8)x=91;y=100;

while(y>0){

@if(x>100){x-=10;y-;}

elsex++;

)

解：⑴n-1

⑵n-1

⑶n-1

(4)n+(n-l)+(n-2)+...+1=

(5)1+(1+2)+(1+2+3)+...+(1+2+3+...+n)=

(6)n

(7)向下取整

(8)1100

1.9假設n為2的乘基

并且n>2

試求下列算法的時間復雜度及變量count的值(以n的函數(shù)形式表示)

intTime(intn){

count=0;x=2;

while(x<n/2){

x*=2;count++;

)

returncount;

)

解：

count=

1.11已知有實現(xiàn)同一功能的兩個算法

其時間復雜度分別為和

假設現(xiàn)實計算機可連續(xù)運算的時間為秒(100多天)

又每秒可執(zhí)行基本操作(根據(jù)這些操作來估算算法時間復雜度)次

試問在此條件下

這兩個算法可解問題的規(guī)模(即n值的范圍)各為多少？哪個算法更適宜？請說明理由

解：n=40

n=16

則對于同樣的循環(huán)次數(shù)n

在這個規(guī)模下

第二種算法所花費的代價要大得多

故在這個規(guī)模下

第一種算法更適宜

1.12設有以下三個函數(shù):

請判斷以下斷言正確與否：

(1)f("O(g(n))

(2)h(n期(f(n))

(3)8(11)是0(11(11))

(4)118)是0(113.5)

(5)h(n)是O(nlogn)

解：⑴對⑵錯⑶錯⑷對⑸錯

1.13試設定若干n值

比較兩函數(shù)和的增長趨勢

并確定n在什么范圍內(nèi)

函數(shù)的值大于的值

解：的增長趨勢快

但在n較小的時候

的值較大

當n>438時

1.14判斷下列各對函數(shù)和

當時

哪個函數(shù)增長更快？

(1)

(2)

(3)

(4)

解:⑴g(n)快(2)g(n)快(3)f(n)快⑷f(n)快

1.15試用數(shù)學歸納法證明：

(1)

(2)

(3)

(4)

1.16試寫一算法

自大至小依次輸出順序讀入的三個整數(shù)X

Y和Z的值

解：

intmax3(intx

inty

intz)

(

if(x>y)

if(x>z)returnx;

elsereturnz;

else

if(y>z)returny;

elsereturnz;

)

1.17一知k階斐波那契序列的定義為

試編寫求k階斐波那契序列的第m項值的函數(shù)算法

k和m均以值調用的形式在函數(shù)參數(shù)表中出現(xiàn)

解：k>0為階數(shù)

n為數(shù)列的第n項

intFibonacci(intk

intn)

(

if(k<l)exit(OVERFLOW);

int*p

x;

p=newint[k+1];

if(!p)exit(OVERFLOW);

inti

J；

for(i=0;i<k+l;i++){

if(i<k-l)p[i]=0;

elsep[i]=l;

}

for(i=k+l;i<n+l;i++){

x=p[0];

for(j=0;j<k;j++)p[j]=p[j+l];

p[k]=2*p[k-l]-x;

returnp[k];

}

1.18假設有A

B

C

D

E五個高等院校進行田徑對抗賽

各院校的單項成績均已存入計算機

并構成一張表

表中每一行的形式為

項目名稱

性別

校名

成績

得分

編寫算法

處理上述表格

以統(tǒng)計各院校的男、女總分和團體總分

并輸出

解：

typedefenum{A

B

C

D

E}SchoolName;

typedefenum{Female

Male)SexType;

typedefstruct{

charevent[3];〃項目

SexTypesex;

SchoolNameschool;

intscore;

}Component;

typedefstruct{

intMaleSum;〃男團總分

intFemaleSum;〃女團總分

intTotalSum;〃團體總分

}Sum;

SumSumScore(SchoolNamesn

Componenta[]

intn)

(

Sumtemp;

temp.MaleSum=0;

temp.FemaleSum=O;

temp.TotalSum=0;

inti;

for(i=0;i<n;i++){

if(a[i].school==sn){

if(a[i].sex=二Male)temp.MaleSum+=a[i].score;

if(a[i].sex二二Female)temp.FemaleSum+=ati].score;

)

)

temp.TotalSum=temp.MaleSum+temp.FemaleSum;

returntemp;

)

1.19試編寫算法

計算的值并存入數(shù)組a[0..arrsizeT]的第iT個分量中(i=l

2

n)

假設計算機中允許的整數(shù)最大值為maxint

則當n>arrsize或對某個

使時

應按出錯處理

注意選擇你認為較好的出錯處理方法

解：

#include<iostream.h>

#include<stdlib.h>

#defineMAXINT65535

#defineArrSize100

intfun(inti);

intmain()

(

inti

k;

inta[ArrSize];

cout?，/Enterk:〃；

cin?k;

if(k>ArrSize-l)exit(0);

for(i=0;i<=k;i++){

if(i==0)a[i]=l;

else{

if(2*i*a[i-l]>MAXINT)exit(0);

elsea[i]=2*i*a[i-l];

}

)

for(i=0;i<=k;i++){

if(a[i]>MAXINT)exit(O);

elsecout?a[i]?/z〃；

)

return0;

)

1.20試編寫算法求一元多項式的值的值

并確定算法中每一語句的執(zhí)行次數(shù)和整個算法的時間復雜度

注意選擇你認為較好的輸入和輸出方法

本題的輸入為

和

輸出為

解：

#include<iostream.h>

#include<stdlib.h>

#defineN10

doublepolynomail(inta[]

inti

doublex

intn);

intmain()

(

doublex;

intn

i；

inta[N];

cout<〈〃輸入變量的值x:〃；

cin>>x;

cout<<〃輸入多項式的階次n:〃；

cin>>n;

if(n>N-l)exit(0);

cout<〈〃輸入多項式的系數(shù)a[0]-a[n]：/z;

for(i=0;i<=n;i++)cin?a[i];

cout?z，Thepolynomailvalueis，z?polynomail(a

n)<<endl;

return0;

)

doublepolynomail(inta[]

inti

doublex

intn)

if(i>0)returna[n-i]+polynomail(a

i-1

x

n)*x;

elsereturna[n];

)

本算法的時間復雜度為o(n)

第2章線性表

2.1描述以下三個概念的區(qū)別：頭指針

頭結點

首元結點(第一個元素結點)

解：頭指針是指向鏈表中第一個結點的指針

首元結點是指鏈表中存儲第一個數(shù)據(jù)元素的結點

頭結點是在首元結點之前附設的一個結點

該結點不存儲數(shù)據(jù)元素

其指針域指向首元結點

其作用主要是為了方便對鏈表的操作

它可以對空表、非空表以及首元結點的操作進行統(tǒng)一處理

2.2填空題

解：(1)在順序表中插入或刪除一個元素

需要平均移動表中一半元素

具體移動的元素個數(shù)與元素在表中的位置有關

(2)順序表中邏輯上相鄰的元素的物理位置必定緊鄰

單鏈表中邏輯上相鄰的元素的物理位置不一定緊鄰

(3)在單鏈表中

除了首元結點外

任一結點的存儲位置由其前驅結點的鏈域的值指示

(4)在單鏈表中設置頭結點的作用是插入和刪除首元結點時不用進行特殊處理

2.3在什么情況下用順序表比鏈表好？

解：當線性表的數(shù)據(jù)元素在物理位置上是連續(xù)存儲的時候

用順序表比用鏈表好

其特點是可以進行隨機存取

2.4對以下單鏈表分別執(zhí)行下列各程序段

并畫出結果示意圖

解:

2.5畫出執(zhí)行下列各行語句后各指針及鏈表的示意圖

L=(LinkList)malloc(sizeof(LNode));P=L;

for(i=l;i<=4;i++){

P->next=(LinkList)malloc(sizeof(LNode));

P=P->next;P->data=i*2-l;

)

P->next=NULL;

for(i=4;i>=l;i-)InsLinkList(L

i+1

i*2);

for(i=l;i〈=3;i++)Del_LinkList(L

i)；

解：

2.6已知L是無表頭結點的單鏈表

且P結點既不是首元結點

也不是尾元結點

試從下列提供的答案中選擇合適的語句序列

a.在P結點后插入S結點的語句序列是—

b.在P結點前插入S結點的語句序列是

c.在表首插入S結點的語句序列是—

d.在表尾插入S結點的語句序列是—

(1)P->next=S;

(2)P->next=P->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)

d.(9)(1)(6)

2.7已知L是帶表頭結點的非空單鏈表

月.P結點既不是首元結點

也不是尾元結點

試從下列提供的答案中選擇合適的語句序列

a.刪除P結點的直接后繼結點的語句序列是—

b.刪除P結點的直接前驅結點的語句序列是—

c.刪除P結點的語句序列是—

d.刪除首元結點的語句序列是

e.刪除尾元結點的語句序列是

(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)whi1e(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->next!=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結點是某雙向鏈表的中間結點

試從下列提供的答案中選擇合適的語句序列

a.在P結點后插入S結點的語句序列是—

b.在P結點前插入S結點的語句序列是

c.刪除P結點的直接后繼結點的語句序列是—

d.刪除P結點的直接前驅結點的語句序列是—

e.刪除P結點的語句序列是—

(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)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.(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簡述以下算法的功能

(1)StatusA(LinkedListL){〃1>是無表頭結點的單鏈表

if(L&&L->next){

Q=L;L=L->next;P=L;

while(P->next)P=P->next;

P->next=Q;Q->next=NULL;

)

returnOK;

)

(2)voidBB(LNode*s

LNode*q){

P=s;

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

p->next=s;

)

voidAA(LNode*pa

LNode*pb){

//pa和pb分別指向單循環(huán)鏈表中的兩個結點

BB(pa

pb);

BB(pb

pa);

)

解：(1)如果L的長度不小于2

將L的首元結點變成尾元結點

(2)將單循環(huán)鏈表拆成兩個單循環(huán)鏈表

2.10指出以下算法中的錯誤和低效之處

并將它改寫為一個既正確又高效的算法

StatusDeleteK(SqList&a

inti

intk)

(

〃本過程從順序存儲結構的線性表a中刪除第i個元素起的k個元素

if(i<l||k<01|i+k>a.length)returnINFEASIBLE;〃參數(shù)不合法

else{

for(count=1;count<k;count++){

〃刪除第一個元素

for(j=a.length;j>=i+l;j--)a.elem[j-i]=a.elem[j];

a.length—;

)

returnOK;

)

解：

StatusDeleteK(SqList&a

inti

intk)

{

//從順序存儲結構的線性表a中刪除第i個元素起的k個元素

〃注意i的編號從0開始

intj;

if(i<01|i>a.length-11|k<0k>a.length-i)returnINFEASIBLE;

for(j=0;j<=k;j++)

a.elem[j+i]=a.elem[j+i+k];

a.length=a.length-k;

returnOK;

}

2.11設順序表va中的數(shù)據(jù)元素遞增有序

試寫一算法

將x插入到順序表的適當位置上

以保持該表的有序性

解：

StatusInsertOrderList(SqList&va

ElemTypex)

(

〃在非遞減的順序表va中插入元素x并使其仍成為順序表的算法

inti;

if(va.length-va.listsize)return(OVERFLOW);

for(i=va.length;i>0

x<va.elem[i-l];i-)

va.elem[i]=va.elem[i-l];

va.elem[i]=x;

va.length++;

returnOK;

)

2.12設和均為順序表

和分別為和中除去最大共同前綴后的子表

若空表

則；若=空表

而空表

或者兩者均不為空表

且的首元小于的首元

則；否則

試寫一個比較

大小的算法

解：

StatusCompareOrderList(SqList&A

SqList&B)

(

inti

k

J；

k=A.length>B.length?A.length:B.length;

for(i=0;i<k;i++){

if(A.>B.elem[i])j=l;

if(A.elem[i]<B.elem[i])j=-l;

)

if(A.length>k)j=l;

if(B.length>k)j=-l;

if(A.length=B.length)j=0;

returnj;

)

2.13試寫一算法在帶頭結點的單鏈表結構上實現(xiàn)線性表操作Locate。，

x);

解：

intLocateElemL(LinkList&L

ElemTypex)

(

inti=0;

LinkListp=L;

while(p&&p->data!=x){

p=p->next;

i++；

}

if(!p)return0;

elsereturni;

}

2.14試寫一算法在帶頭結點的單鏈表結構上實現(xiàn)線性表操作Length(L)

解：

〃返回單鏈表的長度

intListLength_L(LinkList&L)

{

inti=0;

LinkListp=L;

if(p)p=p-next;

while(p){

p=p->next;

i++；

}

returni;

2.15已知指針ha和hb分別指向兩個單鏈表的頭結點

并且已知兩個鏈表的長度分別為m和n

試寫?算法將這兩個鏈表連接在一起

假設指針he指向連接后的鏈表的頭結點

并要求算法以盡可能短的時間完成連接運算

請分析你的算法的時間復雜度

解：

voidMergeList_L(LinkList&ha

LinkList&hb

LinkList&hc)

(

LinkListpa

pb;

pa=ha;

pb=hb;

while(pa->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{

he二ha;

while(pa->next)pa=pa->next;

pa->next=hb->next;

}

)

2.16已知指針la和lb分別指向兩個無頭結點單鏈表中的首元結點

下列算法是從表la中刪除自第i個元素起共len個元素后

將它們插入到表1b中第i個元素之前

試問此算法是否正確？若有錯

請改正之

StatusDeleteAndlnsertSub(LinkedListla

LinkedListlb

inti

intj

intlen)

if(i<0||j<0||len<0)returnINFEASIBLE;

p=la;k=l;

while(k<i){p=p->next;k++;}

q二P；

while(k<=len){q=q->next;k++;}

s=lb;k=l;

while(k<j){s=s->next;k++;}

s->next=p;q->next=s->next;

returnOK;

解：

StatusDeleteAndlnsertSub(LinkList&la

LinkList&lb

inti

intj

intlen)

(

LinkListp

q

s

prev=NULL;

intk=l;

if(i<0||j<0||len<0)returnINFEASIBLE;

//在la表中查找第i個結點

P二la;

while(p&&k<i){

prev=p;

p=p->next;

k++;

}

if(!p)returnINFEASIBLE;

//在la表中查找第i+len-l個結點

q=P；k=1;

while(q&&k<len){

q=p->next;

k++;

if(!q)returnINFEASIBLE;

//完成刪除

注意

i=l的情況需要特殊處理

if(!prev)la=q->next;

elseprev->next=q->next;

//將從la中刪除的結點插入到lb中

if(j=l){

q->next=lb;

lb=p;

)

else{

s=lb;k=l;

while(s&&k<j-1){

s=s->next;

k++;

)

if(!s)returnINFEASIBLE;

q->next=s->next;

s->next=p;〃完成插入

)

returnOK;

}

2.17試寫一算法

在無頭結點的動態(tài)單鏈表上實現(xiàn)線性表操作Insert(L

i

b)

并和在帶頭結點的動態(tài)單鏈表上實現(xiàn)相同操作的算法進行比較

2.18試寫一算法

實現(xiàn)線性表操作Delete(L

i)

并和在帶頭結點的動態(tài)單鏈表上實現(xiàn)相同操作的算法進行比較

2.19已知線性表中的元素以值遞增有序排列

并以單鏈表作存儲結構

試寫?高效的算法

刪除表中所有值大于mink且小于maxk的元素(若表中存在這樣的元素)

同時釋放被刪結點空間

并分析你的算法的時間復雜度(注意

mink和maxk是給定的兩個參變量

它們的值可以和表中的元素相同

也可以不同)

解：

StatusListDelete_L(LinkList&L

ElemTypemink

ElemTypemaxk)

LinkListp

q

prev=NULL;

if(mink>maxk)returnERROR;

P二L;

prev=p;

p=p->next;

while(p&&p->data<maxk){

if(p->data<=mink){

prev=p;

p=p->next;

)

else{

prev->next=p->next;

q二P；

p=p->next;

free(q);

)

)

returnOK;

)

2.20同2.19題條件

試寫一高效的算法

刪除表中所有值相同的多余元素(使得操作后的線性表中所有元素的值均不相同)

同時釋放被刪結點空間

并分析你的算法的時間復雜度

解：

voidListDelete_LSameNode(LinkList&L)

(

LinkListp

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);

}

)

2.21試寫一算法

實現(xiàn)順序表的就地逆置

即利用原表的存儲空間將線性表逆置為

解：

〃順序表的逆置

StatusListOppose_Sq(SqList&L)

(

inti;

ElemTypex;

for(i=0;i<L.length/2;i++){

x=L.elem[i];

L.elem[i]=L.elem[L.length-l-i];

L.elem[L.length-l-i]=x;

)

returnOK;

}

2.22試寫一算法

對單鏈表實現(xiàn)就地逆置

解：

//帶頭結點的單鏈表的逆置

StatusListOppose_L(LinkList&L)

{

LinkListp

q；

P=L;

p=zp->next;

L->next=NULL;

while(p){

q二P；

p=p->next;

q->next=L->next;

L->next=q;

)

returnOK;

)

2.23設線性表

試寫一個按下列規(guī)則合并A

B為線性表C的算法

即使得

當時;

當時

線性表A

B和C均以單鏈表作存儲結構

且C表利用A表和B表中的結點空間構成

注意：單鏈表的長度值m和n均未顯式存儲

解：

//將合并后的結果放在C表中

并刪除B表

StatusListMergeL(LinkList&A

LinkList&B

LinkList&C)

(

LinkListpa

pb

qa

qb;

pa=A->next;

pb=B->next;

C二;A

while(pa&&pb){

qa二pa;qb=pb;

pa=pa->next;pb=pb->next;

qb->next=qa->next;

qa->next=qb;

)

if(!pa)qb->next=pb;

pb=B;

free(pb);

returnOK;

)

2.24假設有兩個按元素值遞增有序排列的線性表A和B

均以單鏈表作存儲結構

請編寫算法將A表和B表歸并成一個按元素值遞減有序(即非遞增有序

允許表中含有值相同的元素)排列的線性表C

并要求利用原表(即A表和B表)的結點空間構造C表

解：

//將合并逆置后的結果放在C表中

并刪除B表

StatusListMergeOppose_L(LinkList&A

LinkList&B

LinkList&C)

LinkListpa

qa

qb;

pa=A;

pb=B;

qa=pa;//保存pa的前驅指針

qb=pb;//保存pb的前驅指針

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;〃將當前最小結點插入A表表頭

A->next=qa;

}

else{

qb=pb;

pb=pb->next;

qb->next=A->next;〃將當前最小結點插入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);

returnOK;

2.25假設以兩個元素依值遞增有序排列的線性表A和B分別表示兩個集合（即同一表中的元

素值各不相同)

現(xiàn)要求另辟空間構成一個線性表C

其元素為A和B中元素的交集

且表C中的元素有依值遞增有序排列

試對順序表編寫求C的算法

解：

//將A、B求交后的結果放在C表中

StatusListCrossSq(SqList&A

SqList&B

SqList&C)

(

inti=0

j=0

k=0;

while(i<A.length&&j<B.length){

if(A.elem[i]<B.elem[j])i++;

else

if(A.elem[i]；>B.elem[j])j++;

else{

ListInsert_Sq(C

k

A.elem[i]);

i++;

k++;

)

)

returnOK;

)

2.26要求同2.25題

試對單鏈表編寫求C的算法

解：

〃將A、B求交后的結果放在C表中

并刪除B表

StatusListCross_L(LinkList&A

LinkList&B

LinkList&C)

(

LinkListpa

pb

qa

qb

pt;

pa=A;

pb二B;

qa=pa;//保存pa的前驅指針

qb=pb;//保存pb的前驅指針

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(

qa=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);

returnOK;

)

2.27對2.25題的條件作以下兩點修改

對順序表重新編寫求得表C的算法

(1)假設在同一表(A或B)中可能存在值相同的元素

但要求新生成的表C中的元素值各不相同；

(2)利用A表空間存放表C

解：

(1)

//A、B求交

然后刪除相同元素

將結果放在C表中

StatusListCrossDe1SameSq(SqList&A

SqList&B

SqList&C)

(

inti=0

j=0

k=0;

while(i<A.length&&j<B.length){

if(A.elem[i]<B.elem[j])i++;

else

if(A.elem[i]>B.elem[j])j++;

else{

if(C.length==0){

ListInsert_Sq(C

k

A.elem[i]);

k++;

)

else

if(C.elem[C.length-1]!=A.elem[i]){

ListInsert_Sq(C

k

A.elem[i]);

k++：

}

i++；

)

}

returnOK;

}

(2)

//A、B求交

然后刪除相同元素

將結果放在A表中

StatusListCrossDe1SameSq(SqList&A

SqList&B)

{

inti=0

j=0

k=0;

while(i<A.length&&j<B.length){

if(A.elem[i]<B.elem[j])i++;

else

if(A.elem[i]>B.elem[j])j++;

else{

if(k==0){

A.elem[k]=A.elem[i];

k++;

}

else

if(A.elem[k]!=A.elem[i]){

A.elem[k]=A.elem[i];

k++;

)

i++；

)

)

A.length=k;

returnOK;

}

2.28對2.25題的條件作以下兩點修改

對單鏈表重新編寫求得表C的算法

(1)假設在同一表(A或B)中可能存在值相同的元素

但要求新生成的表C中的元素值各不相同；

(2)利用原表(A表或B表)中的結點構成表C

并釋放A表中的無用結點空間

解：

(1)

//A、B求交

結果放在C表中

并刪除相同元素

StatusListCrossDelSame_L(LinkList&A

LinkList&B

LinkList&C)

LinkListpa

pb

qa

qb

pt;

pa=A;

pb=B;

qa=pa;//保存pa的前驅指針

qb=pb;//保存pb的前驅指針

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;

pa=pa->next;

qa->next=pa;

free(pt);

while(pb){

pt=pb;

pb=pb->next;

qb->next=pb;

free(pt);

)

pb=B;

free(pb);

returnOK;

)

(2)

//A、B求交

結果放在A表中

并刪除相同元素

StatusListCrossDelSameL(LinkList&A

LinkList&B)

(

LinkListpa

pb

qa

qb

pt;

pa=A;

pb二B;

qa=pa;//保存pa的前驅指針

qb二pb;//保存pb的前驅指針

pa=pa->next;

pb=pb->next;

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;

pa=pa->next;

qa->next=pa;

free(pt);

)

while(pb){

pt=pb;

pb=pb->next;

qb->next=pb;

free(pt);

}

pb=B;

free(pb);

returnOK;

}

2.29已知A

B和C為三個遞增有序的線性表

現(xiàn)要求對A表作如下操作：刪去那些既在B表中出現(xiàn)又在C表中出現(xiàn)的元素

試對順序表編寫實現(xiàn)上述操作的算法

并分析你的算法的時間復雜度(注意：題中沒有特別指明同一表中的元素值各不相同)

解：

//在A中刪除既在B中出現(xiàn)又在C中出現(xiàn)的元素

結果放在D中

StatusListUnion_Sq(SqList&D

SqList&A

SqList&B

SqList&C)

(

SqListTemp;

InitList_Sq(Temp);

ListCross_L(B

c

Temp);

ListMinusL(A

Temp

D);

)

2.30要求同2.29題

試對單鏈表編寫算法

請釋放A表中的無用結點空間

解：

//在A中刪除既在B中出現(xiàn)又在C中出現(xiàn)的元素

并釋放B、C

StatusListUnion_L(LinkList&A

LinkList&B

LinkList&C)

(

ListCross_L(B

O;

ListMinus_L(A

B);

)

//求集合A-B

結果放在A表中

并刪除B表

StatusListMinus_L(LinkList&A

LinkList&B)

(

LinkListpa

Pb

qa

qb

pt；

pa=A;

pb=B;

qa=pa;//保存pa的前驅指針

qb=pb;//保存pb的前驅指針

pa=pa->next;

pb=pb->next;

while(pa&&pb){

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

pt=pb;

pb=pb->next;

qb->next=pb;

free(pt);

else

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

qa=pa;

pa=pa->next;

)

else(

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);

returnOK;

)

2.31假設某個單向循環(huán)鏈表的長度大于1

且表中既無頭結點也無頭指針

已知s為指向鏈表中某個結點的指針

試編寫算法在鏈表中刪除指針s所指結點的前驅結點

解：

//在單循環(huán)鏈表S中刪除S的前驅結點

StatusListDelete_CL(LinkList&S)

(

LinkListp

q；

if(S==S->next)returnERROR;

q=S;

p=S->next;

while(p->next!=S){

q=P；

p=p->next;

)

q->next=p->next;

free(p);

returnOK;

)

2.32已知有一個單向循環(huán)鏈表

其每個結點中含三個域：pre

data和next

其中data為數(shù)據(jù)域

next為指向后繼結點的指針域

pre也為指針域

但它的值為空

試編寫算法將此單向循環(huán)鏈表改為雙向循環(huán)鏈表

即使pre成為指向前驅結點的指針域

解：

//建立一個空的循環(huán)鏈表

StatusInitListDL(DuLinkList&L)