数据结构与算法分析—c语言描述 课后答案

数据结构与算法分析—c语言描述 Mark Allen Weiss著的课后习题答案,12章完整版

DataStructures

and

AlgorithmAnalysisinC

(secondedition)

SolutionsManual

MarkAllenWeiss

FloridaInternationalUniversity

数据结构与算法分析—c语言描述 Mark Allen Weiss著的课后习题答案,12章完整版

Preface

IncludedinthismanualareanswerstomostoftheexercisesinthetextbookDataStructuresandAlgorithmAnalysisinC,secondedition,publishedbyAddison-Wesley.Theseanswersre ectthestateofthebookinthe rstprinting.

Speci callyomittedarelikelyprogrammingassignmentsandanyquestionwhosesolu-tionispointedtobyareferenceattheendofthechapter.Solutionsvaryindegreeofcomplete-ness;generally,minordetailsarelefttothereader.Forclarity,programsaremeanttobepseudo-Cratherthancompletelyperfectcode.

Errorscanbereportedtoweiss@ u.edu.ThankstoGrigoriSchwarzandBrianHarvey

forpointingouterrorsinpreviousincarnationsofthismanual.

数据结构与算法分析—c语言描述 Mark Allen Weiss著的课后习题答案,12章完整版

Table of Contents

1.Chapter1:Introduction......................................................................................................2.Chapter2:AlgorithmAnalysis..........................................................................................3.Chapter3:Lists,Stacks,andQueues.................................................................................4.Chapter4:Trees.................................................................................................................5.Chapter5:Hashing............................................................................................................6.Chapter6:PriorityQueues(Heaps)...................................................................................7.Chapter7:Sorting..............................................................................................................8.Chapter8:TheDisjointSetADT.......................................................................................9.Chapter9:GraphAlgorithms.............................................................................................10.Chapter10:AlgorithmDesignTechniques......................................................................11.Chapter11:AmortizedAnalysis......................................................................................12.Chapter12:AdvancedDataStructuresandImplementation............................................

147142529364245546366

数据结构与算法分析—c语言描述 Mark Allen Weiss著的课后习题答案,12章完整版

Chapter1:Introduction

1.3

Becauseofround-offerrors,itiscustomarytospecifythenumberofdecimalplacesthatshouldbeincludedintheoutputandroundupaccordingly.Otherwise,numberscomeoutlookingstrange.Weassumeerrorcheckshavealreadybeenperformed;theroutineSeparate islefttothereader.CodeisshowninFig. 1.1.Thegeneralwaytodothisistowriteaprocedurewithheading

voidProcessFile(constchar*FileName);

whichopensFileName, doeswhateverprocessingisneeded,andthenclosesit.Ifalineoftheform

#includeSomeFile

isdetected,thenthecall

ProcessFile(SomeFile);

ismaderecursively.Self-referentialincludescanbedetectedbykeepingalistof lesforwhichacalltoProcessFile hasnotyetterminated,andcheckingthislistbeforemakinganewcalltoProcessFile. 1.5

(a)Theproofisbyinduction.Thetheoremisclearlytruefor0 < X ≤ 1,sinceitistrueforX = 1,andforX < 1,log X isnegative.Itisalsoeasytoseethatthetheoremholdsfor1 < X ≤ 2,sinceitistrueforX = 2,andforX < 2,log X isatmost1.Supposethetheoremistrueforp < X ≤ 2p (wherep isapositiveinteger),andconsiderany2p < Y ≤ 4p (p ≥ 1).Thenlog Y = 1 + log (Y / 2) < 1 + Y / 2 < Y / 2 + Y / 2 ≤ Y ,wherethe rstine-qualityfollowsbytheinductivehypothesis.

(b)Let2X = A .ThenA B = (2X )B = 2XB .Thuslog A B = XB .SinceX = log A ,thetheoremisproved.1.6

(a)Thesumis4/3andfollowsdirectlyfromtheformula.

123 . . . 23 . . . _______ + ___

(b)S = __ + _ + + .4S = 1+ + .Subtractingthe rstequationfrom

44424342

21___

thesecondgives3S = 1 + __ + 2 + . . . .Bypart(a),3S = 4/ 3soS = 4/ 9.

