計(jì)算機(jī)專(zhuān)業(yè)英語(yǔ)Elementary Data Structures市公開(kāi)課金獎(jiǎng)市賽課一等獎(jiǎng)?wù)n件

1、Computer English Chapter 4 Elementary Data Structures 第1頁(yè)Key points: useful terms and definitions of data structureDifficult points: Stack, queue, tree第2頁(yè)Requirements:The properties of Stack, Queue, and Linked lists 掌握慣用英漢互譯技巧 第3頁(yè)New Words & Expressions:stack n. 棧，堆棧queue n. 隊(duì)列attribute n. 屬性，性質(zhì)unde

2、rflow n. 下溢overflow n. 上溢pseudocode n. 偽碼 4.1 Stacks and queuesAbbreviations:LIFO（last in first out）后進(jìn)先出FIFO（fisrt in first out）先進(jìn)先出 第4頁(yè)4.1 Stacks and queuesStacks and queues are dynamic sets in which the element removed from the set by the DELETE operation is prespecified. In a stack, the element d

3、eleted from the set is the one most recently inserted: the stack implements a last-in, first-out, or LIFO, policy. Similarly, in a queue, the element deleted is always the one that has been in the set for the longest time: the queue implements a first-in, first out, or FIFO, policy. There are severa

4、l efficient ways to implement stacks and queues on a computer. In this section we show how to use a simple array to implement each.棧和隊(duì)列都是動(dòng)態(tài)集合，其中元素由預(yù)先定義刪除操作可將其去除。在棧中，最近被插入元素最先被刪除，即棧是按后進(jìn)先出(LIFO)標(biāo)準(zhǔn)進(jìn)行；類(lèi)似，在隊(duì)列里，被刪除元素是最早進(jìn)入隊(duì)列，即隊(duì)列是以先進(jìn)先出(FIFO)標(biāo)準(zhǔn)進(jìn)行。在計(jì)算機(jī)上，對(duì)于棧和隊(duì)列有幾個(gè)有效實(shí)現(xiàn)方法，這一節(jié)我們給出怎樣用簡(jiǎn)單數(shù)組來(lái)實(shí)現(xiàn)它們。 第5頁(yè)4.1 Stacks and q

5、ueues4.1.1 StacksThe INSERT operation on a stack is often called PUSH, and the DELETE operation, which does not take an element argument, is often called POP. These names are allusions to physical stacks, such as the spring-loaded stacks of plates used in cafeterias. The order in which plates are po

6、pped from the stack is the reverse of the order in which they were pushed onto the stack, since only the top plate is accessible.棧中插入元素操作通常稱(chēng)為入棧(PUSH)，刪除操作稱(chēng)為出棧(POP)，這里不考慮刪除那個(gè)元素。這些名字起源于實(shí)際堆棧，就像餐廳里使用帶有彈簧座一疊盤(pán)子：因?yàn)橹挥许敳勘P(pán)子是方便取用，所以盤(pán)子從這一疊中取出次序與其被放入次序是相反。第6頁(yè)4.1 Stacks and queues4.1.2 QueuesWe call the INSERT op

7、eration on a queue ENQUEUE, and we call the DELETE operation DEQUEUE; like the stack operation POP, DEQUEUE takes no element argument. The FIFO property of a queue causes it to operate like a line of people in the registrars office. The queue has a head and a tail. When an element is enqueued, it ta

