fundamentals of data structures_ELLIS HOROWITZ

《fundamentals of data structures_ELLIS HOROWITZ》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、PREFACEFormanyyearsadatastructurescoursehasbeentaughtincomputerscienceprograms.Oftenitisregardedasacentralcourseofthecurriculum.Itisfascinatingandinstructivetotracethehistoryofhowthesubjectmatterforthiscoursehaschanged.Backinthemiddle1960'sthecoursewasnotentitledDataStructuresbutperhaps

2、ListProcessingLanguages.ThemajorsubjectsweresystemssuchasSLIP(byJ.Weizenbaum),IPL-V(byA.Newell,C.Shaw,andH.Simon),LISP1.5(byJ.McCarthy)andSNOBOL(byD.Farber,R.Griswold,andI.Polonsky).Then,in1968,volumeIoftheArtofComputerProgrammingbyD.Knuthappeared.Histhesiswasthatlistprocessingwasnotama

3、gicalthingthatcouldonlybeaccomplishedwithinaspeciallydesignedsystem.Instead,hearguedthatthesametechniquescouldbecarriedoutinalmostanylanguageandheshiftedtheemphasistoefficientalgorithmdesign.SLIPandIPL-Vfadedfromthescene,whileLISPandSNOBOLmovedtotheprogramminglanguagescourse.Thenewstrat

4、egywastoexplicitlyconstructarepresentation(suchaslinkedlists)withinasetofconsecutivestoragelocationsandtodescribethealgorithmsbyusingEnglishplusassemblylanguage.Progressinthestudyofdatastructuresandalgorithmdesignhascontinued.Outofthisrecentworkhascomemanygoodideaswhichwebelieveshouldbe

5、presentedtostudentsofcomputerscience.Itisourpurposeinwritingthisbooktoemphasizethosetrendswhichweseeasespeciallyvaluableandlonglasting.Themostimportantofthesenewconceptsistheneedtodistinguishbetweenthespecificationofadatastructureanditsrealizationwithinanavailableprogramminglanguage.Thi

6、sdistinctionhasbeenmostlyblurredinpreviousbookswheretheprimaryemphasishaseitherbeenonaprogramminglanguageoronrepresentationaltechniques.Ourattemptherehasbeentoseparateoutthespecificationofthedatastructurefromitsrealizationandtoshowhowbothoftheseprocessescanbesuccessfullyaccomplished.The

7、specificationstagerequiresonetoconcentrateondescribingthefunctioningofthedatastructurewithoutconcernforitsimplementation.ThiscanbedoneusingEnglishandmathematicalnotation,buthereweintroduceaprogrammingnotationcalledaxioms.Theresultingimplementationindependentspecificationsvaluab