44

4949161______________

(c)S = __ + 2 + 3 + . . . .4S = 1 + + 2 + 3 + . . . .Subtractingthe rstequa-444444

573________

tionfromthesecondgives3S = 1+ + 2 + 3 + . . . .Rewriting,weget

444

∞i∞1______

3S = 2Σi + Σi .Thus3S = 2(4/ 9) + 4/ 3 = 20/ 9.ThusS = 20/ 27.

i =04i =04

∞i N

(d)LetSN = Σ___.Followthesamemethodasinparts(a)-(c)toobtainaformulaforSN i 4i =0

intermsofSN 1,SN 2,...,S 0andsolvetherecurrence.Solvingtherecurrenceisverydif cult.

1.4

数据结构与算法分析—c语言描述 Mark Allen Weiss著的课后习题答案,12章完整版

_______________________________________________________________________________

doubleRoundUp(doubleN,intDecPlaces)

{

inti;

doubleAmountToAdd=0.5;

for(i=0;i<DecPlaces;i++)

AmountToAdd/=10;returnN+AmountToAdd;}

voidPrintFractionPart(doubleFractionPart,intDecPlaces){

inti,Adigit;

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

FractionPart*=10;

ADigit=IntPart(FractionPart);PrintDigit(Adigit);

FractionPart=DecPart(FractionPart);}}

voidPrintReal(doubleN,intDecPlaces){

intIntegerPart;

doubleFractionPart;

if(N<0){

putchar(’-’);N=-N;}

N=RoundUp(N,DecPlaces);

IntegerPart=IntPart(N);FractionPart=DecPart(N);PrintOut(IntegerPart);/*Usingroutineintext*/if(DecPlaces>0)

putchar(’.’);

PrintFractionPart(FractionPart,DecPlaces);}

Fig.1.1.

_______________________________________________________________________________1.7

111__ = N__ N / 2 1 __ ～ ln N ln N / 2 ～ ln 2.

～～ΣΣΣiiii = N / 2 i =1i =1

N

数据结构与算法分析—c语言描述 Mark Allen Weiss著的课后习题答案,12章完整版

1.81.9

24 = 16 ≡ 1 (mod 5).(24)25 ≡ 125 (mod 5).Thus2100 ≡ 1 (mod 5).

(a)Proofisbyinduction.ThestatementisclearlytrueforN = 1andN = 2.AssumetrueforN = 1,2,...,k .Then

k +1

sumontherightisFk +2 2 + Fk +1=Fk +3 2,wherethelatterequalityfollowsfromthede nitionoftheFibonaccinumbers.ThisprovestheclaimforN = k + 1,andhenceforallN .

(b)Asinthetext,theproofisbyinduction.Observethatφ + 1 = φ2.Thisimpliesthatφ 1 + φ 2 = 1.ForN = 1andN = 2,thestatementistrue.AssumetheclaimistrueforN = 1,2,...,k .

Fk +1 = Fk + Fk 1

bythede nitionandwecanusetheinductivehypothesisontheright-handside,obtaining

F < φk + φk 1

k +1

Fi = ΣFi +Fk +1.Σi =1i =1

k

Bytheinductionhypothesis,thevalueofthe

< φ 1φk +1 + φ 2φk +1Fk +1 < (φ 1 + φ 2)φk +1 < φk +1andprovingthetheorem.

(c)Seeanyoftheadvancedmathreferencesattheendofthechapter.Thederivation

involvestheuseofgeneratingfunctions.1.10(a)

i =1

Σ(2i 1) = 2Σi Σ1 = N (N +1) N = N 2.

i =1

i =1

N +1

NNN

(b)Theeasiestwaytoprovethisisbyinduction.ThecaseN = 1istrivial.Otherwise,

iΣi =1

3

= (N +1) + Σi 3

3

N

N(N +1)2_________

= (N +1) +

4 N 2 2___ + (N +1) = (N +1)

4 N 2 + 4N + 4 2___________ = (N +1)

4

3

i =1 2

(N +1)2(N +2)2_____________=

22

2

___________(N +1)(N +2) =

2

N +1 2= Σi i =1

数据结构与算法分析—c语言描述 Mark Allen Weiss著的课后习题答案,12章完整版

Chapter2:AlgorithmAnalysis

2.12.2

2/N ,37,√ N ,N ,N log log N ,N log N ,N log (N 2),N log2N ,N 1.5,N 2,N 2log N ,N 3,2N / 2,2N .N log N andN log (N 2)growatthesamerate.(a)True.

(b)False.AcounterexampleisT 1(N ) = 2N ,T 2(N ) = N ,and f (N ) = N .(d)False.Thesamecounterexampleasinpart(c)applies.2.3

WeclaimthatN log N istheslowergrowingfunction.Toseethis,supposeotherwise.

√

Then,N ε/ log N wouldgrowslowerthanlog N .Takinglogsofbothsides,we ndthat,

underthisassumption,ε/ √ log N log N growsslowerthanlog log N .Butthe rstexpres- growsslowerthansionsimpli estoε√log N .IfL = log N ,thenweareclaimingthatε√L

log L ,orequivalently,thatε2L growsslowerthanlog2 L .Butweknowthatlog2 L = ο (L ),sotheoriginalassumptionisfalse,provingtheclaim.

Clearly,logk 1N = ο(logk 2N )ifk 1 < k 2,soweneedtoworryonlyaboutpositiveintegers.Theclaimisclearlytruefork = 0andk = 1.Supposeitistruefork < i .Then,byL’Hospital’srule,

i 1

logi NlogN_____________lim = lim i

NN →∞NN →∞Thesecondlimitiszerobytheinductivehypothesis,provingtheclaim.2.52.6

Let f (N ) = 1whenN iseven,andN whenN isodd.Likewise,letg (N ) = 1whenN is

odd,andN whenN iseven.Thentheratio f (N ) / g (N )oscillatesbetween0and∞.Foralltheseprograms,thefollowinganalysiswillagreewithasimulation:(I)TherunningtimeisO (N ).(II)TherunningtimeisO (N 2).(III)TherunningtimeisO (N 3).(IV)TherunningtimeisO (N 2).

(V) j canbeaslargeasi 2,whichcouldbeaslargeasN 2.k canbeaslargeas j ,whichisN 2.TherunningtimeisthusproportionaltoN .N 2.N 2,whichisO (N 5).

(VI)Theif statementisexecutedatmostN 3times,bypreviousarguments,butitistrueonlyO (N 2)times(becauseitistrueexactlyi timesforeachi ).ThustheinnermostloopisonlyexecutedO (N 2)times.Eachtimethrough,ittakesO ( j 2) = O (N 2)time,foratotalofO (N 4).Thisisanexamplewheremultiplyingloopsizescanoccasionallygiveanoveresti-mate.2.7

(a)Itshouldbeclearthatallalgorithmsgenerateonlylegalpermutations.The rsttwoalgorithmshaveteststoguaranteenoduplicates;thethirdalgorithmworksbyshuf inganarraythatinitiallyhasnoduplicates,sononecanoccur.Itisalsoclearthatthe rsttwoalgorithmsarecompletelyrandom,andthateachpermutationisequallylikely.Thethirdalgorithm,duetoR.Floyd,isnotasobvious;thecorrectnesscanbeprovedbyinduction.(c)False.AcounterexampleisT 1(N ) = N 2,T 2(N ) = N ,and f (N ) = N 2.

2.4

数据结构与算法分析—c语言描述 Mark Allen Weiss著的课后习题答案,12章完整版

See

J.Bentley,"ProgrammingPearls,"CommunicationsoftheACM30(1987),754-757.Notethatifthesecondlineofalgorithm3isreplacedwiththestatement

Swap(A[i],A[RandInt(0,N-1)]);

thennotallpermutationsareequallylikely.Toseethis,noticethatforN = 3,thereare27equallylikelywaysofperformingthethreeswaps,dependingonthethreerandomintegers.Sincethereareonly6permutations,and6doesnotevenlydivide27,eachpermutationcannotpossiblybeequallyrepresented.

(b)Forthe rstalgorithm,thetimetodecideifarandomnumbertobeplacedinA [i ]hasnotbeenusedearlierisO (i ).TheexpectednumberofrandomnumbersthatneedtobetriedisN / (N i ).Thisisobtainedasfollows:i oftheN numberswouldbeduplicates.Thustheprobabilityofsuccessis(N i ) / N .ThustheexpectednumberofindependenttrialsisN / (N i ).Thetimeboundisthus

