page377.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 47 行
HTML
47 行
<HTML>
<HEAD>
<TITLE>AddTree and RemoveTree</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="tex2html6591" HREF="page378.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page378.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="tex2html6589" HREF="page373.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page373.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="tex2html6583" HREF="page376.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page376.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="tex2html6593" 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="tex2html6594" 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="SECTION0012434000000000000000"><tt>AddTree</tt> and <tt>RemoveTree</tt></A></H3>
<P>
The private member functions <tt>AddTree</tt> and <tt>RemoveTree</tt>
of the <tt>BinomialQueue</tt> class facilitate the implementation of
the various priority queue operations.
These functions are defined in Program <A HREF="page377.html#progbinom2c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page377.html#progbinom2c"><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 <tt>AddTree</tt> function takes a reference to a <tt>BinomialTree</tt>
and appends a pointer to that tree to <tt>list</tt>.
<tt>AddTree</tt> also adjusts the <tt>count</tt> in order to keep
track of the number of items in the priority queue.
It is assumed that the order of the tree which is added
is larger than all the others in the list and, therefore,
that it belongs at the end of the list.
The running time of <tt>AddTree</tt> is clearly <I>O</I>(1).
<P>
<P><A NAME="27714"> </A><A NAME="progbinom2c"> </A> <IMG WIDTH=575 HEIGHT=219 ALIGN=BOTTOM ALT="program27519" SRC="img1560.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1560.gif" ><BR>
<STRONG>Program:</STRONG> <tt>BinomialQueue</tt> Class <tt>AddTree</tt> and <tt>RemoveTree</tt> Member Function Definitions<BR>
<P>
<P>
The <tt>RemoveTree</tt> function takes a reference to a binomial tree
and removes it from the <tt>list</tt>.
It is assumed that the specified tree is actually in the list.
<tt>RemoveTree</tt> also adjust the <tt>count</tt> as required.
The running time of <tt>RemoveTree</tt> depends on the position of the
tree in the list.
A binomial queue which contains exactly <I>n</I> items altogether
has at most <IMG WIDTH=87 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline66948" SRC="img1561.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1561.gif" > binomial trees.
Therefore, the running time of <tt>RemoveTree</tt> is <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59891" SRC="img403.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img403.gif" >
in the worst case.
<P>
<HR><A NAME="tex2html6591" HREF="page378.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page378.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="tex2html6589" HREF="page373.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page373.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="tex2html6583" HREF="page376.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page376.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="tex2html6593" 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="tex2html6594" 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 + -
显示快捷键?