page406.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 80 行
HTML
80 行
<HTML><HEAD><TITLE>Implementation</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="tex2html5860" HREF="page407.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5858" HREF="page405.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5852" HREF="page405.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5862" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0012411000000000000000">Implementation</A></H3><P>Program <A HREF="page406.html#progpartitionAsForesta"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> introduces two classes--<tt>PartitionAsForest</tt>and the nested class <tt>PartitionTree</tt>.The latter is used to represent the individual elements or parts of a partitionand the former encapsulates all of the parts that make up a given partition.<P><P><A NAME="28799"> </A><A NAME="progpartitionAsForesta"> </A> <IMG WIDTH=575 HEIGHT=313 ALIGN=BOTTOM ALT="program28669" SRC="img1628.gif" ><BR><STRONG>Program:</STRONG> <tt>PartitionAsForest.PartitionTree</tt> class <tt>__init__</tt> method.<BR><P><P>The <tt>PartitionTree</tt> class extendsthe abstract <tt>Set</tt> classdefined in Program <A HREF="page388.html#progseta"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>as well as the abstract <tt>Tree</tt> classdefined in Program <A HREF="page267.html#progtreea"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.Since we are representing the parts of a partition using trees,it makes sense that they extend the <tt>Tree</tt> class.On the other hand, since a partition is a set of sets,we must derive the parts of a partition from the <tt>Set</tt> class.<P>The <tt>PartitionTree</tt> class has five instance attributes--<tt>_partition</tt>, <tt>_item</tt>, <tt>_parent</tt>,<tt>_rank</tt> and <tt>_count</tt>.Each instance of this class represents one node of a tree.The <tt>_partition</tt> instance attributerefers to the <tt>PartitionAsForest</tt> instancethat contains this tree.The <tt>_parent</tt> instance attribute refers to the parent of a given nodeand the <tt>_item</tt> instance attribute recordsthe element of the universal set that the given node represents.The <tt>rank</tt> attribute is optional.While it is not required in order to provide the basic functionality,as shown below, the <tt>_rank</tt> variable can be used in the implementation ofthe <tt>join</tt> operation to improvethe performance of subsequent <tt>find</tt> operations.Finally, the <tt>_count</tt> attribute is used to keep trackof the number of items in a given element of the partition.<P>Program <A HREF="page406.html#progpartitionAsForesta"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives the codefor the <tt>PartitionTree</tt> <tt>__init__</tt> method.The <tt>__init__</tt> method creates a tree comprised of a single node.It takes an argument which specifies the element of theuniversal set that the node is to represent.The <tt>parent</tt> instance attribute is set to <tt>None</tt>to indicate that the node has no parent.Consequently, the node is a root node.Finally, the <tt>rank</tt> instance attribute is initialized to zero.The running time of the <tt>__init__</tt> method is <I>O</I>(1).<P>Program <A HREF="page407.html#progpartitionAsForestb"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows the <tt>__init__</tt> method forthe <tt>PartitionAsForest</tt> class.The <tt>PartitionAsForest</tt> class represents a complete partition.The <tt>PartitionAsForest</tt> class extendsthe abstract <tt>Partition</tt> classdefined in Program <A HREF="page404.html#progpartitiona"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.The <tt>PartitionAsForest</tt> class containsthe instance attributes <tt>_array</tt>,which is an array <tt>PartitionTree</tt>s,and <tt>_count</tt>,which is used to record the number of elements in the partition.The <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif" > element of the array always refers to the tree nodethat contains element <I>i</I> of the universe.<P><HR><A NAME="tex2html5860" HREF="page407.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5858" HREF="page405.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5852" HREF="page405.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5862" 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 + -
显示快捷键?