N 1

N 1N 2N 11N1Ni_________ = O (N 2____ 2 2 < Σ < NΣ_ < NΣlog N )ΣN iN iN i ji =0i =0i =0j =1

Thesecondalgorithmsavesafactorofi foreachrandomnumber,andthusreducesthetime

boundtoO (N log N )onaverage.Thethirdalgorithmisclearlylinear.

(c,d)Therunningtimesshouldagreewiththeprecedinganalysisifthemachinehasenoughmemory.Ifnot,thethirdalgorithmwillnotseemlinearbecauseofadrasticincreaseforlargeN .

(e)Theworst-caserunningtimeofalgorithmsIandIIcannotbeboundedbecausethereisalwaysa niteprobabilitythattheprogramwillnotterminatebysomegiventimeT .Thealgorithmdoes,however,terminatewithprobability1.Theworst-caserunningtimeofthethirdalgorithmislinear-itsrunningtimedoesnotdependonthesequenceofrandomnumbers.2.8

Algorithm1wouldtakeabout5daysforN = 10,000,14.2yearsforN = 100,000and140centuriesforN = 1,000,000.Algorithm2wouldtakeabout3hoursforN = 100,000andabout2weeksforN = 1,000,000.Algorithm3woulduse11 2minutesforN = 1,000,000.Thesecalculationsassumeamachinewithenoughmemorytoholdthearray.Algorithm4solvesaproblemofsize1,000,000in3seconds.(a)O (N 2).(b)O (N log N ).

2.10(c)Thealgorithmislinear.

