chap11.htm

程序设计的艺术,此书是英文版的,经久不衰,非常的经典

<h2>Searching a linked list</h2><P>
<a name="07af_13f5"><a name="07af_13f6">The procedure <FONT FACE="Courier New" SIZE=2>LIST</FONT>-<FONT FACE="Courier New" SIZE=2>SEARCH</FONT>(<I>L, k</I>) finds the first element with key <I>k</I> in list <I>L</I> by a simple linear search, returning a pointer to this element. If no object with key <I>k</I> appears in the list, then <FONT FACE="Courier New" SIZE=2>NIL</FONT> is returned. For the linked list in Figure 11.3(a), the call <FONT FACE="Courier New" SIZE=2>LIST</FONT>-<FONT FACE="Courier New" SIZE=2>SEARCH</FONT>(<I>L</I>, 4) returns a pointer to the third element, and the call <FONT FACE="Courier New" SIZE=2>LIST</FONT>-<FONT FACE="Courier New" SIZE=2>SEARCH</FONT>(<I>L</I>, 7) returns <FONT FACE="Courier New" SIZE=2>NIL</FONT>.<P>
<img src="205_a.gif"><P>
<h4><a name="07af_13f8">Figure 11.3 (a) A doubly linked list L representing the dynamic set {1, 4, 9, 16}. Each element in the list is an object with fields for the key and pointers (shown by arrows) to the next and previous objects. The next field of the tail and the prev field of the head are <FONT FACE="Courier New" SIZE=2>NIL</FONT>, indicated by a diagonal slash. The attribute head[L] points to the head. (b) Following the execution of <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, x), where key[x] = 25, the linked list has a new object with key 25 as the new head. This new object points to the old head with key 9. (c) The result of the subsequent call <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, x), where x points to the object with key 4.<a name="07af_13f8"></sub></sup></h4><P>
<pre><a name="07af_13f7">LIST-SEARCH(<I>L</I>, <I>k</I>)</sub></sup></pre><P>
<pre>1  <I>x </I><img src="../images/arrlt12.gif"> head<I>[</I>L<I>]</I></sub></sup></pre><P>
<pre>2  <B>while</B> <I>x</I> <img src="../images/noteq.gif"> NIL and <I>key</I>[<I>x</I>] <img src="../images/noteq.gif"> <I>k</I></sub></sup></pre><P>
<pre>3      <B>do</B> <I>x</I> <img src="../images/arrlt12.gif"> <I>next</I>[<I>x</I>]</sub></sup></pre><P>
<pre>4  <B>return</B> <I>x</I></sub></sup></pre><P>
To search a list of <I>n</I> objects, the <FONT FACE="Courier New" SIZE=2>LIST</FONT>-<FONT FACE="Courier New" SIZE=2>SEARCH</FONT> procedure takes <img src="../images/bound.gif">(<I>n</I>) time in the worst case, since it may have to search the entire list.<P>
<P>







<h2>Inserting into a linked list</h2><P>
<a name="07b0_13f8"><a name="07b0_13f9">Given an element <I>x</I> whose <I>key</I> field has already been set, the <FONT FACE="Courier New" SIZE=2>LIST</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> procedure "splices" <I>x</I> onto the front of the linked list, as shown in Figure 11.3(b).<P>
<pre><a name="07b0_13fa">LIST-INSERT(<I>L, x</I>)</sub></sup></pre><P>
<pre>1  <I>next</I>[<I>x</I>] <img src="../images/arrlt12.gif"> <I>head</I>[<I>L</I>]</sub></sup></pre><P>
<pre>2<B>  if</B> <I>head</I>[<I>L</I>] <img src="../images/noteq.gif"> NIL</sub></sup></pre><P>
<pre>3      <B>then</B> <I>prev</I>[<I>head</I>[<I>L</I>]] <img src="../images/arrlt12.gif"> <I>x</I></sub></sup></pre><P>
<pre>4  <I>head</I>[<I>L</I>] <img src="../images/arrlt12.gif"> <I>x</I></sub></sup></pre><P>
<pre>5  <I>prev</I>[<I>x</I>] <img src="../images/arrlt12.gif"> NIL</sub></sup></pre><P>
The running time for <FONT FACE="Courier New" SIZE=2>LIST</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> on a list of <I>n</I> elements is <I>O</I>(1).<P>
<P>







