unit-8数据结构与算法

Unit8DatastructureByWucanghai1.OverviewofDataStructuresOnceyou'velearnedtoprogram,yourunintoreal-worldproblemsthatrequiremorethanaprogramminglanguagealonetosolve.注1DataStructuresandAlgorithmsinJavaisagentleimmersion(3)intothemostpractical(4)waystomakedatadowhatyouwantittodo.注2注1：这句话的含义是：当你学编程的时候，你遇到的现实的问题就是每一种编程语言单独的存储数据。注2：这句话的含义是：基于Java的数据结构与算法是把数据按你想要的方式存储的最实用的方式。TextADatastructure(1)sandalgorithm(2)sinjavaAnotherwaytolookatdatastructuresistofocusontheirstrengthsandweaknesses.Inthissectionwe'llprovideanoverview,intheformof(5)atable,ofthemajordatastoragestructureswe'llbediscussing.DataStructureAdvantagesDisadvantagesArrayQuickinsertion,veryfastaccessifindexknownSlowsearch,slowdeletion,fixedsize.注3OrderedarrayQuickersearchthanunsortedarraySlowinsertionanddeletion,fixedsize.StackProvideslast-in,first-outaccess.SlowaccesstootheritemsLinkedlistQuickinsertion,quickdeletionSlowsearchBinarytreeQuicksearch,insertion,deletion(iftreeremainsbalanced)Deletionalgorithmiscomplex.注4Red-blacktreeQuicksearch,insertion,deletion.Treealwaysbalanced.ComplexHashtableVeryfastaccessifkeyknown.Fastinsertion.Slowdeletion,accessslowifkeynotknown,inefficientmemoryusage.注5GraphModelsreal-worldsituations.Somealgorithmsareslowandcomplex.注62.OverviewofAlgorithms

Manyofthealgorithmswe'lldiscussapplydirectlytospecificdatastructures.Formostdatastructures,youneedtoknowhowto(1)Insertanewdataitem.(2)Searchforaspecifieditem.(3)Deleteaspecifieditem.

Youmayalsoneedtoknowhowtoiteratethroughalltheitemsinadatastructure,visitingeachoneinturnsoastodisplayitorperformsomeotheractiononit.Oneimportantalgorithmcategory(7)issorting.Therearemanywaystosortdata，Theconceptofrecursionisimportantindesigningcertainalgorithms(1)ProblemswithProcedural(9)Languages

OOPwasinventedbecauseprocedurallanguages,suchasC,Pascal,andBASIC,werefoundtobeinadequate(10)forlargeandcomplexprograms.Whywasthis?3.Object-OrientedProgrammingTheproblemshavetodowiththeoverallorganizationoftheprogram.Proceduralprogramsareorganizedbydividingthecodeintofunctions(calledproceduresorsubroutinesinsomelanguages).注7Groupsoffunctionscouldformlargerunitscalledmodulesorfiles.CrudeOrganizationalUnitsOnedifficultywiththiskindoffunction-basedorganizationwasthatitfocusedonfunctionsattheexpenseofdata.Thereweren'tmanyoptionswhenitcametodata.Tosimplifyslightly,datacouldbelocaltoaparticularfunctionoritcouldbeglobal—accessible(11)toallfunctions.Therewasnoway(atleastnotaflexibleway)tospecifythatsomefunctionscouldaccessavariable(12)andotherscouldn't.Thiscausedproblemswhenseveralfunctionsneededtoaccessthesamedata.Tobeavailabletomorethanonefunction,suchvariableshadtobeglobal,butglobaldatacouldbeaccessedinadvertently(13)byanyfunctionintheprogram.注8Thisleadstofrequentprogrammingerrors.Whatwasneededwasawaytofine-tunedataaccessibility,allowinvariablestobeavailabletofunctionswithaneedtoaccessit,buthidingitfromothers.FromTheideaofobjectsaroseintheprogrammingcommunityasasolutiontotheproblemswithprocedurallanguages.4.ObjectsinaNutshellThisnewentity(14),theobject,solvesseveralproblemssimultaneously(15).Notonlydoesaprogrammingobjectcorrespondmoreaccurately(16)toobjectsintherealworld,italsosolvestheproblemengenderedby(17)globaldataintheproceduralmodel.