2.11UseavariationofbinarysearchtogetanO (log N )solution(assumingthearrayispreread).N .2.13(a)TesttoseeifN isanoddnumber(or2)andisnotdivisibleby3,5,7,...,√

),assumingthatalldivisionscountforoneunitoftime.(b)O (√N

2.9

(c)B = O (log N ).(d)O (2B / 2).

(e)Ifa20-bitnumbercanbetestedintimeT ,thena40-bitnumberwouldrequireaboutT 2

time.

(f)B isthebettermeasurebecauseitmoreaccuratelyrepresentsthesize oftheinput.

数据结构与算法分析—c语言描述 Mark Allen Weiss著的课后习题答案,12章完整版

2.14TherunningtimeisproportionaltoN timesthesumofthereciprocalsoftheprimesless

thanN .ThisisO (N log log N ).SeeKnuth,Volume2,page394.2.15ComputeX 2,X 4,X 8,X 10,X 20,X 40,X 60,andX 62.

2,2.16Maintainan arrayPowersOfX thatcanbe lledinaforloop.ThearraywillcontainX ,X

4 2log N X,uptoX.ThebinaryrepresentationofN (whichcanbeobtainedbytestingevenoroddandthendividingby2,untilallbitsareexamined)canbeusedtomultiplytheappropriateentriesofthearray.

2.17ForN = 0orN = 1,thenumberofmultipliesiszero.Ifb (N )isthenumberofonesinthe

binaryrepresentationofN ,thenifN > 1,thenumberofmultipliesusedis

log N + b (N ) 1

2.18(a)A .

(b)B .

(c)Theinformationgivenisnotsuf cienttodetermineananswer.Wehaveonlyworst-casebounds.(d)Yes.

2.19(a)Recursionisunnecessaryiftherearetwoorfewerelements.

(b)Onewaytodothisistonotethatifthe rstN 1elementshaveamajority,thenthelastelementcannotchangethis.Otherwise,thelastelementcouldbeamajority.ThusifN isodd,ignorethelastelement.Runthealgorithmasbefore.Ifnomajorityelementemerges,thenreturntheN th elementasacandidate.

(c)TherunningtimeisO (N ),andsatis esT (N ) = T (N / 2) + O (N ).

(d)Onecopyoftheoriginalneedstobesaved.Afterthis,theB array,andindeedtherecur-sioncanbeavoidedbyplacingeachBi intheA array.ThedifferenceisthattheoriginalrecursivestrategyimpliesthatO (log N )arraysareused;thisguaranteesonlytwocopies.2.20Otherwise,wecouldperformoperationsinparallelbycleverlyencodingseveralintegers

intoone.Forinstance,ifA=001,B=101,C=111,D=100,wecouldaddAandBatthesametimeasCandDbyadding00A00C+00B00D.WecouldextendthistoaddN pairsofnumbersatonceinunitcost.2.22No.IfLow = 1,High = 2,thenMid = 1,andtherecursivecalldoesnotmakeprogress.2.24No.AsinExercise2.22,noprogressismade.

数据结构与算法分析—c语言描述 Mark Allen Weiss著的课后习题答案,12章完整版

Chapter3:Lists,Stacks,andQueues

3.2

ThecommentsforExercise3.4regardingtheamountofabstractnessusedapplyhere.TherunningtimeoftheprocedureinFig. 3.1isO (L + P )._______________________________________________________________________________

void

PrintLots(ListL,ListP){

intCounter;

PositionLpos,Ppos;

Lpos=First(L);Ppos=First(P);Counter=1;

while(Lpos!=NULL&&Ppos!=NULL){

if(Ppos->Element==Counter++){

printf("%?",Lpos->Element);Ppos=Next(Ppos,P);}

Lpos=Next(Lpos,L);}}

Fig.3.1.

_______________________________________________________________________________3.3

(a)Forsinglylinkedlists,thecodeisshowninFig. 3.2.

数据结构与算法分析—c语言描述 Mark Allen Weiss著的课后习题答案,12章完整版

/*BeforePisthecellbeforethetwoadjacentcellsthataretobeswapped.*/

/*Errorchecksareomittedforclarity.*/void

SwapWithNext(PositionBeforeP,ListL){

PositionP,AfterP;

P=BeforeP->Next;

AfterP=P->Next;/*BothPandAfterPassumednotNULL.*/P->Next=AfterP->Next;BeforeP->Next=AfterP;AfterP->Next=P;}

Fig.3.2.

_______________________________________________________________________________(b)Fordoublylinkedlists,thecodeisshowninFig. 3.3._______________________________________________________________________________

/*PandAfterParecellstobeswitched.Errorchecksasbefore.*/void

SwapWithNext(PositionP,ListL){

PositionBeforeP,AfterP;

BeforeP=P->Prev;AfterP=P->Next;P->Next=AfterP->Next;BeforeP->Next=AfterP;AfterP->Next=P;P->Next->Prev=P;P->Prev=AfterP;

AfterP->Prev=BeforeP;}

Fig.3.3.

_______________________________________________________________________________3.4

Intersect isshownonpage9.

数据结构与算法分析—c语言描述 Mark Allen Weiss著的课后习题答案,12章完整版

/*Thiscodecanbemademoreabstractbyusingoperationssuchas

/*RetrieveandIsPastEndtoreplaceL1Pos->ElementandL1Pos!=NULL./*Wehaveavoidedthisbecausetheseoperationswerenotrigorouslyde ned.List

Intersect(ListL1,ListL2){

ListResult;

PositionL1Pos,L2Pos,ResultPos;

L1Pos=First(L1);L2Pos=First(L2);Result=MakeEmpty(NULL);ResultPos=First(Result);

while(L1Pos!=NULL&&L2Pos!=NULL){

if(L1Pos->Element<L2Pos->Element)

L1Pos=Next(L1Pos,L1);

elseif(L1Pos->Element>L2Pos->Element)

L2Pos=Next(L2Pos,L2);else{

Insert(L1Pos->Element,Result,ResultPos);L1=Next(L1Pos,L1);L2=Next(L2Pos,L2);ResultPos=Next(ResultPos,Result);}}

returnResult;

}

_______________________________________________________________________________3.53.7

Fig. 3.4containsthecodeforUnion.

(a)Onealgorithmistokeeptheresultinasorted(byexponent)linkedlist.EachoftheMN

multipliesrequiresasearchofthelinkedlistforduplicates.SincethesizeofthelinkedlistisO (MN ),thetotalrunningtimeisO (M 2N 2).

(b)Theboundcanbeimprovedbymultiplyingonetermbytheentireotherpolynomial,andthenusingtheequivalentoftheprocedureinExercise3.2toinserttheentiresequence.TheneachsequencetakesO (MN ),butthereareonlyM ofthem,givingatimeboundofO (M 2N ).

(c)AnO (MN log MN )solutionispossiblebycomputingallMN pairsandthensortingbyexponentusinganyalgorithminChapter7.Itistheneasytomergeduplicatesafterward.(d)ThechoiceofalgorithmdependsontherelativevaluesofM andN .Iftheyareclose,thenthesolutioninpart(c)isbetter.Ifonepolynomialisverysmall,thenthesolutioninpart(b)isbetter.

*/*/*/

数据结构与算法分析—c语言描述 Mark Allen Weiss著的课后习题答案,12章完整版

List

Union(ListL1,ListL2){

ListResult;

ElementTypeInsertElement;

PositionL1Pos,L2Pos,ResultPos;

L1Pos=First(L1);L2Pos=First(L2);Result=MakeEmpty(NULL);ResultPos=First(Result);

while(L1Pos!=NULL&&L2Pos!=NULL){

if(L1Pos->Element<L2Pos->Element){

InsertElement=L1Pos->Element;L1Pos=Next(L1Pos,L1);}

elseif(L1Pos->Element>L2Pos->Element){

InsertElement=L2Pos->Element;L2Pos=Next(L2Pos,L2);}else{

InsertElement=L1Pos->Element;

L1Pos=Next(L1Pos,L1);L2Pos=Next(L2Pos,L2);}

Insert(InsertElement,Result,ResultPos);ResultPos=Next(ResultPos,Result);}

/*Flushoutremaininglist*/while(L1Pos!=NULL){

Insert(L1Pos->Element,Result,ResultPos);

L1Pos=Next(L1Pos,L1);ResultPos=Next(ResultPos,Result);}

while(L2Pos!=NULL){

Insert(L2Pos->Element,Result,ResultPos);

L2Pos=Next(L2Pos,L2);ResultPos=Next(ResultPos,Result);}

returnResult;}

