Data Structures with C++ using STL Chapter 151

《Data Structures with C++ using STL Chapter 151》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1MainIndexContentsBuildingaRuler:drawRuler()MergeAlgorithmExample(4slides)PartitioningandMergingofSublistsinmergeSort()FunctioncallsinmergeSort()QuicksortExample(8slides)Findingkth–LargestElementpowerSet()ExampleChapter15–AdvancedRecursiveAlgorithmsRecursivecallsforfib(5)Ef

2、fectoffib(5)UsingDynamicProgrammingThe8-QueensExample(3slides)SummarySlides(6slides)12MainIndexContents2MainIndexContentsBuildingaRuler:drawRuler()Problem:createaprogramthatdrawsmarksatregularintervalsonaline.Thesizesofthemarksdiffer,dependingonthespecificinterval.-Therecur

3、sivefunctiondrawRuler()assumestheexistenceofthefunctiondrawMark(),whichtakesapointxandanintegervaluehasargumentsanddrawsamarkatpointxwithsizeproportionaltoh.2TheMergeAlgorithmExampleThemergealgorithmtakesasequenceofelementsinavectorvhavingindexrange[first,last).Thesequencec

4、onsistsoftwoorderedsublistsseparatedbyanintermediateindex,calledmid.34MainIndexContentsTheMergeAlgorithm…(Cont…)45MainIndexContentsTheMergeAlgorithm…(Cont…)5TheMergeAlgorithm…(Cont…)67MainIndexContentsPartitioningandMergingofSublistsinmergeSort()7FunctioncallsinmergeSort()8

5、QuicksortExampleThequicksortalgorithmusesaseriesofrecursivecallstopartitionalistintosmallerandsmallersublistsaboutavaluecalledthepivot.Example:Letvbeavectorcontaining10integervalues:v={800,150,300,650,550,500,400,350,450,900}9QuicksortExample(Cont…)1011MainIndexContentsQuic

6、ksortExample(Cont…)11QuicksortExample(Cont…)12QuicksortExample(Cont…)13QuicksortExample(Cont…)14QuicksortExample(Cont…)1516MainIndexContentsQuicksortExample(Cont…)16FindingKth–LargestElementTolocatethepositionofthekth-largestvalue(kLargest)inthelist,partitiontheelementsinto

7、twodisjointsublists.ThelowersublistmustcontainkelementsthatarelessthanorequaltokLargestandtheuppersublistmustcontainelementsthataregreaterthanorequaltokLargest.TheelementsinthelowersublistdonotneedtobeorderedbutonlytohavevaluesthatarelessthanorequaltokLargest.Theoppositecon

8、ditionappliestotheuppersublist.1718MainIndexContentspowerSet()Example18Recursiveca