第4章 計算機專業(yè)英語 孫建忠

ComputerEnglishChapter4DataStructure1Keypoints:

usefultermsanddefinitionsofdatastructure

Difficultpoints:

Stack,queue,tree2計算機專業(yè)英語Requirements:1.Threereasonsforusingdatastructuresareefficiency,abstraction,andreusability.2.ThepropertiesofStack,Queue,andTree3.掌握常用英漢互譯技巧

3計算機專業(yè)英語NewWords&Expressions:hashtable雜湊(哈希)表 priorityqueues優(yōu)先隊列reusabilityn.復(fù)用性 binarytree二叉樹traversing遍歷，走過 context-free與上下文無關(guān)4.1AnIntroductiontoDataStructures

4計算機專業(yè)英語Datacomesinallshapesandsizes,butoftenitcanbeorganizedinthesameway.Forexample,consideralistofthingstodo,alistofingredientsinarecipe,orareadinglistforaclass.Althougheachcontainsadifferenttypeofdata,theyallcontaindataorganizedinasimilarway:alist.Alistisonesimpleexampleofadatastructure.Ofcourse,therearemanyothercommonwaystoorganizedataaswell.Incomputing,someofthemostcommonorganizationsarelinkedlists,stacks,queues,sets,hashtables,trees,heaps,priorityqueues,andgraphs.Threereasonsforusingdatastructuresareefficiency,abstraction,andreusability.數(shù)據(jù)以各種形狀和大小出現(xiàn)，但是它常?？梢杂猛瑯拥姆绞絹斫M織。例如,考慮要做事情的列表、處方成份的清單或一個班級的閱讀目錄。雖然它們包含不同類型的數(shù)據(jù),但他們都包含以一種相似方式組織的數(shù)據(jù):一個列表。列表是數(shù)據(jù)結(jié)構(gòu)的一個簡單例子。當然，還有許多其他組織數(shù)據(jù)通用方法。在計算機技術(shù)中，一些最常用的組織方式是鏈接表、堆棧、隊列、集合、哈希表、樹、堆、優(yōu)先隊列和圖。使用數(shù)據(jù)結(jié)構(gòu)的三個原因是效率、抽象性和復(fù)用性。4.1AnIntroductiontoDataStructures

5計算機專業(yè)英語Efficiency

Datastructuresorganizedatainwaysthatmakealgorithmsmoreefficient.Forexample,considersomeofthewayswecanorganizedataforsearchingit.Onesimplisticapproachistoplacethedatainanarrayandsearchthedatabytraversingelementbyelementuntilthedesiredelementisfound.However,thismethodisinefficientbecauseinmanycasesweenduptraversingeveryelement.Byusinganothertypeofdatastructure,suchasahashtableorabinarytreewecansearchthedataconsiderablyfaster.效率數(shù)據(jù)結(jié)構(gòu)使用令算法更有效率的方法組織數(shù)據(jù)。例如，考慮一些我們用來查找數(shù)據(jù)的組織方式。一種過分簡單的方式是將數(shù)據(jù)放置到數(shù)組中，并用遍歷的方法找到需要的元素。然而，這種方法是低效率的，因為在許多情況下，我們需要遍歷所有元素才能完成。使用其他類型的數(shù)據(jù)結(jié)構(gòu),如哈希表和二叉數(shù)，我們能夠相當快速地搜尋數(shù)據(jù)。4.1AnIntroductiontoDataStructures

6計算機專業(yè)英語Abstraction

Datastructuresprovideamoreunderstandablewaytolookatdata;thus,theyofferalevelofabstractioninsolvingproblems.Forexample,bystoringdatainastack,wecanfocusonthingsthatwedowithstacks,suchaspushingandpoppingelements,ratherthanthedetailsofhowtoimplementeachoperation.Inotherwords,datastructuresletustalkaboutprogramsinalessprogrammaticway.抽象化數(shù)據(jù)結(jié)構(gòu)提供一個更好理解的方法查看數(shù)據(jù)；因此，它們在解決問題中提供一定的抽象化水平。例如，通過把數(shù)據(jù)儲存在堆棧中，我們可以將重點集中在對堆棧的操作上，如使元素進棧和出棧，而不是集中在實現(xiàn)操作的細節(jié)上。換句話說，數(shù)據(jù)結(jié)構(gòu)使我們以較少的編程方式談?wù)摮绦颉?.1AnIntroductiontoDataStructures

7計算機專業(yè)英語Reusability

Datastructuresarereusablebecausetheytendtobemodularandcontext-free.Theyaremodularbecauseeachhasaprescribedinterfacethroughwhichaccesstodatastoredinthedatastructureisrestricted.Thatis,weaccessthedatausingonlythoseoperationstheinterfacedefines.Datastructuresarecontext-freebecausetheycanbeusedwithanytypeofdataandinavarietyofsituationsorcontexts.InC,wemakeadatastructurestoredataofanytypebyusingvoidpointerstothedataratherthanbymaintainingprivatecopiesofthedatainthedatastructureitself.復(fù)用性：因為數(shù)據(jù)結(jié)構(gòu)趨向于模塊化并和環(huán)境無關(guān),所以數(shù)據(jù)結(jié)構(gòu)是可以復(fù)用的。因為每種結(jié)構(gòu)有一個預(yù)定的接口,通過該接口限制訪問存儲在數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)，所以它們是模塊化的。也就是說,我們只能使用接口定義的那些操作來訪問數(shù)據(jù)。因為數(shù)據(jù)結(jié)構(gòu)能用于任何類型的數(shù)據(jù),并用于多種環(huán)境中，所以數(shù)據(jù)結(jié)構(gòu)與使用環(huán)境無關(guān)。在C語言中，我們通過使用空指針，而不是通過維護非公開的數(shù)據(jù)備份，使數(shù)據(jù)結(jié)構(gòu)存儲任何類型的數(shù)據(jù)。4.1AnIntroductiontoDataStructures

8計算機專業(yè)英語NewWords&Expressionsinvitingadj.引人動心的 contiguousadj.鄰近的,接近的stackn.堆棧 insertionn.插入deletionn.刪除,刪除部分 pop退棧push進棧 backtrackv.回溯pseudocoden.[計]偽代碼 retrievev.重新得到；n.找回pointern.指針 pertinentadj.有關(guān)的,相干的,中肯的extractvt.取，引 backout返回entailvt.使承擔，帶來 traversev.遍歷shrinkv.收縮 allotvt.分配,充當,依靠predecessorn.前輩,前任 backandforthadv.來來往往地,來回地vacancyn.空,空白,空缺 stuffvt.填充,塞滿AbbreviationsLIFO(last-in,first-out)后進先出 FIFO(first-in,first-out)先進先出4.2Stacks

9計算機專業(yè)英語Oneofthepropertiesofalistthatmakesalinkedstructuremoreinvitingthanacontiguousoneistheneedtoinsertanddeleteentriesinsidethelist.Recallthatitwassuchoperationsthathadthepotentialofforcingthemassivemovementofnamestofillorcreateholesinthecaseofacontiguouslist.Ifwerestrictsuchoperationstotheendsofthestructure,wefindthattheuseofacontiguousstructurebecomesamoreconvenientsystem.Anexampleofthisphenomenonisastack,whichisalistinwhichallinsertionsanddeletionsareperformedatthesameendofthestructure.Aconsequenceofthisrestrictionisthatthelastentryenteredwillalwaysbethefirstentryremoved--anobservationthatleadstostacksbeingknownaslast-in,first-out(LIFO)structures.插入和刪除記錄的需求是使鏈接表結(jié)構(gòu)比鄰接表結(jié)構(gòu)更誘人的原因之一。讓我們回想一下在鄰接表中具有填補和創(chuàng)建存儲空缺能力的操作。如果我們限制這種操作只可以在結(jié)構(gòu)的尾部進行，則鄰接表就是一種比較方便的系統(tǒng)。這種現(xiàn)象的一個例子就是堆棧。在堆棧中，插入和刪除操作都在結(jié)構(gòu)的相同末端進行。如此限制的結(jié)果就是最后一個進入表的記錄也就是第一個從表中刪除的記錄。這種結(jié)構(gòu)稱為后進先出結(jié)構(gòu)。4.2Stacks

10計算機專業(yè)英語Theendofastackatwhichentriesareinsertedanddeletediscalledthetopofthestack.Theotherendissometimescalledthestack'sbase.Toreflectthefactthataccesstoastackisrestrictedtothetopmostentry,weusespecialterminologywhenreferringtotheinsertionanddeletionoperations.Theprocessofinsertinganobjectonthestackiscalledapushoperation,andtheprocessofdeletinganobjectiscalledapopoperation.Thuswespeakofpushinganentryontoastackandpoppinganentryoffastack.堆棧尾部可以進行插入和刪除操作的記錄稱為堆棧的棧頂，另一端叫做棧底。為了表示如何限制堆棧只能從棧頂訪問，我們用一種特殊的術(shù)語來表示插入和刪除操作。把一個對象插入堆棧的操作稱為進棧操作，而從堆棧中刪除一個對象的操作稱為出棧操作，所以我們常說將一個條目進?；蛘邔⑵涑鰲！?.2Stacks

