📄 page400.html
字号:
<HTML><HEAD><TITLE>Linked-List 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="tex2html5788" HREF="page401.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5786" HREF="page396.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5782" HREF="page399.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5790" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0012320000000000000000">Linked-List Implementation</A></H2><P>The array implementation of multisets is really only practicalif the number of items in the universe, <I>N</I>=|<I>U</I>|,is not too large.If <I>N</I> is large, then it is impractical,or at least extremely inefficient,to use an array of <I>N</I> counters to represent the multiset.This is especially so if the number of elements in the multisets is significantly less than <I>N</I>.<P>If we use a linked list of elements to represent a multiset <I>S</I>,the space required is proportional to the size of the multiset, |<I>S</I>|.When the size of the multiset is significantly less thanthe size of the universe, <IMG WIDTH=64 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66917" SRC="img1593.gif" >,it is more efficient in terms of both time and space to use a linked list.<P>Program <A HREF="page400.html#progmultisetAsLinkedLista"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> introduces thethe <tt>MultisetAsLinkedList</tt> class.The <tt>MultisetAsLinkedList</tt> extends thethe abstract <tt>Multiset</tt> classdefined in Program <A HREF="page396.html#progmultiseta"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.In this case a linked list of <tt>int</tt>sis used to record the contents of the multiset.<P>How should the elements of the multiset be stored in the list?Perhaps the simplest way is to store the elements in the listin no particular order.Doing so makes the <tt>insert</tt> operation efficient--it can be done in constant time.Furthermore, the <tt>__contains__</tt> and <tt>withdraw</tt> operationsboth take <I>O</I>(<I>n</I>) time,where <I>n</I> is the number of items in the multiset,<EM>regardless of the order of the items in the linked list</EM>.<P>Consider now the union, intersection, and difference of two multisets,say <I>S</I> and <I>T</I>.If the linked list is unordered,the worst case running time for the union operation is <I>O</I>(<I>m</I>+<I>n</I>),where <I>m</I>=|<I>S</I>| and <I>n</I>=|<I>T</I>|.Unfortunately, intersection, and difference are both <I>O</I>(<I>mn</I>).<P>If, on the other hand,we use an <em>ordered</em> linked list,union, intersection, and difference can all be done in <I>O</I>(<I>m</I>+<I>n</I>) time.The trade-off is that the insertion becomes an <I>O</I>(<I>n</I>) operationrather than a <I>O</I>(1).The <tt>MultisetAsLinkedList</tt> implementation presented in thissection records the elements of the multisetin an <em>ordered</em> linked list.<P><P><A NAME="28249"> </A><A NAME="progmultisetAsLinkedLista"> </A> <IMG WIDTH=575 HEIGHT=142 ALIGN=BOTTOM ALT="program28058" SRC="img1594.gif" ><BR><STRONG>Program:</STRONG> <tt>MultisetAsLinkedList</tt> class <tt>__init__</tt> method.<BR><P><BR> <HR><UL> <LI> <A NAME="tex2html5791" HREF="page401.html#SECTION0012321000000000000000">Union</A><LI> <A NAME="tex2html5792" HREF="page402.html#SECTION0012322000000000000000">Intersection</A></UL><HR><A NAME="tex2html5788" HREF="page401.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5786" HREF="page396.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5782" HREF="page399.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5790" 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 + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -