page405.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 68 行
HTML
68 行
<HTML><HEAD><TITLE>Implementing a Partition using a Forest</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html5846" HREF="page406.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5844" HREF="page403.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5838" HREF="page404.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5848" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0012410000000000000000">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 considerwhen 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 whicheach element of a partition is a tree.Therefore, the whole partition is a <em>forest</em><A NAME=28182> </A>.<P>For example, Figure <A HREF="page405.html#figsets1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows how the partition<P> <IMG WIDTH=500 HEIGHT=42 ALIGN=BOTTOM ALT="eqnarray28184" SRC="img1624.gif" ><P>can be represented using a forest.Notice that each element of the universal set <IMG WIDTH=123 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67059" SRC="img1625.gif" >appears in exactly one node of exactly one tree.<P><P><A NAME="28402"> </A><A NAME="figsets1"> </A> <IMG WIDTH=575 HEIGHT=209 ALIGN=BOTTOM ALT="figure28186" SRC="img1626.gif" ><BR><STRONG>Figure:</STRONG> Representing a partition as a forest.<BR><P><P>The trees in Figure <A HREF="page405.html#figsets1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../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 pointing to its children,each node of the tree points 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="page405.html#figsets2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows how this can be done using an array.(This figure shows the same partition as in Figure <A HREF="page405.html#figsets1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).The array contains a node for each element of the universal set <I>U</I>.Specifically, the <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif" > array element holdsthe node that contains item <I>i</I>.Having found the desired node,we can follow the chain of parent pointersto find the root of the corresponding tree.<P><P><A NAME="28662"> </A><A NAME="figsets2"> </A> <IMG WIDTH=575 HEIGHT=194 ALIGN=BOTTOM ALT="figure28409" SRC="img1627.gif" ><BR><STRONG>Figure:</STRONG> Finding the elements of a partition.<BR><P><BR> <HR><UL> <LI> <A NAME="tex2html5849" HREF="page406.html#SECTION0012411000000000000000">Implementation</A><LI> <A NAME="tex2html5850" HREF="page407.html#SECTION0012412000000000000000"><tt>__init__</tt> Method</A><LI> <A NAME="tex2html5851" HREF="page408.html#SECTION0012413000000000000000"><tt>find</tt> and <tt>join</tt> Methods</A></UL><HR><A NAME="tex2html5846" HREF="page406.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5844" HREF="page403.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5838" HREF="page404.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5848" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?