MarkAllenWeiss数据结构与算法分析课后习题答案3MarkAllenWeiss数据结构与算法分析课后习题答案3

1、Chapter3:Lists,Stacks,andQueuesThecommentsforExercise3.4regardingtheamountofabstractnessusedapplyhereTherunningtimeoftheprocedureinFig.3.1isO(厶+P)voidPrintLots(ListL.ListP)intCounter;PositionLpos,Ppos;Lpos=First(L);Ppos=First(P);Counter=1;while(Lpos!=NULL&Ppos!=NULL)if(Ppos-Element=Counter+)printf(%

2、?丄posoElement);Ppos=Next(Ppos.P);Lpos=Next(Lpos,L);)Fig.3.1.(a)Forsinglylinkedlists,thecodeisshowninFig.3.2.- -/*BeforePisthecellbeforethetwoadjacentcellsthataretobeswapped.*/*Errorchecksareomittedforclarity.*/voidSwapWithNext(PositionBeforeP,ListL)PositionP,AfterP;P=BeforeP-Next;AfterP=P-Next;/*Bot

3、hPandAfterPassumednotNULL.*/P-Next=AfterP-Next;BeforeP-Next=AfterP:AfterP-Next=P;)Fig.3.2.Fordoublylinkedlists,thecodeisshowninFig.3.3./*PandAfterParecellstobeswitched.Errorchecksasbefore*/voidSwapWithNext(PositionP.ListL)PositionBeforeP.AfterP;BeforeP=P-Prev;AfterP=P-Next:P-Next=AfterP-Next;BeforeP

4、-Next=AfterP:AfterP-Next=P;P-Next-Prev=P:P-Prev=AfterP;AfterP-Prev=BeforeP:)Fig.33Intersectisshownonpage9.TOC o 1-5 h z/*Thiscodecanbemademoreabstractbyusingoperationssuchas*/*RetrieveandIsPastEndtoreplaceLlPos-ElementandLIPos!=NULL*/*Wehaveavoidedthisbecausetheseoperationswerenotrigorouslydefined*/

5、ListIntersect(ListLI,ListL2)ListResult;PositionLIPos丄2P0S9ResultPos;LIPos=First(LI);L2Pos=First(L2);Result=MakeEmpty(NULL);ResultPos=First(Result);while(LIPos!=NULL&L2Pos!=NULL)if(LlPos-ElementElement)LIPos=Next(LIPos,LI);elseif(LIPos-ElementL2Pos-Element)L2Pos=Next(L2Pos,L2);elseInsert(LlPos-Elemen

6、t.Result,ResultPos):LI=Next(LIPos,LI);L2=Next(L2Pos,L2);ResultPos=Next(ResultPos,Result);returnResult;Fig.3.4containsthecodeforUnion.3.7(a)Onealgorithmistokeeptheresultinasorted(byexponent)linkedlist.EachoftheMNmultipliesrequiresasearchofthelinkedlistforduplicatesSincethesizeofthelinkedlistisO(MN).t

7、hetotalrunningtimeisO(M2N2).Theboundcanbeimprovedbymultiplyingonetermbytheentireotherpolynomial,andthenusingtheequivalentoftheprocedureinExercise3.2toinserttheentiresequence.TheneachsequencetakesO(MN),butthereareonlyMofthem,givingatimeboundofO(M2N).AnO(MNlogMN)solutionispossiblebycomputingallMNpairs

8、andthensortingbyexponentusinganyalgorithminChapter7.ItistheneasytomergeduplicatesafterwardThechoiceofalgorithmdependsontherelativevaluesofMandN.Iftheyareclose,thenthesolutioninpart(c)isbetter.Ifonepolynomialisverysmall,thenthesolutioninpart(b)isbetter.ListUnion(ListLI,ListL2)ListResult;ElementTypeIn

9、sertElement;PositionLIPos丄2Pos,ResultPos;LIPos=First(LI);L2Pos=First(L2);Result=MakeEmpty(NULL);ResultPos=First(Result);while(LIPos!=NULL&L2Pos!=NULL)if(LlPos-ElementElement)InsertElement=LlPos-Element;LIPos=Next(LIPos,LI);elseif(LlPos-ElementL2Pos-Element)InsertElement=L2Pos-Element;L2Pos=Next(L2Po

10、s,L2);elseInsertElement=LlPos-Element;LIPos=Next(LIPos,LI);L2Pos=Next(L2Pos,L2);Insert(InsertElement.Result,ResultPos):ResultPos=Next(ResultPos,Result):/*Flushoutremaininglist*/while(LIPos!=NULL)Insert(LlPos-Element,Result,ResultPos);LIPos=Next(LIPos.LI);ResultPos=Next(ResultPos,Result);while(L2Pos!

11、=NULL)Insert(L2Pos-Element,Result,ResultPos);L2Pos=Next(L2Pos.L2);ResultPos=Next(ResultPos,Result);returnResult;)Fig.343.8OnecanusethePowfunctioninChapter2,adaptedforpolynomialmultiplication.IfPissmaltastandardmethodthatusesO(P)multipliesinsteadofO(logP)mightbebetterbecausethemultiplieswouldinvolvea

12、largenumberwithasmallnumber,whichisgoodforthemultiplicationroutineinpart(b).30ThisisastandardprogrammingprojectThealgorithmcanbespedupbysetting=MmodN,sothatthehotpotatonevergoesaroundthecirclemorethanonce,andthenifMN/2.passingthepotatoappropriatelyinthealternativedirection.Thisrequiresadoublylinkedl

13、ist.Theworst-caserunningtimeisclearlyO(Nmin(M,N),althoughwhentheseheuristicsareused,andMandNarecomparable,thealgorithmmightbesignificantlyfaster.IfA/=1,thealgorithmisclearlylinear.TheVAX/VMSCcompilersmemorymanagementroutinesdopoorlywiththeparticularpatternoffreesinthiscase,causingO(NlogN)behavior.32

14、Reversalofasinglylinkedlistcanbedonenonrecursivelybyusingastack,butthisrequiresO(N)extraspaceThesolutioninFig.3.5issimilartostrategiesemployedingarbagecollectionalgorithms.Atthetopofthewhileloop.thelistfromthestarttoviousPosisalreadyreversed,whereastherestofthelist,fromCurrentPostotheendisnormal.Thi

15、salgorithmusesonlyconstantextraspace/*AssumingnoheaderandLisnotempty.*/ListReverseList(ListL)PositionCurrentPos,NextPosPreviousPos;PreviousPos=NULL;CurrentPos=L;NextPos=L-Next;while(NextPos!=NULL)CurrentPos-Next=PreviousPos;PreviousPos=CurrentPos;CurrentPos=NextPos;NextPos=NextPos-Next;CurrentPos-Ne

16、xt=PreviousPos;returnCurrentPos;)Fig.3.5.35(a)ThecodeisshowninFig.3.6.SeeFig.3.7.Thisfollowsfromwell-knownstatisticaltheorems.SeeSleatorandTaijanspaperintheChapter11references36(c)DeletetakesO(N)andisintwonestedforloopseachofsizeN,givinganobviousO(N)boundAbetterboundofO(N_)isobtainedbynotingthatonly

17、NelementscanbedeletedfromalistofsizeN、henceO(N2)isspentperformingdeletes.TheremainderoftheroutineisO(N2).sotheboundfollowsO(N)/*ArrayimplementatioiLstartingatslot1*/PositionFind(ElementTypeX,ListL)intLWhere;Where=0;for(i=1;i1;i)Li.Element=Li-1.Element;Ll.Element=X;return1:elsereturn0:/*Notfound.*/)F

18、ig.3-6.Sortthelist,andmakeascantoremoveduplicates(whichmustnowbeadjacent).3.17(a)Theadvantagesarethatitissimplertocode,andthereisapossiblesavingsifdeletedkeysaresubsequentlyreinserted(inthesameplace)Thedisadvantageisthatitusesmorespace,becauseeachcellneedsanextrabit(whichistypicallyabyte),andunusedc

19、ellsarenotfreedTwostackscanbeimplementedinanarraybyhavingonegrowfromthelowendofthearrayup,andtheotherfromthehighenddown(a)LetEbeourextendedstack.WewillimplementEwithtwostacksOnestack,whichwellcallS,isusedtokeeptrackofthePushandPopoperations,andtheother.M9keepstrackoftheminimum.ToimplementPiish(X,E),

20、weperformPi(sh(X,S)IfXissmallerthanorequaltothetopelementinstackM.thenwealsoperformPush(X.M).ToimplementPop(E),weperformPop(S).IfXisequaltothetopelementinstackM,thenwealsoPop(M).FindMin(E)isperformedbyexaminingthetopofMAlltheseoperationsareclearly0(1).(b)ThisresultfollowsfromatheoreminChapter7thatsh

21、owsthatsortingmusttakeQ(WlogN)time.O(N)operationsintherepertoire,includingDeleteMin,wouldbesufficienttosort./*Assumingaheader.*/PositionFind(ElementTypeX,ListL)PositionPrevPos,XPos;PrevPos=FindPrevious(X丄);if(PrevPos-Next!=NULL)/*Found.*/XPos=PrevPos-Next:PrevPos-Next=XPos-Next;XPos-Next=L-Next;L-Next=XPos;returnXPos;elsereturnNULL:)Fig.3.7.Threestackscanbeimplementedbyhavingonegrowfromthebottomup.another