ch06.htm

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

<tt>6:   myChar,nextNode(0)</tt>
<tt>7:  {</tt>
<tt>8:  }</tt>
<tt>9:  </tt>
<tt>10:  Node::~Node()</tt>
<tt>11:  {</tt>
<tt>12:      if ( nextNode )</tt>
<tt>13:          delete nextNode;</tt>
<tt>14:  }</tt>
<tt>15:  </tt>
<tt>16:  </tt>
<tt>17:  void Node::Display() const</tt>
<tt>18:  {</tt>
<tt>19:      cout &lt;&lt; myChar;</tt>
<tt>20:      if ( nextNode )</tt>
<tt>21:          nextNode-&gt;Display();</tt>
<tt>22:  }</tt>
<tt>23:  </tt>
<tt>24:  </tt>
<tt>25:  int Node::HowMany(char theChar) const</tt>
<tt>26:  {</tt>
<tt>27:      int myCount = 0;</tt>
<tt>28:      if ( myChar == theChar )</tt>
<tt>29:          myCount++;</tt>
<tt>30:      if ( nextNode )</tt>
<tt>31:          return myCount + nextNode-&gt;HowMany(theChar);</tt>
<tt>32:      else</tt>
<tt>33:          return myCount;</tt>
<tt>34:  }</tt>
<tt>35:  </tt>
<tt>36:  void Node::Insert(char theChar)</tt>
<tt>37:  {</tt>
<tt>38:      if ( ! nextNode )</tt>
<tt>39:          nextNode = new Node(theChar);</tt>
<tt>40:      else</tt>
<tt>41:          nextNode-&gt;Insert(theChar);</tt>
<tt>42:  }</tt>
</pre>
<p>The constructor on line 5 receives a character and initializes its <tt>myChar</tt> 
  member variable on line 6. The constructor also initializes its <tt>nextNode</tt> 
  pointer to zero--that is, to null. When the <tt>Node</tt> is created, it points 
  to nothing further along in the list.</p>
<p>The destructor on line 10 tests the pointer on line 12, and if the pointer 
  is not <tt>NULL</tt>, the destructor deletes it. </p>
<blockquote>
  <hr>
  <p><strong>NOTE: </strong> The destructor takes advantage of the C++ idiom that 
    any nonzero value is considered <tt>true</tt>. Thus, if <tt>nextNode</tt> 
    is null, its value is <tt>0</tt> and, therefore, <tt>false</tt>, and the <tt>if</tt> 
    statement does not execute. If <tt>nextNode</tt> does point to another node, 
    its value is nonzero and thus <tt>true</tt>, and that object is deleted.</p>
  <hr>
</blockquote>
<p><tt>Display()</tt>, on line 17, prints the character that is held by the current 
  node on line 19, and then calls <tt>Display()</tt> on the <tt>nextNode</tt> 
  in the list, if any (on line 20). In this way, by telling the first node to 
  display itself, you cause every node in the list to display itself. <a name="_Toc445687417"></a></p>
<h2> <a name="Heading5">A Simple Driver Program</a></h2>
<p>On line 25, <tt>HowMany()</tt> takes a character and returns the number of 
  times that character exists in the list. The implementation of this is tricky 
  and instructive because this type of implementation is common in C++. Explaining 
  how this works in words is much less effective than tracing it in the debugger. 
  To do that, we need a driver program, shown in Listing 6.3.</p>
<h4> Listing 6.3 Driver Program</h4>
<pre>
<tt>0:  #include "DefinedValues.h"</tt>
<tt>1:  #include "List0601_Node.h"</tt>
<tt>2:  </tt>
<tt>3:  int main()</tt>
<tt>4:  {</tt>
<tt>5:      Node head('a');</tt>
<tt>6:      head.Insert('b');</tt>
<tt>7:      int count = head.HowMany('a');</tt>
<tt>8:      cout &lt;&lt; "There are " &lt;&lt; count &lt;&lt; " instances of a\n";</tt>
<tt>9:      count = head.HowMany('b');</tt>
<tt>10:      cout &lt;&lt; "There are " &lt;&lt; count &lt;&lt; " instances of b\n";</tt>
<tt>11:      cout &lt;&lt; "\n\nHere's the entire list: ";</tt>
<tt>12:      head.Display();</tt>
<tt>13:      cout &lt;&lt; endl;</tt>
<tt>14:  </tt>
<tt>15:      return 0;</tt>
<tt>16:  }</tt>
<tt>There are 1 instances of a</tt>
<tt>There are 1 instances of b</tt>
<tt>Here's the entire list: ab</tt>
</pre>
<p>Before we examine <tt>HowMany</tt>, let's look at the driver. Its job is to 
  generate two letters and add them to the list. To do this, it creates a first 
  node, called the <tt><i>head</i></tt><i> node</i>, on line 5, and initializes 
  it with the value <tt>'a'</tt>. It then tells the <tt>head</tt> node to insert 
  one more letter (<tt>'b'</tt>), starting on line 6.</p>
<p>Our linked list now looks like Figure 6.3.</p>
<p><b>Figure 6.3 </b><i>With two nodes.</i></p>
<p>On line 0 we <tt>#include</tt> DefinedValues.h, shown in Listing 6.4.</p>
<h4> Listing 6.4 DefinedValues.h</h4>
<pre>
<tt>1:    #ifndef DEFINED</tt>
<tt>2:    #define DEFINED</tt>
<tt>3:    </tt>
<tt>4:    #include &lt;iostream&gt;</tt>
<tt>5:    #include &lt;vector&gt;</tt>
<tt>6:    #include &lt;iterator&gt;</tt>
<tt>7:    #include &lt;algorithm&gt;</tt>
<tt>8:    #include &lt;time.h&gt;</tt>
<tt>9:    #include &lt;utility&gt;</tt>
<tt>10:    </tt>
<tt>11:    using namespace std;</tt>
<tt>12:    </tt>
<tt>13:    const char alpha[27] = "abcdefghijklmnopqrstuvwxyz";</tt>
<tt>14:    </tt>
<tt>15:    const int minPos = 2;</tt>
<tt>16:    const int maxPos = 10;</tt>
<tt>17:    const int minLetters = 2;</tt>
<tt>18:    const int maxLetters = 26;</tt>
<tt>19:    const int SecondsInMinute = 60;</tt>
<tt>20:    const int SecondsInHour = SecondsInMinute * 60;</tt>
<tt>21:    const int SecondsInDay = SecondsInHour * 24;</tt>
<tt>22:    const int GUESSES_PER_SECOND = 10000;</tt>
<tt>23:    </tt>
<tt>24:    const int szInt =  sizeof(int);</tt>
<tt>25:    const int szChar = sizeof(char);</tt>
<tt>26:    const int szBool = sizeof(bool);</tt>
<tt>27:    </tt>
<tt>28:    #endif</tt>
</pre>
<p>This file serves to include the necessary STL header files, and also to define 
  constants we'll need in this program. We will use this same defineValues file 
  throughout all the sample code for the rest of the book.</p>
<p>Let's not examine how <tt>Insert()</tt> works just yet, but rather assume that 
  the letter <i>b</i> is in fact inserted into the list. We'll return to how this 
  works in just a moment, but let's first focus on <tt>HowMany()</tt> works. <a name="_Toc445687418"></a></p>
<h2> <a name="Heading6">The HowMany() Method</a></h2>
<p>On line 7 we ask how many instances of <tt>'a'</tt> there are, and on line 
  9 we ask the same about how many instances of <tt>'b'</tt> there are. Let's 
  walk through the call to <tt>howMany</tt> on line 9. Put a break point on this 
  line, and run the program to the break point.</p>
<p>The program runs as expected and stops at the following line:</p>
<pre>
<tt>     count = head.HowMany('b');</tt>
</pre>
<p>Stepping into this line of code brings you to the top of <tt>HowMany()</tt>:</p>
<pre>
<tt>int Node::HowMany(char theChar) const</tt>
<tt>{</tt>
</pre>
<p>Let's step line by line. The first step initializes <tt>myCount</tt> to <tt>0</tt>, 
  which you can probably see in the local variables window of your debugger.</p>
<p>Which node are we looking at? We'll be entering the <tt>HowMany()</tt> method 
  once for each node. How can we tell where we are? Remember that every nonstatic 
  member method has a pointer called the <tt>this</tt> pointer, which holds the 
  address of the object itself. </p>
<p>You can examine the value of the <tt>this</tt> pointer in your debugger. Take 
  note of the address of the <tt>this</tt><i> </i>pointer<i> </i>while you are 
  here in <tt>HowMany()</tt><i>. </i>On my machine, it is <tt>0x0012ff6c</tt>, 
  but yours might be different. The particular value doesn't matter--just write 
  down whatever you have. This is the address of the node we're examining.</p>
<p>Step to the next line, where <tt>myChar</tt> is compared with <tt>theChar</tt>. 
  Examine the <tt>myChar</tt> member variable (<tt>'a'</tt>) and the local variable 
  <tt>theChar</tt> (<tt>'b'</tt>), again in your local variables window.</p>
<blockquote>
  <hr>
  <p><strong>NOTE: </strong> You might need to expand your <tt>this</tt> pointer 
    to see the member variables, or you might need to click on a different debugger 
    window to find them.</p>
  <hr>
</blockquote>
<p>Clearly, these values are not the same, so the <tt>if</tt> statement fails. 
  <tt>myCount</tt> remains at <tt>0</tt>.</p>
<p>Step again to the next <tt>if</tt> statement. The <tt>nextNode</tt> pointer 
  should be nonzero. On my machine, it is <tt>0x004800a0</tt>. Your value will 
  differ; again, although the absolute value doesn't matter, write down whatever 
  you get.</p>
<p>Because <tt>nextNode</tt> is nonzero, the <tt>if</tt> statement evaluates <tt>true</tt>, 
  and you step to the following line:</p>
<pre>
<tt>          return myCount + nextNode-&gt;HowMany(theChar);</tt>
</pre>
<p>What do you expect to happen if you step <i>into</i> this line? The first thing 
  to be evaluated is </p>
<pre>
<tt>nextNode-&gt;HowMany(theChar);</tt>
</pre>
<p>This calls the <tt>howMany()</tt> method through the <tt>nextNode</tt> pointer. 
  This, in fact, calls <tt>howMany()</tt> on the object to which <tt>nextNode</tt> 
  points. Remember that <tt>nextNode</tt> had a value, the address of the next 
  node in the list. Let's step in.</p>
<p>The debugger appears to go to the top of the same method. Where are we? Examine 
  the <tt>this</tt><i> </i>pointer in your debugging window (you might first have 
  to step to the first line of the method). On my machine, the <tt>this</tt> pointer 
  has changed to <tt>0x004800a0</tt>, which was exactly the value previously held 
  in the <tt>nextNode</tt> pointer. Aha! We're now in the second node in the list. 
  We can imagine that our list looks like Figure 6.4.</p>
<p><b>Figure 6.4 </b><i>Nodes with addresses.</i></p>
<p>We are running <tt>HowMany</tt> in the <i>second</i> node. Once again, <tt>HowMany()</tt> 
  begins by initializing the local variable <tt>myCount</tt>, on line 27, to <tt>0</tt>. 
  Be careful here, the <tt>myCount</tt> we're looking at now is local to this 
  iteration of <tt>HowMany()</tt>. The <tt>myCount</tt> back in the first node 
  has its own local value.</p>
<p><tt>HowMany()</tt> then tests the character that is passed in against the character 
  it is storing on line 28; if they match, it increments the counter. In this 
  case, they do match, so we compare <tt>myChar</tt> (<tt>'b'</tt>) with <tt>theChar</tt> 
  (also <tt>'b'</tt>). They match, so <tt>myCount</tt> is incremented. </p>
<p>Stepping again brings us to the next <tt>if</tt> statement:</p>
<pre>
<tt>30:     if ( nextNode )</tt>
</pre>
<p>This time <tt>nextNode</tt> is <tt>NULL</tt> (you should see all zeros in its 
  value in your local variables window). As expected, the second node's <tt>nextNode</tt> 
  points to <tt>NULL</tt>. The <tt>if</tt> statement fails and the <tt>else</tt> 
  statement executes, returning <tt>myCount</tt>, which has the value <tt>1</tt>. 
</p>
<p>We step into this line and appear to be right back at the <tt>return</tt> statement. 
  Examine the <tt>this</tt> pointer, however, and you'll find that we're back 
  in the first node. The value that is returned (<tt>1</tt>) is added to the value 
  in <tt>myCounter</tt> (now <tt>0</tt>), and it is this combined value that is 
  returned to the calling function, <tt>main()</tt>. </p>
<p>As an exercise, try revising <tt>main()</tt> to insert the values <tt>a</tt>, 
  <tt>b</tt>, <tt>c</tt>, <tt>b</tt>, and <tt>b</tt>. This produces the linked 
  list that is shown in Figure 6.5. Make sure you understand why <tt>HowMany()</tt> 
  returns the value <tt>3</tt> when passed in <tt>'b'</tt>.</p>
<p><b>Figure 6.5</b><tt><b> </b></tt><i>Linked list with <tt>abcbb</tt>. <a name="_Toc445687419"></a></i></p>
<h2> <a name="Heading7">Insert() in Detail</a></h2>
<p>Now is the time to examine the implementation of <tt>Insert()</tt>, as shown 
  on line 36 in Listing 6.2 and reproduced here for your convenience:</p>
<pre>
<tt>36:  void Node::Insert(char theChar)</tt>
<tt>37:  {</tt>
<tt>38:      if ( ! nextNode )</tt>
<tt>39:          nextNode = new Node(theChar);</tt>
<tt>40:      else</tt>
<tt>41:          nextNode-&gt;Insert(theChar);</tt>
<tt>42:  }</tt>
</pre>
<p>The goal of this method is to insert a new character (<tt>theChar</tt>) into 
  the list. </p>
<p>Note that on line 39 we use the keyword <tt>new</tt> to create a new <tt>Node</tt> 
  object. This is explained in full in just a few pages; for now, all you need 
  to know is that this creates a new object of type <tt>Node</tt>.</p>
<p>Let's start over, creating the linked list from Figure 6.5, using the code 
  shown in Listing 6.5.</p>
<h4> Listing 6.5 Decryptix Driver Program</h4>
<pre>
<tt>0:  #include "DefinedValues.h"</tt>
<tt>1:  #include "List0601_Node.h"</tt>
<tt>2:  </tt>
<tt>3:  int main()</tt>
<tt>4:  {</tt>
<tt>5:      Node head('a');</tt>
<tt>6:      head.Insert('b');</tt>
<tt>7:      head.Insert('c');</tt>
<tt>8:      head.Insert('b');</tt>
<tt>9:      head.Insert('b');</tt>
<tt>10:      int count = head.HowMany('a');</tt>
<tt>11:      cout &lt;&lt; "There are " &lt;&lt; count &lt;&lt; " instances of a\n";</tt>
<tt>12:      count = head.HowMany('b');</tt>
<tt>13:      cout &lt;&lt; "There are " &lt;&lt; count &lt;&lt; " instances of b\n";</tt>
<tt>14:      cout &lt;&lt; "\n\nHere's the entire list: ";</tt>
<tt>15:      head.Display();</tt>
<tt>16:      cout &lt;&lt; endl;</tt>
<tt>17:      </tt>
<tt>18:      return 0;</tt>
<tt>19:  }</tt>
<tt>There are 1 instances of a</tt>
<tt>There are 3 instances of b</tt>
<tt>Here's the entire list: abcbb</tt>
</pre>
<p>On line 5 we create the first <tt>Node</tt> object, which we call <tt>head</tt>.