計算機專業(yè)英語Elementary Data Structures市公開課金獎市賽課一等獎?wù)n件

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

2、rflow n. 下溢overflow n. 上溢pseudocode n. 偽碼 4.1 Stacks and queuesAbbreviations:LIFO（last in first out）后進先出FIFO（fisrt in first out）先進先出 第4頁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.棧和隊列都是動態(tài)集合，其中元素由預先定義刪除操作可將其去除。在棧中，最近被插入元素最先被刪除，即棧是按后進先出(LIFO)標準進行；類似，在隊列里，被刪除元素是最早進入隊列，即隊列是以先進先出(FIFO)標準進行。在計算機上，對于棧和隊列有幾個有效實現(xiàn)方法，這一節(jié)我們給出怎樣用簡單數(shù)組來實現(xiàn)它們。 第5頁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.棧中插入元素操作通常稱為入棧(PUSH)，刪除操作稱為出棧(POP)，這里不考慮刪除那個元素。這些名字起源于實際堆棧，就像餐廳里使用帶有彈簧座一疊盤子：因為只有頂部盤子是方便取用，所以盤子從這一疊中取出次序與其被放入次序是相反。第6頁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.)我們稱對隊列進行插入操作為入隊 (ENQUEUE)，刪除操作為出隊(DEQUEUE)；同棧中出棧操作一樣，出隊操作不考慮其中元素。隊列先進先出標準就像排隊等候注冊一行人群。隊列有一個頭部和一個尾部。當一個元素入隊，它就成為隊列尾部，就像一個新來學生成為隊尾一樣；出隊元素總是隊列頭部元素，像是站在隊列最前學生是排隊最久人一樣。(慶幸是，對于計算機元素，我們無須擔心插隊情況。) 第7頁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.鏈表這個數(shù)據(jù)結(jié)構(gòu)中對象都以線性次序排列，但不一樣于數(shù)組次序是由數(shù)組下標確定，鏈表次序是由每個對

11、象指針確定。鏈表為動態(tài)集合提供了一個簡單、靈活表示形式。第8頁4.2 Linked listsFig.4-3 A doubly linked list 第9頁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中每個元素都是一個實體，由一個數(shù)值域和兩個指針域組成，其中兩個指針分別是：next和prev，實體也能夠包含子數(shù)據(jù)。給定表中一個元素x，nextx指出它在鏈表中后繼，prevx指出它前趨。prevx = NIL表示元素x沒有前趨，所以x是第一個元素，即隊頭元素；假如nextx = NIL，表示x沒有后繼，也就是最終一個元素，隊尾元素。指針headL指向隊列中第

14、一個元素，假如headL = NIL表示隊列為空。第10頁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. 一個鏈表能夠是下面幾個形式之一：單向鏈表或雙向鏈表，有序或無序，循環(huán)或非循環(huán)。對于單向鏈表，我們就無須對每個元素使用prev指針了。假如一個表是有序，

16、表線序和表中存放元素值線序是一致，即：最小值元素是隊列頭部元素，最大值元素是隊尾元素。假如一個表是無序，其中元素能夠以任何次序出現(xiàn)。第11頁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. 在一個循環(huán)表中，隊頭prev指針指向隊尾元素，隊尾next指針指向隊頭元素，整個鏈表元素組成一個環(huán)。在這一節(jié)以后內(nèi)容中，我們假定，我們所討論都是無序雙向列表。 第12頁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)過一個簡單線性查詢，操作LIST

19、-SEARCH(L, k)找出表L中第一個值為k元素，并返回它指針。假如表中沒有值為k對象，那就返回空值(NIL)。如圖4-3(a)中鏈表，操作LIST-SEARCH(L, 4)返回第三個元素指針，而LIST-SEARCH(L, 7)返回空值。 第13頁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). 給定一個元素x，它值域已經(jīng)設(shè)定，操作LIST-INSERT將x插入鏈表頭部,如圖4-3(b)所表示。4.2 Linked lists第14頁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)過更新指針將x從鏈表中刪除。假如需要刪除給定值元素，我們必須先執(zhí)行LIST-SEARCH操作，檢索指向元素指針。第15頁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.假如我們不考慮鏈表頭部和尾部邊界情況，對操作LIST-DELETE編碼會更簡單。第16頁4.2 Linked lists4.2.4 SentinelsFig.4-4 A circular, doubly linked list with a sentinel 第17頁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.利用標志這么啞元實體，我們能夠簡化邊界條件判定。比如，假設(shè)我們?yōu)殒湵鞮設(shè)置一個實體nilL，它值域為空，不過它卻指向鏈表中全部其它元素。我們在代碼行中，所使用到NIL之處，都能夠由標志nilL代替。

