📄 page351.html
字号:
<HTML>
<HEAD>
<TITLE>Projects</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="tex2html6257" HREF="page352.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page352.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="tex2html6255" HREF="page299.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page299.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="tex2html6251" HREF="page350.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page350.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="tex2html6259" 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="tex2html6260" 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>
<H1><A NAME="SECTION00111000000000000000000">Projects</A></H1>
<P>
<OL><LI> <A NAME="projectsrchtreebst"> </A>
Complete the implementation of the <tt>BST</tt> class
declared in Program <A HREF="page312.html#progbst1h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page312.html#progbst1h"><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>
by providing suitable definitions for the following member functions:
<tt>IsMember</tt> and <tt>FindMax</tt>.
You must also have a complete implementation of the base class
<tt>BinaryTree</tt>.
(See Project <A HREF="page298.html#projecttreesbintree" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page298.html#projecttreesbintree"><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>).
Write a test program and test your implementation.<LI>
Complete the implementation of the <tt>AVLTree</tt> class
declared in Program <A HREF="page321.html#progavl1h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page321.html#progavl1h"><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>
by providing suitable definitions for the following member functions:
<tt>Left</tt>, <tt>Right</tt>, <tt>RRRotation</tt> and <tt>RLRotation</tt>.
You must also have a complete implementation of the base class
<tt>BST</tt>.
(See Project <A HREF="page351.html#projectsrchtreebst" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page351.html#projectsrchtreebst"><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>).
Write a test program and test your implementation.<LI> <A NAME="projectsrchtreemwaytree"> </A>
Complete the implementation of the <tt>MWayTree</tt> class
declared in Program <A HREF="page332.html#progmwaytree1h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page332.html#progmwaytree1h"><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>
by providing suitable definitions for the following member functions:
<tt>MWayTree</tt> (constructor),
<tt>MWayTree</tt> (destructor), <tt>Purge</tt>,
<tt>Count</tt>, <tt>IsEmpty</tt>, <tt>IsLeaf</tt>, <tt>Degree</tt>,
<tt>Key</tt>, <tt>Subtree</tt>,
<tt>IsMember</tt>, <tt>FindMin</tt>, <tt>FindMax</tt>,
<tt>BreadthFirstTraversal</tt> and <tt>NewIterator</tt>.
Write a test program and test your implementation.<LI>
Complete the implementation of the <tt>BTree</tt> class
declared in Program <A HREF="page341.html#progbtree1h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page341.html#progbtree1h"><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>
by providing suitable definitions for the following member functions:
<tt>BTree</tt>, <tt>InsertKey</tt>, <tt>InsertSubtree</tt>,
<tt>AttachKey</tt>, <tt>AttachSubtree</tt>, <tt>AttachLeftHalfOf</tt>,
<tt>AttachRightHalfOf</tt> and <tt>Withdraw</tt>.
You must also have a complete implementation of the base class
<tt>MWayTree</tt>.
(See Project <A HREF="page351.html#projectsrchtreemwaytree" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page351.html#projectsrchtreemwaytree"><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>).
Write a test program and test your implementation.<LI>
The binary search tree <tt>Withdraw</tt> routine
shown in Program <A HREF="page319.html#progbst4c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page319.html#progbst4c"><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> is biased in the following way:
If the key to be deleted is in a non-leaf node with
two non-empty subtrees,
the key is swapped with the maximum key in the left subtree
and then recursively deleted from the left subtree.
Following a long series of insertions and deletions,
the search tree will tend to have more nodes in the right
subtrees and fewer nodes in the left subtrees.
Devise and conduct an experiment that demonstrates this phenomenon.<LI>
Consider the implementation of AVL trees.
In order to check the AVL balance condition in constant time,
we record in each node the height of that node.
An alternative to keeping track of the height information explicitly
is to record in each node the <em>difference</em> in the heights
of its two subtrees.
In an AVL balanced tree,
this difference is either -1, 0 or +1.
Replace the <tt>height</tt> member variable of the AVL class
defined in Program <A HREF="page321.html#progavl1h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page321.html#progavl1h"><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> with one called <tt>diff</tt>
and rewrite the various member functions accordingly.<LI>
The <I>M</I>-way tree implementation given in Section <A HREF="page331.html#secsrchtreemwayimpl" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page331.html#secsrchtreemwayimpl"><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>
is an <em>internal</em> data structure--it is assumed that all the nodes reside in the main memory.
However, the motivation for using an <I>M</I>-way tree is that
it is an efficient way to organize an <em>external</em>
data structure--one that is stored on disk.
Design, implement and test an external <I>M</I>-way tree implementation.
</OL>
<P>
<HR><A NAME="tex2html6257" HREF="page352.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page352.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="tex2html6255" HREF="page299.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page299.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="tex2html6251" HREF="page350.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page350.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="tex2html6259" 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="tex2html6260" 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 + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -