新编计算机专业英语Chapter 09

1、Chapter Nine Data Structures 新编计算机专业英语IntroductionIn this chapter we investigate how data arrangements other than the cell-by-cell organization provided by a computers main memory can be simulated - a subject known as data structures. The goal is to allow the datas user to access collections of data

2、 as abstract tools rather than force the user to think in terms of the computers main memory organization. Our study will show how the desire to construct such abstract tools leads the concept of objects and object-oriented programming.Data Structure - Data Structure Fundamentals We begin our study

3、by introducing some basic data structures that will serve as examples in future sections. Also, we isolate three topics that are closely associated with the subject of data structures: abstraction, the distinction between static and dynamic structures, and the concept of a pointer.Basic Data Structu

4、res- homogeneous array A homogeneous array is a “rectangular” block of data whose entries are of the same type. In particular, a two-dimensional homogeneous array consists of rows and columns in which positions are identified by pairs of indices - the first index identifies the row associated with t

5、he position, the second index identifies the column.Data Structure - Data Structure Fundamentals Basic Data Structures- heterogeneous array In contrast to a homogeneous array, a heterogeneous array is a block of data items that might be of different types. The items within the block are usually call

6、ed components.Data Structure - Data Structure Fundamentals Basic Data Structures-listA list is a collection whose entries are arranged sequentially. The beginning of a list is called the head of the list. The other end of a list is called the tail.Data Structure - Data Structure Fundamentals Basic D

7、ata Structures-stackA stack is a list in which entries are removed and inserted only at the head. Following colloquial terminology, the head of a stack is called the top of the stack. The tail of a stack is called its bottom or base.Data Structure - Data Structure Fundamentals Basic Data Structures-

8、queueA queue is a list in which entries are removed only at the head and new entries are inserted only at the tail. Data Structure - Data Structure Fundamentals Basic Data Structures-treea tree is a collection whose entries have a hierarchical organization similar to that of an organization chart of

9、 a typical company. Each position in a tree is called a node. The node at the top is called the root nodeThe nodes at the other extreme are called terminal nodes (or sometimes leaf nodes). We often refer to the number of nodes in the longest path from the root to a leaf as the depth of the tree. In

10、other words, the depth of a tree is the number of horizontal layers within it.Data Structure - Data Structure Fundamentals Basic Data Structures-treeAt times we refer to tree structures as though each node gives birth to those nodes immediately below it. In this sense, we often speak of a nodes ance

11、stors or descendants. We refer to its immediate descendants as its children and its immediate ancestor as its parent. Data Structure - Data Structure Fundamentals A binary treeBasic Data Structures-treeMoreover, we speak of nodes with the same parent as being siblings. A tree in which each parent ha

12、s no more than two children is called a binary tree. If we select any node in a tree, we find that the node together with nodes below it also have the structure of a tree. Data Structure - Data Structure Fundamentals A binary treeBasic Data Structures-treeWe call these smaller structures subtrees. T

13、hus, each child node is the root of a subtree below the childs parent. Each such subtree is called a branch from the parent. In a binary tree, we often speak of a nodes left branch or right branch in reference to the way the tree is displayed.Data Structure - Data Structure Fundamentals A binary tre

14、eAbstractionThe data structures defined above are structures that are often associated with data. However, a computers main memory is not organized as lists, stacks, queues, and trees but is instead organized as a sequence of addressable memory cells. Thus, all other structures must be simulated. Ho

15、w this simulation is accomplished is the main subject of this chapter. Data Structure - Data Structure Fundamentals AbstractionFor now we merely point out that organizations such as stacks, queues, and trees are abstract tools that are created so that users of the data can be shielded from the detai

16、ls of actual data storage (memory cells and addresses) and can be allowed to access information as though it were stored in a more convenient form.Data Structure - Data Structure Fundamentals AbstractionStatic Versus Dynamic StructuresAn important distinction in constructing abstract data structures

