page406.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 68 行
HTML
68 行
<HTML>
<HEAD>
<TITLE>Implementing a Partition using a Forest</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="tex2html6942" HREF="page407.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page407.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="tex2html6940" HREF="page404.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page404.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="tex2html6934" HREF="page405.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page405.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="tex2html6944" 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="tex2html6945" 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>
<H2><A NAME="SECTION0013410000000000000000">Implementing a Partition using a Forest</A></H2>
<A NAME="secsetspforest"> </A>
<P>
A partition is a set of sets.
Consequently, there are two related issues to consider
when developing an approach for representing partitions:
<OL><LI> How are the individual elements
or parts of the partition represented?<LI> How are the elements of a partition combined into the whole?
</OL>
This section presents an approach in which
each element of a partition is a tree.
Therefore, the whole partition is a <em>forest</em><A NAME=28705> </A>.
<P>
For example, Figure <A HREF="page406.html#figsets1" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page406.html#figsets1"><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> shows how the partition
<P> <IMG WIDTH=500 HEIGHT=40 ALIGN=BOTTOM ALT="eqnarray28707" SRC="img1670.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1670.gif" ><P>
can be represented using a forest.
Notice that each element of the universal set <IMG WIDTH=125 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67670" SRC="img1671.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1671.gif" >
appears in exactly one node of exactly one tree.
<P>
<P><A NAME="28929"> </A><A NAME="figsets1"> </A> <IMG WIDTH=575 HEIGHT=206 ALIGN=BOTTOM ALT="figure28709" SRC="img1672.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1672.gif" ><BR>
<STRONG>Figure:</STRONG> Representing a Partition as a Forest<BR>
<P>
<P>
The trees in Figure <A HREF="page406.html#figsets1" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page406.html#figsets1"><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> have some very interesting characteristics.
The first characteristic concerns the shapes of the trees:
The nodes of the trees have arbitrary degrees.
The second characteristic concerns the positions of the keys:
there are no constraints on the positions of the keys in a tree.
The final characteristic has to do with the way the tree is represented:
Instead of pointers to its children,
each node of a tree contains only one pointer--a pointer to its parent!
<P>
Since there is no particular order to the nodes in the trees,
it is necessary to keep track of the position of each node explicitly.
Figure <A HREF="page406.html#figsets2" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page406.html#figsets2"><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> shows how this can be done using an array of pointers.
(This figure shows the same partition as in Figure <A HREF="page406.html#figsets1" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page406.html#figsets1"><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 array contains a pointer for each element of the universal set <I>U</I>.
Specifically, the <IMG WIDTH=17 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline58387" SRC="img77.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img77.gif" > array element contains a pointer
to the node that contains item <I>i</I>.
Having found the desired node,
we can follow the chain of parent pointers
to find the root of the corresponding tree.
<P>
<P><A NAME="29189"> </A><A NAME="figsets2"> </A> <IMG WIDTH=575 HEIGHT=196 ALIGN=BOTTOM ALT="figure28936" SRC="img1673.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1673.gif" ><BR>
<STRONG>Figure:</STRONG> Finding the Elements of a Partition<BR>
<P><BR> <HR>
<UL>
<LI> <A NAME="tex2html6946" HREF="page407.html#SECTION0013411000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page407.html#SECTION0013411000000000000000">Implementation</A>
<LI> <A NAME="tex2html6947" HREF="page408.html#SECTION0013412000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page408.html#SECTION0013412000000000000000">Constructors and Destructor</A>
<LI> <A NAME="tex2html6948" HREF="page409.html#SECTION0013413000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page409.html#SECTION0013413000000000000000"><tt>Find</tt> and <tt>Join</tt> Member Functions</A>
</UL>
<HR><A NAME="tex2html6942" HREF="page407.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page407.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="tex2html6940" HREF="page404.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page404.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="tex2html6934" HREF="page405.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page405.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="tex2html6944" 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="tex2html6945" 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 + -
显示快捷键?