📄 ch06.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN"><HTML><HEAD><SCRIPT LANGUAGE="JavaScript"><!--function popUp(pPage) { var fullURL = document.location; var textURL = fullURL.toString(); var URLlen = textURL.length; var lenMinusPage = textURL.lastIndexOf("/"); lenMinusPage += 1; var fullPath = textURL.substring(0,lenMinusPage); popUpWin = window.open('','popWin','resizable=yes,scrollbars=no,width=525,height=394'); figDoc= popUpWin.document; zhtm= '<HTML><HEAD><TITLE>' + pPage + '</TITLE>'; zhtm += '</head>'; zhtm += '<BODY bgcolor="#FFFFFF">'; zhtm += '<IMG SRC="' + fullPath + pPage + '">'; zhtm += '<P><B>' + pPage + '</B>'; zhtm += '</BODY></HTML>'; window.popUpWin.document.write(zhtm); window.popUpWin.document.close(); // Johnny Jackson 4/28/98 }//--> </SCRIPT> <META NAME="Author" Content="Steph Mineart"> <META HTTP-EQUIV="Content-Type" CONTENT="text/html;CHARSET=iso-8859-1"> <TITLE>C++ From Scratch -- Ch 6 -- Using Linked Lists</TITLE><link rel="stylesheet" href="/includes/stylesheets/ebooks.css"></head><BODY TEXT="#000000" BGCOLOR="#FFFFFF"><CENTER><H1><IMG SRC="../button/que.gif" WIDTH="171" HEIGHT="66" ALIGN="BOTTOM" BORDER="0"><BR>C++ From Scratch</H1></CENTER><CENTER> <P><A HREF="../index.htm"><IMG SRC="../button/contents.gif" WIDTH="128"HEIGHT="28" ALIGN="BOTTOM" ALT="Contents" BORDER="0"></A> <HR></CENTER><H1 align="center"> 6</H1><H1 align="center"> Using Linked Lists</H1><ul> <li><a href="#Heading1">Dynamic Data Structures</a> <ul> <li><a href="#Heading2">The Standard Template Library</a> </ul> <li><a href="#Heading3">Linked Lists</a> <ul> <li><a href="#Heading4">Understanding Linked Lists</a> </ul> <li><a href="#Heading5">A Simple Driver Program</a> <li><a href="#Heading6">The HowMany() Method</a> <li><a href="#Heading7">Insert() in Detail</a> <li><a href="#Heading8">Excursion: Understanding the Stack</a> <li><a href="#Heading9">The Stack and Functions</a> <li><a href="#Heading10">Using new</a> <ul> <li><a href="#Heading11">new and delete</a> </ul> <li><a href="#Heading12">Using Our Simple Linked List in Decryptix! </a> <li><a href="#Heading13">Run it!</a> <li><a href="#Heading14">Playing the Game</a> <li><a href="#Heading15">Solving the Problem with a Member Method</a> <li><a href="#Heading16">Operator Overloading</a> <ul> <li><a href="#Heading17">How You Accomplish Operator Overloading</a> </ul> <li><a href="#Heading18">Passing Objects by Value</a> <ul> <li><a href="#Heading19">Why Is it a Reference?</a> </ul></ul><hr size=4><a name="_Toc445687412"></a><p>The problem with using arrays is that you must declare their size at compile time rather than at runtime.</p><blockquote> <hr> <p> <b>compile time</b>--When you compile the program</p> <p> <b>runtime</b>--When you run the program</p> <hr></blockquote><p>This means that you must guess, in advance, how much memory you need to allocate. If you guess wrong and you allocate too little, you run out of room and your program breaks. If, on the other hand, you allocate more than you need, you waste memory.</p><p>In Decryptix! this isn't a very big problem because we create only two arrays: one to hold the solution and one to hold the guess. We can just create a pair of arrays large enough to hold the biggest legal solutions and the largest possible guess, and let it go at that. </p><p>In other programs, however, fixed size arrays are so wasteful of memory as to be unusable. Software designers are often asked to consider how their program will <i>scale:</i> How will they perform as they become larger and handle more data? Programs that use fixed size arrays rarely scale well.</p><blockquote> <hr> <p> <i>Scaling</i> a program refers to the capability to do more: to handle larger and more complex data sets, more users, or more frequent access. When a program scales, it becomes bigger and typically more complex, and all the weaknesses in performance and maintainability surface.</p> <hr></blockquote><p>To solve the problem of fixed size arrays, we need the capability to store data in some form of data structure or collection that grows <i>dynamically</i>, which means that it grows as it needs to while the program runs. <a name="_Toc445687413"></a></p><h2> <a name="Heading1">Dynamic Data Structures</a></h2><p>Over the years, computer scientists have struggled with this issue. In the past, procedural programmers created complex data structures to hold data efficiently. Object-oriented programmers talk about <i>collection classes</i>, classes that are designed to hold collections of other objects. </p><blockquote> <hr> <p><b>collection</b> <b>class</b>--A class designed to hold a collection of other objects</p> <hr></blockquote><p>Collection classes are built on top of traditional data structures as higher-level abstractions, but the problem they are solving is the same: How do we efficiently deal with large sets of data or objects?</p><p>We need a variety of collection classes because our needs and priorities differ from program to program. Sometimes we care about adding objects to the collection quickly. Other times, we don't mind if there is a slight delay adding objects, but we want the capability to find objects quickly. In other programs, the emphasis is on using little memory or little disk space. <a name="_Toc445687414"></a></p><h3> <a name="Heading2">The Standard Template Library</a></h3><p>The C++ Standard Library now offers a suite of <i>collection classes</i> called the Standard Template Library (STL), which is described in coming chapters. The STL classes are designed to hold collections of objects, including built-in objects such as characters and more complex (and dramatically larger) user-defined objects. Most importantly, the STL code has been optimized, debugged, and tested so that you don't have to do this work yourself.</p><p>Before considering the STL in detail, however, it is helpful to create our own rather simple collection class, at least once, to see what is involved.</p><p>We'll rewrite Decryptix! to use a <i>linked list</i> rather than an array. A linked list is a very simple data structure that consists of small containers that can be linked together as needed, and each of which is designed to hold one object. </p><blockquote> <hr> <p> <b>linked</b> <b>list</b>--A simple data structure in which each element in the list points to data and to the next element in the list</p> <hr></blockquote><p>Each individual container is called a <i>node</i>. The first node in the list is called the <i>head</i>, and the last node in the list is called the <i>tail</i>.</p><blockquote> <hr> <p> <b>node</b>--An element in a data structure</p> <p> <b>head</b>--The first node in a linked list</p> <p> <b>tail</b>--The last node in a linked list</p> <hr></blockquote><p>Lists come in three fundamental forms. From simplest to most complex, they are</p><ul> <li> <p> Singly linked</p> </li> <p></p> <li> <p> Doubly linked</p> </li> <p></p> <li> <p> Trees</p> </li></ul><p></p><p>In a singly linked list, each node points forward to the next one, but not backward. To find a particular node, start at the top and go from node to node, as in a treasure hunt ("The next node is under the sofa"). A doubly linked list enables you to move backward and forward in the chain. A tree is a complex structure built from nodes, each of which can point in two or three directions. Figure 6.1 shows these three fundamental structures.</p><p><b>Figure 6.1 </b><i>Singly linked, doubly linked, and tree structures. <a name="_Toc445687415"></a></i></p><h2> <a name="Heading3">Linked Lists</a></h2><p>We'll build the simplest form of linked list, a singly linked list that is not sorted. Characters are added in the order in which they are received (just as they are in an array).</p><p>We'll actually create the linked list three times. The first time we'll take a rather simplistic, traditional approach just to get a good sense of how a linked list works. The second time we'll design a somewhat more object-oriented linked list and see whether we can add some solid object-oriented design heuristics to our solution. Finally, we'll use the linked list to illustrate the concept of abstract data types. <a name="_Toc445687416"></a></p><h3> <a name="Heading4">Understanding Linked Lists</a></h3><p>Our simplest linked list consists of nothing but nodes. A node is a tiny object with two members. The first member is a pointer to the thing we're storing, in our case a single character. The second member is a pointer to another node. By stringing nodes together, we create a linked list. </p><p>When there are no more nodes in the list, the last node points to <tt>NULL</tt>. Figure 6.2 shows what our linked list looks like. The first node in the list (the head node) points to its data (A) and also to the second node in the list. This second node in turn points to its data and also to the third node. The third node is the tail node, and it points to its data and to null, signifying that there are no more nodes in the list.</p><p><b>Figure 6.2 </b><i>Simple linked list.</i></p><p>Let's implement this linked list and then see how we might use it, instead of an array, to hold our solution. To get started, however, we need only create the <tt>Node</tt> class and fill it with a list of characters. Listing 6.1 has the declaration for our <tt>Node</tt> class.</p><blockquote> <hr> <p><strong>NOTE: </strong> During the development of a program, I'm often confronted with a new technology, in this case the linked list. Rather than trying to figure out how to use it in my program while also figuring out how to implement it, I usually first implement the technology with a simple <i>driver program</i>. That is, I'll take it out of context and create a very simple program that does nothing but exercise the new technology. After it is working, I'll go back and integrate it into the real program.</p> <hr></blockquote><h4> Listing 6.1 The Node Class Declaration</h4><pre><tt>0: class Node</tt><tt>1: {</tt><tt>2: public:</tt><tt>3: Node(char c);</tt><tt>4: ~Node();</tt><tt>5: void Display () const;</tt><tt>6: int HowMany (char c) const;</tt><tt>7: void Insert (char c);</tt><tt>8: </tt><tt>9: private:</tt><tt>10: char GetChar ();</tt><tt>11: Node * GetNext ();</tt><tt>12: char myChar;</tt><tt>13: Node * nextNode;</tt><tt>14: };</tt></pre><p>Let's start by looking at the constructor on line 3. A node is created by passing in a character by value. Rather than keeping a pointer to the character, our <tt>Node</tt> class keeps a copy of the character on line 12. With a tiny one-byte object, this is sensible. With larger objects, you'll want to keep a pointer to avoid making a copy.</p><blockquote> <hr> <p><strong>NOTE: </strong> In C++, pointers are typically 4 bytes. With a 1-byte object, it is cheaper to keep a copy (one byte of memory used) than to keep a pointer (4 bytes of memory used). With large user-defined types, it can be far more expensive to make the copy, in which case a pointer or reference is used.</p> <hr></blockquote><p><tt>Node</tt> provides three methods in addition to its constructor and destructor. On line 5 we see <tt>Display()</tt>, whose job it is to print the characters that are stored in the list. The method <tt>HowMany()</tt> also takes a character and returns the number of times that character appears in the list. Finally, <tt>Insert()</tt> takes a character and inserts it into the list. Listing 6.2 shows the implementation of these simple methods.</p><h4> Listing 6.2 Implementing Node</h4><pre><tt>0: #include <iostream></tt><tt>1: using namespace std;</tt><tt>2: </tt><tt>3: #include "Node.h"</tt><tt>4: </tt><tt>5: Node::Node(char c):</tt>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -