page235.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 112 行
HTML
112 行
<HTML><HEAD><TITLE>Removing Items</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="tex2html3910" HREF="page236.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3908" HREF="page231.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3902" HREF="page234.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3912" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION008514000000000000000">Removing Items</A></H3><P>Removing items from a chained scatter table is more complicatedthan putting them into the table.The goal when removing an item is to have the scatter table end upexactly as it would have appearedhad that item never been inserted in the first place.Therefore, when an item is removed from the middle of a chain,items which follow it in the chain have to be moved up to fill in the hole.However, the moving-up operation is complicated by the fact thatseveral chains may have coalesced.<P>Program <A HREF="page235.html#progchainedScatterTabled"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives an implementation of the<tt>withdraw</tt> method of the <tt>ChainedScatterTable</tt> class.The algorithm begins by checking that the table is not empty (lines 4-5).To remove an item, we first have to find it.This is what the loop on lines 6-8 does.If the item to be deleted is not in the table,when this loop terminates the variable <tt>i</tt> has the value <tt>NULL</tt>and an exception is thrown (lines 9-10).Otherwise, the item a position <tt>i</tt> in the table is to be removed.<P><P><A NAME="11964"> </A><A NAME="progchainedScatterTabled"> </A> <IMG WIDTH=575 HEIGHT=733 ALIGN=BOTTOM ALT="program11895" SRC="img960.gif" ><BR><STRONG>Program:</STRONG> <tt>ChainedScatterTable</tt> class <tt>withdraw</tt> method.<BR><P><P>The purpose of the loop on lines 11-28 is to fill in the holein the chain which results when the item at position <tt>i</tt> is removedby moving up items which follow it in the chain.What we need to do is to find the next item which follows the item at <tt>i</tt>that is safe to move into position <tt>i</tt>.The loop on lines 13-24 searches the rest of the chain followingthe item at <tt>i</tt> to find an item which can be safely moved.<P>Figure <A HREF="page235.html#fighash4"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> illustrates the basic idea.The figures shows a chained scatter table of length tenthat contains integer-valued keys.There is a single chain as shown in the figure.However, notice that the values in the chain are not all equal modulo 10.In fact, this chain must have resulted from the coalescing of three chains--one which begins in position 1,one which begins in position 2, and one which begins in position 5.<P><P><A NAME="12544"> </A><A NAME="fighash4"> </A> <IMG WIDTH=575 HEIGHT=450 ALIGN=BOTTOM ALT="figure11909" SRC="img961.gif" ><BR><STRONG>Figure:</STRONG> Removing items from a chained scatter table.<BR><P><P>Suppose we wish to remove item 11 which is in position 2,which is indicated by the box in Figure <A HREF="page235.html#fighash4"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (a).To delete it, we must follow the chain to find the next item that canbe moved safely up to position 2.Item 02 which follows 11 and can be moved safely up to position 2because that is the location to which it hashes.Moving item 02 up moves the hole down the list to position 3(Figure <A HREF="page235.html#fighash4"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (b)).Again we follow the chain to find that item 21 can be moved safely upgiving rise to the situation in Figure <A HREF="page235.html#fighash4"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (c).<P>Now we have a case where an item cannot be moved.Item 05 is the next candidate to be moved.However, it is in position 5 which is the position to which it hashes.If we were to move it up,then it would no longer be in the chain which emanates from position 5.In effect, the item would no longer be accessible!Therefore, it cannot be moved safely.Instead, we must move item 31 ahead of item 5as shown in Figure <A HREF="page235.html#fighash4"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (d).Eventually, the hole propagates to the end of the chain,where it can be delete easily (Figure <A HREF="page235.html#fighash4"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (e)).<P>The loop on lines 13-24 of Program <A HREF="page235.html#progchainedScatterTabled"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>finds the position <tt>j</tt> of an item which can be safely movedto position <tt>i</tt>.The algorithm makes use of the following fact:An item can be safely moved up<em>only if it does not hash to a positionwhich appears in the linked list between <tt>i</tt> and <tt>j</tt></em>.This is what the code on lines 15-21 tests.<P>When execution reaches line 25,either we have found an item which can be safely moved,or there does not exist such an item.If an item is found,it is moved up (line 27)and we repeat the whole process again.On the other hand,if there are no more items to be moved up,then the process is finished and the main loop (lines 11-28) terminates.<P>The statement on line 29 does the actual deed of removingthe data from the position which <tt>i</tt> which by now is at the endof the chain.The final task to be done is to remove the pointer to position <tt>i</tt>,since there is no longer any data at that position.That is the job of the loop on lines 31-35.<P><HR><A NAME="tex2html3910" HREF="page236.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3908" HREF="page231.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3902" HREF="page234.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3912" 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 + -
显示快捷键?