11計算機專業(yè)英語BacktrackingAclassicapplicationofastackinvolvestheexecutionofaprograminvolvingproceduresasfoundinourpseudocode.Whentheexecutionofaprocedureisrequested,themachinemusttransferitsattentiontotheprocedure;yetlater,whentheprocedureiscompleted,themachinemustreturntotheoriginallocationbeforecontinuing.Thismeansthat,whentheinitialtransferismade,theremustbeamechanismforrememberingthelocationtowhichexecutionultimatelyreturns.回溯堆棧的一個典型應(yīng)用發(fā)生在一個程序單元調(diào)用一個過程的操作中。為了完成這個調(diào)用，機器必須將它的注意力轉(zhuǎn)移到這個過程上；當過程調(diào)用結(jié)束后，機器必須返回到程序塊進行調(diào)用時所處的位置。這就意味著必須有一種用來記錄操作結(jié)束后返回的位置的機制。4.2Stacks

12計算機專業(yè)英語Thesituationiscomplicatedbythefactthattheproceduremayitselfrequesttheexecutionofanotherprocedure,whichmayrequeststillanother,andsoon(Figure7.9).Consequently,thereturnlocationsbeingrememberedbegintopileup.Later,aseachoftheseproceduresiscompleted,executionmustbereturnedtotheproperplacewithintheprogramunitthatcalledthecompletedprocedure.Asystemisthereforeneededtosavethereturnlocationsandlaterretrievethemintheproperorder.如果一個被調(diào)用的過程本身還要調(diào)用其他過程，而那些過程同樣也需要調(diào)用另外的過程，這樣一來整個情形就會很復(fù)雜。因此，返回地址的記憶就開始堆積。然后，當每一個過程都結(jié)束后，操作必須返回到被稱為完成過程的程序塊中的合適位置。因此，系統(tǒng)需要按照適當?shù)捻樞虼鎯驼一胤祷氐刂贰?.2Stacks

13計算機專業(yè)英語Astackisanidealstructureforsuchasystem.Aseachprocedureiscalled,apointertothepertinentreturnLocationispushedonastack,andaseachprocedureiscompleted,thetopentryfromthestackisextractedwiththeassuranceofobtainingapointertotheproperreturnlocation.Thisexampleisrepresentativeofstackapplicationsingeneralinthatitdemonstratestherelationshipbetweenstacksandtheprocessofbacktracking.Indeed,theconceptofastackisinherentinanyprocessthatentailsbackingoutofasystemintheoppositeorderfromwhichitwasentered.堆棧是滿足這種需要的理想結(jié)構(gòu)。當一個過程被調(diào)用時，將指向返回地址的指針進棧。然后，當一個過程完成時，將棧頂條目出棧，程序就可以準確得到返回地址。這是應(yīng)用棧的一個典型例子，它表明了棧和回溯過程的關(guān)系。在任何可以從進入端反向返回系統(tǒng)的過程中，堆棧的概念是與生俱來的。4.2Stacks

14計算機專業(yè)英語Asanotherexampleofbacktracking,supposewewanttoprintthenamesinalinkedlistinreverseorder--thatis,lastnamefirst.Ourproblemisthattheonlywaywecanaccessthenamesisbyfollowingthelinkedstructure.Thusweneedawayofholdingeachnameretrieveduntilallofthenamesthatfollowhavebeenretrievedandprinted.Oursolutionistotraversethelistfromitsbeginningtoitsendwhilepushingthenameswefindontoastack.Afterreachingtheendofthelist,weprintthenamesaswepopthemoffthestack.我們在來舉另一個例子，假設(shè)反向輸出一張鏈接表中的姓名，也就是把最后一個名字第一個輸出。問題是我們只能跟著鏈接結(jié)構(gòu)訪問姓名。因此，我們需要一種方式，通過這種方式，我們可以保持每一個姓名能被檢索，直到排列在這個姓名之后的姓名被得到并輸出。我們的方案是從鏈接表的開始順序遍歷到結(jié)尾，與此同時把每一個姓名按照遍歷順序進棧。當?shù)竭_鏈接表的末尾后，我們通過出棧操作來輸出姓名。4.2Stacks

