page234.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 81 行
HTML
81 行
<HTML><HEAD><TITLE>Inserting and Finding an Item</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="tex2html3899" HREF="page235.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3897" HREF="page231.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3891" HREF="page233.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3901" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION008513000000000000000">Inserting and Finding an Item</A></H3><P>Program <A HREF="page234.html#progchainedScatterTablec"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives the codefor the <tt>insert</tt> and <tt>find</tt>methods of the <tt>ChainedScatterTable</tt> class.To insert an item into a chained scatter tablewe need to find an unused array location in which to put the item.We first hash the item to determine the ``natural'' location for that item.If the natural location is unused,we store the item there and we are done.<P><P><A NAME="11961"> </A><A NAME="progchainedScatterTablec"> </A> <IMG WIDTH=575 HEIGHT=504 ALIGN=BOTTOM ALT="program11873" SRC="img957.gif" ><BR><STRONG>Program:</STRONG> <tt>ChainedScatterTable</tt> class <tt>insert</tt> and <tt>find</tt> methods.<BR><P><P>However, if the natural position for an item is occupied,then a collision has occurred and an alternate location in which tostore that item must be found.When a collision occurs it must be the case that there is a chainemanating from the natural position for the item.The insertion algorithm given always adds items at the end of the chain.Therefore, after a collision has been detected,the end of the chain is found (lines 8-9).<P>After the end of the chain is found,an unused array position in which to store the item must be found.This is done by a simple, linear search starting from the array positionimmediately following the end of the chain (lines 10-13).Once an unused position is found,it is linked to the end of the chain (line 14),and the item is stored in the unused position (line 15).<P>The worst case running time for insertion occurs when the scatter tablehas only one unused entry. That is, when the number of items in the table is <I>n</I>=<I>M</I>-1,where <I>M</I> is the table size.In the worst case,all of the used array elements are linked into a single chainof length <I>M</I>-1 and the item to be inserted hashes to the head of the chain.In this case, it takes <I>O</I>(<I>M</I>) to find the end of the chain.In the worst case, the end of the chain immediately follows the unusedarray position.Consequently, the linear search for the unused position is also <I>O</I>(<I>M</I>).Once an unused position has been found,the actual insertion can be done in constant time.Therefore, the running time of the insertion operation is <IMG WIDTH=109 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62315" SRC="img958.gif" > in the worst case.<P>Program <A HREF="page234.html#progchainedScatterTablec"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> also gives the code for the <tt>find</tt>method which is used to locate a given object in the scatter table.The algorithm is straightforward.The item is hashed to find its natural location in the table.If the item is not found in the natural location but a chain emanatesfrom that location,the chain is followed to determineif that item appears anywhere in the chain.<P>The worst-case running time occurs whenthe item for which we are looking is not in the table,the table is completely full,and all of the entries are linked together into a single linked list.In this case, the running time of the <tt>find</tt> algorithm is <IMG WIDTH=200 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline62317" SRC="img959.gif" >.<P><HR><A NAME="tex2html3899" HREF="page235.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html3897" HREF="page231.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html3891" HREF="page233.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html3901" 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 + -
显示快捷键?