8、kes its place at the tail of the queue, just as a newly arriving student takes a place at the end of the line. The element dequeued is always the one at the head of the queue, like the student at the head of the line who has waited the longest. (Fortunately, we dont have to worry about computational

9、 elements cutting into line.)我們稱(chēng)對(duì)隊(duì)列進(jìn)行插入操作為入隊(duì) (ENQUEUE)，刪除操作為出隊(duì)(DEQUEUE)；同棧中出棧操作一樣，出隊(duì)操作不考慮其中元素。隊(duì)列先進(jìn)先出標(biāo)準(zhǔn)就像排隊(duì)等候注冊(cè)一行人群。隊(duì)列有一個(gè)頭部和一個(gè)尾部。當(dāng)一個(gè)元素入隊(duì)，它就成為隊(duì)列尾部，就像一個(gè)新來(lái)學(xué)生成為隊(duì)尾一樣；出隊(duì)元素總是隊(duì)列頭部元素，像是站在隊(duì)列最前學(xué)生是排隊(duì)最久人一樣。(慶幸是，對(duì)于計(jì)算機(jī)元素，我們無(wú)須擔(dān)心插隊(duì)情況。) 第7頁(yè)4.2 Linked listsA linked list is a data structure in which the objects are arra

10、nged in a linear order. Unlike an array, though, in which the linear order is determined by the array indices, the order in a linked list is determined by a pointer in each object. Linked lists provide a simple, flexible representation for dynamic sets.鏈表這個(gè)數(shù)據(jù)結(jié)構(gòu)中對(duì)象都以線性次序排列，但不一樣于數(shù)組次序是由數(shù)組下標(biāo)確定，鏈表次序是由每個(gè)對(duì)

11、象指針確定。鏈表為動(dòng)態(tài)集合提供了一個(gè)簡(jiǎn)單、靈活表示形式。第8頁(yè)4.2 Linked listsFig.4-3 A doubly linked list 第9頁(yè)4.2 Linked listsAs shown in Fig.4-3, each element of a doubly linked list L is an object with a key field and two other pointer fields: next and prev. The object may also contain other satellite data. Given an element x i

12、n the list, nextx points to its successor in the linked list, and prevx points to its predecessor. If prevx = NIL, the element x has no predecessor and is therefore the first element, or head, of the list. If nextx = NIL, the element x has no successor and is therefore the last element, or tail, of

13、the list. An attribute headL points to the first element of the list. If headL = NIL, the list is empty. 如圖4-3所表示，雙向鏈表L中每個(gè)元素都是一個(gè)實(shí)體，由一個(gè)數(shù)值域和兩個(gè)指針域組成，其中兩個(gè)指針?lè)謩e是：next和prev，實(shí)體也能夠包含子數(shù)據(jù)。給定表中一個(gè)元素x，nextx指出它在鏈表中后繼，prevx指出它前趨。prevx = NIL表示元素x沒(méi)有前趨，所以x是第一個(gè)元素，即隊(duì)頭元素；假如nextx = NIL，表示x沒(méi)有后繼，也就是最終一個(gè)元素，隊(duì)尾元素。指針headL指向隊(duì)列中第

14、一個(gè)元素，假如headL = NIL表示隊(duì)列為空。第10頁(yè)4.2 Linked listsA list may have one of several forms. It may be either singly linked or doubly linked, it may be sorted or not, and it may be circular or not. If a list is singly linked, we omit the prev pointer in each element. If a list is sorted, the linear order of t

15、he list corresponds to the linear order of keys stored in elements of the list; the minimum element is the head of the list, and the maximum element is the tail. If the list is unsorted, the elements can appear in any order. 一個(gè)鏈表能夠是下面幾個(gè)形式之一：?jiǎn)蜗蜴湵砘螂p向鏈表，有序或無(wú)序，循環(huán)或非循環(huán)。對(duì)于單向鏈表，我們就無(wú)須對(duì)每個(gè)元素使用prev指針了。假如一個(gè)表是有序，

16、表線序和表中存放元素值線序是一致，即：最小值元素是隊(duì)列頭部元素，最大值元素是隊(duì)尾元素。假如一個(gè)表是無(wú)序，其中元素能夠以任何次序出現(xiàn)。第11頁(yè)4.2 Linked listsIn a circular list, the prev pointer of the head of the list points to the tail, and the next pointer of the tail of the list points to the head. The list may thus be viewed as a ring of elements. In the remainder