17、 is whether the structure being simulated is static or dynamic, that is, whether the shape or size of the structure changes over time. For example, if the abstract tool is a list of names, it is important to consider whether the list will remain a fixed size throughout its existence, expand and shri

18、nk as names are added and deleted.Data Structure - Data Structure Fundamentals Pointerspointer is a storage area that contains such an encoded address. In the case of data structures, pointers are used to record the location where data items are stored.Data Structure - Data Structure Fundamentals Da

19、ta Structure - Implementing Data StructuresStoring ArraysHomogeneous ArraysHeterogeneous ArraysStoring listsStoring Stacks and QueuesStoring Binary TreesManipulating Data StructuresData Structure NotesData structure 数据结构数据结构是计算机中存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来高效率的算法。一个设计良好的数据结构，应该在尽可能使用较少的时间与空间资源的前提下

20、，为各种状态下的运行提供支持。数据结构可通过编程语言所提供的数据类型、引用及其他操作加以实现。Data Structure NotesQueue 队列队列在日常生活中随处可见。例如，为了有一定的秩序，在银行、商场等处经常可见顾客排队依次办理业务，这就是一种队列。对于队列，采用的是先进先出的算法，即先排队的先办理业务，这样，就保证了一定的秩序。在计算机中，队列也是一种常用的数据结构，用来处理按先进先出（FIFO, First In First Out）形式保存的数据。Data Structure NotesStack 堆栈在计算机领域，堆栈是一个重要概念。与队列不同，堆栈采用的是后进先出（LIF

21、O, Last In First Out）的形式存取数据，只能在一端对数据项进行插入和删除操作。Data Structure NotesLinked list链表链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序来实现的。例如在 C 语言中，使用数组必须先定义，而且必须定义数组元素的个数，系统根据定义的类型及元素个数分配相应的存储空间。Data Structure NotesLinked list链表该存储空间的大小是连续、固定的。而链表由一系列分散的节点（链表中每一个元素称为节点）组成，节点可以在运行时动态生成。每个节点包括两个部分：一个是存储数据

22、元素的数据域，另一个是存储下一个节点地址的指针域。各个节点可以不连续地存放，只需要由前一个节点提供下一个节点的地址，就可以顺着链表逐一访问各个节点。Data Structure NotesBinary tree 二叉树二叉树是每个节点最多有两个子树的有序树。二叉树的子树有左右之分，次序不能颠倒（“左子树”（left subtree）和“右子树”（right subtree）。二叉树的第i层至多有2i - 1个结点；深度为k的二叉树至多有2k-1个结点。Customized Data TypesUser-Defined Data TypesExpressing an algorithm is o

23、ften easier if data types other than those provided as primitives in the programming language are available. For this reason, many modern programming languages allow programmers to define additional data types, using the primitive types as building blocks. The most elementary examples of such homema

24、de data types are known as user-defined data types, which are essentially conglomerates of primitive types collected under a single name.Customized Data TypesAbstract Data TypesCustomized Data Types - Classes and ObjectsThe object-oriented paradigm leads to systems composed of units called objects t

25、hat interact with each other to accomplish tasks. Each object is an entity that responds to messages received from other objects. Objects are described by templates known as classes.Customized Data Types - Classes and ObjectsCustomized Data Types - NotesObject-oriented 面向对象“面向对象”的概念最初是指在程序设计中采用封装、继承

26、、抽象的设计方法。现在，面向对象的思想已经涉及到软件开发的各个方面。如面向对象的分析（Object Oriented Analysis，OOA），面向对象的设计（Object Oriented Design，OOD）以及面向对象的编程（Object Oriented Programming，OOP）。Customized Data Types - NotesObject-oriented 面向对象OOP 从所处理的数据入手，以数据为中心，而不是以功能为中心来描述系统。它把编程问题视为一个数据集合，因为数据相对于功能而言，具有更强的稳定性。OOP 同结构化程序设计相比最大的区别就在于：前者首先关

