unit-8數(shù)據(jù)結(jié)構(gòu)與算法

Unit8DatastructureByWucanghai1.OverviewofDataStructuresOnceyou'velearnedtoprogram,yourunintoreal-worldproblemsthatrequiremorethanaprogramminglanguagealonetosolve.注1DataStructuresandAlgorithmsinJavaisagentleimmersion(3)intothemostpractical(4)waystomakedatadowhatyouwantittodo.注2注1：這句話的含義是：當(dāng)你學(xué)編程的時(shí)候，你遇到的現(xiàn)實(shí)的問題就是每一種編程語言單獨(dú)的存儲數(shù)據(jù)。注2：這句話的含義是：基于Java的數(shù)據(jù)結(jié)構(gòu)與算法是把數(shù)據(jù)按你想要的方式存儲的最實(shí)用的方式。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可以訪問的準(zhǔn)確地分類，類別特性，特點(diǎn)實(shí)體，實(shí)數(shù)沉浸;浸沒;浸不滿意的,不足的不經(jīng)意的，隨意的WordsandPhrasesorientpracticalproceduralrevolutionseparatelysimultaneouslystructurevariable面向….的，朝向?qū)嵱玫倪^程的革命分別地同時(shí)地結(jié)構(gòu)體[數(shù)]變量

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.易變的，靈活的機(jī)制

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

注2We'llinvestigate(6)theirstrengthsandweaknessesaswegoalong.Inthissectionwewillrefertotwoveryusefuldatastructure.隨機(jī)存取概念上的探討，投入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