page88.html

来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 157 行 · 第 1/2 页

that does not use a sentinel.
Figure&nbsp;<A HREF="page88.html#figlinklist1" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page88.html#figlinklist1"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>&nbsp;(e) shows a variation in which
a single pointer is used to keep track of the list,
but this time the pointer, <tt>tail</tt>,
points to the last element of the list.
Since the list is circular in this case,
the first element follows the last element of the list.
Therefore, it is relatively simple to insert both
at the head and at the tail of this list.
This variation minimizes the storage required,
at the expense of a little extra time for certain operations.
<P>
Figure&nbsp;<A HREF="page88.html#figlinklist2" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page88.html#figlinklist2"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> illustrates how the empty list
(i.e., the list containing no list elements)
is represented for each of the variations given in Figure&nbsp;<A HREF="page88.html#figlinklist2" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page88.html#figlinklist2"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
Notice that the sentinel is always present
in those list variants which use it.
On the other hand,
in the list variants which do not use a sentinel,
null pointers are used to indicate the empty list.
<P>
<P><A NAME="3235">&#160;</A><A NAME="figlinklist2">&#160;</A> <IMG WIDTH=575 HEIGHT=344 ALIGN=BOTTOM ALT="figure3089" SRC="img612.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img612.gif"  ><BR>
<STRONG>Figure:</STRONG> Empty Singly-Linked Lists<BR>
<P>
<P>
The list variant&nbsp;(b) introduces a potential source of very
subtle programming errors.
A conservative programmer would insist that <em>both</em>
the <tt>head</tt> and <tt>tail</tt> pointers must be null.
However, a clever programmer might realize that it is sufficient
require only that the <tt>head</tt> pointer be null in the case
of an empty list.
Since, the <tt>tail</tt> pointer is not used when the list is empty,
its value may be left undefined.
Of course, if that is the case,
extreme care must be taken to ensure that the <tt>tail</tt> pointer
is never used when the <tt>head</tt> pointer is null.
<P>
In the following sections,
we will present the implementation details of a generic singly-linked list.
We have chosen to present variation&nbsp;(b)--the one which uses a head and a tail pointer--since is supports append and prepend operations  efficiently.
While linked lists which use a sentinel do present some
interesting time efficiencies,
we have chosen not to use a sentinel because
the use of a sentinel is essentially a programming trick.
Also, from an object-oriented perspective,
the use of a sentinel introduces some semantic difficulties.
E.g., if each element of the list contains an object of type <tt>T</tt>,
and we create a list to hold exactly <I>n</I> elements,
it might be reasonable to expect that <tt>T</tt>'s constructor is called
only <I>n</I> times.
However, when using a sentinel
<I>n</I>+1 objects of type <tt>T</tt> are actually created--the extra one being the sentinel itself.
Thus, the constructor of <tt>T</tt> objects is called <I>n</I>+1 times
which may not be at all what the programmer expects.
<P>
<BR> <HR>
<UL> 
<LI> <A NAME="tex2html2991" HREF="page89.html#SECTION005210000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page89.html#SECTION005210000000000000000">An Implementation</A>
<LI> <A NAME="tex2html2992" HREF="page90.html#SECTION005220000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page90.html#SECTION005220000000000000000">List Elements</A>
<LI> <A NAME="tex2html2993" HREF="page91.html#SECTION005230000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page91.html#SECTION005230000000000000000">Default Constructor</A>
<LI> <A NAME="tex2html2994" HREF="page92.html#SECTION005240000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page92.html#SECTION005240000000000000000">Destructor and <tt>Purge</tt> Member Function</A>
<LI> <A NAME="tex2html2995" HREF="page93.html#SECTION005250000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page93.html#SECTION005250000000000000000">Accessors</A>
<LI> <A NAME="tex2html2996" HREF="page94.html#SECTION005260000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page94.html#SECTION005260000000000000000"><tt>First</tt> and <tt>Last</tt> Functions</A>
<LI> <A NAME="tex2html2997" HREF="page95.html#SECTION005270000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page95.html#SECTION005270000000000000000"><tt>Prepend</tt></A>
<LI> <A NAME="tex2html2998" HREF="page96.html#SECTION005280000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page96.html#SECTION005280000000000000000"><tt>Append</tt></A>
<LI> <A NAME="tex2html2999" HREF="page97.html#SECTION005290000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page97.html#SECTION005290000000000000000">Copy Constructor and Assignment Operator</A>
<LI> <A NAME="tex2html3000" HREF="page98.html#SECTION0052100000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page98.html#SECTION0052100000000000000000"><tt>Extract</tt></A>
<LI> <A NAME="tex2html3001" HREF="page99.html#SECTION0052110000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page99.html#SECTION0052110000000000000000"><tt>InsertAfter</tt> and <tt>InsertBefore</tt></A>
</UL>
<HR><A NAME="tex2html2987" HREF="page89.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page89.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html2985" HREF="page79.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page79.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html2979" HREF="page87.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page87.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html2989" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html2990" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright &#169; 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a>  All rights reserved.

</ADDRESS>
</BODY>
</HTML>