page174.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 72 行
HTML
72 行
<HTML><HEAD><TITLE>Removing Items from a List</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html3213" HREF="page175.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3211" HREF="page170.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3205" HREF="page173.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3215" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION007114000000000000000">Removing Items from a List</A></H3><P>Objects are removed from a searchable containerusing the <tt>withdraw</tt> method.Program <A HREF="page174.html#progorderedListAsArrayd"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> defines the <tt>withdraw</tt> methodfor the <tt>OrderedListAsArray</tt> class.In addition to <tt>self</tt>,this method takes a single argument which is athe 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="8859"> </A><A NAME="progorderedListAsArrayd"> </A> <IMG WIDTH=575 HEIGHT=332 ALIGN=BOTTOM ALT="program8738" SRC="img739.gif" ><BR><STRONG>Program:</STRONG> <tt>OrderedListAsArray</tt> class <tt>withdraw</tt> method.<BR><P><P>The withdraw method first needs to find the positionof the item to be removed from the list.An exception is raised 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 arrayrequires that all of the objects at positions<I>i</I>+1, <I>i</I>+2, ..., <IMG WIDTH=74 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline60683" SRC="img661.gif" >,be moved one position to the left.Altogether, <IMG WIDTH=99 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline61027" SRC="img740.gif" > objects need to be moved.Hence, this phase takes <IMG WIDTH=90 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61029" SRC="img741.gif" > time.<P>The running time of the <tt>withdraw</tt> method isthe sum of the running times of the two phases, <I>O</I>(<I>i</I>)+ <IMG WIDTH=96 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61033" SRC="img742.gif" >.Hence, the total running time is <I>O</I>(<I>n</I>),where <IMG WIDTH=78 HEIGHT=9 ALIGN=BOTTOM ALT="tex2html_wrap_inline61037" SRC="img743.gif" > is the number of items in the ordered list.<P>Care must be taken when using the <tt>withdraw</tt> method.Consider the following:<PRE>obj1 = [57]obj2 = [57]list = OrderedListAsArray(1)list.insert(obj1)</PRE>To remove <tt>obj1</tt> from the ordered list, we may write<PRE>list.withdraw(obj1)</PRE>However, the call<PRE>list.withdraw(obj2)</PRE>will fail because <tt>obj2</tt> is not actually in the list.If for some reason we have lost track of <tt>obj1</tt>,we can always write:<PRE>list.withdraw(list.find(obj2))</PRE>which first locates the object in the ordered list (<tt>obj1</tt>)which matches <tt>obj2</tt>and then deletes that object.<P><HR><A NAME="tex2html3213" HREF="page175.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3211" HREF="page170.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3205" HREF="page173.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3215" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?