15計算機專業(yè)英語StackImplementationToimplementastackstructureinacomputer'smemory,itiscustomarytoreserveablockofcontiguousmemorycellslargeenoughtoaccommodatethestackasitgrowsandshrinks.(Determiningthesizeofthisblockcanoftenbeacriticaldecision.Iftoolittleroomisreserved,thestackultimatelyexceedstheallottedstoragespace;iftoomuchroomisreserved,memoryspacewillbewasted.)Oneendofthisblockisdesignatedasthestack'sbase.Itisherethatthefirstentrypushedonthestackisstored,witheachadditionalentrybeingplacednexttoitspredecessorasthestackgrowstowardtheotherendofthereservedblock.棧的實現(xiàn)為了在計算機存儲中實現(xiàn)棧結(jié)構(gòu)，一般采取的方法是保留一塊足夠容納棧大小變化的內(nèi)存單元。（通常來說，確定塊的大小是一個很重要的任務(wù)。如果保留的空間過小，那么棧最后可能從所分配的存儲空間中溢出；而如果保留的空間過大，又是一種浪費。）塊的一端作為棧底，棧的第一條數(shù)據(jù)會被存儲在這里，以后的條目被依次放置在它之后的存儲單元中，也就是堆棧向另外一端增加。4.2Stacks

16計算機專業(yè)英語Thus,asentriesarepushedandpopped,thetopofthestackmovesbackandforthwithinthereservedblockofmemorycells.Ameansisthereforeneededtomaintainarecordofthelocationofthetopentry.Forthispurpose,theaddressofthetopentryisstoredinanadditionalmemorycellknownasthestackpointer.Thatis,thestackpointerpointstothetopofthestack.因此，在條目進棧和出棧的時候，棧頂?shù)奈恢镁驮诖鎯卧獕K中前后移動。為了保存這個位置的軌跡，棧頂條目的地址被存儲在一個附加的存儲單元中，這個附加的存儲單元被被稱為堆棧指針。也就是說，堆棧指針就是一個指向棧頂?shù)闹羔槨?.2Stacks

17計算機專業(yè)英語Thecompletesystem,asillustratedinFigure4-1,worksasfollows:Topushanewentryonthestack,wefirstadjustthestackpointertopointtothevacancyjustbeyondthetopofthestackandthenplacethenewentryatthislocation.Topopanentryfromthestack,wereadthedatapointedtobythestackpointerandthenadjustthepointertopointtothenextentrydownonthestack.一個完整的系統(tǒng)（如圖4-1所示）是這樣工作的：為了把一條新的數(shù)據(jù)壓入堆棧，我們首先調(diào)整堆棧指針，使之指向當前棧頂之前的空白。然后將新的條目置于此處。為了將條目從堆棧中彈出，我們首先讀出堆棧指針所指向的數(shù)據(jù)，然后調(diào)整此指針指向堆棧中的下一條數(shù)據(jù)所在的存儲單元。4.2Stacks

18計算機專業(yè)英語Asweobservedinthecaseoflists,aprogrammerwouldprobablyfinditadvantageoustowriteproceduresthatperformthesepushandpopoperationssothatthestackcouldbeusedasanabstracttool.Notethattheseproceduresshouldhandlesuchspecialcasesasattemptstopopentriesfromanemptystackandtopushentriesontoafullstack.Inparticular,acompletestacksystemwouldprobablycontainproceduresforpushingentries,poppingentries,testingforanemptystack,andtestingforafullstack.同我們觀察到表中的情況一樣，程序員也可以將堆棧編寫成一個可以進行進棧和出棧操作的抽象工具。注意，這些過程應(yīng)該可以處理諸如試圖從空棧中彈出數(shù)據(jù)，或者將數(shù)據(jù)壓入一個已經(jīng)填滿的堆棧等特殊情況。所以一個完整的堆棧系統(tǒng)應(yīng)該包括進棧、出棧、測試堆棧是否空或滿的功能。4.2Stacks

