計算機專業(yè)英語 chapter PPT課件

1、第1頁/共43頁1. Three reasons for using data structures are efficiency, abstraction, and reusability. 2. The properties of Stack, Queue, and Tree3. 掌握常用英漢互譯技巧掌握常用英漢互譯技巧 第2頁/共43頁New Words & Expressions:harsh table 雜湊(哈希)表priority queues 優(yōu)先隊列reusability n.復(fù)用性binary tree 二叉樹traversing 遍歷，走過context-free

2、與上下文無關(guān)4.1 An Introduction to Data Structures 第3頁/共43頁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, the

3、y 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, priori

4、ty queues, and graphs. Three reasons for using data structures are efficiency, abstraction, and reusability.數(shù)據(jù)以各種形狀和大小出現(xiàn)，但是它常?？梢杂猛瑯拥姆绞絹斫M織。例如,考慮要做事情的列表、處方成份的清單或一個班級的閱讀目錄。雖然它們包含不同類型的數(shù)據(jù),但他們都包含以一種相似方式組織的數(shù)據(jù):一個列表。列表是數(shù)據(jù)結(jié)構(gòu)的一個簡單例子。當然，還有許多其他組織數(shù)據(jù)通用方法。在計算機技術(shù)中，一些最常用的組織方式是鏈接表、堆棧、隊列、集合、哈希表、樹、堆、優(yōu)先隊列和圖。使用數(shù)據(jù)結(jié)構(gòu)的三個原因是效

5、率、抽象性和復(fù)用性。4.1 An Introduction to Data Structures 第4頁/共43頁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

6、 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.效率數(shù)據(jù)結(jié)構(gòu)使用令算法更有效率的方

7、法組織數(shù)據(jù)。例如，考慮一些我們用來查找數(shù)據(jù)的組織方式。一種過分簡單的方式是將數(shù)據(jù)放置到數(shù)組中，并用遍歷的方法找到需要的元素。然而，這種方法是低效率的，因為在許多情況下，我們需要遍歷所有元素才能完成。使用其他類型的數(shù)據(jù)結(jié)構(gòu),如哈希表和二叉數(shù)，我們能夠相當快速地搜尋數(shù)據(jù)。4.1 An Introduction to Data Structures 第5頁/共43頁Abstraction Data structures provide a more understandable way to look at data; thus, they offer a level of abstraction

8、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.抽象化數(shù)據(jù)結(jié)構(gòu)

9、提供一個更好理解的方法查看數(shù)據(jù)；因此，它們在解決問題中提供一定的抽象化水平。例如，通過把數(shù)據(jù)儲存在堆棧中，我們可以將重點集中在對堆棧的操作上，如使元素進棧和出棧，而不是集中在實現(xiàn)操作的細節(jié)上。換句話說，數(shù)據(jù)結(jié)構(gòu)使我們以較少的編程方式談?wù)摮绦颉?.1 An Introduction to Data Structures 第6頁/共43頁Reusability Data structures are reusable because they tend to be modular and context-free. They are modular because each has a presc

10、ribed 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

11、 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.復(fù)用性：因為數(shù)據(jù)結(jié)構(gòu)趨向于模塊化并和環(huán)境無關(guān),所以數(shù)據(jù)結(jié)構(gòu)是可以復(fù)用的。因為每種結(jié)構(gòu)有一個預(yù)定的接口,通過該接口限制訪問存儲在數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)，所以它們是模塊化的。也就是說,我們只能使用接口定義的那些操作來訪問數(shù)據(jù)。因為數(shù)據(jù)結(jié)構(gòu)能用于任何類型的數(shù)據(jù),并用于多種環(huán)境中，所以

12、數(shù)據(jù)結(jié)構(gòu)與使用環(huán)境無關(guān)。在C語言中，我們通過使用空指針，而不是通過維護非公開的數(shù)據(jù)備份，使數(shù)據(jù)結(jié)構(gòu)存儲任何類型的數(shù)據(jù)。4.1 An Introduction to Data Structures 第7頁/共43頁New Words & Expressionsinviting adj.引人動心的contiguous adj.鄰近的, 接近的stack n. 堆棧insertion n.插入deletion n.刪除, 刪除部分pop 退棧push 進棧backtrack v.回溯pseudocode n.計偽代碼retrieve v.重新得到；n.找回pointer n.指針pertin