17、of this section, we assume that the lists with which we are working are unsorted and doubly linked. 在一個(gè)循環(huán)表中，隊(duì)頭prev指針指向隊(duì)尾元素，隊(duì)尾next指針指向隊(duì)頭元素，整個(gè)鏈表元素組成一個(gè)環(huán)。在這一節(jié)以后內(nèi)容中，我們假定，我們所討論都是無(wú)序雙向列表。 第12頁(yè)4.2 Linked lists4.2.1 Searching a linked listThe procedure LIST-SEARCH(L, k) finds the first element with key k in l

18、ist L by a simple linear search, returning a pointer to this element. If no object with key k appears in the list, then NIL is returned. For the linked list in Fig.4-3(a), the call LIST-SEARCH(L, 4) returns a pointer to the third element, and the call LIST-SEARCH(L, 7) returns NIL. 經(jīng)過(guò)一個(gè)簡(jiǎn)單線性查詢(xún)，操作LIST

19、-SEARCH(L, k)找出表L中第一個(gè)值為k元素，并返回它指針。假如表中沒(méi)有值為k對(duì)象，那就返回空值(NIL)。如圖4-3(a)中鏈表，操作LIST-SEARCH(L, 4)返回第三個(gè)元素指針，而LIST-SEARCH(L, 7)返回空值。 第13頁(yè)4.2.2 Inserting into a linked listGiven an element x whose key field has already been set, the LIST-INSERT procedure splices x onto the front of the linked list, as shown in

20、 Fig.4-3(b). 給定一個(gè)元素x，它值域已經(jīng)設(shè)定，操作LIST-INSERT將x插入鏈表頭部,如圖4-3(b)所表示。4.2 Linked lists第14頁(yè)4.2 Linked lists4.2.3 Deleting from a linked listThe procedure LIST-DELETE removes an element x from a linked list L. It must be given a pointer to x, and it then splices x out of the list by updating pointers. If we

21、wish to delete an element with a given key, we must first call LIST-SEARCH to retrieve a pointer to the element.執(zhí)行LIST-DELETE操作，可將元素x從鏈表L中去除。必須先給定指向x指針，經(jīng)過(guò)更新指針將x從鏈表中刪除。假如需要?jiǎng)h除給定值元素，我們必須先執(zhí)行LIST-SEARCH操作，檢索指向元素指針。第15頁(yè)4.2 Linked lists4.2.4 SentinelsThe code for LIST-DELETE would be simpler if we could ig

22、nore the boundary conditions at the head and tail of the list.假如我們不考慮鏈表頭部和尾部邊界情況，對(duì)操作LIST-DELETE編碼會(huì)更簡(jiǎn)單。第16頁(yè)4.2 Linked lists4.2.4 SentinelsFig.4-4 A circular, doubly linked list with a sentinel 第17頁(yè)4.2 Linked lists4.2.4 SentinelsA sentinel is a dummy object that allows us to simplify boundary conditio

23、ns. For example, suppose that we provide with list L an object nilL that represents NIL but has all the fields of the other list elements. Wherever we have a reference to NIL in list code, we replace it by a reference to the sentinel nilL. As shown in Fig.4-4, this turns a regular doubly linked list

24、 into a circular, doubly linked list with a sentinel, in which the sentinel nilL is placed between the head and tail; the field nextnilL points to the head of the list, and prevnilL points to the tail.利用標(biāo)志這么啞元實(shí)體，我們能夠簡(jiǎn)化邊界條件判定。比如，假設(shè)我們?yōu)殒湵鞮設(shè)置一個(gè)實(shí)體nilL，它值域?yàn)榭?，不過(guò)它卻指向鏈表中全部其它元素。我們?cè)诖a行中，所使用到NIL之處，都能夠由標(biāo)志nilL代替。

