C中的数据结构与算法分析

C 数据结构 原版

DataStructures

and

AlgorithmAnalysisinC

SecondEdition

SolutionsManual

MarkAllenWeiss

FloridaInternationalUniversity

C 数据结构 原版

Preface

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

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

Errorscanbereportedtoweiss@ u.edu.ThankstoGrigoriSchwarzandBrianHarvey

forpointingouterrorsinpreviousincarnationsofthismanual.

C 数据结构 原版

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 数据结构 原版

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 数据结构 原版

_______________________________________________________________________________

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 数据结构 原版

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

…… 此处隐藏：18952字，全部文档内容请下载后查看。喜欢就下载吧 ……