📄 page298.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="tex2html5603" HREF="page299.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page299.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="tex2html5601" HREF="page250.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page250.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="tex2html5597" HREF="page297.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page297.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="tex2html5605" 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="tex2html5606" 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="SECTION0010800000000000000000">Projects</A></H1>
<P>
<OL><LI>
Devise an algorithm to compute the height of a tree.
Write an implementation of your algorithm
as the <tt>Height</tt> member function of the abstract class <tt>Tree</tt>
declared in Program <A HREF="page266.html#progtree1h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page266.html#progtree1h"><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>.<LI>
Devise an algorithm to count the number of internal nodes in a tree.
Write an implementation of your algorithm
as the <tt>Count</tt> member function of the abstract class <tt>Tree</tt>
declared in Program <A HREF="page266.html#progtree1h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page266.html#progtree1h"><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>.<LI>
Devise an algorithm to count the number of leaves in a tree.
Write an implementation of your algorithm
as a member function of the abstract class <tt>Tree</tt>
declared in Program <A HREF="page266.html#progtree1h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page266.html#progtree1h"><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>.<LI>
Devise an abstract (generic) algorithm to compare trees.
(See Exercise <A HREF="page297.html#exercisetreescompare" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page297.html#exercisetreescompare"><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 an implementation of your algorithm
as the <tt>CompareTo</tt> member function
of the abstract class <tt>Tree</tt>
declared in Program <A HREF="page266.html#progtree1h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page266.html#progtree1h"><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>.<LI>
The <tt>Tree::Iter</tt> class defined in
Programs <A HREF="page273.html#progtree2h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page273.html#progtree2h"><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>, <A HREF="page274.html#progtree4c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page274.html#progtree4c"><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> and <A HREF="page275.html#progtree5c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page275.html#progtree5c"><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>
does a <em>preorder</em> traversal of a tree.
<OL><LI>
Write an iterator class that does
a <em>postorder</em> traversal.<LI>
Write an iterator class that does
a <em>breadth-first</em> traversal.<LI>
Write an iterator class that does
an <em>inorder</em> traversal.
(In this case,
assume that the tree is a <tt>BinaryTree</tt>).
</OL><LI> <A NAME="projecttreesgentree"> </A>
Complete the <tt>GeneralTree</tt> class
declared in Program <A HREF="page276.html#proggentree1h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page276.html#proggentree1h"><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>IsEmpty</tt>, <tt>IsLeaf</tt>, <tt>Degree</tt> and <tt>CompareTo</tt>.
Write a test program and test your implementation.<LI>
Complete the <tt>NaryTree</tt> class
declared in Program <A HREF="page282.html#prognarytree1h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page282.html#prognarytree1h"><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>NaryTree</tt> (destructor), <tt>Purge</tt>,
<tt>IsLeaf</tt>, <tt>Degree</tt> and <tt>CompareTo</tt>.
Write a test program and test your implementation.<LI> <A NAME="projecttreesbintree"> </A>
Complete the <tt>BinaryTree</tt> class
declared in Program <A HREF="page289.html#progbintree1h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page289.html#progbintree1h"><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>IsEmpty</tt>, <tt>IsLeaf</tt>, <tt>Degree</tt>,
<tt>Key</tt>, <tt>AttachKey</tt>, <tt>DetachKey</tt>,
<tt>Left</tt>, <tt>AttachLeft</tt>, <tt>DetachLeft</tt>,
<tt>Right</tt>, <tt>AttachRight</tt>,
<tt>DetachRight</tt> and <tt>Subtree</tt>.
Write a test program and test your implementation.<LI>
Write a visitor that draws a picture of a tree on the screen.<LI>
Design and implement an algorithm that constructs an expression tree
from an <em>infix</em> expression such as
<P> <IMG WIDTH=297 HEIGHT=13 ALIGN=BOTTOM ALT="displaymath64356" SRC="img1218.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1218.gif" ><P>
<b>Hint</b>: See Project <A HREF="page165.html#projectstacksconvert" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page165.html#projectstacksconvert"><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>.
</OL>
<P>
<HR><A NAME="tex2html5603" HREF="page299.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page299.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="tex2html5601" HREF="page250.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page250.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="tex2html5597" HREF="page297.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page297.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="tex2html5605" 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="tex2html5606" 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 + -