page233.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 81 行
HTML
81 行
<HTML>
<HEAD>
<TITLE>Inserting and Finding an Item</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html4798" HREF="page234.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page234.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html4796" HREF="page230.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page230.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html4790" HREF="page232.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page232.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html4800" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html4801" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H3><A NAME="SECTION009513000000000000000">Inserting and Finding an Item</A></H3>
<P>
Program <A HREF="page233.html#proghashtbl6c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page233.html#proghashtbl6c"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> gives the code
for the <tt>Insert</tt> and <tt>Find</tt>
member functions of the <tt>ChainedScatterTable</tt> class.
To insert an item into a chained scatter table
we 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="12589"> </A><A NAME="proghashtbl6c"> </A> <IMG WIDTH=575 HEIGHT=582 ALIGN=BOTTOM ALT="program12500" SRC="img1004.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1004.gif" ><BR>
<STRONG>Program:</STRONG> <tt>ChainedScatterTable</tt> Class <tt>Insert</tt> and <tt>Find</tt> Member Function Definitions<BR>
<P>
<P>
However, if the natural position for an item is occupied,
then a collision has occurred and an alternate location in which to
store that item must be found.
When a collision occurs it must be the case that there is a chain
emanating 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 position
immediately following the end of the chain (lines 11-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 (lines 16-17).
<P>
The worst case running time for insertion occurs when the scatter table
has only one unused entry.
I.e., 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 chain
of 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 unused
array 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=139 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline62946" SRC="img1005.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1005.gif" > in the worst case.
<P>
Program <A HREF="page233.html#proghashtbl6c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page233.html#proghashtbl6c"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> also gives the code for the <tt>Find</tt>
member function 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 emanates
from that location,
the chain is followed to determine
if that item appears anywhere in the chain.
<P>
The worst-case running time occurs when
the 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=266 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline62948" SRC="img1006.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1006.gif" >.
<P>
<HR><A NAME="tex2html4798" HREF="page234.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page234.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html4796" HREF="page230.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page230.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html4790" HREF="page232.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page232.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html4800" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html4801" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright © 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.
</ADDRESS>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?