📄 page187.html
字号:
<HTML>
<HEAD>
<TITLE>Applications</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="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> <BR><HR>
<H2><A NAME="SECTION008140000000000000000">Applications</A></H2>
<A NAME="seclistsapp1"> </A>
<P>
The applications of lists and ordered lists are myriad.
In this section we will consider only one--the use of an ordered list to represent a polynomial.
In general, 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 in <I>x</I>,
for non-negative integer <I>n</I>, has the form
<P> <IMG WIDTH=387 HEIGHT=43 ALIGN=BOTTOM ALT="displaymath61822" SRC="img815.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img815.gif" ><P>
where <IMG WIDTH=45 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline61842" SRC="img816.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img816.gif" >.
The term <IMG WIDTH=11 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline58389" SRC="img78.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img78.gif" > is the <em>coefficient</em> of the <IMG WIDTH=17 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline58387" SRC="img77.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img77.gif" > power of <I>x</I>.
We shall assume that the coefficients are real numbers.
I.e., <IMG WIDTH=93 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline61850" SRC="img817.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img817.gif" >, <IMG WIDTH=44 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline61852" SRC="img818.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img818.gif" >.
<P>
An alternative representation for such a polynomial consists
of a sequence of ordered pairs:
<P> <IMG WIDTH=375 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath61823" SRC="img819.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img819.gif" ><P>
Each ordered pair, <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" >,
corresponds to the term <IMG WIDTH=26 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline61856" SRC="img821.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img821.gif" > of the polynomial.
I.e., the ordered pair is comprised of the coefficient of the <IMG WIDTH=17 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline58387" SRC="img77.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img77.gif" > term
together with the subscript of that term, <I>i</I>.
For example, the polynomial <IMG WIDTH=110 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline61862" SRC="img822.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img822.gif" >
can be represented by the sequence <IMG WIDTH=158 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61864" SRC="img823.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img823.gif" >.
<P>
Consider now the <IMG WIDTH=35 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline61866" SRC="img824.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img824.gif" >-order polynomial <IMG WIDTH=55 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline61868" SRC="img825.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img825.gif" >.
Clearly, there are only two nonzero coefficients:
<IMG WIDTH=56 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline61870" SRC="img826.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img826.gif" > and <IMG WIDTH=44 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline61872" SRC="img827.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img827.gif" >.
The advantage of using the sequence of ordered pairs to represent
such a polynomial is that we can omit from the sequence
those pairs that have a zero coefficient.
We represent the polynomial <IMG WIDTH=55 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline61868" SRC="img825.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img825.gif" > by the sequence <IMG WIDTH=107 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61876" SRC="img828.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img828.gif" >
<P>
Now that we have a way to represent polynomials,
we can consider various operations on them.
For example, consider the polynomial
<P> <IMG WIDTH=304 HEIGHT=43 ALIGN=BOTTOM ALT="displaymath61824" SRC="img829.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img829.gif" ><P>
We can compute its <em>derivative</em><A NAME=10390> </A> with respect to <I>x</I>
by <em>differentiating</em><A NAME=10392> </A>
each of the terms to get
<P> <IMG WIDTH=307 HEIGHT=46 ALIGN=BOTTOM ALT="displaymath61825" SRC="img830.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img830.gif" ><P>
where <IMG WIDTH=109 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline61880" SRC="img831.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img831.gif" >.
In terms of the corresponding sequences,
if <I>p</I>(<I>x</I>) is represented by the sequence
<P> <IMG WIDTH=410 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath61826" SRC="img832.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img832.gif" ><P>
then its derivative is the sequence
<P> <IMG WIDTH=450 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath61827" SRC="img833.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img833.gif" ><P>
<P>
This result suggests a very simple algorithm to differentiate
a polynomial which is represented by a sequence of ordered pairs:
<OL><LI> Drop the ordered pair that has a zero exponent.<LI> For every other ordered pair,
multiply the coefficient by the exponent,
and then subtract one from the exponent.
</OL>
Since the representation of 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
has at most <I>n</I>+1 ordered pairs,
and since a constant amount of work is necessary for each ordered pair,
this is inherently an <IMG WIDTH=32 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60685" SRC="img529.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img529.gif" > algorithm.
<P>
Of course, the worst-case running time of the polynomial differentiation
will depend on the way that the sequence of ordered pairs is implemented.
We will now consider an implementation that makes use of the <tt>ListAsLinkedList</tt>
pointer-based implementation of ordered lists.
To begin with, we need a class to represent the terms of the polynomial.
Program <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 definition of
the <tt>Term</tt> class and several of its member functions.
<P>
<P><A NAME="10572"> </A><A NAME="progapp03ac"> </A> <IMG WIDTH=575 HEIGHT=676 ALIGN=BOTTOM ALT="program10402" SRC="img834.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img834.gif" ><BR>
<STRONG>Program:</STRONG> <tt>Term</tt> Class Definition<BR>
<P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -