page192.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 64 行
HTML
64 行
<HTML><HEAD><TITLE>Inserting Items in a Sorted 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="tex2html3421" HREF="page193.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3419" HREF="page191.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3413" HREF="page191.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3423" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION007211000000000000000">Inserting Items in a Sorted List</A></H3><P>When inserting an item into a sorted listwe have as a <em>precondition</em><A NAME=9853> </A>that the list is already sorted.Furthermore, once the item is inserted,we have the <em>postcondition</em><A NAME=9855> </A>that the list must still be sorted.Therefore, all the items initially in the list that are largerthan the item to be insertedneed to be moved to the right by one positionas shown in Figure <A HREF="page192.html#figlists3"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P><P><A NAME="10093"> </A><A NAME="figlists3"> </A> <IMG WIDTH=575 HEIGHT=182 ALIGN=BOTTOM ALT="figure9857" SRC="img802.gif" ><BR><STRONG>Figure:</STRONG> Inserting an item into a sorted list implemented as an array.<BR><P><P>Program <A HREF="page192.html#progsortedListAsArrayb"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> defines the <tt>insert</tt> methodfor the <tt>SortedListAsArray</tt> class.In addition to <tt>self</tt>,this method takes as its argument the object to be inserted in the list.Recall that the <tt>insert</tt> methodprovided by the <tt>ListAsLinkedList</tt> classsimply adds items at the end of the array.While this is both efficient and easy to implement,it is not suitable for the <tt>SortedListAsArray</tt> classsince the items in the array must be end up in order.<P><P><A NAME="10448"> </A><A NAME="progsortedListAsArrayb"> </A> <IMG WIDTH=575 HEIGHT=256 ALIGN=BOTTOM ALT="program10103" SRC="img803.gif" ><BR><STRONG>Program:</STRONG> <tt>SortedListAsArray</tt> class <tt>insert</tt> method.<BR><P><P>The <tt>insert</tt> method given in Program <A HREF="page192.html#progsortedListAsArrayb"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>first checks that there is still room in the array for one more item.Then, to insert the item into the list,all the items in the list that are larger than the one to be insertedare moved to the right.This is accomplished by the loop on lines 7-9.Finally, the item to be inserted is recorded in theappropriate array position on line 10.<P>In the worst case, the item to be inserted is smaller thanall the items already in the sorted list.In this case, all <IMG WIDTH=78 HEIGHT=9 ALIGN=BOTTOM ALT="tex2html_wrap_inline61037" SRC="img743.gif" > items must be movedone position to the right.Therefore, the running time of the <tt>insert</tt> method is <I>O</I>(<I>n</I>).<P><HR><A NAME="tex2html3421" HREF="page193.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3419" HREF="page191.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3413" HREF="page191.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3423" 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 + -
显示快捷键?