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

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

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

2、orithms12MathematicalPreliminaries53AlgorithmAnalysis174Lists,Stacks,andQueues235BinaryTrees326GeneralTrees407InternalSorting468FileProcessingandExternalSorting549Searching5810Indexing6411Graphs6912ListsandArraysRevisited7613AdvancedTreeStructures82ii

3、iContents14AnalysisTechniques8815LimitstoComputation94PrefaceContainedhereinarethesolutionstoallexercisesfromthetextbookAPracticalIntroductiontoDataStructuresandAlgorithmAnalysis,2ndedition.FormostoftheproblemsrequiringanalgorithmIhavegivenactualcode.

4、InafewcasesIhavepresentedpseudocode.Pleasebeawarethatthecodepresentedinthismanualhasnotactuallybeencompiledandtested.WhileIbelievethealgo-rithmstobeessentiallycorrect,theremaybeerrorsinsyntaxaswellassemantics.Mostimportantly,thesesolutionsprovideaguid

5、etotheinstructorastotheintendedanswer,ratherthanusableprograms.iii1DataStructuresandAlgorithmsInstructor’snote:Unliketheotherchapters,manyofthequestionsinthischapterarenotreallysuitableforgradedwork.Thequestionsaremainlyintendedtogetstudentsthinkingab

6、outdatastructuresissues.1.1Thisquestiondoesnothaveaspecificrightanswer,providedthestudentkeepstothespiritofthequestion.Studentsmayhavetroublewiththecon-ceptof“operations.”1.2Thisexerciseasksthestudenttoexpandontheirconceptofanintegerrepre-sentation.Ago

7、odanswerisdescribedbyProject4.5,whereasingly-linkedlistissuggested.Themoststraightforwardimplementationstoreseachdigitinitsownlistnode,withdigitsstoredinreverseorder.Additionandmulti-plicationareimplementedbywhatamountstograde-schoolarithmetic.Foraddi

8、tion,simplymarchdowninparallelthroughthetwolistsrepresentingtheoperands,ateachdigitappendingtoanewlisttheappropriatepartialsumandbringingforwardacarrybitasnecessary.Formultiplication,com-binetheadditionfunctionwithanewfunctionthatmultipliesasi