25、如圖4-4所表示，這將一個普通雙向鏈表變成一個帶標志雙向鏈表，其中標志于表頭和表尾之間，即：指針域nextnilL指向表頭，prevnilL指向表尾。第18頁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. 類似地，隊尾next域和隊頭prev域都指向nilL。因為nextnilL指向表頭，我們能夠完全去掉指針headL，取而代之是使用nextnilL。一個空表只包含有標志，因為指針域nextnilL和prevnilL都指向nilL。第19頁慣用英漢互譯技巧一、增譯法依據(jù)英漢兩種語言不一樣思維方式、語言習慣和表示方式，在翻譯時增添一

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

28、系。所以，在漢譯英時經(jīng)常需要增補連詞。英語句子離不開介詞和冠詞。4、在漢譯英時還要注意增補一些原文中暗含而沒有明言詞語和一些概括性、注釋性詞語，以確保譯文意思完整。 第20頁慣用英漢互譯技巧一、增譯法1.Indeed, the reverse is true 實際情況恰好相反。（增譯名詞）2.這是這兩代計算機之間又一個共同點。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.每個數(shù)學家對數(shù)學公式經(jīng)常有各自讀法，在許多情況下，并不存在一個普遍接收所謂“正確”讀法。(增加隱含意義詞)4.只有在可能發(fā)生混同、或要強調(diào)其觀點時，數(shù)學家才使用較長讀法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. (增加主語)第21頁慣用英漢互譯技巧二、省譯法這是與增譯法相對應(yīng)一個翻譯方法，即刪去不符合目口號思維習慣、語言習慣和表示方式詞，以防止譯文累贅。增譯法例句反之即可。又如：1.You will be staying in this hotel during your visit in Beijing.你在北京訪問期間就住在這家飯店里。（省譯物主代詞）2.I hope you will enjoy your stay here.希望您在這兒過得愉快。（省譯主語）3.中國政府從來重視環(huán)境保護工作。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ā)展是電子器件能夠做得越來越小。(省譯形式主語it)第22頁慣用英漢互譯技巧三、轉(zhuǎn)換法 在翻譯過程中，為了使譯文符合目口號表述方式、方法和習慣，對原句中詞類、句型和語態(tài)等進行轉(zhuǎn)換：1、在詞性方面，把名詞轉(zhuǎn)換為代詞、形容詞、動詞；把動詞轉(zhuǎn)換成名詞、形容詞、副

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

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

34、在主謂連接處拆譯）3. 中國是個大國，百分之八十人口從事農(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ù)一個方法，它先將數(shù)據(jù)信息分割成許多稱為“分組”數(shù)據(jù)信息包；當路徑可用時，經(jīng)過不一樣通信路徑發(fā)送；當?shù)诌_目標地后，再將它們組裝起來。(將長定語從句拆成幾個并列分句)

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

37、 had a new idea. (正譯)He suddenly thought out a new idea. (正譯)A new idea suddenly occurred to/struck him. （反譯）第26頁慣用英漢互譯技巧六、倒置法在漢語中，定語修飾語和狀語修飾語往往位于被修飾語之前；在英語中，許多修飾語經(jīng)常位于被修飾語之后，所以翻譯時往往要把原文語序顛倒過來。倒置法通慣用于英譯漢, 即對英語長句按照漢語習慣表示法進行前后調(diào)換，按意群或進行全部倒置，標準是使?jié)h語譯句安排符合當代漢語論理敘事普通邏輯次序。有時倒置法也用于漢譯英。如：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.此時此刻，經(jīng)過當代通信伎倆奇跡，看到和聽到我們講話人比整個世界歷史上任何其它這么場所都要多。（部分倒置）2.改革開放以來，中國發(fā)生了巨大改變。Great changes have taken place in China since the introduction of the reform and o

39、pening policy.(全部倒置)第27頁慣用英漢互譯技巧七、包孕法 這種方法多用于英譯漢。所謂包孕是指在把英語長句譯成漢語時，把英語后置成份按照漢語正常語序放在中心詞之前，使修飾成份在漢語句中形成前置包孕。但修飾成份不宜過長，不然會形成拖沓或造成漢語句子成份在連接上糾葛。如：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頁慣用英漢互譯技巧八、插入法 指把難以處理句子成份用破折號、括號或前后逗號插入譯句中。這種方法主要用于筆譯中