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

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

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

2、inaries53AlgorithmAnalysis174Lists,Stacks,andQueues235BinaryTrees326GeneralTrees407InternalSorting468FileProcessingandExternalSorting549Searching5810Indexing6411Graphs6912ListsandArraysRevisited7613AdvancedTreeStructures82iiiContents14AnalysisTechniques8815LimitstoComputation94

3、PrefaceContainedhereinarethesolutionstoallexercisesfromthetextbookAPracticalIntroductiontoDataStructuresandAlgorithmAnalysis,2ndedition.FormostoftheproblemsrequiringanalgorithmIhavegivenactualcode.InafewcasesIhavepresentedpseudocode.Pleasebeawarethatthecodepresentedinthismanual

4、hasnotactuallybeencompiledandtested.WhileIbelievethealgo-rithmstobeessentiallycorrect,theremaybeerrorsinsyntaxaswellassemantics.Mostimportantly,thesesolutionsprovideaguidetotheinstructorastotheintendedanswer,ratherthanusableprograms.iii1DataStructuresandAlgorithmsInstructor’sno

5、te:Unliketheotherchapters,manyofthequestionsinthischapterarenotreallysuitableforgradedwork.Thequestionsaremainlyintendedtogetstudentsthinkingaboutdatastructuresissues.1.1Thisquestiondoesnothaveaspecificrightanswer,providedthestudentkeepstothespiritofthequestion.Studentsmayhavetr

6、oublewiththecon-ceptof“operations.”1.2Thisexerciseasksthestudenttoexpandontheirconceptofanintegerrepre-sentation.AgoodanswerisdescribedbyProject4.5,whereasingly-linkedlistissuggested.Themoststraightforwardimplementationstoreseachdigitinitsownlistnode,withdigitsstoredinreverseor

7、der.Additionandmulti-plicationareimplementedbywhatamountstograde-schoolarithmetic.Foraddition,simplymarchdowninparallelthroughthetwolistsrepresentingtheoperands,ateachdigitappendingtoanewlisttheappropriatepartialsumandbringingforwardacarrybitasnecessary.Formultiplication,com-bi

8、netheadditionfunctionwithanewfunctionthatmultipliesasi