Fig.3.4.

_______________________________________________________________________________3.8

OnecanusethePow functioninChapter2,adaptedforpolynomialmultiplication.IfP is

small,astandardmethodthatusesO (P )multipliesinsteadofO (log P )mightbebetterbecausethemultiplieswouldinvolvealargenumberwithasmallnumber,whichisgoodforthemultiplicationroutineinpart(b).

3.10Thisisastandardprogrammingproject.Thealgorithmcanbespedupbysetting

M' = M mod N ,sothatthehotpotatonevergoesaroundthecirclemorethanonce,and

数据结构与算法分析—c语言描述 Mark Allen Weiss著的课后习题答案,12章完整版

thenifM' > N / 2,passingthepotatoappropriatelyinthealternativedirection.Thisrequiresadoublylinkedlist.Theworst-caserunningtimeisclearlyO (N min (M , N )),althoughwhentheseheuristicsareused,andM andN arecomparable,thealgorithmmightbesigni cantlyfaster.IfM = 1,thealgorithmisclearlylinear.TheVAX/VMSCcompiler’smemorymanagementroutinesdopoorlywiththeparticularpatternof free sinthiscase,causingO (N log N )behavior.

3.12Reversalofasinglylinkedlistcanbedonenonrecursivelybyusingastack,butthis

requiresO (N )extraspace.ThesolutioninFig. 3.5issimilartostrategiesemployedingar-bagecollectionalgorithms.Atthetopofthewhile loop,thelistfromthestarttoPre-viousPos isalreadyreversed,whereastherestofthelist,fromCurrentPos totheend,isnormal.Thisalgorithmusesonlyconstantextraspace._______________________________________________________________________________

/*AssumingnoheaderandLisnotempty.*/List

ReverseList(ListL){

PositionCurrentPos,NextPos,PreviousPos;

PreviousPos=NULL;CurrentPos=L;NextPos=L->Next;

while(NextPos!=NULL){

CurrentPos->Next=PreviousPos;PreviousPos=CurrentPos;CurrentPos=NextPos;NextPos=NextPos->Next;}

CurrentPos->Next=PreviousPos;returnCurrentPos;}