19計算機專業(yè)英語Astackorganizedinacontiguousblockofmemorycellsexhibitslittledifferencebetweentheconceptualstructureandtheactualstructureinmainmemory.Suppose,however,thatwecannotreserveafixedblockofmemoryandbeassuredthatthestackwillalwaysfit.Asolutionistoimplementthestackasalinkedstructuresimilartothatofalist.Thisavoidsthelimitationsofrestrictingthestacktoafixed-sizeblock,sinceitallowstheentriesinthestacktobestuffedintosmallpiecesofavailablespaceanywhereinmemory.Insuchasituation,theconceptualstackstructurewillbequitedifferentfromtheactualarrangementofthedatainmemory.存儲在存儲單元連續(xù)塊中的棧展現(xiàn)出主存儲器中概念結(jié)構(gòu)與實際之間的一定差異。假設(shè)我們不能預(yù)測棧的大小，我們就不能保留一個總能滿足堆棧的固定大小的存儲塊。一種解決方法就是實現(xiàn)一種與表結(jié)構(gòu)相似的鏈接結(jié)構(gòu)棧。這種方法避免了將堆棧限定在一塊固定塊中的局限性，因為它允許將新的條目插入存儲器中任何一塊足夠大的空閑空間中。在這種情況下，概念上的堆棧結(jié)構(gòu)與其在存儲器中實際的數(shù)據(jù)組織方式就大不相同了。

4.2Stacks

20計算機專業(yè)英語NewWords&Expressionsqueuen.行列,隊列;vi.排隊 cafeterian.自助餐廳rearn.后面,背后,后方 setaside留出，撥出headpointer頭指針 tailpointer尾指針crawlvi.&n.爬行,蠕動,徐徐行進egocentricadj.自我中心的 consumptionn.消費,消費量 sideeffect副作用migratevi.移動,移植;vt.使移居,使移植 circularqueue循環(huán)隊列 envisionvt.想象,預(yù)想bridgevt.跨接,接通4.3Queues21計算機專業(yè)英語Incontrasttoastackinwhichbothinsertionsanddeletionsareperformedatthesameend,aqueueisalistinwhichallinsertionsareperformedatoneendwhilealldeletionsaremadeattheother.Wehavealreadymetthisstructureinrelationtowaitinglines,wherewerecognizeditasbeingafirst-in,first-out(FIFO)storagesystem.Actually,theconceptofaqueueisinherentinanysysteminwhichobjectsareservedinthesameorderinwhichtheyarrive.4.3Queues棧的插入與刪除操作都是在表的相同端進行的。而與此不同，隊列是插入和刪除操作分別在兩端進行的表。我們已經(jīng)遇到過這種與等待隊列相關(guān)的結(jié)構(gòu)，在此種情況中，我們把它當作是一種先進先出的存儲系統(tǒng)。實際上，在那些對象輸入與輸出順序相同的系統(tǒng)中，隊列的概念是與生俱來的。隊列的結(jié)尾從等待隊列的關(guān)聯(lián)中得到名字。22計算機專業(yè)英語Theendsofaqueuegettheirnamesfromthiswaiting-linerelationship.Theendatwhichentriesareremovediscalledthehead(orsometimesthefront)ofthequeuejustaswesaythatthenextpersontobeservedinacafeteriaisatthehead(orfront)oftheline.Similarly,theendofthequeueatwhichnewentriesareaddediscalledthetail(orrear).4.3Queues結(jié)尾處，也就是條目被移出隊列的地方，被稱為隊列的隊首（有時候也稱為隊前），這就好像我們在快餐廳中下一個將點餐的顧客為一隊的隊首一樣。同樣，隊列的尾部，也就是條目被添加的地方，被稱為隊尾（或者隊后）。23計算機專業(yè)英語Wecanimplementaqueueinacomputer'smemorywithinablockofcontiguouscellsinawaysimilartoourstorageofastack.Sinceweneedtoperformoperationsatbothendsofthestructure,wesetasidetwomemorycellstouseaspointersinsteadofjustone,aswedidforastack.Oneofthesepointers,calledtheheadpointerskeepstrackoftheheadofthequeue;theother,calledthetailpointer,keepstrackofthetail.