25、如圖4-4所表示，這將一個(gè)普通雙向鏈表變成一個(gè)帶標(biāo)志雙向鏈表，其中標(biāo)志于表頭和表尾之間，即：指針域nextnilL指向表頭，prevnilL指向表尾。第18頁(yè)4.2 Linked lists4.2.4 SentinelsSimilarly, both the next field of the tail and the prev field of the head point to nilL. Since nextnilL points to the head, we can eliminate the attribute headL altogether, replacing referen

26、ces to it by references to nextnilL. An empty list consists of just the sentinel, since both nextnilL and prevnilL can be set to nilL. 類(lèi)似地，隊(duì)尾next域和隊(duì)頭prev域都指向nilL。因?yàn)閚extnilL指向表頭，我們能夠完全去掉指針headL，取而代之是使用nextnilL。一個(gè)空表只包含有標(biāo)志，因?yàn)橹羔樣騨extnilL和prevnilL都指向nilL。第19頁(yè)慣用英漢互譯技巧一、增譯法依據(jù)英漢兩種語(yǔ)言不一樣思維方式、語(yǔ)言習(xí)慣和表示方式，在翻譯時(shí)增添一

27、些詞、短句或句子，方便更準(zhǔn)確地表示出原文所包含意義。這種方式多半用在漢譯英里。1、漢語(yǔ)無(wú)主句較多，而英語(yǔ)句子普通都要有主語(yǔ)。所以在翻譯漢語(yǔ)無(wú)主句時(shí)候，除了少數(shù)可用英語(yǔ)無(wú)主句、被動(dòng)語(yǔ)態(tài)或“There be”結(jié)構(gòu)來(lái)翻譯以外，普通都要依據(jù)語(yǔ)境補(bǔ)出主語(yǔ)，使句子完整。2、英漢兩種語(yǔ)言在名詞、代詞、連詞、介詞和冠詞使用方法上也存在很大差異。英語(yǔ)中代詞使用頻率較高，凡說(shuō)到人器官和歸某人全部或與某人相關(guān)事物時(shí)，必須在前面加上物主代詞。所以，在漢譯英時(shí)需要增補(bǔ)物主代詞，而在英譯漢時(shí)又需要依據(jù)情況適當(dāng)?shù)貏h減。3、英語(yǔ)詞與詞、詞組與詞組以及句子與句子邏輯關(guān)系普通用連詞來(lái)表示，而漢語(yǔ)則往往經(jīng)過(guò)上下文和語(yǔ)序來(lái)表示這種關(guān)

28、系。所以，在漢譯英時(shí)經(jīng)常需要增補(bǔ)連詞。英語(yǔ)句子離不開(kāi)介詞和冠詞。4、在漢譯英時(shí)還要注意增補(bǔ)一些原文中暗含而沒(méi)有明言詞語(yǔ)和一些概括性、注釋性詞語(yǔ)，以確保譯文意思完整。 第20頁(yè)慣用英漢互譯技巧一、增譯法1.Indeed, the reverse is true 實(shí)際情況恰好相反。（增譯名詞）2.這是這兩代計(jì)算機(jī)之間又一個(gè)共同點(diǎn)。This is yet another common point between the computers of the two generations.（增譯介詞）3.Individual mathematicians often have their own way

29、 of pronouncing mathematical expressions and in many cases there is no generally accepted “correct” pronunciation.每個(gè)數(shù)學(xué)家對(duì)數(shù)學(xué)公式經(jīng)常有各自讀法，在許多情況下，并不存在一個(gè)普遍接收所謂“正確”讀法。(增加隱含意義詞)4.只有在可能發(fā)生混同、或要強(qiáng)調(diào)其觀點(diǎn)時(shí)，數(shù)學(xué)家才使用較長(zhǎng)讀法It is only when confusion may occur, or where he/she wishes to emphasis the point, that the mathematic

