Computer English,Chapter 4 Data Structure,计算机专业英语,4-2,Key points: useful terms and definitions of data structure Difficult points: Stack, queue, tree,计算机专业英语,4-3,Requirements:,1. Three reasons for using data structures are efficiency, abstraction, and reusability.,2. The properties of Stack, Queue, and Tree,3. 掌握常用英汉互译技巧,计算机专业英语,4-4,New Words & Expressions: harsh table 杂凑(哈希)表 priority queues 优先队列 reusability n.复用性 binary tree 二叉树 traversing 遍历，走过 context-free 与上下文无关,4.1 An Introduction to Data Structures,计算机专业英语,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,计算机专业英语,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,计算机专业英语,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,计算机专业英语,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,计算机专业英语,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,计算机专业英语,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.,插入和删除记录的需求是使链接表结构比邻接表结构更诱人的原因之一。让我们回想一下在邻接表中具有填补和创建存储空缺能力的操作。如果我们限制这种操作只可以在结构的尾部进行，则邻接表