Dear Student XYZ,

NOW I UNDERSTAND  W H Y  you are having such difficulty...   Thank you !!
Thanks because I believe that your difficulty most likely is also being
experienced by MANY students in the class...  Perhaps most students...

1. When you attempt to DESIGN something, you need to look at it from a
"high level"  -- that is, you need to think about the ADT(s) that might
be involved.

2. You must NOT work on the particulars of the implementation!!   

3. And, the Java details are where "your head is at."   And, that's the
problem....

4. Now, that is not to say that you can't use Java as a "language" to help
you say what you mean...   Of course you can...   And, probably should --
IF IT HELPS and doesn't HINDER...    

5. Now, in the "design" (I say "design" quite loosely, since it is NOT a
design that works -- and it's far too tied to Java) below, your first 
paragraph is good...  You tell me that your Poly is an ADT, one of whose
data members is a Term...  And you show me what a term looks like.

Of course, you've not said ANYTHING else about the behavior of ADT Poly...
you've just attempted to describe how to add two Polys...   OK...  So,
let's just look at ADDITION...

6. Just to begin with, your Base Case fails...    Consider:   x^2 + x^2
Your Base Case doesn't even apply...

7. So, let me suggest that we REJECT ALL the details of your case 
analysis... But, let's KEEP the idea of doing case analysis...  That 
DEFINITELY IS a good idea...

8. Consider two Poly's, P1 and P2:   P1 = aX1 + bX2 + cX3 + ...
and    P2 = gY1 + hY2 + iY3 + ...

where the a,b,c,...  and g,h,i,...   are numeric coefficients...
and the X1, X2, X3,...   and  Y1, Y2, Y3,...   are powers of X and Y,
respectively, IN DECREASING ORDER WITH NO DUPLICATIONS, as you've 
already said...  i.e., these two Poly's are in "standard form"
according to mathematics...

Now, we want to add P1 + P2, arriving at a sum:  P3 = P1 + p2;

In order to do this, RECURSIVELY, we must consider what the Base
Case(s) might be...   Let's call the addition operator ADDPOLY...
So,   P3 = ADDPOLY (P1, P2);
And, let's assume that we're going to represent Poly's as list
structures as required in the assignment...   Then, since we 
know about the ADT "List" we also know that we can define functions,
Head (List)  that yields a copy of the first node in the list
Tail (List)  that yields a copy of the remainder of a list, after
             the first node has been removed

Let's see if we can't now formulate a recursive definition of ADDPOLY...

ADDPOLY (P1, P2) =

   if (P1 == NULL)
      then ADDPOLY = P2

   else if (P2 == NULL)
      then ADDPOLY = P1

   else
      ADDPOLY = ADDPOLY ( (Head (P1) + P2), (Tail (P1) + P2) )

where the + signs in the above are NOT ADDPOLY calls...
Each of these + signs is ADDTERM2POLY (Term, Poly) -- a subfunction
that attempts to add a Term to a Poly

ADDTERM2POLY (T1, P1) =

   if (T1 == NULL)
      then ADDTERM2POLY = P1

   else if (P1 == NULL)
      then ADDTERM2POLY = Poly (T1)   (create a Poly from a single Term)

   else
      ADDTERM2POLY = ADDTERM ( T1, Head (P1) ) + ADDTERM2POLY ( T1, Tail (P1) )

where the + sign above this time means ADDPOLY -- because the things on
each side of the + are Poly's...

ADDTERM (T1, T2) = 

   if (T1 == NULL)
      ADDTERM = Poly (T2)     (create a Poly from a single Term, T2)
   else if (T2 == NULL)
      ADDTERM = Poly (T1)     (ditto)
   else if (exponent(T1) == exponent(T2))
      ADDTERM = (coef(T1) + coef(T2) X ^ (exponent(T1)
   else if (exponent(T1) > exponent(T2)
      ADDTERM = Poly ( T1, T2 )   (create a Poly from two Terms:  T1, T2)
   else
      ADDTERM = Poly ( T2, T1 )   (create a Poly from two Terms:  T2, T1)

Now, I just typed these things off the top of my head...   using 
Divide and Conquer thinking...    and recursion...    And, there easily
may be an error or two lurking about...   BUT, you ought to see the
principles...   No rocket science...  Just straightforward simple clean
thinking... planning...  No routine is terribly long... or complex... or
hard... 

In fact, almost all the routines do "practically nothing" except bit off
a TINY LITTLE PIECE to chew on... and then defer the rest to recursion...

And, the ONLY routine that really does ANYTHING is the one that actually
adds two terms together...   and that one you understand already quite
well...

9. So, THAT is a "DESIGN" for ADDITION...   using recursion...   Of course,
it's not the only possibility...   But, it's pretty straightforward...  
simple... and likely can be made to work quite well...   AND, it's in
terms of ADTs... NOT Java...   

10. So, you can translate this design into Java if you wish...

11. BUT, is ADDITION the right thing to start with?   Personally, I THINK NOT!
I am MUCH more interested in being able to OUTPUT a Poly...   THEN I can
see what I have...  Properly formatted...   easy to write, easy to read...

12. ONLY THEN would I consider addition...    But, before ADDITION, I'd
think about creating a couple Poly constructors...   So that I can test
my OUTPUT overloads...   AND, by the way, once I have a couple Poly
constructors...  I can use them as the "inputs" for my growing overloads
of the addition operator...

Have fun !!

-Bary-


============================


DATA STRUCTURE:

A polynomial is an ADT where one of its data members is a
pointer of type Term, pHead, that points to the beginning of a
forward-directed, single-linked list consisting of Terms.
Terms in linked list are in decreasing order w.r.t. their data
field nPower.

The data structure of type Term follows:

class Term {
    int  nCoefficient,
         nPower;

    Term pNextTerm;
}

When a polynomial is instantiated, by default, its data member pHead points to
only 1 Term.  The data fields of this Term are set to 0, 0 and NULL,
respectively.


POLYNOMIAL ADDITION/SUBTRACTION:

1)  2 Polynomials can be added/subtracted when their like-terms, nPower fields
    are the same.  nCoefficients of both terms are added/subtracted then stored
    at the position of the Term pointer, pTerm, in the Resulting Polynomial.

    CASES TO CONSIDER
    BASE CASE:  Occurs when both nPower data fields of Poly1 and Poly2 are 0.
                Both nCoefficients are added to one another,
                then stored at the Term at pTerm.
                pTerm is returned to NULL.
                Addition/subtraction is completed, and Resultant Polynomial.
                Resulting Polynomial is returned to calling function.

    CASE 2:     Occurs when both nPower data fields of Poly1 and Poly2 are
                the same.
                Both nCoefficients are added to one another,
                then stored at the Term of pTerm.
                Each of Poly1's and Poly2's head Terms are deleted.
                Resultant Polynomial is given a new Term at the end of its
                list.  (This term will be used for the next Term
                addition/subtraction operation).
                Poly1 + Poly2 is executed again (a recursive call to itself).

    CASE 3:     Occurs when
                nPower data field of Poly1 > nPower data field of Poly2.
                nCoefficient of Poly1 is stored at the Term of pTerm.
                Poly1's head Term is deleted.
                Resultant Polynomial is given a new Term at the end of its
                list.  (This term will be used for the next Term
                addition/subtraction operation).
                Poly1 + Poly2 is executed again (a recursive call to itself).

    CASE 4:     Occurs when
                nPower data field of Poly1 < nPower data field of Poly2.
                nCoefficient of Poly2 is stored at the Term of pTerm.
                Poly2's head Term is deleted.
                Resultant Polynomial is given a new Term at the end of its
                list.  (This term will be used for the next Term
                addition/subtraction operation).
                Poly1 + Poly2 is executed again (a recursive call to itself).

