數(shù)據(jù)結(jié)構(gòu)題集答案

第1章緒論

1.1簡述下列術(shù)語：數(shù)據(jù)，數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)、數(shù)據(jù)類型和抽象數(shù)據(jù)類型。

解：數(shù)據(jù)是對客觀事物的符號表示。在計算機(jī)科學(xué)中是指所有能輸入到計算機(jī)中并被計算機(jī)程序處理的符

號的總稱。

數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計算機(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)在計算機(jī)中的表示。

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

抽象數(shù)據(jù)類型是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。是對一般數(shù)據(jù)類型的擴(kuò)展。

1.2試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念與程序設(shè)計語言中數(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ù)據(jù)的邏輯結(jié)構(gòu)和操作說明，不考慮數(shù)據(jù)的存儲結(jié)構(gòu)和操作的具體實

現(xiàn)，這樣抽象層次更高，更能為其他用戶提供良好的使用接口。

1.3設(shè)有數(shù)據(jù)結(jié)構(gòu)(D,R),其中

D={d1,d2,d3,d4},7?={r},r={(Jl,J2),(J2,J3),(J3,J4)}

試按圖論中圖的畫法慣例畫出其邏輯結(jié)構(gòu)圖。

解：

—*(5?)-->(d3)---

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

為自然數(shù)且分母不為零的分?jǐn)?shù))。

解：

ADTComplex!

數(shù)據(jù)對象：D={r,i|r,i為實數(shù)}

數(shù)據(jù)關(guān)系：R=?r,i?

基本操作：

InitComplex(&C,re,im)

操作結(jié)果：構(gòu)造一個復(fù)數(shù)C,其實部和虛部分別為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的兩個元素按升序排列，則返回1,否則返回0

IsDescending(C)

操作結(jié)果：如果復(fù)數(shù)C的兩個元素按降序排列，則返回1,否則返回0

Max(C,&e)

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

Min(C,&e)

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

}ADTComplex

ADTRationalNumber{

數(shù)據(jù)對象：D={s,m|s,m為自然數(shù)，且m不為0}

數(shù)據(jù)關(guān)系：R={<s,m>}

基本操作：

InitRationa1Number(&R,s,m)

操作結(jié)果：構(gòu)造一個有理數(shù)R,其分子和分母分別為s和m

DestroyRationalNumber(&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的兩個元素按升序排列，則返回1,否則返回0

IsDescending(R)

操作結(jié)果：若有理數(shù)R的兩個元素按降序排列，則返回1,否則返回0

Max(R,&e)

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

Min(R,&e)

操作結(jié)果：用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在程序設(shè)計中，常用下列三種不同的出錯處理方式：

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

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

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

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

解：(l)exit常用于異常錯誤處理，它可以強(qiáng)行中斷程序的執(zhí)行，返回操作系統(tǒng)。

(2)以函數(shù)的返回值判斷正確與否常用于子程序的測試，便于實現(xiàn)程序的局部控制。

(3)用整型函數(shù)進(jìn)行錯誤處理的優(yōu)點(diǎn)是可以給出錯誤類型，便于迅速確定錯誤。

1.7在程序設(shè)計中，可采用下列三種方法實現(xiàn)輸出和輸入：

(1)通過scanf和printf語句；

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

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

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

解：(1)用scanf和printf直接進(jìn)行輸入輸出的好處是形象、直觀，但缺點(diǎ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=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);

(3)i=l;k=0;

while(i<=n-l){

i++；

@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+1)*(y+1)){

@y++;

)

(8)x=91;y=100;

while(y>0){

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

elsex++;

)

解：(1)n-l

⑵n-1

(3)n-1

n(n+1)

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

2

⑸l+(l+2)+(l+2+3)+..+(1+2+3+...+n)=〉:

i=l2

=萬1??+1)=汽(/+，)=萬1?2+萬1?

乙/=1乙/=!乙/=1乙/=1

二一n(n+1)(2〃+1)+'n(n+1)=—n(n+1)(2〃+3)

12412

(6)n

(7)|_VnJ向下取整

(8)1100

1.9假設(shè)n為2的乘幕，并且n>2,試求下列算法的時間復(fù)雜度及變量count的值(以n的函數(shù)形式表示)。

intTime(intn){

count=0;x=2;

while(x<n/2){

x*=2：count";

)

returncount;

)

解：67(log2n)

count=

log2—2

1.11已知有實現(xiàn)同一功能的兩個算法，其時間復(fù)雜度分別為。（2"）和。（儲°）,假設(shè)現(xiàn)實計算機(jī)可連續(xù)

運(yùn)算的時間為1()7秒(100多天)，又每秒可執(zhí)行基本操作(根據(jù)這些操作來估算算法時間復(fù)雜度)1()5次。

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

解：2"=101?n=40

，嚴(yán)=IO'2n=16

則對于同樣的循環(huán)次數(shù)n,在這個規(guī)模下，第二種算法所花費(fèi)的代價要大得多。故在這個規(guī)模下，第

一種算法更適宜。

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

/(n)=21/74+n2+1000,g(〃)=IS//+500//,〃(〃)=500〃=+“l(fā)og”

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

(1)￡(11)是0(8(11))

(2)乂0是06(2)

(3)8(0是0016))

(4)h(n)是0(n*

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

解：⑴對⑵錯⑶錯⑷對(5)錯

1.13試設(shè)定若干n值，比較兩函數(shù)〃2和50〃log2”的增長趨勢，并確定n在什么范圍內(nèi)，函數(shù)〃2的值

大于50〃log2n的值。

解：〃2的增長趨勢快。但在門較小的時候，50〃10g?〃的值較大。

當(dāng)n>438時，〃2>50〃log2〃

1.14判斷下列各對函數(shù)/(")和g(〃)，當(dāng)〃—oo時，哪個函數(shù)增長更快？

(1)/(“"IO/+ln(〃!+10"),g(〃)=2〃4+〃+7

(2)f(n)=(ln(n!)+5)2,g(〃)=13n25

(3)f(n)=n2'+-xln4+1,g(n)=(ln(n!))2+n

(4)/(”)=)+(2",g(〃)=

解：(l)g(n)快(2)g(n)快⑶f(n)快(4)f(n)快

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

(1)>+1*2〃+1)/6(n>0)

<=i

⑵=(xn+,-l)/(x-l)(X1,72>0)

/=0

⑶力1=2"-1(/?>1)

/=1

(4)Z⑵-I”"？("21)

i=l

L16試寫一算法，自大至小依次輸出順序讀入的三個整數(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階斐波那契序列的定義為

/o=，/I=0,=0,=1；

。fk_2fk一i

/"=fn-\+f,,-2+1,,+fn-k'n=k,k+].,???

試編寫求k階斐波那契序列的第m項值的函數(shù)算法，k和m均以值調(diào)用的形式在函數(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];

}

L18假設(shè)有A,B,C,D,E五個高等院校進(jìn)行田徑對抗賽，各院校的單項成績均己存入計算機(jī)，并構(gòu)成一

張表，表中每一行的形式為

I項目名稱I性別I校名I成績I得分I

編寫算法，處理上述表格，以統(tǒng)計各院校的男、女總分和團(tuán)體總分，并輸出。

解：

typedefenum{A,B,C,D,E}SchoolName;

typedefenum{Female,Male}SexType;

typedefstruct{

charevent[3];〃項目

SexTypesex;

SchooINameschool;

intscore;

}Component;

typedefstruct(

intMaleSum;〃男團(tuán)總分

intFemaleSum;〃女團(tuán)總分

intTotalSum;〃團(tuán)體總分

}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+=a[i].score;

)

)

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

returntemp;

)

1.19試編寫算法，計算，!*2'的值并存入數(shù)組a[O..arrsize-l]的第i-1個分量中(i=l,2，…,n)。假設(shè)計

算機(jī)中允許的整數(shù)最大值為maxint,則當(dāng)n〉arrsize或?qū)δ硞€人(1W攵W〃)，使人!>maxint時，

應(yīng)按出錯處理。注意選擇你認(rèn)為較好的出錯處理方法。

解：

#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=O;i<=k;i++){

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

else

)

return0;

)

1.20試編寫算法求一元多項式的值4(X)=Z%X'的值勺(%)，并確定算法中每一語句的執(zhí)行次數(shù)

i=0

和整個算法的時間復(fù)雜度。注意選擇你認(rèn)為較好的輸入和輸出方法。本題的輸入為為G=oj,???,〃)，X。

和〃，輸出為乙(Xo)。

解：

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

coul<〈”輸入多項式的系數(shù)a[0]-a[n]:";

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

cout?/zThepolynomailvalueis/z?polynomail(a,n,x,n)?endl;

return0;

)

doublepolynomail(inta[],inti,doublex,intn)

(

if(i>0)returna[n-i]+polynomail(a,i-1,x,n)*x;

elsereturna[n];

)

本算法的時間復(fù)雜度為。(n).

第2章線性表

2.1描述以下三個概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元結(jié)點(diǎn)(第一個元素結(jié)點(diǎn))。

解：頭指針是指向鏈表中第一個結(jié)點(diǎn)的指針。首元結(jié)點(diǎn)是指鏈表中存儲第一個數(shù)據(jù)元素的結(jié)點(diǎn)。頭結(jié)

點(diǎn)是在首元結(jié)點(diǎn)之前附設(shè)的一個結(jié)點(diǎn)，該結(jié)點(diǎn)不存儲數(shù)據(jù)元素，其指針域指向首元結(jié)點(diǎn)，其作用主要是為

了方便對鏈表的操作。它可以對空表、非空表以及首元結(jié)點(diǎn)的操作進(jìn)行統(tǒng)一處理。

2.2填空題。

解：(D在順序表中插入或刪除一個元素，需要平均移動表中一表元素,具體移動的元素個數(shù)與遜

在表中的位置代夫.

(2)順序表中邏輯上相鄰的元素的物理位置遜緊鄰。單鏈表中邏輯上相鄰的元素的物理位置正定

緊鄰。

(3)在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲位置由其榷紿點(diǎn)的集域物g指示。

(4)在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是插入和刪除首元結(jié)點(diǎn)時不用進(jìn)行特殊處理.

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

解：當(dāng)線性表的數(shù)據(jù)元素在物理位置上是連續(xù)存儲的時候，用順序表比用鏈表好，其特點(diǎn)是可以進(jìn)行

隨機(jī)存取。

2.4對以下單鏈表分別執(zhí)行下列各程序段，并畫出結(jié)果示意圖。

L

L

PQRS

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—)Ins_LinkList(L,i+1,i*2);

for(i=l;i<=3;i++)Del_LinkList(L,i);

解：

L-?

p

L—?―>1——>3——>5——>7A

丁

P

L—?―?2——?4——?6——?7——?8A

丁

P

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)的語句序列是o

b.在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語句序列是O

c.在表首插入S結(jié)點(diǎn)的語句序列是。

d.在表尾插入S結(jié)點(diǎn)的語句序列是o

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

(⑵L=S;

(13)L=P;

解：a.(4)(1)

b.(7)(11)(8)(4)(1)

c.(5)(12)

d.(9)(1)(6)

2.7已知L是帶表頭結(jié)點(diǎn)的非空單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列提供的答

案中選擇合適的語句序列。

a.刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列是。

b.刪除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語句序列是。

c.刪除P結(jié)點(diǎn)的語句序列是。

d.刪除首元結(jié)點(diǎn)的語句序列是。

e.刪除尾元結(jié)點(diǎn)的語句序列是o

(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->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結(jié)點(diǎn)是某雙向鏈表的中間結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語句序列。

a.在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語句序列是o

b.在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語句序列是o

c.刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列是0

d.刪除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語句序列是o

e.刪除P結(jié)點(diǎn)的語句序列是。

(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){〃L是無表頭結(jié)點(diǎn)的單鏈表

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)鏈表中的兩個結(jié)點(diǎn)

BB(pa,pb);

BB(pb,pa);

)

解：(1)如果L的長度不小于2,將L的首元結(jié)點(diǎn)變成尾元結(jié)點(diǎn)。

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

2.10指出以下算法中的錯誤和低效之處，并將它改寫為一個既正確又高效的算法。

StatusDeleteK(SqList&a,inti,intk)

(

〃本過程從順序存儲結(jié)構(gòu)的線性表a中刪除第i個元素起的k個元素

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

else{

for(count=l;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)

(

〃從順序存儲結(jié)構(gòu)的線性表a中刪除第i個元素起的k個元素

〃注意i的編號從。開始

intj;

if(i<0||i>a.length-1I|k<0iIk>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設(shè)順序表va中的數(shù)據(jù)元素遞增有序。試寫一算法，將x插入到順序表的適當(dāng)位置上，以保持該表的

有序性。

解：

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設(shè)A=(%,…,％,)和8=(A，…也)均為順序表，4和6'分別為A和8中除去最大共同前

綴后的子表.若A'=B'=空表，則A=B；若4=空表，而B'w空表，或者兩者均不為空表，且A'

的首元小于6'的首元，則A<8；否則A>6。試寫一個比較A,6大小的算法。

解：

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.elem[i]>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試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實現(xiàn)線性表操作Located,x);

解：

intLocateElemL(LinkUst&L,ElemTypex)

(

inti=0;

LinkListp=L;

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

p=p->next;

i++；

)

if(!p)return0;

elsereturni;

)

2.14試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實現(xiàn)線性表操作Length(L)o

解：

〃返回單鏈表的長度

intListLength_L(LinkList&L)

(

inti=0;

LinkListp=L;

if(p)p=p-next;

while(p){

p=p->next;

i++；

)

returni;

)

2.15己知指針ha和hb分別指向兩個單鏈表的頭結(jié)點(diǎn)，并且己知兩個鏈表的長度分別為m和n。試寫一算

法將這兩個鏈表連接在一起，假設(shè)指針he指向連接后的鏈表的頭結(jié)點(diǎn)，并要求算法以盡可能短的時間完成

連接運(yùn)算。請分析你的算法的時間復(fù)雜度。

解：

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分別指向兩個無頭結(jié)點(diǎn)單鏈表中的首元結(jié)點(diǎn)。下列算法是從表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,int1en)

LinkListp,q,s,prev=NULL;

intk=l;

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

//在la表中查找第i個結(jié)點(diǎn)

pTa;

while(p&&k<i){

prev=p;

p=p->next;

k++;

}

if(!p)returnINFEASIBLE;

//在la表中查找第i+lenT個結(jié)點(diǎn)

q=P；k=l;

while(q&&k<len){

q=p->next;

k++;

)

if(!q)returnINFEASIBLE;

//完成刪除，注意，i=l的情況需要特殊處理

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

elseprev->next=q->next;

//將從la中刪除的結(jié)點(diǎn)插入到lb中

if(j=l){

q->next=lb;

lb=p;

)

else{

s=lb;k=l;

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

s=s->next;

k++;

)

if(!s)returnINFEASIBLE;

q->next=s->next;

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

}

returnOK;

}