<h2>Deleting from a linked list</h2><P>
<a name="07b1_13fb"><a name="07b1_13fc">The procedure <FONT FACE="Courier New" SIZE=2>LIST</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> removes an element <I>x</I> from a linked list <I>L</I>. It must be given a pointer to <I>x</I>, and it then "splices" <I>x</I> out of the list by updating pointers. If we wish to delete an element with a given key, we must first call <FONT FACE="Courier New" SIZE=2>LIST</FONT>-<FONT FACE="Courier New" SIZE=2>SEARCH</FONT> to retrieve a pointer to the element.<P>
<pre><a name="07b1_13fd">LIST-DELETE(<I>L</I>, <I>x</I>)</sub></sup></pre><P>
<pre>1  <B>if</B> <I>prev</I>[<I>x</I>] <img src="../images/noteq.gif"> NIL</sub></sup></pre><P>
<pre>2     <B>then</B> <I>next</I>[<I>prev</I>[<I>x</I>]] <img src="../images/arrlt12.gif"> <I>next</I>[<I>x</I>]</sub></sup></pre><P>
<pre>3     <B>else</B> <I>head</I>[<I>L</I>] <img src="../images/arrlt12.gif"> <I>next</I>[<I>x</I>]</sub></sup></pre><P>
<pre>4  <B>if</B> <I>next</I>[<I>x</I>] <img src="../images/noteq.gif"> NIL</sub></sup></pre><P>
<pre>5     <B>then</B> <I>prev</I>[<I>next</I>[<I>x</I>]] <img src="../images/arrlt12.gif"> <I>prev</I>[<I>x</I>]</sub></sup></pre><P>
Figure 11.3(c) shows how an element is deleted from a linked list. <FONT FACE="Courier New" SIZE=2>LIST-DELETE</FONT> runs in <I>O</I>(1) time, but if we wish to delete an element with a given key, <img src="../images/bound.gif">(<I>n</I>) time is required in the worst case because we must first call <FONT FACE="Courier New" SIZE=2>LIST</FONT>-<FONT FACE="Courier New" SIZE=2>SEARCH</FONT>.<P>
<P>