27、心的是所要处理的数据，而后者首先关心的是功能。Customized Data Types - NotesClass 类在现实世界中，经常有属于同一个类型的对象。例如，某辆自行车只是世界上很多自行车中的一辆。在面向对象的程序中，也有很多共享相同特征的不同对象，例如：矩形、雇用记录、视频剪辑等。可以利用这些对象的相同特征为它们建立一个蓝图。对象的软件蓝图称为类。类定义了一件事物的抽象特点。Customized Data Types - NotesClass 类通常来说，类定义了事物的属性和它可以做到的（它的行为）。例如，“狗”这个类会包含狗的一切基础特征，譬如性别、毛皮颜色和吠叫的能力。类可以为程

28、序提供模版和结构。一个类的方法和属性被称为类的“成员”。Customized Data Types - NotesObject 对象对象是类的实例。例如，“狗”这个类列举了狗的特点，从而使这个类定义了所有的狗。而“丁丁”这个对象则是一条具体的狗，它的属性也是具体的。狗有毛皮颜色，而“丁丁”的毛皮颜色是黑的。因此，“丁丁”就是狗这个类的一个实例。一个具体对象的属性的值被称作它的“状态”。因为对象是具体的，所以系统会给对象分配内存空间；而类是抽象的，系统不可能给抽象的东西分配空间，所以不会给类分配内存空间。Supplementary ReadingA Problem with PointersSu

29、pplementary Reading“Apparel Industry Amid Global Meltdown - Outsourcing Intelligence Report” by Swapna Goel, April 2009Supplementary ReadingHighlights:The highpoint of the report is a comprehensive listing of current suppliers - Indian manufacturers, exporters as well as operating buying houses with

30、 their contact details, for easy access. All categories of Indian exporters - the top 100 club, other leading export houses, new batch of exporters who are keen to supply, have been listed separately. Such a complete and current list is unavailable even with the Indian export councils. It has been s

31、elf compiled by gathering data from multiple sources, over a period of time.Supplementary ReadingList of major Indian trade bodies & export councils, trade statistics, future sourcing patterns, recession blues, the China factor and Vietnams meteoric rise - nothing has been left out.Another talking p

32、oint of this report is the focus on the emerging growth sector - trade in technical & home textiles. Profiles of the leading companies in home textiles manufacturing, and a comprehensive list of home textile manufacturers and exporters you can contact for purchases is provided here.Translation issue

33、s in IT fields - I.科技英语翻译翻译是把一种语言所表达的思维内容用另一种语言表达出来的跨语言、跨文化的语言交际活动。科技英语的翻译标准有二点，一是忠实原文，二是表达规范。所谓忠实原文，是指译者必须把原文的全部内容准确而又毫无遗漏地用译文表达出来。所谓表达规范，就是要求译者在表达原文内容时要使用简洁、易懂、符合译语表达习惯的语言。换一句话说，译者应使用为本学科或专业读者普遍接受的词汇、句子结构及篇章结构，译文表达要符合汉语表达习惯。Translation issues in IT fields - I.一、科技英语翻译过程科技英语翻译大致可分为两个阶段：原文理解阶段和汉语表达阶

34、段。1. 理解原文:领略全文大意 理解语言现象，分析语法关系 理解原文事理，注意逻辑判断 理解原文表达重点，领会“感情”色彩 深入原文，理解作者笔墨之外的信息Translation issues in IT fields - I.一、科技英语翻译过程科技英语翻译大致可分为两个阶段：原文理解阶段和汉语表达阶段。2. 译语表达：注意表达的规范性&注意表达的逻辑性Translation issues in IT fields - I.Garbage Collection-ExerciseAs dynamic data structures grow and shrink, storage space is used and released. The process of reclaiming unused storage space for future use is known as garbage collection. Garbage collection is required in numerous settings. The memory manager within