《计算机专业英语》电子教案-第4章

ComputerEnglishChapter4DataStructureChapter4DataStructure计算机专业英语4-2Keypoints:usefultermsanddefinitionsofdatastructureDifficultpoints:Stack,queue,treeChapter4DataStructure计算机专业英语4-3Requirements:1.Threereasonsforusingdatastructuresareefficiency,abstraction,andreusability.2.ThepropertiesofStack,Queue,andTree3.掌握常用英汉互译技巧Chapter4DataStructure计算机专业英语4-4NewWords&Expressions:harshtable杂凑(哈希)表priorityqueues优先队列reusabilityn.复用性binarytree二叉树traversing遍历，走过context-free与上下文无关4.1AnIntroductiontoDataStructuresChapter4DataStructure计算机专业英语4-5Datacomesinallshapesandsizes,butoftenitcanbeorganizedinthesameway.Forexample,consideralistofthingstodo,alistofingredientsinarecipe,orareadinglistforaclass.Althougheachcontainsadifferenttypeofdata,theyallcontaindataorganizedinasimilarway:alist.Alistisonesimpleexampleofadatastructure.Ofcourse,therearemanyothercommonwaystoorganizedataaswell.Incomputing,someofthemostcommonorganizationsarelinkedlists,stacks,queues,sets,hashtables,trees,heaps,priorityqueues,andgraphs.Threereasonsforusingdatastructuresareefficiency,abstraction,andreusability.数据以各种形状和大小出现，但是它常常可以用同样的方式来组织。例如,考虑要做事情的列表、处方成份的清单或一个班级的阅读目录。虽然它们包含不同类型的数据,但他们都包含以一种相似方式组织的数据:一个列表。列表是数据结构的一个简单例子。当然，还有许多其他组织数据通用方法。在计算机技术中，一些最常用的组织方式是链接表、堆栈、队列、集合、哈希表、树、堆、优先队列和图。使用数据结构的三个原因是效率、抽象性和复用性。4.1AnIntroductiontoDataStructuresChapter4DataStructure计算机专业英语4-6EfficiencyDatastructuresorganizedatainwaysthatmakealgorithmsmoreefficient.Forexample,considersomeofthewayswecanorganizedataforsearchingit.Onesimplisticapproachistoplacethedatainanarrayandsearchthedatabytraversingelementbyelementuntilthedesiredelementisfound.However,thismethodisinefficientbecauseinmanycasesweenduptraversingeveryelement.Byusinganothertypeofdatastructure,suchasahashtableorabinarytreewecansearchthedataconsiderablyfaster.效率数据结构使用令算法更有效率的方法组织数据。例如，考虑一些我们用来查找数据的组织方式。一种过分简单的方式是将数据放置到数组中，并用遍历的方法找到需要的元素。然而，这种方法是低效率的，因为在许多情况下，我们需要遍历所有元素才能完成。使用其他类型的数据结构,如哈希表和二叉数，我们能够相当快速地搜寻数据。4.1AnIntroductiontoDataStructuresChapter4DataStructure计算机专业英语4-7AbstractionDatastructuresprovideamoreunderstandablewaytolookatdata;thus,theyofferalevelofabstractioninsolvingproblems.Forexample,bystoringdatainastack,wecanfocusonthingsthatwedowithstacks,suchaspushingandpoppingelements,ratherthanthedetailsofhowtoimplementeachoperation.Inotherwords,datastructuresletustalkaboutprogramsinalessprogrammaticway.抽象化数据结构提供一个更好理解的方法查看数据；因此，它们在解决问题中提供一定的抽象化水平。例如，通过把数据储存在堆栈中，我们可以将重点集中在对堆栈的操作上，如使元素进栈和出栈，而不是集中在实现操作的细节上。换句话说，数据结构使我们以较少的编程方式谈论程序。4.1AnIntroductiontoDataStructuresChapter4DataStructure计算机专业英语4-8ReusabilityDatastructuresarereusablebecausetheytendtobemodularandcontext-free.Theyaremodularbecauseeachhasaprescribedinterfacethroughwhichaccesstodatastoredinthedatastructureisrestricted.Thatis,weaccessthedatausingonlythoseoperationstheinterfacedefines.Datastructuresarecontext-freebecausetheycanbeusedwithanytypeofdataandinavarietyofsituationsorcontexts.InC,wemakeadatastructurestoredataofanytypebyusingvoidpointerstothedataratherthanbymaintainingprivatecopiesofthedatainthedatastructureitself.复用性：因为数据结构趋向于模块化并和环境无关,所以数据结构是可以复用的。因为每种结构有一个预定的接口,通过该接口限制访问存储在数据结构中的数据，所以它们是模块化的。也就是说,我们只能使用接口定义的那些操作来访问数据。因为数据结构能用于任何类型的数据,并用于多种环境中，所以数据结构与使用环境无关。在C语言中，我们通过使用空指针，而不是通过维护非公开的数据备份，使数据结构存储任何类型的数据。4.1AnIntroductiontoDataStructuresChapter4DataStructure计算机专业英语4-9NewWords&Expressionsinvitingadj.引人动心的contiguousadj.邻近的,接近的stackn.堆栈insertionn.插入deletionn.删除,删除部分pop退栈push进栈backtrackv.回溯pseudocoden.[计]伪代码retrievev.重新得到；n.找回pointern.指针pertinentadj.有关的,相干的,中肯的extractvt.取，引backout返回entailvt.使承担，带来traversev.遍历shrinkv.收缩allotvt.分配,充当,依靠predecessorn.前辈,前任backandforthadv.来来往往地,来回地vacancyn.空,空白,空缺stuffvt.填充,塞满AbbreviationsLIFO(last-in,first-out)后进先出FIFO(first-in,first-out)先进先出4.2StacksChapter4DataStructure计算机专业英语4-10Oneofthepropertiesofalistthatmakesalinkedstructuremoreinvitingthanacontiguousoneistheneedtoinsertanddeleteentriesinsidethelist.Recallthatitwassuchoperationsthathadthepotentialofforcingthemassivemovementofnamestofillorcreateholesinthecaseofacontiguouslist.Ifwerestrictsuchoperationstotheendsofthestructure,wefindthattheuseofacontiguousstructurebecomesamoreconvenientsystem.Anexampleofthisphenomenonisastack,whichisalistinwhichallinsertionsanddeletionsareperformedatthesameendofthestructure.Aconsequenceofthisrestrictionisthatthelastentryenteredwillalwaysbethefirstentryremoved--anobservationthatleadstostacksbeingknownaslast-in,first-out(LIFO)structures.插入和删除记录的需求是使链接表结构比邻接表结构更诱人的原因之一。让我们回想一下在邻接表中具有填补和创建存储空缺能力的操作。如果我们限制这种操作只可以在结构的尾部进行，则邻接表就是一种比较方便的系统。这种现象的一个例子就是堆栈。在堆栈中，插入和删除操作都在结构的相同末端进行。如此限制的结果就是最后一个进入表的记录也就是第一个从表中删除的记录。这种结构称为后进先出结构。4.2StacksChapter4DataStructure计算机专业英语4-11Theendofastackatwhichentriesareinsertedanddeletediscalledthetopofthestack.Theotherendissometimescalledthestack'sbase.Toreflectthefactthataccesstoastackisrestrictedtothetopmostentry,weusespecialterminologywhenreferringtotheinsertionanddeletionoperations.Theprocessofinsertinganobjectonthestackiscalledapushoperation,andtheprocessofdeletinganobjectiscalledapopoperation.Thuswespeakofpushinganentry