chap11.htm

介绍算法的书籍

<h2>A multiple-array representation of objects</h2><P>
We can represent a collection of objects that have the same fields by using an array for each field. As an example, Figure 11.5 shows how we can implement the linked list of Figure 11.3(a) with three arrays. The array <I>key</I> holds the values of the keys currently in the dynamic set, and the pointers are stored in the arrays <I>next</I> and <I>prev</I>. For a given array index <I>x</I>, <I>key</I>[<I>x</I>], <I>next</I>[<I>x</I>], and <I>prev</I>[<I>x</I>] represent an object in the linked list. Under this interpretation, a pointer <I>x</I> is simply a common index into the <I>key</I>, <I>next</I>, and <I>prev</I> arrays.<P>
In Figure 11.3(a), the object with key 4 follows the object with key 16 in the linked list. In Figure 11.5, key 4 appears in <I>key</I>[2], and key 16 appears in <I>key</I>[5], so we have <I>next</I>[5] = 2 and <I>prev</I>[2] = 5. Although the constant <FONT FACE="Courier New" SIZE=2>NIL</FONT> appears in the <I>next</I> field of the tail and the <I>prev</I> field of the head, we usually use an integer (such as 0 or -1) that cannot possibly represent an actual index into the arrays. A variable <I>L</I> holds the index of the head of the list.<P>
In our pseudocode, we have been using square brackets to denote both the indexing of an array and the selection of a field (attribute) of an object. Either way, the meanings of <I>key</I>[<I>x</I>], <I>next</I>[<I>x</I>], and <I>prev</I>[<I>x</I>] are consistent with implementation practice.<P>
<img src="209_a.gif"><P>
<h4><a name="07b5_0001">Figure 11.5 The linked list of Figure 11.3(a) represented by the arrays key, next, and prev. Each vertical slice of the arrays represents a single object. Stored pointers correspond to the array indices shown at the top; the arrows show how to interpret them. Lightly shaded object positions contain list elements. The variable L keeps the index of the head.<a name="07b5_0001"></sub></sup></h4><P>
<img src="210_a.gif"><P>
<h4><a name="07b5_0002">Figure 11.6 The linked list of Figures 11.3(a) and 11.5 represented in a single array A. Each list element is an object that occupies a contiguous subarray of length 3 within the array. The three fields key, next, and prev correspond to the offsets 0, 1, and 2, respectively. A pointer to an object is an index of the first element of the object. Objects containing list elements are lightly shaded, and arrows show the list ordering.<a name="07b5_0002"></sub></sup></h4><P>
<P>







<h2>A single-array representation of objects</h2><P>
The words in a computer memory are typically addressed by integers from 0 to <I>M</I> - 1, where <I>M</I> is a suitably large integer. In many programming languages, an object occupies a contiguous set of locations in the computer memory. A pointer is simply the address of the first memory location of the object, and other memory locations within the object can be indexed by adding an offset to the pointer.<P>
We can use the same strategy for implementing objects in programming environments that do not provide explicit pointer data types. For example, Figure 11.6 shows how a single array <I>A</I> can be used to store the linked list from Figures 11.3(a) and 11.5. An object occupies a contiguous subarray <I>A</I>[<I>j </I>. . <I>k</I>]. Each field of the object corresponds to an offset in the range from 0 to <I>k</I> - <I>j</I>, and a pointer to the object is the index <I>j</I>. In Figure 11.6, the offsets corresponding to <I>key,</I> <I>next</I>, and <I>prev</I> are 0, 1, and 2, respectively. To read the value of <I>prev</I>[<I>i</I>], given a pointer <I>i</I>, we add the value <I>i </I>of the pointer to the offset 2, thus reading <I>A</I>[<I>i</I> + 2].<P>
The single-array representation is flexible in that it permits objects of different lengths to be stored in the same array. The problem of managing such a heterogeneous collection of objects is more difficult than the problem of managing a homogeneous collection, where all objects have the same fields. Since most of the data structures we shall consider are composed of homogeneous elements, it will be sufficient for our purposes to use the multiple-array representation of objects.<P>
<P>