2.17試寫一算法，在無頭結(jié)點(diǎn)的動態(tài)單鏈表上實現(xiàn)線性表操作Insert(L,i,b),并和在帶頭結(jié)點(diǎn)的動態(tài)單

鏈表上實現(xiàn)相同操作的算法進(jìn)行比較。

2.18試寫一算法，實現(xiàn)線性表操作Deleted,i),并和在帶頭結(jié)點(diǎn)的動態(tài)單鏈表上實現(xiàn)相同操作的算法進(jìn)

行比較。

2.19已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試寫一高效的算法，刪除表中所有

值大于mink且小于maxk的元素(若表中存在這樣的元素)，同時釋放被刪結(jié)點(diǎn)空間，并分析你的算法的時

間復(fù)雜度(注意，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題條件，試寫一高效的算法，刪除表中所有值相同的多余元素(使得操作后的線性表中所有

元素的值均不相同)，同時釋放被刪結(jié)點(diǎn)空間，并分析你的算法的時間復(fù)雜度。

解：

voidUstDelete_LSameNode(LinklJst&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.;

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

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

)

returnOK;

}

2.22試寫一算法，對單鏈表實現(xiàn)就地逆置。

解：

//帶頭結(jié)點(diǎn)的單鏈表的逆置

StatusListOppose_L(LinkList&L)

(

LinkListp,q;

P=L；

p=p->next;

L->next=NULL;

while(p){

q二P；

p=p->next;

q->next=L->next;

L->next=q;

)

returnOK;

)

2.23設(shè)線性表A=(%,電,???,%,)，6=(由也，…也)，試寫一個按下列規(guī)則合并A,B為線性表

C的算法，即使得

C={a1,bl,---,am,b,n,bin+i,--,hn)當(dāng)機(jī)<〃時；

C=(al,b],---,a?,b?,an+},---,am)當(dāng)機(jī)〉〃時。

線性表A,B和C均以單鏈表作存儲結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點(diǎn)空間構(gòu)成。注意：單鏈表的長度

值m和n均未顯式存儲。

解：

//將合并后的結(jié)果放在C表中，并刪除B表

StatusListMerge_L(LinkIJst&A,LinkList&.B,LinkList&C)

LinkListpa,pb,qa,qb;

pa=A->next;

pb=B->next;

C=A;

whi1e(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假設(shè)有兩個按元素值遞增有序排列的線性表A和B,均以單鏈表作存儲結(jié)構(gòu)，請編寫算法將A表和B

表歸并成一個按元素值遞減有序(即非遞增有序，允許表中含有值相同的元素)排列的線性表C,并要求

利用原表(即A表和B表)的結(jié)點(diǎn)空間構(gòu)造C表。

解：

//將合并逆置后的結(jié)果放在C表中，并刪除B表

StatusListMergeOppose_L(LinkList&A,LinkList&B,LinkList&C)

(

LinkListpa,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é)點(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->next=A->next;

A->next=qb;

)

pb=B;

free(pb);

returnOK;

)

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

同)，現(xiàn)要求另辟空間構(gòu)成一個線性表C,其元素為A和B中元素的交集，且表C中的元素有依值遞增有序

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

解：

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

StatusListCross_Sq(SqList&A,SqUst&B,SqList&.C)

(

inti=0,j=0,k=0;

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

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

else

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

else{

ListInsert_Sq(C,k,A.e1em[i]);

i++；

k++;

}

)

returnOK;

}

2.26要求同2.25題。試對單鏈表編寫求C的算法。

解：

//將A、B求交后的結(jié)果放在C表中，并刪除B表

StatusListCross_L(LinkList&A,LinkList&B,LinkList&C)

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

)

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題的條件作