注9(1)Objects

Youmightthinkthattheideaofanobjectwouldbeenoughforoneprogrammingrevolution(18),butthere'smore.

注10Earlyon,itwasrealizedthatyoumightwanttomakeseveralobjectsofthesametype.Maybeyou'rewritingafurnacecontrolprogram(19)foranentireapartmenthouse,forexample,andyouneedseveraldozenthermostatobjects(20)inyourprogram.(2)ClassesItseemsashametogotothetroubleofspecifyingeachoneseparately(21).Thus,theideaofclasseswasborn。WordsandPhrasesaccessibleaccuratelycategorycharacteristicentityimmersioninadequateinadvertently可以访问的准确地分类，类别特性，特点实体，实数沉浸;浸没;浸不满意的,不足的不经意的，随意的WordsandPhrasesorientpracticalproceduralrevolutionseparatelysimultaneouslystructurevariable面向….的，朝向实用的过程的革命分别地同时地结构体[数]变量

TextBTheintroductionoftwoimportantdatastructures

Inthispartwewilltakeabriefintroductionabouttwoimportantdatastructures,LinkedlistandHashtable,whichwillmakeiteffectivetosearchorstorethedata.1.Linked(1)listWesawthatarrayshadcertaindisadvantagesasdatastoragestructures.Inanunorderedarray,searchingisslow,whereasinanorderedarray,insertionisslow.注1Inbothkindsofarraysdeletionisslow.Also,thesizeofanarraycan'tbechangedafterit'screated.Inthispartwe'lllookatadatastoragestructurethatsolvessomeoftheseproblems:thelinkedlist.Linkedlistsareprobablythesecondmostcommonlyusedgeneral-purposestoragestructuresafterarrays.Thelinkedlistisaversatile(2)mechanism(3)suitableforuseinmanykindsofgeneral-purposedatabases.Itcanalsoreplaceanarrayasthebasisforotherstoragestructuressuchasstacksandqueues.易变的，灵活的机制

Infact,youcanusealinkedlistinmanycaseswhereyouuseanarray(unlessyouneedfrequentrandomaccess(4)toindividualitemsusinganindex).Linkedlistsaren'tthesolutiontoalldatastorageproblems,buttheyaresurprisinglyversatileandconceptually(5)simplerthansomeotherpopularstructuressuchastrees.

注2We'llinvestigate(6)theirstrengthsandweaknessesaswegoalong.Inthissectionwewillrefertotwoveryusefuldatastructure.随机存取概念上的探讨，投入2.LinksInalinkedlist,eachdataitemisembeddedinalink.AlinkisanobjectofaclasscalledsomethinglikeLink.Becausetherearemanysimilarlinksinalist,itmakessensetouseaseparateclassforthem,distinct(7)fromthelinkedlistitself.注3Eachlinkobjectscontainsareference(usuallycallednext)tothenextlinkinthelist.Afieldinthelistitselfcontainsarereferencetothefirstlink.Here'spartofthedefinitionofaclassLink.Itcontainssomedataandareferencetothenextlink.classLink{publicintiData;//datapublicdoubledData;//datapublicLinknext;//referencetonextlink}Thiskindofclassdefinitionissometimescalledself-referentialbecauseitcontainsafield—callednextinthiscase—ofthesametypeasitself.注53.Hash(8)Tables

Ahashtableisadatastructurethatoffersveryfastinsertionandsearching.Whenyoufirsthearaboutthem,hashtablessoundalmosttoogoodtobetrue.Nomatterhowmanydataitemsthereare,insertionandsearching(andsometimesdeletion)cantakecloseto(9)constanttime:O(1)inBigOnotation.注6Inpracticethisisjustafewmachineinstructions.Forahumanuserofahashtablethisisessentially(10)instantaneous.It'ssofastthatcomputerprogramstypicallyusehashtableswhentheyneedtolookuptensofthousandsofitemsinlessthanasecond(asinspellingcheckers).Hashtablesaresignificantly(11)fasterthantreesNotonlyaretheyfast,hashtablesarerelatively(12)easytoprogr