📄 page177.html
字号:
<HTML><HEAD><TITLE>Inserting an Item at an Arbitrary Position</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="tex2html3246" HREF="page178.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3244" HREF="page170.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3238" HREF="page176.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3248" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION007117000000000000000">Inserting an Item at an Arbitrary Position</A></H3><P>Two methods for inserting an item at an arbitraryposition in an ordered list are declared in Program <A HREF="page169.html#progcursora"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>--<tt>insertBefore</tt> and <tt>insertAfter</tt>.In addition to <tt>self</tt>,both of these take one argument, <tt>obj</tt>, the object to be inserted.The effects of these two methods are illustrated in Figure <A HREF="page177.html#figlists1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P><P><A NAME="9040"> </A><A NAME="figlists1"> </A> <IMG WIDTH=575 HEIGHT=262 ALIGN=BOTTOM ALT="figure8838" SRC="img746.gif" ><BR><STRONG>Figure:</STRONG> Inserting an item in an ordered list implemented as an array.<BR><P><P>Figure <A HREF="page177.html#figlists1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows that in both casesa number of items to the right of the insertion pointneed to be moved overto make room for the item that is being inserted into the ordered list.In the case of <tt>insertBefore</tt>,items to the right <em>including the item at the point of insertion</em>are moved;for <tt>insertAfter</tt>,only items to the right of the point of insertion are moved,and the new item is inserted in the array locationfollowing the insertion point.<P>Program <A HREF="page177.html#progorderedListAsArrayf"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives the implementation of the<tt>insertAfter</tt> method for the <tt>OrderedListAsArray.Cursor</tt> class.The code for the <tt>insertBefore</tt> method is identicalexcept for one line as explained below.<P><P><A NAME="9112"> </A><A NAME="progorderedListAsArrayf"> </A> <IMG WIDTH=575 HEIGHT=409 ALIGN=BOTTOM ALT="program9051" SRC="img747.gif" ><BR><STRONG>Program:</STRONG> <tt>OrderedListAsArray.Cursor</tt> class <tt>insertAfter</tt> method.<BR><P><P>In addition to <tt>self</tt>,the <tt>insertAfter</tt> method takes one argument, <tt>obj</tt>.The method begins by performing some simple teststo ensure that the position is validand that there is room left in the array to do the insertion.<P>On line 11 the array index where the new item willultimately be stored is computed.For <tt>insertAfter</tt> the index is <IMG WIDTH=82 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline61047" SRC="img748.gif" >as shown in Program <A HREF="page177.html#progorderedListAsArrayf"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.In the case of <tt>insertBefore</tt>,the value required is simply <tt>_offset</tt>.The loop on lines 13-15 moves items overand then object being inserted is put in the array on line 16.<P>If we assume that no exceptions are raised,the running time of <tt>insertAfter</tt>is dominated by the loop which moves list items.In the worst case, all the items in the array need to be moved.Thus, the running time of both the <tt>insertAfter</tt>and <tt>insertBefore</tt> method is <I>O</I>(<I>n</I>),where <IMG WIDTH=72 HEIGHT=9 ALIGN=BOTTOM ALT="tex2html_wrap_inline60691" SRC="img663.gif" >.<P><HR><A NAME="tex2html3246" HREF="page178.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3244" HREF="page170.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3238" HREF="page176.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3248" 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 + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -