Computer English
Chapter 4 Data Structure
Chapter 4 Data Structure
计算机专业英语 4-2
Key points:
useful terms and definitions
of data structure
Difficult points:
Stack,queue,tree
Chapter 4 Data Structure
计算机专业英语 4-3
Requirements:
1,Three reasons for using data structures are
efficiency,abstraction,and reusability.
2,The properties of Stack,Queue,and Tree
3,掌握常用英汉互译技巧
Chapter 4 Data Structure
计算机专业英语 4-4
New Words & Expressions:
harsh table 杂凑 (哈希 )表 priority queues 优先队列
reusability n.复用性 binary tree 二叉树
traversing 遍历，走过 context-free 与上下文无关
4.1 An Introduction to Data Structures
Chapter 4 Data Structure
计算机专业英语 4-5
Data comes in all shapes and sizes,but often it can be organized in the same
way,For example,consider a list of things to do,a list of ingredients in a
recipe,or a reading list for a class,Although each contains a different type
of data,they all contain data organized in a similar way,a list,A list is one
simple example of a data structure,Of course,there are many other
common ways to organize data as well,In computing,some of the most
common organizations are linked lists,stacks,queues,sets,hash tables,trees,
heaps,priority queues,and graphs,Three reasons for using data structures
are efficiency,abstraction,and reusability.
数据以各种形状和大小出现，但是它常常可以用同样的方式来组织。例如,
考虑要做事情的列表、处方成份的清单或一个班级的阅读目录。虽然它们包含不同类型的数据,但他们都包含以一种相似方式组织的数据,一个列表。
列表是数据结构的一个简单例子。当然，还有许多其他组织数据通用方法。
在计算机技术中，一些最常用的组织方式是链接表、堆栈、队列、集合、
哈希表、树、堆、优先队列和图。使用数据结构的三个原因是效率、抽象性和复用性。
4.1 An Introduction to Data Structures
Chapter 4 Data Structure
计算机专业英语 4-6
Efficiency
Data structures organize data in ways that make algorithms more
efficient,For example,consider some of the ways we can organize data
for searching it,One simplistic approach is to place the data in an
array and search the data by traversing element by element until the
desired element is found,However,this method is inefficient because in
many cases we end up traversing every element,By using another type
of data structure,such as a hash table or a binary tree we can search
the data considerably faster.
效率数据结构使用令算法更有效率的方法组织数据。例如，考虑一些我们用来查找数据的组织方式。一种过分简单的方式是将数据放置到数组中，并用遍历的方法找到需要的元素。然而，这种方法是低效率的，因为在许多情况下，我们需要遍历所有元素才能完成。使用其他类型的数据结构,如哈希表和二叉数，我们能够相当快速地搜寻数据 。
4.1 An Introduction to Data Structures
Chapter 4 Data Structure
计算机专业英语 4-7
Abstraction
Data structures provide a more understandable way to look at
data; thus,they offer a level of abstraction in solving problems,
For example,by storing data in a stack,we can focus on things
that we do with stacks,such as pushing and popping elements,
rather than the details of how to implement each operation,In
other words,data structures let us talk about programs in a less
programmatic way.
抽象化数据结构提供一个更好理解的方法查看数据；因此，它们在解决问题中提供一定的抽象化水平。例如，通过把数据储存在堆栈中，我们可以将重点集中在对堆栈的操作上，如使元素进栈和出栈，而不是集中在实现操作的细节上。
换句话说，数据结构使我们以较少的编程方式谈论程序。
4.1 An Introduction to Data Structures
Chapter 4 Data Structure
计算机专业英语 4-8
Reusability
Data structures are reusable because they tend to be modular and
context-free,They are modular because each has a prescribed
interface through which access to data stored in the data structure is
restricted,That is,we access the data using only those operations the
interface defines,Data structures are context-free because they can
be used with any type of data and in a variety of situations or
contexts,In C,we make a data structure store data of any type by
using void pointers to the data rather than by maintaining private
copies of the data in the data structure itself.
复用性,因为数据结构趋向于模块化并和环境无关,所以数据结构是可以复用的。因为每种结构有一个预定的接口,通过该接口限制访问存储在数据结构中的数据，所以它们是模块化的。也就是说,我们只能使用接口定义的那些操作来访问数据。因为数据结构能用于任何类型的数据,并用于多种环境中，所以数据结构与使用环境无关。在 C语言中，我们通过使用空指针，
而不是通过维护非公开的数据备份，使数据结构存储任何类型的数据。
4.1 An Introduction to Data Structures
Chapter 4 Data Structure
计算机专业英语 4-9
New Words & Expressions
inviting adj.引人动心的 contiguous adj.邻近的,接近的
stack n,堆栈 insertion n.插入
deletion n.删除,删除部分 pop 退栈
push 进栈 backtrack v.回溯
pseudocode n.[计 ]伪代码 retrieve v.重新得到； n.找回
pointer n.指针 pertinent adj.有关的,相干的,中肯的
extract vt,取，引 back out 返回
entail vt,使承担,带来 traverse v.遍历
shrink v.收缩 allot vt.分配,充当,依靠
predecessor n.前辈,前任 back and forth adv.来来往往地,来回地
vacancy n.空,空白,空缺 stuff vt.填充,塞满
Abbreviations
LIFO (last-in,first-out) 后进先出
FIFO (first-in,first-out) 先进先出
4.2 Stacks
Chapter 4 Data Structure
计算机专业英语 4-10
One of the properties of a list that makes a linked structure more inviting
than a contiguous one is the need to insert and delete entries inside the list.
Recall that it was such operations that had the potential of forcing the
massive movement of names to fill or create holes in the case of a
contiguous list,If we restrict such operations to the ends of the structure,
we find that the use of a contiguous structure becomes a more convenient
system,An example of this phenomenon is a stack,which is a list in which
all insertions and deletions are performed at the same end of the structure.
A consequence of this restriction is that the last entry entered will always be
the first entry removed--an observation that leads to stacks being known as
last-in,first-out (LIFO) structures.
插入和删除记录的需求是使链接表结构比邻接表结构更诱人的原因之一。
让我们回想一下在邻接表中具有填补和创建存储空缺能力的操作。如果我们限制这种操作只可以在结构的尾部进行，则邻接表就是一种比较方便的系统。这种现象的一个例子就是堆栈。在堆栈中，插入和删除操作都在结构的相同末端进行。如此限制的结果就是最后一个进入表的记录也就是第一个从表中删除的记录。这种结构称为后进先出结构。
4.2 Stacks
Chapter 4 Data Structure
计算机专业英语 4-11
The end of a stack at which entries are inserted and deleted is
called the top of the stack,The other end is sometimes called the
stack's base,To reflect the fact that access to a stack is restricted to
the topmost entry,we use special terminology when referring to
the insertion and deletion operations,The process of inserting an
object on the stack is called a push operation,and the process of
deleting an object is called a pop operation,Thus we speak of
pushing an entry onto a stack and popping an entry off a stack.
堆栈尾部可以进行插入和删除操作的记录称为堆栈的栈顶，
另一端叫做栈底。为了表示如何限制堆栈只能从栈顶访问，
我们用一种特殊的术语来表示插入和删除操作。把一个对象插入堆栈的操作称为进栈操作，而从堆栈中删除一个对象的操作称为出栈操作，所以我们常说将一个条目进栈或者将其出栈。
4.2 Stacks
Chapter 4 Data Structure
计算机专业英语 4-12
Backtracking
A classic application of a stack involves the execution of a
program involving procedures as found in our pseudocode,When
the execution of a procedure is requested,the machine must
transfer its attention to the procedure; yet later,when the procedure
is completed,the machine must return to the original location
before continuing,This means that,when the initial transfer is
made,there must be a mechanism for remembering the location to
which execution ultimately returns.
回溯堆栈的一个典型应用发生在一个程序单元调用一个过程的操作中。为了完成这个调用，机器必须将它的注意力转移到这个过程上；当过程调用结束后，机器必须返回到程序块进行调用时所处的位置。这就意味着必须有一种用来记录操作结束后返回的位置的机制。
4.2 Stacks
Chapter 4 Data Structure
计算机专业英语 4-13
The situation is complicated by the fact that the procedure may
itself request the execution of another procedure,which may
request still another,and so on (Figure 7.9),Consequently,the
return locations being remembered begin to pile up,Later,as each
of these procedures is completed,execution must be returned to
the proper place within the program unit that called the completed
procedure,A system is therefore needed to save the return
locations and later retrieve them in the proper order.
如果一个被调用的过程本身还要调用其他过程，而那些过程同样也需要调用另外的过程，这样一来整个情形就会很复杂。
因此，返回地址的记忆就开始堆积。然后，当每一个过程都结束后，操作必须返回到被称为完成过程的程序块中的合适位置。因此，系统需要按照适当的顺序存储和找回返回地址。
4.2 Stacks
Chapter 4 Data Structure
计算机专业英语 4-14
A stack is an ideal structure for such a system,As each procedure
is called,a pointer to the pertinent return Location is pushed on a
stack,and as each procedure is completed,the top entry from the
stack is extracted with the assurance of obtaining a pointer to the
proper return location,This example is representative of stack
applications in general in that it demonstrates the relationship
between stacks and the process of backtracking,Indeed,the
concept of a stack is inherent in any process that entails backing
out of a system in the opposite order from which it was entered.
堆栈是满足这种需要的理想结构。当一个过程被调用时，将指向返回地址的指针进栈。然后，当一个过程完成时，将栈顶条目出栈，程序就可以准确得到返回地址。这是应用栈的一个典型例子，它表明了栈和回溯过程的关系。在任何可以从进入端反向返回系统的过程中，堆栈的概念是与生俱来的。
4.2 Stacks
Chapter 4 Data Structure
计算机专业英语 4-15
As another example of backtracking,suppose we want to print the
names in a linked list in reverse order--that is,last name first,Our
problem is that the only way we can access the names is by
following the linked structure,Thus we need a way of holding
each name retrieved until all of the names that follow have been
retrieved and printed,Our solution is to traverse the list from its
beginning to its end while pushing the names we find onto a stack.
After reaching the end of the list,we print the names as we pop
them off the stack.
我们在来举另一个例子，假设反向输出一张链接表中的姓名，也就是把最后一个名字第一个输出。问题是我们只能跟着链接结构访问姓名。因此，
我们需要一种方式，通过这种方式，我们可以保持每一个姓名能被检索，
直到排列在这个姓名之后的姓名被得到并输出。我们的方案是从链接表的开始顺序遍历到结尾，与此同时把每一个姓名按照遍历顺序进栈。当到达链接表的末尾后，我们通过出栈操作来输出姓名。
4.2 Stacks
Chapter 4 Data Structure
计算机专业英语 4-16
Stack Implementation
To implement a stack structure in a computer's memory,it is customary to
reserve a block of contiguous memory cells large enough to accommodate
the stack as it grows and shrinks,(Determining the size of this block can
often be a critical decision,If too little room is reserved,the stack
ultimately exceeds the allotted storage space; if too much room is reserved,
memory space will be wasted.) One end of this block is designated as the
stack's base,It is here that the first entry pushed on the stack is stored,with
each additional entry being placed next to its predecessor as the stack
grows toward the other end of the reserved block.
栈的实现为了在计算机存储中实现栈结构，一般采取的方法是保留一块足够容纳栈大小变化的内存单元。（通常来说，确定块的大小是一个很重要的任务。如果保留的空间过小，那么栈最后可能从所分配的存储空间中溢出；而如果保留的空间过大，又是一种浪费。）块的一端作为栈底，栈的第一条数据会被存储在这里，以后的条目被依次放置在它之后的存储单元中，也就是堆栈向另外一端增加。
4.2 Stacks
Chapter 4 Data Structure
计算机专业英语 4-17
Thus,as entries are pushed and popped,the top of the stack moves
back and forth within the reserved block of memory cells,A means
is therefore needed to maintain a record of the location of the top
entry,For this purpose,the address of the top entry is stored in an
additional memory cell known as the stack pointer,That is,the
stack pointer points to the top of the stack.
因此，在条目进栈和出栈的时候，栈顶的位置就在存储单元块中前后移动。为了保存这个位置的轨迹，栈顶条目的地址被存储在一个附加的存储单元中，这个附加的存储单元被被称为堆栈指针。也就是说，堆栈指针就是一个指向栈顶的指针。
4.2 Stacks
Chapter 4 Data Structure
计算机专业英语 4-18
The complete system,as illustrated in Figure 4-1,works as follows:
To push a new entry on the stack,we first adjust the stack pointer
to point to the vacancy just beyond the top of the stack and then
place the new entry at this location,To pop an entry from the stack,
we read the data pointed to by the stack pointer and then adjust the
pointer to point to the next entry down on the stack.
一个完整的系统（如图 4-1所示）是这样工作的：为了把一条新的数据压入堆栈，我们首先调整堆栈指针，使之指向当前栈顶之前的空白。然后将新的条目置于此处。为了将条目从堆栈中弹出，我们首先读出堆栈指针所指向的数据，然后调整此指针指向堆栈中的下一条数据所在的存储单元。
4.2 Stacks
Chapter 4 Data Structure
计算机专业英语 4-19
As we observed in the case of lists,a programmer would
probably find it advantageous to write procedures that
perform these push and pop operations so that the stack could
be used as an abstract tool,Note that these procedures should
handle such special cases as attempts to pop entries from an
empty stack and to push entries onto a full stack,In particular,
a complete stack system would probably contain procedures
for pushing entries,popping entries,testing for an empty stack,
and testing for a full stack.
同我们观察到表中的情况一样，程序员也可以将堆栈编写成一个可以进行进栈和出栈操作的抽象工具。注意，这些过程应该可以处理诸如试图从空栈中弹出数据，或者将数据压入一个已经填满的堆栈等特殊情况。所以一个完整的堆栈系统应该包括进栈、出栈、测试堆栈是否空或满的功能。
4.2 Stacks
Chapter 4 Data Structure
计算机专业英语 4-20
A stack organized in a contiguous block of memory cells exhibits little
difference between the conceptual structure and the actual structure
in main memory,Suppose,however,that we cannot reserve a fixed
block of memory and be assured that the stack will always fit,A
solution is to implement the stack as a linked structure similar to that
of a list,This avoids the limitations of restricting the stack to a fixed-
size block,since it allows the entries in the stack to be stuffed into
small pieces of available space anywhere in memory,In such a
situation,the conceptual stack structure will be quite different from
the actual arrangement of the data in memory.
存储在存储单元连续块中的栈展现出主存储器中概念结构与实际之间的一定差异。假设我们不能预测栈的大小，我们就不能保留一个总能满足堆栈的固定大小的存储块。一种解决方法就是实现一种与表结构相似的链接结构栈。
这种方法避免了将堆栈限定在一块固定块中的局限性，因为它允许将新的条目插入存储器中任何一块足够大的空闲空间中。在这种情况下，概念上的堆栈结构与其在存储器中实际的数据组织方式就大不相同了。
4.2 Stacks
Chapter 4 Data Structure
计算机专业英语 4-21
New Words & Expressions
queue n.行列,队列 ; vi.排队 cafeteria n.自助餐厅
rear n.后面,背后,后方 set aside 留出，拨出
head pointer 头指针 tail pointer 尾指针
crawl vi.& n,爬行,蠕动,徐徐行进
egocentric adj.自我中心的
consumption n.消费,消费量 side effect 副作用
migrate vi.移动,移植 ; vt.使移居,使移植
circular queue 循环队列 envision vt.想象,预想
bridge vt.跨接,接通
4.3 Queues
Chapter 4 Data Structure
计算机专业英语 4-22
In contrast to a stack in which both insertions and deletions
are performed at the same end,a queue is a list in which all
insertions are performed at one end while all deletions are
made at the other,We have already met this structure in
relation to waiting lines,where we recognized it as being a
first-in,first-out (FIFO) storage system,Actually,the concept
of a queue is inherent in any system in which objects are
served in the same order in which they arrive.
4.3 Queues
栈的插入与删除操作都是在表的相同端进行的。而与此不同，
队列是插入和删除操作分别在两端进行的表。我们已经遇到过这种与等待队列相关的结构，在此种情况中，我们把它当作是一种先进先出的存储系统。实际上，在那些对象输入与输出顺序相同的系统中，队列的概念是与生俱来的。队列的结尾从等待队列的关联中得到名字。
Chapter 4 Data Structure
计算机专业英语 4-23
The ends of a queue get their names from this waiting-line
relationship,The end at which entries are removed is called
the head (or sometimes the front) of the queue just as we say
that the next person to be served in a cafeteria is at the head
(or front) of the line,Similarly,the end of the queue at which
new entries are added is called the tail (or rear).
4.3 Queues
结尾处，也就是条目被移出队列的地方，被称为队列的队首
（有时候也称为队前），这就好像我们在快餐厅中下一个将点餐的顾客为一队的队首一样。同样，队列的尾部，也就是条目被添加的地方，被称为队尾（或者队后）。
Chapter 4 Data Structure
计算机专业英语 4-24
We can implement a queue in a computer's memory within a
block of contiguous cells in a way similar to our storage of a
stack,Since we need to perform operations at both ends of the
structure,we set aside two memory cells to use as pointers
instead of just one,as we did for a stack,One of these pointers,
called the head pointers keeps track of the head of the queue;
the other,called the tail pointer,keeps track of the tail.
4.3 Queues
我们可以像存储栈那样通过连续单元组成的存储块在计算机主存储器中实现队列。因为我们需要在此结构的两端都进行操作，我们分配出两个存储单元用来当作指针，而非栈中那样仅仅需要一个单元来存储指针。其中的一个指针被称为头指针，用来保持队列头的轨迹；另一个指针被称为尾指针，
用来保持队尾的轨迹。
Chapter 4 Data Structure
计算机专业英语 4-25
When the queue is empty,both of these pointers point to the
same location,Each time an entry is inserted,it is placed in the
location pointed to by the tail pointer and then the tail pointer
is adjusted to point toward the next unused location,In this
manner,the tail pointer is always pointing to the first vacancy
at the tail of the queue,Removing an entry from the queue
involves extracting the entry pointed to by the head pointer
and then adjusting the head pointer to point toward the entry
that followed the removed entry.
4.3 Queues
如果一个队列为空，那么两个指针应该指向相同的位置。每当新的条目被插入时，均会被置于尾指针所指向的位置，同时修改尾指针，使之指向下一个未使用的位置。这样，尾指针总是指向队尾后的第一空闲存储单元。
将一条数据移出队列的操作包括将头指针指向的条目取出，同时调整头指针使之指向排在被移出条目之后的位置 。
Chapter 4 Data Structure
计算机专业英语 4-26
A problem remains with the storage system as described thus
far,If left unchecked,the queue crawls slowly through
memory like a glacier,destroying any other data in its path
(Figure 4.2),This movement is the result of the rather
egocentric policy of inserting each new entry by merely placing
it next to the previous one and repositioning the tail pointer
accordingly,If we add enough entries,the tail of the queue
ultimately extends all the way to the end of the machine's
memory.
4.3 Queues
以上描述的存储系统仍然存在着问题。如果剩余的存储器未被检查，队列会像冰河一样在存储器中增长，同时将在此道路上的所有其他数据破坏
（如图所示）。造成这种移动的相当一部分原因在于插入新条目时使用的
“利己”策略，即在插入是仅仅将新数据置于当前队尾之后，同时重置尾指针。如果我们添加足够的条目，那么队尾最后就会从计算机存储器中溢出。
Chapter 4 Data Structure
计算机专业英语 4-27
This consumption of memory is not the result of the queue's size but
is a side effect of the queue's access procedure,(A small yet active
queue can easily require more of a machine's memory resources
than a large,inactive one.) One solution to this memory space
problem might be to move the entries in a queue forward as the
leading ones are removed,in the same manner as people waiting to
buy theater tickets step forward each time a person has been served.
However,this mass movement of data would be very inefficient.
What we need is a way of confining the queue to one area of memory
without being forced to perform major rearrangements of data.
4.3 Queues
存储器的消耗问题并不是因队列的大小而生的，其真正原因在于队列的实现问题。
（一个小而动态变化的队列比一个大而保持不变的队列需要更多的机器存储资源。）解决存储器空间问题的一个可能方法是：当最前面的条目被移出时,前移队列中的其他条目，就好像人们在购买戏票时所采用的方法一样，每当一个人买到票后，就前移一人。然而这种方法在计算机中运行的效率很低，因为它将需要对数据进行大量的移动。
Chapter 4 Data Structure
计算机专业英语 4-28
A common solution is to set aside a block of memory for the queue,
start the queue at one end of the block,and let the queue migrate
toward the other end of the block,Then,when the tail of the queue
reaches the end of the block,we merely start inserting additional
entries back at the original end of the block,which by this time is
vacant,Likewise,when the last entry in the block finally becomes
the head of the queue and is removed,the head pointer is adjusted
back to the beginning of the block where other entries are,by this
time,waiting,In this manner,the queue chases itself around within
the block rather than wandering off through memory.
4.3 Queues
用来在计算机中控制队列的最一般的方法是为队列分配一块存储器，从存储块的末端开始存储队列，并且让队列向另一端增长。然而当队尾到达块的末端，即队列为空时，我们开始将新的条目反向于末端的方向插入。同样，当队列的最后一条成为队头并被移出时，调整头指针回到块的开端，
同时在此等待。在此方法下，队列在一块区域内循环而不会出现内存溢出情况。
Chapter 4 Data Structure
计算机专业英语 4-29
Such a technique results in an implementation that is called a
circular queue because the effect is that of forming a loop out
of the block of memory cells allotted to the queue,As far as the
queue is concerned,the last cell in the block is adjacent to the
first cell.
4.3 Queues
采用此技术的实现方法称为循环队列，因为分配给队列的一块存储单元组成了一个环。就一个队列而言，存储块的最后一个单元与它的第一个单元相邻。
Chapter 4 Data Structure
计算机专业英语 4-30
Once again,we should recognize the difference between the
conceptual structure envisioned by the user of a queue and the
actual cyclic structure implemented in the machine's memory.
As in the case of the previous structures,these differences are
normally bridged by software,That is along with the collection
of memory cells used for data storage,a queue implementation
should include a collection of procedures that insert and
remove entries from the queue as well as detect whether the
queue is empty or full.
4.3 Queues
我们应该再次认识到队列使用者使用的概念结构与实际在计算机存储器中实现的循环结构之间的差异。在前一个结构的例子中，这些差异通常是通过软件来衔接的。也就是说，连同存储数据需要的一组存储单元，队列的实现应该包括一组用来插入和移出队列条目和探测队列是否为空或满的过程函数。然后，开发软件其他单元的程序员可以通过这些方法来实现队列的插入和移出操作，而不用关心其在存储器中的实际实现。
Chapter 4 Data Structure
计算机专业英语 4-31
常用英汉互译技巧一,增译法根据英汉两种语言不同的思维方式、语言习惯和表达方式,在翻译时增添一些词、短句或句子，以便更准确地表达出原文所包含的意义。 这种方式多半用在汉译英里。
1、汉语无主句较多，而英语句子一般都要有主语，所以在翻译汉语无主句的时候，除了少数可用英语无主句、被动语态或,There be…” 结构来翻译以外，一般都要根据语境补出主语，使句子完整。
2、英汉两种语言在名词、代词、连词、介词和冠词的使用方法上也存在很大差别。英语中代词使用频率较高，凡说到人的器官和归某人所有的或与某人有关的事物时，必须在前面加上物主代词。因此，在汉译英时需要增补物主代词，而在英译汉时又需要根据情况适当地删减。
3、英语词与词、词组与词组以及句子与句子的逻辑关系一般用连词来表示，
而汉语则往往通过上下文和语序来表示这种关系。因此，在汉译英时常常需要增补连词。英语句子离不开介词和冠词。
4、在汉译英时还要注意增补一些原文中暗含而没有明言的词语和一些概括性、注释性的词语，以确保译文意思的完整。
Chapter 4 Data Structure
计算机专业英语 4-32
常用英汉互译技巧一,增译法例 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,(增加主语 )
Chapter 4 Data Structure
计算机专业英语 4-33
常用英汉互译技巧二,省译法这是与增译法相对应的一种翻译方法，即删去不符合目标语思维习惯、语言习惯和表达方式的词，以避免译文累赘。增译法的例句反之即可。又如,
例 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)
Chapter 4 Data Structure
计算机专业英语 4-34
常用英汉互译技巧三、转换法在翻译过程中，为了使译文符合目标语的表述方式、方法和习惯，对原句中的词类、句型和语态等进行转换：
1、在词性方面，把名词转换为代词、形容词、动词；把动词转换成名词、形容词、副词、介词；把形容词转换成副词和短语。
2、在句子成分方面，把主语变成状语、定语、宾语、表语；
把谓语变成主语、定语、表语；把定语变成状语、主语；把宾语变成主语。
3、在句型方面，把并列句变成复合句，把复合句变成并列句，
把状语从句变成定语从句。
4、在语态方面，可以把主动语态变为被动语态。
Chapter 4 Data Structure
计算机专业英语 4-35
常用英汉互译技巧三、转换法例 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 don’t have much time left,Let’s go back,( 句型转换 )
Chapter 4 Data Structure
计算机专业英语 4-36
常用英汉互译技巧四、拆句法和合并法例 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.
分组交换是传输数据的一种方法，它先将数据信息分割成许多称为“分组”
的数据信息包；当路径可用时，经过不同的通信路径发送；当到达目的地后，再将它们组装起来。 (将长定语从句拆成几个并列的分句 )
Chapter 4 Data Structure
计算机专业英语 4-37
常用英汉互译技巧五、正译法和反译法这两种方法通常用于汉译英，偶尔也用于英译汉。所谓正译，是指把句子按照与汉语相同的语序或表达方式译成英语。所谓反译则是指把句子按照与汉语相反的语序或表达方式译成英语。正译与反译常常具有同义的效果，
但反译往往更符合英语的思维方式和表达习惯。因此比较地道 。
例 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,（反译）
Chapter 4 Data Structure
计算机专业英语 4-38
常用英汉互译技巧六、倒置法在汉语中，定语修饰语和状语修饰语往往位于被修饰语之前；在英语中，
许多修饰语常常位于被修饰语之后，因此翻译时往往要把原文的语序颠倒过来。 倒置法通常用于英译汉,即对英语长句按照汉语的习惯表达法进行前后调换，按意群或进行全部倒置，原则是使汉语译句安排符合现代汉语论理叙事的一般逻辑顺序。有时倒置法也用于汉译英 。 如：
例 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.(全部倒置 )
Chapter 4 Data Structure
计算机专业英语 4-39
常用英汉互译技巧七、包孕法这种方法多用于英译汉。所谓包孕是指在把英语长句译成汉语时，把英语后置成分按照汉语的正常语序放在中心词之前，使修饰成分在汉语句中形成前置包孕。但修饰成分不宜过长，否则会形成拖沓或造成汉语句子成分在连接上的纠葛 。 如：
例 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,
使我们走到一起的，是我们有超越这些分歧的共同利益
Chapter 4 Data Structure
计算机专业英语 4-40
常用英汉互译技巧八,插入法指把难以处理的句子成分用破折号、括号或前后逗号插入译句中。这种方法主要用于笔译中。偶尔也用于口译中，即用同位语、插入语或定语从句来处理一些解释性成分 。
如,如果说宣布收回香港就会像夫人说的“带来灾难性的影响”，那我们将勇敢地面对这个灾难，做出决策。
If the announcement of the recovery of Hong Kong would bring
about,as Madam put it,“disastrous effects,” we will face that
disaster squarely and make a new policy decision.
Chapter 4 Data Structure
计算机专业英语 4-41
常用英汉互译技巧九、重组法在进行英译汉时，为了使译文流畅和更符合汉语叙事论理的习惯，在捋清英语长句的结构、弄懂英语原意的基础上，彻底摆脱原文语序和句子形式，对句子进行重新组合。
如,Decision must be made very rapidly; physical endurance is
tested as much as perception,because an enormous amount of
time must be spent making certain that the key figures act on
the basis of the same information and purpose.
必须把大量时间花在确保关键人物均根据同一情报和目的行事，
而这一切对身体的耐力和思维能力都是一大考验。因此，一旦考虑成熟，决策者就应迅速做出决策。
Chapter 4 Data Structure
计算机专业英语 4-42
常用英汉互译技巧十、综合法指把难以处理的句子成分用破折号、括号或前后逗号插入译句中。这种方法主要用于笔译中。偶尔也用于口译中，即用同位语、插入语或定语从句来处理一些解释性成分 。
如：
如果说宣布收回香港就会像夫人说的“带来灾难性的影响”，
那我们将勇敢地面对这个灾难，做出决策。
If the announcement of the recovery of Hong Kong would bring
about,as Madam put it,“disastrous effects,” we will face that
disaster squarely and make a new policy decision.
Chapter 4 Data Structure
计算机专业英语 4-43
常用英汉互译技巧十、综合法是指单用某种翻译技巧无法译出时，着眼篇章，以逻辑分析为基础，同时使用转换法、倒置法、增译法、省译法、拆句法等多种翻译技巧的方法。
如,Behind this formal definition are three extremely
important concepts that are the basis for understanding the
Internet,packet switching,the TCP/IP communications
protocol,and client/server computing.
在这个正式的定义背后，隐含着三个极其重要的概念：分组交换,TCP/IP(传输控制协议 /网际协议 )通信协议和客户机 /
服务器计算技术，它们乃是理解因特网的基础。
Chapter 4 Data Structure
Chapter 4 Data Structure
计算机专业英语 4-2
Key points:
useful terms and definitions
of data structure
Difficult points:
Stack,queue,tree
Chapter 4 Data Structure
计算机专业英语 4-3
Requirements:
1,Three reasons for using data structures are
efficiency,abstraction,and reusability.
2,The properties of Stack,Queue,and Tree
3,掌握常用英汉互译技巧
Chapter 4 Data Structure
计算机专业英语 4-4
New Words & Expressions:
harsh table 杂凑 (哈希 )表 priority queues 优先队列
reusability n.复用性 binary tree 二叉树
traversing 遍历，走过 context-free 与上下文无关
4.1 An Introduction to Data Structures
Chapter 4 Data Structure
计算机专业英语 4-5
Data comes in all shapes and sizes,but often it can be organized in the same
way,For example,consider a list of things to do,a list of ingredients in a
recipe,or a reading list for a class,Although each contains a different type
of data,they all contain data organized in a similar way,a list,A list is one
simple example of a data structure,Of course,there are many other
common ways to organize data as well,In computing,some of the most
common organizations are linked lists,stacks,queues,sets,hash tables,trees,
heaps,priority queues,and graphs,Three reasons for using data structures
are efficiency,abstraction,and reusability.
数据以各种形状和大小出现，但是它常常可以用同样的方式来组织。例如,
考虑要做事情的列表、处方成份的清单或一个班级的阅读目录。虽然它们包含不同类型的数据,但他们都包含以一种相似方式组织的数据,一个列表。
列表是数据结构的一个简单例子。当然，还有许多其他组织数据通用方法。
在计算机技术中，一些最常用的组织方式是链接表、堆栈、队列、集合、
哈希表、树、堆、优先队列和图。使用数据结构的三个原因是效率、抽象性和复用性。
4.1 An Introduction to Data Structures
Chapter 4 Data Structure
计算机专业英语 4-6
Efficiency
Data structures organize data in ways that make algorithms more
efficient,For example,consider some of the ways we can organize data
for searching it,One simplistic approach is to place the data in an
array and search the data by traversing element by element until the
desired element is found,However,this method is inefficient because in
many cases we end up traversing every element,By using another type
of data structure,such as a hash table or a binary tree we can search
the data considerably faster.
效率数据结构使用令算法更有效率的方法组织数据。例如，考虑一些我们用来查找数据的组织方式。一种过分简单的方式是将数据放置到数组中，并用遍历的方法找到需要的元素。然而，这种方法是低效率的，因为在许多情况下，我们需要遍历所有元素才能完成。使用其他类型的数据结构,如哈希表和二叉数，我们能够相当快速地搜寻数据 。
4.1 An Introduction to Data Structures
Chapter 4 Data Structure
计算机专业英语 4-7
Abstraction
Data structures provide a more understandable way to look at
data; thus,they offer a level of abstraction in solving problems,
For example,by storing data in a stack,we can focus on things
that we do with stacks,such as pushing and popping elements,
rather than the details of how to implement each operation,In
other words,data structures let us talk about programs in a less
programmatic way.
抽象化数据结构提供一个更好理解的方法查看数据；因此，它们在解决问题中提供一定的抽象化水平。例如，通过把数据储存在堆栈中，我们可以将重点集中在对堆栈的操作上，如使元素进栈和出栈，而不是集中在实现操作的细节上。
换句话说，数据结构使我们以较少的编程方式谈论程序。
4.1 An Introduction to Data Structures
Chapter 4 Data Structure
计算机专业英语 4-8
Reusability
Data structures are reusable because they tend to be modular and
context-free,They are modular because each has a prescribed
interface through which access to data stored in the data structure is
restricted,That is,we access the data using only those operations the
interface defines,Data structures are context-free because they can
be used with any type of data and in a variety of situations or
contexts,In C,we make a data structure store data of any type by
using void pointers to the data rather than by maintaining private
copies of the data in the data structure itself.
复用性,因为数据结构趋向于模块化并和环境无关,所以数据结构是可以复用的。因为每种结构有一个预定的接口,通过该接口限制访问存储在数据结构中的数据，所以它们是模块化的。也就是说,我们只能使用接口定义的那些操作来访问数据。因为数据结构能用于任何类型的数据,并用于多种环境中，所以数据结构与使用环境无关。在 C语言中，我们通过使用空指针，
而不是通过维护非公开的数据备份，使数据结构存储任何类型的数据。
4.1 An Introduction to Data Structures
Chapter 4 Data Structure
计算机专业英语 4-9
New Words & Expressions
inviting adj.引人动心的 contiguous adj.邻近的,接近的
stack n,堆栈 insertion n.插入
deletion n.删除,删除部分 pop 退栈
push 进栈 backtrack v.回溯
pseudocode n.[计 ]伪代码 retrieve v.重新得到； n.找回
pointer n.指针 pertinent adj.有关的,相干的,中肯的
extract vt,取，引 back out 返回
entail vt,使承担,带来 traverse v.遍历
shrink v.收缩 allot vt.分配,充当,依靠
predecessor n.前辈,前任 back and forth adv.来来往往地,来回地
vacancy n.空,空白,空缺 stuff vt.填充,塞满
Abbreviations
LIFO (last-in,first-out) 后进先出
FIFO (first-in,first-out) 先进先出
4.2 Stacks
Chapter 4 Data Structure
计算机专业英语 4-10
One of the properties of a list that makes a linked structure more inviting
than a contiguous one is the need to insert and delete entries inside the list.
Recall that it was such operations that had the potential of forcing the
massive movement of names to fill or create holes in the case of a
contiguous list,If we restrict such operations to the ends of the structure,
we find that the use of a contiguous structure becomes a more convenient
system,An example of this phenomenon is a stack,which is a list in which
all insertions and deletions are performed at the same end of the structure.
A consequence of this restriction is that the last entry entered will always be
the first entry removed--an observation that leads to stacks being known as
last-in,first-out (LIFO) structures.
插入和删除记录的需求是使链接表结构比邻接表结构更诱人的原因之一。
让我们回想一下在邻接表中具有填补和创建存储空缺能力的操作。如果我们限制这种操作只可以在结构的尾部进行，则邻接表就是一种比较方便的系统。这种现象的一个例子就是堆栈。在堆栈中，插入和删除操作都在结构的相同末端进行。如此限制的结果就是最后一个进入表的记录也就是第一个从表中删除的记录。这种结构称为后进先出结构。
4.2 Stacks
Chapter 4 Data Structure
计算机专业英语 4-11
The end of a stack at which entries are inserted and deleted is
called the top of the stack,The other end is sometimes called the
stack's base,To reflect the fact that access to a stack is restricted to
the topmost entry,we use special terminology when referring to
the insertion and deletion operations,The process of inserting an
object on the stack is called a push operation,and the process of
deleting an object is called a pop operation,Thus we speak of
pushing an entry onto a stack and popping an entry off a stack.
堆栈尾部可以进行插入和删除操作的记录称为堆栈的栈顶，
另一端叫做栈底。为了表示如何限制堆栈只能从栈顶访问，
我们用一种特殊的术语来表示插入和删除操作。把一个对象插入堆栈的操作称为进栈操作，而从堆栈中删除一个对象的操作称为出栈操作，所以我们常说将一个条目进栈或者将其出栈。
4.2 Stacks
Chapter 4 Data Structure
计算机专业英语 4-12
Backtracking
A classic application of a stack involves the execution of a
program involving procedures as found in our pseudocode,When
the execution of a procedure is requested,the machine must
transfer its attention to the procedure; yet later,when the procedure
is completed,the machine must return to the original location
before continuing,This means that,when the initial transfer is
made,there must be a mechanism for remembering the location to
which execution ultimately returns.
回溯堆栈的一个典型应用发生在一个程序单元调用一个过程的操作中。为了完成这个调用，机器必须将它的注意力转移到这个过程上；当过程调用结束后，机器必须返回到程序块进行调用时所处的位置。这就意味着必须有一种用来记录操作结束后返回的位置的机制。
4.2 Stacks
Chapter 4 Data Structure
计算机专业英语 4-13
The situation is complicated by the fact that the procedure may
itself request the execution of another procedure,which may
request still another,and so on (Figure 7.9),Consequently,the
return locations being remembered begin to pile up,Later,as each
of these procedures is completed,execution must be returned to
the proper place within the program unit that called the completed
procedure,A system is therefore needed to save the return
locations and later retrieve them in the proper order.
如果一个被调用的过程本身还要调用其他过程，而那些过程同样也需要调用另外的过程，这样一来整个情形就会很复杂。
因此，返回地址的记忆就开始堆积。然后，当每一个过程都结束后，操作必须返回到被称为完成过程的程序块中的合适位置。因此，系统需要按照适当的顺序存储和找回返回地址。
4.2 Stacks
Chapter 4 Data Structure
计算机专业英语 4-14
A stack is an ideal structure for such a system,As each procedure
is called,a pointer to the pertinent return Location is pushed on a
stack,and as each procedure is completed,the top entry from the
stack is extracted with the assurance of obtaining a pointer to the
proper return location,This example is representative of stack
applications in general in that it demonstrates the relationship
between stacks and the process of backtracking,Indeed,the
concept of a stack is inherent in any process that entails backing
out of a system in the opposite order from which it was entered.
堆栈是满足这种需要的理想结构。当一个过程被调用时，将指向返回地址的指针进栈。然后，当一个过程完成时，将栈顶条目出栈，程序就可以准确得到返回地址。这是应用栈的一个典型例子，它表明了栈和回溯过程的关系。在任何可以从进入端反向返回系统的过程中，堆栈的概念是与生俱来的。
4.2 Stacks
Chapter 4 Data Structure
计算机专业英语 4-15
As another example of backtracking,suppose we want to print the
names in a linked list in reverse order--that is,last name first,Our
problem is that the only way we can access the names is by
following the linked structure,Thus we need a way of holding
each name retrieved until all of the names that follow have been
retrieved and printed,Our solution is to traverse the list from its
beginning to its end while pushing the names we find onto a stack.
After reaching the end of the list,we print the names as we pop
them off the stack.
我们在来举另一个例子，假设反向输出一张链接表中的姓名，也就是把最后一个名字第一个输出。问题是我们只能跟着链接结构访问姓名。因此，
我们需要一种方式，通过这种方式，我们可以保持每一个姓名能被检索，
直到排列在这个姓名之后的姓名被得到并输出。我们的方案是从链接表的开始顺序遍历到结尾，与此同时把每一个姓名按照遍历顺序进栈。当到达链接表的末尾后，我们通过出栈操作来输出姓名。
4.2 Stacks
Chapter 4 Data Structure
计算机专业英语 4-16
Stack Implementation
To implement a stack structure in a computer's memory,it is customary to
reserve a block of contiguous memory cells large enough to accommodate
the stack as it grows and shrinks,(Determining the size of this block can
often be a critical decision,If too little room is reserved,the stack
ultimately exceeds the allotted storage space; if too much room is reserved,
memory space will be wasted.) One end of this block is designated as the
stack's base,It is here that the first entry pushed on the stack is stored,with
each additional entry being placed next to its predecessor as the stack
grows toward the other end of the reserved block.
栈的实现为了在计算机存储中实现栈结构，一般采取的方法是保留一块足够容纳栈大小变化的内存单元。（通常来说，确定块的大小是一个很重要的任务。如果保留的空间过小，那么栈最后可能从所分配的存储空间中溢出；而如果保留的空间过大，又是一种浪费。）块的一端作为栈底，栈的第一条数据会被存储在这里，以后的条目被依次放置在它之后的存储单元中，也就是堆栈向另外一端增加。
4.2 Stacks
Chapter 4 Data Structure
计算机专业英语 4-17
Thus,as entries are pushed and popped,the top of the stack moves
back and forth within the reserved block of memory cells,A means
is therefore needed to maintain a record of the location of the top
entry,For this purpose,the address of the top entry is stored in an
additional memory cell known as the stack pointer,That is,the
stack pointer points to the top of the stack.
因此，在条目进栈和出栈的时候，栈顶的位置就在存储单元块中前后移动。为了保存这个位置的轨迹，栈顶条目的地址被存储在一个附加的存储单元中，这个附加的存储单元被被称为堆栈指针。也就是说，堆栈指针就是一个指向栈顶的指针。
4.2 Stacks
Chapter 4 Data Structure
计算机专业英语 4-18
The complete system,as illustrated in Figure 4-1,works as follows:
To push a new entry on the stack,we first adjust the stack pointer
to point to the vacancy just beyond the top of the stack and then
place the new entry at this location,To pop an entry from the stack,
we read the data pointed to by the stack pointer and then adjust the
pointer to point to the next entry down on the stack.
一个完整的系统（如图 4-1所示）是这样工作的：为了把一条新的数据压入堆栈，我们首先调整堆栈指针，使之指向当前栈顶之前的空白。然后将新的条目置于此处。为了将条目从堆栈中弹出，我们首先读出堆栈指针所指向的数据，然后调整此指针指向堆栈中的下一条数据所在的存储单元。
4.2 Stacks
Chapter 4 Data Structure
计算机专业英语 4-19
As we observed in the case of lists,a programmer would
probably find it advantageous to write procedures that
perform these push and pop operations so that the stack could
be used as an abstract tool,Note that these procedures should
handle such special cases as attempts to pop entries from an
empty stack and to push entries onto a full stack,In particular,
a complete stack system would probably contain procedures
for pushing entries,popping entries,testing for an empty stack,
and testing for a full stack.
同我们观察到表中的情况一样，程序员也可以将堆栈编写成一个可以进行进栈和出栈操作的抽象工具。注意，这些过程应该可以处理诸如试图从空栈中弹出数据，或者将数据压入一个已经填满的堆栈等特殊情况。所以一个完整的堆栈系统应该包括进栈、出栈、测试堆栈是否空或满的功能。
4.2 Stacks
Chapter 4 Data Structure
计算机专业英语 4-20
A stack organized in a contiguous block of memory cells exhibits little
difference between the conceptual structure and the actual structure
in main memory,Suppose,however,that we cannot reserve a fixed
block of memory and be assured that the stack will always fit,A
solution is to implement the stack as a linked structure similar to that
of a list,This avoids the limitations of restricting the stack to a fixed-
size block,since it allows the entries in the stack to be stuffed into
small pieces of available space anywhere in memory,In such a
situation,the conceptual stack structure will be quite different from
the actual arrangement of the data in memory.
存储在存储单元连续块中的栈展现出主存储器中概念结构与实际之间的一定差异。假设我们不能预测栈的大小，我们就不能保留一个总能满足堆栈的固定大小的存储块。一种解决方法就是实现一种与表结构相似的链接结构栈。
这种方法避免了将堆栈限定在一块固定块中的局限性，因为它允许将新的条目插入存储器中任何一块足够大的空闲空间中。在这种情况下，概念上的堆栈结构与其在存储器中实际的数据组织方式就大不相同了。
4.2 Stacks
Chapter 4 Data Structure
计算机专业英语 4-21
New Words & Expressions
queue n.行列,队列 ; vi.排队 cafeteria n.自助餐厅
rear n.后面,背后,后方 set aside 留出，拨出
head pointer 头指针 tail pointer 尾指针
crawl vi.& n,爬行,蠕动,徐徐行进
egocentric adj.自我中心的
consumption n.消费,消费量 side effect 副作用
migrate vi.移动,移植 ; vt.使移居,使移植
circular queue 循环队列 envision vt.想象,预想
bridge vt.跨接,接通
4.3 Queues
Chapter 4 Data Structure
计算机专业英语 4-22
In contrast to a stack in which both insertions and deletions
are performed at the same end,a queue is a list in which all
insertions are performed at one end while all deletions are
made at the other,We have already met this structure in
relation to waiting lines,where we recognized it as being a
first-in,first-out (FIFO) storage system,Actually,the concept
of a queue is inherent in any system in which objects are
served in the same order in which they arrive.
4.3 Queues
栈的插入与删除操作都是在表的相同端进行的。而与此不同，
队列是插入和删除操作分别在两端进行的表。我们已经遇到过这种与等待队列相关的结构，在此种情况中，我们把它当作是一种先进先出的存储系统。实际上，在那些对象输入与输出顺序相同的系统中，队列的概念是与生俱来的。队列的结尾从等待队列的关联中得到名字。
Chapter 4 Data Structure
计算机专业英语 4-23
The ends of a queue get their names from this waiting-line
relationship,The end at which entries are removed is called
the head (or sometimes the front) of the queue just as we say
that the next person to be served in a cafeteria is at the head
(or front) of the line,Similarly,the end of the queue at which
new entries are added is called the tail (or rear).
4.3 Queues
结尾处，也就是条目被移出队列的地方，被称为队列的队首
（有时候也称为队前），这就好像我们在快餐厅中下一个将点餐的顾客为一队的队首一样。同样，队列的尾部，也就是条目被添加的地方，被称为队尾（或者队后）。
Chapter 4 Data Structure
计算机专业英语 4-24
We can implement a queue in a computer's memory within a
block of contiguous cells in a way similar to our storage of a
stack,Since we need to perform operations at both ends of the
structure,we set aside two memory cells to use as pointers
instead of just one,as we did for a stack,One of these pointers,
called the head pointers keeps track of the head of the queue;
the other,called the tail pointer,keeps track of the tail.
4.3 Queues
我们可以像存储栈那样通过连续单元组成的存储块在计算机主存储器中实现队列。因为我们需要在此结构的两端都进行操作，我们分配出两个存储单元用来当作指针，而非栈中那样仅仅需要一个单元来存储指针。其中的一个指针被称为头指针，用来保持队列头的轨迹；另一个指针被称为尾指针，
用来保持队尾的轨迹。
Chapter 4 Data Structure
计算机专业英语 4-25
When the queue is empty,both of these pointers point to the
same location,Each time an entry is inserted,it is placed in the
location pointed to by the tail pointer and then the tail pointer
is adjusted to point toward the next unused location,In this
manner,the tail pointer is always pointing to the first vacancy
at the tail of the queue,Removing an entry from the queue
involves extracting the entry pointed to by the head pointer
and then adjusting the head pointer to point toward the entry
that followed the removed entry.
4.3 Queues
如果一个队列为空，那么两个指针应该指向相同的位置。每当新的条目被插入时，均会被置于尾指针所指向的位置，同时修改尾指针，使之指向下一个未使用的位置。这样，尾指针总是指向队尾后的第一空闲存储单元。
将一条数据移出队列的操作包括将头指针指向的条目取出，同时调整头指针使之指向排在被移出条目之后的位置 。
Chapter 4 Data Structure
计算机专业英语 4-26
A problem remains with the storage system as described thus
far,If left unchecked,the queue crawls slowly through
memory like a glacier,destroying any other data in its path
(Figure 4.2),This movement is the result of the rather
egocentric policy of inserting each new entry by merely placing
it next to the previous one and repositioning the tail pointer
accordingly,If we add enough entries,the tail of the queue
ultimately extends all the way to the end of the machine's
memory.
4.3 Queues
以上描述的存储系统仍然存在着问题。如果剩余的存储器未被检查，队列会像冰河一样在存储器中增长，同时将在此道路上的所有其他数据破坏
（如图所示）。造成这种移动的相当一部分原因在于插入新条目时使用的
“利己”策略，即在插入是仅仅将新数据置于当前队尾之后，同时重置尾指针。如果我们添加足够的条目，那么队尾最后就会从计算机存储器中溢出。
Chapter 4 Data Structure
计算机专业英语 4-27
This consumption of memory is not the result of the queue's size but
is a side effect of the queue's access procedure,(A small yet active
queue can easily require more of a machine's memory resources
than a large,inactive one.) One solution to this memory space
problem might be to move the entries in a queue forward as the
leading ones are removed,in the same manner as people waiting to
buy theater tickets step forward each time a person has been served.
However,this mass movement of data would be very inefficient.
What we need is a way of confining the queue to one area of memory
without being forced to perform major rearrangements of data.
4.3 Queues
存储器的消耗问题并不是因队列的大小而生的，其真正原因在于队列的实现问题。
（一个小而动态变化的队列比一个大而保持不变的队列需要更多的机器存储资源。）解决存储器空间问题的一个可能方法是：当最前面的条目被移出时,前移队列中的其他条目，就好像人们在购买戏票时所采用的方法一样，每当一个人买到票后，就前移一人。然而这种方法在计算机中运行的效率很低，因为它将需要对数据进行大量的移动。
Chapter 4 Data Structure
计算机专业英语 4-28
A common solution is to set aside a block of memory for the queue,
start the queue at one end of the block,and let the queue migrate
toward the other end of the block,Then,when the tail of the queue
reaches the end of the block,we merely start inserting additional
entries back at the original end of the block,which by this time is
vacant,Likewise,when the last entry in the block finally becomes
the head of the queue and is removed,the head pointer is adjusted
back to the beginning of the block where other entries are,by this
time,waiting,In this manner,the queue chases itself around within
the block rather than wandering off through memory.
4.3 Queues
用来在计算机中控制队列的最一般的方法是为队列分配一块存储器，从存储块的末端开始存储队列，并且让队列向另一端增长。然而当队尾到达块的末端，即队列为空时，我们开始将新的条目反向于末端的方向插入。同样，当队列的最后一条成为队头并被移出时，调整头指针回到块的开端，
同时在此等待。在此方法下，队列在一块区域内循环而不会出现内存溢出情况。
Chapter 4 Data Structure
计算机专业英语 4-29
Such a technique results in an implementation that is called a
circular queue because the effect is that of forming a loop out
of the block of memory cells allotted to the queue,As far as the
queue is concerned,the last cell in the block is adjacent to the
first cell.
4.3 Queues
采用此技术的实现方法称为循环队列，因为分配给队列的一块存储单元组成了一个环。就一个队列而言，存储块的最后一个单元与它的第一个单元相邻。
Chapter 4 Data Structure
计算机专业英语 4-30
Once again,we should recognize the difference between the
conceptual structure envisioned by the user of a queue and the
actual cyclic structure implemented in the machine's memory.
As in the case of the previous structures,these differences are
normally bridged by software,That is along with the collection
of memory cells used for data storage,a queue implementation
should include a collection of procedures that insert and
remove entries from the queue as well as detect whether the
queue is empty or full.
4.3 Queues
我们应该再次认识到队列使用者使用的概念结构与实际在计算机存储器中实现的循环结构之间的差异。在前一个结构的例子中，这些差异通常是通过软件来衔接的。也就是说，连同存储数据需要的一组存储单元，队列的实现应该包括一组用来插入和移出队列条目和探测队列是否为空或满的过程函数。然后，开发软件其他单元的程序员可以通过这些方法来实现队列的插入和移出操作，而不用关心其在存储器中的实际实现。
Chapter 4 Data Structure
计算机专业英语 4-31
常用英汉互译技巧一,增译法根据英汉两种语言不同的思维方式、语言习惯和表达方式,在翻译时增添一些词、短句或句子，以便更准确地表达出原文所包含的意义。 这种方式多半用在汉译英里。
1、汉语无主句较多，而英语句子一般都要有主语，所以在翻译汉语无主句的时候，除了少数可用英语无主句、被动语态或,There be…” 结构来翻译以外，一般都要根据语境补出主语，使句子完整。
2、英汉两种语言在名词、代词、连词、介词和冠词的使用方法上也存在很大差别。英语中代词使用频率较高，凡说到人的器官和归某人所有的或与某人有关的事物时，必须在前面加上物主代词。因此，在汉译英时需要增补物主代词，而在英译汉时又需要根据情况适当地删减。
3、英语词与词、词组与词组以及句子与句子的逻辑关系一般用连词来表示，
而汉语则往往通过上下文和语序来表示这种关系。因此，在汉译英时常常需要增补连词。英语句子离不开介词和冠词。
4、在汉译英时还要注意增补一些原文中暗含而没有明言的词语和一些概括性、注释性的词语，以确保译文意思的完整。
Chapter 4 Data Structure
计算机专业英语 4-32
常用英汉互译技巧一,增译法例 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,(增加主语 )
Chapter 4 Data Structure
计算机专业英语 4-33
常用英汉互译技巧二,省译法这是与增译法相对应的一种翻译方法，即删去不符合目标语思维习惯、语言习惯和表达方式的词，以避免译文累赘。增译法的例句反之即可。又如,
例 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)
Chapter 4 Data Structure
计算机专业英语 4-34
常用英汉互译技巧三、转换法在翻译过程中，为了使译文符合目标语的表述方式、方法和习惯，对原句中的词类、句型和语态等进行转换：
1、在词性方面，把名词转换为代词、形容词、动词；把动词转换成名词、形容词、副词、介词；把形容词转换成副词和短语。
2、在句子成分方面，把主语变成状语、定语、宾语、表语；
把谓语变成主语、定语、表语；把定语变成状语、主语；把宾语变成主语。
3、在句型方面，把并列句变成复合句，把复合句变成并列句，
把状语从句变成定语从句。
4、在语态方面，可以把主动语态变为被动语态。
Chapter 4 Data Structure
计算机专业英语 4-35
常用英汉互译技巧三、转换法例 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 don’t have much time left,Let’s go back,( 句型转换 )
Chapter 4 Data Structure
计算机专业英语 4-36
常用英汉互译技巧四、拆句法和合并法例 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.
分组交换是传输数据的一种方法，它先将数据信息分割成许多称为“分组”
的数据信息包；当路径可用时，经过不同的通信路径发送；当到达目的地后，再将它们组装起来。 (将长定语从句拆成几个并列的分句 )
Chapter 4 Data Structure
计算机专业英语 4-37
常用英汉互译技巧五、正译法和反译法这两种方法通常用于汉译英，偶尔也用于英译汉。所谓正译，是指把句子按照与汉语相同的语序或表达方式译成英语。所谓反译则是指把句子按照与汉语相反的语序或表达方式译成英语。正译与反译常常具有同义的效果，
但反译往往更符合英语的思维方式和表达习惯。因此比较地道 。
例 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,（反译）
Chapter 4 Data Structure
计算机专业英语 4-38
常用英汉互译技巧六、倒置法在汉语中，定语修饰语和状语修饰语往往位于被修饰语之前；在英语中，
许多修饰语常常位于被修饰语之后，因此翻译时往往要把原文的语序颠倒过来。 倒置法通常用于英译汉,即对英语长句按照汉语的习惯表达法进行前后调换，按意群或进行全部倒置，原则是使汉语译句安排符合现代汉语论理叙事的一般逻辑顺序。有时倒置法也用于汉译英 。 如：
例 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.(全部倒置 )
Chapter 4 Data Structure
计算机专业英语 4-39
常用英汉互译技巧七、包孕法这种方法多用于英译汉。所谓包孕是指在把英语长句译成汉语时，把英语后置成分按照汉语的正常语序放在中心词之前，使修饰成分在汉语句中形成前置包孕。但修饰成分不宜过长，否则会形成拖沓或造成汉语句子成分在连接上的纠葛 。 如：
例 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,
使我们走到一起的，是我们有超越这些分歧的共同利益
Chapter 4 Data Structure
计算机专业英语 4-40
常用英汉互译技巧八,插入法指把难以处理的句子成分用破折号、括号或前后逗号插入译句中。这种方法主要用于笔译中。偶尔也用于口译中，即用同位语、插入语或定语从句来处理一些解释性成分 。
如,如果说宣布收回香港就会像夫人说的“带来灾难性的影响”，那我们将勇敢地面对这个灾难，做出决策。
If the announcement of the recovery of Hong Kong would bring
about,as Madam put it,“disastrous effects,” we will face that
disaster squarely and make a new policy decision.
Chapter 4 Data Structure
计算机专业英语 4-41
常用英汉互译技巧九、重组法在进行英译汉时，为了使译文流畅和更符合汉语叙事论理的习惯，在捋清英语长句的结构、弄懂英语原意的基础上，彻底摆脱原文语序和句子形式，对句子进行重新组合。
如,Decision must be made very rapidly; physical endurance is
tested as much as perception,because an enormous amount of
time must be spent making certain that the key figures act on
the basis of the same information and purpose.
必须把大量时间花在确保关键人物均根据同一情报和目的行事，
而这一切对身体的耐力和思维能力都是一大考验。因此，一旦考虑成熟，决策者就应迅速做出决策。
Chapter 4 Data Structure
计算机专业英语 4-42
常用英汉互译技巧十、综合法指把难以处理的句子成分用破折号、括号或前后逗号插入译句中。这种方法主要用于笔译中。偶尔也用于口译中，即用同位语、插入语或定语从句来处理一些解释性成分 。
如：
如果说宣布收回香港就会像夫人说的“带来灾难性的影响”，
那我们将勇敢地面对这个灾难，做出决策。
If the announcement of the recovery of Hong Kong would bring
about,as Madam put it,“disastrous effects,” we will face that
disaster squarely and make a new policy decision.
Chapter 4 Data Structure
计算机专业英语 4-43
常用英汉互译技巧十、综合法是指单用某种翻译技巧无法译出时，着眼篇章，以逻辑分析为基础，同时使用转换法、倒置法、增译法、省译法、拆句法等多种翻译技巧的方法。
如,Behind this formal definition are three extremely
important concepts that are the basis for understanding the
Internet,packet switching,the TCP/IP communications
protocol,and client/server computing.
在这个正式的定义背后，隐含着三个极其重要的概念：分组交换,TCP/IP(传输控制协议 /网际协议 )通信协议和客户机 /
服务器计算技术，它们乃是理解因特网的基础。
