計算機專業(yè)英語chapter 4PPT學(xué)習(xí)教案

1、會計學(xué)1計算機專業(yè)英語計算機專業(yè)英語chapter 44-2第1頁/共43頁4-31. Three reasons for using data structures are efficiency, abstraction, and reusability. 2. The properties of Stack, Queue, and Tree3. 掌握常用英漢互譯技巧掌握常用英漢互譯技巧 第2頁/共43頁4-4New Words & Expressions:harsh table 雜湊雜湊(哈希哈希)表表priority queues 優(yōu)先隊列優(yōu)先隊列reusability n.復(fù)用性復(fù)用性

2、binary tree 二叉樹二叉樹traversing 遍歷，走過遍歷，走過context-free 與上下文無關(guān)與上下文無關(guān)4.1 An Introduction to Data Structures 第3頁/共43頁4-5Data 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

3、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 l

4、ists, stacks, queues, sets, hash tables, trees, heaps, priority queues, and graphs. Three reasons for using data structures are efficiency, abstraction, and reusability.數(shù)據(jù)以各種形狀和大小出現(xiàn)，但是它常常可以用同樣的方式來組織。例數(shù)據(jù)以各種形狀和大小出現(xiàn)，但是它常?？梢杂猛瑯拥姆绞絹斫M織。例如如,考慮要做事情的列表、處方成份的清單或一個班級的閱讀目錄。雖然考慮要做事情的列表、處方成份的清單或一個班級的閱讀目錄。雖然它們包含不同

5、類型的數(shù)據(jù)它們包含不同類型的數(shù)據(jù),但他們都包含以一種相似方式組織的數(shù)據(jù)但他們都包含以一種相似方式組織的數(shù)據(jù):一個一個列表。列表是數(shù)據(jù)結(jié)構(gòu)的一個簡單例子。當(dāng)然，還有許多其他組織數(shù)據(jù)列表。列表是數(shù)據(jù)結(jié)構(gòu)的一個簡單例子。當(dāng)然，還有許多其他組織數(shù)據(jù)通用方法。在計算機技術(shù)中，一些最常用的組織方式是鏈接表、堆棧、通用方法。在計算機技術(shù)中，一些最常用的組織方式是鏈接表、堆棧、隊列、集合、哈希表、樹、堆、優(yōu)先隊列和圖。使用數(shù)據(jù)結(jié)構(gòu)的三個原隊列、集合、哈希表、樹、堆、優(yōu)先隊列和圖。使用數(shù)據(jù)結(jié)構(gòu)的三個原因是效率、抽象性和復(fù)用性。因是效率、抽象性和復(fù)用性。4.1 An Introduction to Data St

6、ructures 第4頁/共43頁4-6Efficiency 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

7、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)使用令算法更有效率的方法組織數(shù)據(jù)。例如，考慮一些我們用來數(shù)據(jù)結(jié)構(gòu)使用令算法更有效率的方法組織

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

9、raction 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 impl

10、ement each operation. In other words, data structures let us talk about programs in a less programmatic way.抽象化抽象化數(shù)據(jù)結(jié)構(gòu)提供一個更好理解的方法查看數(shù)據(jù)；因此，它們在解決問題中提數(shù)據(jù)結(jié)構(gòu)提供一個更好理解的方法查看數(shù)據(jù)；因此，它們在解決問題中提供一定的抽象化水平。例如，通過把數(shù)據(jù)儲存在堆棧中，我們可以將重點供一定的抽象化水平。例如，通過把數(shù)據(jù)儲存在堆棧中，我們可以將重點集中在對堆棧的操作上，如使元素進棧和出棧，而不是集中在實現(xiàn)操作的集中在對堆棧的操作上，如使元素進棧和出棧，而不是集中

11、在實現(xiàn)操作的細(xì)節(jié)上。換句話說，數(shù)據(jù)結(jié)構(gòu)使我們以較少的編程方式談?wù)摮绦颉＜?xì)節(jié)上。換句話說，數(shù)據(jù)結(jié)構(gòu)使我們以較少的編程方式談?wù)摮绦颉?.1 An Introduction to Data Structures 第6頁/共43頁4-8Reusability 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

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

