ch06.htm

C++ From Scratch: An Object-Oriented Approach is designed to walk novice programmers through the ana

<tt>16:    #include "List0603a_Node.h"</tt>
<tt>17:    </tt>
<tt>18:    Node::Node(char theChar):</tt>
<tt>19:    myChar(theChar),nextNode(0)</tt>
<tt>20:    {</tt>
<tt>21:        cout &lt;&lt; "In constructor of Node(" &lt;&lt; this &lt;&lt; ")\n";</tt>
<tt>22:    }</tt>
<tt>23:    </tt>
<tt>24:    Node::~Node()</tt>
<tt>25:    {</tt>
<tt>26:        cout &lt;&lt; "In destructor of Node(" &lt;&lt; this &lt;&lt; ")\n";;</tt>
<tt>27:        if ( nextNode )</tt>
<tt>28:            delete nextNode;</tt>
<tt>29:    }</tt>
<tt>30:    </tt>
<tt>31:    </tt>
<tt>32:    void Node::Display() const</tt>
<tt>33:    {</tt>
<tt>34:        cout &lt;&lt; this &lt;&lt; ": " &lt;&lt; myChar &lt;&lt; endl;</tt>
<tt>35:        if ( nextNode )</tt>
<tt>36:            nextNode-&gt;Display();</tt>
<tt>37:    }</tt>
<tt>38:    </tt>
<tt>39:    </tt>
<tt>40:    int Node::HowMany(char theChar) const</tt>
<tt>41:    {</tt>
<tt>42:        int myCount = 0;</tt>
<tt>43:        if ( myChar == theChar)</tt>
<tt>44:            myCount++;</tt>
<tt>45:        if ( nextNode )</tt>
<tt>46:            return myCount + nextNode-&gt;HowMany(theChar);</tt>
<tt>47:        else</tt>
<tt>48:            return myCount;</tt>
<tt>49:    }</tt>
<tt>50:    </tt>
<tt>51:    void Node::Insert(char theChar)</tt>
<tt>52:    {</tt>
<tt>53:        if ( ! nextNode )</tt>
<tt>54:            nextNode = new Node(theChar);</tt>
<tt>55:        else</tt>
<tt>56:            nextNode-&gt;Insert(theChar);</tt>
<tt>57:    }</tt>
</pre>
<h4> Listing 6.7c Driver.cpp</h4>
<pre>
<tt>58:    #include &lt;iostream.h&gt;</tt>
<tt>59:    #include "List0603a_Node.h"</tt>
<tt>60:    </tt>
<tt>61:    int main()</tt>
<tt>62:    {</tt>
<tt>63:        Node * pHead = new Node('a');</tt>
<tt>64:        pHead-&gt;Insert('b');</tt>
<tt>65:        pHead-&gt;Insert('c');</tt>
<tt>66:        pHead-&gt;Insert('b');</tt>
<tt>67:        pHead-&gt;Insert('b');</tt>
<tt>68:        int count = pHead-&gt;HowMany('a');</tt>
<tt>69:        cout &lt;&lt; "There are " &lt;&lt; count &lt;&lt; " instances of a\n";</tt>
<tt>70:        count = pHead-&gt;HowMany('b');</tt>
<tt>71:        cout &lt;&lt; "There are " &lt;&lt; count &lt;&lt; " instances of b\n";</tt>
<tt>72:        count = pHead-&gt;HowMany('c');</tt>
<tt>73:        cout &lt;&lt; "There are " &lt;&lt; count &lt;&lt; " instances of c\n";</tt>
<tt>74:        cout &lt;&lt; "\n\nHere's the entire list:\n";</tt>
<tt>75:        pHead-&gt;Display();</tt>
<tt>76:        cout &lt;&lt; "Deleting pHead..." &lt;&lt; endl;</tt>
<tt>77:        delete pHead;</tt>
<tt>78:        cout &lt;&lt; "Exiting main()..." &lt;&lt; endl;</tt>
<tt>79:        return 0;</tt>
<tt>80:    }</tt>
<tt>81:    In constructor of Node(0x00430060)</tt>
<tt>82:    In constructor of Node(0x00431DB0)</tt>
<tt>83:    In constructor of Node(0x00431D70)</tt>
<tt>84:    In constructor of Node(0x00431D30)</tt>
<tt>85:    In constructor of Node(0x00431CF0)</tt>
<tt>86:    There are 1 instances of a</tt>
<tt>87:    There are 3 instances of b</tt>
<tt>88:    There are 1 instances of c</tt>
<tt>89:    </tt>
<tt>90:    </tt>
<tt>91:    Here's the entire list:</tt>
<tt>92:    0x00430060: a</tt>
<tt>93:    0x00431DB0: b</tt>
<tt>94:    0x00431D70: c</tt>
<tt>95:    0x00431D30: b</tt>
<tt>96:    0x00431CF0: b</tt>
<tt>97:    Deleting pHead...</tt>
<tt>98:    In destructor of Node(0x00430060)</tt>
<tt>99:    In destructor of Node(0x00431DB0)</tt>
<tt>100:    In destructor of Node(0x00431D70)</tt>
<tt>101:    In destructor of Node(0x00431D30)</tt>
<tt>102:    In destructor of Node(0x00431CF0)</tt>
<tt>103:    Exiting main()...</tt>
</pre>
<p>The best way to follow the progress of this code is to put the code in the 
  debugger and set a break point in <tt>main()</tt> at line 63. Run the program 
  to the break point and note that we are going to create a new node and initialize 
  it to hold the letter <tt>'a'</tt>. The address of this new node is stashed 
  away in the <tt>Node</tt> pointer <tt>pHead</tt>. Now, step in at line 63. You 
  might step into the <tt>new</tt> operator. If so, just step back out and step 
  in again, which brings you to the constructor for <tt>Node</tt> on line 18. 
</p>
<p>Sure enough, the character <tt>'a'</tt> was passed in (now designated <tt>theChar</tt>), 
  and this character is used to initialize the member variable <tt>myChar</tt>. 
  The node's second member variable, <tt>nextNode</tt>, which is a pointer to 
  a <tt>Node</tt> object, is also initialized with the value <tt>0</tt> or <tt>NULL</tt>. 
  Finally, as you step through the constructor, a message is printed on line 21, 
  the effect of which is shown on line 81. </p>
<p>Notice that the <tt>this</tt> pointer is not dereferenced, so its actual value 
  is printed: That is, the address of the <tt>Node</tt> object on the heap whose 
  constructor we are now discussing. </p>
<p>If you continue stepping, you'll return from the constructor back to <tt>main()</tt> 
  on line 64, where we intend to call the <tt>Insert()</tt> method on that <tt>Node</tt>. 
  We do so indirectly, using the pointer that holds its address, and we pass <tt>'b'</tt> 
  to the <tt>Insert</tt> method in the hope that a new <tt>Node</tt> will be created 
  and appended to the list to hold this new value. </p>
<p>Step in at on line 30 and you enter the <tt>Insert()</tt> method of <tt>Node</tt> 
  on line 51, where the parameter <tt>theChar</tt> holds the value <tt>'b'</tt>. 
  On line 53 you test the <tt>Node</tt>'s <tt>nextNode</tt> pointer, which is 
  <tt>NULL</tt> (or <tt>0</tt>), the value to which you initialized it just a 
  moment ago. The <tt>if</tt> statement returns <tt>true</tt>. Take a moment and 
  reflect on why.</p>
<p>If a pointer has a nonzero value, it evaluates <tt>true</tt>. With a <tt>0</tt> 
  value, it evaluates <tt>false</tt>. Thus, asking if a pointer is false is the 
  same as asking if it is null.</p>
<p>The <tt>not</tt> operator turns false to true. Thus, <tt>(! nextNode)</tt> 
  will evaluate <tt>true</tt> if <tt>nextNode</tt> is zero (<tt>false</tt>). Thus 
</p>
<pre>
<tt>if ( ! nextNode )</tt>
</pre>
<p>will evaluate <tt>true</tt> and the <tt>if</tt> statement will execute as long 
  as <tt>nextNode</tt> points only to <tt>NULL</tt> (zero). </p>
<p>To most programmers, this is so idiomatic that </p>
<pre>
<tt>if ( ! nextNode )</tt>
</pre>
<p>really means <tt>"if nextNode</tt> doesn't yet point to anything..." and we 
  don't much think through all the convoluted logic that makes that work.</p>
<p>In any case, the <tt>if</tt> statement executes by calling <tt>newNode</tt>, 
  passing in <tt>theChar</tt>, and assigning the address that results to <tt>nextNode</tt>. 
  Calling <tt>new</tt> immediately invokes the constructor, so stepping into this 
  line brings us to the <tt>Node</tt> constructor on line 18. Once again, a message 
  is printed on line 82), and we return from the constructor, assigning the address 
  that is returned from <tt>new</tt> to the <tt>nextNode</tt> pointer of the first 
  node. </p>