Fig.3.5.

_______________________________________________________________________________3.15(a)ThecodeisshowninFig. 3.6.

(b)SeeFig. 3.7.

(c)Thisfollowsfromwell-knownstatisticaltheorems.SeeSleatorandTarjan’spaperin

theChapter11references.

3.16(c)Delete takesO (N )andisintwonestedforloopseachofsizeN ,givinganobvious

O (N 3)bound.AbetterboundofO (N 2)isobtainedbynotingthatonlyN elementscanbedeletedfromalistofsizeN ,henceO (N 2)isspentperformingdeletes.TheremainderoftheroutineisO (N 2),sotheboundfollows.

(d)O (N 2).

数据结构与算法分析—c语言描述 Mark Allen Weiss著的课后习题答案,12章完整版

/*Arrayimplementation,startingatslot1*/Position

Find(ElementTypeX,ListL){

inti,Where;

Where=0;

for(i=1;i<L.SizeOfList;i++)

if(X==L[i].Element){

Where=i;break;}

if(Where)/*Movetofront.*/{

for(i=Where;i>1;i--)

L[i].Element=L[i-1].Element;L[1].Element=X;return1;}else

return0;/*Notfound.*/}

Fig.3.6.

_______________________________________________________________________________

(e)Sortthelist,andmakeascantoremoveduplicates(whichmustnowbeadjacent).3.17(a)Theadvantagesarethatitissimplertocode,andthereisapossiblesavingsifdeleted

keysaresubsequentlyreinserted(inthesameplace).Thedisadvantageisthatitusesmorespace,becauseeachcellneedsanextrabit(whichistypicallyabyte),andunusedcellsarenotfreed.3.21Twostackscanbeimplementedinanarraybyhavingonegrowfromthelowendofthe

arrayup,andtheotherfromthehighenddown.3.22(a)LetE beourextendedstack.WewillimplementE withtwostacks.Onestack,which

we’llcallS ,isusedtokeeptrackofthePush andPop operations,andtheother,M ,keepstrackoftheminimum.ToimplementPush(X,E),weperformPush(X,S).IfX issmallerthanorequaltothetopelementinstackM ,thenwealsoperformPush(X,M).Toimple-mentPop(E),weperformPop(S).IfX isequaltothetopelementinstackM ,thenwealsoPop(M).FindMin(E)isperformedbyexaminingthetopofM .AlltheseoperationsareclearlyO (1).

(b)ThisresultfollowsfromatheoreminChapter7thatshowsthatsortingmusttake (N log N )time.O (N )operationsintherepertoire,includingDeleteMin ,wouldbesuf cienttosort.

数据结构与算法分析—c语言描述 Mark Allen Weiss著的课后习题答案,12章完整版

/*Assumingaheader.*/Position

Find(ElementTypeX,ListL){

PositionPrevPos,XPos;

PrevPos=FindPrevious(X,L);

if(PrevPos->Next!=NULL)/*Found.*/{

XPos=PrevPos->Next;

PrevPos->Next=XPos->Next;XPos->Next=L->Next;L->Next=XPos;returnXPos;}else

returnNULL;}

Fig.3.7.

_______________________________________________________________________________3.23Threestackscanbeimplementedbyhavingonegrowfromthebottomup,anotherfromthe

topdown,andathirdsomewhereinthemiddlegrowinginsome(arbitrary)direction.Ifthethirdstackcollideswitheitheroftheothertwo,itneedstobemoved.Areasonablestrategyistomoveitsothatitscenter(atthetimeofthemove)ishalfwaybetweenthetopsoftheothertwostacks.3.24Stackspacewillnotrunoutbecauseonly49callswillbestacked.However,therunning

timeisexponential,asshowninChapter2,andthustheroutinewillnotterminateinarea-sonableamountoftime.3.25ThequeuedatastructureconsistsofpointersQ->Front andQ->Rear, whichpointtothe

beginningandendofalinkedlist.Theprogrammingdetailsareleftasanexercisebecauseitisalikelyprogrammingassignment.3.26(a)Thisisastraightforwardmodi cationofthequeueroutines.Itisalsoalikelyprogram-mingassignment,sowedonotprovideasolution.