13、ent adj.有關(guān)的, 相干的, 中肯的extract vt. 取，引 back out 返回entail vt. 使承擔， 帶來traverse v.遍歷shrink v.收縮allot vt.分配,充當,依靠predecessor n.前輩, 前任back and forth adv.來來往往地, 來回地vacancy n.空, 空白, 空缺stuff vt.填充, 塞滿AbbreviationsLIFO (last-in, first-out) 后進先出FIFO (first-in, first-out) 先進先出4.2 Stacks 第8頁/共43頁One of the proper

14、ties 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 w

15、e 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 t

16、his 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.插入和刪除記錄的需求是使鏈接表結(jié)構(gòu)比鄰接表結(jié)構(gòu)更誘人的原因之一。讓我們回想一下在鄰接表中具有填補和創(chuàng)建存儲空缺能力的操作。如果我們限制這種操作只可以在結(jié)構(gòu)的尾部進行，則鄰接表就是一種比較方便的系統(tǒng)。這種現(xiàn)象的一個例子就是堆棧。在堆棧中，插入和刪除操作都

17、在結(jié)構(gòu)的相同末端進行。如此限制的結(jié)果就是最后一個進入表的記錄也就是第一個從表中刪除的記錄。這種結(jié)構(gòu)稱為后進先出結(jié)構(gòu)。4.2 Stacks 第9頁/共43頁 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,

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

19、stack.堆棧尾部可以進行插入和刪除操作的記錄稱為堆棧的棧頂，另一端叫做棧底。為了表示如何限制堆棧只能從棧頂訪問，我們用一種特殊的術(shù)語來表示插入和刪除操作。把一個對象插入堆棧的操作稱為進棧操作，而從堆棧中刪除一個對象的操作稱為出棧操作，所以我們常說將一個條目進?；蛘邔⑵涑鰲?。4.2 Stacks 第10頁/共43頁BacktrackingA classic application of a stack involves the execution of a program involving procedures as found in our pseudocode. When the ex

20、ecution 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

21、 the location to which execution ultimately returns.回溯堆棧的一個典型應(yīng)用發(fā)生在一個程序單元調(diào)用一個過程的操作中。為了完成這個調(diào)用，機器必須將它的注意力轉(zhuǎn)移到這個過程上；當過程調(diào)用結(jié)束后，機器必須返回到程序塊進行調(diào)用時所處的位置。這就意味著必須有一種用來記錄操作結(jié)束后返回的位置的機制。4.2 Stacks 第11頁/共43頁The situation is complicated by the fact that the procedure may itself request the execution of another procedu

22、re, 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

23、therefore needed to save the return locations and later retrieve them in the proper order. 如果一個被調(diào)用的過程本身還要調(diào)用其他過程，而那些過程同樣也需要調(diào)用另外的過程，這樣一來整個情形就會很復(fù)雜。因此，返回地址的記憶就開始堆積。然后，當每一個過程都結(jié)束后，操作必須返回到被稱為完成過程的程序塊中的合適位置。因此，系統(tǒng)需要按照適當?shù)捻樞虼鎯驼一胤祷氐刂贰?.2 Stacks 第12頁/共43頁A stack is an ideal structure for such a system. As each

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

25、 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.堆棧是滿足這種需要的理想結(jié)構(gòu)。當一個過程被調(diào)用時，將指向返回地址的指針進棧。然后，當一個過程完成時，將棧頂條目出棧，程序就可以準確得到

26、返回地址。這是應(yīng)用棧的一個典型例子，它表明了棧和回溯過程的關(guān)系。在任何可以從進入端反向返回系統(tǒng)的過程中，堆棧的概念是與生俱來的。4.2 Stacks 第13頁/共43頁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 s

27、tructure. 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 w

28、e pop them off the stack. 我們在來舉另一個例子，假設(shè)反向輸出一張鏈接表中的姓名，也就是把最后一個名字第一個輸出。問題是我們只能跟著鏈接結(jié)構(gòu)訪問姓名。因此，我們需要一種方式，通過這種方式，我們可以保持每一個姓名能被檢索，直到排列在這個姓名之后的姓名被得到并輸出。我們的方案是從鏈接表的開始順序遍歷到結(jié)尾，與此同時把每一個姓名按照遍歷順序進棧。當?shù)竭_鏈接表的末尾后，我們通過出棧操作來輸出姓名。4.2 Stacks 第14頁/共43頁Stack ImplementationTo implement a stack structure in a computers memory

29、, 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 ro