4.3Queues我們可以像存儲棧那樣通過連續(xù)單元組成的存儲塊在計算機主存儲器中實現(xiàn)隊列。因為我們需要在此結(jié)構(gòu)的兩端都進行操作，我們分配出兩個存儲單元用來當作指針，而非棧中那樣僅僅需要一個單元來存儲指針。其中的一個指針被稱為頭指針，用來保持隊列頭的軌跡；另一個指針被稱為尾指針，用來保持隊尾的軌跡。24計算機專業(yè)英語Whenthequeueisempty,bothofthesepointerspointtothesamelocation.Eachtimeanentryisinserted,itisplacedinthelocationpointedtobythetailpointerandthenthetailpointerisadjustedtopointtowardthenextunusedlocation.Inthismanner,thetailpointerisalwayspointingtothefirstvacancyatthetailofthequeue.Removinganentryfromthequeueinvolvesextractingtheentrypointedtobytheheadpointerandthenadjustingtheheadpointertopointtowardtheentrythatfollowedtheremovedentry.4.3Queues如果一個隊列為空，那么兩個指針應(yīng)該指向相同的位置。每當新的條目被插入時，均會被置于尾指針所指向的位置，同時修改尾指針，使之指向下一個未使用的位置。這樣，尾指針總是指向隊尾后的第一空閑存儲單元。將一條數(shù)據(jù)移出隊列的操作包括將頭指針指向的條目取出，同時調(diào)整頭指針使之指向排在被移出條目之后的位置。25計算機專業(yè)英語Aproblemremainswiththestoragesystemasdescribedthusfar.Ifleftunchecked,thequeuecrawlsslowlythroughmemorylikeaglacier,destroyinganyotherdatainitspath(Figure4.2).Thismovementistheresultoftheratheregocentricpolicyofinsertingeachnewentrybymerelyplacingitnexttothepreviousoneandrepositioningthetailpointeraccordingly.Ifweaddenoughentries,thetailofthequeueultimatelyextendsallthewaytotheendofthemachine'smemory.

4.3Queues以上描述的存儲系統(tǒng)仍然存在著問題。如果剩余的存儲器未被檢查，隊列會像冰河一樣在存儲器中增長，同時將在此道路上的所有其他數(shù)據(jù)破壞（如圖所示）。造成這種移動的相當一部分原因在于插入新條目時使用的“利己”策略，即在插入是僅僅將新數(shù)據(jù)置于當前隊尾之后，同時重置尾指針。如果我們添加足夠的條目，那么隊尾最后就會從計算機存儲器中溢出。26計算機專業(yè)英語Thisconsumptionofmemoryisnottheresultofthequeue'ssizebutisasideeffectofthequeue'saccessprocedure.(Asmallyetactivequeuecaneasilyrequiremoreofamachine'smemoryresourcesthanalarge,inactiveone.)Onesolutiontothismemoryspaceproblemmightbetomovetheentriesinaqueueforwardastheleadingonesareremoved,inthesamemanneraspeoplewaitingtobuytheaterticketsstepforwardeachtimeapersonhasbeenserved.However,thismassmovementofdatawouldbeveryinefficient.Whatweneedisawayofconfiningthequeuetooneareaofmemorywithoutbeingforcedtoperformmajorrearrangementsofdata.4.3Queues存儲器的消耗問題并不是因隊列的大小而生的，其真正原因在于隊列的實現(xiàn)問題。（一個小而動態(tài)變化的隊列比一個大而保持不變的隊列需要更多的機器存儲資源。）解決存儲器空間問題的一個可能方法是：當最前面的條目被移出時,前移隊列中的其他條目，就好像人們在購買戲票時所采用的方法一樣，每當一個人買到票后，就前移一人。然而這種方法在計算機中運行的效率很低，因為它將需要對數(shù)據(jù)進行大量的移動。27計算機專業(yè)英語Acommonsolutionistosetasideablockofmemoryforthequeue,startthequeueatoneendoftheblock,andletthequeuemigratetowardtheotherendoftheblock.Then,whenthetailofthequeuereachestheendoftheblock,wemerelystartinsertingadditionalentriesbackattheoriginalendoftheblock,whichbythistimeisvacant.Likewise,whenthelastentryintheblockfinallybecomestheheadofthequeueandisremoved,theheadpointerisadjustedbacktothebeginningoftheblockwhereotherentriesare,bythistime,waiting.Inthismanner,thequeuechasesitselfaroundwithintheblockratherthanwanderingoffthroughmemory.4.3Queues用來在計算機中控制隊列的最一般的方法是為隊列分配一塊存儲器，從存儲塊的末端開始存儲隊列，并且讓隊列向另一端增長。然而當隊尾到達塊的末端，即隊列為空時，我們開始將新的條目反向于末端的方向插入。同樣，當隊列的最后一條成為隊頭并被移出時，調(diào)整頭指針回到塊的開端，同時在此等待。在此方法下，隊列在一塊區(qū)域內(nèi)循環(huán)而不會出現(xiàn)內(nèi)存溢出情況。

28計算機專業(yè)英語Suchatechniqueresultsinanimplementationthatiscalledacircularqueuebecausetheeffectisthatofformingaloopoutoftheblockofmemorycellsallottedtothequeue.Asfarasthequeueisconcerned,thelastcellintheblockisadjacenttothefirstcell.4.3Queues采用此技術(shù)的實現(xiàn)方法稱為循環(huán)隊列，因為分配給隊列的一塊存儲單元組成了一個環(huán)。就一個隊列而言，存儲塊的最后一個單元與它的第一個單元相鄰。29計算機專業(yè)英語Onceagain,weshouldrecognizethedifferencebetweentheconceptualstructureenvisionedbytheuserofaqueueandtheactualcyclicstructureimplementedinthemachine'smemory.Asinthecaseofthepreviousstructures,thesedifferencesarenormallybridgedbysoftware.Thatisalongwiththecollectionofmemorycellsusedfordatastorage,aqueueimplementationshouldincludeacollectionofproceduresthatinsertandremoveentriesfromthequeueaswellasdetectwhetherthequeueisemptyorfull.

4.3Queues我們應(yīng)該再次認識到隊列使用者使用的概念結(jié)構(gòu)與實際在計算機存儲器中實現(xiàn)的循環(huán)結(jié)構(gòu)之間的差異。在前一個結(jié)構(gòu)的例子中，這些差異通常是通過軟件來銜接的。也就是說，連同存儲數(shù)據(jù)需要的一組存儲單元，隊列的實現(xiàn)應(yīng)該包括一組用來插入和移出隊列條目和探測隊列是否為空或滿的過程函數(shù)。然后，開發(fā)軟件其他單元的程序員可以通過這些方法來實現(xiàn)隊列的插入和移出操作，而不用關(guān)心其在存儲器中的實際實現(xiàn)。30計算機專業(yè)英語常用英漢互譯技巧一、增譯法根據(jù)英漢兩種語言不同的思維方式、語言習(xí)慣和表達方式，在翻譯時增添一些詞、短句或句子，以便更準確地表達出原文所包含的意義。這種方式多半用在漢譯英里。1、漢語無主句較多，而英語句子一般都要有主語，所以在翻譯漢語無主句的時候，除了少數(shù)可用英語無主句、被動語態(tài)或“Therebe…”結(jié)構(gòu)來翻譯以外，一般都要根據(jù)語境補出主語，使句子完整。2、英漢兩種語言在名詞、代詞、連詞、介詞和冠詞的使用方法上也存在很大差別。英語中代詞使用頻率較高，凡說到人的器官和歸某人所有的或與某人有關(guān)的事物時，必須在前面加上物主代詞。因此，在漢譯英時需要增補物主代詞，而在英譯漢時又需要根據(jù)情況適當?shù)貏h減。3、英語詞與詞、詞組與詞組以及句子與句子的邏輯關(guān)系一般用連詞來表示，而漢語則往往通過上下文和語序來表示這種關(guān)系。因此，在漢譯英時常常需要增補連詞。英語句子離不開介詞和冠詞。4、在漢譯英時還要注意增補一些原文中暗含而沒有明言的詞語和一些概括性、注釋性的詞語，以確保譯文意思的完整。

31計算機專業(yè)英語常用英漢互譯技巧一、增譯法例1.Indeed,thereverseistrue實際情況恰好相反。（增譯名詞）例2.這是這兩代計算機之間的又一個共同點。Thisisyetanothercommonpointbetweenthecomputersofthetwogenerations.（增譯介詞）例3.Individualmathematiciansoftenhavetheirownwayofpronouncingmathematicalexpressionsandinmanycasesthereisnogenerallyaccepted“correct”pronunciation.每個數(shù)學(xué)家對數(shù)學(xué)公式常常有各自的讀法，在許多情況下，并不存在一個普遍接受的所謂“正確”讀法。(增加隱含意義的詞)例4.只有在可能發(fā)生混淆、或要強調(diào)其觀點時，數(shù)學(xué)家才使用較長的讀法Itisonlywhenconfusionmayoccur,orwherehe/shewishestoemphasisthepoint,thatthemathematicianwillusethelongerforms.(增加主語)

