++DATASTRUCTURESANDALGORITHMSUSINGC#C#programmers:nomoretranslatingdatastructuresfromCorJavatouseinyourprograms!MikeMcMillanprovidesatutorialonhowtousedatastructuresandalgorithmsplusthefirstcomprehensivereferenceforC#imple-mentationofdatastructuresandalgorithmsfoundinthe.NETFrameworklibrary,aswellasthosedevelopedbytheprogrammer.Theapproachisverypractical,usingtimingtestsratherthanBigOnota-tiontoanalyzetheefficiencyofanapproach.CoverageincludesarrayandArrayLists,linkedlists,hashtables,dictionaries,trees,graphs,andsortingandsearchingalgorithms,aswellasmoreadvancedalgorithmssuchasprob-abilisticalgorithmsanddynamicprogramming.ThisistheperfectresourceforC#professionalsandstudentsalike.MichaelMcMillanisInstructorofComputerInformationSystemsatPulaskiTechnicalCollege,aswellasanadjunctinstructorattheUniversityofArkansasatLittleRockandtheUniversityofCentralArkansas.Mike’sprevi-ousbooksincludeObject-OrientedProgrammingwithVisualBasic.NET,DataStructuresandAlgorithmsUsingVisualBasic.NET,andPerlfromtheGroundUp.Heisaco-authorofProgrammingandProblem-SolvingwithVisualBasic.NET.Mikehaswrittenmorethantwenty-fivetradejournalarticlesonprogrammingandhasmorethantwentyyearsofexperienceprogrammingforindustryandeducation.DATASTRUCTURESANDALGORITHMSUSINGC#MICHAELMCMILLANPulaskiTechnicalCollegeCAMBRIDGEUNIVERSITYPRESSCambridge,NewYork,Melbourne,Madrid,CapeTown,Singapore,SãoPauloCambridgeUniversityPressTheEdinburghBuilding,CambridgeCB28RU,UKPublishedintheUnitedStatesofAmericabyCambridgeUniversityPress,NewYorkwww.cambridge.orgInformationonthistitle:www.cambridge.org/9780521876919©MichaelMcMillan2007Thispublicationisincopyright.Subjecttostatutoryexceptionandtotheprovisionofrelevantcollectivelicensingagreements,noreproductionofanypartmaytakeplacewithoutthellausvpermissionofCambridgeUniversityPress.Firstpublishedinprintformat2007ISBN-13978-0-521-87691-9hardbackISBN-100-521-87691-5hardbackISBN-13978-0-521-67015-9paperbackISBN-100-521-67015-2paperbackCambridgeUniversityPresshasnoresponsibilityforthepersistenceoraccuracyofurlsforexternalorthird-partyinternetwebsitesreferredtointhispublication,anddoesnotguaranteethatanycontentonsuchwebsitesis,orwillremain,accurateorappropriate.ContentsPrefacepageviiChapter1AnIntroductiontoCollections,Generics,andtheTimingClass1Chapter2ArraysandArrayLists26Chapter3BasicSortingAlgorithms42Chapter4BasicSearchingAlgorithms55Chapter5StacksandQueues68Chapter6TheBitArrayClass94Chapter7Strings,theStringClass,andtheStringBuilderClass119Chapter8PatternMatchingandTextProcessing147vviCONTENTSChapter9BuildingDictionaries:TheDictionaryBaseClassandtheSortedListClass165Chapter10HashingandtheHashtableClass176Chapter11LinkedLists194Chapter12BinaryTreesandBinarySearchTrees218Chapter13Sets237Chapter14AdvancedSortingAlgorithms249Chapter15AdvancedDataStructuresandAlgorithmsforSearching263Chapter16GraphsandGraphAlgorithms283Chapter17AdvancedAlgorithms314References339Index341++PrefaceThestudyofdatastructuresandalgorithmsiscriticaltothedevelopmentoftheprofessionalprogrammer.Therearemany,manybookswrittenondatastructuresandalgorithms,butthesebooksareusuallywrittenascollegetextbooksandarewrittenusingtheprogramminglanguagestypicallytaughtincollege—JavaorC.C#isbecomingaverypopularlanguageandthisbookprovidestheC#programmerwiththeopportunitytostudyfundamentaldatastructuresandalgorithms.C#existsinaver...