Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 38
Текст из файла (страница 38)
The analysis of hashingrelies on probability, but most of the chapter requires no background in the subject.Binary search trees, which are covered in Chapter 12, support all the dynamic-set operationslisted above. In the worst case, each operation takes Θ(n) time on a tree with n elements, buton a randomly built binary search tree, the expected time for each operation is O(lg n). Binarysearch trees serve as the basis for many other data structures.Red-black trees, a variant of binary search trees, are introduced in Chapter 13. Unlikeordinary binary search trees, red-black trees are guaranteed to perform well: operations takeO(lg n) time in the worst case.
A red-black tree is a balanced search tree; Chapter 18 presentsanother kind of balanced search tree, called a B-tree. Although the mechanics of red-blacktrees are somewhat intricate, you can glean most of their properties from the chapter withoutstudying the mechanics in detail.
Nevertheless, walking through the code can be quiteinstructive.In Chapter 14, we show how to augment red-black trees to support operations other than thebasic ones listed above. First, we augment them so that we can dynamically maintain orderstatistics for a set of keys. Then, we augment them in a different way to maintain intervals ofreal numbers.Chapter 10: Elementary Data StructuresIn this chapter, we examine the representation of dynamic sets by simple data structures thatuse pointers. Although many complex data structures can be fashioned using pointers, wepresent only the redimentary ones: stacks, queues, linked lists, and rooted trees. We alsodiscuss a method by which objects and pointers can be synthesized from arrays.10.1 Stacks and queuesStacks and queues are dynamic sets in which the element removed from the set by theDELETE operation is prespecified.
In a stack, the element deleted from the set is the onemost recently inserted: the stack implements a last-in, first-out, or LIFO, policy. Similarly, ina queue, the element deleted is always the one that has been in the set for the longest time: thequeue implements a first-in, first out, or FIFO, policy. There are several efficient ways toimplement stacks and queues on a computer. In this section we show how to use a simplearray to implement each.StacksThe INSERT operation on a stack is often called PUSH, and the DELETE operation, whichdoes not take an element argument, is often called POP. These names are allusions to physicalstacks, such as the spring-loaded stacks of plates used in cafeterias.
The order in which platesare popped from the stack is the reverse of the order in which they were pushed onto thestack, since only the top plate is accessible.As shown in Figure 10.1, we can implement a stack of at most n elements with an array S[1,n]. The array has an attribute top[S] that indexes the most recently inserted element. Thestack consists of elements S[1 top[S]], where S[1] is the element at the bottom of the stackand S[top[S]] is the element at the top.Figure 10.1: An array implementation of a stack S. Stack elements appear only in the lightlyshaded positions. (a) Stack S has 4 elements. The top element is 9. (b) Stack S after the callsPUSH(S, 17) and PUSH(S, 3). (c) Stack S after the call POP(S) has returned the element 3,which is the one most recently pushed.
Although element 3 still appears in the array, it is nolonger in the stack; the top is element 17.When top[S] = 0, the stack contains no elements and is empty. The stack can be tested foremptiness by the query operation STACK-EMPTY. If an empty stack is popped, we say thestack underflows, which is normally an error.
If top[S] exceeds n, the stack overflows. (In ourpseudocode implementation, we don't worry about stack overflow.)The stack operations can each be implemented with a few lines of code.STACK-EMPTY(S)1 if top[S] = 02then return TRUE3else return FALSEPUSH(S, x)1 top[S] ← top[S] + 12 S[top[S]] ← xPOP(S)1 if STACK-EMPTY(S)2then error "underflow"34else top[S] ← top[S] - 1return S[top[S] + 1]Figure 10.1 shows the effects of the modifying operations PUSH and POP. Each of the threestack operations takes O(1) time.QueuesWe call the INSERT operation on a queue ENQUEUE, and we call the DELETE operationDEQUEUE; like the stack operation POP, DEQUEUE takes no element argument.
The FIFOproperty of a queue causes it to operate like a line of people in the registrar's office. Thequeue has a head and a tail. When an element is enqueued, it takes its place at the tail of thequeue, just as a newly arriving student takes a place at the end of the line. The elementdequeued is always the one at the head of the queue, like the student at the head of the linewho has waited the longest.
(Fortunately, we don't have to worry about computationalelements cutting into line.)Figure 10.2 shows one way to implement a queue of at most n - 1 elements using an array Q[1n]. The queue has an attribute head[Q] that indexes, or points to, its head. The attributetail[Q] indexes the next location at which a newly arriving element will be inserted into thequeue. The elements in the queue are in locations head[Q], head[Q] +1,..., tail[Q] - 1, wherewe "wrap around" in the sense that location 1 immediately follows location n in a circularorder.
When head[Q] = tail[Q], the queue is empty. Initially, we have head[Q] = tail[Q] = 1.When the queue is empty, an attempt to dequeue an element causes the queue to underflow.When head[Q] = tail[Q] + 1, the queue is full, and an attempt to enqueue an element causesthe queue to overflow.Figure 10.2: A queue implemented using an array Q[1 12]. Queue elements appear only inthe lightly shaded positions. (a) The queue has 5 elements, in locations Q[7 11]. (b) Theconfiguration of the queue after the calls ENQUEUE(Q, 17), ENQUEUE(Q, 3), andENQUEUE(Q, 5). (c) The configuration of the queue after the call DEQUEUE(Q) returns thekey value 15 formerly at the head of the queue.
The new head has key 6.In our procedures ENQUEUE and DEQUEUE, the error checking for underflow and overflowhas been omitted. (Exercise 10.1-4 asks you to supply code that checks for these two errorconditions.)ENQUEUE(Q, x)1 Q[tail[Q]] ← x234if tail[Q] = length[Q]then tail[Q] ← 1else tail[Q] ← tail[Q] + 1DEQUEUE(Q)1 x ← Q[head[Q]]2 if head[Q] = length[Q]3then head[Q] ← 14else head[Q] ← head[Q] + 15 return xFigure 10.2 shows the effects of the ENQUEUE and DEQUEUE operations. Each operationtakes O(1) time.Exercises 10.1-1Using Figure 10.1 as a model, illustrate the result of each operation in the sequence PUSH(S,4), PUSH(S, 1), PUSH(S, 3), POP(S), PUSH(S, 8), and POP(S) on an initially empty stack Sstored in array S[1 6].Exercises 10.1-2Explain how to implement two stacks in one array A[1 n] in such a way that neither stackoverflows unless the total number of elements in both stacks together is n.
The PUSH andPOP operations should run in O(1) time.Exercises 10.1-3Using Figure 10.2 as a model, illustrate the result of each operation in the sequenceENQUEUE(Q, 4), ENQUEUE(Q, 1), ENQUEUE(Q, 3), DEQUEUE(Q), ENQUEUE(Q, 8),and DEQUEUE(Q) on an initially empty queue Q stored in array Q[1 6].Exercises 10.1-4Rewrite ENQUEUE and DEQUEUE to detect underflow and overflow of a queue.Exercises 10.1-5Whereas a stack allows insertion and deletion of elements at only one end, and a queue allowsinsertion at one end and deletion at the other end, a deque (double-ended queue) allowsinsertion and deletion at both ends. Write four O(1)-time procedures to insert elements intoand delete elements from both ends of a deque constructed from an array.Exercises 10.1-6Show how to implement a queue using two stacks.
Analyze the running time of the queueoperations.Exercises 10.1-7Show how to implement a stack using two queues. Analyze the running time of the stackoperations.10.2 Linked listsA linked list is a data structure in which the objects are arranged in a linear order. Unlike anarray, though, in which the linear order is determined by the array indices, the order in alinked list is determined by a pointer in each object. Linked lists provide a simple, flexiblerepresentation for dynamic sets, supporting (though not necessarily efficiently) all theoperations listed on page 198.As shown in Figure 10.3, each element of a doubly linked list L is an object with a key fieldand two other pointer fields: next and prev.
The object may also contain other satellite data.Given an element x in the list, next[x] points to its successor in the linked list, and prev[x]points to its predecessor. If prev[x] = NIL, the element x has no predecessor and is thereforethe first element, or head, of the list. If next[x] = NIL, the element x has no successor and istherefore the last element, or tail, of the list. An attribute head[L] points to the first element ofthe list. If head[L] = NIL, the list is empty.Figure 10.3: (a) A doubly linked list L representing the dynamic set {1, 4, 9, 16}. Eachelement in the list is an object with fields for the key and pointers (shown by arrows) to thenext and previous objects.
The next field of the tail and the prev field of the head are NIL,indicated by a diagonal slash. The attribute head[L] points to the head. (b) Following theexecution of LIST-INSERT(L, x), where key[x] = 25, the linked list has a new object with key25 as the new head. This new object points to the old head with key 9. (c) The result of thesubsequent call LIST-DELETE(L, x), where x points to the object with key 4.A list may have one of several forms. It may be either singly linked or doubly linked, it maybe sorted or not, and it may be circular or not. If a list is singly linked, we omit the prevpointer in each element. If a list is sorted, the linear order of the list corresponds to the linearorder of keys stored in elements of the list; the minimum element is the head of the list, andthe maximum element is the tail.
If the list is unsorted, the elements can appear in any order.In a circular list, the prev pointer of the head of the list points to the tail, and the next pointerof the tail of the list points to the head. The list may thus be viewed as a ring of elements. Inthe remainder of this section, we assume that the lists with which we are working are unsortedand doubly linked.Searching a linked listThe procedure LIST-SEARCH(L, k) finds the first element with key k in list L by a simplelinear search, returning a pointer to this element. If no object with key k appears in the list,then NIL is returned. For the linked list in Figure 10.3(a), the call LIST-SEARCH(L, 4)returns a pointer to the third element, and the call LIST-SEARCH(L, 7) returns NIL.LIST-SEARCH(L, k)1 x ← head[L]2 while x ≠ NIL and key[x] ≠ k3do x ← next[x]4 return xTo search a list of n objects, the LIST-SEARCH procedure takes Θ(n) time in the worst case,since it may have to search the entire list.Inserting into a linked listGiven an element x whose key field has already been set, the LIST-INSERT procedure"splices" x onto the front of the linked list, as shown in Figure 10.3(b).LIST-INSERT(L, x)1 next[x] ← head[L]2 if head[L] ≠ NIL3then prev[head[L]] ← x4 head[L] ← x5 prev[x] ← NILThe running time for LIST-INSERT on a list of n elements is O(1).Deleting from a linked listThe procedure LIST-DELETE removes an element x from a linked list L.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