30、om 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.棧的實現(xiàn)為了在計算

31、機存儲中實現(xiàn)棧結(jié)構(gòu)，一般采取的方法是保留一塊足夠容納棧大小變化的內(nèi)存單元。（通常來說，確定塊的大小是一個很重要的任務(wù)。如果保留的空間過小，那么棧最后可能從所分配的存儲空間中溢出；而如果保留的空間過大，又是一種浪費。）塊的一端作為棧底，棧的第一條數(shù)據(jù)會被存儲在這里，以后的條目被依次放置在它之后的存儲單元中，也就是堆棧向另外一端增加。4.2 Stacks 第15頁/共43頁Thus, as entries are pushed and popped, the top of the stack moves back and forth within the reserved block of mem

32、ory 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. 因此，在條目進棧和出棧的時候，棧頂?shù)奈恢镁驮诖鎯卧獕K中前后移動。

33、為了保存這個位置的軌跡，棧頂條目的地址被存儲在一個附加的存儲單元中，這個附加的存儲單元被被稱為堆棧指針。也就是說，堆棧指針就是一個指向棧頂?shù)闹羔槨?.2 Stacks 第16頁/共43頁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 plac

34、e 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.一個完整的系統(tǒng)（如圖4-1所示）是這樣工作的：為了把一條新的數(shù)據(jù)壓入堆棧，我們首先調(diào)整堆棧指針，使之指向當前棧頂之前的空白。然后將新的條目置于此處。為了將條目從堆棧中彈出，我們首先讀出堆棧指針所指向的數(shù)據(jù)，然后調(diào)整此指針指向

35、堆棧中的下一條數(shù)據(jù)所在的存儲單元。4.2 Stacks 第17頁/共43頁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 a

36、s 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.同我們觀察到表中的情況一樣，程序員也可以將堆棧編寫成一個可以進行進棧和出棧操作的抽象工具。注意

37、，這些過程應(yīng)該可以處理諸如試圖從空棧中彈出數(shù)據(jù)，或者將數(shù)據(jù)壓入一個已經(jīng)填滿的堆棧等特殊情況。所以一個完整的堆棧系統(tǒng)應(yīng)該包括進棧、出棧、測試堆棧是否空或滿的功能。4.2 Stacks 第18頁/共43頁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

38、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 pie

39、ces 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.存儲在存儲單元連續(xù)塊中的棧展現(xiàn)出主存儲器中概念結(jié)構(gòu)與實際之間的一定差異。假設(shè)我們不能預(yù)測棧的大小，我們就不能保留一個總能滿足堆棧的固定大小的存儲塊。一種解決方法就是實現(xiàn)一種與表結(jié)構(gòu)相似的鏈接結(jié)構(gòu)棧。這種方法避免了將堆棧限定在一塊固定塊中的局限性，因為它允許將新的

40、條目插入存儲器中任何一塊足夠大的空閑空間中。在這種情況下，概念上的堆棧結(jié)構(gòu)與其在存儲器中實際的數(shù)據(jù)組織方式就大不相同了。 4.2 Stacks 第19頁/共43頁New Words & Expressionsqueue n.行列, 隊列; vi.排隊 cafeteria n.自助餐廳rear n.后面, 背后, 后方set aside 留出，撥出head pointer 頭指針tail pointer 尾指針crawl vi.& n. 爬行, 蠕動, 徐徐行進egocentric adj.自我中心的consumption n.消費, 消費量side effect 副作用migr

41、ate vi.移動, 移植; vt.使移居, 使移植circular queue 循環(huán)隊列envision vt.想象, 預(yù)想bridge vt.跨接,接通4.3 Queues第20頁/共43頁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.

42、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棧的插入與刪除操作都是在表的相同端進行的。而

43、與此不同，隊列是插入和刪除操作分別在兩端進行的表。我們已經(jīng)遇到過這種與等待隊列相關(guān)的結(jié)構(gòu)，在此種情況中，我們把它當作是一種先進先出的存儲系統(tǒng)。實際上，在那些對象輸入與輸出順序相同的系統(tǒng)中，隊列的概念是與生俱來的。隊列的結(jié)尾從等待隊列的關(guān)聯(lián)中得到名字。第21頁/共43頁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

44、 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結(jié)尾處，也就是條目被移出隊列的地方，被稱為隊列的隊首（有時候也稱為隊前），這就好像我們在快餐廳中下一個將點餐的顧客為一隊的隊首一樣。同樣，隊列的尾部，也就是條目被添加的地方，被稱為隊尾（或

