ch11.htm

vc的电子书

41:    // private (helper) constructor, used only by
42:    // class methods for creating a new string of
43:    // required size. Null filled.
44:    String::String(unsigned short len)
45:    {
46:       itsString = new char[len+1];
47:       for (unsigned short i = 0; i<=len; i++)
48:          itsString[i] = `\0';
49:       itsLen=len;
50:    }
51:
52:    // Converts a character array to a String
53:    String::String(const char * const cString)
54:    {
55:       itsLen = strlen(cString);
56:       itsString = new char[itsLen+1];
57:       for (unsigned short i = 0; i<itsLen; i++)
58:          itsString[i] = cString[i];
59:       itsString[itsLen]='\0';
60:    }
61:
62:    // copy constructor
63:    String::String (const String & rhs)
64:    {
65:       itsLen=rhs.GetLen();
66:       itsString = new char[itsLen+1];
67:       for (unsigned short i = 0; i<itsLen;i++)
68:          itsString[i] = rhs[i];
69:       itsString[itsLen] = `\0';
70:    }
71:
72:    // destructor, frees allocated memory
73:    String::~String ()
74:    {
75:       delete [] itsString;
76:       itsLen = 0;
77:    }
78:
79:    // operator equals, frees existing memory
80:    // then copies string and size
81:    String& String::operator=(const String & rhs)
82:    {
83:       if (this == &rhs)
84:          return *this;
85:       delete [] itsString;
86:       itsLen=rhs.GetLen();
87:       itsString = new char[itsLen+1];
88:       for (unsigned short i = 0; i<itsLen;i++)
89:          itsString[i] = rhs[i];
90:       itsString[itsLen] = `\0';
91:       return *this;
92:    }
93:
94:    //nonconstant offset operator, returns
95:    // reference to character so it can be
96:    // changed!
97:    char & String::operator[](unsigned short offset)
98:    {
99:       if (offset > itsLen)
100:         return itsString[itsLen-1];
101:      else
102:         return itsString[offset];
103:   }
104:
105:   // constant offset operator for use
106:   // on const objects (see copy constructor!)
107:   char String::operator[](unsigned short offset) const
108:   {
109:      if (offset > itsLen)
110:         return itsString[itsLen-1];
111:      else
112:         return itsString[offset];
113:   }
114:
115:   // creates a new string by adding current
116:   // string to rhs
117:   String String::operator+(const String& rhs)
118:   {
119:      unsigned short  totalLen = itsLen + rhs.GetLen();
120:      String temp(totalLen);
121:      for (unsigned short i = 0; i<itsLen; i++)
122:         temp[i] = itsString[i];
123:      for (unsigned short j = 0; j<rhs.GetLen(); j++, i++)
124:         temp[i] = rhs[j];
125:      temp[totalLen]='\0';
126:      return temp;
127:   }
128:
129:   // changes current string, returns nothing
130:   void String::operator+=(const String& rhs)
131:   {
132:      unsigned short rhsLen = rhs.GetLen();
133:      unsigned short totalLen = itsLen + rhsLen;
134:      String  temp(totalLen);
135:      for (unsigned short i = 0; i<itsLen; i++)
136:         temp[i] = itsString[i];
137:      for (unsigned short j = 0; j<rhs.GetLen(); j++, i++)
138:         temp[i] = rhs[i-itsLen];
139:      temp[totalLen]='\0';
140:      *this = temp;
141:   }
142:
143:   int main()
144:   {
145:      String s1("initial test");
146:      cout << "S1:\t" << s1.GetString() << endl;
147:
148:      char * temp = "Hello World";
149:      s1 = temp;
150:      cout << "S1:\t" << s1.GetString() << endl;
151:
152:      char tempTwo[20];
153:      strcpy(tempTwo,"; nice to be here!");
154:      s1 += tempTwo;
155:      cout << "tempTwo:\t" << tempTwo << endl;
156:      cout << "S1:\t" << s1.GetString() << endl;
157:
158:      cout << "S1[4]:\t" << s1[4] << endl;
159:      s1[4]='x';
160:      cout << "S1:\t" << s1.GetString() << endl;
161:
162:      cout << "S1[999]:\t" << s1[999] << endl;
163:
164:      String s2(" Another string");
165:      String s3;
166:      s3 = s1+s2;
167:      cout << "S3:\t" << s3.GetString() << endl;
168:
169:      String s4;
170:      s4 = "Why does this work?";
171:      cout << "S4:\t" << s4.GetString() << endl;
172:     return 0;
<TT>173: }</TT></FONT>
<FONT COLOR="#0066FF">
Output: S1:        initial test
S1:        Hello world
tempTwo:           ; nice to be here!
S1:        Hello world; nice to be here!
S1[4]:     o
S1:        Hellx World; nice to be here!
S1[999]:           !
S3:        Hellx World; nice to be here! Another string
S4:        Why does this work?
</FONT></PRE>
<P><FONT COLOR="#000077"><B><BR>
Analysis:</B></FONT><B> </B>Lines 7-31 are the declaration of a simple <TT>String</TT>
class. Lines 11-13 contain three constructors: the default constructor, the copy
constructor, and a constructor that takes an existing null-terminated (C-style) string.<BR>
This <TT>String</TT> class overloads the offset operator (<TT>[ ]</TT>), operator
plus (<TT>+</TT>), and operator plus-equals (<TT>+=</TT>). The offset operator is
overloaded twice: once as a constant function returning a <TT>char</TT> and again
as a nonconstant function returning a reference to a <TT>char</TT>.</P>
<P>The nonconstant version is used in statements such as</P>
<PRE><FONT COLOR="#0066FF">SomeString[4]='x';</FONT></PRE>
<P>as seen in line 159. This enables direct access to each of the characters in the
string. A reference to the character is returned so that the calling function can
manipulate it.</P>
<P>The constant version is used when a constant <TT>String</TT> object is being accessed,
such as in the implementation of the copy constructor, (line 63). Note that <TT>rhs[i]</TT>
is accessed, yet <TT>rhs</TT> is declared as a <TT>const String &amp;</TT>. It isn't
legal to access this object by using a nonconstant member function. Therefore, the
reference operator must be overloaded with a constant accessor.</P>
<P>If the object being returned were large, you might want to declare the return
value to be a constant reference. However, because a <TT>char</TT> is only one byte,
there would be no point in doing that.</P>
<P>The default constructor is implemented in lines 33-39. It creates a string whose
length is 0. It is the convention of this <TT>String</TT> class to report its length
not counting the terminating null. This default string contains only a terminating
null.</P>
<P>The copy constructor is implemented in lines 63-70. It sets the new string's length
to that of the existing string--plus 1 for the terminating null. It copies each character
from the existing string to the new string, and it null-terminates the new string.</P>
<P>Lines 53-60 implement the constructor that takes an existing C-style string. This
constructor is similar to the copy constructor. The length of the existing string
is established by a call to the standard <TT>String</TT> library function <TT>strlen()</TT>.</P>
<P>On line 28, another constructor, <TT>String(unsigned short)</TT>, is declared
to be a private member function. It is the intent of the designer of this class that
no client class ever create a <TT>String</TT> of arbitrary length. This constructor
exists only to help in the internal creation of <TT>String</TT>s as required, for
example, by <TT>operator+=</TT>, on line 130. This will be discussed in depth when
<TT>operator+=</TT> is described, below.</P>
<P>The <TT>String(unsigned short)</TT> constructor fills every member of its array
with <TT>NULL</TT>. Therefore, the <TT>for</TT> loop checks for <TT>i&lt;=len</TT>
rather than <TT>i&lt;len</TT>.</P>
<P>The destructor, implemented in lines 73-77, deletes the character string maintained
by the class. Be sure to include the brackets in the call to the delete operator,
so that every member of the array is deleted, instead of only the first.</P>
<P>The assignment operator first checks whether the right-hand side of the assignment
is the same as the left-hand side. If it isn't, the current string is deleted, and
the new string is created and copied into place. A reference is returned to facilitate
assignments lik</P>
<PRE><FONT COLOR="#0066FF">String1 = String2 = String3;</FONT></PRE>
<P>The offset operator is overloaded twice. Rudimentary bounds checking is performed
both times. If the user attempts to access a character at a location beyond the end
of the array, the last character--that is, <TT>len-1</TT>--is returned.</P>
<P>Lines 117-127 implement operator plus (+) as a concatenation operator. It is convenient
to be able to write</P>
<PRE><FONT COLOR="#0066FF">String3 = String1 + String2;</FONT></PRE>
<P>and have <TT>String3</TT> be the concatenation of the other two strings. To accomplish
this, the operator plus function computes the combined length of the two strings
and creates a temporary string <TT>temp</TT>. This invokes the private constructor,
which takes an integer, and creates a string filled with nulls. The nulls are then
replaced by the contents of the two strings. The left-hand side string (<TT>*this</TT>)
is copied first, followed by the right-hand side string (<TT>rhs</TT>).</P>
<P>The first <TT>for</TT> loop counts through the string on the left-hand side and
adds each character to the new string. The second <TT>for</TT> loop counts through
the right-hand side. Note that <TT>i</TT> continues to count the place for the new
string, even as <TT>j</TT> counts into the <TT>rhs</TT> string.</P>
<P>Operator plus returns the <TT>temp</TT> string by value, which is assigned to
the string on the left-hand side of the assignment (<TT>string1</TT>). Operator <TT>+=</TT>
operates on the existing string--that is, the left-hand side of the statement <TT>string1
+= string2</TT>. It works just like operator plus, except that the <TT>temp</TT>
value is assigned to the current string (<TT>*this = temp</TT>) in line 140.</P>
<P>The <TT>main()</TT>function (lines 143-173) acts as a test driver program for
this class. Line 145 creates a <TT>String</TT> object by using the constructor that
takes a null-terminated C-style string. Line 146 prints its contents by using the
accessor function <TT>GetString()</TT>. Line 148 creates another C-style string.
Line 149 tests the assignment operator, and line 150 prints the results.</P>
<P>Line 152 creates a third C-style string, <TT>tempTwo</TT>. Line 153 invokes <TT>strcpy</TT>
to fill the buffer with the characters <TT>; nice to be here!</TT> Line 154 invokes
operator <TT>+=</TT> and concatenates <TT>tempTwo</TT> onto the existing string <TT>s1.</TT>
Line 156 prints the results.</P>
<P>In line 158, the fifth character in <TT>s1</TT> is accessed and printed. It is
assigned a new value in line 159. This invokes the nonconstant offset operator (<TT>[
]</TT>). Line 160 prints the result, which shows that the actual value has, in fact,
been changed.</P>
<P>Line 162 attempts to access a character beyond the end of the array. The last
character of the array is returned, as designed.</P>
<P>Lines 164-165 create two more <TT>String</TT> objects, and line 166 calls the
addition operator. Line 167 prints the results.</P>
<P>Line 169 creates a new <TT>String</TT> object, <TT>s4</TT>. Line 170 invokes the
assignment operator. Line 171 prints the results. You might be thinking, &quot;The
assignment operator is defined to take a constant <TT>String</TT> reference in line
21, but here the program passes in a C-style string. Why is this legal?&quot;</P>
<P>The answer is that the compiler expects a <TT>String</TT>, but it is given a character
array. Therefore, it checks whether it can create a <TT>String</TT> from what it
is given. In line 12, you declared a constructor that creates <TT>String</TT>s from
character arrays. The compiler creates a temporary <TT>String</TT> from the character
array and passes it to the assignment operator. This is known as implicit casting,
or promotion. If you had not declared--and provided the implementation for--the constructor
that takes a character array, this assignment would have generated a compiler error.
<H3 ALIGN="CENTER"><A NAME="Heading47"></A><FONT COLOR="#000077">Linked Lists and
Other Structures</FONT></H3>
<P>Arrays are much like Tupperware. They are great containers, but they are of a
fixed size. If you pick a container that is too large, you waste space in your storage
area. If you pick one that is too small, its contents spill all over and you have
a big mess.</P>
<P>One way to solve this problem is with a linked list. A linked list is a data structure
that consists of small containers that are designed to fit and that are linked together
as needed. The idea is to write a class that holds one object of your data--such
as one <TT>CAT</TT> or one <TT>Rectangle</TT>--and that can point at the next container.
You create one container for each object that you need to store, and you chain them
together as needed.</P>
<P>The containers are called nodes. The first node in the list is called the head,
and the last node in the list is called the tail.</P>
<P>Lists come in three fundamental forms. From simplest to most complex, they are

<UL>
	<LI>Singly linked
	<P>
	<LI>Doubly linked
	<P>
	<LI>Trees
</UL>

<P>In a singly linked list, each node points forward to