📄 chap11.htm
字号:
<HTML><HEAD>
<TITLE>Intro to Algorithms: CHAPTER 11: ELEMENTARY DATA STRUCTURES</TITLE></HEAD><BODY BGCOLOR="#FFFFFF">
<a href="chap12.htm"><img align=right src="../../images/next.gif" alt="Next Chapter" border=0></A>
<a href="toc.htm"><img align=right src="../../images/toc.gif" alt="Return to Table of Contents" border=0></A>
<a href="partiii.htm"><img align=right src="../../images/prev.gif" alt="Previous Chapter" border=0></A>
<h1><a name="07a8_13ca">CHAPTER 11: ELEMENTARY DATA STRUCTURES<a name="07a8_13ca"></h1><P>
<a name="07a8_13c9">In this chapter, we examine the representation of dynamic sets by simple data structures that use pointers. Although many complex data structures can be fashioned using pointers, we present only the rudimentary ones: stacks, queues, linked lists, and rooted trees. We also discuss a method by which objects and pointers can be synthesized from arrays.<P>
<h1><a name="07aa_13d2">11.1 Stacks and queues<a name="07aa_13d2"></h1><P>
<a name="07aa_13ca"><a name="07aa_13cb"><a name="07aa_13cc"><a name="07aa_13cd"><a name="07aa_13ce"><a name="07aa_13cf"><a name="07aa_13d0"><a name="07aa_13d1">Stacks and queues are dynamic sets in which the element removed from the set by the <FONT FACE="Courier New" SIZE=2>DELETE</FONT> operation is prespecified. In a <I><B>stack</I></B>, the element deleted from the set is the one most recently inserted: the stack implements a <I><B>last-in, first-out</I></B>, or <I><B>LIFO</I></B>, policy. Similarly, in a <I><B>queue</I></B> , the element deleted is always the one that has been in the set for the longest time: the queue implements a <I><B>first-in, first-out</I></B>, or <I><B>FIFO</I></B>, policy. There are several efficient ways to implement stacks and queues on a computer. In this section we show how to use a simple array to implement each.<P>
<h2>Stacks</h2><P>
<a name="07ab_13d2"><a name="07ab_13d3"><a name="07ab_13d4">The <FONT FACE="Courier New" SIZE=2>INSERT</FONT> operation on a stack is often called <FONT FACE="Courier New" SIZE=2>PUSH</FONT>, and the <FONT FACE="Courier New" SIZE=2>DELETE</FONT> operation, which does not take an element argument, is often called <FONT FACE="Courier New" SIZE=2>POP</FONT>. These names are allusions to physical stacks, such as the spring-loaded stacks of plates used in cafeterias. The order in which plates are popped from the stack is the reverse of the order in which they were pushed onto the stack, since only the top plate is accessible.<P>
<a name="07ab_13d5">As shown in Figure 11.1, we can implement a stack of at most <I>n</I> elements with an array <I>S</I> [1..<I>n</I>]. The array has an attribute <I>top</I>[<I>S</I>] that indexes the most recently inserted element. The stack consists of elements <I>S</I>[1..<I>top</I>[<I>S</I>]], where <I>S</I>[1] is the element at the bottom of the stack and <I>S</I>[<I>top</I>[<I>S</I>]] is the element at the top.<P>
<a name="07ab_13d6"><a name="07ab_13d7"><a name="07ab_13d8">When <I>top</I> [<I>S</I>] = 0, the stack contains no elements and is <I><B>empty</I></B>. The stack can be tested for emptiness by the query operation <FONT FACE="Courier New" SIZE=2>STACK</FONT>-<FONT FACE="Courier New" SIZE=2>EMPTY</FONT>. If an empty stack is popped, we say the stack <I><B>underflows</I>,</B> which is normally an error. If <I>top</I>[<I>S</I>] exceeds <I>n</I>, the stack <I><B>overflows</I></B>. (In our pseudocode implementation, we don't worry about stack overflow.)<P>
<img src="201_a.gif"><P>
<h4><a name="07ab_13dc">Figure 11.1 An array implementation of a stack S. Stack elements appear only in the lightly shaded positions. (a) Stack S has 4 elements. The top element is 9. (b) Stack S after the calls <FONT FACE="Courier New" SIZE=2>PUSH<FONT FACE="Times New Roman" SIZE=2>(S, 17) and <FONT FACE="Courier New" SIZE=2>PUSH<FONT FACE="Times New Roman" SIZE=2>(S, 3). (c) Stack S after the call <FONT FACE="Courier New" SIZE=2>POP<FONT FACE="Times New Roman" SIZE=2>(S) has returned the element 3, which is the one most recently pushed. Although element 3 still appears in the array, it is no longer in the stack; the top is element 17.<a name="07ab_13dc"></FONT></FONT></FONT></FONT></FONT></FONT></sub></sup></h4><P>
The stack operations can each be implemented with a few lines of code.<P>
<pre><a name="07ab_13d9">STACK-EMPTY(<I>S</I>)</sub></sup></pre><P>
<pre>1 <B>if</B> <I>top</I> [<I>S</I>] = 0</sub></sup></pre><P>
<pre>2 <B>then return</B> TRUE</sub></sup></pre><P>
<pre>3 <B>else return</B> FALSE</sub></sup></pre><P>
<pre></sub></sup></pre><P>
<pre><a name="07ab_13da">PUSH(<I>S, x</I>)</sub></sup></pre><P>
<pre>1 <I>top</I>[<I>S</I>] <img src="../images/arrlt12.gif"> <I>top</I> [<I>S</I>] + 1</sub></sup></pre><P>
<pre>2 <I>S</I> [<I>top</I>[<I>S</I>]] <img src="../images/arrlt12.gif"> <I>x</I></sub></sup></pre><P>
<pre></sub></sup></pre><P>
<pre><a name="07ab_13db">POP(<I>S</I>)</sub></sup></pre><P>
<pre>1 <B>if</B> STACK-EMPTY(<I>S</I>)</sub></sup></pre><P>
<pre>2 <B>then error</B> "underflow"</sub></sup></pre><P>
<pre>3 <B>else</B> <I>top</I> [<I>S</I>] <img src="../images/arrlt12.gif"> <I>top</I> [<I>S</I>] - 1</sub></sup></pre><P>
<pre>4 <B>return</B> <I>S</I> [<I>top</I> [<I>S</I>] + 1]</sub></sup></pre><P>
Figure 11.1 shows the effects of the modifying operations <FONT FACE="Courier New" SIZE=2>PUSH</FONT> and <FONT FACE="Courier New" SIZE=2>POP</FONT>. Each of the three stack operations takes <I>O</I> (1) time.<P>
<P>
<h2>Queues</h2><P>
<a name="07ac_13dc"><a name="07ac_13dd"><a name="07ac_13de"><a name="07ac_13df"><a name="07ac_13e0">We call the <FONT FACE="Courier New" SIZE=2>INSERT</FONT> operation on a queue <FONT FACE="Courier New" SIZE=2>ENQUEUE</FONT>, and we call the D<FONT FACE="Courier New" SIZE=2>ELETE </FONT>operation <FONT FACE="Courier New" SIZE=2>DEQUEUE</FONT>; like the stack operation <FONT FACE="Courier New" SIZE=2>POP</FONT>, <FONT FACE="Courier New" SIZE=2>DEQUEUE</FONT> takes no element argument. The FIFO property of a queue causes it to operate like a line of people in the registrar's office. The queue has a <I><B>head</I></B> and a <I><B>tail</I></B>. When an element is enqueued, it takes its place at the tail of the queue, 1ike a newly arriving student takes a place at the end of the line. The element dequeued is always the one at the head of the queue, like the student at the head of the line who has waited the longest. (Fortunately, we don't have to worry about computational elements cutting into line.)<P>
<img src="202_a.gif"><P>
<h4><a name="07ac_13e4">Figure 11.2 A queue implemented using an array Q[1 . . 12]. Queue elements appear only in the lightly shaded positions. (a) The queue has 5 elements, in locations Q [7..11]. (b) The configuration of the queue after the calls <FONT FACE="Courier New" SIZE=2>ENQUEUE<FONT FACE="Times New Roman" SIZE=2>(Q, 17), <FONT FACE="Courier New" SIZE=2>ENQUEUE<FONT FACE="Times New Roman" SIZE=2>(Q, 3), and <FONT FACE="Courier New" SIZE=2>ENQUEUE<FONT FACE="Times New Roman" SIZE=2>(Q, 5). (c) The configuration of the queue after the call <FONT FACE="Courier New" SIZE=2>DEQUEUE<FONT FACE="Times New Roman" SIZE=2>(Q) returns the key value 15 formerly at the head of the queue. The new head has key 6.<a name="07ac_13e4"></FONT></FONT></FONT></FONT></FONT></FONT></FONT></FONT></sub></sup></h4><P>
Figure 11.2 shows one way to implement a queue of at most <I>n</I> - 1 elements using an array <I>Q</I> [1..<I>n</I>]. The queue has an attribute <I>head</I> [<I>Q</I>] that indexes, or points to, its head. The attribute <I>tail</I> [<I>Q</I>] indexes the next location at which a newly arriving element will be inserted into the queue. The elements in the queue are in locations <I>head</I>[<I>Q</I>], <I>head</I> [<I>Q</I>] + 1, . . . , <I>tail</I> [<I>Q</I>] - 1, where we "wrap around" in the sense that location 1 immediately follows location <I>n</I> in a circular order. When <I>head</I> [<I>Q</I>] = <I>tail</I> [<I>Q</I>], the queue is empty. Initially, we have <I>head</I> [<I>Q</I>] = <I>tail</I> [<I>Q</I>] = 1. When the queue is empty, an attempt to dequeue an element causes the queue to underflow. When <I>head</I> [<I>Q</I>] = <I>tail</I> [<I>Q</I>] + 1, the queue is full, and an attempt to enqueue an element causes the queue to overflow.<P>
<a name="07ac_13e1">In our procedures <FONT FACE="Courier New" SIZE=2>ENQUEUE</FONT> and <FONT FACE="Courier New" SIZE=2>DEQUEUE</FONT>, the error checking for underflow and overflow has been omitted. (Exercise 11.1-4 asks you to supply code that checks for these two error conditions.)<P>
<pre><a name="07ac_13e2">ENQUEUE(<I>Q, x</I>)</sub></sup></pre><P>
<pre>1 <I>Q</I> [<I>tail</I> [<I>Q</I>]] <img src="../images/arrlt12.gif"> <I>x</I></sub></sup></pre><P>
<pre>2 <B>if</B> <I>tail</I> [<I>Q</I>] = <I>length</I> [<I>Q</I>]</sub></sup></pre><P>
<pre>3 <B>then</B> <I>tail</I> [<I>Q</I>] <img src="../images/arrlt12.gif"> 1</sub></sup></pre><P>
<pre>4 <B>else</B> <I>tail</I> [<I>Q</I>] <img src="../images/arrlt12.gif"> <I>tail</I> [<I>Q</I>] + 1</sub></sup></pre><P>
<pre></sub></sup></pre><P>
<pre><a name="07ac_13e3">DEQUEUE(<I>Q</I>)</sub></sup></pre><P>
<pre>1 <I>x</I> <img src="../images/arrlt12.gif"> <I>Q</I> [<I>head</I> [<I>Q</I>]]</sub></sup></pre><P>
<pre>2 <B>if</B> <I>head</I> [<I>Q</I>] = <I>length</I> [<I>Q</I>]</sub></sup></pre><P>
<pre>3 <B>then</B> <I>head</I> [<I>Q</I>] <img src="../images/arrlt12.gif"> 1</sub></sup></pre><P>
<pre>4 <B>else</B> <I>head</I> [<I>Q</I>] <img src="../images/arrlt12.gif"> <I>head</I> [<I>Q</I>] + 1</sub></sup></pre><P>
<pre>5 <B>return</B> <I>x</I></sub></sup></pre><P>
Figure 11.2 shows the effects of the <FONT FACE="Courier New" SIZE=2>ENQUEUE</FONT> and <FONT FACE="Courier New" SIZE=2>DEQUEUE</FONT> operations. Each operation takes <I>O</I>(1) time.<P>
<P>
<h2><a name="07ad_13e9">Exercises<a name="07ad_13e9"></h2><P>
<a name="07ad_13ea">11.1-1<a name="07ad_13ea"><P>
Using Figure 11.1 as a model, illustrate the result of each of the operations <FONT FACE="Courier New" SIZE=2>PUSH</FONT>(<I>S</I>, 4), <FONT FACE="Courier New" SIZE=2>PUSH</FONT>(<I>S</I>, 1), <FONT FACE="Courier New" SIZE=2>PUSH</FONT>(<I>S</I>, 3), <FONT FACE="Courier New" SIZE=2>POP</FONT>(<I>S</I>), <FONT FACE="Courier New" SIZE=2>PUSH</FONT>(<I>S</I>, 8), and <FONT FACE="Courier New" SIZE=2>POP</FONT>(<I>S</I>) on an initially empty stack <I>S</I> stored in array <I>S</I> [1 . . 6].<P>
<a name="07ad_13eb">11.1-2<a name="07ad_13eb"><P>
Explain how to implement two stacks in one array <I>A</I> [1 . . <I>n</I>] in such a way that neither stack overflows unless the total number of elements in both stacks together is <I>n</I>. The <FONT FACE="Courier New" SIZE=2>PUSH</FONT> and <FONT FACE="Courier New" SIZE=2>POP</FONT> operations should run in <I>O</I>(1) time.<P>
<a name="07ad_13ec">11.1-3<a name="07ad_13ec"><P>
Using Figure 11.2 as a model, illustrate the result of each of the operations <FONT FACE="Courier New" SIZE=2>ENQUEUE</FONT>(<I>Q</I>, 4), <FONT FACE="Courier New" SIZE=2>ENQUEUE</FONT>(<I>Q</I>, 1), <FONT FACE="Courier New" SIZE=2>ENQUEUE</FONT>(<I>Q</I>, 3), <FONT FACE="Courier New" SIZE=2>DEQUEUE</FONT>(<I>Q</I>), <FONT FACE="Courier New" SIZE=2>ENQUEUE</FONT>(<I>Q</I>, 8), and <FONT FACE="Courier New" SIZE=2>DEQUEUE</FONT>(<I>Q</I>) on an initially empty queue <I>Q</I> stored in array <I>Q</I> [1 . . 6].<P>
<a name="07ad_13ed">11.1-4<a name="07ad_13ed"><P>
<a name="07ad_13e4"><a name="07ad_13e5">Rewrite <FONT FACE="Courier New" SIZE=2>ENQUEUE</FONT> and <FONT FACE="Courier New" SIZE=2>DEQUEUE</FONT> to detect underflow and overflow of a queue.<P>
<a name="07ad_13ee">11.1-5<a name="07ad_13ee"><P>
<a name="07ad_13e6"><a name="07ad_13e7"><a name="07ad_13e8">Whereas a stack allows insertion and deletion of elements at only one end, and a queue allows insertion at one end and deletion at the other end, a <I><B>deque</I></B> (double-ended queue) allows insertion and deletion at both ends. Write four <I>O</I>(1)-time procedures to insert elements into and delete elements from both ends of a deque constructed from an array.<P>
<a name="07ad_13ef">11.1-6<a name="07ad_13ef"><P>
Show how to implement a queue using two stacks. Analyze the running time of the queue operations.<P>
<a name="07ad_13f0">11.1-7<a name="07ad_13f0"><P>
Show how to implement a stack using two queues. Analyze the running time of the stack operations.<P>
<P>
<P>
<h1><a name="07ae_13f5">11.2 Linked lists<a name="07ae_13f5"></h1><P>
<a name="07ae_13e9"><a name="07ae_13ea"><a name="07ae_13eb">A <I><B>linked list</I></B> is a data structure in which the objects are arranged in a linear order. Unlike an array, though, in which the linear order is determined by the array indices, the order in a linked list is determined by a pointer in each object. Linked lists provide a simple, flexible representation for dynamic sets, supporting (though not necessarily efficiently) all the operations listed on page 198.<P>
<a name="07ae_13ec"><a name="07ae_13ed"><a name="07ae_13ee"><a name="07ae_13ef"><a name="07ae_13f0">As shown in Figure 11.3, each element of a <I><B>doubly linked list</I> </B><I><B><FONT FACE="Courier New" SIZE=2>L</I></B></FONT> is an object with a <I>key</I> field and two other pointer fields: <I>next</I> and <I>prev</I>. The object may also contain other satellite data. Given an element <I>x</I> in the list, <I>next</I> [<I>x</I>] points to its successor in the linked list, and <I>prev</I> [<I>x</I>] points to its predecessor. If <I>prev</I> [<I>x</I>] = <FONT FACE="Courier New" SIZE=2>NIL</FONT>, the element <I>x</I> has no predecessor and is therefore the first element, or <I><B>head</I></B>, of the list. If <I>next</I> [<I>x</I>] = <FONT FACE="Courier New" SIZE=2>NIL</FONT>, the element <I>x</I> has no successor and is therefore the last element, or <I><B>tail</I></B>, of the list. An attribute <I>head</I> [<I>L</I>] points to the first element of the list. If <I>head</I> [<I>L</I>] = <FONT FACE="Courier New" SIZE=2>NIL</FONT>, the list is empty.<P>
<a name="07ae_13f1"><a name="07ae_13f2"><a name="07ae_13f3"><a name="07ae_13f4">A list may have one of several forms. It may be either singly linked or doubly linked, it may be sorted or not, and it may be circular or not. If a list is <I><B>singly linked</I></B>, we omit the <I>prev</I> pointer in each element. If a list is <I><B>sorted</I></B>, the linear order of the list corresponds to the linear order of keys stored in elements of the list; the minimum element is the head of the list, and the maximum element is the tail. If the list is <I><B>unsorted</I></B>, the elements can appear in any order. In a <I><B>circular list</I></B>, the <I>prev</I> pointer of the head of the list points to the tail, and the <I>next</I> pointer of the tail of the list points to the head. The list may thus be viewed as a ring of elements. In the remainder of this section, we assume that the lists with which we are working are unsorted and doubly linked.<P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -