page187.html

wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq

<P>
Each <tt>Term</tt> instance has two member variables,
<tt>coefficient</tt> and <tt>exponent</tt>,
which correspond to the elements of the ordered pair as discussed above.
The former is a <tt>double</tt> and the latter, an <tt>unsigned int</tt>.
<P>
The <tt>Term</tt> class is derived from the <tt>Object</tt> class
instances of the <tt>Term</tt> class will be put into a container.
Program&nbsp;<A HREF="page187.html#progapp03ac" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page187.html#progapp03ac"><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> gives the definitions of three
member functions:
a constructor, <tt>CompareTo</tt>, and <tt>Differentiate</tt>.
The constructor simply takes a pair of arguments and
initializes the corresponding member variables accordingly.
<P>
The <tt>CompareTo</tt> function is used to compare two <tt>Term</tt> instances.
Consider two terms ,  <IMG WIDTH=21 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline61890" SRC="img835.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img835.gif"  > and  <IMG WIDTH=20 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline61892" SRC="img836.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img836.gif"  >.
We define the relation  <IMG WIDTH=10 HEIGHT=19 ALIGN=MIDDLE ALT="tex2html_wrap_inline61894" SRC="img837.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img837.gif"  > on terms of a polynomial as follows:
<P> <IMG WIDTH=384 HEIGHT=19 ALIGN=BOTTOM ALT="displaymath61828" SRC="img838.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img838.gif"  ><P>
Note that the relation  <IMG WIDTH=10 HEIGHT=19 ALIGN=MIDDLE ALT="tex2html_wrap_inline61894" SRC="img837.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img837.gif"  > does not depend on the value of the variable <I>x</I>.
<P>
Finally, the <tt>Differentiate</tt> function does what its name says:
It differentiates a term with respect to <I>x</I>.
Given a term such as  <IMG WIDTH=42 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61902" SRC="img839.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img839.gif"  >, it computes the result (0,0);
and given a term such as  <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61854" SRC="img820.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img820.gif"  > where <I>i</I><I>&gt;</I>0,
it computes the result  <IMG WIDTH=70 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61910" SRC="img840.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img840.gif"  >.
<P>
We now consider the representation of a polynomial using an ordered list.
Program&nbsp;<A HREF="page187.html#progapp03bc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page187.html#progapp03bc"><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> gives the definition of the class <tt>Polynomial</tt>
which is derived in this case from the <tt>ListAsLinkedList</tt> class.
In this example, the pointer-based implementation of lists is used.
<P>
<P><A NAME="10580">&#160;</A><A NAME="progapp03bc">&#160;</A> <IMG WIDTH=575 HEIGHT=524 ALIGN=BOTTOM ALT="program10438" SRC="img841.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img841.gif"  ><BR>
<STRONG>Program:</STRONG> <tt>Polynomial</tt> Class Definition<BR>
<P>
<P>
Program&nbsp;<A HREF="page187.html#progapp03bc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page187.html#progapp03bc"><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> defines the member function <tt>Differentiate</tt>
which has the effect of changing the polynomial to its
derivative with respect to <I>x</I>.
To compute this derivative,
it is necessary to call the <tt>Differentiate</tt> member function
of the <tt>Term</tt> class for each term in the polynomial.
Since the polynomial is implemented as a container,
there is an <tt>Accept</tt> member function which can be used
to perform a given operation on all of the objects in that container.
In this case, we define a visitor, <tt>DifferentiatingVisitor</tt>,
which assumes its argument is an instance of the <tt>Term</tt> class
and differentiates it.
<P>
After the terms in the polynomial have been differentiated,
it is necessary to check for the term (0,0)
which arises from differentiating  <IMG WIDTH=42 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61902" SRC="img839.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img839.gif"  >.
The <tt>Find</tt> member function is used to locate the term,
and if one is found the <tt>Withdraw</tt> function is used to remove it.
<P>
The analysis of the running time
of the <tt>Polynomial::Differentiate</tt> function is straightforward.
The running time of <tt>Term::Differentiate</tt> is clearly <I>O</I>(1).
So too is the running time of the function the <tt>Visit</tt>
member function of the <tt>DifferentiatingVisitor</tt>.
The latter function is called once for each contained object.
In the worst case, given an  <IMG WIDTH=21 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline58453" SRC="img94.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img94.gif"  >-order polynomial,
there are <I>n</I>+1 terms.
Therefore, the time required to differentiate the terms is <I>O</I>(<I>n</I>).
Locating the zero term is <I>O</I>(<I>n</I>) in the worst case,
and so too is deleting it.
Therefore, the total running time required to differentiate
a  <IMG WIDTH=21 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline58453" SRC="img94.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img94.gif"  >-order polynomial is <I>O</I>(<I>n</I>).
<P>
<HR><A NAME="tex2html4221" HREF="page188.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page188.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="tex2html4219" HREF="page167.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page167.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="tex2html4215" HREF="page186.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page186.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="tex2html4223" 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="tex2html4224" 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 &#169; 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>