?? page391.html
字號:
<HTML>
<HEAD>
<TITLE>Basic Operations</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="tex2html6763" HREF="page392.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page392.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="tex2html6761" HREF="page390.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page390.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="tex2html6755" HREF="page390.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page390.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="tex2html6765" 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="tex2html6766" 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="SECTION0013201000000000000000">Basic Operations</A></H3>
<P>
Program <A HREF="page391.html#progbitset1c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page391.html#progbitset1c"><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 constructor for the <tt>SetAsArray</tt>
class as well as the three basic operations--<tt>Insert</tt>, <tt>IsMember</tt>, and <tt>Withdraw</tt>.
The constructor takes a single argument
<IMG WIDTH=144 HEIGHT=11 ALIGN=BOTTOM ALT="tex2html_wrap_inline67308" SRC="img1608.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1608.gif" >,
which defines the universe and, consequently,
the size of the array of Boolean values.
The constructor creates the empty set by initializing
all the element of the Boolean array to <tt>false</tt>.
Clearly, the running time of the constructor is <I>O</I>(<I>N</I>).
<P>
<P><A NAME="28733"> </A><A NAME="progbitset1c"> </A> <IMG WIDTH=575 HEIGHT=506 ALIGN=BOTTOM ALT="program28266" SRC="img1610.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1610.gif" ><BR>
<STRONG>Program:</STRONG> <tt>SetAsArray</tt> Class Constructor, <tt>Insert</tt>, <tt>Withdraw</tt> and <tt>IsMember</tt> Member Function Definitions<BR>
<P>
<P>
The <tt>Insert</tt> function is used to put an item into the set.
The function takes a reference to an <tt>Object</tt> instance
which is assumed to be a <tt>Set::Element</tt>.
A dynamic cast is used to ensure that the object to be inserted is
of the correct type and to extract the integer value from that object.
Then the corresponding element of <tt>array</tt> is set to <tt>true</tt>
to indicate that the specified object has been added to the set.
Note that the set does not keep track of the actual object instance
that was inserted.
Therefore, the set cannot own contained objects.
Instead, objects that are inserted
are represented <em>implicitly</em> by array indices.
The running time of the <tt>Insert</tt> operation is <I>O</I>(1).
<P>
The <tt>IsMember</tt> function is used to test whether a given item
is an element of the set.
The semantics are somewhat subtle.
Since a set does not actually keep track of
the specific object instances that are inserted,
the membership test is based on the <em>value</em> of the argument.
Again, a dynamic cast is used to ensure that the argument is
of the correct type and to extract the integer value from that object.
The function simply returns the value of the appropriate
element of the <tt>array</tt>.
The running time of the <tt>IsMember</tt> operation is <I>O</I>(1).
<P>
The <tt>Withdraw</tt> member function is used to take an item out of a set.
The withdrawal operation is the opposite of insertion.
Instead of setting the appropriate array element to <tt>true</tt>,
it is set to <tt>false</tt>.
The running time of the <tt>Withdraw</tt>
is identical to that of <tt>Insert</tt>, viz., is <I>O</I>(1).
<P>
<HR><A NAME="tex2html6763" HREF="page392.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page392.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="tex2html6761" HREF="page390.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page390.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="tex2html6755" HREF="page390.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page390.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="tex2html6765" 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="tex2html6766" 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 + -