Chapter-4-Data-Structure-Computer-English-计算机专业英语—.ppt

《Chapter-4-Data-Structure-Computer-English-计算机专业英语—.ppt》由会员分享，可在线阅读，更多相关《Chapter-4-Data-Structure-Computer-English-计算机专业英语—.ppt（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Computer English Chapter 4 Data Structure1Chapter 4 Data StructureKey points:useful terms and definitions of data structureDifficult points:Stack,queue,tree2计算机专业英语Chapter 4 Data StructureRequirements:1.Three reasons for using data structures are efficiency,abstraction,and reusability.2.The properti

2、es of Stack,Queue,and Tree3.掌握常用英汉互译技巧掌握常用英汉互译技巧 3计算机专业英语Chapter 4 Data StructureNew Words&Expressions:harsh table 杂凑杂凑(哈希哈希)表表priority queues 优先队列优先队列reusability n.复用性复用性binary tree 二叉树二叉树traversing 遍历，走过遍历，走过context-free 与上下文无关与上下文无关4.1 An Introduction to Data Structures 4计算机专业英语Chapter 4 Data Str

3、uctureChapter 4 Data StructureEfficiency 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

4、 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.效率效率数据结构使用令算法更有效率的方法组织数据。例如，考虑一些我们用来数据结构使用令算法更有效率的方

5、法组织数据。例如，考虑一些我们用来查找数据的组织方式。一种过分简单的方式是将数据放置到数组中，并用查找数据的组织方式。一种过分简单的方式是将数据放置到数组中，并用遍历的方法找到需要的元素。然而，这种方法是低效率的，因为在许多情遍历的方法找到需要的元素。然而，这种方法是低效率的，因为在许多情况下，我们需要遍历所有元素才能完成。使用其他类型的数据结构况下，我们需要遍历所有元素才能完成。使用其他类型的数据结构,如哈希如哈希表和二叉数，我们能够相当快速地搜寻数据表和二叉数，我们能够相当快速地搜寻数据。4.1 An Introduction to Data Structures 6计算机专业英语Chap

6、ter 4 Data StructureAbstraction 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 detai

7、ls of how to implement each operation.In other words,data structures let us talk about programs in a less programmatic way.抽象化抽象化数据结构提供一个更好理解的方法查看数据；因此，它们在解决问题中提供数据结构提供一个更好理解的方法查看数据；因此，它们在解决问题中提供一定的抽象化水平。例如，通过把数据储存在堆栈中，我们可以将重点集中一定的抽象化水平。例如，通过把数据储存在堆栈中，我们可以将重点集中在对堆栈的操作上，如使元素进栈和出栈，而不是集中在实现操作的细节上。在对堆栈的

8、操作上，如使元素进栈和出栈，而不是集中在实现操作的细节上。换句话说，数据结构使我们以较少的编程方式谈论程序。换句话说，数据结构使我们以较少的编程方式谈论程序。4.1 An Introduction to Data Structures 7计算机专业英语Chapter 4 Data StructureReusability Data structures are reusable because they tend to be modular and context-free.They are modular because each has a prescribed interface thr

9、ough 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 s

10、tore 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.复用性：复用性：因为数据结构趋向于模块化并和环境无关因为数据结构趋向于模块化并和环境无关,所以数据结构是可以所以数据结构是可以复用的。因为每种结构有一个预定的接口复用的。因为每种结构有一个预定的接口,通过该接口限制访问存储在数据通过该接口限制访问存储在数据结构中的数据，所以它们是模块化的。也就是说结构中的数据，所以它们

11、是模块化的。也就是说,我们只能使用接口定义的我们只能使用接口定义的那些操作来访问数据。因为数据结构能用于任何类型的数据那些操作来访问数据。因为数据结构能用于任何类型的数据,并用于多种环并用于多种环境中，所以数据结构与使用环境无关。在境中，所以数据结构与使用环境无关。在C语言中，我们通过使用空指针，语言中，我们通过使用空指针，而不是通过维护非公开的数据备份，使数据结构存储任何类型的数据。而不是通过维护非公开的数据备份，使数据结构存储任何类型的数据。4.1 An Introduction to Data Structures 8计算机专业英语Chapter 4 Data StructureChap

12、ter 4 Data StructureOne 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

13、 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 t

14、he 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.插入和删除记录的需求是使链接表结构比邻接表结构更诱人的原因之一。插入和删除记录的需求是使链接表结构比邻接表结构更诱人的原因之一。让我们回想一下在邻接表中具有填补和创建存储空缺能力的操作。如果我让我

15、们回想一下在邻接表中具有填补和创建存储空缺能力的操作。如果我们限制这种操作只可以在结构的尾部进行，则邻接表就是一种比较方便的们限制这种操作只可以在结构的尾部进行，则邻接表就是一种比较方便的系统。这种现象的一个例子就是堆栈。在堆栈中，插入和删除操作都在结系统。这种现象的一个例子就是堆栈。在堆栈中，插入和删除操作都在结构的相同末端进行。如此限制的结果就是最后一个进入表的记录也就是第构的相同末端进行。如此限制的结果就是最后一个进入表的记录也就是第一个从表中删除的记录。这种结构称为后进先出结构。一个从表中删除的记录。这种结构称为后进先出结构。4.2 Stacks 10计算机专业英语Chapter 4

16、Data Structure 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 stacks 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 de

17、letion 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.堆栈尾部可以进行插入和删除操作的记录称为堆栈的栈顶，堆栈尾部可以进行插入和删除操作的记录称为堆栈的栈顶，另一端叫做栈底。为了表

18、示如何限制堆栈只能从栈顶访问，另一端叫做栈底。为了表示如何限制堆栈只能从栈顶访问，我们用一种特殊的术语来表示插入和删除操作。把一个对象我们用一种特殊的术语来表示插入和删除操作。把一个对象插入堆栈的操作称为进栈操作，而从堆栈中删除一个对象的插入堆栈的操作称为进栈操作，而从堆栈中删除一个对象的操作称为出栈操作，所以我们常说将一个条目进栈或者将其操作称为出栈操作，所以我们常说将一个条目进栈或者将其出栈。出栈。4.2 Stacks 11计算机专业英语Chapter 4 Data StructureChapter 4 Data StructureThe situation is complicated

19、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

20、 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.如果一个被调用的过程本身还要调用其他过程，而那些过程如果一个被调用的过程本身还要调用其他过程，而那些过程同样也需要调用另外的过程，这样一来整个情形就会很复杂。同样也需要调用另外的过程，这样一来整个情形就会很复杂。因此，返回地址的记忆就开始堆积。然后，当每一个过程都因此，返回

21、地址的记忆就开始堆积。然后，当每一个过程都结束后，操作必须返回到被称为完成过程的程序块中的合适结束后，操作必须返回到被称为完成过程的程序块中的合适位置。因此，系统需要按照适当的顺序存储和找回返回地址。位置。因此，系统需要按照适当的顺序存储和找回返回地址。4.2 Stacks 13计算机专业英语Chapter 4 Data StructureChapter 4 Data StructureAs another example of backtracking,suppose we want to print the names in a linked list in reverse order-t

22、hat 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

23、 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.我们在来举另一个例子，假设反向输出一张链接表中的姓名，也就是把最我们在来举另一个例子，假设反向输出一张链接表中的姓名，也就是把最后一个名字第一个输出。问题是我们只能跟着链接结构访问姓名。因此，后一个名字第一个输出。问题是我们只能跟着链接结构访问姓名。因此，我们需要一种方式，通过这种方式，我们可以保持每一个姓名能被检索，我们需要一种方式，通过

24、这种方式，我们可以保持每一个姓名能被检索，直到排列在这个姓名之后的姓名被得到并输出。我们的方案是从链接表的直到排列在这个姓名之后的姓名被得到并输出。我们的方案是从链接表的开始顺序遍历到结尾，与此同时把每一个姓名按照遍历顺序进栈。当到达开始顺序遍历到结尾，与此同时把每一个姓名按照遍历顺序进栈。当到达链接表的末尾后，我们通过出栈操作来输出姓名。链接表的末尾后，我们通过出栈操作来输出姓名。4.2 Stacks 15计算机专业英语Chapter 4 Data StructureStack ImplementationTo implement a stack structure in a compute