<h2>Allocating and freeing objects</h2><P>
<a name="07b7_1409"><a name="07b7_140a"><a name="07b7_140b"><a name="07b7_140c"><a name="07b7_140d"><a name="07b7_140e">To insert a key into a dynamic set represented by a doubly linked list, we must allocate a pointer to a currently unused object in the linked-list representation. Thus, it is useful to manage the storage of objects not currently used in the linked-list representation so that one can be allocated. In some systems, a <I><B>garbage collector</I></B> is responsible for determining which objects are unused. Many applications, however, are simple enough that they can bear responsibility for returning an unused object to a storage manager. We shall now explore the problem of allocating and freeing (or deallocating) homogeneous objects using the example of a doubly linked list represented by multiple arrays.<P>
<img src="211_a.gif"><P>
<h4><a name="07b7_1412">Figure 11.7 The effect of the <FONT FACE="Courier New" SIZE=2>ALLOCATE<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>OBJECT</FONT></FONT> and <FONT FACE="Courier New" SIZE=2>FREE<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>OBJECT</FONT></FONT></FONT></FONT> procedures. (a) The list of Figure 11.5 (lightly shaded) and a free list (heavily shaded). Arrows show the free-list structure. (b) The result of calling <FONT FACE="Courier New" SIZE=2>ALLOCATE<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>OBJECT</FONT></FONT></FONT>() (which returns index 4), setting key[4] to 25, and calling <FONT FACE="Courier New" SIZE=2>LIST<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT></FONT></FONT>(L, 4). The new free-list head is object 8, which had been next[4] on the free list. (c) After executing <FONT FACE="Courier New" SIZE=2>LIST<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT></FONT></FONT>(L, 5), we call <FONT FACE="Courier New" SIZE=2>FREE<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>OBJECT</FONT></FONT></FONT>(5). Object 5 becomes the new free-list head, with object 8 following it on the free list.<a name="07b7_1412"></sub></sup></h4><P>
Suppose that the arrays in the multiple-array representation have length <I>m</I> and that at some moment the dynamic set contains <I>n</I> <img src="../images/lteq12.gif"> <I>m</I> elements. Then <I>n</I> objects represent elements currently in the dynamic set, and the remaining <I>m</I> - <I>n</I> objects are <I><B>free</I></B>; the free objects can be used to represent elements inserted into the dynamic set in the future.<P>
<a name="07b7_140f">We keep the free objects in a singly linked list, which we call the <I><B>free list</I></B>. The free list uses only the <I>next</I> array, which stores the <I>next</I> pointers within the list. The head of the free list is held in the global variable <I>free</I>. When the dynamic set represented by linked list <I>L</I> is nonempty, the free list may be intertwined with list <I>L</I>, as shown in Figure 11.7. Note that each object in the representation is either in list <I>L</I> or in the free list, but not in both.<P>
The free list is a stack: the next object allocated is the last one freed. We can use a list implementation of the stack operations <FONT FACE="Courier New" SIZE=2>PUSH</FONT> and <FONT FACE="Courier New" SIZE=2>POP</FONT> to implement the procedures for allocating and freeing objects, respectively.<P>
<img src="212_a.gif"><P>
<h4><a name="07b7_1413">Figure 11.8 Two linked lists, L<SUB>1</SUB> (lightly shaded) and L<SUB>2</SUB> (heavily shaded), and a free list (darkened) intertwined.<a name="07b7_1413"></sub></sup></h4><P>
We assume that the global variable <I>free</I> used in the following procedures points to the first element of the free list.<P>
<pre><a name="07b7_1410">ALLOCATE-OBJECT( )</sub></sup></pre><P>
<pre>1  <B>if</B> <I>free</I> = NIL</sub></sup></pre><P>
<pre>2      <B>then error</B> "out of space"</sub></sup></pre><P>
<pre>3      <B>else</B> <I>x</I> <img src="../images/arrlt12.gif"> <I>free</I></sub></sup></pre><P>
<pre>4           <I>free</I> <img src="../images/arrlt12.gif"> <I>next</I>[<I>x</I>]</sub></sup></pre><P>
<pre>5           <B>return</B> <I>x</I></sub></sup></pre><P>
<pre></sub></sup></pre><P>
<pre><a name="07b7_1411">FREE-OBJECT(<I>x</I>)</sub></sup></pre><P>
<pre>1  <I>next</I>[<I>x</I>] <img src="../images/arrlt12.gif"> <I>free</I></sub></sup></pre><P>
<pre>2  <I>free</I> <img src="../images/arrlt12.gif"> <I>x</I></sub></sup></pre><P>
The free list initially contains all <I>n</I> unallocated objects. When the free list has been exhausted, the <FONT FACE="Courier New" SIZE=2>ALLOCATE</FONT>-<FONT FACE="Courier New" SIZE=2>OBJECT</FONT> procedure signals an error. It is common to use a single free list to service several linked lists. Figure 11.8 shows three linked lists and a free list intertwined through <I>key</I>, <I>next</I>, and <I>prev</I> arrays.<P>
The two procedures run in <I>O</I>(1) time, which makes them quite practical. They can be modified to work for any homogeneous collection of objects by letting any one of the fields in the object act like a <I>next</I> field in the free list.<P>
<P>