13、 void pointers to the data rather than by maintaining private copies of the data in the data structure itself.復(fù)用性：復(fù)用性：因為數(shù)據(jù)結(jié)構(gòu)趨向于模塊化并和環(huán)境無關(guān)因為數(shù)據(jù)結(jié)構(gòu)趨向于模塊化并和環(huán)境無關(guān),所以數(shù)據(jù)結(jié)構(gòu)是可以復(fù)用的。因所以數(shù)據(jù)結(jié)構(gòu)是可以復(fù)用的。因為每種結(jié)構(gòu)有一個預(yù)定的接口為每種結(jié)構(gòu)有一個預(yù)定的接口,通過該接口限制訪問存儲在數(shù)據(jù)結(jié)構(gòu)中的數(shù)通過該接口限制訪問存儲在數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)，所以它們是模塊化的。也就是說據(jù)，所以它們是模塊化的。也就是說,我們只能使用接口定義的那些操作來我們只

14、能使用接口定義的那些操作來訪問數(shù)據(jù)。因為數(shù)據(jù)結(jié)構(gòu)能用于任何類型的數(shù)據(jù)訪問數(shù)據(jù)。因為數(shù)據(jù)結(jié)構(gòu)能用于任何類型的數(shù)據(jù),并用于多種環(huán)境中，所以并用于多種環(huán)境中，所以數(shù)據(jù)結(jié)構(gòu)與使用環(huán)境無關(guān)。在數(shù)據(jù)結(jié)構(gòu)與使用環(huán)境無關(guān)。在C語言中，我們通過使用空指針，而不是通語言中，我們通過使用空指針，而不是通過維護非公開的數(shù)據(jù)備份，使數(shù)據(jù)結(jié)構(gòu)存儲任何類型的數(shù)據(jù)。過維護非公開的數(shù)據(jù)備份，使數(shù)據(jù)結(jié)構(gòu)存儲任何類型的數(shù)據(jù)。4.1 An Introduction to Data Structures 第7頁/共43頁4-9New Words & Expressionsinviting adj.引人動心的引人動心的contiguou

15、s adj.鄰近的鄰近的, 接接近的近的stack n. 堆棧堆棧insertion n.插入插入deletion n.刪除刪除, 刪除部分刪除部分pop 退棧退棧push 進棧進棧backtrack v.回溯回溯pseudocode n.計計偽代碼偽代碼retrieve v.重新得到；重新得到；n.找回找回pointer n.指針指針pertinent adj.有關(guān)的有關(guān)的, 相干相干的的, 中肯的中肯的extract vt. 取，引取，引 back out 返回返回entail vt. 使承擔(dān)，使承擔(dān)， 帶來帶來traverse v.遍歷遍歷shrink v.收縮收縮allot vt.分配

16、分配,充當(dāng)充當(dāng),依靠依靠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頁4-10One of the properties of a list that makes a linked structure more inviting tha

17、n 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 fi

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

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

20、的系統(tǒng)。這種現(xiàn)象的一個例子就是堆棧。在堆棧中，插入和刪除操方便的系統(tǒng)。這種現(xiàn)象的一個例子就是堆棧。在堆棧中，插入和刪除操作都在結(jié)構(gòu)的相同末端進行。如此限制的結(jié)果就是最后一個進入表的記作都在結(jié)構(gòu)的相同末端進行。如此限制的結(jié)果就是最后一個進入表的記錄也就是第一個從表中刪除的記錄。這種結(jié)構(gòu)稱為后進先出結(jié)構(gòu)。錄也就是第一個從表中刪除的記錄。這種結(jié)構(gòu)稱為后進先出結(jié)構(gòu)。4.2 Stacks 第9頁/共43頁4-11 The end of a stack at which entries are inserted and deleted is called the top of the stack. The

21、 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 deletion operations. The process of inserting an object on the stack is called a push operation, and the proce

22、ss 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.堆棧尾部可以進行插入和刪除操作的記錄稱為堆棧的棧頂，另一端叫做棧底。為了表示如何限制堆棧只能從棧頂訪問，我們用一種特殊的術(shù)語來表示插入和刪除操作。把一個對象插入堆棧的操作稱為進棧操作，而從堆棧中刪除一個對象的操作稱為出棧操作，所以我們常說將一個條目進?；蛘邔⑵涑鰲?。堆棧尾部可以進行插入和刪除操作的記錄稱為堆棧的棧頂，另一端叫做棧底。為

23、了表示如何限制堆棧只能從棧頂訪問，我們用一種特殊的術(shù)語來表示插入和刪除操作。把一個對象插入堆棧的操作稱為進棧操作，而從堆棧中刪除一個對象的操作稱為出棧操作，所以我們常說將一個條目進棧或者將其出棧。4.2 Stacks 第10頁/共43頁4-12BacktrackingA classic application of a stack involves the execution of a program involving procedures as found in our pseudocode. When the execution of a procedure is requested,

24、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 the location to which execution ulti

25、mately returns.回溯回溯堆棧的一個典型應(yīng)用發(fā)生在一個程序單元調(diào)用一個過程的操作中。為了完堆棧的一個典型應(yīng)用發(fā)生在一個程序單元調(diào)用一個過程的操作中。為了完成這個調(diào)用，機器必須將它的注意力轉(zhuǎn)移到這個過程上；當(dāng)過程調(diào)用結(jié)束成這個調(diào)用，機器必須將它的注意力轉(zhuǎn)移到這個過程上；當(dāng)過程調(diào)用結(jié)束后，機器必須返回到程序塊進行調(diào)用時所處的位置。這就意味著必須有一后，機器必須返回到程序塊進行調(diào)用時所處的位置。這就意味著必須有一種用來記錄操作結(jié)束后返回的位置的機制。種用來記錄操作結(jié)束后返回的位置的機制。4.2 Stacks 第11頁/共43頁4-13The situation is complicate

26、d 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 pr

27、oper place 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. 如果一個被調(diào)用的過程本身還要調(diào)用其他過程，而那些過程同樣也需要調(diào)用另外的過程，這樣一來整個情形就會很復(fù)雜。因此，返回地址的記憶就開始堆積。然后，當(dāng)每一個過程都結(jié)束后，操作必須返回到被稱為完成過程的程序塊中的合適位置。因此，系統(tǒng)需要按照適當(dāng)?shù)捻樞虼鎯?/p>

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

29、tack, 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 in that it demonstrates the relationship between stacks and the process of back

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

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

32、ay 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 while pushing the names we find onto a stack. Afte

33、r reaching the end of the list, we print the names as we pop them off the stack. 我們在來舉另一個例子，假設(shè)反向輸出一張鏈接表中的姓名，也就是把我們在來舉另一個例子，假設(shè)反向輸出一張鏈接表中的姓名，也就是把最后一個名字第一個輸出。問題是我們只能跟著鏈接結(jié)構(gòu)訪問姓名。因最后一個名字第一個輸出。問題是我們只能跟著鏈接結(jié)構(gòu)訪問姓名。因此，我們需要一種方式，通過這種方式，我們可以保持每一個姓名能被此，我們需要一種方式，通過這種方式，我們可以保持每一個姓名能被檢索，直到排列在這個姓名之后的姓名被得到并輸出。我們的方案是從檢索

34、，直到排列在這個姓名之后的姓名被得到并輸出。我們的方案是從鏈接表的開始順序遍歷到結(jié)尾，與此同時把每一個姓名按照遍歷順序進鏈接表的開始順序遍歷到結(jié)尾，與此同時把每一個姓名按照遍歷順序進棧。當(dāng)?shù)竭_鏈接表的末尾后，我們通過出棧操作來輸出姓名。棧。當(dāng)?shù)竭_鏈接表的末尾后，我們通過出棧操作來輸出姓名。4.2 Stacks 第14頁/共43頁4-16Stack ImplementationTo implement a stack structure in a computers memory, it is customary to reserve a block of contiguous memory c