25、rs 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 muc

26、h room is reserved,memory space will be wasted.)One end of this block is designated as the stacks 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.栈的实现栈的实现为

27、了在计算机存储中实现栈结构，一般采取的方法是保留一块足够容纳栈大小变化的为了在计算机存储中实现栈结构，一般采取的方法是保留一块足够容纳栈大小变化的内存单元。（通常来说，确定块的大小是一个很重要的任务。如果保留的空间过小，内存单元。（通常来说，确定块的大小是一个很重要的任务。如果保留的空间过小，那么栈最后可能从所分配的存储空间中溢出；而如果保留的空间过大，又是一种浪费。那么栈最后可能从所分配的存储空间中溢出；而如果保留的空间过大，又是一种浪费。）块的一端作为栈底，栈的第一条数据会被存储在这里，以后的条目被依次放置在它）块的一端作为栈底，栈的第一条数据会被存储在这里，以后的条目被依次放置在它之后的

28、存储单元中，也就是堆栈向另外一端增加。之后的存储单元中，也就是堆栈向另外一端增加。4.2 Stacks 16计算机专业英语Chapter 4 Data StructureChapter 4 Data StructureThe 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 a

29、nd 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所示）是这样工作的：为了把一条所示）是这样工作的：为了把一条新的数据压入堆栈，我们首先调整堆栈指针，使之指向当前新的数据压入堆栈，我们首先调整堆栈指针，使之指

30、向当前栈顶之前的空白。然后将新的条目置于此处。为了将条目从栈顶之前的空白。然后将新的条目置于此处。为了将条目从堆栈中弹出，我们首先读出堆栈指针所指向的数据，然后调堆栈中弹出，我们首先读出堆栈指针所指向的数据，然后调整此指针指向堆栈中的下一条数据所在的存储单元。整此指针指向堆栈中的下一条数据所在的存储单元。4.2 Stacks 18计算机专业英语Chapter 4 Data StructureAs we observed in the case of lists,a programmer would probably find it advantageous to write procedure

31、s 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 conta

32、in procedures for pushing entries,popping entries,testing for an empty stack,and testing for a full stack.同我们观察到表中的情况一样，程序员也可以将堆栈编写成同我们观察到表中的情况一样，程序员也可以将堆栈编写成一个可以进行进栈和出栈操作的抽象工具。注意，这些过程一个可以进行进栈和出栈操作的抽象工具。注意，这些过程应该可以处理诸如试图从空栈中弹出数据，或者将数据压入应该可以处理诸如试图从空栈中弹出数据，或者将数据压入一个已经填满的堆栈等特殊情况。所以一个完整的堆栈系统一个已经填满的堆栈等特殊

33、情况。所以一个完整的堆栈系统应该包括进栈、出栈、测试堆栈是否空或满的功能。应该包括进栈、出栈、测试堆栈是否空或满的功能。4.2 Stacks 19计算机专业英语Chapter 4 Data StructureA 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

34、 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 piece

35、s 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.存储在存储单元连续块中的栈展现出主存储器中概念结构与实际之间的一定存储在存储单元连续块中的栈展现出主存储器中概念结构与实际之间的一定差异。假设我们不能预测栈的大小，我们就不能保留一个总能满足堆栈的固差异。假设我们不能预测栈的大小，我们就不能保留一个总能满足堆栈的固定大小

36、的存储块。一种解决方法就是实现一种与表结构相似的链接结构栈。定大小的存储块。一种解决方法就是实现一种与表结构相似的链接结构栈。这种方法避免了将堆栈限定在一块固定块中的局限性，因为它允许将新的条这种方法避免了将堆栈限定在一块固定块中的局限性，因为它允许将新的条目插入存储器中任何一块足够大的空闲空间中。在这种情况下，概念上的堆目插入存储器中任何一块足够大的空闲空间中。在这种情况下，概念上的堆栈结构与其在存储器中实际的数据组织方式就大不相同了。栈结构与其在存储器中实际的数据组织方式就大不相同了。4.2 Stacks 20计算机专业英语Chapter 4 Data StructureNew Words