32計算機專業(yè)英語常用英漢互譯技巧二、省譯法這是與增譯法相對應(yīng)的一種翻譯方法，即刪去不符合目標語思維習(xí)慣、語言習(xí)慣和表達方式的詞，以避免譯文累贅。增譯法的例句反之即可。又如：例1.YouwillbestayinginthishotelduringyourvisitinBeijing.你在北京訪問期間就住在這家飯店里。（省譯物主代詞）例2.Ihopeyouwillenjoyyourstayhere.希望您在這兒過得愉快。（省譯主語）例3.中國政府歷來重視環(huán)境保護工作。TheChinesegovernmenthasalwaysattachedgreatimportancetoenvironmentalprotection.(省譯名詞)例4.ThedevelopmentofICmadeitpossibleforelectronicdevicestobecomesmallerandsmaller.集成電路的發(fā)展是電子器件可以做得越來越小。(省譯形式主語it)

33計算機專業(yè)英語常用英漢互譯技巧三、轉(zhuǎn)換法

在翻譯過程中，為了使譯文符合目標語的表述方式、方法和習(xí)慣，對原句中的詞類、句型和語態(tài)等進行轉(zhuǎn)換：1、在詞性方面，把名詞轉(zhuǎn)換為代詞、形容詞、動詞；把動詞轉(zhuǎn)換成名詞、形容詞、副詞、介詞；把形容詞轉(zhuǎn)換成副詞和短語。2、在句子成分方面，把主語變成狀語、定語、賓語、表語；把謂語變成主語、定語、表語；把定語變成狀語、主語；把賓語變成主語。3、在句型方面，把并列句變成復(fù)合句，把復(fù)合句變成并列句，把狀語從句變成定語從句。4、在語態(tài)方面，可以把主動語態(tài)變?yōu)楸粍诱Z態(tài)。

34計算機專業(yè)英語常用英漢互譯技巧三、轉(zhuǎn)換法

例1.ToomuchexposuretoTVprogramswilldogreatharmtotheeyesightofchildren.孩子們看電視過多會大大地損壞視力。(名詞轉(zhuǎn)動詞)例2.由于我們實行了改革開放政策，我國的綜合國力有了明顯的增強。Thankstotheintroductionofourreformandopeningpolicy,ourcomprehensivenationalstrengthhasgreatlyimproved.(動詞轉(zhuǎn)名詞)例3.時間不早了，我們回去吧！Wedon’thavemuchtimeleft.Let’sgoback.(句型轉(zhuǎn)換)35計算機專業(yè)英語常用英漢互譯技巧四、拆句法和合并法例1.IncreasedcooperationwithChinaisintheinterestsoftheUnitedStates.同中國加強合作，符合美國的利益。（在主謂連接處拆譯）例3.中國是個大國，百分之八十的人口從事農(nóng)業(yè)，但耕地只占土地面積的十分之一，其余為山脈、森林、城鎮(zhèn)和其他用地。Chinaisalargecountrywithfour-fifthsofthepopulationengagedinagriculture,butonlyonetenthofthelandisfarmland,therestbeingmountains,forestsandplacesforurbanandotheruses.（合譯法）例4.Packetswitchingisamethodofslicingdigitalmessagesintoparcelscalled“packets,”sendingthepacketsalongdifferentcommunicationpathsastheybecomeavailable,andthenreassemblingthepacketsoncetheyarriveattheirdestination.分組交換是傳輸數(shù)據(jù)的一種方法，它先將數(shù)據(jù)信息分割成許多稱為“分組”的數(shù)據(jù)信息包；當路徑可用時，經(jīng)過不同的通信路徑發(fā)送；當?shù)竭_目的地后，再將它們組裝起來。(將長定語從句拆成幾個并列的分句)36計算機專業(yè)英語常用英漢互譯技巧五、正譯法和反譯法這兩種方法通常用于漢譯英，偶爾也用于英譯漢。所謂正譯，是指把句子按照與漢語相同的語序或表達方式譯成英語。所謂反譯則是指把句子按照與漢語相反的語序或表達方式譯成英語。正譯與反譯常常具有同義的效果，但反譯往往更符合英語的思維方式和表達習(xí)慣。因此比較地道。例1.你可以從因特網(wǎng)上獲得這一信息。YoucanobtainthisinformationontheInternet.（正譯）Thisinformationisaccessible/availableontheInternet.（反譯）例2.他突然想到了一個新主意。Suddenlyhehadanewidea.(正譯)Hesuddenlythoughtoutanewidea.(正譯)Anewideasuddenlyoccurredto/struck