45、者隊后）。第22頁/共43頁We 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.

46、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我們可以像存儲棧那樣通過連續(xù)單元組成的存儲塊在計算機主存儲器中實現(xiàn)隊列。因為我們需要在此結(jié)構(gòu)的兩端都進行操作，我們分配出兩個存儲單元用來當作指針，而非棧中那樣僅僅需要一個單元來存儲指針。其中的一個指針被稱為頭指針，用來保持隊列頭的軌跡；另一個指針被稱為尾指針，用來保持隊尾的軌跡。第23

47、頁/共43頁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 poi

48、nting 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如果一個隊列為空，那么兩個指針應(yīng)該指向相同的位置。每當新的條目被插入時，均會被置于尾指針所指向的位

49、置，同時修改尾指針，使之指向下一個未使用的位置。這樣，尾指針總是指向隊尾后的第一空閑存儲單元。將一條數(shù)據(jù)移出隊列的操作包括將頭指針指向的條目取出，同時調(diào)整頭指針使之指向排在被移出條目之后的位置 。第24頁/共43頁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). Th

50、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 Qu

51、eues以上描述的存儲系統(tǒng)仍然存在著問題。如果剩余的存儲器未被檢查，隊列會像冰河一樣在存儲器中增長，同時將在此道路上的所有其他數(shù)據(jù)破壞（如圖所示）。造成這種移動的相當一部分原因在于插入新條目時使用的“利己”策略，即在插入是僅僅將新數(shù)據(jù)置于當前隊尾之后，同時重置尾指針。如果我們添加足夠的條目，那么隊尾最后就會從計算機存儲器中溢出。第25頁/共43頁This consumption of memory is not the result of the queues size but is a side effect of the queues access procedure. (A small

52、yet active queue can easily require more of a machines 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 eac

53、h 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存儲器的消耗問題并不是因隊列的大小而生的，其真正原因在于隊列的實現(xiàn)問題。（一個小而動態(tài)變化的隊列比一個大而保持不變的隊列需要更多的機

54、器存儲資源。）解決存儲器空間問題的一個可能方法是：當最前面的條目被移出時,前移隊列中的其他條目，就好像人們在購買戲票時所采用的方法一樣，每當一個人買到票后，就前移一人。然而這種方法在計算機中運行的效率很低，因為它將需要對數(shù)據(jù)進行大量的移動。第26頁/共43頁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. Th

55、en, 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

56、 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用來在計算機中控制隊列的最一般的方法是為隊列分配一塊存儲器，從存儲塊的末端開始存儲隊列，并且讓隊列向另一端增長。然而當隊尾到達塊的末端，即隊列為空時，我們開始將新的條目反向于末端的方向插入。同樣，當隊列

57、的最后一條成為隊頭并被移出時，調(diào)整頭指針回到塊的開端，同時在此等待。在此方法下，隊列在一塊區(qū)域內(nèi)循環(huán)而不會出現(xiàn)內(nèi)存溢出情況。 第27頁/共43頁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 i

58、n the block is adjacent to the first cell.4.3 Queues采用此技術(shù)的實現(xiàn)方法稱為循環(huán)隊列，因為分配給隊列的一塊存儲單元組成了一個環(huán)。就一個隊列而言，存儲塊的最后一個單元與它的第一個單元相鄰。第28頁/共43頁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

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

60、detect whether the queue is empty or full. 4.3 Queues我們應(yīng)該再次認識到隊列使用者使用的概念結(jié)構(gòu)與實際在計算機存儲器中實現(xiàn)的循環(huán)結(jié)構(gòu)之間的差異。在前一個結(jié)構(gòu)的例子中，這些差異通常是通過軟件來銜接的。也就是說，連同存儲數(shù)據(jù)需要的一組存儲單元，隊列的實現(xiàn)應(yīng)該包括一組用來插入和移出隊列條目和探測隊列是否為空或滿的過程函數(shù)。然后，開發(fā)軟件其他單元的程序員可以通過這些方法來實現(xiàn)隊列的插入和移出操作，而不用關(guān)心其在存儲器中的實際實現(xiàn)。第29頁/共43頁常用英漢互譯技巧一、增譯法根據(jù)英漢兩種語言不同的思維方式、語言習(xí)慣和表達方式，在翻譯時增添一些詞、短句或句子，以便更準確地表達出原文所