37、&Expressionsqueue 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 循环队列循环队列envis

38、ion vt.想象想象,预想预想bridge vt.跨接跨接,接通接通4.3 Queues21计算机专业英语Chapter 4 Data StructureIn 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 t

39、his 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栈的插入与删除操作都是在表的相同端进行的。而与此不同，栈的插入与删除操作都是在表的相同端进行的。而

40、与此不同，队列是插入和删除操作分别在两端进行的表。我们已经遇到过队列是插入和删除操作分别在两端进行的表。我们已经遇到过这种与等待队列相关的结构，在此种情况中，我们把它当作是这种与等待队列相关的结构，在此种情况中，我们把它当作是一种先进先出的存储系统。实际上，在那些对象输入与输出顺一种先进先出的存储系统。实际上，在那些对象输入与输出顺序相同的系统中，队列的概念是与生俱来的。队列的结尾从等序相同的系统中，队列的概念是与生俱来的。队列的结尾从等待队列的关联中得到名字。待队列的关联中得到名字。22计算机专业英语Chapter 4 Data StructureChapter 4 Data Structu

41、reWe can implement a queue in a computers 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 poi

42、nters,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我们可以像存储栈那样通过连续单元组成的存储块在计算机我们可以像存储栈那样通过连续单元组成的存储块在计算机主存储器中实现队列。因为我们需要在此结构的两端都进行主存储器中实现队列。因为我们需要在此结构的两端都进行操作，我们分配出两个存储单元用来当作指针，而非栈中那操作，我们分配出两个存储单元用来当作指针，而非栈中那样仅仅需要一个单

43、元来存储指针。其中的一个指针被称为头样仅仅需要一个单元来存储指针。其中的一个指针被称为头指针，用来保持队列头的轨迹；另一个指针被称为尾指针，指针，用来保持队列头的轨迹；另一个指针被称为尾指针，用来保持队尾的轨迹。用来保持队尾的轨迹。24计算机专业英语Chapter 4 Data StructureWhen 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

44、 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 adjusti

45、ng the head pointer to point toward the entry that followed the removed entry.4.3 Queues如果一个队列为空，那么两个指针应该指向相同的位置。每当新的条目被如果一个队列为空，那么两个指针应该指向相同的位置。每当新的条目被插入时，均会被置于尾指针所指向的位置，同时修改尾指针，使之指向下插入时，均会被置于尾指针所指向的位置，同时修改尾指针，使之指向下一个未使用的位置。这样，尾指针总是指向队尾后的第一空闲存储单元。一个未使用的位置。这样，尾指针总是指向队尾后的第一空闲存储单元。将一条数据移出队列的操作包括将头指针指向

46、的条目取出，同时调整头指将一条数据移出队列的操作包括将头指针指向的条目取出，同时调整头指针使之指向排在被移出条目之后的位置针使之指向排在被移出条目之后的位置。25计算机专业英语Chapter 4 Data StructureA 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).Th

47、is 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 machines memory.4.3 Queue

48、s以上描述的存储系统仍然存在着问题。如果剩余的存储器未被检查，队列以上描述的存储系统仍然存在着问题。如果剩余的存储器未被检查，队列会像冰河一样在存储器中增长，同时将在此道路上的所有其他数据破坏会像冰河一样在存储器中增长，同时将在此道路上的所有其他数据破坏（如图所示）。造成这种移动的相当一部分原因在于插入新条目时使用的（如图所示）。造成这种移动的相当一部分原因在于插入新条目时使用的“利己利己”策略，即在插入是仅仅将新数据置于当前队尾之后，同时重置尾策略，即在插入是仅仅将新数据置于当前队尾之后，同时重置尾指针。如果我们添加足够的条目，那么队尾最后就会从计算机存储器中溢指针。如果我们添加足够的条目，

49、那么队尾最后就会从计算机存储器中溢出。出。26计算机专业英语Chapter 4 Data StructureChapter 4 Data StructureA 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 b

50、lock,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,