page167.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 113 行
HTML
113 行
<HTML>
<HEAD>
<TITLE>Ordered Lists</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html3967" HREF="page168.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page168.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="tex2html3965" HREF="page166.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page166.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="tex2html3959" HREF="page166.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page166.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="tex2html3969" 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="tex2html3970" 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> <BR><HR>
<H1><A NAME="SECTION008100000000000000000">Ordered Lists</A></H1>
<P>
<P><A NAME="9312"> </A><A NAME="figclasses3"> </A> <IMG WIDTH=575 HEIGHT=97 ALIGN=BOTTOM ALT="figure9308" SRC="img784.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img784.gif" ><BR>
<STRONG>Figure:</STRONG> Object Class Hierarchy<BR>
<P>
<P>
The most basic of the searchable containers is an
<em>ordered list</em><A NAME=9316> </A>.
In Chapter <A HREF="page107.html#chapadts" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page107.html#chapadts"><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> we defined a searchable container as
a container which supports the following additional operations:
<DL ><DT><STRONG><tt>Insert</tt></STRONG>
<DD>
used to put objects into a the container;
<DT><STRONG><tt>Withdraw</tt></STRONG>
<DD>
used to remove objects from the container;
<DT><STRONG><tt>Find</tt></STRONG>
<DD>
used to locate objects in the container; and,
<DT><STRONG><tt>IsMember</tt></STRONG>
<DD>
used to test whether a given object instance is in the container.
<P>
</DL>
<P>
An ordered list is a container which holds
a <em>sequence</em><A NAME=9325> </A> of objects.
Each object has a unique <em>position</em><A NAME=9327> </A> in the sequence.
In addition to the basic repertoire of operations supported by
all searchable containers,
ordered lists provide the following operations:
<DL ><DT><STRONG><tt>FindPosition</tt></STRONG>
<DD>
used to find the position of an object in the ordered list;
<DT><STRONG><tt>operator []</tt></STRONG>
<DD>
used to access the object at a given position in the ordered list;
<DT><STRONG><tt>Withdraw(Position&)</tt></STRONG>
<DD>
used to remove the object at a given position from the ordered list.
<DT><STRONG><tt>InsertAfter</tt></STRONG>
<DD>
used to insert an object into the ordered list <em>after</em>
the object at a given position; and
<DT><STRONG><tt>InsertBefore</tt></STRONG>
<DD>
used to insert an object into the ordered list <em>before</em>
the object at a given position.
<P>
</DL>
<P>
Program <A HREF="page167.html#proglist1h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page167.html#proglist1h"><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> declares two abstract classes--<tt>List</tt> and <tt>OrderedList</tt>.
The <tt>List</tt> class is derived from the <tt>SearchableContainer</tt> class
which is in turn derived from the <tt>Container</tt> class.
Consequently, the <tt>List</tt> class interface comprises
all of the member functions inherited from these base classes
plus four additional member functions,
<tt>FindPosition</tt>,
two versions of <tt>operator[]</tt> and <tt>Withdraw</tt>.
As befits the definition of an abstract class,
all of these functions are pure virtual member functions
of the <tt>List</tt> class.
<P>
<P><A NAME="9591"> </A><A NAME="proglist1h"> </A> <IMG WIDTH=575 HEIGHT=371 ALIGN=BOTTOM ALT="program9348" SRC="img785.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img785.gif" ><BR>
<STRONG>Program:</STRONG> <tt>List</tt> and <tt>Ordered</tt> Class Definitions<BR>
<P>
<P>
The <tt>OrderedList</tt> class extends the <tt>List</tt> class
by adding two more member functions--<tt>InsertAfter</tt> and <tt>InsertBefore</tt>.
The two functions provided by the <tt>OrderedList</tt> class have
been separated out from the <tt>List</tt> class interface
because the <tt>List</tt> class is used as the base class
from which other types of lists are derived.
<P>
Program <A HREF="page167.html#proglist1h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page167.html#proglist1h"><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> also defines the abstract class <tt>Position</tt>.
The <tt>Position</tt> class abstracts
the notion of the position of an item in a list.
Since this is abstraction is almost identical to that of an iterator,
the <tt>Position</tt> class is derived from the <tt>Iterator</tt> abstract class.
No additional member functions are defined.
<P>
As we did in the previous chapter with stacks, deques and queues,
we will examine two ordered list implementations--an array-based one and a pointer-based one.
Section <A HREF="page168.html#seclistslista" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page168.html#seclistslista"><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> presents
an implementation based on the <tt>Array<T></tt> class;
Section <A HREF="page177.html#seclistslistp" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page177.html#seclistslistp"><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>,
a pointer-based implementation based on the <tt>LinkedList<T></tt> class.
<P>
<BR> <HR>
<UL>
<LI> <A NAME="tex2html3971" HREF="page168.html#SECTION008110000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page168.html#SECTION008110000000000000000">Array Implementation</A>
<LI> <A NAME="tex2html3972" HREF="page177.html#SECTION008120000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page177.html#SECTION008120000000000000000">Linked List Implementation</A>
<LI> <A NAME="tex2html3973" HREF="page186.html#SECTION008130000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page186.html#SECTION008130000000000000000">Performance Comparison:
<tt>ListAsArray</tt> vs. <tt>ListAsLinkedList</tt></A>
<LI> <A NAME="tex2html3974" HREF="page187.html#SECTION008140000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page187.html#SECTION008140000000000000000">Applications</A>
</UL>
<HR><A NAME="tex2html3967" HREF="page168.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page168.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="tex2html3965" HREF="page166.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page166.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="tex2html3959" HREF="page166.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page166.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="tex2html3969" 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="tex2html3970" 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 © 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>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?