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

ComputerEnglishChapter4DataStructure1Keypoints:

usefultermsanddefinitionsofdatastructure

Difficultpoints:

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

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

4計(jì)算機(jī)專業(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織。例如,考慮要做事情的列表、處方成份的清單或一個(gè)班級的閱讀目錄。雖然它們包含不同類型的數(shù)據(jù),但他們都包含以一種相似方式組織的數(shù)據(jù):一個(gè)列表。列表是數(shù)據(jù)結(jié)構(gòu)的一個(gè)簡單例子。當(dāng)然，還有許多其他組織數(shù)據(jù)通用方法。在計(jì)算機(jī)技術(shù)中，一些最常用的組織方式是鏈接表、堆棧、隊(duì)列、集合、哈希表、樹、堆、優(yōu)先隊(duì)列和圖。使用數(shù)據(jù)結(jié)構(gòu)的三個(gè)原因是效率、抽象性和復(fù)用性。4.1AnIntroductiontoDataStructures

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2Stacks

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

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

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

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

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

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

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

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

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

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

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