<p>Before leaving <tt>Insert</tt>, let's examine the <tt>this</tt><i> </i>and 
  the <tt>nextNode</tt> pointers. You should find that <tt>this</tt> has an address 
  that is equal to the first address printed because we are now back in that first 
  node. You should find that the <tt>nextNode</tt> pointer has the address of 
  the object we just created. Sure enough, we now have a linked list with two 
  objects in it.</p>
<p>Continuing causes us to return from <tt>Insert()</tt> back to <tt>main()</tt>, 
  where the same logic is repeated to insert <tt>'c'</tt>, <tt>'b'</tt>, and once 
  again <tt>'b'</tt>.</p>
<p>If you don't want to work your way through the logic repeatedly, continue to 
  step over these lines until you reach line 70. We are now ready to determine 
  how many instances of <tt>'b'</tt> exist in the program. </p>
<p>Step into this line of code. This takes you into <tt>Node::HowMany() on line 
  40</tt>, in which the parameter <tt>theChar</tt> has the value <tt>'b'</tt>. 
  On line 42 we'll initialize <tt>myCount</tt> to <tt>0</tt>. On line 43 we test 
  <tt>myChar</tt>, which has the value <tt>'a'</tt>, against <tt>theChar</tt>, 
  which has the value <tt>'b'</tt>. This test fails, so we fall through to line 
  45, where we test to see whether <tt>nextNode</tt> is nonzero; it is. This causes 
  us to execute the body of the <tt>if</tt> statement:</p>
<pre>
<tt>          return myCount + nextNode-&gt;HowMany(theChar);</tt>
</pre>
<p>Step into this line. You find yourself in <tt>HowMany()</tt> for the second 
  node. Continue stepping. <tt>myChar</tt> is <tt>'b'</tt> this time, and it thus 
  matches <tt>theChar</tt>. We increment <tt>myCount</tt> and test <tt>nextNode</tt>. 
  Again it is nonzero, so again we step in, this time to the third node in the 
  list.</p>
<p>In the third node, <tt>myChar</tt> is <tt>'c'</tt>, so it does not match <tt>myChar</tt>; 
  but <tt>nextNode</tt> is nonzero, so we step into the fourth node.</p>
<p>In the fourth node, <tt>mychar</tt> is <tt>'b'</tt>, and we increment <tt>myCount</tt> 
  to <tt>1</tt>. Why is it set to <tt>1</tt> and not to <tt>2</tt>, given that 
  this is the second node with <tt>'b'</tt>? The answer is that <tt>myCount</tt> 
  is local to this invocation of <tt>HowMany()</tt> and therefore can't know about 
  the previous values. Again, <tt>nextNode</tt> is nonzero, so we now step into 
  the fifth node.</p>
<p>Take a look at the <tt>this</tt> pointer and expand it in your local variables 
  window. You are now looking at the local member variables for the fifth node 
  object. <tt>myChar</tt> is <tt>'b'</tt>, and <tt>nextPointer</tt> is <tt>0</tt>. 
  Thus, we increment <tt>myCount</tt>; then the test for <tt>nextPointer</tt> 
  fails, so we return <tt>myCount</tt>. </p>
<p>We thus return the value <tt>1</tt> to the call from the fourth node. This 
  value is added to the <tt>myCount</tt> variable (also <tt>1</tt>), summing to 
  <tt>2</tt>, and this value is now returned to the third node. The third node's 
  <tt>myCount</tt> is <tt>0</tt>, so the value <tt>2</tt> is now returned to the 
  second node. Its <tt>myCount</tt> variable is <tt>1</tt>, so <tt>3</tt> is returned 
  to the first node. The first node's <tt>myCount</tt> is <tt>0</tt>, so <tt>3</tt> 
  is returned to <tt>main()</tt>.</p>
<p>It is very important that you understand how this was accomplished. You might 
  find that using pencil and paper and drawing a picture (see Figure 6.9) makes 
  this easier to understand. </p>
<p><b>Figure 6.9 </b><i>Walking the list to get the answer.</i></p>
<p>As you continue to step out of the function calls, you'll find yourself popping 
  up through the calls to <tt>HowMany()</tt>, unwinding your way from Node 5 to 
  4, 3, 2, and back to Node 1. Step into and out of this set of calls repeatedly 
  until you can match what is happening in your debugger to the diagram in Figure 
  6.9.</p>
