数据结构与算法分析答案（c++版）（第二版）

《数据结构与算法分析答案（c++版）（第二版）》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、SolutionsManualforAPracticalIntroductiontoDataStructuresandAlgorithmAnalysisSecondEditionCliffordA.ShafferDepartmentofComputerScienceVirginiaTechBlacksburg,VA24061November30,2000Copyright
c2000byCliffordA.Shaffer.ContentsPrefaceii1DataStructuresandAlgorithms12MathematicalPreliminaries53Algo

2、rithmAnalysis174Lists,Stacks,andQueues235BinaryTrees326GeneralTrees407InternalSorting468FileProcessingandExternalSorting549Searching5810Indexing6411Graphs6912ListsandArraysRevisited7613AdvancedTreeStructures82iiiContents14AnalysisTechniques8815LimitstoComputation94PrefaceContainedhereinaret

3、hesolutionstoallexercisesfromthetextbookAPracticalIntroductiontoDataStructuresandAlgorithmAnalysis,2ndedition.FormostoftheproblemsrequiringanalgorithmIhavegivenactualcode.InafewcasesIhavepresentedpseudocode.Pleasebeawarethatthecodepresentedinthismanualhasnotactuallybeencompiledandtested.Whi

4、leIbelievethealgo-rithmstobeessentiallycorrect,theremaybeerrorsinsyntaxaswellassemantics.Mostimportantly,thesesolutionsprovideaguidetotheinstructorastotheintendedanswer,ratherthanusableprograms.iii1DataStructuresandAlgorithmsInstructor’snote:Unliketheotherchapters,manyofthequestionsinthisch

5、apterarenotreallysuitableforgradedwork.Thequestionsaremainlyintendedtogetstudentsthinkingaboutdatastructuresissues.1.1Thisquestiondoesnothaveaspecificrightanswer,providedthestudentkeepstothespiritofthequestion.Studentsmayhavetroublewiththecon-ceptof“operations.”1.2Thisexerciseasksthestudentt

6、oexpandontheirconceptofanintegerrepre-sentation.AgoodanswerisdescribedbyProject4.5,whereasingly-linkedlistissuggested.Themoststraightforwardimplementationstoreseachdigitinitsownlistnode,withdigitsstoredinreverseorder.Additionandmulti-plicationareimplementedbywhatamountstograde-schoolarithme

7、tic.Foraddition,simplymarchdowninparallelthroughthetwolistsrepresentingtheoperands,ateachdigitappendingtoanewlisttheappropriatepartialsumandbringingforwardacarrybitasnecessary.Formultiplication,com-binetheadditionfunctionwithanewfunctionthatmultipliesasi