page172.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 73 行
HTML
73 行
<HTML>
<HEAD>
<TITLE>Removing Items from a List</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="tex2html4039" HREF="page173.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page173.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="tex2html4037" HREF="page168.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page168.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="tex2html4031" HREF="page171.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page171.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="tex2html4041" 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="tex2html4042" 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>
<H3><A NAME="SECTION008114000000000000000">Removing Items from a List</A></H3>
<P>
Objects are removed from a searchable container
using the <tt>Withdraw</tt> function.
Program <A HREF="page172.html#proglist3c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page172.html#proglist3c"><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> defines the <tt>Withdraw</tt> function
for the <tt>ListAsArray</tt> class.
This function takes a single argument which is a
reference to the object to be removed from the container.
It is the specific object instance which is removed from the container,
not simply one which matches (i.e., compares equal to) the argument.
<P>
<P><A NAME="9609"> </A><A NAME="proglist3c"> </A> <IMG WIDTH=575 HEIGHT=277 ALIGN=BOTTOM ALT="program9491" SRC="img791.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img791.gif" ><BR>
<STRONG>Program:</STRONG> <tt>ListAsArray</tt> Class <tt>Withdraw</tt> Member Function Definition<BR>
<P>
<P>
The withdraw function first needs to find the position
of the item to be removed from the list.
This part is identical to the main loop of the <tt>IsMember</tt> function.
An exception is thrown if the list is empty,
or if the object to be removed is not in the list.
The number of iterations needed to find an object depends
on its position.
If the object to be removed is found at position <I>i</I>,
then the search phase takes <I>O</I>(<I>i</I>) time.
<P>
Removing an object from position <I>i</I> of
an ordered list which is stored in an array
requires that all of the objects at positions
<I>i</I>+1, <I>i</I>+2, ..., <IMG WIDTH=68 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline61316" SRC="img711.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img711.gif" >,
be moved one position to the left.
Altogether, <IMG WIDTH=93 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline61668" SRC="img792.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img792.gif" > objects need to be moved.
Hence, this phase takes <IMG WIDTH=90 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61670" SRC="img793.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img793.gif" > time.
<P>
The running time of the <tt>Withdraw</tt> function is
the sum of the running times of the two phases, <I>O</I>(<I>i</I>)+ <IMG WIDTH=90 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61670" SRC="img793.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img793.gif" >.
Hence, the total running time is <I>O</I>(<I>n</I>),
where <IMG WIDTH=72 HEIGHT=9 ALIGN=BOTTOM ALT="tex2html_wrap_inline61308" SRC="img709.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img709.gif" > is the number of items in the ordered list.
<P>
Care must be taken when using the <tt>Withdraw</tt> function.
Consider the following:
<PRE>Object& object1 = *new Int (57);
Object& object2 = *new Int (57);
ListAsArray list (1);
list.Insert (object1);</PRE>
To remove <tt>object1</tt> from the ordered list, we may write
<PRE>list.Withdraw (object1);</PRE>
However, the call
<PRE>list.Withdraw (object2);</PRE>
will fail because <tt>object2</tt> is not actually in the list.
If for some reason we have lost track of <tt>object1</tt>,
we can always write:
<PRE>list.Withdraw (list.Find (object2));</PRE>
which first locates the object in the ordered list (<tt>object1</tt>)
which matches <tt>object2</tt>
and then deletes that object.
<P>
<HR><A NAME="tex2html4039" HREF="page173.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page173.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="tex2html4037" HREF="page168.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page168.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="tex2html4031" HREF="page171.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page171.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="tex2html4041" 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="tex2html4042" 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 + -
显示快捷键?