page188.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 82 行
HTML
82 行
<HTML>
<HEAD>
<TITLE>Sorted 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="tex2html4233" HREF="page189.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page189.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="tex2html4231" 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="tex2html4225" HREF="page187.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page187.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="tex2html4235" 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="tex2html4236" 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="SECTION008200000000000000000">Sorted Lists</A></H1>
<P>
The next type of searchable container that we consider is a
<em>sorted list</em><A NAME=10461> </A>.
A sorted list is like an ordered list:
It is a searchable container that holds a sequence of objects.
However, the position of an item in a sorted list is not arbitrary.
The items in the sequence appear in order, say,
from the smallest to the largest.
Of course, for such an ordering to exist,
the relation used to sort the items must be a <em>total order</em><A NAME="tex2html363" HREF="footnode.html#10583" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/footnode.html#10583"><IMG ALIGN=BOTTOM ALT="gif" SRC="foot_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/foot_motif.gif"></A>.
<P>
In addition to the basic repertoire of operations supported by
all searchable containers,
sorted lists provide the following operations:
<DL ><DT><STRONG><tt>FindPosition</tt></STRONG>
<DD>
used to find the position of an object in the sorted list;
<DT><STRONG><tt>operator []</tt></STRONG>
<DD>
used to access the object at a given position in the sorted list;
<DT><STRONG><tt>Withdraw</tt></STRONG>
<DD>
used to remove the object at a given position from the sorted list.
<P>
</DL>
These operations have similar semantics
to the like-named ones for ordered lists.
Conspicuous by their absence are the operations
<tt>InsertAfter</tt> and <tt>InsertBefore</tt>
which are provided by the <tt>OrderedList</tt> class.
These operations are not provided for sorted lists
because they allow arbitrary insertions,
but arbitrary insertions do not necessarily result in sorted lists.
<P>
Program <A HREF="page188.html#progsorted1h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page188.html#progsorted1h"><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> gives the declaration
of the class which is used to represent sorted lists: <tt>SortedList</tt>.
Like its unsorted counterpart,
the class <tt>SortedList</tt> is derived
from the class <tt>List</tt> which is in turn derived from
<tt>SearchableContainer</tt>.
No new member functions are added to the inherited interface.
<P>
<P><A NAME="10584"> </A><A NAME="progsorted1h"> </A> <IMG WIDTH=575 HEIGHT=66 ALIGN=BOTTOM ALT="program10482" SRC="img847.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img847.gif" ><BR>
<STRONG>Program:</STRONG> <tt>SortedList</tt> Class Definition<BR>
<P>
<P>
Sorted lists are very similar to ordered lists.
As a result, we can make use of the code for ordered lists
when implementing sorted lists.
Specifically, we will consider an array-based implementation of
sorted lists that is derived from the <tt>ListAsArray</tt> class
defined in 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>,
and a pointer-based implementation of sorted lists
that is derived from the <tt>ListAsLinkedList</tt>
class given in 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>.
<P>
<BR> <HR>
<UL>
<LI> <A NAME="tex2html4237" HREF="page189.html#SECTION008210000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page189.html#SECTION008210000000000000000">Array Implementation</A>
<LI> <A NAME="tex2html4238" HREF="page194.html#SECTION008220000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page194.html#SECTION008220000000000000000">Linked List Implementation</A>
<LI> <A NAME="tex2html4239" HREF="page197.html#SECTION008230000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page197.html#SECTION008230000000000000000">Performance Comparison:
<tt>SortedListAsArray</tt> vs. <tt>SortedListAsList</tt></A>
<LI> <A NAME="tex2html4240" HREF="page198.html#SECTION008240000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page198.html#SECTION008240000000000000000">Applications</A>
</UL>
<HR><A NAME="tex2html4233" HREF="page189.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page189.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="tex2html4231" 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="tex2html4225" HREF="page187.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page187.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="tex2html4235" 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="tex2html4236" 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 + -
显示快捷键?