Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 40
Текст из файла (страница 40)
The problem of managing such a heterogeneous collection of objectsis more difficult than the problem of managing a homogeneous collection, where all objectshave the same fields. Since most of the data structures we shall consider are composed ofhomogeneous elements, it will be sufficient for our purposes to use the multiple-arrayrepresentation of objects.Allocating and freeing objectsTo insert a key into a dynamic set represented by a doubly linked list, we must allocate apointer to a currently unused object in the linked-list representation.
Thus, it is useful tomanage the storage of objects not currently used in the linked-list representation so that onecan be allocated. In some systems, a garbage collector is responsible for determining whichobjects are unused. Many applications, however, are simple enough that they can bearresponsibility for returning an unused object to a storage manager.
We shall now explore theproblem of allocating and freeing (or deallocating) homogeneous objects using the example ofa doubly linked list represented by multiple arrays.Suppose that the arrays in the multiple-array representation have length m and that at somemoment the dynamic set contains n ≤ m elements. Then n objects represent elements currentlyin the dynamic set, and the remaining m–n objects are free; the free objects can be used torepresent elements inserted into the dynamic set in the future.We keep the free objects in a singly linked list, which we call the free list. The free list usesonly the next array, which stores the next pointers within the list.
The head of the free list isheld in the global variable free. When the dynamic set represented by linked list L isnonempty, the free list may be intertwined with list L, as shown in Figure 10.7. Note that eachobject in the representation is either in list L or in the free list, but not in both.Figure 10.7: The effect of the ALLOCATE-OBJECT and FREE-OBJECT procedures. (a) Thelist of Figure 10.5 (lightly shaded) and a free list (heavily shaded). Arrows show the free-liststructure. (b) The result of calling ALLOCATE-OBJECT() (which returns index 4), settingkey[4] to 25, and calling LIST-INSERT(L, 4).
The new free-list head is object 8, which hadbeen next[4] on the free list. (c) After executing LIST-DELETE(L, 5), we call FREEOBJECT(5). Object 5 becomes the new free-list head, with object 8 following it on the freelist.The free list is a stack: the next object allocated is the last one freed. We can use a listimplementation of the stack operations PUSH and POP to implement the procedures forallocating and freeing objects, respectively. We assume that the global variable free used inthe following procedures points to the first element of the free list.ALLOCATE-OBJECT()1 if free = NIL2then error "out of space"3else x ← free4free ← next[x]5return xFREE-OBJECT(x)1 next[x] ← free2 free ← xThe free list initially contains all n unallocated objects.
When the free list has been exhausted,the ALLOCATE-OBJECT procedure signals an error. It is common to use a single free list toservice several linked lists. Figure 10.8 shows two linked lists and a free list intertwinedthrough key, next, and prev arrays.Figure 10.8: Two linked lists, L1 (lightly shaded) and L2 (heavily shaded), and a free list(darkened) intertwined.The two procedures run in O(1) time, which makes them quite practical. They can bemodified to work for any omogeneous collection of objects by letting any one of the fields inthe object act like a next field in the free list.Exercises 10.3-1Draw a picture of the sequence 13, 4, 8, 19, 5, 11 stored as a doubly linked list using themultiple-array representation. Do the same for the single-array representation.Exercises 10.3-2Write the procedures ALLOCATE-OBJECT and FREE-OBJECT for a homogeneouscollection of objects implemented by the single-array representation.Exercises 10.3-3Why don't we need to set or reset the prev fields of objects in the implementation of theALLOCATE-OBJECT and FREE-OBJECT procedures?Exercises 10.3-4It is often desirable to keep all elements of a doubly linked list compact in storage, using, forexample, the first m index locations in the multiple-array representation.
(This is the case in apaged, virtual-memory computing environment.) Explain how the procedures ALLOCATE>OBJECT and FREE-OBJECT can be implemented so that the representation is compact.Assume that there are no pointers to elements of the linked list outside the list itself. (Hint:Use the array implementation of a stack.)Exercises 10.3-5Let L be a doubly linked list of length m stored in arrays key, prev, and next of length n.Suppose that these arrays are managed by ALLOCATE-OBJECT and FREE-OBJECTprocedures that keep a doubly linked free list F. Suppose further that of the n items, exactly mare on list L and n-m are on the free list.
Write a procedure COMPACTIFY-LIST(L, F) that,given the list L and the free list F, moves the items in L so that they occupy array positions 1,2,..., m and adjusts the free list F so that it remains correct, occupying array positions m + 1, m+ 2,..., n. The running time of your procedure should be Θ(m), and it should use only aconstant amount of extra space. Give a careful argument for the correctness of yourprocedure.10.4 Representing rooted treesThe methods for representing lists given in the previous section extend to any homogeneousdata structure.
In this section, we look specifically at the problem of representing rooted treesby linked data structures. We first look at binary trees, and then we present a method forrooted trees in which nodes can have an arbitrary number of children.We represent each node of a tree by an object. As with linked lists, we assume that each nodecontains a key field. The remaining fields of interest are pointers to other nodes, and they varyaccording to the type of tree.Binary treesAs shown in Figure 10.9, we use the fields p, left, and right to store pointers to the parent, leftchild, and right child of each node in a binary tree T .
If p[x] = NIL, then x is the root. If nodex has no left child, then left[x] = NIL, and similarly for the right child. The root of the entiretree T is pointed to by the attribute root[T]. If root[T] = NIL, then the tree is empty.Figure 10.9: The representation of a binary tree T. Each node x has the fields p[x] (top), left[x](lower left), and right[x] (lower right). The key fields are not shown.Rooted trees with unbounded branchingThe scheme for representing a binary tree can be extended to any class of trees in which thenumber of children of each node is at most some constant k: we replace the left and rightfields by child1, child2,..., childk.
This scheme no longer works when the number of childrenof a node is unbounded, since we do not know how many fields (arrays in the multiple-arrayrepresentation) to allocate in advance. Moreover, even if the number of children k is boundedby a large constant but most nodes have a small number of children, we may waste a lot ofmemory.Fortunately, there is a clever scheme for using binary trees to represent trees with arbitrarynumbers of children.
It has the advantage of using only O(n) space for any n-node rooted tree.The left-child, right-sibling representation is shown in Figure 10.10. As before, each nodecontains a parent pointer p, and root[T] points to the root of tree T . Instead of having apointer to each of its children, however, each node x has only two pointers:Figure 10.10: The left-child, right-sibling representation of a tree T . Each node x has fieldsp[x] (top), left-child[x] (lower left), and right-sibling[x] (lower right).
Keys are not shown.1. left-child[x] points to the leftmost child of node x, and2. right-sibling[x] points to the sibling of x immediately to the right.If node x has no children, then left-child[x] = NIL, and if node x is the rightmost child of itsparent, then right-sibling[x] = NIL.Other tree representationsWe sometimes represent rooted trees in other ways. In Chapter 6, for example, we representeda heap, which is based on a complete binary tree, by a single array plus an index. The treesthat appear in Chapter 21 are traversed only toward the root, so only the parent pointers arepresent; there are no pointers to children.
Many other schemes are possible. Which scheme isbest depends on the application.Exercises 10.4-1Draw the binary tree rooted at index 6 that is represented by the following fields.index key left right12345678910121541021871421578105NIL1NIL6NILNIL3NILNIL9NIL4NIL2NILNILExercises 10.4-2Write an O(n)-time recursive procedure that, given an n-node binary tree, prints out the key ofeach node in the tree.Exercises 10.4-3Write an O(n)-time nonrecursive procedure that, given an n-node binary tree, prints out thekey of each node in the tree. Use a stack as an auxiliary data structure.Exercises 10.4-4Write an O(n)-time procedure that prints all the keys of an arbitrary rooted tree with n nodes,where the tree is stored using the left-child, right-sibling representation.Exercises 10.4-5:Write an O(n)-time nonrecursive procedure that, given an n-node binary tree, prints out thekey of each node.
Use no more than constant extra space outside of the tree itself and do notmodify the tree, even temporarily, during the procedure.Exercises 10.4-6:The left-child, right-sibling representation of an arbitrary rooted tree uses three pointers ineach node: left-child, right-sibling, and parent.
From any node, its parent can be reached andidentified in constant time and all its children can be reached and identified in time linear inthe number of children. Show how to use only two pointers and one boolean value in eachnode so that the parent of a node or all of its children can be reached and identified in timelinear in the number of children.Problems 10-1: Comparisons among listsFor each of the four types of lists in the following table, what is the asymptotic worst-caserunning time for each dynamic-set operation listed?unsorted, singly sorted, singly unsorted, doubly sorted, doublylinkedlinkedlinkedlinkedSEARCH(L, k)INSERT(L, x)DELETE(L, x)SUCCESSOR(L, x)PREDECESSOR(L,x)MINIMUM(L)MAXIMUM(L)Problems 10-2: Mergeable heaps using linked listsA mergeable heap supports the following operations: MAKE-HEAP (which creates an emptymergeable heap), INSERT, MINIMUM, EXTRACT-MIN, and UNION.[1] Show how toimplement mergeable heaps using linked lists in each of the following cases.
Try to makeeach operation as efficient as possible. Analyze the running time of each operation in terms ofthe size of the dynamic set(s) being operated on.a. Lists are sorted.b. Lists are unsorted.c. Lists are unsorted, and dynamic sets to be merged are disjoint.Problems 10-3: Searching a sorted compact listExercise 10.3-4 asked how we might maintain an n-element list compactly in the first npositions of an array. We shall assume that all keys are distinct and that the compact list isalso sorted, that is, key[i] < key[next[i]] for all i = 1, 2,..., n such that next[i] ≠ NIL.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
