Polynomials in C++

[dicapryl]

Hi all! I'm new to here .. so please excuse me if my questions are unclear etc :)

I am trying to store polynomials in C++ using linked lists.
My class is called Polynomial and i've created a structure that represents each term in the polynomial (a node in the linked list). A node is called 'term'.
However, I am having a problem visualizing how to link all these 'term's together to create a 'Polynomial' that i can actually call.
I can add terms, delete terms etc from a single list, but when it comes to dealing with a Polynomial object passed in to some function, I have problems breaking it into its 'term's.

In essence, its the constructor and actually building the list to call it a Polynomial object that is giving be problems.

I thought of making the Polynomial object point to the head of the list?
Does that make sense? Any suggestions from anyone :)?

~Thanks a lot.

-dicapryl

[macklin01]

Hi all! I'm new to here .. so please excuse me if my questions are unclear etc :)

I am trying to store polynomials in C++ using linked lists.
My class is called Polynomial and i've created a structure that represents each term in the polynomial (a node in the linked list). A node is called 'term'.
However, I am having a problem visualizing how to link all these 'term's together to create a 'Polynomial' that i can actually call.
I can add terms, delete terms etc from a single list, but when it comes to dealing with a Polynomial object passed in to some function, I have problems breaking it into its 'term's.

In essence, its the constructor and actually building the list to call it a Polynomial object that is giving be problems.

I thought of making the Polynomial object point to the head of the list?
Does that make sense? Any suggestions from anyone :)?

~Thanks a lot.

-dicapryl

Hi, and welcome!

In my opinion, linked lists aren't ideal for this. Really, you only need an array of coefficients, which puts them all adjacent in memory. I'd go with a class instead. Remember: all that's important for a polynomial are the coefficients, as well as how to evaluate it. Something like this:

class Polynomial
{
 private:
  int degree;
  double* coefficients;
 public:
  Polynomial();
  ~Polynomial();
  bool SetDegree( int NewDegree );
  int GetDegree( void );
  bool SetCoefficient( int term, double entry );
  double GetCoefficient( int term );
 
  double Evaluate( double x );
  bool display( void );
};
 
Polynomial::Polynomial()
{ 
 degree = 0;
 coefficients = new double [degree+1];
 for( int i=0; i <= degree ; i++ )
 { coefficients[i] = 0; }
}
 
Polynomial::~Polynomial()
{
 delete [] coefficients;
} 
 
bool Polynomial::SetDegree( int NewDegree )
{
 delete [] coefficients;
 degree = NewDegree;
 coefficients = new double [degree+1];
 for( int i=0; i <= degree ; i++ )
 { coefficients[i] = 0; }
 return true;
}
 
int Polynomial::GetDegree( void );
{ return degree; }
 
bool Polynomial::SetCoefficient( int term, double entry )
{
 if( term > degree || term < 0 )
 { return false; } 
 coefficients[term] = entry;
 return true;
}
 
double Polynomial::GetCoefficient( int term )
{
 if( term > degree || term < 0 )
 { return 0.0; } 
 return coefficients[term];
}
 
double Polynomial::Evaluate( double x )
{
 double output = 0.0; 
 for( int i=degree ; i >= 0 ; i-- )
 { 
  output *= x;
  output += coefficients[i];
 }
 return output;
}
 
bool Polynomial::display( void )
{
 for( int i=0 ; i <= degree ; i++ )
 {
  cout << coefficients[i] << "x^" << i;
  if( i % 5 == 0 )
  { cout << endl; }
  else
  { cout << "\t"; }
 }
 cout << endl;
 return true;
}
 

[macklin01]

I had hoped to append this to my post, but ran out of time.

There should be a copy constructor, too, in the public: section:

 public:
  ...
 Polynomial( Polynomial& Input );
  ...
};
 
Polynomial::Polynomial( Polynomial& Input )
{
 degree = Input.GetDegree();
 coefficients = new double [degree+1];
 for( int i=0 ; i <= degree ; i++ )
 { coefficients[i] = Input.GetCoefficient(i); }
}
 

You can then add operators to add and subtract polynomials, etc. Using the operator() for evaluation might be nice, too. e.g.,

double Polynomial::operator()( double x )
{
 return Evaluate(x);
}
 

All polynomial operations should be regarded as operations on coefficients, so it makes sense to store and manipulate the coefficients.

Please let me know if you have any problems here, as I just wrote this off the top of my head and haven't had a chance to test. (I'm only worried about the copy constructor. ;)) Thanks -- Paul

Sample use:
 
// Here's the polynomial 1 + 2x + x^2;
 
Polynomial P;
P.SetDegree(2);
P.SetCoefficient(0,1);
P.SetCoefficient(1,2);
P.SetCoefficient(2,1);
 
P.display();
 
cout << "P(1) should be 4: " << P(1) << endl;
 
// remind me what the coefficient of x is again:
 
cout << "coefficient of x: " << P.GetCoefficient(1) << endl;