35、ells 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 room is reserved, memory space will be wasted.) One end of th

36、is 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)棧的實現(xiàn)為了在計算機存儲中實現(xiàn)棧結(jié)構(gòu)，一般采取的方法是保留一塊足夠容納棧大小變化為了在計算機存儲中實現(xiàn)棧結(jié)構(gòu)，一般采取的方法是保

37、留一塊足夠容納棧大小變化的內(nèi)存單元。（通常來說，確定塊的大小是一個很重要的任務(wù)。如果保留的空間過的內(nèi)存單元。（通常來說，確定塊的大小是一個很重要的任務(wù)。如果保留的空間過小，那么棧最后可能從所分配的存儲空間中溢出；而如果保留的空間過大，又是一小，那么棧最后可能從所分配的存儲空間中溢出；而如果保留的空間過大，又是一種浪費。）塊的一端作為棧底，棧的第一條數(shù)據(jù)會被存儲在這里，以后的條目被依種浪費。）塊的一端作為棧底，棧的第一條數(shù)據(jù)會被存儲在這里，以后的條目被依次放置在它之后的存儲單元中，也就是堆棧向另外一端增加。次放置在它之后的存儲單元中，也就是堆棧向另外一端增加。4.2 Stacks 第15頁/共4

38、3頁4-17Thus, as entries are pushed and popped, the top of the stack moves back and forth within the reserved block of memory 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

39、known as the stack pointer. That is, the stack pointer points to the top of the stack. 因此，在條目進棧和出棧的時候，棧頂?shù)奈恢镁驮诖鎯卧獕K中前后移動。為了保存這個位置的軌跡，棧頂條目的地址被存儲在一個附加的存儲單元中，這個附加的存儲單元被被稱為堆棧指針。也就是說，堆棧指針就是一個指向棧頂?shù)闹羔?。因此，在條目進棧和出棧的時候，棧頂?shù)奈恢镁驮诖鎯卧獕K中前后移動。為了保存這個位置的軌跡，棧頂條目的地址被存儲在一個附加的存儲單元中，這個附加的存儲單元被被稱為堆棧指針。也就是說，堆棧指針就是一個指向棧頂?shù)闹羔槨?

40、.2 Stacks 第16頁/共43頁4-18The 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 place the new entry at this location. To pop an entry from the stack, we r

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

42、之前的空白。然后將新的條目置于此處。為了將條目從堆棧中彈出，我們首先讀出堆棧指針?biāo)赶虻臄?shù)據(jù)，然后調(diào)整此指針指向堆棧中的下一條數(shù)據(jù)所在的存儲單元。4.2 Stacks 第17頁/共43頁4-19As 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. N

43、ote 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 contain procedures for pushing entries, popping entries, testing for an empty stack, and testing for

44、a full stack.同我們觀察到表中的情況一樣，程序員也可以將堆棧編寫成一個可以進行進棧和出棧操作的抽象工具。注意，這些過程應(yīng)該可以處理諸如試圖從空棧中彈出數(shù)據(jù)，或者將數(shù)據(jù)壓入一個已經(jīng)填滿的堆棧等特殊情況。所以一個完整的堆棧系統(tǒng)應(yīng)該包括進棧、出棧、測試堆棧是否空或滿的功能。同我們觀察到表中的情況一樣，程序員也可以將堆棧編寫成一個可以進行進棧和出棧操作的抽象工具。注意，這些過程應(yīng)該可以處理諸如試圖從空棧中彈出數(shù)據(jù)，或者將數(shù)據(jù)壓入一個已經(jīng)填滿的堆棧等特殊情況。所以一個完整的堆棧系統(tǒng)應(yīng)該包括進棧、出棧、測試堆棧是否空或滿的功能。4.2 Stacks 第18頁/共43頁4-20A stack o

