计算机专业英语Elementary Data Structures市公开课金奖市赛课一等奖课件

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. 属性，性质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.栈和队列都是动态集合，其中元素由预先定义删除操作可将其去除。在栈中，最近被插入元素最先被删除，即栈是按后进先出(LIFO)标准进行；类似，在队列里，被删除元素是最早进入队列，即队列是以先进先出(FIFO)标准进行。在计算机上，对于栈和队列有几个有效实现方法，这一节我们给出怎样用简单数组来实现它们。 第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.链表这个数据结构中对象都以线性次序排列，但不一样于数组次序是由数组下标确定，链表次序是由每个对

11、象指针确定。链表为动态集合提供了一个简单、灵活表示形式。第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中每个元素都是一个实体，由一个数值域和两个指针域组成，其中两个指针分别是：next和prev，实体也能够包含子数据。给定表中一个元素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. 一个链表能够是下面几个形式之一：单向链表或双向链表，有序或无序，循环或非循环。对于单向链表，我们就无须对每个元素使用prev指针了。假如一个表是有序，

16、表线序和表中存放元素值线序是一致，即：最小值元素是队列头部元素，最大值元素是队尾元素。假如一个表是无序，其中元素能够以任何次序出现。第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. 在一个循环表中，队头prev指针指向队尾元素，队尾next指针指向队头元素，整个链表元素组成一个环。在这一节以后内容中，我们假定，我们所讨论都是无序双向列表。 第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. 经过一个简单线性查询，操作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，它值域已经设定，操作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.执行LIST-DELETE操作，可将元素x从链表L中去除。必须先给定指向x指针，经过更新指针将x从链表中删除。假如需要删除给定值元素，我们必须先执行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.利用标志这么哑元实体，我们能够简化边界条件判定。比如，假设我们为链表L设置一个实体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页惯用英汉互译技巧一、增译法依据英汉两种语言不一样思维方式、语言习惯和表示方式，在翻译时增添一

27、些词、短句或句子，方便更准确地表示出原文所包含意义。这种方式多半用在汉译英里。1、汉语无主句较多，而英语句子普通都要有主语。所以在翻译汉语无主句时候，除了少数可用英语无主句、被动语态或“There be”结构来翻译以外，普通都要依据语境补出主语，使句子完整。2、英汉两种语言在名词、代词、连词、介词和冠词使用方法上也存在很大差异。英语中代词使用频率较高，凡说到人器官和归某人全部或与某人相关事物时，必须在前面加上物主代词。所以，在汉译英时需要增补物主代词，而在英译汉时又需要依据情况适当地删减。3、英语词与词、词组与词组以及句子与句子逻辑关系普通用连词来表示，而汉语则往往经过上下文和语序来表示这种关

28、系。所以，在汉译英时经常需要增补连词。英语句子离不开介词和冠词。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.每个数学家对数学公式经常有各自读法，在许多情况下，并不存在一个普遍接收所谓“正确”读法。(增加隐含意义词)4.只有在可能发生混同、或要强调其观点时，数学家才使用较长读法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页惯用英汉互译技巧二、省译法这是与增译法相对应一个翻译方法，即删去不符合目口号思维习惯、语言习惯和表示方式词，以防止译文累赘。增译法例句反之即可。又如：1.You will be staying in this hotel during your visit in Beijing.你在北京访问期间就住在这家饭店里。（省译物主代词）2.I hope you will enjoy your stay here.希望您在这儿过得愉快。（省译主语）3.中国政府从来重视环境保护工作。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.集成电路发展是电子器件能够做得越来越小。(省译形式主语it)第22页惯用英汉互译技巧三、转换法 在翻译过程中，为了使译文符合目口号表述方式、方法和习惯，对原句中词类、句型和语态等进行转换：1、在词性方面，把名词转换为代词、形容词、动词；把动词转换成名词、形容词、副

32、词、介词；把形容词转换成副词和短语。2、在句子成份方面，把主语变成状语、定语、宾语、表语；把谓语变成主语、定语、表语；把定语变成状语、主语；把宾语变成主语。3、在句型方面，把并列句变成复合句，把复合句变成并列句，把状语从句变成定语从句。4、在语态方面，能够把主动语态变为被动语态。 第23页惯用英汉互译技巧三、转换法 1. Too much exposure to TV programs will do great harm to the eyesight of children.孩子们看电视过多会大大地损坏视力。(名词转动词)2. 因为我们实施了改革开放政策，我国综合国力有了显著增强。Than

33、ks to the introduction of our reform and opening policy, our comprehensive national strength has greatly improved. (动词转名词)3. 时间不早了，我们回去吧！We dont have much time left. Lets go back. (句型转换)第24页惯用英汉互译技巧四、拆句法和合并法 1.Increased cooperation with China is in the interests of the United States.同中国加强合作，符合美国利益。（

34、在主谓连接处拆译）3. 中国是个大国，百分之八十人口从事农业，但耕地只占土地面积十分之一，其余为山脉、森林、城镇和其它用地。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.分组交换是传输数据一个方法，它先将数据信息分割成许多称为“分组”数据信息包；当路径可用时，经过不一样通信路径发送；当抵达目标地后，再将它们组装起来。(将长定语从句拆成几个并列分句)

36、第25页惯用英汉互译技巧五、正译法和反译法这两种方法通惯用于汉译英，偶然也用于英译汉。所谓正译，是指把句子按照与汉语相同语序或表示方式译成英语。所谓反译则是指把句子按照与汉语相反语序或表示方式译成英语。正译与反译经常含有同义效果，但反译往往更符合英语思维方式和表示习惯，所以比较地道 。1.你能够从因特网上取得这一信息。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页惯用英汉互译技巧六、倒置法在汉语中，定语修饰语和状语修饰语往往位于被修饰语之前；在英语中，许多修饰语经常位于被修饰语之后，所以翻译时往往要把原文语序颠倒过来。倒置法通惯用于英译汉, 即对英语长句按照汉语习惯表示法进行前后调换，按意群或进行全部倒置，标准是使汉语译句安排符合当代汉语论理叙事普通逻辑次序。有时倒置法也用于汉译英。如：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.此时此刻，经过当代通信伎俩奇迹，看到和听到我们讲话人比整个世界历史上任何其它这么场所都要多。（部分倒置）2.改革开放以来，中国发生了巨大改变。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多信道广播是使数据向网络中许多位置高效传送一组技术。2.What brings us together is that we have common interests which transcend those differences. 使我们走到一起，是我们有超越这些分歧共同利益。 第28页惯用英汉互译技巧八、插入法 指把难以处理句子成份用破折号、括号或前后逗号插入译句中。这种方法主要用于笔译中