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 -order polynomial in x,
for non-negative integer n, has the form
where .
The term
is the coefficient of the
power of x.
We shall assume that the coefficients are real numbers.
I.e.,
,
.
An alternative representation for such a polynomial consists of a sequence of ordered pairs:
Each ordered pair, ,
corresponds to the term
of the polynomial.
I.e., the ordered pair is comprised of the coefficient of the
term
together with the subscript of that term, i.
For example, the polynomial
can be represented by the sequence
.
Consider now the -order polynomial
.
Clearly, there are only two nonzero coefficients:
and
.
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
by the sequence
Now that we have a way to represent polynomials, we can consider various operations on them. For example, consider the polynomial
We can compute its derivative with respect to x by differentiating each of the terms to get
where .
In terms of the corresponding sequences,
if p(x) is represented by the sequence
then its derivative is the sequence
This result suggests a very simple algorithm to differentiate a polynomial which is represented by a sequence of ordered pairs:
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 ListAsLinkedList
pointer-based implementation of ordered lists.
To begin with, we need a class to represent the terms of the polynomial.
Program gives the definition of
the Term class and several of its member functions.
Program: Term Class Definition
Each Term instance has two member variables, coefficient and exponent, which correspond to the elements of the ordered pair as discussed above. The former is a double and the latter, an unsigned int.
The Term class is derived from the Object class
instances of the Term class will be put into a container.
Program gives the definitions of three
member functions:
a constructor, CompareTo, and Differentiate.
The constructor simply takes a pair of arguments and
initializes the corresponding member variables accordingly.
The CompareTo function is used to compare two Term instances.
Consider two terms , and
.
We define the relation
on terms of a polynomial as follows:
Note that the relation does not depend on the value of the variable x.
Finally, the Differentiate function does what its name says:
It differentiates a term with respect to x.
Given a term such as , it computes the result (0,0);
and given a term such as
where i>0,
it computes the result
.
We now consider the representation of a polynomial using an ordered list.
Program gives the definition of the class Polynomial
which is derived in this case from the ListAsLinkedList class.
In this example, the pointer-based implementation of lists is used.
Program: Polynomial Class Definition
Program defines the member function Differentiate
which has the effect of changing the polynomial to its
derivative with respect to x.
To compute this derivative,
it is necessary to call the Differentiate member function
of the Term class for each term in the polynomial.
Since the polynomial is implemented as a container,
there is an Accept 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, DifferentiatingVisitor,
which assumes its argument is an instance of the Term class
and differentiates it.
After the terms in the polynomial have been differentiated,
it is necessary to check for the term (0,0)
which arises from differentiating .
The Find member function is used to locate the term,
and if one is found the Withdraw function is used to remove it.
The analysis of the running time
of the Polynomial::Differentiate function is straightforward.
The running time of Term::Differentiate is clearly O(1).
So too is the running time of the function the Visit
member function of the DifferentiatingVisitor.
The latter function is called once for each contained object.
In the worst case, given an -order polynomial,
there are n+1 terms.
Therefore, the time required to differentiate the terms is O(n).
Locating the zero term is O(n) in the worst case,
and so too is deleting it.
Therefore, the total running time required to differentiate
a
-order polynomial is O(n).