Chapter 4 Data Structure 4.1 An Introduction to Data Structures 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-6
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.1 An Introduction to Data Structures 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-7
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.1 An Introduction to Data Structures 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语言中,我们通过使用空指针 而不是通过维护非公开的数据备份,使数据结构存储任何类型的数据。 计算机专业英语 48
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.2 Stacks New Words expressions inviting adi引人动心的 contiguous adi邻近的,接近的 stack n.堆栈 insertion n插入 deletion n删除,删除部分 pop退栈 pl uS h进栈 backtrack v回溯 pseudocode n. 计]伪代码 retrieve v.重新得到;n.找回 pointer n指针 pertinent adj.有关的相干的,中肯的 extract vt.取,引 back out返回 entail vt.使承担,带来 raverse v遍历 shrink v收缩 allot vt分配,充当,依靠 predecessor n.前辈,前任 back and forth adv来来往往地,来回地 vacancy n空,空白,空缺 stuff vt填充,塞满 Abbreviations LIFO( last-in,frst-0ut)后进先出 FIFO( (first-in, first-out)先进先出 计算机专些英语 4-9
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.2 Stacks 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. 插入和删除记录的需求是使链接表结构比邻接表结构更诱人的原因之一。 让我们回想一下在邻接表中具有填补和创建存储空缺能力的操作。如果我 们限制这种操作只可以在结构的尾部进行,则邻接表就是一种比较方便的 系统。这种现象的一个例子就是堆栈。在堆栈中,插入和删除操作都在结 构的相同末端进行。如此限制的结果就是最后一个进入表的记录也就是第 个从表中删除的记录。这种结构称为后进先出结构。 A什算机专出英语 4-10
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