📄 page244.html

📁 wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq
💻 HTML
字号:
<HTML>
<HEAD>
<TITLE>Finding Items</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="tex2html4935" HREF="page245.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page245.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="tex2html4933" HREF="page241.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page241.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="tex2html4927" HREF="page243.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page243.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="tex2html4937" 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="tex2html4938" 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="SECTION009643000000000000000">Finding Items</A></H3>
<P>
The <tt>Find</tt> and <tt>FindMatch</tt> member functions
of the <tt>OpenScatterTable</tt> class are defined
in Program&nbsp;<A HREF="page244.html#proghashtbl10c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page244.html#proghashtbl10c"><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>.
The <tt>FindMatch</tt> function takes a <tt>const</tt> reference
to an object and searches the scatter table for
an object which matches the given one.
<P>
<P><A NAME="14306">&#160;</A><A NAME="proghashtbl10c">&#160;</A> <IMG WIDTH=575 HEIGHT=468 ALIGN=BOTTOM ALT="program14026" SRC="img1053.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1053.gif"  ><BR>
<STRONG>Program:</STRONG> <tt>OpenScatterTable</tt> Class <tt>FindMatch</tt> and 	<tt>Find</tt> Member Function Definitions<BR>
<P>
<P>
<tt>FindMatch</tt> follows the same probing sequence
used by the <tt>Insert</tt> function.
Therefore, if there is a matching object in the scatter table,
<tt>FindMatch</tt> will make exactly the same number of probes
to locate the object as were made to put the object into the table
in the first place.
The <tt>FindMatch</tt> routine makes at most <I>M</I> probes,
where  <IMG WIDTH=87 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline63192" SRC="img1052.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1052.gif"  > is the size of the scatter table.
However, note that the loop immediately terminates
should it encounter an <tt>empty</tt> location.
This is because if the target has not been found by the time
an empty cell is encountered,
then the target is not in the table.
Notice also that the comparison is only attempted for entries which
are marked <tt>occupied</tt>.
Any locations marked <tt>deleted</tt> are not examined during the search
but they do not terminate the search either.
<P>
The running time of the <tt>Find</tt> routine is determined
by that of <tt>FindMatch</tt>.
In the worst case <tt>FindMatch</tt> makes <I>n</I> comparisons,
where <I>n</I> is the number of items in the table.
Therefore, the running time of <tt>Find</tt> is
 <IMG WIDTH=258 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline63210" SRC="img1054.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1054.gif"  >.
<P>
<HR><A NAME="tex2html4935" HREF="page245.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page245.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="tex2html4933" HREF="page241.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page241.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="tex2html4927" HREF="page243.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page243.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="tex2html4937" 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="tex2html4938" 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 &#169; 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 + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -