?? page244.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 <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"> </A><A NAME="proghashtbl10c"> </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 © 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 + -