30、ian will use the longer forms. (增加主語(yǔ))第21頁(yè)慣用英漢互譯技巧二、省譯法這是與增譯法相對(duì)應(yīng)一個(gè)翻譯方法，即刪去不符合目口號(hào)思維習(xí)慣、語(yǔ)言習(xí)慣和表示方式詞，以防止譯文累贅。增譯法例句反之即可。又如：1.You will be staying in this hotel during your visit in Beijing.你在北京訪問(wèn)期間就住在這家飯店里。（省譯物主代詞）2.I hope you will enjoy your stay here.希望您在這兒過(guò)得愉快。（省譯主語(yǔ)）3.中國(guó)政府從來(lái)重視環(huán)境保護(hù)工作。The Chinese governmen

31、t has always attached great importance to environmental protection. (省譯名詞)4.The development of IC made it possible for electronic devices to become smaller and smaller.集成電路發(fā)展是電子器件能夠做得越來(lái)越小。(省譯形式主語(yǔ)it)第22頁(yè)慣用英漢互譯技巧三、轉(zhuǎn)換法 在翻譯過(guò)程中，為了使譯文符合目口號(hào)表述方式、方法和習(xí)慣，對(duì)原句中詞類(lèi)、句型和語(yǔ)態(tài)等進(jìn)行轉(zhuǎn)換：1、在詞性方面，把名詞轉(zhuǎn)換為代詞、形容詞、動(dòng)詞；把動(dòng)詞轉(zhuǎn)換成名詞、形容詞、副

32、詞、介詞；把形容詞轉(zhuǎn)換成副詞和短語(yǔ)。2、在句子成份方面，把主語(yǔ)變成狀語(yǔ)、定語(yǔ)、賓語(yǔ)、表語(yǔ)；把謂語(yǔ)變成主語(yǔ)、定語(yǔ)、表語(yǔ)；把定語(yǔ)變成狀語(yǔ)、主語(yǔ)；把賓語(yǔ)變成主語(yǔ)。3、在句型方面，把并列句變成復(fù)合句，把復(fù)合句變成并列句，把狀語(yǔ)從句變成定語(yǔ)從句。4、在語(yǔ)態(tài)方面，能夠把主動(dòng)語(yǔ)態(tài)變?yōu)楸粍?dòng)語(yǔ)態(tài)。 第23頁(yè)慣用英漢互譯技巧三、轉(zhuǎn)換法 1. Too much exposure to TV programs will do great harm to the eyesight of children.孩子們看電視過(guò)多會(huì)大大地?fù)p壞視力。(名詞轉(zhuǎn)動(dòng)詞)2. 因?yàn)槲覀儗?shí)施了改革開(kāi)放政策，我國(guó)綜合國(guó)力有了顯著增強(qiáng)。Than

33、ks to the introduction of our reform and opening policy, our comprehensive national strength has greatly improved. (動(dòng)詞轉(zhuǎn)名詞)3. 時(shí)間不早了，我們回去吧！We dont have much time left. Lets go back. (句型轉(zhuǎn)換)第24頁(yè)慣用英漢互譯技巧四、拆句法和合并法 1.Increased cooperation with China is in the interests of the United States.同中國(guó)加強(qiáng)合作，符合美國(guó)利益。（

34、在主謂連接處拆譯）3. 中國(guó)是個(gè)大國(guó)，百分之八十人口從事農(nóng)業(yè)，但耕地只占土地面積十分之一，其余為山脈、森林、城鎮(zhèn)和其它用地。China is a large country with four-fifths of the population engaged in agriculture, but only one tenth of the land is farmland, the rest being mountains, forests and places for urban and other uses.（合譯法）4. Packet switching is a method of