<p>When this is comfortable, continue stepping over code lines until you get to 
  the call to <tt>Display</tt> on line 74. Here you are calling <tt>Display()</tt> 
  on <tt>pHead</tt>. Step into this method call and you'll be in <tt>Display()</tt> 
  for your first node on line 32. Step into the method and note the address of 
  the <tt>this</tt> pointer, which confirms that you are in the first <tt>Node</tt> 
  in the list. <tt>myChar</tt> is printed on line 34 (printing <tt>'a'</tt>), 
  and the <tt>nextNode</tt> pointer is checked on line 45. It returns <tt>true</tt>, 
  so <tt>Display()</tt> is called on the second node in the list.</p>
<p>Step into this call, and you are back at line 32. Step in and notice that the 
  <tt>this</tt> pointer now reflects the address of the second node, as you'd 
  expect. On line 34, the member variable <tt>myChar</tt> is printed (<tt>'b'</tt>), 
  and once again we call <tt>Display()</tt>, this time on the third node. </p>
<p>This continues until the fifth node prints its value. Because the fifth node 
  does not point to another node, the <tt>if</tt> statement fails, and we return 
  through the various <tt>Display()</tt> method invocations, back to <tt>main()</tt>. 
</p>
<p>On line 77 we call <tt>delete</tt> on <tt>pHead</tt>. To see what this does, 
  place a break point on line 24 and go until the break point. You find yourself 
  in the destructor of the head node. On line 26 we print the address of the first 
  (head) node, and then on line 27 we test <tt>nextNode</tt>, which points to 
  the second node. We delete that object, causing us to come to the destructor 
  for the second node, where the logic is repeated. The second node deletes the 
  third node, the third Node deletes the fourth Node, and the fourth node deletes 
  the fifth.</p>
<p>The client of the linked list, in this case <tt>main()</tt>, never had to call 
  <tt>HowMany()</tt> or <tt>Display()</tt> on any node except the head node, and 
  it doesn't have to delete any node except the head node. The maintenance of 
  the list is managed by the list itself. Commands such as <tt>Display()</tt> 
  or <tt>delete</tt> are passed along the list as required, each node falling 
  like a domino into the next in the list. <a name="_Toc445687425"></a></p>
<h2> <a name="Heading12">Using Our Simple Linked List in Decryptix! </a></h2>
<p>We are just about ready to change the type of the member variable <tt>solution</tt> 
  in the <tt>Game</tt> class. Until now, it has been an array; we want it to be 
  a linked list.</p>
<p>Let's examine all the places we use <tt>Solution</tt> to see what our linked 
  list must be able to accomplish, and whether our list of Nodes is up to the 
  task.</p>
<p>Following are the lines in <tt>Game</tt> in which we refer to the solution:</p>
<pre>
<tt>                  theGame.Display(theGame.GetSolution());</tt>
<tt>                  int howManyInAnswer = howMany (solution, alpha[i]);</tt>
<tt>                  if ( thisGuess[i] == solution[i] )</tt>
</pre>
<p>That is, we must have the capability to retrieve the solution and display it, 
  count the instances of a particular character in the solution, and retrieve 
  the character at a given offset. </p>
<p>Rather than expose the workings of the <tt>Node</tt> object to the <tt>Game</tt>, 
  I've chosen to create a small class that will serve as an interface to the nodes, 
  which I'll call <tt>LinkedList</tt>. Listing 6.8 shows the declaration of the 
  <tt>LinkedList</tt> class.</p>
<h4> Listing 6.8 LinkedList Declared</h4>
<pre>
<tt>1:  </tt>
<tt>2:  class LinkedList</tt>
<tt>3:  {</tt>
<tt>4:  public:</tt>
<tt>5:      LinkedList();</tt>
<tt>6:      ~LinkedList();</tt>
<tt>7:      bool    Add            (char c, bool dupes = true);</tt>
<tt>8:      void    Display        ()        const;</tt>
<tt>9:      int        HowMany        (char c)    const;</tt>
<tt>10:      char    operator[]    (int offset);</tt>
<tt>11: private:</tt>
<tt>12:      Node *    headNode;</tt>
<tt>13:  };</tt>
</pre>
<p>To the client (in this case, <tt>Game</tt>), <tt>LinkedList</tt> <i>is</i>