<h2>Sentinels</h2><P>
The code for <FONT FACE="Courier New" SIZE=2>LIST</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> would be simpler if we could ignore the boundary conditions at the head and tail of the list.<P>
<pre><a name="07b2_13fe">LIST-DELETE'(<I>L</I>, <I>x</I>)</sub></sup></pre><P>
<pre>1  <I>next</I>[<I>prev</I>[<I>x</I>]]<I> </I><img src="../images/arrlt12.gif"><I> next</I>[<I>x</I>]</sub></sup></pre><P>
<pre>2  <I>prev</I>[<I>next</I>[<I>x</I>]] <img src="../images/arrlt12.gif"> <I>prev</I>[<I>x</I>]</sub></sup></pre><P>
<a name="07b2_13ff">A <I><B>sentinel</I></B> is a dummy object that allows us to simplify boundary conditions. For example, suppose that we provide with list <I>L</I> an object <I>nil</I>[<I>L</I>] that represents <FONT FACE="Courier New" SIZE=2>NIL</FONT> but has all the fields of the other list elements. Wherever we have a reference to <FONT FACE="Courier New" SIZE=2>NIL</FONT> in list code, we replace it by a reference to the sentinel <I>nil</I>[<I>L</I>]. As shown in Figure 11.4, this turns a regular doubly linked list into a circular list, with the sentinel <I>nil</I>[<I>L</I>] placed between the head and tail; the field <I>next</I>[<I>nil</I>[<I>L</I>]] points to the head of the list, and <I>prev</I>[<I>nil</I>[<I>L</I>]] points to the tail. Similarly, both the <I>next</I> field of the tail and the <I>prev</I> field of the head point to <I>nil</I>[<I>L</I>]. Since <I>next</I>[<I>nil</I>[<I>L</I>]] points to the head, we can eliminate the attribute <I>head</I>[<I>L</I>] altogether, replacing references to it by references to <I>next</I>[<I>nil</I>[<I>L</I>]]. An empty list consists of just the sentinel, since both <I>next</I>[<I>nil</I>[<I>L</I>]] and <I>prev</I>[<I>nil</I>[<I>L</I>]] can be set to <I>nil</I>[<I>L</I>].<P>
The code for <FONT FACE="Courier New" SIZE=2>LIST</FONT>-<FONT FACE="Courier New" SIZE=2>SEARCH</FONT> remains the same as before, but with the references to <FONT FACE="Courier New" SIZE=2>NIL</FONT> and <I>head</I>[<I>L</I>] changed as specified above.<P>
<img src="207_a.gif"><P>
<h4><a name="07b2_1402">Figure 11.4 A linked list L that uses a sentinel nil[L] (heavily shaded) is the regular doubly linked list turned into a circular list with nil[L] appearing between the head and tail. The attribute head[L] is no longer needed, since we can access the head of the list by next[nil[L]]. (a) An empty list. (b) The linked list from Figure 11.3(<FONT FACE="Courier New" SIZE=2>a</FONT>), with key 9 at the head and key 1 at the tail. (c) The list after executing <FONT FACE="Courier New" SIZE=2>LIST<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT></FONT></FONT><FONT FACE="Times New Roman" SIZE=2>(L, x),</FONT> where, key[x] = 25. The new object becomes the head of the list. (d) The list after deleting the object with key 1. The new tail is the object with key 4.<a name="07b2_1402"></sub></sup></h4><P>
<pre><a name="07b2_1400">LIST-SEARCH'(<I>L</I>, <I>k</I>)</sub></sup></pre><P>
<pre>1  <I>x</I> <img src="../images/arrlt12.gif"> <I>next</I>[<I>nil</I>[<I>L</I>]]</sub></sup></pre><P>
<pre>2  <B>while</B> <I>x</I> <img src="../images/noteq.gif"> <I>nil</I>[<I>L</I>] and <I>key</I>[<I>x</I>] <img src="../images/noteq.gif"> <I>k</I></sub></sup></pre><P>
<pre>3      <B>do</B> <I>x</I> <img src="../images/arrlt12.gif"> <I>next</I>[<I>x</I>]</sub></sup></pre><P>
<pre>4  <B>return</B> <I>x</I></sub></sup></pre><P>
We use the two-line procedure <FONT FACE="Courier New" SIZE=2>LIST</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE'</FONT> to delete an element from the list. We use the following procedure to insert an element into the list.<P>
<pre><a name="07b2_1401">LIST-INSERT'(<I>L</I>, <I>x</I>)</sub></sup></pre><P>
<pre>1  <I>next</I>[<I>x</I>] <img src="../images/arrlt12.gif"> <I>next</I>[<I>nil</I>[<I>L</I>]]</sub></sup></pre><P>
<pre>2  <I>prev</I>[<I>next</I>[<I>nil</I>[<I>L</I>]]] <img src="../images/arrlt12.gif"> <I>x</I></sub></sup></pre><P>
<pre>3  <I>next</I>[<I>nil</I>[<I>L</I>]] <img src="../images/arrlt12.gif"> <I>x</I></sub></sup></pre><P>
<pre>4  <I>prev</I>[<I>x</I>] <img src="../images/arrlt12.gif"> <I>nil</I>[<I>L</I>]</sub></sup></pre><P>
Figure 11.4 shows the effects of <FONT FACE="Courier New" SIZE=2>LIST</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT'</FONT> and <FONT FACE="Courier New" SIZE=2>LIST</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE'</FONT> on a sample list.<P>
Sentinels rarely reduce the asymptotic time bounds of data structure operations, but they can reduce constant factors. The gain from using sentinels within loops is usually a matter of clarity of code rather than speed; the linked list code, for example, is simplified by the use of sentinels, but we save only <I>O</I>(1) time in the <FONT FACE="Courier New" SIZE=2>LIST</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT'</FONT> and <FONT FACE="Courier New" SIZE=2>LIST</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE'</FONT> procedures. In other situations, however, the use of sentinels helps to tighten the code in a loop, thus reducing the coefficient of, say, <I>n</I> or <I>n</I><SUP>2</SUP> in the running time.<P>
Sentinels should not be used indiscriminately. If there are many small lists, the extra storage used by their sentinels can represent significant wasted memory. In this book, we only use sentinels when they truly simplify the code.<P>
<P>







<h2><a name="07b3_1407">Exercises<a name="07b3_1407"></h2><P>
<a name="07b3_1408">11.2-1<a name="07b3_1408"><P>
<a name="07b3_1402">Can the dynamic-set operation <FONT FACE="Courier New" SIZE=2>INSERT</FONT> be implemented on a singly linked list in <I>O</I>(1) time? How about <FONT FACE="Courier New" SIZE=2>DELETE</FONT>?<P>
<a name="07b3_1409">11.2-2<a name="07b3_1409"><P>
<a name="07b3_1403">Implement a stack using a singly linked list <I>L</I>. The operations <FONT FACE="Courier New" SIZE=2>PUSH</FONT> and <FONT FACE="Courier New" SIZE=2>POP</FONT> should still take <I>O</I>(1) time.<P>
<a name="07b3_140a">11.2-3<a name="07b3_140a"><P>
<a name="07b3_1404">Implement a queue by a singly linked list <I>L</I>. The operations <FONT FACE="Courier New" SIZE=2>ENQUEUE</FONT> and <FONT FACE="Courier New" SIZE=2>DEQUEUE</FONT> should still take <I>O</I>(1) time.<P>
<a name="07b3_140b">11.2-4<a name="07b3_140b"><P>
Implement the dictionary operations <FONT FACE="Courier New" SIZE=2>INSERT</FONT>, <FONT FACE="Courier New" SIZE=2>DELETE</FONT>, and <FONT FACE="Courier New" SIZE=2>SEARCH</FONT> using singly linked, circular lists. What are the running times of your procedures?<P>
<a name="07b3_140c">11.2-5<a name="07b3_140c"><P>
The dynamic-set operation <FONT FACE="Courier New" SIZE=2>UNION</FONT> takes two disjoint sets <I>S</I><SUB>l</SUB> and <I>S</I><SUB>2</SUB> as input, and it returns a set <I>S</I> = <I>S</I><SUB>1</SUB> <img src="../images/wideu.gif"> <I>S<SUB>2</SUB> </I>consisting of all the elements of<I> S</I><SUB>1</SUB> and <I>S</I><SUB>2</SUB>. The sets <I>S</I><SUB>1</SUB> and <I>S</I><SUB>2</SUB> are usually destroyed by the operation. Show how to support <FONT FACE="Courier New" SIZE=2>UNION</FONT> in <I>O</I>(1) time using a suitable list data structure.<P>
<a name="07b3_140d">11.2-6<a name="07b3_140d"><P>
<a name="07b3_1405"><a name="07b3_1406">Write a procedure that merges two singly linked, sorted lists into one singly linked, sorted list without using sentinels. Then, write a similar procedure using a sentinel with key <img src="../images/infin.gif"> to mark the end of each list. Compare the simplicity of code for the two procedures.<P>
<a name="07b3_140e">11.2-7<a name="07b3_140e"><P>
Give a <img src="../images/bound.gif">(<I>n</I>)-time nonrecursive procedure that reverses a singly linked list of <I>n</I> elements. The procedure should use no more than constant storage beyond that needed for the list itself.<P>
<a name="07b3_140f">11.2-8<a name="07b3_140f"><P>
Explain how to implement doubly linked lists using only one pointer value <I>np</I>[<I>x</I>] per item instead of the usual two (<I>next</I> and <I>prev</I>). Assume that all index values can be interpreted as <I>k</I>-bit integers, and define <I>np</I>[<I>x</I>] to be <I>np</I>[<I>x</I>] = <I>next</I>[<I>x</I>] XOR <I>prev</I>[<I>x</I>], the <I>k</I>-bit "exclusive-or" of <I>next</I>[<I>x</I>] and <I>prev</I>[<I>x</I>]. (The value <FONT FACE="Courier New" SIZE=2>NIL</FONT> is represented by 0.) Be sure to describe what information is needed to access the head of the list. Show how to implement the <FONT FACE="Courier New" SIZE=2>SEARCH</FONT>, <FONT FACE="Courier New" SIZE=2>INSERT</FONT>, and <FONT FACE="Courier New" SIZE=2>DELETE</FONT> operations on such a list. Also show how to reverse such a list in <I>O</I>(1) time.<P>
<P>


<P>







<h1><a name="07b4_1409">11.3 Implementing pointers and objects<a name="07b4_1409"></h1><P>
<a name="07b4_1407"><a name="07b4_1408">How do we implement pointers and objects in languages, such as Fortran, that do not provide them? In this section, we shall see two ways of implementing linked data structures without an explicit pointer data type. We shall synthesize objects and pointers from arrays and array indices.<P>