Polynomials with linked lists

[johndory]

Hello,
I really need your help.
I am writing a program to create a polynomial using linked list. The program is to perform different operations such as addition, subtraction, multiplication. I am however having problems setting the coefficients of this polynomial. I have an idea on how to implement the operations but i'm having problem setting the coefficient.
e.g for a polynomial as 3x^2 + 5x + 1. i have to set the coefficients as
p.set(0, 1)
p.set(1, 5)
p.set(2, 3).
poly p(2) to represent a second order polynomial.

Below is the code that i have written so far. I am having a bunch of errors which i have posted below the code. any help or assistance is greatly appreciated.

//Header file
# include <iostream>
using namespace std;
class Lnode{
public:
	Lnode();
	Lnode(int, double);
	double coefficient;
	int exponent;
	Lnode *next;
};
Lnode::Lnode(){
	coefficient = 0.0;
	exponent = 0;
	next = NULL;
}
Lnode::Lnode(int exp, double coef){
	coefficient = coef;
	exponent = exp;
	next = NULL;
}

class poly{
public:
	poly();
	poly(int);
	void setCoef(int exp, double coef);
	void print();

private:
	int size;
	Lnode *head, *tail;
	
};

# include <iostream>
# include "Polynomials.h"
using namespace std;

poly::poly(){
	head = tail = NULL;
}
poly::poly(int n){
	int i;
	for(i=0; i<=n+1; i++)
		Lnode *newnode = new Lnode;
}
void poly::setCoef(int exp, double coef){
	Lnode *newnode = new Lnode(exp, coef);
	newnode->next = head;
	head = newnode;
	if (tail==NULL)
		tail = head;
	size++;
}


void poly::print(){
	Lnode *current;
	current = head;
	while(current != NULL){
		cout<<current->coefficient<<"x^"<<current->exponent<<" ";
		current = current->next;
	}
}

//Test File

# include <iostream>
# include "Polynomials.h"
# include "poly.cpp"
using namespace std;

void main() {
	poly p(3);
	a.setCoef(0,1.1);
	a.setCoef(1,2.1);
	a.print();
}

// i set my coefficients to double and not integer as i put above.
These are the error that i am getting:

Error 1 error C2011: 'Lnode' : 'class' type redefinition
Error 2 error C2027: use of undefined type 'Lnode'
Error 3 error C2059: syntax error : ')'
Error 4 error C2143: syntax error : missing ';' before '{'
Error 5 error C2447: '{' : missing function header (old-style formal list?)
Error 6 error C2027: use of undefined type 'Lnode'
Error 7 error C2062: type 'int' unexpected
Error 8 error C2143: syntax error : missing ';' before '{'
Error 9 error C2447: '{' : missing function header (old-style formal list?)
Error 10 error C2011: 'poly' : 'class' type redefinition
Error 11 error C2027: use of undefined type 'poly'
Error 12 error C2059: syntax error : ')'
Error 13 error C2143: syntax error : missing ';' before '{'
Error 15 error C2027: use of undefined type 'poly'
Error 16 error C2062: type 'int' unexpected
Error 17 error C2143: syntax error : missing ';' before '{'
Error 18 error C2447: '{' : missing function header (old-style formal list?)
Error 19 error C2027: use of undefined type 'poly'
Error 20 error C2027: use of undefined type 'Lnode'
Error 21 error C2227: left of '->{ctor}' must point to class/struct/union/generic type

Please, please help me. Thank you in advance for your help.

[VernonDozier]

Let's look at your polynomial class. For now, I'm ignoring the Linked List part:

class poly{
public:
	poly();
	poly(int);
	void setCoef(int exp, double coef);
	void print();

private:
	int size;
	Lnode *head, *tail;
	
};

Ignoring the linked list pointers you have one data member: size. How can one represent a polynomial with that? Looking at your Lnode class:

class Lnode{
public:
	Lnode();
	Lnode(int, double);
	double coefficient;
	int exponent;
	Lnode *next;
};

it appears that you have something to do with polynomials in that class (coefficient and exponent). So what does the poly class do if it doesn't store polynomials?

[johndory]

Thank you very much for taking the time out to reply me. However, i must be really dumb as i still do not understand what i am supposed to do.