35、slicing digital messages into parcels called “packets,” sending the packets along different communication paths as they become available, and then reassembling the packets once they arrive at their destination.分組交換是傳輸數(shù)據(jù)一個(gè)方法，它先將數(shù)據(jù)信息分割成許多稱(chēng)為“分組”數(shù)據(jù)信息包；當(dāng)路徑可用時(shí)，經(jīng)過(guò)不一樣通信路徑發(fā)送；當(dāng)?shù)诌_(dá)目標(biāo)地后，再將它們組裝起來(lái)。(將長(zhǎng)定語(yǔ)從句拆成幾個(gè)并列分句)

36、第25頁(yè)慣用英漢互譯技巧五、正譯法和反譯法這兩種方法通慣用于漢譯英，偶然也用于英譯漢。所謂正譯，是指把句子按照與漢語(yǔ)相同語(yǔ)序或表示方式譯成英語(yǔ)。所謂反譯則是指把句子按照與漢語(yǔ)相反語(yǔ)序或表示方式譯成英語(yǔ)。正譯與反譯經(jīng)常含有同義效果，但反譯往往更符合英語(yǔ)思維方式和表示習(xí)慣，所以比較地道 。1.你能夠從因特網(wǎng)上取得這一信息。You can obtain this information on the Internet. （正譯）This information is accessible/available on the Internet. （反譯）2.他突然想到了一個(gè)新主意。Suddenly he

37、 had a new idea. (正譯)He suddenly thought out a new idea. (正譯)A new idea suddenly occurred to/struck him. （反譯）第26頁(yè)慣用英漢互譯技巧六、倒置法在漢語(yǔ)中，定語(yǔ)修飾語(yǔ)和狀語(yǔ)修飾語(yǔ)往往位于被修飾語(yǔ)之前；在英語(yǔ)中，許多修飾語(yǔ)經(jīng)常位于被修飾語(yǔ)之后，所以翻譯時(shí)往往要把原文語(yǔ)序顛倒過(guò)來(lái)。倒置法通慣用于英譯漢, 即對(duì)英語(yǔ)長(zhǎng)句按照漢語(yǔ)習(xí)慣表示法進(jìn)行前后調(diào)換，按意群或進(jìn)行全部倒置，標(biāo)準(zhǔn)是使?jié)h語(yǔ)譯句安排符合當(dāng)代漢語(yǔ)論理敘事普通邏輯次序。有時(shí)倒置法也用于漢譯英。如：1.At this moment, thro

38、ugh the wonder of telecommunications, more people are seeing and hearing what we say than on any other occasions in the whole history of the world.此時(shí)此刻，經(jīng)過(guò)當(dāng)代通信伎倆奇跡，看到和聽(tīng)到我們講話人比整個(gè)世界歷史上任何其它這么場(chǎng)所都要多。（部分倒置）2.改革開(kāi)放以來(lái)，中國(guó)發(fā)生了巨大改變。Great changes have taken place in China since the introduction of the reform and o

39、pening policy.(全部倒置)第27頁(yè)慣用英漢互譯技巧七、包孕法 這種方法多用于英譯漢。所謂包孕是指在把英語(yǔ)長(zhǎng)句譯成漢語(yǔ)時(shí)，把英語(yǔ)后置成份按照漢語(yǔ)正常語(yǔ)序放在中心詞之前，使修飾成份在漢語(yǔ)句中形成前置包孕。但修飾成份不宜過(guò)長(zhǎng)，不然會(huì)形成拖沓或造成漢語(yǔ)句子成份在連接上糾葛。如：1.IP multicasting is a set of technologies that enables efficient delivery of data to many locations on a network.IP多信道廣播是使數(shù)據(jù)向網(wǎng)絡(luò)中許多位置高效傳送一組技術(shù)。2.What brings us together is that we have common interests which transcend those differences. 使我們走到一起，是我們有超越這些分歧共同利益。 第28頁(yè)慣用英漢互譯技巧八、插入法 指把難以處理句子成份用破折號(hào)、括號(hào)或前后逗號(hào)插入譯句中。這種方法主要用于筆譯中