计算机专业英语Elementary-Data-Structures省公共课一等奖全国赛课获奖课件.pptx

Computer English Chapter 4 Elementary Data Structures 第1页Key points:useful terms and definitions of data structureDifficult points:Stack,queue,tree第2页Requirements:1.The properties of Stack,Queue,and Linked lists2.掌握惯用英汉互译技巧掌握惯用英汉互译技巧 第3页New Words&Expressions:stack n.栈，堆栈栈，堆栈queue n.队列队列attribute n.属性，性质属性，性质underflow 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 deleted 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 several 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 queues4.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 popped 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 operation 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 takes 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 elements cutting into line.)我们称对队列进行插入操作为入队我们称对队列进行插入操作为入队(ENQUEUE)，删除操作为出队，删除操作为出队(DEQUEUE)；同；同栈中出栈操作一样，出队操作不考虑其中元素。队列先进先出标准就像排队等栈中出栈操作一样，出队操作不考虑其中元素。队列先进先出标准就像排队等候注册一行人群。队列有一个头部和一个尾部。当一个元素入队，它就成为队候注册一行人群。队列有一个头部和一个尾部。当一个元素入队，它就成为队列尾部，就像一个新来学生成为队尾一样；出队元素总是队列头部元素，像是列尾部，就像一个新来学生成为队尾一样；出队元素总是队列头部元素，像是站在队列最前学生是排队最久人一样。站在队列最前学生是排队最久人一样。(庆幸是，对于计算机元素，我们无须担庆幸是，对于计算机元素，我们无须担心插队情况。心插队情况。)第7页4.2 Linked listsA linked list is a data structure in which the objects are arranged 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.链表这个数据结构中对象都以线性次序排列，但不一样于数链表这个数据结构中对象都以线性次序排列，但不一样于数组次序是由数组下标确定，链表次序是由每个对象指针确定。组次序是由数组下标确定，链表次序是由每个对象指针确定。链表为动态集合提供了一个简单、灵活表示形式。链表为动态集合提供了一个简单、灵活表示形式。第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 in 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 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指向队列中第一个元素，假如指向队列中第一个元素，假如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 the 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指针了。指针了。假如一个表是有序，表线序和表中存放元素值线序是一致，即：最小值假如一个表是有序，表线序和表中存放元素值线序是一致，即：最小值元素是队列头部元素，最大值元素是队尾元素。假如一个表是无序，其元素是队列头部元素，最大值元素是队尾元素。假如一个表是无序，其中元素能够以任何次序出现。中元素能够以任何次序出现。第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 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 list 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-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 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 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 ignore 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 conditions.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 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代替。如图代替。如图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 references 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页惯用英汉互译技巧惯用英汉互译技巧一、增译法增译法依据英汉两种语言不一样思维方式、语言习惯和表示方式，在翻译时增添依据英汉两种语言不一样思维方式、语言习惯和表示方式，在翻译时增添一些词、短句或句子，方便更准确地表示出原文所包含意义。这种方式多一些词、短句或句子，方便更准确地表示出原文所包含意义。这种方式多半用在汉译英里。半用在汉译英里。1、汉语无主句较多，而英语句子普通都要有主语。汉语无主句较多，而英语句子普通都要有主语。所以在翻译汉语无主句所以在翻译汉语无主句时候，除了少数可用英语无主句、被动语态或时候，除了少数可用英语无主句、被动语态或“There be”结构来翻译以结构来翻译以外，普通都要依据语境补出主语，使句子完整。外，普通都要依据语境补出主语，使句子完整。2、英汉两种语言在名词、代词、连词、介词和冠词使用方法上也存在很大英汉两种语言在名词、代词、连词、介词和冠词使用方法上也存在很大差异。差异。英语中代词使用频率较高，凡说到人器官和归某人全部或与某人相英语中代词使用频率较高，凡说到人器官和归某人全部或与某人相关事物时，必须在前面加上物主代词。所以，在汉译英时需要增补物主代关事物时，必须在前面加上物主代词。所以，在汉译英时需要增补物主代词，而在英译汉时又需要依据情况适当地删减。词，而在英译汉时又需要依据情况适当地删减。3、英语词与词、词组与词组以及句子与句子逻辑关系普通用连词来表示，英语词与词、词组与词组以及句子与句子逻辑关系普通用连词来表示，而汉语则往往经过上下文和语序来表示这种关系。而汉语则往往经过上下文和语序来表示这种关系。所以，在汉译英时经常所以，在汉译英时经常需要增补连词。英语句子离不开介词和冠词。需要增补连词。英语句子离不开介词和冠词。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 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 mathematician 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 government 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、在、在词性词性方面，把名词转换为代词、形容词、动词；把动词方面，把名词转换为代词、形容词、动词；把动词转换成名词、形容词、副词、介词；把形容词转换成副词和短转换成名词、形容词、副词、介词；把形容词转换成副词和短语。语。2、在、在句子成份句子成份方面，把主语变成状语、定语、宾语、表语；方面，把主语变成状语、定语、宾语、表语；把谓语变成主语、定语、表语；把定语变成状语、主语；把宾把谓语变成主语、定语、表语；把定语变成状语、主语；把宾语变成主语。语变成主语。3、在、在句型句型方面，把并列句变成复合句，把复合句变成并列句，方面，把并列句变成复合句，把复合句变成并列句，把状语从句变成定语从句。把状语从句变成定语从句。4、在、在语态语态方面，能够把主动语态变为被动语态。方面，能够把主动语态变为被动语态。第23页惯用英汉互译技巧惯用英汉互译技巧三、转换法三、转换法 1.Too much exposure to TV programs will do great harm to the eyesight of children.孩子们看电视过多会大大地损坏视力。孩子们看电视过多会大大地损坏视力。(名词转动词名词转动词)2.因为我们实施了改革开放政策，我国综合国力有了显著增强。因为我们实施了改革开放政策，我国综合国力有了显著增强。Thanks 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.同中国加强合作，符合美国利益。同中国加强合作，符合美国利益。（在主谓连接处拆译）（在主谓连接处拆译）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 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.分组交换是传输数据一个方法，它先将数据信息分割成许多称为分组交换是传输数据一个方法，它先将数据信息分割成许多称为“分组分组”数据信息包；当路径可用时，经过不一样通信路径发送；当抵达目标地后，数据信息包；当路径可用时，经过不一样通信路径发送；当抵达目标地后，再将它们组装起来。再将它们组装起来。(将长定语从句拆成几个并列分句将长定语从句拆成几个并列分句)第25页惯用英汉互译技巧惯用英汉互译技巧五、正译法和反译法五、正译法和反译法这两种方法通惯用于汉译英，偶然也用于英译汉。所谓正译，是指把句子这两种方法通惯用于汉译英，偶然也用于英译汉。所谓正译，是指把句子按照与汉语相同语序或表示方式译成英语。所谓反译则是指把句子按照与按照与汉语相同语序或表示方式译成英语。所谓反译则是指把句子按照与汉语相反语序或表示方式译成英语。正译与反译经常含有同义效果，但反汉语相反语序或表示方式译成英语。正译与反译经常含有同义效果，但反译往往更符合英语思维方式和表示习惯，所以比较地道译往往更符合英语思维方式和表示习惯，所以比较地道。1.你能够从因特网上取得这一信息。你能够从因特网上取得这一信息。You can obtain this information on the Internet.（正译）（正译）This information is accessible/available on the Internet.（反译）（反译）2.他突然想到了一个新主意。他突然想到了一个新主意。Suddenly he had a new idea.(正译正译)He suddenly thought out a new idea.(正译正译)A new idea suddenly occurred to/struck him.（反译）（反译）第26页惯用英汉互译技巧惯用英汉互译技巧六、倒置法六、倒置法在汉语中，定语修饰语和状语修饰语往往位于被修饰语之前；在英语中，在汉语中，定语修饰语和状语修饰语往往位于被修饰语之前；在英语中，许多修饰语经常位于被修饰语之后，所以翻译时往往要把原文语序颠倒过许多修饰语经常位于被修饰语之后，所以翻译时往往要把原文语序颠倒过来。倒置法通惯用于英译汉来。倒置法通惯用于英译汉,即对英语长句按照汉语习惯表示法进行前后调即对英语长句按照汉语习惯表示法进行前后调换，按意群或进行全部倒置，标准是使汉语译句安排符合当代汉语论理叙换，按意群或进行全部倒置，标准是使汉语译句安排符合当代汉语论理叙事普通逻辑次序。有时倒置法也用于汉译英。事普通逻辑次序。有时倒置法也用于汉译英。如：如：1.At this moment,through 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 opening 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页惯用英汉互译技巧惯用英汉互译技巧八八、插入法插入法 指把难以处理句子成份用破折号、括号或前后逗号插入译句中。指把难以处理句子成份用破折号、括号或前后逗号插入译句中。这种方法主要用于笔译中。偶然也用于口译中，即用同位语、这种方法主要用于笔译中。偶然也用于口译中，即用同位语、插入语或定语从句来处理一些解释性成份。插入语或定语从句来处理一些解释性成份。如：如：假如说宣告收回香港就会像夫人说假如说宣告收回香港就会像夫人说“带来灾难性影响带来灾难性影响”，那我，那我们将勇敢地面对这个灾难，做出决议。们将勇敢地面对这个灾难，做出决议。If the announcement of the recovery of Hon