page243.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 69 行
HTML
69 行
<HTML>
<HEAD>
<TITLE>Inserting 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="tex2html4923" HREF="page244.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page244.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="tex2html4921" 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="tex2html4915" HREF="page242.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page242.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="tex2html4925" 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="tex2html4926" 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="SECTION009642000000000000000">Inserting Items</A></H3>
<P>
The procedure for inserting an item into a scatter table
using open addressing is actually quite simple--find an unoccupied array location and then put the item in that location.
To find an unoccupied array element,
the array is probed according to a probing sequence.
In this case, the probing sequence is linear probing.
Program <A HREF="page243.html#proghashtbl9c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page243.html#proghashtbl9c"><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> defines the routines needed
to insert an item into the scatter table.
<P>
<P><A NAME="14302"> </A><A NAME="proghashtbl9c"> </A> <IMG WIDTH=575 HEIGHT=486 ALIGN=BOTTOM ALT="program13984" SRC="img1051.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1051.gif" ><BR>
<STRONG>Program:</STRONG> <tt>OpenScatterTable</tt> Class <tt>C</tt>, <tt>FindUnoccupied</tt>, and <tt>Insert</tt> Member Function Definitions<BR>
<P>
<P>
The function <tt>C</tt> defines the probing sequence.
As it turns out,
the implementation required for a linear probing sequence is trivial.
The function <tt>C</tt> is the identity function.
<P>
The purpose of the private member function <tt>FindUnoccupied</tt>
is to locate an unoccupied array position.
The <tt>FindUnoccupied</tt> routine probes the array
according the probing sequence determined by the <tt>C</tt> function.
At most <I>n</I>+1 probes are made,
where <IMG WIDTH=72 HEIGHT=9 ALIGN=BOTTOM ALT="tex2html_wrap_inline61308" SRC="img709.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img709.gif" > is the number of items in the scatter table.
When using linear probing it is always possible to find an unoccupied
cell in this many probes as long as the table is not full.
Notice also that we do not search for an <tt>empty</tt> cell.
Instead, the search terminates when a cell is found,
the state of which is not <tt>occupied</tt>,
i.e., <tt>empty</tt> or <tt>deleted</tt>.
The reason for this subtlety has to do with
the way items may be removed from the table.
The <tt>FindUnoccupied</tt> routine returns a value between 0 and <I>M</I>-1,
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 length of the scatter table,
if an unoccupied location is found.
Otherwise, it returns <I>M</I> to indicate that an unoccupied cell was not found.
<P>
The <tt>Insert</tt> routine takes a reference to an <tt>Object</tt>
and puts that object into the scatter table.
It does so by calling <tt>FindUnoccupied</tt> to
determine the location of an unoccupied entry in which to put the object.
The state of the unoccupied entry is set to <tt>occupied</tt>
and a pointer to the object is saved in the entry.
<P>
The running time of the <tt>Insert</tt> routine
is determined by that of <tt>FindUnoccupied</tt>.
The worst case running time of <tt>FindUnoccupied</tt> is <I>O</I>(<I>n</I>),
where <I>n</I> is the number of items in the scatter table.
Therefore,
the running time of <tt>Insert</tt> is <IMG WIDTH=132 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline62846" SRC="img981.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img981.gif" >.
<P>
<HR><A NAME="tex2html4923" HREF="page244.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page244.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="tex2html4921" 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="tex2html4915" HREF="page242.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page242.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="tex2html4925" 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="tex2html4926" 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 + -
显示快捷键?