Let's look at your polynomial class. For now, I'm ignoring the Linked List part:

class poly{
public:
	poly();
	poly(int);
	void setCoef(int exp, double coef);
	void print();

private:
	int size;
	Lnode *head, *tail;
	
};

Ignoring the linked list pointers you have one data member: size. How can one represent a polynomial with that? Looking at your Lnode class:

class Lnode{
public:
	Lnode();
	Lnode(int, double);
	double coefficient;
	int exponent;
	Lnode *next;
};

it appears that you have something to do with polynomials in that class (coefficient and exponent). So what does the poly class do if it doesn't store polynomials?

[VernonDozier]

What you need to do is, before starting to code, get a picture in your mind of how a polynomial is stored. Take the polynomial you displayed in your original post:

3x^2 + 5x + 1

What do you need to store for this polynomial and where do you want to store it? You need to store the 3, the 5, and the 1 coefficients somewhere. You should probably also store the fact that it is a polynomial of degree 2. It seems to me that you are trying to do that with the poly data member called size.

I don't know what the linked list is supposed to do. Can you elaborate? Unless you are somehow supposed to store each coefficient of the polynomial in a separate node (rarely done I would imagine), most likely you are expected to store all the above data (the coefficients and the degree) in the poly class. Currently you are only storing size, which I am assuming is the degree of th polynomial. So do you want to store all the information about the polynomial in a single object of type poly (this is normally how it is done)?

[johndory]

Thanks again for your help. I sorry to bother you. So, are you stating that i should put the double coefficient and int exponent in the poly class. I am supposed to create a polynomial using linked list and i think that i am trying to store each coefficient separately in a node and link them together. maybe i'm wrong, but is there a way that i can do what you described below while still using the linked list?
please help.

What you need to do is, before starting to code, get a picture in your mind of how a polynomial is stored. Take the polynomial you displayed in your original post:

3x^2 + 5x + 1

What do you need to store for this polynomial and where do you want to store it? You need to store the 3, the 5, and the 1 coefficients somewhere. You should probably also store the fact that it is a polynomial of degree 2. It seems to me that you are trying to do that with the poly data member called size.

I don't know what the linked list is supposed to do. Can you elaborate? Unless you are somehow supposed to store each coefficient of the polynomial in a separate node (rarely done I would imagine), most likely you are expected to store all the above data (the coefficients and the degree) in the poly class. Currently you are only storing size, which I am assuming is the degree of th polynomial. So do you want to store all the information about the polynomial in a single object of type poly (this is normally how it is done)?

[VernonDozier]

Well it is certainly possible. Taking your polynomial:

3x^2 + 5x + 1

I suppose you could store it as a linked list like this:

1 ---> 5 ---> 3 or like this:

3 ---> 5 ---> 1

Either could work. For sake of argument, let's assume the former. The front of the list is the coefficient of x^0. Perhaps you could define a coefficient class like this:

class coefficient
{
private:                 // only listing the data members here
     double coeff;
     coefficient* nextCoefficient;
     coefficient* prevCoefficient;
};

Then a poly class like this:

class poly
{
private:        // only listing the data members here
     int size;   // I assume this is the polynomial degree?
     coefficient* zeroCoefficient;
};

Something like this maybe? So for the above polynomial, you would call a constructor in the poly class and pass that constructor the degree and coefficients of the polynomial. This poly constructor would create 3 coefficient nodes (degree of polynomial + 1 since that's how many coefficients there would be). After creating the three coefficient nodes, zeroCoefficient would point to the node containing the coefficient of x^0.

Is that what you have in mind?

[Lerner]

This polynomial: 3x^2 + 5x + 1 could also be written like this: 3x^2 + 5x^1 + 1x^0. This suggests that the polynomial could written as a series of terms with 3x^2, 5x^1, and 1x^0 each being one term. Each term would have a coefficient, a variable (which must the same for each term for now), and an exponential value of the variable. The whole polynomial could then be thought of as a collection of terms. That collection could be a string (as above) or an array of terms or as a list of terms, etc. In your case you seem to want a list of terms. So be it.

With a list you need to know a certain amount of information. At minimum you want to know where to start. The first node/link in a list is frequently called the head node/link. Each list must have a known head node, but that's it. Everything else is fluff. Nice fluff usually. But fluff nonetheless. For example, frequently people like to keep track of the last node in a list and they frequently call that the tail. In addition, it is sometimes useful to know how many nodes/links there is in the list.

Knowing all this I would be tempted to do something like this:

struct Term
  char variable
  double coefficient
  int exponent
  Term * next

struct Polynomial
   Term * head
   Term * tail
   int size

Now, size here may represent the number of terms in the polynomial or it could represent the degree of the polynomial, since the two are related by the following: if all terms of a polynomial are including in the collection of terms, even if the coefficient is zero, then the degree of the polynomial is one less than the number of terms.

To be more useful, each of the above user defined types could be expanded by adding a variety of methods to do things. For example, a default constructor of the type Term could set the coefficient and exponent to zero and the variable to x. A non-default constructor for Polynomial could be passed either the size or the degree of the polynomial and that information could be used to declare enough nodes to represent all the Terms of the Polynomial. Another method of Polynomial could be used to set each coefficient and exponent of every term in the polynomial. In this method, call it set(), the first parameter could be an int. This int could be used to control a loop to determine how far away from head you go to set the member values of the term indicated. The int could also represent the exponent of the term. The second parameter would be a double and it would be assigned to the coefficient of the term. Maybe a third method would print the polynomial from head to tail. Under this scenario however, the terms would be displayed from lowest exponent to highest. So maybe adding a second pointer to type in Term, thereby changing the list representing the polynomial from singly linked to doubly linked, would be a possibility. This would make it easy to print the list from tail to head thereby allowing display of the polynomial in the usual highest to lowest order based on the polynomial term exponents. Of course, if this orgainization doesn't fit well, there are other ways to do it, too. Addition and subtraction now becomes addition and subtraction of coefficients whose term has the same variable and exponent. Multiplcation becomes a nested loop creating a large number of terms some of which have the same exponents so the coefficients of like terms can be added to reduce the form of the coefficient. The resultant polynomial representing the product of the two original polynomials will need to have it's degree/size calculated by one protocol or another, since it's not provided by the user, but that shouldn't be too much of a bother to figure out.

[johndory]

Thank you for replying. so, i don't want to be a bug but i'm kinda slow. the operations are not hard to figure out, it's just the setting of the coefficients. i have never really used struct before.
i don't want to use a constructor to set the coefficient. i want to use a constructor for the degree..like poly p(3) where p is a 3rd order polynomial.
i want to set the coefficient like p.set(0, 1), p.set(1, 5), p.set(2, 3) for 3x^2+5x+1.
This has been my problem for about a week now. this has been holding me back from completing the rest of my assignment.

I do appreciate your help and i'll understand if you cannot help me any further.
thanks.

[VernonDozier]

Well that's fine. You can use the constructor to set the degree. One thing you have to decide is whether to store all coefficients, even the zero coefficients, or only store the non-zero coefficients. If you don't store all of the coefficients, you will have to store the exponents as well as the coefficients in the nodes, as Lerner did here:

struct Term
  char variable
  double coefficient
  int exponent
  Term * next

If not, if you store all coefficients, including 0's, mine would work:

class coefficient
{
private:                 // only listing the data members here
     double coeff;
     coefficient* nextCoefficient;
     coefficient* prevCoefficient;
};

Either way works, but pick one or a combination of the two (i.e. store zeroes but store both coefficient and exponent. I like his terms head and tail and using the word "Term" as the class name might be more descriptive. I also like the idea of a doubly linked list rather than a singly linked list. So revising my class into something more along the lines of Lerner's, you'd get this:

class Term
{
private:                 // only listing the data members here
     double coeff;
     int exponent;
     Term* next;
     Term* prev;
};

class Poly
{
private:                  // only listing data members
     int degree;
     Term* head;
     Term* tail;
};

Before coding or creating constructors, etc., you'll need to decide whether to store the 0 coefficients or not. Regardless of whether you do, it probably couldn't hurt to have the exponent stored too even though one can figure it out. It may make later calculations easier and it absolutely cannot hurt. The decision you pick regarding whether to store 0 coefficients will affect how you code so it's best to pick one or the other now. Either will work. I prefer storing the 0 coefficient, but that's personal preference. Can't really suggest more until you pick your class data members since the code will be designed around them.

[johndory]

hi,
thanks for not giving up on me. i understand what u have written, it makes perfect sense;however, when i try to put what i have visualized on paper and write the code, i get lost.
so, if it's not too much to ask, please please please, can u show me how to set the coefficients and the degree like i have described.
also, is it really necessary to use a doubly linked list. moreover, u kept writing 0 coefficients, do u mean zero exponents? if so, i would like to do it your way i.e including the zero exponent.

thanks.

[VernonDozier]

No, you do not need to use a doubly linked list. A singly linked list will do. I was just thinking that possibly there might later be a point when a doubly linked list makes things easier and/or more efficient. But no, you do not need one.

I'm speaking of 0 coefficients. Think of an example like this:

6x^4 + 8x^2 - x

You can rewrite this as:
6x^4 + 0x^3 + 8x^2 - 1x^1 + 0x^0

So your linked list would be this (assuming starting with the x^0 coefficient):

0 ---> -1 ---> 8 ---> 0 ---> 6

The zeroes above were what I was referring to in the last post. So if you decide to go the singly linked list route, your classes would change to something like this:

class Term
{
public:  // member functions
     void SetTerm (double coefficient, int exp);
     Term* GetNext ();   // returns data member next

private: // data members
     double coeff;
     int exponent;
     Term* next;
};

class Poly
{
public: // member functions
     void SetPoly (double coefficients[]);  // assume have degree + 1 coefficients

private: // data members
     int degree;
     Term* head;
};

This is assuming that the Poly constructor has already been called and the Term nodes have been created and that degree has been set, as well as head, and that you ARE in fact storing the 0 coefficients. The SetPoly function might be like this:

void Poly::SetPoly (double coefficients[]);  // assume have degree + 1 coefficients
{
     Term* currentTerm = head;
     for (int i = 0; i <= degree; i++)
    {
         currentTerm->SetTerm (coefficients[i], i);
         currentTerm = currentTerm->GetNext ();
    }
}

All of this is assuming that all constructors have been called, linked list has been created correctly, and GetNext and SetTerm functions have been written. I think this is in line with the way you are wanting to design your program.

To call this function, do something like this:

Poly p (4);   // 4th degree polynomial.  call to constructor.
double coeffarray = {0.0, -1.0, 8.0, 0.0, 6.0};  // typo earlier
p.SetPoly (coeffarray);

[johndory]

Thank you very much. i really appreciate it.
i have one more question, what if i do not want to have the zero coefficients??? also, this can work even if there are no zero coefficients rite???
thank u, thank u, thank u..

No, you do not need to use a doubly linked list. A singly linked list will do. I was just thinking that possibly there might later be a point when a doubly linked list makes things easier and/or more efficient. But no, you do not need one.

I'm speaking of 0 coefficients. Think of an example like this:

6x^4 + 8x^2 - x

You can rewrite this as:
6x^4 + 0x^3 + 8x^2 - 1x^1 + 0x^0

So your linked list would be this (assuming starting with the x^0 coefficient):

0 ---> -1 ---> 8 ---> 0 ---> 6

The zeroes above were what I was referring to in the last post. So if you decide to go the singly linked list route, your classes would change to something like this:

class Term
{
public:  // member functions
     void SetTerm (double coefficient, int exp);
     Term* GetNext ();   // returns data member next

private: // data members
     double coeff;
     int exponent;
     Term* next;
};

class Poly
{
public: // member functions
     void SetPoly (double coefficients[]);  // assume have degree + 1 coefficients

private: // data members
     int degree;
     Term* head;
};

This is assuming that the Poly constructor has already been called and the Term nodes have been created and that degree has been set, as well as head, and that you ARE in fact storing the 0 coefficients. The SetPoly function might be like this:

void Poly::SetPoly (double coefficients[]);  // assume have degree + 1 coefficients
{
     Term* currentTerm = head;
     for (int i = 0; i <= degree; i++)
    {
         currentTerm->SetTerm (coefficients[i], i);
         currentTerm = currentTerm->GetNext ();
    }
}

All of this is assuming that all constructors have been called, linked list has been created correctly, and GetNext and SetTerm functions have been written. I think this is in line with the way you are wanting to design your program.

To call this function, do something like this:

Poly p (4);   // 4th degree polynomial.  call to constructor.
double coeffarray = {0.0, -1.0, 8.0, 0.0, 6.0};  // typo earlier
p.SetPoly (coeffarray);

[VernonDozier]

It will certainly work if you have no 0 coefficients. It can be made to work without storing the 0 coefficients, but it would have to be tweaked. Let's look at it...

void Poly::SetPoly (double coefficients[])  // assume have degree + 1 coefficients
{
     Term* currentTerm = head;
     for (int i = 0; i <= degree; i++)
    {
         currentTerm->SetTerm (coefficients[i], i);
         currentTerm = currentTerm->GetNext ();
    }
}

The assumption here is that there are degree + 1 nodes in the linked list. If you are not storing the 0 coefficients, that assumption no longer holds. However in your Term constructor, the "next" data member of the last term will point to NULL (you must design your linked list this way). That can tell us when there are no more terms and thus when to bail out of the loop. So something like this:

void Poly::SetPoly (double coefficients[]) 
{
     Term* currentTerm = head;
     int i = 0;
     while (currentTerm != NULL)
    {
         if (coefficients[i] != 0.0)
         {
              currentTerm->SetTerm (coefficients[i], i);
              currentTerm = currentTerm->GetNext ();
         }
         i++;
    }
}

One note of caution. It can be very dangerous to use the "!=" operator when comparing a double to a value, as I did above. Normally you use less than and greater than comparisons when comparing doubles. Thus you may want to consider storing the 0 coefficients or having some way of flagging the double as exactly 0. Floating point arithmetic rounding errors can be tricky. 0 might be stored as 0.00000000001 or something and screw up the equality operator test. That aside, if you do not store the 0 coefficients, your linked list for the following polynomial...

6x^4 + 0x^3 + 8x^2 - 1x^1 + 0x^0

would be this:

(-1.0, 1) ---> (8.0, 2) ---> (6.0, 4)

where the ordered pair represents the coefficient, then the exponent. In this case you would have three nodes rather than five, yet the degree would still be 4.

Please not the mistaken semicolon in the function implementation from last post. It has been corrected in this post.

[VernonDozier]

The previous post's solution has at least one possible drawback. What if the number of coefficients with 0 values changes? You would need to insert and delete nodes. You may end up needing to do that anyway regardless of whether you store the 0 coefficients or not. Thus treat the code I suggested as a skeleton of these classes rather than set in stone. Change as needed. You may consider storing the number of nodes in Poly as well as degree. You may also consider passing the SetPoly function a new degree as well as new coefficients. Lots of ways to do it.

[johndory]

i think i've bugged u enough; thanks anyway.
ok, i have one last question, really this time. in the Term class, there is the function setTerm.
is this just assigning variables like coefficient = coef.. something like that or this is a different procedure. if u could show me please. ...
thank u very much. u do not know how much i really appreciate ur help..
thanks again

The previous post's solution has at least one possible drawback. What if the number of coefficients with 0 values changes? You would need to insert and delete nodes. You may end up needing to do that anyway regardless of whether you store the 0 coefficients or not. Thus treat the code I suggested as a skeleton of these classes rather than set in stone. Change as needed. You may consider storing the number of nodes in Poly as well as degree. You may also consider passing the SetPoly function a new degree as well as new coefficients. Lots of ways to do it.

[VernonDozier]

i think i've bugged u enough; thanks anyway.
ok, i have one last question, really this time. in the Term class, there is the function setTerm.
is this just assigning variables like coefficient = coef.. something like that or this is a different procedure. if u could show me please. ...
thank u very much. u do not know how much i really appreciate ur help..
thanks again

It's simply setting the private data members to the values passed to the function. Since the data members are private, you need to write "Set" and "Get" functions to change/mutate them and to access their values, respectively. It's simply a function like this:

void Term::SetTerm (double coefficient, int exp)
{
     coeff = coefficient;
     exponent = exp;
}

[johndory]

Thanks a lot. i know i said that that was the last question but i had one question about the getnext() function. what is its use??? why can't term->next be used? or is this what it is going to return. please help me write it. i am really sorry for all the trouble.

It's simply setting the private data members to the values passed to the function. Since the data members are private, you need to write "Set" and "Get" functions to change/mutate them and to access their values, respectively. It's simply a function like this:

void Term::SetTerm (double coefficient, int exp)
{
     coeff = coefficient;
     exponent = exp;
}

[VernonDozier]

Thanks a lot. i know i said that that was the last question but i had one question about the getnext() function. what is its use??? why can't term->next be used? or is this what it is going to return. please help me write it. i am really sorry for all the trouble.

class Term
{
public:  // member functions
     void SetTerm (double coefficient, int exp);
     Term* GetNext ();   // returns data member next

private: // data members
     double coeff;
     int exponent;
     Term* next;
};

It has to do with the word "private" above. "next" is private in the class declaration above. GetNext is public. GetNext was called from inside SetPoly in my example. SetPoly is NOT a member function of the Term class. As such, it cannot access Term's private data members or Term's private member functions directly. It must use some "public" method from Term. That's what "Get" and "Set" functions are for. Change the word "private" to "public" above and you COULD get "next" directly from SetPoly as you wanted to by doing this:

currentTerm = currentTerm->next;

rather than this:

currentTerm = currentTerm->GetNext ();

However, since it is private, you must get it from a call to a public member function of the Term class like GetNext. GetNext is a very simple function:

Term* Term::GetNext ()
{
     return next;
}

In general, always make your data members private and your "Get" and "Set" functions public.

[johndory]

wow, u have been such a great help. i truly appreciate it. however, the more u help me, the more questions i have unanswered. i'm a little bit lost on how to set the degree. any hints?. but i really do appreciate all your help. is there a way points can be awarded coz u deserve them.

class Term
{
public:  // member functions
     void SetTerm (double coefficient, int exp);
     Term* GetNext ();   // returns data member next

private: // data members
     double coeff;
     int exponent;
     Term* next;
};

It has to do with the word "private" above. "next" is private in the class declaration above. GetNext is public. GetNext was called from inside SetPoly in my example. SetPoly is NOT a member function of the Term class. As such, it cannot access Term's private data members or Term's private member functions directly. It must use some "public" method from Term. That's what "Get" and "Set" functions are for. Change the word "private" to "public" above and you COULD get "next" directly from SetPoly as you wanted to by doing this:

currentTerm = currentTerm->next;

rather than this:

currentTerm = currentTerm->GetNext ();

However, since it is private, you must get it from a call to a public member function of the Term class like GetNext. GetNext is a very simple function:

Term* Term::GetNext ()
{
     return next;
}

In general, always make your data members private and your "Get" and "Set" functions public.

[VernonDozier]

To add points to my rep, you can go to any of any of my posts and click on "Add to VernonDozier's Reputation". I've never actually done it myself yet, but you can add good points (green) or bad points (orange), as well as type in a reason. You can do this with any user and any post, regardless of whether you have posted on that thread or not and regardless of whether you have anything to do with the thread. Sometimes people just agree or disagree and adjust someone's rep accordingly.

As far as setting the degree, a simple "Set" function is about as easy as the "get" function from the last post. It can be done as a constructor function or in a different function. Again, you want your "Set" and "Get" functions public (usually you want your constructors public too). I'll show you an example of each. Since degree is a data member of the Poly class, these functions would be public members of the Poly class.

Poly::Poly (int theDegree)
{
     degree = theDegree;
}

void Poly::SetDegree (int theDegree)
{
     degree = theDegree;
}

As you can see the function contents are identical and very short. The top one is a constructor, the other one is a "Set" function. They are very short and often you have "Get" and "Set" functions for every data member, designed pretty much the same way. The SetPoly function I had set two data member values in one shot, which also works.

Can't help you much more till you post some more revised code or the moderators might get mad, and they can adjust my reputation more than you can!:) Best of luck. Feel free to post more code and ask for more help.

[fireprogramer]

can you put a complex coef instead of an integer
by using a class of complex number
pleas if you know tell me how
i have a home work : writting a polynome class with
complex coef and also by using linked lists