<h2><a name="07b8_1415">Exercises<a name="07b8_1415"></h2><P>
<a name="07b8_1416">11.3-1<a name="07b8_1416"><P>
Draw a picture of the sequence <img src="../images/lftwdchv.gif">13, 4, 8, 19, 5, 11<img src="../images/wdrtchv.gif"> stored as a doubly linked list using the multiple-array representation. Do the same for the single-array representation.<P>
<a name="07b8_1417">11.3-2<a name="07b8_1417"><P>
Write the procedures <FONT FACE="Courier New" SIZE=2>ALLOCATE</FONT>-<FONT FACE="Courier New" SIZE=2>OBJECT</FONT> and <FONT FACE="Courier New" SIZE=2>FREE</FONT>-<FONT FACE="Courier New" SIZE=2>OBJECT</FONT> for a homogeneous collection of objects implemented by the single-array representation.<P>
<a name="07b8_1418">11.3-3<a name="07b8_1418"><P>
Why don't we need to set or reset the <I>prev</I> fields of objects in the implementation of the <FONT FACE="Courier New" SIZE=2>ALLOCATE</FONT>-<FONT FACE="Courier New" SIZE=2>OBJECT</FONT> and <FONT FACE="Courier New" SIZE=2>FREE</FONT>-<FONT FACE="Courier New" SIZE=2>OBJECT</FONT> procedures?<P>
<a name="07b8_1419">11.3-4<a name="07b8_1419"><P>
<a name="07b8_1412"><a name="07b8_1413">It is often desirable to keep all elements of a doubly linked list compact in storage, using, for example, the first <I>m</I> index locations in the multiple-array representation. (This is the case in a paged, virtual-memory computing environment.) Explain how the procedures <FONT FACE="Courier New" SIZE=2>ALLOCATE</FONT>-<FONT FACE="Courier New" SIZE=2>OBJECT</FONT> and <FONT FACE="Courier New" SIZE=2>FREE</FONT>-<FONT FACE="Courier New" SIZE=2>OBJECT</FONT> 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. (<I>Hint</I>: Use the array implementation of a stack.)<P>
<a name="07b8_141a">11.3-5<a name="07b8_141a"><P>
<a name="07b8_1414">Let <I>L</I> be a doubly linked list of length <I>m</I> stored in arrays <I>key, prev</I>, and <I>next</I> of length <I>n</I>. Suppose that these arrays are managed by <FONT FACE="Courier New" SIZE=2>ALLOCATE</FONT>-<FONT FACE="Courier New" SIZE=2>OBJECT</FONT> and <FONT FACE="Courier New" SIZE=2>FREE</FONT>-<FONT FACE="Courier New" SIZE=2>OBJECT</FONT> procedures that keep a doubly linked free list <I>F</I>. Suppose further that of the <I>n</I> items, exactly <I>m</I> are on list <I>L</I> and <I>n - m</I> are on the free list. Write a procedure <FONT FACE="Courier New" SIZE=2>COMPACTIFY</FONT>-<FONT FACE="Courier New" SIZE=2>LIST</FONT> (<I>L, F</I>) that, given the list <I>L</I> and the free list <I>F</I>, moves the items in <I>L</I> so that they occupy array positions 1, 2, . . . , <I>m</I> and adjusts the free list <I>F</I> so that it remains correct, occupying array positions <I>m +</I> 1,<I> m + </I>2,<I> . . . , n</I>. The running time of your procedure should be <img src="../images/bound.gif">(<I>m</I>), and it should use only a constant amount of extra space. Give a careful argument for the correctness of your procedure.<P>
<P>


<P>







<h1><a name="07b9_141a">11.4 Representing rooted trees<a name="07b9_141a"></h1><P>
<a name="07b9_1415"><a name="07b9_1416"><a name="07b9_1417"><a name="07b9_1418"><a name="07b9_1419">The methods for representing lists given in the previous section extend to any homogeneous data structure. In this section, we look specifically at the problem of representing rooted trees by linked data structures. We first look at binary trees, and then we present a method for rooted trees in which nodes can have an arbitrary number of children.<P>
We represent each node of a tree by an object. As with linked lists, we assume that each node contains a <I>key</I> field. The remaining fields of interest are pointers to other nodes, and they vary according to the type of tree.<P>





<h2>Binary trees</h2><P>
As shown in Figure 11.9, we use the fields <I>p</I>, <I>left</I>, and <I>right</I> to store pointers to the parent, left child, and right child of each node in a binary tree <I>T</I>. If <I>p</I>[<I>x</I>] = <FONT FACE="Courier New" SIZE=2>NIL</FONT>, then <I>x</I> is the root. If node <I>x</I> has no left child, then <I>left</I>[<I>x</I>] = <FONT FACE="Courier New" SIZE=2>NIL</FONT>, and similarly for the right child. The root of the entire tree <I>T</I> is pointed to by the attribute <I>root</I>[<I>T</I>]. If <I>root </I>[<I>T</I>] = <FONT FACE="Courier New" SIZE=2>NIL</FONT>, then the tree is empty.<P>
<img src="214_a.gif"><P>
<h4><a name="07ba_0001">Figure 11.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.<a name="07ba_0001"></sub></sup></h4><P>
<P>







<h2>Rooted trees with unbounded branching</h2><P>
The scheme for representing a binary tree can be extended to any class of trees in which the number of children of each node is at most some constant <I>k</I>: we replace the <I>left</I> and <I>right</I> fields by <I>child</I><SUB>1</SUB>, <I>child</I><SUB>2</SUB>, . . . , <I>child<SUB>k</I></SUB>. This scheme no longer works when the number of children of a node is unbounded, since we do not know how many fields (arrays in the multiple-array representation) to allocate in advance. Moreover, even if the number of children <I>k</I> is bounded by a large constant but most nodes have a small number of children, we may waste a lot of memory.<P>
<a name="07bb_141a">Fortunately, there is a clever scheme for using binary trees to represent trees with arbitrary numbers of children. It has the advantage of using only <I>O</I>(<I>n</I>) space for any <I>n</I>-node rooted tree. The <I><B>left-child, right-sibling representation</I></B> is shown in Figure 11.10. As before, each node contains a parent pointer <I>p</I>, and <I>root</I>[<I>T</I>] points to the root of tree <I>T</I>. Instead of having a pointer to each of its children, however, each node <I>x</I> has only two pointers:<P>
1.     <I>left-child</I>[<I>x</I>] points to the leftmost child of node <I>x</I>, and<P>
2.     <I>right-sibling</I>[<I>x</I>] points to the sibling of <I>x</I> immediately to the right.<P>
If node <I>x</I> has no children, then <I>left-child</I>[<I>x</I>] = <FONT FACE="Courier New" SIZE=2>NIL</FONT>, and if node <I>x</I> is the rightmost child of its parent, then <I>right-sibling</I>[<I>x</I>] = <FONT FACE="Courier New" SIZE=2>NIL</FONT>.<P>
<P>