45、rganized 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 fixed block of memory and be assured that the stack will always fit. A solution is to implement the stack as

46、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 pieces of available space anywhere in memory. In such a situation, the conceptual stack structure will be quite

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

48、棧限定在一塊固定塊中的局限性，因為它允許將新的條目插入存儲器中任何一塊足夠大的空閑空間中。在這種情況下，概念上的堆目插入存儲器中任何一塊足夠大的空閑空間中。在這種情況下，概念上的堆棧結(jié)構(gòu)與其在存儲器中實際的數(shù)據(jù)組織方式就大不相同了。棧結(jié)構(gòu)與其在存儲器中實際的數(shù)據(jù)組織方式就大不相同了。 4.2 Stacks 第19頁/共43頁4-21New Words & Expressionsqueue n.行列行列, 隊列隊列; vi.排隊排隊 cafeteria n.自助餐廳自助餐廳rear n.后面后面, 背后背后, 后方后方set aside 留出，撥出留出，撥出head pointer 頭指針頭指針

49、tail pointer 尾指針尾指針crawl vi.& n. 爬行爬行, 蠕動蠕動, 徐徐行進徐徐行進egocentric adj.自我中心的自我中心的consumption n.消費消費, 消費量消費量side effect 副作用副作用migrate vi.移動移動, 移植移植; vt.使移居使移居, 使移植使移植circular queue 循環(huán)隊列循環(huán)隊列envision vt.想象想象, 預(yù)想預(yù)想bridge vt.跨接跨接,接通接通4.3 Queues第20頁/共43頁4-22In contrast to a stack in which both insertions and

50、 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 this structure in relation to waiting lines, where we recognized it as being a first-in, first-out (FIFO) storage system. Actual

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

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

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

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

55、e structure, we set aside two memory cells to use as pointers instead of just one, as we did for a stack. 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)隊列。因

56、為我們需要在此結(jié)構(gòu)的兩端都進行操作，我們分配出兩個存儲單元用來當(dāng)作指針，而非棧中那樣僅僅需要一個單元來存儲指針。其中的一個指針被稱為頭指針，用來保持隊列頭的軌跡；另一個指針被稱為尾指針，用來保持隊尾的軌跡。我們可以像存儲棧那樣通過連續(xù)單元組成的存儲塊在計算機主存儲器中實現(xiàn)隊列。因為我們需要在此結(jié)構(gòu)的兩端都進行操作，我們分配出兩個存儲單元用來當(dāng)作指針，而非棧中那樣僅僅需要一個單元來存儲指針。其中的一個指針被稱為頭指針，用來保持隊列頭的軌跡；另一個指針被稱為尾指針，用來保持隊尾的軌跡。第23頁/共43頁4-25When the queue is empty, both of these point

57、ers 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 pointing to the first vacancy at the tail of the queu

58、e. 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)該指向相同的位置。每當(dāng)新的條目如果一個隊列為空，那么兩個指針應(yīng)該指向相同的位置。每當(dāng)新的條目被插入時，均會被置于尾指針?biāo)赶虻奈恢?，同時修改尾指針，使之指被插入時，均

59、會被置于尾指針?biāo)赶虻奈恢茫瑫r修改尾指針，使之指向下一個未使用的位置。這樣，尾指針總是指向隊尾后的第一空閑存儲向下一個未使用的位置。這樣，尾指針總是指向隊尾后的第一空閑存儲單元。將一條數(shù)據(jù)移出隊列的操作包括將頭指針指向的條目取出，同時單元。將一條數(shù)據(jù)移出隊列的操作包括將頭指針指向的條目取出，同時調(diào)整頭指針使之指向排在被移出條目之后的位置調(diào)整頭指針使之指向排在被移出條目之后的位置 。第24頁/共43頁4-26A problem remains with the storage system as described thus far. If left unchecked, the queue

60、crawls slowly through memory like a glacier, destroying any other data in its path (Figure 4.2). This 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 entr