page105.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 76 行
HTML
76 行
<HTML>
<HEAD>
<TITLE>Exercises</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="tex2html3202" HREF="page106.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page106.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="tex2html3200" HREF="page79.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page79.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="tex2html3194" HREF="page104.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page104.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="tex2html3204" 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="tex2html3205" 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="SECTION005400000000000000000">Exercises</A></H1>
<P>
<OL><LI>
<OL><LI>
How much space does the <tt>Array<T></tt> class
declared in Program <A HREF="page80.html#progarrayh" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page80.html#progarrayh"><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> use for
an array of integers of length <I>N</I>?<LI>
How much space does the <tt>LinkedList<T></tt> class
declared in Program <A HREF="page89.html#proglinklist1h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page89.html#proglinklist1h"><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> use to store
a list of <I>n</I> integers?<LI>
For what value of <I>N</I>/<I>n</I> do the two classes use
the same amount of space?
</OL><LI>
The array subscripting operators defined in Program <A HREF="page86.html#progarray6c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page86.html#progarray6c"><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>
only test whether <IMG WIDTH=120 HEIGHT=21 ALIGN=MIDDLE ALT="tex2html_wrap_inline61255" SRC="img670.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img670.gif" >,
the do not test whether <IMG WIDTH=67 HEIGHT=10 ALIGN=BOTTOM ALT="tex2html_wrap_inline61257" SRC="img671.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img671.gif" >.
Explain why the second test is not required in this implementation.<LI>
The <tt>SetBase</tt> member function of the <tt>Array<T></tt> class
defined in Program <A HREF="page85.html#progarray5c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page85.html#progarray5c"><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> simply changes the value
of the <tt>base</tt> member variable.
As a result, after the base is changed,
all the array elements appear to have moved.
How might the routine be modified so that the elements of the array
don't change their apparent locations when the base is changed?<LI>
Write the C++ code for the
assignment operator of the <tt>Array<T></tt> class
declared in Program <A HREF="page80.html#progarrayh" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page80.html#progarrayh"><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>
Which routines are affected if we drop the <tt>tail</tt> member
variable from the <tt>LinkedList<T></tt> class declared in
Program <A HREF="page89.html#proglinklist1h" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page89.html#proglinklist1h"><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>?
Determine new running times for the affected routines.<LI>
How does the implementation of the <tt>Prepend</tt> function
of the <tt>LinkedList<T></tt> class defined in Program <A HREF="page95.html#proglinklist5c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page95.html#proglinklist5c"><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>
change when a circular list with a
sentinel is used as shown in Figure <A HREF="page88.html#figlinklist1" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page88.html#figlinklist1"><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> (c).<LI>
How does the implementation of the <tt>Append</tt> function
of the <tt>LinkedList<T></tt> class defined in Program <A HREF="page96.html#proglinklist6c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page96.html#proglinklist6c"><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>
change when a circular list with a
sentinel is used as shown in Figure <A HREF="page88.html#figlinklist1" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page88.html#figlinklist1"><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> (c).<LI>
Consider the assignment operator for the <tt>LinkedList<T></tt> class
given in Program <A HREF="page97.html#proglinklist7c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page97.html#proglinklist7c"><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>.
What is the purpose of the test <tt>&linkedlist != this</tt>
on line 15?<LI>
Equation <A HREF="page101.html#eqnfdsaddress" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page101.html#eqnfdsaddress"><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 only correct if the subscript
ranges in each dimension start at zero.
How does the formula change when each dimension
is allowed to have an arbitrary subscript range?<LI>
The alternative to <em>row-major</em> layout of of multi-dimensional
arrays is called <em>column-major order</em><A NAME=4237> </A>.
In column-major layout the leftmost subscript
expression increases fastest.
For example, the elements of the columns of a two-dimensional matrix
end up stored in contiguous memory locations.
Modify Equation <A HREF="page101.html#eqnfdsaddress" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page101.html#eqnfdsaddress"><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> to compute the correct address
for column-major layout.<LI>
We wish to add an <tt>operator+</tt> member function to the
<tt>Matrix<T></tt> class declared in Program <A HREF="page104.html#progmatrixh" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page104.html#progmatrixh"><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>
that does the usual matrix addition.
Write the C++ code for this member function.
</OL><HR><A NAME="tex2html3202" HREF="page106.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page106.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="tex2html3200" HREF="page79.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page79.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="tex2html3194" HREF="page104.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page104.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="tex2html3204" 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="tex2html3205" 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 + -
显示快捷键?