By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
454,603 Members | 1,422 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 454,603 IT Pros & Developers. It's quick & easy.

Polynomials in C++

P: 2
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
Nov 14 '06 #1
Share this Question
Share on Google+
2 Replies


100+
P: 145
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:

Expand|Select|Wrap|Line Numbers
  1. class Polynomial
  2. {
  3.  private:
  4.   int degree;
  5.   double* coefficients;
  6.  public:
  7.   Polynomial();
  8.   ~Polynomial();
  9.   bool SetDegree( int NewDegree );
  10.   int GetDegree( void );
  11.   bool SetCoefficient( int term, double entry );
  12.   double GetCoefficient( int term );
  13.  
  14.   double Evaluate( double x );
  15.   bool display( void );
  16. };
  17.  
  18. Polynomial::Polynomial()
  19.  degree = 0;
  20.  coefficients = new double [degree+1];
  21.  for( int i=0; i <= degree ; i++ )
  22.  { coefficients[i] = 0; }
  23. }
  24.  
  25. Polynomial::~Polynomial()
  26. {
  27.  delete [] coefficients;
  28.  
  29. bool Polynomial::SetDegree( int NewDegree )
  30. {
  31.  delete [] coefficients;
  32.  degree = NewDegree;
  33.  coefficients = new double [degree+1];
  34.  for( int i=0; i <= degree ; i++ )
  35.  { coefficients[i] = 0; }
  36.  return true;
  37. }
  38.  
  39. int Polynomial::GetDegree( void );
  40. { return degree; }
  41.  
  42. bool Polynomial::SetCoefficient( int term, double entry )
  43. {
  44.  if( term > degree || term < 0 )
  45.  { return false; } 
  46.  coefficients[term] = entry;
  47.  return true;
  48. }
  49.  
  50. double Polynomial::GetCoefficient( int term )
  51. {
  52.  if( term > degree || term < 0 )
  53.  { return 0.0; } 
  54.  return coefficients[term];
  55. }
  56.  
  57. double Polynomial::Evaluate( double x )
  58. {
  59.  double output = 0.0; 
  60.  for( int i=degree ; i >= 0 ; i-- )
  61.  { 
  62.   output *= x;
  63.   output += coefficients[i];
  64.  }
  65.  return output;
  66. }
  67.  
  68. bool Polynomial::display( void )
  69. {
  70.  for( int i=0 ; i <= degree ; i++ )
  71.  {
  72.   cout << coefficients[i] << "x^" << i;
  73.   if( i % 5 == 0 )
  74.   { cout << endl; }
  75.   else
  76.   { cout << "\t"; }
  77.  }
  78.  cout << endl;
  79.  return true;
  80. }
  81.  
Nov 14 '06 #2

100+
P: 145
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:

Expand|Select|Wrap|Line Numbers
  1.  public:
  2.   ...
  3.  Polynomial( Polynomial& Input );
  4.   ...
  5. };
  6.  
  7. Polynomial::Polynomial( Polynomial& Input )
  8. {
  9.  degree = Input.GetDegree();
  10.  coefficients = new double [degree+1];
  11.  for( int i=0 ; i <= degree ; i++ )
  12.  { coefficients[i] = Input.GetCoefficient(i); }
  13. }
  14.  
You can then add operators to add and subtract polynomials, etc. Using the operator() for evaluation might be nice, too. e.g.,

Expand|Select|Wrap|Line Numbers
  1. double Polynomial::operator()( double x )
  2. {
  3.  return Evaluate(x);
  4. }
  5.  
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

Expand|Select|Wrap|Line Numbers
  1. Sample use:
  2.  
  3. // Here's the polynomial 1 + 2x + x^2;
  4.  
  5. Polynomial P;
  6. P.SetDegree(2);
  7. P.SetCoefficient(0,1);
  8. P.SetCoefficient(1,2);
  9. P.SetCoefficient(2,1);
  10.  
  11. P.display();
  12.  
  13. cout << "P(1) should be 4: " << P(1) << endl;
  14.  
  15. // remind me what the coefficient of x is again:
  16.  
  17. cout << "coefficient of x: " << P.GetCoefficient(1) << endl;
  18.  
  19.  
Nov 14 '06 #3

Post your reply

Sign in to post your reply or Sign up for a free account.