page400.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 89 行
HTML
89 行
<HTML>
<HEAD>
<TITLE>Union, Intersection and Difference</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="tex2html6869" HREF="page401.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page401.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="tex2html6867" HREF="page398.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page398.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="tex2html6863" HREF="page399.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page399.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="tex2html6871" 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="tex2html6872" 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="SECTION0013312000000000000000">Union, Intersection and Difference</A></H3>
<P>
Because multisets permit duplicates but sets do not,
the definitions of union, intersection and difference
are slightly modified for multisets.
The <em>union</em><A NAME=28515> </A> of multisets <I>S</I> and <I>T</I>,
written <IMG WIDTH=39 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline67136" SRC="img1593.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1593.gif" >,
is the multiset comprised of all the elements of <I>S</I>
together with all the element of <I>T</I>.
Since a multiset may contain duplicates,
it does not matter if the same element appears in <I>S</I> and <I>T</I>.
<P>
The subtle difference between union of sets and union of multisets
gives rise to an interesting and useful property.
If <I>S</I> and <I>T</I> are regular sets,
<P> <IMG WIDTH=370 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath67448" SRC="img1634.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1634.gif" ><P>
On the other hand, if <I>S</I> and <I>T</I> are <em>multisets</em>,
<P> <IMG WIDTH=315 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath67449" SRC="img1635.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1635.gif" ><P>
<P>
The <em>intersection</em><A NAME=28518> </A> of sets <I>S</I> and <I>T</I>
is written <IMG WIDTH=39 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline67158" SRC="img1597.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1597.gif" >.
The elements of <IMG WIDTH=39 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline67158" SRC="img1597.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1597.gif" > are those items
which are elements of <em>both</em> <I>S</I> and <I>T</I>.
If a given element appears more than once in <I>S</I> or <I>T</I> (or both),
the intersection contains <I>m</I> copies of that element,
where <I>m</I> is the smaller of the number of times the element appears
in <I>S</I> or <I>T</I>.
E.g., if <IMG WIDTH=129 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67498" SRC="img1636.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1636.gif" > and <IMG WIDTH=101 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67500" SRC="img1637.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1637.gif" >,
the intersection is <IMG WIDTH=113 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67502" SRC="img1638.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1638.gif" >.
<P>
The <em>difference</em><A NAME=28521> </A> of sets <I>S</I> and <I>T</I>,
written <I>S</I>-<I>T</I>,
contains those elements of <I>S</I> which are <em>not also</em> elements of <I>T</I>.
I.e., the result <I>S</I>-<I>T</I> is obtained by taking the set <I>S</I>
and removing from it those elements which are also found in <I>T</I>.
<P>
Program <A HREF="page400.html#progmultiset2c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page400.html#progmultiset2c"><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
implementations of the union, intersection, and difference operators
(<tt>+</tt>, <tt>*</tt>, and <tt>-</tt>, respectively)
for operands of type <tt>MultisetAsArray</tt>.
This code is quite similar to that of
the <tt>SetAsArray</tt> class (Program <A HREF="page392.html#progbitset2c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page392.html#progbitset2c"><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>)
and the <tt>SetAsBitVector</tt> class (Program <A HREF="page395.html#progbitset4c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page395.html#progbitset4c"><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 worst-case running time of each of these operations is <I>O</I>(<I>N</I>).
<P>
<P><A NAME="28772"> </A><A NAME="progmultiset2c"> </A> <IMG WIDTH=575 HEIGHT=639 ALIGN=BOTTOM ALT="program28532" SRC="img1639.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1639.gif" ><BR>
<STRONG>Program:</STRONG> <tt>MultisetAsArray</tt> Class Union, Intersection and Difference Operator Definitions<BR>
<P>
<P>
Instead of using the Boolean operators <tt>&&</tt>, <tt>||</tt> and <tt>!</tt>,
we have used <tt>+</tt> (integer addition),
<tt>Min</tt> and <tt>-</tt> (integer subtraction).
The following table summarizes the operators used in the various
set and multiset implementations.
<DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=4 BORDER FRAME=HSIDES RULES=GROUPS>
<COL ALIGN=LEFT><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER>
<TBODY>
<TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>
</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP COLSPAN=3> class</TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>
<P>
operation </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <tt>SetAsArray</tt> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <tt>SetAsBitVector</tt>
</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <tt>MultisetAsArray</tt> </TD></TR>
</TBODY><TBODY>
<TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>union </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <tt>||</tt> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <tt>|</tt> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <tt>+</tt> </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>
intersection </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <tt>&&</tt> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <tt>&</tt> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <tt>Min</tt> </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>
difference </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <tt>&&</tt> and <tt>!</tt> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <tt>&</tt> and<tt></tt>
</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <tt><=</tt> and <tt>-</tt> </TD></TR>
</TBODY>
</TABLE>
</P></DIV><HR><A NAME="tex2html6869" HREF="page401.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page401.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="tex2html6867" HREF="page398.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page398.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="tex2html6863" HREF="page399.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page399.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="tex2html6871" 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="tex2html6872" 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 + -
显示快捷键?